南工大第二章 線性表

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

2、)4、等概率情況下，在有n個結(jié)點的順序表上做插入結(jié)點操作，需平均移動的結(jié)點數(shù)目為 d 。A. nB. (n-1)/2C. n/2D. (n+1)/25、在一個長度為n的順序存儲的線性表中查找值為x的元素時，平均查找長度(及x同元素的平均比較次數(shù)，假定查找每個元素的概率都相等)為 b 。A. nB. n/2C. (n+1)/2D. (n-1)/26、在順序表中，只要知道 d ，就可以求出任一結(jié)點的存儲地址。A. 基地址B. 結(jié)點大小C. 向量大小D. 基地址和結(jié)點大小7、將兩個各有n個元素的有序表歸并為一個有序表，其最少的比較次數(shù)是 a 。A. nB. 2n-1C. 2nD. n-18、線性表采

3、用鏈表存儲時其存儲地址要求 d 。A. 必須是連續(xù)的B. 部分地址必須是連續(xù)的C. 必須是不連續(xù)的D. 連續(xù)的和不連續(xù)的都可以9、下面關(guān)于線性表的描述中，錯誤的是 d 。A. 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元B. 線性表采用順序存儲，便于進行插入和刪除操作C. 線性表采用鏈?zhǔn)酱鎯?，不必占用一片連續(xù)的存儲單元D. 線性表采用鏈?zhǔn)酱鎯?，便于插入和刪除操作10、向具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是 b A. O(1)B. O(n)C. O(n2)D. O(log2n)11、在一個帶頭結(jié)點的單鏈表HL中，若要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行的語句是

4、B 。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;12、在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行的語句是 C 。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

5、->next=q;13、設(shè)有編號為1, 2, 3, 4的4輛列車，順序進入一個棧結(jié)構(gòu)的站臺，下列不可能的出棧順序為 D 。A. 1234B. 1243C. 1324D. 142314、4個元素按A, B, C, D順序進入S棧，執(zhí)行兩次Pop(S, x)運算后，棧頂元素的值是 B 。A. AB. BC. CD. D15、從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪除的結(jié)點，應(yīng)執(zhí)行下列 D 命令。A. x=top; top=top->next;B. top=top->next; x=top->data;C. x=top->data;D. x=top-&

6、gt;data; top=top->next;16、向順序棧中輸入元素時 B 。A. 先存入元素，后移動棧頂指針B. 先移動棧頂指針，后存入元素C. 誰先誰后無關(guān)緊要D. 同時進行17、設(shè)有一個順序棧，元素A, B, C, D, E, F依次進棧，如果6個元素出棧的順序是B, D, C, F, E, A，則棧的容量至少為 A 。A. 3B. 4C. 56. 618、設(shè)已將元素A, B, C依次入棧，元素D正等待進棧。那么下列4個序列中不可能出現(xiàn)的出棧順序為 A 。A. CADBB. CBDAC. CDBAD. DCBA19、棧和隊列的相同之處是 C 。 A.元素的進出滿足先進后出 B.元

7、素的進出滿足后進先出 C.只允許在端點進行插入和刪除操作 D.無共同點 20、設(shè)棧S 和隊列Q 的初始狀態(tài)為空,元素e1，e2，e3，e4，e5 和e6 依次通過棧，一個元素出棧后即進入隊列Q,若6 個元素出隊的序列是e2，e4，e3，e6，e5，e1，則棧S 的容量至少應(yīng)該是 C 。 A. 6 B. 4 C. 3 D. 2 21、隊列通常采用的兩種存儲結(jié)構(gòu)是( A)。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隊滿的條件是 B 。A. SQ->rear=SQ->frontB. (SQ-

8、>rear+1)%MAXLEN=SQ->frontC. SQ->rear+2 = SQL->frontD. (SQ->rear+2)%MAXLEN=SQL->front23、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為 B 。A. 5和1B. 4和2C. 2和4D. 1和524、鏈棧與順序棧相比，有一個較為明顯的優(yōu)點是 A 。A. 通常不會出現(xiàn)滿棧的情況B. 通常不會出現(xiàn)棧空的情況C. 插入操作更加方便D. 刪除操作更加方便25、設(shè)用一個大小為M=6

9、0的順序表AM表示一個循環(huán)隊列，如果當(dāng)前的尾指針rear=32，頭指針front=15，則當(dāng)前循環(huán)隊列的元素的個數(shù)為 C 。A. 42B. 17C. 18D. 4126、串是一種特殊的線性表，其特殊性體現(xiàn)在 D 。A. 可以順序存儲B. 數(shù)據(jù)元素是一個字符C. 可以鏈?zhǔn)酱鎯. 數(shù)據(jù)元素可以是多個字符27、設(shè)主串的長度為n，模式串的長度為m，則串匹配的KMP算法的時間復(fù)雜度為 C 。A. O(m)B. O(n)C. O(m+n)D. O(m×n)28、已知串S=“abab”，其Next數(shù)組值為 B 。A. 0123B. 0121C. 0112D. 012229、若字符串“ABCDEF

10、G”采用不帶表頭的鏈?zhǔn)酱鎯?，每個結(jié)點保存一個字符。假設(shè)每個字符占用1個字節(jié)，每個指針占用兩個字節(jié)，則該字符串的存儲密度為 D 。A. 20%B. 40%C. 50%D. 33.3%30、在雙向鏈表中，在指針p所指的結(jié)點前插入一個指針q所指向的結(jié)點，操作是 A 。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-

11、>Prior=p->Prior; p->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ū)︻^元素和隊尾元素，且要求第一個進入隊列的元素存儲在A0處，則初始時front和rear的值分別是 D 。A. 0, 0B. 0, n-1C. n-1, 0D. n-1, n-132、某隊列允許在兩端進行入隊操作，但僅允許在一端進行出隊操作（稱為輸出受限

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

13、行號、列號和值D. 矩陣中非零數(shù)據(jù)元素的行號、列號和值36、對特殊矩陣采用壓縮存儲的目的主要是為了 C 。A. 表達變得簡單B. 對矩陣元素的存取變得簡單C. 去掉矩陣中的多余元素C. 減少不必要的存儲空間37、廣義表是線性表的推廣，它們之間的區(qū)別在于 A 。A. 能否使用子表B. 能否使用原子項C. 表的長度D. 是否能為空38、已知廣義表(a, b, c, d)的表頭是 A ，表尾是 D 。A. aB. ()C. (a, b, c, d)D. (b, c, d)39、下面說法不正確的是 A 。A. 廣義表的表頭總是一個廣義表B. 廣義表的表尾總是一個廣義表C. 廣義表難以用順序存儲結(jié)構(gòu)表示

14、D. 廣義表可以是一個多層次的結(jié)構(gòu)40、若廣義表A滿足Head(A)=Tail(A)，則A為 C 。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)中每一個

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

16、 pop, push, push, pop, pop之后，輸出序列為 push 。13、對于循環(huán)向量的循環(huán)隊列，求隊列長度的公式為 （rear-front+n+1）%n 。14、棧的邏輯特點是 先進后出 。隊列的邏輯特點是 先進先出 。兩者的共同特點是只允許在它們的 端點 出插入和刪除數(shù)據(jù)元素，區(qū)別是 棧在頂點進行插入和刪除，而隊列在隊首進行刪除，在隊尾進行插入 。15、鏈隊列LQ為空時，LQ->front->next= NULL/LQ->rear .16、在一個鏈隊列中，若隊首指針為front，隊尾指針為rear，則判斷該隊列只有一個結(jié)點的條件為 front-rear=1/

17、front->next=rear 。17、設(shè)串S=“Ilikecomputer”，T=“com”，則Length(S)= 14 。Index(S, T)= 6 。18、在KMP算法中，nextj只與主竄S 串有關(guān)，而與 子串 無關(guān)。19、字符串“ababaab“的Next數(shù)組值是 0121301 。20、稀疏矩陣一般壓縮存儲的方式有三種，分別是 三元組存儲，行指針鏈表 、 和 十字鏈表 。21、二維數(shù)組M中每個元素的長度是3字節(jié)，行下標(biāo)i從07，列下標(biāo)j從09，從首地址&M00開始連續(xù)存放在存儲器中。若按行優(yōu)先的方式存放，元素M75的起始地址為 SA+225 ；若按列優(yōu)先方式存放

18、，元素M75的起始地址為 SA+141 。22、廣義表(a, (a, b), d, e, (i, j), k)的長度是 6 ，深度是 3 。23、設(shè)廣義表A( ), (a, (b), c)，則Cal(Cdr(Cal(Cdr(Cal(A)= (b) 三、寫一個算法合并兩個已排序的線性表。（用兩種方法：數(shù)組表示的線性表（順序表）和指針表示的線性表（鏈表）要求：1、定義線性表節(jié)點的結(jié)構(gòu)，并定義節(jié)點的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main函數(shù)中進行測試：先構(gòu)建兩個有序的線性表，然后合并這兩個線性表。#include<iostream>us

19、ing namespace std;int main()int a10 = 0,1,2,3,4;int b5 = 5,6,7,8,9;for (int i = 5; i < 10; i+)ai = bi - 5;for (int i = 0; i < 10; i+)cout << ai<<" "system("pause");return 0;#include <iostream> using namespace std;struct ListNodeint m_nValue;ListNode *m_pNe

20、xt;/合并兩個有序鏈表,非遞歸方法 ListNode *MergeTwoList(ListNode *pListOneHead, ListNode *pListTwoHead)if (pListOneHead = NULL)return pListTwoHead;if (pListTwoHead = NULL)return pListOneHead;ListNode *pNode1 = pListOneHead;ListNode *pNode2 = pListTwoHead;ListNode *pMergeListHead = NULL;ListNode *pCurLastNode = NU

21、LL;if (pNode1->m_nValue < pNode2->m_nValue)pMergeListHead = pListOneHead;pNode1 = pNode1->m_pNext;pCurLastNode = pMergeListHead;elsepMergeListHead = pListTwoHead;pNode2 = pNode2->m_pNext;pCurLastNode = pMergeListHead;while (pNode1 != NULL && pNode2 != NULL)if (pNode1->m_nVa

22、lue < pNode2->m_nValue)pCurLastNode->m_pNext = pNode1;pCurLastNode = pNode1;pNode1 = pNode1->m_pNext;elsepCurLastNode->m_pNext = pNode2;pCurLastNode = pNode2;pNode2 = pNode2->m_pNext;if (pNode1 = NULL)pCurLastNode->m_pNext = pNode2;if (pNode2 = NULL)pCurLastNode->m_pNext = pN

23、ode1;return pMergeListHead;/創(chuàng)建一個鏈表，輸入從頭到尾結(jié)點的值，輸入-1表示結(jié)束 void CreateList(ListNode *& pHead)ListNode *pListNode = NULL;ListNode *pCurLastNode = NULL;bool isHead = true;while (1)if (isHead)pHead = new ListNode();cin >> pHead->m_nValue;if (pHead->m_nValue = -1)pHead = NULL;break;pHead->

24、;m_pNext = NULL;isHead = false;pCurLastNode = pHead;elsepListNode = new ListNode();cin >> pListNode->m_nValue;if (pListNode->m_nValue = -1)break;pListNode->m_pNext = NULL;pCurLastNode->m_pNext = pListNode;pCurLastNode = pListNode;/從頭到尾打印鏈表 void PrintList(ListNode *&pHead)if (pH

25、ead != NULL)ListNode *pCur = pHead;while (pCur != NULL)cout << pCur->m_nValue << " "pCur = pCur->m_pNext;cout << endl;elsecout << "鏈表為空！" << endl;int main(int argc, int argv)ListNode *pList1Head = NULL;CreateList(pList1Head);PrintList(pList1Hea

26、d);ListNode *pList2Head = NULL;CreateList(pList2Head);PrintList(pList2Head);ListNode *pMergeListHead = MergeTwoList(pList1Head, pList2Head);if (pMergeListHead != NULL)cout << pMergeListHead->m_nValue << endl;PrintList(pMergeListHead);system("pause");return 0;四、用STL中的vector定義

27、一個對象vec，在vec中添加若干個元素，然后對這些元素進行排序（可以采用任意一種排序方法），并輸出排序后的元素。#include <iostream> #include <vector> #include <algorithm> /先自定義一個結(jié)構(gòu)體 struct Test int member1;int member2;/自定義排序函數(shù) bool SortByM1(const Test &v1, const Test &v2)/注意：本函數(shù)的參數(shù)的類型一定要與vector中元素的類型一致 return v1.member1 < v2

28、.member1;/升序排列 void MyPushback(std:vector<Test> & vecTest, const int &m1, const int &m2)Test test;test.member1 = m1;test.member2 = m2;vecTest.push_back(test);void PrintVector(std:vector<Test> & vec)/*插一句，vec.begin()對應(yīng)的位置是向量的第一個位置，vec.end()對應(yīng)的是vector中的最后的一個元素位置的后面的一個位置（我認為

29、，實際上是一個無效位置）文檔上的定義：Returns an iterator referring to the past-the-end element in the vector container.*/for (std:vector<Test>:iterator it = vec.begin(); it != vec.end(); it+)std:cout << it->member1 << 't' << it->member2 << std:endl;int main()std:vector<T

30、est> vecTest;MyPushback(vecTest, 9, 1);MyPushback(vecTest, 8, 2);MyPushback(vecTest, 7, 3);MyPushback(vecTest, 6, 4);MyPushback(vecTest, 5, 5);MyPushback(vecTest, 4, 6);MyPushback(vecTest, 3, 7);MyPushback(vecTest, 2, 8);MyPushback(vecTest, 1, 9);/排序之前 std:cout << "Before Sort:" &

31、lt;< std:endl;PrintVector(vecTest);std:cout << "對向量中的所有元素按member1進行升序排列:" << std:endl;std:sort(vecTest.begin(), vecTest.end(), SortByM1);PrintVector(vecTest);/std:cout<<"對向量中的第2個到第5個元素按member1進行升序排列:"<<std:endl; /std:sort(vecTest.begin()+1,vecTest.begin

32、()+5,SortByM1);/vecTest.begin()+5為第6個位置 /PrintVector(vecTest); system("pause");return 0;五、已知一個單向鏈表，試給出復(fù)制該鏈表的算法。要求：1、定義線性表的節(jié)點的結(jié)構(gòu)以及節(jié)點的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main函數(shù)中進行測試：先構(gòu)建一個線性表，并定義一個空線性表，然后進行復(fù)制。#include "iostream" using namespace std;struct ListNodeint m_Value;Li

33、stNode* pNext;ListNode* CloneList(ListNode* pHead)ListNode* pNode = pHead;ListNode* pCloneHead=0, *pCloneNode=0;if (pNode != NULL)pCloneHead = new ListNode();pCloneHead->m_Value = pNode->m_Value;pCloneHead->pNext = NULL;pCloneNode = pCloneHead;pNode = pNode->pNext;while (pNode != NULL)Li

34、stNode* pTempNode = new ListNode();pTempNode->m_Value = pNode->m_Value;pTempNode->pNext = NULL;pCloneNode->pNext = pTempNode;pCloneNode = pCloneNode->pNext;pNode = pNode->pNext;return pCloneHead;bool printList(ListNode* pHead)ListNode* pNode = pHead;if (pNode = NULL)return false;wh

35、ile (pNode)cout << pNode->m_Value << endl;pNode = pNode->pNext;return true;ListNode * CreatList()ListNode * pHead = new ListNode();pHead->m_Value = 1;pHead->pNext = NULL;ListNode* pNode = pHead;for (int i = 2; i <= 10; i += 2)ListNode* pTempNode = new ListNode();pTempNode-

36、>m_Value = i;pTempNode->pNext = NULL;pNode->pNext = pTempNode;pNode = pNode->pNext;return pHead;int main()ListNode* pHead = CreatList();if (CloneList(pHead)printList(pHead);elsecout << "Initial the list erro!" << endl;system("pause");return 0;六、寫出從一個帶表頭的單鏈

37、表中刪除其值等于給定值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ù)中進行測試：先構(gòu)建一個線性表，然后調(diào)用函數(shù)刪除值等于給定值的節(jié)點。#include<iostream>using namespace std;typedef int Elementtype;struct celltype Elementtype

38、 element;celltype *next; /*結(jié)點型*/typedef celltype *LIST;typedef celltype *position;position End(LIST L)position q;q = L;while (q->next != NULL)q = q->next;return (q); /時間復(fù)雜性：O(n)void Insert(Elementtype x, position p, LIST &L)position q;q = new celltype;q->element = x;q->next = p->n

39、ext;p->next = q; /時間復(fù)雜性：O(1)position MakeNull(LIST &L)L = new celltype;L->next = NULL;return L; /時間復(fù)雜性：O(1)void print(position p)int count = 0;cout << "鏈表中的情況:"<<endl;int flg = 0;while (p->next != NULL)flg = 1;p = p->next;cout<<"邏輯位置："<<+co

40、unt<<" "<< "元素："<<p->element <<endl;if (!flg)cout << "啥玩意兒也沒有！"cout << endl;void CreateList(Elementtype x, position p, LIST &L)x = 1;cout << "請輸入鏈表元素，輸入-1表示輸入結(jié)束：" << endl;while (x != -1)cin >> x;Inse

41、rt(x, p, L);print(p);int Delete(int x,LIST &L)int m = 1;position p1 = 0,p2=0;cout << "請輸入一個刪除的元素："cin >> x;if (L->element = x)p1 = L;L = L->next;delete p1;return m;elsep1 = p2 = L;while (p1->element != x && p1->next != NULL)p2 = p1;m+;p1 = p1->next; p

42、2->next;p2->next = p1->next;delete p1;return m;return -1;int main()LIST L;Elementtype x = 1;position p = MakeNull(L);CreateList(x, p, L);Delete(x, L);print(p);system("pause");return 0;七、寫出一個將兩個靜態(tài)鏈表（屬于同一個存儲池）合并的算法函數(shù)： void Merge(cursor M, cursor N); 合并的方法是將N鏈表中的所有結(jié)點添加到M鏈表的后面，并將N鏈表的表

43、頭結(jié)點添加到空閑結(jié)點鏈表中。要求：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

44、 p ); 在鏈表M中刪除位置為p的元素的后一個元素。3、在1、2的基礎(chǔ)上完成本題。4、在main函數(shù)中進行測試：先構(gòu)建一個存儲池，然后在該存儲池中創(chuàng)建兩個靜態(tài)表，最后將這兩個靜態(tài)表合并。/運行時Merge（M，N）函數(shù)不知道出了什么問題？暫時無法解決#include<iostream>using namespace std;#define maxsize 100typedef int elementtype;typedef struct elementtype element;int next; spacestr; /*結(jié)點類型*/spacestr SPACEmaxsize;/*

45、存儲池*/typedef int position, cursor;cursor available;void Initialize()int j;/* 依次鏈接池中結(jié)點*/for (j = 0; j<maxsize - 1; j+)SPACEj.next = j + 1;SPACEj.next = -1; /* 最后一個接點指針域為空*/available = 0;/* 標(biāo)識線性表*/ 可用空間的分配操作cursor GetNode() / q=new spacestr ;cursor p;if (SPACEavailable.next = -1)p = -1;elsep = SPAC

46、Eavailable.next;SPACEavailable.next = SPACEp.next;return p;/* 從池中刪除*/void FreeNode(cursor q) /delete q;SPACEq.next = SPACEavailable.next;SPACEavailable.next = q;/* 放回池中*/ / 在位置p后面插入元素值為x的結(jié)點void Insert(elementtype x, position p)position q;q = GetNode();SPACEq.element = x;SPACEq.next = SPACEp.next;SPA

47、CEp.next = q;/ 刪除位置p后的一個結(jié)點void Delete(position p)position q;if (SPACEp.next != -1)q = SPACEp.next;SPACEp.next = SPACEq.next;FreeNode(q);void Merge(cursor M, cursor N)cout << "n合并后的數(shù)組是：" << endl;position p = M; position q = N; while (SPACEq.next != -1)SPACEp.next = q;p = SPACEp.

48、next;q = SPACEq.next;position r = available; SPACEN.next = r; available = N;void Insert(elementtype x, position p, cursor M)position q;q = GetNode(); SPACEq.element = x; SPACEq.next = SPACEp.next; SPACEp.next = q;void Delete(cursor M, position p)position q; q = GetNode();if (SPACEp.next != -1) if (S

49、PACESPACEp.next.next != -1) q = SPACEp.next; SPACEp.next = SPACEq.next; FreeNode(q); else q = SPACEp.next;FreeNode(q);void Input(cursor M)/創(chuàng)建靜態(tài)鏈表 elementtype x;cursor p = 0;cout << "請輸入靜態(tài)鏈表的值以-1結(jié)束" << endl;while (1) Initialize();cin >> x;if (x != -1) Insert(x, p, M);p = S

50、PACEp.next;else SPACEp.element = -1;p = -1;break;void Output(cursor M) position p; p = M; while (p != -1) cout << SPACEp.element << "t" p = SPACEp.next; cout << endl;int main()Initialize();SPACE0.element = 2; SPACE0.next = 6; SPACE1.element = 4; SPACE1.next = 3; SPACE2.next = 4;SPACE3.element = 8; SPACE3.next = -1;SPACE4.element = 10; SPACE4.next = 7; SPACE5.next = 0;SPACE6.element = 16; SPACE6.next = 1; SPACE7.element = 18; SPACE7.next = 9; SPACE8.element = 20; SPACE8.next = -1; SPACE9.element = 22; SPAC