《C++ 常用代码.doc》由会员分享,可在线阅读,更多相关《C++ 常用代码.doc(22页珍藏版)》请在金锄头文库上搜索。
1、一、快速排序void qsort(int x,int y) /待排序的数据存放在a1.an数组中 int h=x,r=y; int m=a(x+y)1; /取中间的那个位置的值 while(hr)while (ahm) r-; /比中间那个位置的值大,循环直到找一个比中间那个值小的 if(h=r)int temp=ah;/如果此时hx) qsort(x,r);/注意此处,尾指针跑到前半部分了 if(hy) qsort(h,y); /注意此处,头指针跑到后半部分了调用:qsort(1,n)即可实现数组a中元素有序。适用于n比较大的排序二、冒泡排序void paopao(void) /待排序的数据
2、存放在a1.an数组中for(int i=1;in;i+) /控制循环(冒泡)的次数,n个数,需要n-1次冒泡 for(int j=1;j=n-i;j+) /相邻的两两比较 if(ajaj+1) int temp=aj;aj=aj+1;aj+1=temp;或者void paopao(void) /待排序的数据存放在a1.an数组中for(int i=1;i=1;j-) /相邻的两两比较 if(ajaj+1) int temp=aj;aj=aj+1;aj+1=temp;调用:paopao(),适用于n比较小的排序三、桶排序void bucketsort(void)/a的取值范围已知。如a=cma
3、x。memset(tong,0,sizeof(tong);/桶初始化for(int i=1;ia;tonga+;/相应的桶号计数器加1 for(int i=1;i0) /当桶中装的树大于0,说明i出现过tongi次,否则没出现过i while (tongi!=0) tongi-;couti ;桶排序适用于那些待排序的关键字的值在已知范围的排序。四、合(归)并排序void merge(int l,int m,int r)/合并l,m和m+1,r两个已经有序的区间 int b101;/借助一个新的数组B,使两个有序的子区间合并成一个有序的区间,b数组的大小要注意 int h,t,k; k=0;/用
4、于新数组B的指针 h=l;t=m+1;/让h指向第一个区间的第一个元素,t指向第二个区间的第一个元素。 while(h=m)&(t=r)/在指针h和t没有到区间尾时,把两个区间的元素抄在新数组中 k+; /新数组指针加1 if (ahat)bk=ah;h+; /抄第一个区间元素到新数组 elsebk=at;t+; /抄第二个区间元素到新数组 while(h=m)k+;bk=ah;h+; /如果第一个区间没有抄结束,把剩下的抄在新数组中 while(t=r)k+;bk=at;t+; /如果第二个区间没有抄结束,把剩下的抄在新数组中 for(int o=1;o=y) return; mid=(x+
5、y)/2;/求x,y区间,中间的那个点mid,mid把x,y区间一分为二 mergesort(x,mid);/对前一段进行二路归并 mergesort(mid+1,y);/对后一段进行二路归并 merge(x,mid,y);/把已经有序的前后两段进行合并归并排序应用了分治思想,把一个大问题,变成两个小问题。二分是分治的思想。五、二分查找int find(int x,int y,int m) /在x,y区间查找关键字等于m的元素下标 int head,tail,mid; head=x;tail=y;mid=(x+y)/2);/取中间元素下标 if(amid=m) return mid;/如果中间
6、元素值为m返回中间元素下标mid if(headtail) return 0;/如果xy,查找失败,返回0 if(mamid) /如果m比中间元素大,在后半区间查找,返回后半区间查找结果 return find(mid+1,tail); else /如果m比中间元素小,在前半区间查找,返回后前区间查找结果 return find(head,mid-1);六、高精度加法#include#includeusing namespace std;int main() string str1,str2; int a250,b250,len; /数组的大小决定了计算的高精度最大位数 int i; mems
7、et(a,0,sizeof(a); memset(b,0,sizeof(b); cinstr1str2; /输入两个字符串 a0=str1.length(); /取得第一个字符串的长度 for(i=1;i=a0;i+) /把第一个字符串转换为整数,存放在数组a中 ai=str1a0-i-0; b0=str2.length(); /取得第二个字符串长度 for(i=1;ib0?a0:b0); /取两个字符串最大的长度 for(i=1;i1) len-; for(i=len;i=1;i-) coutai; return 0;注意:两个数相加,结果的位数,应该比两个数中大的那个数多一位。七、高精度减
8、法#includeusing namespace std;int compare(string s1,string s2);int main() string str1,str2; int a250,b250,len; int i; memset(a,0,sizeof(a); memset(b,0,sizeof(b); cinstr1str2; a0=str1.length(); for(i=1;i=a0;i+) ai=str1a0-i-0; b0=str2.length(); for(i=1;i=b0;i+) bi=str2b0-i-0; if(compare(str1,str2)=0) /
9、大于等于,做按位减,并处理借位。 for(i=1;i=a0;i+) ai-=bi; if (ai1) a0-; for(i=a0;i=1;i-) coutai; coutendl; else cout-; /小于就输出负号 for(i=1;i=b0;i+) /做按位减,大的减小的 bi-=ai; if (bi1) b0-; for(i=b0;i=1;i-) coutbi; couts2.length() return 0; /先比较长度,哪个字符串长,对应的那个数就大 if(s1.length()s2.length() return 1; for(int i=0;is2i) return 0; if(s1is2i) return 1; return 0; /如果长度相同,每一位也一样,就返回0,说明相等做减法时,首先要判断两个字符串的大小,决定是否输出负号,然后就是按位减法,注意处理借位。八、高精度乘法#include#includeusing namespace std;int main() string str1,str2; int a250,b250,c500,len; /250位以内的两个数相乘 int i,j; memset(a,0,sizeof(a); memset(b,0,sizeof(b); cinstr1str2; a0=str1.length();