数据结构线性表

第一节线性表的概念及逻辑结构第二章线性表2线性表是N个数据元素的有限序列构成的一种线性结构。线性表的形式定义：

Linear--List=（D，R）

D={a1，a2，……an} R={〈ａi-1，ai〉│i=2..n}n称为线性表长度，n=0称空表；

ai为数据元素。3线性表还可以逻辑地表示为：（a1，a2，……an）线性表的特点：唯一首元素；唯一尾元素；除首元素外，任何元素有一个前驱；除尾元素外，任何元素有一个后继；每个元素有一位序。第二节线性表的

抽象类型定义5数据对象：D数据关系：R基本操作：Initlist（&L)Destroylist（&L)Clearlist（&L)Listempty（L)Listlength（L)Getelem(L,i,&e)Locatelem(L,e)Priorelem(L,e,&pe)Nextelem(L,e,&ne)Listinset(&L,i,e)Listdelete(&L,i,&e)Listtraverse(L)ADTList{}ADTList第三节线性表的

顺序表示和实现7一顺序表示用一组连续的存储单元依次存储线性表的数据元素。

设b为首地址

L为数据元素长度a1a2an空闲bb+Lb+（n-1）Lb+（maxlen-1）L8二线性表的顺序结构实现 线性表由三个部分组成：1）一组连续存储空间2）当前长度3）空间大小

用c语言可描述为：elem[]lengthlistsize9#defineList-Init-Size100#defineListincrement10typedefstruct{ Elemtype*elem； int length； int listsize；}Sqlist；10初始化一个线性表StatusInitlist_Sq(Sqlist&L){L.elem=分配List-Init-Size个空间;L.length=0;L.listsize=List-Init-Size;returnOK;}11线性表插入前后状况7742302428211312插入25774230282425211312下移一格三

插入操作的算法实现12StatusListinsert_Sq(Sqlist&L,inti,Elemtypee){if(i<1‖i>L.length+1)returnERROR;if(L.length>=L.listsize){newbase=追加分配新空间

L.elem=newbase;L.listsize+=Listincrement;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}13线性表删除前后状况7742302428211312删除2477422830211312上移一格四删除操作的算法实现14StatusListdelete_Sq(Sqlist&L,inti,Elemtype&e){if(i<1‖i>L.length)returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}15五算法分析

设在线性表第i个元素前插入一新元素的概率为Pi，删除第i个元素的概率为Qi，元素移动为算法的基本操作。则插入和删除的平均移动期望值为：

Ei=Pi（n-i+1）Ed=Qi（n-i）

等概率下：

Ei=n/2Ed=（n-1）/2n+1∑i=1n∑i=1第四节线性表的

链式表示和实现17一逻辑表示a1a2^anL头结点元素结点尾结点结点：数据域指针域空链表：^L18二存储结构线性表的单链表存储结构：typedefstructLnode{Elemtypedata；structLnode*next；}Lnode，*Linklist；19三基本操作实现1）取链表中第i个元素

StatusGetelem_L(LinklistL,inti,Elemtype&e){p=L->next;j=1;while(p&&j<i){p=p->next;++j}if(!p‖j>i)returnERROR;e=p->data;returnOK;}202）在P所指结点之后插入新结点PabxSPabxSS-〉next=P-〉next；P-〉next=S21

StatusListinsert_L(Linklist&L,inti,Elemtypee){p=L;j=0;while(p&&j<i-1){p=p->next;++j}if(!p‖j>i-1)returnERROR;new(s);s->data=e;s->next=p->next;p->next=s;returnOK;}223）删除P所指结点之后的结点PabcP-＞next=P-＞next-＞next23

StatusListdelete_L(Linklist&L,inti,Elemtype&e){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j}if(!(p->next)‖j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}24四应用举例有序表的合并a1a2^anLab1b2^bnLbc1c2^cnLcPc**C语言算法实现参见下页25voidMergelist_L(Linklist&La,Linklist&Lb,Linklist&Lc){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;}}pc->next=pa?pa:pb;free(Lb);}第四节

循环链表27a1a2anL1单循环链表单循环空链表L282双向链表双向空链表La1a2anL29后指针数据前指针双向链表结点结构typedefstructDublnode{ Elemtypedata; structDublnode*prior； structDublnode*next；}Dublnode,*Dublinklist；双向链表结点的存储结构定义303双向链表插入一新结点abxPS①②③④s-＞prior=p-＞prior；p-＞prior-＞next=s；s-＞next=p；p-＞prior=s；314双向链表删除一结点a2a2a2P①②①

p-＞prior-＞next=p-＞next；②p