数据结构知识点含算法Word文件下载.docx
《数据结构知识点含算法Word文件下载.docx》由会员分享,可在线阅读,更多相关《数据结构知识点含算法Word文件下载.docx(24页珍藏版)》请在冰点文库上搜索。
![数据结构知识点含算法Word文件下载.docx](https://file1.bingdoc.com/fileroot1/2023-5/5/3bf127c2-3af2-4f0e-94b3-dbb34d1eed15/3bf127c2-3af2-4f0e-94b3-dbb34d1eed151.gif)
4.1单链表
a.特点:
逻辑顺序与物理顺序有可能不一致;
属于顺序存取的存储结构,即存取每个数据元素所花费的时间不相等
b.带头结点的怎么判定空表:
head和tail指向单链表的头结点
c.链表的插入(q->
next=p->
next;
p->
next=q;
)
【Ο(n)】
d.链表的删除(q=p->
next=q->
deleteq;
e.不足:
next仅指向后继,不能有效找到前驱
4.2双链表
a.增加前驱指针,弥补单链表的不足
b.带头结点的怎么判定空表:
c.插入:
(q->
next=p->
q->
prev=p;
next=q;
next->
prev=q;
d.删除:
(p->
prev->
prev=p->
prev;
next=NULL;
deletep;
4.3顺序表和链表的比较
4.3.1主要优点
a.顺序表的主要优点
没用使用指针,不用花费附加开销;
线性表元素的读访问非常简洁便利
b.链表的主要优点
无需事先了解线性表的长度;
允许线性表的长度有很大变化;
能够适应经常插入删除内部元素的情况
4.3.2应用场合的选择
a.不宜使用顺序表的场合
经常插入删除时,不宜使用顺序表;
线性表的最大长度也是一个重要因素
b.不宜使用链表的场合
当不经常插入删除时,不应选择链表;
当指针的存储开销与整个结点内容所占空间相比其比例较大时,应该慎重选择
第三章栈与队列
1.栈
a.栈是一种限定仅在一端进行插入和删除操作的线性表;
其特点后进先出;
插入:
入栈(压栈);
删除:
出栈(退栈);
插入、删除一端被称为栈顶(浮动),另一端称为栈底(固定);
实现分为顺序栈和链式栈两种
b.应用:
1)数制转换
while(N){
N%8入栈;
N=N/8;
}
while(栈非空){
出栈;
输出;
}
2)括号匹配检验
不匹配情况:
各类括号数量不同;
嵌套关系不正确
算法:
逐一处理表达式中的每个字符ch:
ch=非括号:
不做任何处理
ch=左括号:
入栈
ch=右括号:
if(栈空)returnfalse
else{
出栈,检查匹配情况,
if(不匹配)returnfalse
如果结束后,栈非空,返回false
3)表达式求值
3.1中缀表达式:
计算规则:
先括号内,再括号外;
同层按照优先级,即先乘*、除/,后加+、减-;
相同优先级依据结合律,左结合律即为先左后右
3.2后缀表达式:
<
表达式>
:
:
=<
项>
+|<
<
-|<
因子>
*|<
/|<
常数>
•<
数字>
|<
∷=0|1|2|3|4|5|6|7|8|9
3.3中缀表达式转换为后缀表达式
InfixExp为中缀表达式,PostfixExp为后缀表达式
初始化操作数栈OP,运算符栈OPND;
OPND.push('
#'
);
读取InfixExp表达式的一项
操作数:
直接输出到PostfixExp中;
操作符:
当‘(’:
入OPND;
当‘)’:
OPND此时若空,则出错;
OPND若非空,栈中元素依次弹出,输入PostfixExpz中,直到遇到‘(’为止;
若为‘(’,弹出即可
当‘四则运算符’:
循环(当栈非空且栈顶不是‘(’&
&
当前运算符优先级>
栈顶运算符优先级),反复弹出栈顶运算符并输入到PostfixExp中,再将当前运算符压入栈
3.4后缀表达式求值
初始化操作数栈OP;
while(表达式没有处理完){
item=读取表达式一项;
操作数:
入栈OP;
运算符:
退出两个操作数,
计算,并将结果入栈}
c.递归使用的场合:
定义是递归的;
数据结构是递归的;
解决问题的方法是递归的
2.队列
a.若线性表的插入操作在一端进行,删除操作在另一端进行,则称此线性表为队列
b.循环队列判断队满对空:
队空:
front==rear;
队满:
(rear+1)%n==front
第五章二叉树
1.概念
a.一个结点的子树的个数称为度数
b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1
c.二叉树的深度定义为二叉树中层数最大的叶结点的层数
d.如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树,则此二叉树称作满二叉树
e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2;
最下面一层的结点都集中在该层最左边的位置上,则称此二叉树为完全二叉树
f.当二叉树里出现空的子树时,就增加新的、特殊的结点——空树叶组成扩充二叉树,扩充二叉树是满二叉树
外部路径长度E:
从扩充的二叉树的根到每个外部结点(新增的空树叶)的路径长度之和
内部路径长度I:
扩充的二叉树中从根到每个内部结点(原来二叉树结点)的路径长度之和
2.性质
a.二叉树的第i层(根为第0层,i≥0)最多有2^i个结点
b.深度为k的二叉树至多有2k+1-1个结点
c.任何一颗二叉树,度为0的结点比度为2的结点多一个。
n0=n2+1
d.满二叉树定理:
非空满二叉树树叶数等于其分支结点数加1
e.满二叉树定理推论:
一个非空二叉树的空子树(指针)数目等于其结点数加1
f.有n个结点(n>
0)的完全二叉树的高度为⌈log2(n+1)⌉,深度为⌈log2(n+1)⌉−𝟏
g.对于具有n个结点的完全二叉树,结点按层次由左到右编号,则有:
1)如果i=0为根结点;
如果i>
0,其父结点编号是(i-1)/2
2)当2i+1<
n,i结点的左子结点是2i+1;
否则i结点没有左子结点
3)当2i+2<
n,i结点的右子结点是2i+2;
否则i结点没有右子结点
3.周游(重点为由前序中序/中序后序求得二叉树)
a.深度优先周游二叉树,可以有下列三种周游顺序:
(实现:
栈)
1)前序周游(tLR次序):
访问根结点;
前序周游左子树;
前序周游右子树
2)中序周游(LtR次序):
中序周游左子树;
中序周游右子树
3)后序周游(LRt次序):
后序周游左子树;
后序周游右子树;
访问根结点
b.广度周游二叉树:
从二叉树的顶层(根结点)开始,自上至下逐层遍历;
在同一层中,按照从左到右的顺序对结点逐一访问(实现:
队列)
4.存储
链式存储结构,
顺序存储结构(仅限完全二叉树:
因为完全二叉树排列紧凑)
5.二叉搜索树(BST)
a.判定:
是一颗空树;
或者是具有下列性质的二叉树:
对于任何一个结点,设其值为K,则该结点的
左子树(若不空)的所有结点的值都小于K;
右子树(若不空)的所有结点的值都大于K;
它的左右子树也分别为二叉搜索树
b.性质:
按照中序周游将各结点打印出来,得到的排列按照由小到大有序
c.检索:
从根结点开始,在二叉搜索树中检索值K
如果根结点储存的值为K,则检索结束
如果K小于根结点的值,则只需检索左子树
如果K大于根结点的值,则只检索右子树
该过程一直持续到找到K或者遇上叶子结点
如果遇上叶子结点仍没有发现K,则查找失败
**查找关键码:
把查找时所经过的点一次写出
d.插入:
用待插入结点与树根比较,若待插入的关键值小于树根的关键值,就进入左子树,否则进入右子树;
在子树中,按照同样的方式沿检索路径直到叶结点,将新结点插入到二叉搜索树的叶子结点位置
e.创建:
从空的BST开始,将关键码按BST定义一次插入
与插入相反,删除在查找成功之后进行,并且要求在删除二叉排序树上某个结点之后,仍然保持二叉排序树的特性,删除过程分为如下情况:
1)被删除的结点是叶子:
直接将其删除即可
2)被删除的结点只有左子树或只有右子树:
直接将要删除的点删除后,将该点的左(右)孩子和上面结点相连
3)被删除结点有左、右子树:
若p有左右子树,则在左子树里找中序周游的最后一个结点r,将r的右指针置成指向p的右子树的根,用结点p的左子树的根去代替被删除的结点p
6.堆
a.最小/大堆定义:
最小堆:
是个关键码序列{k0,k1…kn-1},具有如下特性(i=0,1,…,⌊n/2⌋-1)
ki≤k2i+1(左孩子)
ki≤k2i+2(右孩子)(即父≤2个孩子)
类似可以定义最大堆
ki≥k2i+1
ki≥k2i+2(即父≥2个孩子)
b.建“初堆”:
按序列建立完全二叉树,从其中最后一个有孩子的结点开始按堆的定义调整
插入点追加到最后,自下而上依次比较父与子,直到满足堆的定义
用最后结点替换被删结点,自上至下调整成堆
e.移出最小/大值:
可以将堆中最后一个位置上的元素(数组中实际的最后一个元素)移到根的位置上,利用从左开始向下筛选对堆重新调整
7.Huffman树
a.概念
路径:
从树中一个结点到另一个结点之间的分支构成这两个结点间的路径
结点路径长度:
从根结点到该结点的路径上分支的数目
树的路径长度:
树中每个结点的路径长度之和
b.带权的路径长度
树中所有叶子结点的带权路径长度之和=其中:
𝒘
𝒌
:
权值𝒍
:
结点到根的路径长度
c.编码:
左0右1
d.如何构建:
选取序列中最小的相加生成树如此反复
第六章树
若<
k,k'
>
∈N,则称k是k'
的父结点,k'
是k的子结点
若有序对<
及<
k,k″>
∈N,则称k'
和k″互为兄弟
若有一条由k到达ks的路径,则称k是ks的祖先,ks是k的子孙
2.树/森林与二叉树的相互转换
a.树转换成二叉树
加线:
在树中所有兄弟结点之间加一连线
抹线:
对每个结点,除了其最左孩子外,去除其与其余孩子之间的连线
旋转:
以树的根结点为轴心,将整树顺时针转45°
b.二叉树转化成树
加线:
若p结点是双亲结点的左孩子,则将p的右孩子,右孩子的右孩子,……沿分支找到的所有右孩子,都与p的双亲用线连起来
抹线:
抹掉原二叉树中双亲与右孩子之间的连线
调整:
将结点按层次排列,形成树结构
c.森林转换成二叉树
将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根,再以根结点为轴心,顺时针旋转,构成二叉树型结构
d.二叉树转换成森林
将二叉树中根结点与其右孩子连线,及沿右分支搜索到的所有右孩子间连线全部抹掉,使之变成孤立的二叉树
还原:
将孤立的二叉树还原成树
3.周游
a.先根(次序)周游
若树不空,则先访问根结点,然后依次先根周游各棵子树
b.后根(次序)周游
若树不空,则先依次后根周游各棵子树,然后访问根结点
c.按层次周游
若树不空,则自上而下自左至右访问树中每个结点
4.存储结构
“左子/右兄”二叉链表表示法:
结点左指针指向孩子,右结点指向右兄弟,按树结构存储,无孩子或无右兄弟则置空
5.“UNION/FIND算法”(等价类)
判断两个结点是否在同一个集合中,查找一个给定结点的根结点的过程称为FIND
归并两个集合,这个归并过程常常被称为UNION
“UNION/FIND”算法用一棵树代表一个集合,如果两个结点在同一棵树中,则认为它们在同一个集合中;
树中的每个结点(除根结点以外)有仅且有一个父结点;
结点中仅需保存父指针信息,树本身可以存储为一个以其结点为元素的数组
6.树的顺序存储结构
a.带右链的先根次序表示法
在带右链的先根次序表示中,结点按先根次序顺序存储在一片连续的存储单元中
每个结点除包括结点本身数据外,还附加两个表示结构的信息字段,结点的形式为:
info是结点的数据;
rlink是右指针,指向结点的下一个兄弟;
ltag是一个左标记,当结点没有子结点(即对应二叉树中结点没有左子结点时),ltag为1,否则为0
b.带双标记位的先根次序表示法
规定当结点没有下一个兄弟(即对应的二叉树中结点没有右子结点时)rtag为1,否则为0
c.带双标记位的层次次序表示法
结点按层次次序顺序存储在一片连续的存储单元中
第七章图
1.定义
a.假设图中有n个顶点,e条边:
含有e=n(n-1)/2条边的无向图称作完全图
含有e=n(n-1)条弧的有向图称作有向完全图
若边或弧的个数e<
nlogn,则称作稀疏图,否则称作稠密图
b.顶点的度(TD)=出度(OD)+入度(ID)
顶点的出度:
以顶点v为弧尾的弧的数目
顶点的入度:
以顶点v为弧头的弧的数目
c.连通图、连通分量
若图G中任意两个顶点之间都有路径相通,则称此图为连通图
若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量
d.强连通图、强连通分量
对于有向图,若任意两个顶点之间都存在一条有向路径,则称此有向图为强连通图
否则,其各个极大强连通子图称作它的强连通分量
e.生成树、生成森林
假设一个连通图有n个顶点和e条边,其中n-1条边和n个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树
对非连通图,则将由各个连通分量构成的生成树集合称做此非连通图的生成森林
2.存储结构
a.相邻矩阵表示法
表示顶点间相邻关系的矩阵
若G是一个具有n个顶点的图,则G的相邻矩阵是如下定义的n×
n矩阵:
A[i,j]=1,若(Vi,Vj)(或<
Vi,Vj>
)是图G的边
A[i,j]=0,若(Vi,Vj)(或<
)不是图G的边
b.邻接表表示法
为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧)(建立单链表时按结点顺序建立)
a.深度优先周游:
从图中某个顶点V0出发,访问此顶点,然后依次从V0的各个未被访问的邻接点出发,深度优先搜索遍历图中的其余顶点,直至图中所有与V0有路径相通的顶点都被访问到为止
b.广度优先周游:
从图中的某个顶点V0出发,并在访问此顶点之后依次访问V0的所有未被访问过的邻接点,随后按这些顶点被访问的先后次序依次访问它们的邻接点,直至图中所有与V0有路径相通的顶点都被访问到为止,若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止
4.拓扑排序
拓扑排序的方法是:
1)选择一个入度为0的顶点且输出之
2)从图中删掉此顶点及所有的出边
3)回到第1步继续执行,直至图空或者图不空但找不到无前驱(入度为0)的顶点为止
5.单源最短路径(Dijkstra算法)
6.每对顶点间的最短路径(Floyd算法)
7.最小生成树
a.Prim算法
b.Kruskal算法
c.两种算法比较:
Prim算法适合稠密图,Kruskal算法适合稀疏图
第八章内排序
算法
最大时间
平均时间
最小时间
S(n)
稳定性
直接插入排序
Θ(n2)
Θ(n)
Θ
(1)
稳定
冒泡排序
直接选择排序
不稳定
Shell排序
Θ(n3/2)
快速排序
Θ(nlogn)
Θ(logn)
归并排序
堆排序
桶式排序
Θ(n+m)
基数排序
Θ(d·
(n+r))
Θ(n+r)
第十章检索
1.平均检索长度(ASL)是待检索记录集合中元素规模n的函数,其定义为:
ASL=
Pi为检索第i个元素的概率;
Ci为找到第i个元素所需的比较次数
2.散列
a.除余法
用关键码key除以M(取散列表长度),并取余数作为散列地址
散列函数为:
hash(key)=keymodM
b.解决冲突的方法
开散列方法:
把发生冲突的关键码存储在散列表主表之外(在主表外拉出单链表)
闭散列方法:
把发生冲突的关键码存储在表中另一个位置上
c.线性探查
基本思想:
如果记录的基位置存储位置被占用,就在表中下移,直到找到一个空存储位置;
依次探查下述地址单元:
d0+1,d0+2,...,m-1,0,1,...,d0-1;
用于简单线性探查的探查函数是:
p(K,i)=i
d.散列表的检索
1.假设给定的值为K,根据所设定的散列函数h,计算出散列地址h(K)
2.如果表中该地址对应的空间未被占用,则检索失败,否则将该地址中的值与K比较
3.若相等则检索成功;
否则,按建表时设定的处理冲突方法查找探查序列的下一个地址,如此反复下去,直到某个地址空间未被占用(可以插入),或者关键码比较相等(有重复记录,不需插入)为止
e.散列表的删除:
删除后在删除地点应加上墓碑(被删除标记)
f.散列表的插入:
遇到墓碑不停止,知道找到真正的空位置
第十一章索引技术
1.概念:
a.主码:
数据库中的每条记录的唯一标识
b.辅码:
数据库中可以出现重复值的码
2.B树
a.定义:
B树定义:
一个m阶B树满足下列条件:
(1)每个结点至多有m个子结点;
(2)除根和叶外
其它每个结点至少有⌈⌉个子结点;
(3)根结点至少有两个子结点
例外(空树,or独根)
(4)所有的叶在同一层,可以有⌈⌉-1到m-1个关键码
(5)有k个子结点的非根结点恰好包含k-1个关键码
b.查找
在根结点所包含的关键码K1,…,Kj中查找给定的关键码值(用顺序检索(key少)/二分检索(key多));
找到:
则检索成功;
否则,确定要查的关键码值是在某个Ki和Ki+1之间,于是取pi所指结点继续查找;
如果pi指向外部结点,表示检索失败.
c.插入
找到的叶是插入位置,若插入后该叶中关键码个数<
m,插入完成;
否则分裂,中间为分界码(插入到父结点),若父结点上溢则继续向上分裂
d.删除
删除的关键码不在叶结点层:
先把此关键码与它在B树里的后继对换位置,然后再删除该关键码(叶中删)
删除的关键码在叶结点层:
删除后关键码个数不小于⌈⌉-1——直接删除
关键码个数小于⌈⌉-1,如果兄弟结点关键码个数不等于⌈⌉-1——从兄弟结点移若干个关键码到该结点中来(父结点中的一个关键码要做相应变化)
如果兄弟结点关键码个数等于⌈⌉-1——合并
3.B+树
m阶B+树的结构定义如下:
(1)每个结点至多有m个子结点;
(2)每个结点(除根外)至少有⌈⌉个子结点;
(3)根结点至少有两个子结点;
(4)叶在同一层,有⌈⌉..m个key,叶包含全部key,B+树的叶结点链接成一个双链表
(5)有k个子结点的结点必有k个关键码。
第十二章高级数据结构
1.广义表
a.广义表的结构特点:
1.广义表中的数据元素有相对次序
2.广义表的长度定义为最外层包含元素个数
3.广义表的深度定义为所含括弧的重数:
“原子”的深度为0;
“空表”的深度为1
4.广义表可以共享
5.广义表可以是一个递归的表:
递归表的深度是无穷值,长度是有限值
6.任何一个非空广义表LS=(α1,α2,…,αn)均可分解为:
表头Head(LS)=α1和表尾Tail(LS)=(α2,…,αn)两部分
b.广义表的各种类型
纯表(purelist):
从根结点到任何叶结点只有一条路径;
也就是说任何一个元素(原子、子表)只能在广义表中出现一次
可重入表(reentrantlist):
图示对应于一个DAG;
其元素(包括原子和子表)可能会在表中多次出现,但不会出现回路
循环表(cycliclist,递归表):
有向图中可能包含回路;
循环表的深度为无穷大
2.平衡的二叉搜索树(AVL)
a.平衡因子
用bf(x)来表示结点x的平衡因子,它被定义为:
bf(x)=x的右子树的高度–x的左子树的高度
b.AVL的插入:
按BST建立,发现不满足AVL定义即调整,插入时出现的情况:
1)LL/RR:
中间元素成为双亲,左右各位孩子(满足BST定义)
2)LR/RL:
最后元素成为双亲,前两个为孩子(满足BST定义)
附录:
二叉树前序周游
template<
classT>
void