數(shù)據(jù)結(jié)構(gòu)與算法線性表練習(xí)題

1、三、寫(xiě)一個(gè)算法合并兩個(gè)已排序的線性表。（用兩種方法：數(shù)組表示的線性表（順序表）和指針表示的線性表（鏈表）要求：1、定義線性表節(jié)點(diǎn)的結(jié)構(gòu)，并定義節(jié)點(diǎn)的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main函數(shù)中進(jìn)行測(cè)試：先構(gòu)建兩個(gè)有序的線性表，然后合并這兩個(gè)線性表。四、已知一個(gè)單向鏈表，試給出復(fù)制該鏈表的算法。要求：1、定義線性表的節(jié)點(diǎn)的結(jié)構(gòu)以及節(jié)點(diǎn)的型和位置的型。 2、定義線性表的基本操作 3、在1，2的基礎(chǔ)上，完成本題。 4、在main函數(shù)中進(jìn)行測(cè)試：先構(gòu)建一個(gè)線性表，并定義一個(gè)空線性表，然后進(jìn)行復(fù)制。五、寫(xiě)出從一個(gè)帶表頭的單鏈表中刪除其值等于給定值x的結(jié)

2、點(diǎn)的算法函數(shù)：int delete(LIST &L, int x);如果x在該鏈表中，則刪除對(duì)應(yīng)結(jié)點(diǎn)，并返回其在鏈表中的位置（邏輯位置，第一個(gè)結(jié)點(diǎn)的邏輯位置為1），否則返回-1。要求：1、定義線性表的節(jié)點(diǎn)的結(jié)構(gòu)以及節(jié)點(diǎn)的型和位置的型。2、定義線性表的基本操作3、在1，2的基礎(chǔ)上，完成本題。4、在main函數(shù)中進(jìn)行測(cè)試：先構(gòu)建一個(gè)線性表，然后調(diào)用函數(shù)刪除值等于給定值的節(jié)點(diǎn)。六、寫(xiě)出一個(gè)將兩個(gè)靜態(tài)鏈表（屬于同一個(gè)存儲(chǔ)池）合并的算法函數(shù)： void Merge(cursor M, cursor N); 合并的方法是將N鏈表中的所有結(jié)點(diǎn)添加到M鏈表的后面，并將N鏈表的表頭結(jié)點(diǎn)添加到空閑結(jié)點(diǎn)鏈表

3、中。要求：1、定義靜態(tài)鏈表的結(jié)點(diǎn)的結(jié)構(gòu)以及結(jié)點(diǎn)的型SPACE以及位置（position）和游標(biāo)（cursor）的型。2、定義靜態(tài)鏈表的基本操作：void Initialize(); 初始化，將所有存儲(chǔ)池中的結(jié)點(diǎn)設(shè)置為空閑；cursor GetNode(); 從空閑鏈中獲取一個(gè)結(jié)點(diǎn)；void FreeNode(cursor q); 將結(jié)點(diǎn)q加入到空閑鏈； void Insert ( elementtype x, position p, cursor M ); 在鏈表M中的位置為p的元素后面添加一個(gè)值為x的結(jié)點(diǎn)；void Delete (cursor M, position p ); 在鏈表M中刪

4、除位置為p的元素的后一個(gè)元素。3、在1、2的基礎(chǔ)上完成本題。4、在main函數(shù)中進(jìn)行測(cè)試：先構(gòu)建一個(gè)存儲(chǔ)池，然后在該存儲(chǔ)池中創(chuàng)建兩個(gè)靜態(tài)表，最后將這兩個(gè)靜態(tài)表合并。七、利用指針表示的線性表(鏈表)表示一個(gè)多項(xiàng)式，并實(shí)現(xiàn)兩個(gè)多項(xiàng)式的相加和相乘運(yùn)算。假設(shè)多項(xiàng)式形式為： 其中，系數(shù)ai0，指數(shù)ei滿足em>em-1>>e2>e1>=0。要求：1、定義多項(xiàng)式每一項(xiàng)的結(jié)構(gòu)。2、定義兩個(gè)多項(xiàng)式的相加和相乘運(yùn)算函數(shù)。3、在main函數(shù)中，構(gòu)建兩個(gè)多項(xiàng)式，并測(cè)試相加和相乘運(yùn)算。八、試編寫(xiě)一個(gè)整數(shù)進(jìn)制轉(zhuǎn)換的通用函數(shù)convert(int num, STACK S, int n)，要

5、求將整數(shù)m轉(zhuǎn)換為n進(jìn)制數(shù)，n進(jìn)制數(shù)的各位依次存放在棧S中。并在主函數(shù)中進(jìn)行測(cè)試。要求：1、定義棧以及棧的型。2、定義棧的各種操作。 3、實(shí)現(xiàn)函數(shù)convert。 4、在main函數(shù)中，通過(guò)調(diào)用函數(shù)convert將num的n進(jìn)制數(shù)存放到一個(gè)棧中，并通過(guò)出棧的方法輸出該n進(jìn)制數(shù)九、設(shè)有一個(gè)循環(huán)隊(duì)列Queue，只有頭指針front，不設(shè)尾指針，另設(shè)一個(gè)含有元素個(gè)數(shù)的計(jì)數(shù)器count，試寫(xiě)出相應(yīng)的判斷隊(duì)列空、判斷隊(duì)列滿、出隊(duì)算法和入隊(duì)算法。要求：1、定義相應(yīng)的循環(huán)隊(duì)列的型（只有頭指針，沒(méi)有尾指針，但有一個(gè)元素個(gè)數(shù)的計(jì)數(shù)器）；2、定義該隊(duì)列的四個(gè)算法：判斷隊(duì)列空、判斷隊(duì)列滿、出隊(duì)算法和入隊(duì)算法；3、在m

6、ain函數(shù)驗(yàn)證算法的正確性。十、設(shè)主串T=“abcaabbabcabaacbacba“，模式為p=“abcabaa”。 1、計(jì)算模式p的nextval函數(shù)值2、不寫(xiě)算法，只畫(huà)出利用KMP算法進(jìn)行模式匹配時(shí)，每一趟的匹配過(guò)程。要求：1、寫(xiě)出模式p的nextval值；2、畫(huà)出KMP算法的每一趟匹配過(guò)程（可參照教材P61從第8行開(kāi)始的內(nèi)容）；3、不需要編寫(xiě)程序。十一、假設(shè)表達(dá)式中允許包含三種括號(hào)：圓括號(hào)、方括號(hào)和大括號(hào)。設(shè)計(jì)一個(gè)算法采用順序棧（用數(shù)組表示的棧）判斷表達(dá)式中的括號(hào)是否正確配對(duì)。要求： 1、定義棧以及棧的型，棧中所存放元素的類(lèi)型為字符型，定義枚舉類(lèi)型Boolean，其中兩個(gè)元素分別為T(mén)R

7、UE和FALSE。2、定義棧的各種操作。3、定義函數(shù)Boolean check(char *s); 判斷s中的括號(hào)是否正確配對(duì)，如果正確配對(duì)，返回TRUE，否則返回FALSE。4、在主函數(shù)中驗(yàn)證所編寫(xiě)函數(shù)的正確性。十二、設(shè)有一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表h，設(shè)計(jì)一個(gè)算法用于查找第一個(gè)元素之為x的結(jié)點(diǎn)，并將其與其前驅(qū)結(jié)點(diǎn)進(jìn)行交換。要求： 1、定義帶頭結(jié)點(diǎn)的雙向鏈表的型DLIST。 2、定義雙向鏈表DLIST的基本操作。 3、定義函數(shù)int swap(elementtype x, DLIST &h)，查找第一個(gè)元素之為x的結(jié)點(diǎn)，如果在鏈表中存在元素值為x的結(jié)點(diǎn)，并其與其前驅(qū)結(jié)點(diǎn)進(jìn)行交換，并返回1，

8、否則返回0。 4、在主函數(shù)中測(cè)試所編寫(xiě)函數(shù)的正確性。十三、試編寫(xiě)一個(gè)求三元組順序表示的稀疏矩陣對(duì)角線元素之和的算法十四、當(dāng)具有相同行值和列值的稀疏矩陣A和B均以三元組順序表方式存儲(chǔ)時(shí)，試寫(xiě)出矩陣相加的算法，其結(jié)果存放在以行邏輯鏈接順序表方式存儲(chǔ)的矩陣C中。十五、設(shè)有一個(gè)稀疏矩陣：1、寫(xiě)出三元組順序表存儲(chǔ)表示2、寫(xiě)出十字鏈表存儲(chǔ)的順序表示十六、畫(huà)出廣義表LS=( ), (e), (a, (b, c, d)的頭尾鏈表存儲(chǔ)結(jié)構(gòu)(類(lèi)似于教材P70圖2-27.9)。要求：按照教材中的事例畫(huà)出相應(yīng)的圖形，不需要編程。t 其中第一個(gè)節(jié)點(diǎn)如下： 十七、試編寫(xiě)求廣義表中原子元素個(gè)數(shù)的算法。要求：1、定義廣義表的

9、節(jié)點(diǎn)的型；2、定義廣義表的基本操作；3、定義本題要求的函數(shù)int elements(listpointer L)；函數(shù)返回值為廣義表中原子的個(gè)數(shù)。例如，廣義表(a, b, c, d)原子的個(gè)數(shù)為4，而廣義表(a, (a, b), d, e, (i, j), k)中院子的個(gè)數(shù)為3。提示：先利用基本操作Cal(L)獲得表頭，判斷表頭是不是原子，再利用基本操作Cdr(L)獲得除第一個(gè)元素外的其他元素所形成的表L1，利用遞歸的方法求L1中原子的個(gè)數(shù)。要求：1、上述作業(yè)要求在單獨(dú)完成；2、完成后，于規(guī)定期限內(nèi)提交到ftp服務(wù)器的相應(yīng)目錄中中，注意，在提交時(shí)將所編寫(xiě)的程序統(tǒng)一拷貝到一個(gè)Word文件中，文件

10、名格式為“學(xué)號(hào)+姓名”三（數(shù)組表示）#include<iostream>using namespace std;#define maxlength 100typedef int position;typedef int Elementtype;struct LISTElementtype elementsmaxlength;int last;position End(LIST L)/線性表長(zhǎng)度 return (L.last+1);void Insert(Elementtype x,position p,LIST&L)position q;if(L.last>=maxl

11、ength-1)cout<<"list is full"<<endl;else if(p>L.last+1)|(p<1)cout<<"position does not exit"<<endl;elsefor(q=L.last;q>=p;q-)L.elementsq+1=L.elementsq;L.last=L.last+1;L.elementsp=x; void Delete(position p,LIST &L)position q;if(p>L.last)|(p<

12、1)cout<<"position does not exist"<<endl;elseL.last=L.last-1;for(q=p;q<=L.last;q+)L.elementsq=L.elementsq+1; position Locate(Elementtype x,LIST L)position q;for(q=1;q<=L.last;q+)if(L.elementsq=x)return q;return(L.last+1); void merge(LIST&L,LIST&L1,LIST&L2)posit

13、ion p=0,p1,p2;position len1=End(L1);position len2=End(L2);L.last=len1+len2-1;for(p1=0;p1<End(L1);p1+)L.elementsp=L1.elementsp1;p+; p-;for(p2=0;p2<End(L2);p2+)L.elementsp=L2.elementsp2;p+; p-;void read(LIST &L)cout<<endl;cout<<"請(qǐng)輸入線性表長(zhǎng)度"<<endl;cin>>L.last;f

14、or(int i=0;i<L.last;i+)cin>>L.elementsi; void write(LIST &L) for(int i=0;i<L.last;i+) cout<<L.elementsi<<"t"cout<<endl; int main()LIST L,L1,L2;read(L1);write(L1);read(L2);write(L2);merge(L,L1,L2);write(L); 數(shù)據(jù)結(jié)構(gòu)三（指針）#include<iostream>using namespace s

15、td;typedef int Elementtype;struct celltypeElementtype element;celltype *next;typedef celltype *LIST;typedef celltype *position;position End(LIST L)position p;p=L;while(p->next!=NULL)p=p->next;return p;void Insert(Elementtype x,position p)position q;q=new celltype;q->element=x;q->next=p-&

16、gt;next;p->next=q;void Delete(position p)/刪除p的下一個(gè)節(jié)點(diǎn) position q;if(p->next!=NULL)q=p->next;p->next=q->next;delete q;position Locate(Elementtype x,LIST L)position p;p=L;while(p->next!=NULL)if(p->next->element=x)return p;elsep=p->next;return p;position MakeNull(LIST&L)L=n

17、ew celltype;L->next=NULL;return L; void merge(LIST&L,LIST&L1,LIST&L2)position p,p1,p2;for(p1=L1;p1;p1=p1->next)p=new celltype;p->element=p1->element;if(L=0)L=p;p2=p;elsep2->next=p;p2=p;p2->next=NULL;for(p1=L2;p1;p1=p1->next)p=new celltype;p->element=p1->element

18、;if(L=0)L=p;p2=p;elsep2->next=p;p2=p;p2->next=NULL;void Read(LIST &L)position p1,p2;/p1=new celltype;cout<<"請(qǐng)輸入數(shù)據(jù)以-1結(jié)束"<<endl;for(;)p1=new celltype;cin>>p1->element;if(p1->element=-1)break;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1; p2->next=NULL;void w

19、rite(LIST&L)position p;p=L;for(;p;p=p->next)cout<<p->element<<"t"cout<<endl;int main()LIST L=NULL,L1=NULL,L2=NULL;Read(L1);write(L1);Read(L2);write(L2);merge(L,L1,L2);write(L);數(shù)據(jù)結(jié)構(gòu)四#include<iostream>using namespace std;typedef int Elementtype;struct cellty

20、peElementtype element;celltype *next;typedef celltype *LIST;typedef celltype *position;position End(LIST L)position p;p=L;while(p->next!=NULL)p=p->next;return p;void Insert(Elementtype x,position p)/節(jié)點(diǎn)插p節(jié)點(diǎn)之后 position q;q=new celltype;q->element=x;q->next=p->next;p->next=q;void Dele

21、te(position p)/刪除P節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) position q;if(p->next!=NULL)q=p->next;p->next=q->next;delete p;position Locate(Elementtype x,LIST L)position p;p=L;while(p->next!=NULL)if(p->next->element=x)return p;else p=p->next;return p;position MakeNull(LIST &L)L=new celltype;L->next=NUL

22、L;return L;void Copy(LIST &L1,LIST &L2) position p1,p2,p3;for(p2=L2;p2;p2=p2->next)p1=new celltype;p1->element=p2->element;if(L1=0)L1=p1;p3=p1;elsep3->next=p1;p3=p1; p3->next=NULL;void Read(LIST &L)position p1,p2;p1=new celltype;cout<<"請(qǐng)輸入數(shù)據(jù)以-1結(jié)束"<<en

23、dl;for(;)p1=new celltype;cin>>p1->element;if(p1->element=-1)break;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1; p2->next=NULL;void Write(LIST &L)position p=L;for(;p;p=p->next)cout<<p->element<<"t"cout<<endl;int main()LIST L1=NULL,L2=NULL;Read(L2);Wr

24、ite(L2);Copy(L1,L2);Write(L1);數(shù)據(jù)結(jié)構(gòu)五#include<iostream>using namespace std;typedef int Elementtype;struct celltypeElementtype element;celltype *next; typedef celltype *LIST; typedef celltype *position;position End(LIST L)position p;p=L;while(p->next!=NULL)p=p->next;return p;void Insert(Ele

25、menttype x,position p)/插入到P后面的一個(gè)節(jié)點(diǎn) position q;q->element=x;q->next=p->next;p->next=q;void Delete(position p)/刪除P后面一個(gè)節(jié)點(diǎn) position q;if(p->next!=NULL)q=p->next;p->next=q->next;delete q;int Delete(LIST &L,int x)position p=L;int count=1;if(p->element=x)return count;p=p->

26、next;while(p->next!=NULL)count+;if(p->next->element=x)if(p->next->next!=NULL)position q;q=p->next;p->next=q->next;delete q;return count;elsedelete p->next;p->next=NULL;return count;elsep=p->next;return -1;position Locate(Elementtype x,LIST L)position p=L;while(p->

27、next!=NULL)if(p->next->element=x)return p;elsep=p->next;return p;position MakeNull(LIST&L)L=new celltype;L->next=NULL;return L;void Read(LIST &L)position p1,p2;p1=new celltype;cout<<"請(qǐng)輸入數(shù)據(jù)以-1結(jié)束"<<endl;for(;)p1=new celltype;cin>>p1->element;if(p1->

28、;element=-1)break;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1; p2->next=NULL;void Write(LIST &L)position p=L;for(;p;p=p->next)cout<<p->element<<"t"cout<<endl;int main()LIST L1=NULL;Read(L1);Write(L1);cout<<Delete(L1,3);cout<<endl;Write(L1);數(shù)據(jù)結(jié)構(gòu)六#in

29、clude<iostream>using namespace std;#define maxsize 100typedef int Elementtype;typedef structElementtype element;int next;spacestr;/節(jié)點(diǎn)類(lèi)型 spacestr SPACEmaxsize;/存儲(chǔ)池 typedef int position,cursor;cursor available;/游標(biāo)變量，標(biāo)識(shí)線性表 void Initialize()int j;for(j=0;j<maxsize-1;j+)SPACEj.next=j+1;/鏈接池中節(jié)點(diǎn) S

30、PACEj.next=-1;available=0;/標(biāo)識(shí)線性表，將所有存儲(chǔ)池中的節(jié)點(diǎn)設(shè)置為空閑，avaailable為頭節(jié)點(diǎn)不利用 cursor GetNode()/從空閑鏈中獲取一個(gè)節(jié)點(diǎn) position p;if(SPACEavailable.next=-1)p=-1;elsep=SPACEavailable.next;SPACEavailable.next=SPACEp.next;return p;void FreeNode(cursor q)/將結(jié)點(diǎn)q加入到空閑鏈 SPACEq.next=available;available=q;void Insert(Elementtype x,

31、position p,cursor M)/在鏈表M中的位置為p的元素后面添加一個(gè)值為x的結(jié)點(diǎn)position q;q=GetNode();SPACEq.element=x;SPACEq.next=SPACEp.next;SPACEp.next=q;void Delete(cursor M,position p)/在鏈表M中刪除位置為P的元素的后一個(gè)元素 position q;q=GetNode();if(SPACEp.next!=-1)if(SPACESPACEp.next.next!=-1)q=SPACEp.next;SPACEp.next=SPACEq.next;FreeNode(q);e

32、lseq=SPACEp.next;FreeNode(q);/*合并:將N鏈表中的所有結(jié)點(diǎn)添加到M鏈表的后面，并將N鏈表的表頭結(jié)點(diǎn)添加到空閑結(jié)點(diǎn)鏈表中。*/void Merge(cursor M,cursor N)position p=M;position q=N;while(SPACEp.next!=-1)p=SPACEp.next;SPACEp.next=SPACEq.next;position r=available;SPACEN.next=r;available=N;void Input(cursor M)/創(chuàng)建靜態(tài)鏈表 Elementtype x;cursor p=0;cout<

33、<"請(qǐng)輸入靜態(tài)鏈表的值以-1結(jié)束"<<endl;while(1)cin>>x;if(x!=-1)Insert(x,p,M);p=SPACEp.next;elseSPACEp.element=-1;p=-1;break;void Output(cursor M)position p;p=M;while(p!=-1)cout<<SPACEp.element<<"t"p=SPACEp.next; cout<<endl;int main()/spacestr s;Initialize();/pos

34、ition p=GetNode();SPACE0.element = 2; SPACE0.next = 6;SPACE1.element = 4; SPACE1.next = 3;SPACE2.next = 4;SPACE3.element = 8; SPACE3.next = -1;SPACE4.element = 10; SPACE4.next = 7;SPACE5.next = 0;SPACE6.element = 16; SPACE6.next = 1;SPACE7.element = 18; SPACE7.next = 9;SPACE8.element = 20; SPACE8.ne

35、xt = -1;SPACE9.element = 22; SPACE9.next = 8;available = 10;cursor M = 2;cursor N = 5;Output(M);Output(N);Merge(M, N);Output(M);Delete(M,3);Insert(34,3,M);Output(M);return 0;數(shù)據(jù)結(jié)構(gòu)七#include<iostream>using namespace std;struct PolyNodeint coef;/系數(shù) int expn;/指數(shù)PolyNode *next;typedef PolyNode *LIST

36、;typedef PolyNode *position;void Input(LIST &L,int n)position p1,p2;cout<<"輸入數(shù)據(jù)系數(shù)和指數(shù)(并且以指數(shù)從大到小方式輸入)"<<endl;for(int i=0;i<n;i+)p1=new PolyNode; cin>>p1->coef>>p1->expn;if(L=0)L=p1;p2=p1;elsep2->next=p1;p2=p1;p2->next=NULL; void Output(LIST&L)po

37、sition p;p=L;for(;p;p=p->next)cout<<"+"<<p->coef<<"X"<<p->expn;cout<<endl;void Plus(LIST &L,LIST &L1,LIST &L2)position p,p1=L1,p2=L2,pp;while(p1!=NULL|p2!=NULL)p=new PolyNode;if(p1=NULL&&p2!=NULL)p->coef=p2->coef;p-

38、>expn=p2->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p2=p2->next; if(p1!=NULL&&p2=NULL)p->coef=p1->coef;p->expn=p1->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p1=p1->next;elseif(p1->expn>p2->expn)p->coef=p1->coef;p->expn=p1->expn;if(L=0)L=p;pp=p

39、;elsepp->next=p;pp=p;p1=p1->next;if(p1->expn<p2->expn)p->coef=p2->coef;p->expn=p2->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p2=p2->next;elsep->coef=(p1->coef)+(p2->coef);p->expn=p1->expn;if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p1=p1->next;p2=p2->n

40、ext; pp->next=NULL;void Multiply(LIST &L,LIST&L1,LIST &L2)position p,p1,p2,pp;p1=new PolyNode;p1=L1;while(p1!=NULL)p2=new PolyNode;p2=L2;while(p2!=NULL)p=new PolyNode;p->coef=(p1->coef)*(p2->coef);p->expn=(p1->expn)*(p2->expn);if(L=0)L=p;pp=p;elsepp->next=p;pp=p;p

41、2=p2->next;p1=p1->next;pp->next=NULL;int main()LIST L1=NULL,L2=NULL,L3=NULL,L4=NULL;Input(L1,3);Output(L1);Input(L2,3);Output(L2);Plus(L3,L1,L2);Output(L3);Multiply(L4,L1,L2);Output(L4);return 0;數(shù)據(jù)結(jié)構(gòu)八#include<iostream>using namespace std;#define maxlength 100typedef int Elementtype;st

42、ruct STACKint top;Elementtype elementsmaxlength;void MakeNull(STACK &S)/將棧設(shè)置為空 S.top=maxlength;bool Empty(STACK &S)/測(cè)試棧是否為空 if(S.top>=maxlength)return true;elsereturn false;Elementtype Top(STACK S)/返回棧頂元素 if(Empty(S)cout<<"stack is empty"<<endl;elsereturn (S.elements

43、S.top);void Pop(STACK &S)/刪除棧頂元素 if(Empty(S)cout<<"stack is empty"<<endl;elseS.top=S.top+1;void Push(Elementtype x,STACK &S)if(S.top=0)cout<<"stack is full"<<endl;elseS.top=S.top-1;S.elementsS.top=x;void Convert(int num,STACK &S,int n)MakeNull(

44、S);while(num!=0) Push(num%n,S);num=num/n;void Output(STACK &S)while(!Empty(S)cout<<S.elementsS.top;S.top+;cout<<endl; int main()STACK S;Convert(8,S,3);Output(S);數(shù)據(jù)結(jié)構(gòu)九#include<iostream>using namespace std;#define maxlength 100typedef int Elementtype;struct QUEUEint front;int cou

45、nt;Elementtype elementsmaxlength;void MakeNull(QUEUE &Q)/將隊(duì)列設(shè)置為空 Q.front=0;Q.count=0;bool Empty(QUEUE Q)/測(cè)試隊(duì)列是否為空 if(Q.count=0)return true;elsereturn false;bool Full(QUEUE Q)if(Q.count=maxlength)return true;else return false; Elementtype Front(QUEUE Q)/返回隊(duì)列的第一個(gè)元素 if(Empty(Q)cout<<"que

46、ue is empty"<<endl;elsereturn (Q.elementsQ.front);void EnQueue(Elementtype x,QUEUE &Q)/將元素插入到隊(duì)列的后端 if(Full(Q)cout<<"queue is full"<<endl;elseQ.elements(Q.front+Q.count)%maxlength=x;Q.count+;void DeQueue(QUEUE &Q)/刪除隊(duì)列的第一個(gè)元素 if(Empty(Q)cout<<"queue

47、is empty"<<endl;elseQ.front=(Q.front+1)%maxlength;Q.count-;void Input(QUEUE &Q,int n)MakeNull(Q);int i=0;Elementtype x;while(i<n)cin>>x;EnQueue(x,Q);i+;void Output(QUEUE &Q)for(int i=0;i<Q.count;i+)cout<<Q.elements(Q.front+i)%maxlength<<"t"cout<

48、;<endl;int main()QUEUE Q;Input(Q,5);Output(Q);cout<<Front(Q)<<endl;DeQueue(Q);Output(Q);EnQueue(2,Q);Output(Q);數(shù)據(jù)結(jié)構(gòu)十主串T=“abcaabbabcabaacbacba“，模式p=“abcabaa”1模式p的next函數(shù)值123456701101302.第一次比較：主串 abcaabbabcabaacbacba i=5 模式串 abcab j=5,匹配失敗 第二次比較：主串 abcaabbabcabaacbacba i=7 模式串 abc j=3,匹配

49、失敗 第三次比較：主串 abcaabbabcabaacbacba i=7 模式串 a j=1,匹配失敗 第四次比較：主串 abcaabbabcabaacbacba i=8 模式串 abcabaa j=1,匹配成功數(shù)據(jù)結(jié)構(gòu)十一#include<iostream>using namespace std;#define maxlength 100typedef char Elementtype;struct STACKint top;Elementtype elementsmaxlength; enum BooleanFALSE,TRUE;void MakeNull(STACK &

50、;S)/將棧設(shè)置為空 S.top=maxlength;bool Empty(STACK &S)/測(cè)試棧是否為空 if(S.top>=maxlength)return true;elsereturn false;Elementtype Top(STACK S)/返回棧頂元素 if(Empty(S)cout<<"stack is empty"<<endl;elsereturn (S.elementsS.top);void Pop(STACK &S)/刪除棧頂元素 if(Empty(S)cout<<"stack is empty"<<endl;elseS.top=S.top+1;void Push(Elementtype x,STACK &S)/進(jìn)棧 if(S.top=0)cout&l