《数据结构小实验.》由会员分享，可在线阅读，更多相关《数据结构小实验.（34页珍藏版）》请在金锄头文库上搜索。
1、第二章第一题/设线性表存储在数组A1.arrsize的前elenum个分量中，且递增有序。/试编写一个算法：将x插入到线性表的适当位置上以保持线性表的有序性，并且分析算法的时间复杂度。#include #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) int i;if(size=LE
2、N) 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;isize;i+) cout elemi ;coutendl;int main()SqList a;int size,data,val;coutsize;coutPlease input the number : ;for(int i=0;i data;if(!a.Insert(data) cout Insert Fail, it is full! endl;coutval;i
3、f(!a.Insert(val) cout Insert Fail, it is full! endl;coutNow the number is as follow : ;a.Show();return 0;第2题/已知单链表L中的结点是按值非递减有序排列的，试编写一算法将值为X的结点插入到表L中，使得L仍然有序。#include using namespace std;typedef int T;struct LNodeT data;LNode *next;LNode(const T &d=0,LNode *n=NULL):data(d),next(n);class LinkListLNo
4、de *head;public:LinkList();LinkList();void Show();void Insert(T x);LinkList:LinkList()LNode *q;T x;head=NULL;coutPlease input the data from high to low (exit in 0) : x&x!=0)q=new LNode(x);q-next=head;head=q;LinkList:LinkList ()LNode *p;while(head!=NULL)p=head;head=head-next ;delete p;void LinkList:S
5、how ()LNode *p=head;while(p!=NULL)coutdata next ;coutdata x)q=new LNode(x);q-next =head;head=q;return;while(p-next&p-next-datanext;q=new LNode(x);q-next=p-next ;p-next=q;int main()T a;char flag=y;LinkList A;coutThe linlist is as follows : ;A.Show ();while(flag=y|flag=Y)couta;A.Insert (a);coutThe lin
6、list is as follows : ;A.Show ();coutflag;return 0;第3题/用单链表作存储结构，编写一个实现线性表中元素逆置的算法。#include using 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;coutx&x!=0)p=new LNode(x,NULL);if(h
7、ead=NULL) head=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)coutdatanext ;coutendl;int main()LNode *h;char flag;flag=y;whil
8、e(flag=y|flag=Y)h=Create();h=Reverse(h);coutReverse as follow: ;Show(h);coutflag;return 0;第4题/已知一个单链表中的数据元素含有三类字符（即字母字符，数字字符和其它字符）/试编写算法，构造三个循环链表，使每个循环链表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间。#include using namespace std;typedef char T;struct LNodeT data;LNode *next;LNode(const T &d= ,LNode *n=NULL):data
9、(d),next(n);class LinkListLNode *head;public:LinkList();void Show(LNode*);void Classify(LNode*&,LNode*&,LNode*&);void Dest(LNode*);LinkList:LinkList()coutx&x!=0)q=new LNode(x);p-next=q;p=p-next;void LinkList:Dest(LNode *H)LNode *p=H;while(p-next !=H)LNode*q=p;p=p-next ;delete q;void LinkList:Show (L
10、Node *H)LNode *p=H-next ;while(p!=H) coutdata next ;coutnext;A=new LNode();p=A;B=new LNode();q=B;C=new LNode();r=C;while(s!=NULL)if( s-data=0&s-datanext =s;p=p-next ;else if(s-data=a&s-datadata=A&s-datanext =s;q=q-next ;elser-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 *a
