C++常用经典算法及其实现.
- 格式：pdf
- 大小：28.51 KB
- 文档页数：22
for(i=b[0];i>=1;i--)
cout<<b[i];
cout<<endl;
}
return 0;
}
int compare(string s1,string s2)
// 比较字符串（两个数）数字的大小，大于等于返回
0，
小于返回 1。
{
if(s1.length()>s2.length()) return 0;
{for(int i=1;i<n;i++)
// 控制循环（冒泡）的次数， n 个数，需要 n-1 次冒泡
for(int j=n-i;j>=1;j--) //
相邻的两两比较
if(a[j]<a[j+1]) {int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}
}
调用： paopao() ，适用于 n 比较小的排序
mergesort(x,mid);// 对前一段进行二路归并
mergesort(mid+1,y);// 对后一段进行二路归并 merge(x,mid,y);// 把已经有序的前后两段进行合并
}
归并排序应用了分治思想，把一个大问题，变成两个小问题。二分是分治的思想。
五、二分查找
int find(int x,int y,int m) // 在 [x,y] 区间查找关键字等于 m 的元素下标
cout<<endl;
}
else
{
cout<<'-'; // 小于就输出负号
for(i=1;i<=b[0];i++)
// 做按位减，大的减小的
{b[i]-=a[i];
if (b[i]<0) {b[i+1]--;b[i]+=10;}
}
b[0]++;
while((b[b[0]]==0)&&(b[0]>1)) b[0]--;
for(i=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];
h=l;t=m+1;// 让 h 指向第一个区间的第一个元素， t 指向第二个区间的第一个元素。
while((h<=m)&&(t<=r))// 中
在指针 h 和 t 没有到区间尾时，把两个区间的元素抄在新数组
{k++;
// 新数组指针加 1
if (a[h]<a[t]){b[k]=a[h];h++;}
一、快速排序
常用算法经典代码（ C++ 版）
void qsort(int x,int y) // 待排序的数据存放在 a[1]..a[n] 数组中
{int h=x,r=y; int m=a[(x+y)>>1]; //
取中间的那个位置的值
while(h<r)
{while (a[h]<m) h++; //
// 大于等于，做按位减，并处理借位。
{
for(i=1;i<=a[0];i++)
{a[i]-=b[i];
if (a[i]<0) {a[i+1]--;a[i]+=10;}
}
a[0]++;
while((a[a[0]]==0)&&(a[0]>1)) a[0]--;
for(i=a[0];i>=1;i--)
cout<<a[i];
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++)
// 做按位乘法同时处理进位，注意循环内语句的写法。
七、高精度减法 #include<iostream> using namespace std; int compare(string s1,string s2); int main() {
string str1,str2; int a[250],b[250],len; int i; memset(a,0,sizeof(a)); memset(b,0,sizeof(b));
// 抄第一个区间元素到新数组
else{b[k]=a[t];t++;}
// 抄第二个区间元素到新数组
}
while(h<=m){k++;b[k]=a[h];h++;} 组中
// 如果第一个区间没有抄结束，把剩下的抄在新数
while(t<=r){k++;b[k]=a[t];t++;} 中
// 如果第二个区间没有抄结束， 把剩下的抄在新数组
}
return 0; // 如果长度相同，每一位也一样，就返回 0，说明相等
}
做减法时，首先要判断两个字符串的大小，决定是否输出负号，然后就是按位减法，注意 处理借位。
八、高精度乘法 #include<iostream> #include<cstring> using namespace std; int main()
num1(b,str2); // 把 str2 从最低位开始，每 4 位存放在数组 b 中
// 先比较长度，哪个字符串长，对应的那个数就大
if(s1.length()<s2.length()) return 1;
for(int i=0;i<=s1.length();i++)
// 长度相同时，就一位一位比较。
{
if(s1[i]>s2[i]) return 0;
if(s1[i]<s2[i]) return 1;
四、合（归）并排序
void merge(int l,int m,int r)// 合并 [l,m] 和[m+1,r] 两个已经有序的区间
{ int b[101];// 借助一个新的数组 B，使两个有序的子区间合并成一个有序的区间， 大小要注意
b 数组的
int h,t,k; k=0;// 用于新数组 B 的指针
{
string str1,str2;
int a[250],b[250],c[500],len;
//250 位以内的两个数相乘
int i,j;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>str1>>str2;
a[0]=str1.length();
此处可以进行 2500 位万进制乘法， 即 10000 位十进制乘法。
{
string str1,str2;
int len;
cin>>str1>>str2; memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
num1(a,str1); // 把 str1 从最低位开始，每 4 位存放在数组 a 中
{ int head,tail,mid;
head=x;tail=y;mid=((x+y)/2);//
取中间元素下标
if(a[mid]==m) return mid;//
如果中间元素值为 m 返回中间元素下标 mid
if(head>tail) return 0;// 如果 x>y ，查找失败，返回 0
for(int o=1;o<=k;o++)// 有序的区间。
把新数组中的元素， 再抄回原来的区间， 这两个连续的区间变为
a[l+o-1]=b[o];
}
void mergesort(int x,int y)// 对区间 [x,y] 进行二路归并排序
{
int mid;
if(x>=y) return;
mid=(x+y)/2;// 求 [x,y] 区间，中间的那个点 mid,mid 把 x,y 区间一分为二
a[i+1]+=a[i]/10;
a[i]%=10;
}
len++; // 下面是去掉最高位的 0，然后输出。
while((a[len]==0)&&(len>1)) len--;
for(i=len;i>=1;i--)
cout<<a[i];
return 0;
}
注意：两个数相加，结果的位数，应该比两个数中大的那个数多一位。
cin>>str1>>str2;
// 输入两个字符串
a[0]=str1.length();
// 取得第一个字符串的长度
for(i=1;i<=a[0];i++)
