数据结构基础讲义

1、IT Education & TrainingDate:25 February 2022数据结构-肖兴贵传智播客IT Education & TrainingDate:25 February 2022 1 概要 2 线性表 3 栈和队列 4 树和二叉树 5 查找和排序主要内容IT Education & TrainingDate:25 February 20221.1 讨论的范畴算法+数据结构 = 程序设计 处理问题的策略给出问题的数学模型编制出的指令集处理问题用计算机问题问题构建数学模型构建数学模型程序实现程序实现IT Education & Training

2、Date:25 February 20221.1 讨论的范畴 例1 求小红C语言和数据结构两门语言的考试的平均成绩成绩和总成绩。全省的呢？ 例2 酒店管理中的客房分配问题。 例3 煤气管道的铺设问题。 等等 例子中的数学模型正是数据结构要讨论的问题。IT Education & TrainingDate:25 February 20221.2 定义 数据结构是一门讨论描述现实世界实体的数学模型及其上的操作在计算机中如何表示和实现的学科。 a. 在解决问题时可能遇到的典型的逻辑结构（数据结构） b. 逻辑结构的存储映象（存储实现）c. 数据结构的相关操作及其实现。(算法)通俗点讲，数据结

3、构研究的是数据的存储和操作。IT Education & TrainingDate:25 February 20221.3 三个方面 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：查找、排序、插入、删除、修改等数据的运算：查找、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构IT Education & TrainingDate:25 February 20221.3 逻辑和物理结构逻辑结构物理结构IT Education & Trai

4、ningDate:25 February 2022 数学模型 集合和关系 数据和信息 数据元素 数据项 关键码 抽象数据类型1.4 相关概念IT Education & TrainingDate:25 February 2022 算法是特定问题求解步骤的描述，在计算机中表现为指令的有限序列，算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。 数据结构和算法的关系：数据结构是专门研究数据的存储问题，而对存储后的数据进行相应的操作就是算法。1.5 算法的定义IT Education & TrainingDate:25 February 20221.

5、5 算法效率的度量 我们通过大O表示法来表示算法的效率：时间复杂度、空间复杂度。规则如下：（1）只关注最高次项，常数项和次要项忽略；（2）时间复杂度是指最坏时间复杂度；（3）只有常数项记做1。执行次数函数执行次数函数阶阶非正式术语非正式术语12O(1)常数阶2n+3O(n)线性阶3n2+2n+1O(n2)平方阶5log2n+20O(logn)对数阶2n+3nlog2n+19O(nlogn)nlogn阶6n3+2n2+3n+4O(n3)立方阶2nO(2n)指数阶IT Education & TrainingDate:25 February 20221.6 时间复杂度举例 线性阶：O(n)

6、 平方阶: O(n2)IT Education & TrainingDate:25 February 20221.6 空间复杂度举例 空间复杂度：O(n)IT Education & TrainingDate:25 February 20222.1 线性表概念 线性结构的基本特点是节点之间满足线性关系。数组、链表、栈、队列都属于线性结构。他们的共同之处，是节点中有且只有一个开始节点和终端节点。他们分别属于几种不同的抽象数据类型实现，它们之间的区别，主要就是操作的不同。 线性表是零个或者多个数据元素的有限序列，数据元素之间是有顺序的，数据元素个数是有限的，数据元素的类型必须相同I

7、T Education & TrainingDate:25 February 20222.1 编程实战 动态数组数组到底应该有多大才合适，通常不得而知。所以希望能够在运行时具有改变数组大小的能力。（基本操作：创建、销毁、插入、删除、遍历打印） 单向链表 头指针头指针a0a1an 1( a )( b )IT Education & TrainingDate:25 February 20222.3 编程实战头指针头指针a0a1an 1( a )( b ) 经典双向链表主要操作：初始化头结点、添加、删除、获取元素、遍历IT Education & TrainingDate:2

8、5 February 2022Q1. 创建两循环单向链表并将它们合为一各链表？Q2. 头指针和头节点有什么区别？头结点和其他节点有什么区别？第1天 习题IT Education & TrainingDate:25 February 20223.1 栈的特点 栈为一种可以实现“先进后出”的存储结构，凡是对数据的处理具有“后进先出(LIFO)”的特点，都可以用栈这种数据结构来操作。 栈的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。IT Education & TrainingDate:25 February 20223.2 编程实战 栈的顺序存储利用一组地址

9、连续的的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top只是栈顶元素在顺序表中的位置。 栈的链式存储IT Education & TrainingDate:25 February 20223.4 队列的特点 队列为一种可以实现“先进先出”(FIFO)的存储结构。 队列是一种特殊的受限制的线性表，只允许在一端进行插入操作，而在另一端进行删除操作的线性表，队列不允许在中间部位进行操作。IT Education & TrainingDate:25 February 20223.5 编程实战 队列的顺序存储IT Education & TrainingDate:25

10、February 20223.6 编程实战 队列的链式存储IT Education & TrainingDate:25 February 2022Q1. 假设以带头结点的循环链表表示队列，并又只设一个指针指向队尾元音结点(注意不设头指针)，试编写相应的队列初始化、入队列和出队列的算法。Q2. 假设称正读和反读都相同的字符序列为“回文”，例如，”aba”和”abcba”是回文，”abcde”和”ababab”则不是回文。试写一个算法判别读入的一个以“”为结束符的字符序列是否是“回文”。第2天 习题IT Education & TrainingDate:25 February 20

11、224.1 树的定义定义：- 由一个或多个结点组成的有限集合T，有且仅有一个结点称为根，其余的结点分为m个互不相交的有限集合T1, T2，Tm。每个集合本身又是棵树，被称作这个根的子树。树的特点：非线性结构，有一个直接前驱，但可能有多个直接后继（1:n）树的定义具有递归性，树中还有树树可以为空，即节点个数为0IT Education & TrainingDate:25 February 20224.2 树的术语专业术语专业术语含义含义根也叫根结点(没有前驱)叶子也叫终端结点(没有后继)森林指m棵不相交的树的集合(例如删除A后的子树个数)有序树结点各子树从左至右有序，不能互换（左为第一）

12、无序树结点各子树可互换位置双亲 即上层的那个结点(直接前驱) parent孩子即下层结点的子树 (直接后继) child兄弟同一双亲下的同层结点（孩子之间互称兄弟）sibling堂兄弟即双亲位于同一层的结点（但并非同一双亲）cousin祖先即从根到该结点所经分支的所有结点子孙即该结点下层子树中的任一结点结点也叫节点，即树的数据元素结点的度、树的度结点挂接的子树数、所有结点度中的最大值结点的层次从根到该结点的层数（根结点算第一层）终端结点即度为0的结点，即叶子 分支结点除树根以外的结点（也称为内部结点）树的深度(或高度)指所有结点中最大的层数(从根节点到最低层的结点层数)IT Education

13、 & TrainingDate:25 February 20224.3 树的表示法IT Education & TrainingDate:25 February 20224.4 树的表示法IT Education & TrainingDate:25 February 20224.5 二叉树的概念二叉树由一个根结点加上两棵分别称为左子树和右子树的互不相交的树组成：每个结点最多只有两棵子树（不存在度大于2的结点）左子树和右子树次序不能颠倒（有序树）IT Education & TrainingDate:25 February 20224.6 树转化为二叉树左孩子右兄

14、弟表示法可以将一颗多叉树转化为一颗二叉树。IT Education & TrainingDate:25 February 20224.7 满二叉树和完全二叉树IT Education & TrainingDate:25 February 20224.7 树的顺序存储多叉树顺序存储的缺陷IT Education & TrainingDate:25 February 20224.7 完全二叉树的顺序存储非完全二叉树存储缺点：浪费空间；插入、删除不便完全二叉树存储IT Education & TrainingDate:25 February 20224.7 二叉树的链

15、式存储二叉链存储IT Education & TrainingDate:25 February 20224.7 二叉树的链式存储三叉链存储IT Education & TrainingDate:25 February 20224.8 二叉树的遍历 遍历是指按某条搜索路线遍访每个结点且不重复（又称周游），遍历是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。 牢记一种约定，对每个结点的查看都是“先左后右”。 遍历方式遍历方式特点特点先序遍历(先根遍历，DLR)根 - 左子树 - 右子树中序遍历(中根遍历，LDR)左子树 - 根 - 右子树后序遍历(后根

16、遍历，LRD)左子树 - 右子树 - 根IT Education & TrainingDate:25 February 20224.8 二叉树的遍历IT Education & TrainingDate:25 February 20224.8 编程实战 二叉树的动态创建和释放 二叉树的递归遍历 计算二叉树叶子节点数目 计算二叉树高度IT Education & TrainingDate:25 February 2022第3天 习题Q1 编写递归算法，在二叉树中求位于先序序列中第A个位置的结点的值。Q2 编写递归算法，计算二又树中叶子结点的数目。Q3 编写递归算法，将二叉

17、树中所有结点的左、右子树相互交换。IT Education & TrainingDate:25 February 20225.1 查找的概念根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的一个记录，则称查找是成功的。IT Education & TrainingDate:25 February 20225.2 编程实战 顺序查找 二分查找IT Education & TrainingDate:25 February 20225.3 排序的概念排序是计算机内经常进行的一种操作，其目的是将一组“无序”的数据元素调整为“有序”的数据元素。排序是高效查询的前提。IT Education & TrainingDate:25 February 20225.4 编程实战 冒泡 选择 插入排序IT Education & TrainingDate:25 February 20225.5 排序算法比较IT Education & TrainingD