【精品】数据结构实验一

1、#include <iostream>using namespace std;template <class int>struct node / 结点int data;/数据域struct node <int> * next;/指针域;class linklistpublic:linklist()(front = new nodc<int>front->ncxt=null;)/带头结点的无参构造函数 linklist 1( int a,int n);头插法带头结点的有参构造函数linklist 2( int a,inl n)"/尾

2、插法带头结点的有参构造函数linklisi()析构函数void printlist(); 按次序遍历线性表屮的各个数据元素int gctlcngth(); 获取线性表的长度int *get(int i);查找线性表小第i个位置上的元素int iocate(int x); 查找线性表中值为x的元素，找到厉返冋其位置 void insert(inl i,inl x);在线性表的第i个位置上插入值为x的新元索 int delete();删除线性表第i个元素，并将该元素返回private:node<int>*front； 头指针；linklist<int>:linklist l

3、(int aljjnt n)/front = new node <int>/front->ncxt=null;/for(int i=n-l;i>=0;i)node <int> * s = new node <int>/s->data = ai;/s->ncxt 二 front->ncxt;/front->next = s;/)linklist<int>:linklist 2(int a,int n)/front = new node <int>/s->data = aij;/r->nex

4、l = s;node <int>* p = front;/ whilc(p)/front = p;/p=p->next;/delete front;void linklist<int>:inscrt(int x)inode<int>* p = front;while (p !=null && p->data < x)寻找不小 丁*的节点位置1pic 二 p;p=p->next;if(p)1node <int> * s = new node <int>/s->data = x;s->n

5、ext = p->next;p->next = s;)int linklist<int>:delete()node <int>* p = front;/ if(i!=l) p = get(int i);node <int>* q = p->ncxt;/p->next = q->next;int x = q->next;delete q;return x;)int* linklist<int>:get(int i)node <ini>* p = front->next;/intj=l;while

6、 (p&&j!=i)p=p->next;j+；if(!p) throw "查找位置非法”else return p;int linklist <int>:locatc(int x)按值查找node <int>* p = front->next; int j=l;while(p)if(p datax) return j;p=p->next; j+;return 1;1int linklist<int>:getlength()node <int>* p = fronl->next;int length

7、 = 0;wh ile(p!=null)单链表见到null则表示结束m+;p=p->next;return length;)void main()int a7= 1234567;linklist<int> list(a,6); insert (l0);#i nclude<ios treeimusing namespace std;#definetrue 1#definefalse 0#defineok 1#defineerror 0#define overflow 2typedef int status;typedef int elemtype;typedef stru

8、ct lnode/存储结构 elemtype data;struet lnode *next;lnode, linklist;void createlist (linklist &l, int n)/尾插法创建单链表 linklist p;l=new lnode;i->next=null;/建立一个带头结点的单链表linklist q二l;/使q指向表尾for(int i = l;i<=n;i+) p=new lnode;cin>>p->data;p->next=null;q_next二p;q二p;status getelem(linklist l,

9、 int i, elemtype &e)/取第 i 个元素 linklist p=l->next;int j二1;while(p&&j<i) p=p->next;+j；if (!p| | j>i) return error;/第 i 个元素不存在e=p->data;return ok;status linkinsert (linklist &l, int i, elemtype e)/插入linklist p=l;int j=0;while (p&&j<i-l) p二p->next;+j;/寻找第i-l个

10、结点if(!p|ij>il)return error;/i小于1或者大于表长加1linklist s=new lnode; /生成新结点s>da tei二 e;s->next二p->next;/插入 l 中p->next=s;return ok;status listdelete(linklist &l, int i, elemtype &e)/ 删除 linklist p二l;linklist q;int j=0;while(p->next&&j<il)/寻找第i个结点，并令p指向其前驱p二p_>next;+j;

11、if (! (p->next) | | j>i_l) return error;/删除位置不合理q二p-next;p->next=q->next;/删除并释放结点e=q->data;delete(q);return ok;void mergelist(linklist &la, linklist &lb,linklist &lc)/合并两个顺序链表linklist pa,pc, pb;pa二la->next;pb=lb->next;lc二pc二la;while(pa&&pb)i f (pa->data二pb

12、->data) pc>next=pa;pc=pa;pa二pa->next;el sepc->next二pb;pc=pb;pb二pb->next;pc->next二pa?pa:pb;delete (lb);)void show(linklist l)linklist p;p二 i 厂 >next;wh i 1 e (p) cout<<p->data<</，-> p二p_>next;coutendl;int length(linklist l, int i)i 二0;linklist p二i厂>next;wh

13、 i 1 e(p)+i；p=p>next;return i;ivoid xiugai (linklist l) int i, j二 1;elemtype k;elemtype e, m;linklist p二l一>next;/显示/表长/修改cout«请输入要修改的元素位置(0<i<length):;cin»i;getelem(l, i, e);cout<</，该位置的元素:，z<<e<<endl ;cout«，z修改后的元素值:；cin»k;while(p&&j<i) p

14、=p->next;+j；m=p->data;p->data=k; cout<<，z修改后的单链表显示如下:，z<<endl ;show(l);)void hebingo/合并两个单链表 int a, b;linklist la,lb, lc;cout«请输入第一个有序链表的长度:,，«endl ;cin>>a;cout«请输入第一个有序链表的元素共(，«a«，z个人endl; createlist (la,a);show(la);cout«，z请输入第二个有序链表的长度:,，

15、71;endl ;cin»b;cout«，z请输入第二个有序链表的元素共(，«b«，/个人endl; createlist (lb,b);show (lb);mergelist (la,lb,lc);cout<<z/合并后的有序链表如下：endl; show(lc);void main()/主函数 int select;int x;elemtypelinkli sty; list;or(;)cout<</，单链表的基本操作，z«endl ;cout<</，1单链表的创建，«endl;cout<

16、</，2.单链表的显示，z<<endl ;cout<</，3.单链表的长度，«endl ;cout<</，4.取第i个位置的元素，«endl;cout<</，5.修改第i个位置的元素，«endl;cout<</，6.插入元素到单链表里，z«endl ;cout<<，z7.删除单链表里的元素，z«endl ;cout<</，&合并两个单链表z，<<endl ;cout<</，9 退出系统，«endl;cout<

17、<，z 请选择:;cin>>select;switch (select)case 1: cout«z，请输入单链表的长度:,，«endl;cin>>x;cout<<，z请输入，<<x<</，个元素，<<endl ;createli st (1 i st, x);break;case 2: cout<<z，单链表显示如下:z，<<endl;show(l ist);break;case 3: int s;cout<<z，单链表的长度为:"length (1

18、 ist, s) <<endl ; break;case 4: cout<<z/请选择所要取出元素的位置:；cin>>x;while(x<01 |x>length(list, s)cout<<z/输入有误，请重新输入，z<<endl;cout«，z请选择所要取出元素的位置:；cin>>x;getelem(l ist, x, y);cout<<，z该位置的元素为：z，<<y<<endl ;break;case 5: xiugai(1ist); break;case 6

19、: cout请选择要插入的位置:;cin>>x; while(x<0|x>length (1i st,s)cout<<，/输入有误，请重新输入，z<<endl ;cout«z，请选择所要插入元素的位置:; cin>>x;cout«，z要插入的元素值:；cin>>y;linktnsert( list, x, y);cout<<，z插入后单链表显示如下:，z<<endl ;show(l i st);break;case 7: cout<<，z请选择要删除的位置：；cin&

20、gt;>x; while(x<0|x>length (1i st,s)cout<<，z输入有误，请重新输入，<<endl ;cout«，/请选择所要删除元素的位置:,; cin>>x;listdelete(l ist, x, y);c0ut<<，z要删除的元素值:,<<y<<endl ;cout«，z删除后的单链表显示如下:,，«endl; show(l i st);break;case 8: hebing();break;case 9: exit(0);break;defa

21、ult : cout«，z输入有误，请重新输入，z<<endl;break;#include <iostream>using namespace std;typedef struct node存储结构iint data;数据域struct node * next;/指针域i；class linklistpublic:linklist() front = new node;front->next=null;);/带头结点的无参构造函数 linklistl( int a,int n);头插法带头结点的有参构造函数linklist2( int a,int n)

22、;尾插法带头结点的有参构造函数linklis(); 析构函数void printlist(); 按次序遍历线性表屮的各个数据元索int getlength();获取线性表的长度int *get(int i);査找线性表中第i个位.用上的元素int locate(int x); 查找线性表川值为x的元素，找到肩返冋其位置 void insert(int i,int x);在线性表的第i个位置上插入值为x的新元索 int delete();删除线性表第i个元索，并将该元索返回private:node * front;头指针)；linklist:linklistl(int a,int n)头插法fr

23、ont = new node;/front->next=null;/for(int i=n-l;i>=0;i)node * s = new node <int>/s->data = a|i|;/s->next = front->next;/front->ncxt = s;/)linklist:linklisl2(int a| ,int n)/front = new node;/node * r =front;for(int i=0:i<n;i+)s->data = ai;/r->next = s;)r->next=null

24、;linklist :-linklist()/inode * p = front;/while(p)/1front = p;/p=p->next;/delete front;/;void linklist:inscrt(int x)inode * p = front;while (p !=null && p->data < x)寻找不小丁*的节点位置pre 二 p;p=p->next;if(p)node * s = new node;/ s->data = x;s->next = p->next; p->next = s;i);i

25、nt linklist:delete()node * p = front;/if (i!=d p = get(int i);node * q = p->ncxt;/ p->next = q->next;int x = q>nexl;delete q;return x;1int * linklist:get(int i)node * p = front->ncxt;/intj = 1;while (p&&j!=i)p=p->next;j+；)if(!p)throw ”查找位置非法"else return p;)；int linklis

26、t:iocatc(int x)按值査找inode * p = front->next;int j=l;while(p)1if(p->data=x) return j;p=p->next;j+；return 1;)int linklist:getlength()node * p = front->next;int length = 0;while(p!=null)单链农见至ijnull则农示结束length+;p=p->nexl;return length;)；void main()int a7= 1234567;linklist list(a,6);list.in

27、sert (1,0);#include <iostrcam>using namespace std; struct node 存储结构int data; /数据域struct node * next;/指针域)；class linklistpublic:linklist()( front = new node;front->next=null;);/ 带头结点的无参构造函数 linklist( int aj,int n);头插法带头结点的有参构造函数void linklist 1( int a|,inl n)"/尾插法带头结点的有参构造函数-iinklist();

28、析构函数void printlist(); 按次序遍j线性表中的各个数据元素int getlength(); 获取线性衣的长度int *get(int i);查找线性表中第i个位置上的元索int iocate(int x); 查找线性表屮值为x的元索，找到后返回位置 void insert(int i,int x);在线性表的第i个位置上插入值为x的新元素 int dclctc(int i);删除线性表笫i个元素，并将该元素返回private:node * front; 头指针；linklist: :linklist(int a,int n) 头插法1front = new node;/fro

29、nt->next=null;/for(int i=n-l:i>=0;i)node * s = new node;/s->data = ai;/s->next = front->next;/front->next = s;/i；void linklist:linklistl(int a,int n)/front = new node;/node * r =front;for(int i=0:i<n;i+)node * s = new node;s->data = ai;/r->next = s;r = s;)r->next=null;linklist:linklist()node * p = front;/while(p)/front = p;/p 二 p->n ext;/delete front;/);void linklist:printlist()/按序号依次遍j单链表中的各个数据元素icout«"按序号依次遍历单-链表中的各个数据元索:"«endl; int length=getlength();for(int i=o