大学计算机基础-第7章 数据结构课件

第7章数据结构7.1数据结构概念及定义7.2线性表7.3栈和队列7.4树7.5排序7.6查找技术数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。线性表的定义；线性表的顺序存储结构及其插入与删除运算。栈和队列的定义；栈和队列的顺序存储结构及其基本运算。线性单链表、双向链表与循环链表的结构及其基本运算。树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。二级大纲之二--------数据结构线性表的基本知识（定义、结构）栈和队列的基本知识（定义、结构）树的基本概念（定义、相关术语）二叉树（定义、性质、遍历）常用排序算法与二分查找法的时间复杂度本章重点内容7.1.1数据结构概述数据（data）-------是指能够输入到计算机中，并能被计算机存储、识别和处理的符号集合。数据结构（DataStructure）-------研究数据的特性以及数据之间存在的关系；是计算机存储、组织数据的方式。如：学生之间、同事之间总会存在一定的联系。什么是数据结构?逻辑结构------如何表示这些数据元素的关系（与计算机无关）存储结构------怎样在计算机中存储数据元素运算------对每种逻辑结构进行相应的处理7.1.1数据结构概述数据结构的研究内容7.1.2数据元素和数据项数据元素（DataElement）------是数据的基本单位，具有完整明确的实际意义，也称元素、节点、顶点、记录。数据项（DataItem）------是组成数据元素的最小单位，也称为字段或域。如：学生通讯录中，一个学生是一个数据元素，而姓名、电话号码、住址等是数据元素的3个数据项。数据元素和数据项7.1.3数据对象和数据类型数据对象（DataObject）------是性质相同的数据元素组成的集合，是数据的一个子集。如：整数对象集、实数对象集。数据类型（DataType）------是一个值的集合与在这些值上定义的一组操作的总称。如：整型、字符型、逻辑型数据对象和数据类型7.4.5数据的存储结构

什么是数据的存储结构?定义:数据的存储结构是数据的逻辑结构在计算机中的表示和实现，故又称数据的“物理结构”。存储结构包含的内容数据结构举例学号姓名语文数学化学平均成绩2010001向恩立829083852010002赵军928599922010003刘冰80757978….….…..….….…..逻辑结构：用二维表表示数据间的关系。表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各科成绩及平均成绩等数据项组成。7.1.6数据结构的定义7.1.7线性结构与非线性结构线性结构

数据元素有唯一前趋和唯一后继（第一个没有前趋，最后一个没有后继。如：1对1是线性结构非线性结构

非线性结构的其它数据结构。如：1对多(树）、多对多（图）、无关系（集合）非线性结构数据结构的分类（分为两大类）7.2线性表

7.2.1线性表的基本概念7.2.2线性表的逻辑结构特征7.2.3线性表的顺序存储结构7.2.4线性表的基本运算7.2.5线性表的链式存储7.2.6基本运算在链表上的实现7.2.7其它链表7.2线性表

定义：

线性表是n（n≥1）个数据元素a1，a2，…，an组成的有限序列，其数据元素按“一个接一个排列”的方式进行组织。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。举例（2，4，6，8，10）是一个线性表，数据元素类型是整型，数据元素的取值为偶数；（A，B，C，D，E，F）也是一个线性表，数据元素类型是字符型，数据元素的取值为大写英文字母；什么是线性表？7.2.2线性表的逻辑结构特点

有且仅有一个开始元素a1，没有直接前驱，仅只有一个直接后继a1；有且仅有一个终端元素an，没有直接后继，仅只有一个直接前驱an-1；其他元素ai（2≤i≤n−1）都有且仅有一个直接前驱ai−1和一个直接后继ai+1；逻辑结构主要特点7.2.3线性表的顺序存储结构

定义：把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元中，用这种方法存储的线性表简称为顺序表。存储特点：所有元素结点的存储空间是连续的。数据元素在存储空间中是按逻辑顺序依次存放的。什么是顺序存储结构？7.2.4线性表的基本运算

举例：一个长度为8的线性表顺序存储在长度为10的存储空间中，现在要求删除线性表中的第1个元素和第7个元素，如图所示。线性表的顺序存储优缺点结构比较简单，适合小线性表（元素少）或者其中元素不常变动的线性表。对于大的线性表，特别是元素变动频繁的大线性表不宜采用顺序存储结构，因为插入与删除的效率比较低。7.2.4线性表的基本运算Data为数据域，用来存放元素本身的信息，类型由具体问题而定；Next为指针域，用来存放下一个结点的地址，即存储一个指针，该指针指向本元素的直接后继元素所在的结点。DataNext7.2.5线性表的链式存储

在单链表中结点的结构描述7.2.6链表的基本运算

链表的插入运算方法：该算法要求先找到第i−1个结点，故其时间频度为n，时间复杂度为O(n)。但在插入元素时不需移动元素，只需修改指针即可。

7.2.7其他链表将单链表最后一个结点的指针改为指向链表中的头结点，就使得整个链表构成一个环，又没有增加额外的存储空间，这种链表被称为单循环链表。循环链表7.3栈和队列

7.3.1栈的定义7.3.2队列7.3.1栈的定义

定义：-------栈（Stack）又叫堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。什么是栈？栈的基本运算入栈运算出栈运算读栈顶元素【例7.9】对于一个栈，给出输入项a,b,c。如果输入项序列由a,b,c组成，则可能产生的序列有哪些？7.3.1栈的定义

7.3.2队列

定义：也是一种受限的线性表。若限定线性表的插入只能在表尾位置进行，而删除只能在表头进行，则称这种线性表为队列。什么是队列？与栈不同的是，队列是先进先出（FirstInFirstOut，FIFO）的线性表，而栈是后进先出（LastInFirstOut，LIFO）的线性表。队列的顺序存储结构队列的顺序存储结构也用一维数组来模拟实现。队列的插入在队尾进行，删除却在队头进行，所以，必须由两个变量分别记录队头、队尾在数组中的位置，分别称为队头指针和队尾指针。

空顺序队列

非空顺序队列

7.3.2队列

队列的基本运算出队操作：即删除队列的队头元素。入队操作：在队列的队尾插入结点，将Rear指针加1，将数据存入Rear指针指向的位置。7.3.2队列

7.4树7.4.1树的定义与相关术语7.4.2二叉树的定义与基本操作7.4.3二叉树的性质7.4.4二叉树的存储结构7.4.5二叉树的遍历7.4.1树的定义与相关术语树是n(n≥0)个结点的有限集合T。当n=0时，称为空树；当n＞0时，该集合满足如下条件：其中必有一个称为根（Root）的特定结点，它没有直接前驱，但有零个或多个直接后继。其余n-1个结点可以划分成m（m>0）个互不相交的有限集T1，T2，T3，…Tm，其中Ti又是一棵树，称为根（Root）的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。什么是树？树的相关术语结点：包含一个数据元素及若干指向其他结点的分支信息。结点的度：一个结点的子树的个数称为此结点的度。叶子结点：无后继的结点，即度为0的结点，也称为终端结点。树结构如右图所示：7.4.1树的定义与相关术语树的相关术语树的度：树中所有结点的度的最大值。孩子结点：一个结点的直接后继称为该结点的孩子结点。在图中，B、C、D是A的孩子结点。双亲结点：一个结点的直接前驱称为该结点的双亲结点。在图中，A是B、C、D的双亲结点。兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。在图中，B、C、D互为兄弟结点。结点的层次：从根结点开始定义，根结点的层次为l，根的直接后继的层次为2，依此类推。7.4.1树的定义与相关术语树的相关术语树的深度：树中所有结点的层次的最大值。在图中，树的深度为4。祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图中，L的祖先结点是E、B、A。子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。在图，B结点的子孙结点是E、F、K、L。7.4.1树的定义与相关术语树的相关术语有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。森林：m(m＞0)棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。7.4.1树的定义与相关术语7.4.2二叉树的定义与基本操作

满足以下两个条件的树形结构叫做二叉树。每个结点的度都不大于2。有序树每个结点的孩子结点次序不能任意颠倒二叉树是有序树。什么是二叉树？二叉树的基本操作将BinaryTree初始化为空二叉树创建一棵非空二叉树BinaryTree销毁二叉树BinaryTree判断二叉树是否为空求根结点求双亲求左孩子求右孩子遍历操作：按某个次序依次访问二叉树中每个结点一次且仅一次。7.4.2二叉树的定义与基本操作

7.4.3二叉树的性质

性质1：在二叉树的第i层上结点数最多为2i−1。性质2：深度为k的二叉树至多有2k−1个结点（k≥1）。性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。二叉树的重要性质（五个)2134589111067121314(b)完全二叉树满二叉树定义：深度为k且有2k−1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数（2i-1)。如图所示的二叉树即为一棵满二叉树。7.4.3二叉树的性质

定义：深度为k，结点数为n的二叉树，如果其结点1…n的位置序号分别与满二叉树的结点1…n的位置序号一一对应，则为完全二叉树。如右图所示即为满二叉树。7.4.3二叉树的性质

完全二叉树性质4：具有n个结点的完全二叉树的深度为性质4：具有n个结点的完全二叉树的深度为性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有”如i=1，则序号为i的结点是根结点，无双亲结点；如i>1，则序号为i的结点的双亲结点序号为:如2*i＞n，则序号为i的结点无左孩子；如2*i≤n，则序号为i的结点的左孩子结点的序号为2*i。如2*i+1＞n，则序号为i的结点无右孩子；如2*i+1≤n，则序号为i的结点的右孩子结点的序号为2*i+1。

。7.4.3二叉树的性质

二叉树的重要性质（五个)7.4.4二叉树的存储结构

顺序存储结构链式存储结构顺序存储结构:是用一组连续的存储单元来存放二叉树的数据元素。如图所示：二叉树的两种存储结构7.4.4二叉树的存储结构

链式存储结构如图所示

二叉树的两种存储结构7.4.5二叉树的遍历

定义：“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。方法：确定一条搜索路径，使得结构中的每个数据元素都出现在这条搜索路径上，才能确保每个数据元素都被访问到。什么是二叉树的遍历？二叉树的三种遍历方法先序遍历（DLR）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作。访问根结点。按先序遍历左子树。按先序遍历右子树。7.4.5二叉树的遍历

二叉树的三种遍历方法中序遍历（LDR）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作。按中序遍历左子树访问根结点按中序遍历右子树7.4.5二叉树的遍历

二叉树的三种遍历方法后序遍历（LRD）操作过程若二叉树为空，则空操作，否则依次执行如下3个操作。按后序遍历左子树按后序遍历右子树访问根结点7.4.5二叉树的遍历

7.5排序

7.5.1排序的基本概念7.5.2排序方法7.5.3插入类排序7.5.4选择类排序7.5.5交换类排序7.5.1排序的基本概念排序（Sorting）是数据处理领域中经常使用的一种重要运算，分为内、外排序。文件放在内存处理的，称为“内排序”；排序过程中不仅使用内存，还使用外存，称为“外排序”。本节着重介绍内排序算法如果待排序的记录集合中有多个排序码相同的记录，经过排序后这些记录的相对次序仍保持不变，这种排序算法称为“稳定”的，否则称为“不稳定”的。排序的基本概念7.5.2排序的方法

插入类排序：直接插入排序，二分法插入排序，希尔排序。选择类排序：直接选择排序，堆排序。交换类排序：起泡排序，快速排序。分配类排序：基数排序。归并类排序。排序方法的分类（五类）排序算法的评价时间复杂度--------时间复杂度是指算法执行所需要的时间，取决于算法中执行数据比较的次数和移动的次数。空间复杂度---------空间复杂度是指算法执行所需要的附加空间的大小。7.5.2排序的方法

7.5.3插入排序基本思想：把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n−1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。直接插入排序的空间复杂度：只需要一个元素的辅助空间，用于元素的位置交换。直接插入排序的时间复杂度：因此，直接插入排序的时间复杂度为O（n2）。直接插入排序基本思想：在插入Ri时（这时R1，R2，…，Ri−1已为有序表），可以不断二分有序表来确定插入位置，通过待插入记录与有序表居中的记录按排序码比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较的子表中只有一个记录时，比较一次便确定了插入位置。空间复杂度：只需要一个元素的辅助空间，用于元素的位置交换。时间复杂度：确定插入位置所进行的折半查找，关键码的比较次数至多为log2(n+1)」次，移动记录的次数和直接插入排序相同，故时间复杂度仍为O(n2)。7.5.3插入排序二分法插入排序7.5.3插入排序基本思想：先选定一个整数增量d1<n，把全部记录分成若干个组，所有记录距离为d1倍数的记录放在同一个组，在各组内进行排序，然后取d2<d1，重复上述分组和排序过程，直到di=1，即所有记录放在一组中排序结束。各组内排序可采用直接插入排序。空间复杂度：只需要一个元素的辅助空间，用于元素的位置交换。时间复杂度：希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。希尔插入排序7.5.4选择排序

基本思想：第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。空间复杂度：只需要一个元素的辅助空间，用于元素的位置交换。时间复杂度：简单选择排序移动记录的次数较少，但关键码的比较次数依然是n(n+1)，所以时间复杂度仍为O(n2)。简单选择排序的7.5.5交换类排序基本思想：对含有n个记录的表，从第一个排序码开始将两两相邻的一对记录排序码进行比较，如果它们的次序不对，就交换它们的位置，直到得到一个排序码最大的记录，并将它放到r[n]；第二趟冒泡对前面n−1个记录的表，再得到一个关键码最大的记录，将它放到r[n−1]；如此执行n−1趟，得到n个记录的有序表。空间复杂度：只需要一个元素的辅助空间，用于元素的位置交换。时间复杂度：冒泡排序算法的时间复杂度为O(n2)。

冒泡排序7.5.5交换类排序

基本思想是通过比较关键码、交换记录，以某个记录为界（该记录称为支点），将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。空间复杂度：快速排序是递归的。存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。时间复杂度：在n个记录的待排序列中，一次划分需要约n次关键码比较，时效为O(n)，若设T(n)为对n个记录的待排序列进行快速排序所需时间。快速排序7.6查找技术7.6