返回主目錄

本章說明2.1線性表的類型定義2.2線性表的順序表示和實現2.3線性表的鏈式存儲結構2.4循環鏈表和雙向鏈2.5一元多項式的表示及相加

本章小結本章說明學習目標了解線性表的邏輯結構特性是數據元素之間存在著線性關系，在計算機中表示這種關系的兩類不同的存儲結構是順序存儲結構和鏈式存儲結構。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。熟練掌握這兩類存儲結構的描述方法以及線性表的基本操作在這兩種存儲結構上的實現。能夠從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的不同特點及其適用場合。結合線性表類型的定義增強對抽象數據類型的理解。本章說明重點和難點鏈表是本章的重點和難點。扎實的指針操作和內存動態分配的編程技術是學好本章的基本要求，分清鏈表中指針p和結點*p之間的對應關系，區分鏈表中的頭結點、頭指針和首元結點的不同所指以及循環鏈表、雙向鏈表的特點等。知識點線性表、順序表、鏈表、有序表線性結構的特點：在數據元素的非空有限集中存在唯一的一個被稱做“第一個”的數據元素存在唯一的一個被稱做“最后一個”的數據元素除第一個之外，每個元素都只有一個前驅除最后一個之外，每個元素都只有一個后繼1.線性表是最常用、最簡單的一種線性數據結構。定義：一個線性表是n個數據元素的有限序列。2.1線性表的類型定義例如：英文字母（A，B，C，……，Z）是一個線性表。表中元素是一個字母。例如：星期（星期日，星期一，星期二，……，星期六）是一個線性表。表中的數據元素是星期中一天的名稱。例如：在稍復雜的線性表中，一個數據元素可以是由若干個數據項組成的記錄，含有大量記錄線性表稱為文件。如，一個學校的學生健康情況登記表。姓名學號性別年齡班級健康狀況王小林790631男18計91健康陳紅790632女20計91一般劉建平790633男21計91健康張立立790634男17計91神經衰弱┆┆┆┆┆┆數據元素2.線性表的結構特性

線性表是n≥0個數據元素a1，a2，…，ai-1，ai，ai+1，…，an的有限序列。一個線性表中的數據元素是屬于同一數據對象，相鄰數據元素之間存在著序偶關系。(同構元素）可將線性表記為（a1,…,ai-1,ai,ai+1,…an）。ai-1是ai的直接前驅元素，ai+1是ai的直接后繼元素。

a1無直接前驅，an無直接后繼。i是數據元素ai在線性表中的位序。線性表的長度定義為線性表中數據元素的個數n。當n=0時，為空表。2.1線性表的類型定義3.線性表的基本運算表的初始化求表長取（或修改）表中的結點查找結點插入結點刪除結點不是全部操作，不同的問題需要的操作不同。2.1線性表的類型定義4.抽象數據類型線性表的定義P19

ADTList{

數據對象：D={ai|ai∈ElemSet,i=1,2,…,n,n>=0}

數據關系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n}

基本操作：

InitList(&L)//創建一個空的線性表LDestroyList(&L)//撤消L2.1線性表的類型定義ClearList(&L)//將L重置為空表

ListEmpty(L)//判L是否為空?空為TListLength(L)//返回表長度(元素個數)GetElemList(L,i,&e)//用e返回L中第i個數據元素的個數2.1線性表的類型定義4.抽象數據類型線性表的定義P19

例2-1兩個線性表LA、LB，將存在于線性表LB中而不在LA中的數據元素加入到線性表LA中。即LA=LA∪LB算法思想：逐一取出LB中的元素，判斷是否在LA中，若不在,則插入之。僅已知LA、LB

（1）先求出LA、LB長度（2）若LB未取空，取LB中一元素=>e，若LB取空則轉（4）（3）如e不在LA中，則插入到LA中，轉（2）（4）結束2.1線性表的類型定義voidunin(List&La，ListLb){La_len=(ListLength(La));Lb_len=(ListLength(Lb));for(i=1;i<=Lb_len;i++){GetElem(Lb,i,&e);//取LB中第i個元素

if(!LocateElem(La,e,equal))ListInsert(&La,++La_len,e); }//La中不存在和e相同的元素，則插入之}//union算法的時間復雜度：O(ListLength(LA)×ListLength(LB))算法2.1實現求表長、插入、取元素時間復雜度：O(1)2.1線性表的類型定義例2-2線性表LA和LB是非遞減有序的，將兩表合并成新的線性表LC，且LC也是非遞減的。算法思想：將LA、LB兩表中的元素逐一按序加入到一個新表LC中。即（1）LA、LB均不空，則在LA中取一元素=>a,LB中取一元素=>b,否則轉（3）（2）若a<=b,a=>c,否則b=>c,轉（1）（3）若LA不空，則LA剩余部分放到LC尾（4）若LB不空，則LA剩余部分放到LC尾voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);//建一空表LCi=j=1;k=0;//i，j，k分別指向La，Lb，Lc

初始位置算法2.22.1線性表的類型定義La_len=(ListLength(La));Lb_len=(ListLength(Lb));while(i<=La_len)&&(j<=Lb_len){//La和Lb均非空

GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}算法2.22.1線性表的類型定義while(i<=La_len)//La還有元素

{GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len)//Lb還有元素

{GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList時間復雜度：(ListLength(LA)+ListLength(LB))2.1線性表的類型定義2.2線性表的順序表示和實現3.線性表的動態分配順序存儲結構4.順序線性表的操作2.順序表的特點1.線性表的順序表示5.順序表的優缺點用一組地址連續的存儲單元存儲一個線性表的數據元素，稱為順序表。用一維數組表示元素地址計算方法：

元素存儲位置：LOC(ai+1)=LOC(ai)+L一般存儲位置：LOC(ai)=LOC(a1)+(i-1)*L其中：L—一個元素占用的存儲單元個數

LOC(ai)—線性表第i個元素的地址實現：可用C語言的一維數組實現2.2線性表的順序表示和實現a1a2an01n-112n內存V數組下標元素序號M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];空閑空間數據元素不是簡單類型時,可定義結構體數組或動態申請和釋放內存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);2.順序表的特點特點：實現邏輯上相鄰—物理地址相鄰

實現隨機存取2.2線性表的順序表示和實現3.線性表的動態分配順序存儲結構用一維數組定義一個線性表#defineLIST_INIT_SIZE100#defineLISTINCREAMENT10typestruct{ElemType*elem;//指向線性表起始地址的指針

intlength;//線性表實際存放數據長度

intlistsize;//線性表申請長度

}SqList2.2線性表的順序表示和實現4.順序線性表的操作順序表容易實現訪問操作，可隨機存取元素。但插入和刪除操作主要是移動元素。(1)初始化操作算法思想：構造一個空表。設置表的起始位置表長可用空間2.2線性表的順序表示和實現線性表初始化算法2.3StatusInitList_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_Sq2.2線性表的順序表示和實現（2）插入定義：線性表的插入是指在第i（1

i

n+1）個元素之前插入一個新的數據元素x，使長度為n的線性表

變成長度為n+1的線性表

需將第i至第n共（n-i+1)個元素后移算法時間復雜度T(n)內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1內存a1a2aiai+1an01i-1V數組下標n-1in12i元素序號i+1nn+1an-1xX插入算法2.4

（在表L中的第i個元素之前插入e），見P24①判i值的合法性，1≤i≤表長+1；②判表的空間滿否？若滿則增加分配（動態分配）；③從表元素n到i，依次后移一個位置；④將e插入第i個位置，表長度增1。＊算法中定義的線性表是L，以結構形式出現2.2線性表的順序表示和實現插入算法2.4時間復雜度T(n)

可見插入元素的時間主要花費在移動元素上，而移動元素的個數主要取決于插入的位置。

設pi是在第i個元素之前插入一個元素的概率，則在長度為n的線性表中插入一個元素時需移動元素的平均次數為若在任何位置上插入元素都是等概率2.2線性表的順序表示和實現

在順序表中插入一個元素時，平均移動表的一半元素，當n很大時，效率很低。（3）刪除

算法思想：刪除第i個元素，將第（i+1）至第n個元素逐一向前移動一個位置，將長度為n

變成長度為n-1=>n的線性表

需將第i+1至第n個，共（n-i)個元素前移算法算法時間復雜度內存a1a2aiai+1an01i-1V數組下標n-1i12i元素序號i+1n內存a1a2ai+201i-1V數組下標n-1i12i元素序號i+1nanai+1刪除在表L中刪除第i個元素，放入e，見P24①判i值的合法性，1≤i≤表長n②取第i個元素，放入e③從i+1到表長n，依次前移④表長度減1刪除算法2.5思想2.2線性表的順序表示和實現刪除算法2.5時間復雜度

可見刪除元素的時間主要花費在移動元素上，而移動元素的個數主要取決于刪除的位置。

設qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素所需移動的元素次數的平均次數為若在任何位置上插入元素都是等概率2.2線性表的順序表示和實現

在順序表中刪除一個元素時，平均移動表的一半元素，當n很大時，效率很低。5.順序表的的優缺點優點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預先分配空間需按最大空間分配，利用不充分表容量難擴充2.2線性表的順序表示和實現2.3線性表的鏈式存儲結構

1.特點用一組任意的存儲單元存儲線性表的數據元素利用指針實現了用不相鄰的存儲單元存放邏輯上相鄰的元素每個數據元素ai，除存儲本身信息外，還需存儲其直接后繼的信息（指針），用來表示線性表數據元素的邏輯關系結點

數據域：元素本身信息指針域：指示直接后繼的存儲位置數據域指針域結點ZHAOQIANSUNLIZHOUWUZHENGWANG^H例線性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925數據域指針域LIQIANSUNWANGWUZHAOZHENGZHOU存儲地址1713192531374331H頭指針數據之間的邏輯關系由結點中的指針指示最后結點2.線性鏈表的定義由n個結點鏈結成一個鏈表，稱為線性鏈表或單鏈表。結點（Node）、數據域、指針域、指針、鏈、頭指針3.線性鏈表的實現

typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;2.3線性表的鏈式存儲結構LNode*L,*p;(*p)表示p所指向的結點p->data表示p指向結點的數據域p->next表示p指向結點的指針域生成一個LNode型新結點：p=(LNode*)malloc(sizeof(LNODE));系統回收p結點：free(p)帶頭結點非空表：空表：datanextp結點（*p）a1a2an/\…L/\L2.3線性表的鏈式存儲結構4.鏈式存儲結構的優點插入、刪除操作是不再需要移動大量的元素，但失去了順序表的可隨機存取特點。5.單鏈表的操作取第i個元素（算法2.8）算法思想：單鏈表是非隨機存取結構。每個元素的位置信息都包含在前驅結點的信息中，所以取得第i個元素必須從頭指針出發尋找。設置一個指針變量指向第一個結點，然后，讓該指針變量逐一向后指向，直到第i個元素。2.3線性表的鏈式存儲結構StatusGetElem_L(LinkListL,inti,ElemType){ //L為帶頭結點的單鏈表的頭指針。

//當第i個元素存在時，其值賦給e并返回OK，否則返回ERROR p=L→next;//p指向第1個結點，j做計數器

j=1; while(p&&j<i)//直到p指向第i元素或p為空

{p=p→next;++j;} e=p→data; returnOK;}//GetElem_L取結點算法實現2.3線性表的鏈式存儲結構要求：在帶頭結點的單鏈表L中第i個位置之前插入元素e（即在數據元素a和b之間插入元素e）算法思想：設p為指向頭結點的指針，s為指向結點e的指針先找到第i-1個位置（即p指向元素a的位置）生成新結點然后插入:修改s、p的指針決定a和b之間的相鄰關系是由a的指針決定的。若要實現插入，生成e結點，然后讓a的指針指向e且e的指針指向b。實現三個元素a、e和b的邏輯關系。插入結點算法2.92.3線性表的鏈式存儲結構EsB…A…ps->next=p->nextp->next=sXsB…A…p可否交換兩個指針的修改次序？La1a2頭結點an^…...0pj=0pj=n非法插入情況：i>表長:j<i-1,p=nulli<1:即i=0,-1,-2…..,j>i-1StatusListInsert_L(ListLInk&L,inti,ElemTypee){//在帶頭結點的單鏈表L中第i個位置之前插入元素e p=L;j=0; while(p&&j<i-1){p=p→next;++j;}//找第i-1結點

if(!p||j>i-1)returnERROR;//i小于1或大于表長

s=(LinkList*)malloc(sizeof(LNode)); s→data=e;s→next=p-next; p→next=s; returnOK;}//ListInsert_L 插入結點算法2.9實現2.3線性表的鏈式存儲結構BC…A…pC…A…p刪除操作p->next=p->next->next刪除結點算法2.10實現StatusListDelete_L(LinkList&L,inti,ElemType&e){//在帶頭結點的單鏈表L中刪除第i個元素，并由e返回

p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}//尋找第i個結點，并令p指向其前驅第i-1結點

if(!p->next)||j>i-1)returnERROR;//i>表長||i<1q=p->next;p->next=q->next;e=q->data;free(q);returnOK;}//ListDelete_L2.3線性表的鏈式存儲結構動態創建鏈表算法算法思想：設線性表n個元素，逆位序輸入數據元素建立一個單鏈表，h為頭指針。h頭結點an^0h頭結點an-10an^a2…...h頭結點an-10an^ha1a2頭結點an^…...0h頭結點0^動態創建鏈表算法2.11實現VoidCreateList_L(LinkList&L,intn){//逆位序輸入n個元素值，建立帶頭結點的單鏈表LL=（LinkList*)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){p=(LinkList*)malloc(sizeof(LNode));scanf(&p->data);p->next=L->next;L->next=p;}}//CreatList_L2.3線性表的鏈式存儲結構例：將兩個有序鏈表合并為一個有序鏈表。算法思想設立三個指針pa、pb和pc分別用來指向兩個有序鏈表和合并表的當前元素。比較兩個表的當前元素的大小，將小的元素鏈接到合并表Lc中,讓合并表的當前指針指向該元素，然后，修改指針。在歸并兩個鏈表為一個鏈表時，不需要另建新表的結點空間，而只需將原來兩個鏈表中結點之間的關系解除，重新建立關系。合并有序鏈表算法2.122.3線性表的鏈式存儲結構3511/\La8152620/\8911LbLcpbpapcpc-next=pbpc->next=papbpcpapcpapcpbpcpapcpbpcpbpcpapc每次鏈接pa或pb的一個結點后，便做如下操作：

pa=pa->next;pc=pc->next;pa和pc分別后移一個位置或pb=pb->next;pc=pc->next;pb和pc分別后移一個位置合并有序鏈表算法2.12實現VoidMergeList_L(LinkListLa,LinkListLb,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);}//MergeList_L2.3線性表的鏈式存儲結構單鏈表特點它是一種動態結構，整個存儲空間為多個鏈表共用。不需預先分配空間。指針占用額外存儲空間。不能隨機存取，查找速度慢。插入、刪除操作的速度快。2.3線性表的鏈式存儲結構6.靜態單鏈表有些高級語言沒有指針，我們可以用數組來表示單鏈表，在數組中以整型游標來代替指針。這種用數組描述的鏈表稱為靜態鏈表。存儲結構：

#defineMAXSIZE1000typedefstruct{ ElemTypedata; intcur;}component,SLinklist[MAXSIZE];S[i].cur指示第i+1個結點的位置。靜態鏈表的操作和動態鏈表相似，以整型游標代替動態指針。2.3線性表的鏈式存儲結構011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910SHI9S[0].cur為頭指針，可以遍歷整個靜態鏈表找到插入位置i011ZHAO22QIAN33SUN44LI55ZHOU66WU87ZHENG88WANG09SHI510SHI85刪除ZHENG,s[6].cur=s[7].curintLocateElem_SL(SLinkListS,ElemTypee){//在靜態單鏈線性表L中查找第1個值為e的元素

//找到返回位序，否則返回0i=S[0].cur;while(i&&S[i].data!=e)i=S[i].cur;returni;//沒找到則到鏈尾，i=0}//LocateElem_SL算法2.13靜態鏈表查找2.3線性表的鏈式存儲結構假設由終端輸入A集合元素并建立靜態鏈表S，然后輸入集合B元素在S中查找，若存在和B相同的元素，則從S中刪除之，否則插入到S中。算法思想：將整個數組空間初始化成一個鏈表從備用空間取得一個結點將空閑結點鏈接到備用鏈表上例2-3運算(A-B)U(B-A)2.3線性表的鏈式存儲結構01122334455667788991010003122c0344556677089910100Space[0].cur是備用空閑鏈表的頭指針，space[1].cur是鏈表的頭指針A=(c,b,e,g,f,d),B=(a,b,n,f)。即0、1下標不存放數據初始化后04122c33b0455667708991010005122c33b44e05667788991010006122c33b44e55g0677889910100Space[0].cur是備用空閑鏈表的頭指針，space[1].cur是鏈表的頭指針A=(c,b,e,g,f,d),B=(a,b,n,f)07122c33b44e55g66f07889910100A=(c,b,e,g,f,d),B=(a,b,n,f)取B中元素在A中查找，若有與其相同的，則將A中的同元素刪除，若沒有則在A中插入08122c33b44e55g66f77d089910100A輸入結束09122c33b44e55g66f77d88a091010003122c43b94e55g66f77d88a0910100刪b,space[2].cur取a，在A中找，沒有插入A=(c,b,e,g,f,d),B=(a,b,n,f)取B中元素在A中查找，若有與其相同的，則將A中的同元素刪除，若沒有則在A中插入03122c43b94e55g66f77d88a091010009122c43n04e55g66f77d88a391010006122c43n04e55g76f97d88a3910100插入n，space[0].data=e;刪除f，space[5].cur=space[6].curvoidInitSpace_SL(SLinkList&space){//將一維數組space中各分量鏈成一個備用鏈表

//space[0].cur為頭指針，0表示空指針

for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1].cur=0;}//InitSpace_SLintMalloc_SL(SLinkList&space){i=space[0].cur;//返回分配結點的下標，有空閑的

if(space[0].cur)space[0].cur=space[i].cur;returni;}//Malloc_SL算法2.142.15靜態鏈表初始化2.3線性表的鏈式存儲結構voidFree_SL(SLinkList&space,intk){//將下標為k的空閑結點回收到備用鏈表

space[k].cur=space[0].cur;space[0].cur=k;}//Free_SL(2.16)voiddifferece(SLinkList&space,int&S){//依次輸入集合A和B，在space中建立靜態鏈表，S為頭指針

//設space的備用空間足夠大，space[0].cur為其頭指針，

InitSpace_SL(space);//初始化備用空間

S=Malloc_SL(space);//生成S頭結點，分配下標1r=S;scanf(m,n);//r指向表尾元素，輸入A,B元素個數算法2.162.17靜態鏈表初始化2.3線性表的鏈式存儲結構for(j=1;j<=m;++j){//建立集合A的鏈表

i=Malloc_SL(space);//分配結點，i為結點下標

scanf(space[i].data);space[r].cur=i;r=i;//插入到表尾，r指向新表尾

}//forspace[r].cur=0;//創建結束，表尾的指針為空

for(j=1;j<=n;++j){//輸入B元素，在插入否則刪除

scanf(b);p=S;k=space[S].cur;//k指向集合A中第一個結點算法2.17續2.3線性表的鏈式存儲結構while(k!=space[r].cur&&space[k].data!=b){p=k;k=space[k].cur;}//在當前表中查找

if(k==space[r].cur{i=Malloc_SL(space);space[i].data=b;space[i].cur=space[r].cur;space[r].cur=i；r=i;}//ifelse{space[p].cur=space[k].cur;Free_SL(space,k);if(r==k)r=p;}//else}//for}//difference算法2.17續2.3線性表的鏈式存儲結構2.4循環鏈表和雙向鏈表

1.循環鏈表：循環鏈表是表中最后一個結點的指針指向頭結點，使鏈表構成環狀特點：從表中任一結點出發均可找到表中其他結點，提高查找效率操作與單鏈表基本一致，判表尾條件不同單鏈表p或p->next=NULL循環鏈表p或p->next=H

非空表空表HH2.雙向鏈表在雙向鏈表的結點中有兩個指針域，分別指向前驅和后繼。雙向鏈表也可以有循環鏈表。雙向鏈表的存儲結構

typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinklist;priordatanext2.4循環鏈表和雙向鏈表

L空雙向循環鏈表：非空雙向循環鏈表：Labbcapp->prior->next=p=p->next->proir;雙向鏈表的操作雙指針使得鏈表的雙向查找更為方便、快捷NextElem和PriorElem的執行時間為O(1)僅需涉及一個方向的指針的操作和線性鏈表的操作相同插入和刪除需同時修改兩個方向的指針2.4循環鏈表和雙向鏈表

Hab插入算法：在表L中第i個位置之前插入元素e設P指針，p=GetElemP-DuL(L,i)，使其指向第i個結點p

若p=null，則i不存在；p<>null，則為e申請結點,e賦值xs

插入

s->prior=p->prior

p->prior->next=s

s->next=pp->prior=s算法實現2.18思考：四個指針的修改順序可否任意改變？刪除算法：刪除表L中第i個元素，賦于e。P37算法2．19

設P指針，p=GetElemP-DuL(L,i)，使其指向第i個結點pp=null，則i不存在；若p<>null，p指向第i個結點，將其賦給e

刪除

p->prior->next=p-nextp->next->prior=p->priorHbca算法實現算法評價：T(n)=O(1)2.19與單鏈表相同2.5一元多項式的表示及相加

可用線性表P表示

但對S(x)這樣的多項式浪費空間

一般

其中

用數據域含兩個數據項的線性表表示其存儲結構可以用順序存儲結構，也可以用單鏈表一元多項式的表示coefexpnext一元多項式相加單鏈表的結點定義TypedefstructPnode{floatcoef;intexpn;structPnode*next;}term,ElemType;-1A70517^3198-98^22781-1B-1C70517^111227和存放在A鏈中設p,q分別指向A,B中某一結點，p,q初值是第一結點比較p->exp與q->expp->exp<q->exp:p結點是和多項式中的一項

p后移,q不動p->exp>q->exp:q結點是和多項式中的一項將q插在p之前,q后移,p不動p->exp=q->exp:

系數相加0：從A表中刪去p,

釋放p,q，p,q后移

0：修改p系數域,

釋放q，p,q后移直到p或q為NULL

若q==NULL，結束

若p==NULL，將B中剩余部分連到A上即可運算規則釋放B的表頭q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^算法描述2.20本章小結線性表是n(n≥0)個數據元素的序列，通常寫成

（a1,…,ai-1,ai,ai+1,…an）線性表中除了第一個和最后一個元素之外，都只有一個前驅和一個后繼。線性表中每個元素都有自己確定的位置，即“位序”。n=0時的線性表稱為“空表”，在寫線性表的操作算法時一定要考慮你的算法對空表的情況是否也正確。順序表是線性表的順序存儲結構的一種別稱。特點是以“存儲位置相鄰”表示兩個元素之間的前驅、后繼關系。優點是可以隨機存取表中任意一個元素。缺點是每作一次插入或刪除操作時，平均來說必須移動表中一半元素。常應用于主要是為查詢而很少作插入和刪除操作，表長變化不大的線性表。本章小結鏈表是線性表的鏈式存儲結構的別稱。特點：是以“指針”指示后繼元素，因此線性表的元素可以存儲在存儲器中任意一組存儲單元中。優點：是便于進行插入和刪除操作。缺點：是不能進行隨機存取，每個元素的存儲位置都存放在其前驅元素的指針域中，為取得表中任意一個數據元素都必須從第一個數據元素起查詢。由于它是一種動態分配的結構，結點的存儲空間可以隨用隨取，并在刪除結點時隨時釋放，以便系統資源更有效地被利用。這對編制大型軟件非常重要，作為一個程序員在編制程序時必須養成這種習慣。本章小結基礎知識題描述以下三個概念的區別：頭指針，頭結點，首元結點(第一個元素結點)。簡述線性表的兩種存儲結構順序表和鏈表的優缺點。已知L是無表頭結點的單鏈表，且P是指向表中某個結點的指針，試寫出在P所指結點之前插入指針S所指結點的語句序列。已知P是指向雙向鏈表中某個結點的指針，試寫出刪除P所指結點的前驅結點的語句序列。簡述以下算法的功能。

(1)StatusA(LinkedListL){//L是無表頭結點的單鏈表

if(L&&L->next){

Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

}

returnOK;

}//A

(2)voidBB(LNode*s,LNode*q){

p=s;

while(p->next!=q)p=p->next;

p->next=s;

}//BB

voidAA(LNode*pa,LNode*pb){

//pa和pb分別指向單循環鏈表中的兩個結點

BB(pa,pb);

BB(pb,pa);

}//AA基礎知識題1.設順序表

a中的數據元素遞增有序。試寫一算法，將x插入到順序表的適當位置上，以保持該表的有序性。

voidInsertOrderList(SqList&a,ElemTypex)

//已知順序表a中的數據元素遞增有序，將x插入到順序表的適當位置上，以保持該表的有序性。2.設A=(,…,)和B=(,…,)均為順序表，A'和B'分別為A和B中除去最大共同前綴后的子表（例如，A=(x,y,y,z,x,z)，B=(x,y,y,z,y,x,x,z)，則兩者中最大的共同前綴為(x,y,y,z)，在兩表中除去最大共同前綴后的子表分別為A'=(x,z)和B'=(y,x,x,z)）。若A'=B'=空表，則A=B；若A'=空表，而B'≠空表，或者兩者均不為空表，且A'的首元小于B'的首元，則A<B；否則A>B。試寫一個比較A、B大小的算法。（請注意：在算法中，不要破壞原表A和B，并且，也不一定先求得A'和B'才進行比較）

charCompare(SqListA,SqListB)

//已知順序表A和B,返回'<'(若'A<B')或'='(若'A=B')或'>'(若'A>B')編程題3.已知線性表中的元素以值遞增有序排列，并以單鏈表作存儲結構。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素(若表中存在這樣的元素)同時釋放被刪結點空間。（注意：mink和maxk是給定的兩個參數值，它們的值可以和表中的元素相同，也可以不同）

voiddel_between_mink_and_maxk(LinkList&hlink,ElemTypemink,ElemTypemaxk)

//hlink為指向單鏈表頭結點的指針，刪除鏈表中其值介于mink和maxk之間的結點。4.試寫一算法，實現順序表的就地逆置，即利用原表的存儲空間將線性表(a1,…,an)逆置為(an,an