README

现在是 2022.3.16 离西电空间院数据结构考试还有38小时不到，我开始复习了。
感觉这篇文章，没有太大的学习价值(当作正经的笔记来学习），只是帮助我在明天晚上差不多这个时候，理解和记忆考试考点而写的。
现在开始吧

数据结构

数据结构主要研究：非数值计算的程序设计中，计算机操作对象以及他们之间的 关系和操作

绪论

基本概念和术语

基本概念

典型结构

集合
线形
树形
图或网络

逻辑与存储

逻辑结构： 具体问题抽象出的数学模型。体现逻辑关系。
物理结构（存储结构）：数据元素（Data Element）及关于在计算机中的表示

DE 存储成为结点
关系存储： a. 顺序存储 b.链式存储 c. 索引存储 d. 散列存储

数据结构广义定义

数据元素的逻辑结构、物理结构、抽象运算

基本操作

插入删除更新排序查找

算法的定义与特征

算法定义

对特定问题求解的一种描述，是指令的有限序列。

算法特征

有穷性
确定性
可行性
0或多个输入
1或多个输出

算法的表述

类C语言（C/C++）
语言的基本结构： 顺序、分支、循环

算法的基本要求

算法分析

两大标准
a. 时间复杂度：
算法中基本操作重复执行的次数（频度）

分为平均时间复杂度和最坏时间复杂度。

b. 空间复杂度：算法所需存储空间
$称此算法原地工作$

复杂度的值取规模函数的最高阶，都是关于开销（时间或者空间）与规模的函数。
常用规则（西电的考试不会用到）
$加法规则$

$乘法规则$

可以结合 洛必达法则 与 函数图像 来证明，口令“常对幂指阶"

线性表

定义与基本操作

定义

略过（考试不会太要求这个

可以是基本数据类型，也可以是 struct 类型

元素同构，且不能出现缺项
元素个数—— 表长度，空表

线性结构特点

“第一个”唯一
“最后一个”唯一
除首个外，每个有且仅有一个直接前驱
除最后外，每个有且仅有一个直接后继

基本运算

typedef int ElemType;
void initList(sq);  // 建立线性表的架构
int ListLen(sq);    // 返回线性表sq的长度
ElemType GetElem(sq, i)；  // 返回第i个数据元素；否则返回NULL
ElemType LocateElem(sq, x);  // 按值查找，找到第一个相应元素的序号
List* LinstInsert(sq, x, i);    // 在线性表sq的第i个位置上增加一个以x为值的新元素
List* ListDelete(sq, i);        // 删除线性表sq的第i个元素ai
ElemType PriorElem(sq, e);  // 返回前驱，否则NULL
ElemType NextElem(sq, e);   // 返回后继，否则NULL

顺序表

这门课内，不考察 动态数组 的实现。

特点

实现逻辑上相邻——物理地址相邻
实现随机存取
（一维数组

优缺点

缺点：
- 插入、删除操作需要移动大量的元素
- 预先分配空间需按最大空间分配，利用不充分
有点：
- 逻辑相邻，物理相邻
- 可随机存取任一元素
- 存储空间使用紧凑
- 表容量难以扩充

单链表

利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素。

结点 = 数据域 + 指针域
数据域：元素本身信息
指针域：只是直接后继的存储位置

顺序vs链式

存储空间
$存储密度结点数据本身占用存储量结点数据占用存储量$
运算时间
程序设计语言

栈与队列

栈

通常插入、删除的一端（表尾）为栈顶top，另一端（表头）为栈底bottom，表中无元素时，称为空栈
特点：先进后出（FILO）或后进先出（LIFO）

#define MAXSIZE 6
typedef struct{
    elemtype elements[MAXSIZE];
    int top;
}SqStack;

基本操作

判空判满

栈空， top = -1, 无法出栈（underflow
栈满， top = MAXSIZE-1，无法入栈（overflow

队列

只能在表的一端进插入，另一段删除

队尾（rear）——允许插入的端

队头（front）——允许删除的端
队列特点：先进先出（FIFO）

#define MAXSIZE 6
typedef struct{
    elemtype elements[MAXSIZE];
    int front, rear;
}SqQueue;

初始化时，均置为-1

基本操作

循环队列

存储队列的数组被当作首尾相接的表处理。
队头、队尾指针加1时从MAXSIZE-1直接进到0，可用语言的取模（余数）运算实现。

王道考研中，rear是最后的空指针，课本里面，rear是最后一个结点。

判空判满

队空 rear = front
队满 (rear + 1) % maxSize = front;

串

串就是字符串，n个字符的有限序列，是一种特殊的线性表。

空串：长度为0的串，没有任何字符
空白串：包含一个或者多个空格字符的串。

空串是任意串的子串
任意串是自身子串

基本操作

感觉ppt上内容很少，也没怎么看明白，kmp应该大概率也不会考，应该只要知道c语言的字符串定义就差不多了。

数组与广义表

这一章的内容比较简单
多画图，通过可视化来研究各种矩阵，展开后的位置。

数组

元素数目固定
元素类型相同
下标有界有序

定义：
由值和下标构成的有序对，结构中的每一个元素都与一对下标有关。

运算：

给定一组下标，存取对应DE
给定下标，修改对应DE

数组可以是多维的，多维数组可以以一维的方式存储。

数组内存地址计算

行优先：
列优先：

压缩存储

多个值相同的元素，分配一个空间
零元素不分配空间。

特殊矩阵

对角矩阵

单对角矩阵（左）三对角矩阵（右）

用一维数组进行压缩存储，

上（下）三角矩阵

对称矩阵
同三角矩阵

这里的做法就是，按照 行优先 或者 列优先，求出任意(i,j)元素前面的元素数量

稀疏矩阵

中非零原属个数远小于零元素个数
组成：所有非零元素（行，列，值） + （行数，列数，非零元素个数）

稀疏矩阵转置算法思想

时间复杂度：

广义表

广义表（lists, 又称列表）是线性表的推广（表中有表）。

性质：

元素可以是子表，子表的元素也可以是子表
具有递归和共享的性质

长度: 最外层的长度
深度: 最大嵌套次数
求表头: Head(Ls)
求表尾: Tail(Ls) 求表的最后一个子表，用小括号（）包起来

树

定义

tree是个结点的有限集

有且仅有一个特定的结点，称为树的**根(root)**，只有直接后继，没有直接前驱
当时，其余结点可以分为个互不相交的有限集，T1,T2,,Tm，其中每个集合本身又是一棵树，称为根的子树(subtree)
if n = 0, 称为空树；

特点： a. 树中至少有一个结点——根 b. 树中各子树是互不相交的集合

基本运算&术语

二叉树

二叉树是n（n>=0)个结点的有限集，或为空树（n=0），或由一个结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。

结点至多两棵子树（不存在度大于2的结点）
二叉树的子树有左、右之分，且其次序不能任意颠倒

二叉树的性质

二叉树在第层上，最多有个结点
深度为k的二叉树，最多有个结点
对二叉树，若叶结点树为，度为2的非叶子结点个数为，则有
完全二叉树，具有n个结点的完全二叉树的高度为
对于完全二叉树，结点序列按照层序编号，则有
1. i=1，这个结点是根，无双亲；i>1，双亲是
2. 2i>n, 则无左孩子，否则2i是左孩子
3. 2i+1>n，则无右孩子

特殊二叉树

满二叉树
完全二叉树

存储结构

顺序存储结构——适合满二叉树和完全二叉树
链式存储

二叉树遍历

先序遍历
中序遍历
后序遍历
层序遍历
这几个非常重要，层序遍历需要用上队列。

线索二叉树，不看，考试补考

树的存储结构

一、双亲表示法

孩子不好找，寻找结点的孩子，需要遍历全部结点

二、孩子表示法
每个结点的孩子，用单链表存储

三、孩子双亲表示法
以上三种，都不是很重要

四、孩子兄弟表示法（二叉树法，这个直接记住
可以把所有都结点转化为，孩子和兄弟，左孩子，右兄弟，所有树都变成二叉树

缺点，找双亲比较麻烦

孩子兄弟转换法，森林转换

森林变二叉树
- 各树转成二叉树
- 每棵树结点用线链接
- 第一棵树的跟结点作为第二棵树的跟结点，按顺时针方向旋转（其他的树，当第一棵树的兄弟

二叉树转变成森林

Huffman树

一种构造出有最小路径和的算法

图

定义：

—— 顶点的，有穷、非空集合；
—— 边的集合

有向图：每条边都有方向
无向图：每条边都没方向

不考虑指向自身的边，与重复出现的边

完全有向图：任一顶点到其余个顶点都有弧
完全无向图：任两个顶点都有边
稀疏图：
稠密图：

基本概念

表示方法

邻接矩阵

邻接表

顶点的出度：该顶点在对应连标结点数；
顶点的入度：结点序号在所有连标中出现次数

十字链表、邻接多重表（不列举

邻接矩阵表示唯一；邻接表形态于边的输入次序有关;

遍历

深度优先搜索DFS

先序遍历，碰到就访问

时间复杂度：空间复杂度：

广度优先搜索BFS

连通性

DFS和BFS只能遍历一个连通分量，遇到多个连通分量，需要多次调用

生成树

树：无回路的连通图
生成树：连通图的绩效连通子图（n个顶点，n-1条边）

连通网：各边带权的连通图；其生成树全值为各边全值之和。

MiniCost Spanning Tree

Prim

找最短路径
找连接目前回路的最短路径（引入新结点
不断的加入新结点

时间复杂度：与边数无关，适合边稠密网

Kruskal

不停的找最短边，直到所有连通分量连通

时间复杂度：与顶点数无关，适合边稀疏网

拓扑排序

AOV网
问题发生在，无环有向图（DAG图)

基本步骤：

选入度为零的顶点输出
删除改点与相关点
重复步骤1，2，若无结点，完成；还有结点，说明有回路

最短路径

dijkstra

从一个点出发，找到其他点，最近点距离
然后查找，经过上一个结点，初始位置能到达点最短距离
只是一个结点的运算时间复杂度：遍历所有结点

floyd

初始状态 -> z0为中转点 -> z1为中转点。。。 ->

查找

静态查找表：顺序查找、二分查找和顺序索引 (查询、检索)
动态查找表：二叉排序树、平衡二叉树（查询、检索、插入、删除
哈希表

关键字：数据元素（记录）某个数据项点值

主关键字：可以唯一的识别一个记录的关键字（学号
次/辅关键字：可以识别若干记录的关键字

平均查找长度

查找算法

顺序查找

int Searth_Seq(Stable R[],keytype key){
  int i=n;R[0].key = key;
  while(R[i].key != key)
    i--;
  return (i);  
// 添加了R[0] 充当监视哨，优化了反复盘踞
}

$成功$
简单、适用范围广，ASL大

折半查找

又称二分查找
条件：有序表查找
采用分治思想

int BinSearch(Stable R[], keytype key){
  low = 1; high = n;  // 置上下界值
  while(low <= high){
    mid = (low + high)/2;
    if(key == R[mid].key) return mid; // 成功
    if(key < R[mid].key)  high = mid - 1; // 查找左子表
    else  low = mid + 1;  // 查找右子表
  }
  return 0; // 失败
}

二叉排序树（BST

或是空树，或者有以下性质

左子树不空，左子树上所有结点小于root
右子树不空，右子树上所有结点大于root
左右都是BST

中序遍历 可以得到一个递增序列

二叉树查找

BiTree SearchBST(BiTree T, keytype key){
  while(!T){
    if(T->key == key) return T;
    if(T->key > key)  T=T->lchild;
    else T = T -> rchild;
  }
  return NULL;
}