导图社区数据结构

数据结构

数据结构复习笔记，包括绪论、线性结构、树形结构、图状结构、查找，包含名词解释、代码、图示，条理清晰、内容详尽，适用于期中期末复习以及书本逻辑梳理。

提示: 本内容由社区用户上传并分享。平台不对内容的真实性、合法性、知识产权归属及是否侵害第三方权利进行事前审核或保证。本内容可能包含受版权保护的图片、字体或其他第三方素材，使用前请自行确认授权范围。

编辑于2023-09-14 22:39:22 上海

小熊跺跺脚

他的近期作品集查看更多>>

信管专业课程复习含10个作品
信息管理与信息系统专业课程思维导图，涵盖大一至大三重点课程，适用于平时思维梳理以及期中期末复习。

他的近期作品查看更多>>

数据结构

社区模板帮助中心，点此进入>>

小熊跺跺脚

他的近期作品集查看更多>>

信管专业课程复习含10个作品
信息管理与信息系统专业课程思维导图，涵盖大一至大三重点课程，适用于平时思维梳理以及期中期末复习。

他的近期作品查看更多>>

相似推荐
大纲

互联网9大思维
- 42.0k
- 985
- 2.5k
- 403
- 0
MindMaster
安全教育的重要性
- 9.0k
- 955
- 100
- 18
- 0
issen
组织架构-单商户商城webAPP 思维导图。
- 20.2k
- 3
- 187
- 8
- 1
Kacyun
个人日常活动安排思维导图
- 10.4k
- 0
- 84
- 0
- 0
少儿栏目外景策划波波老师
域控上线
- 5.6k
- 172
- 11
- 4
- 0
jackrao
西游记主要人物性格分析
- 20.9k
- 1.5k
- 648
- 102
- 0
issen
17种头脑风暴法
- 216.9k
- 4.3k
- 12.0k
- 4.1k
- 1
MindMaster
python思维导图
- 11.5k
- 560
- 243
- 6
- 0
(*^▽^*)
css
- 5.0k
- 1
- 43
- 3
- 0
A张舫
CSS
- 7.8k
- 274
- 189
- 33
- 0
journey

数据结构

线性结构

线性表

实现

顺序表

特点

试用于随机存取等操作

逻辑上相邻的数据元素，其物理次序也是相邻的

LOC（ai+1）=LOC（ai）+l

取值效率高 O（1）

操作

定义

存储空间的基地址

当前长度

初始化

分配MAXSIZE的数组空间

分配失败退出

空表长度为0

取值

e=L.elem[i-1];

查找

平均移动（n➕1）/2

if（L.elem[i]==e） return i+1；

插入

i值不合法、存储空间已满

for ( j=L.lenth-1; j>=i-1 ; j-- ) L.elem[j+1] = L.elem[j]; L.elem[i-1]=e;

L.length++;

平均移动n/2

删除

平均移动（n➖1）/2

i值合法

for（j=i ; j <=L.length-1 ; j++ ） L.elem[j-1] = L.elem[j];

L.length--;

时间复杂度

求表长/取第i个数据元素：O(1)

查找/插入/删除：O(n)

插入移动次数：n/2

删除移动次数

(n-1)/2

链表

线性链表/单链表

特点

非随机存取的存储结构

插入和删除效率高 O（1）

操作

定义

ElemType data

struct LNode *next

初始化

L = new LNode

L->next = NULL

创建

前插法

L=new LNode; L->next = NULL; for(i=0;i<n;i++) { p=new LNode; cin>>p->data; p->next = L->next; L->next=p; }

后插法

L=new LNode; L->next = NULL; r=L; //尾指针r指向头结点 for(i=0; i<n; i++) { p=new LNode; cin>>p->data; p->next = NULL; r->next=p; r=p;}

取值

while（p && j<i） { p=p->next; ++j;} e=p->data;

查找

while(p&&p->data!=e) p=p->next; return p;

插入

p=L; while( p &&(j<i-1)) {p=p->next;++j} s=new LNode; s->data=e; s->next=p->next; p->next=s;

删除

p=L; while( p->next &&(j<i-1)) {p=p->next;++j} q=p->next; p->next=q->next; delete q;

时间复杂度O(n)

应用

一元多项式的表示和相加

栈和队列

栈

后进先出（仅在表尾进行插删除操作）

实现

顺序栈

非空栈中的栈顶指针始终在栈顶元素的下一个位置上

注意判断栈满和栈空

定义

SElemType *base; SElemType *top; int stacksize;

初始化

S.top = S.base; S.stacksize = MAXSIZE;

入栈

*S.top++=e

出栈

e=*--S.top

取栈顶元素

return *（S.top-1)

链栈

初始化

S=NULL

入栈

p = new StackNode; p->data = e ; p->next = S ; S=p;

出栈

e = S->data; p = S; S = S->next;

取栈顶元素

return S->data

应用

数值转换

表达式求值算法

中缀表达式求值

中缀表达式转换为后缀表达式

后缀表达式求值

队列

先进先出（在表的一端进行插入，在另一端进行删除操作）

实现

循环队列

front\rear,非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置

判断满/空

空

Q.fornt==Q.rear

满

Q.front==(Q.rear+1)%MAxSize

定义

QElemType *base; int front; int rear;

初始化

Q.base = new QElemType[MAXQSIZE]; Q.front = Q.rear = 0;

求队列长度

return(Q.rear-Q.front+MAXSIZE)%MAXSIZE

入队

Q.base[Q.rear] = e Q.rear = (Q.rear+1)%MAXQSIZE //队尾指针＋1

出队

e=Q.base[Q.front] Q.front = (Q.front+1)%MAXQZSIZE //队头指针＋1

取队头元素

return Q.base[Q.front]

链队列

头指针和尾指针

队列为空：头指针和尾指针均指向头节点

定义

QElemType data; struct QNode *next；

QueuePtr front QueuePtr rear

初始化

Q.front = Q.rear = new QNode; Q.front->next = NULL

入队

p = new QNode; p->next = NULL; Q.rear->next = p; Q.rear = p

出队

p = Q.front->next; e=p.data; Q.front ->next = p->next; if(Q.rear==p) Q.rear = Q.front; delete p;

取队头元素

if(Q.front!= Q.rear) return Q.front->next->data

树形结构

树

基本术语

结点

根结点

终端结点/叶子

分支结点/内部结点

结点的度

结点拥有的子树数

树的度

树内各结点度的最大值

孩子、双亲、兄弟、堂兄弟

深度

树中节点的最大层次

有序树、无序树

森林

m棵互不相交的树的集合

二叉树

定义

每个结点至多只有两棵子树（不存在度大于2的结点），子树次序不能颠倒，有左右之分

5种基本形态

注意：二叉树的度不一定是2

性质

在二叉树第i层上至多有2^(i-1)个结点

深度为k的二叉树至多有2^k-1个结点

任何一棵二叉树，n0=n2+1

n=n0+n1+n2=n1+2n2+1

满二叉树

深度为k且有2^k-1个结点

每一层上的结点数都是最大结点数

完全二叉树

具有n个结点的完全二叉树的深度为

对任意结点

存储结构

顺序存储结构

子主题

链式存储结构

在含有n个结点的二叉链表中有n+1个空链域

TElemType data; struct BiTNode *lchild,*rchild

应用

遍历二叉树

前序遍历

VLR

中序遍历

LVR

递归算法

非递归算法

后序遍历

LRV

根据遍历序列确定二叉树

已知前序遍历+中序遍历，求后序遍历

前序遍历第一个结点为根结点，中序遍历可断开左右分段

已知后序遍历+中序遍历，求前序遍历

后序遍历最后一个结点是根节点

在二叉树结点的先序、中序、后序遍历中，所有叶子节点的先后顺序相同

前序遍历和中序遍历，得到唯一的一棵二叉树

应用

创建二叉树的存储结构——二叉链表

计算二叉树的深度

线索二叉树

作用

加快查找结点的前驱或后继的速度

特点

二叉树的二叉线索存储表示

TElemType data; struct BiThrNode *lchild,*rchild; int LTag,RTag;

前序和后序线索化后，空链域为1；中序线索化后，空链域为2

线索树的遍历

线索树的创建

树和森林

树的存储结构

双亲表示法

孩子表示法

孩子兄弟表示法

右指针指向兄弟

森林与二叉树的转换

一棵树可转换成唯一的一棵没有右子树的二叉树

树和森林的遍历

树

先根遍历

后根遍历

按层次遍历

以二叉链表做为树的存储结构时，先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历实现

森林

森林的先序

对应二叉树的先序遍历

森林的中序

二叉树的中序遍历

树和森林的遍历

最优二叉树/哈夫曼树

概念

路径长度

路径上的分支数目

树的带权路径长度

特点

具有相同带权结点的哈夫曼树不唯一

哈夫曼树中权越大的叶子离根越近

一颗有n个叶子结点构成的哈夫曼树有2n-1个结点

构造

构造森林全是根

选用两小造新树

删除两小添新人

重复②③剩单根

构造

哈夫曼编码

最优前缀编码

最高n-1层，最多n-1个分支

哈夫曼树的结点个数一定是奇数

应用

利用二叉树求解表达式的值

查找

查找的基本概念

查找表

关键字

主关键字、副关键字

查找

动态查找表和静态查找表

性能分析

平均查找长度ASL

查找表

静态查找表

查找元素存在性、检索属性

顺序表的查找

顺序查找（可设置哨兵）

查找时从表的最后开始比较

时间复杂度O(n)

在等概率情况下ASL=(n+1)/2

既适用于顺序结构，也适用于链式结构

有序表的查找

折半查找

适用于采用顺序存储结构的有序表（对线性链表无法有效地查找）

比较次数

成功

路径上的结点数/结点的层次

不成功

路径上内部结点数

性能分析

近似ASL=log(n+1)-1

平均查找长度

分块查找

索引表

表有序或者分块有序（块间有序，块内无序）

确定块的查找可以顺序/折半查找，块中只能顺序查找

性能分析

表长为n, 每一块的记录个数为s, 则ASL=log(n/s+1)+s/2

与n、s都有关，可能效率不如折半查找

插入和删除比较容易

动态查找表

查找过程中进行插入/删除操作

二叉排序树

性质

左子树若不为空，左子树上所有结点的值均小于它的根节点的值

右子树若不为空，右子树上所有结点的值均大于它的根节点的值

它的左、右子树也分别为二叉排序树

中序遍历一棵二叉排序树可得到一个结点值递增的有序序列

查找

提高查找效率

平衡二叉树AVL

性质

左子树和右子树均为平衡二叉树，且左右子树深度之差的绝对值不超过1.

平衡因子

左子树深度-右子树深度

AVL树只能为1、0、-1

平衡树的生成（调整规律）

单向右旋平衡处理

单向左旋平衡处理

双向旋转（先左后右）平衡处理

先右后左平衡处理

查找性能分析

时间复杂度O(logn)

插入

新插入的结点一定是新添加的叶子结点

创建

删除

三种情况

哈希表

对应关系：哈希函数

函数值以同等概率取其值域的每个值

术语

散列函数和散列地址

散列表

冲突和同义词

构造方法

直接定址法

Hash(key) = a key + b

关键字/关键字的线性函数值

除数留余法

Hash(key) = key mod p

p选择质数或者不包含小于20的质因数的合数

考虑的因素

处理冲突的方法

开放定址法

Hi=(H(key)+di)%m(散列表表长)

线性探测再散列

di=1,2,3,...

易发生二次聚集

S»1/2(1+1/(1-a))

二次探测再散列

di=1²，-1²，2²,-2²...

伪随机探测再散列

di=伪随机数序列

链地址法

m个哈希地址就设m个单链表

前插法效率高

更适合表长不确定的情况

查找效率分析

ASL取决于

哈希函数

处理冲突的方法

装填因子

α=表中填入的记录数/哈希表的长度

平均查找长度依赖于装填因子

几点结论

链地址法优于开放地址法

除留余数法作哈希函数优于其他类型函数

图状结构

基本术语

子图

无向完全图、有向完全图

无向图

n(n-1)/2条边

有向图

n(n-1)条边

稀疏图

网

带权的图

邻接点、依附、相关联

度

顶点的度

和顶点v相关联的边的数目TD(v)

有向图

入度

出度

路径和路径长度

简单路径

顶点不重复出现的路径

回路或环

连通

连通图

图中任意两个顶点间都连通

连通分量

无向图中的极大连通子图

强连通图

有向图中，每两点间都可以相互到达

强连通分量

有向图的极大连通子图

连通图的生成树

一个连通图的生成树是一个极小连通子图

含有图中全部顶点，但只有足以构成一棵树的n-1条边

存储结构

邻接矩阵

对于无向图，顶点Vi的度是邻接矩阵中第i行/列的元素之和

对于有向图，第i行元素的和是顶点Vi的出度OD(Vi), 第j列元素的和是顶点Vj的入度ID(Vj)

创建

顶点表

邻接矩阵

VerTexType vex[MVNum]; ArcType arcs[MVNum][MVNum]; int vexnum,arcnum

图

初始化邻接矩阵，使每个权值初始化为0

网

初始化邻接矩阵，使每个权值初始化为极大值

优缺点

优点

便于判断两个顶点之间是否有边

便于计算各个顶点的度

缺点

不便于增加和删除顶点

不便于统计边的数目

空间复杂度高

时间复杂度O(n*n)

适用于稀疏图

邻接表

每个顶点建立一个单链表

若无向图有n个顶点，e条边，则邻接表需要n个头结点和2e个表结点

为方便计算有向图中顶点的入度，可以建立一个有向图的逆邻接表

优缺点

优点

便于增加和删除顶点

便于统计边的数目

时间复杂度、空间复杂度 O(n+e)

缺点

不便于判断两个顶点之间是否有边

不便于计算各个顶点的度

图的遍历

辅助数组visited[n] false=0;true=1

深度优先搜索(DFS)

类似于树的先根遍历

时间复杂度

邻接矩阵 O(n*n)

当用邻接表存储图时 O(n+e)

利用递归/栈来实现

广度优先搜索(BFS)

类似于树的按层次遍历

时间复杂度

和DFS相同

利用队列

图的应用

最小生成树

生成树

一个图可以有许多棵不同的生成树

特点

顶点个数与图的顶点个数相同

是图的极小连通子图

一个有n个顶点的连通图的生成树有n-1条边

在生成树中再加一条边必然形成回路

构造

Prim算法

归并顶点

时间复杂度O(n*n)

试用于求边稠密的网

Kruskal算法

归并边

时间复杂度O(eloge)

试用于求边稀疏的网

最短路径

从某个源点到其余各顶点的最短路径

Dijkstra算法

过程

初始化

选择

更新

时间复杂度O(n*n)

每一对顶点之间的最短路径

拓扑排序

由某个集合上的一个偏序得到集合上的一个全序

AOV网

顶点表示活动，弧表示活动间的优先关系的有向图

如何进行拓扑排序

在有向图中选一个没有前驱的顶点且输出

从图中删除该顶点和所有以它为尾的弧

重复以上两步，直至全部顶点均已输出，或者当前不存在无前驱的顶点为止。后一种情况说明有向图中有环。

也可利用DFS,按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列

关键路径

路径长度最长的路径，即为完成工程的最短时间

e(i)

活动ai的最早开始时间

l(i)

活动ai最迟必须开始的时间

关键活动

e(i)=l(i)

关键路径上的活动都是关键活动（提前完成非关键活动不能并不能加快工程进度）

ve(i)

事件的最早发生时间

计算时应从ve(0)向前递推

vl(i)

事件的最迟发生时间

计算时从vl(n-1)=ve(n-1)向前后递推

求关键路径的算法

绪论

数据

基本单位

数据元素

由数据项组成

不可分割的最小单位

数据项

数据结构

逻辑结构

数据元素之间的逻辑关系

线性结构

线性表

栈和队列

字符串

非线性结构

集合结构

树结构

图结构

物理结构

在计算机中存储结构

顺序存储结构

链式存储结构

算法

定义

指令的有序序列

特性

有穷性、确定性、可行性

评价标准

效率度量

时间复杂度

常量阶 O（1）

与问题规模n无关的常数

线性阶 O（n）

平方阶 O（n²）

由最深层循环内的基本语句的频度决定

立方阶O（n³）

对数阶（log₂ⁿ）

空间复杂度