数据结构实验报告 线性表的基本操作.docx

数据结构实验报告 线性表的基本操作一、 实验目的 二、 实验内容和要求 三、 源代码 1) 顺序表的代码 2) 单链表的代码 四、 测试结果 1) 顺序表的测试结果 2) 单链表的测试结果 五、心得体会 实验一 线性表的基本操作及其应用 一、实验目的 1、帮助读者复习C+语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现。 4、掌握顺序表的存储结构形式及其描述和基本运算的实现。 5、熟练掌握动态链表结构及有关算法的设计 二、实验内容 题目一：顺序表的基本操作 问题描述 实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。 基本要求 依次从键盘读入数据，建立带头结点的顺序表； 输出顺序表中的数据元素 求顺序表的长度； 根据指定条件能够取元素和修改元素； 实现在指定位置插入和删除元素的功能。 根据算法，将两个有序的顺序表合并成一个有序顺序表。 测试数据 由学生任意指定。 题目二：单链表的基本操作 问题描述 实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。 基本要求 依次从键盘读入数据，建立带头结点的单链表； 输出单链表中的数据元素 求单链表的长度； 根据指定条件能够取元素和修改元素； 实现在指定位置插入和删除元素的功能。 根据算法，将两个有序的单链表合并成一个有序单链表。 测试数据 由学生任意指定。 三、源代码 (一) 顺序表的基本操作 #include<iostream> using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; typedef int ElemType; #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef 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(OVERFLOW); L.length =0; L.listsize=LIST_INIT_SIZE; return OK; 2 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=newbase; 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) return ERROR; else e=L.elemi-1; return e; void MergeList(SqList La,SqList Lb,SqList &Lc) /合并 ElemType ai,bj; InitList_Sq(Lc); 3 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) ListInsert(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<<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+) 显示输入元素4 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>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(L1); cout<<"请输入顺序表的长度：" cin>>a; cout<<"请输入顺序表的元素(共"<<a<<"个)"<<endl; create(L1,a); show(L1,a); void chaxun(SqList &L1) /取第i个位置的元素 int j;ElemType e1; cout<<"请选择所要取出元素的位置:" 5 cin>>j; while(j<0|j>Listlength(L1) cout<<"输入有误，请重新输入"<<endl; cout<<"请选择所要取出元素的位置:" cin>>j; GetElem(L1,j,e1); cout<<"取出的元素为:"<<e1<<endl; void xiugai(SqList &L1) /修改第i个位置的元素 int a; int j; ElemType e1; a=L1.length; cout<<"请选择所要修改元素的位置:" cin>>j; while(j<0|j>Listlength(L1) cout<<"输入有误，请重新输入"<<endl; cout<<"请选择所要修改元素的位置:" cin>>j; cout<<"要修改成的元素:" cin>>e1; Listxiugei(L1,j,e1); cout<<"修改后的顺序表数据:"<<endl; show(L1,a); void shanchu(SqList &L1) /删除顺序表里的元素 int a; int j; ElemType e1; a=L1.length; cout<<"请选择所要删除元素的位置:" cin>>j; while(j<0|j>Listlength(L1) cout<<"输入有误，请重新输入"<<endl; cout<<"请选择所要删除元素的位置:" cin>>j; 6 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<<"请选择所要插入元素的位置:" 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 &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<<"请输入第二个有序表的元素(共"<<b<<"个)"<<endl; create(L2,b); show(L2,b); MergeList(L1,L2,L3); cout<<"合并后的有序表如下：" show(L3,a+b); 7 void main /主菜单 int choice; for(;) cout<<" 顺序表的基本操作"<<endl; cout<<" 1.顺序表的创建"<<endl; cout<<" 2.顺序表的显示"<<endl; cout<<" 3.顺序表的长度"<<endl; cout<<" 4.取第i个位置的元素"<<endl; cout<<" 5.修改第i个位置的元素"<<endl; cout<<" 6.插入元素到顺序表里"<<endl; cout<<" 7.删除顺序表里的元素"<<endl; cout<<" 8.合并两个顺序表"<<endl; cout<<" 9.退出系统"<<endl; cout<<"请选择：" 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: chaxun(Lx);break; case 5: xiugai(Lx);break; case 6: charu(Lx);break; case 7: shanchu(Lx);break; case 8: hebing(Lx);break; case 9: cout<<"退出系统!"<<endl;exit(0);break; default : cout<<"输入有误，请重新选择"<<endl;break; (二) 单链表的基本操作 #include<iostream> using namespace std; 8 #define true 1 #define false 0 #define ok 1 #define error 0 #define overflow -2 typedef int Status; typedef int ElemType; typedef struct LNode /存储结构 ElemType data; struct LNode *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个元素 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; 9 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 error; /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)|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; 10 pa=La->next; pb=Lb->next; Lc=pc=La; while(pa&&pb) if(pa->data<=pb->data) 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; LinkList p=L->next; while(p) +i; p=p->next; return i; void xiugai(LinkList L) / 显示 表长 修改11 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<<"修改后的元素值:" 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<<"请输入第一个有序链表的元素共："<<endl; CreateList(La,a); show(La); cout<<"请输入第二个有序链表的长度:"<<endl; cin>>b; cout<<"请输入第二个有序链表的元素共："<<endl; CreateList(Lb,b); show (Lb); MergeList(La,Lb,Lc); cout<<"合并后的有序链表如下："<<endl; 12 show(Lc); void main /主函数 int select; int x; ElemType y; LinkList list; for(;) cout<<" 单链表的基本操作"<<endl; cout<<" 1.单链表的创建"<<endl; cout<<" 2.单链表的显示"<<endl; cout<<" 3.单链表的长度"<<endl; cout<<" 4.取第i个位置的元素"<<endl; cout<<" 5.修改第i个位置的元素"<<endl; cout<<" 6.插入元素到单链表里"<<endl; cout<<" 7.删除单链表里的元素"<<endl; cout<<" 8.合并两个单链表"<<endl; cout<<" 9.退出系统"<<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); break; case 3: int s; cout<<"单链表的长度为:"<<Length(list,s)<<endl; break; case 4: cout<<"请选择所要取出元素的位置:" 13 cin>>x; while(x<0|x>Length(list,s) cout<<"输入有误，请重新输入"<<endl; cout<<"请选择所要取出元素的位置:" cin>>x; GetElem(list,x,y); cout<<"该位置的元素为:"<<y<<endl; break; case 6: cout<<"请选择要插入的位置:" cin>>x; while(x<0|x>Length(list,s) cout<<"输入有误，请重新输入"<<endl; cout<<"请选择所要插入元素的位置:" cin>>x; cout<<"要插入的元素值:" cin>>y; LinkInsert( list,x,y); cout<<"插入后单链表显示如下:"<<endl; show(list); break; 请选择要删除的位置:" cin>>x; while(x<0|x>Length(list,s) cout<<"输入有误，请重新输入"<<endl; cout<<"请选择所要删除元素的位置:" cin>>x; cout<<"要删除的元素值:"<<y<<endl; cout<<"删除后的单链表显示如下:"<<endl; show(list); break; break; 14 case 5: xiugai(list); break; case 7: cout<<" ListDelete(list,x,y); case 8: hebing; case 9: exit(0); break; default : cout<<"输入有误，请重新输入"<<endl; break; 四、测试结果 1) 顺序表 的测试结果 15 16 2) 单链表的测试结果 17 18 19 五、心得体会 当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。记得去年学习C+时，学了一个学期，程序设计用了三周，才完成的，这个实验报告居然要一周完成两个设计，觉得很难。但是现在一周过去了，我也写完了，自我感觉良好。 通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C+是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C+语言，将各种操作描述出来构成算法。数据结构+算法=程序设计。 在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C+的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。 单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比如说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数通过修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。 这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。 20