计算机软件技术(第2~5章)课件及作业

1、电子工程学院 第二部分第二部分 数据结构数据结构 电子工程学院 2 数据结构的教学目的和要求数据结构的教学目的和要求 掌握线性表、栈、队列、串、数组、树、图等掌握线性表、栈、队列、串、数组、树、图等 数据的逻辑结构、存储结构及有关的算法，以及数数据的逻辑结构、存储结构及有关的算法，以及数 据的查找和排序方法。据的查找和排序方法。 使用类使用类C语言描述算法，能够分析算法和设计算语言描述算法，能够分析算法和设计算 法。法。 数据结构的学习过程也是较复杂程序设计的训数据结构的学习过程也是较复杂程序设计的训 练过程。在编写程序解决实际问题时，应当采用规练过程。在编写程序解决实际问题时，应当采用规 范

2、的算法，并且按照软件开发方法所要求的模块独范的算法，并且按照软件开发方法所要求的模块独 立性高的原则，设计出高质量的程序。立性高的原则，设计出高质量的程序。 电子工程学院 3 数据结构目录数据结构目录 数据结构概述数据结构概述 线性表线性表 栈栈 队列队列 串串 数组数组 树树 图图 查找查找 排序排序 电子工程学院 4 一、数据结构概述一、数据结构概述 主要内容：主要内容： 1. 数据结构的基本概念和术语数据结构的基本概念和术语 2. 算法的概念算法的概念 3. 算法的时间特性及时间复杂度的分析算法的时间特性及时间复杂度的分析 4. 算法的空间特性及空间复杂度的分析算法的空间特性及空间复杂度

3、的分析 电子工程学院 5 1.1 数据结构的基本概念和术语数据结构的基本概念和术语 数据：数字、字符以及所有能输入到计算机中数据：数字、字符以及所有能输入到计算机中 并被计算机程序处理的符号的集合。并被计算机程序处理的符号的集合。 例如：一个二维表是一个数据。例如：一个二维表是一个数据。 数据元素：数据的基本单位。数据元素也称为数据元素：数据的基本单位。数据元素也称为 元素、结点、顶点、记录。元素、结点、顶点、记录。 例如：二维表中的某一行是一个数据元素。例如：二维表中的某一行是一个数据元素。 数据项：一个数据元素可以由若干个数据项组数据项：一个数据元素可以由若干个数据项组 成，数据项是具有独

4、立含义的，不可再分割的最成，数据项是具有独立含义的，不可再分割的最 小标识单位。小标识单位。 例如：二维表中某一行的某一列是一个数据项。例如：二维表中某一行的某一列是一个数据项。 电子工程学院 6 数据结构：数据之间的相互关系，即数据的组织数据结构：数据之间的相互关系，即数据的组织 形式。形式。 数据结构所研究的主要内容包括以下三个方面：数据结构所研究的主要内容包括以下三个方面： （1）数据的逻辑结构）数据的逻辑结构数据元素之间的逻辑关数据元素之间的逻辑关 系系 （2）数据的存储结构）数据的存储结构数据结构在计算机中的数据结构在计算机中的 存储方法存储方法 （3）数据的运算）数据的运算对数据施

5、加的操作对数据施加的操作 电子工程学院 7 数据类型：确定了一个值域以及对该类型数据可数据类型：确定了一个值域以及对该类型数据可 以进行的操作。按以进行的操作。按“值值”是否可分解，可以将数据是否可分解，可以将数据 类型划分为两类：类型划分为两类： （1）原子类型，其值不可分解。）原子类型，其值不可分解。 如如C语言中的基本类型（整型、实型、字符型语言中的基本类型（整型、实型、字符型 等）、指针类型。等）、指针类型。 （2）结构类型，其值可分解为若干个成分。）结构类型，其值可分解为若干个成分。 如数组、结构体等类型的数据还可以进一步分如数组、结构体等类型的数据还可以进一步分 解。解。 电子工程

6、学院 8 数据的逻辑结构分为两大类：数据的逻辑结构分为两大类： （1）线性结构。其逻辑特征为：若数据结构是非）线性结构。其逻辑特征为：若数据结构是非 空集，第一个结点没有直接前趋结点，最后一个空集，第一个结点没有直接前趋结点，最后一个 结点没有直接后继结点，其余结点都有一个直接结点没有直接后继结点，其余结点都有一个直接 前趋结点和一个直接后继结点。线性表、栈、队前趋结点和一个直接后继结点。线性表、栈、队 列、串等都是线性结构。列、串等都是线性结构。 （2）非线性结构。其逻辑特征为：一个结点可能）非线性结构。其逻辑特征为：一个结点可能 有多个直接前趋和直接后继结点。树、图等属于有多个直接前趋和直

7、接后继结点。树、图等属于 非线性结构。非线性结构。 电子工程学院 9 数据的存储结构数据的存储结构可以有以下四种基本的存储方法可以有以下四种基本的存储方法 ： （1）顺序存储方法。结点间的逻辑关系由存储单）顺序存储方法。结点间的逻辑关系由存储单 元的邻接关系来体现。元的邻接关系来体现。 （2）链接存储方法。通过指示元素存储地址的指）链接存储方法。通过指示元素存储地址的指 针表示数据元素之间的逻辑关系，即逻辑上相针表示数据元素之间的逻辑关系，即逻辑上相 邻的结点在物理位置上不一定相邻。邻的结点在物理位置上不一定相邻。 （3）索引存储方法。在存储结点的同时，还建立）索引存储方法。在存储结点的同时，

8、还建立 附加的索引表，索引表中的每一项称为索引项附加的索引表，索引表中的每一项称为索引项 （索引项包括：关键字，地址），关键字是能（索引项包括：关键字，地址），关键字是能 够唯一标识一个结点的那些数据项。够唯一标识一个结点的那些数据项。 若每个结点在索引表中都有一个索引项，称若每个结点在索引表中都有一个索引项，称 为稠密索引；若一组结点在索引表中对应一为稠密索引；若一组结点在索引表中对应一 个索引项，称为稀疏索引。个索引项，称为稀疏索引。 电子工程学院 10 （4）散列存储方法。根据结点的关键字直接计算出）散列存储方法。根据结点的关键字直接计算出 该结点的存储地址。该结点的存储地址。 上述四种

9、基本的存储方法，既可以单独使用，上述四种基本的存储方法，既可以单独使用， 也可以组合起来对数据结构进行存储。例如采用也可以组合起来对数据结构进行存储。例如采用 拉链法表示散列表，是顺序存储方法与连接存储拉链法表示散列表，是顺序存储方法与连接存储 方法的组合。方法的组合。 同一种逻辑结构采用不同的存储方法，可以得同一种逻辑结构采用不同的存储方法，可以得 到不同的存储结构。到不同的存储结构。 例如线性表可以采用顺序存例如线性表可以采用顺序存 储结构（顺序表）和链式存储结构（链表）。储结构（顺序表）和链式存储结构（链表）。 电子工程学院 11 2.2 算法的描述和分析算法的描述和分析 1. 算法的概

10、念算法的概念 算法是对数据的操作或处理过程的描述。算法是对数据的操作或处理过程的描述。 注意：注意： （1）每一种数据的逻辑结构对应一组基本运算，）每一种数据的逻辑结构对应一组基本运算， 而基本运算的实现与数据的存储结构有关。而基本运算的实现与数据的存储结构有关。 （2）算法）算法+数据结构数据结构=程序程序 电子工程学院 12 算法是对特定问题求解步骤的描述，是指令的有算法是对特定问题求解步骤的描述，是指令的有 限序列。限序列。 算法必须满足以下性质：算法必须满足以下性质： （1）输入性：）输入性：0至多个输入。至多个输入。 （2）输出性：）输出性：1至多个输出。至多个输出。 （3）有穷性）

11、有穷性: 对于合法的输入值，算法在执行有对于合法的输入值，算法在执行有 穷步之后能够结束。穷步之后能够结束。 （4）确定性）确定性: 对于相同的输入执行相同的路径，对于相同的输入执行相同的路径， 即对于相同的输入只能得出相同的输出。即对于相同的输入只能得出相同的输出。 （5）可行性）可行性: 用于描述算法的操作都是足够基本用于描述算法的操作都是足够基本 的，即算法中描述的操作都是可以通过已经实现的，即算法中描述的操作都是可以通过已经实现 的基本运算执行有限次来实现的。的基本运算执行有限次来实现的。 电子工程学院 13 算法性能的评价标准：算法性能的评价标准： （1）算法的时间特性，执行算法所需

12、的计算时间）算法的时间特性，执行算法所需的计算时间 （2）算法的空间特性，执行算法所需的辅助存储）算法的空间特性，执行算法所需的辅助存储 空间空间 （3）算法应当易于理解，易于编码，易于调试）算法应当易于理解，易于编码，易于调试 上述性能要求常常相互抵触，要节约算法的执行上述性能要求常常相互抵触，要节约算法的执行 时间往往要以牺牲更多的空间为代价；而为了节时间往往要以牺牲更多的空间为代价；而为了节 省空间可能要耗费更多的计算时间。算法的时间省空间可能要耗费更多的计算时间。算法的时间 特性和空间特性都与问题的规模有关，因此我们特性和空间特性都与问题的规模有关，因此我们 只能根据具体情况有所侧重。

13、只能根据具体情况有所侧重。 可以通过教材可以通过教材216页表页表9.1，理解算法的时间特性，理解算法的时间特性 和空间特性相互抵触的情况。和空间特性相互抵触的情况。 电子工程学院 14 2. 算法的时间特性算法的时间特性 一个算法所需的计算时间，应当是该算法中每一个算法所需的计算时间，应当是该算法中每 条语句的执行时间之和，而每条语句的执行时间条语句的执行时间之和，而每条语句的执行时间 是该语句的执行次数（称为频度）与该语句执行是该语句的执行次数（称为频度）与该语句执行 一次所需时间的乘积。一次所需时间的乘积。 我们假设每条语句执行一次所需的时间均是单我们假设每条语句执行一次所需的时间均是单

14、 位时间，一个算法的计算时间就是该算法中所有位时间，一个算法的计算时间就是该算法中所有 语句的频度之和。语句的频度之和。 通常用算法的时间复杂度来衡量算法的时间特通常用算法的时间复杂度来衡量算法的时间特 性。性。 电子工程学院 15 【例例2.2】求两个求两个n阶方阵的乘积阶方阵的乘积CAB，其算法，其算法 如下：如下： define n 自然数自然数 void MATRIXMLT(int Ann, int Bnn,int Cnn) int i,j,k; for(i=0;in;i+) for (j=0；jn;j+) Cij=0; for(k=0;kn;k+) Cij=Cij+Aik*Bkj;

15、各语句的频度各语句的频度 n+1 n(n+1) n2 n2(n+1) n3 电子工程学院 16 该算法中所有语句的频度之和为：该算法中所有语句的频度之和为： T(n)=2n3+3n2+2n+1 T(n)是矩阵阶数是矩阵阶数n的函数，的函数，n是算法求解方阵乘是算法求解方阵乘 积问题的规模。积问题的规模。 时间复杂度时间复杂度取取T(n)的数量级，记为：的数量级，记为： T(n) = O(f(n) 上述算法的时间复杂度为上述算法的时间复杂度为O(n3) 当有循环或循环嵌套时，算法的时间复杂度是由当有循环或循环嵌套时，算法的时间复杂度是由 最内层语句的频度最内层语句的频度f(n)决定的。决定的。

16、电子工程学院 17 【例例2.3】交换交换a和和b的值。的值。 temp=a; a=b; b=temp; 该算法的执行时间是一个与问题规模该算法的执行时间是一个与问题规模n无关的常无关的常 数，时间复杂度记作数，时间复杂度记作T(n)=O(1)。 即使算法中的每条语句执行了若干次，只要算即使算法中的每条语句执行了若干次，只要算 法的执行时间不随着问题的规模增加而增长，其法的执行时间不随着问题的规模增加而增长，其 时间复杂度为时间复杂度为O(1)。 电子工程学院 18 【例例2.4】判断判断n是否为素数。是否为素数。 void prime(int n) int i=2; while(n%i)!=

17、0 else printf(%d 不是素数不是素数,n); 设语句设语句i+；的频度为；的频度为f(n)，由，由isqrt(n)可知可知 f(n)sqrt(n)，时间复杂度应考虑最坏的情况，时间复杂度应考虑最坏的情况， 所以所以 )()()(nOnfOnT 电子工程学院 19 【例例2.5】变量计数。变量计数。 i=1； 1 while(i0）记作）记作 (a1,ai-1,ai,ai+1,an) 线性表中各元素具有相同的特性（类型）；线性表中各元素具有相同的特性（类型）； i是数据元素是数据元素ai在线性表中的位序；在线性表中的位序； 对于一个非空线性表，有且仅有一个开始结点对于一个非空线性表

18、，有且仅有一个开始结点a1； 有且仅有一个终端结点有且仅有一个终端结点an；除第一个结点外，其余；除第一个结点外，其余 结点结点ai（2in) 有且仅有一个直接前趋有且仅有一个直接前趋ai-1；除最后；除最后 一个结点外，其余结点一个结点外，其余结点ai（1in-1) 有且仅有一个有且仅有一个 直接后继直接后继ai+1。 电子工程学院 24 线性表的基本运算：线性表的基本运算： （1）InitList( while(i=Length(La) x=Get(La,i); /取取ai if(x%2= =0) Insert(Lb,x,j); j+; Delete(La,i); / ai是偶数，插入到是

19、偶数，插入到B表末尾，并从表末尾，并从A表中删除表中删除 else i+; / ai是奇数，仍放在是奇数，仍放在A表中表中 /O(Length(la) 电子工程学院 27 【例例3.1】算法分析（算法分析（1） 初始状态：初始状态： i=1 j=1 A表长度表长度Length(La)=5 B表长度表长度Length(Lb)=0 电子工程学院 28 【例例3.1】算法分析（算法分析（2） 取取a1，x=25为奇数，保留在为奇数，保留在A表。表。 while(i=Length(La) x=Get(La,i); if(x%2= =0) Insert(Lb,x,j); j+; Delete(La,i)

20、; else i+; i=2 电子工程学院 29 【例例3.1】算法分析（算法分析（3） 取取a2，x=38为偶数，插入到为偶数，插入到B表，并从表，并从A表删除表删除a2 。 while(i=Length(La) x=Get(La,i); if(x%2= =0) Insert(Lb,x,j); j+; Delete(La,i); else i+; i=2 j=2 电子工程学院 30 【例例3.1】算法分析（算法分析（4） 取取a2，x=18为偶数，插入到为偶数，插入到B表，并从表，并从A表删除表删除a2 。 while(i=Length(La) x=Get(La,i); if(x%2= =0

21、) Insert(Lb,x,j); j+; Delete(La,i); else i+; i=2 j=3 电子工程学院 31 【例例3.1】算法分析（算法分析（5） 取取a2，x=7为奇数，保留在为奇数，保留在A表。表。 while(i=Length(La) x=Get(La,i); if(x%2= =0) Insert(Lb,x,j); j+; Delete(La,i); else i+; i=3 电子工程学院 32 【例例3.1】算法分析（算法分析（6） 取取a3，x=13为奇数，保留在为奇数，保留在A表。表。 while(i=Length(La) x=Get(La,i); if(x%2=

22、 =0) Insert(Lb,x,j); j+; Delete(La,i); else i+; i=4 电子工程学院 33 【例例】求求A = A B，即将存在于，即将存在于B中，而不存在于中，而不存在于 A中的元素插入到中的元素插入到A中。中。 分析：将分析：将B中不存在于中不存在于A中的元素插入到中的元素插入到A原有元原有元 素之后。素之后。 void union_list(Linear_list*La,Linear_list*Lb) La_len=Length(La); Lb_len=Length(Lb); for(i=1;ibj void mergelist(Linear_list L

23、a,Linear_list Lb,Linear_list*Lc) /在调用算法之前，已建立线性表在调用算法之前，已建立线性表La、Lb和空线性表和空线性表Lc i=j=1;k=0; La_len=Length(La); Lb_len=Length(Lb); while(i=La_len bj=Get(Lb,j); if(ai=bj) Insert(Lc,ai,+k); i+; else Insert(Lc;bj,+k); j+; /循环结束之后，将循环结束之后，将La或或Lb的剩余部分插入到的剩余部分插入到Lc中中 while(i=La_len) ai=Get(La,i); Insert(Lc

24、,ai,+k); i+; while(j=Lb_len) bj=Get(Lb,j); Insert(Lc,bj,+k); j+; /O(Length(La)+Length(Lb) 假设假设Get、Insert运算与问题的规模无关运算与问题的规模无关 电子工程学院 35 【例例】算法分析（算法分析（1） 初始状态：初始状态： i=1 j=1 K=0 La表长度表长度Length(La)=4 Lb表长度表长度Length(Lb)=3 Lc表长度表长度Length(Lc)=0 电子工程学院 36 【例例】算法分析（算法分析（2） while(i=La_len bj=Get(Lb,j); if(ai=

25、bj) Insert(Lc,ai,+k); i+; else Insert(Lc;bj,+k); j+; i=1， j=2 K=1 La表长度表长度Length(La)=4 Lb表长度表长度Length(Lb)=3 Lc表长度表长度Length(Lc)=1 电子工程学院 37 【例例】算法分析（算法分析（3） while(i=La_len bj=Get(Lb,j); if(ai=bj) Insert(Lc,ai,+k); i+; else Insert(Lc;bj,+k); j+; i=2， j=2 K=2 La表长度表长度Length(La)=4 Lb表长度表长度Length(Lb)=3 L

26、c表长度表长度Length(Lc)=2 电子工程学院 38 【例例】算法分析（算法分析（4） while(i=La_len bj=Get(Lb,j); if(ai=bj) Insert(Lc,ai,+k); i+; else Insert(Lc;bj,+k); j+; i=2， j=3 K=3 La表长度表长度Length(La)=4 Lb表长度表长度Length(Lb)=3 Lc表长度表长度Length(Lc)=3 电子工程学院 39 【例例】算法分析（算法分析（5） while(i=La_len bj=Get(Lb,j); if(ai=bj) Insert(Lc,ai,+k); i+; e

27、lse Insert(Lc;bj,+k); j+; i=3， j=3 K=4 La表长度表长度Length(La)=4 Lb表长度表长度Length(Lb)=3 Lc表长度表长度Length(Lc)=4 电子工程学院 40 【例例】算法分析（算法分析（6） while(i=La_len bj=Get(Lb,j); if(ai=bj) Insert(Lc,ai,+k); i+; else Insert(Lc;bj,+k); j+; i=3， j=4 K=4 La表长度表长度Length(La)=4 Lb表长度表长度Length(Lb)=3 Lc表长度表长度Length(Lc)=5 电子工程学院

28、41 【例例】算法分析（算法分析（7） /循环结束之后，将循环结束之后，将La或或Lb的剩余部分插入到的剩余部分插入到Lc中中 while(i=La_len) ai=Get(La,i); Insert(Lc,ai,+k); i+; while(jdata1和和L-dataL-last 中中 L-last表示线性表当前的长度表示线性表当前的长度 电子工程学院 45 n顺序表上实现的基本运算顺序表上实现的基本运算 通过函数的参数将结果带回到主调函数，也可以通过函通过函数的参数将结果带回到主调函数，也可以通过函 数返回值将结果带回到主调函数。数返回值将结果带回到主调函数。 通过函数的参数将结果带回到

29、主调函数。由于在函数中通过函数的参数将结果带回到主调函数。由于在函数中 改变了指针的指向，所以参数的类型为指针的引用。调用改变了指针的指向，所以参数的类型为指针的引用。调用 形式：形式：InitList(L); void InitList(sequenlist* L- last=0; /时间复杂度为时间复杂度为O(1) 电子工程学院 46 通过函数返回值将结果带回到主调函数。通过函数返回值将结果带回到主调函数。 调用形式：调用形式：L=InitList(); sequenlist*InitList( ) sequenlist*L=(sequenlist*)malloc(sizeof(seque

30、nlist); L- last=0; return L; /时间复杂度为时间复杂度为O(1) 电子工程学院 47 （2）线性表的第）线性表的第i（1in+1）个位置上（第）个位置上（第i个结个结 点之前）插入一个新结点点之前）插入一个新结点 int Insert(sequenlist*L,datatype x,int i) /将新结点插入顺序表的第将新结点插入顺序表的第i个位置个位置 /插入成功，返回插入成功，返回1；不成功，返回；不成功，返回0 int j; if(L-last=maxsize-1) print (表已满表已满); return 0; else if(iL-last+1) p

31、rint (非法插入位置非法插入位置); return 0; else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; /结点结点anai依次后移依次后移 L-datai=x; /插入到插入到L-datai中中 L-last+; /表长度加表长度加1 return 1; 电子工程学院 48 顺序表插入结点的过程顺序表插入结点的过程 电子工程学院 49 在等概率下插入一个结点，平均移动一半元素在等概率下插入一个结点，平均移动一半元素 n 1i iis 1)i -(np(n)E 2 n 1)i -(n 1n 1 (n)E n 1i is 插入位置等概率插入位置等概率

32、 插入位置等概率插入位置等概率 电子工程学院 50 （3）删除顺序表中的第）删除顺序表中的第i（1in）个结点）个结点 int Delete(sequenlist*L,int i) /删除顺序表的第删除顺序表的第i个结点。删除成功，返回个结点。删除成功，返回1；不成功，返回；不成功，返回0 int j; if (iL-last) print(非法删除位置非法删除位置); return 0; else for(j=i;jlast-1; j+) L-dataj=L-dataj+1; /结点结点ai+1an依次前移依次前移 L-last-; /表长度减表长度减1 return 1； 电子工程学院 5

33、1 顺序表删除结点的过程顺序表删除结点的过程 删除后顺序表的长度为删除后顺序表的长度为n-1 电子工程学院 52 n在等概率下删除一个结点，平均移动一半元素在等概率下删除一个结点，平均移动一半元素 n 1i ide i)-(np(n)E n 1 pi 2 1-n i)-(n n 1 (n)E n 1i de 其中其中 电子工程学院 53 int Locate(sequenlist*L,datatype x) /在顺序表中查找第一个值与在顺序表中查找第一个值与x相同的元素相同的元素 /查找成功，返回该元素的位序；不成功，返回查找成功，返回该元素的位序；不成功，返回0 i=1; while(ila

34、st) if(L-datai!=x) i+; else return i; return 0; 电子工程学院 54 【例例】编写算法，实现顺序表就地逆置。编写算法，实现顺序表就地逆置。 n分析：所谓顺序表就地逆置，就是利用一个中间变分析：所谓顺序表就地逆置，就是利用一个中间变 量将顺序表中的元素前后颠倒。量将顺序表中的元素前后颠倒。 电子工程学院 55 若若L-last=7 循环变量循环变量i取值：取值：1, 2, 3, 4（当（当i值为值为4时结束循环）时结束循环） 电子工程学院 56 顺序表就地逆置的算法顺序表就地逆置的算法 int invert(SeqList*L) int i=1; d

35、atatype temp; /定义中间变量定义中间变量 while(ilast/2) /顺序表中的元素前后交换顺序表中的元素前后交换 temp=L-datai; L-datai=L-dataL-last-i+1; L-dataL-last-i+1=temp; i+; 电子工程学院 57 顺序表应用实例：在顺序表中删除所有值为顺序表应用实例：在顺序表中删除所有值为x的结点。的结点。 n模块结构图模块结构图 n每个模块的功能相对独立，模块结构图可以反映每个模块的功能相对独立，模块结构图可以反映 出模块的功能和模块之间调用与被调用的关系。出模块的功能和模块之间调用与被调用的关系。 n程序除具有删除所

36、有值为程序除具有删除所有值为x的结点的功能之外，还的结点的功能之外，还 需要具有建立和输出顺序表的功能。需要具有建立和输出顺序表的功能。 电子工程学院 58 n程序中所含内容依次如下：程序中所含内容依次如下： （1）文件包含命令：包含程序中所需要的系统头）文件包含命令：包含程序中所需要的系统头 文件；文件； （2）无参宏定义：作为顺序表空间的长度；）无参宏定义：作为顺序表空间的长度； （3）类型定义：自定义类型名和结构体类型定义；）类型定义：自定义类型名和结构体类型定义； （4）函数声明：说明函数的类型、函数名、函数）函数声明：说明函数的类型、函数名、函数 的参数类型和参数的个数；的参数类型和

37、参数的个数； （5）主函数（）主函数（main函数）的定义；函数）的定义； （6）6个函数的定义。个函数的定义。 n完整的完整的C程序见教材程序见教材P75。 电子工程学院 59 顺序表的优缺点顺序表的优缺点 n顺序存储结构的线性表具有顺序存取和随机顺序存储结构的线性表具有顺序存取和随机 存取表中元素的优点，但是存在下列缺点：存取表中元素的优点，但是存在下列缺点： （1 1）插入、删除操作时需要移动大量元素，效率）插入、删除操作时需要移动大量元素，效率 较低。较低。 （2 2）最大表长难以估计，太大了浪费空间，太小）最大表长难以估计，太大了浪费空间，太小 了容易溢出。了容易溢出。 n如果在线性

38、表中经常进行插入和删除操作，选如果在线性表中经常进行插入和删除操作，选 用顺序存储结构不太合适，可以选用链式存储用顺序存储结构不太合适，可以选用链式存储 结构。结构。 电子工程学院 60 2.3 线性表的链式存储结构（链表）线性表的链式存储结构（链表） n线性表的链式存储结构，数据元素之间的逻线性表的链式存储结构，数据元素之间的逻 辑关系由结点中的指针来指示。各结点在物辑关系由结点中的指针来指示。各结点在物 理位置上不要求连续存放。理位置上不要求连续存放。 2.3.1 单链表单链表 n每个元素（结点）含有数据域（每个元素（结点）含有数据域（data）和一）和一 个指针域（个指针域（next）。

39、）。 电子工程学院 61 n 单链表的示意图单链表的示意图 电子工程学院 62 n单链表结点的结构体类型定义单链表结点的结构体类型定义 typedef 结点数据域类型结点数据域类型 datatype; typedef struct node datatype data; /数据域数据域 struct node*next; /指针域指针域 linklist; 定义指针：定义指针：linklist*head,*p; head作为头指针作为头指针 p作为工作指针作为工作指针 产生结点：产生结点：p=(linklist*)malloc(sizeof(linklist); 释放结点：释放结点：free(

40、p); 结点的数据域：结点的数据域：p-data 或或 (*p).data 读作：读作：p所指结点的数据域所指结点的数据域 结点的指针域：结点的指针域：p-next 或或 (*p).next 读作：读作：p所指结点的指针域所指结点的指针域 电子工程学院 63 n 术语术语 （1 1）开始结点：第一个数据元素结点。）开始结点：第一个数据元素结点。 （2 2）头指针：指向单链表中第一个结点）头指针：指向单链表中第一个结点 （3 3）头结点：有时在单链表的第一个结点之前附）头结点：有时在单链表的第一个结点之前附 设一个结点，称为头结点。设一个结点，称为头结点。 说明：说明： u头结点的头结点的nex

41、tnext域指向链表中的第一个结点。域指向链表中的第一个结点。 u头结点数据域的使用：头结点数据域的使用： a.a.加特殊信息加特殊信息 b.b.如数据域为整型，则在该处存放链表长度信如数据域为整型，则在该处存放链表长度信 息。息。 电子工程学院 64 使用头结点的优点使用头结点的优点 （1 1）由于开始结点的位置被存放在头结点的指针域中，）由于开始结点的位置被存放在头结点的指针域中， 所以对链表第一个位置的操作同其他位置一样，所以对链表第一个位置的操作同其他位置一样， 无须特殊处理。无须特殊处理。 （2 2）无论链表是否为空，其头指针是指向头结点的非）无论链表是否为空，其头指针是指向头结点的

42、非 空指针，因此对空表与非空表的处理统一了，可空指针，因此对空表与非空表的处理统一了，可 以简化对链表的操作。以简化对链表的操作。 电子工程学院 65 1. 建立单链表建立单链表 n建立单链表的过程是在空表的基础上动态插入建立单链表的过程是在空表的基础上动态插入 结点。按照插入结点的顺序，分为头插法和尾结点。按照插入结点的顺序，分为头插法和尾 插法两种方法。插法两种方法。 （1）带头结点的头插法建表）带头结点的头插法建表 步骤：步骤： 建立只有头结点的空表；建立只有头结点的空表； 动态产生动态产生n个结点，个结点，每产生一个新结点，将每产生一个新结点，将 该结点插入到表头。该结点插入到表头。

43、电子工程学院 66 算法分析（建立空表）算法分析（建立空表） linklist*CreateListF( ) /带头结点的头插法，返回单链表的头指针带头结点的头插法，返回单链表的头指针 linklist*head,*p; char ch; head=(linklist*)malloc(sizeof(linklist); /产生头结点产生头结点 head-next=NULL; while(ch=getchar( )!=n) /输入输入abc p=(linklist*)malloc(sizeof(linklist); /生成新结点生成新结点 p-data=ch; /对结点的数据域赋值对结点的数据域

44、赋值 p-next=head-next; /新结点的指针域指向原第一个结点新结点的指针域指向原第一个结点 head-next=p; /修改头结点的指针域修改头结点的指针域 return head; /时间复杂度为时间复杂度为O(n) 电子工程学院 67 算法分析（在表头插入结点）算法分析（在表头插入结点） linklist*CreateListF( ) /带头结点的头插法，返回单链表的头指针带头结点的头插法，返回单链表的头指针 linklist*head,*p; char ch; head=(linklist*)malloc(sizeof(linklist); /产生头结点产生头结点 head

45、-next=NULL; while(ch=getchar( )!=n) /输入输入abc p=(linklist*)malloc(sizeof(linklist); /生成新结点生成新结点 p-data=ch; /对结点的数据域赋值对结点的数据域赋值 p-next=head-next; /新结点的指针域指向原第一个结点新结点的指针域指向原第一个结点 head-next=p; /修改头结点的指针域修改头结点的指针域 return head; /时间复杂度为时间复杂度为O(n) 电子工程学院 68 （2）带头结点的尾插法建表）带头结点的尾插法建表 n从空表开始，每次将新结点插入到表尾。从空表开始，

46、每次将新结点插入到表尾。 linklist*CreateListR( ) /带头结点的尾插法，返回单链表的头指针带头结点的尾插法，返回单链表的头指针 linklist*head,*p,*r; char ch; head=(linklist*)malloc(sizeof(linklist); /生成头结点生成头结点 head-next=NULL; /建立空表建立空表 r=head; /r指针指向头结点指针指向头结点 while(ch=getchar( )!=n) /输入输入abc p=(linklist*)malloc(sizeof(linklist); /生成新结点生成新结点 p-data=c

47、h; /将输入的字符赋给新结点的数据域将输入的字符赋给新结点的数据域 r-next=p; /新结点插入表尾新结点插入表尾 r=p; / r指针指向到表尾指针指向到表尾 r-next=NULL; /表尾结点的指针域置空表尾结点的指针域置空 return head; /时间复杂度为时间复杂度为O(n) 电子工程学院 69 （3）不带头结点的尾插法）不带头结点的尾插法 n比较不带头结点的尾插法。第一个结点与后面各结点的处比较不带头结点的尾插法。第一个结点与后面各结点的处 理方法不同。理方法不同。 linklist*CreateListR( ) /不带头结点的尾插法，返回单链表的头指针不带头结点的尾插

48、法，返回单链表的头指针 linklist*head,*p,*r; char ch; head=NULL; r=NULL; /建立空表，尾指针置为空建立空表，尾指针置为空 while(ch=getchar( )!=n) p=(linklist*)malloc(sizeof(linklist); /生成新结点生成新结点 p-data=ch; /将输入的字符赋给新结点的数据域将输入的字符赋给新结点的数据域 if(head= =NULL) head=p; /新结点插入空表，新结点插入空表， else r-next=p; /新结点插入非空表的末尾新结点插入非空表的末尾 r=p; /指针指针r指向表的末尾

49、指向表的末尾 if(r!=NULL) r-next=NULL; /对于非空表对于非空表,将终端结点的指针域置空将终端结点的指针域置空 return head; 电子工程学院 70 2. 单链表的查找单链表的查找 （1）按序号查找。必须从表头开始顺序查找第）按序号查找。必须从表头开始顺序查找第i个结点。个结点。 linklist*Get(linklist*head,int i) lintlist*p=head; /p指向头结点指向头结点 int j=0; while(p-next!=NULL /p指向下一个结点指向下一个结点 j+; /计数器加一计数器加一 if(i=j) return p; /

50、查找到，返回第查找到，返回第i个结点的地址个结点的地址 else return NULL; /查找不到，返回空地址值查找不到，返回空地址值 /时间复杂度为时间复杂度为O(n) 电子工程学院 71 （2）按值查找。必须从表头开始顺序查找值为）按值查找。必须从表头开始顺序查找值为key的结点。的结点。 linklist*Locate(linklist*head,datatype key) linklist*p=head-next; /p指向第指向第1个结点个结点 while(p!=NULL /p指向下一个结点指向下一个结点 if(p=NULL) return NULL; /p为为NULL，查找不到

51、，返回，查找不到，返回NULL else return p; /查找到，返回该结点的地址查找到，返回该结点的地址 /时间复杂度为时间复杂度为O(n) n循环结束有两种可能：循环结束有两种可能： 由于由于p!=NULL为假结束的循环，则查找不到；为假结束的循环，则查找不到； 由于由于p-data!=key为假结束的循环，则查找到。为假结束的循环，则查找到。 电子工程学院 72 3. 单链表的插入单链表的插入 n在单链表中只能在某个结点之后插入新结点（简称后在单链表中只能在某个结点之后插入新结点（简称后 插）。插）。在第在第i i个结点之前插入结点，必须个结点之前插入结点，必须先找到第先找到第i-

52、1个个 结点，然后在第结点，然后在第i-1个结点之后插入，即变前插为后插。个结点之后插入，即变前插为后插。 void Insert(linklist*L,datatype x,int i) /L指向具有头结点的单链表，在第指向具有头结点的单链表，在第i个结点之前插入值为个结点之前插入值为x的结点的结点 linklist*p,*s; p=Get(L,i-1); /调用算法调用算法3.8，查找第，查找第i-1个结点个结点*p if(p=NULL) printf(查找不到第查找不到第i-1个结点个结点); else /将新结点插在将新结点插在*p之后之后 s=(linklist*)malloc(si

53、zeof(linklist); /生成新结点生成新结点 s-data=x; s-next=p-next; /新结点的指针域指向结点新结点的指针域指向结点ai p-next=s; /结点结点ai-1的指针域指向新结点的指针域指向新结点 电子工程学院 73 【例【例3.2】将值为将值为x的节点插入到递增有序的单链表中的节点插入到递增有序的单链表中 步骤：步骤： （1）在单链表中从表头开始查找插入位置）在单链表中从表头开始查找插入位置p，结点，结点 数据域数据域p-data的值应当大于等于的值应当大于等于x的值。的值。 （2）将值为）将值为x的新结点插入结点的新结点插入结点*p之前，使插入后之前，使

54、插入后 该链表仍然有序。必须用指针该链表仍然有序。必须用指针q指向结点指向结点*p的直接的直接 前趋结点，然后在结点前趋结点，然后在结点*q之后插入新结点，将之后插入新结点，将“前前 插插”变为变为“后插后插”。 电子工程学院 74 例例3.2的算法的算法 void Insert (linklist*head,datatype x) /将值为将值为x的新结点插入到带有头结点的有序单链表中的新结点插入到带有头结点的有序单链表中 s=(linklist*)malloc(sizeof(linklist); /生成一个新结点生成一个新结点 s-data=x; s-next=NULL; p=head-n

55、ext; /p指向第一个结点指向第一个结点 q=head; /q指向头结点指向头结点 while(p!=NULL p=p-next; if(p=NULL) q-next=s; /在空表或终端结点之后插入在空表或终端结点之后插入 else s-next=p; q-next=s; /将将*s插入到插入到*q和和*p之间之间 /时间复杂度为时间复杂度为O(n) 电子工程学院 75 4. 单链表的删除单链表的删除 n在单链表中只能删除某个结点的后继结点。在单链表中只能删除某个结点的后继结点。 删除第删除第i个结点个结点*r，先查找第，先查找第i-1个结点个结点*p， 然后删除然后删除*r。 void

56、Delete(linklist*L,int i) /在带头结点的单链表中删除第在带头结点的单链表中删除第i个结点个结点 linklist*p=Get(L, i-1); /调用算法调用算法3.8，找第，找第i-1个结点个结点 if(p!=NULL / r指向指向*p的后继结点的后继结点 p-next=r-next; / 删除结点删除结点*r free(r); / 释放结点释放结点*r所占的存储空间所占的存储空间 else printf(第第i个结点不存在个结点不存在); 电子工程学院 76 n删除结点删除结点*p，先顺序查找，先顺序查找*p的直接前趋结点的直接前趋结点*q， 然后删除然后删除*p

57、。 void Delete(linklist*head,linklist*p) /在具有头结点的单链表中删除结点在具有头结点的单链表中删除结点*p q=head; q指向头结点指向头结点 while(q-next!=p) q=q-next;/查找查找*p的前趋结点的前趋结点 q-next=p-next;/删除结点删除结点*p free(p);/释放结点释放结点*p /时间复杂度为时间复杂度为O(n) 电子工程学院 77 【例例】将两个非递减单链表将两个非递减单链表La、Lb合并为一个非递合并为一个非递 减的单链表。减的单链表。 n将将B表中的结点按顺序添加到表中的结点按顺序添加到A表中。表中。

58、 void union_L(linklist*La,linklist*Lb) /合并具有头结点的非递减单链表合并具有头结点的非递减单链表La和和Lb为为La p=La-next;q=Lb-next; r=La; while(p!=NULL r-next=q; r=q; q-next=p; q=u; /将将*q插入到插入到*p之前之前 else r=p;p=p-next;/r、p后移后移 if(q!=NULL) r-next=q;/将将Lb的剩余部分添加到的剩余部分添加到La的末尾的末尾 电子工程学院 78 【例例】将具有头结点的单链表逆置。将具有头结点的单链表逆置。 n将线性表将线性表E=e1

59、, e2, , en-1, en逆置，即使元素排逆置，即使元素排 列次序颠倒过来，成为逆线性表列次序颠倒过来，成为逆线性表E= en , en-1 , , e2 , e1 。 n顺序表逆置是交换元素的值。顺序表逆置是交换元素的值。 n单链表逆置只需要改变指针的指向，并且逆置之后单链表逆置只需要改变指针的指向，并且逆置之后 的单链表占用原单链表结点的空间。的单链表占用原单链表结点的空间。 电子工程学院 79 n分析（执行循环语句之前）分析（执行循环语句之前） /算法的部分代码算法的部分代码 p=head-next; q=p-next; while(q!=NULL) r=q-next; q-nex

60、t=p; p=q; q=r; head-next-next=NULL; head-next=p; 电子工程学院 80 n分析（第分析（第1次执行循环体）次执行循环体） /算法的部分代码算法的部分代码 p=head-next; q=p-next; while(q!=NULL) r=q-next; q-next=p; p=q; q=r; head-next-next=NULL; head-next=p; 电子工程学院 81 n分析（第分析（第2次执行循环体）次执行循环体） /算法的部分代码算法的部分代码 p=head-next; q=p-next; while(q!=NULL) r=q-next;