计算机软件技术基础3-1 数据结构及算法(概述+线性表)

1、1 23.1 概 述3.1.1 3.1.1 数据结构的概念数据结构的概念3.1.2 3.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构3.1.3 3.1.3 算法与算法分析算法与算法分析3.1.4 3.1.4 算法分析技术初步算法分析技术初步3.1.5 3.1.5 小结小结33.1.1 3.1.1 数据结构的概念数据结构的概念1. 数值型与非数值型数据数值型与非数值型数据2.数值型：数值型：整型、实型、布尔型等整型、实型、布尔型等3.非数值型：非数值型：文献检索、金融管理、商业文献检索、金融管理、商业系统系统 等数据处理等数据处理2. 数据结构数据结构研究非数值运算的程序设计问题。研

2、究非数值运算的程序设计问题。数据结构就是相互之间存在一种或多种特定数据结构就是相互之间存在一种或多种特定关系的数据元素的集合。关系的数据元素的集合。如如线性关系、层次关系、网状关系线性关系、层次关系、网状关系等。等。4数据数据(data)是信息的载体，指所有能输入到计是信息的载体，指所有能输入到计算机中并被计算机程序处理的符号的总称。如算机中并被计算机程序处理的符号的总称。如数、字符、符号等的集合。分为数、字符、符号等的集合。分为数值型数值型和和非数非数值型值型数据两类。数据两类。数据元素数据元素(data element)是数据的基本单位。是数据的基本单位。如数据集合如数据集合N= 1N=

3、1，2 2，3 3，4 4，5 5 中整数中整数1 1至至5 5均为数据元素。均为数据元素。 数据元素不一定是单个的数字或字符，也可数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。能是若干个数据项的组合，如学生信息。 数据元素有时也称结点或记录。数据元素有时也称结点或记录。3. 基本概念和术语基本概念和术语3.1.1 3.1.1 数据结构的概念数据结构的概念5数据类型数据类型程序设计语言中允许的变量类型程序设计语言中允许的变量类型 基本数据类型（原子类型）：变量值不可分，基本数据类型（原子类型）：变量值不可分，如整型、实型、字符型等如整型、实型、字符型等 结构类型：变

4、量值可分，如数组、结构体等结构类型：变量值可分，如数组、结构体等数据对象数据对象(data object)性质相同的数据元素的性质相同的数据元素的集合集合。如大写字母字符的数据对象是集合：如大写字母字符的数据对象是集合：C= AC= A，BB，.，Z Z 。3.1.1 3.1.1 数据结构的概念数据结构的概念6数据结构数据结构(data structure)是指同一数据对象中各是指同一数据对象中各数据元素间存在的关系。数据元素间存在的关系。 数据结构与算法数据结构与算法 程序程序算法算法数据结构数据结构算法算法指解决特定问题的有限运算序列指解决特定问题的有限运算序列3.1.1 3.1.1 数据

5、结构的概念数据结构的概念71.1.逻辑结构逻辑结构：研究数据元素及其关系的数学特性，：研究数据元素及其关系的数学特性， 即数据元素间的逻辑关系。即数据元素间的逻辑关系。二元组二元组 S =S =（D D，R R） D D数据元素的非空有限集合数据元素的非空有限集合R RD D上关系的非空有限集合。上关系的非空有限集合。3.1.2 3.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构8四类基本结构：四类基本结构：线性结构（一对一）线性结构（一对一）通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构（一对多）树形结构（一对多）电子字典、家谱、目录电子字典、家谱、目录图形结构（多对多）图形

6、结构（多对多）交通线路、通信网络交通线路、通信网络集合集合3.1.2 3.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构9例1：linearity = (D, R)，其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , 例2：Tree= (D, R)，其中D 1,2,3,4,5,6,7,8,9,10R = rr = , , , , , , , , 3.1.2 3.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构10例4：S = (D, R)，其中D 1,2,3,4,5,6R = r1, r2r 1= , , , , r2=,例3：G

7、raph= (D, R)，其中D 1,2,3,4,5; R = rr = , , , , 3.1.2 3.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构112.2.物理结构物理结构( (存储结构存储结构) )：是逻辑结构在计算是逻辑结构在计算机中的映象，即具体实现。机中的映象，即具体实现。四种基本存储结构：顺序存储结构 链式存储结构 索引存储结构 散列存储结构3.3.逻辑结构与存储结构的关系逻辑结构与存储结构的关系算法的设计取决于选定的逻辑结构，而算 法的实现依赖于采用的存储结构。同一种逻辑结构可采用不同的存储结构。3.1.2 3.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理

8、结构12一、什么是算法一、什么是算法 算法是对特定问题求解步骤的一种描述，是指算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个令的有限序列，其中每条指令表示一个或多个操作。操作。 算法的五个特征：算法的五个特征：有穷性、确定性、可行性、有穷性、确定性、可行性、 输入、输出输入、输出 算法描述：算法描述：采用采用类类C C语言语言的形式，有时也用自然的形式，有时也用自然语言。注释部分用语言。注释部分用/或或/ /* *.* */ /表示。表示。3.1.3 3.1.3 算法与算法分析算法与算法分析13二、算法设计的要求：二、算法设计的要求：正确性、健壮性、效率与低存

9、储正确性、健壮性、效率与低存储三、算法评价标准：三、算法评价标准：时间复杂度、空间复杂度时间复杂度、空间复杂度一般时间复杂度考虑的较多。一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法，算法的分析一个可执行的算法不一定是一个好算法，算法的分析 通常用计算机执行时在通常用计算机执行时在时间时间和和空间空间两方面的消耗多少两方面的消耗多少作为评价该算法优劣的标准。作为评价该算法优劣的标准。 度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常有两种方法： 事后统计事后统计和和事前分析估算事前分析估算着重介绍方法。（算法、问题规模、语言、机器代码质量、机器执行指令的速度）3

10、.1.3 3.1.3 算法与算法分析算法与算法分析14一、时间复杂度一、时间复杂度1.1. 频度：频度：指一条语句重复执行的次数。记作：指一条语句重复执行的次数。记作：F(n)F(n)2.2. 算法的时间度量算法的时间度量：T(n)=O(F(n)T(n)=O(F(n)是问题规模是问题规模 n n 的某个函数的某个函数F(n),F(n),称为算法称为算法的渐进时间复杂度或时间复杂度。的渐进时间复杂度或时间复杂度。例：例：T(n)=3nT(n)=3n2 2 + 2n, + 2n, 则则 T(n)=O(nT(n)=O(n2 2) ) T(n)=3 T(n)=3n n + 2+ 2n n, ,则则 T

11、(n)=O(3T(n)=O(3n n) )3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步15“+x”“+x”的语句频度及三段程序的时间复杂度：的语句频度及三段程序的时间复杂度：(a)(a) (b) (b) (c) (c)F(n):F(n): 1 1 n n n n2 2T(n):T(n): O(1) O(1) O(n) O(n) O(n O(n2 2) )例例: : ( (a) +x;s=0a) +x;s=0 (b) for (i=1;i=n;+i) +x;s+=x; (b) for (i=1;i=n;+i) +x;s+=x; (c) for (j=1;j=n;+j) (c) f

12、or (j=1;j=n;+j)for (k=1;k=n;+k) +x;s+=x;for (k=1;k=n;+k) +x;s+=x;3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步16问题问题 ？有A、B两段程序同时运行，在某时刻A的运行速度是B的2倍，因此，A的算法复杂度比B低（即效率高）。3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步17 常见的时间复杂度常见的时间复杂度 1 1）O(1)O(1)：常量型常量型 2 2）O(n)O(n)、O(nO(n2 2) )、.、O(O(n nk k) )：多项式型多项式型 3 3）O(logO(log2 2n)n)、O(2lo

13、gO(2log2 2n)n)：对数型对数型 4 4）O(2O(2n n) )、O(eO(en n) )：指数型指数型按增长率排序，一般有：按增长率排序，一般有：1) 1) 3) 2) 4)3) 2) 4)T(n)n510 15 202n(n/2)35n2100n200log2n20003.1.4 3.1.4 算法与分析技术初步算法与分析技术初步18 当难以精确计算基本操作执行次数（或语句频当难以精确计算基本操作执行次数（或语句频度）情况下，只需求出关于度）情况下，只需求出关于 n n 的增长率或阶的增长率或阶即可。即可。 当难以确定各种输入数据集出现的概率时，平当难以确定各种输入数据集出现的概

14、率时，平均时间复杂度也难以确定时，可用最坏的情均时间复杂度也难以确定时，可用最坏的情况作为分析依据况作为分析依据 3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步19例：例：求下列程序段的时间复杂度求下列程序段的时间复杂度1.1. for (i=0; in; i+)for (i=0; in; i+)2.2. for (j=0; jn; j+)for (j=0; jn; j+)3.3. bij=0;bij=0;4.4. for (k=0; kn; k+)for (k=0; k 外层逐层分析外层逐层分析3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步24 5)5) 过程调用

15、语句：过程调用语句：a.a.非递归过程：根据过程调用的层次，由内而外分非递归过程：根据过程调用的层次，由内而外分 析程序的运行时间。析程序的运行时间。b.b.递归调用：可先对递归过程设一特定的运行时间递归调用：可先对递归过程设一特定的运行时间 函数函数T(n)T(n)，根据过程递归调用的情况，得到根据过程递归调用的情况，得到T(n)T(n) 的一个递推关系。的一个递推关系。 6)6) go to go to 语句：语句：可以最坏情况进行计算，即在遇到向可以最坏情况进行计算，即在遇到向下转移的下转移的go to go to 语句时，可认为语句时，可认为go to go to 语句所引起语句所引起

16、的控制转移根本没有发生；当遇到向上转移的的控制转移根本没有发生；当遇到向上转移的go go to to 语句时，则必须考虑它对程序运行时间的影响。语句时，则必须考虑它对程序运行时间的影响。3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步254.4. 时间复杂度计算举例时间复杂度计算举例 例1： (1) for ( i=1; i=i+1; -j ) (3) if ( Aj-1Aj ) (4)temp = Aj-1;(5)Aj-1=Aj;(6)Aj=temp; 分析：(4)(6): O(1)(3)(6): O(1)(2)(6): O(1(n-i) = O(n-i)(1)(6): T(n

17、)=O(n2)()(211nOinOni3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步26例2：for ( i=2 ; i= i ; -j) S ;求“S”语句的频度及整个程序段的算法复杂度分析：i=2：执行 n-1 次i=3：执行 n-2 次i=n-2；执行 3 次则：F(n) = 3+4+5+n-1 = (n-3)(n+2)/2 T(n) = O(n2)3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步27例3： i=1; While ( i=n) i=i*3 ;求语句的频度及整个程序段的算法复杂度分析：设句的频度为F(n)则：1log)( 33)(nnFnnFT(

18、n) = O(log3n)3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步28例4： prime( int n ) / n为一正整数 int i=2 ; while ( n%i)!=0 & i*1.0 sqrt(n)printf(“%d是一素数n”, n); elseprintf(“%d不是一素数n”, n);求算法的复杂度分析：设嵌套最深层语句“ i+”的频度为F(n),有：F(n)1.0= (y+1)(y+1) do y = y+1 ;求语句的频度和整个程序段的算法复杂度分析：F(n)F(n) 10 ) do if w 20 then w=w-10 ; k-elsew=

19、w+10;求语句的频度分析：对每一合法k值，句执行2次则，句频度F(n)= (21-10)2223.1.4 3.1.4 算法与分析技术初步算法与分析技术初步31例7： x = 87 ; y = 10 ; while ( y 0 ) if ( x 100 ) x - = 10 ; y - - ; else x + + ; 求语句的频度和整个算法的复杂度。分析：句频度F(n)= 15119114T(n)=O(1)3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步32例8： int fact ( int n)/ 计算n! (1)if ( n=1)(2)fact=1;else(3)fact=

20、n*fact(n-1) ; 计算程序段的时间复杂度1 , 1n ),1()(ndnTCnT3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步33例9： float p (n) int n; (1) if (n=1) return(n) ; (2) else return(p(n-1)+p(n-2);计算程序段的时间复杂度1 0, , 1n ),2() 1()(nndnTnTCnT3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步34二、空间复杂度二、空间复杂度 空间复杂度是指在算法中所需的辅助空间单空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间（因

21、为元而不包括问题的原始数据占用的空间（因为这些单元与算法无关），记作：这些单元与算法无关），记作：S(n)S(n) 时间与空间是一对矛盾。要节约空间往往就时间与空间是一对矛盾。要节约空间往往就要消耗较多时间，反之亦然，而目前由于计算要消耗较多时间，反之亦然，而目前由于计算机硬件的发展，一般都有足够的内存空间，因机硬件的发展，一般都有足够的内存空间，因此在分析中着重考虑时间的因素。此在分析中着重考虑时间的因素。3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步35 理解数据、数据元素、数据对象、逻辑结构理解数据、数据元素、数据对象、逻辑结构和物理结构、数据类型、数据结构、算法等基和物理

22、结构、数据类型、数据结构、算法等基本概念。本概念。 掌握频度、时间复杂度的计算。掌握频度、时间复杂度的计算。 了解空间复杂度。了解空间复杂度。3.1.5 3.1.5 小结小结363.2 3.2 线线 性性 表表3.2.13.2.1 线性表的定义和运算线性表的定义和运算3.2.2 3.2.2 顺序存储线性表顺序存储线性表3.2.3 3.2.3 线性链表线性链表3.2.4 3.2.4 向量和链表的比较向量和链表的比较3.2.5 3.2.5 小结小结3.2.6 3.2.6 作业作业373.2.13.2.1 线性表的定义和运算线性表的定义和运算1.1. 线性表的概念线性表的概念2.2. 线性表的逻辑结

23、构是n个数据元素的有限序列:L=(aL=(a1 1, a, a2 2 ,. ,.，a an n) ) L L为线性表，a ai i(i=1,.，n)是属于某数据对象的元素，n n为线性表的长度(n0)，n=0的表称为空表。2. 2. 线性表的定义线性表的定义 L=L=（D D，R R）2 ,11niDaaaaRiiii,.,21naaaD 383. 3. 线性表的结构特点线性表的结构特点表中的数据元素为同一数据类型数据元素之间是线性关系每个元素有且只有一个前趋元素有且只有一个前趋元素(第一个元素除外)，每个元素有且只有一个后继元素有且只有一个后继元素(最后一个元素除外)3.2.13.2.1 线

24、性表的定义和运算线性表的定义和运算394.4. 有序表与无序表的概念有序表与无序表的概念 若线性表中的数据元素相互之间可以比较，且aiai+1 ，i=2，3，.，n（或aiai+1 ，i=1，2，.，n-1），则称该线性表为有序表有序表，否则称为无序表无序表。5.5. 线性表的基本运算线性表的基本运算 插入、删除、查找、排序等。(按位置、按值)3.2.13.2.1 线性表的定义和运算线性表的定义和运算403.2.2 3.2.2 顺序存储线性表顺序存储线性表（顺序表顺序表）一、顺序存储结构一、顺序存储结构 用一组地址连续的存储单元存放线性表的数据元素（也称为向量式存储结构） 该结构用高级语言中的

25、一维数组类型表示。 例如：可用一维数组AnAn来存储线性表：（a a1 1, a, a2 2 ,. ,.，a an n）。）。 地址计算： addraddr( (a ai i)=)=addraddr(a(a1 1)+(i-1)+(i-1)* *L L 特点：随机存储结构(查找方便)。41例：例：a1a2a3a4a5a62000H2001H2005Haddr(a4) = addr(a1) + (i-1)L = 2000H+(4-1)1=2003H3.2.2 3.2.2 顺序存储线性表顺序存储线性表 42二、顺序存储结构的插入与删除二、顺序存储结构的插入与删除1.1.插入插入1)1)概念：概念：有

26、线性表(a1,a2 ,.，an)，长度为n，要在第i-1i-1与第i i个元素之间插入一个新元素。使得线性表变为：( (a a1 1,a,a2 2 ,. ,. a ai i-1-1,x, ,x, a ai i,.,a,.,an n) ), 长度为n+1。2)2)插入过程：插入过程：将ai至an依次后移一个位置(共移动n-i+1n-i+1个元素)，然后将新元素插入在第i个位置上( (合法位置：合法位置：1=1=i=n+1i=n+1)。请参见教材教材2727页图页图2-32-3所示。3.2.2 3.2.2 顺序存储线性表顺序存储线性表 433)3)算法描述算法描述intint InsertList

27、InsertList(Lm,n,i,x) (Lm,n,i,x) /形式参数形式参数 if (in+1) return(0); if (in+1) return(0); /位置非法位置非法for (j=n;j=i;j-)for (j=n;j=i;j-)Lj+1=Lj; Lj+1=Lj; /移动元素移动元素Li=x; Li=x; /插入元素插入元素n+; n+; /长度加长度加1 1return(1); return(1); /执行成功，返回执行成功，返回 3.2.2 3.2.2 顺序存储线性表顺序存储线性表 442.2. 删除删除1 1）概念：）概念：删除第i个位置上的元素，使线性表的长度由n变

28、为n-1。2 2）删除过程：）删除过程：ai+1an依次前移一个位置(共移动n-in-i个元素) 。(合法位置：合法位置：1=1=i=ni=n)参见教教材材2727页图页图2-42-4所示。3.2.2 3.2.2 顺序存储线性表顺序存储线性表 453 3）算法描述）算法描述intint DeleteListDeleteList(Lm,n,i)(Lm,n,i) if (in) return(0); if (in) return(0); /参数不合法参数不合法for (j=i;j=n-1;j+)for (j=i;j=n-1;j+) Lj=Lj+1; Lj=Lj+1; /前移前移n-; n-; /表

29、长减表长减1 1 return(1); return(1); 3.2.2 3.2.2 顺序存储线性表顺序存储线性表 463.3. 运算的时间分析运算的时间分析 在插入和删除运算中，时间主要消耗在移动元素上。 设pi在第i个元素前插入一个元素的概率，则在长度为n的线性表中插入一个元素所需的平均移动次数为：11)1(niiininpE3.2.2 3.2.2 顺序存储线性表顺序存储线性表 47在等概率情况下，pi=1/(n+1)，则有：112)1(11niinninnEniideinqE1)(21)(11ninnEnide 同理，删除时有：在等概率情况下，qi=1/n，则有：问题：顺序表插入、删除的

30、时间复杂度？O(n)3.2.2 3.2.2 顺序存储线性表顺序存储线性表 484.4.顺序表特点：顺序表特点： 优点：存储效率高、查找方便。 缺点：1)插入删除代价高(插入或删除一个元素，平均需要移动表中一半的元素移动表中一半的元素),仅适用于不经常进行插入和删除运算以及表中元素相对稳定的场合。2)要求连续存储区，管理不灵活，元素删除后不能释放空间。3.2.2 3.2.2 顺序存储线性表顺序存储线性表 49三、顺序存储结构的应用举例三、顺序存储结构的应用举例 2. 2.顺序表合并顺序表合并 将两个有序顺序表A（有m个元素）和B（有n个元素），合并为一个有序线性表C。3.2.2 3.2.2 顺序

31、存储线性表顺序存储线性表 50解：LINK (A, m, B, n, C) i=0; j=0; t=0; k=0;while (im & jn)/扫描A和B，将当前较小者赋给C if (Ai Bj) Ck+=Bj+; else Ck+=Bj+; /相等者只保存一个i+; if ( i= =m)/B未完，将B余下的元素赋给Cfor (t=j; tn; t+)Ck+=Bt;if ( j= =n) /A未完，将A余下的元素赋给Cfor (t=i; tdata;a1-next;）3.2.3 3.2.3 线性链表线性链表53二、线性链表的逻辑结构二、线性链表的逻辑结构2.2. 线性链表的特点线性

32、链表的特点 存储单元不要求连续，插入和删除方便； 要求较多的存储空间（存放指针域）。a2 1008data nextdata nexta1 1002data nexta4nila3 10071000100110021003100410051006100710081009地址head内存3.2.3 3.2.3 线性链表线性链表54三、单链表三、单链表1.1. 基本概念：基本概念：每个结点只有一个指针域的链表。 结点定义：结点定义：typedeftypedef structstruct node node char data; char data; structstruct node node *

33、 *next;next; NODE; NODE; 3.2.3 3.2.3 线性链表线性链表55三、单链表三、单链表2.2. 线性链表的基本运算线性链表的基本运算（1 1）基本操作基本操作 3.2.3 3.2.3 线性链表线性链表1 1）指针赋值：）指针赋值：s=p;q=p-next;s=p;q=p-next; 2 2）指针移动：指针移动：p=p-next;)p=p-next;)3 3）后插：）后插：s-next=p-nexts-next=p-next；p-next=sp-next=s；4 4）前插：前插：q=headq=head；while(q-next!=p) q=q-next;while(

34、q-next!=p) q=q-next;q-next=sq-next=s；s-next=ps-next=p；56pppspsheadpsheadqpsppsq1 1）指针赋值：）指针赋值：s=p;q=p-next;s=p;q=p-next; 2 2）指针移动：指针移动：p=p-next;)p=p-next;)3 3）后插：）后插：s-next=p-nexts-next=p-next；p-next=sp-next=s；4 4）前插：前插：q=headq=head；while(q-next!=p) q=q-next;while(q-next!=p) q=q-next;q-next=sq-next=

35、s；s-next=ps-next=p；57（2 2）结点的动态生成及回收结点的动态生成及回收 动态生成：GETNODEGETNODE（P P）; ;datadata（P P） data=b;） C语言中的实现：(包含头文件“alloc.h”) intint Get(NODE Get(NODE * *P)P) P=(NODE P=(NODE * *) )mallocmalloc( (sizeofsizeof(NODE);(NODE); if (!P) return(0); if (!P) return(0); else return(1); else return(1); 回收：RETRET（P

36、 P）; ; C语言中的实现：freefree（P P）; ;3.2.3 3.2.3 线性链表线性链表58NODE NODE * *CreateListCreateList( (intint n) n) /建立有建立有n n个结点的单链表个结点的单链表 NODE NODE * *h=NULL,h=NULL,* *pre=NULL,pre=NULL,* *s;s; /定义变量定义变量for (i=0;in;i+)for (i=0;idata); s-(“%d”,&s-data); s-next=NULL;next=NULL; /生成结点并赋值生成结点并赋值 if (h=NULL) h=s

37、;if (h=NULL) h=s; else pre-next=s; else pre-next=s; pre=s;pre=s; /结点指针链接结点指针链接 return(h);return(h); /返回链表头指针返回链表头指针 三、单链表三、单链表3.3.线性链表的建立线性链表的建立（补充补充）3.2.3 3.2.3 线性链表线性链表591 1）问题描述：问题描述：在值为a的结点前插入一个值为x的结点。若链表为空，则x成为其头结点；若表中无a元素，则将x插入表尾。aHeadHeadx x qss-next=q-next; q-next=s;s-next=q-next; q-next=s;三

38、、单链表三、单链表4.4.插入运算插入运算3.2.3 3.2.3 线性链表线性链表602 2）算法描述算法描述InsertListInsertList(head,a,x)(head,a,x) GETNODE(p); p-data = x;GETNODE(p); p-data = x; /取得一个新结点取得一个新结点p p if (head=NULL) then if (head=NULL) then /空表空表 head=p; p-next = NULL; return; head=p; p-next = NULL; return; if (head-data=a)then if (head-

39、data=a)then /a/a为头结点为头结点 p-p-next = head; head = p; return; next = head; head = p; return; q=head; q=head; while (q-next!=NULL & q-next-data!=a) while (q-next!=NULL & q-next-data!=a) q =q- next; q =q- next; /查找查找a a之前的结点之前的结点q q p-p-next = q-next;next = q-next; q-next = p; q-next = p; /完成插入完

40、成插入 LOOKFOR(head,a,q)3.2.3 3.2.3 线性链表线性链表611 1）问题描述：问题描述：将值为a的结点删除。headheada pqp=q-next; q-next=p-next;free(p);p=q-next; q-next=p-next;free(p);三、单链表三、单链表5.5.删除运算删除运算3.2.3 3.2.3 线性链表线性链表622 2）算法描述算法描述 DeleteListDeleteList(head,a)(head,a) if (head=NULL) return; if (head=NULL) return; /空表空表 if (head-da

41、ta=a)thenif (head-data=a)then /a/a为头结点为头结点 p=head; head=head-next; free(p); return; p=head; head=head-next; free(p); return; LOOKFOR(head,a,q); LOOKFOR(head,a,q); if (q-next= =NULL) then return;if (q-next= =NULL) then return; p=q-next; p=q-next; q-next=p-next; q-next=p-next; free free(p);(p); /完成删除完

42、成删除return;return; 3.2.3 3.2.3 线性链表线性链表63三、单链表三、单链表5.5.算法运算时间分析算法运算时间分析在单链表中插入或删除一个结点时，仅需改变一个或两个指针，而无需移动元素。3.2.3 3.2.3 线性链表线性链表64 1）在链表的第一个结点之前附加一个头结点headhead（空表）（空表）四、线性链表的其他形式四、线性链表的其他形式1.1.带头结点的线性链表带头结点的线性链表头结点：头结点：数据域不 用，或用于存放其它信息，如表长。指针域指向链表的第一个结点。3.2.3 3.2.3 线性链表线性链表652）头结点的用处：可简化算法简化算法的形式，例如在插

43、入插入运算中，当表空表空时尚有头结点存在，因此头指针非空，当a a为表中第一个元素为表中第一个元素时，因有头结点存在，则在a结点之前插入一元素时不必修改头指针。3.2.3 3.2.3 线性链表线性链表66 表中最后一个结点指向表的第一个结点，整个链表形成一个环。（只要给定循环链表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始）四、线性链表的其他形式四、线性链表的其他形式2.2.循环链表循环链表headhead（空表）（空表）headhead（空表）（空表）3.2.3 3.2.3 线性链表线性链表67 优点：提高查找效率 思考：如何判断循环链表的表尾？（单链表：判断指针域为空）四

44、、线性链表的其他形式四、线性链表的其他形式2.2.循环链表循环链表3.2.3 3.2.3 线性链表线性链表68 逻辑结构:四、线性链表的其他形式四、线性链表的其他形式3.3.双向链表双向链表prior data nextheadhead（空表）（空表）headhead（空表）（空表）3.2.3 3.2.3 线性链表线性链表69四、线性链表的其他形式四、线性链表的其他形式3.3.双向链表双向链表 特点特点：一个结点有两个指针域，容易找到前驱。 双向链表的插入双向链表的插入：在P结点之后插入值为y的结点PxyqGETNODE(q);q-data=y;q-next=p-next;p-next=q;q

45、-next-prior = q;q-prior = p;3.2.3 3.2.3 线性链表线性链表70四、线性链表的其他形式四、线性链表的其他形式3.3.双向链表双向链表 双向链表的删除双向链表的删除：删除结点P。p-prior-next=p-next;p-next-prior =p-prior;free(p);Px3.2.3 3.2.3 线性链表线性链表71nniinxPxPxPPxP.)(10五、链表应用举例五、链表应用举例1.1.一元多项式相加一元多项式相加 结点结构：结点结构：每一个非零项构成链表中的一个结点， 结点由两个数据域和一个指针域构成：coef exp nextpi3.2.3

46、3.2.3 线性链表线性链表72 A(x)=3x14+2x8+1 B(x)=8x14-3x10+10 x6 C(x)=A(x)+B(x)设 pa, pb 指针（1）若指数相等，则系数相加，c(x)中建项（系数为0，不建）（2）若pa-exppb-exp 复抄pa所指项，反之，复抄pb所指项。-13 142810ah-18 14-3 1010 6bhcofexpch-11411-3102 810 61 0papbpc73structstruct node1 node1 * *addpolyaddpoly( (structstruct node1 node1 * *ah,ah, struct st

47、ruct node1 node1 * *bhbh) ) struct struct node1 node1 * *pa,pa,* *pbpb, ,* *pc,pc,* *chch, ,* *pp;pp; intint x,e; x,e; chch=(=(structstruct node1 node1 * *) )mallocmalloc(LEN);(LEN); chch-exp=-1; -exp=-1; chch-next=-next=chch; pc=; pc=chch; /; /* *建立新表头结点建立新表头结点* */ / pa=ah-next; pa=ah-next; pbpb= =bhbh-next; -next; while(pa-exp!=-1)|( while(pa-exp!=-1)|(pbpb-exp!