第2章 数据结构

1、? 算法算法? 数据结构概述数据结构概述? 线性结构线性结构? 栈和队列栈和队列? 树树? 图图第第2章章 数据结构数据结构 数据结构是讨论非数值类问题的对象描述、信息组织方法及其相应的操作。 第第2章章 数据结构数据结构电子计算机的主要用途：电子计算机的主要用途： 早期：早期： 主要用于数值计算。主要用于数值计算。 后来：后来： 处理逐渐扩大到非数值计算领域处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）（能处理多种复杂的具有一定结构关系的数据）数学模型数学模型选择计算机语言选择计算机语言编出程序编出程序测试测试最终解答最终解答数据元素之间的相互关系一般无法用数学方程加

2、以描述数据元素之间的相互关系一般无法用数学方程加以描述数据结构的数据结构的研究内容算法算法数据结构概述数据结构概述线性结构线性结构栈和队列栈和队列数组数组树树图图第第2章章 数据结构数据结构1. 算法的特征算法: 对问题求解的描述，具有以下五个重要的特征： 1）有穷性：一个算法必须保证执行有限步之后结束。 2）确切性：算法的每一步骤必须有确切的定义。 3）输入：一个算法有0个或多个输入，以刻画运算对象的初始情况。 4）输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。 5）可行性：比如，永动机则不可行。一、算法2、算法的描述: 1）流程图 2）伪代码类似

3、程序设计语言 3、算法的基本结构 算法代码化的过程:1）顺序结构 2）分支结构 3）循环结构一、算法 算法的时间复杂度是指（ ）。A. 执行算法程序所需要的时间B. 算法程序的长度C. 算法执行过程中所需要的基本运算次数D. 算法程序中的指令条数一、算法 算法的空间复杂度是指（ ）。A. 算法程序的长度B. 算法程序中的指令条数C. 算法程序所占的存储空间D. 算法执行过程中的所需要的存储空间一、算法4、算法效率衡量方法与准则 :时间复杂度：Windows程序设计中，指执行时间的长短。空间复杂度：指存储空间的大小。 一、算法5、算法与数据结构的关系:计算机科学家沃斯（计算机科学家沃斯（N.Wi

4、rth）提出的）提出的:“算法算法+数据结构数据结构=程序程序” 一、算法 计算机内的数值运算依靠方程式，而计算机内的数值运算依靠方程式，而非数值运算则要依靠数据结构。 同样的数据对象，用不同的数据结构来表示，同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。运算效率可能有明显的差异。算法算法数据结构概述数据结构概述线性结构线性结构栈和队列栈和队列数组数组树树图图第第2章章 数据结构数据结构 特性相同的数据元素构成的集合中，如果在数据元素之间存在一种或多种特定的关系，则称之为数据结构 。 Data_Structure =（D，R） 其中，其中，D是数据元素的有限集，是数据元素的

5、有限集，R是是D上关系的有上关系的有限集。限集。二、数据结构概述例1 线性数据结构 =（D，R） D = 1，2，3，4，5，6，7，8，9，10 R = ，二、数据结构概述例2 图形数据结构 =（D，R）D = 1，2，3，4，5，6，7，8，9R = ，二、数据结构概述 例3 树形结构 =（D，R）D = a，b，c，d，e，f，g，h，i，j，k，lR = ，二、数据结构概述四类基本的数据结构 集合结构。各元素间没有直接的关联。 线性结构。该结构的数据元素之间存在着一对一的关系。 树型结构。该结构的数据元素之间存在着一对多的关系。 图形结构。该结构的数据元素之间存在着多对多的关系，也称作

6、网状结构。二、数据结构概述不同联系不同联系系主任负责系11班级包含学生1N产品组成零件MN一对一联系一对多联系多对多联系（1）Data_Structure=(D,S)，其中，其中， D= 01，02，03，04，05 S= （2） S=(D, R) D= a, b, c, d, e, f R= , , , , 解解: 上述表达式可用图形表示为：上述表达式可用图形表示为：aebcfd习题：将下述表达式用图形的形式表示出来集合结构线性结构（3） Data_Structure=（D，S），其中，），其中， D= 01，02，03，04，05 ，06，07 S=（01，02），（），（01，03），（

7、），（01，04），（），（02，05），（），（02，06），（），（03，07） （4）d1d2d3d4d501020304050607树形结构图状结构逻辑结构可细分为4类：集合结构；线性结构；树形结构；图状结构集合结构；线性结构；树形结构；图状结构一对一关系一对一关系一对多关系一对多关系多对多关系多对多关系非线性非线性结构结构数据结构的分类按数据结构的性质划分 数据的逻辑结构数据元素之间的逻辑关系 （设计算法 数学模型） 数据的物理结构数据结构在计算机中的映像 （存储结构，算法的实现）按数据结构的操作来划分 静态结构操作后数据的结构特征保持不变（如数组）。 半静态结构操作后数据的结构特性

8、只允许很小变迁（如栈、队列）。动态结构操作后，数据的结构特性变化比较灵活，可随机地重新组织结构（如指针）。二、数据结构概述下面叙述正确的是（ ）。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上3种描述都不对二、数据结构概述按数据结构在计算机内的存储方式来划分 顺序存储结构借助元素在存储器的相对位置来表示数据元素之间的逻辑关系。 链式存储结构借助指示元素存储地址的指针表示数据元素之间的逻辑关系 索引存储结构在存储结点的同时，还建立附加的索引表，索引表中的每一项称为索引项，形

9、式为：关键字，地址。 散列存储结构根据结点的关键字直接计算出该结点的存储地址。说明：四种存储方法可结合起来对数据结构进行存储映像。二、数据结构概述算法算法数据结构概述数据结构概述线性结构线性结构栈和队列栈和队列数组数组树树图图第第2章章 数据结构数据结构线性表线性表线性表的定义线性表的定义 线性表线性表是是n(n=0)个数据元素的个数据元素的有限序列有限序列，表中，表中各个元素具有相同的属性。各个元素具有相同的属性。 记做：记做：(a1,a2,.ai-1,ai,ai+1,an-1,an ) 其中，其中，ai-1称为称为ai 的的直接前趋元素直接前趋元素，ai+1是是ai的的直直接后继元素接后继

10、元素 线性表的长度：线性表的长度：表中的元素个数表中的元素个数 n 三、线性结构 数据处理的最小单位是（ ）。 A. 数据 B. 数据元素 C. 数据项 D. 数据结构思考：补充补充数据项数据项数据项，是数据的最小单位，数据项定义的内容包括： 名称、编号（I）、别名、简述 类型、长度 取值范围 item数据项定义举例数据项定义举例数据项名：年级数据项名：年级别名：别名：取值及含义：取值及含义： freshmen，一年级，一年级 sophomore，二年级，二年级 junior，三年级，三年级 senior，四年级，四年级注释：注释：F，M，J，S可分别用可分别用1，2，3，4代替代替记录线性表

11、的顺序表示和实现线性表的顺序表示和实现 顺序表顺序表线性表的线性表的顺序存储表示表示顺序表，随机存取三、线性结构线性表的链式表示和实现线性表的链式表示和实现 单链表单链表线性表的线性表的链式存储表示表示 数据域（数据域（data）和指针域（指针域（next） 三、线性结构结点：数据元素的存储映象数据元素的存储映象数据域数据域指针域指针域链表：n n个结点链接成起来形成一个链表，即为线性表的个结点链接成起来形成一个链表，即为线性表的 链式存储结构。链式存储结构。a1a2ai-1aian指针域为空指针域为空数据元素数据元素直接后继位置直接后继位置头结点头结点LL 数据结构是讨论非数值类问题的对象描

12、述、信息组织方法及其相应的操作 设有一个电话号码薄，有N个人的姓名和电话号码。要求设计一个程序，按人名查找号码，若不存在则给出不存在的信息。三、线性结构三、线性结构顺序表的表示：顺序表的表示：顺序存储定义：把逻辑上相邻的元素存储在物理 位置上相邻的存储单元中。采用顺序存储结构存储的线性表采用顺序存储结构存储的线性表简言之：逻辑相邻，物理也相邻顺序存储方法：顺序存储方法：用一组用一组地址连续地址连续的存储单元依次的存储单元依次 存放线性表的数据元素。存放线性表的数据元素。线性表的顺序表示和实现线性表的顺序表示和实现线性表顺序存储结构的特点线性表顺序存储结构的特点1、逻辑上相邻的物理元素，其物理位

13、置上也相邻 2、若已知线性表中第1个元素的存储位置，则线性表中任意一个元素的位置都可由公式计算得出。 即，线性表的顺序存储结构是一种随机存取的存储结构。例：例：一个一维数组一个一维数组M，下标范围是，下标范围是0到到9，每个数组元素，每个数组元素用用相邻的的5个字节存储。存储器按字节编址，设存储数个字节存储。存储器按字节编址，设存储数组元素组元素M0的第一个字节的地址是的第一个字节的地址是98，则，则M3的第一个的第一个字节的地址是字节的地址是 。113 非数值计算问题 例1.2 田径赛的时间安排问题： 设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）。要求设

14、计比赛日程表，使得在尽可能短的时间内完成比赛。姓名姓名项目项目1项目项目2项目项目3丁一丁一跳高跳高跳远跳远100米米马二马二标枪标枪铅球铅球张三张三标枪标枪100米米200米米李四李四铅球铅球200米米跳高跳高王五王五跳远跳远200米米三、线性结构（1）设用如下六个不同的编码代表不同的项目： 跳高跳高 跳远跳远 标枪标枪 铅球铅球 100米米 200米米 A B C D E F姓名姓名项目项目1项目项目2项目项目3丁一丁一 A B E马二马二 C D 张三张三 C E F李四李四 D F A王五王五 B F （2）用顶点（圆圈）代表比赛项目 不能同时进行比赛的项目之间连上一条边。不能同时进行

15、比赛的项目之间连上一条边。比赛比赛时间时间比赛比赛项目项目1A，C2B，D3E4F2、线性表、线性表顺序存储结构的特点顺序存储结构的特点：逻辑相邻，物理相邻3、优点：、优点：可以可以随机存取表中的任何一个元素表中的任何一个元素4、缺点：、缺点：在插入、删除时，需要移动大量元素在插入、删除时，需要移动大量元素1、线性表的定义、线性表的定义 L=（a1，a2，an）其中，其中，n n是线性表的长度。当是线性表的长度。当n n0 0时，时，L L是一个空表是一个空表 小结：ABCD顺序存储结构顺序存储结构ABCD链式存储结构链式存储结构L=（A, B, C, D）用一组任意的存储单元存储线性表的元素

16、逻辑相邻，物理不一定相邻ai除表示本身信除表示本身信息之外，还要表息之外，还要表示其直接后继的示其直接后继的地址地址线性表的链式表示和实现线性表的链式表示和实现例：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：头指针是指向链表中第一头指针是指向链表中第一个结点的指针，因此关键是要个结点的指针，因此关键是要寻找第一个结点的地址。寻找第一个结点的地址。

17、7ZHAOH31称：头指针称：头指针H的值是的值是31答：X= Y= Z= , 首址= 末址= 。例：现有一个有5个元素的线性表 L=23，17，47，05， 31，若它以链式结构存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。问：其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？100100119119104104108108116116112112116NULL(0)100108112 线性表中结点间的关系是 的。一对一 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： A

18、. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构【答案】C 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。 A. 110 B. 108 C. 100 D. 120【答案】B三、线性结构 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以【答案】D三、线性结构已知：已知：线性表线性表A A和和B B，分别由，分别由单链表单链表LaLa和和LbLb存储，其中数据存储，其中数据 元素按值元素按值非递减有序排列非递减有序排列（即已经有序）；

19、（即已经有序）；例：例：两个链表的归并两个链表的归并重点是链表重点是链表要求：要求：将将A A和和B B归并为一个新的线性表归并为一个新的线性表C C , C , C的数据元素仍按的数据元素仍按 值非递减排列。设线性表值非递减排列。设线性表C C由单链表由单链表 Lc Lc 存储。存储。假设：假设：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）预测：预测：合并后的合并后的C C = =（2, 3, 5, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，1111）线性表的链式表示和实现（应用举例）链表示意图：合并

20、算法设计：算法设计：算法主要包括算法主要包括搜索、比较、插入搜索、比较、插入三个操作：三个操作：搜索：搜索：需要设立需要设立三个指针三个指针来指向来指向La 、Lb和和Lc c链表；链表；比较：比较：比较比较La a和和Lb b表中结点数据的大小；表中结点数据的大小；插入：插入：将将La a和和Lb b表表中数据中数据较小的结点插入新链表较小的结点插入新链表Lc c 。3 5 8 11 LaLb2 6 8 11 9 Lc 2 3 5 6 8 8 9 11 11线性表的链式表示和实现PcPa、Pb用于搜索用于搜索La和和Lb，Pc指向新链表指向新链表Lc的当前结点。的当前结点。链表链表Lc存储在

21、新开辟的空间中存储在新开辟的空间中，归并过程示意如下：，归并过程示意如下：Lb2 6 8 119 3 5 8 11 LaLc 2 3 5 Pa6 Pb8 PcPbPcPaPaPcPcPbPcPaPb线性表的链式表示和实现线性表线性表顺序存储顺序存储特征：特征：逻辑相邻，物理也相邻；逻辑相邻，物理也相邻；优点：优点：随机存取结构随机存取结构缺点：缺点：插入、删除需要移动大量元素插入、删除需要移动大量元素改进方案：改进方案：链式存储结构链式存储结构逻辑结构：逻辑结构：“一对一一对一” 或或 “1:11:1”存储结构：存储结构：顺序存储、链式存储顺序存储、链式存储运运 算：算：插入、删除插入、删除小

22、结：三、线性结构 在线性表的在线性表的第第i i个位置前个位置前插入一个元素的示插入一个元素的示意图如下：意图如下：1213212428304277121321242830427712345678123456789插入插入i=5i=5三、线性结构123456789121321242528304277123456781213212428304277i=5删除顺序表中删除顺序表中第第i i个个元素的示意图如下：元素的示意图如下：三、线性结构算法算法数据结构概述数据结构概述线性结构线性结构栈和队列栈和队列数组数组树树图图第第2章章 数据结构数据结构 栈 栈的应用举例 队列四、栈和队列栈的定义 栈（S

23、tack）是限定只能在表的一端进行插入和删除操作的线性表，又称限定性线性表结构。2. 栈的结构特点和操作 栈顶（Top）、栈底（Bottom）、先入后出（LIFO） 栈堆栈结构示意图 栈栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶top；表头称为栈底bottom；例：栈S=（a1，a2，an-1 ，an）栈顶栈底入栈：在栈顶插入一个元素的操作；出栈：从栈顶删除一个元素的操作；基本操作：在栈顶进行插入、删除、栈的初始化、 判空及取栈顶元素 栈basebase为栈底指针，始终指向栈底，base=NULL表示栈结构不存在；top为栈顶指针，初值指向栈底，top入栈：插入新的栈顶元素，指针

24、top加1-先插入后加1A即top=base，表示栈空。BCD出栈：指针top减1，删除栈顶元素-先减1后删除非空栈的栈顶指针top始终指向栈顶元素的下一个位置EFtoptoptop栈满栈满top-base=stacksizebasetopABCDEFtoptoptoptoptoptop栈空栈空入栈入栈PUSH(s,x):stop+=x;出栈出栈 POP(s,x):x=s-top;例：一个栈的输入序列为1，2，3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？可以通过穷举所有可能性来求解： 1入1出， 2入2出，3入3出， 即123； 1入1出， 2、3入，3、2出， 即132； 1、

25、2入，2出， 3入3出， 即231； 1、2入，2、1出，3入3出， 即213； 1、2、3入，3、2、1出， 即321；合计有5种可能性。 栈例：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是： A. a，b，c，d B. c，d，a，b C. b，c，d，a D. a，c，d，b若输入序列是若输入序列是 ,PjPkPi (PjPkPi) ，一定不存在这样的输出序列一定不存在这样的输出序列 ,PiPjPk 即对于输入序列即对于输入序列1，2，3，不存在输出序列，不存在输出序列3，1，2 栈队列的定义 队列（Queue）是限定只能在表的一端进行插入，在表的另一端进行删除操

26、作的线性表。2. 队列的结构特点和操作 队列头（front）、队列尾（rear），先入先出（FIFO） 队列队列是只允许在表的一端进行插入，另一端进行删除。队列是只允许在表的一端进行插入，另一端进行删除。允许插入的一端称为队尾（rear）；允许删除的一端称为队头（front）；特点：特点：先进先出先进先出/FIFOa1 a2 a3 an队头队尾入队列出队列 队列 串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成 字符串，由零个或多个字符组成的有限序列。 S“a0a1.an-1”串的长度：n空串：n=0，Null String子串与主串，子串的位置（从0开始）串的比较：最大相等前缀

27、子序列补充串 下列数据结构中，按先进后出原则组织数据的是（ ）A线性链表B栈C循环链表D顺序表【答案】B四、栈和队列 下列关于栈的叙述中正确的是（ ） A在栈中只能插入数据B在栈中只能删除数据C栈是先进先出的线性表D栈是先进后出的线性表【答案】D四、栈和队列 下列关于队列的叙述中正确的是（ ） A在队列中只能插入数据B在队列中只能删除数据C队列是先进先出的线性表D队列是先进后出的线性表【答案】C四、栈和队列 下列叙述中，正确的是（ ）A线性链表中的各元素在存储空间中的位置必须是连续的B线性链表中的表头元素一定存储在其他元素的前面C线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面D线性链表中的各