大学数据结构

1、1第一章数据结构与算法n1.1算法n1.2数据结构的基本概念n1.3线性表及其顺序存储结构n1.4栈和队列n1.5线性链表n1.6树与二叉树n1.7查找技术n1.8排序技术21.1算法n1.1.1 算法的基本概念n算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等于计算机方法，程序的编制不可能优于算法的设计。1、算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。31.1算法n特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不允许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完

2、，取能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。41.1算法n2、算法的基本要素：n一是对数据对象的运算和操作；n二是算法的控制结构。n基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。n一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。51.1算法n1.1.2算法的复杂度n 算法时间复杂度和算法空间复杂度。61.1算法n1.算法的时间复杂度n算法时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即n 算法的工作量=f(n)最坏情况复杂性：是指在规模为n时，算法

3、所执行的基本运算的最大次数。（例：O（n2）)常见的时间复杂度，按数量级比较排列关系为：)2()()()log()(log) 1 (222nkOnOnOnnOnOO71.1算法n2.算法空间复杂度n算法空间复杂度是指执行这个算法所需要的内存空间。n 一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。81.2数据结构的基本概念 n数据结构是指相互有关联的数据元素的集合。n数据结构研究的三个方面：（1）数据集合中和数元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（

4、3）对各种数据结构进行的运算。 n讨论以上问题的主要目的是为了提高数据的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度，二是尽量节省在数据处理过程中所占用的计算机存储空间。9n数据的逻辑结构包含：n（1）表示数据元素的信息；n（2）表示各数据元素之间的前后件关系。n数据的逻辑结构分为：线性结构与非线性结构n线性结构条件：n（1）有且只有一个根结点；n（2）每一个结点最多有一个前件，也最多有一个后件。n非线性结构：不满足线性结构条件的数据结构。数据的逻辑结构数据的逻辑结构10n数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 数据的存储

5、结构有顺序、链接、索引等。数据的存储结构数据的存储结构111.3 线性表及其存储结构n1.3.1 线性表的基本概念线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。学生情登记表姓名学号性别年龄健康状况王强800356男19良好刘建平800357男20一般赵军800361女19良好葛文华800367男21较差12n在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。n非空线性表的结构特征：n（1）有且只有一个根结点a1，它无前件；n（2）有且只有一个终端结点an，它无后件；n（3）除根结点与终端结点外，其他所有结点有且

6、只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。13n线性表的顺序存储结构具有以下两个基本特点：n（1）线性表中所有元素的所占的存储空间是连续的；n（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。线性表的顺序存储结构14顺序表的基础要点n1、线性表是具有、线性表是具有n个数据元素的有限序列。个数据元素的有限序列。n2、线性表的顺序存储结构具有三个弱点：线性表的顺序存储结构具有三个弱点：n在插入和删除时，需移动大量元素在插入

7、和删除时，需移动大量元素n由于难以估计，必须预先分配较大的空间由于难以估计，必须预先分配较大的空间n表的容量难以扩充表的容量难以扩充 (如何解决？）如何解决？）n3、顺序存储结构通过元素的相对存储地址来表示元素之间的关系、顺序存储结构通过元素的相对存储地址来表示元素之间的关系n4、线性表顺序存储的优点是可随机存取元素。、线性表顺序存储的优点是可随机存取元素。n5、顺序表中逻辑上相邻的元素的物理位置必定紧邻。、顺序表中逻辑上相邻的元素的物理位置必定紧邻。 n6、顺序表是一种随机存取的存储结构。、顺序表是一种随机存取的存储结构。n7、在顺序表中插入或删除一个元素时，需要平均移动表的一半元、在顺序表

8、中插入或删除一个元素时，需要平均移动表的一半元素，具有移动的元素个数与该元素的位置有关。素，具有移动的元素个数与该元素的位置有关。n8、在长度为、在长度为n的顺序表中插入一个元素的时间复杂度为的顺序表中插入一个元素的时间复杂度为O(n)，删除，删除一个元素的时间复杂度为一个元素的时间复杂度为O(n)。15n线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示数据元素间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。这个信息称为指针(poin

9、ter)或链(link)。这两部分组成了链表中的结点结构：n datalink指针域，用来存放结点指针域，用来存放结点的直接后继的地址的直接后继的地址数据域，用来数据域，用来存放结点的值存放结点的值1.4 线性表的链式存储结构-链表16n n术语n表示每个数据元素的两部分信息组合在一起被称为结点；n其中表示数据元素内容的部分被称为数据域（data）；n表示直接后继元素存储地址的部分被称为指针或指针域（next）。n headd cba单联表结构示意图单联表结构示意图datalink17n数据结构中的每一个结点对应于一个存储单元，这种存储单元称为存储结点，简称结点。n结点由两部分组成：（1）用于

10、存储数据元素值，称为数据域；（2）用于存放指针，称为指针域，用于指向前一个或后一个结点。n在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。n链式存储方式即可用于表示线性结构，也可用于表示非线性结构。18n链式存储结构的特点n（1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；n（2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。19n循环

11、链表(circular linked list)n循环链表是表中最后一个结点的指针指向头结点，使链表构成环状n特点：从表中任一结点出发均可找到表中其他结点，提高查找效率hh空表20例题讲解21n链表不具有的特点是A) 不必事先估计存储空间 B) 可随机访问任一元素C) 插入删除不需要移动元素D) 所需空间与线性表长度成正比n用链表表示线性表的优点是 A) 便于随机存取 B) 花费的存储空间较顺序存储少 C) 便于插入和删除操作 D) 数据元素的物理顺序与逻辑顺序相同n长度为n的顺序存储线性表中，当在任何位置上插入一个元素概率都相等时，插入一个元素所需移动元素的平均个数为 【1】 。22n线性表

12、L=(a1,a2,a3,ai，an)，下列说法正确的是A) 每个元素都有一个直接前件和直接后件B) 线性表中至少要有一个元素C) 表中诸元素的排列顺序必须是由小到大或由大到小D) 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 n在单链表中，增加头结点的目的是 A) 方便运算的实现 B) 使单链表至少有一个结点 C) 标识表结点中首结点的位置 D) 说明单链表是线性表的链式存储实现23n循环链表的主要优点是 A) 不再需要头指针了 B) 从表中任一结点出发都能访问到整个链表 C) 在进行插入、删除运算时，能更好保证链表不断开 D) 已知某个结点的位置能容易的找到

13、它的直接前件n线性表的顺序存储结构和线性表的链式存储结构分别是 A) 顺序存取的存储结构、顺序存取的存储结构 B) 随机存取的存储结构、顺序存取的存储结构 C) 随机存取的存储结构、随机存取的存储结构 D) 任意存取的存储结构、任意存取的存储结构 24n下列对于线性链表的描述中正确的是下列对于线性链表的描述中正确的是_。A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的n下列叙述中正确的是下列叙述中正确的是_。A）一个逻辑数据结构

14、只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率25栈n是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的表尾端进行。如下所示：nn 进行插入和删除的表尾端是浮动端，通常被称为栈顶， an 为栈顶元素， 并用一个“栈顶指针”指示；而表头端是固定端，通常被称为栈底， a1 为栈底元素，。我们经常将栈用下图的形式描述：a1, a2, a3, ., an 插入和删除端插入和删除端26an.a2a1栈 顶 to

15、p27结论：结论：后进先出后进先出（Last In First Out），简），简称为称为LIFO线性表。线性表。 举例举例1：家里吃饭的碗，通常在洗干净后一个：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。最后拿出最下面的那只碗。 举例举例2：在建筑工地上，使用的砖块从底：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上往上一层一层地码放，在使用时，将从最上面一层一层地拿取。面一层一层地拿取。28栈的基本运算n栈的

16、基本运算：n（1）插入元素称为入栈运算；n（2）删除元素称为退栈运算；n（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化29n 栈顶指针和栈中元素之间的关系栈顶指针和栈中元素之间的关系base A B C D Etoptop 指向栈顶元素栈的顺序存储及运算30栈的链式存储n若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图所示。n由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表

17、的头指针作为栈顶指针。31队列及其基本运算n队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。n例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。32n下图是队列的示意图：nn a1a2annnn插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端被称为队头，用一个“队头指针”指示。n 结论：先进先出（First In First Out），

18、简称为FIFO线性表。 出队入队33n队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。Rear指针指向队尾，front指针指向队头。n队列是“先进行出”（FIFO）或“后进后出”（LILO）的线性表。n队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。队列基本运算34n队列的顺序存储结构n实现：用一维数组实现sqMfront=-1rear=-1123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元

19、素；front指示队头元素前一位置初值front=rear=-1空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront35n存在问题n设数组维数为M，则：n当front=-1,rear=M-1时，再有元素入队发生溢出真溢出n当front-1,rear=M-1时，再有元素入队发生溢出假溢出n解决方案：循环队列（掌握计算队列元素个数的方法）n基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-11frontr

20、ear.n实现：利用“模”运算n入队： rear=(rear+1)%M; sqrear=x;n出队： front=(front+1)%M; x=sqfront;n队满、队空判定条件n 解决方案：n 1.另外设一个标志以区别队空、队满n 2.少用一个元素空间：n 队空：front=rearn 队满：(rear+1)%M=frontn 36n队列的链式存储结构n 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由一个头指针和一个尾指针唯一确定。添加头节点。和顺序队列类

21、似，我们也是将这两个指针封装在一起，frontrear37例题讲解38n按照按照“后进先出后进先出”原则组织数据的数据结构是原则组织数据的数据结构是_。A）队列 B）栈 C）双向链表 D）二叉树n下列叙述中正确的是下列叙述中正确的是_。A）循环队列有队头和队尾两个指针，因此，循环队列是非线性结构B）在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况C）在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D）循环队列中元素的个数是由队头指针和队尾指针共同决定39n设某循环队列的容量为50，头指针Front=5 (指向队头元素的前一位置)，尾指针rear=29（指向队尾元素），则

22、该循环队列中共有 个元素。n设某循环队列的容量为50，如果头指针Front45（指向队头元素的前一位置），尾指针rear=10 (指向队尾元素) 则该循环队列中共有 个元素。 n当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为 。4016 树与二叉树 n树是一种简单的非线性结构，所有元素之间具有明显的层次特性。n 在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根。每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。n 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最

23、大的度称为树的度。树的最大层次称为树的深度。41(C)是有13个结点的树，其中A是根，其余结点分成3个子集： T T1 1 、T T2 2 、T T3 3 。都是根A的子树，且本身也是一棵树。例如： T T1 1 其根为B，两棵子树为 T T11 11 = F T T1212 = E, K, L ， T T1212 又是一棵子树，树根为F，K 和 L是E的两个互不相交的子集。442AK L ME F G H I J B C DA(a)(b)(c)431.6.2二叉树及其基本性质n二叉树的特点：n（1）非空二叉树只有一个根结点；n（2）每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。

24、44G HD E FB CA45二叉树的基本性质： n（1）在二叉树的第k层上，最多有2k-1(k1)个结点；n（2）深度为m的二叉树最多有2m-1个结点；n（3）度为0的结点（即叶子结点）总是比度为2的结点多一个；n（4）具有n个结点的二叉树，其深度至少为log2n+1,其中log2n表示取log2n的整数部分；n（5）具有n个结点的完全二叉树的深度为log2n+1；46n满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。n 完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。满二叉树

25、和完全二叉树 47 8 9 10 11 12 13 14 154 5 6 72 3148 8 9 10 11 12 4 5 6 72 31 7 8 94 5 6 2 31 4 5 62 31一棵满二叉树一定是一棵完全二叉树，而一棵完全二叉树不一定是满二叉树。491.6.3二叉树的存储结构二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。n1. 顺序存储结构n这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元依次自上而下、自左至右存储完全二叉树的结点元素，即 ：按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。50abcdefghijkl完

26、全二叉树ABCDEFGHIJKL 1 2 3 4 5 6 7 8 9 10 11 12512 链式存储结构链式存储结构 在在顺序存储顺序存储结构中，利用结构中，利用编号表示编号表示元素的位置及元素之间元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号位置用特定的符号填补填补，若空缺结点较多，势必造成空间利，若空缺结点较多，势必造成空间利用率的用率的下降下降。在这种情况下，就应该考虑使用链式存储结构。在这种情况下，就应该考虑使用链式存储结构。 常见的二叉树结点结构如下所示：常见的二叉树结点结构如下所示：Lc

27、hilditemRchild521.6.4二叉树的遍历n所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。n二叉树的遍历方式分为：前序遍历、中序遍历、后序遍历53n（1）先序遍历n若二叉树为空，则结束遍历操作；否则n访问根结点；n先序遍历左子树；n先序遍历右子树。n（2）中序遍历n若二叉树为空，则结束遍历操作；否则n中序遍历左子树；n访问根结点；n中序遍历右子树。54n（3）后序遍历n若二叉树为空，则结束遍历操作；否则n后序遍历左子树；n后序遍历右子树；n访问根结点。n下面是一棵二叉树及其经过三种遍历得到的相应序列。55G HB CAD E F先序序列：先序序列：ABDGCEFH中序序列：中序序列：DGBAECHF后序序列：后序序列：GDBEHFCA5617 查找技术 n1.7.1顺序查找顺序查找是一种最简单的查找方法。顺序查找的使用情况：n（1）线性表为无序表；n（2）表采用链式存储结构。57n1.7.2二分法查找n二分法查找只适用于顺序存储的有序表。n对