第 01 章 基本概念

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的一门学科

四类基本数据结构：集合，线性，树，图

数据类型：一组性质相同的值的集合以及这个集合上的操作的一组总称

抽象数据类型：指一个数学模型以及定义在该模型上的一组操作

算法：对特定问题求解步骤的一种描述，指令的有限序列

算法的五个特性：有穷性，确定性，可行性，0个或多个输入，1个或多个输出

算法的设计要求：正确性，可读性，健壮性，高效率，低存储

时间复杂度的计算：只考虑基本操作（可以这么理解：最深那一层括号中的语句都属于基本操作），即基本操作的重复次数是问题规模n的某个函数f(n)，记作：T(n) = O(f(n))

频度：基本操作的执行次数

加工型操作：会修改元素

引用型操作：只用不改

第 02 章 线性表

线性表：n个数据元素的有限序列

4个唯一：

• 存在唯一一个被称作“第一个”的数据元素
• 存在唯一一个被称作“最后一个”的数据元素
• 除第一个之外的数据元素均只有一个前驱
• 除最后一个之外的数据元素均只有一个后继

存储方式

• 顺序：用一组地址连续的存储单元依次存储
  • 优点：随机存取
  • 缺点：插入或删除元素不方便
• 链式：用一组物理位置任意的存储单元来存储
  • 优点：插入或删除元素很方便
  • 缺点：非随机存取

本章涉及到的一些存储结构

// 顺序存储结构
typedef struct {
    ElemType *elem; // 数组
    int length; // 有效长度
    int listSize; // 分配的空间
} SqList;

// 链式存储结构
typedef struct LNode {
    ElemType data; // 数据域
    struct LNode *next; // 指针域
} LNode,*LinkList; // LinkList是指向单链表的指针，由此唯一确定一个单链表

第 03 章 栈与队列

栈：限定在表尾进行插入或删除操作的线性表，后进后出

这里的表尾即是栈顶，表头是栈底

队列：限定在表的一端插入，另一端删除的线性表，先进先出

插入的一端称为队尾，删除的一端称为队头

本章涉及到的一些存储结构：

// 顺序栈的存储结构
typedef struct {
    SElemType *base; // 栈底指针
    SElemType *top; // 栈顶指针，灵魂所在
    int stackSize; // 分配的空间
} SqStack;

// 链栈的存储结构
typedef struct StackNode {
    SElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

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

// 循环队列
typedef struct {
    QElemType *base;
    int front;
    int rear;
} SqQueue;

// 链队列的存储结构
typedef struct QNode {
    QElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front; // 队头
    QueuePtr rear; // 队尾
} LinkQueue;

第 04 章 串

串：0个或多个字符组成的有限序列

串相等：两个串长度相等且各个对应位置的字符都相等

子串：由串中任意个连续的字符组成的子序列

kmp算法：next数组要解决的时当模式串失配的时候，该指向的位置

next数组的求法

nextval数组的求法

第 05 章 数组和广义表

数组：具有相同类型的数据元素的集合

两种顺序存储方式：

• 以行序为主序（按一行一行的顺序存）
• 以列序为主序（按一列一列的顺序存）

稀疏矩阵：在m x n的矩阵中有t个非零元素，令 L = t/(m x n)，当L <=0.05时称为稀疏矩阵

• 三元组顺序表
• 十字链表

广义表：n个元素的有限序列，每一个元素可能是原子，也可能是一个子表

• 表头：第一个元素就是表头，可以是原子，也可以是子表
• 表尾：除表头之外的其他元素组成的表
• 长度：最外层所包含元素的个数
• 深度：该广义表展开后括号的重数，深度可以理解为有多少组括号。
  • 原子深度为0，空表深度为1
  • 递归表的深度是无穷值，长度是有限值

本章涉及到的一些存储结构：

// 稀疏矩阵的三元组顺序存储结构
typedef struct {
    int i, j; // 该非零元素的下标
    Element e;
} Triple;
typedef struct {
    Triple data[MAX_SIZE + 1]; // 下标为0的空间不用
    int mu, nu, tu; // 行数，列数，非零元素个数
} TSMatrix;

// 广义表的首尾链表表示法
typedef enum {
    ATOM, LIST
} ELemtag;
typedef struct GLNode {
    Elemtag tag; // 标志域，用于区分元素结点和表结点 
    union { // 元素结点和表结点的联合部分 
      Atomtype atom; // atom 是原子结点的值域 
      struct {
          struct GLNode *hp, *tp; // hp和tp分别指向表头和表尾 
      }ptr; // ptr是表结点的指针域
    };
  }*GList;                           

// 广义表的孩子兄弟链表表示法
typedef enum {
    ATOM, LIST
} ELemtag;
typedef struct GLNode {
    ELemtag tag; // 标志域
    union {
        AtomType atom; // 原子结点的值域
        struct GLNode *hp; // 表结点的指针
    };
    struct GLNode *tp;// 指向兄弟结点
} *GList;

第 06 章 树和二叉树

• 树：n个结点的有限集，n=0 称为空树，若n>0，则有且仅有一个“根”，其余为根的子树
• 度：结点拥有的子树数量（树的度是树内各结点的度的最大值）
• 二叉树：由一个根结点及左子树和右子树组成（与树的区别就是二叉树严格区分左右，这是二叉树与树的主要区别）
  • 二叉树中不存在度大于2的结点
  • 子树有左右之分
• 满二叉树，一颗深度为k的且有2^k -1个结点的二叉树
• 完全二叉树，这颗深度为k的二叉树与同样深度为k的满二叉树中编号为1~n的结点一一对应上时，称为完全二叉树（完全二叉树是路径长度最短的二叉树）
• 关于二叉树的性质：
  • 性质1：在二叉树的第i层上至多有 2^(i-1)个结点
  • 性质2：深度为k的二叉树至多有2^k -1个结点
  • 性质3：对任何一棵二叉树T，如果其叶子数为n，度为2的结点树为m，则 n = m + 1
  • 性质4：具有n个结点的完全二叉树的深度为log2n + 1
  • 性质6：在n个结点的二叉链表中有n+1个空指针域

遍历二叉树：巡访二叉树中的结点，使得每一个结点均被访问且仅被访问过一次

• 先序：根，左，右
• 中序：左，根，右
• 后序：左，右，根

线索二叉树：根据遍历二叉树的方法，使用结点的空闲位置，指出前驱结点或后缀结点，实质是在遍历的过程中用线索取代空指针

中序前驱左孩找右，中序后继右孩找左

哈夫曼树：带权路径长度最短的二叉树

• 包含n个叶子结点的哈夫曼树中共有2n-1个结点
• 哈夫曼树中的结点的度或为0或为2

本章涉及到的一些存储结构：

// 二叉树的存储结构
typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; // 左右孩子
} BiTNode, *BiTree;

// 树的双亲表示法
typedef struct PTNode {
    TElemType data;
    int parent; // 双亲位置
}PTNode;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int r,n; // n是结点数，r是根结点的下标
}PTree;

// 带双亲的孩子链表表示法
typedef struct CTNode { // 链表结点
    int child; // 孩子的下标
    struct CTNode *next;
} *ChildPtr;
typedef struct { // 结点
    int parent; // 双亲的下标
    TElemType data;
    ChildPtr firstChild; // 指向第一个孩子的指针
} CTBox;
typedef struct { // 树结构
    CTBox nodes[MAX_TREE_SIZE];
    int n, r; // n是结点数，r是根结点的下标
} CTree;

// 孩子兄弟表示法
typedef struct CSNode {
    ElemType data;
    struct CSNode *firstChild,*nextsibling; // 第一个孩子，兄弟结点
}CSNode,*CSTree;

第 07 章 图

图是由顶点的有穷非空集合和顶点之间边的集合组成的

边：无向图中的连线

弧：有向图中的连线

无向完全图：任意两顶点都存在边的无向图，含有n个顶点的无向完全图有n(n-1)/2条边

有向完全图：任意两顶点都存在方向互为相反的两条弧，有n个顶点的有向完全图有n(n-1)条边

权：与边或弧相关的数

网：带权的图

子图：顶点和边各自的子集

在无向图或者有向图中，边的数目总和 = 度的总和/2

连通：如果说从顶点a到顶点b有路径，则称a和b是连通的

连通图：图中任意两个顶点都是连通的

连通图至少有n-1条边，当边的数目小于n-1，则此图一定是非连通图

强连通图：任意两个顶点都连通的有向图

生成树：所有顶点均由边连接在一起但不存在回路的图

• 顶点个数与图的顶点个数相同
• 生成树的图的极小连通子图
• 一个有n个顶点的连通图的生成树有n-1条边

图的各种存储结构：

• 邻接矩阵：使用两个数组，一个一维数组存储顶点形象，另外一个二维数组存储边或弧的关系
  • 有向图中行的1的个数是顶点的出度，列的1的个数是顶点的入度
  • 无向图中顶点的度是行或列中的1的个数
• 邻接表，类似树的孩子链表表示法，有向图的又分为邻接表（找出度易）和逆链接表（找入度易）
• 十字链表，仅适用于有向图

不知道什么时候记录的：

在无向图中，表结点的个数是边的个数的2倍

有向图中，表结点的个数是边的个数

图的遍历：

• 深度优先遍历：当前访问的顶点有未被访问的邻接顶点，则选其一访问，重复不断，反之则退回到上一个顶点（连通图的深度优先遍历类似于树的先根遍历）
• 广度优先遍历：从某一顶点出发，访问其所有的邻接顶点，然后按次序再访问其所有的邻接顶点（一层一层的扫描，类似树的层序遍历）

最小生成树：在一个无向网中，使得各边权数之和最小的那棵生成树

构造最小生成树的两个算法：

• 普里姆算法：从某个顶点开始，逐个找个各顶点最小权值的边
• 克鲁斯卡尔算法，依次加入最小的连通分量，但是不能形成环

最短路径问题：

• 从某个源点到其余顶点的最短路径问题：迪杰斯特拉算法：在求出的最短路径的基础上求出其他结点的最短路径
• 每对顶点间的最短路径问题，佛洛伊德算法：逐步试着在原直接路径中增加中间顶点，若加入后路径变短，则修改之

有向无环图：有向图中不存在环，简称DAG图

AOV网：用DAG图表示一个工程，顶点表示活动

拓扑排序：找到做事的先后顺序

1. 在有向图中选一个没有前驱（即入度为0）的顶点并输出之
2. 从图中删除该顶点和所有以它为尾的弧
3. 重复上面两部，直到全部顶点均已输出，或者当图中不存在无前驱的顶点为止

AOE网：顶点表示事件，弧表示活动，弧的权表示活动持续时间

• 关键路径：路径长度最长的路径
• 关键活动：最迟开始时间和最早开始时间相等的活动
• 关键事件：最迟开始时间和最早开始时间相等的事件

第 09 章 查找

静态查找：只查找

• 顺序查找
• 折半查找-针对有序表
• 索引查找-分块有序（但是块内是无序的）

动态查找：查找后插入或者删除

• 二叉排序树：左子树的值比根小，右子树的值比根大，中序遍历二叉排序树可得到一个关键字的有序序列
• 二叉排序树的删除：
  • 被删除结点为叶子结点，那就直接删除就行
  • 若被删除结点只有左子树，则用左孩子替代，若只有右子树，则用右孩子替代
  • 左右子树都非空，用被删除结点的中序直接前驱替代，或者用中序直接后继替代，或者用左子树直接替代

---

散列表，Hash Table，又称为哈希表，特点：数据元素的关键字与其存储地址直接相关，关键字通过哈希函数（散列函数）确定存储地址

• 同义词：不同关键字通过散列函数映射到同一个值
• 冲突：通过散列函数确定的位置存放了其他元素

解决冲突：链地址法

第 10 章 排序

内部排序：待排序的所有记录全部放置在内存中

外部排序：待排序的记录个数太多，需要使用到外存