順序表鏈表KMP實驗報告

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

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

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

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

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

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

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

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

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

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

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

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

13、m D: DS線性表綜合練習-數(shù)制轉換目的：(1)對于任意十進制數(shù)轉換為k進制，包括整數(shù)部分和小數(shù)部分轉換。整數(shù)部分采用除k求余法，小數(shù)部分采用乘k取整法例如x=19.125，求2進制轉換整數(shù)部分19，小數(shù)部分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)所以整數(shù)部分轉為 10011，小數(shù)部分轉為0.001，合起來為10011.001(3)提示整數(shù)部分可用堆棧，小數(shù)部分可用隊列實現(xiàn)(4)注意：必須按照上述方法來實現(xiàn)數(shù)制

14、轉換，其他方法0分要求：Input第一行輸入一個t，表示下面將有t組測試數(shù)據(jù)。（完成）接下來每行包含兩個參數(shù)n和k，n表示要轉換的數(shù)值，可能是非整數(shù)；k表示要轉換的數(shù)制，1<k<=16（完成）Output對于每一組測試數(shù)據(jù)，每行輸出轉換后的結果，結果精度到小數(shù)點后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組括號已經(jīng)匹配消除3、 若到最后，括號不能完全匹配，則說明輸入的表達式有錯(3)建議使用C+自帶的stack對象來實現(xiàn)要求：Input第一行輸入一個t，表示下面將有t組測試數(shù)據(jù)。接下來的t行的每行輸入一個表達式，表達式只考慮英文半角狀態(tài)輸入，無需考慮中文全角輸入（完成）Output對于每一行的表達式，檢查括

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

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

18、Output每行輸出一個表達式的計算結果，計算結果用浮點數(shù)（含4位小數(shù)）的格式表示（完成）8. Problem H: DS堆棧-迷宮求解目的：(1)給出一個N*N的迷宮矩陣示意圖，從起點0,0出發(fā)，尋找路徑到達終點N-1, N-1。(2)要求使用堆棧對象來實現(xiàn)，具體算法參考課本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、要的函數(shù)、算法或知識點，并談談你對它們的理解DS實驗01-順序表1. Problem A: DS順序表-類實現(xiàn)函數(shù)：list_insert(int i,int item);插入函數(shù)一維數(shù)組需要把插入點后的數(shù)據(jù)往后推一格再給插入點賦值。所耗時間比鏈表久。list_del(int i)刪除函數(shù)將刪除點后點數(shù)據(jù)前推一格覆蓋刪除點。所耗時間比鏈表久。list_get(int i)返回指定值函數(shù)比鏈表快。2. Problem B: DS順序表-連續(xù)操作同Problem A: DS順序表-類實現(xiàn)。使用for循環(huán)以及插入函數(shù)。3. Problem C: DS順序表-合并操作合并操作：兩個線性表，分別讀取數(shù)字

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

22、b_pNexbb_pPre改變數(shù)值進行交換：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單鏈表-合并 過程基本與線性表合并相同。不同的是需要調(diào)整指針。4. Problem D: DS線性表-多項式相加線性表實現(xiàn)： 建立兩個數(shù)組分別存儲系數(shù)和指數(shù)。多項式相加的操作過程基本與合并相似。先比較指數(shù)，若指數(shù)較

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

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

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

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

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

28、右下角即成功，如果最后pop（）到棧內(nèi)沒有元素了的話就說明沒有路徑。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時候表示調(diào)用第nextj個位置的字符與mainstri匹配。三實驗程序或內(nèi)容：1. 針對每一項實驗要求，給出編寫的代碼，2. 可以粘貼全部代碼，或

29、者可以只粘貼重要的代碼（為了節(jié)省紙張），但代碼必須完整，至少是完整的函數(shù)。3. 代碼符合以下要求，評分更高：a. 排版整齊，可讀性高b. 代碼有注釋，越詳細越清晰越好DS實驗01-順序表1. Problem A: DS順序表-類實現(xiàn)#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(); ; /構造函數(shù)SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構函數(shù)SeqList:SeqList() deletelist; /返回長度int SeqList:list_size() return size; /插入函數(shù)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; /刪除函數(shù)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、/返回值函數(shù)int SeqList:list_get(int i) if(i<=0|i>size)return error; return listi-1; /輸出函數(shù)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個數(shù)據(jù)，即n是實際長度；接著輸入n個數(shù)據(jù) 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行輸入要插入的位置和新數(shù)據(jù) cin>>position>>NUM; if(L.list_insert(position,NUM)=-1)cout<<"error"<<endl; else cout<<L.list_size()<<" " L.l

34、ist_display(); /第3行輸入要插入的位置和新數(shù)據(jù) 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(); ; /構造函數(shù)SeqList

38、:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構函數(shù)SeqList:SeqList() deletelist; /返回長度int SeqList:list_size() return size; /插入函數(shù)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; /刪除函數(shù)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; /返回值函數(shù)int SeqList:list_get(int i) if(i<=0|i>size)return error; return listi-1; /輸出函數(shù)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個數(shù)據(jù)，即n是實際長度；接著輸入n個數(shù)據(jù) 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個插入數(shù)據(jù)，接著輸入k個數(shù)據(jù) 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個數(shù)據(jù) 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(); ; /構造函數(shù)SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構函數(shù)SeqList:SeqList() deletelist; /返回長度int SeqList:list_size() return size; /插入函數(shù)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; /刪除函數(shù)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; /返回值函數(shù)int SeqList:list_get(int i) if(i<

45、;=0|i>size)return error; return listi-1; /輸出函數(shù)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單鏈表-類實現(xiàn)#include<iostream> using namespace std; #define ok 1 #define error -1; class Li