数据结构小实验

1、第二章第一题/设线性表存储在数组A1.arrsize的前elenum个分量中，且递增有序。/试编写一个算法：将x插入到线性表的适当位置上以保持线性表的有序性，并且分析算法的时间复杂度。#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中的结点是按值非递减有序排列的，试编写一算法将值为X的结点插入到表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题/用单链表作存储结构，编写一个实现线性表中元素逆置的算法。#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题/已知一个单链表中的数据元素含有三类字符（即字母字符，数字字符和其它字符）/试编写算法，构造三个循环链表

12、，使每个循环链表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间。#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题/试编写一个算法，找出一个循环链表中的最小值。#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;第三章/*将一个十进制N转换为一个d（二 九）进制的数，其解决方法很多,其中一个简单算法基于下列原理: N=(n / d)*d+n % d 例如 d=8时， (1348)10=(2504)8，其运算过程如下： n n / 8 n % 8 1348 168 4 168 21 0 21 2 5 2 0

22、2 要求：输入一个十进制数N和对应的转换进制d，在屏幕上输出转换结果。 如，输入 N=1348 d=8 则结果为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题/*以二叉链表作存储结构，编写一个算法将二叉树左、右子树进行交换的算法。*/#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个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行前序遍历。*/#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题/*试编写算法判别两棵二叉树是否等价。如果T1和T2都是空二叉树，或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的；T1的右子树与T2的右子树是等价的。*/#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题/*设计一个实现一棵二叉树复制的算法。*/#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题/*编写一个将二叉树的所有叶子结点从左向右链接成单链表的算法。*/#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题/*设具有n个结点的完全二叉树采用顺序存储结构，试写一个算法将该顺序存储结构转换为二叉链式存储结构。*/#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<<"请输入完全二叉树的节点个数："<<endl;cin>>s;size=s;cout<<"请输入完全二叉树的节点数据："<<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<<"该完全二叉树转换成二叉链式结构为："<<endl;b.Show ();第7题/*设具有n个结点的二叉树采用二叉链式存储结构，试写出一个算法将该二叉链式存储结构转换为顺序存储结构。*/#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<<"二叉链式："<<endl;b.Show1 ();co

51、ut<<"顺序存取："<<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<<"请选择： 1: 二分查找 2: 顺序查找 0: 退出 "cin>>j;switch(j)case 1:k=HalfSearc