计算机软件技术基础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= 1，2，

3、3，4，5 中整数中整数1至至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 数据结构的概念数据结构的概念71.1.逻

5、辑结构：研究数据元素及其关系的数学特性，逻辑结构：研究数据元素及其关系的数学特性， 即数据元素间的逻辑关系。即数据元素间的逻辑关系。二元组二元组 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：Graph= (D, R)，其中D 1,

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

8、辑结构可采用不同的存储结构。同一种逻辑结构可采用不同的存储结构。3.1.2 3.1.2 数据的逻辑结构和物理结构数据的逻辑结构和物理结构12一、什么是算法一、什么是算法 算法是对特定问题求解步骤的一种描述，是指算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个令的有限序列，其中每条指令表示一个或多个操作。操作。 算法的五个特征：有穷性、确定性、可行性、算法的五个特征：有穷性、确定性、可行性、 输入、输出输入、输出 算法描述：采用类算法描述：采用类C C语言的形式，有时也用自然语言的形式，有时也用自然语言。注释局部用语言。注释局部用/或或/ /* *.* */ /表

9、示。表示。3.1.3 3.1.3 算法与算法分析算法与算法分析13二、算法设计的要求：正确性、健壮性、效率与低存储二、算法设计的要求：正确性、健壮性、效率与低存储三、算法评价标准：时间复杂度、空间复杂度三、算法评价标准：时间复杂度、空间复杂度一般时间复杂度考虑的较多。一般时间复杂度考虑的较多。 一个可执行的算法不一定是一个好算法，算法的分一个可执行的算法不一定是一个好算法，算法的分析析 通常用计算机执行时在时间和空间两方面的消通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准。耗多少作为评价该算法优劣的标准。 度量一个程序的执行时间通常有两种方法：度量一个程序的执行时间通常

10、有两种方法： 事后统计和事前分析估算事后统计和事前分析估算着重介绍第二种方法。算法、问题规模、语言、机着重介绍第二种方法。算法、问题规模、语言、机器代码质量、机器执行指令的速度器代码质量、机器执行指令的速度3.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),称为算法的渐称为算法的渐进时间复杂度或时间复杂度

11、。进时间复杂度或时间复杂度。例：例：T(n)=3n2 + 2n, T(n)=3n2 + 2n, 那么那么 T(n)=O(n2) T(n)=O(n2) T(n)=3n + 2n, T(n)=3n + 2n, 那么那么 T(n)=O(3n) T(n)=O(3n)3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步15“+x“+x的语句频度及三段程序的时间复杂度：的语句频度及三段程序的时间复杂度：(a)(a) (b) (b) (c) (c)F(n):F(n): 1 1 n n n2 n2T(n):T(n): O(1) O(1) O(n) O(n) O(n2) O(n2)例例: : ( (a)

12、 +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) for (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.

13、1.4 算法与分析技术初步算法与分析技术初步17 常见的时间复杂度常见的时间复杂度 1 1O(1)O(1)：常量型：常量型 2 2O(n)O(n)、O(n2)O(n2)、.、O(nk)O(nk)：多项式型：多项式型 3 3O(log2n)O(log2n)、O(2log2n)O(2log2n)：对数型：对数型 4 4O(2n)O(2n)、O(en)O(en)：指数型：指数型按增长率排序，一般有：按增长率排序，一般有：1) 3) 2) 4)1) 3) 2) 4)T(n)n510 15 202n(n/2)35n2100n200log2n20003.1.4 3.1.4 算法与分析技术初步算法与分析技术

14、初步18 当难以精确计算根本操作执行次数或语句当难以精确计算根本操作执行次数或语句频度情况下，只需求出关于频度情况下，只需求出关于 n n 的增长率或的增长率或阶即可。阶即可。 当难以确定各种输入数据集出现的概率时，当难以确定各种输入数据集出现的概率时，平均时间复杂度也难以确定时，可用最坏的平均时间复杂度也难以确定时，可用最坏的情况作为分析依据情况作为分析依据 3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步19例：求以下程序段的时间复杂度例：求以下程序段的时间复杂度1. for (i=0; in; i+)1. for (i=0; in; i+)2. for (j=0; jn; j

15、+)2. for (j=0; jn; j+)3. bij=0;3. bij=0;4. for (k=0; kn; k+)4. for (k=0; k 外层逐层分析外层逐层分析3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步24 5) 5) 过程调用语句：过程调用语句：a.a.非递归过程：根据过程调用的层次，由内而外分非递归过程：根据过程调用的层次，由内而外分 析程序的运行时间。析程序的运行时间。b.b.递归调用：可先对递归过程设一特定的运行时间递归调用：可先对递归过程设一特定的运行时间 函数函数T(n)T(n)，根据过程递归调用的情况，得到，根据过程递归调用的情况，得到T(n)T(

16、n) 的一个递推关系。的一个递推关系。 6) go to 6) go to 语句：可以最坏情况进行计算，即在遇到向语句：可以最坏情况进行计算，即在遇到向下转移的下转移的go to go to 语句时，可认为语句时，可认为go to go to 语句所引起语句所引起的控制转移根本没有发生；当遇到向上转移的的控制转移根本没有发生；当遇到向上转移的go go to to 语句时，那么必须考虑它对程序运行时间的影响。语句时，那么必须考虑它对程序运行时间的影响。3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步254.4. 时间复杂度计算举例时间复杂度计算举例 例1： (1) for ( i=

17、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)=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

18、)(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(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);求算法的复

19、杂度分析：设嵌套最深层语句“ 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=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 + + ; 求语句的频度和整个算

20、法的复杂度。分析：句频度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=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,

21、, 1n ),2() 1()(nndnTnTCnT3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步34二、空间复杂度二、空间复杂度 空间复杂度是指在算法中所需的辅助空间空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间因单元而不包括问题的原始数据占用的空间因为这些单元与算法无关，记作：为这些单元与算法无关，记作：S(n)S(n) 时间与空间是一对矛盾。要节约空间往往时间与空间是一对矛盾。要节约空间往往就要消耗较多时间，反之亦然，而目前由于计就要消耗较多时间，反之亦然，而目前由于计算机硬件的开展，一般都有足够的内存空间，算机硬件的开展，一般都有足够的内存空间，因

22、此在分析中着重考虑时间的因素。因此在分析中着重考虑时间的因素。3.1.4 3.1.4 算法与分析技术初步算法与分析技术初步35 理解数据、数据元素、数据对象、逻辑结理解数据、数据元素、数据对象、逻辑结构和物理结构、数据类型、数据结构、算法等构和物理结构、数据类型、数据结构、算法等根本概念。根本概念。 掌握频度、时间复杂度的计算。掌握频度、时间复杂度的计算。 了解空间复杂度。了解空间复杂度。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 线性链

23、表线性链表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. 线性表的逻辑结构是线性表的逻辑结构是n n个数据元素的有限序个数据元素的有限序列列: :3.3.L=(a1, a2 ,.L=(a1, a2 ,.，an) an) 4.4. L L为线性表，为线性表，ai(i=1,.ai(i=1,.，n)n)是属于某数据是属于某数据对对象的元素，象的元素，n n为线性表的长度为线性表的长度(n0)(n0)，n=0n=0的表的表称为

24、空表。称为空表。5.5. 2. 2. 线性表的定义线性表的定义6.6. L= L=D D，R R2 ,11niDaaaaRiiii,.,21naaaD 383. 3. 线性表的结构特点线性表的结构特点表中的数据元素为同一数据类型数据元素之间是线性关系每个元素有且只有一个前趋元素有且只有一个前趋元素(第一个元素除外)，每个元素有且只有一个后继元素有且只有一个后继元素(最后一个元素除外)3.2.13.2.1 线性表的定义和运算线性表的定义和运算394.4. 有序表与无序表的概念有序表与无序表的概念5.5. 假设线性表中的数据元素相互之间可以比假设线性表中的数据元素相互之间可以比较，且较，且aiai

25、+1 aiai+1 ，i=2i=2，3 3，.，n n或或aiai+1 aiai+1 ，i=1i=1，2 2，.，n-1n-1，那么称该，那么称该线性表为有序表，否那么称为无序表。线性表为有序表，否那么称为无序表。6.6. 线性表的根本运算线性表的根本运算7.7. 插入、删除、查找、排序等。插入、删除、查找、排序等。( (按位置、按按位置、按值值) )3.2.13.2.1 线性表的定义和运算线性表的定义和运算403.2.2 3.2.2 顺序存储线性表顺序顺序存储线性表顺序表表一、顺序存储结构一、顺序存储结构 用一组地址连续的存储单元存放线性表的数据元用一组地址连续的存储单元存放线性表的数据元素

26、也称为向量式存储结构素也称为向量式存储结构 该结构用高级语言中的一维数组类型表示。该结构用高级语言中的一维数组类型表示。 例如：可用一维数组例如：可用一维数组AnAn来存储线性表：来存储线性表：a1, a2 ,.a1, a2 ,.，anan。 地址计算：地址计算： addr(ai)=addr(a1)+(i-1) addr(ai)=addr(a1)+(i-1)* *L L 特点：随机存储结构特点：随机存储结构( (查找方便查找方便) )。41例：例：a1a2a3a4a5a62000H2001H2005Haddr(a4) = addr(a1) + (i-1)L = 2000H+(4-1)1=200

27、3H3.2.2 3.2.2 顺序存储线性表顺序存储线性表 42二、顺序存储结构的插入与删除二、顺序存储结构的插入与删除1.1.插入插入1)1)概念：概念：有线性表(a1,a2 ,.，an)，长度为n，要在第i-1i-1与第i i个元素之间插入一个新元素。使得线性表变为：( (a a1 1,a,a2 2 ,. a,. ai-1i-1,x, a,x, ai i,.,a,.,an n) ), 长度为n+1。2)2)插入过程：插入过程：将ai至an依次后移一个位置(共移动n-i+1n-i+1个元素)，然后将新元素插入在第i个位置上( (合法位置：合法位置：1=1=i=n+1i=n+1)。请参见教材教材

28、2727页图页图2-32-3所示。3.2.2 3.2.2 顺序存储线性表顺序存储线性表 433)3)算法描述算法描述int InsertList(Lm,n,i,x) int InsertList(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); /执行成功，返回执行成

29、功，返回 3.2.2 3.2.2 顺序存储线性表顺序存储线性表 442. 2. 删除删除1 1概念：删除第概念：删除第i i个位置上的元素，使线个位置上的元素，使线性表的长度由性表的长度由n n变为变为n-1n-1。2 2删除过程：删除过程：ai+1ai+1anan依次前移一个位置依次前移一个位置( (共移动共移动n-in-i个元素个元素) ) 。( (合法位置：合法位置：1=i=n)1=i=n)参见教材参见教材2727页图页图2-42-4所示。所示。3.2.2 3.2.2 顺序存储线性表顺序存储线性表 453 3算法描述算法描述int DeleteList(Lm,n,i)int Delete

30、List(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-; /表长表长减减1 1 return(1); return(1); 3.2.2 3.2.2 顺序存储线性表顺序存储线性表 463.3. 运算的时间分析运算的时间分析4.4. 在插入和删除运算中，时间主要消耗在在插入和删除运算中，时间主要消耗在移动元素上。移动元素上。5.5. 设设pipi在第在第i i个元素前插入一个元素的个元素前插入

31、一个元素的概率，那么在长度为概率，那么在长度为n n的线性表中插入一个元的线性表中插入一个元素所需的平均移动次数为：素所需的平均移动次数为：11)1(niiininpE3.2.2 3.2.2 顺序存储线性表顺序存储线性表 47在等概率情况下，pi=1/(n+1)，那么有：112)1(11niinninnEniideinqE1)(21)(11ninnEnide 同理，删除时有：在等概率情况下，qi=1/n，那么有：问题：顺序表插入、删除的时间复杂度？O(n)3.2.2 3.2.2 顺序存储线性表顺序存储线性表 484.4.顺序表特点：顺序表特点： 优点：存储效率高、查找方便。 缺点：1)插入删除

32、代价高(插入或删除一个元素，平均需要移动表中一半的元素移动表中一半的元素),仅适用于不经常进行插入和删除运算以及表中元素相对稳定的场合。2)要求连续存储区，管理不灵活，元素删除后不能释放空间。3.2.2 3.2.2 顺序存储线性表顺序存储线性表 49三、顺序存储结构的应用举例三、顺序存储结构的应用举例 2. 2.顺序表合并顺序表合并 将两个有序顺序表将两个有序顺序表A有有m个元素和个元素和B有有n个元素，合并为一个有序线性表个元素，合并为一个有序线性表C。3.2.2 3.2.2 顺序存储线性表顺序存储线性表 50解：LINK (A, m, B, n, C) i=0; j=0; t=0; k=0

33、;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-a1-data;a1-next;next;3.2.3 3.2.3 线性链表线性链表53二、线性链表的逻辑结构二、线性链表的逻辑结构2.2. 线性链表的特点线性链表的特点 存储单元不要求连续，插入和删除方便； 要求较多的存储空间存放指针域。a2 10

34、08data nextdata nexta1 1002data nexta4nila3 10071000100110021003100410051006100710081009地址head内存3.2.3 3.2.3 线性链表线性链表54三、单链表三、单链表1. 1. 根本概念：每个结点只有一个指针域的链表。根本概念：每个结点只有一个指针域的链表。 结点定义：结点定义：typedef struct node typedef struct node char data; char data; struct node struct node * *next;next; NODE; NODE; 3.2

35、.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(q-next!=p) q=q-next;q-next=sq-next

36、=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=s；s-next=ps-next=p；572 2结点的动态生成及回收结点的动态

37、生成及回收 动态生成：动态生成：GETNODEGETNODEP P; ;datadataP P data=b;p-data=b; C C语言中的实现：语言中的实现：( (包含头文件包含头文件“alloc.h“alloc.h) ) int Get(NODE int Get(NODE * *P)P) P=(NODE P=(NODE * *)malloc(sizeof(NODE);)malloc(sizeof(NODE); if (!P) return(0); if (!P) return(0); else return(1); else return(1); 回收：回收：RETRETP P; ;

38、C C语言中的实现：语言中的实现：freefreeP P; ;3.2.3 3.2.3 线性链表线性链表58NODE NODE * *CreateList(int n) /CreateList(int 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-,&s-data); s-next=NULL;next=NULL; /生成结点并赋值生成结点并赋值 if (h=NULL) h=s; if (

39、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 a的结点前插入一个的结点前插入一个值为值为x x的结点。假设链表为空，那么的结点。假设链表为空，那么x x成为成为其头结点；假设表中无其头结点；假设表中无a a元素，那么将元素，那么将x x插插入表尾。入表尾。aHeadH

40、eadx x qss-next=q-next; q-next=s;s-next=q-next; q-next=s;三、单链表三、单链表4.4.插入运算插入运算3.2.3 3.2.3 线性链表线性链表602 2算法描述算法描述InsertList(head,a,x)InsertList(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; head=p;

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

42、= q-next; p-next = q-next; q-next = p; / q-next = p; /完成插入完成插入 LOOKFOR(head,a,q)3.2.3 3.2.3 线性链表线性链表611 1问题描述：将值为问题描述：将值为a 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算法描述算法描述 DeleteList(head,a) DeleteList(he

43、ad,a) if (head=NULL) return; / if (head=NULL) return; /空表空表 if (head-data=a)then /a if (head-data=a)then /a为头结点为头结点 p=head; head=head-next; free(p); p=head; head=head-next; free(p); return; return; LOOKFOR(head,a,q); LOOKFOR(head,a,q); if (q-next= =NULL) then return; if (q-next= =NULL) then return;

44、p=q-next; p=q-next; q-next=p-next; q-next=p-next; free(p); / free(p); /完成删除完成删除return;return; 3.2.3 3.2.3 线性链表线性链表63三、单链表三、单链表5.5.算法运算时间分析算法运算时间分析在单链表中插入或删除一个结点时，仅需改变一个或两个指针，而无需移动元素。3.2.3 3.2.3 线性链表线性链表64 1 1在链表的第一个结点之前附加一个头结点在链表的第一个结点之前附加一个头结点headhead（空表）（空表）四、线性链表的其他形式四、线性链表的其他形式1.1.带头结点的线性链表带头结点的

45、线性链表头结点：头结点：数据域不 用，或用于存放其它信息，如表长。指针域指向链表的第一个结点。3.2.3 3.2.3 线性链表线性链表652 2头结点的用处：可简化算法的形式，例如头结点的用处：可简化算法的形式，例如在插入运算中，当表空时尚有头结点存在，因在插入运算中，当表空时尚有头结点存在，因此头指针非空，当此头指针非空，当a a为表中第一个元素时，因为表中第一个元素时，因有头结点存在，那么在有头结点存在，那么在a a结点之前插入一元素结点之前插入一元素时不必修改头指针。时不必修改头指针。3.2.3 3.2.3 线性链表线性链表66 表中最后一个结点指向表的第一个结点，表中最后一个结点指向表

46、的第一个结点，整个链表形成一个环。只要给定循环链整个链表形成一个环。只要给定循环链表中任一结点的地址，就可以查遍表中所表中任一结点的地址，就可以查遍表中所有的结点，而不必从头指针开始有的结点，而不必从头指针开始四、线性链表的其他形式四、线性链表的其他形式2.2.循环链表循环链表headhead（空表）（空表）headhead（空表）（空表）3.2.3 3.2.3 线性链表线性链表67 优点：提高查找效率优点：提高查找效率 思考：如何判断循环链表的表尾？思考：如何判断循环链表的表尾？单链表：判断指针域为空单链表：判断指针域为空四、线性链表的其他形式四、线性链表的其他形式2.2.循环链表循环链表3

47、.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-next-prior = q;q-prior = p;3.2.3

48、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 3.2.3 线性链表线性链表72 A(x)=3x14+2x8+1 B

49、(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 0papbpc73struct node1 struct node1 * *addpoly(struct node1 addpoly(struct node1 * *ah, struct node1 ah, struct node1 * *bh)bh) struct n

50、ode1 struct node1 * *pa,pa,* *pb,pb,* *pc,pc,* *ch,ch,* *pp;pp; int x,e; int x,e; ch=(struct node1 ch=(struct node1 * *)malloc(LEN);)malloc(LEN); ch-exp=-1; ch-next=ch; pc=ch; / ch-exp=-1; ch-next=ch; pc=ch; /* *建立新表头结点建立新表头结点* */ / pa=ah-next; pb=bh-next; pa=ah-next; pb=bh-next; while(pa-exp!=-1)|(

51、pb-exp!=-1) while(pa-exp!=-1)|(pb-exp!=-1) if( pa-exp=pb-exp) if( pa-exp=pb-exp) x=pa-cof+pb-cof; e=pa-exp; / x=pa-cof+pb-cof; e=pa-exp; /* *系数相加系数相加* */ / pa=pa-next; pb=pb-next pa=pa-next; pb=pb-next； / /* *修改指针修改指针* */ / 3.2.3 3.2.3 线性链表线性链表74 else if (pa-exppb-exp) x=pa-cof; e=pa-exp; /*复抄复抄A(x)

52、*/ pa=pa-next; else x=pb-cof; e=pb-exp; /*复抄复抄B(x)*/ pb=pb-next; if (x!=0) /*形成新结点链入形成新结点链入C(x)*/ pp=(struct node1 *)malloc(LEN); pp-cof=x; pp-exp=e; pp-next=ch; pc-next=pp; pc=pp; return(ch); 3.2.3 3.2.3 线性链表线性链表75五、链表应用举例五、链表应用举例2.2.在带表头结点的单链表结构上查找值为在带表头结点的单链表结构上查找值为x x的结点的结点LOOKFOR(head, x, p)p=h

53、ead-next; for( ; p!=NULL & p-data!=x) p=p-next; return;3.2.3 3.2.3 线性链表线性链表76五、链表应用举例五、链表应用举例3.3.将两个有序单链表合并为一带表头的有序单链表将两个有序单链表合并为一带表头的有序单链表Merge (P1, P2) GETNODE(ch);GETNODE(ch); p=ch;p-next=NULL; p=ch;p-next=NULL; while(P1!=NULL)&(P2!=NULL) while(P1!=NULL)&(P2!=NULL) if(P1-datadata)if(P1-datadata)

54、p-next=P1; P1=P1-next; p-next=P1; P1=P1-next; else p-next=P2; P2=P2-next;else p-next=P2; P2=P2-next;p=p-next;p=p-next; If(P1!=NULL) p-next=P1;If(P1!=NULL) p-next=P1; If(P2!=NULL) p-next=P2; If(P2!=NULL) p-next=P2; P1=NULL; P1=NULL; P2=P1; P2=P1; return(ch); return(ch); 3.2.3 3.2.3 线性链表线性链表773.2.4 3.

55、2.4 向量和链表的比较向量和链表的比较 线性表的长度是否固定线性表的长度是否固定向量向量的存储空间是静态分配的，适用于表长固定的场合；链表链表的存储空间是动态分配的，适用于表长不固定的场合。 线性表的主要操作是什么线性表的主要操作是什么 向量向量是连续存放的，适用于频繁查找操作的表。链表链表适用于经常进行插入和删除的表。 采用的算法语言：采用的算法语言：链表要求指针类型变量。78 理解线性表的概念 熟悉线性表的顺序和链式两种存储结构 掌握顺序表的插入和删除算法 掌握链表的建立、遍历、插入和删除算法 掌握双向链表 的插入和删除操作 掌握应用实例，加深理解链表的各种操作 了解向量和链表各自的优缺点2.2.5 2.2.5 小结小结