【正文】 List_Sq(amp。 //修改長度 return 1。ki。L,int i,ElemType e){ int k。 // delete[]。L){// ElemType *a=new ElemType[+]。算法思想(1) 先編寫函數(shù)IncSize(amp。查找的時(shí)間復(fù)雜度是按最壞的情況來考慮，即查找的是最后一個(gè)元素或找不到該元素，其比較次數(shù)為n次,所以查找的時(shí)間復(fù)雜度為：。 if(i)return i+1。算法實(shí)現(xiàn)int LocateElem_Sq(SqList L,ElemType e){ int i=0。L,int i,ElemType e){ if(i1||i)return 0。 //通過參數(shù)e得到第i個(gè)元素的值 return 1。e)該操作將順序表L中第i個(gè)元素的值賦值到e中，如果提取成功返回1否則返回0。//動(dòng)態(tài)分配一個(gè)長度為maxlength的連續(xù)存儲(chǔ)空間，類型為ElemType， =0。（3）置表的當(dāng)前容量listsize為動(dòng)態(tài)分配時(shí)的大小；（4）置容量擴(kuò)充值incsize的大小為INCSIZE。1．初始化操作InitList_Sq(amp。 //當(dāng)前表的存儲(chǔ)容量 int incsize。 //定義順序表存儲(chǔ)空間大小的初始分配常量const int INCSIZE=50。設(shè)順序表中元素的首地址為，每個(gè)元素需要占用的字節(jié)數(shù)為，則表中任一元素的存儲(chǔ)位置可用下面的公式算出：。（8）遍歷TraverseList(L)：依次輸出L中每個(gè)元素的值。（6）刪除DeleteList(amp。L,i,e)：修改表L中第i個(gè)元素的值為e的運(yùn)算。L）：構(gòu)造一個(gè)空線性表L的運(yùn)算。按表中的排列順序，元素‘0’是第一個(gè)元素沒有前驅(qū)，元素‘Z’是最后一個(gè)元素沒有后繼。其中的數(shù)據(jù)元素是整數(shù)，該線性表的長度為10。其中：a0是開始結(jié)點(diǎn)，an1是終端結(jié)點(diǎn)，ak是ak+1的直接前驅(qū)結(jié)點(diǎn)，而ak+1是ak的直接后繼結(jié)點(diǎn)(k=0,1,2,…,n2)；終端結(jié)點(diǎn)an1沒有后繼結(jié)點(diǎn)，開始結(jié)點(diǎn)a0沒有前驅(qū)結(jié)點(diǎn)；元素ai(i=0,1,2…,n1)在表中的位置為i+1；元素的個(gè)數(shù)n稱為線性表L的長度，長度為零的線性表叫空表。線性表的基本操作主要有插入、刪除和查找等?！羰炀氄莆枕樞虮砗玩湵砩细鞣N基本操作的實(shí)現(xiàn)過程。第2章 線性表及其應(yīng)用第2章 線性表及其應(yīng)用本章學(xué)習(xí)要點(diǎn)◆掌握線性表的邏輯結(jié)構(gòu)及相關(guān)概念。◆靈活運(yùn)用順序表和鏈表的特點(diǎn)解決實(shí)際應(yīng)用問題。本章將具體給出線性表的定義、存儲(chǔ)結(jié)構(gòu)、基本操作及其算法實(shí)現(xiàn)，最后給出線性表的應(yīng)用實(shí)例。需要說明的是：在C/C++語言中，數(shù)組元素的下標(biāo)是從0開始的，具有n個(gè)數(shù)據(jù)元素的數(shù)組A的所有元素為A[0],A[1],…,A[n1]。按表中的排列順序，元素1是第一個(gè)元素沒有前驅(qū)，元素10是最后一個(gè)元素沒有后繼。【】。（2）提取GetElem(L,i,amp。（4）查找LocateElem(L,e)：查找表L中第一個(gè)值與e相同的元素的位置。L,i,amp。在線性表的其它操作中，有些操作可以通過調(diào)用基本操作來實(shí)現(xiàn)，有些操作比如線性表的排序和歸并等操作的實(shí)現(xiàn)將在以后的章節(jié)中進(jìn)行。2．順序表的結(jié)構(gòu)定義順序表的存儲(chǔ)結(jié)構(gòu)和一維數(shù)組的存儲(chǔ)結(jié)構(gòu)極為相近；但是由于在線性表中允許執(zhí)行插入和刪除等操作，也就是說一個(gè)線性表的長度是可變的，為適應(yīng)這種情況在C++語言中用以下結(jié)構(gòu)類型來表示順序表。 //定義順序表存儲(chǔ)空間的擴(kuò)充常量值struct SqList //定義順序表的結(jié)構(gòu)類型為SqList{ ElemType *elem。 //一次增補(bǔ)的容量值 }。L)該操作的功能是構(gòu)造一個(gè)空線性順序表L。 =maxlength。算法實(shí)現(xiàn)int GetElem_Sq(SqList L,int i,ElemType amp。 }}3．修改操作SetElem_Sq(amp。 else { [i1]=e。 while(iamp。 else return 0。5．插入操作InsertList_Sq(amp。L),；(2) 如果插入的位置i不合理返回0，表示插入不成功；(3) ，則調(diào)用函數(shù)IncSize(amp。 for(int i=0。 // =a。 if(i1||i+1)return 0。k) [k]=[k1]。}算法分析從以上算法可見，在不考慮擴(kuò)容的情況下，插入運(yùn)算的時(shí)間主要花費(fèi)在元素的向后移動(dòng)上。L,i,amp。算法實(shí)現(xiàn)int DeleteList_Sq(SqList amp。 //置e的值為L中第i個(gè)元素的值 while(i) //將L中第i個(gè)以后的所有元素都依次向前移動(dòng)一個(gè)位置 { [i1]=[i]。}算法分析刪除運(yùn)算的時(shí)間主要花費(fèi)在元素的向前移動(dòng)上。算法實(shí)現(xiàn)int Length_Sq(SqList L){ return 。i。 }}在前面順序表的結(jié)構(gòu)定義及其基本操作算法的基礎(chǔ)上，本節(jié)給出順序表的各個(gè)基本操作的綜合演示程序代碼以及運(yùn)行結(jié)果。 InitList_Sq(L)。 for(i=1。 }}2．綜合演示主程序void main_Sq(){ SqList L。 cout順序表的初始數(shù)據(jù)為:\n。 cout7退出演示程序：。 cini。 case 2: cout輸入修改位置i和值e:。 case 3: cout輸入插入位置i和值e:。 case 4: cout輸入刪除位置i:。 break。 else cout表中位置: i 處的值為：e\n。 break。 }//end_switch }//end_while}//end_main_Sq()（運(yùn)行結(jié)果略） 順序存儲(chǔ)結(jié)構(gòu)小結(jié)在順序表的存儲(chǔ)結(jié)構(gòu)中，由于表中數(shù)據(jù)元素的存儲(chǔ)順序與元素之間的邏輯順序完全一致，因此確定表中元素的存儲(chǔ)位置非常容易，訪問表中任一元素也就非常方便。L)來批量移動(dòng)記錄，從而浪費(fèi)大量的時(shí)間；如果選取的值較大，但是在實(shí)際運(yùn)行時(shí)很少進(jìn)行插入操作，這將導(dǎo)致存儲(chǔ)空間的大量浪費(fèi)；（3）順序存儲(chǔ)要求一次分配足夠大的連續(xù)的內(nèi)存空間，如果當(dāng)前系統(tǒng)中沒有連續(xù)的足夠大的空閑空間可用，這將導(dǎo)致內(nèi)存分配失敗。從第一個(gè)人開始報(bào)數(shù)（從1到m報(bào)數(shù)），凡報(bào)到m的人退出圈子并記下此人的排號(hào)，當(dāng)最后一個(gè)人退出圈子時(shí)，按出圈次序依次輸出所有人原來的排號(hào)序列（用線性順序表編程實(shí)現(xiàn)）。 //定義線性順序表L coutinput n m:。i=n。 for(i=0。 //刪除第k+1個(gè)人并提取其編號(hào)到e中 coute ?！尽吭嚲帉懸凰惴?，實(shí)現(xiàn)對(duì)線性順序表L的逆置操作。 //定義指向第一個(gè)元素和指向最后一個(gè)元素的下標(biāo)i、j ElemType t。 i++,j。 Inverst_Sq(L)。為了能正確表示線性表中的每個(gè)數(shù)據(jù)元素以及它們之間存在的邏輯關(guān)系（前驅(qū)與后繼關(guān)系），對(duì)于一個(gè)數(shù)據(jù)元素來說，除了要存儲(chǔ)它本身的信息之外，還需要存儲(chǔ)指示其直接后繼元素的指針（地址）信息。含有n個(gè)數(shù)據(jù)元素的線性表 ，(b)所示的方法構(gòu)成一個(gè)具有n個(gè)結(jié)點(diǎn)的鏈表，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。為了對(duì)單鏈表的各種操作進(jìn)行統(tǒng)一處理和方便表示，在鏈表的開頭增設(shè)一個(gè)結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，它的結(jié)構(gòu)與鏈表中其他結(jié)點(diǎn)的結(jié)構(gòu)一樣，但在data域中不存放數(shù)據(jù)。}*LinkList。L)該操作是構(gòu)造一個(gè)只含有頭結(jié)點(diǎn)的空鏈表L。 //L指向頭結(jié)點(diǎn) Lnext=NULL。算法實(shí)現(xiàn)int GetElem_L(LinkList L,int i,ElemType amp。kiamp。 if(i1||!p)return 0。L,i,e)修改操作修改單鏈表L中第i結(jié)點(diǎn)數(shù)據(jù)域data的值為e的值。 LinkList p=Lnext。p。 return 1。 while(pamp。}5．插入操作InsertList_L(amp。用語句qnext=pnext。算法實(shí)現(xiàn)int InsertList_L(LinkList amp。kiamp。 //查找L中第i個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的指針p if(i1||ki)return 0。 //將q插入L中第i個(gè)結(jié)點(diǎn)之前 pnext=q。e)操作的功能是將單鏈表L中第i個(gè)結(jié)點(diǎn)的值賦值給e，并將該結(jié)點(diǎn)從鏈表中刪除。實(shí)現(xiàn)。L,int i,ElemType amp。kiamp。 if(i1||!pnext)return 0。 delete q。 LinkList p=Lnext。}8．遍歷操作TraverseList_L(L)該操作依次顯示輸出L中每個(gè)結(jié)點(diǎn)中數(shù)據(jù)域的值。 while(p) { coutpdata 。1．建立一個(gè)有n個(gè)結(jié)點(diǎn)的單鏈表void Create_L(LinkListamp。 cout建立鏈表L:\n。 for(i=1。 }}2．單鏈表的綜合演示主程序void main_L(){ LinkList L。 TraverseList_L(L)。 cinnum。 else cout輸入的位置不合理\n。 if(!SetElem_L(L,i,e)) cout輸入的位置不合理,修改不成功\n。 if(!InsertList_L(L,i,e)) cout插入的位置不合理,操作不成功\n。 if(!DeleteList_L(L,i,e)) cout刪除位置不合理,操作失敗\n。 cine。 case 6: TraverseList_L(L)。 default: cout選擇不合理重新選擇\n。但是，相對(duì)于順序表而言雖然插入和刪除操作的時(shí)間復(fù)雜度相同，由于其基本操作中，鏈表僅僅是簡單的指針賦值運(yùn)算而順序表要移動(dòng)整個(gè)記錄，所以順序表實(shí)際花費(fèi)的時(shí)間較多。另一方面，順序表要求較大的連續(xù)存儲(chǔ)空間，而鏈表中的結(jié)點(diǎn)在內(nèi)存中不要求連續(xù)存放。本節(jié)給出的循環(huán)鏈表可以部分彌補(bǔ)以上缺陷。在循環(huán)鏈表中同樣設(shè)有一個(gè)頭結(jié)點(diǎn)，空循環(huán)鏈表只有一個(gè)頭結(jié)點(diǎn)組成并且自成循環(huán)。其原因是在結(jié)點(diǎn)中只有一個(gè)指向直接后繼結(jié)點(diǎn)的指針，而不含指向直接前驅(qū)結(jié)點(diǎn)的指針信息。DNode *next,*prior。雙向鏈表的特點(diǎn)是可以直接求得鏈表中任意一個(gè)結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。在C++語言中靜態(tài)鏈表的結(jié)構(gòu)類型定義如下：const int MAXSIZE=1000。其中，SNode為靜態(tài)鏈表的結(jié)點(diǎn)類型（相當(dāng)于鏈表的結(jié)點(diǎn)類型），數(shù)據(jù)域data中存放元素的數(shù)據(jù)，下標(biāo)（游標(biāo)）域cur中存放下一個(gè)元素（直接后繼）的下標(biāo)；SLinkList為靜態(tài)鏈表存儲(chǔ)空間Space的定義類型（相當(dāng)于鏈表中堆空間的類型）。（a）所示。in1。Space)該操作相當(dāng)于堆分配命令語句new,其作用是將Space中的空閑鏈表上第一個(gè)結(jié)點(diǎn)摘取下來并返回該結(jié)點(diǎn)的下標(biāo)。Space){ int p。Space,p) 該操作相當(dāng)于釋放堆空間的語句delete,其作用是將一個(gè)結(jié)點(diǎn)p插入到Space中空閑鏈表上第一個(gè)結(jié)點(diǎn)的位置。 Space[0].cur=p。p)初始化操作是從其存儲(chǔ)空間Space的空閑鏈表中摘取一個(gè)結(jié)點(diǎn)，其下標(biāo)保存到p作為該鏈表的頭結(jié)點(diǎn)的指針。Space,int amp。} （2）靜態(tài)鏈表p的插入操作InsertList_S(amp。算法設(shè)計(jì)代碼如下：int InsertList_S(SLinkList amp。amp。 if(!(q=NewSNode(Space)))//獲取一個(gè)結(jié)點(diǎn) return 0。 return 1。e)該操作刪除p中第i個(gè)結(jié)點(diǎn)將data值賦值給e,并將資源歸還給Space。p,int i,ElemType amp。ki) { h=Space[h].cur。 Space[h].cur=Space[q].cur。}（4）靜態(tài)鏈表p的遍歷操作TraverseList_S(Space,p)該操作按序顯示鏈表p中每一個(gè)結(jié)點(diǎn)的值。 } coutendl。 InitSpace_S(SS)。 cinn。i++) { cine。 TraverseList_S(SS,p)。 while(1) { cout“輸入選擇:”。 if(!InsertList_S(SS,p,i,e)) cout插入的位置不合理,或空間已滿。 cini。 case 3: TraverseList_S(SS,p)。 k++。 return。（3）由于假定系統(tǒng)不能使用指針類型變量，即不能動(dòng)態(tài)分配內(nèi)存，因此當(dāng)空間Space中的空閑鏈表為空時(shí)，將使靜態(tài)鏈表的插入操作失敗。算法實(shí)現(xiàn)void main(){ int m,n,i,k。 p=L。 p=pnext。 cout所求編號(hào)序列為:\n。km。 q=pnext。 } coutendl。 //定義人數(shù)n、間隔數(shù)m、循