數(shù)據(jù)結構與算法線性表練習題

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

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

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

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

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

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

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

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

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

10、名格式為“學號+姓名”三（數(shù)組表示）#include<iostream>using namespace std;#define maxlength 100typedef int position;typedef int Elementtype;struct LISTElementtype elementsmaxlength;int last;position End(LIST L)/線性表長度 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<<"請輸入線性表長度"<<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ù)結構三（指針）#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的下一個節(jié)點 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<<"請輸入數(shù)據(jù)以-1結束"<<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ù)結構四#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é)點插p節(jié)點之后 position q;q=new celltype;q->element=x;q->next=p->next;p->next=q;void Dele

21、te(position p)/刪除P節(jié)點的下一個節(jié)點 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<<"請輸入數(shù)據(jù)以-1結束"<<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ù)結構五#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后面的一個節(jié)點 position q;q->element=x;q->next=p->next;p->next=q;void Delete(position p)/刪除P后面一個節(jié)點 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<<"請輸入數(shù)據(jù)以-1結束"<<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ù)結構六#in

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

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

31、position p,cursor M)/在鏈表M中的位置為p的元素后面添加一個值為x的結點position q;q=GetNode();SPACEq.element=x;SPACEq.next=SPACEp.next;SPACEp.next=q;void Delete(cursor M,position p)/在鏈表M中刪除位置為P的元素的后一個元素 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鏈表中的所有結點添加到M鏈表的后面，并將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、<"請輸入靜態(tài)鏈表的值以-1結束"<<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ù)結構七#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ù)結構八#include<iostream>using namespace std;#define maxlength 100typedef int Elementtype;st

42、ruct STACKint top;Elementtype elementsmaxlength;void MakeNull(STACK &S)/將棧設置為空 S.top=maxlength;bool Empty(STACK &S)/測試棧是否為空 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ù)結構九#include<iostream>using namespace std;#define maxlength 100typedef int Elementtype;struct QUEUEint front;int cou

45、nt;Elementtype elementsmaxlength;void MakeNull(QUEUE &Q)/將隊列設置為空 Q.front=0;Q.count=0;bool Empty(QUEUE Q)/測試隊列是否為空 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)/返回隊列的第一個元素 if(Empty(Q)cout<<"que

46、ue is empty"<<endl;elsereturn (Q.elementsQ.front);void EnQueue(Elementtype x,QUEUE &Q)/將元素插入到隊列的后端 if(Full(Q)cout<<"queue is full"<<endl;elseQ.elements(Q.front+Q.count)%maxlength=x;Q.count+;void DeQueue(QUEUE &Q)/刪除隊列的第一個元素 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ù)結構十主串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ù)結構十一#include<iostream>using namespace std;#define maxlength 100typedef char Elementtype;struct STACKint top;Elementtype elementsmaxlength; enum BooleanFALSE,TRUE;void MakeNull(STACK &

50、;S)/將棧設置為空 S.top=maxlength;bool Empty(STACK &S)/測試棧是否為空 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)/進棧 if(S.top=0)cout&l