408数据结构强化（自用）

常用代码片段（持续更新）

折半查找

void SearchBinary(int A[];int x){int low = 0, high = n-1, mid;while(low<=high){mid = (low+high)/2;if(A[mid]==x) break;else if(A[mid] < x) low = mid + 1;else high = mid - 1;}

顺序表逆置

void Reverse(SqList &L){for(int i=0;i<L.length/2;i++){temp = L.data[i];L.data[i] = L.data[length-i-1];L.data[length-i-1] = temp;}
}

快速排序

int huafen(int A[]; int L; int R)int mid = A[L];while(L<R){while(L<=R&&A[R]>=mid) R--;A[L] = A[R];while(L<=R&&A[L]<=mid) L++:A[R] = A[L];}A[L] = mid;retutn L;}
void Qsort(int A[], int L, int R){if(L>=R) return;int M = huafen(A, L, R);Qsort(A, M+1, R); //右半部分快排Qsort(A, L, M-1); //左半部分快排
}

快速排序的划分思想

//使用划分函数找到数组中第k小的元素
int huafen(int A[]; int L; int R)int mid = A[L];while(L<R){while(L<=R&&A[R]>=mid) R--;A[L] = A[R];while(L<=R&&A[L]<=mid) L++:A[R] = A[L];}A[L] = mid;retutn L;}
int func(int A[], int n, int k){int L = 0, R = n-1, M = 0;while(1){M = huafen(A ,R ,L);if(M == k-1) break;else if(M > k-1) R = M-1;else if(M < k-1) L = m+1;}return A[k-1];
}