【正文】 axsize]。 void list_display()。 int list_size()。 int maxsize。 ()。 for(j=0。 (i++,NUM)。 //第 2 行先輸入 i 表示插入開始的位置，再輸入 k 表示有 k 個插入數(shù)據(jù)，接著輸入 k 個數(shù)據(jù) cinik。j++) { cinNUM。 SeqList L。jsize。 } //返回值函數(shù) int SeqList::list_get(int i) { if(i=0||isize)return error。jsize1。 return ok。ji1。 size++。 } //析構(gòu)函數(shù) SeqList::~SeqList() { delete[]list。 }。 int list_insert(int i,int item)。 int size。 return 0。 else cout(position)endl。 else { cout() 。 else { cout() 。 else { cout() 。 else { cout() 。 } cout() 。 for(i=0。 } coutendl。 } //輸出函數(shù) void SeqList::list_display() { int j。 } size。 int j。 } list[j]=item。 } int j。 } //插入函數(shù) int SeqList::list_insert(int i,int item) { if(isize+1||i0||size==maxsize)return error。 size=0。 int list_get(int i)。 ~SeqList()。 define ok 0 define error 1 //順序表類定義 class SeqList { private: int *list。如果有匹配到 j 就會大于 1； ⑤ ：子串有 j個字符，則 next 中用到的只有前 j 個。 DS 實(shí)驗(yàn) 04串應(yīng)用 KMP 算法 1. Problem A: DS 串應(yīng)用 KMP 算法 next[j]： ① ：第一為 0的 作用 是讓子串向右移動一格，此時 i 會變。建立存儲類型為類的棧 stackCPOS。而右括號出現(xiàn)的時候左括號以后的運(yùn)算符都已計(jì)算并變成數(shù) 字進(jìn)入了 OPND棧，所以右括號出現(xiàn)時候()彈出的必然是左括號。 OPTR先 PUSH入 號，輸入表達(dá)式時最后一位為 號，在 c= =()= =’ ’ 的時候結(jié)束表達(dá)式計(jì)算。 若右括號與 top()匹配則 pop()。 Push數(shù)值與 2的倍數(shù)取整進(jìn)棧然后逆向輸出。先判斷是否為 號且有多少個 號，若沒有 號則 push()字符進(jìn)第二個棧，有多少個 號就 pop()多少個。比線性表要簡單，直接把 Pa， Pb 里的系數(shù) 跟 指數(shù)創(chuàng)建一個結(jié)點(diǎn)放入多項(xiàng)式 Pc 中即可，相加直接在加入的時候完成。Pa,polynomai amp。 p)。 鏈表實(shí)現(xiàn)： Status MakeNode(Linkamp。 4. Problem D: DS 線性表 多項(xiàng)式相加 線性表實(shí)現(xiàn)： 建立兩個數(shù)組 分別存儲系數(shù)和指數(shù)。 qdata=temp。 2. Problem B: DS 單鏈表 結(jié)點(diǎn)交換 改變 指針 進(jìn)行 交換 ： a_pNex b_pNex a a_pPre b b_pPre 改變 數(shù)值 進(jìn)行 交換： int LinkList::swap(ListNode *p,ListNode *q) { if(p==head||q==head||!p||!q)return error。比順序表慢。比順序表快。 3. Problem C: DS 順序表 合并操作 合并操作：兩個線性表，分別讀取數(shù)字，比較兩數(shù)字大小，小的先插入第三個線性表， 一直讀到其中一個線性表 到底跳出循環(huán)，將另一條線性表里剩余的數(shù)字全都插在第三個線性表后。所耗時間比鏈表久。 要求： Input 第一行輸入 t，表示有 t 個迷宮 （ 完成） 第二行輸入 n，表示第一個迷宮有 n 行 n 列 （ 完成） 第 三行起，輸入迷宮每一行的每個方格的狀態(tài)， 0 表示可通過， 1 表示不可通過 輸入 n 行 （ 完成） 以此類推輸入下一個迷宮 Output 逐個輸出迷宮的路徑 （ 完成） 如果迷宮不存在路徑，則輸出 no path 并回車 （ 完成） 如果迷宮存在路徑，將路徑中每個方格的 x 和 y 坐標(biāo)輸出，從起點(diǎn)到終點(diǎn)，每輸出四個方格就換行，最終以單詞 END 結(jié)尾 （ 完成） DS 實(shí)驗(yàn) 04串應(yīng)用 KMP 算法 1. Problem A: DS 串應(yīng)用 KMP 算法 目的 ： (1) 學(xué)習(xí) KMP 算法，給出主串和模式串，求模式串在主串的位置 要求： Input 第一個輸入 t，表 示有 t 個實(shí)例 （ 完成） 第二行輸入第 1 個實(shí)例的主串，第三行輸入第 1 個實(shí)例的模式串 （ 完成） 以此類推 Output 第一行輸出第 1 個實(shí)例的模式串的 next 值 （ 完成） 第二行輸出第 1 個實(shí)例的匹配位置，位置從 1 開始計(jì)算，如果匹配成功輸出位置，匹配失敗輸出 0（ 完成） 以此類推 二、 主要思路與 方法： 1. 對于本次實(shí)驗(yàn)，說明你認(rèn)為最重要的函數(shù) 、 算法 或知識點(diǎn) ，并談?wù)勀銓?它們的 理解 DS 實(shí)驗(yàn) 01順序表 1. Problem A: DS 順序表 類實(shí)現(xiàn) 函數(shù)： list_insert(int i,int item)。組隊(duì)列是是指隊(duì)列內(nèi)的元素分組聚集在一起。例如表達(dá)式中包含括號如下： ( ) [ ( ) ( [ ] ) ] { } 1 2 3 4 5 6 7 8 9 10 11 12 (2)從上例可以看出第 1 和第 2 個括號匹配，第 3 和第 10 個括號匹配， 4 和 5 匹配，6 和 9 匹配， 7 和 8 匹配， 11 和 12 匹配。 要求： Input 第一行輸入先輸入 n 表示客戶數(shù)量 （ 完成） 第二行輸入每個客戶的類型，數(shù)據(jù)之間用用空格隔開 （ 完成） 第三行輸入每個客戶的辦理時間，數(shù)據(jù)之間用用空格隔開 （ 完成） Output 第一行輸出 A 類客戶的平均辦理時間 （ 完成） 第二行輸出 B 類客戶的平均辦理時間 （ 完成） 第三行輸出 C 類客戶的平均辦理時間 （ 完成） 3. Problem C: DS 堆棧 行編輯 目的 ： (1)使用 C++的 STL 堆棧對象，編寫程序?qū)崿F(xiàn)行編輯功能。 (4)可用順序 表或單鏈表實(shí)現(xiàn) 要求： Input 第 1 行：輸入 t 表示有 t 組測試數(shù)據(jù) （ 完成） 第 2 行：輸入 n 表示有第 1 組的第 1 個多項(xiàng)式包含 n 個項(xiàng) （ 完成） 第 3 行：輸入第一項(xiàng)的系數(shù)和指數(shù)，以此類推輸入 n 行 （ 完成） 接著輸入 m 表示第 1 組的第 2 個多項(xiàng)式包含 m 項(xiàng) （ 完成） 同理輸入第 2 個多項(xiàng)式的 m 個項(xiàng)的系數(shù)和指數(shù) （ 完成） 參考上面輸入第 2 組數(shù)據(jù)，以此類推輸入 t 組 （ 完成） 假設(shè)所有數(shù)據(jù)都是整數(shù) （ 完成） Output 對于每 1 組數(shù)據(jù)，先用兩行輸出兩個原來的多項(xiàng)式，再用一行輸出運(yùn)算結(jié)果，不必考慮結(jié)果全為 0 的情況 （ 完成） 輸出格式參考樣本數(shù) 據(jù)，格式要求包括： ，用小括號括起來 （ 完成） 0，則該項(xiàng)不用輸出 （ 完成） 0，則用符號 ^表示，例如 x 的 3 次方，表示為 x^3（ 完成） +連接，每個 +兩邊加 1 個空格隔開 （ 完成） DS 實(shí)驗(yàn) 03堆棧與隊(duì)列 1. Problem A: DS 堆棧 逆序輸出（ STL 棧使用） 目的 ： (1)C++中已經(jīng)自帶堆棧對象 stack，無需編寫堆棧操作的具體實(shí)現(xiàn)代碼。附件（四） 深 圳 大 學(xué) 實(shí) 驗(yàn) 報 告 課程名稱： 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)與課程設(shè)計(jì) 實(shí)驗(yàn)項(xiàng)目名稱 ： 順序表、鏈表、堆棧隊(duì)列、串 KMP 算法 學(xué)院 ： 專業(yè) ： 指導(dǎo)教師 ： 報告人 ： 學(xué)號 ： 班級： 實(shí)驗(yàn) 時間： 實(shí)驗(yàn)報告 提交 時間： 教務(wù)處制 一、 實(shí) 驗(yàn)?zāi)康呐c 完成說明 ： 1. 簡單介紹本實(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í)際長度、最大長度（設(shè)定為 1000） (3)操作包括：創(chuàng)建、插入、刪除、查找 要求 ： Input 第 1 行先輸入 n 表示有 n 個數(shù)據(jù)，即 n是實(shí)際長度；接著輸入 n個數(shù)據(jù) （ 完成） 第 2 行輸入要插入的位置和新數(shù)據(jù) （ 完成） 第 3 行輸入要插入的位置和新數(shù)據(jù) （ 完成） 第 4 行輸入要刪除的位置 （ 完成） 第 5 行輸入要刪除的位置 （ 完成） 第 6 行輸入要查找的位置 （ 完成） 第 7 行輸入要查找的位置 （ 完成） Output 第 1 行輸出創(chuàng)建后的順序表內(nèi)容，包括順序表實(shí)際長度 和數(shù)據(jù) （ 完成） 每成功執(zhí)行一次操作（插入或刪除），輸出執(zhí)行后的順序表內(nèi)容 （ 完成） 每成功執(zhí)行一次查找，輸出查找到的數(shù)據(jù) （ 完成） 如果執(zhí)行操作失?。òú迦搿h除、查找等失?。敵鲎址?error，不必輸出順序表內(nèi)容 （ 完成） 2. Problem B: DS 順序表 連續(xù)操作 目的 ： (1)建立順序表的類，屬性包括：數(shù)組、實(shí)際長度、最大長度（設(shè)定為 1000） (2)實(shí)現(xiàn)連續(xù)多個插入，即從位置 i 開始插入多個數(shù)據(jù) (3)實(shí)現(xiàn)連續(xù)多個刪除，即從位置 i 開始刪除多個數(shù)據(jù) 要求： Input 第 1 行先輸入 n 表示 有 n 個數(shù)據(jù)，即 n是實(shí)際長度；接著輸入 n個數(shù)據(jù) （ 完成） 第 2 行先輸入 i 表示插入開始的位置，再輸入 k 表示有 k 個插入數(shù)據(jù)，接著輸入 k個數(shù)據(jù) （ 完成） 第 3 行先輸入 i 表示刪除開始的位置，再輸入 k 表示要刪除 k個數(shù)據(jù) （ 完成） Output 順序表內(nèi)容包括順序表的實(shí)際長度和數(shù)據(jù)，數(shù)據(jù)之間用空格隔開 （ 完成） 第 1 行輸出創(chuàng)建后的順序表內(nèi)容 （ 完成） 第 2 行輸出執(zhí)行連續(xù)插入后的順序表內(nèi)容 （ 完成） 第 3 行輸出執(zhí)行連續(xù)刪除后的順序表內(nèi)容 （ 完成） 3. Problem C: DS 順序表 合并操作 目的 ： (1)建立順序表的類， 屬性包括：數(shù)組、實(shí)際長度、最大長度（設(shè)定為 1000） (2)已知兩個遞增序列，把兩個序列的數(shù)據(jù)合并到順序表中， (3)并使得順序表的數(shù)據(jù)遞增有序 。 x的 1 次方同理不顯示。每個窗口按 照客戶到來的順序進(jìn)行服務(wù)。 （ 完成） 接下來每行包含兩個參數(shù) n 和 k， n 表示要轉(zhuǎn)換的數(shù)值，可能是非整數(shù)； k 表示要轉(zhuǎn)換的數(shù)制， 1k=16（ 完成） Output 對于每一組測試數(shù)據(jù)，每行輸出轉(zhuǎn)換后的結(jié)果，結(jié)果精度到小數(shù)點(diǎn)后 3 位 （ 完成） 5. Problem E: DS 堆棧 括號匹配 目的 ：