数据-教材课件汇总完整版ppt全套课件最全教学教程整本书电子教案全书教案合集最新课件汇编

1、1第1章 绪 论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 数据抽象和抽象数据类型1.4 算法描述与分析 小结 习题一 2 教学安排课时：2学时难点：时间的渐进复杂度（语句频度）计算重点：数据结构基本概念、算法分析教学方法：多媒体教学，通过大量实例讲解基本的概念和语法习题：见课件后习题31.1 什么是数据结构 数据结构的重要性： （1）考研的必考科目，很多大的软件公司面试必考内容。 （2）专业基础课（学位课程），有承上启下的作用。 先修课程： 计算机基础、C语言程序设计、离散数学 后继课程： 操作系统（队列、存储管理表、目录树） 数据库原理（线性表、多链表、索引树） 编译原理（栈

2、、哈希表、语法树） 人工智能（广义表、集合、搜索树、有向图） 41.1 什么是数据结构 在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直至得到正确结果。所谓数学模型一般指具体的代数方程等。然而，有些实际问题无法用数学方程表示。现在来分析几个这方面的典型实例，它们的主要特点是处理数据信息的存储与检索等，而不是单纯的数值计算。例如：图书档案类问题、棋类对奕问题、交通或通信网问题。5表1.1 学 籍 表 首先分析图书目录卡或学籍档案类问题。设一个班级有30个学生，这个班级的学籍表如表1.1所示。 1.1 什么是数据结构6 我们可以

3、把每个学生的信息看成一个记录，表中的每个记录又由7个数据项组成。该学籍表由30个记录组成，记录之间是一种顺序关系。这种表通常称为线性表，数据之间的逻辑结构称为线性结构，其主要操作有检索、查找、插入或删除等。 对于这些运算，显然是由计算机来完成，这就要设计相应的插入、删除和修改的算法。也就是说，数据结构还需要给出每种结构类型所定义的各种运算的算法。 通过以上讨论，我们可以直观地认为：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。 1.1 什么是数据结构7 1数据 数据是描述客观事物的数值、字符以及能输人机器且能被处理的各种字符的集合，即数据就是计算机化的信息。换句话

4、说，数据就是对客观事物采用计算机能够识别、存储及处理的形式所进行的描述。 在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并 被计算机程序处理的信息，包括文字、表格、图像等，统称为数据。例如，一个学生成绩管理程序所要处理的数据，如表1.1所示。 1.2 基本概念和常用术语 8表1.1 学生成绩表学号姓名数据结构大学物理高等数学平均成绩0232101王刚959085900232102李娟908085850232103赵平999591950232104王强867084800232105张雪929184891.2 基本概念和常用术语 9 2数据元素 数据元素也叫结点，它是组成数据的基

5、本单位，是一个数据整体中相对独立的单元。例如，在表1.1所示的学生成绩中，为了便于处理，把其中的每一行（代表一个学生成绩）作为一个基本单位来考虑，故该数据由五个结点构成。 一般情况下，一个结点还可以分割成若干具有不同属性的字段(也叫数据项)。例如，在表1.1所示的表格数据中，每个结点都由学号、姓名、数据结构、大学物理、高等数学和平均成绩六个字段构成。字段是构成数据的最小单位。 1.2 基本概念和常用术语 10 3数据对象 在数据结构中，将性质相同的数据元素的集合称之为数据对象，它是数据的一个子集。上例：一个班级的学生成绩表可以看作一个数据对象。 4数据结构 数据结构由某一数据元素集合及该集合中

6、所有数据元素之间的关系组成。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构、数据的存储结构和对数据所施加的操作。 1.2 基本概念和常用术语 11 根据数据结构中数据元素之间的结构关系的不同特征，通常将数据结构分为如下四种基本结构： （1）集合结构（set）：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。元素顺序是随意的。 （2）线性结构（linear）或称序列（sequence）结构：数据元素的有序集合。数据元素之间形成一对一的关系。 （3）树形结构（tree）：树是层次结构，树中数据元素之间存在一对多的关系。 （4）图形结构（graph）：图中数据元

7、素之间的关系是多对多的。 1.2 基本概念和常用术语121.2 基本概念和常用术语13 5逻辑结构 结点和结点之间的逻辑关系称为数据的逻辑结构。 数据结构从逻辑结构划分为: （1）线性结构。元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。见图1.1中的(b)。 （2）非线性结构。元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。见图1.1中的（c）和（d） （3）集合结构。元素之间无任何关系，元素的排列无任何顺序。见图1.1中（a）。 1.2 基本概念和常用术语14 6存储结构 数据的逻辑结构是独立于计算机

8、的，它与数据在计算机中的存储无关，要对数据进行处理，就必须将数据存储在计算机中。数据在计算机中的存储方式称为数据的存储结构。数据的存储结构主要有4种。 （1）顺序存储 （2）链式存储 （3）索引存储 （4）散列存储 1.2 基本概念和常用术语15 7数据处理 数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等操作的过程。 8数据类型 数据类型是指程序设计语言中各变量可取的数据种类，它是高级程序设计语言中的一个基本概念，和数据结构的概念密切相关。 8算法 简单地说，算法就是解决特定问题的方法。特定问题可以是数值的，也可以是非数值的。 解决数值问题的算法叫做数值算法 。数据处理

9、方面的算法都属于非数值算法 。 1.2 基本概念和常用术语16 1.3.1 数据抽象 抽象（abstraction）可以被理解为一种机制，其实质是抽取共同的和实质的东西，忽略非本质的细节。抽象可以使我们的求解问题过程以自顶向下的方式分步进行:首先考虑问题的最主要方面，然后再逐步细化，进一步考虑问题的某些细节，并最终实现之。 数据的抽象经历了三个发展阶段： 第一个发展阶段是从无类型的二进制数到基本数据类型的产生。 第二个发展阶段是从基本数据类型到用户自定义类型的产生。 第三个发展阶段是从用户自定义类型到抽象数据类型的出现。 1.3 数据抽象和抽象数据类型 17 1.3.2 抽象数据类型 抽象数据

10、类型(Abstract Data Type，简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。 1.3 数据抽象和抽象数据类型 18 1.3.3 抽象数据类型描述和实现 抽象数据类型形式化定义可以用以下三元组表示 ADT（D，S，P）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 抽象数据类型描述的一般形式如下： ADT 抽象数据类型名称 数据对象： 数据关系： 操作集合： 操作名1： 操作名n：ADT抽象数据类型名称 1

11、.3 数据抽象和抽象数据类型 19 1.4.1 算法及其性能标准 算法具有五个基本特征： 有穷性，算法的执行必须在有限步内结束。 确定性，算法的每一个步骤必须是确定的无二义性的。 输入，算法可以有0个或多个输入。 输出，算法一定有输出结果 可行性，算法中的运算都必须是可以实现的。 1.4 算法和算法分析 20 衡量一个算法的性能，主要有以下几个标准: 正确性（corectness）:算法的执行结果应当满足预先规定的功能和性能要求。 简明性（siplcty）:一个算法应当思路清晰、层次分明、简单明了、易读易懂。 健壮性（robustness）:当输入不合法数据时，应能做适当处理，不至于引起严重后

12、果。 效率（efecency）:有效使用存储空间，井有高的时间效率。 1.4 算法和算法分析 21 1.4.2 算法时间复杂度和渐近时间复杂度 衡量算法的二种方法：事前分析、事后测试 如何估算算法的时间效率？和算法执行时间相关的因素如下： （1）算法所用的“策略”。 （2）算法所解决问题的“规模”。 （3）编程所用的“语言”。 （4）“编译”的质量。 （5）执行算法的计算机的“速度”。 *后三条受到计算机硬件和软件的制约，“估算”只需考虑前两条。1.4 算法和算法分析 22 1.4.2 算法时间复杂度和渐近时间复杂度 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它

13、是n的某一函数T(n)称为这一算法的“算法时间复杂性”。 一个算法的“运行工作量”通常是随问题规模的增长而增长，因此比较不同算法的优劣主要应该以其“增长的趋势”为准则。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作： 称T(n)为算法的(渐近)时间复杂度。换句话说，当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。 1.4 算法和算法分析 23 在实际研究中，我们使用语句频度的数量级来衡量一个算法的时间复杂度。语句的频度（frequency count）指的是该语句重复执行的次数，下面举一个例子介绍时间复杂度的估算方法。 例1 二层for

14、循环的时间复杂度 sum=0； for(i=1;i=n;i+) for(j=1;j=n;j+) sum+； 解：语句1的频度是1 语句2的频度是n1 语句3的频度是n(n+1) 语句4的频度是n2 该程序的时间复杂度T(n)=2n2+2n+2 =O(n2) 1.4 算法和算法分析 24 又如下列三个程序段：(a) x=x+1;(b) for(i=1; i=n; i+) x=x+1;(c) for (j=1; j=n; j+) for (k=1; k=n; k+) x=x+1; 现把它们看成三个简单的算法，在三个算法中语句x=x+1的频度分别为1； n； n2； 1.4 算法和算法分析 那么算法

15、(a)，(b)，(c)的时间复杂度分别记作： T(n)=O(1) ； T(n)=O(n) ； T(n)=O(n2 )。251.4 算法和算法分析 算法描述如下：void simsort( arr a , int n ) /*n和数组a的数据由主调函数提供*/ for (i=0; in-1; i+) for (j=i+1; jn; j+) if (ai.data aj.data) m=ai; ai=aj; aj=m; for (i=0; in; i+) printf(n %8d %8d %10d, i, ai.num, ai.data); 26 现在来分析上述算法的时间复杂度。算法中有一个二重循

16、环，if语句频度为 即：n2/2 + n/2。现在试着忽略低次幂项n/2，只剩n2/2。然后再忽略n2/2项的常数系数1/2，本项的数量级就为n2。而算法中输出语句的频度为n，数量级显然为n。该算法的时间复杂度以最大语句频度if语句的频度n2来估算，即不考虑算法中其他语句频度，则记作： T(n)=O(n2) 1.4 算法和算法分析 27 由上述各个例题可见，随着问题规模n的增大，其时间消耗T(n)也在增大。 通常将这些时间复杂度分别称为常量阶O(1)，线性阶O(n)和平方阶O(n2)，算法还可能呈现的时间复杂度有指数阶和对数阶O(lbn)（log2n）等。研究算法的时间复杂度，目的是研究随着问

17、题规模n的逐渐增大，时间消耗的增长趋势(很快、缓慢、很少)。不同数量级时间复杂度的性状如图1.3所示。 1.4 算法和算法分析 28图1.3 各种数量级的时间复杂度 1.4 算法和算法分析 29 从图1.3中可见，随着问题规模的增大，其时间消耗也在增大，但它们的增长趋势明显不同。假设对同一个问题的解决，设计两种不同的算法A和B，算法A的时间复杂度为O(n2)，算法B的时间复杂度为O(lbn)。随着问题规模n的增大，算法A所消耗时间将会迅速增大，而算法B所消耗时间的增大趋向平缓，即增长比较慢。显然，在问题的规模n很大时算法B运行效率高，可以认为算法B优于算法A。 1.4 算法和算法分析 30 1

18、.4.3 算法的空间复杂度 一个程序的空间复杂度(space complexity)是程序运行从开始到结束所需的存储量。 程序运行所需的存储空间包括两部分： （1）固定部分(fxed space requirement)：它主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。 （2）可变部分(varible space requirement)：包括数据元素所占的空间，以及算法执行所需的额外空间，如递归栈所用的空间。 1.4 算法和算法分析 31 数据结构应讨论数据的逻辑结构、存储结构以及在数据结构上定义的一组运算和实现这些运算的算法。数据结构上的运算是在逻辑结构上定义的，而只有当

19、存储结构确定后才能给出其实现的算法。本章介绍的使用抽象数据类型描述数据结构的方式将贯穿全书。一个数据结构的ADT描述是用户使用数据结构的规范，它应严格定义，它的实现与使用分离，实行封装和信息隐蔽。数据结构的实现必须严格符合其ADT规范，这是程序设计的基本原则之一。本章最后介绍的算法效率和算法分析的基本方法将在以后各章中用以分析算法的时间和空间效率。 小 结 32 1. 简述下列术语的含义:数据、数据元素、逻辑结构、存储结构、线性数据结构和非线性数据结构。 2. 什么是数据结构?有关数据结构的讨论应包括哪些方面? 3. 什么是算法？算法的主要特点是什么？ 4. 如何评价一个算法？ 5. 什么是算

20、法的时间复杂度和空间复杂度？ 6. 确定下列各程序划线语旬的执行次数，计算它们的渐近时间复杂度。 习 题 一 33 （1）i=l; k=O; do k=k+l0*i;i+; wh1e(i=n-l); （2）i=l; x=O; do x+; i=2*i; while(in); （3）for(int i=l; i=n; i+) for(int j= 1; j=i; j+ ) for (int k=l; k=(y+l)*(y+1) y+; 习 题 一 34第2章 线性表 1.1 线性表概念 1.2 基本概念和术语 1.3 数据抽象和抽象数据类型1.4 算法描述与分析 小结 习题一 2.1 线性表概念

21、 线性表是由n（n1）个类型相同的数据元素组成的有限序列，通常表示成下列形式: L = (a1，a2，.，ai1，ai，ai+1 ，.，an)其中:L为线性表名称， ai为组成该线性表的数据元素。 线性表中数据元素的个数被称为线性表的长度，当n=O时，线性表为空，又称为空线性表。 设ai是表中第i个元素，i=1，2，n-1，我们称ai是ai1的直接前驱元素，ai1是ai的直接后继元素。在线性表中，除a1无直接前驱外，其余元素有且仅有一个直接前驱；除an无直接后继外，其余元素有且仅有一个直接后继。 3536线性表的抽象数据类型定义如下： ADT List数据元素：D=ai| aiD0, i=1,

22、2,，n ， n0 ，D0为某一数据对象关系：R1 | ai, ai-1D，i=2, ,n基本操作：（1）InitList（&L）操作前提：L为未初始化线性表。操作结果：将L初始化为空表。（2）DestroyList(&L)操作前提：线性表L已存在。操作结果：将L销毁。2.1 线性表概念37（3）ClearList(&L)操作前提：线性表L已存在 。操作结果：将表L置为空表。（4）EmptyList（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。（5）ListLength（L）操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）L

23、ocate(L,e)操作前提： 表L已存在，e为合法元素值。操作结果： 如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。2.1 线性表概念38（7）GetData(L,i)操作前提：表L存在，且i值合法，即1iListLength(L)操作结果：返回线性表L中第i个元素的值。（8）ListInsert (&L,i,e)操作前提：表L已存在，e为合法元素值且iListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1。（9）ListDelete(&L,i,&e)操作前提：表L已存在且非空， 1iListLength(L)。操作结果：

24、删除L的第i个数据元素，并用e返回其值，L的长度减1。ADT List 2.1 线性表概念39 在上述的操作运算中，最基本最重要的是插入、删除。线性表的其他复杂操作和运算还有：对有序表的插入和删除；按某种要求重排线性表中各元素的顺序；按某个特定值查找线性表中的元素；两个线性表的合并等。2.1 线性表概念40 2.2.1 线性表的顺序存储结构 在计算机内，可以用不同的方法来存储数据信息，最常用的方法是顺序存储。顺序存储结构也称为向量存储。向量是内存中一批地址连续的存储单元。由于线性表的所有数据元素属于同一类型，因此每个元素在存储器中占用的空间大小相同，假设向量的第一个元素存放的地址为LOC(a1

25、)，每个元素占用的空间大小为L个字节，则元素ai的存放地址为: LOC(ai)LOC(a1)L*(i1)2.2 线性表的顺序表示和实现 41 线性表的顺序存储结构的特点是:线性表中逻辑上相邻的结点在存储结构中也相邻，如图2.1所示。因此，线性表的顺序存储结构是一种随机存取的存储结构。 2.2 线性表的顺序表示和实现 图2.1 线性表的顺序存储结构示意图 42 2.2.2 线性表在顺序存储结构下的运算 可以用C语言描述顺序表如下： /线性表的顺序存储结构 define ERROR 0 define OK 1 define LIST_INIT_SIZE 100/存储空间的初始分配量 typedef

26、 struct ElemType elemLIST_INIT_SIZE; /存储空间基址 int length; /当前长度 SqList; 2.2 线性表的顺序表示和实现 43 1顺序表的插入操作 向量的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素x。由于C语言的数组下标是从零开始，长度为n的线性表(a1，ai-1，ai，an)，插入元素后变成长度为n+1的线性表(a1,，ai-1，x，ai，an)。插入操作应先把元素ai，an向后各自移动一个位置，然后将x插在第i个位置上。插入之后还要将线性表的长度加1。其插入过程见图2.2，插入过程可用如下算法来实现。

27、2.2 线性表的顺序表示和实现 44图2.2 顺序表中插入结点的过程 2.2 线性表的顺序表示和实现 45算法 2.1 int ListInsert_Sq(SqList *L,int i,ElemType e) int j; if(iL-length+1) /非法位置，退出运行 return ERROR; if(L-length=LIST_INIT_SIZE)/当前存储已满，退出运行 return ERROR; for(j=L-length-1;j=i-1;j-) L-elemj+1=L-elemj; L-elemi-1=e; L-length+; return OK; 2.2 线性表的顺序表

28、示和实现 46 现在分析算法2.1的时间复杂度。假设Pi是在第i个元素之前插入一个元素的概率, 而此时移动元素的次数是(n-i+1)。插入位置i的正确取值逻辑范围是1，n+1。在长度为n的线性表中插入一个元素时所需移动元素次数的平均值为：2.2 线性表的顺序表示和实现 如果在线性表的任何位置插入元素的概率相等，即则 算法的时间复杂度是T(n)=O(n)。47 2顺序表的删除操作 要删除线性表中的第i个元素ai，操作和插入操作类似。把元素ai+1，an分别向前移动一个位置。对于长度为n的线性表(a1，ai-1，ai，an)，变成长度为n-1的线性表(a1，ai-1，ai+1，an)。在程序中最后

29、还要将线性表长度减1。删除算法如下。其删除过程见图2.3，删除过程可用如下算法来实现。2.2 线性表的顺序表示和实现 48图2.2 顺序表中删除结点的过程 2.2 线性表的顺序表示和实现 49算法2.2int ListDelete_Sq(SqList *L,int i,ElemType *e)int j;if(iL-length)return ERROR; /非法位置*e=L-elemi-1; /被删除元素的值赋给efor(j=i;jlength-1;j+) L-elemj-1=L-elemj; /结点前移L-length-;return OK; 程序中线性表长度减1的语句可以写成：(*L).

30、length-; 2.2 线性表的顺序表示和实现50 现在分析算法2.2的时间复杂度。假设Pi表示删除表中第i个结点的概率, 而此时移动元素的次数是(n-i)。删除位置i的正确取值逻辑范围是1，n。在长度为n的线性表中删除一个元素时所需移动元素次数的平均值为：2.2 线性表的顺序表示和实现 如果在线性表的任何位置插入元素的概率相等，即则 算法的时间复杂度是T(n)=O(n)。51 3.顺序表存储结构特点 （1）数据元素最大个数需要预先确定，使得高级程序设计语言编译系统需要预先分配相应的存储空间。 （2）插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需要移动大

31、量数据。 （3）顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生上溢错误。2.2 线性表的顺序表示和实现 52 2.3.1 线性链表 线性表的链表存储结构的特点是可利用内存空间中一组任意的存储单元(可以是不连续的，也可以是连续的)来存储线性表的数据元素。分配给每个结点的存储单元一般分为两个域：一个域用来存储数据元素的信息，称为数据域，该域可以是一个简单类型，也可是包含较多信息的结构类型；另一个域用来存储直接后继结点的地址，称为指针域。这两部分信息组成了链表中的结点结构: 其中: data域是数据域，用来存放结点的

32、值；next 域是指针域(亦称链域)，用来存放结点的直接后继的地址(或位置)。 2.3 线性表的链式表示和实现53 单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为“空”，即NULL(图示中也可用表示)。例如，图2.3是线性表 （ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）的单链表示意图。 2.3 线性表的链式表示和实现图2.3 单链表示意图 54 由于单链表只注重结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此我们通常是用箭头来表示链域中的指针，于是链

33、表就可以列直观地画成用箭头链接起来的结点序列。例如图2.3可以画成图2.4的形式。 2.3 线性表的链式表示和实现图2.4 单链表的一般图示法 55 由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述。 typedef int ElemType ； typedef struct LNode ElemType data; /*数据域*/ struct LNode *next; /*指针域*/ LNode,*LinkList; 如图2.5（a）所示，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为空，如图2.5（b）所示。 2.3 线性表的链式表示和实现56 1.单

34、链表的建立 （1）头插法 图2.6表示在空链表head中依次插入d，c，b之后，将a插入到当前链表表头时指针的修改情况。具体算法如下： 2.3 线性表的链式表示和实现 headd bcsa图2.6 结点*s插到单链表head的头上 57算法2.3 LinkList CreateListH(void) char ch; LinkList head=(LinkList)malloc(sizeof(LNode); LinkList s;head-next=NULL;ch=getchar(); while(ch!=n) s=(LinkList)malloc(sizeof(LNode); s-data=

35、ch;s-next=head-next;/对应图2.6的 head-next=s; /对应图2.6的 ch=getchar(); return head; 2.3 线性表的链式表示和实现58 （2）尾插法 在空链表head中插入a，b，c之后，将d 插入到当前链表的表尾，其指针修改情况如图2.7所示。 2.3 线性表的链式表示和实现图2.7 结点*s插到单链表head的尾上 headabcrds59算法2.4LinkList CreateListT(void) char ch;LinkList head=(LinkList)malloc(sizeof(LNode); LinkList s,r;

36、r=head;ch=getchar(); while(ch!=n) s=(LinkList)malloc(sizeof(LNode); s-data=ch;r-next=s; /对应图2.7的 r=s; /对应图2.7的 ch=getchar(); r-next=NULL; return head; 2.3 线性表的链式表示和实现60 2查找 （1）按序号查找 LinkList GetNode(LinkList head,int i)/在带头结点的单链表head中查找第i个结点，若找到(1in)，则返回该结点的存储位置，否则返回NULL int j;LinkList p; p=head;j=0

37、; /从头结点开始扫描 while( p-next & jnext; /扫描下一结点 j+; /已扫描结点计数器 if（i =j） return p； /找到了第i个结点 else return NULL；/找不到，i0或in 2.3 线性表的链式表示和实现61 （2）按值查找 LinkList LocateNode( LinkList head,ElemType e)/ 在带头结点的单链表head中查找其结点值等于e的结点，若找到则返回该结点的位置，否则返回NULL LinkList p; p=head-next; /从开始结点比较，p初始值指向第一个结点 while( p & p-data

38、!=e) /直到p为NULL或p-data等于e止 p=p-next; return p; /若p=NULL，则查找失败 2.3 线性表的链式表示和实现62 3插入 算法描述：要在带头结点的单链表head中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点，申请一个新的结点并由指针s指示，并修改第i-1个结点的指针指向s，然后使s指针域指向第i个结点。插入结点的过程如图2.8所示。 2.3 线性表的链式表示和实现se heada1ai-1aip图2.8 在单链表第i个结点前插入一个结点过程 63int InsertList(LinkList head,int i,Ele

39、mType e)/在带头结点的单链表L中第i个位置插入值为e的新结点 LinkList p,s; p=GetNode(head,i-1); /寻找第i-1个结点，并返回指针 if(p=NULL) return ERROR; /插入位置不合理 s=(LinkList)malloc(sizeof(LNode); s-data=e; s-next=p-next; /对应图2.8的 p-next=s; /对应图2.8的 return OK; 2.3 线性表的链式表示和实现64 4删除 算法描述：欲在带头结点的单链表head中删除第i个结点，则首先要找到第i-1个结点并使p指向第i-1个结点，而后删除第

40、i个结点并释放结点空间。删除过程如图2.9所示。 2.3 线性表的链式表示和实现图2.9 在单链表第i个结点前删除一个结点过程 headai-1aipai+1r65Int DeleteList(LinkList head, ElemType *e,int i)/在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中 LinkList p,r; p=GetNode(head,i-1);/找第i-1个结点，并返回指针 if( p=NULL | p-next=NULL) /in时删除位置有错return ERROR; r=p-next; p-next=r-next; *e=r-data

41、; free(r); return OK; 2.3 线性表的链式表示和实现66 2.3.2 循环链表 循环链表(Circular Linked List)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。类似地，还有多重链的循环链表。为了操作方便，在循环单链表中设置一个头结点。这样，空循环链表仅由一个自成循环的头结点表示。带头结点的单循环链表如图2.10所示。 2.3 线性表的链式表示和实现.La1a2an L图2.10 单循环链表示意图 67 在循环单链表中附设尾指针

42、有时比附设头指针会使操作变得更简单。如在用头指针表示的循环单链表中，找开始结点a1的时间复杂度是O(1) ，然而要找到终端结点an，则需要从头指针开始遍历整个链表，其时间复杂度是O (n) 。 2.3 线性表的链式表示和实现rear.a1a2an 图2.11 带尾指针rear的单循环链表 68 例2.1有两个尾指针指示的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其尾指针为LA。 2.3 线性表的链式表示和实现RB.b1b2bn pRA.a1a2an 图2.12 带尾结点两个单循环链表的链接 69 LinkList ConnectR(LinkList RA,Lin

43、kList RB)/此算法将两个采用尾指针的循环链表首尾连接起来 LinkList p; p=RA-next; /保存链表RA的头结点地址 RA-next=RB-next-next;/链表RB的开始结点链到链表RA的终端结点之后 free(RB-next); /释放链表RB的头结点 RB-next=p; /链表RA的头结点链到链表RB的终端结点之后 return RB; /返回新循环链表的尾指针2.3 线性表的链式表示和实现70 2.3.3 双向循环链表 在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双 ( 向) 链表 (Doubl

44、e Linked List)。双链表的结构定义如下： typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList; 2.3 线性表的链式表示和实现图2.13 双向循环链表结点结构 prior data next71 2.3 线性表的链式表示和实现双向循环链表的结构如图2.14所示：head2.14(a) 空的双向循环链表head.a1a2an 2.14(b) 非空的双向循环链表 72 1双向链表的前插操作 算法描述：欲在双向链表第i个结点（指针p所指）之前插入一个的新的结点，则指针

45、的变化情况如图2.15所示。 2.3 线性表的链式表示和实现p:s图2.15 双链表的前插操作 73 int DInserLinkList(DuLinkList L,int i,ElemType e)DuLinkList s,p; int count=0; p=L; while(p-next!=L & countnext; count+; if(count=0 | icount) return ERROR;/检查待插入的位置i不合法退出 s=(DuLNode *)malloc(sizeof(DuLNode); if(s) s-data=e; s-prior=p-prior; /对应图2.15的

46、 p-prior-next=s; /对应图2.15的 s-next=p; /对应图2.15的 p-prior=s; /对应图2.15的 return OK;else return ERROR; 2.3 线性表的链式表示和实现74 2双向链表的删除插操作 算法描述：欲删除双向链表中的第i个结点（指针p所指），则指针的变化情况如图2.16所示： 2.3 线性表的链式表示和实现图2.16 双链表的删除操作 :p75 intDDeletelinkList(DuLinkList L,int i,ElemType *e) DuLinkList p;int count=0; p=L; while(p-nex

47、t!=L & countnext; count+; if(count=0 | icount) return ERROR;/检查待插入的位置i不合法退出 *e=p-data; p-prior-next=p-next; /对应图2.17的 p-next-prior=p-prior; /对应图2.17的 free(p); return OK; 2.3 线性表的链式表示和实现762.3 线性表的链式表示和实现 2.3.5 顺序表和链表比较 1基于空间的考虑 当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构较好。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用

48、顺序表作为存储结构。 2基于时间的考虑 若线性表的操作主要是进行查找，很少做插入和删除时，采用顺序表做存储结构为宜。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。 3基于语言的考虑 对于没有提供指针类型的高级语言，采用静态链表结构，否则采用动态链表。 772.4 多项式相加问题 符号多项式的相加操作是线性表处理的典型用例。在数学上的一个多项式: 我们称P为n项多项式，aixi是多项式的项(0in)，其中ai为系数，为变数，i为指数，一般多项式可以使用顺序表来表示其数据结构，也可以使用链表来表示。 78 在数学上，一个一元多项式Pn(x)可按升幂的形式写成： Pn(x)=p0+p1x1+

49、p2x2+p3x3+ +pnxn它实际上可以由n+1个系数唯一确定。因此，在计算机内，可以用一个线性表P来表示： P=（p0，p1，p2， ，pn）其中每一项的指数则隐含在其系数的序号里了。 但是在通常的应用中，多项式的指数有时可能会很高并且变化很大。例如： R(x)=1+5x10000+7x20000若采用顺序存储，则需要20001个空间，而存储的有用数据只有三个，这无疑是一种浪费。 2.4 多项式相加问题 79 假设一元多项式Pn(x) = p1xe1+p2xe2+pmxem其中pi是指数为ei的项的系数，(且0e1e2em=n)，若只存非零系数，则多项式中每一项由两项构成（指数项和系数项

50、），用线性表来表示，即： ( (p1,e1)，(p2,e2)，(pm,em) )采用这样的方法存储，在最坏情况下，即n+1个系数都不为零，则比只存储系数的方法多存储一倍的数据。但对于非零系数多的多项式则不宜采用这种表示。 下面给出用单链表实现一元多项式相加运算的方法。 2.4 多项式相加问题 80 1.多项式相加的链表存储结构 多项式用链表来表示其结点结构如下： typedef struct Polynode int coef; /*存储系数*/ int exp; /*存储指数*/ struct Polynode *next; /*指向下一个结点*/ Polynode,* Polylist;

51、2.4 多项式相加问题 81 2.通过键盘输入一组多项式的系数和指数，以输入系数0为结束标志，并约定建立多项式链表时，总是按指数从小到大的顺序排列。 算法描述：从键盘接受输入的系数和指数；用尾插法建立一元多项式的链表。 2.4 多项式相加问题 82 Polylist polycreate() Polynode *head, *rear, *s; int c,e; head=(Polynode *)malloc(sizeof(Polynode); /建头结点 rear=head; /rear始终指向表尾，便于尾插法建表 scanf(“%d,%d”,&c,&e);/键入多项式的系数和指数项 whi

52、le(c!=0) /若c=0，则代表多项式的输入结束 s=(Polynode*)malloc(sizeof(Polynode); /新结点 s-coef=c ; s-exp=e ; rear-next=s ; /在当前表尾做插入 rear=s; scanf(“%d,%d”,&c,&e); rear-next=NULL; /表示结束 return(head); 2.4 多项式相加问题 833.多项式相加的算法实现 图2.17 所示为两个多项式的单链表，分别表示多项式 A(x)=7+3x+9x8+5x17和多项式B(x)=8x+22x7-9x8。 图2.17 多项式的单链表表示法 多项式相加的运算

53、规则是：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。2.4 多项式相加问题 84 设p、q分别指向多项式A，B的一项，比较结点的指数项（1）若p-expexp，则结点p所指的结点应 是“和多项式”中的一项，令指针p后移；（2）若p-expq-exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移；（3）若p-exp=q-exp，则将两个结点中的系数相加，当和不为零时修改结点p的系数域，释放q结点；若和为零，则和多项式中无此项，从A中删去p结点，同时释放p和q结点

54、。 2.4 多项式相加问题 85图2.18 多项式相加得到的多项式和 2.4 多项式相加问题 86void polyadd(Polylist polya,Polylist polyb) Polynode * p, *q, *pre,*temp; int sum; p=polya-next ;/令p指向polya多项式链表中的第一个结点 q=polyb-next ;/令q指向polyb多项式链表中的第一个结点 pre=polya; /pre指向和多项式的尾结点 while（p!=NULL & q!=NULL） if(p-expexp） pre-next=p; pre=pre-next;p=p-n

55、ext; 2.4 多项式相加问题 87 else if ( p-exp=q-exp）/若指数相等，则系数相加 sum=p-coef + q-coef ; if (sum !=0) p-coef=sum; pre-next=p; pre=pre-next; p=p-next; temp=q; q=q-next; free(temp); else /和为零，则删除p与q，指针指向下一个结点 temp=p-next ; free(p); p=temp ; temp=q-next; free(q); q=temp ; else pre-next=q; pre=pre-next; q =q-next;

56、if(p!=NULL) pre-next=p; else pre-next=q; 2.4 多项式相加问题 88一、填空1.在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。2.线性表中结点的集合是 的，结点间的关系是 的。3.向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 个元素。4.向一个长度为n的向量中删除第i个元素(1in)时，需向前移动 个元素。5.在顺序表中访问任意一结点的时间复杂度均为 ，因此，顺序表也称为 的数据结构。习题 896.顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置 相邻。7.在单

57、链表中，除了首元结点外，任一结点的存储位置由 指示。8.在n个结点的单链表中要删除已知结点*p，需找到它的 ，其时间复杂度为 。二、判断正误（在正确的说法后面打勾，反之打叉）（ ）1. 链表的每个结点中都恰好包含一个指针。 （ ）2. 链表的物理存储结构具有同链表一样的顺序。 习题 90（ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ ）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（ ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）6. 顺序存储方式的优点是存储密度大，且插入、删除运

58、算效率高。（ ）7. 线性表在物理存储空间中也一定是连续的。（ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（ ）9. 顺序存储方式只能用于存储线性结构。 习题 91（ ）10. 线性表的逻辑顺序与存储顺序总是一致的。三、单项选择题（ ）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构（ ）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120 习题 92（ ）3. 在n个结点的顺序表

59、中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1in）和求第i个结点的直接前驱（2in） （B）在第i个结点后插入一个新结点（1in）（C）删除第i个结点（1in）（D）将n个结点从小到大排序（ ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 个元素（A）8 （B）63.5 （C）63 （D）7（ ）5. 链接存储的存储结构所占存储空间：习题 93（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数（

60、 ）6. 链表是一种采用 存储结构存储的线性表；（A）顺序 （B）链式 （C）星式 （D）网状（ ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以习题 94（ ）8 线性表在 情况下适用于使用链式结构实现。（）需经常修改中的结点值 （）需不断对进行删除插入 （）中含有大量的结点 （）中结点结构复杂（ ）9 单链表的存储密度（）大于1； （）等于1； （）小于1； （）不能确定 四、编程题 1.已知单链表L1和L2，试编写算法将L1和L2连接成一个单链表。 2.给出求顺序表长度的算法。