順序表鏈表KMP實(shí)驗(yàn)報(bào)告

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

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

3、、實(shí)際長(zhǎng)度、最大長(zhǎng)度（設(shè)定為1000）(2)實(shí)現(xiàn)連續(xù)多個(gè)插入，即從位置i開始插入多個(gè)數(shù)據(jù)(3)實(shí)現(xiàn)連續(xù)多個(gè)刪除，即從位置i開始刪除多個(gè)數(shù)據(jù)要求：Input第1行先輸入n表示有n個(gè)數(shù)據(jù)，即n是實(shí)際長(zhǎng)度；接著輸入n個(gè)數(shù)據(jù)（完成）第2行先輸入i表示插入開始的位置，再輸入k表示有k個(gè)插入數(shù)據(jù)，接著輸入k個(gè)數(shù)據(jù)（完成）第3行先輸入i表示刪除開始的位置，再輸入k表示要?jiǎng)h除k個(gè)數(shù)據(jù)（完成）Output順序表內(nèi)容包括順序表的實(shí)際長(zhǎng)度和數(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ù)組、實(shí)際長(zhǎng)度、最大長(zhǎng)度（設(shè)定為1000）(2)已知兩個(gè)遞增序列，把兩個(gè)序列的數(shù)據(jù)合并到順序表中，(3)并使得順序表的數(shù)據(jù)遞增有序。要求：Input第1行先輸入n表示有n個(gè)數(shù)據(jù)，接著輸入n個(gè)數(shù)據(jù)，表示第1個(gè)序列，要求數(shù)據(jù)遞增互不等（完成）第2行先輸入m表示有m個(gè)數(shù)據(jù)，接著輸入m個(gè)數(shù)據(jù)，表示第2個(gè)序列，要求數(shù)據(jù)遞增互不等（完成）Output順序表內(nèi)容包括順序表的實(shí)際長(zhǎng)度和數(shù)據(jù)，數(shù)據(jù)之間用空格隔開（完成）第1行輸出創(chuàng)建后的順序表內(nèi)容（完成）DS實(shí)驗(yàn)02-鏈表1. Problem A: DS單鏈表-類實(shí)現(xiàn)目的：(1)用C+語言和類實(shí)現(xiàn)

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

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

7、示有n個(gè)數(shù)據(jù)，接著輸入n個(gè)數(shù)據(jù)（完成）第2行輸入要交換的兩個(gè)結(jié)點(diǎn)位置（完成）第3行輸入要交換的兩個(gè)結(jié)點(diǎn)位置（完成）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)假定兩個(gè)單鏈表是遞增有序，定義并實(shí)現(xiàn)以下函數(shù)，完成兩個(gè)單鏈表的合并，繼續(xù)保持遞增有序(2)int LL_merge(ListNode *La, Lis

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

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

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

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

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

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

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

15、，7和8匹配，11和12匹配。從中可以看到括號(hào)嵌套的的情況是比較復(fù)雜的，使用堆?？梢院芊奖愕奶幚磉@種括號(hào)匹配檢驗(yàn)，可以遵循以下規(guī)則：1、 當(dāng)接收第1個(gè)左括號(hào)，表示新的一組匹配檢查開始；隨后如果連續(xù)接收到左括號(hào)，則不斷進(jìn)堆棧。2、 當(dāng)接受第1個(gè)右括號(hào)，則和最新進(jìn)棧的左括號(hào)進(jìn)行匹配，表示嵌套中1組括號(hào)已經(jīng)匹配消除3、 若到最后，括號(hào)不能完全匹配，則說明輸入的表達(dá)式有錯(cuò)(3)建議使用C+自帶的stack對(duì)象來實(shí)現(xiàn)要求：Input第一行輸入一個(gè)t，表示下面將有t組測(cè)試數(shù)據(jù)。接下來的t行的每行輸入一個(gè)表達(dá)式，表達(dá)式只考慮英文半角狀態(tài)輸入，無需考慮中文全角輸入（完成）Output對(duì)于每一行的表達(dá)式，檢查括

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

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

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

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

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

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

22、b_pNexbb_pPre改變數(shù)值進(jìn)行交換：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àng)式相加線性表實(shí)現(xiàn)： 建立兩個(gè)數(shù)組分別存儲(chǔ)系數(shù)和指數(shù)。多項(xiàng)式相加的操作過程基本與合并相似。先比較指數(shù)，若指數(shù)較

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

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

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

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

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

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

29、者可以只粘貼重要的代碼（為了節(jié)省紙張），但代碼必須完整，至少是完整的函數(shù)。3. 代碼符合以下要求，評(píng)分更高：a. 排版整齊，可讀性高b. 代碼有注釋，越詳細(xì)越清晰越好DS實(shí)驗(yàn)01-順序表1. Problem A: DS順序表-類實(shí)現(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(); ; /構(gòu)造函數(shù)SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構(gòu)函數(shù)SeqList:SeqList() deletelist; /返回長(zhǎng)度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個(gè)數(shù)據(jù)，即n是實(shí)際長(zhǎng)度；接著輸入n個(gè)數(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行輸入要?jiǎng)h除的位置 cin>>position; if(L.list_del(position)=-1)cout<<"error"

35、;<<endl; else cout<<L.list_size()<<" " L.list_display(); /第5行輸入要?jiǎng)h除的位置 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(); ; /構(gòu)造函數(shù)SeqList

38、:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構(gòu)函數(shù)SeqList:SeqList() deletelist; /返回長(zhǎng)度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個(gè)數(shù)據(jù)，即n是實(shí)際長(zhǎng)度；接著輸入n個(gè)數(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個(gè)插入數(shù)據(jù)，接著輸入k個(gè)數(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表示要?jiǎng)h除k個(gè)數(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(); ; /構(gòu)造函數(shù)SeqList:SeqList() maxsize=1000; size=0; list=new intmaxsize; /析構(gòu)函數(shù)SeqList:SeqList() deletelist; /返回長(zhǎng)度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實(shí)驗(yàn)02-鏈表1. Problem A: DS單鏈表-類實(shí)現(xiàn)#include<iostream> using namespace std; #define ok 1 #define error -1; class Li