数据结构常用算法

//汉诺塔 void Hanoi(int n,string A,string B,string C){ if(n == 1) cout<<A<<"->"<<C<<endl; else{ Hanoi(n-1,A,C,B); cout<<A<<"->"<<C<<endl; Hanoi(n-1,B,A,C); } } //递归实现 int maxNUm(int num[],int n){ if(1 == n) return num[0]; else { int tem = maxNUm(num,n-1); return (tem > num[n-1]) ? tem : num[n-1]; } } int addNum(int num[],int n){ if(1 == n) return num[0]; else { return num[n-1] + addNum(num,n-1); } } int av(int num[],int n){ if(1 == n)return num[0]; else { return ((n-1)*av(num,n-1) + num[n-1])/n; } } void pai(int num[],int m,int n){ int j,tem; if(0 == m){ for (j = 0;j < n;++j) { cout<<num[j]<<" "; } cout<<endl; } else { for (j = 0;j<=m;++j) { tem = num[m]; num[m] = num[j]; num[j] = tem; pai(num,m-1,n); tem = num[m]; num[m] = num[j]; num[j] = tem; } } } void getNext(char *p,int *next){ int j,k; next[0] = -1; j = 0; k = -1; int b1 = strlen(p); while (j < strlen(p) -1) { if(k ==-1 || p[j] == p[k] ) { ++j; ++k; next[j] = k; }else k = next[k]; } } int KEMMatch(char *t,char *p){ int *next = new int(strlen(p)); getNext(p,next); int i = 0; int j = 0; while (i < strlen(t)) { if(j == -1 || t[i] == p[j]) { ++i; ++j; }else { j = next[j]; } if(j == strlen(p)) return i - strlen(p); } return -1; } /**********************************************************/ //堆插入 //堆插入 void constructHeap(int a[],int n,int value){ a[n] = value; int j,temp = value; j = (n-1)/2; while (j>=0 && n!=0) { if(a[j] <= temp) break; a[n] = a[j]; n = j; j = (n-1)/2; } a[n] = temp; } //堆更新 void UpdataHeap(int a[],int index,int n) { int j,temp = a[index]; j = 2*index + 1; while (j < n) { if(j+1 < n && a[j+1] < a[j]) ++j; if(a[j] >= temp) break; a[index] = a[j]; index = j; j = index*2 +1; } a[index] = temp; } void HeapDelete(int a[],int n){ swap(a[0],a[n-1]); UpdataHeap(a,0,n-1); } //数组堆化 void MakeHeap(int a[],int n){ for (int i = n/2-1; i>=0; --i) { UpdataHeap(a,i,n); } } //堆排序 void HeapSort(int a[],int n){ for (int i=n-1; i>=1; --i) { swap(a[0],a[i]); UpdataHeap(a,0,i); } } /*********************************/ /*给定一数组a[N]，我们希望构造数组b [N]，其中b[j]=a[0]*a[1]…a[N-1] / a[j]，在构造过程中，不允许使用除法： 要求O（1）空间复杂度和O（n）的时间复杂度； 除遍历计数器与a[N] b[N]外，不可使用新的变量（包括栈临时变量、堆空间和全局静态变量等）； */ void getB(int a[],int b[],int n){ b[0] = 1; int i; for (i = 1;i<n;++i) { b[i] = b[i-1] * a[i-1]; } for (i = n-1;i>=1;--i) { b[i] *= b[0]; b[0] *= a[i]; } } /*************************************/ //冒泡排序 void BubbleSort(int a[],int n){ int i,j; int flag = true; for ( i = 0;i < n;++i) { flag = false; for (j = 1;j < n-i;++j) { if(a[j-1] > a[j]) swap(a[j-1],a[j]); flag = true; } if(!flag) break; } } /*************************************/ //插入排序 void InsertSort(int a[],int n){ int i,j,temp; for (i = 1;i<n;++i) { if(a[i] < a[i-1]){ temp = a[i]; j = i; do { a[j] = a[j-1]; --j; } while (j>=1 && temp<a[j-1]); a[j] = temp; } } } /*************************************/ //希尔排序 void ShellSort(int a[],int n){ int i,j,temp,gap; gap = n; do { gap = gap/3 +1; for (i = gap;i < n;++i) { if(a[i] < a[i-gap]){ temp = a[i]; j = i; do { a[j] = a[j-gap]; j -= gap; } while (j>=gap && temp < a[j-gap]); a[j] = temp; } } } while (gap > 1); } /*************************************/ //快速排序 void QuikSort(int a[],int l,int r){ if(l < r) { int i = l,j = r,tem = a[l]; while (i < j) { while (i<j && a[j] >= tem) --j; if(i < j) a[i++] = a[j]; while (i < j && a[i] <= tem) ++i; if(i < j) a[j--] = a[i]; } a[i] = tem; QuikSort(a,l,i-1); QuikSort(a,i+1,r); } } /*************************************/ //选择排序 void SelectSort(int a[],int n){ int i,j,k; for (i = 0;i<n-1;++i) { k = i; for (j = i+1; j<n;++j) { if (a[j] < a[k]) k = j; } if(i != k)swap(a[i],a[k]); } } /*************************************/ //斐波那契数列 long Fibonacci1(int n){ if(0 == n) return 0; else if(1 == n) return 1; else if(n > 1) return Fibonacci1(n-1) + Fibonacci1(n-2); else return -1; } long fab2(int in){ int x = 0,y = 1,i; for(i=2;i<=in;i++){ y = x + y; x = y - x; } return y; }; /************************************/ //给定整数sum，在乱序数组中寻找所有满足x+y=sum的组合 void sumN(int a[],int n,int value){ QuikSort(a,0,n-1); int i = 0,j = n-1; while (i < j) { if((a[i] + a[j]) == value) { cout<<a[i]<<"+"<<a[j]<<endl; ++i; --j; }else if((a[i] + a[j]) < value) ++i; else --j; } } /************************************/ //寻找在数组中最大的K个数 //堆插入 void constructHeap(int a[],int n,int value){ a[n] = value; int j,temp = value; j = (n-1)/2; while (j>=0 && n!=0) { if(a[j] <= temp) break; a[n] = a[j]; n = j; j = (n-1)/2; } a[n] = temp; } //堆更新 void UpdataHeap(int a[],int index,int n) { int j,temp = a[index]; j = 2*index + 1; while (j < n) { if(j+1 < n && a[j+1] < a[j]) ++j; if(a[j] >= temp) break; a[index] = a[j]; index = j; j = index*2 +1; } a[index] = temp; } void MaxK(int a[],int n,int k){ int i; int *temp = new int[k]; for (i=0;i<n;++i) { if(i < k) constructHeap(temp,i,a[i]);//先构造k堆 else { if (temp[0] < a[i]) { temp[0] = a[i]; UpdataHeap(temp,0,k);//更新k堆； } } } for (i=0;i<k;++i) { cout<<temp[i]<<" "; } delete []temp; } /************************************/