数据结构与算法课程笔记
计算机也许足够快,但并非无限快。
数据结构与算法课程笔记
intros
绪论
这门课研究什么?
非数值计算问题的数学模型不再是数学方程,而是诸如线性表、树和图的数据结构。因此,简单地说,数据结构是一门研究非数值计算程序设计中的操作对象,以及这些对象之间的关系和操作的学科。
八股:数据、数据元素、数据项和数据对象
- 数据 (Data) 是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。
- 数据元素(Data Element)是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、记录等。数据元素用千完整地描述一个对象,如前一节示例中的一名学生记录,树中棋盘的一个格局(状态),以及图中的一个顶点等。
- 数据项 (Data Item) 是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。
- 数据对象 (Data Object) 是性质相同的数据元素的集合,是数据的一个子集。
- ……只要集合内元素的性质均相同,都可称之为一个数据对象。
八股:数据结构
逻辑结构
逻辑结构:数据的逻辑结构是从逻辑关系上描述数据,
它与数据的存储无关,是独立于计算机的。
数据的逻辑结构有两个要素: 一是数据元素;二是关系。
存储结构
数据对象在计算机中的存储表示称为数据的存储结构,也称为物理结构。
链式存储结构需要给每个结点附加指针字段,用于存放后继元素的存储地址。
八股:算法
五个重要特性:
- 有穷性
- 确定性
- 可行性
- 输入
- 输出
评价优劣的标准:
- 正确性
- 可读性
- 健壮性
- 高效性
复杂度:
设每条语句执行一次所需的时间均是单位时间, 则一个算法的执行时间可用该算法中有语句频度之和来度量。
省略号:它表示随问题规模 n 的增大,算法执行时间的增长率和
线性表
单链表
顺序存储结构是一种随机存取(Random Access)的存储结构。
链式表示是循序访问/顺序存取的。
下面是单链表。
1 |
|
有几个需要注意的地方:
- 一般情况下,为了处理方便,在单链表的第一个结点之前附设一个结点,称之为头结点。
- 首元结点是指链表中存储第一个数据元素
的结点。 - 头结点便于首元结点的处理,便于空表和非空表的统一处理————当链表不设头结点,假设
为单链表的头指针,它应该指向首元结点,则当单链表为长度 为 的空表时, 指针为空(判定空表的条件可记为: )但是在设置头结点的情况下,就可以用头结点 的后继指针, 来判断是否为空表了。
插入和删除操作:
1 | void insert(node * prev, int number){ |
循环链表
其特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点。
双向链表
1 |
|
这是删除和插入操作。
1 | void insert(node * p, int number){ |
顺序 vs. 链表
- 空间性能:存储空间的分配;存储密度的大小
- 时间性能:Access, insert, delete
栈与队列
栈 (stack) 是限定仅在表尾进行插入或删除操作的线性表。 因此, 对栈来说, 表尾端有其特殊含义, 称为栈顶 (top), 相应地, 表头端称为栈底 (bottom)。 不含元素的空表称为空栈。
队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表的一端进行插入,而在另一端删除元素。
实现
顺序栈是指利用顺序存储结构实现的栈,即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针 top 指示栈顶元素在顺序栈中的位置。
一般我们可能会用C++ STL stack和C++ STL queue来实现栈和队列的操作。
循环队列
怎样解决这种 “假溢出” 问题呢? 一个较巧妙的办法是将顺序队列变为一个环状的空间,如图 3.13 所示,称之为循环队列。
串、数组和广义表
串
串(string)(或字符串)是由零个或多个字符组成的有限序列, 一般记为
KMP算法
出于我本人对中国计算机教科书的了解,这一段我使用了阮行止师傅博客中的笔记和OI Wiki对应页面上的说明作为我的参考资料。
数组
数组是由类型相同的数据元素构成的有序集合,每个元素称为数组元素,每个元素受
数组的顺序存储
由于存储单元是一维的结构, 而数组可能是多维的结构, 则用一组连续存储单元存放数组的数据元素就有次序约定问题。
C语言用的是以行序为主序的存储结构。也就是说,
容易看出,数组元素的存储位置是其下标的线性函数,一旦确定了数组各维的长度,
特殊数组的压缩
以对称矩阵为例。
满足
显然在
广义表
空表也是广义表。
- 取表头 GetHead(LS): 取出的表头为非空广义表的第一个元素,它可以是一个单原子,也可以是一个子表。
- 取表尾 GetTail(LS): 取出的表尾为除去表头之外,由其余元素构成的表。即表尾一定是一个广义表。比如说,如果该表只有一个元素,那么表尾就是空表。
按照表头和表尾可以非常方便地递归式表达广义表。
树和二叉树
定义 & 基本术语
树(Tree)是
- 有且仅有一个称之为根的结点;
- 除根结点以外的其余结点可分为
个互不相交的有限集 其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。 - 节点:树这一数据结构的数据元素。
- 节点的度:结点拥有的子树数称为结点的度。
- 树的度:树的度是树内各结点度的最大值
- 叶子: 度为 0 的结点称为叶子或终端结点
- 非终端结点:度不为 0 的结点称为非终端结点或分支结点。除根结点之外,非终端结点也称为内部结点。
- 双亲和孩子:结点的子树的根称为该结点的孩子,相应地,该结点称为孩子的双亲。
- 兄弟:同一个双亲的孩子之间互称兄弟
- 祖先:从根到该结点所经分支上的所有结点
- 子孙:以某结点为根的子树中的任一结点都称为该结点的子孙。
- 层次:根的层次为1,树中任一结点的层次等千其双亲结点的层次加 l
- 堂兄弟:双亲在同一层的结点互为堂兄弟。
- 树的深度:树中结点的最大层次称为树的深度或高度。
- 森林:是
棵互不相交的树的集合。
二叉树的递归定义表明二叉树或为空,或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。由千这两棵子树也是二叉树,则由二叉树的定义,它们也可以是空树。由此,二叉树可以有5种基本形态。
特殊形态二叉树
满二叉树:深度为
完全二叉树:深度为
除第
存储
顺序存储结构使用一组地址连续的存储单元来存储数据元素,为了能够在存储结构中反映出结点之间的逻辑关系,必须将二叉树中的结点依照一定的规律安排在这组单元中。对千完全二叉树,只要从根起按层序存储即可,依次自上而下、自左至右存储结点元素,即将完全二叉树上编号为
由此可见, 这种顺序存储结构仅适用于完全二叉树。因为, 在最坏的情况下, 一个深度为
1 |
|
遍历
指按某条搜索路径巡访树中每个结点,使得每个结点均被访问一次,而且仅被访问一次。
主要有三种:
- 先序遍历:根左右
- 中序遍历:左根右
- 后序遍历:左右根
由二叉树的先序序列和中序序列,或由 其后序序列和中序序列均能唯一地确定一棵二叉树。
但是,由一棵二叉树的先序序列和后序序列不能唯一确定一棵二叉树,因为无法确定左右子树两部分。
线索化
所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。[1]
树 & 森林
存储:双亲表示法(仅表示data和parent);孩子表示法(同构或不同构、线性表);孩子兄弟表示法(这种存储结构的优点是它和二叉树的二叉链表表示完全一样, 便千将一般的树结构转换为二叉树进行处理, 利用二叉树的算法来实现对树的操作。因此孩子兄弟表示法是应用较为普遍的一种树的存储表示方法。)
哈夫曼树
哈夫曼(Huffman)树又称最优树,是一类带权路径长度最短的树。
哈夫曼编码
在5.2节提出的案例5.1中已经讨论,在进行数据压缩时,为了使压缩后的数据文件尽可能短,可采用不定长编码。其基本思想是:为出现次数较多的字符编以较短的编码。为确保对数据文件进行有效的压缩和对压缩文件进行正确的解码,可以利用哈夫曼树来设计二进制编码。
图
查找
概念表和术语
- 查找表:查找表是由同一类型的数据元素(或记录)构成的集合。
- 关键字:关键字是数据元素(或记录) 中某个数据项的值。
- 查找:查找是指根据给定的某个值,在查找表中确定一个其关键字等千给定值的记录或数据元素。
- 动态与静态查找:若在查找的同时对表做修改操作(如插入和删除),则相应的表称之为动态查找表,否则称之为静态查找表。
- 平均查找长度:为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值,称为查找算法在查找成功时的平均查找长度(ASL)。
查找方式
顺序查找,时间复杂度为
二分查找,时间复杂度为
折半查找的优点是:比较次数少,查找效率高。其缺点是:对表结构要求高,只能用于顺序存储的有序表。查找前需要排序,而排序本身是一种费时的运算。同时为了保持顺序表的有序性,对有序表进行插入和删除时,平均比较和移动表中一半元素,这也是一种费时的运算。因此,折半查找不适用于数据元素经常变动的线性表。
分块查找 (Blocking Search) 又称索引顺序查找,这是一种性能介于顺序查找和折半查找之间的一种查找方法。时间复杂度为
要求:
- 分块有序;构建索引表
分块查找的优点是:在表中插入和删除数据元素时,只要找到该元素对应的块,就可以在该块内进行插入和删除运算。 由于块内是无序的,故插入和删除比较容易,无需进行大量移动。 如果线性表既要快速查找又经常动态变化,则可采用分块查找。 其缺点是:要增加一个索引表的存储空间并对初始索引表进行排序运算。
- 树表查找
二叉排序树 (Binary Sort Tree) 又称二叉查找树,它是一种对排序和查找都很有用的特殊二叉树。
- 平衡树查找
如何创建一棵平衡二叉树呢?插入结点时, 首先按照二叉排序树处理, 若插入结点后破坏了平衡二叉树的特性, 需对平衡二叉树进行调整。 调整方法是:找到离插入结点最近且平衡因子绝对值超过1的祖先结点, 以该结点为根的子树称为最小不平衡子树, 可将重新平衡的范围局限于这棵子树。
- B树查找
散列表查找
如果能在元素的存储位置和其关键字之间建立某种直接关系,那么在进行查找时,就无需做比较或做很少次的比较,按照这种关系直接由关键字找到相应的记录。这就是散列查找法 (Hash Search) 的思想,它通过对元素的关键字值进行某种运算,直接求出元素的地址, 即使用关键字到地址的直接转换方法,而不需要反复比较。因此,散列查找法又叫杂凑法或散列法。
散列查找法主要研究以下两方面的问题:
- 如何构造散列函数;
- 如何处理冲突。
处理散列表的冲突
- 线性探测法的优点是:只要散列表未填满,总能找到一个不发生冲突的地址。缺点是:会产生 ”二次聚集“ 现象。
- 链地址法的基本思想是:把具有相同散列地址的记录放在同一个单链表中,称为同义词链表。