《数据-教材课件汇总完整版ppt全套课件最全教学教程整本书电子教案全书教案合集最新课件汇编.ppt》由会员分享，可在线阅读，更多相关《数据-教材课件汇总完整版ppt全套课件最全教学教程整本书电子教案全书教案合集最新课件汇编.ppt（657页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1第第1 1章章 绪绪 论论 1.1 1.1 什么是数据结构什么是数据结构 1.2 1.2 基本概念和术语基本概念和术语 1.3 1.3 数据抽象和抽象数据类型数据抽象和抽象数据类型1.4 1.4 算法描述与分析算法描述与分析 小结小结 习题一习题一 2l l教学安排教学安排课时：课时：2 2学时学时难点：时间的渐进复杂度（语句频度）计算难点：时间的渐进复杂度（语句频度）计算重点：数据结构基本概念、算法分析重点：数据结构基本概念、算法分析教学方法：多媒体教学，通过大量实例讲解基本的概教学方法：多媒体教学，通过大量实例讲解基本的概念和语法念和语法习题：见课件后习题习题：见课件后习题31.1 1.
2、1 什么是数据结构什么是数据结构数据结构的重要性：（1）考研的必考科目，很多大的软件公司面试必考内容。（2）专业基础课（学位课程），有承上启下的作用。先修课程：计算机基础、C语言程序设计、离散数学后继课程：操作系统（队列、存储管理表、目录树）数据库原理（线性表、多链表、索引树）编译原理（栈、哈希表、语法树）人工智能（广义表、集合、搜索树、有向图）41.1 1.1 什么是数据结构什么是数据结构在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直至得到正确结果。所谓数学模型一般指具体的代数方程等。然而，有些实际问题无法用数学方程表示
3、。现在来分析几个这方面的典型实例，它们的主要特点是处理数据信息的存储与检索等，而不是单纯的数值计算。例如：图书档案类问题、棋类对奕问题、交通或通信网问题。5表1.1 学 籍 表首先分析图书目录卡或学籍档案类问题。设一个班级有30个学生，这个班级的学籍表如表1.1所示。1.1什么是数据结构什么是数据结构6我们可以把每个学生的信息看成一个记录，表中的每个记录又由7个数据项组成。该学籍表由30个记录组成，记录之间是一种顺序关系。这种表通常称为线性表，数据之间的逻辑结构称为线性结构，其主要操作有检索、查找、插入或删除等。对于这些运算，显然是由计算机来完成，这就要设计相应的插入、删除和修改的算法。也就是
4、说，数据结构还需要给出每种结构类型所定义的各种运算的算法。通过以上讨论，我们可以直观地认为：数据结构是研究程序数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学设计中计算机操作的对象以及它们之间的关系和运算的一门学科。科。1.1什么是数据结构什么是数据结构71数据数据数据是描述客观事物的数值、字符以及能输人机器且能被处理的各种字符的集合，即数据就是计算机化的信息。换句话说，数据就是对客观事物采用计算机能够识别、存储及处理的形式所进行的描述。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的信息，包括文字、表格、图像等，统称为数据。例如，一
5、个学生成绩管理程序所要处理的数据，如表1.1所示。1.2基本概念和常用术语基本概念和常用术语8表表1.1 1.1 学生成绩表学生成绩表学号学号姓名姓名数据结构数据结构大学物理大学物理高等数学高等数学平均成绩平均成绩0232101王刚959085900232102李娟908085850232103赵平999591950232104王强867084800232105张雪929184891.2基本概念和常用术语基本概念和常用术语92数据元素数据元素数据元素也叫结点，它是组成数据的基本单位，是一个数据整体中相对独立的单元。例如，在表1.1所示的学生成绩中，为了便于处理，把其中的每一行（代表一个学生成绩
6、）作为一个基本单位来考虑，故该数据由五个结点构成。一般情况下，一个结点还可以分割成若干具有不同属性的字段(也叫数据项)。例如，在表1.1所示的表格数据中，每个结点都由学号、姓名、数据结构、大学物理、高等数学和平均成绩六个字段构成。字段是构成数据的最小单位。1.2基本概念和常用术语基本概念和常用术语10 3数据对象数据对象在数据结构中，将性质相同的数据元素的集合称之为数据对象，它是数据的一个子集。上例：一个班级的学生成绩表可以看作一个数据对象。4数据结构数据结构数据结构由某一数据元素集合及该集合中所有数据元素之间的关系组成。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构、数据的存储结构和
7、对数据所施加的操作。1.2基本概念和常用术语基本概念和常用术语11根据数据结构中数据元素之间的结构关系的不同特征，通常将数据结构分为如下四种基本结构：（1）集合结构（set）：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。元素顺序是随意的。（2）线性结构（linear）或称序列（sequence）结构：数据元素的有序集合。数据元素之间形成一对一的关系。（3）树形结构（tree）：树是层次结构，树中数据元素之间存在一对多的关系。（4）图形结构（graph）：图中数据元素之间的关系是多对多的。1.2基本概念和常用术语基本概念和常用术语121.2基本概念和常用术语基本
8、概念和常用术语135逻辑结构逻辑结构结点和结点之间的逻辑关系称为数据的逻辑结构逻辑结构。数据结构从逻辑结构划分为:（1）线性结构。元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继。见图1.1中的(b)。（2）非线性结构。元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继。见图1.1中的（c）和（d）（3）集合结构。元素之间无任何关系，元素的排列无任何顺序。见图1.1中（a）。1.2基本概念和常用术语基本概念和常用术语146存储结构存储结构数据的逻辑结构是独立于计算机的，它与数据在计算机中的存储无关，要对数据进行
9、处理，就必须将数据存储在计算机中。数据在计算机中的存储方式称为数据的存储结构存储结构。数据的存储结构主要有4种。（1）顺序存储（2）链式存储（3）索引存储（4）散列存储1.2基本概念和常用术语基本概念和常用术语157数据处理数据处理数据处理是指对数据进行查找、插入、删除、合并、排序、统计以及简单计算等操作的过程。8数据类型数据类型数据类型是指程序设计语言中各变量可取的数据种类，它是高级程序设计语言中的一个基本概念，和数据结构的概念密切相关。8算法算法简单地说，算法就是解决特定问题的方法。特定问题可以是数值的，也可以是非数值的。解决数值问题的算法叫做数值算法。数据处理方面的算法都属于非数值算法。
10、1.2基本概念和常用术语基本概念和常用术语161.3.1数据抽象数据抽象抽象抽象（abstraction）可以被理解为一种机制，其实质是抽取共同的和实质的东西，忽略非本质的细节。抽象可以使我们的求解问题过程以自顶向下的方式分步进行:首先考虑问题的最主要方面，然后再逐步细化，进一步考虑问题的某些细节，并最终实现之。数据的抽象经历了三个发展阶段：第一个发展阶段是从无类型的二进制数到基本数据类型的产生。第二个发展阶段是从基本数据类型到用户自定义类型的产生。第三个发展阶段是从用户自定义类型到抽象数据类型的出现。1.3数据抽象和抽象数据类型数据抽象和抽象数据类型171.3.2抽象数据类型抽象数据类型抽象
11、数据类型抽象数据类型(AbstractDataType，简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。1.3数据抽象和抽象数据类型数据抽象和抽象数据类型181.3.3抽象数据类型描述和实现抽象数据类型描述和实现抽象数据类型形式化定义可以用以下三元组表示ADT（D，S，P）其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。抽象数据类型描述的一般形式如下：ADT抽象数据类型名称数据对象：数据关系：操作集合：操作名1：操作名n：
12、ADT抽象数据类型名称1.3数据抽象和抽象数据类型数据抽象和抽象数据类型191.4.1算法及其性能标准算法及其性能标准算法具有五个基本特征：有穷性，算法的执行必须在有限步内结束。确定性，算法的每一个步骤必须是确定的无二义性的。输入，算法可以有0个或多个输入。输出，算法一定有输出结果可行性，算法中的运算都必须是可以实现的。1.4算法和算法分析算法和算法分析20衡量一个算法的性能，主要有以下几个标准:正确性（corectness）:算法的执行结果应当满足预先规定的功能和性能要求。简明性（siplcty）:一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮性（robustness）:当输入不合
13、法数据时，应能做适当处理，不至于引起严重后果。效率（efecency）:有效使用存储空间，井有高的时间效率。1.4算法和算法分析算法和算法分析211.4.2算法时间复杂度和渐近时间复杂度算法时间复杂度和渐近时间复杂度衡量算法的二种方法：衡量算法的二种方法：事前分析、事后测试如何估算算法的时间效率？和算法执行时间相关的因素如下：如何估算算法的时间效率？和算法执行时间相关的因素如下：（1）算法所用的“策略”。（2）算法所解决问题的“规模”。（3）编程所用的“语言”。（4）“编译”的质量。（5）执行算法的计算机的“速度”。*后三条受到计算机硬件和软件的制约，“估算”只需考虑前两条。1.4算法和算法分
14、析算法和算法分析221.4.2算法时间复杂度和渐近时间复杂度算法时间复杂度和渐近时间复杂度定义：定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数T(n)称为这一算法的“算法时算法时间复杂性间复杂性”。一个算法的“运行工作量”通常是随问题规模的增长而增长，因此比较不同算法的优劣主要应该以其“增长的趋势”为准则。假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：称T(n)为算法的算法的(渐近渐近)时间复杂度时间复杂度。换句话说，当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。1.4算法和算法分析算法和
15、算法分析23在实际研究中，我们使用语句频度的数量级来衡量一个算法的时间复杂度。语句的频度语句的频度（frequencycount）指的是该语句重复执行的次数，下面举一个例子介绍时间复杂度的估算方法。例例1二层for循环的时间复杂度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;
16、j=n;j+)for(k=1;k=n;k+)x=x+1;现把它们看成三个简单的算法，在三个算法中语句x=x+1的频度分别为1；n；n2；1.4算法和算法分析算法和算法分析那么算法(a)，(b)，(c)的时间复杂度分别记作：T(n)=O(1)；T(n)=O(n)；T(n)=O(n2)。251.4算法和算法分析算法和算法分析算法描述如下：voidsimsort(arra,intn)/*n和数组a的数据由主调函数提供*/for(i=0;in-1;i+)for(j=i+1;jn;j+)if(ai.dataaj.data)m=ai;ai=aj;aj=m;for(i=0;in;i+)printf(n%8d
17、%8d%10d,i,ai.num,ai.data);26现在来分析上述算法的时间复杂度。算法中有一个二重循环，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)，算法还可
18、能呈现的时间复杂度有指数阶和对数阶O(lbn)（log2n）等。研究算法的时间复杂度，目的是研究随着问题规模n的逐渐增大，时间消耗的增长趋势(很快、缓慢、很少)。不同数量级时间复杂度的性状如图1.3所示。1.4算法和算法分析算法和算法分析28图1.3各种数量级的时间复杂度1.4算法和算法分析算法和算法分析29从图1.3中可见，随着问题规模的增大，其时间消耗也在增大，但它们的增长趋势明显不同。假设对同一个问题的解决，设计两种不同的算法A和B，算法A的时间复杂度为O(n2)，算法B的时间复杂度为O(lbn)。随着问题规模n的增大，算法A所消耗时间将会迅速增大，而算法B所消耗时间的增大趋向平缓，即增
19、长比较慢。显然，在问题的规模n很大时算法B运行效率高，可以认为算法B优于算法A。1.4算法和算法分析算法和算法分析301.4.3算法的空间复杂度算法的空间复杂度一个程序的空间复杂度空间复杂度(spacecomplexity)是程序运行从开始到结束所需的存储量。程序运行所需的存储空间包括两部分：（1）固定部分固定部分(fxedspacerequirement)：它主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。（2）可变部分可变部分(variblespacerequirement)：包括数据元素所占的空间，以及算法执行所需的额外空间，如递归栈所用的空间。1.4算法和算法分析算法和
20、算法分析31数据结构应讨论数据的逻辑结构、存储结构以及在数据结构上定义的一组运算和实现这些运算的算法。数据结构上的运算是在逻辑结构上定义的，而只有当存储结构确定后才能给出其实现的算法。本章介绍的使用抽象数据类型描述数据结构的方式将贯穿全书。一个数据结构的ADT描述是用户使用数据结构的规范，它应严格定义，它的实现与使用分离，实行封装和信息隐蔽。数据结构的实现必须严格符合其ADT规范，这是程序设计的基本原则之一。本章最后介绍的算法效率和算法分析的基本方法将在以后各章中用以分析算法的时间和空间效率。小小结结321.简述下列术语的含义:数据、数据元素、逻辑结构、存储结构、线性数据结构和非线性数据结构。
21、2.什么是数据结构?有关数据结构的讨论应包括哪些方面?3.什么是算法？算法的主要特点是什么？4.如何评价一个算法？5.什么是算法的时间复杂度和空间复杂度？6.确定下列各程序划线语旬的执行次数，计算它们的渐近时间复杂度。习习题题一一33（1）i=l;k=O;dok=k+l0*i;i+;wh1e(i=n-l);（2）i=l;x=O;dox+;i=2*i;while(in);（3）for(inti=l;i=n;i+)for(intj=1;j=i;j+)for(intk=l;k=(y+l)*(y+1)y+;习习题题一一34第第2 2章章 线性表线性表 1.1 线性表概念 1.2 基本概念和术语 1.3
22、 数据抽象和抽象数据类型1.4 算法描述与分析 小结 习题一 2.1 线性表概念线性表概念线性表是由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线性表的抽象数据类
23、型定义如下：ADT List数据元素：D=ai|aiD0,i=1,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已存在。操作结果
24、：如果L为空表则返回0，否则返回表中的元素个数。（6）Locate(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
25、已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ADT List 2.1线性表概念线性表概念39在上述的操作运算中，最基本最重要的是插入、删除。线性表的其他复杂操作和运算还有：对有序表的插入和删除；按某种要求重排线性表中各元素的顺序；按某个特定值查找线性表中的元素；两个线性表的合并等。2.1线性表概念线性表概念402.2.1 线性表的顺序存储结构在计算机内，可以用不同的方法来存储数据信息，最常用的方法是顺序存储。顺序存储结构也称为向量存储。向量是内存中一批地址连续的存储单元。由于线性表的所有数据元素属于同一类型，因此每个元素在存储器
26、中占用的空间大小相同，假设向量的第一个元素存放的地址为LOC(a1)，每个元素占用的空间大小为L个字节，则元素ai的存放地址为:LOC(ai)LOC(a1)L*(i1)2.2线性表的顺序表示和实现线性表的顺序表示和实现41线性表的顺序存储结构的特点是:线性表中逻辑上相邻的结点在存储结构中也相邻，如图2.1所示。因此，线性表的顺序存储结构是一种随机存取的存储结构。2.2线性表的顺序表示和实现线性表的顺序表示和实现图2.1 线性表的顺序存储结构示意图422.2.2 线性表在顺序存储结构下的运算 可以用C语言描述顺序表如下：/线性表的顺序存储结构define ERROR 0define OK 1de
27、fine LIST_INIT_SIZE 100/存储空间的初始分配量typedef struct ElemType elemLIST_INIT_SIZE;/存储空间基址 int length;/当前长度 SqList;2.2线性表的顺序表示和实现线性表的顺序表示和实现431顺序表的插入操作向量的插入操作是指在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素x。由于C语言的数组下标是从零开始，长度为n的线性表(a1，ai-1，ai，an)，插入元素后变成长度为n+1的线性表(a1,，ai-1，x，ai，an)。插入操作应先把元素ai，an向后各自移动一个位置，然后将x插在第i个
28、位置上。插入之后还要将线性表的长度加1。其插入过程见图2.2，插入过程可用如下算法来实现。2.2线性表的顺序表示和实现线性表的顺序表示和实现44图2.2 顺序表中插入结点的过程2.2线性表的顺序表示和实现线性表的顺序表示和实现45算法 2.1int 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
29、-elemj;L-elemi-1=e;L-length+;return OK;2.2线性表的顺序表示和实现线性表的顺序表示和实现46现在分析算法2.1的时间复杂度。假设Pi是在第i个元素之前插入一个元素的概率,而此时移动元素的次数是(n-i+1)。插入位置i的正确取值逻辑范围是1，n+1。在长度为n的线性表中插入一个元素时所需移动元素次数的平均值为：2.2线性表的顺序表示和实现线性表的顺序表示和实现如果在线性表的任何位置插入元素的概率相等，即则算法的时间复杂度是T(n)=O(n)。472顺序表的删除操作 要删除线性表中的第i个元素ai，操作和插入操作类似。把元素ai+1，an分别向前移动一个位
30、置。对于长度为n的线性表(a1，ai-1，ai，an)，变成长度为n-1的线性表(a1，ai-1，ai+1，an)。在程序中最后还要将线性表长度减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;jleng
31、th-1;j+)L-elemj-1=L-elemj;/结点前移L-length-;return OK;程序中线性表长度减1的语句可以写成：(*L).length-;2.2线性表的顺序表示和实现线性表的顺序表示和实现50现在分析算法2.2的时间复杂度。假设Pi表示删除表中第i个结点的概率,而此时移动元素的次数是(n-i)。删除位置i的正确取值逻辑范围是1，n。在长度为n的线性表中删除一个元素时所需移动元素次数的平均值为：2.2线性表的顺序表示和实现线性表的顺序表示和实现如果在线性表的任何位置插入元素的概率相等，即则算法的时间复杂度是T(n)=O(n)。513.顺序表存储结构特点（1）数据元素最大
32、个数需要预先确定，使得高级程序设计语言编译系统需要预先分配相应的存储空间。（2）插入与删除运算的效率很低。为了保持线性表中的数据元素的顺序，在插入操作和删除操作时需要移动大量数据。（3）顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生上溢错误。2.2线性表的顺序表示和实现线性表的顺序表示和实现522.3.1 线性链表线性表的链表存储结构的特点是可利用内存空间中一组任意的存储单元(可以是不连续的，也可以是连续的)来存储线性表的数据元素。分配给每个结点的存储单元一般分为两个域：一个域用来存储数据元素的信息，称为数据域
33、，该域可以是一个简单类型，也可是包含较多信息的结构类型；另一个域用来存储直接后继结点的地址，称为指针域。这两部分信息组成了链表中的结点结构:其中:data域是数据域，用来存放结点的值；next 域是指针域(亦称链域)，用来存放结点的直接后继的地址(或位置)。2.3线性表的链式表示和实现线性表的链式表示和实现53单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于终端结点无后继，故终端结点的指针域为“空”，即NULL(图示中也可用表示)。例如，图2.3是线性表（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WAN
34、G）的单链表示意图。2.3线性表的链式表示和实现线性表的链式表示和实现图2.3 单链表示意图54由于单链表只注重结点间的逻辑顺序，并不关心每个结点的实际存储位置，因此我们通常是用箭头来表示链域中的指针，于是链表就可以列直观地画成用箭头链接起来的结点序列。例如图2.3可以画成图2.4的形式。2.3线性表的链式表示和实现线性表的链式表示和实现图2.4 单链表的一般图示法55由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述。typedef int ElemType；typedef struct LNode ElemType data;/*数据域*/struct LNode*ne
35、xt;/*指针域*/LNode,*LinkList;如图2.5（a）所示，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为空，如图2.5（b）所示。2.3线性表的链式表示和实现线性表的链式表示和实现561.单链表的建立（1）头插法图2.6表示在空链表head中依次插入d，c，b之后，将a插入到当前链表表头时指针的修改情况。具体算法如下：2.3线性表的链式表示和实现线性表的链式表示和实现headdbcsa图2.6 结点*s插到单链表head的头上57算法2.3LinkList CreateListH(void)char ch;LinkList head=(LinkList)mallo
36、c(sizeof(LNode);LinkList s;head-next=NULL;ch=getchar();while(ch!=n)s=(LinkList)malloc(sizeof(LNode);s-data=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插到单
37、链表head的尾上 headabcrds59算法2.4LinkList CreateListT(void)char ch;LinkList head=(LinkList)malloc(sizeof(LNode);LinkList s,r;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线性表的链式表示和实现线性表的链式表示和实现602查找（1）按序号查找
38、 LinkList GetNode(LinkList head,int i)/在带头结点的单链表head中查找第i个结点，若找到(1in)，则返回该结点的存储位置，否则返回NULL int j;LinkList p;p=head;j=0;/从头结点开始扫描 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
39、 e)/在带头结点的单链表head中查找其结点值等于e的结点，若找到则返回该结点的位置，否则返回NULL LinkList p;p=head-next;/从开始结点比较，p初始值指向第一个结点 while(p&p-data!=e)/直到p为NULL或p-data等于e止 p=p-next;return p;/若p=NULL，则查找失败 2.3线性表的链式表示和实现线性表的链式表示和实现623插入算法描述算法描述：要在带头结点的单链表head中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点，申请一个新的结点并由指针s指示，并修改第i-1个结点的指针指向s，然后使s指针
40、域指向第i个结点。插入结点的过程如图2.8所示。2.3线性表的链式表示和实现线性表的链式表示和实现seheada1ai-1aip图2.8 在单链表第i个结点前插入一个结点过程 63int InsertList(LinkList head,int i,ElemType 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;
41、/对应图2.8的 p-next=s;/对应图2.8的 return OK;2.3线性表的链式表示和实现线性表的链式表示和实现644删除算法描述算法描述：欲在带头结点的单链表head中删除第i个结点，则首先要找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。删除过程如图2.9所示。2.3线性表的链式表示和实现线性表的链式表示和实现图2.9 在单链表第i个结点前删除一个结点过程headai-1aipai+1r65Int DeleteList(LinkList head,ElemType*e,int i)/在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e
42、中 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;free(r);return OK;2.3线性表的链式表示和实现线性表的链式表示和实现662.3.2 循环链表循环链表(Circular Linked List)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。类似
43、地，还有多重链的循环链表。为了操作方便，在循环单链表中设置一个头结点。这样，空循环链表仅由一个自成循环的头结点表示。带头结点的单循环链表如图2.10所示。2.3线性表的链式表示和实现线性表的链式表示和实现.La1a2an L图2.10 单循环链表示意图67在循环单链表中附设尾指针有时比附设头指针会使操作变得更简单。如在用头指针表示的循环单链表中，找开始结点a1的时间复杂度是O(1)，然而要找到终端结点an，则需要从头指针开始遍历整个链表，其时间复杂度是O(n)。2.3线性表的链式表示和实现线性表的链式表示和实现rear.a1a2an 图2.11 带尾指针rear的单循环链表68例例2.12.1
44、有两个尾指针指示的循环单链表LA、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其尾指针为LA。2.3线性表的链式表示和实现线性表的链式表示和实现RB.b1b2bn pRA.a1a2an 图2.12 带尾结点两个单循环链表的链接69LinkList ConnectR(LinkList RA,LinkList RB)/此算法将两个采用尾指针的循环链表首尾连接起来 LinkList p;p=RA-next;/保存链表RA的头结点地址 RA-next=RB-next-next;/链表RB的开始结点链到链表RA的终端结点之后 free(RB-next);/释放链表RB的头结点 RB-nex
45、t=p;/链表RA的头结点链到链表RB的终端结点之后 return RB;/返回新循环链表的尾指针2.3线性表的链式表示和实现线性表的链式表示和实现702.3.3 双向循环链表在单链表的每个结点里再增加一个指向其前趋的指针域prior。这样形成的链表中就有两条方向不同的链，我们称之为双(向)链表(Double Linked List)。双链表的结构定义如下：typedef struct DuLNode ElemType data;struct DuLNode*prior,*next;DuLNode,*DuLinkList;2.3线性表的链式表示和实现线性表的链式表示和实现图2.13 双向循环链
46、表结点结构priordatanext712.3线性表的链式表示和实现线性表的链式表示和实现双向循环链表的结构如图2.14所示：head2.14(a)空的双向循环链表head.a1a2an 2.14(b)非空的双向循环链表721双向链表的前插操作算法描述算法描述：欲在双向链表第i个结点（指针p所指）之前插入一个的新的结点，则指针的变化情况如图2.15所示。2.3线性表的链式表示和实现线性表的链式表示和实现p:s 图2.15 双链表的前插操作73int DInserLinkList(DuLinkList L,int i,ElemType e)DuLinkList s,p;int count=0;p
47、=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的 p-prior-next=s;/对应图2.15的 s-next=p;/对应图2.15的 p-prior=s;/对应图2.15的 return OK;else return ERROR;2.3线性表的链式表示和实现线性表的链式表示和实现742双向链表的删除插操作算法描述算法描述：欲删除
48、双向链表中的第i个结点（指针p所指），则指针的变化情况如图2.16所示：2.3线性表的链式表示和实现线性表的链式表示和实现图2.16 双链表的删除操作:p75intDDeletelinkList(DuLinkList L,int i,ElemType*e)DuLinkList p;int count=0;p=L;while(p-next!=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;/对
49、应图2.17的 free(p);return OK;2.3线性表的链式表示和实现线性表的链式表示和实现762.3线性表的链式表示和实现线性表的链式表示和实现2.3.5 顺序表和链表比较1基于空间的考虑 当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构较好。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。2基于时间的考虑 若线性表的操作主要是进行查找，很少做插入和删除时，采用顺序表做存储结构为宜。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。3基于语言的考虑 对于没有提供指针类型的高级语言，采用静态链表结构，否则采用动态链表
50、。772.4多项式相加问题多项式相加问题符号多项式的相加操作是线性表处理的典型用例。在数学上的一个多项式:我们称P为n项多项式，aixi是多项式的项(0in)，其中ai为系数，为变数，i为指数，一般多项式可以使用顺序表来表示其数据结构，也可以使用链表来表示。78在数学上，一个一元多项式Pn(x)可按升幂的形式写成：Pn(x)=p0+p1x1+p2x2+p3x3+pnxn它实际上可以由n+1个系数唯一确定。因此，在计算机内，可以用一个线性表P来表示：P=（p0，p1，p2，pn）其中每一项的指数则隐含在其系数的序号里了。但是在通常的应用中，多项式的指数有时可能会很高并且变化很大。例如：R(x)=