数据结构算法设计.docx

数据结构算法 直接插入排序 void? insertSort (int? r[ ], int n) {? ? for (i=2; i<=n; i++) { r[0]=r[i]; j=i-1; while (r[0]<r[j]) {? r[j+1]=r[j];? ? j=j-1;? ? } r[j+1]=r[0];? ? } } 冒泡排序 void BubbleSort(int r[ ], int n) {? ? exchange=n; ? ? while (exchange) { bound=exchange; exchange=0；? for (j=1; j<bound; j++) if (r[j]>r[j+1]) { r[j]←→r[j+1]； exchange=j； } } } 选择排序 void? selectSort ( int? r[ ], int n) {? for ( i=1; i<n; i++) {? index=i; ? ? ? ? for (j=i+1; j<=n; j++) if? (r[j]<r[index])? index=j; if (index!=i)? r[i]<==>r[index]; ? ? } } 折半查找非递归算法 int BinSearch1(int r[ ], int n, int k) //数组r[1] ~ r[n]存放查找集合 { low=1; high=n; while (low<=high)? ? ? ? ? ? ? ? ? { mid=(low+high)/2;? ? ? ? ? ? if (k<r[mid])? high=mid-1; else if (k>r[mid])? low=mid+1; else return mid; } return 0; } 折半查找递归算法 int BinSearch2(int r[ ], int low, int high, int k) //数组r[1] ~ r[n]存放查找集合 {? ? if (low>high) return 0;? else { mid=(low+high)/2; if (k<r[mid]) return BinSearch2(r, low, mid-1, k); else? if (k>r[mid]) return BinSearch2(r, mid+1, high, k); else return mid; } } 快速排序 int Partition(int r[ ], int first, int end) {? ? i=first; j=end;? ? ? ? //初始化 while (i<j)? ? {? while (i<j && r[i]<= r[j]) j--；? //右侧扫描 if (i<j) { r[i]←→r[j];? i++;? //将较小记录交换到前面 } while (i<j && r[i]<= r[j]) i++；? //左侧扫描 if (i<j) { r[j]←→r[i];? j--;? //将较大记录交换到后面 } } retutn i;? ? //i为轴值记录的最终位置 } 堆排序 void? HeapSort ( int? r[], int n) { for (i=n/2; i>=1; i--)? ? ? //初建堆 sift(r, i, n) ;? ? for (i=1; i>n; i++ ) { r[1]←→r[n-i+1];? ? ? ? //移走堆顶 sift(r, 1, n-i);? ? ? ? ? ? ? //重建堆 } } 前序遍历——递归算法 void? PreOrder(BiNode *root) { if (root ==NULL)? return;? ? else { printf(root->data);? ? ? ? PreOrder(root->lchild);? ? PreOrder(root->rchild);? ? } } 中序遍历——递归算法 void? InOrder (BiNode? *root) { if (root==NULL) return;? ? else { InOrder(root->lchild); printf(root->data); InOrder(root->rchild); } } 后序遍历——递归算法 void? PostOrder(BiNode? *root) { if (root==NULL) return; else { PostOrder(root->lchild); PostO