历时一个礼拜，我终于看完了“大话数据结构”

You got a dream, you gotta protect it. People can't do something themselves, they wanna tell you can't do it. If you want something, go get it. Period.

如果你有梦想的话，那么就要去捍卫它。当别人做不到的时候，他们就想要告诉你，你也不行。如果你想要什么，就得努力去争取，就这样。

  这段时间一直在复习，之前看了一遍《Head First Java》，然后看了一遍《深入理解JVM虚拟机》，根据大佬们推荐的后端之路，接下来就是程杰编著的《大话数据结构》了。

  我是本科是学通信的，课程上学过C、C++、Java，但并不像科班生有计算机网络、操作系统、数据结构等必修课。所以我觉得既不是科班也不是非科班，顶多算半个科班吧。

  记得本科的时候学过一门课叫“计算机软件基础”，好像是大一的时候上的吧，那应该是第一次接触到了“数据结构”，但完全是理论的东西，并没有实操，而且内容也不像数据结构教材那样丰富。

  直到今日，我觉得我才算是完整地走了一遍“数据结构”之路。将整个数据结构的知识拉通地走了一遍。（ps：有时候我特别悔恨我当时为什么不在ACM继续留下去，一直觉得是自己太菜、觉得做题太枯燥。但是现在看来，确实是自己理论知识不过关啊，那个时候就应该将数据结构这本书拿来阅读一遍。）

  好了，说了这么多，该说正事儿了。《大话数据结构》这本书还是非常友好的，大佬们说非常适合初学者，但是我觉得也适用于有编程经验并且多多少少已经有一些数据结构基础的童鞋~

  整本书分为了9章，前面7章讲了数据结构及其算法，后面2章分别是“查找”与“排序”，可以说是使用前面讲的数据结构的实现的一些常用算法。

  下面分别进行总结，方便以后的复习。

第一章：线性表

  数据称为”元素“，两种存储结构：

• 顺序存储结构（数组实现）
• 链式存储结构（结构体、指针）
  • 单链表（仅有指向后继结点的指针）
  • 静态链表（特殊，通过数组实现。针对一些没有指针引用的语言）
  • 循环链表（将终端结点指针指向头结点）
  • 双向链表（既指向前继，也有指向后继）

第二章：栈与队列

  数据称为”元素“，两种存储结构。

2.1 栈

• 顺序存储结构（数组实现）
• 链式存储结构（链栈）（结构体、指针）

2.2 队列

• 顺序存储结构（数组实现）
  • 普通队列（一般不使用，可能会存在假溢出）
  • 循环队列
• 链式存储结构（链队列）（结构体、指针）

第三章：串

  串(string)是由零个或多个字符组成的有限序列，又名“字符串”。

• 顺序存储结构（数组实现，一般用法）
• 链式存储结构（结构体、指针）

3.1 朴素的模式匹配算法

  子串在串中的定位操作通常称为串的模式匹配。

  朴素的模式匹配算法，显得很低效。

3.2 KMP模式匹配算法

  可以大大避免重复遍历的情况。

第四章：树

  以上都是一对一的数据结构，树是一对多的数据结构。

4.1 结点分类

  结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶子结点(Leaf)或终端结点。树的度是树内各结点的度的最大值。

4.２ 结点间关系

  结点的子树的跟称为该结点的孩子(Child)，相应的，该结点称为该孩子的双亲(Parent)。同一个双亲的孩子之间称为兄弟(Sibling)。

4.３ 树的其它概念

• 结点的层次
• 树的深度
• 森林：是m棵互不相交的树的集合

4.4 树的存储结构

  存储结构为结构体+数组

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法（基本上就是二叉树的原型）

4.5 二叉树

• 斜树
• 满二叉树
• 完全二叉树

4.6 二叉树的性质

  p169

4.7 二叉树的存储结构

• 顺序存储结构（数组），一般只用于完全二叉树
• 链式存储结构（二叉链表），常用存储方式

4.8 遍历二叉树

• 前序遍历
• 中序遍历
• 后序遍历
• 层次遍历

4.9 创建二叉树

  参考遍历方式。

4.10 线索二叉树

4.11 树、二叉树、森林的转换

4.12 赫夫曼树及其应用

  压缩的原理。

第五章：图

  数据元素称为“顶点”。

• 网（带权值的图）
• 连通图（顶点互通）
  • 连通分量
• 生成树：n个顶点，n-1条边
• 有向树

5.1 图的存储

• 邻接矩阵
  • 一维数组存顶点
  • 二维数组存边
• 邻接表
  • 一维数组存顶点
  • 单链表存边
• 十字链表（针对有向图）
• 邻接多重表
• 边集数组

5.2 图的遍历

• 深度优先遍历(DFS)，递归的方式
• 广度优先遍历(BFS)，非递归

5.3 最小生成树

  带权值的网图，n个顶点，n-1条边把一个连通图串起来。并使得权值的和最小。

• 普利姆算法(Prim)（以某顶点为起点，找到最小的边）
• 克鲁斯卡尔算法（以某边为起点）

5.4 最短路径

• Dijktra（得到单一顶点到其它所有点的最短路径）
• Floyd（得到所有顶点到所有顶点的路径）

5.5 拓扑排序

  可用于判断一个给定的图是否有有向无环图。

第六章：查找

• 顺序表查找
• 有序表查找
  • 折半查找
  • 插值查找
  • 斐波那契查找
• 索引查找
  • 线性索引
    • 稠密索引
    • 分块索引
    • 倒排索引
  • 树形索引
  • 多级索引
• 二叉排序树（动态查找，可在查找的时候插入、删除）
  • 平衡二叉树
  • 多路查找树
• 散列表查找（哈希表hashtable），主要是面向查找的存储结构
  • 处理三列冲突的方法
    • 开放定址法
      • 线性探测
      • 二次探测
      • 随机探测
    • 再散列函数法
    • 链地址法（Java集合中HashTable的查原理用是的就是这种方法）

  这一章令我最印象深刻的就是散列表查找了。因为之前在学习Java集合的时候，接触过HashTable集合。它里面的查逻辑就是使用的散列表查询。那段时间对于hash还是很懵懂的样子，现在终于搞懂了其中的奥妙~

第七章：排序

  不多说，直接上代码！

#include <stdio.h>
#include <stdlib.h>

#define N 500

#define MAXSIZE 10
#define MAX_LENGTH_INSERT_SORT 7
#define TRUE 1
#define FALSE 0

typedef int BOOL;

typedef struct{

    // r[0]一般作为哨兵或者临时变量
    int r[MAXSIZE+1];
    int length;

}SqList;

void swap(SqList *L, int i, int j){

    int temp = L->r[i];
    L->r[i] = L->r[j];
    L->r[j] = temp;

}

/* 对顺序表L作交换排序（冒泡排序初版） */
void BubbleSort0(SqList *L){

    int i,j;
    for(i = 1; i < L->length; i++){
        for(j = i+1; j <= L->length; j++){

            if(L->r[i]>L->r[j]){
                swap(L,i,j);
            }
        }
    }
}

/* 正宗冒泡排序算法*/
void BubbleSort1(SqList *L){

    int i,j;
    for(i = 1; i < L->length; i++){
        for(j = L->length-1; j>=i; j--){
            if(L->r[j] > L->r[j+1])
                swap(L, j, j+1);
        }
    }

}

/* 冒泡排序算法的优化，常用此算法 */
void BubbleSort2(SqList *L){

    int i,j;
    BOOL flag = TRUE;
    for(i = 1; i < L->length && flag; i++){

        flag = FALSE;
        for(j = L->length-1; j>=i; j--){
            if(L->r[j] > L->r[j+1]){
                swap(L, j, j+1);
                flag = TRUE;
            }
        }
    }
}

/* 直接插入排序，性能是简单排序里最好的 */
void InsertSort(SqList *L){

    int i, j;
    for(i = 2; i <= L->length; i++){
        if(L->r[i] < L->r[i-1]){
            // 新来的卡牌设置为哨兵，作为后面的循环终止的判断依据
            L->r[0] = L->r[i];
            for(j = i-1; L->r[j]>L->r[0]; j--){
                // 记录后移
                L->r[j+1] = L->r[j];
            }
            // 将牌插入到正确的位置
            L->r[j+1] = L->r[0];
        }
    }
}

/* 对顺序表L作归并排序 */
void MergeSort(SqList *L){

    MSort(L->r, L->r, 1, L->length);

}

/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] */
void Merge(int SR[], int TR[], int i, int m, int n){

    int j,k,l;
    for(j=m+1,k=i; i<=m && j<=n; k++){
        if(SR[i]<SR[i++])
            TR[k] = SR[i++];
        else
            TR[k] = SR[j++];
    }

    // 将剩余的SR[i..m]复制到TR
    if(i<=m){
        for(l=0;l<=m-i;l++)
            TR[k+l] = SR[i+l];
    }

    // 将剩余的SR[j..n]复制到TR
    if(j<=n){
        for(l=0;l<=n-j;l++){
            TR[k+l] = SR[j+l];
        }
    }
}

/* 将SR[s..t]归并排序为TR1[s..t] */
void MSort(int SR[], int TR1[], int s, int t){

    int m;
    int TR2[MAXSIZE+1];
    if(s == t){
        TR1[1] = SR[s];
    }
    else{

        // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
        m = (s+t)/2;
        // 将SR[s..t]归并排序为TR2[s..m]
        MSort(SR, TR2, s, m);
        // 将SR[m+1..t]归并排序为TR2[m+1..t]
        MSort(SR, TR2, m+1, t);
        // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
        Merge(TR2, TR1, s, m, t);
    }
}

/* 将SR[]中相邻长度为s的子序列两两归并到TR[] */
void MergePass(int SR[], int TR[], int s, int n){

    int i = 1;
    int j;
    while(i <= n-2*s+1){

        // 两两归并
        Merge(SR, TR, i, i+s-1, i+2*s-1);
        i = i+2*s;

    }

    // 归并最后两个序列
    if(i < n-s+1)
        Merge(SR, TR, i, i+s-1, n);
    else
        for(j = i; j <= n; j++)
            TR[j] = SR[j];
}

/* 对顺序表L作非递归排序，归并排序常用此算法 */
void MergeSort2(SqList *L){
    // 申请额外空间
    int* TR = (int*)malloc(L->length * sizeof(int));
    int k = 1;
    while(k<L->length){

        MergePass(L->r, TR, k, L->length);
        // 子序列长度加倍
        k = 2*k;
        MergePass(TR, L->r, k, L->length);
        // 子序列长度加倍
        k = 2*k;

    }
}

/* 快速排序优化算法
   交换顺序表L中子表的记录，使枢轴记录到位，并返回其所在位置
   此时在它之前（后）的记录均不大（小）于它
*/
int Partition(SqList *L, int low, int high){

    int pivotkey;
    // 计算数组中间的元素的下标
    int m = low + (high - low)/2;
    // 交换左端与右端数据，保证左端较小
    if(L->r[low] > L->r[high])
        swap(L, low, high);
    // 交换中间与右端数据，保证中间较小
    if(L->r[m] > L->r[high])
        swap(L, high, m);
    // 交换中间与左端数据，保证左端居中，此时L->r[low]已为整个序列左中右三个关键字的中间值
    if(L->r[m] > L->r[low])
        swap(L, m, low);

    // 用子表的第一个记录作枢轴记录
    pivotkey = L->r[low];

    // 将枢轴关键字备份到r[0]
    L->r[0] = pivotkey;
    while(low < high){

        while(low < high && L->r[high] >= pivotkey)
            high--;
        // 将比枢轴记录小的记录替换到低端
        L->r[low] = L->r[high];
        while(low < high && L->r[low] <= pivotkey)
            low++;
        // 将比枢轴记录大的记录替换到高端
        L->r[high] = L->r[low];
    }
    // 将枢轴记录替换回L->r[low]
    L->r[low] = L->r[0];
    return low;
}

/* 对顺序表L中的子序列L->r[low..high]进行快速排序 */
void QSort(SqList *L, int low, int high){

    int pivot;

    if((high - low) > MAX_LENGTH_INSERT_SORT){
        while(low < high){

            /* 将L->r[low..high]一分为二，并算出枢轴值pivot */
            pivot = Partition(L, low, high);

            // 对低子表递归排序
            QSort(L, low, pivot-1);
            // 尾递归（对高子表进行递归排序）
            low = pivot + 1;
        }
    }
    else
        InsertSort(L);

}


/* 对顺序表L作快速排序 */
void QuickSort(SqList *L){

    QSort(L, 1, L->length);

}

int main()
{
    SqList s;
    int temp[10] = {99,1,5,18,3,7,4,6,2,11};
    memcpy(s.r, temp, 10*sizeof(int));
    s.length = 9;

    QuickSort(&s);

    for(int i = 1; i <= s.length; i++){
        printf("%d ", s.r[i]);
    }
    printf("
");

    printf("Hello world!
");

    return 0;
}

  以后麻麻再也不用担心我不会写快排啦~