lrc="https://qiniu.sukoshi.xyz/public/music/鹿乃 - アイロニ.lrc"
面向自己做笔记,我不生产笔记,我只是ppt的搬运工
藏藏[1]
第一章 绪论
1.1 什么是数据结构
- 数据的结构,直接影响算法的选择和效率。程序设计的实质是对实际问题选择一个好的数据结构,加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。好像说了什么又好像没说什么
1.2 基本概念和术语
就算列出来我也不会背的
-
数据: 被计算机加工处理的对象。
-
数据项:不可分割的数据的最小单位,数据项是构成数据元素的最小单位。
-
数据元素(记录、表目):数据的基本单位(并非最小单位),是数据集合中的一个个体。一个数据元素可由若干个数据项组成。
-
数据类型:在一种程序设计语言中,变量所具有的数据种类。分以下两种类型:
- 原子类型:不可分解,如int、char。
- 结构类型:可分解的。
-
数据对象:是性质相同的数据元素的集合,是数据的一个子集。(某种数据类型元素的集合。)数据对象可以是有限的,也可以是无限的。
-
数据结构:具有结构的数据元素的集合。它包括数据元素的逻辑结构、存储结构和相适应的运算。
-
逻辑结构:数据元素之间的逻辑关系。
-
四种基本的逻辑结构
- 集合结构:数据元素除了“属于同一集合”的联系之外,没有其它的关系。
- 线性结构:数据元素之间存在一对一的关系。
- 树形结构:数据元素之间存在一对多的关系。
- 网状结构:数据元素之间存在多对多的关系。
-
存储结构(物理结构):指数据的逻辑结构在计算机存储器中的映象表示。
-
数据元素的映象:用二进制位(bit)的位串表示数据元素。每个数据元素的映象称为结点(又称元素,是一个二进制位串), 每个数据项的映象称为数据域。
-
关系的映象:两种基本方法及其组合使用。
-
顺序映象:以相对的存储位置表示关系。
-
链式映象:以附加信息(指针)表示关系。
-
-
-
数据存储方式的四种常用结构
- 顺序存储:数据元素依次放在连续的存储单元中。
- 链式存储:在存储结点中增加若干指针域,记录后继或者相关结点的地址(指针)。
- 索引存储:将数据元素分为若干子表,子表的开始位置存放在索引表中。
- 散列存储:根据数据元素的关键字值,由散列函数计算出存储地址。
-
运算(操作):在数据逻辑结构上定义的一组数据被使用的方式,其具体实现要在存储结构上进行。
-
抽象数据类型:一个数学模型以及定义在该模型上的一组操作。
1.3 抽象数据类型的表现与实现(如何说抽象话)
会就不用看了,不好看,至少不如我好看
1 |
|
小细节:约定当a&&b时如果a==0则不对b进行求值,同理若a||b时如a==1则不对b求值。
1.4 算法和算法分析
1.4.1 算法
- 算法:是对特定问题求解步骤的一种描述算法是指令的有限序列,其中每一条指令表示一个或多个操作。算法具有以下特性
- 有穷性 :一个算法必须总是在执行有穷步之后结束,且每一步都在有穷时间内完成。
- 确定性:算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。
- 可行性:一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
- 输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象集合。
- 输出:一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。
1.4.2 算法设计的要求
- 好的算法有以下几个特点
- 正确性(Correctness ):算法应满足具体问题的需求。
- 可读性(Readability):算法应该好读。以有利于阅读者对程序的理解。
- 健状性(Robustness):算法应具有容错处理。当输入非法数据时,算法应对其作出反应,而不是产生莫名其妙的输出结果。
- 效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大存储空间。一般,这两者与问题的规模有关。
1.4.3 算法度量
-
渐进时间复杂度(简称时间复杂度):若有某个辅助函数*f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)*是T(n)的同数量级函数(记作T(n) =O(f(n) ) ,称O(f(n)) 为算法的渐近时间复杂度,简称时间复杂度。
-
语句的频度:该语句重复执行的次数。
1.4.4 算法的存储空间需求
- 空间复杂度:算法所需存储空间的度量,记作S(n)=O(f(n))。
第二章 线性表
2.1 线性表的类型定义
- 线性结构:一个数据元素的有序(次序)集合。
线性表的顺序表示和实现
-
顺序表: “用一组地址连续的存储单元依次存放线性表中的数据元素”,即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系,并以表中第一个元素的存储位置作为线性表的起始地址,称作线性表的基地址。
-
线性表的顺序存储
1
2
3
4
5
6const int MAXLISTSIZE = 80;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
这种顺序存储表示仅适用于不常进行插入和删除操作、表中元素相对稳定的线性表。
- 线性表存储的特点
- 逻辑上相邻的元素,其物理位置也相邻;
- 可随机存取表中任一元素;
- 必须按最大可能长度预分存储空间,存储空间利用率低,表的容量难以扩充,是一种静态存储结构;
- 插入删除时,需移动大量元素,平均移动元素为n/2。
2.3 线性表的链式表示和实现
-
线性表的链式存储
1
2
3
4struct node{
ElemType data;
struct node *next;
}LNode, *Linklist;
线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
- 数据元素ai除了存储其本身的信息之外(数据域),还需存储一个指示其直接后继的信息(即直接后继的存储位置(指针域))。这两部分共同构成数据元素的存储映像,成为结点。
-
单链表的优势
- 能有效利用存储空间;逻辑上相邻的元素,物理位置不一定需要相邻; 元素之间的邻接关系由指针域指示。链表是一种动态存储结构;
- 用“指针”指示数据元素之间的后继关系,便于进行“插入”、“删除”等操作;
2.3.3双向链表
-
双向链表:其结点结构中含有两个指针域,其一指向数据元素的"直接后继",另一指向数据元素的“直接前驱”
1
2
3
4
5typedef struct DulNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode, *DuLink;
查找结点也是要从头指针指示的头结点开始。,插入和删除时必须同时修改两个方向上的指针。
2.3.2 循环链表
- 循环链表的特点
- 从任一结点出发,沿着链可访问全部结点;
- 运算与单链表基本一致,仅是循环结束条件为P->next==H (H为头指针);
- 判断是否是表尾结点:p->next==H ;
2.4 顺序表与链表的比较
- 基于空间:
-
顺序表静态分配可能会产生空间浪费或空间不足的问题,但链表动态分配很难产生溢出的情况。
-
存储密度顺序表为百分百,而链表因为有指针域,存储密度会降低。
- 基于时间:
- 顺序表可实现随机存储,但链表不可以。
第三章 栈和队列
3.1 栈
-
栈和队列是在程序设计中被广泛使用的两种线性数据结构,它们的特点在于基本操作的特殊性,栈必须按“后进先出”的规则进行操作,而队列必须按“先进先出”的规则进行操作。和线性表相比,它们的插入和删除操作受更多的约束和限定,故又称为限定性的线性表结构。可将线性表和栈及队列的插入和删除操作对比如下:
- 栈只允许在表尾一端进行插入和删除;
- 队列只允许在表尾一端进行插入,在表头一端进行删除。
- 线性表允许在表内任一位置进行插入和删除
- 和线性表相比,从"数据结构"的角度看,它们都是线性结构,即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外,主要区别是对插入和删除操作的"限定"。
-
顺序栈:栈中的数据元素是用一组连续的存储空间来存放的。栈底位置可以设置在存储空间的一个端点,而栈顶是随着插入和删除而变化的,用一个top指针来指示当前栈顶位置
1 | CONST arrmax=100 |
- 链栈
1 | typedef struct node { |
由于栈只在栈顶作插入和删除操作,因此链栈中不需要头结点,但要注意链栈中指针的方向是从栈顶指向栈底的,这正好和单链表是相反的。
二元表达式的前中后缀表示法这里不写了,跟树的序表示基本一致
3.2 队列
-
队列是一种特殊的线性表,限定插入和删除操作分别在表的两端进行。具有先进先出(FIFO—First In First Out)的特点。把允许插入的一端叫队尾(rear) ,把允许删除的一端叫队头(front)。没有元素时称为空队列。
-
队列的链式存储结构
1 | typedef struct node { |
- 队列的顺序存储
1 | typedef struct { |
队列存在假上溢现象,可以用循环队列解决。
第四章 串
我的评价是,屁都不会
4.1 串类型的定义
4.1.1 串的概念及基本术语
-
串(字符串):是由零个或多个字符组成的有限序列。串是特殊的线性表,数据元素是单个字符。
-
子串和主串:串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。
-
串相等:两个串长度相等,且对应位置的字符都相等。
-
空串和空白串:空串不包含任何字符,表示为;空白串由一个或多个空格组成。
-
子串的位置:子串的第一个字符在主串中的序号称为子串的位置。
4.1.2 串的基本操作
4.2 串的表示和实现
4.2.1 定长顺序存储表示
1 |
|
4.2.2 堆分配存储表示
1 | typedef struct{ |
4.2.3 串的块链表示
- 链串
1 | typedef struct node{ |
链串便于进行插入和删除运算,但存储空间利用率太低。
块链即为将链串数据域改为定长字符串,则链表每一个结点为一块(内含一个字符串),形成链接块的链表(每个位置不需要占满,多于位置用#占位即可),显然,存储密度小时运算处理方便。
4.3 串的模式匹配算法
KMPS算法
next[j]={ 0, &当j=1时\\ Max{k|1<k<j且p_1…p_{k-1}},&\\ 1, &其他情况}
第五章 数组和广义表
5.1 数组和线性表的关系以及数组的运算
-
数组与线性表之间的关系:线性表的扩展,其数据元素本身也是线性表
-
数组的特点:
- 数组中各元素都具有统一的类型
- 可以认为,d维数组的非边界元素具有d个直接前趋和d个直接后继
- 数组维数确定后,数据元素个数和元素之间的关系不再发生改变,适合于顺序存储
- 每组有定义的下标都存在一个与其相对应的值
-
在数组上的基本操作:
- 给定一组下标,取得相应的数据元素值
- 给定一组下标,修改相应的数据元素值
5.2 数组的顺序存储结构
-
“行序为主序” 即 “低下标优先”,“列序为主序” 即 “高下标优先”
-
注:Pascal、C语言以行序为主序,Fortran 语言以列序为主序
数组是一种随机存取结构:对任一元素定位时间相等
5.3 矩阵的压缩存储//提醒我有空去加图
5.3.1对称矩阵
- 存储方法:只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间: sa[0.. n(n+1)/2-1] 。
5.3.2 三角矩阵
- 存储方法:重复元素c共享一个元素存储空间,共占用n(n+1)/2+1个元素空间: sa[0.. n(n+1)/2]。sa[0]=C
5.3.3 带状矩阵(对角矩阵)
-
特点:在nn的方阵中,非零元素集中在主对角线及其两侧共L(奇数)条对角线的带状区域内 — L对角矩阵。
-
存储方法:
- 以对角线的顺序存储,共n*L个元素。
- 只存储带状区内的元素。除首行和末行,按每行 L个元素,共 (n-2)L+(L+1)=(n-1)L+1 个元素。sa[0..(n-1)L]
5.3.4 随机稀疏矩阵
-
大多数元素为零。
-
常用存储方法:记录每一非零元素(i,j,aij )—节省空间,但丧失随机存取功能
- 顺序存储:三元组表
- 链式存储:十字(正交)链表
5.3.4.1 三元组表
1 |
|
-
求逆置矩阵
-
普通算法
-
快速转置
-
5.3.4.2 行逻辑链接的表
1 | typedef struct{ |
5.3.4.3 十字链表
1 | typedef struct OLNode |
5.4 广义表的定义和表示方法
-
概念:广义表是由零个或多个原子或者子表组成的有限序列。可以记作:LS=(d1, d2, … , dn )
- 原子:逻辑上不能再分解的元素。
- 子表:作为广义表中元素的广义表。
-
广义表中的元素全部为原子时即为线性表。线性表是广义表的特例,广义表是线性表的推广。
-
广义表的相关术语
- 表的长度:表中的元素(第一层)个数。
- 表的深度:表中元素的最深嵌套层数。
- 表头:表中的第一个元素。
- 表尾:除第一个元素外,剩余元素构成的广义表。
非空广义表的表尾必定仍为广义表
5.5 广义表的存储结构
5.5.1 头尾链表形式
1 | typedef enum {ATOM, LIST} ElemTag; |
5.5.2 扩展的线性链表形式
1 | typedef enum {ATOM, LIST} ElemTag; |
5.6 广义表的递归算法
- 广义表的定义是递归的。
第六章 树和二叉树
6.1 树的结构定义和基本操作
-
树是由n个结点组成的有限集合T,非空树满足
a) 有一个称之为根(root)的结点
b) 除根以外的其余结点被分成m个互不相交的集合T1, T2 ,…, Tm,其中每一个集合本身又是一棵树,且称为根的子树
-
树除根结点外,每个结点都仅有一个前趋结点。
-
树的基本术语
结点的度 结点拥有的子树数目。
叶子(终端) 结点度为0的结点。
分支(非终端) 结点度不为0的结点。
树的度 树的各结点度的最大值。
内部结点 除根结点之外的分支结点。
双亲与孩子(父与子)结点 结点的子树的根称为该结点的孩子;该结点称为孩子的双亲.
兄弟 属于同一双亲的孩子。
结点的祖先 从根到该结点所经分支上的所有结点。
结点的子孙 该结点为根的子树中的任一结点。
结点的层次 表示该结点在树中的相对位置。根为第一层,其它的结点依次下推;若某结点在第L层上,则其孩子在第L+1层上。
堂兄弟 双亲在同一层的结点互为堂兄弟。
树的深度 树中结点的最大层次。
有序树 树中各结点的子树从左至右是有次序的,不能互换。否则,称为无序树。
路径长度 从树中某结点Ni出发,能够“自上而下地”通过树中结点到达结点Nj,则称Ni到Nj存在一条路径,路径长度等于这两个结点之间的分支数。
树的路径长度 从根到每个结点的路径长度之和。
森林 是m棵互不相交的树的集合。
6.2 二叉树
-
二叉树的定义 二叉树是n个结点的有限集合,它或为空树(n=0),或由一个根结点和两棵互不相交的左子树和右子树的二叉树组成。
-
二叉树的特点
-
定义是递归的
-
结点的度小于3
-
是有序树
-
-
二叉树的每个结点至多只有两棵子树,且子树有左右之分,其次序不能任意颠倒。
-
满二叉树:一棵深度为k且有个结点的二叉树称为满二叉树。
-
完全二叉树:若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下面一层上的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。
-
二叉树的性质
-
二叉树的第i层上至多有2i-1(i1)个结点。
-
深度为k的二叉树至多有2k-1个结点()。
-
对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2 ,则n0 = n2+ 1。
-
具有n个结点的完全二叉树的深度为 log2n+1。
-
一棵具有n个结点的完全二叉树(又称顺序二叉树),对其结点按层从上至下(每层从左至右)进行1至n的编号,则对任一结点i(1in)有:
-
若i>1,则i的双亲是i/2;若i=1,则i是根,无双亲。
-
若2i小于等于n,则i的左孩子是2i;否则, i无左孩子。
-
若2i+1小于等于n,则i的右孩子是2i+1;否则, i无右孩子。
-
-
二叉树的顺序存储
1 |
|
- 二叉树的链式存储
1 | typedef struct node{ |
- 三叉存储:多了一个指向parent的指针,便于查找双亲的节点,但是增加了空间开销。
6.3 遍历二叉树
不会有人不会前中后序遍历二叉树吧不会吧不会吧
-
前序加后序无法确定一棵树。
-
层序加任意序都可以确定一颗二叉树。
6.4 线索二叉树
-
增加两个指针域fwd和bkwd分别指向前驱和后继,但存储空间的利用率会大大降低。
-
也可让空左子指针指向前驱,空右子指针指向后继。
6.5 哈夫曼树及其应用
-
结点权值: 有某种意义的实数(Wi)(比如文件中某一字符出现的次数)
-
结点的路径长度:从树根到每一个结点的路径上的分支数。
-
带权路径长度:结点的路径长度与该结点的权之积。
-
树的带权路径长度:树中所有叶子结点的带权路径长度之和。
-
最优二叉树(哈夫曼树):带权路径长度WPL最小的二叉树。
1 | Const m=结点数目;(m=2n-1) |
- 哈夫曼编码是不等长编码
- 哈夫曼编码是前缀编码,即任一字符的编码都不是另一字符编码的前缀
- 哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n,则哈夫曼编码树的结点总数为 2n-1
6.6 树和森林
进行一个树与二叉树的转换,再进行一个树与木木木木木的转换
-
树的存储结构
- 多重链表表示法:指针域是所有的孩子
- 双亲表示法:用一维数组存储每个结点的双亲的编号
- 孩子兄弟表示法:指针域指向第一个孩子节点和下一个兄弟结点
6.7 二叉树和树的应用实例
- 表达式的先序中序后序序列,与树的遍历异曲同工。
第9章 查找
本章约定,关键字类型为整形
9.1 概念和术语
- 查找表:同一类型的记录(数据元素)的集合。数据元素之间存在着松散的关系。为了提高查找的效率,可在元素之间人为地附加某种确定的关系。
- 关键字:记录(数据元素)中的某个数据项的值。
- 主关键字:该关键字可以唯一地标识一个记录。
- 次关键字:该关键字不能唯一标识一个记录。
- 查找:指定某个值,在查找表中确定是否存在一个记录,该记录的关键字等于给定值。
- 静态查找表:对查找表的查找仅是以查询为目的,不改动查找表中的数据。
- 动态查找表:在查找的过程中同时插入不存在的记录,或删除某个已存在的记录。
- 查找成功:查找表中存在满足查找条件的记录。
- 查找不成功:查找表中不存在满足查找条件的记录。
- 内查找:整个查找过程都在内存中进行。
- 外查找:在查找过程中需要访问外存。
- 平均查找长度ASL:查找方法时效的度量,为确定记录在查找表中的位置,需将关键字和给定值比较次数的期望值。
9.2 静态查找表
- 关键词:数据元素某个数据项的值,用来唯一标识该元素
9.2.1 顺序表的查找
9.2.2 有序表的查找
9.2.3 静态树表的查找
第10章 内部排序
有些排序用人话太难描述了,没个图真不行。
10.1 概述
10.1.1 什么是排序
- 排序:其目的是将一组“无序”的记录序列调整为“有序”的记录序列,是根据记录关键字的值的非递减或者非递增(递增或者递减)的关系将文件记录的次序重新排列。
10.1.2 排序的分类
根据排序时文件记录的存放位置:
-
内部排序: 排序全部在内存中进行。内部排序的过程是一个逐步扩大有序序列长度的过程,内部排序的方法基于不同的扩大方法。
-
外部排序:排序过程中存在内外存信息的交换
根据排序前后相对关键字记录的相对次序:
-
稳定排序:
-
不稳定排序:有实例不满足稳定性要求。
根据存储结构划分种类:
-
顺序存储
-
链式存储
-
地址存储:待排记录顺序存储,排序时只对辅助表(关键字+指针)进行物理排序。
根据内部排序的方法:
插入、选择、归并、基数、交换
根据排序算法所需要的辅助空间:
-
就地排序:O(1)
-
非就地排序:O(n)或与n有关
10.1.3 评价排序算法的主要标准
-
时间开销:比较操作、移动操作,同时根据结果分为最好、最坏、平均
-
空间开销:辅助空间的大小
讨论约定:
顺序存储
1 |
|
10.2 插入排序
- 直接插入排序(基于顺序查找):
嗯着找,找到就插入。复杂度O(n^2)
- 折半插入排序(基于折半查找):
将循环中每一次在区间 [1,i-1] 上为确定插入位置的顺序查找操作改为折半查找操作。可以减少关键字间的比较次数。
- 表插入排序(基于链式存储):
构造静态链表,用改变指针来代替移动记录操作,减少记录的移动次数。
- 2-路插入思想:
设置与r同样大小的辅助空间d,将r[1]赋值给d[1],将d看作循环向量。对于r[i] ,若r[i] d[1],则插入d[1]之后的有序序列中,反之则插入d[1]之前的有序序列中。(避免r[1]关键字最小/最大),减少记录的移动次数但相应的使空间的开销翻倍
- 希尔排序(基于逐渐缩小增量):
先选定一个记录下标的增量d,将整个记录序列按增量d从第一个记录开始划分为若干组,对每组使用直接插入排序的方法;然后减小增量d,不断重复上述过程,如此下去,直到d=1(此时整个序列是一组)。
是一种典型的就地排序。
10.3 交换排序
10.3.1 冒泡排序
将两个相邻记录的关键字进行比较,若为逆序则交换两者位置,小者往上浮,大者往下沉。
10.3.2 快速排序
指定枢轴/支点/基准记录rp,通过一趟排序将其放在正确的位置上,它把待排记录分割为独立的两部分,使得左边记录的关键字 右边记录的关键字对左右两部分记录序列重复上述过程,依次类推,直到子序列中只剩下一个记录或不含记录为止。(可以用递归方法实现)
非稳定排序。
10.4 选择排序
10.4.1 简单选择排序
每次从待排序列中选出关键字最小记录作为有序序列中最后一个记录,直至最后一个记录为止。
是就地排序。
时间复杂度为O(n^2)。
10.4.2 树形选择排序
锦标赛名次产生过程。较简单选择排序减少“比较”次数,但辅助空间较多,需要与最大值进行多余的比较。
是稳定排序。
时间复杂度为O()
10.4.3 堆排序
平均性能接近最坏性能
就地排序。
不稳定排序。
10.5 归并排序
指将两个或两个以上的同序序列归并成一个序列的操作。
10.5.1 两路归并排序
任何情况时间复杂度O
非就地排序,空间复杂度O(n)
很少用于内部排序
10.5.2 自然两路归并排序
以游程(自然的有序段)作为子序列进行归并,可以比直接两路归并更有效。
不稳定排序
10.6 基数排序(分配排序)
通过“分配”和“收集”过程来实现排序,时间复杂度可以突破基于关键字比较一类方法的下界O(nlgn),达到O(n)。
借助多关键字思想实现排序
10.7 各种内部排序方法的比较
老师说了一定要记住,但确实就记不住
未完待续 更新日期:20-12-13
这门“重实践”的课背的东西好多,我麻的一比,属于是艺术史了。 ↩︎