实验五 线性表的链式表示和实现.doc

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验五 线性表的链式表示和实现 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、了解线性表的链式存储结构，学会定义线性表的链式存储结构。2、掌握单链表、循环单链表的一些基本操作实现函数。二. 实验内容1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件LinkList.h中（注：教材上为不带表头附加结点）。同时建立一个验证操作实现的主函数文件test5.cpp，编译并调试程序，直到正确运行。 提示： 单向链表的存储结构可定义如下： struct LNode / 定义单链表节点类型 ElemType data; / 存放结点中的数据信息 LNode *next; / 指示下一个结点地址的指针 线性表基本操作可包括如下一些： void InitList (LNode *&H) /初始化单链表 void ClearList(LNode *&H) /清除单链表 int LengthList (LNode *H) /求单链表长度 bool EmptyList (LNode *H) /判断单链表是否为空表 ElemType GetList (LNode *H, int pos) /取单链表第 pos 位置上的元素 void TraverseList(LNode *H) /遍历单链表 bool InsertList ( LNode *&H, ElemType item, int pos)/向单链表插入一个元素 bool DeleteList ( LNode *&H, ElemType &item, int pos)/从单链表中删除一个元素 带表头附加结点的单链表初始化操作的实现可参考如下： void InitList(LNode *&H) /构造一个空的线性链表H，即为链表设置一个头结点，/头结点的data数据域不赋任何值，头结点的指针域next则为空 H=(LNode *)malloc(sizeof(LNode); / 产生头结点H if (!H) exit(0); / 存储分配失败，退出系统 H-next=NULL; / 指针域为空 2、选做部分：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc) ，实现将两个有序单链表La和 Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb。要求把该函数添加到文件LinkList.h中，并在主函数文件test5.cpp中添加相应语句进行测试。3、填写实验报告，实验报告文件取名为report5.doc。4、上传实验报告文件report5.doc 、源程序文件test5.cpp及LinkList.h到Ftp服务器上（ 40:5000 ）自己的文件夹下。三. 函数的功能说明及算法思路 void InitList (LNode *&H) /初始化单链表 void ClearList(LNode *&H) /清除单链表 int LengthList (LNode *H) /求单链表长度 bool EmptyList (LNode *H) /判断单链表是否为空表 ElemType GetList (LNode *H, int pos) /取单链表第 pos 位置上的元素 void TraverseList(LNode *H) /遍历单链表 bool InsertList ( LNode *&H, ElemType item, int pos)/向单链表插入一个元素 bool DeleteList ( LNode *&H, ElemType &item, int pos)/从单链表中删除一个元素void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc)算法思路：实现将两个有序单链表La和 Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb。四. 实验结果与分析五. 心得体会注意表头附加结点和不加表头附加结点的区别【附录-源程序】test5.cpp#include#include#includetypedef int ElmeType;struct LNodeElmeType data;LNode *next;#includeLinkList.hvoid main()ElmeType x;LNode *ListOne,*ListTwo,*ListThree;InitList(ListOne);couta-1x;while(x!=-1)InsertList(ListOne,x,0);cinx;if(EmptyList(ListOne)coutendl;elsecoutendl;TraverseList(ListOne);coutLengthList(ListOne)endl;coutx;DeleteList(ListOne,x,0);TraverseList(ListOne);coutx;coutGetList(ListOne,x)endl;InitList(ListTwo);coutb-1x;while(x!=-1)InsertList(ListTwo,x,0);cinx;InitList(ListThree);MergeList(ListOne,ListTwo,ListThree);TraverseList(ListThree);ClearList(ListOne);LinkList.hvoid InitList(LNode *&H) H=(LNode *)malloc(sizeof(LNode); if (!H) exit(0); H-next=NULL; void ClearList(LNode *&H)LNode *cp;LNode *np;cp=H-next;while(cp!=NULL)np=cp-next;delete cp;cp=np;H-next=NULL;int LengthList (LNode *H)int i=0;while(H-next!=NULL)i+;H=H-next;return i;bool EmptyList (LNode *H)return H-next=NULL;ElmeType GetList (LNode *H, int pos) if(pos1)cerrPos is out range!next!=NULL)i+;if(pos=i) break;H=H-next;if(H!=NULL)return H-next-data;else cerrpos is out range!next;while(p!=NULL)coutdatanext;coutendl;bool InsertList ( LNode *&H, ElmeType item, int pos)if(pos-1)coutpos data=item;LNode *cp=H-next;LNode *ap=H;if(pos=0)while(cp!=NULL)if(itemdata) break;else ap=cp;cp=cp-next;else if(pos=-1)while(cp!=NULL)ap=cp;cp=cp-next;else int i=0;while(cp!=NULL)i+;if(i=pos) break;else ap=cp; cp=cp-next;if(cp=NULL & i+1pos)coutpos1next=H;H=newptr;elsenewptr-next=cp;ap-next=newptr;return true;bool DeleteList ( LNode *&H, ElmeType &item, int pos)if(H-next=NULL)cerrendl;return false;if(pos-1)coutposnext;LNode *ap=H;if(pos=0)while(cp!=NULL)if(item=cp-data) break;elseap=cp;cp=cp-next;if(cp=NULL)coutdata!=NULL)ap=cp;cp=cp-next;elseint i=0;while(cp!=NULL)i+;if(i=pos) break;else ap=cp;cp=cp-next;if(cp=NULL)coutposnext;else ap-next=cp-next;delete cp;return true;void MergeList(LNode *&La,