順序表鏈表KMP實驗報告

1、.附件（四）深 圳 大 學 實 驗 報 告 課程名稱： 數據結構實驗與課程設計 實驗項目名稱： 順序表、鏈表、堆棧隊列、串KMP算法 學院： 專業(yè)： 指導教師： 報告人： 學號： 班級： 實驗時間： 實驗報告提交時間： 教務處制一、 實驗目的與完成說明：1. 簡單介紹本實驗的主要目的2. 說明你自己在本次實驗中完成了第幾項要求（必填）DS實驗01-順序表1. Problem A: DS順序表-類實現目的： (1)實現順序表的用C+語言和類實現順序表(2)屬性包括：數組、實際長度、最大長度（設定為1000）(3)操作包括：創(chuàng)建、插入、刪除、查找要求：Input第1行先輸入n表示有n個數據，即n是

2、實際長度；接著輸入n個數據（完成）第2行輸入要插入的位置和新數據（完成）第3行輸入要插入的位置和新數據（完成）第4行輸入要刪除的位置（完成）第5行輸入要刪除的位置（完成）第6行輸入要查找的位置（完成）第7行輸入要查找的位置（完成）Output第1行輸出創(chuàng)建后的順序表內容，包括順序表實際長度和數據（完成）每成功執(zhí)行一次操作（插入或刪除），輸出執(zhí)行后的順序表內容（完成）每成功執(zhí)行一次查找，輸出查找到的數據（完成）如果執(zhí)行操作失敗（包括插入、刪除、查找等失?。敵鲎址甧rror，不必輸出順序表內容（完成）2. Problem B: DS順序表-連續(xù)操作目的： (1)建立順序表的類，屬性包括：數組

3、、實際長度、最大長度（設定為1000）(2)實現連續(xù)多個插入，即從位置i開始插入多個數據(3)實現連續(xù)多個刪除，即從位置i開始刪除多個數據要求：Input第1行先輸入n表示有n個數據，即n是實際長度；接著輸入n個數據（完成）第2行先輸入i表示插入開始的位置，再輸入k表示有k個插入數據，接著輸入k個數據（完成）第3行先輸入i表示刪除開始的位置，再輸入k表示要刪除k個數據（完成）Output順序表內容包括順序表的實際長度和數據，數據之間用空格隔開（完成）第1行輸出創(chuàng)建后的順序表內容（完成）第2行輸出執(zhí)行連續(xù)插入后的順序表內容（完成）第3行輸出執(zhí)行連續(xù)刪除后的順序表內容（完成）3. Problem

4、C: DS順序表-合并操作目的： (1)建立順序表的類，屬性包括：數組、實際長度、最大長度（設定為1000）(2)已知兩個遞增序列，把兩個序列的數據合并到順序表中，(3)并使得順序表的數據遞增有序。要求：Input第1行先輸入n表示有n個數據，接著輸入n個數據，表示第1個序列，要求數據遞增互不等（完成）第2行先輸入m表示有m個數據，接著輸入m個數據，表示第2個序列，要求數據遞增互不等（完成）Output順序表內容包括順序表的實際長度和數據，數據之間用空格隔開（完成）第1行輸出創(chuàng)建后的順序表內容（完成）DS實驗02-鏈表1. Problem A: DS單鏈表-類實現目的：(1)用C+語言和類實現

5、單鏈表，含頭結點(2)屬性包括：data數據域、next指針域(3)操作包括：插入、刪除、查找(4)注意：單鏈表不是數組，所以位置從1開始對應首結點，頭結點不放數據要求：Input第1行先輸入n表示有n個數據，接著輸入n個數據（完成）第2行輸入要插入的位置和新數據（完成）第3行輸入要插入的位置和新數據（完成）第4行輸入要刪除的位置（完成）第5行輸入要刪除的位置（完成）第6行輸入要查找的位置（完成）第7行輸入要查找的位置（完成）Output數據之間用空格隔開，（完成）第1行輸出創(chuàng)建后的單鏈表的數據（完成）每成功執(zhí)行一次操作（插入或刪除），輸出執(zhí)行后的單鏈表數據（完成）每成功執(zhí)行一次查找，輸出查找

6、到的數據（完成）如果執(zhí)行操作失敗（包括插入、刪除、查找等失?。?，輸出字符串error，不必輸出單鏈表（完成）2. Problem B: DS單鏈表-結點交換目的：(1)用C+實現含頭結點的單鏈表，然后實現單鏈表的兩個結點交換位置。(2)注意不能簡單交換兩個結點包含數據，必須通過修改指針來實現兩個結點的位置交換(3)交換函數定義可以參考：(4)swap（int  pa, int pb)  /pa和pb表示兩個結點在單鏈表的位置序號(5)swap (ListNode * p, ListNode * q)  /p和q表示指向兩個結點的指針要求：Input第1行先輸入n表

7、示有n個數據，接著輸入n個數據（完成）第2行輸入要交換的兩個結點位置（完成）第3行輸入要交換的兩個結點位置（完成）Output第一行輸出單鏈表創(chuàng)建后的所有數據，數據之間用空格隔開（完成）第二行輸出執(zhí)行第1次交換操作后的單鏈表數據，數據之間用空格隔開（完成）第三行輸出執(zhí)行第2次交換操作后的單鏈表數據，數據之間用空格隔開（完成）如果發(fā)現輸入位置不合法，輸出字符串error，不必輸出單鏈表（完成）3. Problem C: DS單鏈表-合并目的：(1)假定兩個單鏈表是遞增有序，定義并實現以下函數，完成兩個單鏈表的合并，繼續(xù)保持遞增有序(2)int LL_merge(ListNode *La, Lis

8、tNode *Lb)要求：Input第1行先輸入n表示有n個數據，接著輸入n個數據（完成）第2行先輸入m表示有M個數據，接著輸入m個數據（完成）Output輸出合并后的單鏈表數據，數據之間用空格隔開（完成）4. Problem D: DS線性表-多項式相加目的：(1)對于一元多項式 p(x)=p0+p1x+p2x2+ +pnxn ，每個項都有系數和指數兩部分，例如p2x2的系數為p2,指數為2(2)編程實現兩個多項式的相加例如5+x+2x2+3x3，-5-x+6x2+4x4，兩者相加結果：8x2+3x3+4x4 (3)其中系數5和-5都是x的0次方的系數，相加后為0，所以不顯示。x的1次方同理

9、不顯示。(4)可用順序表或單鏈表實現要求：Input第1行：輸入t表示有t組測試數據（完成）第2行：輸入n表示有第1組的第1個多項式包含n個項（完成）第3行：輸入第一項的系數和指數，以此類推輸入n行（完成）接著輸入m表示第1組的第2個多項式包含m項（完成）同理輸入第2個多項式的m個項的系數和指數（完成）參考上面輸入第2組數據，以此類推輸入t組（完成）假設所有數據都是整數（完成）Output對于每1組數據，先用兩行輸出兩個原來的多項式，再用一行輸出運算結果，不必考慮結果全為0的情況（完成）輸出格式參考樣本數據，格式要求包括：1.如果指數或系數是負數，用小括號括起來（完成）2.如果系數為0，則該項

10、不用輸出（完成）3.如果指數不為0，則用符號表示，例如x的3次方，表示為x3（完成）4.多項式的每個項之間用符號+連接，每個+兩邊加1個空格隔開（完成）DS實驗03-堆棧與隊列1. Problem A: DS堆棧-逆序輸出（STL棧使用）目的：(1)C+中已經自帶堆棧對象stack，無需編寫堆棧操作的具體實現代碼。(2)本題目主要幫助大家熟悉stack對象的使用，然后實現字符串的逆序輸出(3)輸入一個字符串，按字符按輸入順序壓入堆棧，然后根據堆棧后進先出的特點，做逆序輸出要求：Input第一行輸入t，表示有t個測試實例（完成）第二起，每一行輸入一個字符串，注意字符串不要包含空格（完成）Outp

11、ut每行逆序輸出每一個字符串（完成）2. Problem B: DS線性表綜合練習-隊列之銀行排隊目的：(1)在銀行營業(yè)大廳共服務3種客戶，類型為ABC，大廳分別設置了3個窗口分別服務三種客戶，即每個窗口只服務一種客戶?，F有一批客戶來銀行辦理業(yè)務，每個客戶都有類型和辦理業(yè)務時間。每個窗口按照客戶到來的順序進行服務。要求：Input第一行輸入先輸入n表示客戶數量（完成）第二行輸入每個客戶的類型，數據之間用用空格隔開（完成）第三行輸入每個客戶的辦理時間，數據之間用用空格隔開（完成）Output第一行輸出A類客戶的平均辦理時間（完成）第二行輸出B類客戶的平均辦理時間（完成）第三行輸出C類客戶的平均辦

12、理時間（完成）3. Problem C: DS堆棧-行編輯目的：(1)使用C+的STL堆棧對象，編寫程序實現行編輯功能。行編輯功能是：當輸入#字符，則執(zhí)行退格操作；如果無字符可退就不操作，不會報錯(2)本程序默認不會顯示#字符，所以連續(xù)輸入多個#表示連續(xù)執(zhí)行多次退格操作(3)每輸入一行字符打回車則表示字符串結束(4)注意：必須使用堆棧實現，而且結果必須是正序輸出要求：Input第一行輸入一個整數t，表示有t行字符串要輸入（完成）第二行起輸入一行字符串，共輸入t行（完成）Output每行輸出最終處理后的結果，如果一行輸入的字符串經過處理后沒有字符輸出，則直接輸出NULL（完成）4. Proble

13、m D: DS線性表綜合練習-數制轉換目的：(1)對于任意十進制數轉換為k進制，包括整數部分和小數部分轉換。整數部分采用除k求余法，小數部分采用乘k取整法例如x=19.125，求2進制轉換整數部分19，小數部分0.12519 / 2 = 9 10.125 * 2 = 0.25 09 / 2 = 4 10.25 * 2 = 0.5 04 / 2 = 2 0 0.5 * 2 = 1 12 / 2 = 1 01 / 2 = 0 1(2)所以整數部分轉為 10011，小數部分轉為0.001，合起來為10011.001(3)提示整數部分可用堆棧，小數部分可用隊列實現(4)注意：必須按照上述方法來實現數制

14、轉換，其他方法0分要求：Input第一行輸入一個t，表示下面將有t組測試數據。（完成）接下來每行包含兩個參數n和k，n表示要轉換的數值，可能是非整數；k表示要轉換的數制，1<k<=16（完成）Output對于每一組測試數據，每行輸出轉換后的結果，結果精度到小數點后3位（完成）5. Problem E: DS堆棧-括號匹配目的：(1)處理表達式過程中需要對括號匹配進行檢驗，括號匹配包括三種：“(”和“)”，“”和“”，“”和“”。例如表達式中包含括號如下：()()()123456789101112(2)從上例可以看出第1和第2個括號匹配，第3和第10個括號匹配，4和5匹配，6和9匹配

15、，7和8匹配，11和12匹配。從中可以看到括號嵌套的的情況是比較復雜的，使用堆棧可以很方便的處理這種括號匹配檢驗，可以遵循以下規(guī)則：1、 當接收第1個左括號，表示新的一組匹配檢查開始；隨后如果連續(xù)接收到左括號，則不斷進堆棧。2、 當接受第1個右括號，則和最新進棧的左括號進行匹配，表示嵌套中1組括號已經匹配消除3、 若到最后，括號不能完全匹配，則說明輸入的表達式有錯(3)建議使用C+自帶的stack對象來實現要求：Input第一行輸入一個t，表示下面將有t組測試數據。接下來的t行的每行輸入一個表達式，表達式只考慮英文半角狀態(tài)輸入，無需考慮中文全角輸入（完成）Output對于每一行的表達式，檢查括

16、號是否匹配，匹配則輸入ok，不匹配則輸出error（完成）6. Problem F: DS線性表綜合練習-組隊列目的：(1)組隊列是隊列結構中一種常見的隊列結構，在很多地方有著廣泛應用。組隊列是是指隊列內的元素分組聚集在一起。組隊列包含兩種命令：1、 ENQUEUE，表示當有新的元素進入隊列，首先會檢索是否有同一組的元素已經存在，如果有，則新元素排在同組的最后，如果沒有則插入隊列末尾。2、 DEQUEUE，表示隊列頭元素出隊3、 STOP，停止操作(2)建議使用C+自帶的隊列對象queue，編程更方便要求：Input第1行輸入一個t(t<=10)，表示1個隊列中有多少個組（完成）第2行輸

17、入一個第1組的元素個數和數值第3行輸入一個第2組的元素個數和數值，（完成但不嚴謹）以此類推輸入完n組之后，開始輸入多個操作命令(<200)，例如輸入ENQUEUE 100，表示把元素100插入隊列（完成）最后輸入STOP，表示輸入命令結束（完成）Output經過命令操作后隊列的最終結果（完成）7. Problem G: DS堆棧-表達式計算目的：(1)計算一個表達式的運算結果(2)使用C+自帶stack堆棧對象來實現(3)參考課本的偽代碼，把偽代碼改造成可運行的代碼要求：Input第一個輸入t，表示有t個實例（完成）第二行起，每行輸入一個表達式，每個表達式末尾帶#表示結束（完成）輸入t行

18、Output每行輸出一個表達式的計算結果，計算結果用浮點數（含4位小數）的格式表示（完成）8. Problem H: DS堆棧-迷宮求解目的：(1)給出一個N*N的迷宮矩陣示意圖，從起點0,0出發(fā)，尋找路徑到達終點N-1, N-1。(2)要求使用堆棧對象來實現，具體算法參考課本3.2.4節(jié)51頁。要求：Input第一行輸入t，表示有t個迷宮（完成）第二行輸入n，表示第一個迷宮有n行n列（完成）第三行起，輸入迷宮每一行的每個方格的狀態(tài)，0表示可通過，1表示不可通過輸入n行（完成）以此類推輸入下一個迷宮Output逐個輸出迷宮的路徑（完成）如果迷宮不存在路徑，則輸出no path并回車（完成）如果

19、迷宮存在路徑，將路徑中每個方格的x和y坐標輸出，從起點到終點，每輸出四個方格就換行，最終以單詞END結尾（完成）DS實驗04-串應用KMP算法1. Problem A: DS串應用-KMP算法目的：(1) 學習KMP算法，給出主串和模式串，求模式串在主串的位置要求：Input第一個輸入t，表示有t個實例（完成）第二行輸入第1個實例的主串，第三行輸入第1個實例的模式串（完成）以此類推Output第一行輸出第1個實例的模式串的next值（完成）第二行輸出第1個實例的匹配位置，位置從1開始計算，如果匹配成功輸出位置，匹配失敗輸出0（完成）以此類推二、主要思路與方法：1. 對于本次實驗，說明你認為最重

20、要的函數、算法或知識點，并談談你對它們的理解DS實驗01-順序表1. Problem A: DS順序表-類實現函數：list_insert(int i,int item);插入函數一維數組需要把插入點后的數據往后推一格再給插入點賦值。所耗時間比鏈表久。list_del(int i)刪除函數將刪除點后點數據前推一格覆蓋刪除點。所耗時間比鏈表久。list_get(int i)返回指定值函數比鏈表快。2. Problem B: DS順序表-連續(xù)操作同Problem A: DS順序表-類實現。使用for循環(huán)以及插入函數。3. Problem C: DS順序表-合并操作合并操作：兩個線性表，分別讀取數字

21、，比較兩數字大小，小的先插入第三個線性表，一直讀到其中一個線性表到底跳出循環(huán)，將另一條線性表里剩余的數字全都插在第三個線性表后。DS實驗02-鏈表1. Problem A: DS單鏈表-類實現函數：LL_insert(int i,int item);插入函數。調整指針指向即可插入。比順序表快。LL_get(int i);返回值函數。遍歷到指定結點后輸出。比順序表慢。LL_del(int i);刪除函數。調整指針指向，釋放結點或放置另一條鏈表中回收利用。2. Problem B: DS單鏈表-結點交換改變指針進行交換：a_pNexb_pNexaa_pPrebb_pPrea_pNexaa_pPre

22、b_pNexbb_pPre改變數值進行交換：int LinkList:swap(ListNode *p,ListNode *q) if(p=head|q=head|!p|!q)return error; int temp;temp=p->data;p->data=q->data;q->data=temp; return ok; 3. Problem C: DS單鏈表-合并 過程基本與線性表合并相同。不同的是需要調整指針。4. Problem D: DS線性表-多項式相加線性表實現： 建立兩個數組分別存儲系數和指數。多項式相加的操作過程基本與合并相似。先比較指數，若指數較

23、小就插在最左邊，若指數相等則相加再插入。一條多項式插完后另一條多項式剩余系數指數插在右邊。鏈表實現：Status MakeNode(Link& p,ElemType e,ElemType e1);分配一個結點Status CreatPolyn(polynomai &P,Link& p);將結點插入多項式中。插入過程中比較指數大小按由小到大的順序插在相應的位置里，如果有相同指數的則系數相加（系數可為正負），若系數為0則調用刪除函數刪除該結點。Status AddPolyn(polynomai &Pa,polynomai &Pb,polynomai &

24、;Pc);多項式相加。比線性表要簡單，直接把Pa，Pb里的系數跟指數創(chuàng)建一個結點放入多項式Pc中即可，相加直接在加入的時候完成。DS實驗03-堆棧與隊列1. Problem A: DS堆棧-逆序輸出（STL棧使用）建立一個棧，將數值push()進棧后用top()返回值并pop()彈出值逆向輸出。2. Problem B: DS線性表綜合練習-隊列之銀行排隊建立兩個隊列，一個為<int>，另一個為<char>，用于存儲時間和字符，在一個個用front()取值并用pop()彈出，用判斷語句進行平均數求值。3. Problem C: DS堆棧-行編輯建立兩個棧，用其中一個棧存

25、儲string數組的每一個字符。先判斷是否為#號且有多少個#號，若沒有#號則push()字符進第二個棧，有多少個#號就pop()多少個。全程判斷棧是否為空。最后判斷第二個棧是否為空，不為空就輸出字符串，為空就輸出NULL。4. Problem D: DS線性表綜合練習-數制轉換Push數值與進制數的余數進棧然后逆向輸出。Push數值與2的倍數取整進棧然后逆向輸出。5. Problem E: DS堆棧-括號匹配若棧為空時下一個就是右括號直接括號不匹配。若是左括號則進棧。一直進左括號知道有右括號出現。若右括號與top()匹配則pop()。若括號匹配則棧為空。6. Problem F: DS線性表綜

26、合練習-組隊列建立隊列數組，同組的元素進入同一個隊列中。7. Problem G: DS堆棧-表達式計算使用OPTR棧存儲運算符，使用OPND棧存儲數字。OPTR先PUSH入#號，輸入表達式時最后一位為#號，在c= =OPTR.top()= =#的時候結束表達式計算。讀入字符的過程中不斷有運算符和數字進棧，直到兩個運算符遭遇的時候，判斷棧內top()運算符與c內運算符的優(yōu)先級，即表達式中前一個運算符與后一個運算符的優(yōu)先級。如果是小于，則直接讓c進OPTR棧，再讀入下一個字符；如果是大于，則OPTR彈出一個運算符，OPND彈出兩個數字進行計算求值重新放回OPND棧；如果是等于則OPTR出棧消除括

27、號。只有左括號和右括號以及兩個#號的優(yōu)先級為等于號。而右括號出現的時候左括號以后的運算符都已計算并變成數字進入了OPND棧，所以右括號出現時候OPTR.pop()彈出的必然是左括號。最后OPND會剩下最后一個數字即結果。函數： Strcat(char,char)在字符串后面加字符。8. Problem H: DS堆棧-迷宮求解建立一個類CPOS，對象分別是xp,yp作為坐標。建立存儲類型為類的棧stack<CPOS>。從起點開始如果右邊能走優(yōu)先往右。直到右邊不能走了就往下，如果右邊和下邊都不能走就pop（），同時剛剛的坐標上直接標記無法通行（1），然后判斷下邊能不能走。坐標軸到達了

28、右下角即成功，如果最后pop（）到棧內沒有元素了的話就說明沒有路徑。DS實驗04-串應用KMP算法1. Problem A: DS串應用-KMP算法nextj： ：第一為0的作用是讓子串向右移動一格，此時i會變。 ：1的作用是子串換成第一個字符再進行比較，此時i不會變。 ：j取nextj的時候i不變。 ：如果一直沒有匹配到，j一直為1，nextj一直為0。如果有匹配到j就會大于1； ：子串有j個字符，則next中用到的只有前j個。 ：nextj大于0時候表示調用第nextj個位置的字符與mainstri匹配。三實驗程序或內容：1. 針對每一項實驗要求，給出編寫的代碼，2. 可以粘貼全部代碼，或

29、者可以只粘貼重要的代碼（為了節(jié)省紙張），但代碼必須完整，至少是完整的函數。3. 代碼符合以下要求，評分更高：a. 排版整齊，可讀性高b. 代碼有注釋，越詳細越清晰越好DS實驗01-順序表1. Problem A: DS順序表-類實現#include<iostream> using namespace std; #define ok 0 #define error -1 /順序表類定義 class SeqList private: int *list; int maxsize; int size; public: SeqList(); SeqList(); int list_size

30、(); int list_insert(int i,int item); int list_del(int i); int list_get(int i); void list_display(); ; /構造函數SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構函數SeqList:SeqList() deletelist; /返回長度int SeqList:list_size() return size; /插入函數int SeqList:list_insert(int i,int item) if(i>si

31、ze+1|i<0|size=maxsize)return error; if(i=size+1) listi-1=item; size+; return ok; int j; for(j=size;j>i-1;j-) listj=listj-1; listj=item; size+; return ok; /刪除函數int SeqList:list_del(int i) if(i>size|i<0|size=0)return error; int j; for(j=i-1;j<size-1;j+) listj=listj+1; size-; return ok;

32、/返回值函數int SeqList:list_get(int i) if(i<=0|i>size)return error; return listi-1; /輸出函數void SeqList:list_display() int j; for(j=0;j<size;j+) cout<<listj<<" " cout<<endl; int main() int n,i,NUM,position; SeqList L; /第1行先輸入n表示有n個數據，即n是實際長度；接著輸入n個數據 cin>>n; for(i

33、=0;i<n;i+) cin>>NUM; L.list_insert(i+1,NUM); cout<<L.list_size()<<" " L.list_display(); /第2行輸入要插入的位置和新數據 cin>>position>>NUM; if(L.list_insert(position,NUM)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.l

34、ist_display(); /第3行輸入要插入的位置和新數據 cin>>position>>NUM; if(L.list_insert(position,NUM)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.list_display(); /第4行輸入要刪除的位置 cin>>position; if(L.list_del(position)=-1)cout<<"error"

35、;<<endl; else cout<<L.list_size()<<" " L.list_display(); /第5行輸入要刪除的位置 cin>>position; if(L.list_del(position)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.list_display(); /第6行輸入要查找的位置 cin>>position; if(L.li

36、st_get(position)=-1)cout<<"error"<<endl; else cout<<L.list_get(position)<<endl; /第7行輸入要查找的位置 cin>>position; if(L.list_get(position)=-1)cout<<"error"<<endl; else cout<<L.list_get(position)<<endl; return 0; 2.Problem B: DS順序表-連續(xù)

37、操作#include<iostream> using namespace std; #define ok 0 #define error -1 /順序表類定義 class SeqList private: int *list; int maxsize; int size; public: SeqList(); SeqList(); int list_size(); int list_insert(int i,int item); int list_del(int i); int list_get(int i); void list_display(); ; /構造函數SeqList

38、:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構函數SeqList:SeqList() deletelist; /返回長度int SeqList:list_size() return size; /插入函數int SeqList:list_insert(int i,int item) if(i>size+1|i<0|size=maxsize)return error; if(i=size+1) listi-1=item; size+; return ok; int j; for(j=size;j>i-1;j-)

39、 listj=listj-1; listj=item; size+; return ok; /刪除函數int SeqList:list_del(int i) if(i>size|i<0|size=0)return error; int j; for(j=i-1;j<size-1;j+) listj=listj+1; size-; return ok; /返回值函數int SeqList:list_get(int i) if(i<=0|i>size)return error; return listi-1; /輸出函數void SeqList:list_displa

40、y() int j; for(j=0;j<size;j+) cout<<listj<<" " cout<<endl; int main() int n,i,NUM,k,j; SeqList L; /第1行先輸入n表示有n個數據，即n是實際長度；接著輸入n個數據 cin>>n; for(j=0;j<n;j+) cin>>NUM; L.list_insert(j+1,NUM); cout<<L.list_size()<<" " L.list_display();

41、/第2行先輸入i表示插入開始的位置，再輸入k表示有k個插入數據，接著輸入k個數據 cin>>i>>k; for(j=0;j<k;j+) cin>>NUM; L.list_insert(i+,NUM); cout<<L.list_size()<<" " L.list_display(); /第3行先輸入i表示刪除開始的位置，再輸入k表示要刪除k個數據 cin>>i>>k; for(j=0;j<k;j+) L.list_del(i); cout<<L.list_size(

42、)<<" " L.list_display(); return 0; 3. Problem C: DS順序表-合并操作#include<iostream> using namespace std; #define ok 0 #define error -1 /順序表類定義 class SeqList private: int *list; int maxsize; int size; public: SeqList(); SeqList(); int list_size(); int list_insert(int i,int item); int

43、list_del(int i); int list_get(int i); void list_display(); ; /構造函數SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構函數SeqList:SeqList() deletelist; /返回長度int SeqList:list_size() return size; /插入函數int SeqList:list_insert(int i,int item) if(i>size+1|i<0|size=maxsize)return error; if

44、(i=size+1) listi-1=item; size+; return ok; int j; for(j=size;j>i-1;j-) listj=listj-1; listj=item; size+; return ok; /刪除函數int SeqList:list_del(int i) if(i>size|i<0|size=0)return error; int j; for(j=i-1;j<size-1;j+) listj=listj+1; size-; return ok; /返回值函數int SeqList:list_get(int i) if(i<

45、;=0|i>size)return error; return listi-1; /輸出函數void SeqList:list_display() int j; for(j=0;j<size;j+) cout<<listj<<" " cout<<endl; int main() int n,m,j,NUM; SeqList L1,L2,L3; cin>>n; for(j=0;j<n;j+) cin>>NUM; L1.list_insert(j+1,NUM); cin>>m; for(j

46、=0;j<m;j+) cin>>NUM; L2.list_insert(j+1,NUM); int i=1; j=1; int k=1; /排列Start while(i<L1.list_size()+1|j<L2.list_size()+1) if(i=L1.list_size()+1) while(j<L2.list_size()+1) L3.list_insert(k+,L2.list_get(j); j+; break; if(j=L2.list_size()+1) while(i<L1.list_size()+1) L3.list_inser

47、t(k+,L1.list_get(i); i+; break; if(L1.list_get(i)>L2.list_get(j) L3.list_insert(k+,L2.list_get(j); j+; continue; if(L1.list_get(i)<L2.list_get(j) L3.list_insert(k+,L1.list_get(i); i+; continue; if(L1.list_get(i)=L2.list_get(j) L3.list_insert(k+,L2.list_get(j); j+; continue; /排列End cout<<L3.list_size()<<" " L3.list_display(); return 0; DS實驗02-鏈表1. Problem A: DS單鏈表-類實現#include<iostream> using namespace std; #define ok 1 #define error -1; class Li