四章节数据结构教程文件

《四章节数据结构教程文件》由会员分享，可在线阅读，更多相关《四章节数据结构教程文件（44页珍藏版）》请在金锄头文库上搜索。

1、第四章 数据结构,主要内容,4.1 基本数据结构与算法 4.2 线性表 4.3 栈和队列 4.4 树和二叉树 4.5 查找 4.6 内部排序,4.1 基本数据结构与算法,4.1.1 数据结构的基本概念,1.数据结构的定义,(1)数据：信息载体，能够被计算机识别、存储和加工处理。可以使数值数据(整数、实数)，也可以是非数值数据(声音、图像等) 。,(2)数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理(又称结点、记录)。,数据项：一个数据元素由若干数据项组成，数据的不可分割的最 小单位。,关键码：其值能唯一确定一个数据元素的数据项。,举例：图书管理系统 数据元素 数据项 关

2、键码 (一本书)书目信息 书目信息每一项 书号(唯一确定一本书),(3)数据对象：具有相同性质的数据元素的集合。数据元素是数据对象类的一个实例。,(4)数据结构：,定义:相互之间存在着一种或多种关系的数据元素的集合。,研究内容:,数据的逻辑结构：各数据元素之间的逻辑关系 数据的存储结构：各数据元素在计算机中的存储关系 对各种数据结构进行的运算：添加，删除，排序等。,2.数据的逻辑结构,四类基本逻辑结构,(1)集合结构：数据元素间的关系是“属于同一个集合” (2)线性结构：数据元素之间存在一个对一个的关系。 (3)树形结构：数据元素之间存在一个对多个的关系。 (4)图形结构：数据元素之间存在多个

3、对多个的关系。,树型结构,线性结构与非线性结构,概念,结点:组成数据结构的数据元素称为一个结点。,前后件关系:,数据元素之间的固有关系可以用前后件关系(前驱与后继关系)描述。 举例：家庭成员辈分关系(父亲、儿子、女儿)，“父亲”是“儿子”和“女儿”的前件， “儿子”和“女儿”是 “父亲”后件。,线性结构,有且只有一个根结点 每个结点最多有一个前件，也最多有一个后件,非线性结构,一个数据结构如果不是线性结构，则称之为非线性结构。数据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件。树型、图形结构属于非线性结构。,3.数据的存储结构,定义：数据的逻辑结构在计算机存储空间中的存放形式。

4、数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。,实现方式：,(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。,顺序存储结构的线性表,线性表(a1, a2, a3, a4),(2)链式存储方式：对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。,链式存储结构的线性表,线性表(a1, a2, a3, a4),链式存储结构的特点,每个结点由两部分组成：一部分存放数据，另一部分存储指向前件或后件结点的指针域。 逻辑上相邻的结点物理上不必相连。 数据运算(插入和删除等)灵活。

5、,(3)索引存储方法和散列存储方法(为了查找方便),4.数据结构的表示,(1)二元关系表示,B=( D, R ),B：数据结构 D：数据元素的集合 R：D上的关系 (反映数据元素前后件关系),家庭成员数据结构 B=( D, R ) D =父亲,儿子,女儿 R =(父亲,儿子),(父亲,女儿),(2)图形表示,D中每个数据元素用标有元素值的方框表示,简称结点。 R中每个二元组,用一条有向线段从前件结点指向后件结点。,根结点：没有前件的结点 叶子结点(终端结点)：没有后件的结点,5.数据的运算,定义：在数据的逻辑结构上定义的操作算法,常见运算：插入、删除、查找、排序和更新等,分类：,加工型运算：运

6、算改变了数据结构的值 引用型运算：不改变值，只查询或求得结构的值。,4.1.2 算法和算法分析,1.算法基本概念,定义：为解决某个特定问题而采取的确定且有限的步骤的一种描述。(解题方案的准确而完整描述),特点(五个)：,有穷性：包含有限个操作步骤，有限时间内完成。 确定性：每一条指令无二义性 可行性：指定操作都可以实现 输入性：一个算法有零个或多个的输入 输出性：一个算法有一个或多个的输出,2.算法基本要素及描述,基本要素：,数据对象的运算和操作 算法的控制结构,算法表示：自然语言，伪代码，流程图,3.算法设计要求,(1)正确性：执行结果应满足预先的功能和性能要求 (2)可读性：层次分明、易读

7、易懂。 (3)健壮性：输入数据非法时，算法能作适当处理 (4) 效率： 有效使用存储空间和较高的时间效率。,4.算法的设计方法,(1)列举法：列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的。,(2)归纳法：列举少量简单而又特殊的情况，分析归纳出一般结论。,(3)递推法：从已知初始条件出发，逐步推出各种中间结果和最后结果。,(4)递归法：解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合 。,(5)减半递推技术：,减少：问题规模减半，而性质不变 递推：重复减半的过程,(6)回溯法：尝试。分析找出解决线索，逐步试探,成功：求得解 失败

8、：逐步回推，换线索再试探。,5.算法复杂度,评价算法标准：算法所占用计算机资源，即时间代价和空间代价。,相关名词：,(1)问题规模：不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于项数。,(2)算法运行时间：大致等于其所有语句执行时间的总和。,(3)语句频度：该语句在算法中重复执行的次数。,算法的时间复杂度：,定义：算法运行从开始到结束所需要的计算工作量。,记作：,T (n)=O( f (n) ),n：问题规模。 T (n) 是n的某个函数。 O：数量级。当问题规模趋向无穷时， T (n)的数量级 称为时间复杂度。,算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入

9、实例的初始状态。 最优算法：随n的增大， T (n)增长较慢的算法。,两种：,平均时间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 最坏时间复杂度：最坏情况下算法的时间复杂度。,算法的空间复杂度：,定义：算法运行从开始到结束所需的存储空间量(耗费的存储空间)。,所需存储空间包括两部分,固定部分：此部分空间与所处理数据的大小和规模无关。 可变部分：此部分空间与处理的数据的大小和规模有关， 即执行算法所需额外空间。,4.2 线性表,4.2.1 线性表的基本概念,定义：具有相同数据类型的n(n0)个数据元素组成的有限序列。最简单、最常用的数据结构。,表示：L=( a1，a2

10、，a3，ai-1，ai ，ai+1，an ),n为线性表长度(n=0称为空表)，表中相邻元素之间存在着顺序关系。a1 ：表头元素；an ：表尾元素；ai-1称为ai的直接前驱；ai+1 称为ai的直接后继。,结构特点：,(1)有且只有一个根结点a1，无前驱 。 (2)有且只有一个终端结点an ，无后继 。 (3)其他结点有且只有一个直接前驱和一个直接后继。,线性表的分类,(1)简单线性表：数据元素是简单项(数字、字母、季节名等)，(12,34,4,67,8),(2)复杂线性表：数据元素由若干个数据项组成，此时数据元素称为记录。,复杂线性表举例（学生登记表）,4.2.2 线性表的顺序存储结构,顺

11、序表：采用顺序存储结构的线性表称为顺序表(一维数组),顺序存储：用一组地址连续的存储空间依次存储放线性表的各元素,特点(顺序存储结构),表中的所有元素所占存储空间连续 表中各元素在存储空间中按逻辑顺序存放,第i个元素地址：,m：每个元素占m个存储单元 Loc(a1)第一个元素地址(基址),1.顺序表基本概念,顺序表的顺序存储结构,2.顺序表基本运算,基本运算：,插入：在线性表指定位置插入一个新元素 删除：删除线性表中指定的元素 查找：在线性表中查找特定元素 排序：线性表中元素按关键字升序或降序排序 分解：将一个线性表分解为多个 合并 复制 逆转,插入运算：,定义：是指在表的第i个位置上插入一个

12、值为b的新元素,原表长为n：( a1，a2，ai-1，ai ，ai+1， an ),新表长为n+1：( a1，a2，ai-1，b，ai ，ai+1， ， an ),步骤：,(1)将ai an顺序向后移动,为新元素让出位置 (2)将b置入空出的第i个位置,举例：(在第4个和第5个元素之间插入元素91),时间性能分析：,插入运算，时间主要消耗在数据移动上。在长度为n的线性表中插入一个元素，则平均移动元素次数：,Pi：在第i个位置上作插入的概率。设Pi=1/(n+1) 共需移动(n-i+1)个元素。,删除运算：,定义：指将表中第i个元素从线性表中去掉。,原表长为n：( a1，a2，ai-1，ai ，

13、ai+1， an ),新表长为n-1：( a1，a2，ai-1，ai+1， ， an ),步骤：,(1)删除ai (2)将ai+1 an b顺序向前移动,举例：(删除第五个元素21),时间性能分析：,时间消耗与插入运算相同，平均移动元素次数：,qi:在第i个位置上作删除的概率。设qi=1/n 共需移动(n-i)个元素。,3.顺序表优点和缺点,优点：,逻辑上相邻元素存储位置也相邻,无需增加额外存储空间 可方便随机存取表中任一元素,缺点：,插入和删除运算不方便,必须移动大量结点,效率较低 不适合元素经常变动的大的线性表,4.2.3 线性表的链式存储结构,链式存储结构：存储空间可以不连续。不要求逻辑

14、上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由指针域确定。,结点组成：数据结构中每个数据结点对应一个存储单元，简称结点。,两部分：,数据域：存放数据元素值 指针域：存放指针，指向后继结点,线性链表中用专门的HEAD指针指向第一个元素的结点，其最后一个元素没有后件，因此最后一个结点指针域为空(用NULL或0表示),线性链表,定义：线性表的链式存储结构称为线性链表,分类：单链表、循环单链表、双向链表,1.单链表,定义：由n个结点链接，且每个结点中只包含一个指针域的链表。,逻辑状态与物理状态：线性单链表( A, B, C, D, E, F ),逻辑状态,物理状态,头指针 存储地址 数据域 指针

15、域,1 7 13 19 25 31,单链表存取：必须从头指针开始进行，依次顺着指针向链尾方向扫描。找到各个元素。,(1)单链表插入：增加新结点,修改链接指针,后插结点,在指针p所指结点之后插入一个指针s所指的结点 修改p和s所指结点的指针域的指针即可,步骤,snext=pnext 修改s指针域, s结点的后继是p结点的后继 pnexts 修改p指针域, 使其指向新结点s,(2)单链表删除：不需要移动元素,仅修改指针链接,删除结点,删除p指向的结点 只修改p(被删除结点)的前驱结点的指针域即可,步骤,先找到p的前驱结点q 删除p结点，修改q结点指针域 qnextpnext,(3)带头结点的单链表

16、,设置：在单链表的第一个结点之前设一个结点(头结点)，其数据域可以不存任何信息，指针域指向第一个结点的指针。,作用：头结点始终存在，地址不变。插入和删除第一个结点时就不影响表头指针(只改变头结点的指针域即可)，简化了 插入、删除算法。,带头结点的单链表L为空的判定条件为：L.next= =NULL,带头结点的单链表,2.循环链表,特点：表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。,优点：从表中任一结点出发均可找到表中其它结点。(单链表每次查找必须从头指针开始，不方便。),注意：操作和线性链表基本一致，差别是循环条件不是判断p或p-next是否为空,而是它们是否等于头指针 。,带头结点的循环单链表,3.双向链表,设置：双向链表，每个结点有两个指针域，next指向后继结点，prior指向前趋结点。,作用：克服单链表的的缺点每个结点，只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找。使用双向链表可以方便地沿向前或向后两个方