SUN数据结构第2章线性表(第3-4讲)

1、第第 2 2 章章 线线 性性 表表 1.1.线性表的定义线性表的定义 线性表线性表L L是是n n（n0n0）个具有相同属性的数据元）个具有相同属性的数据元 素素a1a1，a2a2，a3a3，anan组成的有限序列，其中组成的有限序列，其中 序列中元素的个数序列中元素的个数n n称为称为线性表的长度线性表的长度。 当当n=0n=0时称为，即不含有任何元素。时称为，即不含有任何元素。 常常将非空的线性表常常将非空的线性表L(n0)L(n0)记作：记作： L=(a1L=(a1，a2a2，an) an) 其中其中a ai-1 i-1为 为aiai的的直接前驱直接前驱，a ai i 1 1为 为ai

2、ai的的直接后继直接后继。 a1a1为为表头元素表头元素，anan为为表尾元素表尾元素。 第第 2 2 章章 线线 性性 表表 线性表（线性表（Linear listLinear list）是最简单且最常用的一种）是最简单且最常用的一种 数据结构，其逻辑结构为数据结构，其逻辑结构为线性结构线性结构。 线性表具有下列特点：线性表具有下列特点： 存在唯一的一个没有前驱的（头）数据元素；存在唯一的一个没有前驱的（头）数据元素； 存在唯一的一个没有后继的（尾）数据元素；存在唯一的一个没有后继的（尾）数据元素； 每个数据元素每个数据元素( (除表头元素除表头元素) )均有一个直接前驱；均有一个直接前驱；

3、 每个数据元素每个数据元素( (除表尾元素除表尾元素) )均有一个直接后继；均有一个直接后继； 表中表中数据元素的类型数据元素的类型是相同的。是相同的。 第第 2 2 章章 线线 性性 表表 例例1 1、2626个英文字母组成的字母表个英文字母组成的字母表 （A A，B B，C C、Z Z） 例例2 2、某校从、某校从19781978年到年到19831983年各种型号的计算机年各种型号的计算机 拥有量的变化情况。拥有量的变化情况。 （6 6，1717，2828，5050，9292，188188） 例例3 3、一副扑克的点数、一副扑克的点数 （2 2，3 3，4 4，J J，Q Q，K K，A

4、A） 以上三例都为以上三例都为线性表线性表。 第第 2 2 章章 线线 性性 表表 复杂线性表中一个数据元素可由若干个复杂线性表中一个数据元素可由若干个数据项数据项组成。组成。 例例4 4、学生健康情况登记表如下：、学生健康情况登记表如下： 姓姓 名名学学 号号性性 别别年龄年龄健康情况健康情况 王小林王小林790631790631男男1818健康健康 陈陈 红红790632790632女女2020一般一般 刘建平刘建平790633790633男男2121健康健康 张立立张立立790634790634男男1717神经衰弱神经衰弱 . . . . . . 第第 2 2 章章 线线 性性 表表 第

5、第 2 2 章章 线线 性性 表表 第第 2 2 章章 线线 性性 表表 顺序表具有以下两个基本特点：顺序表具有以下两个基本特点： (1) (1) 线性表的所有元素所占的存储空间是连线性表的所有元素所占的存储空间是连 续的。续的。 (2) (2) 线性表中各数据元素在存储空间中是按线性表中各数据元素在存储空间中是按 逻辑顺序依次存放的。逻辑顺序依次存放的。 由于线性表的所有数据元素属于同一数据类由于线性表的所有数据元素属于同一数据类 型，所以每个元素在存储器中占用的空间型，所以每个元素在存储器中占用的空间 （字节数）相同。（字节数）相同。 第第 2 2 章章 线线 性性 表表 以以“存储位置相

6、邻存储位置相邻”表示有序对表示有序对a 则相则相 邻元素存储位置关系为：邻元素存储位置关系为： LOC(aLOC(ai i)=LOC(a)=LOC(ai-1 i-1)+k )+k 其中其中k k指一个数据元素所占存储量。指一个数据元素所占存储量。 所有数据元素的存储位置均取决于第一个数据所有数据元素的存储位置均取决于第一个数据 元素的存储位置元素的存储位置基地址：基地址： LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)+(i-1)* *k k 第第 2 2 章章 线线 性性 表表 第第 2 2 章章 线线 性性 表表 例例: :假设线性表的每个元素需占用假设线性表的

7、每个元素需占用2 2个存储单元，个存储单元， 以第以第1 1个元素的存储地址个元素的存储地址LOC(aLOC(a1 1) )为基准，计算线为基准，计算线 性表的第性表的第9 9个数据元素个数据元素a a9 9的存储位置为：的存储位置为： LOC(a LOC(a9 9)=LOC(a)=LOC(a1 1)+(9-1)+(9-1)* *2 2 =LOC(a=LOC(a1 1)+16)+16 由于线性表中的数据元素都是按照逻辑关系进行存由于线性表中的数据元素都是按照逻辑关系进行存 储，所以只要确定了顺序表的起始位置，线性表中储，所以只要确定了顺序表的起始位置，线性表中 的任一数据元素都可以随机存取，因

8、此线性表的顺的任一数据元素都可以随机存取，因此线性表的顺 序存储结构是一种序存储结构是一种“随机存取随机存取”的存储结构。的存储结构。 第第 2 2 章章 线线 性性 表表 顺序表在具体实现时，一般用高级语言中的数组来顺序表在具体实现时，一般用高级语言中的数组来 对应连续的存储空间。设最多可存储对应连续的存储空间。设最多可存储MaxLenMaxLen个元素，个元素， 在在C C语言中可用数组语言中可用数组dataMaxLendataMaxLen来存储数据元素，来存储数据元素， 为保存线性表的长度需定义一个整型变量为保存线性表的长度需定义一个整型变量lengthlength。 线性表的第线性表的

9、第l l，2 2，n n个元素分别存放在此数组个元素分别存放在此数组 下标为下标为0 0，1 1，length-1length-1数组元素中，如下图所数组元素中，如下图所 示示 第第 2 2 章章 线线 性性 表表 在在C C语言中，可用下述类型定义来描述顺序表：语言中，可用下述类型定义来描述顺序表： #define MaxLen 100 #define MaxLen 100 typedef int DataType; typedef int DataType; typedef structtypedef struct DataType dataMaxLen; DataType dataMax

10、Len; int length; int length; SeqList;SeqList; SeqList L; SeqList L; 第第 2 2 章章 线线 性性 表表 顺序表的基本操作的实现顺序表的基本操作的实现 在顺序表存储结构中，很容易实现线性表的一在顺序表存储结构中，很容易实现线性表的一 些操作，如求线性表的长度、第些操作，如求线性表的长度、第i i个元素的访个元素的访 问等。问等。 注意：注意：C C语言中的数组下标从语言中的数组下标从“0”0”开始，因此，开始，因此， 若若L L是是SeqListSeqList类型的顺序表，则表中第类型的顺序表，则表中第i i个元个元 素是素是

11、 L.datai-1L.datai-1 第第 2 2 章章 线线 性性 表表 结构体指针（补充）结构体指针（补充） 结构体指针是一个指针变量结构体指针是一个指针变量, ,用来指向结构体变量用来指向结构体变量. . 结构体指针定义的格式：结构体指针定义的格式： struct struct 结构体名结构体名 * *结构体指针名；结构体指针名； 例如：例如： struct student struct student * *pstu;pstu; struct student struct student 是预先说明的结构体数据类型。是预先说明的结构体数据类型。 第第 2 2 章章 线线 性性 表表

12、在定义结构体指针以后，就可以用结构体指针引用在定义结构体指针以后，就可以用结构体指针引用 结构体成员。引用的方法如下：结构体成员。引用的方法如下： （* *结构体指针名）结构体指针名）. . 成员名成员名 结构体指针名结构体指针名 - - 成员名成员名 或或 例如例如: : struct studentstruct student int num; int num; char name20; char name20; int age; int age; float score; float score; stu30;stu30; struct student struct student *

13、*pstu; pstu; pstu=stu;pstu=stu; 以下引用都正确，且等以下引用都正确，且等 价：价： stu0.numstu0.num ( (* *pstu).numpstu).num pstu -numpstu -num 结构体指针（补充）结构体指针（补充） 第第 2 2 章章 线线 性性 表表 例如例如: : struct dataxystruct dataxy int x; int x; int y; int y; ; typedef struct dataxy data; typedef struct dataxy data; data a,data a,* *p;p;

14、p= p= 结构体成员引用的三种形式结构体成员引用的三种形式: : 结构体变量名结构体变量名 . . 结构体成员名结构体成员名 ( (* *结构体指针名结构体指针名). ). 结构体成员名结构体成员名 结构体指针名结构体指针名 - - 结构体成员名结构体成员名 括号一定不可省括号一定不可省 结构体指针（补充）结构体指针（补充） a.xa.x ( (* *p).x p).x p-x p-x 如何引用如何引用 变量变量a a的的x x 成员？成员？ 第第 2 2 章章 线线 性性 表表 1 1初始化顺序表初始化顺序表InitList(L)InitList(L)的实现的实现 void InitLis

15、t(SeqList void InitList(SeqList * *L)L) L-length=0; L-length=0; 算法的时间复杂度为算法的时间复杂度为O(1)O(1) 第第 2 2 章章 线线 性性 表表 2 2求线性表长度求线性表长度GetLength(L)GetLength(L)的实现的实现 int GetLength(SeqList int GetLength(SeqList * *L) L) return L-length;return L-length; 该算法的时间复杂度为该算法的时间复杂度为O(1)O(1) 第第 2 2 章章 线线 性性 表表 3 3按序号取元素按

16、序号取元素GetNode(L,i)GetNode(L,i)的实现的实现 DataType GetNode(SeqList DataType GetNode(SeqList * *L,int i)L,int i) if(iL-length)if(iL-length) printf(“error!”);printf(“error!”); exit(1);exit(1); return L-datai-1;return L-datai-1; 时间复杂度时间复杂度O(1)O(1) 第第 2 2 章章 线线 性性 表表 4 4查找运算查找运算Locate(L,x)Locate(L,x)的实现的实现 in

17、t Locate(SeqList int Locate(SeqList * *L,DataType x)L,DataType x) int i; int i; i=0; i=0; while(ilength i+; if(ilength) return i ; if(ilength) return i ; else return -1; else return -1; 时间复杂度为时间复杂度为O(n)O(n)。（。（n=L-lengthn=L-length） i+1;i+1; 第第 2 2 章章 线线 性性 表表 复习复习 1.1.线性表逻辑结构为（线性表逻辑结构为（ ），若其采用顺序），若其

18、采用顺序 存储结构则称为（存储结构则称为（ ）。）。 2.2.顺序表的结构类型说明（）。顺序表的结构类型说明（）。 3.3.初始化一顺序表初始化一顺序表L L后，后，L.length=( );L.length=( ); 向顺序表中插入了一些元素后，想知道顺序向顺序表中插入了一些元素后，想知道顺序 表中元素的个数可查看顺序表的成员表中元素的个数可查看顺序表的成员( )( )； 假设顺序表中存了假设顺序表中存了n n个学生的成绩，想找第个学生的成绩，想找第i i 个学生的成绩可查看顺序表的成员（个学生的成绩可查看顺序表的成员（ ）。）。 第第 2 2 章章 线线 性性 表表 0 a1 1 a2 2

19、 a3 i-1 ai i ai+1 i+1 ai+2 i+2 ai+3 n-1 an 0 a1 1 a2 2 a3 i-1 x i ai i+1 ai+1 i+2ai+2 nan 插入插入x 在数组中插入元素在数组中插入元素 第第 2 2 章章 线线 性性 表表 1 1、插入之前需先检查表空间是否足够；、插入之前需先检查表空间是否足够； 2 2、插入位置：、插入位置：1=i=n+1;1=i=n+1; 3 3、注意数据的移动方向；、注意数据的移动方向； 4 4、插入之后线性表的长度增加、插入之后线性表的长度增加1 1。 第第 2 2 章章 线线 性性 表表 void InsertList(Seq

20、List void InsertList(SeqList * *L,int i,Datatype x)L,int i,Datatype x) if (iL-length+1) if (iL-length+1) printf(“Error!”) ; / printf(“Error!”) ; /插入位置出错插入位置出错 exit(1); exit(1); if(L-length=MaxLen) if(L-length=MaxLen) printf(“overflow!”) ; printf(“overflow!”) ; /表已满表已满 exit(1);exit(1); for(j=L-length

21、-1;j=i-1;j-) for(j=L-length-1;j=i-1;j-) L-dataj+1=L-dataj; / L-dataj+1=L-dataj; /数据元素后移数据元素后移 L-datai-1=x; L-datai-1=x; / /插入插入x x L-length+; L-length+; / /表长度加表长度加1 1 时间时间 复杂复杂 度为度为 (n)(n) 注意数据的移动顺序注意数据的移动顺序 第第 2 2 章章 线线 性性 表表 0 a1 1 a2 2 a3 i-1 ai i ai+1 i+1 ai+2 n1 an 0 a1 1 a2 2 a3 i-1 ai 1 i ai

22、 2 n-2 an 在数组中删除元素在数组中删除元素 删除删除aiai 第第 2 2 章章 线线 性性 表表 1 1、删除之前需先检查表是否为空；、删除之前需先检查表是否为空； 2 2、删除位置：、删除位置：1=i=n;1=i=n; 3 3、若删除的元素还有用，则在删除之前、若删除的元素还有用，则在删除之前 应先取出；应先取出； 4 4、删除之后线性表的长度减、删除之后线性表的长度减1 1。 第第 2 2 章章 线线 性性 表表 void DeleteList(SeqList void DeleteList(SeqList * *L,int i) L,int i) if(iL-length)

23、if(iL-length) printf (“position error”); printf (“position error”); exit(1); exit(1); for(j=i;jlength-1;j+) for(j=i;jlength-1;j+) L-dataj-1=L-dataj; L-dataj-1=L-dataj; / /向前移动元素向前移动元素 L-length-; L-length-; 时间复杂度为时间复杂度为(n)(n) 第第 2 2 章章 线线 性性 表表 void delete(SeqList void delete(SeqList * *A, SeqList A,

24、 SeqList * *B) B) int i,k; int i,k; DataType x; DataType x; for(i=1;i=Getlengh(B);i+) for(i=1;i0) Delelem(A,k); if(k0) Delelem(A,k); / /若在线性表若在线性表A A中找到了，将其删除中找到了，将其删除 实际应用中，可以借助基本运算构造出更复杂的运算。实际应用中，可以借助基本运算构造出更复杂的运算。 第第 2 2 章章 线线 性性 表表 typedef int DataType; typedef int DataType; void part(SeqList vo

25、id part(SeqList * *L)L) int i,j; int i,j; DataType x,y; DataType x,y; x=L-data0; / x=L-data0; /将基准元素将基准元素a1a1置入置入x x中中 for(i=1;ilength;i+)for(i=1;ilength;i+) if(L-dataidataidatai; y=L-datai; for(j=i-1;j=0;j-) for(j=i-1;j=0;j-)/向后移动向后移动 L-dataj+1=L-dataj;L-dataj+1=L-dataj; L-data0=y; L-data0=y; 第第 2

26、2 章章 线线 性性 表表 void commelem(SeqList void commelem(SeqList * *A, SeqList A, SeqList * *B, SeqList B, SeqList * *C)C) int i,k,j=1; int i,k,j=1; DataType x; DataType x; Initlist(C); Initlist(C); for(i=1;i=Getlen(A);i+) for(i=1;iO) InsetrList(C,j,x);j+; if(kO) InsetrList(C,j,x);j+; / /若在线性表若在线性表B B中找到了，

27、将其插入到中找到了，将其插入到C C中中 第第 2 2 章章 线线 性性 表表 优点：顺序表中的任意数据元素的存储地址可由公优点：顺序表中的任意数据元素的存储地址可由公 式直接导出，因此顺序表可以式直接导出，因此顺序表可以“随机存取随机存取”其中的其中的 任意元素。任意元素。 不足：不足： （1 1）需预先分配相应的存储空间）需预先分配相应的存储空间 预分配空间过小，存储空间不便于扩充；预预分配空间过小，存储空间不便于扩充；预 分配空间过大，容易造成空间浪费。分配空间过大，容易造成空间浪费。 （2 2）插入与删除运算的效率很低，插入、删除操）插入与删除运算的效率很低，插入、删除操 作时需移动大

28、量数据。作时需移动大量数据。 第第 2 2 章章 线线 性性 表表 课后作业：课后作业： 创建顺序表，在顺序表的第创建顺序表，在顺序表的第i i个位置插个位置插 入一个元素。入一个元素。 例：创建线性表例：创建线性表20 56 89 45 6720 56 89 45 67 在该线性表的第在该线性表的第3 3个位置插入一个元素个位置插入一个元素 9797 程序运行结果能够输出程序运行结果能够输出20 56 97 89 45 20 56 97 89 45 6767 第第 2 2 章章 线线 性性 表表 线性表的链式存储结构就是用一组任意的存储单线性表的链式存储结构就是用一组任意的存储单 元（可以是

29、不连续的）存储线性表的数据元素。元（可以是不连续的）存储线性表的数据元素。 采用链式存储结构的表示的线性表简称链表。采用链式存储结构的表示的线性表简称链表。 链式存储方式可用于表示线性结构，也可用于表链式存储方式可用于表示线性结构，也可用于表 示非线性结构。示非线性结构。 第第 2 2 章章 线线 性性 表表 由于线性表中各元素间存在着线性关系，每一个由于线性表中各元素间存在着线性关系，每一个 元素有一个直接前驱和一个直接后继。元素有一个直接前驱和一个直接后继。 用链式存储结构表示线性表中的一个元素时至少用链式存储结构表示线性表中的一个元素时至少 需要两部分信息，一部分用于存放数据元素值，需要

30、两部分信息，一部分用于存放数据元素值， 称为数据域；另一部分用于存放直接前驱或直接称为数据域；另一部分用于存放直接前驱或直接 后继结点的地址（指针），称为指针域，称这种后继结点的地址（指针），称为指针域，称这种 存储单元为结点。存储单元为结点。 第第 2 2 章章 线线 性性 表表 数据域（存储数据元素本身信息数据域（存储数据元素本身信息 ） + + 指针域指针域 ( (指示后继元素存储位置指示后继元素存储位置) ) = = 结点结点 ( (表示数据元素的存储映象表示数据元素的存储映象) ) datadatanextnext 结点的结构如下所示：结点的结构如下所示： 以以“结点的序列结点的序列

31、”表示线性表表示线性表 称作链表称作链表 第第 2 2 章章 线线 性性 表表 head head a1a2a3 (a) 空 链表 （ b ) 非 空 链表 头结点的作用：带头结点的单链表使得对头结点的作用：带头结点的单链表使得对“第一个第一个 结点结点”的插入删除操作与其他结点一致，且使的插入删除操作与其他结点一致，且使“空空 表表”与与“非空表非空表”的处理一致。的处理一致。 后述单链表一般都指带头结点的单链表。后述单链表一般都指带头结点的单链表。 由于链表中第一个结点没有直接前驱由于链表中第一个结点没有直接前驱, ,所以必须所以必须 设置一个头指针设置一个头指针headhead存储第一个

32、结点的地址。存储第一个结点的地址。 最后一个结点没有直接后继最后一个结点没有直接后继, ,其指针域应为空指其指针域应为空指 针针,C,C语言用语言用NULLNULL或或0 0表示表示, ,在图中表示为在图中表示为“”。 不带头结点的单链表不带头结点的单链表 带头结点的单链表带头结点的单链表 第第 2 2 章章 线线 性性 表表 由于链表中第一个结点没有直接前驱，所以必须设由于链表中第一个结点没有直接前驱，所以必须设 置一个头指针置一个头指针headhead存储第一个结点的地址。最后一存储第一个结点的地址。最后一 个结点没有直接后继，其指针域应为空指针，个结点没有直接后继，其指针域应为空指针，C

33、 C语语 言用言用NULLNULL或或0 0来表示，在图中表示为来表示，在图中表示为“”。 4 head 头指针 1 2 3 4 5 6 7 8 9 10 data next A7 B2 C9 D1 E0 (a)线性链表的物理状态 第第 2 2 章章 线线 性性 表表 n单链表：只设置一个指向后继结点地单链表：只设置一个指向后继结点地 址的指针域；址的指针域； n循环链表：链表首尾相接构成一个环循环链表：链表首尾相接构成一个环 状结构；状结构； n双向链表：单链表中增加一个指向前双向链表：单链表中增加一个指向前 驱的指针。驱的指针。 第第 2 2 章章 线线 性性 表表 C C语言采用结构体描

34、述结点和单链表如下：语言采用结构体描述结点和单链表如下： typedef struct nodetypedef struct node DataType data; / DataType data; /* *结点值结点值* */ / struct node struct node * *next; next; / /* *存储下一个结点的地址存储下一个结点的地址* */ / ListNode,ListNode,* *LinkList;LinkList; ListNode ListNode * *p;p; LinkList head;LinkList head; 同一数据类型的同一数据类型的 两

35、个变量两个变量 单链表中访问数据元素只能由链表单链表中访问数据元素只能由链表 头依次到链表尾，而不能做逆向访头依次到链表尾，而不能做逆向访 问。问。 第第 2 2 章章 线线 性性 表表 在在C C语言中通常采用以下函数进行相关操作：语言中通常采用以下函数进行相关操作： （1 1）为结点变量分配存储空间的标准函数）为结点变量分配存储空间的标准函数 p=(ListNode p=(ListNode * *)malloc(sizeof(ListNode)malloc(sizeof(ListNode)； 函数函数mallocmalloc分配一个类型为分配一个类型为ListNodeListNode的结点

36、变量的结点变量 的空间的空间, ,并将其首地址放入指针变量并将其首地址放入指针变量p p中。中。 （2 2）释放结点变量空间的标准函数）释放结点变量空间的标准函数 free(p)free(p)；/释放释放p p所指的结点变量空间所指的结点变量空间 第第 2 2 章章 线线 性性 表表 void InitList(LinkList L)void InitList(LinkList L) L=(ListNodeL=(ListNode* *)malloc(sizeof(ListNode);)malloc(sizeof(ListNode); L-next=NULL;L-next=NULL; 1 1初始

37、化链表初始化链表InitList(L)InitList(L)的实现的实现 建立一个空的带头结点的单链表。所谓空链表就建立一个空的带头结点的单链表。所谓空链表就 是指表长为是指表长为0 0的表。在这种情况下，链表中没有的表。在这种情况下，链表中没有 元素结点。但应有一个头结点，其指针域为空。元素结点。但应有一个头结点，其指针域为空。 第第 2 2 章章 线线 性性 表表 2 2求链表长度求链表长度GetLength(L)GetLength(L)的实现的实现 int GetLength(LinkList L)int GetLength(LinkList L) int num=0;int num=0

38、; ListNode ListNode * *p;p; p=L-next; p=L-next; while(p!=NULL) while(p!=NULL) num+; num+; p=p-next; p=p-next; return(num); return(num); 时间复杂度为时间复杂度为O(n)O(n)。 第第 2 2 章章 线线 性性 表表 ListNode ListNode * *GetNode(LinkList L,int i)GetNode(LinkList L,int i) ListNode ListNode * *p; p; int pos=1; int pos=1; p=

39、L-next; p=L-next; if(iGetLength(L) if(iGetLength(L) exit(1);exit(1); while(posi) while(posnext; p=p-next; pos+; pos+; return p; return p; 3.3.按序号取元素按序号取元素GetNode(L,i)GetNode(L,i)的实现的实现 时间复杂度为时间复杂度为O(n)O(n)。 访问链表中的元素，必须由头指针依次向后查找，访问链表中的元素，必须由头指针依次向后查找， 所以链表是一种所以链表是一种“顺序存取顺序存取”结构。结构。 第第 2 2 章章 线线 性性 表

40、表 4 4（1 1）查找运算）查找运算locate(L,x)locate(L,x)的实现的实现 ( (返回要找结点的地址值返回要找结点的地址值) ) ListNode ListNode * *Locate(LinkList L,DataType x)Locate(LinkList L,DataType x) ListNode ListNode * *p=L-next; p=L-next; while(p p=p-next; return p;return p; 时间复杂度为时间复杂度为O(n)O(n)。 第第 2 2 章章 线线 性性 表表 int Locate(LinkList L,Data

41、Type x)int Locate(LinkList L,DataType x) ListNode ListNode * *p=L-next; p=L-next; int i=1;int i=1; while(p!=NULL p=p-next; i+;i+; if(p=NULL) return 0;if(p=NULL) return 0; else return i; else return i; 4(2)4(2)查找运算查找运算locate(L,x)locate(L,x)的实现的实现( (返回返回intint值值) ) 时间复杂度为时间复杂度为O(n)O(n)。 第第 2 2 章章 线线 性

42、性 表表 5.5.链表的插入算法链表的插入算法 InsertList(L,i,x)InsertList(L,i,x)的实现的实现 单链表结点的插入是利用修改结点指针域单链表结点的插入是利用修改结点指针域 的值，使其指向新的结点位置来完成的插的值，使其指向新的结点位置来完成的插 入操作，而无需移动任何元素。入操作，而无需移动任何元素。 过程示意图见下页过程示意图见下页 第第 2 2 章章 线线 性性 表表 s=(LNode *)malloc(sizeof(LNode)； s-data=x； (b)申请新结点s ，数据域置 x xs head a1a2 . ai-1 p . aian xs hea

43、d a1a2 . ai-1 p . aian (a)找到插入位置 s-next=q-next q-next=s (c)修改指针域，将新结点s 插入 关键语句： q q void Inselem(LinkList L,int i,DataType x)void Inselem(LinkList L,int i,DataType x) ListNode ListNode * *p,p,* *q,q,* *s;s; int pos=1; int pos=1; p=L; p=L; if(iGetLength(L)+1) exit(1); if(iGetLength(L)+1) exit(1); s=(

44、ListNode s=(ListNode * *)malloc(sizeof(ListNode);)malloc(sizeof(ListNode); s-data=x; s-data=x; while(pos=i) while(posnext; q=p;p=p-next; pos+; pos+; / /* *找到插入位置找到插入位置* */ / s-next=q-next; s-next=q-next; q-next=s; q-next=s; 5 5链表的插入算法链表的插入算法inselem(L,i,x)inselem(L,i,x)的实现的实现 链表链表 中是中是 动态动态 分配分配 内存内存

45、 可有多种写法可有多种写法 第第 2 2 章章 线线 性性 表表 6 6链表的删除运算链表的删除运算DeleteList(L,i)DeleteList(L,i)的实现的实现 要删除链表中第要删除链表中第i i个结点，首先在单链表中找到个结点，首先在单链表中找到 删除位置前一个结点，并用指针删除位置前一个结点，并用指针q q指向它，指针指向它，指针p p 指向要删除的结点。将指向要删除的结点。将* *q q的指针域修改为待删除的指针域修改为待删除 结点结点* *p p的后继结点的地址。删除后的结点需动态的后继结点的地址。删除后的结点需动态 的释放。的释放。 删除过程见下页。删除过程见下页。 第第

46、 2 2 章章 线线 性性 表表 x=p-data； (b)返回被删除结点数据x x p head a1a2 . ai-1 q . aian (a)找到删除位置p head a1. (c)修改指针域，将结点p 删除 q ai-1 p ai . anai+1 关键语句：q-next=p-next； free(p) 第第 2 2 章章 线线 性性 表表 void DeleteList(LinkList L,int i)void DeleteList(LinkList L,int i) int pos=1; int pos=1; ListNode ListNode * *q=L,q=L,* *p;p

47、; if(iGetlength(L) exit(1); if(iGetlength(L) exit(1); while(posi) while(posnext; q=q-next; pos+; pos+; p=q-next; p=q-next; q-next=p-next; q-next=p-next; free(p); free(p); 6 6链表的删除运算链表的删除运算 DeleteList(L,i)DeleteList(L,i)的实现的实现 第第 2 2 章章 线线 性性 表表 利用插入算法实现单链表的建立（利用插入算法实现单链表的建立（P27P27） 动态地建立单链表的常用方法有两种：

48、头插法动态地建立单链表的常用方法有两种：头插法 建表和尾插法建表。建表和尾插法建表。 （）头插法建单链表（）头插法建单链表 头插法生成的链表的结点次序与输入顺序相反。头插法生成的链表的结点次序与输入顺序相反。 【算法【算法2-92-9】头插法建立单链表】头插法建立单链表 LinkList CreatListF(void)LinkList CreatListF(void) char ch;char ch; LinkList head; LinkList head; ListNode ListNode * *s;s; head=(ListNode head=(ListNode * *)malloc

49、(sizeof(ListNode);)malloc(sizeof(ListNode); ch=getchar(); ch=getchar(); while(ch!=n)while(ch!=n) s=(ListNode s=(ListNode * *)malloc(sizeof(ListNode); )malloc(sizeof(ListNode); s-data=ch;s-data=ch; s-next=head-next;s-next=head-next; head-next=s;head-next=s; ch=getchar();ch=getchar(); return head;retu

50、rn head; 第第 2 2 章章 线线 性性 表表 在利用尾插法建表时有几点需要注意：在利用尾插法建表时有几点需要注意：采用尾采用尾 插法建表，生成的链表中结点的次序和输入顺序插法建表，生成的链表中结点的次序和输入顺序 一致；一致；增加一个尾指针增加一个尾指针r,r,使其始终指向当前链使其始终指向当前链 表的尾结点。表的尾结点。 （）尾插法建单链表（）尾插法建单链表 【算法【算法2-102-10】尾插法建立单链表】尾插法建立单链表 LinkList CreatListR1(void) char ch; LinkList head； ListNode *s,*r; head=(ListNod

51、e *)malloc(sizeof(ListNode); r=head; ch=getchar(); while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode); s-data=ch; r-next=s; r=s; r-next=NULL;return head; 第第 2 2 章章 线线 性性 表表 从第一个结点开始，顺着指针链依次访问每一个从第一个结点开始，顺着指针链依次访问每一个 结点并输出。结点并输出。 void PrintList(LinkList L)void PrintList(LinkList L) ListNode

52、 ListNode * *p;p; p=L-next; p=L-next; while(p!=NULL) while(p!=NULL) printf(%4d,p-data); printf(%4d,p-data); p=p-next; p=p-next; printf(n); printf(n); 7 7链表元素输出运算链表元素输出运算PrintList(L)PrintList(L)的实现的实现 第第 2 2 章章 线线 性性 表表 在单链表中，最后一个结点的指针域为空。访问单链在单链表中，最后一个结点的指针域为空。访问单链 表中任何数据只能从链表头开始顺序访问，而不能进表中任何数据只能从链表

53、头开始顺序访问，而不能进 行任何位置的随机查询访问。如要查询的结点在链表行任何位置的随机查询访问。如要查询的结点在链表 的尾部则需遍历整个链表。所以单链表的应用受到一的尾部则需遍历整个链表。所以单链表的应用受到一 定的限制。对单链表进行改进：定的限制。对单链表进行改进： head . a1a2ai an （a ） 带头结点的空循环链表 （b ） 带头结点的循环链表 head 第第 2 2 章章 线线 性性 表表 循环链表是另一种形式的链式存储结构。它将单循环链表是另一种形式的链式存储结构。它将单 链表中最后一个结点的指针指向链表的头结点，链表中最后一个结点的指针指向链表的头结点， 使整个链表头

54、尾相接形成一个环形。这样，从链使整个链表头尾相接形成一个环形。这样，从链 表中任一结点出发，顺着指针链都可找到表中其表中任一结点出发，顺着指针链都可找到表中其 它结点。它结点。 循环链表的最大特点是不增加存储量，只是简单循环链表的最大特点是不增加存储量，只是简单 地改变一下最后一个结点的指针指向，就可以使地改变一下最后一个结点的指针指向，就可以使 操作更加方便灵活。操作更加方便灵活。 带头结点的单循环链表的操作算法和带头结点的单链表的操带头结点的单循环链表的操作算法和带头结点的单链表的操 作算法很相似，差别仅在于算法中的循环条件不同。作算法很相似，差别仅在于算法中的循环条件不同。 第第 2 2

55、 章章 线线 性性 表表 双向链表用两个指针表示结点间的逻辑关系。双向链表用两个指针表示结点间的逻辑关系。 其增加了一个指向直接前驱的指针域，这样形成其增加了一个指向直接前驱的指针域，这样形成 的链表有两条不同方向的链，前驱和后继，因此的链表有两条不同方向的链，前驱和后继，因此 称为双链表。称为双链表。 双向链表结点的定义如下：双向链表结点的定义如下： typedef struct DNode ElemType data; struct DNode *prior; struct DNode *next; Dnode,*DuLinkList; priordatanext 双向链表结点的结构：双向

56、链表结点的结构： 第第 2 2 章章 线线 性性 表表 a1a2an . (a)空双向链表 （b )非 空双向链表 head head 双向链表结构示意图：双向链表结构示意图： 第第 2 2 章章 线线 性性 表表 ai-1 x s-data=x s ai p ai-1 s ai p (a)插入前的状态 x (b)插入过程 关键语句： s -prior=p-prior; s -next=p; p -prior=s; s -prior-next=s; 关键语句指针操作序列既不是唯一也不是任意的。操作关键语句指针操作序列既不是唯一也不是任意的。操作 必须在操作必须在操作之前完成，否则之前完成，否则*p的前驱结点就丢掉了。的前驱结点就丢掉了。 第第 2 2 章章 线线 性性 表表 q -next-prior=p; . . ai-1ai q ai+1 ai-1ai q ai+1 (a)删除前状态 ( b） 删除过程 . 关键语