線性表的類型定義、順序表示和實現(xiàn)課件

第2章線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)第2章線性表2.1線性表的類型定義1線性表是一種最簡單的線性結構。什么是線性結構？簡單地說，線性結構是一個數(shù)據(jù)元素的有序（次序）集合。它有四個基本特征：在數(shù)據(jù)元素的非空有限集中，①存在惟一的一個被稱做"第一個"的數(shù)據(jù)元素；②存在惟一的一個被稱做"最后一個"的數(shù)據(jù)元素；③除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅；④除最后一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼。這里的"有序"僅指在數(shù)據(jù)元素之間存在一個"領先"或"落后"的次序關系，而非指數(shù)據(jù)元素"值"的大小可比性。比較典型的線性結構：線性表、棧、隊列、串等。線性表是一種最簡單的線性結構。22.1線性表的類型定義

2.1.1線性表的定義線性表(linear_list)是n個數(shù)據(jù)元素的有限序列，記作（a1,a2,…,ai,…,an）。線性表的數(shù)學模型（形式定義）：含有n個數(shù)據(jù)元素的線性表是一個數(shù)據(jù)結構LinearList=（A,R）其中：A={ai|ai∈ElemType,1≤i≤n,n≥0}R={r}r=｛<ai,ai+1>|1≤i≤n-1}2.1線性表的類型定義

2.1.1線性表的定義線性表(l3說明：①線性表的數(shù)據(jù)元素可以是各種類型（整、實、記錄類型等）typedefintElemType;typedefcharElemType;等；②同一線性表中的數(shù)據(jù)元素必須具有相同的特性，屬同一類型；③關系r是一個有序偶對的集合，即對于非空的線性表（a1,a2,…,ai-1,ai,ai+1,…,an），ai-1領先于ai，表示了數(shù)據(jù)元素之間的相鄰關系，稱ai-1是ai的直接前驅，ai是ai-1的直接后繼；④序列中數(shù)據(jù)元素的個數(shù)n定義為線性表的表長，n=0時的線性表被稱為空表；⑤稱i為數(shù)據(jù)元素在線性表中的位序。說明：①線性表的數(shù)據(jù)元素可以是各種類型（整、實、記錄類型等）42.1.2線性表的抽象數(shù)據(jù)類型ADTLinearList{ Data: 一個線性表L定義為L=(a1,a2,…,an)，當L=（）時定義為一個空表。 Operation: boolinitList(&L);//初始化線性表L，即把它設置為一個空表 voidclearList(&L);//將L重置為空表 intgetSize(L);//返回L中數(shù)據(jù)元素的個數(shù) boolisEmpty(L); //判斷L是否為空，若空則返回true，否則返回false voidtraverList(L,visit()); //遍歷線性表L，依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit() ElemType&getElem(L,pos); //返回線性表第pos個數(shù)據(jù)元素的值2.1.2線性表的抽象數(shù)據(jù)類型ADTLinearList5 intlocateElem(&L,e,compare()); //返回L中第1個與e滿足關系compare()的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在，則返回0 boolinsertElem(&L,e,pos); //在L的pos位置插入e，線性表L長度加1 booldeleteElem(&L,pos); //刪除L的第pos個數(shù)據(jù)元素 boolcreateList(&L,n,visit()); //創(chuàng)建有n個元素的線性表} intlocateElem(&L,e,compare(62.1.3操作舉例例：假設利用兩個線性表La和Lb分別表示兩個集合A和B，求一個新的集合A=A∪B。算法：①取得Lb中的1個元素；②在La中查找這個元素；③若不存在：插入La中；若存在，取Lb中下一個元素，重復①、②、③，直到取完Lb的每個元素。2.1.3操作舉例例：假設利用兩個線性表La和Lb分別表示7voidunionList(SqList&la,SqListlb){intlbSize=getSize(lb);ElemTypee;for(inti=1;i<=lbSize;++i){e=getElem(lb,i);if(!locateElem(la,e,equal))insertElem(la,e,la.size+1);}}intequal(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;return0;}算法的時間復雜度為O(La.size×Lb.size)。voidunionList(SqList&la,SqLi82.2線性表的順序表示和實現(xiàn)

2.2.1線性表的順序表示線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關系來反映數(shù)據(jù)元素之間邏輯上的相鄰關系。采用順序存儲結構的線性表通常稱為順序表。表示為：A=(a1，a2，…，ai，ai+1，…，an)2.2線性表的順序表示和實現(xiàn)

2.2.1線性表的順序表示9第i個元素的地址假設線性表中有n個元素，每個元素占k個單元，第一個元素的地址為loc(a1)，則可以通過如下公式計算出第i個元素的地址loc(ai)：loc(ai)=loc(a1)+(i-1)×k其中l(wèi)oc(a1)稱為基地址。第i個元素的地址假設線性表中有n個元素，每個元素占k個單元，10線性表的順序存儲結構示意圖順序存儲結構可以借助于高級程序設計語言中的一維數(shù)組來表示。線性表的順序存儲結構示意圖順序存儲結構可以借助于高級程序設計11用C++語言描述的順序表類型如下所示：

sqlist.h#include<iostream>usingnamespacestd;structNode//定義結點（數(shù)據(jù)元素）的類型{ intid; intage;};typedefNodeElemType;//聲明結點的類型名為ElemTypestructSqList//定義線性表的存儲結構{ ElemType*list; intsize; intmaxSize;};用C++語言描述的順序表類型如下所示：

sqlist.h#i12boolinitList(SqList&L,intms);voidclearList(SqList&L);intgetSize(SqListL);boolisEmpty(SqListL);boolisFull(SqListL);voidtraverList(SqListL,void(*visit)(ElemType&));ElemType&getElem(SqListL,intpos);intlocateElem(SqList&L,ElemTypee,int(*compare)(ElemType,ElemType));intfindList(SqListL,ElemTypee);boolinsertElem(SqList&L,ElemTypee,intpos);booldeleteElem(SqList&L,intpos);boolcreateList(SqList&L,intn,void(*visit)(ElemType&));boolinitList(SqList&L,intms132.2.2線性表順序存儲結構上的基本運算

sqlist.cpp⑴初始化線性表①初始化變量，申請空間；②size賦值；maxsize賦值。boolinitList(SqList&L,intms){L.list=newElemType[ms];if(!L.list){cerr<<"Memoryallocationfailure!"<<endl;exit(1);}L.size=0;L.maxSize=ms;returntrue;}2.2.2線性表順序存儲結構上的基本運算

sqlist.c14⑵刪除線性表的所有元素，使之成為空表在順序存儲方式下實現(xiàn)此操作只要將線性表的長度置0即可。voidclearList(SqList&L){L.size=0;}⑶檢查線性表是否為空boolisEmpty(SqListL){returnL.size==0;}⑵刪除線性表的所有元素，使之成為空表15⑷獲取表元素的個數(shù)intgetSize(SqListL){returnL.size;}⑸檢查線性表是否已滿boolisFull(SqListL){returnL.size==L.maxSize;}⑷獲取表元素的個數(shù)16⑹得到線性表中指定序號的元素ElemType&getElem(SqListL,intpos){if(pos<1||pos>L.size){cerr<<"posisoutrange!"<<endl;exit(1);}returnL.list[pos-1];}⑹得到線性表中指定序號的元素17⑺遍歷線性表 遍歷一個線性表就是從線性表的第一個元素起，按照元素之間的邏輯順序，依次訪問每一個元素，并且每個元素只被訪問一次，直到訪問完所有元素為止。voidtraverList(SqListL,void(*visit)(ElemType&)){for(inti=0;i<L.size;++i)visit(L.list[i]);cout<<endl;}如要依次輸出每個元素的值，visit()的實參可定義如下：voidprint(ElemType&e){cout<<"id:"<<e.id<<"age:"<<e.age<<endl;}⑺遍歷線性表18⑻查找線性表中滿足給定條件的元素intlocateElem(SqList&L,ElemTypee,int(*compare)(ElemType,ElemType)){for(inti=0;i<L.size;++i)if(compare(L.list[i],e)==1)returni+1;return0;}如要查找與e的相等（某對應成員的值相等）的元素，則compare()的實參可定義如下：intequal(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;return0;}⑻查找線性表中滿足給定條件的元素19算法的時間復雜度： 時間耗費主要在比較元素的次數(shù)上，而次數(shù)取決于待查找元素的位置。最好情況:compare(L.list[0],e)==1O(1）最壞情況:compare(L.list[n-1],e)==1O(n)平均情況:O(n)算法的時間復雜度：20⑼向線性表中的指定位置插入一個元素原表：a1，a2，…，ai-1，ai，ai+1，…，an插入后的表：a1，a2，…，ai-1，b，ai，ai+1，…，an①ai-1和ai邏輯關系發(fā)生變化；②因邏輯相鄰的數(shù)據(jù)元素物理位置上也相鄰，因此，除非i=n+1，否則必須將原表中位置n，n-1，…，i上的結點，依次后移到位置n+1，n，…，i+1上，空出第i個位置，在該位置上插入新結點b。⑼向線性表中的指定位置插入一個元素21boolinsertElem(SqList&L,ElemTypee,intpos){if(pos<1||pos>L.size+1){cerr<<"posisoutrange!"<<endl;returnfalse;}for(inti=L.size-1;i>=pos-1;--i)L.list[i+1]=L.list[i];L.list[pos-1]=e;++L.size;returntrue;}boolinsertElem(SqList&L,Elem22⑽從線性表中刪除指定位置的元素原表：a1，a2，…，ai-1，ai，ai+1，…，an刪除后的表：a1，a2，…，ai-1，ai+1，ai+2，…，an①ai-1和ai邏輯關系發(fā)生變化②需移動元素：i=n只刪an即可1≤i≤n-1將ai+1~an前移⑽從線性表中刪除指定位置的元素23booldeleteElem(SqList&L,intpos){if(pos<1||pos>L.size){cerr<<"posisoutrange!"<<endl;returnfalse;}for(inti=pos-1;i<L.size-2;++i)L.list[i]=L.list[i+1];--L.size;returntrue;}booldeleteElem(SqList&L,int24算法時間復雜度：在順序表中插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動數(shù)據(jù)元素上。對于插入算法而言，設Pi為在第i個元素之前插入元素的概率，并假設在任何位置上插入的概率相等，即Pi=1/(n+1),i=1,2,…，n+1。設Eins為在長度為n的表中插入一元素所需移動元素的平均次數(shù)，則對于刪除而言，設Qi為刪除第i個元素的概率，并假設在任何位置上刪除的概率相等，即Qi=1/n,i=1,2,…,n。刪除一個元素所需移動元素的平均次數(shù)Edel為：上述在順序表中插入或刪除一個數(shù)據(jù)元素的算法的時間復雜度為O(n)。算法時間復雜度：25⑾創(chuàng)建有n個元素的線性表boolcreateList(SqList&L,intn,void(*visit)(ElemType&)){if(n>L.maxSize)returnfalse;for(inti=0;i<n;++i){visit(L.list[i]);++L.size;}returntrue;}⑾創(chuàng)建有n個元素的線性表262.2.3順序表應用例例：已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要將La和Lb歸并為一個新的線性表Lc，且Lc中的數(shù)據(jù)元素仍按值非遞減排列。2.2.3順序表應用例例：已知線性表La和Lb中的數(shù)據(jù)元素27main.cpp#include"sqlist.h"SqListmergeList(SqListLa,SqListLb);voidprint(ElemType&e){cout<<"id:"<<e.id<<"age:"<<e.age<<endl;}main.cpp#include"sqlist.h"28intmain(){SqListla,lb;ElemTypea1,a2,a3,b1,b2,b3,b4;a1.id=1;a2.id=3;a3.id=6;b1.id=2;b2.id=4;b3.id=5;b4.id=7;initList(la,10);initList(lb,10);insertElem(la,a1,1);insertElem(la,a2,2);insertElem(la,a3,3);insertElem(lb,b1,1);insertElem(lb,b2,2);insertElem(lb,b3,3);insertElem(lb,b4,4);traverList(la,print);traverList(lb,print);SqListlc=mergeList(la,lb);traverList(lc,print);}intmain()29SqListmergeList(SqListLa,SqListLb){SqListLc;initList(Lc,20);inti,j,k,laSize,lbSize;ElemTypeai,bj;i=j=1,k=0;laSize=getSize(La);lbSize=getSize(Lb);SqListmergeList(SqListLa,SqL30while((i<=laSize)&&(j<=lbSize)){ai=getElem(La,i);bj=getElem(Lb,j);if(compare(ai,bj)==1){insertElem(Lc,ai,++k);++i;}else{insertElem(Lc,bj,++k);++j;}}while((i<=laSize)&&(j<=lb31while(i<=laSize){ai=getElem(La,i++);insertElem(Lc,ai,++k);}while(j<=lbSize){bj=getElem(Lb,j++);insertElem(Lc,bj,++k);}returnLc;}while(i<=laSize)322.3線性表的鏈式表示和實現(xiàn)線性表的鏈式存貯結構，也稱為鏈表。其存貯方式是：在內(nèi)存中利用存貯單元(可以不連續(xù))來存放元素值及它在內(nèi)存的地址，各個元素的存放順序及位置都可以以任意順序進行，原來相鄰的元素存放到計算機內(nèi)存后不一定相鄰，從一個元素找下一個元素必須通過地址(指針)才能實現(xiàn)。故不能像順序表一樣可隨機訪問，而只能按順序訪問。常用的鏈表有單鏈表、循環(huán)鏈表、雙向鏈表和多重鏈表等。2.3線性表的鏈式表示和實現(xiàn)線性表的鏈式存貯結構，也稱為鏈332.3.1單鏈表結構在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣的鏈表為單鏈表或線性鏈表。線性鏈表中的結點結構可描述為：其中data域用來存放結點本身信息，類型由具體問題而定，這里，我們也將其設定為ElemType類型，表示某一種具體的已知類型，next域用來存放下一個元素地址。2.3.1單鏈表結構在定義的鏈表中，若只含有一個指針域來存34線性表的類型定義、順序表示和實現(xiàn)35單鏈表可用Ｃ++描述為：structLNode{ ElemTypedata; LNode*next;};單鏈表可用Ｃ++描述為：36對上述線性表可設： LNode*H;其中：①H為單鏈表的頭指針，H指向表中第一個結點，若H=NULL,則線性表為"空表"；②若一個指針域的值為空，則在圖形中用"^"表示；③存儲第一個元素的結點稱為表頭結點，存儲最后一個元素的結點稱為表尾結點，指向表頭結點的指針(H)稱為表頭指針，通常以表頭指針命名一個鏈表，不能丟。對上述線性表可設：37④為了方便插入和刪除表頭結點操作更方便，經(jīng)常在表頭結點之前增加一個結點，稱為表頭附加結點（又稱頭結點）。值得注意的是，若線性表為空，在不帶頭結點的情況下，頭指針為空(NULL)，但在帶頭結點的情況下，鏈表的頭指針不為空，而是其頭結點中指針域的指針為空。④為了方便插入和刪除表頭結點操作更方便，經(jīng)常在表頭結點之前增382.3.2單鏈表中基本操作的實現(xiàn)

（帶頭結點）設線性表為(a1，a2，…，ai，ai+1，…，an),其相應帶有頭結點的線性鏈表為：2.3.2單鏈表中基本操作的實現(xiàn)

（帶頭結點）設線性表為(39單鏈表類型定義如下：

linklist.h#include<iostream>usingnamespacestd;structElem{ intid; intage;};typedefElemElemType;structLNode{ ElemTypedata; LNode*next;};typedefLNode*LinkList;單鏈表類型定義如下：

linklist.h#include40voidinitList(LinkList&L);LinkListgetRear(LinkListL);voidcreateList(LinkList&L,intn,void(*visit)(ElemType&));voidclearList(LinkList&L);intgetSize(LinkListL);boolisEmpty(LinkListL);voidtraverList(LinkListL,void(*visit)(ElemType&));ElemType&getElem(LinkListL,intpos);intlocateElem(LinkListL,ElemTypee,int(*compare)(ElemType,ElemType));boolinsertElem(LinkList&L,ElemTypee,intpos);booldeleteElem(LinkList&L,intpos);LinkListmergeList(LinkListLa,LinkListlb,int(*compare)(ElemType,ElemType));voidinitList(LinkList&L);41linklist.cpp

⑴初始化單鏈表voidinitList(LinkList&L){L=newLNode;if(!L)exit(1);//存儲空間分配失敗L->next=NULL;}算法的時間復雜度為O(1)。linklist.cpp

⑴初始化單鏈表voidinit42⑵獲取鏈尾指針LinkListgetRear(LinkListL){LinkListp=L;while(p->next!=NULL)p=p->next;returnp;}⑵獲取鏈尾指針LinkListgetRear(LinkL43⑶創(chuàng)建單鏈表voidcreateList(LinkList&L,intn,void(*visit)(ElemType&)){LinkListp;LinkListr=L;for(inti=1;i<=n;++i){p=newLNode;visit(p->data);p->next=NULL;r->next=p;r=r->next;}}⑶創(chuàng)建單鏈表voidcreateList(LinkLis44⑷遍歷單鏈表voidtraverList(LinkListL,void(*visit)(ElemType&)){LinkListp=L;if(p->next==NULL)cout<<"listisempty!"<<endl;else{while(p->next!=NULL){p=p->next;visit(p->data);}cout<<endl;}}⑷遍歷單鏈表voidtraverList(LinkLis45⑸清空單鏈表voidclearList(LinkList&L){LinkListr=L->next,p;L->next=NULL;while(r!=NULL){p=r;r=r->next;deletep;}}算法的時間復雜度為O(Listlength(L))。⑸清空單鏈表voidclearList(LinkList46⑹判斷單鏈表是否為空boolisEmpty(LinkListL){if(L->next==NULL)returntrue;elsereturnfalse;}⑹判斷單鏈表是否為空boolisEmpty(LinkLi47⑺獲取單鏈表長度intgetSize(LinkListL){LinkListp=L;intn=-1;while(p!=NULL){p=p->next;++n;}returnn;}⑺獲取單鏈表長度intgetSize(LinkList48⑻獲取指定位置的元素ElemType&getElem(LinkListL,intpos){LinkListp=L;inti=0;if(pos<1||pos>getSize(L)){cout<<"posisoutrange!"<<endl;exit(1);}while(i<pos){p=p->next;++i;}returnp->data;}⑻獲取指定位置的元素ElemType&getElem(L49⑼定位滿足條件的元素intlocateElem(LinkListL,ElemTypee,int(*compare)(ElemType,ElemType)){LinkListp=L;inti=0;while(p->next!=NULL){p=p->next;++i;if(compare(p->data,e)==1)returni;}return0;}⑼定位滿足條件的元素intlocateElem(Link50⑽在指定位置插入元素⑽在指定位置插入元素51boolinsertElem(LinkList&L,ElemTypee,intpos){LinkListp=L,s;inti=0;while(p!=NULL&&i<pos-1){p=p->next;++i;}if(pos<1||p==NULL)returnfalse;s=newLNode;s->data=e;s->next=p->next;p->next=s;returntrue;}boolinsertElem(LinkList&L,El52⑾刪除指定位置的元素⑾刪除指定位置的元素53booldeleteElem(LinkList&L,intpos){LinkListp=L,q;inti=0;if(pos<1||(p->next)==NULL)returnfalse;while((p->next)!=NULL&&i<pos-1){p=p->next;++i;}q=p->next;p->next=q->next;deleteq;returntrue;}booldeleteElem(LinkList&L,in542.3.3單鏈表算法例例：將兩個有序鏈表并為一個有序鏈表。2.3.3單鏈表算法例例：將兩個有序鏈表并為一個有序鏈表。55LinkListmergeList(LinkListLa,LinkListlb,int(*compare)(ElemType,ElemType)){LinkListLc,pa,pb,pc;pa=La->next;pb=lb->next;Lc=pc=La;while(pa&&pb){if(compare(pa->data,pb->data)){pc->next=pa;pc=pa;pa=pa->next;}LinkListmergeList(LinkListLa56else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;returnLc;}else57main.cpp#include"linklist.h"intcomp1(ElemTypee1,ElemTypee2){if(e1.id<=e2.id)return1;elsereturn0;}intcomp2(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;elsereturn0;}main.cpp#include"linklist.h"58voidprint(ElemType&e){cout<<"id:"<<e.id<<"age:"<<e.age<<endl;}voidinputElem(ElemType&e){cout<<"inputid:";cin>>e.id;cout<<"intputage:";cin>>e.age;cout<<endl;}voidprint(ElemType&e)59intmain(){LinkListla,lb,lc;initList(la);initList(lb);initList(lc);ElemTypea1,a2,a3,b1,b2,b3,b4;a1.id=1;a2.id=3;a3.id=6;b1.id=2;b2.id=4;b3.id=5;b4.id=7;intmain()60insertElem(la,a1,1);insertElem(la,a2,2);insertElem(la,a3,3);insertElem(lb,b1,1);insertElem(lb,b2,2);insertElem(lb,b3,3);insertElem(lb,b4,4);traverList(la,print);traverList(lb,print);cout<<"r:"<<endl;lc=mergeList(la,lb,comp1);traverList(lc,print);cout<<locateElem(lc,b1,comp2)<<endl;}insertElem(la,a1,1);61小結：從以上對鏈表的各種操作的討論可知，鏈式存儲結構的優(yōu)勢在于：①能有效利用存儲空間；②用"指針"指示數(shù)據(jù)元素之間的后繼關系，便于進行"插入"、"刪除"等操作；而其劣勢則是不能隨機存取數(shù)據(jù)元素。同時，它還丟失了一些順序表有的長處，如線性表的"表長"和數(shù)據(jù)元素在線性表中的"位序"，在上述的單鏈表中都看不見了。又如，不便于在表尾插入元素，需遍歷整個表才能找到插入的位置。小結：從以上對鏈表的各種操作的討論可知，鏈式存儲結構的優(yōu)勢在62為了更突出鏈表的優(yōu)勢，需改進單鏈表結構的定義。除了保留指向頭結點的指針外，還應增設"尾指針"和"表長"兩個屬性。同時，我們從上面討論的鏈表基本操作的實現(xiàn)算法中可以看出，在對鏈表進行操作時，經(jīng)常需要一個指針在鏈表中巡游，由此可以設想，如果將這個在操作中進行巡游的"指針"以及它所指結點的數(shù)據(jù)元素在線性表中的"位序"納入鏈表結構中，作為鏈表定義中的兩個成員，必然會對鏈表的操作帶來很多方便。為了更突出鏈表的優(yōu)勢，需改進單鏈表結構的定義。除了保留指向頭632.3.4靜態(tài)鏈表某些語言無指針類型，如何使用鏈式存儲？用"整數(shù)（又稱游標(cursor)）"來模擬指針實現(xiàn)鏈表。因需要為備用空間靜態(tài)分配一個數(shù)組，故把這種用"游標"實現(xiàn)的鏈表稱為靜態(tài)鏈表（staticlinkedlist）其方法是：定義一個規(guī)模較大的記錄數(shù)組作為備用結點空間，當需要"產(chǎn)生"新結點時，從備用空間中取出一個結點——相當于生成新結點；當要釋放結點時，將結點歸還到備用空間中。2.3.4靜態(tài)鏈表某些語言無指針類型，如何使用鏈式存儲？64數(shù)組中的元素：特點：仍需靜態(tài)分配一個較大空間插入和刪除時不需要移動元素，僅需修改指針，具有鏈式存儲結構的主要優(yōu)點。數(shù)組中的元素：65例：A=(44，50，57，62，68，75，83，94)①利用來自數(shù)組中的結點（元素），動態(tài)產(chǎn)生一個單鏈表，稱為靜態(tài)鏈表；②靜態(tài)鏈表也由一個頭指針唯一指定；③為便于結點的產(chǎn)生和釋放，通常將備用數(shù)組空間鏈成一個具有頭指針的單鏈表，并稱它為可用空間表或備用空間表。例：A=(44，50，57，62，68，75，83，94)①66靜態(tài)鏈表同樣可以借助一維數(shù)組來描述：constintMAXSIZE=100;structSNode{ElemTypedata;intcur;//指示其后繼結點在數(shù)組中的位置};typedefSNodeSLinkList[MAXSIZE];//聲明SLinkList為SNode數(shù)組類型，包含MAXSIZE個元素。SLinkListS;靜態(tài)鏈表同樣可以借助一維數(shù)組來描述：67①S[0]存放單鏈表的表頭附加結點；②S[1]存放空閑表的表頭附加結點；③剩余空間MAXSIZE-2個結點作為元素結點使用；④空閑表最后一個結點的cur=0,表示空指針。①S[0]存放單鏈表的表頭附加結點；68初始化單鏈表：單鏈表：無元素，S[0].cur=0空閑表：所有的空間for(inti=2;i<MAXSIZE-1;++i) S[i].cur=i+1;S[MAXSIZE-1].cur=0;//空閑表的最后一個結點指針為空S[1].cur=2;S[0].cur=0;初始化單鏈表：69當向數(shù)組中的單鏈表插入一個新元素時，首先從空閑表中取出（即刪除）表頭結點作為保存新元素的結點使用，然后再把該結點按條件插入到單鏈表中。當從數(shù)組中的單鏈表刪除一個元素結點時，首先從單鏈表中取出這個結點，然后再把該結點插入到空閑單鏈表的表頭。當向數(shù)組中的單鏈表插入一個新元素時，首先從空閑表中取出（即刪702.3.5循環(huán)鏈表單鏈表上的訪問是一種順序訪問，從其中某一個結點出發(fā)，可以找到它的直接后繼，但無法找到它的直接前驅。因此，我們可以考慮建立這樣的鏈表，具有單鏈表的特征，但又不需要增加額外的存貯空間，僅對表的鏈接方式稍作改變，使得對表的處理更加方便靈活。從單鏈表可知，最后一個結點的指針域為NULL表示單鏈表已經(jīng)結束。如果將單鏈表最后一個結點的指針域改為存放鏈表中頭結點（或第一個結點）的地址，就使得整個鏈表構成一個環(huán)，又沒有增加額外的存貯空間，稱這們的鏈表為單循環(huán)鏈表，在不引起混淆時稱為循環(huán)表（后面還要提到雙向循環(huán)表）。2.3.5循環(huán)鏈表單鏈表上的訪問是一種順序訪問，從其中某一71為了使某些操作實現(xiàn)起來方便，在循環(huán)單鏈表中也可設置一個頭結點。這樣，空循環(huán)鏈表僅由一個自成循環(huán)的頭結點表示。為了使某些操作實現(xiàn)起來方便，在循環(huán)單鏈表中也可設置一個頭結點72單鏈表與循環(huán)鏈表：①操作基本相同；②差別：a.查找單鏈表：從表頭開始。查表頭結點O(1)，查表尾結點O(n)。循環(huán)鏈表：從任一點出發(fā)均可。用尾指針表示時，查表尾O(1)，即rear，查表頭O(1)，即rear->next。b.判定是否到鏈尾單鏈表：p->next==NULL。循環(huán)鏈表：p->next==L。單鏈表與循環(huán)鏈表：73c.鏈表的合并例：有兩個帶頭結點的循環(huán)單鏈表A、B，編寫一個算法，將兩個循環(huán)單鏈表合并為一個循環(huán)單鏈表，其頭指針為A。算法思想1（非循環(huán)鏈表必需的方法）：先找到兩個鏈表的尾，并分別用指針p、q指向它們，然后將第一個鏈表的尾與第二個表的第一個結點鏈接起來，并修改第二個表的尾q，使它的鏈域指向第一個表的頭結點。c.鏈表的合并74采用上面的方法，需要遍歷鏈表，找到表尾，其執(zhí)行時間是O(n)。采用上面的方法，需要遍歷鏈表，找到表尾，其執(zhí)行時間是O(n)75若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需要修改指針，無需遍歷，其執(zhí)行時間是O(1)。若在尾指針表示的單循環(huán)鏈表上實現(xiàn)，則只需要修改指針，無需遍歷76//此算法將兩個鏈表首尾連接起來voidmerge(LNode*&A,LNode*&B){ LNode*p; p=A->next;//保存鏈表A的頭結點地址 A->next=B->next->next;//鏈表B的開始結點鏈到鏈表A的終端結點之后 deleteB->next;//釋放鏈表B的頭結點 B->next=p;//鏈表A的頭結點鏈到鏈表B的終端結點之后 A=B;}//此算法將兩個鏈表首尾連接起來772.3.5雙向鏈表循環(huán)單鏈表的出現(xiàn)，雖然能夠實現(xiàn)從任一結點出發(fā)沿著鏈能找到其前驅結點，但時間耗費是O(n)。如果希望從表中快速確定某一個結點的前驅，另一個解決方法就是在單鏈表的每個結點里再增加一個指向其前驅的指針域。這樣形成的鏈表中就有兩條方向不同的鏈，我們可稱之為雙(向)鏈表(DoubleLinkedList)。2.3.5雙向鏈表循環(huán)單鏈表的出現(xiàn)，雖然能夠實現(xiàn)從任一結點78雙向鏈表結點結構：雙鏈表的結構定義如下：typedefstructDuLNode{ ElemTypedata; structDuLNode*prior structDuLNode*next;}DuLNode,*DuLinkList;雙向鏈表結點結構：79由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個結點的直接前驅結點與直接后繼結點變得非常方便。設指針p指向雙鏈表中某一結點，則有下式成立： p->prior->next=p=p->next->prior由于在雙向鏈表中既有前向鏈又有后向鏈，尋找任一個結點的直接前80雙鏈表的部分操作：

①雙向鏈表的前插操作s=newLNode;s->data=c;//產(chǎn)生新結點s->prior=p->prior;//①p->prior->next=s;//②s->next=p;//③p->prior=s;//④雙鏈表的部分操作：

①雙向鏈表的前插操作s=newLNod81②雙向鏈表的刪除操作p->prior->next=p->next;p->next->prior=p->prior;deletep;②雙向鏈表的刪除操作p->prior->next=p->ne82例：設一個循環(huán)雙鏈表L=（a,b,c,d）,編寫一個算法,將鏈表轉換為L=（b,a,c,d）。算法思想：本題實際上是交換表中前兩個元素的次序。①摘下b（（1）→（2））②插入到a前面（（3）→（4）→（5）→（6））例：設一個循環(huán)雙鏈表L=（a,b,c,d）,編寫一個83第2章線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)第2章線性表2.1線性表的類型定義84線性表是一種最簡單的線性結構。什么是線性結構？簡單地說，線性結構是一個數(shù)據(jù)元素的有序（次序）集合。它有四個基本特征：在數(shù)據(jù)元素的非空有限集中，①存在惟一的一個被稱做"第一個"的數(shù)據(jù)元素；②存在惟一的一個被稱做"最后一個"的數(shù)據(jù)元素；③除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅；④除最后一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼。這里的"有序"僅指在數(shù)據(jù)元素之間存在一個"領先"或"落后"的次序關系，而非指數(shù)據(jù)元素"值"的大小可比性。比較典型的線性結構：線性表、棧、隊列、串等。線性表是一種最簡單的線性結構。852.1線性表的類型定義

2.1.1線性表的定義線性表(linear_list)是n個數(shù)據(jù)元素的有限序列，記作（a1,a2,…,ai,…,an）。線性表的數(shù)學模型（形式定義）：含有n個數(shù)據(jù)元素的線性表是一個數(shù)據(jù)結構LinearList=（A,R）其中：A={ai|ai∈ElemType,1≤i≤n,n≥0}R={r}r=｛<ai,ai+1>|1≤i≤n-1}2.1線性表的類型定義

2.1.1線性表的定義線性表(l86說明：①線性表的數(shù)據(jù)元素可以是各種類型（整、實、記錄類型等）typedefintElemType;typedefcharElemType;等；②同一線性表中的數(shù)據(jù)元素必須具有相同的特性，屬同一類型；③關系r是一個有序偶對的集合，即對于非空的線性表（a1,a2,…,ai-1,ai,ai+1,…,an），ai-1領先于ai，表示了數(shù)據(jù)元素之間的相鄰關系，稱ai-1是ai的直接前驅，ai是ai-1的直接后繼；④序列中數(shù)據(jù)元素的個數(shù)n定義為線性表的表長，n=0時的線性表被稱為空表；⑤稱i為數(shù)據(jù)元素在線性表中的位序。說明：①線性表的數(shù)據(jù)元素可以是各種類型（整、實、記錄類型等）872.1.2線性表的抽象數(shù)據(jù)類型ADTLinearList{ Data: 一個線性表L定義為L=(a1,a2,…,an)，當L=（）時定義為一個空表。 Operation: boolinitList(&L);//初始化線性表L，即把它設置為一個空表 voidclearList(&L);//將L重置為空表 intgetSize(L);//返回L中數(shù)據(jù)元素的個數(shù) boolisEmpty(L); //判斷L是否為空，若空則返回true，否則返回false voidtraverList(L,visit()); //遍歷線性表L，依次對L的每個數(shù)據(jù)元素調(diào)用函數(shù)visit() ElemType&getElem(L,pos); //返回線性表第pos個數(shù)據(jù)元素的值2.1.2線性表的抽象數(shù)據(jù)類型ADTLinearList88 intlocateElem(&L,e,compare()); //返回L中第1個與e滿足關系compare()的數(shù)據(jù)元素的位序。若這樣的數(shù)據(jù)元素不存在，則返回0 boolinsertElem(&L,e,pos); //在L的pos位置插入e，線性表L長度加1 booldeleteElem(&L,pos); //刪除L的第pos個數(shù)據(jù)元素 boolcreateList(&L,n,visit()); //創(chuàng)建有n個元素的線性表} intlocateElem(&L,e,compare(892.1.3操作舉例例：假設利用兩個線性表La和Lb分別表示兩個集合A和B，求一個新的集合A=A∪B。算法：①取得Lb中的1個元素；②在La中查找這個元素；③若不存在：插入La中；若存在，取Lb中下一個元素，重復①、②、③，直到取完Lb的每個元素。2.1.3操作舉例例：假設利用兩個線性表La和Lb分別表示90voidunionList(SqList&la,SqListlb){intlbSize=getSize(lb);ElemTypee;for(inti=1;i<=lbSize;++i){e=getElem(lb,i);if(!locateElem(la,e,equal))insertElem(la,e,la.size+1);}}intequal(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;return0;}算法的時間復雜度為O(La.size×Lb.size)。voidunionList(SqList&la,SqLi912.2線性表的順序表示和實現(xiàn)

2.2.1線性表的順序表示線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表中的各個元素，使得線性表中在邏輯結構上相鄰的數(shù)據(jù)元素存儲在相鄰的物理存儲單元中，即通過數(shù)據(jù)元素物理存儲的相鄰關系來反映數(shù)據(jù)元素之間邏輯上的相鄰關系。采用順序存儲結構的線性表通常稱為順序表。表示為：A=(a1，a2，…，ai，ai+1，…，an)2.2線性表的順序表示和實現(xiàn)

2.2.1線性表的順序表示92第i個元素的地址假設線性表中有n個元素，每個元素占k個單元，第一個元素的地址為loc(a1)，則可以通過如下公式計算出第i個元素的地址loc(ai)：loc(ai)=loc(a1)+(i-1)×k其中l(wèi)oc(a1)稱為基地址。第i個元素的地址假設線性表中有n個元素，每個元素占k個單元，93線性表的順序存儲結構示意圖順序存儲結構可以借助于高級程序設計語言中的一維數(shù)組來表示。線性表的順序存儲結構示意圖順序存儲結構可以借助于高級程序設計94用C++語言描述的順序表類型如下所示：

sqlist.h#include<iostream>usingnamespacestd;structNode//定義結點（數(shù)據(jù)元素）的類型{ intid; intage;};typedefNodeElemType;//聲明結點的類型名為ElemTypestructSqList//定義線性表的存儲結構{ ElemType*list; intsize; intmaxSize;};用C++語言描述的順序表類型如下所示：

sqlist.h#i95boolinitList(SqList&L,intms);voidclearList(SqList&L);intgetSize(SqListL);boolisEmpty(SqListL);boolisFull(SqListL);voidtraverList(SqListL,void(*visit)(ElemType&));ElemType&getElem(SqListL,intpos);intlocateElem(SqList&L,ElemTypee,int(*compare)(ElemType,ElemType));intfindList(SqListL,ElemTypee);boolinsertElem(SqList&L,ElemTypee,intpos);booldeleteElem(SqList&L,intpos);boolcreateList(SqList&L,intn,void(*visit)(ElemType&));boolinitList(SqList&L,intms962.2.2線性表順序存儲結構上的基本運算

sqlist.cpp⑴初始化線性表①初始化變量，申請空間；②size賦值；maxsize賦值。boolinitList(SqList&L,intms){L.list=newElemType[ms];if(!L.list){cerr<<"Memoryallocationfailure!"<<endl;exit(1);}L.size=0;L.maxSize=ms;returntrue;}2.2.2線性表順序存儲結構上的基本運算

sqlist.c97⑵刪除線性表的所有元素，使之成為空表在順序存儲方式下實現(xiàn)此操作只要將線性表的長度置0即可。voidclearList(SqList&L){L.size=0;}⑶檢查線性表是否為空boolisEmpty(SqListL){returnL.size==0;}⑵刪除線性表的所有元素，使之成為空表98⑷獲取表元素的個數(shù)intgetSize(SqListL){returnL.size;}⑸檢查線性表是否已滿boolisFull(SqListL){returnL.size==L.maxSize;}⑷獲取表元素的個數(shù)99⑹得到線性表中指定序號的元素ElemType&getElem(SqListL,intpos){if(pos<1||pos>L.size){cerr<<"posisoutrange!"<<endl;exit(1);}returnL.list[pos-1];}⑹得到線性表中指定序號的元素100⑺遍歷線性表 遍歷一個線性表就是從線性表的第一個元素起，按照元素之間的邏輯順序，依次訪問每一個元素，并且每個元素只被訪問一次，直到訪問完所有元素為止。voidtraverList(SqListL,void(*visit)(ElemType&)){for(inti=0;i<L.size;++i)visit(L.list[i]);cout<<endl;}如要依次輸出每個元素的值，visit()的實參可定義如下：voidprint(ElemType&e){cout<<"id:"<<e.id<<"age:"<<e.age<<endl;}⑺遍歷線性表101⑻查找線性表中滿足給定條件的元素intlocateElem(SqList&L,ElemTypee,int(*compare)(ElemType,ElemType)){for(inti=0;i<L.size;++i)if(compare(L.list[i],e)==1)returni+1;return0;}如要查找與e的相等（某對應成員的值相等）的元素，則compare()的實參可定義如下：intequal(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;return0;}⑻查找線性表中滿足給定條件的元素102算法的時間復雜度： 時間耗費主要在比較元素的次數(shù)上，而次數(shù)取決于待查找元素的位置。最好情況:compare(L.list[0],e)==1O(1）最壞情況:compare(L.list[n-1],e)==1O(n)平均情況:O(n)算法的時間復雜度：103⑼向線性表中的指定位置插入一個元素原表：a1，a2，…，ai-1，ai，ai+1，…，an插入后的表：a1，a2，…，ai-1，b，ai，ai+1，…，an①ai-1和ai邏輯關系發(fā)生變化；②因邏輯相鄰的數(shù)據(jù)元素物理位置上也相鄰，因此，除非i=n+1，否則必須將原表中位置n，n-1，…，i上的結點，依次后移到位置n+1，n，…，i+1上，空出第i個位置，在該位置上插入新結點b。⑼向線性表中的指定位置插入一個元素104boolinsertElem(SqList&L,ElemTypee,intpos){if(pos<1||pos>L.size+1){cerr<<"posisoutrange!"<<endl;returnfalse;}for(inti=L.size-1;i>=pos-1;--i)L.list[i+1]=L.list[i];L.list[pos-1]=e;++L.size;returntrue;}boolinsertElem(SqList&L,Elem105⑽從線性表中刪除指定位置的元素原表：a1，a2，…，ai-1，ai，ai+1，…，an刪除后的表：a1，a2，…，ai-1，ai+1，ai+2，…，an①ai-1和ai邏輯關系發(fā)生變化②需移動元素：i=n只刪an即可1≤i≤n-1將ai+1~an前移⑽從線性表中刪除指定位置的元素106booldeleteElem(SqList&L,intpos){if(pos<1||pos>L.size){cerr<<"posisoutrange!"<<endl;returnfalse;}for(inti=pos-1;i<L.size-2;++i)L.list[i]=L.list[i+1];--L.size;returntrue;}booldeleteElem(SqList&L,int107算法時間復雜度：在順序表中插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動數(shù)據(jù)元素上。對于插入算法而言，設Pi為在第i個元素之前插入元素的概率，并假設在任何位置上插入的概率相等，即Pi=1/(n+1),i=1,2,…，n+1。設Eins為在長度為n的表中插入一元素所需移動元素的平均次數(shù)，則對于刪除而言，設Qi為刪除第i個元素的概率，并假設在任何位置上刪除的概率相等，即Qi=1/n,i=1,2,…,n。刪除一個元素所需移動元素的平均次數(shù)Edel為：上述在順序表中插入或刪除一個數(shù)據(jù)元素的算法的時間復雜度為O(n)。算法時間復雜度：108⑾創(chuàng)建有n個元素的線性表boolcreateList(SqList&L,intn,void(*visit)(ElemType&)){if(n>L.maxSize)returnfalse;for(inti=0;i<n;++i){visit(L.list[i]);++L.size;}returntrue;}⑾創(chuàng)建有n個元素的線性表1092.2.3順序表應用例例：已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要將La和Lb歸并為一個新的線性表Lc，且Lc中的數(shù)據(jù)元素仍按值非遞減排列。2.2.3順序表應用例例：已知線性表La和Lb中的數(shù)據(jù)元素110main.cpp#include"sqlist.h"SqListmergeList(SqListLa,SqListLb);voidprint(ElemType&e){cout<<"id:"<<e.id<<"age:"<<e.age<<endl;}main.cpp#include"sqlist.h"111intmain(){SqListla,lb;ElemTypea1,a2,a3,b1,b2,b3,b4;a1.id=1;a2.id=3;a3.id=6;b1.id=2;b2.id=4;b3.id=5;b4.id=7;initList(la,10);initList(lb,10);insertElem(la,a1,1);insertElem(la,a2,2);insertElem(la,a3,3);insertElem(lb,b1,1);insertElem(lb,b2,2);insertElem(lb,b3,3);insertElem(lb,b4,4);traverList(la,print);traverList(lb,print);SqListlc=mergeList(la,lb);traverList(lc,print);}intmain()112SqListmergeList(SqListLa,SqListLb){SqListLc;initList(Lc,20);inti,j,k,laSize,lbSize;ElemTypeai,bj;i=j=1,k=0;laSize=getSize(La);lbSize=getSize(Lb);SqListmergeList(SqListLa,SqL113while((i<=laSize)&&(j<=lbSize)){ai=getElem(La,i);bj=getElem(Lb,j);if(compare(ai,bj)==1){insertElem(Lc,ai,++k);++i;}else{insertElem(Lc,bj,++k);++j;}}while((i<=laSize)&&(j<=lb114while(i<=laSize){ai=getElem(La,i++);insertElem(Lc,ai,++k);}while(j<=lbSize){bj=getElem(Lb,j++);insertElem(Lc,bj,++k);}returnLc;}while(i<=laSize)1152.3線性表的鏈式表示和實現(xiàn)線性表的鏈式存貯結構，也稱為鏈表。其存貯方式是：在內(nèi)存中利用存貯單元(可以不連續(xù))來存放元素值及它在內(nèi)存的地址，各個元素的存放順序及位置都可以以任意順序進行，原來相鄰的元素存放到計算機內(nèi)存后不一定相鄰，從一個元素找下一個元素必須通過地址(指針)才能實現(xiàn)。故不能像順序表一樣可隨機訪問，而只能按順序訪問。常用的鏈表有單鏈表、循環(huán)鏈表、雙向鏈表和多重鏈表等。2.3線性表的鏈式表示和實現(xiàn)線性表的鏈式存貯結構，也稱為鏈1162.3.1單鏈表結構在定義的鏈表中，若只含有一個指針域來存放下一個元素地址，稱這樣