数据结构基础知识点_数据结构常考基础知识

1.线性表

1.线性表的概念

2.线性表的顺序存储地址计算

3.线性表的顺序存储结构

3.1.顺序表的插入

L->length-1,i-1:数组的索引，要减一
L->elem[j+1]=e:循环判断条件是j>=i-1，原索引为i-1的数据往后移了一位，但是循环内又–j，要加回来

3.2.顺序表的删除

L->elem[j-1]=L->elem[j]:删除第i个元素，其索引为i-1，其后为L->elem[i]，现在循环初始条件为j=i，故要从j-1处开始从前向后每个元素向前移动一位

4.线性表的链式表示

单链表的定义：嵌套定义

4.1.头指针、头结点、首元结点

头指针：链表中第一个节点的存储位置，具有标识作用，通常用头指针冠以链表的名字
头结点：放在第一个元素结点之前，其数据域一般无意义（也可以存放链表的长度、用作监视哨），非必需

首元结点：第一个元素的结点

4.2.单链表、双链表、循环链表

4.3指针的基本操作

4.4单链表的插入

带头结点

不带头结点

伪代码

!p->next:p为空
p->next=s:此时定位成功，p->data=ai-1,
算法分析：先后再前

4.5单链表的删除

思路：先找到该位置的前驱结点，然后p->next=p->next->next

2.栈与队列

1.栈的概念

特性：后进先出(LIFO)的线性表

1.1顺序栈的实现

base:栈底指针，初始化完成后始终指向栈底的位置，若base=NULL，则表明栈结构不存在；作用：初始化时指向请求空间的基地址，即S.base=new SElemTpe[MAXSIZE]
top：栈顶指针，其初值指向栈顶；作用：判断栈空栈满、出入栈时指针的加减
本书中，约定栈空时top=0

1.2顺序栈的栈空、栈满、出栈、入栈等一些基本操作

进栈：先放再加，即*S.top++=e
出栈：先减再放，即e=*–S.top
—因为栈顶指针始终指向栈顶元素的下一位置，S.top自身指向的空间是没有元素的
栈空：S.top==S.base
获取栈顶元素而不修改栈顶指针：return *(S.top-1)
取栈长：return (S.top-S.base)
示意图：
栈非空时，top指针始终指向现存栈顶元素的下一个位置

上溢：出错现象，应避免
下溢：可能是正常现象，以为其初态为空栈，所以下溢常常用来作为程序控制转移的条件

1.3链栈的实现（与单链表LinkList一样）

typedef struct StackNode{
	ElemType data;
	struct StackNode *next;
}StackNode,*LinkStack;
1
2
3
4

1.4链栈的初始化、入栈、出栈、取栈顶元素

初始化：初始化本身就是构造一个空栈，故：S=NULL
入栈：链栈的链头即栈顶，且不需要再判断栈是否满了，直接为入栈元素动态分配一个结点空间即可：

p = new StackNode;//新建结点空间
p->data=e;//令p的数据域为e
p->next=S;//将新结点插入栈顶
S=p;//修改栈顶指针为p

出栈：要判断栈是否为空，用引用型变量&e来返回出栈元素：

e=S->data;//用e返回要出栈元素数据域
p=S;//p指向栈顶元素空间
S=S->next;//修改栈顶指针
delete p;//释放原栈顶空间

2.队列的概念

特性：先进先出(FIFO)的线性表

2.1顺序队列的实现

front:头指针，队列元素出队时++，始终指向队头元素
rear:尾指针，队列元素入队时++，始终指向队尾元素的下一位置
空队列：初始化创建空队列时，令front=rear=0

2.2顺序队列出现的问题

由于队列“队尾入队，队头出队”这种受限制的操作，可能出现“假溢出”现象，即当Q.rear=MAXQSIZE之后，如上图(d)所示，即便J1,J2,J3已经出队了，队列SqQueue不是满队列，但是再在rear队尾新增队列元素，就会因数组越界而导致程序的非法错误。
解决方案：循环队列

2.3循环队列的对空、队满、初始化、入队、出队、取队头元素等操作

少用一个元素空间，即循环队列中有MAXQSIZE-1个元素则认为是队满
队空：Q.rearQ.front
队满：Q.front（Q.rear+1）%MAXIQSIZE
初始化：请求空间Q.base = new QElemType[MAXQSIZE];后，头尾指针置为0即可：Q.rear=Q.front=0;
求队长：return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE
入队：判断队伍是否未满，未满则入队：

Q.base[Q.rear]=e;//新元素插入队尾，因为尾指针始终指向队尾元素的下一位置，所以先插入再修改尾指针
Q.rear=(Q.rear+1)%MAXQSIZE;//尾指针+1

出队：判断队伍是否未空，未空则出队，用引用型变量&e来返回出队元素：

e=Q.base[Q.front];//保存出队元素
Q.front=(Q.front+1)%MAXQSIZE;//头指针+1

取队头元素：return Q.base[Q.front];
知道front、count求rear:Q.rear=(Q.front+count)%MAXQSIZE
知道rear、count求front：Q.front=(Q.rear-count+MAXQSIZE)%MAXQSIZE

2.4链队的实现（与单链表LinkList一样）

typedef struct QNode{
	ElemType data;
	struct QNode *next;
}QNode,*QueuePtr;
1
2
3
4

2.5链队的初始化、入队、出队等操作

初始化：构造一个只有一个头结点的空队

Q.front=Q.rear=new QNode;//生成新结点作为头结点，头指针与尾指针均指向此点
Q.front->next=NULL;//头结点的指针域置空

入队：不必判断是否满队列：

p=new QNode;//新建结点空间
p->data=e;
p->next=NULL;Q.rear->next=p;//新结点插入队尾
Q.rear=p;//修改队尾指针

出队：要判断队伍是否未空，p用来临时存放释放对象：

p=Q.front->next；//因为有头结点，所以Q.front->next才是队头元素
e=p->data;
Q.front->next=p->next;//修改头结点指针域
if(Q.rear=p)Q.rear=Q.front;//如果最后一个元素被删，队尾指针指向头结点
delete p;//释放p

取队头元素：return Q.front->next->data;
图示：

3.树和二叉树

1.树的定义

2.基本术语

结点：树中一个独立单元
结点的度：一个结点的子树个数
树的度：max{各个结点的度}
叶子：度为0的结点
非终端结点/分支结点：度不为0的结点；除了根结点外的非终端结点也称为内部结点
（结点的）层次：节点的层次从根结点算起，根为1，向下累加
结点的深度：从根开始向下累加
结点的高度：从叶子开始向上累加
树的深度/高度：max{各个结点的层次}
有序树和无序树：树中结点的各字暑从左到右有序（不可互换）则称为有序树，否则为无序树
森林：m棵互不相交的树的集合
实例

3.二叉树的定义

3.1二叉树与树的区别

1.每个结点最多只有两个子树，即结点的度不大于2
2.二叉树是有序树
3.二叉树是递归的结构

3.2满二叉树、完全二叉树

1.满二叉树
通俗定义：所有分支结点都存在左右子树，并且所有叶子结点都在同一层上
科学定义：深度为k且含有2k-1个结点的二叉树

2.完全二叉树：
深度为k的，有n个结点的二叉树，当且仅当其每一个结点的编号（次序）与深度为k的满二叉树一一对应时，则称为完全二叉树

深度为k的完全二叉树在k-1层一定是满二叉树

3.3二叉树的性质

1.在二叉树的第i层至多有2****i-1个结点(i≥1)
2.深度为k的二叉树至多有2k-1个结点
3.任一二叉树T，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4.具有n个结点的完全二叉树深度为
5.

3.4二叉树的顺序存储结构

仅使用于满二叉树与完全二叉树

3.5二叉树的链式存储结构

含有三个域，数据域和左右指针域

3.6遍历二叉树

1.先序遍历（DLR）
先访问根结点，即先根遍历

2.中序遍历(LDR)


3.后序遍历（LRD）


4.三种遍历特征
先序遍历第一个结点为根结点，中序遍历根结点左边为左子树，右边为右子树，后序遍历最后一个结点为根结点

3.7线索二叉树

求解一个x序线索二叉树步骤：
1.求遍历
2.找空域（缺哪条腿）
3.连线（缺左腿连前趋，缺右腿连后继）

3.8二叉树、树、森林之间的转换

1.遍历对应

2.树/森林–>二叉树
直接根据1的遍历对应画出二叉树即可

3.二叉树–>森林/树
二叉树有右孩子则对应森林，无则对应树

1.连线（若一个结点是左孩子，则将其右孩子、右孩子的右孩子、…都与其父结点连线）
2.删除线（断除原二叉树中所有右孩子的线）
3.分层次调整一下

4.树和森林的遍历

5.哈夫曼树

哈夫曼树又称最优树，是一类带权路径长度最短的树，特点：权值越大的叶子结点离根结点越近（哈夫曼算法）
1.相关术语
路径：树中从一个结点到另一个节点之间的分支
路径长度：路径上的分支数目
树的路径长度：从树根到每一结点的路径长度之和
权：赋予某个实体的一个量；而一个实体有结点（元素）和边（关系）两大类，故对应有结点权和边权
结点的带权路径长度：该结点到树根之间的路径长度x结点权值
树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作WPL=Σ(n,k=1)wklk
哈夫曼树：二叉树中WPL最小的树
2.构造哈夫曼树：贪心算法，给出的权值中，一直找最小的两个权值相加，先新建左子树，若相加的值不是最小的，则新建右子树

3.哈夫曼编码：左为0右为1

4.图

1.图的定义

有向图与无向图

2.相关术语

1.子图：图的子集

2.无向完全图与有向完全图
无向完全图：有n(n-1)/2条边的无向图
有向完全图：有n(n-1)条弧的有向图
完全图：每两个顶点均有一条边（无向）或两条弧（有向）相连的图
3.稀疏图和稠密图
稀疏图：边或弧很少(如e<nlog2n)
稠密图：边或弧很多
4.权：边或弧被赋予的一个量
5.网：带权的图
6.邻接点：对于无向图，若顶点v和顶点w之间存在一条边，则称v和w互为邻接点
7.度、入度、出度：
度：顶点v的度是指与顶点v相关联的边的数目，记作TD(v)
入度、出度：
对于有向图:
入度是指以v为头的弧线的数目，记作ID(v)
出度是指以v为尾的弧线的数目，记作OD(v)
8.路径、简单路径、简单回路：
路径：一个顶点到另一个顶点的序列
路径长度：路径经过的边或弧的数目
回路/环：第一个顶点和最后一个顶点相同的路径
简单路径：序列中顶点不重复出现的路径
简单回路/简单环：除了起始点与终点以外序列中顶点不重复出现的路径
9.连通图、连通分量、强连通图、强连通分量
连通：从v到w有路径，则称为v和w是连通的
连通图：无向图中任意两个顶点都是连通的
非连通图：无向图中并非任意两个顶点都是连通的
连通分量：无向图中的极大连通子图
强连通图：有向图中任意两个顶点之间都存在一条有向路径
强连通分量：有向图中的极大连通子图
10.连通图的生成树

一棵有n个顶点的生成树有且仅有n-1条边，若边数小于n-1，则一定是非连通图；若边数大于n-1，则一定有环；但是，有n-1条边的图不一定是生成树
11.有向树和生成森林

3.图的存储结构

3.1邻接矩阵

无向图的邻接矩阵

有向图的邻接矩阵（出行入列n平方）

3.2邻接表

3.3一些知识点

1.用邻接矩阵创建无向网的算法时间复杂度是O(n2)
2.用邻接表创建无向图的时间复杂度是O(n+e)
3.n个顶点e条边：
无向图：n个顶点表结点，2e个边表结点
有向图：n个顶点表结点，e个边表结点
4.深度优先搜索遍历的时间复杂度：
用邻接矩阵表示图时，查找每一个临界点的时间复杂度是O(n2)
用邻接表：O(e)
所以，用邻接表做存储结构时，深度优先搜索的时间复杂度为O(n+e)
5.广度优先：
用邻接矩阵表示图时，查找每一个临界点的时间复杂度是O(n2)
用邻接表做存储结构时，深度优先搜索的时间复杂度为O(n+e)
故DFS与BFS仅访问顶点的顺序不同

3.4图的遍历

1.深度优先（回溯法）–DFS

2.广度优先（分支限界） --BFS

4.最小生成树（均是贪心算法）

1.普利姆算法–最近点

2.克鲁斯卡尔算法–最短边

5.查找

1.顺序查找

2.二分查找

O（log2n）

3.快速排序

从右往左找小的，从左往右找大的

4.二叉排序树

4.1二叉排序树思路：中序遍历二叉树得到一个按关键码有序的序列

4.2二叉排序树算法

小的往左边找，大的往右边找

小的往左边插，大的往右边插

4.3二叉排序树的构造

平均查找长度ASL

4.4二叉树的删除

1.删除叶子结点：找到相应的双亲结点，将其指针域p->next=NULL
2.删除的结点只有左子树或者只有右子树：p->next=p->next->next

3.被删除的结点既有左子树也有右子树：前趋替代法/后继替代法

5.哈希表

解决冲突的方法：
1.开放地址法
开放地址法：指的是将哈希表中的「空地址」向处理冲突开放。当哈希表未满时，处理冲突时需要尝试另外的单元，直到找到空的单元为止。H(i) = (Hash(key) + F(i)) % m，i = 1, 2, 3, …, n (n ≤ m - 1)
H(i) 是在处理冲突中得到的地址序列。即在第 1 次冲突（i = 1）时经过处理得到一个新地址 H(1)，如果在 H(1) 处仍然发生冲突（i = 2）时经过处理时得到另一个新地址 H(2) …… 如此下去，直到求得的 H(n) 不再发生冲突
Hash(key) 是哈希函数，m 是哈希表表长，取余目的是为了使得到的下一个地址一定落在哈希表中
F(i) 是冲突解决方法，取法可以有以下几种：
线性探测法：F(i) = 1, 2, 3, …, m - 1
二次探测法：F(i) = 1^2, -1^2, 2^2, -2^2, …, n^2(n ≤ m / 2)
伪随机数序列：F(i) = 伪随机数序列

2.链地址法

6.排序