中南大学数据结构实验报告1(线性表)

1、实验一 线性表的操作算法1、 实验目的：1了解线性表的逻辑结构和存储结构，以及定义在逻辑结构上的各种基本运算2分别以数组和链表为存储结构，实现线性表的插入，删除，查找，排序，合并等操作2、 实验内容：用C/C+语言编写程序，分别以数组和链表为存储结构，完成以下功能： 1输入数据，创建一个线性表 2可在线性表的任意位置插入新结点 3可删除线性表的任意一个结点 4可在线性表中查找结点 5将线性表从小至大排序6将两个线性表合并3、 详细设计：顺序表#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#def

2、ine OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct /结构体ElemType *elem;int length;int listsize;SqList;SqList Lx;Status InitList_Sq(SqList &L) /分配空间 L.elem=new ElemTypeLIST_INIT_SIZE; if(!L.elem)exit(OV

3、ERFLOW); L.length =0; L.listsize=LIST_INIT_SIZE; return OK;Status ListInsert(SqList &L,int i,ElemType e) /插入新元素 int *q,*p;ElemType *newbase;if(i<1 | i>L.length+1) return ERROR;if(L.length>=L.listsize) newbase=new ElemTypeL.listsize+LISTINCREMENT; if(!newbase) exit(OVERFLOW); L.elem=newb

4、ase; L.listsize+=LISTINCREMENT; q=&(L.elemi-1); for (p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; *q=e; +L.length; return OK;Status Listlength(SqList L) /长度 int *p=L.elem; /判断线形表是否存在while(p) return (L.length); Status GetElem(SqList L, int i,ElemType &e) /取元素 if(i<1 | i>L.length)ret

5、urn ERROR;else e=L.elemi-1;return e;void MergeList(SqList La,SqList Lb,SqList &Lc) /合并 ElemType ai,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while(i<=La_len)&&(j<=Lb_len) GetElem(La,i,ai);GetElem(Lb,j,bj); if(ai<=bj) ListIns

6、ert(Lc,+k,ai);+i; else ListInsert(Lc,+k,bj);+j; while(i<=La_len) GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j<=Lb_len) GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);void show(SqList L,int i) /显示 int j;ElemType k; cout<<"顺序表显示如下:"<<endl; for(j=0;j<i-1;j+) k=L.elemj; cout<

7、<k<<"->" if(j=i-1 && i>0) k=L.elemj; cout<<k; cout<<endl;void create(SqList &L,int n) /输入元素 int e;for(int i=0;i<n;i+) cin>>e;L.elemi=e;L.length=i+1; Status ListDelete_Sq(SqList &L,int i,ElemType &e) /删除 ElemType *p, *q;if(i<1 | i&g

8、t;L.length) return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p<=q;+p) *(p-1)=*p;-L.length;return OK;Status Listxiugei(SqList &L,int i,ElemType &e) /修改 if(i<1 | i>L.length)return ERROR; else L.elemi-1=e; return OK; void shuru(SqList &L1) /顺序表的创建 int a;InitList_Sq(L

9、1);cout<<"请输入顺序表的长度："cin>>a;cout<<"请输入顺序表的元素(共"<<a<<"个)"<<endl; create(L1,a); show(L1,a);void shanchu(SqList &L1) /删除顺序表里的元素 int a;int j; ElemType e1;a=L1.length;cout<<"请选择所要删除元素的位置:"cin>>j;while(j<0|j>

10、Listlength(L1) cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要删除元素的位置:" cin>>j; ListDelete_Sq(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a-1);void charu(SqList &L1) /插入元素到顺序表里 int a; int j; ElemType e1;a=L1.length;cout<<"请选择所要插入元素

11、的位置:"cin>>j;while(j<0|j>Listlength(L1) cout<<"输入有误，请重新输入"<<endl;cout<<"请选择所要插入元素的位置:" cin>>j; cout<<"要插入的元素:"cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的顺序表数据:"<<endl;show(L1,a+1);void hebing(SqList &

12、amp;L3) /合并两个顺序表 SqList L1,L2; int a,b; InitList_Sq(L1); InitList_Sq(L2); cout<<"请输入第一个有序表的长度：" cin>>a; cout<<"请输入第一个有序表的元素(共"<<a<<"个)"<<endl; create(L1,a); show(L1,a); cout<<"请输入第二个有序表的长度：" cin>>b; cout<<&

13、quot;请输入第二个有序表的元素(共"<<b<<"个)"<<endl; create(L2,b); show(L2,b); MergeList(L1,L2,L3); cout<<"合并后的有序表如下：" show(L3,a+b);void main() /主菜单 int choice; for(;) cout<<"顺序表的基本操作"<<endl; cout<<"1.顺序表的创建"<<endl; cout<

14、;<"2.顺序表的显示"<<endl; cout<<"3.顺序表的长度"<<endl; cout<<"4.插入元素到顺序表里"<<endl; cout<<"5.删除顺序表里的元素"<<endl; cout<<"6.合并两个顺序表"<<endl; cout<<"7.退出系统"<<endl; cout<<"请选择：&quo

15、t; cin>>choice; switch(choice) case 1: shuru(Lx);break; case 2: show(Lx,Lx.length);break; case 3: cout<<"顺序表的长度:"<<Listlength(Lx)<<endl;break; case 4: charu(Lx);break; case 5: shanchu(Lx);break; case 6: hebing(Lx);break; case 7: cout<<"退出系统!"<<

16、endl;exit(0);break; default : cout<<"输入有误，请重新选择"<<endl;break; 链表#include<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode /存储结构 ElemType data; struct LNode

17、*next;LNode,*LinkList;void CreateList(LinkList &L,int n) /尾插法创建单链表 LinkList p; L=new LNode; L->next=NULL; /建立一个带头结点的单链表 LinkList q=L; /使q指向表尾 for(int i=1;i<=n;i+) p=new LNode; cin>>p->data; p->next=NULL; q->next=p; q=p; Status GetElem(LinkList L,int i,ElemType &e)/取第i个元素

18、 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-1) p=p->next; +j; /寻找第i-1个结点 if(!p|j>i-1) return erro

19、r; /i小于1或者大于表长加1 LinkList s=new LNode; /生成新结点 s->data=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<i-1) /寻找第i个结点，并令p指向其前驱 p=p->next; +j; if(!(p->next)|

20、j>i-1) 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) if(pa->data<=pb->data)

21、 pc->next=pa; pc=pa; pa=pa->next; else pc->next=pb; pc=pb; pb=pb->next; pc->next=pa?pa:pb; delete(Lb); void show(LinkList L) /显示 LinkList p; p=L->next; while(p) cout<<p->data<<"->" p=p->next; cout<<endl;int Length(LinkList L,int i) /表长 i=0; Link

22、List p=L->next; while(p) +i; p=p->next; return i; void 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<<"该位置的元素:"<<e<<endl; cout<<"

23、;修改后的元素值:" cin>>k; while(p&&j<i) p=p->next; +j; m=p->data; p->data=k; cout<<"修改后的单链表显示如下:"<<endl; show(L); void hebing() /合并两个单链表 int a,b; LinkList La,Lb,Lc; cout<<"请输入第一个有序链表的长度:"<<endl; cin>>a; cout<<"请输入第一

24、个有序链表的元素共（"<<a<<"个）："<<endl; CreateList(La,a); show(La); cout<<"请输入第二个有序链表的长度:"<<endl; cin>>b; cout<<"请输入第二个有序链表的元素共（"<<b<<"个）："<<endl; CreateList(Lb,b); show (Lb); MergeList(La,Lb,Lc); cout<&

25、lt;"合并后的有序链表如下："<<endl; show(Lc);void main() /主函数 int select; int x; ElemType y; LinkList list; for(;) cout<<"单链表的基本操作"<<endl; cout<<"1.单链表的创建"<<endl; cout<<"2.单链表的显示"<<endl; cout<<"3.单链表的长度"<<end

26、l; cout<<"4.插入元素到单链表里"<<endl; cout<<"5.删除单链表里的元素"<<endl; cout<<"6.合并两个单链表"<<endl; cout<<"7.退出系统"<<endl; cout<<"请选择:" cin>>select; switch(select) case 1:cout<<"请输入单链表的长度:"<<endl; cin>>x; cout<<"请输入"<<x<<"个元素"<<endl; CreateList(list,x); break; case 2: cout<<"单链表显示如下:"<<endl; show(list); b