《数据结构课件线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构课件线性表.ppt（68页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章 线性表 2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加2.1 线性表的类型定义n n线性结构的特点：在数据元素的非空有限集中，1）有且仅有一个开始结点；2）有且仅有一个终端结点；3）除第一个结点外，集合中的每个数据元素均有且只有一个前驱；4）除最后一个结点外，集合中的每个数据元素均有且只有一个后继。n n线性序列：线性结构中的所有结点按其关系可以排成一个序列，记为(a1,ai,ai+1,an)2.1 线性表的类型定义1.1.线性表线性表 1 1）线性表是）线性表是n(n 0)n(n 0)个数据元素的有限序列。个数据元素
2、的有限序列。2 2）线性表是一种最常用且最简单的数据结构。）线性表是一种最常用且最简单的数据结构。含有含有n n个数据元素的线性表是一个数据结构：个数据元素的线性表是一个数据结构：List=(D,R)List=(D,R)其中：其中：D=aD=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=,i=2,3,n2,3,n D D0 0 为某个数据对象为某个数据对象数据的子集数据的子集uu特性：均匀性，有序性（线性序列关系）特性：均匀性，有序性（线性序列关系）2.1 线性表的类型定义1.1
3、.线性表线性表 3 3）线性表的长度及空表）线性表的长度及空表uu线性表中数据元素的个数线性表中数据元素的个数n n（n0n0）定义为线性表的长度）定义为线性表的长度uu当线性表的长度为当线性表的长度为0 0 时，称为空表。时，称为空表。uu a ai i 是第是第i i个数据元素，称个数据元素，称i i为为a ai i 在线性表中的位序。在线性表中的位序。2.线性表的基本操作 p19p201 1）InitList(&L)InitList(&L)初始化，构造一个空的线性表初始化，构造一个空的线性表2 2）ListLength(L)ListLength(L)求长度求长度,返回线性表中数据元返回线
4、性表中数据元素个数素个数3 3）GetElem(L,i,&e)GetElem(L,i,&e)取表取表L L中第中第i i个数据元素赋值个数据元素赋值给给e e4 4）LocateElem(L,e)LocateElem(L,e)按值查找，若表中存在一按值查找，若表中存在一个或多个值为个或多个值为e e的结点，返回第一个找到的数的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。据元素的位序，否则返回一个特殊值。5 5）ListInsert(&L,i,e)ListInsert(&L,i,e)在在L L中第中第i i个位置前插入新个位置前插入新的数据元素的数据元素e e，表长加，表长加1 1
5、。6 6）ListDelete(&L,i,e)ListDelete(&L,i,e)删除表中第删除表中第i i个数据元素，个数据元素，e e返回其值，表长减返回其值，表长减1 1。线性表的基本操作举例n n例2-1 求A=A B P20算法2.1uu时间复杂度：LocateElem()执行次数 O(ListLength(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）
6、在计算机内存中用一组地址连续的存储单元依次）在计算机内存中用一组地址连续的存储单元依次 存储线性表中的各个数据元素。存储线性表中的各个数据元素。2 2）假设线性表的每个元素需占用）假设线性表的每个元素需占用L L个存储单元，并以个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始存所占的第一个单元的存储地址作为数据元素的起始存储位置，则线性表中第储位置，则线性表中第i+1i+1个数据元素的存储位置个数据元素的存储位置LocLoc(a(ai+1i+1)和第和第i i个数据元素的存储位置个数据元素的存储位置Loc(aLoc(ai i)之间满足下之间满足下列关系：列关系：Loc(a Loc(
7、ai+1i+1)=Loc(a)=Loc(ai i)+L)+L 一般来说，线性表的第一般来说，线性表的第i i个元素个元素a ai i的存储位置为：的存储位置为：Loc(a Loc(ai i)=Loc(a)=Loc(a1 1)+(i-1)*L)+(i-1)*L 其中其中Loc(aLoc(a1 1)是线性表的第一个数据元素是线性表的第一个数据元素a a1 1的存储位置，的存储位置，通常称作线性表的通常称作线性表的起始位置起始位置起始位置起始位置或或基地址基地址基地址基地址。1.顺序表线性表的顺序存储结构3 3）线性表的顺序存储结构示意图）线性表的顺序存储结构示意图p22p22图图2.22.2n n
8、用用“物理位置物理位置”相邻来表示线性表中数据元素之间相邻来表示线性表中数据元素之间的逻辑关系。的逻辑关系。n n根据线性表的顺序存储结构的特点，只要确定了存根据线性表的顺序存储结构的特点，只要确定了存储线性表的起始位置，线性表中任一数据元素都可储线性表的起始位置，线性表中任一数据元素都可随机存取，所以，线性表的顺序存储结构是一种随机存取，所以，线性表的顺序存储结构是一种随随随随机存取机存取机存取机存取的存储结构。的存储结构。#define LIST_MAX_LENTH 100/#define LIST_MAX_LENTH 100/或者或者N/N/或者是一或者是一 个个 常数常数typedef
9、 struct ElemType typedef struct ElemType int *elem;/int *elem;/存储空间的基址存储空间的基址 int length;/int length;/当前的长度当前的长度 SqList;SqList;SqList L;SqList L;2.顺序存储线性表的描述v C语言中静态分配描述 p22求置空表Status ClearList(&L)L.length=0;return OK;2.顺序存储线性表的描述v C语言中静态分配描述 p22求长度Status List length(SqList L)length=L.length;return
10、OK;2.顺序存储线性表的描述v C语言中静态分配描述 p22初始化Status Status InitListInitList_ _ SqListSqList(SqListSqList L)L)L.elemL.elem=(*=(*intint)malloc(LIST_MAX_LENGTHmalloc(LIST_MAX_LENGTH *sizeof(intsizeof(int););if(!L.elemif(!L.elem)exit(Overflow);)exit(Overflow);L.length=0;L.length=0;return OK;return OK;2.顺序存储线性表的描述v
11、 C语言中静态分配描述 p222.顺序表的描述1)C语言中动态分配描述 p22#define LIST_INIT_SIZE 100#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define LISTINCREMENT 10typedef struct typedef struct ElemType *elem;ElemType *elem;int length;int length;int listsize;int listsize;SqList;SqList;SqList L;SqList L;n n说明：说明：elemelem数组指针
12、指向线性表的基地址；数组指针指向线性表的基地址；lengthlength指示线指示线性表的当前长度；性表的当前长度；listsizelistsize指示顺序表当前分配的存储空间指示顺序表当前分配的存储空间大小。当空间不足时，再分配的存储空间增量为大小。当空间不足时，再分配的存储空间增量为 LISTINCREMENT*sizeof(ElemType)LISTINCREMENT*sizeof(ElemType)2)几个基本操作初始化n np23算法2.3 Status InitList_SqList(SqList&L)L.elem=ElemType*)malloc(LIST_INIT_SIZE *
13、sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;插入 p24算法2.4 Status ListInsert_sq(SqList&L,int i,ElemType e)Status ListInsert_sq(SqList&L,int i,ElemType e)if(iL.length+1)return ERROR;if(iL.length+1)return ERROR;if(L.length=L.listsize)if(L.length=L.listsize)ne
14、wbase=(ElemType*)realloc(L.elem,newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.elem=newbase;L.elem=newbase;L.listsize+=LISTINCREMENT;L.listsize+=LISTINCREMENT;n n需将第需将第n(n(即即L.length)L.length)至第至第i
15、 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可以比原来分配的空间大或小。插入（续）q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;删
16、除 p24p25算法2.5 Status ListDelete_sq(SqList&L,int i,ElemType&e)Status ListDelete_sq(SqList&L,int i,ElemType&e)if(iL.length)return ERROR;if(iL.length)return ERROR;p=&(L.elemi-1);p=&(L.elemi-1);e=*p;e=*p;q=L.elem+length-1;/q=L.elem+length-1;/表尾表尾 首地址首地址+长度长度 for(+p;p=q;+p)*(p-1)=*p;for(+p;p=q;+p)*(p-1)=
17、*p;-L.length;-L.length;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平均：等概率情况下，平均移动次数平均：等概率情况下，平均移动次数n/2 n/2 课本式子课本式子2-52-5
18、n n删除：删除：uu最坏：最坏：i=1i=1，移动次数为，移动次数为n-1n-1uu最好最好:i=:i=表长，移动次数为表长，移动次数为0 0uu平均：等概率情况下，平均移动次数平均：等概率情况下，平均移动次数(n-1)/2(n-1)/2 课本式子课本式子2-62-6查找p25p26算法2.6 int LocateElem_Sq(SqList L,ElemType e)i=1;while(i=L.length&e!=L.elemi-1)+i;if(i=L.length)return i;else return 0;查找的另一种描述i=1;p=L.elem;while(i=L.length&e
19、!=*p+)+i;if(i=L.length)return i;else return 0;合并 P26算法2.7的另外一种描述 void MergeList_Sq(SqList La,SqList Lb,SqList&LcSqList La,SqList Lb,SqList&Lc)int i=0,j=0,k=0;InitList_SqList(Lc);while(i=La.length-1&j=Lb.length-1)if(La.elemi=Lb.elemj)Lc.elemk+=La.elemi+;else Lc.elemk+=Lb.elemj+;while(i=La.length-1)Lc
20、.elemk+=La.elemi+;while(j=Lb.length-1)Lc.elemk+=Lb.elemj+;Lc.length=k;合并 P26算法2.7void MergeList_Sq(SqList La,SqList Lb,SqList&Lc)void MergeList_Sq(SqList La,SqList Lb,SqList&Lc)pa=La.elem;pb=Lb.elem;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;Lc.listsize=Lc.length=La.length+Lb.le
21、ngth;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTypepc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType););if(!Lc.elem)exit(OVERFLOW);if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_l
22、ast&pb=pb_last)while(pa=pa_last&pb=pb_last)if(*pa=*pb)*pc+=*pa+;if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;while(pb=pb_last)*pc+=*pb+;建立#define LIST_INIT_SIZE 100#define LIST_INIT_SIZE 100Status CreateList_Sq(SqLi
23、st&L,int n)Status CreateList_Sq(SqList&L,int n)int i;int i;L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int);if(!L.elem)exit(OVERFLOW);if(!L.elem)exit(OVERFLOW);L.length=n;L.length=n;L.Listsize=LIST_INIT_SIZE;L.Listsize=LIST_INIT_SIZE;for(i=0;in;i+)scanf(%
24、d,&L.elemi);for(i=0;in;i+)scanf(%d,&L.elemi);for(i=0;in;i+)printf(“%d for(i=0;i=La.listsize)return OVERFLOW;OVERFLOW;while(i La.length&La.elemi=i;j-)La.elemj+1=La.elemj;/元素的后移La.elemi=x;/插入La.length+;return OK;递减插入Status DeOrderInsert_Sq(SqList&La,ElemType xSqList&La,ElemType x)int i,j;if(La.length=
25、La.listsize)return OVERFLOW;OVERFLOW;i=La.length-1;while(i=0&La.elemii;j-)La.elemj+1=La.elemj;La.elemi+1=x;La.length+;return OK;4.顺序表的分析1 1）优点）优点uu顺序表的结构简单顺序表的结构简单uu顺序表的存储效率高，是紧凑结构顺序表的存储效率高，是紧凑结构uu顺序表是一个随机存储结构（直接存取结构）顺序表是一个随机存储结构（直接存取结构）顺序表是一个随机存储结构（直接存取结构）顺序表是一个随机存储结构（直接存取结构）2 2）缺点）缺点uu在顺序表中进行插入和删除
26、操作时，需要移动数据在顺序表中进行插入和删除操作时，需要移动数据元素，算法效率较低。元素，算法效率较低。uu对长度变化较大的线性表，或者要预先分配较大空对长度变化较大的线性表，或者要预先分配较大空间或者要经常扩充线性表，给操作带来不方便。间或者要经常扩充线性表，给操作带来不方便。uu原因：数组的静态特性造成原因：数组的静态特性造成作业n n2.1 编写程序，建立并显示一个有10个数据元素的顺序线性表。n n2.2 实现顺序线性表的插入、查找、删除等 算法。顺序表之整体概念：elem01length-1 listsizelength数组下标 内存状态变量操作算法listsize-1初始化操作插入
27、操作删除操作查找操作排序操作.空闲表区 elem 顺序表之整体概念：顺序表有下列缺点：顺序表有下列缺点：（1 1）插入、删除操作时需要移动大量元素，）插入、删除操作时需要移动大量元素，效率较低；效率较低；（2 2）最大表长难以估计，太大了浪费空间，）最大表长难以估计，太大了浪费空间，太小了容易溢出。太小了容易溢出。因此，在插入和删除操作是经常性操作的应用场合因此，在插入和删除操作是经常性操作的应用场合选用顺序存储结构不太合适，此时可以选用链式存储结选用顺序存储结构不太合适，此时可以选用链式存储结构，数据元素之间的逻辑关系由结点中的指针来指示。构，数据元素之间的逻辑关系由结点中的指针来指示。2.
28、3 线性表的链式表示和实现1.线性链表n n特点：在内存中用一组任意的存储单元来存储线性特点：在内存中用一组任意的存储单元来存储线性表的数据元素，用每个数据元素所带的指针来确定表的数据元素，用每个数据元素所带的指针来确定其后继元素的存储位置。这两部分信息组成数据元其后继元素的存储位置。这两部分信息组成数据元素的存储映像，称作素的存储映像，称作结点结点结点结点。n n结点结点结点结点：数据域：数据域+指针域（链域）指针域（链域）n n链式存储结构：链式存储结构：n n个结点链接成一个链表个结点链接成一个链表n n线性链表（单链表）：链表的每个结点只包含一个线性链表（单链表）：链表的每个结点只包含
29、一个指针域。指针域。datanext单链表(Singly Linked List)n nfirst first 头指针头指针n nlast last 尾指针尾指针 n n 指针为空指针为空n n单链表由头指针唯一确单链表由头指针唯一确定，因此常用头指针的定，因此常用头指针的名字来命名。如表名字来命名。如表first.first.单链表的存储映像单链表的存储映像1）线性链表的描述 p28typedef struct LNode ElemType data;Struct LNode *next;LNode,*LinkList;LinkList L;/L是LinkList类型的变量，表示单链表的头指
30、针2）术语n n头指针：指向链表中第一个结点n n第一个数据元素结点（开始结点）n n头结点：有时在单链表的第一个数据元素结点之前附设一个结点，称之头结点。uu说明：头结点的说明：头结点的nextnext域指向链表中的第一个数据域指向链表中的第一个数据元素结点。元素结点。uu对于头结点数据域的处理：对于头结点数据域的处理：a.a.加特殊信息加特殊信息 b.b.置空置空 c.c.如数据域为整型，则在该处存放链表长度信息。如数据域为整型，则在该处存放链表长度信息。3）带头结点的单链表示意图 p28图2.7n n由于开始结点的位置被存放在头结点的指针域中，所以由于开始结点的位置被存放在头结点的指针域
31、中，所以由于开始结点的位置被存放在头结点的指针域中，所以由于开始结点的位置被存放在头结点的指针域中，所以对链表第一个位置的操作同其他位置一样，无须特殊处对链表第一个位置的操作同其他位置一样，无须特殊处对链表第一个位置的操作同其他位置一样，无须特殊处对链表第一个位置的操作同其他位置一样，无须特殊处理。理。理。理。n n无论链表是否为空，其头指针是指向头结点的非空指针，无论链表是否为空，其头指针是指向头结点的非空指针，无论链表是否为空，其头指针是指向头结点的非空指针，无论链表是否为空，其头指针是指向头结点的非空指针，因此对空表与非空表的处理也就统一了，简化了链表操因此对空表与非空表的处理也就统一了
32、，简化了链表操因此对空表与非空表的处理也就统一了，简化了链表操因此对空表与非空表的处理也就统一了，简化了链表操作的实现。作的实现。作的实现。作的实现。非空表非空表 空表空表2.基本操作1）取元素 p29 算法2.82）插入元素 p30 算法2.9 3）删除元素 p30 算法2.104）建立链表 p30p31 算法2.115）有序链表的合并 p31 算法2.126）查找（按值查找）7）求长度8）集合的并运算取元素（按序号查找）p29 算法2.8 从链表的头指针出发，顺链域next逐个结点往下搜索，直至找到第i个结点为止（j=i)Status GetElem_L(LinkList L,int i,
33、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 ListInsert_L(LinkList&L,int i,ElemType e)Status ListInsert_L(LinkList&L,int i,ElemType e)LinkList p,s;LinkList p,s;p=L;int j=0;p=L;int j=0;while(p&jnext;+j;/while
34、(p&jnext;+j;/插入点，前一指针插入点，前一指针if(!p|j i-1)return ERROR;if(!p|j i-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s=(LinkList)malloc(sizeof(LNode);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-next=p-nexta(1)b在带表头结点的单链表在带表头结点的单链表 第一个结点前插入新结点第一个结
35、点前插入新结点 newnodenext=pnext;if(pnext=NULL)last=newnode;pnext=newnode;删除元素p30 算法2.10Status ListDelete_L(LinkList&L,int i,ElemType&e)Status ListDelete_L(LinkList&L,int i,ElemType&e)LinkList p,q;LinkList p,q;p=L;int j=0;p=L;int j=0;while(p-next&jnext;+j;while(p-next&jnext;+j;if(!(p-next)|j i-1)return ERR
36、OR;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在链表表头插入新结点，结点次序与输入次序相反。void CreateList_L(LinkList&L,int n)
37、void CreateList_L(LinkList&L,int n)LinkList p;LinkList p;L=(LinkList)malloc(sizeof(LNode);L=(LinkList)malloc(sizeof(LNode);L-next=NULL;L-next=NULL;for(int i=n;i0;-i)for(int i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);p=(LinkList)malloc(sizeof(LNode);scanf(%d,&p-data);scanf(%d,&p-data);p-next=L-next;L
38、-next=p;p-next=L-next;L-next=p;尾插法建表：将新结点插到链表尾部，须增设一个尾插法建表：将新结点插到链表尾部，须增设一个 尾指针尾指针lastlast，使其始终指向当前链表，使其始终指向当前链表 的尾结点。的尾结点。合并有序链表p31 算法2.12void MergeList_Lvoid MergeList_L(LinkList La,LinkList Lb,LinkList(LinkList La,LinkList Lb,LinkList&Lc)&Lc)LinkList pa,pb,pc;LinkList pa,pb,pc;pa=La-next;pb=Lb-ne
39、xt;pa=La-next;pb=Lb-next;Lc=pc=La;/LaLc=pc=La;/La头结点作为头结点作为LcLc头结点头结点while(pa&pb)while(pa&pb)if(pa-data data)if(pa-data data)pc-next=pa;pc=pa;pa=pa-next;pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;pc-next=pa?pa:pb;free(Lb);free(Lb);查
40、找（按值查找）int LinkLocate_L(LinkList L,int x)int LinkLocate_L(LinkList L,int x)int i;LinkList p;int i;LinkList 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)printf(Not found!n);if(!p)printf(Not found!n);return(0);return(0);else printf(i=%dn,i);
41、return(i);else printf(i=%dn,i);return(i);求长度int LinkLength_L(LinkList L)int LinkLength_L(LinkList L)int j;LinkList p;int j;LinkList 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总结：总结：带头结点：链表置空带头结点：链表置空
42、L-L-next=NULLnext=NULL；判断是否为空的条件判断是否为空的条件 if(L-next=NULL)if(L-next=NULL)不带头结点：则置空不带头结点：则置空 L=NULL;L=NULL;判空条件判空条件 if(L=NULL)if(L=NULL)集合并运算5-2 A=ABvoid UnionList_L(LinkList&La,LinkList Lb)void UnionList_L(LinkList&La,LinkList Lb)LinkList p,q,first;int x;LinkList p,q,first;int x;first=La-next;p=Lb-ne
43、xt;/first=La-next;p=Lb-next;/对对LbLb中的每一个元素中的每一个元素 while(p)while(p)x=p-data;p=p-next;q=first;x=p-data;p=p-next;q=first;while(q&q-data!=x)q=q-next;while(q&q-data!=x)q=q-next;if(!q)if(!q)q=(LinkList)malloc(sizeof(LNode);q=(LinkList)malloc(sizeof(LNode);q-data=x;q-next=La-next;q-data=x;q-next=La-next;La
44、-next=q;La-next=q;说明：n nf firstirst的位置始终不变；的位置始终不变；n n插入位置在插入位置在LaLa表的表头元素之前；表的表头元素之前；n n查找不会在刚刚插入的结点间进行，只能从查找不会在刚刚插入的结点间进行，只能从firstfirst指指向的原始向的原始LaLa表中进行表中进行 （因为每次查找时均有（因为每次查找时均有q=firstq=first）n n时间复杂度：时间复杂度：O(m*n)O(m*n)；对；对LbLb中的每一个元素作判中的每一个元素作判断不在断不在LaLa中，插入到中，插入到LaLa最头最头 3.循环链表1 1）循环链表）循环链表）循环链
45、表）循环链表是一种首尾相接的链表。是一种首尾相接的链表。是一种首尾相接的链表。是一种首尾相接的链表。循环链表最后一个结点的循环链表最后一个结点的循环链表最后一个结点的循环链表最后一个结点的nextnext指针不为指针不为指针不为指针不为 0(0(NULLNULL)，而是指向了表头结点。而是指向了表头结点。而是指向了表头结点。而是指向了表头结点。在循环链表中没有在循环链表中没有在循环链表中没有在循环链表中没有NULLNULL 为简化操作，在循环链表中往往加入表头结点。为简化操作，在循环链表中往往加入表头结点。为简化操作，在循环链表中往往加入表头结点。为简化操作，在循环链表中往往加入表头结点。特点
46、：循环链表中，从任一结点出发都可访问到表中特点：循环链表中，从任一结点出发都可访问到表中特点：循环链表中，从任一结点出发都可访问到表中特点：循环链表中，从任一结点出发都可访问到表中 所有结点；而在单链表中，必须从头指针开始，所有结点；而在单链表中，必须从头指针开始，所有结点；而在单链表中，必须从头指针开始，所有结点；而在单链表中，必须从头指针开始，否则无法访问到该结点之前的其他结点。否则无法访问到该结点之前的其他结点。否则无法访问到该结点之前的其他结点。否则无法访问到该结点之前的其他结点。循环链表与单链表不同的是链表中表尾结点的循环链表与单链表不同的是链表中表尾结点的 指针域不指针域不是是NU
47、LLNULL，而是链表头结点的指针，而是链表头结点的指针HH（链表指针）（链表指针）n循环链表的示例循环链表的示例（循环条件：（循环条件：（循环条件：（循环条件：p!=H)p!=H)n带表头结点的循环链表带表头结点的循环链表（循环条件：（循环条件：（循环条件：（循环条件：p-next!=Hp-next!=H）2）循环链表的操作n n合并两个单链表 p=La;while(p-next)p=p-next;p-next=Lb-next;free(Lb);时间复杂度 O(m)合并两个循环链表p=La;p=La;while(p-next!=La)p=p-next;while(p-next!=La)p=p
48、-next;p-next=Lb-next;/p-next=Lb-next;/合并合并p=p-next;p=p-next;while(p-next!=Lb)p=p-next;while(p-next!=Lb)p=p-next;/找到第二个链表尾结点找到第二个链表尾结点p-next=La;p-next=La;free(Lb);free(Lb);时间复杂度时间复杂度 O(m+n)O(m+n)循环链表的建立算法void CreateList_L(LinkList&L)void CreateList_L(LinkList&L)LinkList p;int x;LinkList p;int x;L=(Li
49、nkList)malloc(sizeof(LNode);L=(LinkList)malloc(sizeof(LNode);L-next=L;L-next=L;while(scanf(%d,&x),x!=0)while(scanf(%d,&x),x!=0)p=(LinkList)malloc(sizeof(LNode);p=(LinkList)malloc(sizeof(LNode);p-data=x;p-next=L-next;p-data=x;p-next=L-next;L-next=p;L-next=p;显示输出算法（带头结点）循环链表void PrintList_LC(LinkList
50、L)LinkList p;p=L-next;printf(L-);while(p!=L)printf(%d-,p-data);p=p-next;printf(Ln);4.双向链表双向链表(Doubly Linked List)n双向链表是指在前驱和后继方向都能游双向链表是指在前驱和后继方向都能游历历(遍历遍历)的线性链表。的线性链表。1)双向链表的结点结构：双向链表的结点结构：前驱方向前驱方向 (a)(a)结点结构结点结构 后继方向后继方向双向链表通常采用带表头结点的循环链双向链表通常采用带表头结点的循环链表形式。表形式。n对双向循环链表中任一结点的指针，对双向循环链表中任一结点的指针，有：有