完整版常用算法经典代码C++版.docx
《完整版常用算法经典代码C++版.docx》由会员分享,可在线阅读,更多相关《完整版常用算法经典代码C++版.docx(26页珍藏版)》请在冰点文库上搜索。
完整版常用算法经典代码C++版
一、快速排序
voidqsort(intx,inty)//待排序的数据存放在a[1]..a[n]数组中
{inth=x,r=y;
intm=a[(x+y)>>1];//取中间的那个位置的值
while(h{while(a[h] while(a[r]>m)r--;//比中间那个位置的值大,循环直到找一个比中间那个值小的 if(h<=r){inttemp=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}调用:qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序 二、冒泡排序voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=1;j<=n-i;j++)//相邻的两两比较 if(a[j]}或者voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=n-i;j>=1;j--)//相邻的两两比较 if(a[j]} 调用:paopao(),适用于n比较小的排序 三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数 {intacin>>a;tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i while(tong[i]!=0) {tong[i]--;cout<}} 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合(归)并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 {k++; //新数组指针加1 if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
{while(a[h] while(a[r]>m)r--;//比中间那个位置的值大,循环直到找一个比中间那个值小的 if(h<=r){inttemp=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}调用:qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序 二、冒泡排序voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=1;j<=n-i;j++)//相邻的两两比较 if(a[j]}或者voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=n-i;j>=1;j--)//相邻的两两比较 if(a[j]} 调用:paopao(),适用于n比较小的排序 三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数 {intacin>>a;tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i while(tong[i]!=0) {tong[i]--;cout<}} 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合(归)并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 {k++; //新数组指针加1 if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
while(a[r]>m)r--;//比中间那个位置的值大,循环直到找一个比中间那个值小的
if(h<=r)
{inttemp=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}调用:qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序 二、冒泡排序voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=1;j<=n-i;j++)//相邻的两两比较 if(a[j]}或者voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=n-i;j>=1;j--)//相邻的两两比较 if(a[j]} 调用:paopao(),适用于n比较小的排序 三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数 {intacin>>a;tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i while(tong[i]!=0) {tong[i]--;cout<}} 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合(归)并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 {k++; //新数组指针加1 if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
调用:
qsort(1,n)即可实现数组a中元素有序。
适用于n比较大的排序
二、冒泡排序
voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中
{for(inti=1;i for(intj=1;j<=n-i;j++)//相邻的两两比较 if(a[j]}或者voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=n-i;j>=1;j--)//相邻的两两比较 if(a[j]} 调用:paopao(),适用于n比较小的排序 三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数 {intacin>>a;tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i while(tong[i]!=0) {tong[i]--;cout<}} 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合(归)并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 {k++; //新数组指针加1 if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
for(intj=1;j<=n-i;j++)//相邻的两两比较
if(a[j]}或者voidpaopao(void)//待排序的数据存放在a[1]..a[n]数组中{for(inti=1;i for(intj=n-i;j>=1;j--)//相邻的两两比较 if(a[j]} 调用:paopao(),适用于n比较小的排序 三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数 {intacin>>a;tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i while(tong[i]!=0) {tong[i]--;cout<}} 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合(归)并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 {k++; //新数组指针加1 if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
或者
{for(inti=1;i for(intj=n-i;j>=1;j--)//相邻的两两比较 if(a[j]} 调用:paopao(),适用于n比较小的排序 三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数 {intacin>>a;tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i while(tong[i]!=0) {tong[i]--;cout<}} 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合(归)并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 {k++; //新数组指针加1 if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
for(intj=n-i;j>=1;j--)//相邻的两两比较
if(a[j]} 调用:paopao(),适用于n比较小的排序 三、桶排序voidbucketsort(void)//a的取值范围已知。如a<=cmax。 {memset(tong,0,sizeof(tong));//桶初始化for(inti=1;i<=n;i++)//读入n个数 {intacin>>a;tong[a]++;}//相应的桶号计数器加1 for(inti=1;i<=cmax;i++) {if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i while(tong[i]!=0) {tong[i]--;cout<}} 桶排序适用于那些待排序的关键字的值在已知范围的排序。 四、合(归)并排序voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 inth,t,k; k=0;//用于新数组B的指针 h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 {k++; //新数组指针加1 if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
paopao(),适用于n比较小的排序
三、桶排序
voidbucketsort(void)//a的取值范围已知。
如a<=cmax。
{memset(tong,0,sizeof(tong));//桶初始化
for(inti=1;i<=n;i++)//读入n个数
{inta
cin>>a;
tong[a]++;}//相应的桶号计数器加1
for(inti=1;i<=cmax;i++)
{if(tong[i]>0)//当桶中装的树大于0,说明i出现过tong[i]次,否则没出现过i
while(tong[i]!
=0)
{tong[i]--;
cout<
桶排序适用于那些待排序的关键字的值在已知范围的排序。
四、合(归)并排序
voidmerge(intl,intm,intr)//合并[l,m]和[m+1,r]两个已经有序的区间
{intb[101];//借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意
inth,t,k;
k=0;//用于新数组B的指针
h=l;t=m+1;//让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。
while((h<=m)&&(t<=r))//在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中
{k++; //新数组指针加1
if(a[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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。a[l+o-1]=b[o];}voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序{ intmid; 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);//把已经有序的前后两段进行合并} 归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。 五、二分查找intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标{inthead,tail,mid; head=x;tail=y;mid=((x+y)/2);//取中间元素下标 if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid if(head>tail)return0;//如果x>y,查找失败,返回0 if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果 returnfind(mid+1,tail); else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果 returnfind(head,mid-1);}六、高精度加法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数 inti; 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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
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(into=1;o<=k;o++)//把新数组中的元素,再抄回原来的区间,这两个连续的区间变为有序的区间。
a[l+o-1]=b[o];
voidmergesort(intx,inty)//对区间[x,y]进行二路归并排序
{
intmid;
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);//把已经有序的前后两段进行合并
归并排序应用了分治思想,把一个大问题,变成两个小问题。
二分是分治的思想。
五、二分查找
intfind(intx,inty,intm)//在[x,y]区间查找关键字等于m的元素下标
{inthead,tail,mid;
head=x;tail=y;mid=((x+y)/2);//取中间元素下标
if(a[mid]==m)returnmid;//如果中间元素值为m返回中间元素下标mid
if(head>tail)return0;//如果x>y,查找失败,返回0
if(m>a[mid]) //如果m比中间元素大,在后半区间查找,返回后半区间查找结果
returnfind(mid+1,tail);
else//如果m比中间元素小,在前半区间查找,返回后前区间查找结果
returnfind(head,mid-1);
六、高精度加法
#include
usingnamespacestd;
intmain()
stringstr1,str2;
inta[250],b[250],len; //数组的大小决定了计算的高精度最大位数
inti;
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< return0; } 注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。 七、高精度减法#includeusingnamespacestd;intcompare(strings1,strings2);intmain(){ stringstr1,str2; inta[250],b[250],len; inti; 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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
return0;
注意:
两个数相加,结果的位数,应该比两个数中大的那个数多一位。
七、高精度减法
intcompare(strings1,strings2);
inta[250],b[250],len;
cin>>str1>>str2;
a[0]=str1.length();
for(i=1;i<=a[0];i++)
b[0]=str2.length();
for(i=1;i<=b[0];i++)
if((compare(str1,str2))==0) //大于等于,做按位减,并处理借位。
{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< cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
cout< } 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< cout< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
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< } return0; }intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。{ if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大 if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
intcompare(strings1,strings2) //比较字符串(两个数)数字的大小,大于等于返回0,小于返回1。
if(s1.length()>s2.length())return0; //先比较长度,哪个字符串长,对应的那个数就大
if(s1.length() for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。 { if(s1[i]>s2[i])return0; if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
for(inti=0;i<=s1.length();i++) //长度相同时,就一位一位比较。
if(s1[i]>s2[i])return0;
if(s1[i] } return0; //如果长度相同,每一位也一样,就返回0,说明相等} 做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。 八、高精度乘法#include#includeusingnamespacestd;intmain(){ stringstr1,str2; inta[250],b[250],c[500],len; //250位以内的两个数相乘 inti,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< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
return0; //如果长度相同,每一位也一样,就返回0,说明相等
做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。
八、高精度乘法
inta[250],b[250],c[500],len; //250位以内的两个数相乘
inti,j;
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?
?
cout< return0; } 注意:两个数相乘,结果的位数应该是这两个数的位数和减1。优化:万进制#include#includeusingnamespacestd;voidnum1(ints[],stringst1);inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。Intmain(){ stringstr1,str2; intlen; 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(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位 for(intj=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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
两个数相乘,结果的位数应该是这两个数的位数和减1。
优化:
万进制
voidnum1(ints[],stringst1);
inta[2501],b[2501],c[5002];//此处可以进行2500位万进制乘法,即10000位十进制乘法。
Intmain()
intlen;
num1(a,str1);//把str1从最低位开始,每4位存放在数组a中
num1(b,str2);//把str2从最低位开始,每4位存放在数组b中
for(inti=1;i<=a[0];i++)//作按位乘法并处理进位,此处是万进制进位
for(intj=1;j<=b[0];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< for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
for(inti=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< } cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
cout< return0;}voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中{ intk=1,count=1; s[0]=st1.length();//存放st1的长度,省去一长度变量 for(inti=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;} 九、高精度除法(没讲) 十、筛选法建立素数表voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数{ memset(prim,0,sizeof(prim));//初始化质数表 prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表 for(inti=2;i<=x;i++) if(prim[i]==0) {intj=2*i; while(j<=x) {prim[j]=1;j=j+i;}}} 对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。 十一、深度优先搜索voiddfs(intx) \\以图的深度优先遍历为例。 { cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
voidnum1(ints[],stringst1)//此函数的作用就是把字符串st1,按4位一组存放在数组s中
{ intk=1,count=1;
s[0]=st1.length();//存放st1的长度,省去一长度变量
for(inti=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;
九、高精度除法(没讲)
十、筛选法建立素数表
voidmaketable(intx)//建立X以内的素数表prim,prim[i]为0,表示i为素数,为1表示不是质数
memset(prim,0,sizeof(prim));//初始化质数表
prim[0]=1;prim[1]=1;prim[2]=0;//用筛选法求X以内的质数表
for(inti=2;i<=x;i++)
if(prim[i]==0)
{intj=2*i;
while(j<=x)
{prim[j]=1;j=j+i;}
对于那些算法中,经常要判断素数的问题,建立一个素数表,可以达到一劳永逸的目的。
十一、深度优先搜索
voiddfs(intx) \\以图的深度优先遍历为例。
cout< visited[x]=1;\\作已访问的标记 for(intk=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尚未访问 inth=1,r=1; //置空的辅助队列q visited[v]=1;//顶点v,作访问标记 cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
visited[x]=1;\\作已访问的标记
for(intk=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尚未访问
inth=1,r=1; //置空的辅助队列q
visited[v]=1;//顶点v,作访问标记
cout< q[r]=v; //v入队列 while(h<=r)//当队列非空时循环 { inttmp=q[h]; //队头元素出队,并赋值给tmp for(intj=1;j<=n;j++) if((visited[j]==0)&&(a[tmp][j]==1)){//j为tmp的尚未访问的邻接顶点 visited[j]=1; 对j作访问标记 cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
q[r]=v; //v入队列
while(h<=r)//当队列非空时循环
inttmp=q[h]; //队头元素出队,并赋值给tmp
for(intj=1;j<=n;j++)
if((visited[j]==0)&&(a[tmp][j]==1))
{//j为tmp的尚未访问的邻接顶点
visited[j]=1; 对j作访问标记
cout< r++;//队尾指针加1q[r]=j;//j入队} //end-if h++; }//end-while}十三、二叉树的前序、中序和后序遍历voidpreorder(intx)//二叉树的先序遍历 { if(x==0)return; cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
r++;//队尾指针加1
q[r]=j;//j入队
} //end-if
h++;
}//end-while
十三、二叉树的前序、中序和后序遍历
voidpreorder(intx)//二叉树的先序遍历
if(x==0)return;
cout< preorder(a[x].ld);//再先序遍历根的左子树 preorder(a[x].rd);//最后先序遍历根的右子树} voidinorder(intx)//二叉树的中序遍历 { if(x==0)return; preorder(a[x].ld);//先中序遍历根的左子树 cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
preorder(a[x].ld);//再先序遍历根的左子树
preorder(a[x].rd);//最后先序遍历根的右子树
voidinorder(intx)//二叉树的中序遍历
preorder(a[x].ld);//先中序遍历根的左子树
cout< preorder(a[x].rd);//最后中序遍历根的右子树} voidreorder(intx)//二叉树的后序遍历 { if(x==0)return; preorder(a[x].ld);//先后序遍历根的左子树 preorder(a[x].rd);//再后序遍历根的右子树 cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
preorder(a[x].rd);//最后中序遍历根的右子树
voidreorder(intx)//二叉树的后序遍历
preorder(a[x].ld);//先后序遍历根的左子树
preorder(a[x].rd);//再后序遍历根的右子树
cout<} 十四、树转换为二叉树算法 十五、二叉排序树 十六、哈夫曼树voidhaff(void)//构建哈夫曼树{ for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点 {intl=fmin(i-1);//查找权值最小的结点的编号l a[i].lchild=l;//把l作为结点i的左孩子 a[l].father=i;//把l的父结点修改为i intr=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 }}intfmin(intk)//在1到K中寻找最小的权值的编号 { intmins=0; for(ints=1;s<=k;s++) if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点mins=s; //的孩子,不等于0说明这个结点已经用过。 returnmins; }voidinorder(intx)//递归生成哈夫曼编码{ 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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
十四、树转换为二叉树算法
十五、二叉排序树
十六、哈夫曼树
voidhaff(void)//构建哈夫曼树
for(inti=n+1;i<=2*n-1;i++)//依次生成n-1个结点
{intl=fmin(i-1);//查找权值最小的结点的编号l
a[i].lchild=l;//把l作为结点i的左孩子
a[l].father=i;//把l的父结点修改为i
intr=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
intfmin(intk)//在1到K中寻找最小的权值的编号
intmins=0;
for(ints=1;s<=k;s++)
if((a[mins].da>a[s].da)&&(a[s].father==0))//a[s].father=0,说明这个结点还不是别个结点
mins=s; //的孩子,不等于0说明这个结点已经用过。
returnmins;
voidinorder(intx)//递归生成哈夫曼编码
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<'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
'< if(a[x].rchild!=0)inorder(a[x].rchild);//递归生成右子树}十七、并查集intgetfather(intx)//非递归求X结点的根结点的编号{while(x!=father[x]) x=father[x]; returnx;} intgetfather(intx)//递归求X结点的根结点的编号{if(x==father[x])returnx; elsereturngetfa
if(a[x].rchild!
=0)inorder(a[x].rchild);//递归生成右子树
十七、并查集
intgetfather(intx)//非递归求X结点的根结点的编号
{while(x!
=father[x])
x=father[x];
returnx;
intgetfather(intx)//递归求X结点的根结点的编号
{if(x==father[x])returnx;
elsereturngetfa
copyright@ 2008-2023 冰点文库 网站版权所有
经营许可证编号:鄂ICP备19020893号-2