158  
常用经典算法(C++)
作者: 方凯 于 2018年07月10日 发布在分类 / 计算机专业 / 数据结构&算法 下,并于 2019年07月25日 编辑
算法 c++

常用算法经典代码( C++ 版)  

一、快速排序

void qsort(int x,int y) // 待排序的数据存放在 a[1]..a[n] 数组中
{
int h=x,r=y;
int m=a[(x+y)>>1]; // 取中间的那个位置的值
while(h<r){
    while (a[h]<m) 
        h++; // 比中间那个位置的值小,循环直到找一个比中间那个值大的
    while (a[r]>m) 
        r--; // 比中间那个位置的值大,循环直到找一个比中间那个值小的
    if(h<=r){
        int temp=a[h];// 如果此时 h<=r ,交换 a[h] 和 a[r]
        a[h]=a[r];
        a[r]=temp;
        h++;r--; // 这两句必不可少哦
    }
}
if(r>x) qsort(x,r);// 注意此处,尾指针跑到前半部分了
if(h<y) qsort(h,y); // 注意此处,头指针跑到后半部分了
}

调用: qsort(1,n) 即可实现数组 a 中元素有序。适用于 n 比较大的排序

二、冒泡排序

void paopao(void) // 待排序的数据存放在 a[1]..a[n] 数组中
{
for(int i=1;i<n;i++)// 控制循环(冒泡)的次数, n 个数,需要 n-1 次冒泡
     for(int j=1;j<=n-i;j++) // 相邻的两两比较
         if(a[j]<a[j+1]) {
              int temp=a[j];
              a[j]=a[j+1];
              a[j+1]=temp;
         }
}

或者


void paopao(void) // 待排序的数据存放在 a[1]..a[n] 数组中
{
    for(int i=1;i<n;i++)  // 控制循环(冒泡)的次数, n 个数,需要 n-1 次冒泡
        for(int j=n-i;j>=1;j--) // 相邻的两两比较
            if(a[j]<a[j+1]) {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
}


调用: paopao() ,适用于 n 比较小的排序

三、桶排序

void bucketsort(void)//a 的取值范围已知。如 a<=cmax 。
{
memset(tong,0,sizeof(tong));// 桶初始化
for(int i=1;i<=n;i++)// 读入 n 个数
{
int a
cin>>a;
tong[a]++;}// 相应的桶号计数器加 1

for(int i=1;i<=cmax;i++)
{
    if(tong[i]>0) // 当桶中装的树大于 0 ,说明 i 出现过 tong[i] 次,否则没出现过 i
        while (tong[i]!=0)
        {
            tong[i]--;
            cout<<i<<’ ‘;}
        }
}


桶排序适用于那些待排序的关键字的值在已知范围的排序。

四、合(归)并排序

void merge(int l,int m,int r)// 合并 [l,m] 和 [m+1,r] 两个已经有序的区间
{ 
int b[101];// 借助一个新的数组 B ,使两个有序的子区间合并成一个有序的区间, b 数组的大小要注意
int h,t,k;
k=0;// 用于新数组 B 的指针
h=l;t=m+1;// 让 h 指向第一个区间的第一个元素, t 指向第二个区间的第一个元素。
while((h<=m)&&(t<=r))// 在指针 h 和 t 没有到区间尾时,把两个区间的元素抄在新数组中
{
    k++;       // 新数组指针加 1
    if (a[h]<a[t]) {
        b[k]=a[h];h++;
    }       // 抄第一个区间元素到新数组
    else{
        b[k]=a[t];t++;
    }   // 抄第二个区间元素到新数组
}

while(h<=m){
    k++;
    b[k]=a[h];
    h++;
}  // 如果第一个区间没有抄结束,把剩下的抄在新数组中

while(t<=r){
    k++;
    b[k]=a[t];
    t++;
}   // 如果第二个区间没有抄结束,把剩下的抄在新数组中

for(int o=1;o<=k;o++)// 把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。
a[l+o-1]=b[o];
}

void mergesort(int x,int y)// 对区间 [x,y] 进行二路归并排序
{
int mid;
if(x>=y) return;
mid=(x+y)/2;// 求 [x,y] 区间,中间的那个点 mid,mid 把 x,y 区间一分为二
mergesort(x,mid);// 对前一段进行二路归并
mergesort(mid+1,y);// 对后一段进行二路归并
merge(x,mid,y);// 把已经有序的前后两段进行合并
}


归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。

五、二分查找

int find(int x,int y,int m) // 在 [x,y] 区间查找关键字等于 m 的元素下标

{ int head,tail,mid;

head=x;tail=y;mid=((x+y)/2);// 取中间元素下标

if(a[mid]==m) return mid;// 如果中间元素值为 m 返回中间元素下标 mid

if(head>tail) return 0;// 如果 x>y ,查找失败,返回 0

if(m>a[mid])  // 如果 m 比中间元素大,在后半区间查找,返回后半区间查找结果

return find(mid+1,tail);

else // 如果 m 比中间元素小,在前半区间查找,返回后前区间查找结果

return find(head,mid-1);

}


六、高精度加法


#include<iostream>

#include<cstring>

using namespace std;

int main()

{

string str1,str2;

int a[250],b[250],len;   // 数组的大小决定了计算的高精度最大位数

int i;

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

cin>>str1>>str2;   // 输入两个字符串

a[0]=str1.length();  // 取得第一个字符串的长度

for(i=1;i<=a[0];i++)  // 把第一个字符串转换为整数,存放在数组 a 中

a[i]=str1[a[0]-i]-'0';

b[0]=str2.length();   // 取得第二个字符串长度

for(i=1;i<=b[0];i++)   // 把第二个字符串中的每一位转换为整数,存放在数组 B 中

b[i]=str2[b[0]-i]-'0';

len=(a[0]>b[0]?a[0]:b[0]);   // 取两个字符串最大的长度

for(i=1;i<=len;i++)   // 做按位加法,同时处理进位

{

a[i]+=b[i];

a[i+1]+=a[i]/10;

a[i]%=10;   

}

len++;    // 下面是去掉最高位的 0 ,然后输出。

while((a[len]==0)&&(len>1)) len--;

for(i=len;i>=1;i--)

cout<<a[i];

return 0; 

}


注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。

七、高精度减法

#include<iostream>
using namespace std;
int compare(string s1,string s2);
int main()
{
string str1,str2;
int a[250],b[250],len;
int i;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>str1>>str2;
a[0]=str1.length();
for(i=1;i<=a[0];i++)
    a[i]=str1[a[0]-i]-'0';

b[0]=str2.length();
for(i=1;i<=b[0];i++)
    b[i]=str2[b[0]-i]-'0';

if((compare(str1,str2))==0)  // 大于等于,做按位减,并处理借位。
{
    for(i=1;i<=a[0];i++)
    {
        a[i]-=b[i];
        if (a[i]<0) {
            a[i+1]--;
            a[i]+=10;
        }
    }
    a[0]++;
    while((a[a[0]]==0)&&(a[0]>1)) a[0]--;
    for(i=a[0];i>=1;i--)
        cout<<a[i];
        cout<<endl; 
    }                          
}else{
cout<<'-';  // 小于就输出负号
for(i=1;i<=b[0];i++)  // 做按位减,大的减小的
{
    b[i]-=a[i];
    if (b[i]<0) {
        b[i+1]--;
        b[i]+=10;
    }
}
b[0]++;
while((b[b[0]]==0)&&(b[0]>1)) b[0]--;
    for(i=b[0];i>=1;i--)
        cout<<b[i];
    cout<<endl;
}
return 0; 
}

int compare(string s1,string s2)  // 比较字符串(两个数)数字的大小,大于等于返回 0 ,小于返回 1 。
{
if(s1.length()>s2.length()) 
return 0;  // 先比较长度,哪个字符串长,对应的那个数就大

if(s1.length()<s2.length()) return 1;

for(int i=0;i<=s1.length();i++)  // 长度相同时,就一位一位比较。
{
    if(s1[i]>s2[i]) return 0;
    if(s1[i]<s2[i]) return 1;                          
}
return 0;   // 如果长度相同,每一位也一样,就返回 0 ,说明相等
}


做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。

八、高精度乘法

#include<iostream>
#include<cstring>

using namespace std;
int main()
{
string str1,str2;
int a[250],b[250],c[500],len;    //250 位以内的两个数相乘
int i,j;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>str1>>str2;
a[0]=str1.length();
for(i=1;i<=a[0];i++)
    a[i]=str1[a[0]-i]-'0';

b[0]=str2.length();
for(i=1;i<=b[0];i++)
    b[i]=str2[b[0]-i]-'0';

memset(c,0,sizeof(c));
for(i=1;i<=a[0];i++)   // 做按位乘法同时处理进位,注意循环内语句的写法。
    for(j=1;j<=b[0];j++){
        c[i+j-1]+=a[i]*b[j];
        c[i+j]+=c[i+j-1]/10;
        c[i+j-1]%=10;   
    }

len=a[0]+b[0]+1;  // 去掉最高位的 0 ,然后输出

while((c[len]==0)&&(len>1)) len--;   // 为什么此处要 len>1??

for(i=len;i>=1;i--)
    cout<<c[i];
return 0; 
}

// 注意:两个数相乘,结果的位数应该是这两个数的位数和减 1 。
// 优化:万进制

#include<iostream>
#include<cstring>

using namespace std;
void num1(int s[],string st1);

int a[2501],b[2501],c[5002];// 此处可以进行 2500 位万进制乘法,即 10000 位十进制乘法。

Int main()
{
string str1,str2;
int len;
cin>>str1>>str2;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
num1(a,str1); // 把 str1 从最低位开始,每 4 位存放在数组 a 中
num1(b,str2); // 把 str2 从最低位开始,每 4 位存放在数组 b 中
for(int i=1;i<=a[0];i++) // 作按位乘法并处理进位,此处是万进制进位
    for(int j=1;j<=b[0];j++){
        c[i+j-1]+=a[i]*b[j];
        c[i+j]+=c[i+j-1]/10000;
        c[i+j-1]%=10000;
}

len=a[0]+b[0]; //a[0] 和 b[0] 存放的是每个数按 4 位处理的位数
while ((c[len]==0)&&(len>1)) len--;// 去掉高位的 0 ,并输出最高位
    cout<<c[len];
for(int i=len-1;i>=1;i--)// 把剩下来的每一位还原成 4 位输出
{
    if (c[i]<1000) cout<<’ 0’ ;
    if (c[i]<100) cout<<’ 0’ ;
    if (c[i]<10) cout<<’ 0’ ;        
    cout<<c[i];
}
cout<<endl;
return 0;
}
void num1(int s[],string st1)// 此函数的作用就是把字符串 st1 ,按 4 位一组存放在数组 s 中

{   
int k=1,count=1;
s[0]=st1.length();// 存放 st1 的长度,省去一长度变量
for(int i=s[0]-1;i>=0;i--) // 从最低位开始,处理每一位
{ 
    if (count%4==0) {
        s[k]+=(st1[i]-‘ 0’ )*1000;
        if(i!=0) k++;
    }
    if (count%4==1) 
        s[k]=(st1[i]-‘ 0’ );
    if (count%4==2)
        s[k]+=(st1[i]-‘ 0’ )*10;
    if (count%4==3)
        s[k]+=(st1[i]-‘ 0’ )*100;
    count++;
}
    s[0]=k; // 存放数组的位数,就是按 4 位处理后的万进制数的位数。   
    return;
}


十、筛选法建立素数表


void maketable(int x)// 建立 X 以内的素数表 prim , prim[i] 为 0 ,表示 i 为素数,为 1 表示不是质数
{
    memset(prim,0,sizeof(prim));// 初始化质数表
    prim[0]=1;prim[1]=1;prim[2]=0;// 用筛选法求 X 以内的质数表
    for(int i=2;i<=x;i++)
        if (prim[i]==0){
            int j=2*i;
            while(j<=x)
            {
                prim[j]=1;
                j=j+i;
            }
        }
}


对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。

十一、深度优先搜索


void dfs(int x)  \\ 以图的深度优先遍历为例。
{ 
    cout<<x<<‘ ‘; \\ 访问 x 顶点
    visited[x]=1; \\ 作已访问的标记
    for(int k=1;k<=n;k++) \\ 对与顶点 x 相邻而又没访问过的结点 k 进行深度优先搜索。
        if((a[x][k]==1)&&(visited[k]==0))
    dfs(k);
}


十二、广度优先搜索


void  bfs(void) // 按广度优先非递归遍历图 G , n 个顶点,编号为 1..n 。注:图不一定是连通的
{   // 使用辅助队列 Q 和访问标记数组 visited 。

    for(v=1;v<=n;v++)  
        visited[v]=0 ; // 标记数组初始化
        for(v=1; v<=n; v++)
            if(visited[v]==0 ) {      //v 尚未访问

                int h=1,r=1;    // 置空的辅助队列 q

                visited[v]=1 ; // 顶点 v, 作访问标记

                cout<<v<<‘ ‘; // 访问顶点 v

                q[r]=v ;     //v 入队列

                while(h<=r) // 当队列非空时循环
                {
                    int tmp=q[h];  // 队头元素出队,并赋值给 tmp
                    for(int j=1;j<=n;j++)
                        if((visited[j]==0)&&(a[tmp][j]==1))
                        {
                            //j 为 tmp 的尚未访问的邻接顶点
                            visited[j]=1;  对 j 作访问标记
                            cout<<j<<‘ ‘; 访问 j
                            r++; // 队尾指针加 1
                            q[r]=j; //j 入队
                        }  //end-if
                    h++;
                }//end -while
            }
}


十三、 二叉树的前序、中序和后序遍历


void preorder(int x)// 二叉树的先序遍历
{
    if(x==0) return;
    cout<<x;// 先访问根
    preorder(a[x].ld);// 再先序遍历根的左子树
    preorder(a[x].rd);// 最后先序遍历根的右子树
}

void inorder(int x)// 二叉树的中序遍历
{
    if(x==0) return;
    preorder(a[x].ld);// 先中序遍历根的左子树
    cout<<x;// 再访问根
    preorder(a[x].rd);// 最后中序遍历根的右子树
}

void reorder(int x)// 二叉树的后序遍历
{
    if(x==0) return;

    preorder(a[x].ld);// 先后序遍历根的左子树

    preorder(a[x].rd);// 再后序遍历根的右子树

    cout<<x;// 最后访问根
}


十四、树转换为二叉树算法

十五、二叉排序树

十六、哈夫曼树


void haff(void) // 构建哈夫曼树
{
    for(int i=n+1;i<=2*n-1;i++) // 依次生成 n-1 个结点
    {
        int l=fmin(i-1); // 查找权值最小的结点的编号 l
        a[i].lchild=l; // 把 l 作为结点 i 的左孩子
        a[l].father=i; // 把 l 的父结点修改为 i
        int r=fmin(i-1); // 查找次小权值的编号 r
        a[i].rchild=r; // 把 l 作为结点 i 的右孩子
        a[r].father=i; // 把 r 的父结点修改为 i
        a[i].da=a[l].da+a[r].da; // 合并 l,j 结点,生成新结点 i
    }
}

int fmin(int k)// 在 1 到 K 中寻找最小的权值的编号
{
int mins=0;
for(int s=1;s<=k;s++)
if((a[mins].da>a[s].da)&&(a[s].father==0)) //a[s].father=0, 说明这个结点还不是别个结点
mins=s;                           // 的孩子,不等于 0 说明这个结点已经用过。
return mins;
}

void inorder(int x)// 递归生成哈夫曼编码
{
    if(a[x].father==0) {
        a[x].code="";
    }// 根结点
    if(a[a[x].father].lchild==x)
        a[x].code=a[a[x].father].code+'0';
    if(a[a[x].father].rchild==x)
        a[x].code=a[a[x].father].code+'1';
    if(a[x].lchild!=0)
        inorder(a[x].lchild);// 递归生成左子树
    if((a[x].lchild==0)&&(a[x].rchild==0))// 输出叶子结点
        cout<<a[x].da<<':'<<a[x].code<<endl;
    if(a[x].rchild!=0) 
        inorder(a[x].rchild);// 递归生成右子树
}


十七、并查集


int getfather(int x)// 非递归求 X 结点的根结点的编号
{
    while(x!=father[x])
        x=father[x];
    return x;
}

int getfather(int x)// 递归求 X 结点的根结点的编号
{
    if(x==father[x]) 
        return x;
    else 
        return getfather(father[x]); 
}

int getfather(int x)// 非递归求 X 结点的根结点编号同时进行路径压缩
{
    int p=x;
    while(p!=father[p])// 循环结束后, P 即为根结点
        p=father[p];
    while(x!=father[x])// 从 X 结点沿 X 的父结点进行路径压缩
    {
        int temp=father[x];// 暂存 X 没有修改前的父结点
            father[x]=p;// 把 X 的父结点指向 P
            x=temp;
    }
    return p;
}

int getfather(int x)// 递归求 X 结点的根结点编号同时进行路径压缩
{
    if(x==father[x]) 
        return x;
    else {
        int temp=getfather(father[x]);
        father[x]=temp;
        return temp;
    }
}
void merge(int x,int y)// 合并 x,y 两个结点
{
    int x1,x2;
    x1=getfather(x);// 取得 X 的父结点
    x2=getfather(y);// 取得 Y 的父结点
    if(x1!=x2) 
    father[x1]=x2; // 两个父结点不同的话就合并,注意:合并的是 X , Y 两个结点的根。
}


十八、 Prime 算法

void prime(void) //prim 算法求最小生成树, elist[i] 是边集数组, a[i][j] 为 <I,j> 的权值。 edge 为结构体类型。
{
    for (int i=1;i<=n-1;i++)// 初始化结点 1 到其它 n-1 个结点形成的边集
    {
        elist[i].from=1;
        elist[i].to=i+1;
        elist[i].w=a[1][i+1];
    }
    for (int i=1;i<=n-1;i++)// 依次确定 n-1 条边
    {
        int m=i;
        for(int j=i+1;j<=n-1;j++)// 确定第 i 条边时,依次在 i+1 至 n-1 条边中找最小的那条边
            if(elist[j].w<elist[m].w) m=j;

        if(m!=i) // 如果最小的边不是第 i 条边就交换
        {
            edge tmp=elist[i];
            elist[i]=elist[m];
            elist[m]=tmp;
        }
        for(int j=i+1;j<=n-1;j++)// 更新第 i+1 至 n-1 条边的最小距离。
        {
            if(elist[j].w>a[elist[i].to][elist[j].to]) 
                elist[j].w=a[elist[i].to][elist[j].to];
        }
    }
    for(int i=1;i<=n-1;i++)// 求最小生成树的值
        ans=ans+elist[i].w;
}        
               


如果要求出哪些边构成最小生成树,在更新第 i+1 n-1 条边到已经生成的树中最小距离时 ( 上面代码中加粗的部分 ) ,还要加上 elist[j].from=elist[i].to; 语句,即在更新权值时,还应该更新起点。

Prime 算法适用于顶点不是太多的稠密图,如果对于顶点数较多的稀疏图,就不太适用了。

十九、 Dijkstra 算法


void dijkstra(int x)  // 求结点 x 到各个结点的最短路径
{
memset(vis,0,sizeof(vis)); // 初始化, vis[i] = 0 表示源点到结点 i 未求,否则已求
vis[x]=1;pre[x]=0; // 初始化源点。
for(int i=1;i<=n;i++)   // 对其它各点初始化。
    if(i!=x){
        dis[i]=g[x][i];
        pre[i]=x;
    }
    for(int i=1;i<=n-1;i++)   // 对于 n 个结点的图,要求 x 到其它 n-1 个结点的最短距离
    {
        int m=big; // 虚拟一个最大的数 big=99999999;
        int k=x;
        for(int j=1;j<=n;j++)   // 在未求出的结点中找一个源点到其距离最小的点
            if(vis[j]==0&&m>dis[j]){
                m=dis[j];
                k=j;
            }
        vis[k]=1;   // 思考:如果 k=X 说明什么?说明后面的点,无解。
        for(int j=1;j<=n;j++)   // 用当前找的结点更新未求结点到 X 的最短路径
        if((vis[j]==0)&&(dis[k]+g[k][j]<dis[j]))
        {
            dis[j]=dis[k]+g[k][j];  // 更新
            pre[j]=k;  // 保存前趋结点,以便后面求路径
        }
    }
}


说明: dis[i] 表示 x i 的最短距离, pre[i] 表示 i 结点的前趋结点。

二十、 Kruscal 算法


void qsort(int x,int y)// 对边集数组进行快速排序
{
    int h=x,r=y,m=elist[(h+r)>>1].w;
    while(h<r){
        while(elist[h].w<m) h++;
            while(elist[r].w>m) r--;
                if(h<=r)
                {
                    edge tmp=elist[h];
                    elist[h]=elist[r];
                    elist[r]=tmp;
                    h++;r--;
                }
    }
    if(x<r) qsort(x,r);
    if(h<y) qsort(h,y);
}

int getfather(int x)// 找根结点,并压缩路径,此处用递归实现的。
{
    if(x==father[x]) return x;
    else {
        int f=getfather(father[x]);
        father[x]=f;
        return f;
    }
}

void merge(int x,int y)// 合并 x,y 结点,在此题中的 x,y 为两个根结点。
{
    father[x]=y;
}

void kruscal(void)
{
    int sum=0,ans=0;
    qsort(1,t);// 对 t 条边按权值大小按从小到大的次序进行快速排序
    for(int i=1;i<=t;i++){
        int x1=getfather(elist[i].from);// 取第 i 条边的起点所在的树的根
        int x2=getfather(elist[i].to);//   取第 i 条边的终点所在的树的根
        if(x1!=x2){
            sum++;
            merge(x1,x2);
            ans+=elist[i].w;
        }// 不在同一个集合,合并,即第 i 条边可以选取。
        if(sum>n-1)
        break;// 已经确定了 n-1 条边了,最小生成树已经生成了,可以提前退出循环了
    }

    if(sum<n-1)
        cout<<"Impossible"<<endl; // 从 t 条边中无法确定 n-1 条边,说明无法生成最小生成树
    else  
        cout<<ans<<endl;
}


克鲁斯卡尔算法,只用了边集数组,没有用到图的邻接矩阵,因此当图的结点数比较多的时候,输入数据又是边的信息时,就要考虑用 Kruscal 算法。对于岛国问题,我们就要选择此算法,如果用 Prim 算法,还要开一个二维的数组来表示图的邻接矩阵,对于 10000 个点的数据,显然在空间上是无法容忍的。

二十一、 Floyed 算法


void floyed(void)//   a[i][j] 表示结点 i 到结点 j 的最短路径长度,初始时值为 <I,J> 的权值。
{
    for(int k=1;k<=n;k++) // 枚举中间加入的结点不超过 K 时 f[i][j] 最短路径长度, K 相当 DP 中的阶段
        for(int i=1;i<=n;i++) // i , j 是结点 i 到结点 J ,相当于 DP 中的状态
            for(int j=1;j<=n;j++)
                if (a[i][j]>a[i][k]+a[k][j]) 
                    a[i][j]=a[i][k]+a[k][j];// 这是决策,加和不加中间点,取最小的值
}


弗洛伊德算法适合于求没有负权回路的图的最短路径长度,利用 FLOYED 算法,可写出判断结点 i 和结点 J 是否连通的算法。




 推荐知识


 访问权限

创建人 方凯
文档编辑权限 创建者私有
文档阅读权限 来自分类
分类阅读权限 所有人
分类编辑权限 所有人
分类审核权限 无需审核
分类预览权限 所有人
分类下载权限 所有人
 历史版本

修改日期 修改人 备注
2019-07-25 15:25:15[当前版本] 方凯 格式调整
2019-07-25 15:24:56 方凯 格式调整
2019-07-24 17:30:06 方凯 格式调整
2018-10-22 13:57:17 方凯 格式调整

WCP知识管理系统-Vfree.4.2.0/419