【精品数据结构】数据结构1－3

1、数据结构 北京邮电大学自动化学院 杨福兴 电话E-mail: 2004年9月13日,使用教材： 严蔚敏 吴伟民 编著， 数据结构（C语言版），清华大学出版社 参考书： 1、曹桂琴 编著，数据结构基础，大连理工大学出版社。 2、晋良颖 编，数据结构，人民邮电出版社 3、Bruno R.Preiss，数据结构与算法，电子工业出版社,使用教材及参考书,许晓燕 负责班级：12班 电 话E-mail: 吴 魏 负责班级：34班 电 话：E-mail: wilson_ 徐 刚 负责班级：56班 电 话：

2、E-mail: 1,数据结构辅导老师名单,课程教学目的,在计算机及其应用的各个领域中，都会用到各种各样的数据结构，通过本课程使学生学会分析和研究计算机加工对象的特性，选择合适的数据结构和存储表示，以及编制相应的实现算法 课程教学基本要求:本课程介绍各种最常用的数据结构，阐述各种数据结构内涵的逻辑关系，讨论它们在计算机中的存储表示，以及在这些数据结构上的运算和实际的执行算法，并对算法的效率进行简要的分析和讨论。,数据结构的研究不仅涉及到 计算机硬件（特别是编码理论、存储装置和存取方法）的研究范围， 而且和计算机软件的研究有着密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配

3、问题。 在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。,课程介绍,因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。 程序算法数据结构 目前在我国，数据结构已经不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一。 通过对这门课程的学习可增强选择合适的数据结构与编写高效的程序的能力。,课程介绍,教学安排及考试,讲课学时：34学时 上机时间：5次（每次2学时） 考试成绩计算： 平时成绩（考勤、 作业及上机） 30分 考试（70分） 考查课和考试课分别考试，考查课在第17周考试，考试课按学校安排时间考试。,目

4、录,第1章 绪论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查找 第9章 内部排序 第10章 文件,计算机的应用已不再局限于科学计算，而更多地用于控制、管理及数据处理等非数值计算的处理工作。 与此对应，计算机加工处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据。 为了编写出一个“好”的程序，必须分析待处理的对象的特征以及各对象之间存在的关系，这就是“数据结构”这门学科形成和发展的背景。,第一章 绪 论,第一章 绪 论,1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算

5、法和算法分析,第一章 绪 论,一般来说，用计算机解决一个具体问题时，大致需要经多下列几个步骤： 首先要从具体问题抽象出一个适当的数学模型 然后设计一个解此数学模型的算法， 最后编出程序、进行测试、调整直至得到最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 然而，更多的非数值问题无法用数学方程描述。什么是数据结构呢？先看以下几个例子。,1.1 什么是数据结构,书目文件,例1 书目自动检索系统,例2 人机对奕问题,对于一个多叉路口，设计一个交通信号灯的管理系统。 首先需要分析一下所有车辆的行驶路线的冲突问题。 这个问题可以

6、归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。,例3 多叉路口交通灯管理问题,可通行方向 AB AC A D B A BC BD DA DB D C E A EB EC ED,例3多叉路口交通灯管理问题,有些通行方向显然不能同时进行，相应的结点间画一条连线。,AB,AC,AD,BA,BC,BD,DA,D B,DC,EA,EB,EC,ED,图1.2 交叉路口的图示模型,把图1.2中的结点进行分组，使得有结点相连的结点不在同一个组里。 地图着色问题 如果把上图中的一个结点理解为一个国家， 结点之间的连线看作两国有共同边界，上述问题

7、就变成著名的“着色问题”：即求出最少要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。 通过上面的分析，我们就获得了该交通管系统的数学模型。下面就可以着手进行算法的设计。,例3多叉路口交通灯管理问题,算法设计,2. “贪心法” while 有结点未着色； 选择一种新颜色； 在未着色的结点中,给尽可能多的彼此结点之间没有边点着色； ,1. 对n个结点，逐个测试其所有组合；,例3多叉路口交通灯管理问题,AB,AC,AD,BA,BC,BD,DA,D B,DC,EA,EB,EC,ED,图1.2 交叉路口的图示模型,AB,AC,AD,BA,BC,BD,DA,DB,DC,EA,EB,EC

8、,ED,着色结果,把上面方法应用于图1.2，得到下面的分组： 绿色：AB, AC, AD, BA, DC, ED 蓝色：BC, BD, EA 红色：DA, DB 白色：EB, EC,例3多叉路口交通灯管理问题,综上三个例子，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。 因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。 数据结构就是研究数据的逻辑结构和物理结构它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。,第一章 绪 论,数据(Data)

9、:是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。 数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 例如，例12中的“树”中的一个棋盘格局，例13中的“图”中的一个园圈都被称为一个数据元素。,1.2 基本概念和术语,一个数据元素可由若干个数据项组成。例如，例11中一本书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。 数据项是数据的不可分割的最小单位。 数据对象(Data O

10、bject)：是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N0，1，2，字母字符数据对象是集合C A，B，C，。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。,1.2 基本概念和术语,数据结构主要指逻辑结构和物理结构。数据之间的相互关系称为逻辑结构。通常分为四类基本结构： 一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树型结构 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。,1.2 基本概念

11、和术语,数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例 复数的数据结构定义如下： Complex=(C，R) 其中：C是含两个实数的集合C1，C2，分别表示复数的实部和虚部。R=P，P是定义在集合上的一种关系C1，C2。,1.2 基本概念和术语,数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。 数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示 由此得出两种不同的存储结构：顺序存储结构和链式存储结构 顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

12、链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。,1.2 基本概念和术语,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,1.2 基本概念和术语,数据类型：数据类型是一个值的集合和定义在这个值集范围上的一组操作的总称。例如，C语言中的整型变量，其值集为某个区间上的整数，定义在其上的操作为：加、减、乘、除和取模等算术运算。 按“值”的不同特性，高级程序语言中的数据类型可分为： 一类是非结构的原子类型。原子类型的值是不可分解的。如：C语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。 另一类是

13、结构类型。结构类型的值是由若干成分按某种结构组成的。例如数组的值由若干分量组成。每个分量可以是整数，也可以是数组等。,1.2 基本概念和术语,抽象数据类型：一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。 抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。 和数据结构的形式定义相对应，抽象数据类型可用三元组描述如下：（，） D是数据对象，S是D上的关系集，P是对D的基本操作集。,1.2 基本概念和术语,

14、本书采用以下格式定义抽象数据类型 抽象数据类型的定义： ADT抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名 基本操作的定义格式为：基本操作名（参数表）初始条件： 操作结果：,1.2 基本概念和术语,抽象数据类型三元组的定义： ADT Triplet 数据对象：D=e1,e2,e3|e1,e2,e3ElemSet 数据关系：R1=, 基本操作： InitTriplet(,1.3 抽象数据类型的表示和实现,（2）数据结构的表示用类型定义（typedef）描述。数据元素类型约定为Elemtype，由用户在使用该数据类型时定义。 （3）基本操作的算法都用以下形式的函数描述：

15、 函数类型 函数名（函数参数表） /算法说明 语句序列 /函数名,1.3 抽象数据类型的表示和实现,（4）赋值语句有 简单赋值 变量名=表达式； 串值赋值 变量名1=变量名2=表达式 成组赋值 （变量名1，。，）=（表达式1，） 交换赋值 变量名 变量名 条件赋值 变量名=条件表达式？表达式T：表达式F,1.3 抽象数据类型的表示和实现,（5）选择语句有 条件语句1 if（表达式）语句； 条件语句2 if（表达式）语句； Else 语句 开关语句1 switch(表达式 ) case 值1：语句序列1；break; Default: 语句序列n+1; 开关语句2 switch case 条件1

16、：语句序列1；break; Default: 语句序列n+1;,1.3 抽象数据类型的表示和实现,（6）循环语句有 For语句 for（赋初值表达式；条件；修改表达式序列）语句； While 语句 while（条件）语句； do-while语句 do 语句序列while（条件）；,1.3 抽象数据类型的表示和实现,（7）结束语句 函数结束语句 return 表达式； return； Case结束语句 break; 异常结束语句 exit(异常代码) 8）输入和输出语句 输入语句 scanf(格式串，变量1，变量n)； 输出语句 printf(格式串，表达式1，表达式2)；,1.3 抽象数据类型

17、的表示和实现,（9）注释 单行注释/文字序列 （10）基本函数有 求最大值 max(表达式1，表达式n） 求最小值 min(表达式1，表达式n） 求绝对值 abs(表达式) 求不足整数值 floor（表达式） 判定行结束 eoln（文件变量）或eoln,1.3 抽象数据类型的表示和实现,（11）逻辑运算约定 与运算i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作T(n)=O(f(n) 它表示随着问题规模n的增加，算法执行时间的增长率

18、和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。,例1，在如下所示的两个矩阵相乘的算法中，“乘法”运算是“矩阵相乘问题”的基本操作。,显然，被称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。 语句的频度是指的是该语句重复执行的次数。 例 +x;s=0; 将x自增看成是基本操作，则语句频度为，即时间复杂度为(1)。 如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。,3、 算法效率的度量,例、for(i=1;i=n;+i) +x;s+=x;

19、语句频度为：2n 其时间复杂度为：O(n) 即时间复杂度为线性阶。 例、for(i=1;i=n;+i) for(j=1;j=n;+j) +x;s+=x; 语句频度为：2n2 时间复杂度为：O(n2) 即时间复杂度为平方阶。,3、 算法效率的度量,定理：若A(n)=amnm +am-1nm-1 +a1n+a0是一个m次多项式，则A(n)=O(nm)。证略。 例for(i=2;i=n;+I) for(j=2;j=i-1;+j) +x;ai，j=x; 语句频度为：1+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为O(n2), 即此算法的时间

20、复杂度为平方阶。,3、 算法效率的度量,以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn),当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,3、 算法效率的度量,有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如： Void bubble-sort(int a，int n) for(I=n-1;change=TURE;I1 chan

21、ge=TURE 最好情况：0次 最坏情况：1+2+3+n-1=n(n-1)/2 平均时间复杂度为:O(n2) 在本书以后各章节中讨论的时间复杂度，除特别指明外，均指最坏情况下的时间复杂度。,3、 算法效率的度量,类似于算法的时间复杂度，本书中以空间复杂度作为算法所需存储空间的量度，记作: S(n)=O(f(n) 其中n为问题的规模(或大小)。 一个上机执行的程序除了需要存储空间来寄存本身所用指令、常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。,4、算法的存储空间需求,线性结构的特点：在数据元素中的非空有限集中 （1）存在唯一的一个被称作“第一

22、”的数据元素； （2）存在唯一的一个被称作“最后一个”的数据元素； （3）除第一个外，集合中的每一个数据元素均只有一个前驱； （4）除最后一个外，集合中的每一个数据元素均只有一个后继。,第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 一元多项式的表示及相加,第二章 线性表,1、线性表 线性表(Linear List) ：一个线性表是n个数据元素的有限序列。例如： 例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、某校从1999年到2003年各种型号的计算机拥有量的变化情况。 （6，17，28，50，92，188）,2.

23、1 线性表的类型定义,在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称为文件。 例3、学生健康情况登记表如下：,1、线性表,综合上述三个例子可见，线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特征，即属同一数据对象，相邻数据元素之间存在着序偶关系。若将线性表记为： (a1，,a i-1，ai，a i+1,an) 则表中ai-1领先于ai，ai领先于a i+1 ，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。 当i=1,2,n-1时，ai有且仅有一个直接后继，当i=2,3,n时， ai有且仅

24、有一个直接前驱。 线性表中的元素的个数n(n 0)定义为线性表的长度，n=0时称为空表。,1、线性表,ADT List 数据对象：=ai|aiElemSet，i=1,2,n,n0 数据关系：R1=| ai-1,ai, D,i=2,n 基本操作： InitList(/当前长度 int ListSize; Sqlist;,在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。 注意：C语言中的数组下标从“0”开始，因此，若L是Sqlist类型的顺序表，则表中第i个元素是L.datai-1。 顺序表上基本运算 1、 顺序表的初始化 2、 插入运算 3、 删除运算 4、 按

25、值查找,二、顺序表上实现的基本操作,线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表: (a1，a2，. ，ai-1，ai，ai+1，. ，an) 成为表长为 n+1 表: (a1，a2，.，ai-1，x，ai，ai+1，.，an) 。 i 的取值范围为1=i=n+1 。 顺序表上完成这一运算需要通过以下步骤进行： (1) 将aian 顺序向下移动，为新元素让出位置； (2) 将 x 置入空出的第i个位置； (3) 修改 last 指针(相当于修改表长)，使之仍指向最后一个元素。,1、插入,x,算法2.3 Status ListInsert_Sq(SqLi

26、st / 增加存储容量 ,算法2.3 q= /IistInsert_Sq,算法的复杂度 这里的问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。 当=n时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）； 当=1时，结点后移语句将循环执行n次，需移动表中所有结点，这是最坏情况，其时间复杂度为O（n）。 由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度。,在长度为n的线性表中第i个位置上插入一个结点，令Eis(n)表示移动结点的期望值（即移动的平均

27、次数），则在第i个位置上插入一个结点的移动次数为n-i+1。故 不失一般性，假设在表中任何位置(1in+1)上插入结点的机会是均等的，则 p1=p2=p3=pn+1=1/(n+1) 因此，在等概率插入的情况下，,也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长 n较大时，算法的效率相当低。虽然Eis(n)中n的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为O(n)。,线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，an) 变成长度为n-1的线性表 (a1，a i-1，a i+1，an) 顺序表上

28、完成这一运算的步骤如下： (1) 将ai+1an 顺序向前移动。 (2) 修改last指针(相当于修改表长)使之仍指向最后一个元素。,2、删除,算法2.4 Status ListDelete_Sq(SqList /IistDelete_Sq,该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。 假设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素次数的期望值（平均次数）为： 不失一般性，假设在表中任何位置上删除结点的机 会是均等的，则 qi=1/n 因此，在等概率插入的情况下， 也就是说，在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间

29、复杂度也是O(n)。,4、算法的存储空间需求,线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的数据元素。 由于顺序表需要一组地址连续的存储单元，对于长度可变的线性表就需要预分配足够的空间，有可能使一部分存储空间长期闲置不能充分利用。 也可能由于估计不足，当表长超过预分配的空间而造成溢出，在这种情况下，又难于扩充连续的存储空间。 为了克服上述缺点，我们将谈论线性表的另一种存储方式链式存储结构，简称为链表(Linked List)。,2.3 线性表的链式表示和实现,线性表的链式存储的特点是指用一组任

30、意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。 为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分信息组成了元素ai的存储映象，称为结点，它包括两个域： 其中：data域是数据域，用来存放结点的值。 next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。,2.3.1 线性链表,链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。

31、n个结点（ai( 1=i=n）的存储映象）连接成一个链表，即为线性表(a1,a2,an) 的链式存储结构。由于上述链表的每一个结点只有一个链域，故将这种链表称为单链表（Single Linked)。 链表中每个结点的存储地址是存放在其前驱结点next域中，而开始结点无前驱，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为空，即NULL（图示中也可用表示)。 通常我们把线性链表画成用箭头相连接的节点序列，其中箭头表示链域中的指针。,2.3.1 线性链表,设h是指向链表的头指针，p是指向链表中的某一结点的指针，可以说明如下：JD *h,*p; p及其指向的节点关系如

32、图所示。图中 （*p）表示由指针所指向的节点。 (*p).datap-data表示p指向结点的数据域 (*p).linkp-link表示p指向结点的指针域,由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述： typedef struct LNode Elemtype data; struct LNode *next; LNode,*Linklist , JD;,若L为“空”（L=NULL），则所表示的线性表为“空”表，其长度n为“零”。,h,1145,1248,头结点,2158 ,.,例如在上图中，h-data=1012 (h-link)-data=1145 (*h).d

33、ata=1012,p为动态变量，它是通过标准函数生成的，即 p=(listnode*)malloc(sizeof(listnode); 函数malloc分配了一个类型为listnode的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点变量不再需要了，又可通过标准函数free(p) 释放所指的结点变量空间。,1012,指针变量p（其值为结点地址）和结点变量*p之间的关系。 p结点是指指针p所指向的结点（即其存储位置存放在p中的结点）。 假设p是指向线性表中第i个数据元素（结点ai）的指针，则p-next是指向第i+1个数据元素（结点ai+1）的指针。 换句话说，若p-data=ai

34、，则p-next-data=ai+1。由此，在单链表中，取得第i个数据元素必须从指针出发寻找，因此，单链表是非随机存取的存储结构。,赵,钱,孙,李,周,吴,郑,王,H,例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG),43,13,1,NULL,37,7,19,25,数据域,指针域,李,钱,孙,王,吴,赵,郑,周,存储地址,1,7,13,19,25,31,37,43,头指针,假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符n为输入结束标记。动态地建立单链表的常用方法有如下两种： 1、头插法建表 该方法从一个空表开始，重复读入数据，生

35、成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,一、建立单链表,linklist createlistf(void) char ch; linklist head; listnode *p; head=null; ch=getchar( ); while (ch!=n p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=head; head=p; ch=getchar( ); return (head); ,listlink createlist(int n) int data; l

36、inklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d， ,2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。 若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。例：,linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL;r=N

37、ULL; while(ch=getchar( )!=n) p=(listnode *)malloc(sizeof(listnode); pdata=ch; if(head=NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); ,说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前驱结点的指针域中。算法中的第一个if语句就是用来对第一个

38、位置上的插入操作做特殊处理。算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表head是空表，尾指针r亦为空，结点*r不存在；否则链表head非空，最后一个尾结点*r是终端结点，应将其指针域置空。,如果我们在链表的开始结点之前附加一个结点，并称它为头结点，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理； b、无论链表是否为空，其头指针是指向头结点 的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。,其算法如

39、下： linklist createlistr1( ) char ch; linklist head=(linklist)malloc(sizeof(listnode); listnode *p，*r; r=head; while(ch=getchar( )!=n p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=NULL; return(head); ,上述算法里动态申请新结点空间时未加错误处理，可作下列处理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL)

40、error(No space for node can be obtained); return ERROR; 以上算法的时间复杂度均为O(n)。,1、按序号查找 在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第0 个结点，其算法如下：,二、查找运算,Listnode * getnode(linklist head ， int i)

41、 int j; listnode * p; p=head; j=0; while(pnext ,2、按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。其算法如下： Listnode * locatenode(linklist head，int key) listnode *p=headnext; while( p 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为O(n)。,插入运算是将值为

42、x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*s，并令结点*s的指针域指向新结点，新结点的指针域指向结点ai，p结点的指针域指向新结点s，从而实现三个结点ai-1，x和ai之间的逻辑关系的变化，插入过程如：,s-link=p-link;,p-link=s;,三、插入运算,具体算法如下： void insertnode(linklist head，datetype x，int i) listnode * p，*q; p=getnode(head，i-1); if(p=NULL) error(posi

43、tion error); s=(listnode *)malloc(sizeof(listnode); sdata=x; snext=pnext; pnext=s; ,s-link=p-link;,p-link=s;,设链表的长度为n，合法的插入位置是1in+1。 注意当i=1时，getnode找到的是头结点， 当i=n+1时，getnode找到的是结点an。 因此，用i-1做实参调用getnode时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作getnode上，故时间复杂度亦为O(n)。,删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前驱结点 a i-1

44、的指针域next中，所以我们必须首先找到a i-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。,p-link=p-link-link;,四、删除运算,具体算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; ,设单链表的长度为n，则删去第i个结点仅当1in时是

45、合法的。注意，当i=n+1时，虽然被删结点不存在，但其前驱结点却存在，它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在，仅当*p存在（即p!=NULL）且*p不是终端结点 （即pnext!=NULL）时，才能确定被删结点存在。 显然此算法的时间复杂度也是O(n)。 从上面的讨论可以看出，链表上实现插入和删除运算，无须移动结点，仅需修改指针。,1、在头指针为h的带表头结点的单链表中，把结点b插入到a结点之前，若不存在结点a就把结点b插入到表尾。 插入过程： 找到结点a时，p指向结点，q指向结点a的直接前驱结点。 首先生成一个s结点，将s结点的数据域置为b，然后修改相应的指

46、针，把结点a作为s结点的直接后继，把s结点作为q结点的直接后继。,五、链表的其他运算示例,Void dlbqcr(JD *h,int a,int b) /在头指针为h的带表头结点的单链表中结点a之前插入结点b，若表中无结点a，则插到表尾 JD*p,*q,*s; s=(JD*)malloc(sizeof(JD); s-data=b; p=h-link;q=h; While(p-data!=a/表中无结点a，则插到表尾,2、设线性表的n个数据元素依次存放在一维数组an中，请建立一个带表头结点的单链表，h为新建单链表的指针。 要建立一个带表头结点的单链表，首先生成一个h结点作为表结点，其链域置为“空

47、”。 在生成一个s结点，将其数据域置为第n个数据元素，链域置为“空”。s结点作为表中第一个结点。 顺次生成新的s结点，置其数据域为第i个数据元素(i=n-1,n-2,2,1)，修改有关指针：把表中第一个结点作为s结点的直接后继，s结点作为表中第一个结点。即把含第i个数据元素的结点插入到表中第一个结点之前。,JD*DLBJL(INT A,INTN) /线性表中的n个数据元素存入一维数组a中，建立一个带表头结点的单链表，其头指针为h JD *S,*h; Int i; h=(JD*)malloc(sizeof(JD); h-data=0;h-link=NULL; For(i=n;i0;i-) s=(

48、JD*)mallic(sizeof(JD); s-data=ai-1; s-link=h-link; h-link=s; return(h);,3、设h是带表头结点的单链表的头指针，请设计一个逆置这个单链表的算法。 建立逆表的方法是：顺序扫描原表，依次将原表中的结点逐个插入到第一个结点之前，可得到逆置链表。 设s指向当前逆转结点，p指向s结点的直接后继结点。 Void dlbnz(JD*h) JD*s,*p; p=h-link;/ *p先指向原表中第一个结点 h-link=NULL;/逆表的初态为空表 While(p!=NULL) s=p;/ *s指向当前逆转的结点 p=p-link; s-l

49、ink=h-link; h-link=s;/把s结点插入到逆表,4、设pa，pb分别为两个按升序排列的单链表的头指针，请设计一个算法把这两个单链表合并为一个按升序排列的单链表。 合并的方法是：从两表的第一个结点开始顺链逐个将对应数据元素进行比较，复制小者并插入c表尾。当两表中之一已到表尾，则复制另一链表的剩余部分，插入到c表尾。 /JD*dlnhb(JD *pa, JD*pb) /把pa、pb为头指针的按升序排列的单链表合并成一个按升序排列的单链表。 JD *p,*q;*pc; pc=(JD)malloc(sizeof(JD); p=pc;,While(pa!=NULL ,While(pa!=

50、NULL) q=(JD*)malloc(sizeof(JD); q-data=pa-data; pa=pa-link; p-link=q; p=q; While(pb!=NULL) q=(JD*)malloc(sizeof(JD); q-data=pb-data; pb=pb-link; p-link=q; p=q; p-link=NULL p=pc; pc=p-link; free(p) return(pc);,循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。 单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点或开始

51、结点，就得到了单链形式的循环链表，并简单称为单循环链表。 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：,2.3.2 循环链表, 非空表, 空表,在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)。,在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext) next和rear，显然，查找

52、时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。 由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。,例、在链表上实现将两个线性表(a1，a2，a3，an)和(b1，b2，b3，bn)链接成一个线性表的运算。 JD * xhblj(JD *ha,JD *hb); /ha，hb为两个带头结点的循环链表的尾指针，把hb表连在ha表之后 JD *q,*p q=hanext; p=hbnext; hanext=pnext; /a、b两个线性表尾首相连 hbnext=q;/ a、b

53、两个线性表首尾相连 ha=hb; free(p);/释放hb表头结点 ,单链表有一个很大的缺点：它只能顺着直接后继指针向后查找其他结点，如若找某结点的直接前驱结点，只能从表头指针开始查找。换句话说，在单链表中，NextElem的执行时间为O(1)，而PriorElem的执行时间为O（n）。 为了克服单链表这种单向性的缺点，双向链表可有效解决这个问题。 双向链表(Double linked list):在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。这样形成的链表中就有两个方向不同的链，故称为双向链表。,2.3.3双链表,typedef struct node datatype

54、element; struct node *prior,*next; JD;,非空双向循环链表：,p-prior-next= p= p-next-proir;,双向链表（double linked list） 结点定义,和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为双向链表。 设指针p指向某一结点，则双向链表结构的对称性可用下式描述： (pprior)next=p=(pnext)prior 即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放 在它的后继结点*(pnex

55、t)的直接前趋指针域中。 在双链表中，有些操作如：ListLength、GetElem和LocateElem等仅需要涉及一个方向的指针，则它们的算法描述和线性链表的操作相同，但在插入和删除操作时有很大的不同，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(n)。,（1）插入,void sxlbcr(JD*p,int x) JD *s;s=(JD *s) malloc (sizeof(JD); sdata=x; sprior=p-prior;/1步 p-prior-next=s;/2步 snext=p;/3步 pprior=s; /4步 ,（2）删除,p-pri

56、or-next=p-next;,p-next-prior=p-prior;,void ddeletenode(dlistnode *p) ppriornext=pnext; pnextprior=pprior; free(p); ,从本节的讨论中可见：由于链表在空间的合理利用上和插入、删除时不需要移动等优点，因此在很多场合下，它是线性表的首选存储结构。 然而它也存在着实现某些基本操作如求线性表长度时不如顺序存储结构的缺点；另一方面，由于在链表中，节点之间的关系用指针来表示，则数据元素在线性表中的“位序”的概念已淡化，而被数据元素在线性表链表中的“位置”所代替。 为此，从实际应用角度出发重新定义

57、线性链表及其基本操作（见P3738）。,4、算法的存储空间需求,多项式的运算问题，已经成为表处理的一个经典问题。通常一个多项式Pn(x)可按升密写成：,2.4一元多项式相加,它由n+1个系数唯一确定。在计算机里，它可用一个线性表P来表示：,每一项的指数i隐含在其系数pi的序号里。 假设Qm(x)是一元m次多项式，同样可用线性表Q来表示：,假设mn,则两个多项式相加的结果Rn(x)=Pn(x)+Qm(x)可用线性表R表示:,我们可以对P、Q和R采用顺序存储结构,使得多项式相加的算法定义十分简洁。,至此，一元多项式的表示及相加问题似乎已经解决。然而，在通常的应用中，多项式的次数可能很高且变化很大，

58、使得顺序存储结构的最大长度很难确定。特别是在处理式的次数可能很高且变化很大，使得顺序存储结构的最大长度很难确定。特别是在处理形如：,2.4一元多项式相加,的多项式时，就要用一长度为20001的线性表来表示，表中仅有3个非零元素，这种对内存空间浪费应当避免。 但是如果只存储非零系数项，显然必须同时存储相应的指数。 一般情况下的一元n次多项式可写成：,其中，pi是指数为ei的项的非零系数，且满足：,若用一个长度为m且为每个数据元素有两个数据项（系数项和指数项）的线性表,2.4一元多项式相加,便可唯一确定多项式Pn(x)。在最坏情况下，n+1(=m)个系数都不为零，则比只存储每项系数的方案要多一倍的数据。但是，对于S(x)类的多项式，这种表示将大大节省空间。 对应于线性表的两种存储结构，由上式定义的一元多项式也可以有两种存储表示方法。在实际的应用程序中取用哪一种，则要