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

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

2、刪除、查查找要求：Input第1行先輸入nn表示有n個(gè)個(gè)數(shù)據(jù)，即nn是實(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ù)據(jù)（完成）每成功執(zhí)行一次次操作（插入入或刪除），輸輸出執(zhí)行后的的順序表內(nèi)容容（完成）每成功執(zhí)行一次次查找，輸出出查找到的數(shù)數(shù)據(jù)（完成）如果執(zhí)行操作失失?。òú宀迦?、刪除、查查找等失?。?，輸輸出字符串eer

3、ror，不不必輸出順序序表內(nèi)容（完成）2. Probblem BB: DS順順序表-連連續(xù)操作目的： (1)建立順序表表的類，屬性性包括：數(shù)組組、實(shí)際長(zhǎng)度度、最大長(zhǎng)度度（設(shè)定為11000）(2)實(shí)現(xiàn)連續(xù)續(xù)多個(gè)插入，即即從位置i開(kāi)開(kāi)始插入多個(gè)個(gè)數(shù)據(jù)(3)實(shí)現(xiàn)連續(xù)續(xù)多個(gè)刪除，即即從位置i開(kāi)開(kāi)始刪除多個(gè)個(gè)數(shù)據(jù)要求：Input第1行先輸入nn表示有n個(gè)個(gè)數(shù)據(jù)，即nn是實(shí)際長(zhǎng)度度；接著輸入入n個(gè)數(shù)據(jù)（完成）第2行先輸入ii表示插入開(kāi)開(kāi)始的位置，再再輸入k表示示有k個(gè)插入入數(shù)據(jù)，接著著輸入k個(gè)數(shù)數(shù)據(jù)（完成）第3行先輸入ii表示刪除開(kāi)開(kāi)始的位置，再再輸入k表示示要?jiǎng)h除k個(gè)個(gè)數(shù)據(jù)（完成）Output順序表內(nèi)容

4、包括括順序表的實(shí)實(shí)際長(zhǎng)度和數(shù)數(shù)據(jù)，數(shù)據(jù)之之間用空格隔隔開(kāi)（完成）第1行輸出創(chuàng)建建后的順序表表內(nèi)容（完成）第2行輸出執(zhí)行行連續(xù)插入后后的順序表內(nèi)內(nèi)容（完成）第3行輸出執(zhí)行行連續(xù)刪除后后的順序表內(nèi)內(nèi)容（完成）3. Probblem CC: DS順順序表-合合并操作目的： (1)建立順序表表的類，屬性性包括：數(shù)組組、實(shí)際長(zhǎng)度度、最大長(zhǎng)度度（設(shè)定為11000）(2)已知兩個(gè)個(gè)遞增序列，把把兩個(gè)序列的的數(shù)據(jù)合并到到順序表中，(3)并使得順順序表的數(shù)據(jù)據(jù)遞增有序。要求：Input第1行先輸入nn表示有n個(gè)個(gè)數(shù)據(jù)，接著著輸入n個(gè)數(shù)數(shù)據(jù)，表示第第1個(gè)序列，要要求數(shù)據(jù)遞增增互不等（完成）第2行先輸入mm表示有m

5、個(gè)個(gè)數(shù)據(jù)，接著著輸入m個(gè)數(shù)數(shù)據(jù)，表示第第2個(gè)序列，要要求數(shù)據(jù)遞增增互不等（完成）Output順序表內(nèi)容包括括順序表的實(shí)實(shí)際長(zhǎng)度和數(shù)數(shù)據(jù)，數(shù)據(jù)之之間用空格隔隔開(kāi)（完成）第1行輸出創(chuàng)建建后的順序表表內(nèi)容（完成）DS實(shí)驗(yàn)02-鏈表Problemm A: DDS單鏈表-類實(shí)現(xiàn)目的：(1)用C+語(yǔ)言和類實(shí)實(shí)現(xiàn)單鏈表，含含頭結(jié)點(diǎn)(2)屬性包括括：dataa數(shù)據(jù)域、nnext指針針域(3)操作包括括：插入、刪刪除、查找(4)注意：?jiǎn)螁捂湵聿皇菙?shù)數(shù)組，所以位位置從1開(kāi)始始對(duì)應(yīng)首結(jié)點(diǎn)點(diǎn)，頭結(jié)點(diǎn)不不放數(shù)據(jù)要求：Input第1行先輸入nn表示有n個(gè)個(gè)數(shù)據(jù)，接著著輸入n個(gè)數(shù)數(shù)據(jù)（完成）第2行輸入要插插入的位置和和新數(shù)

6、據(jù)（完成）第3行輸入要插插入的位置和和新數(shù)據(jù)（完成）第4行輸入要?jiǎng)h刪除的位置（完成）第5行輸入要?jiǎng)h刪除的位置（完成）第6行輸入要查查找的位置（完成）第7行輸入要查查找的位置（完成）Output數(shù)據(jù)之間用空格格隔開(kāi)，（完成）第1行輸出創(chuàng)建建后的單鏈表表的數(shù)據(jù)（完成）每成功執(zhí)行一次次操作（插入入或刪除），輸輸出執(zhí)行后的的單鏈表數(shù)據(jù)據(jù)（完成）每成功執(zhí)行一次次查找，輸出出查找到的數(shù)數(shù)據(jù)（完成）如果執(zhí)行操作失失敗（包括插插入、刪除、查查找等失?。斴敵鲎址甧error，不不必輸出單鏈鏈表（完成）Problemm B: DDS單鏈表-結(jié)點(diǎn)交換換目的：(1)用C+實(shí)現(xiàn)含頭結(jié)結(jié)點(diǎn)的單鏈表表，然后實(shí)現(xiàn)現(xiàn)單鏈

7、表的兩兩個(gè)結(jié)點(diǎn)交換換位置。(2)注意不能能簡(jiǎn)單交換兩兩個(gè)結(jié)點(diǎn)包含含數(shù)據(jù)，必須須通過(guò)修改指指針來(lái)實(shí)現(xiàn)兩兩個(gè)結(jié)點(diǎn)的位位置交換(3)交換函數(shù)數(shù)定義可以參參考：(4)swapp（int ppa, innt pb) /ppa和pb表表示兩個(gè)結(jié)點(diǎn)點(diǎn)在單鏈表的的位置序號(hào)(5)swapp (LisstNodee * p, ListtNode * q) /p和和q表示指向向兩個(gè)結(jié)點(diǎn)的的指針要求：Input第1行先輸入nn表示有n個(gè)個(gè)數(shù)據(jù)，接著著輸入n個(gè)數(shù)數(shù)據(jù)（完成）第2行輸入要交交換的兩個(gè)結(jié)結(jié)點(diǎn)位置（完成）第3行輸入要交交換的兩個(gè)結(jié)結(jié)點(diǎn)位置（完成）Output第一行輸出單鏈鏈表創(chuàng)建后的的所有數(shù)據(jù)，數(shù)數(shù)據(jù)之間用空

8、空格隔開(kāi)（完成）第二行輸出執(zhí)行行第1次交換換操作后的單單鏈表數(shù)據(jù)，數(shù)數(shù)據(jù)之間用空空格隔開(kāi)（完成）第三行輸出執(zhí)行行第2次交換換操作后的單單鏈表數(shù)據(jù)，數(shù)數(shù)據(jù)之間用空空格隔開(kāi)（完成）如果發(fā)現(xiàn)輸入位位置不合法，輸輸出字符串eerror，不不必輸出單鏈鏈表（完成）Problemm C: DDS單鏈表-合并目的：(1)假定兩個(gè)個(gè)單鏈表是遞遞增有序，定定義并實(shí)現(xiàn)以以下函數(shù)，完完成兩個(gè)單鏈鏈表的合并，繼繼續(xù)保持遞增增有序(2)int LL_meerge(LListNoode *LLa, LiistNodde *Lbb)要求：Input第1行先輸入nn表示有n個(gè)個(gè)數(shù)據(jù)，接著著輸入n個(gè)數(shù)數(shù)據(jù)（完成）第2行先輸入m

9、m表示有M個(gè)個(gè)數(shù)據(jù)，接著著輸入m個(gè)數(shù)數(shù)據(jù)（完成）Output輸出合并后的單單鏈表數(shù)據(jù)，數(shù)數(shù)據(jù)之間用空空格隔開(kāi)（完成）Problemm D: DDS線性表-多項(xiàng)式相相加目的：(1)對(duì)于一元元多項(xiàng)式 p(x)=p0+p11x+p2xx2+ +pnxxn ，每每個(gè)項(xiàng)都有系系數(shù)和指數(shù)兩兩部分，例如如p2x2的的系數(shù)為p22,指數(shù)為22(2)編程實(shí)現(xiàn)現(xiàn)兩個(gè)多項(xiàng)式式的相加例如5+x+22x2+3xx3，-5-x+6x22+4x4，兩兩者相加結(jié)果果：8x2+3x3+44x4 (3)其中系數(shù)數(shù)5和-5都都是x的0次次方的系數(shù)，相相加后為0，所所以不顯示。xx的1次方同同理不顯示。(4)可用順序序表或單鏈表表實(shí)

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

11、來(lái)（完成）2.如果系數(shù)為為0，則該項(xiàng)項(xiàng)不用輸出（完成）3.如果指數(shù)不不為0，則用用符號(hào)表示示，例如x的的3次方，表表示為x33（完成）4.多項(xiàng)式的每每個(gè)項(xiàng)之間用用符號(hào)+連接接，每個(gè)+兩兩邊加1個(gè)空空格隔開(kāi)（完成）DS實(shí)驗(yàn)03-堆棧與隊(duì)隊(duì)列Problemm A: DDS堆棧-逆序輸出（SSTL棧使用用）目的：(1)C+中中已經(jīng)自帶堆堆棧對(duì)象sttack，無(wú)無(wú)需編寫堆棧棧操作的具體體實(shí)現(xiàn)代碼。(2)本題目主主要幫助大家家熟悉staack對(duì)象的的使用，然后后實(shí)現(xiàn)字符串串的逆序輸出出(3)輸入一個(gè)個(gè)字符串，按按字符按輸入入順序壓入堆堆棧，然后根根據(jù)堆棧后進(jìn)進(jìn)先出的特點(diǎn)點(diǎn)，做逆序輸輸出要求：Input第

12、一行輸入t，表表示有t個(gè)測(cè)測(cè)試實(shí)例（完成）第二起，每一行行輸入一個(gè)字字符串，注意意字符串不要要包含空格（完成）Output每行逆序輸出每每一個(gè)字符串串（完成）Problemm B: DDS線性表綜綜合練習(xí)-隊(duì)列之銀行行排隊(duì)目的：(1)在銀行營(yíng)營(yíng)業(yè)大廳共服服務(wù)3種客戶，類類型為ABBC，大廳廳分別設(shè)置了了3個(gè)窗口分別別服務(wù)三種客客戶，即每個(gè)個(gè)窗口只服務(wù)務(wù)一種客戶?，F(xiàn)現(xiàn)有一批客戶戶來(lái)銀行辦理理業(yè)務(wù)，每個(gè)個(gè)客戶都有類類型和辦理業(yè)業(yè)務(wù)時(shí)間。每每個(gè)窗口按照照客戶到來(lái)的的順序進(jìn)行服服務(wù)。要求：Input第一行輸入先輸輸入n表示客客戶數(shù)量（完成）第二行輸入每個(gè)個(gè)客戶的類型型，數(shù)據(jù)之間間用用空格隔隔開(kāi)（完成）

13、第三行輸入每個(gè)個(gè)客戶的辦理理時(shí)間，數(shù)據(jù)據(jù)之間用用空空格隔開(kāi)（完成）Output第一行輸出A類類客戶的平均均辦理時(shí)間（完成）第二行輸出B類類客戶的平均均辦理時(shí)間（完成）第三行輸出C類類客戶的平均均辦理時(shí)間（完成）Problemm C: DDS堆棧-行編輯目的：(1)使用C+的STLL堆棧對(duì)象，編編寫程序?qū)崿F(xiàn)現(xiàn)行編輯功能能。行編輯功功能是：當(dāng)輸輸入#字符，則則執(zhí)行退格操操作；如果無(wú)無(wú)字符可退就就不操作，不不會(huì)報(bào)錯(cuò)(2)本程序默默認(rèn)不會(huì)顯示示#字符，所所以連續(xù)輸入入多個(gè)#表示示連續(xù)執(zhí)行多多次退格操作作(3)每輸入一一行字符打回回車則表示字字符串結(jié)束(4)注意：必必須使用堆棧棧實(shí)現(xiàn)，而且且結(jié)果必須是是

14、正序輸出要求：Input第一行輸入一個(gè)個(gè)整數(shù)t，表表示有t行字字符串要輸入入（完成）第二行起輸入一一行字符串，共共輸入t行（完完成）Output每行輸出最終處處理后的結(jié)果果，如果一行行輸入的字符符串經(jīng)過(guò)處理理后沒(méi)有字符符輸出，則直直接輸出NUULL（完成成）Problemm D: DDS線性表綜綜合練習(xí)-數(shù)制轉(zhuǎn)換目的：(1)對(duì)于任意意十進(jìn)制數(shù)轉(zhuǎn)轉(zhuǎn)換為k進(jìn)制制，包括整數(shù)數(shù)部分和小數(shù)數(shù)部分轉(zhuǎn)換。整整數(shù)部分采用用除k求余法法，小數(shù)部分分采用乘k取取整法例如xx=19.1125，求22進(jìn)制轉(zhuǎn)換整數(shù)部分19，小數(shù)部分0.12519 / 2 = 9 10.1255 * 2 = 0.225 009 / 2

15、= 4 10.25 * 2 = 0.5 004 / 2 = 2 0 0.5 * 2 = 1 12 / 2 = 1 01 / 2 = 0 1(2)所以整數(shù)數(shù)部分轉(zhuǎn)為 100111，小數(shù)部分分轉(zhuǎn)為0.0001，合起起來(lái)為100011.0001(3)提示整數(shù)數(shù)部分可用堆堆棧，小數(shù)部部分可用隊(duì)列列實(shí)現(xiàn)(4)注意：必必須按照上述述方法來(lái)實(shí)現(xiàn)現(xiàn)數(shù)制轉(zhuǎn)換，其其他方法0分分要求：Input第一行輸入一個(gè)個(gè)t，表示下下面將有t組組測(cè)試數(shù)據(jù)。（完成）接下來(lái)每行包含含兩個(gè)參數(shù)nn和k，n表表示要轉(zhuǎn)換的的數(shù)值，可能能是非整數(shù)；k表示要轉(zhuǎn)轉(zhuǎn)換的數(shù)制，11k=116（完成）Output對(duì)于每一組測(cè)試試數(shù)據(jù)，每行行輸出轉(zhuǎn)換

16、后后的結(jié)果，結(jié)結(jié)果精度到小小數(shù)點(diǎn)后3位位（完成）Problemm E: DDS堆棧-括號(hào)匹配目的：(1)處理表達(dá)達(dá)式過(guò)程中需需要對(duì)括號(hào)匹匹配進(jìn)行檢驗(yàn)驗(yàn)，括號(hào)匹配配包括三種：“(”和“)”，“”和和“”，“”和“”。例例如表達(dá)式中中包含括號(hào)如如下：()()()1234456789101112(2)從上例可可以看出第11和第2個(gè)括括號(hào)匹配，第第3和第100個(gè)括號(hào)匹配配，4和5匹匹配，6和99匹配，7和和8匹配，111和12匹匹配。從中可可以看到括號(hào)號(hào)嵌套的的情情況是比較復(fù)復(fù)雜的，使用用堆?？梢院芎芊奖愕奶幚砝磉@種括號(hào)匹匹配檢驗(yàn)，可可以遵循以下下規(guī)則：1、 當(dāng)接收第第1個(gè)左括號(hào)號(hào)，表示新的的一組匹配

17、檢檢查開(kāi)始；隨隨后如果連續(xù)續(xù)接收到左括括號(hào)，則不斷斷進(jìn)堆棧。2、 當(dāng)接受第第1個(gè)右括號(hào)號(hào)，則和最新新進(jìn)棧的左括括號(hào)進(jìn)行匹配配，表示嵌套套中1組括號(hào)號(hào)已經(jīng)匹配消消除3、 若到最后后，括號(hào)不能能完全匹配，則則說(shuō)明輸入的的表達(dá)式有錯(cuò)錯(cuò)(3)建議使用用C+自帶帶的stacck對(duì)象來(lái)實(shí)實(shí)現(xiàn)要求：Input第一行輸入一個(gè)個(gè)t，表示下下面將有t組組測(cè)試數(shù)據(jù)。接接下來(lái)的t行行的每行輸入入一個(gè)表達(dá)式式，表達(dá)式只只考慮英文半半角狀態(tài)輸入入，無(wú)需考慮慮中文全角輸輸入（完成）Output對(duì)于每一行的表表達(dá)式，檢查查括號(hào)是否匹匹配，匹配則則輸入ok，不不匹配則輸出出errorr（完成）Problemm F: DDS線性

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

19、個(gè)數(shù)和數(shù)數(shù)值第3行輸輸入一個(gè)第22組的元素個(gè)個(gè)數(shù)和數(shù)值，（完成但不嚴(yán)謹(jǐn)）以此類推輸入完完n組之后，開(kāi)開(kāi)始輸入多個(gè)個(gè)操作命令(datta;p-datta=q-data;q-datta=temmp; retturn ook; Problemm C: DDS單鏈表-合并 過(guò)程基基本與線性表表合并相同。不不同的是需要要調(diào)整指針。Problemm D: DDS線性表-多項(xiàng)式相相加線性表實(shí)現(xiàn)： 建建立兩個(gè)數(shù)組組分別存儲(chǔ)系系數(shù)和指數(shù)。多項(xiàng)式相加的操操作過(guò)程基本本與合并相似似。先比較指指數(shù)，若指數(shù)數(shù)較小就插在在最左邊，若若指數(shù)相等則則相加再插入入。一條多項(xiàng)項(xiàng)式插完后另另一條多項(xiàng)式式剩余系數(shù)指指數(shù)插在右邊邊。鏈

20、表實(shí)現(xiàn)：Status MakeNNode(LLink& p,EleemTypee e,EllemTyppe e1);分配一個(gè)個(gè)結(jié)點(diǎn)Status CreattPolynn(polyynomaii &P,LLink& p);將結(jié)結(jié)點(diǎn)插入多項(xiàng)項(xiàng)式中。插入入過(guò)程中比較較指數(shù)大小按由由小到大的順順序插在相應(yīng)應(yīng)的位置里，如如果有相同指指數(shù)的則系數(shù)數(shù)相加（系數(shù)數(shù)可為正負(fù)），若若系數(shù)為0則則調(diào)用刪除函函數(shù)刪除該結(jié)結(jié)點(diǎn)。Status AddPoolyn(ppolynoomai &Pa,poolynommai &PPb,pollynomaai &Pcc);多項(xiàng)式相加。比比線性表要簡(jiǎn)簡(jiǎn)單，直接把把Pa，Pbb里的系

21、數(shù)跟跟指數(shù)創(chuàng)建一一個(gè)結(jié)點(diǎn)放入入多項(xiàng)式Pcc中即可，相相加直接在加加入的時(shí)候完完成。DS實(shí)驗(yàn)03-堆棧與隊(duì)隊(duì)列Problemm A: DDS堆棧-逆序輸出（SSTL棧使用用）建立一個(gè)棧，將將數(shù)值pussh()進(jìn)棧棧后用topp()返回值值并pop()彈出值逆逆向輸出。Problemm B: DDS線性表綜綜合練習(xí)-隊(duì)列之銀行行排隊(duì)建立兩個(gè)隊(duì)列，一一個(gè)為，另一一個(gè)為，用用于存儲(chǔ)時(shí)間間和字符，在在一個(gè)個(gè)用ffront()取值并用用pop()彈出，用判判斷語(yǔ)句進(jìn)行行平均數(shù)求值值。Problemm C: DDS堆棧-行編輯建立兩個(gè)棧，用用其中一個(gè)棧棧存儲(chǔ)strring數(shù)組組的每一個(gè)字字符。先判斷斷是否為

22、#號(hào)號(hào)且有多少個(gè)個(gè)#號(hào)，若沒(méi)沒(méi)有#號(hào)則ppush()字符進(jìn)第二二個(gè)棧，有多多少個(gè)#號(hào)就就pop()多少個(gè)。全全程判斷棧是是否為空。最最后判斷第二二個(gè)棧是否為為空，不為空空就輸出字符符串，為空就就輸出NULLL。Problemm D: DDS線性表綜綜合練習(xí)-數(shù)制轉(zhuǎn)換Push數(shù)值與與進(jìn)制數(shù)的余余數(shù)進(jìn)棧然后后逆向輸出。Push數(shù)值與與2的倍數(shù)取取整進(jìn)棧然后后逆向輸出。Problemm E: DDS堆棧-括號(hào)匹配若棧為空時(shí)下一一個(gè)就是右括括號(hào)直接括號(hào)號(hào)不匹配。若是左括號(hào)則進(jìn)進(jìn)棧。一直進(jìn)左括號(hào)知知道有右括號(hào)號(hào)出現(xiàn)。若右括號(hào)與toop()匹配配則pop()。若括號(hào)匹配則棧棧為空。Problemm F:

23、DDS線性表綜綜合練習(xí)-組隊(duì)列建立隊(duì)列數(shù)組，同同組的元素進(jìn)進(jìn)入同一個(gè)隊(duì)隊(duì)列中。Problemm G: DDS堆棧-表達(dá)式計(jì)算算使用OPTR棧棧存儲(chǔ)運(yùn)算符符，使用OPPND棧存儲(chǔ)儲(chǔ)數(shù)字。OPTR先PUUSH入#號(hào)號(hào)，輸入表達(dá)達(dá)式時(shí)最后一一位為#號(hào)，在在c= =OOPTR.ttop()= =#的時(shí)候結(jié)束束表達(dá)式計(jì)算算。讀入字符的過(guò)程程中不斷有運(yùn)運(yùn)算符和數(shù)字字進(jìn)棧，直到到兩個(gè)運(yùn)算符符遭遇的時(shí)候候，判斷棧內(nèi)內(nèi)top()運(yùn)算符與cc內(nèi)運(yùn)算符的的優(yōu)先級(jí)，即即表達(dá)式中前前一個(gè)運(yùn)算符符與后一個(gè)運(yùn)運(yùn)算符的優(yōu)先先級(jí)。如果是小于，則則直接讓c進(jìn)進(jìn)OPTR棧棧，再讀入下下一個(gè)字符；如果是大于，則則OPTR彈彈出一個(gè)運(yùn)

24、算算符，OPNND彈出兩個(gè)個(gè)數(shù)字進(jìn)行計(jì)計(jì)算求值重新新放回OPNND棧；如果是等于則OOPTR出棧棧消除括號(hào)。只只有左括號(hào)和和右括號(hào)以及及兩個(gè)#號(hào)的的優(yōu)先級(jí)為等等于號(hào)。而右右括號(hào)出現(xiàn)的的時(shí)候左括號(hào)號(hào)以后的運(yùn)算算符都已計(jì)算算并變成數(shù)字字進(jìn)入了OPPND棧，所所以右括號(hào)出出現(xiàn)時(shí)候OPPTR.poop()彈出出的必然是左左括號(hào)。最后OPND會(huì)會(huì)剩下最后一一個(gè)數(shù)字即結(jié)結(jié)果。函數(shù)： Strrcat(cchar,charr)在字符串串后面加字符符。Problemm H: DDS堆棧-迷宮求解建立一個(gè)類CPPOS，對(duì)象象分別是xpp,yp作為為坐標(biāo)。建立立存儲(chǔ)類型為為類的棧sttack。從起點(diǎn)開(kāi)始如果果右邊能

25、走優(yōu)優(yōu)先往右。直直到右邊不能能走了就往下下，如果右邊邊和下邊都不不能走就poop（），同同時(shí)剛剛的坐坐標(biāo)上直接標(biāo)標(biāo)記無(wú)法通行行（1），然然后判斷下邊邊能不能走。坐坐標(biāo)軸到達(dá)了了右下角即成成功，如果最最后pop（）到到棧內(nèi)沒(méi)有元元素了的話就就說(shuō)明沒(méi)有路路徑。DS實(shí)驗(yàn)04-串應(yīng)用KKMP算法Problemm A: DDS串應(yīng)用-KMP算算法nextj：第一為0的作作用是讓子串串向右移動(dòng)一一格，此時(shí)ii會(huì)變。：1的作用是子子串換成第一一個(gè)字符再進(jìn)行比較，此此時(shí)i不會(huì)變變。：j取nexttj的時(shí)時(shí)候i不變。：如果一直沒(méi)有有匹配到，jj一直為1，nnextjj一直為00。如果有匹匹配到j(luò)就會(huì)會(huì)大于1；：

26、子串有j個(gè)字字符，則neext中用到到的只有前jj個(gè)。：nextjj大于0時(shí)時(shí)候表示調(diào)用用第nexttj個(gè)位位置的字符與與mainsstri匹配。三實(shí)驗(yàn)程序或或內(nèi)容：1. 針對(duì)每一一項(xiàng)實(shí)驗(yàn)要求求，給出編寫寫的代碼，2. 可以粘貼貼全部代碼，或或者可以只粘粘貼重要的代代碼（為了節(jié)節(jié)省紙張），但代碼必須須完整，至少少是完整的函函數(shù)。3. 代碼符合合以下要求，評(píng)評(píng)分更高：a. 排版整齊齊，可讀性高高b. 代碼有注注釋，越詳細(xì)細(xì)越清晰越好好DS實(shí)驗(yàn)01-順序表1. Probblem AA: DS順順序表-類類實(shí)現(xiàn)#includde using nnamesppace sstd; #definee ok

27、 00 #definee erroor -1 /順序表類定定義 class SSeqLisst privatee: intt *lisst; intt maxssize; intt sizee; public: SeqqList(); SeeqListt(); intt listt_sizee(); intt listt_inseert(innt i,intt itemm); intt listt_del(int i); intt listt_get(int i); voiid lisst_dissplay(); ; /構(gòu)造函數(shù)SeqListt:SeqqList() maxxsize=1000

28、; sizze=0; lisst=neww intmaaxsizee; /析構(gòu)函數(shù)SeqListt:SeeqListt() delletelist; /返回長(zhǎng)度int SeqqList:listt_sizee() retturn ssize; /插入函數(shù)int SeqqList:listt_inseert(innt i,intt itemm) if(isizze+1|ii-1;jj-) listtj=llistjj-1; lisstj=item; sizze+; retturn ook; /刪除函數(shù)int SeqqList:listt_del(int i) if(isizze|i0|siize

29、=00)retuurn errror; intt j; forr(j=i-1;jssize-11;j+) listtj=llistjj+1; sizze-; retturn ook; /返回值函數(shù)數(shù)int SeqqList:listt_get(int i) if(isiize)retturn eerror; retturn llistii-1; /輸出函數(shù)void SeeqListt:lisst_dissplay() intt j; forr(j=0;jsizze;j+) couttlisstj ; couutn; forr(i=0;iNUM; L.liist_innsert(i+1,NNUM

30、); couutL.list_size()possitionnNUMM; if(L.lisst_inssert(ppositiion,NUUM)=-1)couuteerrorenddl; elsse couutL.list_size()possitionnNUMM; if(L.lisst_inssert(ppositiion,NUUM)=-1)couuteerrorenddl; elsse couutL.list_size()possitionn; if(L.lisst_dell(posiition)=-1)couterrrorendl; elsse couutL.list_size()pos

31、sitionn; if(L.lisst_dell(posiition)=-1)couterrrorendl; elsse couutL.list_size()possitionn; if(L.lisst_gett(posiition)=-1)couterrrorendl; elsee couutL.list_get(ppositiion)possitionn; if(L.lisst_gett(posiition)=-1)couterrrorendl; elsee couutL.list_get(ppositiion)endl; retturn 00; 2.Probllem B: DS順序序表-

32、連續(xù)續(xù)操作#includde using nnamesppace sstd; #definee ok 00 #definee erroor -1 /順序表類定定義 class SSeqLisst privatee: intt *lisst; intt maxssize; intt sizee; public: SeqqList(); SeeqListt(); intt listt_sizee(); intt listt_inseert(innt i,intt itemm); intt listt_del(int i); intt listt_get(int i); voiid lisst_di

33、ssplay(); ; /構(gòu)造函數(shù)SeqListt:SeqqList() maxxsize=1000; sizze=0; lisst=neww intmaaxsizee; /析構(gòu)函數(shù)SeqListt:SeeqListt() delletelist; /返回長(zhǎng)度int SeqqList:listt_sizee() retturn ssize; /插入函數(shù)int SeqqList:listt_inseert(innt i,intt itemm) if(isizze+1|ii-1;jj-) listtj=llistjj-1; lisstj=item; sizze+; retturn ook; /刪除

34、函數(shù)int SeqqList:listt_del(int i) if(isizze|i0|siize=00)retuurn errror; intt j; forr(j=i-1;jssize-11;j+) listtj=llistjj+1; sizze-; retturn ook; /返回值函數(shù)數(shù)int SeqqList:listt_get(int i) if(isiize)retturn eerror; retturn llistii-1; /輸出函數(shù)void SeeqListt:lisst_dissplay() intt j; forr(j=0;jsizze;j+) couttlisstj

35、 ; couutn; forr(j=0;jNUM; L.liist_innsert(j+1,NNUM); couutL.list_size()ik; forr(j=0;jNUM; L.liist_innsert(i+,NNUM); couutL.list_size()ik; forr(j=0;jk;jj+) L.liist_deel(i); couutL.list_size() ; L.llist_ddisplaay(); retturn 00; 3. Probblem CC: DS順順序表-合合并操作#includde using nnamesppace sstd; #definee ok

36、00 #definee erroor -1 /順序表類定定義 class SSeqLisst privatee: intt *lisst; intt maxssize; intt sizee; public: SeqqList(); SeeqListt(); intt listt_sizee(); intt listt_inseert(innt i,intt itemm); intt listt_del(int i); intt listt_get(int i); voiid lisst_dissplay(); ; /構(gòu)造函數(shù)SeqListt:SeqqList() maxxsize=1000;

37、 sizze=0; lisst=neww intmaxsiize; /析構(gòu)函數(shù)SeqListt:SeeqListt() delletelist; /返回長(zhǎng)度int SeqqList:listt_sizee() retturn ssize; /插入函數(shù)int SeqqList:listt_inseert(innt i,intt itemm) if(isizze+1|ii-1;jj-) listtj=llistjj-1; lisstj=item; sizze+; retturn ook; /刪除函數(shù)int SeqqList:listt_del(int i) if(isizze|i0|siize=0

38、0)retuurn errror; intt j; forr(j=i-1;jssize-11;j+) listtj=llistjj+1; sizze-; retturn ook; /返回值函數(shù)數(shù)int SeqqList:listt_get(int i) if(isiize)reeturn errorr; retturn llistii-1; /輸出函數(shù)void SeeqListt:lisst_dissplay() intt j; forr(j=0;jsizze;j+) couttlisstj ; couutn; forr(j=0;jNUM; L1.llist_iinsertt(j+1,NUM)

39、; cinnm; forr(j=0;jNUM; L2.llist_iinsertt(j+1,NUM); intt i=1; j=11; int k=11; /排列Staart whiile(iL1.liist_siize()+1|jL2.liist_siize()+1) if(i=L1.liist_siize()+1) whilee(jL22.listt_sizee()+1) LL3.lisst_inssert(kk+,L22.listt_get(j); jj+; breakk; if(j=L2.liist_siize()+1) whilee(iL2.list_get(jj) L3.liist

40、_innsert(k+,LL2.lisst_gett(j); j+; contiinue; if(L1.list_get(ii)L2.list_get(jj) L3.liist_innsert(k+,LL1.lisst_gett(i); i+; contiinue; if(L1.list_get(ii)=L22.listt_get(j) L3.liist_innsert(k+,LL2.lisst_gett(j); j+; contiinue; /排列Endd couutL33.listt_sizee() ; L3.list_displlay(); retturn 00; DS實(shí)驗(yàn)02-鏈表Pr

41、oblemm A: DDS單鏈表-類實(shí)現(xiàn)#includde using nnamesppace sstd; #definee ok 11 #definee erroor -1; class LListNoode public: intt dataa; LisstNodee *nexxt; LisstNodee()neext=NUULL; ; class LLinkLiist public: LisstNodee *heaad; intt len; LinnkListt(); LiinkLisst(); LisstNodee *LL_indexx(int i); intt LL_gget(inn

42、t i); intt LL_iinsertt(int i,int ittem); intt LL_ddel(innt i); voiid LL_displlay(); ; LinkLisst:LiinkLisst() heaad= neew LisstNodee(); lenn=0; LinkLisst:LLinkLiist() LisstNodee *p,*q; p=hhead; whiile(p!=NULLL) q=p; p=p-nextt; deleete q; lenn=0; heaad=NULLL; void LiinkLisst:LLL_dispplay() LisstNodee

43、*p; p=hhead-next; whiile(p) couttdatanextt; couutenndl; ListNodde* LiinkLisst:LLL_indeex(intt i) if(ileen)retturn NNULL; LisstNodee *p; p=hhead-next; whiile(p-nextt & -i) p=p-nextt; retturn pp; int LinnkListt:LL_get(iint i) if(ilenn)retuurn errror; LisstNodee *p=NNULL; p=hhead-next; whiile(p-nextt &

44、 -i) p=p-nextt; retturn pp-datta; int LinnkListt:LL_inserrt(intt i,intt itemm) if(ilenn+1)reeturn errorr; LisstNodee *p; p=nnew LiistNodde(); p-data=item; if(i=1) ListtNode *pE; pE=hhead-next; headd-nexxt=p; p-nnext=ppE; len+; retuurn okk; if(i=leen+1) ListtNode *pE; pE=hhead-next; whille(pE-nextt)

45、pE=pEE-nexxt; pE-next=p; len+; retuurn okk; elsse ListtNode *pE,*pN; pE=hhead-next; pN=ppE; whille(pE-nextt & -i) pN=pEE; pE=pEE-nexxt; pN-next=p; p-nnext=ppE; len+; retturn ook; int LinnkListt:LL_del(iint i) if(ilenn)retuurn errror; LisstNodee *pE; if(i=1) pE=hhead-next-nextt; headd-nexxt=pE; len-;

46、 retuurn okk; elsse ListtNode *pN; pE=hhead-next; whille(pE-nextt & -i) pN=pEE; pE=pEE-nexxt; pE=ppE-neext; pN-next=pE; len-; retuurn okk; int maiin() int n,i,NNUM,poositioon; LinnkListt L; /第1行先輸輸入n表示有有n個(gè)數(shù)據(jù)，即即n是實(shí)際長(zhǎng)長(zhǎng)度；接著輸輸入n個(gè)數(shù)據(jù)據(jù) cinnn; forr(i=0;iNUM; L.LLL_inseert(i+1,NUMM); L.LLL_dissplay(); /第2行輸入

47、入要插入的位位置和新數(shù)據(jù)據(jù) cinnpossitionnNUMM; if(L.LL_inserrt(possitionn,NUM)=-1)couterrrorpossitionnNUMM; if(L.LL_inserrt(possitionn,NUM)=-1)couterrrorpossitionn; if(L.LL_del(ppositiion)=-1)coouterrorrpossitionn; if(L.LL_del(ppositiion)=-1)coouterrorrpossitionn; if(L.LL_get(ppositiion)=-1)coouterrorrenndl; els

48、ee couutL.LL_geet(possitionn)possitionn; if(L.LL_get(ppositiion)=-1)coouterrorrenndl; elsee couutL.LL_geet(possitionn)enndl; retturn 00; 2.Probblem BB: DS單單鏈表-結(jié)結(jié)點(diǎn)交換#includde using nnamesppace sstd; #definee ok 11 #definee erroor -1; class LListNoode public: intt dataa; LisstNodee *nexxt; LisstNodee(

49、)neext=NUULL; ; class LLinkLiist public: LisstNodee *heaad; intt len; LinnkListt(); LiinkLisst(); LisstNodee *LL_indexx(int i); intt LL_gget(innt i); intt LL_iinsertt(int i,int ittem); intt LL_ddel(innt i); voiid LL_displlay(); intt swapp(int ppa, innt pb); intt swapp(ListtNode *p,LiistNodde *q); ;

50、LinkLisst:LiinkLisst() heaad= neew LisstNodee(); lenn=0; LinkLisst:LLinkLiist() LisstNodee *p,*q; p=hhead; whiile(p!=NULLL) q=p; p=p-nextt; deleete q; lenn=0; heaad=NULLL; void LiinkLisst:LLL_dispplay() LisstNodee *p; p=hhead-next; couutdataa; p=pp-nexxt; whiile(p) coutt data; p=p-nextt; couutenndl;

51、 ListNodde* LiinkLisst:LLL_indeex(intt i) if(ilenn)retuurn NUULL; if(i=0)returrn heaad; LisstNodee *p; p=hhead-next; whiile(p-nextt & -i) p=p-nextt; retturn pp; int LinnkListt:LL_get(iint i) if(ilenn)retuurn errror; retturn LLL_inddex(i)-datta; int LinnkListt:LL_inserrt(intt i,intt itemm) if(ilenn+1

52、)reeturn errorr; LisstNodee *p; p=nnew LiistNodde; p-data=item; if(i=leen+1) LL_iindex(len)-nextt=p; len+; retuurn okk; elsse ListtNode *pNexx,*pPrre; pNexx=LL_iindex(i-1); pPree=LL_iindex(i); pNexx-nexxt=p; p-nnext=ppPre; len+; retuurn okk; int LinnkListt:LL_del(iint i) if(ilenn)retuurn errror; Lis

53、stNodee *pNeex,*pPPre; pNeex=LL_indexx(i-1); pPrre=LL_indexx(i+1); pNeex-neext=pPPre; lenn-; retturn ook; int LinnkListt:swaap(intt pa, int pbb) if(pallen|ppbleen)retturn eerror; LisstNodee *a_ppNex,*a,*a_pPre,*b_pNNex,*bb,*b_ppPre; a_ppNex=LLL_inddex(paa-1); a=LLL_inddex(paa); a_ppPre=LLL_inddex(pa

54、a+1); b_ppNex=LLL_inddex(pbb-1); b=LLL_inddex(pbb); b_ppPre=LLL_inddex(pbb+1); if(a-neext=bb) a_pNNex-nnext=bb; b-nnext=bb_pNexx; b_pNNex-nnext=bb_pPree; retuurn okk; if(b-neext=aa) b_pNNex-nnext=aa; a-nnext=aa_pNexx; a_pNNex-nnext=aa_pPree; retuurn okk; a_ppNex-next=b; b-next=a_pPrre; b_ppNex-next=

55、a; a-next=b_pPrre; retturn ook; /改變指針進(jìn)進(jìn)行交換int LinnkListt:swaap(LisstNodee *p,LListNoode *qq) if(p=heead|qq=heaad|!pp|!q)returrn errror; LisstNodee *a_ppNex,*a,*a_pPre,*b_pNNex,*bb,*b_ppPre; a=pp; a_ppPre=pp-nexxt; b=qq; b_ppPre=qq-nexxt; a_ppNex=hhead; b_ppNex=hhead; whiile(a_pNex-nextt!=p) a_pNNex=

56、a_pNex-nextt; whhile(bb_pNexx-nexxt!=q) b_pNNex=b_pNex-nextt; if(a-neext=bb) a_pNNex-nnext=bb; b-nnext=bb_pNexx; b_pNNex-nnext=bb_pPree; retuurn okk; if(b-neext=aa) b_pNNex-nnext=aa; a-nnext=aa_pNexx; a_pNNex-nnext=aa_pPree; retuurn okk; a_ppNex-next=b; b-next=a_pPrre; b_ppNex-next=a; a-next=b_pPrre

57、; retturn ook; /*改變變數(shù)值進(jìn)行交交換int LinnkListt:swaap(LisstNodee *p,LListNoode *qq) if(p=heead|qq=heaad|!pp|!q)returrn errror; int teemp;temp=pp-datta;p-datta=q-data;q-datta=temmp; retturn ook; */ int maiin() int n,i,NNUM,nuum1,nuum2; LinnkListt L; /第1行先輸輸入n表示有有n個(gè)數(shù)據(jù)，即即n是實(shí)際長(zhǎng)長(zhǎng)度；接著輸輸入n個(gè)數(shù)據(jù)據(jù) cinnn; forr(i=0;iN

58、UM; L.LLL_inseert(i+1,NUMM); if(n!=0)L.LL_displlay(); /第2行輸入入要交換的兩兩個(gè)結(jié)點(diǎn)位置置 cinnnumm1nuum2; if(L.swaap(numm1,numm2)=-1)couuteerrornumm1nuum2; if(L.swaap(L.LLL_inddex(nuum1),LL.LL_iindex(num2)=-11)coutterrrorendll; elsse L.LLL_dissplay(); retturn 00; 3.Probblem CC: DS單單鏈表-合合并#includde using nnamesppace

59、 sstd; #definee ok 11 #definee erroor -1; class LListNoode public: intt dataa; LisstNodee *nexxt; LisstNodee()neext=NUULL; ; class LLinkLiist public: LisstNodee *heaad; intt len; LinnkListt(); LiinkLisst(); LisstNodee *LL_indexx(int i); intt LL_gget(innt i); intt LL_iinsertt(int i,int ittem); intt L

60、L_ddel(innt i); voiid LL_displlay(); intt swapp(int ppa, innt pb); intt swapp(ListtNode *p,LiistNodde *q); intt LL_mmerge(ListNNode *La, LListNoode *LLb) ; ; LinkLisst:LiinkLisst() heaad= neew LisstNodee(); lenn=0; LinkLisst:LLinkLiist() LisstNodee *p,*q; p=hhead; whiile(p!=NULLL) q=p; p=p-nextt; de