數(shù)據(jù)結(jié)構(gòu)小實(shí)驗(yàn)

1、第二章第一題/設(shè)線性表存儲(chǔ)在數(shù)組A1.arrsize的前elenum個(gè)分量中，且遞增有序。/試編寫一個(gè)算法：將x插入到線性表的適當(dāng)位置上以保持線性表的有序性，并且分析算法的時(shí)間復(fù)雜度。#include <iostream> #define LEN 100 using namespace std;class SqListint *elem; int size; public: SqList();int Insert(int x); void Show();SqList:SqList() size=0;elem = new intLEN;int SqList:Insert(int x)

2、 int i;if(size>=LEN) return 0;for(i=size-1;i>=0&&elemi>=x;i-) elemi+1=elemi;elemi+1=x;size+;return 1;void SqList:Show()for(int i=0;i<size;i+) cout <<elemi<<" "cout<<endl;int main()SqList a;int size,data,val;cout<<"Please input the size : &qu

3、ot;cin>>size;cout<<"Please input the number : "for(int i=0;i<size; i+)cin >> data;if(!a.Insert(data) cout << "Insert Fail, it is full!" << endl;cout<<"Please input the number you want to Insert:"cin>>val;if(!a.Insert(val) cou

4、t << "Insert Fail, it is full!" << endl;cout<<"Now the number is as follow : "a.Show();return 0;第2題/已知單鏈表L中的結(jié)點(diǎn)是按值非遞減有序排列的，試編寫一算法將值為X的結(jié)點(diǎn)插入到表L中，使得L仍然有序。#include <iostream>using namespace std;typedef int T;struct LNodeT data;LNode *next;LNode(const T &d=0

5、,LNode *n=NULL):data(d),next(n);class LinkListLNode *head;public:LinkList();LinkList();void Show();void Insert(T x);LinkList:LinkList()LNode *q;T x;head=NULL;cout<<"Please input the data from high to low (exit in 0) : "<<endl;while(cin>>x&&x!=0)q=new LNode(x);q-&g

6、t;next=head;head=q;LinkList:LinkList ()LNode *p;while(head!=NULL)p=head;head=head->next ;delete p;void LinkList:Show ()LNode *p=head;while(p!=NULL)cout<<p->data <<" "p=p->next ;cout<<endl;void LinkList:Insert (T x)LNode *p=head,*q;if(p!=NULL&&p->data &

7、gt;x)q=new LNode(x);q->next =head;head=q;return;while(p->next&&p->next->data<x)p=p->next;q=new LNode(x);q->next=p->next ;p->next=q;int main()T a;char flag='y'LinkList A;cout<<"The linlist is as follows : "A.Show ();while(flag='y'|fla

8、g='Y')cout<<"Please input the data you want to Insert : "cin>>a;A.Insert (a);cout<<"The linlist is as follows : "A.Show ();cout<<"Continue ? (y or n) "cin>>flag;return 0;第3題/用單鏈表作存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)實(shí)現(xiàn)線性表中元素逆置的算法。#include <iostream>using

9、 namespace std;typedef int T;struct LNode T data;LNode* next;LNode(const T &d=0,LNode *n=NULL):data(d),next(n);LNode* Create() int x;LNode *head,*tail,*p;head=tail=NULL;cout<<"Please input the data(exit in 0): "while(cin>>x&&x!=0)p=new LNode(x,NULL);if(head=NULL) he

10、ad=tail=p;elsetail->next =p;tail=tail->next ;return head;LNode* Reverse(LNode * head) LNode *p,*q;p=head;head=NULL;while(p!=NULL)q=p;p=p->next ;q->next =head;head=q;return head;void Show(LNode *head)LNode *p=head ;while (p!=NULL)cout<<p->data<<" " ;p=p->next ;

11、cout<<endl;int main()LNode *h;char flag;flag='y'while(flag='y'|flag='Y')h=Create();h=Reverse(h);cout<<"Reverse as follow: "Show(h);cout<<"Continue (y or n) :"cin>>flag;return 0;第4題/已知一個(gè)單鏈表中的數(shù)據(jù)元素含有三類字符（即字母字符，數(shù)字字符和其它字符）/試編寫算法，構(gòu)造三個(gè)循環(huán)鏈表

12、，使每個(gè)循環(huán)鏈表中只含有同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的結(jié)點(diǎn)空間。#include <iostream>using namespace std;typedef char T;struct LNodeT data;LNode *next;LNode(const T &d=' ',LNode *n=NULL):data(d),next(n);class LinkListLNode *head;public:LinkList();void Show(LNode*);void Classify(LNode*&,LNode*&,LNo

13、de*&);void Dest(LNode*);LinkList:LinkList()cout<<"Please input the data (exit in '0'): "T x;head=new LNode();LNode *p=head,*q;while(cin>>x&&x!='0')q=new LNode(x);p->next=q;p=p->next;void LinkList:Dest(LNode *H)LNode *p=H;while(p->next !=H)LN

14、ode*q=p;p=p->next ;delete q;void LinkList:Show (LNode *H)LNode *p=H->next ;while(p!=H) cout<<p->data <<" "p=p->next ;cout<<endl;void LinkList:Classify(LNode *&A,LNode *&B,LNode *&C)LNode *s,*p,*q,*r;s=head->next;A=new LNode();p=A;B=new LNode();q

15、=B;C=new LNode();r=C;while(s!=NULL)if( s->data>='0'&&s->data<='9' )p->next =s;p=p->next ;else if(s->data>='a'&&s->data<='z'|s->data>='A'&&s->data<='Z' )q->next =s;q=q->next ;elser-

16、>next =s;r=r->next ;s=s->next ;p->next =A;q->next =B;r->next =C;int main()char flag;flag='y'while(flag='y' | flag='Y')LinkList a;LNode *aa=NULL,*bb=NULL,*cc=NULL;a.Classify (aa,bb,cc);cout<<"The number is : "a.Show (aa);cout<<"The

17、char is : "a.Show (bb);cout<<"The others is : "a.Show (cc);a.Dest (aa);a.Dest (bb);a.Dest (cc);cout<<endl;cout<<"Continue ? (y or n) : "cin>>flag;return 0;第5題/試編寫一個(gè)算法，找出一個(gè)循環(huán)鏈表中的最小值。#include <iostream>using namespace std;typedef int T;struct LNod

18、eT data;LNode *next;LNode(const T &d=0,LNode *n=NULL):data(d),next(n);class DlListLNode * head;public:DlList();DlList();void Show();T Min();DlList:DlList()T x;head=new LNode();LNode *p=head,*q;cout<<"Please input the data (exit in 0) : "while(cin>>x&&x!=0)q=new LNod

19、e();q->data=x;p->next=q;p=q;p->next=head;DlList:DlList ()LNode *p=head;while(p->next !=head)LNode *q=p;p=p->next ;delete q;void DlList:Show ()LNode *p=head->next ;while(p!=head)cout<<p->data<<" "p=p->next ;cout<<endl;T DlList:Min ()T Min,temp;LNode

20、 *p=head->next ;if(p!=NULL) Min=p->data;p=p->next ;while(p!=head)if(p->data < Min) temp=Min;Min=p->data;p->data=temp;p=p->next;return Min;int main()char flag;flag='y'while(flag='y'|flag='Y')DlList A;cout<<"The DlList is as follows : "A.

21、Show ();cout<<"The Min data is : "<<A.Min ()<<endl;cout<<"Continue ? (y or n) : "cin>>flag;return 0;第三章/*將一個(gè)十進(jìn)制N轉(zhuǎn)換為一個(gè)d（二 九）進(jìn)制的數(shù)，其解決方法很多,其中一個(gè)簡(jiǎn)單算法基于下列原理: N=(n / d)*d+n % d 例如 d=8時(shí)， (1348)10=(2504)8，其運(yùn)算過(guò)程如下： n n / 8 n % 8 1348 168 4 168 21 0 21 2 5 2 0

22、2 要求：輸入一個(gè)十進(jìn)制數(shù)N和對(duì)應(yīng)的轉(zhuǎn)換進(jìn)制d，在屏幕上輸出轉(zhuǎn)換結(jié)果。 如，輸入 N=1348 d=8 則結(jié)果為2504*/#include <iostream>#include <stack>using namespace std;void trans(int N,int d)stack<char> S;int num=N;while(N)char temp=N%d;num=(temp<10)?(temp+'0'):(temp+'A'-10);S.push(num);N/=d; while(!S.empty() cou

23、t<<S.top();S.pop (); cout<<endl;int main()int number,d;cout<<"Please input N= "while(cin>>number)cout<<"Please input d= "cin>>d;cout<<"After transform N= "if(number<0)cout<<"-"trans(-number,d);else trans(numbe

24、r,d);cout<<"Please input N= "return 0;第六章第1題/*以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)算法將二叉樹左、右子樹進(jìn)行交換的算法。*/#include <iostream>using namespace std;class BNodefriend class BTree;int data;BNode *lchild,*rchild;public:BNode(const int &d=0,BNode *l=NULL,BNode *r=NULL):data(d),lchild(l),rchild(r);class B

25、Treeprivate:BNode *Create();void Exchange (BNode *&p);void Show(BNode *p,int l);protected:BNode *root;public:BTree() root=Create(); ;void Exchange();void Show();BNode *BTree:Create ()BNode *p;int ch;cin>>ch;if(ch=-1) return NULL;elsep=new BNode(ch);p->lchild =Create();p->rchild =Crea

26、te();return p;void BTree:Exchange() Exchange(root);void BTree:Exchange (BNode *&p) BNode *q;if(p!=NULL)q=p->lchild;p->lchild=p->rchild;p->rchild=q;Exchange(p->lchild );Exchange(p->rchild );void BTree:Show()Show(root,1);void BTree:Show(BNode *p,int l)if(p!=NULL)Show(p->rchild

27、 ,l+1);for(int i=0;i<6*(l-1);i+) cout<<" "cout<<"."<<p->data <<endl;Show(p->lchild ,l+1);int main()cout<<"Please input the datas of BTree in preorder ( '-1' represent NULL) :"<<endl;BTree b1;cout<<"Before E

28、xchange :"<<endl;b1.Show ();cout<<endl<<endl;cout<<"After Exchange :"<<endl;b1.Exchange ();b1.Show ();return 0;第2題/*一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹存放在二叉樹的順序存儲(chǔ)結(jié)構(gòu)中，試編寫非遞歸算法對(duì)該樹進(jìn)行前序遍歷。*/#include <iostream>#include <stack>using namespace std;void Preorder(int a,int

29、 n) stack<int> s;int i=1;s.push (ai-1);while(!s.empty ()i=s.top ();cout<<ai-1<<" "s.pop ();if(2*i+1<=n) s.push (a2*i); if(2*i<=n) s.push (a2*i-1); int main() int a7=1,2,3,4,5,6,7;cout<<"Layerorder : "<<endl;for(int j=0;j<7;j+)cout<<aj&

30、lt;<" "cout<<endl;cout<<"Preorder : "<<endl;Preorder(a,7);cout<<endl;return 0;第3題/*試編寫算法判別兩棵二叉樹是否等價(jià)。如果T1和T2都是空二叉樹，或T1和T2的根結(jié)點(diǎn)的值相同，并且T1的左子樹與T2的左子樹是等價(jià)的；T1的右子樹與T2的右子樹是等價(jià)的。*/#include <iostream>using namespace std;class BNode friend class BTree;int data

31、;BNode *lchild,*rchild;public:BNode(const int &d=0,BNode *l=NULL,BNode *r=NULL):data(d),lchild(l),rchild(r);class BTree private:BNode* Create();bool Equal(BNode *p,BNode *q);protected:BNode *root;public:BTree() root=Create(); ;bool Equal(BTree &p);BNode *BTree:Create ()BNode *p;int ch;cin>

32、;>ch;if(ch=-1) return NULL;elsep=new BNode(ch);p->lchild =Create();p->rchild =Create();return p;bool BTree:Equal (BTree &p)return (Equal(root,p.root );bool BTree:Equal (BNode *p,BNode *q)if(p=NULL&&q=NULL) return true;if(p=NULL|q=NULL) return false;else return (p->data =q->

33、;data)&&Equal(p->lchild ,q->lchild )&&Equal(p->rchild ,q->rchild );int main() cout<<"Please input the datas of BTree in preorder ( '-1' represent NULL) :"<<endl<<endl;cout<<"1:"<<endl;BTree b1;cout<<"2:&

34、quot;<<endl;BTree b2;if(b1.Equal (b2)cout<<"Equal !"<<endl;elsecout<<"InEquality !"<<endl;return 0;第4題/*設(shè)計(jì)一個(gè)實(shí)現(xiàn)一棵二叉樹復(fù)制的算法。*/#include <iostream>using namespace std;class BNodefriend class BTree;int data;BNode *lchild,*rchild;public:BNode(const in

35、t &d=0,BNode *l=NULL,BNode *r=NULL):data(d),lchild(l),rchild(r);class BTreeprivate:BNode *Create(void);void Show(BNode *p,int l);void Copy(BNode *&p,BNode *q);protected:BNode *root;public:BTree() root=Create();BTree() dest(root); ;void Copy(BTree &bt);void dest(BNode *p);void Show();BNod

36、e *BTree:Create ()BNode *p;int ch;cin>>ch;if(ch=-1) return NULL;elsep=new BNode(ch);p->lchild =Create();p->rchild =Create();return p;void BTree:dest (BNode *p)if(p!=NULL)dest(p->lchild );dest(p->rchild );delete p;void BTree:Copy (BTree &bt)dest(root);Copy(root,bt.root );void BT

37、ree:Copy (BNode *&p,BNode *q)if(q=NULL) q=NULL;elsep=new BNode(q->data);Copy(p->lchild ,q->lchild );Copy(p->rchild ,q->rchild );void BTree:Show()Show(root,1);void BTree:Show(BNode *p,int l)if(p!=NULL)Show(p->rchild ,l+1);for(int i=0;i<6*(l-1);i+)cout<<" "cout

38、<<"."<<p->data <<endl;Show(p->lchild ,l+1);int main()cout<<"Please input the datas of BTree in preorder ( '-1' represent NULL) :"<<endl<<endl;cout<<"1:"<<endl;BTree b1;cout<<"2:"<<endl;B

39、Tree b2;cout<<"Before Copy :"<<endl;b1.Show ();cout<<"After Copy :"<<endl;b1.Copy (b2);b1.Show ();return 0;第5題/*編寫一個(gè)將二叉樹的所有葉子結(jié)點(diǎn)從左向右鏈接成單鏈表的算法。*/#include <iostream>using namespace std;struct LNodeint data;LNode *next;class BNodefriend class BTree;int d

40、ata;BNode *lchild,*rchild;public:BNode(const int &d=0,BNode *l=NULL,BNode *r=NULL):data(d),lchild(l),rchild(r);class BTreeprivate:LNode* head;BNode* Create();void Leave(BNode *p);protected:BNode *root;public:BTree() root=Create();head=NULL; ;void Leave();BNode* BTree:Create ()BNode *p;int ch;cin

41、>>ch;if(ch=-1) return NULL;elsep=new BNode(ch);p->lchild =Create();p->rchild =Create();return p;void BTree:Leave ()Leave(root);void BTree:Leave (BNode *p)LNode *q;if(p!=NULL)if(p->lchild =NULL&&p->rchild =NULL)q=new LNode();q->data =p->data ;q->next =head;head=q;co

42、ut<<p->data <<" -> "Leave(p->lchild );Leave(p->rchild );int main()cout<<"Please input the datas of BTree in preorder ( '-1' represent NULL) :"<<endl;BTree b;cout<<"Leave ( from left to right ) : "<<endl;b.Leave ();

43、cout<<endl;return 0;第6題/*設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，試寫一個(gè)算法將該順序存儲(chǔ)結(jié)構(gòu)轉(zhuǎn)換為二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。*/#include <iostream>using namespace std;class BNode friend class BTree;int data;BNode *lchild,*rchild;public:BNode(const int &d=0,BNode *l=NULL,BNode *r=NULL):data(d),lchild(l),rchild(r);class BTree private:int

44、 size; int a100;BNode* Create(int n);void Show(BNode *p,int l); protected:BNode *root; public:BTree(); void Show();BTree:BTree()int s;cout<<"請(qǐng)輸入完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)："<<endl;cin>>s;size=s;cout<<"請(qǐng)輸入完全二叉樹的節(jié)點(diǎn)數(shù)據(jù)："<<endl;for(int i=0;i<size;i+)cin>>ai;root=

45、Create(1);BNode* BTree:Create (int n) if(n<=size)BNode *p;p=new BNode(an-1);p->lchild =Create(2*n);p->rchild =Create(2*n+1);return p;return NULL;void BTree:Show() Show(root,1);void BTree:Show(BNode *p,int l) if(p!=NULL)Show(p->rchild ,l+1);for(int i=0;i<6*(l-1);i+) cout<<"

46、"cout<<"."<<p->data <<endl;Show(p->lchild ,l+1);void main() BTree b;cout<<"該完全二叉樹轉(zhuǎn)換成二叉鏈?zhǔn)浇Y(jié)構(gòu)為："<<endl;b.Show ();第7題/*設(shè)具有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，試寫出一個(gè)算法將該二叉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)轉(zhuǎn)換為順序存儲(chǔ)結(jié)構(gòu)。*/#include <iostream>using namespace std;class BNode friend class BTr

47、ee;int data;BNode *lchild,*rchild;public:BNode(const int &d=0,BNode *l=NULL,BNode *r=NULL):data(d),lchild(l),rchild(r);class BTree private:int size;int a100;BNode* Create(); void Tran(BNode*p,int i); void Show1(BNode *p,int l) ;protected:BNode *root; public:BTree() size=0;root=Create(); void Tra

48、n(); void Show1();void Show2();BNode*BTree:Create ()int ch;cin>>ch;if(ch=-1) return NULL;elseBNode *p;p=new BNode(ch);p->lchild =Create();p->rchild =Create();size+;return p;void BTree:Tran ()Tran(root,1);void BTree:Tran (BNode *p,int i)if(p!=NULL)ai-1=p->data ;int l=2*i;int r=2*i+1;Tr

49、an(p->lchild ,l);Tran(p->rchild ,r);else ai-1=-1;void BTree:Show1() Show1(root,1);void BTree:Show1(BNode *p,int l) if(p!=NULL)Show1(p->rchild ,l+1);for(int i=0;i<6*(l-1);i+) cout<<" "cout<<"."<<p->data <<endl;Show1(p->lchild ,l+1);void BT

50、ree:Show2 ()int i,c;c=i=0;while (c<size)if (ai!=-1) cout<<ai<<" "c+;i+;cout<<endl;int main() cout<<"Please input the datas of BTree in preorder ( '-1' represent NULL) :"<<endl;BTree b;cout<<"二叉鏈?zhǔn)剑?quot;<<endl;b.Show1 ();co

51、ut<<"順序存?。?quot;<<endl;b.Tran ();b.Show2 ();return 0;第八章#include <iostream>using namespace std;typedef int Key;struct RecKey key;/二分查找/非遞歸int HalfSearch_(Rec r,int n,Key k)int l=1,h=n,m;while(l<=h)m=(l+h)/2;if(rm.key =k) return m;else if(rm.key >k) h=m-1;else l=m+1;retur

52、n 0;/遞歸int HalfSearch(Rec r,int l,int h,Key k)int m;if(l>h) return 0;elsem=(l+h)/2;if(rm.key =k) return m;else if(rm.key >k) HalfSearch(r,l,m-1,k);else HalfSearch(r,m+1,h,k);/順序查找int SqSearch(Rec r,int n,Key k)int i=n;r0.key =k;while(ri.key !=k) i-;return i;void Show(Rec r,int n)int i,j;for(i=

53、1,j=1;i<=n;i+,j+)cout<<i<<"->"<<ri.key <<" "if(j%9=0) cout<<endl;cout<<endl;Rec* Create(int &size)int i,n;cout<<"Please input the size : "cin>>n;Rec *r=new Recn+1;cout<<"Please input "<<n<

54、;<" datas (有序): "for(i=1;i<=n;i+) cin>>ri.key;size+;return r;int main()cout<<"*查找*"<<endl;int i=0,j,k,d;Rec *a=Create(i);Show(a,i);cout<<"Please input the data you want to search : "cin>>d;while(1)cout<<"請(qǐng)選擇： 1: 二分查找 2: 順序查找 0: 退出 "cin>>j;switch(j)case 1:k=HalfSearc