实验五__线性表的链式表示和实现.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服务器上（ 22:2007 ）自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） 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四. 实验结果与分析（包括运行结果截图、结果分析等）1. 2.五. 心得体会要多看书多注意程序的完整性【附录-源程序】1. test5.cpp#include #include #include typedef int ElemType;typedef struct NodeElemType data;struct Node *next;LNode;#includeLinkList.hvoid main()LNode *Head;ElemType x;int i;InitList(Head);for(i=1;i x;InsertList(Head,x,0);TraverseList(Head);cin x;InsertList(Head,x,0);TraverseList(Head);DeleteList(Head,x,3);cout 被删除的元素 x next=NULL; / 指针域为空 void ClearList(LNode *&H) /释放动态申请的内存空间LNode *cp, *np; /当前结点指针与后继结点指针 cp=H;while(cp!=NULL) /按顺序遍历单链表，释放每个结点 np=cp-next; / 保存下一个结点 free(cp); cp=np; /使下一个结点成为当前结点H=NULL; /置单链表为空int LengthList (LNode *H)LNode *p=H-next; /用来遍历链表结点int i=0; /用来统计结点个数while(p!=NULL)i+; p=p-next;return i;bool EmptyList (LNode *H) return H-next = NULL; ElemType GetList (LNode *H, int pos) LNode *p=H-next; /用来遍历链表结点 int i=0; /用来统计已查找的结点个数 if (pos1) cerr pos is out range!next; if (p!=NULL) return p-data; else /pos值大于表长 cerrpos is out range!next; /用来遍历链表结点while(p!=NULL) if (p-data=item)return true; else p=p-next;return false;void TraverseList(LNode *H) LNode *p=H-next; while ( p!=NULL ) coutdatanext; coutendl;bool InsertList ( LNode *&H, ElemType item, int pos) LNode *newptr, *cp, *ap; if (pos-1) cout参数不合法next; ap=H;if (pos = 0) /按值有序插入情况 while ( cp != NULL) if ( item data ) 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 ) cout参数不合法data = item; newptr-next=cp; ap-next=newptr;return true;bool DeleteList ( LNode *&H, ElemType &item, int pos)LNode *cp, *ap;if (H-next=NULL) cerr空表，不能删除!endl; return false; if (pos-1) cout参数不合法!next; ap=H;if (pos = 0) /按值删除情况 while ( cp != NULL) if ( item = cp-data ) break; else ap=cp; cp=cp-next; if (cp=NULL) cout没有相应结点可删除!next != 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) cout参数不合法!data; ap-next=cp-next; /删除非表头结点，即cp所指的结点 free(cp); return true;2.test5_2.cpp#include #include #include typedef int ElemType;typedef struct NodeElemType data;struct Node *next;LNode;#includeLinkList_2.hvoid main()LNode *H1,*H2,*H3;ElemType x;int i;InitList(H1);InitList(H2);for(i=1;i x;InsertList(H1,x,0);TraverseList(H1);for(i=1;i x;InsertList(H2,x,0);TraverseList(H2);MergeList(H1,H2,H3);TraverseList(H3);ClearList(H1);LinkList2.hvoid 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);void InitList(LNode *&H) /构造一个空的线性链表H，即为链表设置一个头结点，/头结点的data数据域不赋任何值，头结点的指针域next则为空 H=(LNode *)malloc(sizeof(LNode); / 产生头结点H if (!H) exit(0); / 存储分配失败，退出系统 H-next=NULL; / 指针域为空 void ClearList(LNode *&H) /释放动态申请的内存空间LNode *cp, *np; /当前结点指针与后继结点指针 cp=H;while(cp!=NULL) /按顺序遍历单链表，释放每个结点 np=cp-next; / 保存下一个结点 free(cp); cp=np; /使下一个结点成为当前结点H=NULL; /置单链表为空int LengthList (LNode *H)LNode *p=H-next; /用来遍历链表结点int i=0; /用来统计结点个数while(p!=NULL)i+; p=p-next;return i;bool EmptyList (LNode *H) return H-next = NULL; ElemType GetList (LNode *H, int pos) LNode *p=H-next; /用来遍历链表结点 int i=0; /用来统计已查找的结点个数 if (pos1) cerr pos is out range!next; if (p!=NULL) return p-data; else /pos值大于表长 cerrpos is out range!next; /用来遍历链表结点while(p!=NULL) if (p-data=item)return true; else p=p-next;return false;void TraverseList(LNode *H) LNode *p=H-next; while ( p!=NULL ) coutdatanext; coutendl;bool InsertList ( LNode *&H, ElemType item, int pos) LNode *newptr, *cp, *ap; if (pos-1) cout参数不合法next; ap=H;if (pos = 0) /按值有序插入情况 while ( cp != NULL) if ( item data ) 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 ) cout参数不合法data = item; newptr-next=cp; ap-next=newptr;return true;bool DeleteList ( LNode *&H, ElemType &item, int pos)LNode *cp, *ap;if (H-next=NULL) cerr空表，不能删除!endl; return false; if (pos-1) cout参数不合法!next;