工大數(shù)據(jù)結(jié)構(gòu)第二章作業(yè)(共68頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與算法上機(jī)作業(yè)第二章 線性表一、選擇題1、若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新的元素算法的時間復(fù)雜度為 。A. O(log2n)B. O(1)C. O(n)D. O(n2)2、以下關(guān)于線性表的說法中，不正確的是 。A. 線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、結(jié)構(gòu)等不同類型B. 線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的C. 線性表中的每一個結(jié)點都有且只有一個直接前驅(qū)和直接后繼（單項鏈表）D. 存在這樣的線性表：表中各結(jié)點都沒有直接前驅(qū)和直接后繼（數(shù)組實現(xiàn)）3、在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復(fù)雜度為 。A. O(1)B. O(n

2、)C. O(n2)D. O(log2n)4、等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點操作，需平均移動的結(jié)點數(shù)目為 。A. nB. (n-1)/2C. n/2D. (n+1)/2已經(jīng)有N個點了,再加一個就是N+1個.假設(shè)新加的結(jié)點插在第i位,那么后面N+1-i個結(jié)點都要往后移動.i的取值服從1到N+1的平均分布,即概率是1/(N+1).求期望得N/2,即平均要移動N/2個結(jié)點 期望有計算公式，這里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+.+(N+1-N-1)*1/(N+1)=N/25、在一個長度為n的順序存儲的線性表中查找值為x的

3、元素時，平均查找長度(及x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等)為 。A. nB. n/2C. (n+1)/2D. (n-1)/26、在順序表中，只要知道 ，就可以求出任一結(jié)點的存儲地址。A. 基地址B. 結(jié)點大小C. 向量大小D. 基地址和結(jié)點大小7、將兩個各有n個元素的有序表歸并為一個有序表，其最少的比較次數(shù)是 。A. nB. 2n-1C. 2nD. n-18、線性表采用鏈表存儲時其存儲地址要求 。A. 必須是連續(xù)的B. 部分地址必須是連續(xù)的C. 必須是不連續(xù)的D. 連續(xù)的和不連續(xù)的都可以9、下面關(guān)于線性表的描述中，錯誤的是 。A. 線性表采用順序存儲，必須占用一片連續(xù)的存儲

4、單元B. 線性表采用順序存儲，便于進(jìn)行插入和刪除操作C. 線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元D. 線性表采用鏈?zhǔn)酱鎯?，便于插入和刪除操作10、向具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是 A. O(1)B. O(n)C. O(n2)D. O(log2n)11、 語句是 。A. HL=p; p->next=HL;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. p->next=HL->next; HL->next=p;HL為鏈表的頭指針。HL指示鏈表中第一個節(jié)點的存儲位置，在表頭插入一個由指

5、針p指向的節(jié)點后，頭指針指向p，p的指針域指向原鏈表中第一個節(jié)點12、在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行的語句是 。A. p=q->next; p->next=q->next;B. p=q->next; q->next=p;C. p=q->next; q->next=p->next;D. q->next=q->next->next; q->next=q;？13、設(shè)有編號為1, 2, 3, 4的4輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，下列不可能的出棧順序為 。A. 1234B. 1243C. 132

6、4D. 1423至少有14種。全進(jìn)之后再出情況只有1種：4，3，2，1進(jìn)3個后再出的情況有3種3,4,2,1 3,2,4,1 3,2,1,4進(jìn)2個后再出的情況有5種2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4進(jìn)1個后再出的情況，有5種1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,314、4個元素按A, B, C, D順序進(jìn)入S棧，執(zhí)行兩次Pop(S, x)運算后，棧頂元素的值是 。A. AB. BC. CD. D15、從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應(yīng)執(zhí)行下列 命令。A. x=top; to

7、p=top->next;B. top=top->next; x=top->data;C. x=top->data;D. x=top->data; top=top->next;16、向順序棧中輸入元素時 。A. 先存入元素，后移動棧頂指針B. 先移動棧頂指針，后存入元素C. 誰先誰后無關(guān)緊要D. 同時進(jìn)行17、設(shè)有一個順序棧，元素A, B, C, D, E, F依次進(jìn)棧，如果6個元素出棧的順序是B, D, C, F, E, A，則棧的容量至少為 。A. 3B. 4C. 5D. 6順序如下A入棧B入棧然后B出棧,C入棧D入棧,D出棧,C出棧,E入棧,F入棧,F出

8、棧,E出棧.棧里元素最多時候就是acd和aef,所以3個就夠了18、設(shè)已將元素A, B, C依次入棧，元素D正等待進(jìn)棧。那么下列4個序列中不可能出現(xiàn)的出棧順序為 。A. CADBB. CBDAC. CDBAD. DCBA19、棧和隊列的相同之處是 。 A.元素的進(jìn)出滿足先進(jìn)后出 B.元素的進(jìn)出滿足后進(jìn)先出 C.只允許在端點進(jìn)行插入和刪除操作 D.無共同點 棧Insert(L,n+1,x)Delete(L,n)而棧只允許在表尾一端進(jìn)行插入和刪除隊列Insert(L,n+1,x)Delete(L,1)隊列只允許在表尾一端進(jìn)行插入，在表頭一端進(jìn)行刪除20、設(shè)棧S 和隊列Q 的初始狀態(tài)為空,元素e1，

9、e2，e3，e4，e5 和e6 依次通過棧，一個元素出棧后即進(jìn)入隊列Q,若6 個元素出隊的序列是e2，e4，e3，e6，e5，e1，則棧S 的容量至少應(yīng)該是 。 A. 6 B. 4 C. 3 D. 2 設(shè)棧長度為s,起始為0因為棧后進(jìn)先出,隊列先進(jìn)先出.又因為元素E1.E6是順序入棧,那么分析過程如下：按照出棧過程分析,因為給定出棧順序：E2,E4,E3,E6,E5,E1,E2要進(jìn)棧,所以E1必須進(jìn)棧,進(jìn)棧順序：E1,E2,所以s為2下面E2出棧,打印出E2,剩余結(jié)果為E4,E3,E6,E5,E1,因為E2出棧了,所以當(dāng)前棧容量為2,但是只是用了1個,存放E1,下面繼續(xù)E3進(jìn)棧,E4進(jìn)棧,此時

10、s為3,根據(jù)出棧結(jié)果,那么E4出棧,E3出棧,此時棧容量為3但是只有E1在棧中,剩余結(jié)果為E6,E5,E1,同理,E5進(jìn)棧,E6進(jìn)棧,此時棧被填滿,容量為3,后E6出棧,E5出棧,E1出棧,?？?容量為3.所以S的容量至少為3.21、隊列通常采用的兩種存儲結(jié)構(gòu)是( )。A. 順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) B.散列方式和索引方式C. 鏈表存儲結(jié)構(gòu)和線性存儲結(jié)構(gòu) D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)22、循環(huán)隊列SQ隊滿的條件是 。A. SQ->rear=SQ->frontB. (SQ->rear+1)%MAXLEN=SQ->frontB. SQ->rear=0D. SQ-

11、>front=0隊空:Q.front=Q.rear 隊滿:(Q.rear+1)%MAXQSIZE=Q.front23、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為 。A. 5和1B. 4和2C. 2和4D. 1和524、鏈棧與順序棧相比，有一個較為明顯的優(yōu)點是 。A. 通常不會出現(xiàn)滿棧的情況B. 通常不會出現(xiàn)?？盏那闆rC. 插入操作更加方便D. 刪除操作更加方便25、設(shè)用一個大小為M=60的順序表AM表示一個循環(huán)隊列，如果當(dāng)前的尾指針rear=32，頭指針front=15，則當(dāng)前

12、循環(huán)隊列的元素的個數(shù)為 。A. 42B. 16C. 17D. 4126、串是一種特殊的線性表，其特殊性體現(xiàn)在 。A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C. 可以鏈?zhǔn)酱鎯. 數(shù)據(jù)元素可以是多個字符27、設(shè)主串的長度為n，模式串的長度為m，則串匹配的KMP算法的時間復(fù)雜度為 。A. O(m)B. O(n)C.O(m+n)D. O(m×n)28、已知串S=“abab”，其Next數(shù)組值為 。A. 0123B. 0121C. 0112D. 012229、若字符串“ABCDEFG”采用不帶表頭的鏈?zhǔn)酱鎯?，每個結(jié)點保存一個字符。假設(shè)每個字符占用1個字節(jié)，每個指針占用兩個字節(jié)，則該字符串的存

13、儲密度為 。A. 20%B. 40%C. 50%D. 33.3%存儲密度;結(jié)點數(shù)據(jù)本身所占的存儲量/結(jié)點結(jié)構(gòu)所占的存儲量 1/（1+3）30、在雙向鏈表中，在指針p所指的結(jié)點前插入一個指針q所指向的結(jié)點，操作是 。A. p->Prior=q; q->Next=p; p->Prior->next=q; q->Prior=q;B. p->Prior=q; p->Prior->next=q; q->next=p; q->Prior=p->Prior;C. q->Next=p; q->Prior=p->Prior; p

14、->Prior->Next=q; p->Prior=q;D. q->Prior=p->Prior; q->Next=q;p->Prior=q; p->Next=q;31、已知循環(huán)隊列存儲在一維數(shù)組A0n-1中，且隊列非空時front和rear分別指向?qū)︻^元素和隊尾元素，且要求第一個進(jìn)入隊列的元素存儲在A0處，則初始時front和rear的值分別是 。A. 0, 0B. 0, n-1C. n-1, 0D. n-1, n-132、某隊列允許在兩端進(jìn)行入隊操作，但僅允許在一端進(jìn)行出隊操作（稱為輸出受限的雙端隊列），若a, b, c, d, e元素依次進(jìn)

15、隊，則不可能得到的順序是 。A. bacdeB. dbaceC. dbcaeD. ecbad33、在雙向鏈表中間插入一個結(jié)點時，需要修改修改 個指針域。A. 1B. 2C. 3D. 434、在按行優(yōu)先順序存儲的三元組表中，下述陳述錯誤的是 。A. 同一行的非零元素，是按列號遞增次序存儲的B. 同一列的非零元素，是按行號遞增次序存儲的C. 三元組表中三元組行號是非遞減的D. 三元組表中三元組列號是非遞減的35、在稀疏矩陣的三元組表示法中，每個三元組表示 。A. 矩陣中非零元素的值B. 矩陣中數(shù)據(jù)元素的行號和列號C. 矩陣中數(shù)據(jù)元素的行號、列號和值D. 矩陣中非零數(shù)據(jù)元素的行號、列號和值36、對特

16、殊矩陣采用壓縮存儲的目的主要是為了 。A. 表達(dá)變得簡單B. 對矩陣元素的存取變得簡單C. 去掉矩陣中的多余元素D. 減少不必要的存儲空間37、廣義表是線性表的推廣，它們之間的區(qū)別在于 。A. 能否使用子表B. 能否使用原子項C. 表的長度D. 是否能為空38、已知廣義表(a, b, c, d)的表頭是 ，表尾是 。A. aB. ()C. (a, b, c, d)D. (b, c, d)39、下面說法不正確的是 。A. 廣義表的表頭總是一個廣義表B. 廣義表的表尾總是一個廣義表C. 廣義表難以用順序存儲結(jié)構(gòu)表示D. 廣義表可以是一個多層次的結(jié)構(gòu)40、若廣義表A滿足Head(A)=Tail(A)

17、，則A為 。A. ( )B. ()C. ( ),( )D. ( ), ( ), ( )二、填空題1、線性表中結(jié)點的集合是有限的，結(jié)點之間的關(guān)系是 一對一 關(guān)系。2、順序表中訪問任一個結(jié)點的時間復(fù)雜度為 O（1） 。3、線性表中第一個結(jié)點沒有直接前驅(qū)，稱為 頭 結(jié)點。4、在一個長度為n的順序表中刪除第i個元素，要移動 n-i 個元素。5、在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n-i-1 個元素，在插入操作中，移動元素的均值為 （n+1）/2 。6、根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成 單向鏈表 和 雙向鏈表 。7、鏈?zhǔn)酱鎯Φ奶攸c是利用

18、指針 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。8、靜態(tài)鏈表(線性表的游標(biāo)實現(xiàn))是指用 數(shù)組下標(biāo) 表示單鏈表的指針。9、在靜態(tài)鏈表中，一般都有一個變量available表示的結(jié)點鏈，其中的結(jié)點為 空閑結(jié)點 。10、在棧中，可進(jìn)行插入和刪除操作的一端稱 棧頂 。11、在進(jìn)棧運算時，應(yīng)先判別棧是否 滿 。在出棧運算時應(yīng)先判別棧是否 空 。當(dāng)棧中元素為n個時，進(jìn)棧運算時發(fā)生上溢，則說明該棧的最大容量為 n 。12、設(shè)有一空棧，現(xiàn)有輸入序列為1, 2, 3, 4, 5，經(jīng)過push, push, pop, push, pop, push, push, pop, pop之后，輸出序列為 2354 。13、對于循環(huán)向

19、量的循環(huán)隊列，求隊列長度的公式為 （rear-front+n+1）%n 。14、棧的邏輯特點是 先進(jìn)后出 。隊列的邏輯特點是 先進(jìn)先出 。兩者的共同特點是只允許在它們的 端點 出插入和刪除數(shù)據(jù)元素，區(qū)別是 棧在棧頂進(jìn)行插入刪除，隊列在兩端操作，隊尾插入，隊首刪除 。15、鏈隊列LQ為空時，LQ->front->next= NULL .16、在一個鏈隊列中，若隊首指針為front，隊尾指針為rear，則判斷該隊列只有一個結(jié)點的條件為 front.next=rear 。17、設(shè)串S=“Ilikecomputer”，T=“com”，則Length(S)= 13 。Index(S, T)=

20、 6 。18、在KMP算法中，nextj只與 子 串有關(guān)，而與 主串 無關(guān)。19、字符串“ababaab“的Next數(shù)組值是 。20、稀疏矩陣一般壓縮存儲的方式有三種，分別是三原組存儲、行指針鏈表和 十字鏈表。21、二維數(shù)組M中每個元素的長度是3字節(jié)，行下標(biāo)i從07，列下標(biāo)j從09，從首地址&M00開始連續(xù)存放在存儲器中。若按行優(yōu)先的方式存放，元素M75的起始地址為 M00+225 ；若按列優(yōu)先方式存放，元素M75的起始地址為 M00+141 。22、廣義表(a, (a, b), d, e, (i, j), k)的長度是 5 ，深度是 3 。23、設(shè)廣義表A( ), (a, (b),

21、c)，則Cal(Cdr(Cal(Cdr(Cal(A)= （b） 三、寫一個算法合并兩個已排序的線性表。（用兩種方法：數(shù)組表示的線性表（順序表）和指針表示的線性表（鏈表）要求：1、定義線性表節(jié)點的結(jié)構(gòu)，并定義節(jié)點的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main函數(shù)中進(jìn)行測試：先構(gòu)建兩個有序的線性表，然后合并這兩個線性表。四、已知一個單向鏈表，試給出復(fù)制該鏈表的算法。要求：1、定義線性表的節(jié)點的結(jié)構(gòu)以及節(jié)點的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main函數(shù)中進(jìn)行測試：先構(gòu)建一個線性表，并定義一個空線性表，然后

22、進(jìn)行復(fù)制。五、寫出從一個帶表頭的單鏈表中刪除其值等于給定值x的結(jié)點的算法函數(shù)：int delete(LIST &L, int x);如果x在該鏈表中，則刪除對應(yīng)結(jié)點，并返回其在鏈表中的位置（邏輯位置，第一個結(jié)點的邏輯位置為1），否則返回-1。要求：1、定義線性表的節(jié)點的結(jié)構(gòu)以及節(jié)點的型和位置的型。2、定義線性表的基本操作3、在1，2的基礎(chǔ)上，完成本題。4、在main函數(shù)中進(jìn)行測試：先構(gòu)建一個線性表，然后調(diào)用函數(shù)刪除值等于給定值的節(jié)點。三，四，五#include<iostream> using namespace std;  

23、typedef int elementtype;/元素類型   struct celltype/鏈表節(jié)點   elementtype elements;  celltype *next;  ;typedef celltype *LIST;  typedef celltype *position;/線性表的“型”與位置的“型”相同   position End(LIST L)&#

24、160; /返回L中指向最后一個節(jié)點的指針   position p;  p=L;   while(p->next!=NULL)    p=p->next;   return p;     void Insert(elementtype x, position p, LIST &L ) /創(chuàng)建元素x的節(jié)點插在p的后面 

25、   position q   q = new celltype   q->elements = x   q->next = p->next   p->next = q   /時間復(fù)雜性：O(1)    position Locate( elementty

26、pe x, LIST L ) /返回元素x在線性表中的位置    position p   p = L    while ( p->next != NULL )   if ( p->next->elements = x )    r

27、eturn p     else      p = p->next;  return p    /時間復(fù)雜性：O(n)    elementtype Retrieve( position p , LIST L )  return ( p->next ->elements&

28、#160;);  /時間復(fù)雜性：O(1)    void Delete( position p, LIST &L ) /刪除位置p的下一個節(jié)點    position q    if ( p->next != NULL )      q = p->next&#

29、160;   p->next = q->next    delete q        /時間復(fù)雜性：O(1)  position Previous ( position p, LIST L ) /返回位置p的前驅(qū)元素    position q   if&

30、#160;( p = L->next ) cout<<”不存在前驅(qū)元素！"<<endl;   else   q = L    while ( q->next != p )     q = q->next     return q

31、        /時間復(fù)雜度O(n)    position Next ( position p, LIST L ) /返回位置p的后驅(qū)元素    position q    if ( p->next = NULL )   cout<<"不存在后繼元素！&quo

32、t;<<endl;  else   q = p->next;return q    /時間復(fù)雜度O(1)    position MakeNull ( LIST &L )    L = new celltype    L->next = NULL;  return L

33、    /時間復(fù)雜性：O(1)  position First ( LIST L )   return L;  /時間復(fù)雜性：O(1)    void Travel( LIST L )/遍歷線性表元素    position p   p = L->next  &#

34、160;while ( p != NULL)      cout << p->elements<<endl;   p = p->next        /= void Merge(LIST &L,LIST L1,LIST L2)   /合并兩個線性表(鏈表

35、)，將L1，L2合并到L中   position p1=0,p2=0,p3=0;  for(p3=L1;p3;p3=p3->next)     p1=new celltype;    p1->elements=p3->elements;     If(L=0)L=p1;    p2=p1;       

36、;else       p2->next=p1;    p2=p1;         for(p3=L2;p3;p3=p3->next)     p1=new celltype;    p1->elements=p3->elements;   if(L=0) 

37、60;     L=p1;    p2=p1;     else       p2->next=p1;    p2=p1;         p2->next=NULL;     /=/復(fù)制鏈表  void copy(LIST&#

38、160;&L1,LIST L2)   position p1=0,p2=0,p3=0;  for(p3=L2;p3;p3=p3->next)     p1=new celltype;    p1->elements=p3->elements;     If(L1=0)        L1=p1; 

39、60;  p2=p1;       else       p2->next=p1;    p2=p1;         p2->next=NULL;     /= /刪除指定元素的節(jié)點 int Delete(LIST &L,int x)&#

40、160;  int m=1;/指定元素在線性表中的位置  position p1=0,p2=0;  if(L->elements=x)    p1=L;   L=L->next;   delete p1;   return m;     else    p1=p2=L;

41、0;  while(p1->elements!=x && p1->next!=NULL)      p2=p1;    m+;    p1=p1->next;      p2->next=p1->next;    delete p1;      

42、; return m;   return -1;/不存在元素x     void Read(LIST &L,int i) /輸入數(shù)據(jù)  cout<<"請輸入第"<<i<<"個線性表"<<endl;  LIST p1=0,p2=0;  elementtype x;  for(;) &#

43、160;   cout<<"請輸入數(shù)據(jù)(-1作為結(jié)束標(biāo)志):"   cin>>x;   if(x=-1) break;   p1=new celltype;   p1->elements=x;   if(L=0)       L=p1;   

44、0;p2=p1;       else       p2->next=p1;    p2=p1;         p2->next=NULL;    void Write(LIST L) /輸出   position p=L;  

45、;for(;p;p=p->next)     cout<<p->elements<<'t'   cout<<endl;     void main()   cout<<"本次測試的類型為int"<<endl;  LIST L=NULL,L1=NULL,L2=NULL;  Read(L1,1);   c

46、out<<"L1的元素為："<<endl;  Write(L1);  Read(L2,2);   cout<<"L2的元素為："<<endl;  Write(L2);  Merge(L,L1,L2);   cout<<"L1,L2合并后L的元素為："<<endl;  Write(L);  /*  

47、LIST L=NULL,L1=NULL;  read(L);   cout<<"原有的元素："  write(L);  copy(L1,L);   cout<<"復(fù)制之后的元素："  write(L1);      LIST head=NULL;  read(head);  cout<<&qu

48、ot;刪除前："  write(head);   cout<<"請輸入要刪除的數(shù)據(jù)："  Elementtype x;  cin>>x;   int m=Delete(head,x);  cout<<"刪除后："  write(head);  if(m=-1)   cout<<"需

49、要刪除的數(shù)不存在"<<endl;    elsecout<<"需要刪除的數(shù)是第"<<m<<"個"<<endl;    */    /線性表的數(shù)組實現(xiàn)-線性表的合并 #include<iostream> using namespace std;   #define maxlength 100 typedef&

50、#160;int position;/位置類型 typedef int Elementtype;/下標(biāo)類型   struct LIST   Elementtype elementsmaxlength;  int last;/最后一個元素的下標(biāo)  ;   position End(LIST L)/線性表的長度   return (L.last+1); 

51、60;  void Insert(Elementtype x,position p,LIST &L) /在表L的位置p處插入x   position q;   if(L.last>=maxlength-1)   cout<<"list is full"<<endl;    else if(p>L.last+1) |

52、 (p<1)   cout<<"position does not exist"<<endl;   else     for(q=L.last;q>=p;q-)     L.elementsq+1=L.elementsq;    L.last=L.last+1;   L.elementsp=x;

53、0;       void Delete(position p,LIST &L) /刪除位置p處的元素   position q;   if(p>L.last+1) | (p<1)   cout<<"position does not exist"<<endl;    else

54、0;    L.last=L.last-1;   for(q=p;q<=L.last;q+)     L.elementsq=L.elementsq+1;        position Locate(Elementtype x,LIST L) /返回x在表L中的位置   position q;   for(q=0;q<L.l

55、ast;q+)   if(L.elementsq=x)      return q;   return (L.last+1);  /x不存在   Elementtype Retrive(position p,LIST L) /返回L中位置為p的元素   if(p<1) | (p>L.last+1)     

56、cout<<"position does not exist"<<endl;   return -1;      return L.elementsp;    /= /將兩個線性表合并void Merge(LIST &L,LIST L1,LIST L2)   position p,p1,p2;   

57、;position len1=End(L1);/L1的長度  position len2=End(L2);/L2的長度   L.last=len1+len2-1;/合并后L的最后一個元素的位置  p=p1=p2=0for(;p1<len1;)/將L1的元素寫進(jìn)L     L.elementsp=L1.elementsp1;   p+;   p1+;      f

58、or(;p2<len2;)/繼續(xù)將L2的元素寫進(jìn)L     L.elementsp=L2.elementsp2;   p+;   p2+;        void Read(LIST &L,int i) /輸入線性表   cout<<"請輸入第"<<i<<"個線性表的長度："&#

59、160; cin>>L.last;  L.last-;   cout<<"請輸入第"<<i<<"個線性表的元素："<<endl;  for(position p=0;p<=L.last;p+)    cin>>L.elementsp;     void Write(LIST L) /輸出線性表 

60、60; cout<<"線性表的長度為："<<End(L)<<endl;  cout<<"線性表的元素為："<<endl;   for(position p=0;p<=L.last;p+)cout<<L.elementsp<<'t'   cout<<endl;      void main() 

61、0; cout<<"本次測試的類型為int"<<endl;  LIST L,L1,L2;  Read(L1,1);  Read(L2,2);  Merge(L,L1,L2);  Write(L);  六、寫出一個將兩個靜態(tài)鏈表（屬于同一個存儲池）合并的算法函數(shù)： void Merge(cursor M, cursor N); 合并的方法是將N鏈表中的所有結(jié)點添加到M鏈表的后面，并將N鏈表的表頭結(jié)點添加到空閑結(jié)點鏈表中。要求

62、：1、定義靜態(tài)鏈表的結(jié)點的結(jié)構(gòu)以及結(jié)點的型SPACE以及位置（position）和游標(biāo)（cursor）的型。2、定義靜態(tài)鏈表的基本操作：void Initialize(); 初始化，將所有存儲池中的結(jié)點設(shè)置為空閑；cursor GetNode(); 從空閑鏈中獲取一個結(jié)點；void FreeNode(cursor q); 將結(jié)點q加入到空閑鏈； void Insert ( elementtype x, position p, cursor M ); 在鏈表M中的位置為p的元素后面添加一個值為x的結(jié)點；void Delete (cursor M, position p ); 在鏈表M中刪除位置為

63、p的元素的后一個元素。3、在1、2的基礎(chǔ)上完成本題。 4，在main函數(shù)中進(jìn)行測試：先構(gòu)建一個存儲池，然后在該存儲池中創(chuàng)建兩個靜態(tài)表，最后將這兩個靜態(tài)表合并。#include<iostream> using namespace std;  #define maxsize 100 typedef int elementtype;typedef struct   elementtype element   i

64、nt next    spacestr; /*結(jié)點類型*/    spacestr SPACE maxsize  /*存儲池*/   typedef int position, cursor;  cursor available;/* 標(biāo)識線性表/空閑池*/   void Initialize()   int j;   

65、;/* 依次鏈接池中結(jié)點*/  for (j=0; j<maxsize-1; j+ )    SPACEj.next=j+1;   SPACEj.next=-1;/* 最后一個接點指針域為空*/   available=0;/* 標(biāo)識線性表,將所有存儲池中的結(jié)點設(shè)置為空閑，avilable為頭結(jié)點，不利用*/     / 可用空間的分配操作,從空閑鏈中獲取一個結(jié)點 cursor&#

66、160;GetNode() / q=new spacest    cursor p;   if (SPACEavailable.next =-1)   p=-1;   else      p= SPACEavailable.next     SPACEavailable.next = SPACE&#

67、160;p .next     return p;  /* 將空閑池頭結(jié)點的下一個節(jié)點從空閑池中刪除*/    void FreeNode(cursor q) /delete q; SPACE  q .next =SPACEavailable.next   SPACEavailable.next = q   /* 將q

68、指向的節(jié)點放回池中*/   / 在位置p后面插入元素值為x的結(jié)點 void Insert ( elementtype x, position p)    position q   q = GetNode( )  SPACE q .element = x    SPACE q .n

69、ext = SPACE p .next   SPACE p .next = q      / 刪除位置p后的一個結(jié)點 void Delete ( position p)    position q；    if ( SPACE p .next != 

70、-1 )      q = SPACE p .next  ； SPACE p .next = SPACE q .next  ；  FreeNode( q )         /創(chuàng)建靜態(tài)鏈表 void Create(cursor M) 

71、60; elementtype input;  position p = M;  while(1)     cout<<"請輸入靜態(tài)鏈表的值，輸入-1結(jié)束："<<endl;   cin>>input;   if(input != -1)         

72、 Insert(input,p);p = SPACEp.next;       else     break;        void Merge(cursor M,cursor N)  /連接兩個鏈表,將N鏈表中的所有結(jié)點添加到M鏈表的后面，并將N鏈表的表頭結(jié)點添加到空閑結(jié)點鏈表中   position p;  p=M;

73、60;  while(SPACEp.next!=-1)    p=SPACEp.next;   position q; q=SPACEN.next;  SPACEp.next=q;  FreeNode(N);     /輸出靜態(tài)鏈表 void Print(cursor M)   position p;  p = M;  

74、0;while(SPACEp.next != -1)     cout<<SPACESPACEp.next.element<<'t'   p = SPACEp.next;      cout<<endl;    void main()     spacestr s;  Initialize();