数据结构与算法复习

1.快速排序

快速排序的一个实现

void QuickSort(Sqlist &L, int lowf, int highf){
    low = lowf; high = highf;
    if(low >= hight) return;
    // 书上 L.elem[low].key 这里就当元素只有值没有附加信息
    temp = L.elem[low]; // 记录枢纽的值
    while(low < high){
        // 先从右向左查找
        while( low < high && L.elem[high] > temp) high--;
        L.elem[low] = L.elem[high]  // 将比枢纽小的移动到低端
        // 在从左向右查找
        while( low < high && L.elem[high] <= temp) low++;
        L.elem[high] = L.elem[low]  // 将比枢纽大的移动到高端
    }
    L.elem[low] = temp;

    QuickSort(L, lowf, highf-1);
    QuickSort(L, lowf+1, highf)
}

Top K问题 找出最大的前K个值.

Quick Select找出第k大元素

** 解决思路 **

选取一个基准元素pivot，将数组切分为两个子数组，比pivot大的扔左子数组，比pivot小的扔右子数组，然后递推地切分子数组。QuickSelect不同于Quick Sort的是其没有对每个子数组做切分，而是对目标子数组做切分。

• 若切分后的左子数组的长度 > k，则第k大元素必出现在左子数组中；
• 若切分后的左子数组的长度 = k，则第k大元素为pivot；
• 若上述两个条件均不满足，则第k大元素必出现在右子数组中。

** 改进QuickSort **

// L.elem 从0开始存数据
int QuickSelect(Sqlist &L, int k, int lowf, int highf){
    low = lowf; high = highf;
    if(low = hight) return L.elem[low];
    // 书上 L.elem[low].key 这里就当元素只有值没有附加信息
    temp = L.elem[low]; // 记录枢纽的值
    while(low < high){
        // 先从右向左查找
        while( low < high && L.elem[high] > temp) high--;
        L.elem[low] = L.elem[high]; // 将比枢纽小的移动到低端
        // 在从左向右查找
        while( low < high && L.elem[high] <= temp) low++;
        L.elem[high] = L.elem[low]; // 将比枢纽大的移动到高端
    }
    L.elem[low] = temp;
    if( k==low+1) return temp;
    else if(k > low+1)  return QuickSelect(L, k, lowf+1, highf);
    else if(k < low+1)  return QuickSelect(L, k, lowf, highf-1);

}

2. 左右子树交换的递归实现

void BTSwap(BiTree T)  
{  
    if(T)  
    {   // 交换左右子树
        BiTree p=T->lchild;
        T->lchild=T->rchild;
        T->rchild=p;
        // 递归交换左孩子和右孩子的左右子树
        BTSwap(T->lchild); 
        BTSwap(T->rchild);
    }  
}

3. Dijkstra 算法

原理图

#define Inf 99999; // 我们认为的一个最大的数

// 邻接矩阵 起点 最短路 `(无最短的路径 只求出最短路的长度)`
void Dijkstra(MGraph G, int v0, ShortPath &D){
    D[v0] = 0; book[v0] = true; // 把v0加入到S集合中
    for(int i=1; i < G.vexnum; i++)  // 其余的顶点
        min = Inf;
        for(w=0;w < G.vexnum; w++){
            if(!book[w]){
                 if(D[w] < min ){ // 找出V集合中距离v0最近的点 
                    v = w; 
                    min = D[w];
                }
            }
            book[v] = true; // 将选出的点加入到S集合中
        }
        for(w=0; w

4. 归并排序

原理图

    void MSort(RcdType SR[], RcdType &TR1[], int s, int t){
    // 将SR归并排序为TR1
        if(s==t) TR1[s] = SR[s];
        else {
            m = (s + t) / 2; // 将SR分为两部分
            MSort(SR, TR2, s, m);  // 递归将分为的两部分有序
            MSort(SR, TR2, m+1, t);
            Merge(TR2, TR1, s, m, t); // 将相邻序列合并 这个与第二章顺序表的合并类似
        }
    }
    // 归并排序
    void MergeSort(SqList &L){
        MSort(L.elem, L.elem, 1, L.Length);
    }