2019年数据结构课件

《2019年数据结构课件》由会员分享，可在线阅读，更多相关《2019年数据结构课件（39页珍藏版）》请在金锄头文库上搜索。

1、数据结构,数学科学学院 朱松 13901992420 QQ:1651418549,学科简介,数据结构+算法=程序 研究对象 大量数据，特别是非数值数据的复杂结构及关系，如图像、声音、字符等 研究内容 数据的逻辑结构 数据的存储结构 数据的基本运算 算法 算法的特征 算法的描述 算法分析及评价,课程内容,数据结构 线性表 栈和队列 串 数组和广义表 树和二叉树 图 基本算法 查找 排序,课程内容,树 线索二叉树、哈夫曼树 图 最小生成树、最短路径 查找 静态查找、动态查找、哈希查找 排序 插入排序 直接插入排序、希尔排序 交换排序 冒泡排序、快速排序 选择排序 直接选择排序、堆排序,参考书目,1

2、. 颜辉、付宏主编：实用数据结构教程，2019 2. 殷人昆主编：数据结构，2019 3.（美）Sartaj Sahni 著，汪诗林等译：数据结构、算法与应用，2019,数据结构基本概念和术语,数据 指所有能输入到计算机中并能被计算机程序识别和处理的符号集合 数据一般分数值型数据和非数值型数据 数值数据：包括整数、实数或复数等。主要用于工程计算、科学计算等。 非数值数据：包括字符、文字、图形、图像、语音等。用于情报检索、企业管理、人工智能、远程教育、远程医疗、电子商务、电子图书馆和办公自动化等诸多领域。 数据元素 数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可以有

3、一个或若干个数据项组成。数据元素也称为结点或记录。 数据项 数据的具有独立意义的不可分的最小单位，它是对数据的数据元素属性的描述，又称为字段或域。,数据结构基本概念和术语,数据对象 具有相同性质的数据元素的集合，是数据的子集。 数据类型 是具有相同性质的计算机数据的集合及定义在这个数据集合上的一组操作的总称。 原子类型：如果一个数据元素由一个数据项构成，这个数据元素的类型就是这个数据项的数据类型，其值在逻辑上是不可分解的。 结构类型：如果一个数据元素由多个不同类型的数据项组成，这个数据元素的类型就是由各数据项类型构成的结构类型。,数据结构基本概念和术语,抽象数据类型(Abstract Data

4、 Type) 简写为ADT，是一个数据结构以及定义在该结构上的一组操作的总称。 数据结构+定义在此数据结构上的一组操作=抽象数据类型 抽象数据类型包括数据对象定义、数据关系定义和基本操作定义三部分。 三元组表示为(D,S,P) D:数据对象；S：D上的关系集；P：对D的基本操作集。 数据结构 是相互之间存在一种或多种特定关系的数据元素及定义这些数据元素基本运算的集合。,数据结构的研究内容,数据的逻辑结构 数据集合中各数据元素之间所固有的逻辑关系。对数据元素间逻辑关系的描述称为数据的逻辑结构，在形式上，可以定义为一个二元组：（D，S） D：数据元素的有限集，S：D上关系的有限集。 集合结构 集合

5、结构中，元素间的次序是随意的 线性结构 线性结构是数据元素的有限序列，常用的线性结构有线性表、栈、队列和串。 树形结构 树形结构中，除一个特殊元素称为根，它没有前趋只有后继外，其余元素都有仅有一个前趋，可以有多个后继，又称为层次结构。 图形结构 图是最一般的数据结构，图中每个元素的前趋和后继的数目都不限。 基本结构又可分为线性结构和非线性结构。它独立于计算机。,数据结构的研究内容,数据的存储结构 数据的存储结构是数据的逻辑结构在计算机内部的表示和实现，又称为数据的物理结构，它包括数据元素的表示和关系的表示，和计算机语言无关。 顺序存储方法 用一组地址连续的存储空间一次存放数据元素，是逻辑上相邻

6、的数据元素存储时物理位置也相邻。 特点： 存储密度大，存储空间利用率高； 是一种随机存储结构； 插入和删除操作复杂。,数据结构的研究内容,数据的存储结构 链式存储方法 用一组地址任意的存储空间依次存放数据元素，即不要求逻辑上相邻的数据元素在物理存储上也相邻，数据元素之间的相邻关系通过附加指针来体现，通过指针将数据元素串联起来。 链式存储方法不仅存储数据元素的值，还存储数据元素之间的关系。 特点 除存储数据元素本身的信息外，还要存储数据元素之间关系信息，因此与顺序存储结构相比存储密度小，存储空间利用率低； 逻辑上相邻的数据元素，物理位置上不一定相邻，是非随机的存储结构； 插入和删除操作简单灵活，

7、只需改变指针值即可。 索引存储方法、散列存储方法,数据结构的研究内容,数据的基本运算 每一种逻辑结构都有一个运算的集合。这些运算实际上实在数据元素上施加的一系列抽象操作，即指这些操作要求做什么，但无需考虑如何做；以下为一些常见的基本运算。 查找：就是在数据结构里查找满足一定条件的数据元素 插入：向数据结构中添加新的数据元素 删除：把指定的数据元素从数据结构中去掉 修改：更改指定数据元素的一个或多个属性值 排序：按指定的关键字将数据元素的次序字数据机构中重新排列。,算法,算法概念 算法是解决问题方案准确而完整的描述。它是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操

8、作。 算法特征 有穷性：一个算法必须在执行有限步骤之后结束，而且每一步都必须在有限时间内完成。 确定性：算法中每条指令必须有确切含义，无二义性。且在任何条件下，算法只有唯一的一条执行路径。 可行性：算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 输入：一个算法有零个或多个输入，这些输入取自于某个特定的数据对象集合。 输出：一个算法至少有一个或多个输出，这些输出是同输入有着某些特定关系的量。,算法,算法的描述 编写一个算法时，可以采用自然语言、流程图、计算机语言或专门为描述算法而设计的语言。 算法分析及评价 正确性：是设计和评价一个算法的首要条件。 所设计的程序没有语法错误。

9、 所设计的程序对于几组输入数据能够得出满足要求的结果。 所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果 程序对于一切合法的输入数据都能产生满足要求的结果。达到第四层含义的正确极为困难，且代价巨大。 可读性：是指一个算法供人们阅读和理解的容易程度。相应的说明文档是必须的。 健壮性：是指一个算法对不合理数据输入的反应和处理能力。 算法的时间效率：就是考虑一个算法运行时所需时间的多少。 算法的空间效率：算法的空间复杂度是指在算法的执行过程中，需要的辅助空间数量。,线性表,定义 线性表是由n个数据元素组成的有限序列。 逻辑特征 线性表用二元组可以表示为： 基本逻辑

10、特征是线性表中的数据元素之间存在着一对一的关系 例1：将两个线性表La和Lb合并为一个线性表 例2：已知线性表La和Lb中的数据元素按值非递减有序排列，现要求La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。,线性表,顺序存储结构 线性表的顺序存储结构又简称为顺序表。 基本操作：查找、插入、删除 链式存储结构 线性表的链式存储结构又简称为链表。 型式：单链表、双链表、循环链表、静态链表 静态链表：是用数组元素的下标来模拟单链表的指针，即用数组来描述单链表。 问题：能否用数组描述双链表 基本操作：查找、插入、删除,线性表,顺序和链式存储的比较 顺序存储结构的优点 存储结

11、构简单、直观、易理解 逻辑位置相邻则物理位置相邻 随机存储，方便灵活 顺序存储结构的缺点 需连续的存储空间，不易控制空间分配 插入和删除操作效率低 链式存储结构的优点 插入、删除操作简单 存储容量确定，不造成空间浪费 链式存储结构的缺点 额外存储指针信息 查找操作复杂,线性表,例3：一元多项式的表示与运算 表示、加法、乘法 方法一： 方法二：,栈,定义 一种先进后出的线性表，只允许在表的一端进行插入删除操作。 允许插入和删除操作的一端称为栈顶，另一端为栈底。 插入元素又称为进栈或入栈，删除元素又称为出栈或退栈。 例1. 括号匹配问题 两种括号：圆括号和方括号；允许随意嵌套。 正确格式：()，(

12、)等 错误格式：()，)等 例2. 函数调用 运行被调用函数前的工作： 将所有的实在参数、返回地址等信息传递给被调用函数保存 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口。 被调用函数返回前的工作 保存被调函数的计算结果 释放被调函数的数据区 依照被调函数保存的返回地址将控制转移到调用函数,栈,例3. 开关盒布线 给定一个矩形布线区域，其外围有若干针脚。两个针脚之间通过布设一条金属线路而实现互连。这条线路被称为电线，被限制在矩形区域内。如果有电线交叉，则发生短路。每对互连的针脚被称为网组。 问题：给定一个开关盒布线实例，确定它是不是一个可布线的。 例4. 迷宫老鼠 迷宫是一个

13、矩形区域，它有一个入口和一个出口。在迷宫的内部包含不能穿越的墙或障碍。 假定用nxm的矩阵来描述迷宫，位置(1,1)表示入口，(n,m)表示出口，n和m分别代表迷宫的行数和列数。 问题：寻找一条从入口和出口的路径。 问题1. 表达式求值问题 用两个栈分别记录运算符和运算对象，支持加减乘除和圆括号 问题2. 汉诺塔,队列,定义 一种先进先出的线性表；只允许在一端进行插入，另一端删除。 允许插入的一端称为队尾，允许删除的一端称为队头。 顺序存储结构 解决“假溢出 解决下标越界 解决头尾指针相同时的满空二义性 问题1. 迷宫老鼠之最短路径 问题2. 识别图元 数字化图像是一个mxm的像素矩阵。在单色

14、图像中，每个像素的值要么为0，要么为1，值为0的像素表示图像的背景，值为1的像素则表示图元上的一个点，称为图元像素。彼此相邻的图元像素构成一个图元。,串,定义 由零个或多个字符组成的有限序列，也称字符串。 串的模式匹配（查找子串） S(n字符)，T(m字符)为给定的两个串，从S中查找等于T的子串；S称为主串，T称为模式串。 Brute-Force算法(BF算法) (O(mn) 从主串S的第pos个字符起和模式串的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较。 最坏情况m(n-m) KMP算法(Knuth,Morris,Pratt) (O(m+

15、n) 1. 首先在模式串中找出与其首字母起子串相重叠的各个子串。 2. 从主串S的第一个字母与模式串的第一个字母开始依次比较，如发现不同，则根据情况滑动模式串，再从发现不同的那个字母开始比较。 例：凯撒密码加密问题 将明文中的所有字母都在字母表上向后按照一个固定数目进行偏移后被替换成密文。,数组,定义 数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。 二维数组的存储 以行为主序的存储方式，称为行优先存储。 以列为主序的存储方式，称为列优先存储。 特殊矩阵的压缩存储 对称矩阵、三角矩阵、对角矩阵等 稀疏矩阵的压缩存储 三元组顺序表 (行下标,列下标,元素) 十字链表 (行下标,

16、列下标,元素,指向同行下个元素指针 ,指向同列下个元素指针 ) 每行首个非零元素指针列表 每列首个非零元素指针列表 基本运算 转置、加法、乘法,广义表,定义 广义表是n个数据元素的有限序列，每个数据元素可以是单个元素，也可以是广义表。 广义表的定义是一个递归的定义。 广义表记为：LS=(a1,a2,an),ai可为单个元素，称为LS的原子，用小写字母表示；也可为广义表，称为LS的子表，用大写字母表示。 表头：LS的第一个元素a1为LS的表头。 表尾：除第一个元素外，其余元素组成的表(a2,an)为LS的表尾。 长度：广义表中包含元素的个数(包含原子和子表)，即最高层表结点的个数。 深度：广义表中括号嵌套的最大层数。 例 A=()：一个空表，长度为零。 B=(e)：有一个原子，长度为1。 C=(a,(b,c,d)：长度为2，元素分别为原子和子表。 D=(A,B,C)：长度为3，元素都是列表。 E=(a,E)：一个递归的表，长度为2。,广义表,存储 头尾链表存储 表结点：标志域、表头指针、表尾指针 原子结点：标志域、值域 typedef enumATOM,LI