数据结构线性表及其基本算法

数据结构线性表及其基本算法教学目标线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。教学重点与难点本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析；难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。教学方法课堂讲授提问互动实验定义:线性表（linearlist）（a1，a2，…，an

）其中:n：数据元素的个数或线性表的长度；ai：

是一个抽象的符号，它的数据类型设定为ElemType，表示某一种具体的已知数据类型（1≤i≤n）。2.1线性表的类型定义非空线性表的特征（P18）有且仅有一个开始结点(表头结点head)a1，它没有直接前驱，只有一个直接后继;

有且仅有一个终端结点(表尾结点tail)an，它没有直接后继，只有一个直接前驱;

其它结点都有一个直接前驱和直接后继；元素之间为一对一的线性关系。线性表的抽象数据类型定义（P18

）

ADTList{

数据对象：D={ai|ai∈ElemSet;1≤i≤n,n≥0;}

数据关系：R={<ai,ai+1>|ai,ai+1∈D,i=1,2,……,n-1}

基本操作：

InitList(&L) ListLength(L) GetElem(L,i,&e) PriorElem(L,cur_e,&pre_e) NextElem(L,cur_e,&next_e) LocateElem(L,e,compare()) ListInsert(&L,i,e) ListDelete(&L,i,&e) }ADTList算法2.1（线性表的首尾合并）voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}//union算法分析：

设LocateElem的执行时间与表长成正比，即：算法的时间复杂度为：O(ListLength(La)*ListLength(Lb))s->prior=p->prior;p->prior->next=s;typedefstructpnode{elem)exit（OVERFLOW）;①将结点s插入在指针p所指结点的直接后继位置的语句是_____________；typedefstructDuLNode{typedefstructLNode{else{q=bt->next;bt->next=at;ct->next=bt;if(p==L||j>i)returnERROR;③删除指针p所指结点的直接后继结点的语句序列是__________________；p=p->next;while(pa<=pa_last)*pc++=*pa++;当i=n+1时，不需移动元素，插入新结点 （算法）(7)已带表头结点的单链表L，指针p指向L链表中的一个结点，指针q是指向L链表外的一个结点，则：Lc=pc=La;算法2.2（有序线性表的合并）voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_Len=ListLength(La);Lb_Len=ListLength(Lb);while((i<=La_Len)&&(j<=Lb_Len){ GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai<=bj){ListInsert(Lc,++k,ai);++i;} else{ListInsert(Lc,++k,bj);++j;}}while(i<=La_len){ GetElem(La,i++;ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){ GetElem(Lb,j++;bj);ListInsert(Lc,++k,bj);}}//MergeListelem)exit（OVERFLOW）;假设在每个位置插入的概率为pi（不妨设为等概率），则平均移动元素的次数为：p=p->next;②将结点s插入在指针p所指结点的直接前驱位置的语句是___________；x=at->coef+bt->coef);理解两类存储结构（顺序和链式存储结构）的描述方法，以及单链表、循环链表、双向链表的特点；(3)指针p指向双向循环链表的尾结点的条件是：循环链表的操作与单链表的操作类似，差别如下：length&&!(*compare)(*p++,e)++i;(1)下列说法正确的是：for(i=1;i<=Lb_len;i++){if(!pc)returnOVERFLOW;typedefstructDuLNode{会用单链表编写查找、插入、删除、合并等的有关算，并学会何时选用何种链表的方法；elsereturn0;2.2线性表的顺序存储结构一、特点用一组地址连续的存储单元依次存放线性表中的元素；以元素在机内的“物理位置相邻”来表示数据之间的逻辑关系: LOC(ai+1)＝LOC(ai)＋L是一种随机存取的存储结构;

LOC(ai)＝LOC(a1)＋(i－1)*L插入／删除时需移动大量元素;a1a2……aiai+1……anLOC(a1)LOC(ai)LOC(ai+1)2.2线性表的顺序存储结构二、描述方式

#defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 typedefstruct{ ElemType*elem; intlength; intlistsize; }SqList2.2线性表的顺序存储结构三、基本操作的算法描述初始化顺序表 （算法）插入元素 （算法）删除元素 （算法）元素的查找 （算法）顺序表的合并 （算法）算法2.3（初始化顺序表）StatusInitList_Sq(SqList&L){ L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)) if(!L.elem)exit（OVERFLOW）; L.length=0; L.listsize=LIST_INIT_SIZE; returnOK;}//InitList_Sq算法2.4：顺序表中插入一个元素StatusListInsert_Sq(SqList&L,inti,ElemTypee){ if(i<1||i>L.length+1)returnERROR; if(L.length>=L.listsize){ newbase=(ElemType*) realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMET;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p))*(p+1)=*p;*q=e;++L.length;returnOK;}//ListInsert_Sqfor(j=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j]a1a2aiai+1an01i-1i下标a1a2aian-1ane插入算法的时间复杂度分析插入算法花费的时间，主要在于循环中元素的向后移动上面，而元素的移动次数与插入的位置i有关：(设L.length=n)当i=1时，全部元素都得移动，需n次移动，当i=n+1时，不需移动元素，一般地：在i位置插入时移动次数ci为n-i+1，假设在每个位置插入的概率为pi（不妨设为等概率），则平均移动元素的次数为：

故时间复杂度为O(n)。

算法2.5顺序表中删除元素StatusListDelete_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; }//ListDelete_Sq

e=L.elem[i-1];For(j=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j]；删除算法的时间复杂度分析删除算法花费的时间，主要在于循环中元素的前移上，而元素的移动次数与删除的位置i有关：(设L.length=n)当i=1时，其后的全部元素都得移动，需n-1次移动，当i=n时，不需移动元素，一般地：在i位置删除元素时的移动次数ci为n-i假设在每个位置删除的概率为pi（不妨设为等概率），则平均移动元素的次数为：故时间复杂度为O(n)。算法2.6顺序表中元素的查找intLocateElem_Sq(SqlistL,ElemTypee,status(*compare))(ElemType,ElemType)){ i=1; p=L.elem; while(i<L.length&&!(*compare)(*p++,e)++i; if(i<=L.length)returni;elsereturn0;}//ListDelete_Sq注：设L.length=n，则T(n)=O(n)算法2.6-1顺序表中元素的查找intLocateElem_Sq(SqlistL,ElemTypee){i=0; while(i<L.length&&L.elem[i]!=e)++i; if(i<L.length)returni+1;elsereturn0;}//ListDelete_Sq注：设L.length=n，则T(n)=O(n)

算法2.7顺序表的合并StatusMergeList_Sq(SqlistLa,SqlistLb,Sqlist&Lc){ pa=La.elem;pb=Lb.elem; Lc.ListSize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*) malloc(Lc.ListSize*sizeof(ElemType)); if(!pc)returnOVERFLOW; pa_last=pa+La.length-1;pb_last=pb+Lb.length-1; while((pa<=pa_last)&&(pb<=pb_last) if(*pa<=*pb)*pc++=*pa++; else*pc++=*pb++;while(pa<=pa_last)*pc++=*pa++; while(pb<=pb_last)*pc++=*pb++;}顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，空间利用不充分。160H2.3线性表的链式存储结构先看一个例子：线性表(a1,a2,a3,a4,a5,a6,a7,a8)指针域200190150210260110NULL240头指针存储地址数据域110a5150a2160a1190a3200a6210a4240a8260a7示意图：an∧a1a2a3HHNULLL∧an∧a1a2L元素的查找 （算法）学会从时间和空间复杂角度比较线性表的不同特点极其使用场合。(1)下列说法正确的是：if(x){at->coef=x;ct=at;}pnode*at,*bt,*ct,*q;if((i<1)||(i>L.最后一个结点的判定条件:p->next=Lintlength;4：顺序表中插入一个元素j++;while(p!=L&&j<i){利用链表设计算法解决简单应用问题。}//unionif(!newbase)exit(OVERFLOW);当i=n+1时，不需移动元素，2.3线性表的链式存储结构线性表的链式存贮结构及特点用一组任意的存储单元存放线性表中的各元素;数据之间的逻辑关系由结点中的指针指示;是一种非随机存取(顺序存取)的存储结构;插入／删除时无需移动大量元素。常用的链表有：单链表 循环链表双向链表多重链表2.3.1线性链表（单链表）

在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。结点结构与定义：datanext

线性链表示意图∧a1a2a3HtypedefstructLNode{ ElemTypedata; structLNode*next;}LNode,*LinkList;an∧a1a2L2.3.1线性链表（单链表）单链表的基本算法：读取元素 （算法）插入新结点 （算法）删除结点 （算法）链表的创建 （算法）有序链表的合并 （算法）

2.3.1线性链表（单链表）算法（取元素）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;}

注意：循环控制条件及异常处理算法的时间复杂度：O(n)算法（插入元素）

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;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returnOK;}xsbap2.3.1线性链表（单链表）bap算法的时间复杂度为0(n)。2.3.1线性链表（单链表）算法（删除元素）

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;}2.3.1线性链表（单链表）算法（头插法建立单链表）

voidCreateListe_L_1(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;L->next=p;}}2.3.1线性链表（单链表）算法（尾插法建立单链表）

voidCreateListe_L_2(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;q=L;for(i=1;i<=n;i++){p=(LinkList)malloc(sizeof(LNode));scanf(&p->data);q->next=p;q=p;}q->next=NULL;}2.3.1线性链表（单链表）

算法（有序链表的合并）voidMergeListe_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;}}//whilepc->next=pa?pa:pb;free(Lb);}2.3.2单循环链表Lan

a1a2

循环链表的操作与单链表的操作类似，差别如下：链表的判空条件：L->next=L最后一个结点的判定条件:p->next=L可以设立尾指针单循环链表示意图2.3.3双向链表概念引入结点结构与定义priordatanexttypedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList双向链表示意图L

a2

a3a1

an^

^L

a2

a3a1

an算法（双向循环链表中插入元素）StatusListInsett_DuL(DuLinkList&L,inti,ElemTypee){p=L->next;j=1;while(p!=L&&j<i){p=p->next;j++;}if(p==L||j>i)returnERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}//ListInsert_Dul算法（双向循环链表中删除元素）StatusListDelete_DuL(DuLinkList&L,inti,ElemTypee){p=L->next;j=1;while(p!=L&&j<i){p=p->next;j++;}if(p==L||j>i)returnERROR;e=p->data;p->prior->next=p->next;p-->next->prior=p->prior;free(p);returnOK;}//ListDelete具体要求顺序表链表基于空间适于线性表长度变化不大，易于事先确定其大小时采用。适于当线性表长度变化大，难以估计其存储规模时采用。基于时间由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。线性表的两种存储结构的比较2.4线性表的应用举例高级语言中的数组；计算机的文件系统；计算机的目录系统；号码查询系统（可采用顺序表或单链表结构）；各种事务处理（各种表格均采用顺序表和线性链表结构）一元多项式的表示和相加例：一元多项式的表示和相加情况一：Pn(x)=p0+p1x+p2x2+……+pnxnQn(x)=q0+q1x+q2x2+……+qnxmRn(x)=(p0+

q0)+(p1+

q1)

x+(p2+

q2)

x2+……+(pn+

qn)xn+qn+1xn+1+……+qmxm可以表示为：P=（p0，p1，p2，…，pn）Q=（q0，q1，q2，…，qm）R=((p0+

q0，(p1+

q1)，(p2+

q2)

，…，(pn+

qn)，qn+1，…，qm）)存储结构选择及运算实现

情况二：Pn(x)=p1xe1+p2xe2+……+pnxenQn(x)=q1xt1+q2xt2+……+qmxtm可以表示为：P=（(p1，e1)，(p2，e2)，…，(pn，en)）Q=（(q1，t1)，(q2，t2)，…，(qm，tm)）存储结构选择及运算实现typedefstructpnode{realcoef;intexp;structpnode*next;}*polyn一元多项式的相加Ploynpolynadd(polypa,polypb){pnode*at,*bt,*ct,*q;ct=pc=pa;at=pa->next;bt=pb->next;while(at&&bt){if(at->exp<bt->exp){ct=at;at=at->next;}elseif(at->exp==bt->exp){x=at->coef+bt->coef);if(x){at->coef=x;ct=at;}else{ct=at->next;free(at);}at=ct->next;q=bt;bt=bt->next;free(q);}else{q=bt->next;bt->next=at;ct->next=bt;ct=ct->next;bt=q;}}/*while*/if(bt)ct->next=bt;free(bt);returnpa;}本章小结了解线性表的定义和线性结构的特点。理解两类存储结构（顺序和链式存储结构）的描述方法，以及单链表、循环链表、双向链表的特点；掌握线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析；会用单链表编写查找、插入、删除、合并等的有关算，并学会何时选用何种链表的方法；学会从时间和空间复杂角度比较线性表的不同特点极其使用场合。习题一、填空题(1)链表中逻辑上相邻的元素的物理位置____________相连。(2)在单链表中除首结点外，任意结点的存储位置都由__________结点中的指针指示。(3)在单链表中，设置头结点的作用是在插入或删除首结点时不必对____________进行处理。(4)线性表的存储结构有顺序存储和____________存储两种。(5)线性表的元素长度为4，在顺序存储结构下LOC(ai)＝2000，则LOC(ai+1)＝____。(