线性表的链式表示与实现

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验五线性表的链式表示和实现学生姓名吴奇专业班级信管1204 学号31201403实验成绩指导老师（签名）日期一.实验目的和要求1、掌握线性表的链式存储结构；2、掌握单链表、循环单链表的一些基本操作实现函数。

二.实验内容1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表各基本操作的实现函数，把它们存放在头文件LinkList.h中，同时建立一个验证操作实现的主函数文件test2_2.cpp。

编译并调试程序，直到正确运行。

2、选做：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) ，实现将两个带表头附加结点的有序单链表La和Lb合并成一个新的带表头附加结点的有序单链表Lc的功能，要求利用原存储空间。

请把该函数添加到头文件LinkList.h中，并在主文件test2_2.cpp中添加相应语句进行测试。

3、填写实验报告，实验报告文件取名为report5.doc。

4、上传实验报告文件report5.doc、源程序文件test2_2.cpp及LinkList.h 到Ftp服务器上自己的文件夹下。

三. 函数的功能说明及算法思路void initlist(lnode *&hl) 初始化链表{hl=new lnode; 新建头节点if(!hl){cout<<"储存分配失败，按任意键退出系统!!"<<endl;getchar();exit(0);}hl->next=NULL;}bool insertlist(lnode *&hl,elemtype item) 链表中插入元素{lnode *n,*ap,*cp;n=new lnode; ap ,cp为一前一后遍历指针n->date=item;cp=hl;ap=NULL;while(cp!=NULL) 查找插入位置{ap=cp;cp=cp->next;}n->next=cp; 插入元素ap->next=n;return true;}bool emptylist(lnode *hl) 判断是否为空链表{if(hl->next==NULL)return true;elsereturn false;/*return hl->next==NULL;*/}void travellist(lnode *hl) 遍历链表{ lnode *p; 新建指针P指向第一个节点p=hl->next;while(p!=NULL){cout<<p->date<<" ";p=p->next;}cout<<endl;}void getlist(lnode *hl,int pos) 得到链表中指定位置元素{int i=0;lnode *p; 新建指针P指向第一个节点p=hl->next;while(p!=NULL){i++;if(i==pos) 查找需要得到的元素的位置break; 找到，跳出p=p->next; 往下遍历}if(p!=NULL)cout<<p->date<<endl;else{cout<<"超出线性表的长度,按任意键退出!"<<endl;getchar();exit(0);}}int lengthlist(lnode *hl) 计算链表长度{int i=0;while(hl->next!=NULL){i++;hl=hl->next;}return i;}void cleanlist(lnode *&hl) 清除链表{lnode *ap,*cp;ap=hl->next; ap指针指向第一个节点while(ap!=NULL){cp=ap->next; cp指向下一个节点，防止断掉delete ap; 删除当前节点ap=cp;}hl->next=NULL;}bool deletelist(lnode *&hl,elemtype item) 删除链表中的指定元素{ if(hl->next==NULL){cout<<"线性表为空,按任意键退出!"<<endl;getchar();exit(0);}lnode *ap,*cp; ap,cp为遍历指针ap=hl->next;cp=NULL;while(ap!=NULL){if(ap->date==item)break;else{cp=ap;ap=ap->next;}if(ap==NULL){cout<<"没有需要删除的元素!"<<endl;return false;}}if(cp==NULL)hl->next=ap->next;elsecp->next=ap->next;delete ap;cout<<"线性表中现在的元素为:"<<endl;travellist(hl);cout<<"线性表现在的长度为:"<<lengthlist(hl)<<endl;return true;}void mergelist(lnode *&la,lnode *&lb,lnode *&lc){lnode *p1,*p2,*p3;p1=la->next; p1指向la的第一个元素p2=lb->next; p2指向lb的第一个元素p3=lc; p3指向lcwhile(p1!=NULL&&p2!=NULL){if(p1->date<=p2->date){p3->next=p1;p1=p1->next;p3= p3->next;}else{p3->next=p2;p2=p2->next;p3= p3->next;}}if(p1!=NULL)p3->next=p1;elsep3->next=p2;}四. 实验结果与分析五. 心得体会本次实验中遇到的问题还是比较多的，脑子已经被链表搞的稀里糊涂的了，但是基本的操作已经弄懂了，只是这次实验的选作部分有点错误，经过老师的知道解决了这个问题.【附录----源程序】Test5.cpp#include<iostream.h>#include<stdio.h>#include<stdlib.h>typedef int elemtype;#include"linklist.h"void main(){elemtype x,y,z,j,k,l;lnode *mylist,*mylist1,*mylist2,*newlist;initlist(mylist);initlist(newlist);initlist(mylist1);initlist(mylist2);cout<<"请输入任意正整数插入第一个线性表中,以输入任意<=0的数为结束标志:"<<endl;cin>>x;while(x>0){insertlist(mylist,x);cin>>x;}if(emptylist(mylist)){cout<<"第一个线性表为空,按任意键退出!"<<endl;getchar();exit(0);}else{cout<<"第一个线性表中的元素为:"<<endl;travellist(mylist);}cout<<"第一个线性表的初始长度为:"<<lengthlist(mylist)<<endl;cout<<"请输入你想要查询第一个线形表的第几个元素:"<<endl;cin>>k;cout<<"第一个线性表中第"<<k<<"个元素为:";getlist(mylist,k);cout<<"请输入需要删除的一个元素:"<<endl;cin>>j;deletelist(mylist,j);cout<<"是否继续删除？1-是，2-否"<<endl;cin>>l;while(l==1){cout<<"请输入需要删除的一个元素:"<<endl;cin>>j;deletelist(mylist,j);cout<<"是否继续删除？1-是，2-否"<<endl;cin>>l;}cout<<"请输入任意有序正整数插入需要合并的第一个线性表中,以输入任意<=0的数为结束标志:"<<endl;cin>>y;while(y>0){insertlist(mylist1,y);cin>>y;}if(emptylist(mylist)){cout<<"第一个线性表为空,按任意键退出!"<<endl;getchar();exit(0);}else{cout<<"线性表中的元素为:"<<endl;travellist(mylist1);}cout<<"请输入任意有序正整数插入需要合并的第二个线性表中,以输入任意<=0的数为结束标志:"<<endl;cin>>z;while(z>0){insertlist(mylist2,z);cin>>z;}if(emptylist(mylist)){cout<<"第二个线性表为空,按任意键退出!"<<endl;getchar();exit(0);}else{cout<<"线性表中的元素为:"<<endl;travellist(mylist2);}mergelist(mylist1,mylist2,newlist);cout<<"新线性表中的元素为:"<<endl;travellist(newlist);}linklist.hstruct lnode{elemtype date;lnode *next;};void initlist(lnode *&hl){hl=new lnode;if(!hl){cout<<"储存分配失败，按任意键退出系统!!"<<endl;getchar();exit(0);}hl->next=NULL;}bool insertlist(lnode *&hl,elemtype item){lnode *n,*ap,*cp;n=new lnode;n->date=item;cp=hl;ap=NULL;while(cp!=NULL){ap=cp;cp=cp->next;}n->next=cp;ap->next=n;return true;}bool emptylist(lnode *hl){if(hl->next==NULL)return true;elsereturn false;/*return hl->next==NULL;*/}void travellist(lnode *hl){ lnode *p;p=hl->next;while(p!=NULL){cout<<p->date<<" ";p=p->next;}cout<<endl;}void getlist(lnode *hl,int pos){int i=0;lnode *p;p=hl->next;while(p!=NULL){i++;if(i==pos)break;p=p->next;}if(p!=NULL)cout<<p->date<<endl;else{cout<<"超出线性表的长度,按任意键退出!"<<endl;getchar();exit(0);}}int lengthlist(lnode *hl){int i=0;while(hl->next!=NULL){i++;hl=hl->next;}return i;}void cleanlist(lnode *&hl){lnode *ap,*cp;ap=hl->next;while(ap!=NULL){cp=ap->next;delete ap;ap=cp;}hl->next=NULL;}bool deletelist(lnode *&hl,elemtype item){ if(hl->next==NULL){cout<<"线性表为空,按任意键退出!"<<endl;getchar();exit(0);}lnode *ap,*cp;ap=hl->next;cp=NULL;while(ap!=NULL){if(ap->date==item)break;else{cp=ap;ap=ap->next;}if(ap==NULL){cout<<"没有需要删除的元素!"<<endl;return false;}}if(cp==NULL)hl->next=ap->next;elsecp->next=ap->next;delete ap;cout<<"线性表中现在的元素为:"<<endl;travellist(hl);cout<<"线性表现在的长度为:"<<lengthlist(hl)<<endl;return true;}void mergelist(lnode *&la,lnode *&lb,lnode *&lc){lnode *p1,*p2,*p3;p1=la->next;p2=lb->next;while(p1!=NULL&&p2!=NULL){if(p1->date<=p2->date){lc->next=p1;p1=p1->next;lc=lc->next;}else{lc->next=p2;p2=p2->next;lc=lc->next;}}if(p1!=NULL)lc->next=p1;elselc->next=p2;}。