数据结构-2-线性表.ppt

《数据结构-2-线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构-2-线性表.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 线性表 2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加2.1 线性表的类型定义n n线性结构的特点：线性结构的特点：在数据元素的非空有限集中，在数据元素的非空有限集中，1）有且）有且仅有一个开始结点；仅有一个开始结点；2）有且仅有一个终端结）有且仅有一个终端结点；点；3）除第一个结点外，集合中的每个数据）除第一个结点外，集合中的每个数据元素均有且只有一个前驱；元素均有且只有一个前驱；4）除最后一个结）除最后一个结点外，集合中的每个数据元素均有且只有一点外，集合中的每个数据元素均有且只有一个后继。个后继。n n线性序列：

2、线性结构中的所有结点按其关系线性序列：线性结构中的所有结点按其关系可以排成一个序列，记为可以排成一个序列，记为(a1,ai,ai+1,an)2.1 线性表的类型定义1.1.线性表线性表线性表线性表 1 1）线性表是）线性表是）线性表是）线性表是n(n 0)n(n 0)个数据元素的有限序列。个数据元素的有限序列。个数据元素的有限序列。个数据元素的有限序列。2 2）线性表是一种最常用且最简单的数据结构。）线性表是一种最常用且最简单的数据结构。）线性表是一种最常用且最简单的数据结构。）线性表是一种最常用且最简单的数据结构。含有含有含有含有n n个数据元素的线性表是一个数据结构：个数据元素的线性表是一

3、个数据结构：个数据元素的线性表是一个数据结构：个数据元素的线性表是一个数据结构：List=(D,R)List=(D,R)其中：其中：其中：其中：D=D=a ai i|a|ai iD D0 0,i=1,2,n,n0,i=1,2,n,n0 R=N,N=a R=N,N=|a|ai-1i-1,a ai i D D0 0,i=2,3,n,i=2,3,n D D0 0 为某个数据对象为某个数据对象为某个数据对象为某个数据对象数据的子集数据的子集数据的子集数据的子集uu特性：均匀性，有序性（线性序列关系）特性：均匀性，有序性（线性序列关系）特性：均匀性，有序性（线性序列关系）特性：均匀性，有序性（线性序列关

4、系）2.1 线性表的类型定义1.1.线性表线性表线性表线性表 3 3）线性表的长度及空表）线性表的长度及空表）线性表的长度及空表）线性表的长度及空表uu线性表中数据元素的个数线性表中数据元素的个数线性表中数据元素的个数线性表中数据元素的个数n n（n0n0）定义为线性表的长度定义为线性表的长度定义为线性表的长度定义为线性表的长度uu当线性表的长度为当线性表的长度为当线性表的长度为当线性表的长度为0 0 时，称为空表。时，称为空表。时，称为空表。时，称为空表。uu a ai i 是第是第是第是第i i个数据元素，称个数据元素，称个数据元素，称个数据元素，称i i为为为为a ai i 在线性表中的

5、位序。在线性表中的位序。在线性表中的位序。在线性表中的位序。2.线性表的基本操作 p19p201 1）InitListInitList(&L)(&L)初始化，构造一个空的线性表初始化，构造一个空的线性表2 2）ListLengthListLength(L)(L)求长度求长度,返回线性表中数据元返回线性表中数据元素个数素个数3 3）GetElemGetElem(L,i,&e)(L,i,&e)取表取表L L中第中第i i个数据元素赋值个数据元素赋值给给e e4 4）LocateElemLocateElem(L,e)(L,e)按值查找，若表中存在一按值查找，若表中存在一个或多个值为个或多个值为e e

6、的结点，返回第一个找到的数的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。据元素的位序，否则返回一个特殊值。5 5）ListInsertListInsert(&L,i,e)(&L,i,e)在在L L中第中第i i个位置前插入新个位置前插入新的数据元素的数据元素e e，表长加表长加1 1。6 6）ListDeleteListDelete(&L,i,e)(&L,i,e)删除表中第删除表中第i i个数据元素，个数据元素，e e返回其值，表长减返回其值，表长减1 1。线性表的基本操作举例n n例2-1 求A=A B P20算法2.1uu时间复杂度：LocateElem()执行次数 O(Li

7、stLength(A)*ListLength(B)n n例2-2 合并LA 和 LB 到LC中 P20-21算法2.2uu时间复杂度：ListInsert()执行次数O(ListLength(LA)+ListLength(LB)2.2 线性表的顺序表示和实现 1.顺序表线性表的顺序存储结构1 1）在计算机内存中用一组地址连续的存储单元依次）在计算机内存中用一组地址连续的存储单元依次 存储线性表中的各个数据元素。存储线性表中的各个数据元素。2 2）假设线性表的每个元素需占用）假设线性表的每个元素需占用L L个存储单元，并以个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始存所占的第一个

8、单元的存储地址作为数据元素的起始存储位置，则线性表中第储位置，则线性表中第i+1i+1个数据元素的存储位置个数据元素的存储位置LocLoc(a(ai+1i+1)和第和第i i个数据元素的存储位置个数据元素的存储位置Loc(Loc(a ai i)之间满足下之间满足下列关系：列关系：Loc(aLoc(ai+1i+1)=Loc()=Loc(a ai i)+L)+L 一般来说，线性表的第一般来说，线性表的第i i个元素个元素a ai i的存储位置为：的存储位置为：Loc(Loc(a ai i)=Loc(a)=Loc(a1 1)+(i-1)*L)+(i-1)*L 其中其中Loc(aLoc(a1 1)是线

9、性表的第一个数据元素是线性表的第一个数据元素a a1 1的存储位置，的存储位置，通常称作线性表的通常称作线性表的起始位置起始位置起始位置起始位置或或基地址基地址基地址基地址。1.顺序表线性表的顺序存储结构3 3）线性表的顺序存储结构示意图）线性表的顺序存储结构示意图p22p22图图2.2.2 2n n用用“物理位置物理位置”相邻来表示线性表中数据元素之间相邻来表示线性表中数据元素之间的逻辑关系。的逻辑关系。n n根据线性表的顺序存储结构的特点，只要确定了存根据线性表的顺序存储结构的特点，只要确定了存储线性表的起始位置，线性表中任一数据元素都可储线性表的起始位置，线性表中任一数据元素都可随机存取

10、，所以，线性表的顺序存储结构是一种随机存取，所以，线性表的顺序存储结构是一种随随随随机存取机存取机存取机存取的存储结构。的存储结构。#define LIST_MAX_LENTH 100/define LIST_MAX_LENTH 100/define LIST_MAX_LENTH 100/define LIST_MAX_LENTH 100/或者或者或者或者N/N/N/N/或者是一或者是一或者是一或者是一 个个个个 常数常数常数常数typedef struct ElemTypetypedef struct ElemTypetypedef struct ElemTypetypedef struct

11、 ElemType int int int int *elemelemelemelem;int int int int length;length;length;length;SqList SqList SqList SqList;SqList SqList SqList SqList L;L;L;L;2.顺序存储线性表的描述v C语言中静态分配描述求置空表Status Status ClearListClearList(&L)(&L)L.length=0;L.length=0;return OK;return OK;2.顺序存储线性表的描述求长度Status List length(Stat

12、us List length(SqList SqList L)L)length=L.length;length=L.length;return OK;return OK;2.顺序存储线性表的描述初始化Status Status Status Status InitListInitListInitListInitList_ _ _ _ SqListSqListSqListSqList(SqList SqList SqList SqList L)L)L)L)L.L.L.L.elemelemelemelem=(*=(*=(*=(*intintintint)malloc malloc malloc m

13、alloc(LIST_MAX_LENGTH(LIST_MAX_LENGTH(LIST_MAX_LENGTH(LIST_MAX_LENGTH *sizeofsizeofsizeofsizeof(intintintint););););if(!L.if(!L.if(!L.if(!L.elemelemelemelem)exit(Overflow);)exit(Overflow);)exit(Overflow);)exit(Overflow);L.length=0;L.length=0;L.length=0;L.length=0;return OK;return OK;return OK;return

14、 OK;2.顺序存储线性表的描述2.顺序表的描述1)C语言中动态分配描述#define LIST_INIT_SIZE 100define LIST_INIT_SIZE 100define LIST_INIT_SIZE 100define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define LISTINCREMENT 10#define LISTINCREMENT 10#define LISTINCREMENT 10typedef structtypedef structtypedef structtypedef struct ElemType E

15、lemType ElemType ElemType *elemelemelemelem;int int int int length;length;length;length;int listsizeint listsizeint listsizeint listsize;SqListSqListSqListSqList;SqList SqList SqList SqList L;L;L;L;n n说明：说明：elemelemelemelem数组指针指向线性表的基地址；数组指针指向线性表的基地址；lengthlengthlengthlength指示线性指示线性表的当前长度；表的当前长度；lis

16、tsizelistsizelistsizelistsize指示顺序表当前分配的存储空间大指示顺序表当前分配的存储空间大小。当空间不足时，再分配的存储空间增量为小。当空间不足时，再分配的存储空间增量为 LISTINCREMENT*LISTINCREMENT*LISTINCREMENT*LISTINCREMENT*sizeofsizeofsizeofsizeof(ElemTypeElemTypeElemTypeElemType)2)几个基本操作初始化n np23算法2.3 Status Status Status Status InitListInitListInitListInitList_ _

17、 _ _SqListSqListSqListSqList(SqListSqListSqListSqList&L)&L)&L)&L)L.L.L.L.elemelemelemelem=(=(=(=(ElemTypeElemTypeElemTypeElemType*)*)*)*)mallocmallocmallocmalloc(LIST_INIT_SIZE(LIST_INIT_SIZE(LIST_INIT_SIZE(LIST_INIT_SIZE *sizeofsizeofsizeofsizeof(ElemTypeElemTypeElemTypeElemType););););if(!L.if(!L.

18、if(!L.if(!L.elemelemelemelem)exit(OVERFLOW);)exit(OVERFLOW);)exit(OVERFLOW);)exit(OVERFLOW);L.length=0;L.length=0;L.length=0;L.length=0;L.L.L.L.listsizelistsizelistsizelistsize=LIST_INIT_SIZE;=LIST_INIT_SIZE;=LIST_INIT_SIZE;=LIST_INIT_SIZE;return OK;return OK;return OK;return OK;插入 p24算法2.4 Status S

19、tatus Status Status ListInsertListInsertListInsertListInsert_sq(_sq(_sq(_sq(SqListSqListSqListSqList&L,&L,&L,&L,intintintint i,i,i,i,ElemTypeElemTypeElemTypeElemType e)e)e)e)if(iL.length+1)return ERROR;if(iL.length+1)return ERROR;if(iL.length+1)return ERROR;if(iL.length+1)return ERROR;if(L.length=L.

20、if(L.length=L.if(L.length=L.if(L.length=L.listsizelistsizelistsizelistsize)newbasenewbasenewbasenewbase=(=(=(=(ElemTypeElemTypeElemTypeElemType*)*)*)*)reallocreallocreallocrealloc(L.(L.(L.(L.elemelemelemelem,(L.(L.(L.(L.listsizelistsizelistsizelistsize+LISTINCREMENT)*+LISTINCREMENT)*+LISTINCREMENT)*

21、+LISTINCREMENT)*sizeofsizeofsizeofsizeof(ElemTypeElemTypeElemTypeElemType););););if(!L.if(!L.if(!L.if(!L.elemelemelemelem)exit(OVERFLOW);)exit(OVERFLOW);)exit(OVERFLOW);)exit(OVERFLOW);L.L.L.L.elemelemelemelem=newbase newbase newbase newbase;L.L.L.L.listsizelistsizelistsizelistsize+=LISTINCREMENT;+=

22、LISTINCREMENT;+=LISTINCREMENT;+=LISTINCREMENT;n n需将第需将第n(n(即即L.length)L.length)至第至第i i个元素向后移动一个位置。个元素向后移动一个位置。注意：注意：C C语言中数组下标从语言中数组下标从0 0开始，则表中第开始，则表中第i i个数据个数据元素是元素是L.elemi-1L.elemi-1。插入 p24算法2.4 函数realloc的格式及功能格式：void*realloc(void*p,unsigned size)功能：将p所指向的已分配内存区域的大小 改为size。size可以比原来分配的空间大或小。插入（续）

23、q=&(L.elemi-1);q=&(L.elemi-1);q=&(L.elemi-1);q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)for(p=&(L.elemL.length-1);p=q;-p)for(p=&(L.elemL.length-1);p=q;-p)for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*(p+1)=*p;*(p+1)=*p;*(p+1)=*p;*q=e;*q=e;*q=e;*q=e;+L.length;+L.length;+L.length;+L.length;return O

24、K;return OK;return OK;return OK;删除 p24p25算法2.5 Status Status Status Status ListDeleteListDeleteListDeleteListDelete_sq(_sq(_sq(_sq(SqListSqListSqListSqList&L,&L,&L,&L,intintintint i,i,i,i,ElemTypeElemTypeElemTypeElemType&e)&e)&e)&e)if(iL.length)return ERROR;if(iL.length)return ERROR;if(iL.length)ret

25、urn ERROR;if(iL.length)return ERROR;p=&(L.p=&(L.p=&(L.p=&(L.elemelemelemelemi-1);i-1);i-1);i-1);e=*p;e=*p;e=*p;e=*p;q=L.q=L.q=L.q=L.elemelemelemelem+length-1;/+length-1;/+length-1;/+length-1;/表尾表尾表尾表尾 for(+p;p=q;+p)*(p-1)=*p;for(+p;p=q;+p)*(p-1)=*p;for(+p;p=q;+p)*(p-1)=*p;for(+p;p=q;+p)*(p-1)=*p;-L.

26、length;-L.length;-L.length;-L.length;return OK return OK return OK return OK uu需将第需将第i+1i+1至第至第L.lengthL.length个元素向前移动一个位置个元素向前移动一个位置插入和删除算法时间分析n n用用“移动结点的次数移动结点的次数”来衡量时间复杂度。与表长及插来衡量时间复杂度。与表长及插入位置有关。入位置有关。n n插入：插入：uu最坏：最坏：i=1i=1，移动次数为移动次数为n nuu最好最好:i=i=表长表长+1+1，移动次数为，移动次数为0 0uu平均：等概率情况下，平均移动次数平均：等概率

27、情况下，平均移动次数n/2 n/2 n n删除：删除：uu最坏：最坏：i=1i=1，移动次数为移动次数为n-1n-1uu最好最好:i=i=表长，移动次数为表长，移动次数为0 0uu平均：等概率情况下，平均移动次数平均：等概率情况下，平均移动次数(n-1)/2n-1)/2查找p25p26算法2.6 intintintint LocateElemLocateElemLocateElemLocateElem_Sq(_Sq(_Sq(_Sq(SqListSqListSqListSqList L,L,L,L,ElemTypeElemTypeElemTypeElemType e)e)e)e)i=1;i=1;

28、i=1;i=1;while(i=L.length&e!=L.elemi-1)+i;while(i=L.length&e!=L.elemi-1)+i;while(i=L.length&e!=L.elemi-1)+i;while(i=L.length&e!=L.elemi-1)+i;if(i=L.length)return i;else return 0;if(i=L.length)return i;else return 0;if(i=L.length)return i;else return 0;if(i=L.length)return i;else return 0;查找的另一种描述i=1;

29、i=1;i=1;i=1;p=L.p=L.p=L.p=L.elemelemelemelem;while(i=L.length&e!=*p+)+i;while(i=L.length&e!=*p+)+i;while(i=L.length&e!=*p+)+i;while(i=L.length&e!=*p+)+i;if(i=L.length)return i;if(i=L.length)return i;if(i=L.length)return i;if(i=L.length)return i;else return 0;else return 0;else return 0;else return 0

30、;合并 P26算法2.7void void MergeListMergeList_Sq(_Sq(SqListSqList La,La,SqListSqList Lb,Lb,SqListSqList&LcLc)pa=La.pa=La.elemelem;pbpb=Lb.=Lb.elemelem;LcLc.listsizelistsize=LcLc.length=La.length+Lb.length;.length=La.length+Lb.length;pc=pc=LcLc.elemelem=(=(ElemTypeElemType*)*)mallocmalloc(LcLc.listsizelis

31、tsize*sizeofsizeof(ElemElemTypeType););if(!if(!LcLc.elemelem)exit(OVERFLOW);)exit(OVERFLOW);pa_last=La.elem+La.length-1;pa_last=La.elem+La.length-1;pbpb_last=Lb.elem+Lb.length-1;_last=Lb.elem+Lb.length-1;while(pa=pa_last&while(pa=pa_last&pbpb=pbpb_last)_last)if(*pa=*if(*pa=*pbpb)*pc+=*pa+;)*pc+=*pa+

32、;else*pc+=*else*pc+=*pbpb+;+;while(pa=pa_last)*pc+=*pa+;while(pa=pa_last)*pc+=*pa+;while(while(pbpb=pbpb_last)*pc+=*_last)*pc+=*pbpb+;+;建立#define LIST_INIT_SIZE 100define LIST_INIT_SIZE 100Status Status CreateListCreateList_Sq(_Sq(SqList SqList&L,&L,intint n)n)intint i;i;L.L.elemelem=(=(intint*)*)ma

33、llocmalloc(LIST_INIT_SIZE(LIST_INIT_SIZE *sizeofsizeof(intint););if(!L.if(!L.elemelem)exit(OVERFLOW);)exit(OVERFLOW);L.length=n;L.length=n;L.L.ListsizeListsize=LIST_INIT_SIZE;=LIST_INIT_SIZE;for(i=0;in;i+)scanf(%d,&L.for(i=0;in;i+)scanf(%d,&L.elemelemi);i);for(i=0;in;i+)for(i=0;i=La.if(La.length=La.

34、listsizelistsize)return OVERFLOW;)return OVERFLOW;while(i La.length&La.while(i La.length&La.elemelemix)i+;i=i;j-)j=La.length-1;j=i;j-)La.elemj+1=La.La.elemj+1=La.elemelemj;j;La.La.elemelemi=x;i=x;La.length+;La.length+;return OK;return OK;递减插入Status Status DeOrderInsertDeOrderInsert_Sq(_Sq(SqListSqLi

35、st&La,&La,ElemTypeElemType x)x)intint i,j;i,j;if(La.length=La.if(La.length=La.listsizelistsize)return OVERFLOW;)return OVERFLOW;i=La.length-1;i=La.length-1;while(i=0&La.while(i=0&La.elemelemix)i-;ii;j-)for(j=La.length-1;ji;j-)La.elemj+1=La.La.elemj+1=La.elemelemj;j;La.elemi+1=x;La.elemi+1=x;La.lengt

36、h+;La.length+;return OK;return OK;4.顺序表的分析1 1）优点）优点uu顺序表的结构简单顺序表的结构简单uu顺序表的存储效率高，是紧凑结构顺序表的存储效率高，是紧凑结构uu顺序表是一个随机存储结构（直接存取结构）顺序表是一个随机存储结构（直接存取结构）顺序表是一个随机存储结构（直接存取结构）顺序表是一个随机存储结构（直接存取结构）2 2）缺点）缺点uu在顺序表中进行插入和删除操作时，需要移动数据在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。元素，算法效率较低。uu对长度变化较大的线性表，或者要预先分配较大空对长度变化较大的线性表，或者要预先分

37、配较大空间或者要经常扩充线性表，给操作带来不方便。间或者要经常扩充线性表，给操作带来不方便。uu原因：数组的静态特性造成原因：数组的静态特性造成2.3 线性表的链式表示和实现1.线性链表n n特点：在内存中用一组任意的存储单元来存储线性特点：在内存中用一组任意的存储单元来存储线性表的数据元素，用每个数据元素所带的指针来确定表的数据元素，用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成数据元其后继元素的存储位置。这两部分信息组成数据元素的存储映像，称作素的存储映像，称作结点结点结点结点。n n结点结点结点结点：数据域：数据域 +指针域（链域）指针域（链域）n n链式存储结构：

38、链式存储结构：n n个结点链接成一个链表个结点链接成一个链表n n线性链表（单链表）：链表的每个结点只包含一个线性链表（单链表）：链表的每个结点只包含一个指针域。指针域。datanext单链表(Singly Linked List)n nfirst first 头指针头指针n nlast last 尾指针尾指针 n n 指针为空指针为空n n单链表由头指针唯一确单链表由头指针唯一确定，因此常用头指针的定，因此常用头指针的名字来命名。如表名字来命名。如表first.first.单链表的存储映像单链表的存储映像1）线性链表的描述 p28typedef struct LNode ElemType d

39、ata;Struct LNode *next;LNode,*LinkList;LinkList L;/L是LinkList类型的变量，表示单链表的头指针2）术语n n头指针：指向链表中第一个结点n n第一个数据元素结点（开始结点）n n头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。uu说明：头结点的说明：头结点的nextnext域指向链表中的第一个数据域指向链表中的第一个数据元素结点。元素结点。uu对于头结点数据域的处理：对于头结点数据域的处理：a.a.加特殊信息加特殊信息 b.b.置空置空 c.c.如数据域为整型，则在该处存放链表长度信息。如数据域为整型，则在该处存放

40、链表长度信息。3）带头结点的单链表示意图 p28图2.7n n由于开始结点的位置被存放在头结点的指针域中，所以由于开始结点的位置被存放在头结点的指针域中，所以由于开始结点的位置被存放在头结点的指针域中，所以由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处对链表第一个位置的操作同其他位置一样，无须特殊处对链表第一个位置的操作同其他位置一样，无须特殊处对链表第一个位置的操作同其他位置一样，无须特殊处理。理。理。理。n n无论链表是否为空，其头指针是指向头结点的非空指针，无论链表是否为空，其头指针是指向头结点的非空指针，无论链表是否为空，其头指针是指向

41、头结点的非空指针，无论链表是否为空，其头指针是指向头结点的非空指针，因此对空表与非空表的处理也就统一了，简化了链表操因此对空表与非空表的处理也就统一了，简化了链表操因此对空表与非空表的处理也就统一了，简化了链表操因此对空表与非空表的处理也就统一了，简化了链表操作的实现。作的实现。作的实现。作的实现。非空表非空表 空表空表2.基本操作1）取元素 p29 算法2.82）插入元素 p30 算法2.9 3）删除元素 p30 算法2.104）建立链表 p30p31 算法2.115）有序链表的合并 p31 算法2.126）查找（按值查找）7）求长度8）集合的并运算取元素（按序号查找）p29 算法2.8 从

42、链表的头指针出发，顺链域next逐个结点往下搜索，直至找到第i个结点为止（j=i)Status GetElem_L(LinkList L,int i,ElemType&e)LinkList p;p=L-next;int j=1;while(p&jnext;+j;if(!p|ji)return ERROR;e=p-data;return OK;插入元素p30 算法2.9在第i个元素之前插入，先找到第i-1个结点Status Status ListInsertListInsert_L(_L(LinkListLinkList&L,&L,intint i,i,ElemTypeElemType e)e)

43、LinkListLinkList p,s;p,s;p=L;p=L;intint j=0;j=0;while(p&jnext;+j;while(p&jnext;+j;if(!p|j i-1)return ERROR;if(!p|j i-1)return ERROR;s=(s=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););s-data=e;s-next=p-next;s-data=e;s-next=p-next;p-next=s;p-next=s;return OK;return OK;esP-next=s(2)(3)ps-ne

44、xt=p-nexta(1)b在带表头结点的单链表在带表头结点的单链表 第一个结点前插入新结点第一个结点前插入新结点 newnodenext=pnext;if(pnext=NULL)last=newnode;pnext=newnode;删除元素p30 算法2.10Status Status ListDeleteListDelete_L(_L(LinkListLinkList&L,&L,intint i,i,ElemTypeElemType&e)&e)LinkListLinkList p,q;p,q;p=L;p=L;intint j=0;j=0;while(p-next&jnext;+j;whil

45、e(p-next&jnext;+j;if(!(p-next)|j i-1)return ERROR;if(!(p-next)|j i-1)return ERROR;q=p-next;q=p-next;p-next=q-next;p-next=q-next;e=q-data;e=q-data;free(q);free(q);return OK;return OK;q=pnext;pnext=qnext;delete q;if(pnext=NULL)last=p;从带表头结点的单链表中删除第一个结点从带表头结点的单链表中删除第一个结点建立链表（头插法建表）p31 算法2.11在链表表头插入新结点，

46、结点次序与输入次序相反。void void CreateListCreateList_L(_L(LinkListLinkList&L,&L,intint n)n)LinkListLinkList p;p;L=(L=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););L-next=NULL;L-next=NULL;for(for(intint i=n;i0;-i)i=n;i0;-i)p=(p=(LinkListLinkList)mallocmalloc(sizeofsizeof(LNodeLNode););scanfscanf(%d

47、,&p-data);(%d,&p-data);p-next=L-next;L-next=p;p-next=L-next;L-next=p;尾插法建表：将新结点插到链表尾部，须增设一个尾插法建表：将新结点插到链表尾部，须增设一个 尾指针尾指针lastlast，使其始终指向当前链表使其始终指向当前链表 的尾结点。的尾结点。合并有序链表p31 算法2.12void void MergeListMergeList_L_L(LinkListLinkList La,La,LinkListLinkList Lb,Lb,LinkListLinkList&LcLc)LinkListLinkList pa,pa,

48、pbpb,pc;,pc;pa=La-next;pa=La-next;pbpb=Lb-next;=Lb-next;LcLc=pc=La;=pc=La;while(pa&while(pa&pbpb)if(pa-data data data)-data)pc-next=pa;pc=pa;pa=pa-next;pc-next=pa;pc=pa;pa=pa-next;else pc-next=else pc-next=pbpb;pc=;pc=pbpb;pbpb=pbpb-next;-next;pc-next=pa?pa:pc-next=pa?pa:pbpb;free(Lb);free(Lb);查找（按值

49、查找）intint LinkLocateLinkLocate_L(_L(LinkListLinkList L,L,intint x)x)intint i;i;LinkList LinkList p;p;p=L-next;i=1;p=L-next;i=1;while(p!=NULL&p-data!=x)while(p!=NULL&p-data!=x)p=p-next;i+;p=p-next;i+;if(!p)if(!p)printf printf(Not found!n);(Not found!n);return(0);return(0);else else printf printf(i=%d

50、n,i);return(i);(i=%dn,i);return(i);求长度intint LinkLengthLinkLength_L(_L(LinkListLinkList L)L)intint j;j;LinkListLinkList p;p;p=L-next;j=0;p=L-next;j=0;while(p)p=p-next;j+;while(p)p=p-next;j+;return(j);return(j);注意：注意：p=NULLp=NULL与与p-next=NULLp-next=NULL是不同的。是不同的。n n总结：总结：带头结点：链表置空带头结点：链表置空 L-L-next=N