计算机软件及应用线性表

11七月2024第1页【学习目标】1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。

3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

4.结合线性表类型的定义增强对抽象数据类型的理解。11七月2024第2页【重点和难点】

链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针p和结点*p之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。

【知识点】线性表、顺序表、链表、有序表11七月2024第3页线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。

线性结构

是一个数据元素的有序（次序）集线性表是一种最简单的线性结构11七月2024第4页1

线性表的类型定义3线性表类型的实现

链式映象4一元多项式的表示2线性表类型的实现

顺序映象11七月2024第5页线性表的类型定义11七月2024第6页定义：一个线性表是具有相同类型的n（n≧0）个数据元素的有限序列，通常记为：例英文字母表（A,B,C,…..Z)例数据元素特征：i为元素的序号元素个数n—表长度，n=0空表1<i<n时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继1线性表的定义11七月2024第7页

数据对象：D＝{ai|ai∈D0,i=1,2,...,n,n≥0}{称n

为线性表的表长;

称n=0

时的线性表为空表。}数据关系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),

称i为ai在线性表中的位序。}11七月2024线性表的基本运算置空表setnull(L)：将线性表L置为空表。求长度length(L)：计算线性表L中数据元素的个数。取元素get(L,i)：取出线性表L中第i个数据元素；要求i≤length(L)。取前趋prior(L,x)：取出线性表L中值为x的元素的前趋元素；要求x的位序大于1。取后继next(L,x)：取出线性表L中值为x的元素的后继元素；要求x的位序小于length(L)。定位序locate(L,x)：确定元素x在线性表L中的位置，并给出位置序号；若L中无x返回0。11七月2024线性表的基本运算（续）插入insert(L,x,i)：在线性表L中第i个位置上插入值为x的新元素，使表长增1；要求1≤i≤length(L)+1。删除delete(L,i)：删除线性表L中的第i个元素，使表长减1；要求1≤i≤length(L)。11七月2024第10页利用上述定义的线性表可以实现其它更复杂的操作例

2-2例

2-111七月2024第11页求两个集合的并，即A=A∪B例2-1

11七月2024第12页

要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表

LA中的数据元素插入到线性表LA

中去。上述问题可演绎为：11七月2024第13页1．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访;3．若不存在，则插入之。get(LB,i)→e

locate(LA,e)

insert(LA,n+1,e)操作步骤：11七月2024第14页

e=get(Lb,i);//取Lb中第i个数据元素赋给e

if(!locate(La,e))

insert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之voidunion(La,Lb){La_len=length(La);//求线性表的长度

Lb_len=length(Lb);for(i=1;i<=Lb_len;i++){}}//union11七月2024第15页

已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。仍选用线性表表示集合。例

2-211七月2024第16页集合B集合A从集合B

取出物件放入集合A要求集合A中同样物件不能有两件以上因此，算法的策略应该和例2-1相同11七月2024第17页voidunion(List&La,ListLb){

La_len=length(La);Lb_len=length(Lb);}//unione=get(Lb,i);//取Lb中第i个数据元素赋给e

if(!locate(La,e))

insert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}setnull(La);//构造(空的)线性表LA11七月2024第18页若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)。我们再来看看有序表表示的集合。11七月2024第19页例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)对集合LA和LB而言，

值相同的数据元素必定相邻。要求生成一个新表LC，使LC中的数据元素仍按值非递减有有序排列。11七月2024第20页voidMergeList(ListLa,ListLb,List&Lc){

//本算法将非递减的有序表La和Lb归并为Lc}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空setnull(Lc);//构造空的线性表Lci=j=1;k=0;La_len=length(La);Lb_len=length(Lb);例

2-311七月2024第21页

while(i<=La_len){//当La不空时

ai=get(La,i++);insert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//当Lb不空时

bj=get(Lb,j++);insert(Lc,++k,bj);

}//插入Lb表中剩余元素While((i<=La_len)&&(j<=Lb_len)){//当La,Lb都不空时

ai=get(La,i);bj=get(Lb,j);if(ai<=bj){insert(Lc,++k,ai);++i;}else{insert(Lc,++k,bj);++j}

}11七月2024第22页线性表类型的实现----顺序映象11七月2024第23页

用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2

…ai-1ai

…an线性表的起始地址称作线性表的基地址11七月2024第24页元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*d1≦i≦n特点：逻辑上相邻—物理地址相邻随机存取实现：可用C语言的一维数组实现LOC(a1)+(n-1)*dLOC(a1)LOC(a1)+(i-1)*d存储地址LOC(a1)+dan…..ai…..a2a1d11七月2024顺序表的类型描述

#defineMAXSIZE500typedefstruct{elemtypedata[MAXSIZE];intlast;}sequenlist,seqlist;即把顺序表类型sequenlist描述为一个结构体，域data数组存放表中的数据元素，域last存放表长，data[last]存放表中最后一个元素。11七月2024库函数提供动态地开辟和释放存储单元的有关函数：malloc函数其函数原型为void*malloc(unsignedintsize);其作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数的值（即“返回值”）是一个指向分配域起始地址的指针（类型为void）。如果此函数未能成功地执行（例如内存空间不足），则返回空指针(NULL)。

11七月2024(2)calloc函数其函数原型为void*calloc（unsignedｎ，unsignedsize）;其作用是在内存的动态存储区中分配ｎ个长度为size的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功，返回NULL。用calloc函数可以为一维数组开辟动态存储空间，n为数组元素个数，每个元素长度为size11七月2024(3)free函数其函数原型为voidfree（void*p）;其作用是释放由ｐ指向的内存区，使这部分内存区能被其他变量使用。ｐ是最近一次调用calloc或malloc函数时返回的值。free函数无返回值.

11七月2024第29页void

setnull(sequenlist*L)

{//构造一个空的线性表

}//InitList_Sqintlength(sequenlistL){returnL.last;}L->last=0;11七月2024第30页线性表的基本操作在顺序表中的实现Locate(L,x)//查找11七月2024第31页例如：顺序表的查找操作23754138546217L.dataL.lastMAXSIZEx=38pppppi12341850p可见，基本操作是：将顺序表中的元素逐个和给定值x相比较。11七月2024第32页

intlocate(sequenlistL,elemtypex){

//

在顺序表中查询第一个满足判定条件的数据元素，

//若存在，则返回它的位序，否则返回0}

O(ListLength(L))算法的时间复杂度为：inti=1;//i的初值为第1元素的位序while

(i<=L.last&&(L.data[i]!=x))++i;if(i<=L.last)returni;elsereturn0;11七月2024第33页线性表操作insert(L,i,x)的实现：首先分析:插入元素时，线性表的逻辑结构发生什么变化？11七月2024第34页

(a1,…,ai-1,ai,…,an)改变为

(a1,…,ai-1,x,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aixan<ai-1,ai><ai-1,e>,<e,ai>表的长度增加11七月2024第35页算法的思想进行合法性检查（i）检查线性表是否已满讲第n个至第i个元素逐一后移一个单位在第i个位置上插入表的长度+111七月2024插入运算的算法描述

voidinsert(sequenlist*L;elemtypex;inti){intj;if((i<1)||i>(L->last+1))printf(“插入位置不正确\n”);elseif(L->last>=MAXSIZE)printf(“表已满，发生上溢\n”);else{for(j=L->last;j>=i;j--)L->data[j+1]=L->data[j];L->data[i]=x;L->last=L->last+1;}}/*insert*/11七月2024第37页考虑插入算法的时间复杂度:11七月2024第38页线性表操作

delete(&L,i)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？11七月2024第39页

(a1,…,ai-1,ai,ai+1,…,an)改变为

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

11七月2024第40页算法的思想进行合法性检查，i是否满足要求判定线性表是否为空将第i+1至第n个元素逐一往前移动一个位置将表的长度减少111七月2024删除运算的算法描述

voiddelete(sequenlist*L，inti){intj;if((i<1)||(i>L->last))printf(“删除位置不正确\n”);else{for(j=i+1;j<=L->last;j++)L->data[j-1]=L->data[j];L->last=L->last-1;}}/*delete*/11七月2024第42页考虑删除算法的时间复杂度:11七月2024举例—删除顺序表中的重复元素一个顺序表中可能含有一些值相同的重复元素，题目要求对于值相同的重复元素只保留位序最小的一个而删除其它多余的元素。如（5，2，2，3，5，2）经删除重复元素后变为（5，2，3）

11七月2024删除顺序表中的重复元素的算法描述

voidPurge(L)sequenlist*L;{inti,j,k;i=1;while(i<L->last){j=i+1;while(j<=L->last)if(L->data[j]==L->data[i]){for(k=j+1;k<=L->last;k++)L->data[k-1]=L->data[k];L->last=L->last-1;}elsej++;

i++;}}/*Purge*/11七月2024举例—有序表的合并顺序表A和B的元素均按由小到大的升序排列，编写算法将它们合并成为顺序表C，要求C中元素也是从小到大的升序排列。算法思路：依次扫描A和B中元素，比较当前两个元素值，将较小的元素赋给C，直到其中一个顺序表扫描完毕，然后将另一个顺序表中剩余元素赋给C即可。

11七月2024有序表的合并的算法描述

voidmerge(C,A,B)sequenlist*C,*A,*B;{inti,j,k;i=1;j=1;k=1;while(i<=A->last&&j<=B->last)if(A->data[i]<B->data[j])C->data[k++]=A->data[i++];elseC->data[k++]=B->data[j++];While(i<A->last)C->data[k++]=A->data[i++];While(j<B->last)C->data[k++]=B->data[j++];C->last=k-1;}/*merge*/11七月2024第47页线性表类型的实现---链式映象11七月2024第48页

用一组地址任意的存储单元存放线性表中的数据元素。一、单链表以数据域(数据元素的信息)

+指针(指示后继元素存储位置)=结点以“结点的序列”表示线性表

称作链表11七月2024第49页

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。

a1a2…...an^头指针空指针11七月2024第50页

typedefstructnode{elemtypedata;//数据域

structnode*next;//指针域

}

LinkList;

二、结点和单链表的C语言描述LinkList*H,*P；//H,P为单链表的头指针11七月2024第51页头结点

a1a2…...an^头指针头指针

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空

11七月2024第52页1.元素的查找按序号查找11七月2024第53页L

线性表的操作

GetLinkList(L,i)在单链表中的实现(找到第3个元素):211830754256∧pppj12311七月2024第54页

因此，查找第i个数据元素的基本操作为：移动指针，比较j和i。

单链表不是一种顺序存取的结构，为找第i个数据元素，必须先找到第i-1个数据元素。

令指针p

始终指向线性表中第j

个数据元素。11七月2024

LinkList*getLinkList(LinkList*L，inti){LinkList*P;intj=0;P=L;while((j<i)&&(P->next!=NULL)){P=P->next;j++;}if(j==i)returnP;elsereturnNULL;}11七月2024elemtypeGetLinkList(LinkList*L，inti){LinkList*P;intj=0;P=L;while((j<i)&&(P->next!=NULL)){P=P->next;j++;}if(j==i)returnP->data;elsereturn0;}11七月2024

intGetLinkList(LinkList*L，inti,elemtype*e){LinkList*P;intj=0;P=L;while((j<i)&&(P->next!=NULL)){P=P->next;j++;}if(j==i){*e=P->data;return1;}elsereturn0;}11七月2024第58页p=L;j=0;//p指向头结点，j为计数器while(j<i&&p->next!=NULL){p=p->next;++j;}这两种情况有六种组合1.p->next=NULL且j<i空表且i>0或者i>表长，异常2.p->next=NULL且j=i空表且i=0或者i=表长3.p->next=NULL且j>i空表且i<0，异常出循环4.p->next

!=NULL且j<i继续循环5.p->next

!=NULL且j=i确定第i个结点正常出循环6.p->next!

=NULL且j>i异常出循环11七月2024第59页1.元素的查找按值查找L211830754256∧pLocateLinkList(L,x)

11七月2024LinkList*LocateLinkList(LinkList*L，elemtypex){LinkList*P;P=L->next;while((P!=NULL)&&(P->data!=x))P=P->next;returnP;/*返回找到的结点位置或NULL*/}如果要返回位序，程序怎么修改11七月2024第61页2.插入操作11七月2024第62页ai-1

线性表的操作

insertLinkList(L,x,i)在单链表中的实现：

有序对<ai-1,ai>

改变为<ai-1,x>和<x,ai>xaiai-111七月2024第63页s->data=e;s->next=p->next;p->next=s;//插入eai-1aiai-1sp11七月2024第64页

因此，在单链表中第i个结点之前进行插入的基本操作为:

找到线性表中第i-1个结点，然后修改其指向后继的指针。

可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。11七月2024插入算法描述voidinsertLinkList(LinkList*L,elemtypex,inti){LinkList*P,*S;P=getLinkList(L,i-1);/*查找第i-1个结点*/if(P==NULL)Printf(“第i-1个元素不存在，参数i有错\n”);else{S=(LinkList*)malloc(sizeof(LinkList));S->data=x;S->next=P->next;P->next=S;}}11七月2024第66页intinsertLinkList(LinkList*L,ElemTypee,inti)

{

}……LinkList*p=L;intj=0;while(p&&j<i-1)

{p=p->next;++j;}

//

寻找第i-1个结点if(!p||j>i-1)

return0;//

i大于表长或者小于111七月2024第67页s=(LinkList*)malloc(sizeof(node));

//生成新结点s->data=e;s->next=p->next;p->next=s;//插入return1;eai-1aiai-1sp11七月2024第68页循环条件的分析第一次循环p!=NULL,j有三种可能1.j<i-1继续循环2.j=i-1,此时i=1，在第一个元素插入3.j>i-1i<1不合法1.p=!NULL且j<i-1继续循环2.p=!NULL且j=i-1已经定位正常出循环3.p=NULL且j<=i-1i不合法(i>=表长+2），出循环第二次循环后，p有可能NULL,但是j>i-1不可能，出现的各种可能情况：11七月2024第69页3.删除操作11七月2024第70页线性表的操作deleteLinkList(L,i)在链表中的实现:有序对<ai-1,ai>和<ai,ai+1>

改变为<ai-1,ai+1>ai-1aiai+1ai-111七月2024第71页

在单链表中删除第

i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq11七月2024删除单链表L中的第i个结点算法

voiddeleteLinkList(LinkList*L,inti){LinkList*P,*S;P=getLinkList(L,i-1);/*查找第i-1个结点*/if(P==NULL)Printf(“第i-1个元素不存在，参数i有错\n”);else{S=P->next;P->next=S->next;free(S);}}11七月2024第73页intdeleteLinkList(LinkList*L,inti,ElemType&e){}

LinkList*p=L;intj=0;while(p->next!=NULL&&j<i-1){p=p->next;//寻找第i个结点，并令p指向其前趋

++j;

}

if(!(p->next)||j>i-1)

return0;//删除位置不合理q=p->next;p->next=q->next;

//删除并释放结点e=q->data;free(q);return1;11七月2024第74页删除算法讨论：删除范围为[1,表长]，不能删除头结点出循环的五种可能情况：p->next=NULL且j<i-1空表或i>表长p->next=NULL且j=i-1空表且i=1，或i=表长+1p->next=NULL且j>i-1空表且i<1p->next!=NULL且j=i-1非空表且定位p->next!=NULL且j>i-1非空表且i<111七月20244.求表长只要设一个移动指针扫描整个单链表，就可以统计出元素个数即表长。其算法描述如下：

intLengthLinkList(LinkList*L){LinkList*P=L;intj=0;While(P->next!=NULL){P=P->next;j++;}returnj;/*返回表长*/}该算法扫描整个单链表，时间复杂度为O(n)。

11七月2024第76页5.建立单链表11七月2024第77页如何从得到单链表？链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。11七月2024第78页例如：逆位序输入n个数据元素的值，建立带头结点的单链表。(头插法)操作步骤：一、建立一个“空表”；二、输入数据元素an，建立结点并插入；三、输入数据元素an-1，建立结点并插入；ananan-1四、依次类推，直至输入a1为止。11七月2024第79页adcbi=0i=1i=2i=3∧head采用头插法建立单链表的过程heada∧headda∧headcda∧headbcda∧第1步:建头结点第2步:i＝0,新建a结点,插入到头结点之后第3步:i＝1,新建d结点,插入到头结点之后第4步:i＝2,新建c结点,插入到头结点之后第5步:i＝3,新建b结点,插入到头结点之后11七月2024第80页voidCreateList(LinkList*&L,intn){//逆序输入n个数据元素，建立带头结点的单链表}算法的时间复杂度为:O(Listlength(L))L=(LinkList*)malloc(sizeof(node));L->next=NULL;

//先建立一个带头结点的单链表for(i=n;i>0;--i){p=(LinkList*)malloc(sizeof(node));

scanf(“%d”,&p->data);//输入元素值

p->next=L->next;L->next=p;//插入}11七月2024第81页正序插法11七月2024具体的算法描述如下：LinkList*CreateLinkList(){charch;intx;LinkList*head;LinkList*r,*P;head=(LinkList*)malloc(sizeof(LinkList));head->next=NULL;

r=head;/*尾指针初始化*/ch=getchar();while(ch!=’*’)//“*”为输入数据结束符号*/{scanf(“%d”,&x);P=(LinkList*)malloc(sizeof(LinkList));P->data=x;P->next=NULL;r->next=P;r=r->next;ch=getchar();}returnhead;}11七月2024单链表建立过程示例线性表（25，45，18，76，29）的单链表动态建立过程如下图：11七月2024第84页LinkList*CreateList(intn){/*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/ inti; LinkList*L; LinkList*p,*r; L=(LinkList*)malloc(sizeof(LinkList));/*生成头结点*/ L->next=NULL; r=L; printf("请输入%d个数据\n",n); for(i=1;i<=n;i++) { p=(LinkList*)malloc(sizeof(LinkList));

scanf("%d",&p->data); p->next=NULL; r->next=p; r=p; } returnL}11七月2024第85页归并两个有序表Lb26891115∧La35811∧11七月2024第86页LinkList*MergeList(LinkList*&La,LinkList*&Lb)pa=La->next;pb=Lb->next;Lc=pc=La;While(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;}}if(pa)pc->next=pa;elsepc->next=pb;

free(Lb);returnLc}

。11七月2024第87页

例设C={a1,b1,a2,b2,…,an,bn}为一线性表,采用带头结点的hc单链表存放,编写一个算法,将其拆分为两个线性表,使得:A={a1,a2,…,an},B={b1,b2,…,bn}

解:设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点*ha和*hb,它们用于存放拆分后的线性表A和B,ra和rb分别指向这两个单链表的表尾。 用p指针扫描单链表hc,将当前结点*p链到ha未尾,p沿next域下移一个结点,若不为空,则当前结点*p链到hb未尾,p沿next域下移一个结点,如此这样,直到p为空。最后将两个尾结点的next域置空。11七月2024第88页

voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb;ha=hc;

/*ha的头结点利用hc的头结点*/

ra=ha;

/*ra始终指向ha的末尾结点*/

hb=(LinkList*)malloc(sizeof(LinkList));

/*创建hb头结点*/

rb=hb;

/*rb始终指向hb的末尾结点*/

本算法实际上是采用尾插法建立两个新表。所以,尾插法建表算法是很多类似习题的基础！11七月2024第89页

while(p!=NULL){ra->next=p; ra=p;/*将*p链到ha单链表未尾*/p=p->next;if(p!=NULL){rb->next=p;rb=p; /*将*p链到hb单链表未尾*/p=p->next;}}ra->next=rb->next=NULL;/*两个尾结点的next域置空*/}11七月2024举例——将单链表H逆置所谓逆置是指结点间的关系相反，即前趋变后继而后继变前趋。如图(a)的单链表逆置后成为图(b)的单链表。算法思路：依次从原链表中取出每个结点，每次都把它作为第一个结点插入到新链表中去。为此要借用两个指针变量P和q，P用来指向原链表中的当前第一个结点，q用来指向从原表取出的每一个结点并利用它插入到新链表中去，当P为空时完成逆置。

11七月2024将单链表H逆置的算法描述

voidreverse(H)LinkList*H;{LinkList*P,*q;P=H->next;H->next=NULL;while(P!=NULL){q=P;P=P->next;q->next=H->next;H->next=q;}}*reverse*/该算法没有开辟新的存储空间，对链表顺序扫描一遍就完成了逆置，时间开销为O(n)。11七月2024第92页作业：1.给定一个单链表L，编写一个删除L中值为x的结点的直接前驱结点算法。2.有一个单链表（不同的结点的数据域值可能相同），其头指针为head,编写一个函数计算数据域为x的结点个数。11七月2024第93页作业2：1.给定一个单链表L，编写一个删除L中值为x的结点的算法。2.设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。11七月2024第94页优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充顺序存储结构的优缺点11七月2024第95页单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢11七月2024第96页循环链表是表中最后一个结点的指针指向头结点，使链表构成环状h空表循环链表(circularlinkedlist)特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->next==NULL循环链表p或p->next==Hh…11七月2024第97页r空表设置尾指针的循环链表设置尾指针的循环链表，在对两个单循环链表进行连接使可以提高效率。r2b1bnr1a1anr1->next=r2->next->next;r2->next=p;r…pp=r1->next;11七月2024第98页单链表具有单向性的缺点，找前驱不方便！结点定义typedefstructdupnode{elemtypedata;structdupnode*prior,*next;}duplinklist;priordatanextL空双向循环链表：非空双向循环链表：LABbcapp->prior->next=p=p->next->proir;双向链表（doublelinkedlist）11七月2024第99页双向链表的操作特点：“查询”和单链表相同。“插入”和“删除”时需要同时修改两个方向上的指针。11七月2024第100页voidins_dlinklist(duplinklist*p,intx){duplinklist*s;s=(duplinklist*)malloc(sizeof(duplinklist));s->data=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法评价：T(n)=O(1)xSbaP插入p->prior->next=s;s->prior=p->prior;s->next=p;p->prior=s;11七月2024第101页ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入11七月2024第102页bcaPvoiddel_dlinklist(duplinklist*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}删除算法描述算法评价：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;11七月2024第103页ai-1删除aiai+1p->next=p->next->next;p->next->prior=p;pai-111七月2024第104页用上述定义的单链表实现线性表的操作时，存在的问题：

改进链表的设置

1．单链表的表长是一个隐含的值；

1．增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；2．在单链表的最后一个元素之后插入元素时，需遍历整个链表；3．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。2．将基本操作中的“位序i”改变为“指针p”。11七月2024第105页一个带头结点的线性链表类型typedefstructnode{//结点类型

ElemTypedata;

structnode*next;}Link;typedefstruct

{//链表类型

Link*head,*tail;