【正文】 間比鏈表久。所耗時(shí)間比鏈表久。2. Problem B: DS順序表連續(xù)操作同Problem A: DS順序表類實(shí)現(xiàn)。3. Problem C: DS順序表合并操作合并操作：兩個(gè)線性表，分別讀取數(shù)字，比較兩數(shù)字大小，小的先插入第三個(gè)線性表，一直讀到其中一個(gè)線性表到底跳出循環(huán)，將另一條線性表里剩余的數(shù)字全都插在第三個(gè)線性表后。插入函數(shù)。比順序表快。返回值函數(shù)。比順序表慢。刪除函數(shù)。2. Problem B: DS單鏈表結(jié)點(diǎn)交換改變指針進(jìn)行交換：a_pNexb_pNexaa_pPrebb_pPrea_pNexaa_pPreb_pNexbb_pPre改變數(shù)值進(jìn)行交換：int LinkList::swap(ListNode *p,ListNode *q) { if(p==head||q==head||!p||!q)return error。 temp=pdata。 qdata=temp。 }3. Problem C: DS單鏈表合并 過(guò)程基本與線性表合并相同。4. Problem D: DS線性表多項(xiàng)式相加線性表實(shí)現(xiàn)： 建立兩個(gè)數(shù)組分別存儲(chǔ)系數(shù)和指數(shù)。先比較指數(shù)，若指數(shù)較小就插在最左邊，若指數(shù)相等則相加再插入。鏈表實(shí)現(xiàn)：Status MakeNode(Linkamp。分配一個(gè)結(jié)點(diǎn)Status CreatPolyn(polynomai amp。 p)。插入過(guò)程中比較指數(shù)大小按由小到大的順序插在相應(yīng)的位置里，如果有相同指數(shù)的則系數(shù)相加（系數(shù)可為正負(fù)），若系數(shù)為0則調(diào)用刪除函數(shù)刪除該結(jié)點(diǎn)。Pa,polynomai amp。Pc)。比線性表要簡(jiǎn)單，直接把Pa，Pb里的系數(shù)跟指數(shù)創(chuàng)建一個(gè)結(jié)點(diǎn)放入多項(xiàng)式Pc中即可，相加直接在加入的時(shí)候完成。2. Problem B: DS線性表綜合練習(xí)隊(duì)列之銀行排隊(duì)建立兩個(gè)隊(duì)列，一個(gè)為int，另一個(gè)為char，用于存儲(chǔ)時(shí)間和字符，在一個(gè)個(gè)用front()取值并用pop()彈出，用判斷語(yǔ)句進(jìn)行平均數(shù)求值。先判斷是否為號(hào)且有多少個(gè)號(hào)，若沒有號(hào)則push()字符進(jìn)第二個(gè)棧，有多少個(gè)號(hào)就pop()多少個(gè)。最后判斷第二個(gè)棧是否為空，不為空就輸出字符串，為空就輸出NULL。Push數(shù)值與2的倍數(shù)取整進(jìn)棧然后逆向輸出。若是左括號(hào)則進(jìn)棧。若右括號(hào)與top()匹配則pop()。6. Problem F: DS線性表綜合練習(xí)組隊(duì)列建立隊(duì)列數(shù)組，同組的元素進(jìn)入同一個(gè)隊(duì)列中。OPTR先PUSH入號(hào)，輸入表達(dá)式時(shí)最后一位為號(hào)，在c= =()= =’’的時(shí)候結(jié)束表達(dá)式計(jì)算。如果是小于，則直接讓c進(jìn)OPTR棧，再讀入下一個(gè)字符；如果是大于，則OPTR彈出一個(gè)運(yùn)算符，OPND彈出兩個(gè)數(shù)字進(jìn)行計(jì)算求值重新放回OPND棧；如果是等于則OPTR出棧消除括號(hào)。而右括號(hào)出現(xiàn)的時(shí)候左括號(hào)以后的運(yùn)算符都已計(jì)算并變成數(shù)字進(jìn)入了OPND棧，()彈出的必然是左括號(hào)。函數(shù)： Strcat(char[],char)在字符串后面加字符。建立存儲(chǔ)類型為類的棧stackCPOS。直到右邊不能走了就往下，如果右邊和下邊都不能走就pop（），同時(shí)剛剛的坐標(biāo)上直接標(biāo)記無(wú)法通行（1），然后判斷下邊能不能走。DS實(shí)驗(yàn)04串應(yīng)用KMP算法1. Problem A: DS串應(yīng)用KMP算法next[j]：① ：第一為0的作用是讓子串向右移動(dòng)一格，此時(shí)i會(huì)變。③ ：j取next[j]的時(shí)候i不變。如果有匹配到j(luò)就會(huì)大于1；⑤ ：子串有j個(gè)字符，則next中用到的只有前j個(gè)。三．實(shí)驗(yàn)程序或內(nèi)容：1. 針對(duì)每一項(xiàng)實(shí)驗(yàn)要求，給出編寫的代碼，2. 可以粘貼全部代碼，或者可以只粘貼重要的代碼（為了節(jié)省紙張），但代碼必須完整，至少是完整的函數(shù)。 define ok 0 define error 1 //順序表類定義 class SeqList { private: int *list。 int size。 ~SeqList()。 int list_insert(int i,int item)。 int list_get(int i)。 }。 size=0。 } //析構(gòu)函數(shù)SeqList::~SeqList() { delete[]list。 } //插入函數(shù)int SeqList::list_insert(int i,int item) { if(isize+1||i0||size==maxsize)return error。 size++。 } int j。ji1。 } list[j]=item。 return ok。 int j。jsize1。 } size。 } //返回值函數(shù)int SeqList::list_get(int i) { if(i=0||isize)return error。 } //輸出函數(shù)void SeqList::list_display() { int j。jsize。 } coutendl。 SeqList L。 for(i=0。i++) { cinNUM。 } cout() 。 //第2行輸入要插入的位置和新數(shù)據(jù) cinpositionNUM。 else { cout() 。 } //第3行輸入要插入的位置和新數(shù)據(jù) cinpositionNUM。 else { cout() 。 } //第4行輸入要?jiǎng)h除的位置 cinposition。 else { cout() 。 } //第5行輸入要?jiǎng)h除的位置 cinposition。 else { cout() 。 } //第6行輸入要查找的位置 cinposition。 else cout(position)endl。 if((position)==1)couterrorendl。 return 0。 define ok 0 define error 1 //順序表類定義 class SeqList { private: int *list。 int size。 ~SeqList()。 int list_insert(int i,int item)。 int list_get(int i)。 }。 size=0。 } //析構(gòu)函數(shù)SeqList::~SeqList() { delete[]list。 } //插入函數(shù)int SeqList::list_insert(int i,int item) { if(isize+1||i0||size==maxsize)return error。 size++。 } int j。ji1。 } list[j]=item。 return ok。 int j。jsize1。 } size。 } //返回值函數(shù)int SeqList::list_get(int i) { if(i=0||isize)return error。 } //輸出函數(shù)void SeqList::list_display() { int j。jsize。 } coutendl。 SeqList L。 for(j=0。j++) { cinNUM。 } cout() 。 //第2行先輸入i表示插入開始的位置，再輸入k表示有k個(gè)插入數(shù)據(jù)，接著輸入k個(gè)數(shù)據(jù) cinik。jk。 (i++,NUM)。 ()。 for(j=0。j++) { (i)。 ()。 }3. Problem C: DS順序表合并操作includeiostream using namespace std。 int maxsize。 public: SeqList()。 int list_size()。 int list_del(int i)。 void list_display()。 //構(gòu)造函數(shù)SeqList::SeqList() { maxsize=1000。 list=new int[maxsize]。 } //返回長(zhǎng)度int SeqList::list_size() { return size。 if(i==size+1) { list[i1]=item。 return ok。 for(j=size。j) { list[j]=list[j1]。 size++。 } //刪除函數(shù)int SeqList::list_del(int i) { if(isize||i0||size==0)return error。 for(j=i1。j++) { list[j]=list[j+1]。 return ok。 return list[i1]。 for(j=0。j++) { coutlist[j] 。 } int main() { int n,m,j,NUM。 cinn。jn。 (j+1,NUM)。 for(j=0。j++) { cinNUM。 } int i=1。 int k=1。 j++。 } if(j==()+1) { while(i()+1) { (k++,(i))。 } break。 j++。 } if((i)(j)) { (k++,(i))。 continue。 j++。 } } //排列End cout() 。 return 0。 define ok 1 define error 1。 ListNode *next。} }。 int len。 ~LinkList()。 int LL_get(int i)。 int LL_del(int i)。 }。 len=0。 p=head。 p=pnext。 } len=0。 } void LinkList::LL_display() { ListNode *p。 while(p) { coutpdata39。 p=pnext。 } ListNode* LinkList::LL_index(int i) { if(i=0||ilen)return NULL。 p=headnext。amp。 } return p。 ListNode *p=NULL。 while(pnext amp。 i) { p=pnext。 } int LinkList::LL_insert(int i,int item) { if(i0||ilen+1)return error。 p=new ListNode()。 if(i==1) { ListNode *pE。 headnext=p。 len++。 } if(i==len+1) { L