《数据结构》本科教学课件

《数据结构》本科第一章绪论2

目前，计算机业在飞速发展，其应用领域也早不限于科学计算，而是广泛深入到社会的各个部门。从应用的角度来看，计算机在各部门的应用大致可归纳为以下几类：

（1）科学计算与分析

（2）计算机管理

（3）计算机实时控制

（4）计算机辅助设计/制造（CAD/CAM）及绘图

（5）计算机通讯网络

（6）办公自动化

（7）人工智能

（8）机器仿真

（9）计算机辅助教育（CAI）和娱乐绪论（续）

随着计算机应用的广泛深入，计算机应用领域会越来越广，计算机要处理的数据更加多样化，而数据之间的关系和对数据处理的要求也更为复杂。这就要求我们在从事具体的计算机应用时，要用较科学的方式描述、存储和处理数据，从而使计算机高效率地去完成预期的任务。

本章主要讨论数据结构、算法及算法分析方面的一些基本概念。

31.1数据结构研究的内容和方法41.1.1数据结构的含义 数据结构（DataStructure）简称DS，研究的是计算机所处理数据元素间的关系及其操作实现的算法。包括数据的逻辑结构、数据的存储结构以及数据的操作。 数据结构在计算机科学中涉及到计算机硬件（特别是编码理论、存储机制等）、计算机软件的研究(无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题)。数据结构的含义

因此可以认为，数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，如图1.1：5

图1.1“数据结构”所处的地位

代数系统数据表示法数据结构

数据存取

机器组织

编码理论

数据的操作

算子关系数学

数据类型

存储装置硬件（计算机系统设计）软件（计算机程序设计）

文件系统

数据组织

信息检索1.1.2数据结构研究的内容1. 数据的逻辑结构（LogicalStructure）指数据元素之间的逻辑关系。数据（Data），客观事物的符号表示。是指输入到计算机并能被计算机程序处理的符号的总称。如方程中的整数、实数，源程序中的字符串，以及文字、图像和声音信号等等，都可作为计算机中的数据。数据元素（DataElement），数据的基本单位。简单的数据元素可以是整数、字符等形式。一般，数据元素由若干个数据项（DataItem）组成，常称为记录（Record）。6数据的逻辑结构（续）

例如表1.1的图书管理表，其中

a1，……，an对应的每一行各是一个数据元素，而编号、书名等就是数据项。在计算机存取数据时，数据项是不可分割的最小存取单位。表1.1图书管理表编号书名作者出版社出版日期……001数据库周志逵科教1998.7……002数据结构夏克俭王绍斌国防工业2007.2………………………………………………………………7a1a2..an数据的逻辑结构（续）

上表（List）中每一行为一个数据元素（或记录），记为ai(1≤i≤n)，元素之间呈现的是一种线性关系。此表可表示为： list=(a1,a2,……,an)

显然表中每一数据元素包含的许多值是非数值性的（如文字、日期等数据），对其进行的操作（或运算）也不再是加、减、乘、除等数学运算，而是诸如：

查询（查找一本书的信息）、 插入（增加一本书的信息）、 修改（某书修订后，修改元素中某些信息）、 删除（某书不再版了，做删除标记）、 分类（按某数据项的值建立索引） 等这样的运算。8数据的逻辑结构（续）9

具有相同性质的数据元素组成的集合，称为数据对象（DataObject），它是数据的一个子集。 计算机要处理的数据元素不是相互孤立的，而是有着各种各样的联系，这种数据元素之间的关系就称作逻辑结构。根据数据元素之间关系的不同特性，归纳出四类基本的逻辑结构：（1）集合结构中的数据元素除了“属于同一集合”的关系外，没有其他关系（如例1–1）。（2）线性结构数据元素之间存在一对一的关系（如例1–2）。（3）层次结构数据元素之间存在一对多的关系（如例1–3）。（4）网状结构数据元素之间存在若干个多对多关系（如例1–4）。例1-1集合10

例1–1学校举办了英语演讲比赛和歌曲演唱比赛，参赛者可以获得优胜奖和参与奖。问多少学生在两个竞赛中都获得了优胜奖？求解这个问题可以将在两个竞赛中获得优秀奖的人分别构成一个整体，问题便成了求两个集合的交集。

英语

歌曲丁1优胜王2优胜张3优胜李4参与张3参与李4优胜例1-2表例1–2到医院看病的病人需要排队，而医院实行先来先服务的原则。每个病人都有自己的病历，病历上有病历的编号还有病人的其他具体信息。如表1.2所示。表1.2病人信息表 这张表中的元素存在一个顺序关系，即谁在谁前，谁在谁后的信息（即病人诊断顺序依次为张立，田方，……）。所以，可以用线性结构来刻画这种关系。编号

姓名性别

年龄-------172张立女30-------091田方男20------------------------------------------11例1-3大学系级行政机构12

大学系级行政机构，如图1.2所示：

其中系、办公室、……教师、学生可视为数据元素。元素之间呈现的是一种层次关系，即系级下层机构为办公室、教研室和班级，而办公室、教研室和班级等单位又由若干个管理人员、教师、实验员和学生组成。管理员教师实验员学生办公室班级教研室系例1-4田径比赛的时间安排问题13

设田径比赛项目有：A(跳高)、

B(跳远)、C(标枪)、D(铅球)、E(100m跑)、F(200m跑)。参赛选手的项目表如下：问如何安排比赛时间，才能使得：

(1)每个比赛项目都能顺利进行（无冲突）；

(2)尽可能缩短比赛时间。

姓名

项目1

项目2

项目3丁一ABE马二CD张三CEF李四DFA王五BF例1-4（续）14

此问题可归纳为图的“染色“问题：设项目A∽F各表示一数据元素，以○表示。若两个项目不能同时举行，则将其连线。由此得到如图1.3所示的结构。若用四种颜色表示四个时间段，一种着色方案如图所示。

FCEABDFCEABD

图1.3即：红色时间段(如8~10点)—A、C项目；浅蓝—B、D项目；深蓝—E项目；紫色—F项目。数据逻辑结构（续）15

上面的例子中所描述的逻辑结构都是从具体问题中抽象出来的数据模型，是独立于计算机存储器的。数据元素并不是孤立存在的，它们之间存在着某种关系（或联系、结构）。对于例1-2，数据元素之间呈现的是一种线性关系，或线性(linear)结构；对于例1-3，呈现的是一种层次关系，或树(Tree)结构；对于例1-4，呈现的是一种网状关系，或图(Graph)结构。如图1.4所示。

（线性关系）（层次关系）（网状关系） 图1.42．数据的存储结构（或物理结构）（PhysicalStructure）

数据结构在计算机中的表示（映像）称为数据的存储结构或物理结构，它包括数据元素的表示和关系的表示。数据元素的表示 计算机中表示信息的最小单位是比特（Bit），即二进制数中的一位。数据元素由若干位组成的位串来表示，通常称这个位串为节点（Node）或元素（Element）。当数据元素由若干数据项组成时，数据项的取值范围称为数据域（DataField）。关系的表示在存储器物理位置上如何反映数据元素之间的关系。目前，对一个数据结构常用的有四种存储表示：（1）顺序存储（SequentialStorage

）：将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中（如c语言的一维数组）。如表L=(a1,a2，……,an)的顺序结构如图1.5所示。16数据的存储结构（续）（2）链式存储（LinkedStorage）：将数据结构中各元素分布到存储器的不同点(称为节点)，用地址（或链指针）方式建立它们之间的联系，由此得到的存储结构为链式存储结构。如表L=(a1,a2，……,an)的链式存储结构如图1.6：

链式结构是本课程的一个重点，因为元素之间的关系在计算机内部很大程度上是通过地址或指针来建立的。（3）索引存储（IndexedStorage）：在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表。17a1

a2…………an图1.5

(存储器)

a1

a2

an^数据的存储结构（续）18例1-5电话号码查询问题。 为便于提高查询的速度，在存储用户数据文件的同时，建立一张姓氏索引表，如图1.7所示。这样，查找一个电话就可以先查找索引表，再查找相应的数据文件，无疑加快了查询的速度。

姓名

电话

丁一62331234…………

王二62345678…………

张三63450987…………

数据文件

姓氏

地址

丁

王

张…………

索引表数据的存储结构（续）19

（4）散列存储(HashStructure)：根据数据元素的特殊字段(称为关键字key)，计算数据元素的存放地址，然后数据元素按地址存放，所得到的存储结构为散列存储结构(或Hash结构)。3.数据的操作

一般而言，必须对数据进行加工处理，才能得到问题的解。在非数值性问题中，对数据的操作（或运算）已不限于对数据进行加、减、乘、除等数学运算。数据的操作是定义在逻辑结构上的，而操作的具体实现是在存储结构上进行的。基本的数据操作主要有以下几种： （1）查找：在数据结构中寻找满足某个特定条件的数据元素的位置或值。数据的操作（2）插入：在数据结构中添加新的数据元素。（3）删除：删去数据结构中指定的数据元素。（4）更新：改变数据结构中某个数据元素一个或多个数据项的值。（5）排序：重新安排数据元素之间的逻辑顺序，使之按（某个数据项的）值由小（大）到大（小）的次序排列。 其中，查找是一种引用型操作，即它不改变现有结构，而其余四种均会改变现有结构，被称为加工型操作。 综上所述，数据结构是一门研究非数值计算的程序设计中计算机操作的对象以及它们之间关系和操作的学科。在本书中，对数据结构的详细讨论，都是从数据的逻辑结构、数据的存储结构和对数据的操作这三方面展开的，读者应掌握住这个规律，以便以后知识的学习。201.1.3研究数据结构的方法

研究数据结构是为了编写解决问题（或完成任务）的程序。用计算机求解一个实际问题的过程，一般可以用图1.8所示的模型加以描述。图1.8计算机求解问题的流程

即首先要从现实问题出发，抽象出一个适当的数学模型，然后设计一个求解此数学模型的算法，最后根据这个算法编出程序，经过测试、排错、运行直至得到最终的解答。现实问题、数学模型、算法和程序是问题求解过程中出现的四个重要环节。21现实问题数学模型算法程序解1.2抽象数据类型的表示与实现

抽象数据类型（AbstractDataType,简称ADT）是指一个数据结构以及定义在其上的一组操作。本书采用类C语言作为描述算法，这使得数据结构的描述和讨论简明清晰，不拘泥于C语言的细节，又容易转换为C或C++程序。以下面的形式描述ADT：

ADT=（D，R，P） 其中，D是数据元素的有限集；R是D上关系的有限集，（D，R）构成了一个数据结构；P是对该数据结构的基本操作集。用以下格式定义抽象的数据类型：ADT抽象数据类型名{数据元素集：<元素集的定义>

数据关系集：<关系集的定义>

基本操作集：<基本操作的定义> }ADT抽象数据类型名；22抽象数据类型

其中，基本操作的定义格式是： 基本操作名(参数表)

初始条件：<初始条件描述>

操作结果：<操作结果描述>

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&开头，除了可提供输入值外，还可返回操作结果。“初始条件”描述了操作执行之前的数据结构及参数应满足的条件，“操作结果”说明了操作正常完成之后，数据结构的变化和应返回的结果。

231.3学习数据结构的目的1.3.1数据结构的发展简史及在计算机科学中的地位

数据结构的内容来源于图论、操作系统、编译系统、编码理论和检索与分类技术的相关领域。20世纪60年代末，美国一些大学把上述领域中的技术归纳为《数据结构》课程。美国人D.E.克劳特《计算机程序设计技巧》一书，对数据的逻辑结构、存储结构及算法进行了系统的阐述。我国从70年代末在各大专院校陆续开设数据结构课程，目前该课程已经是计算机专业的核心课程之一。 关于计算机科学的概念，计算机界的权威人士认为： 其一，计算机科学是信息结构转换的科学，构造有关信息结构的转换模型，对其进行研究是计算机科学中最根本性的问题。而构造出现实问题中的数据结构模型，并合理地将其映象到计算机存储装置中，是这种观点的具体体现。24学习数据结构的目的

其二，计算机科学是算法的学问，研究的是对数据处理的方法或规则。要用计算机完成具体任务，离不开对算法的研究。因而，“数据结构”+“算法”是计算机科学研究中的基础课题，其理论基础是离散数学中的图论、集合论和关系理论等等，实践基础是程序设计技术。1.3.2学习数据结构的目的在分析、开发系统与应用软件中要用到的数据结构知识。 如操作系统、编译系统、数据库和人工智能中涉及到：栈和队列、存储管理表、目录树、语法树、索引树、搜索树、散列表、有向图等等。学习数据结构是为了提高程序设计水平。 我们知道，不论计算机从事哪方面的应用，一般都是由计算机运行程序来实现的，而任何一个程序都是建立和运行在相应的数据结构基础上的。这就要求在做程序设计时，一方面要描述好对应的数据结构，另一方面要设计正确、精确和快速处理数据的算法（或程序）。做到这两点，无疑程序设计水平将会有一个大的提高。251.4算法的定义及其特性1.4.1算法的定义

算法（Algorithm）是一个有穷规则（或语句、指令）的有序集合。它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出。例1-6求两正整数m、n的最大公因子的算法如下：

①输入m,n； ②m/n（整除），余数→r(0≤r≤n)； ③若r=0,则当前n=结果，输出n,算法停止；否则，转④； ④n→m,r->n；转②。如初始输入m=10,n=4,则m,n,r在算法中的变化如下：

mnr1042420(停止)

即10和4的最大公因子为2。26算法特性1.4.2算法的性质

(1)

有穷性

——算法执行的步骤（或规则）是有限的；

(2)

确定性

——每个计算步骤无二义性；

(3)

可行性

——每个计算步骤能够在有限的时间内完成；

(4)

输入

——算法有一个或多个外部输入；

(5)

输出

——算法有一个或多个输出。 这里要说明的是，算法与程序有联系又有区别。二者都是为完成某个任务，或解决某个问题而编制的规则（或语句）的有序集合，这是它们的共同点。区别在于：其一，算法与计算机无关，但程序依赖于具体的计算机语言。其二，算法必须是有穷尽的，但程序可能是无穷尽的。其三，算法可忽略一些语法细节问题，重点放在解决问题的思路上，但程序必须严格遵循相应语言工具的语法。算法转换成程序后才能在计算机上运行。另外，在设计算法时，一定要考虑它的确定性，即算法的每个步骤都是无二义性的（即一条规则不能有两种以上的解释）。27例1-6中的算法转换成C语言将例1-6中的算法转换成C语言程序如下：#include“stdio.h”intmaxog();main(){intm,n,j;charflag=‘Y’;while(flag==‘y’||flag==‘Y’) {printf(“\n”);scanf(“input=%d%d”,&m,&n);//输入两个整数m,n if(m>0&&n>0){j=maxog(m,n);//求m,n的最大公因子

printf(“output=%d\n”,j);}//输出结果

printf(“continue?(y/n)”); flag=getchar();//输入’y’或’Y’继续，否则停止

}}28算法转换成C语言 intmaxog(intm,intn)//求m、n的最大公因子算法（或函数）

{intr=m%n; while(r!=0) {m=n;n=r;r=m%n;} return(n);}

以后章节中的算法均以C语言的函数形式描述，而main()和数据I/O就不描述了。另外，由于某种原因（如参数错，存储分配失败等）导致算法无法继续执行下去时，约定调用函数ERROR()进行出错处理。 讨论了数据结构与算法的基本概念后，有必要提到瑞士科学家沃思（N.Wirth）的著名公式：数据结构+算法=程序 数据结构是研究从具体问题中抽象出来的数学模型如何在计算机存储器中表示出来；而算法研究的是对数据处理的步骤。如果对问题的数据表示和数据处理都做出了具体的设计，就相当于完成了相应的程序。291.4.3算法的设计目标算法的设计应满足以下五点： 正确性算法应当满足具体问题的需求，一般包括对输入、输出、处理等的明确的无歧义性的描述。 可读性可读性有助于对算法的理解及帮助排除算法中隐藏的错误，也有助于算法的交流和移植。 健壮性当输入不合法的数据时，算法应能做出相应的处理，而不产生不可预料的结果。 高效率算法的效率指算法执行时间的长短，称作算法的时间复杂度。 低存储量需求算法的存储量需求指算法执行期间所需要的最大存储空间，称作算法的空间复杂度。

301.4.4算法效率的度量

算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。这个时耗与下面因素有关：书写算法的程序设计语言；编译产生的机器语言代码质量；机器执行指令的速度；问题的规模。 这四个因素中，前三个都与机器有关。当度量一个算法的效率抛开具体的机器、仅考虑算法本身的效率高低时，算法效率仅与问题的规模有关，也就是说，算法效率是问题规模的函数。为了详细描述这个函数，我们引入以下几个概念：

1.语句的频度(FrequencyCount)

语句频度定义为可执行语句在算法（或程序）中重复执行的次数。若某语句执行一次的时间为t，执行次数为f，则该语句所耗时间的估计为t·f。31例1-7求两个n阶方阵乘积

c[0][0]c[0][1]···········c[0][j]···········c[0][n-1] c[1][0]c[1][1]···········c[1][j]···········c[1][n-1] ···········

Cn·n=An·nBn·n= ··········· c[i][0]c[i][1]···········c[i][j]···········c[i][n-1] ··········· c[n-1][0]c[n-1][1]·······c[n-1][j]·······c[n-1][n-1]

其中：n-1

c[i][j]=∑A[i][k]B[k][j]

k=032例1-7（序）voidMATRIXM(A,B,C) floatA[n][n],B[n][n],c[n][n]; {inti,j,k; 语句频度

for(i=0;i<n;i++) n+1 for(j=0;j<n;j++) n(n+1){c[i][j]=0; n2 for(k=0;k<n;k++) n2(n+1) c[i][j]=c[i][j]+A[i][k]*B[k][j];}} n32.算法的时间复杂度(TimeComplexity)

算法的时间复杂度定义为算法中可执行语句的频度之和，记为T(n)。T(n)是算法所需时间的一种估计，n为问题的规模（或大小、体积）。如例1-7中，问题的规模n为矩阵的阶，该算法的时间复杂度为：

T(n)=(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1

当n->∞时，lim(T(n)/n3)=2，故T(n)与n3为同阶无穷大，或说T(n)与n3成正比、T(n)的量级为n3，记为：T(n)=O(n3)

。33例1-8在数组中查找

在数组（A[1],A[2],..........,A[n]）中查找最后一个与给定值k相等的元素的序号的算法。

intsearch(datatypeA[n+1],datatypek) {inti=n;A[0]=k;while(i>0&&A[i]!=k)i--; return(i); }

本例应以平均查找次数为算法的T(n)。设查找每个元素的概率pi(1≤i≤n)均等，即pi=1/n，查找元素k时，k与A[i]的比较次数（即执行while循环语句的次数）Ci=n-(i-1)，则查找次数的平均值（或期望值）：

因n->∞时，lim(T(n)/n)=1/2，故T(n)=O(n)，此时又称T(n)为算法的渐进时间复杂度。34T(n)=T(n)的量级T(n)的量级通常有：O(c)——常数级，不论问题规模多大，T(n)一致，因而是理想的T(n)量级；O(n)——线性级；O(n2),O(n3)——平方、立方级；O(log2n),O(n*log2n)——对数、线性对数级；O(2n)——指数级，时间复杂度最差。以上几种常见的T(n)随n变化

的增长率如图1.9所示：35T(n)

O(2n)

O(n3)

O(n2)

O(n)

O(n*log2n)

O(log2n)

O(c)

n

算法分析

对较为复杂的算法，可分段分析其时间复杂度。如某算法可分为两部分，其时间复杂度分别为：

T1(n)=O(f(n)),T2(n)=O(g(n))此时两部分问题的体积一致，则总的T(n)=T1(n)+T2(n)=O(max(f(n),g(n)),表示取f(n)、g(n)中最大者。 但若T1(m)=O(f(m)),T2(n)=O(g(n)),两部分的体积不一致，则： T(m,n)=T1(m)+T2(n)=O(f(m)+g(n))。 另外，算法空间复杂度的定义： 设算法对应问题的体积（或规模）为n,执行算法所占存储空间的量级为D(n)，则D(n)为算法的空间复杂度(SpaceComplexity)。36第一章小结

37DS时间复杂度T(n)空间复杂度D(n)逻辑结构线性结构树型结构网状结构存储结构链式存储索引存储顺序存储散列存储查询DS上的操作插入删除更新算法算法定义、性质算法分析第一章作业1.试用DS=（D，R）形式说明字符串:S=“s1,s2,……,sn”(si∈char)是一个数据结构，即S=（D，R）中D=？R=？2.设五叉口：其中E、C道为单行线。试构造使该路口行驶车辆不碰撞的交通管理模型。（提示:找出路口各行车路线(AB,BC,….),若两行车路线不能对驶,则将其连线。)3.设n为正整数，求下列算法段的时间复杂度，即T(n)=O(?)(1)i=1;k=0;(2)i=1;j=0;(3)for(i=n-1;i>=1;i--)while(i<n) while(i+j<=n)for(j=0;j<=i-1;j++){k=k+10*i;i++;}{if(i>j)j++;{temp=A[j];A[j]=A[j+1]; elsei++;} A[j+1]=temp;}38

CBAED第二章线性表

数据元素之间满足线性关系的表称为线性表，是一种最基本、最简单的数据结构类型。本章讨论线性表的逻辑和存储结构、相关算法的实现以及线性表应用举例。2.1线性表的定义及基本操作2.1.1定义：线性表(LinearList)是若干数据元素的一个线性序列，记为：

L=(a0,∙∙∙∙ai-1aiai+1∙∙∙∙∙∙an-1)

其中：L为表名，ai(0≤i≤n-1)为数据元素；n为表长，n>0

时，L为非空表，否则为空表。2.1.2线性表的逻辑结构和特征

线性表L可用二元组形式描述：L=(D,R)

数据元素集合:D={ai|ai∈datatype,i=0,1,2,∙∙∙∙∙∙∙∙∙n-1,n≥0}

关系集合:R={<ai,ai+1>|ai,ai+1∈D,0≤i≤n-2}

表长n=0时，L为空表；关系符<ai,ai+1>在这里称为有序对，表示任意相邻的两个元素之间的一种先后次序关系，称ai是ai+1的直接前驱,ai+1是ai的直接后继，当表长n≤1时，关系集R为空集。39例2-1线性表的例子

L1=(A,B,……,Z)元素为字符；L2=(6,7,……,105)元素为整数； 学生记录表：

线性表的特征：对非空表,a0是表头,无前驱；an-1是表尾,无后继；其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。2.1.3线性表的抽象数据类型表示

设线性表L=(a0,a1,……,an-1)，对L的抽象数据类型表示：40

学号

姓名性别

年龄班级-------J99001丁兰女19计99-------J99002王林男20计99-------------------------------------------------J99032马红女18计99-------a0a1....a31线性表的抽象数据类型表示ADTList{数据元素集：D={ai|ai∈datatype,i=0,1,2,……n-1,n≥0}

数据关系集：R={<ai,ai+1>|ai,ai+1∈D,0≤i≤n-2}

基本操作集：PListInit(&L)

操作结果：构造一个空的线性表L。ListDestroy(&L)

初始条件：线性表L存在。操作结果：撤销线性表L。ListClear(&L)

初始条件：线性表L存在。操作结果：将L置为一张空表。ListLength(L)

初始条件：线性表L存在。操作结果：返回L中元素个数(即表长n)。ListEmpty(L)

初始条件：线性表L存在。操作结果：L为空表时返回TRUE，否则返回FALSE。41线性表的抽象数据类型表示GetElem(L,i)

初始条件：线性表L存在，且0≤i≤n­1。操作结果：返回L中第i个元素的值(或指针)。LocateElem(L,e)

初始条件：线性表L存在，且e∈datatype。 操作结果：若e在L中，返回e的序号(或指针)；否则返回e不在表中的信息（实际应用中如-1或NULL）。即： i当元素e=ai∈L,且ai是第一个与e相等时；LocateElem(L,e)=-1e不属于L时。PreElem(L,cur)

初始条件：线性表L存在，且cur∈datatype。操作结果：若cur在L中且不是表头，返回cur的直接前驱，否则返回NULL。SuccElem(L,cur)

初始条件：线性表L存在，且cur∈datatype。操作结果：若cur在L中且不是表尾元素，返回cur的直接后继的值，否则返回NULL。42线性表的抽象数据类型表示ListInsert(&L,i,e)

初始条件：线性表L存在，且e∈datatype。 操作结果：若0≤i≤n-1，将e插入到ai之前，若i=n，将e插到表尾，表长增加1，函数返回TURE；i为其他值时返回FALSE，L无变化。即： 插入前：(a0,a1,---,ai-1,ai,ai+1-------,an-1)

插入后：(a0,a1,---,ai-1,e,ai,ai+1-------,an-1)ListDel(&L,i)

初始条件：线性表L存在。 操作结果：若0≤i≤n-1，将第ai从表中删除，函数返回TURE，否则函数返回FALSE，L无变化。即：删除前:(a0,a1,---,ai-1,ai,ai+1-------,an-1)

删除后:

(a0,a1,---,ai-1，ai+1-------,an)ListTraverse(L)

初始条件：线性表L存在。操作结果：依次对表中的元素利用visit()函数进行访问。}ADTList；43线性表的操作

以上运算是对线性表L施加的一些基本运算，对线性表L的运算还有：

合并、拆分、复制、排序等等。例2-2设线性表La=(a0a1,……,am-1),Lb=(b0b1,……,bn-1)，求La∪Lb=>La，如图2.1所示。

算法思路：依次取Lb中的bi(i=0,1,…,n-1)，若bi不在La中，则将其插入。算法描述：voidUnion(list*La,list*Lb) {inti,k; datatypex; for(i=0;i<ListLength(Lb);i++) {x=GetElem(Lb,i);k=LocateElem(La,x); if(k==-1)ListInsert(La,ListLength(La),x);}}类似可写出求La–Lb,La∩Lb等运算的算法。44

1357La

57911

Lb线性表的操作例2-3

设计清除线性表L=(a0,a1,---,ai,-------,an-1)中重复元素的算法。算法思路：对当前表L中的每个ai（0≤i≤n-2），依次与aj(i+1≤j≤n-1)比较，若与ai相等，则删除之。算法描述：

voidPurge(list*L) {inti=0,j;datatypex,y; 初始：L=（1，3，1，5，3，5，7）

while(i<ListLength(L)-1) i {x=GetElem(L,i);j=i+1;j while(j<ListLength(L))结果：L=（1，3，5，7）

{y=GetElem(L,j);if(y==x)ListDel(L,j);elsej++;} i++;}}2.2

线性表的顺序存储结构 线性表在计算机存储器中的映象（或表示）一般有两种形式，一种是顺序映象，一种是链式映象。452.2.1顺序表

若将线性表L=(a0,a1,……,an-1)中的各元素依次存储于计算机一片连续的存储空间，如图2.2所示。这种机内表示为线性表的顺序存储结构(顺序表)。地址：b:}占d个单元

b+d: 设Loc(ai)为ai的地址，Loc(a0)=b，则：

… Loc(a1)=b+1*d

b+i*d: ........ … Loc(ai)=b+i*d

b+n*d:

图2.2

顺序表的特点：(1)逻辑上相邻的元素ai,ai+1，存储位置也是相邻的；(2)对ai的存取为随机存取或按地址存取。(3)存储密度高。存储密度D=(数据结构中元素所占存储空间)/(整个数据结构所占空间)。 顺序表的不足：对表的插入和删除等运算的时间复杂度较差。46a0a1

…ai…an-1线性表顺序存储结构

在C语言中，一维数组也是存放于一片连续的存储空间，故可借助于C语言中一维数组类型来描述线性表的顺序存储结构，即: #definemaxsize1024//线性表的最大长度

typedefstruct//表的类型

{datatypedata[maxsize];//表的存储空间

intlast;//当前表尾指针

}sqlist;*sqlink;//表说明符 如果说明sqlinkL;L=(sqlink)malloc(sizeof(sqlist));则指针L指向一个线性表：

ai表示为L->data[i](0≤i≤L->last)

图2.3

47L->data[0]..…i..…L->last->n-1maxsize-1空闲单元a0…ai

…an-12.2.2基本运算的相关算法

关于线性表的运算，有些实现起来是相当简单的，例如： 置空表：ListClear(L),令L->last=-1；取ai:GetElem(L,i),取L->data[i]； 求表长：ListLength(L),取L->last之值加1即可。 所以主要讨论插入、删除、定位等算法的实现。1.前插：将一给定值e插在元素ai之前，即实现ListInsert(L,i,e)。算法思路：若表存在空闲空间,且0≤i≤L->last+1,将(L->data[L->last]～L->data[i])顺序下移一个数据单位，然后将e插入L->data[i]处。算法描述：

intListInsert(sqlinkL,inti,datatypee){if(L->last>=maxsize-1){ERROR(L);return(0);} elseif(i<0||i>L->last+1){ERROR(i);return(0);} else{for(intj=L->last;j>=i;j--) L->data[j+1]=L->data[j]; L->data[i]=e;L->last++; return(1);}}48L->data[0]..…i..…L->last->n-1maxsize-1空闲a0…ai

…an-1基本运算的相关算法算法分析：算法的主要时耗在数据元素的移动上，即算法中for语句上，故以插入一个元素的平均移动次数刻画算法的T(n)(n为表长)。设e插入ai(0≤i≤n)处的概率pi均等，即pi=1/(n+1),而插入e时的元素移动次数Ci=n-i,则平均移动次数为：

T(n)=piCi=

n/2=O(n)。49a0…ai

…an-1L->data[0]..…i..…L->last->n-1maxsize-1pi=1/(n+1)Ci=n-i基本运算的相关算法2.删除：将表中第i个元素ai从表中删除，即实现ListDel(L,i)。算法思路：若参数i满足：0≤i≤L->last,将表中L->data[i+1]∽L->data[L->last]部分顺序向上移动一个元素位置，挤掉L->data[i]。算法描述：

intListDel(sqlinkL,inti){if(i<0||i>L->last){ERROR(L);return(0);} else{for(intj=i+1;j<=L->last;j++) L->data[j-1]=L->data[j];L->last--;return(1);}}算法分析：设删除ai(0≤i≤n-1)的概率pi均等,即pi=1/n,删除ai的元素移动次数Ci=n-(i+1),则平均移动次数为：

T(n)=piCi=(n-1)/2=O(n)。50a0…ai

…an-1L->data[0]..…i..…L->last->n-1maxsize-1空闲基本运算的相关算法3.定位：确定给定元素e在表L中第一次出现的位置（或序号）。即实现LocateElem(L,e)。算法对应的存储结构如图所示。算法思路：设一扫描变量i(初值=0)，判断当前表中元素ai是否等于e，若相等，则返回当前i值（表明e落在表的第i位置）；否则i加1，继续往下比较。若表中无一个元素与e相等，则返回-1。算法描述：

intLocateElem(sqlinkL,datatypee) {inti=0; while(i<=L->last&&L->data[i]!=e) i++; if(i<=L->last)return(i);elsereturn(-1);}算法分析：算法时耗主要在while语句中元素e与ai的比较次数上，用平均比较次数来刻画算法的T(n)。设元素ai(0≤i≤n-1)与e相等的概率pi均等，即pi=1/n,查找ai与e相等的比较次数Ci=i+1,则平均的比较次数为：

T(n)=piCi=(n+1)/2=O(n)。51L->data[0]..…i..…L->last->n-1maxsize-1空闲a0…ai

…an-12.3线性表的链式存储结构

线性表的顺序存储结构有存储密度高及能够随机存取等优点，但存在以下几点不足：(1)插入、删除等运算耗时，且存在元素在存储器中成片移动的现象；(2)要求系统提供一片较大的连续存储空间。 下面讨论线性表的链式存储结构，即链表。是第二章的重点。2.3.1单链表 将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块，称为节点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构。表中元素ai的节点形式如图2.4所示。

图2.4

其中，data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的节点。于是，线性表L=(a0,a1,……,an-1)的结构如图2.5所示:52

data

next

a0

a1

an-1^

L ..….单链表例2-4

设线性表L=(赵，钱，孙，李，周，吴，郑，王)，各元素在存储器中的分布如图2.6所示。

53地址dataNext100李142106钱112112孙100118王NULL124吴136130赵106136郑118142周124

图2.6带头节点的单链表：

a0

an-1^

H…L赵钱孙吴郑王^周李单链表

节点描述：typedefstructnode//节点类型

{datatypedata;//节点的数据域

structnode *next;//节点的后继指针域

}linknode,*link;

若说明linknodeA;linkp;则结构变量A为所描述的节点，而指针变量p为指向此类型节点的指针（或p的值为节点的地址），如图2.8所示:

设p指向链表中节点ai，如图2.9所示:

获取ai，写作：p->data；而取ai+1,写作：p->next->data。另外，若指针p的值为NULL，则它不指向任何节点,此时取p->data或p->next是错误的。54

data

next

PA：

aiai+1P2.3.2单链表的基本操作

可调用C中malloc()函数向编译系统申请节点的存储空间，若说明：

linkp;p=(link)malloc(sizeof(linknode));则获得了一个类型为linknode的节点，且该节点的地址已存入指针变量P中：1．建立单链表算法思路：依次读入L=(a0,.....,an-1)中每一ai(设为整型)，若ai≠结束符(-1)，则将ai形成一节点，链入表尾，最后返回链表的头节点指针H。算法描述：linkCreatelist() {datatypea;linkH,p,r; H=r=(link)malloc(sizeof(linknode)); scanf(“%d”,&a);//输入数据元素

while(a!=-1) {p=(link)malloc(sizeof(linknode));//申请新节点

p->data=a;r->next=p;r=p;//存入数据,将新节点链入表尾

scanf(“%d”,&a);} r->next=NULL;return(H);}//表尾的后继置空55

data

next

P

建立单链表设L=(2，4，8，-1)，则建表过程如下： 设表长为n，显然此算法的时间复杂度为T(n)=O(n)。从此算法可以看到，链表的结构是动态形成的，即算法运行前，表结构是不存在的，而通过算法的运行，得到一个如图所示的单链表。2．链表查找（1）按序号查找：即实现GetElem(L,i)。算法思路：从链表的a0起，判断是否为第i节点，若是则返回该节点的指针，否则查找下一节点,依次类推。算法描述：LinkGetElem(linkH,inti){intj=-1;linkp=H;if(i<0)return(NULL);while(p->next&&j<i){p=p->next;j++;}if(i==j)return(p);elsereturn(NULL);}//查找失败,即i>表长

}56H248^单链表运算（2）按值查找（定位）：即实现LocateElem(L,e)。算法思路：从节点a0起，依次判断某节点是否等于e,若是,返回该节点的地址，否则查找下一节点a1,依次类推。若表中不存在e,则返回NULL。算法描述：linkLocateElem(linkH,datatypee){linkp=H->next;while(p&&p->data!=e)p=p->next;return(p);//若p->data=x则返回指针p;否则p必为空，返回NULL}此算法的时间复杂度T(n)也为O(n)。3．前插即实现ListInsert(L,i,e)。讨论将x插入表中节点ai之前的情况。算法思路：调用算法GetElem(H,i-1)，获取节点ai-1的指针p(ai

之前驱)，然后申请一个q节点，存入e，并将其插入p节点之后。插入时的指针变化如图2.14所示。57单链表插入

图2.14算法描述：voidListLinsert(linkH,inti,datatypee){linkp,q;

if(i==0)p=H;elsep=GetElem(H,i-1);//取节点ai-1的指针

if(p==NULL)ERROR(i);//参数i出错

else{q=(link)malloc(sizeof(linknode))；//申请插入节点

q->data=e;//存入数据

q->next=p->next;//插入新节点

p->next=q;}}

此算法的时间主要花费在函数Getlist(H,i-1)上，故T(n)=O(n)，但插入时未引起元素的移动，这一点优于顺序结构的插入。58Ha0ai^anai-1Peq单链表删除4．删除即实现ListDel(L,i)。

图2.15

算法思路：同插入法，先调用函数GetElem(H,i-1),找到节点ai的前驱，然后如图2.15所示，将节点ai删除之。算法描述：VoidLdelete(linkH,inti) {linkp,q;if(i==0)p=H;elsep=GetElem(H,i-1);//求ai-1的地址

if(p&&p->next)//若p及p->next所在的节点存在

{q=p->next;p->next=q->next;free(q);}//删除

elseERROR(i);//参数i出错

}同插入法，此算法的T(n)=O(n)。59Ha0ai

ai-1Pai+1q例2-5将单链表倒置算法思路：依次取原链表中节点，将其作为新链表首节点插入H节点之后。

图.16算法描述：voidL1n-Ln1(linkH) {linkp,q;p=H->next;//令指针p指向节点a0 H->next=NULL;//将原链表置空

while(p){q=p;p=p->next; q->next=H->next;//将节点ai插入到头节点之后

H->next=q;}}60H248^H^2H42^H842^例2-6

设节点data域为整型，求链表中相邻两节点data值之和为最大的第一节点的指针。如图2.17所示的链表，它应返回值为4的节点所在的指针。算法思路：设p,q分别为链表中相邻两节点指针，求p->data+q->data为最大的那一组值，返回其相应的指针p即可。(本例应返回“4”的地址)算法描述：linkAdjmax(linkH) {linkp,p1,q;intm0,m1;p=H->next; p1=p;if(p1==NULL)return(p1);//表空返回

q=p->next;if(q==NULL)return(p1);//表长=1时的返回

m0=p->data+q->data;//相邻两节点data值之和

while(q->next) {p=q;q=q->next;//取下一对相邻节点的指针

m1=p->data+q->data; if(m1>m0){p1=p;m0=m1;}}//取和为最大的第一节点指针

return(p1);}61H26473^《数据结构》上机题（C语言程序）1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。例如输入：264730（0为结束符），建立：

所求结果=4

程序结构：类型说明； 建表函数：Creatlist(L);求值函数：Adjmax(L); main(){变量说明； 调用Creatlist(L)建表；调用Adjmax(L)求值； 打印数据；释放链表空间；

Y继续？

N

停止

}

62《数据结构》上机题1H26473^例2-7

设两单链表A、B按data值（设为整型）递增有序，设计算法，将表A和B合并成一表A，且表A也按data值递增有序。如图2.18：算法思路：设指针p、q分别指向表A和B中的节点，若p->data≤q->data则p节点进入结果表，否则q节点进入结果表。算法描述：voidMerge(linkA,linkB){linkr,p,q;p=A->next;q=B->next;free(B);r=A;while(p&&q) {if(p->data<=q->data){r->next=p;r=p;p=p->next;}else{r->next=q;r=q;q=q->next;}}if(p==NULL)p=q;r->next=p;}//收尾处理63A12A135^B2^4345^2.3.3单向循环链表

单向循环链表是单链表的一种改进，若将单链表的首尾节点相连，便构成单向循环链表结构，如图2.20所示:

若操作频繁在尾部进行，可设表尾指针R(省去H)。这样,为获得表尾an-1，取R->data即