大话数据结构

本文是《大话数据结构》的笔记。

第1章数据结构绪论

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据元素的逻辑结构有 集合 线性 树型 图形 4 种，存在计算机内存里，就只有 顺序存储 和 链接存储 2 种。

抽象数据类型ADT：一个数学模型以及定义在该模型上的一组操作。它的定义仅仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。

ADT 类型名
Data
    数据 ...
Operation
    操作1 .. 初始条件，操作结果
    操作2 ..

第2章算法

算法：解决特定问题求解步骤的描述，在计算机中表现为有限的指令序列。基本特征：输入、输出、有穷、确定、可行。

时间复杂度：语句总执行次数T(n)关于元素个数n的函数，分析T(n)的数量级，记做O(T(n)),称为算法的渐进时间复杂度。

从T(n)到O(T(n))的推导方法，以2n^2 + 4n + 3为例：

函数中，常数忽略不计，只保留最高项，去除4n+3
去除最高项的系数，去除2,所以结果为O(n^2)

int i = 1;
while( i <= n ){
    i = i * 2;
}

上面这段代码的时间复杂度为O(log(n))，再次思考下“时间复杂度用来衡量代码执行的次数”，上面代码，每执行一次，就是乘以 2, 所以可以理解为，当 2 的 x 次方大于等于 n 时循环结束， x 就是代码的执行次数，求对数，就是 x = log2(n) ，把底数忽略掉，就是 log(n)了。

时间复杂度又分为：

渐近时间复杂度（只保留二项式最高项、去除常数项和系数）
最好时间复杂度（以长度为n的数组中，找到某数为例，当它处于数组第一位时）
最坏时间复杂度（例子同上，当它处于数组第n位时或不存在时）
平均时间复杂度（例子同上，，把所有情况的次数加总，再除于情况数）
加权平均时间复杂度（例子同上，每种情况发生的概率是不一样的，需要加权平均，计算期望值）
均摊时间复杂度（以C++动态数组Array的构造为例）

均摊时间复杂度例子如下：

// 全局变量，大小为10的数组array，长度len，下标i。
int array[] = new int[10]; 
int len = 10;
int i = 0;

// 往数组中添加一个元素
void add(int element) {
   if (i >= len) { // 数组空间不够了
     // 重新申请一个2倍大小的数组空间
     int new_array[] = new int[len*2];
     // 把原来array数组中的数据依次copy到new_array
     for (int j = 0; j < len; ++j) {
       new_array[j] = array[j];
     }
     // new_array复制给array，array现在大小就是2倍len了
     array = new_array;
     len = 2 * len;
   }
   // 将element放到下标为i的位置，下标i加一
   array[i] = element;
   ++i;
}

第3章线性表

线性表：零个或多个数据元素的有限序列。

ADT List
Data {a1,a2,a3,a4,a5}
Operation
    init_list( *L );
    is_empty( *L );
    clear_list( *L );
    get_elem( int i );
    len( *L );
    insert( *L, int i, elem );
    delete( *L, int i, *e );
    search( L, elem );

顺序存储结构的线性表

使用顺序存储结构来实现线性表，即用一段连续的内存地址存储单元，依次存储线性表的数据元素：

顺序存储结构需要的三个属性:

存储空间的起始位置
线性表的最大存储元素个数
线性表当前存储元素个数

#define MAXSIZE 20          // 最大存储元素个数
typedef int ElemType;       // 元素类型视情况而定，这里暂时定为 int

typedef struct{
    ElemType data[MAXSIZE]; // data 即为存储空间的起始位置
    int length;             // 线性表当前存储元素个数
} SqList;

获取操作：获取第n个元素，data + n运算，O(1)性能，具有这一特性称为随机存储结构
插入操作：O(n)性能，要考虑存储已满，插入位置不在范围内等异常情况
删除操作：O(n)性能

顺序存储结构的缺点：插入和删除太慢，需要移动大量元素。

链式存储结构实现线性表

链式结构概念：节点、指针域、数据域。

// 节点(单链表)
typedef struct Node{
    struct Node *next;  // 指针域
    ElemType data;      // 数据域
} Node;

// 定义链表
typedef struct Node* LinkList;

通常对于单向链表，可能会设计一个头节点：它是为了操作的统一和方便设立，放在第一个元素之前，其数据域一般无意义（也可存入链表长度等信息），有了头结点，在第一个元素结点前插入结点与删除第一结点的操作就与其他结点前的操作统一了。

单链表的获取值为val的元素：只能从头开始，依次对比，O(n)性能。

单链表的插入:

单链表的删除：

在链表中某个值前后插入元素，或删除某个值为val的元素，都是要从头节点开始去查找的，性能O(n),找到相应结点后。接下来只是简单的移动指针而已，不需要移动大量内存数据。

所以如果我们预先知道，某个结点的位置，那么性能O(1)

双向链表

typedef struct DouNode{
    struct DouNode *pre;
    struct DouNode *next;
    ElemType data;
} DouNode;

typedef DouNode * DouLinkList;  // 双向链表

插入操作:

双向链表插入操作

删除操作:

双向链表删除操作

双向循环链表:

双向循环链表

写好链表相关代码的要点：

1.要非常清楚“指针”的含义，要非常清楚的知道“指针”的指向：

p -> next = q;                  // p 节点 指向 q 节点
p -> next = p -> next -> next;  // p 节点 指向 它的 “下下节点”

2.插入时警惕 “指针丢失”

比如在单链表的 a节点与 b节点之间插入 x节点：

a->next = x;            // a -> next 存放的 b节点 的地址在这一步 “丢失”
x->next = a->next;

// 正确写法
x->next = a->next;
a->next = x;

3.删除时警惕 “内存泄漏”

单链表的 a节点 b 与 c节点，删除 b 节点：

a->next = b->next;      // a节点 指向 c节点
delete(b);              // b节点已经无任何指针指向了，不主动删除，就发生了“内存泄漏”

4.引入“哨兵”节点，统一代码逻辑

思考下，如果没有“头节点”，链表的 “插入节点” 和 “删除节点” 代码该如何写?

5.留意边界条件的处理

如果链表为空时，代码是否能正常工作？
如果链表只包含一个结点时，代码是否能正常工作？
如果链表只包含两个结点时，代码是否能正常工作？
代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

6.练习

单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第n个节点
求链表的中间节点

第4章栈和队列

顺序存储结构的栈

typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];
    int top;                // 栈顶下标
} SqStack;

进栈操作：

共享栈：

typedef struct{
    ElemType data[MAXSIZE];
    int top1;
    int top2;
} SqDoubleStack;

共享栈

PS: 当top1 + 1 = top2时，即为栈满

链式存储结构下的栈

typedef struct StackNode{
    ElemType data;
    struct StackNode *next;
}StackNode, *LinkStackPtr;

typedef struct LinkStack{
    LinkStackPtr top;
    int count;
};

PUSH 和 POP:

顺序存储结构的队列

typedef struct{
    ElemType data[MAXSIZE];
    int front;              // 头元素下标
    int rear;               // 尾元素下标
} SqQueue;

使用数组，为了重复利用空间，而设计的循环结构，rear 与 front 中间留出一个空位：

当 (rear +1) % MAXSIZE == front时，判定队列已满

链式存储结构下的队列

// 节点结构
typedef struct QNode{
    ElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

// 队列的链表结构
typedef struct{
    QueuePtr front,rear; // 队头、队尾指针
}LinkQueue;

进队列：

出队列时，当剩最后一个元素时，需将rear指回头节点，如右图：

第5章串

第6章树

树Tree是 n 个结点的有限集。n=0时称为空树。在任意的非空树中：

根节点root唯一,子节点只有唯一的一个父节点
当n > 1时，其余节点可以划分为多个子树SubTree
度：结点拥有的子树个数，叶节点的度为0
子节点child，父节点parent，层级level，兄弟Sibling、深度depth

树的存储结构

查找一个节点的父亲节点，性能O(1)
查找一个节点的子节点,性能O(1)

#define MAX_TREE_SIZE 100
typedef char TELemType;

// Child Tree Node
typedef struct CTNode{
    int child;           // 孩子节点的下标
    struct CTNode *next; // 下一个孩子节点
}CTNode, *ChildPtr;

// Normal Node
typedef struct TNode{
    TELemType data;
    int parent;          // 父节点下标
    ChildPtr firstchild; // 第一个孩子节点
} TNode;

typedef struct Tree{
    TNode nodes[MAX_TREE_SIZE];
    int root; // 根的位置
    int num;  // 节点数
} Ptree;

二叉树

定义:

每个节点至多有两个子树
左子树与右子树，不能交换，左子树与右子树是完全不同的

五种形态:

五种形态

线索二叉树

利用中序遍历时，叶子节点的lchild与rchild指针为nullptr的空间，替换成前驱，或者后继节点的内存地址，这样我们就可以使用循环（而不是以递归的方式）遍历二叉树，这样的效率更高，栈空间消耗少。

线索二叉树代码参考

第7章图

定义: G(V,E)，G 表示一个图，V 是 G 中顶点的集合，E 是 G 中边的集合。

无向图：G( V, E ), 点集合V = { A, B, C, D } 边集合 E = { (A,B), (B,C), (C,D), (D,A), (A,C) }

无向图

有向图：G( V, E ),点集合 V = { A,B,C,D } 边集合 E = { <A,D>, <B,A>, <C,A>, <B,C> },有向边也称为弧

有向图

Prim 算法（最小生成树）

Kruskal 算法（最小生成树）

DijKstra 算法（最短路径）

Floyd 算法（最短路径）

第8章查找

查找Searching：根据特定的某个值，在查找表中确定一个其关键字等于该值的数据元素。

大话数据结构

第1章 数据结构绪论

第2章 算法

第3章 线性表