目录

《大话数据结构》

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

第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节点 bc节点,删除 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;

WX20190531-140714.png

进栈操作:

WX20190531-140829.png

共享栈:

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;
};

PUSHPOP:

WX20190531-143243.png

顺序存储结构的队列

WX20190531-143911.png

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

使用数组,为了重复利用空间,而设计的循环结构,rearfront 中间留出一个空位:

WX20190531-144253.png

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

链式存储结构下的队列

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

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

WX20190531-144927.png

进队列:
WX20190531-145443.png

出队列时,当剩最后一个元素时,需将rear指回头节点,如右图:
WX20190531-145659.png

第5章 串

第6章 树

Treen 个结点的有限集。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;

二叉树

定义:

  • 每个节点至多有两个子树

  • 左子树与右子树,不能交换,左子树与右子树是完全不同的

五种形态:

五种形态

线索二叉树

利用中序遍历时,叶子节点的lchildrchild指针为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:根据特定的某个值,在查找表中确定一个其关键字等于该值的数据元素。

第9章 排序