数据结构线性表的链式表示和实现的实习报告

数学与计算科学学院实 验 报 告实验项目名称 线性表的链式表示与实现 所属课程名称 数据结构 实 验 类 型 验证型 实 验 日 期 班 级 学 号 姓 名 成 绩 一、 实验概述：【实验目的】1. 掌握单链表的基本操作在链式存储结构上的实现。2. 学会定义链式表的存储结构，学会用C+语言来实现链式表的基本操作，提高编程能力3. 线性表的逻辑结构特征 3.1 以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。 3.2 有且仅有一个开始结点，没有直接前驱，且仅有一个直接后继；有且仅有一个终结结点，没有直接后继，且仅有一个直接前驱。3.3 其余内部结点都有且仅有一个直接前驱和一个直接后继。【实验原理】1. 线性链表的特点1.1 动态分配的存储结构1.2 每一个结点的指针域指向其直接后继元素的数据域，尾元结点除外1.3 指针是数据元素之间的逻辑关系的映像2线性链表的类C语言表示typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;【实验环境】VC+6.0 二、【实验内容】【实验方案】编写主函数，调用链式表的存储结构初始化建表，插入和删除的算法，调试运行得出结果【实验过程】（实验步骤、记录、数据、分析）1. 先将线性表的单链表存储结构与算法编入VC+6.0中Typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList; void CreateList_L(LinkList &L, int n) L=(LinkList)malloc(sizeof(LNode); L-next=NULL; for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode); scanf(%d,&p-data); p-next=L-next; L-next=p;Status GetElem_L(LinkList L,int i,ElemType &e) p=L-next;j=1;while(p&jnext; +j;if(!p|ji) return ERROR;e=p-data;return OK;Status ListInsert_L(LinkList &L,int i,ElemType e)p=L;j=0;while(p&jnext; +j;if(!p|ji-1) return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;Status ListDelete_L(LinkList &L,int i,ElemType &e)p=L;j=0;while(p-next&jnext; +j;if(!p-next|ji-1) return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;2. 调试第一次显示错误如下：原因：由于没有头文件及宏定义以及自定义，因此导致许多错误，可能还有许多错误没有显示3. 将以下语句编入VC+6.0中#include stdio.h#include stdlib.h#define OK 1#define ERROR 0typedef int ElemType;typedef int Status;4. 调试第二次显示错误如下：原因：由于算法中许多变量没有定义，因此有许多错误5. 将以下语句加入算法中：int i;LinkList p;（加入创建链表的算法中）LinkList p;int j;（加入查找元素的算法中）LinkList p,s;int j;(加入插入元素的算法中)LinkList p,q;int j;（加入删除元素的算法中）6. 调试第三次显示没有错误：7. 现在开始编写主函数：（1） 先编写调用创建链表的函数的主函数：如下：void main()LinkList L;int i,n;scanf(%d,&n); CreateList_L(L,n);for(i=n;i0;-i) printf(%d ,L-data);printf(n);调试显示为：运行显示为：产生了随机数说明for循环语句那里编写错误因此修改为：LinkList p;for(p=L-next;p!=NULL;p=p-next) printf(%d ,p-data);调试显示为：运行显示为：这次正确了 那么继续编写下面的其他主函数，形成的总的主函数为：void main()LinkList L,p;int i,n;scanf(%d,&n); CreateList_L(L,n);for(p=L-next;p!=NULL;p=p-next) printf(%d ,p-data);printf(n);ElemType e;scanf(%d, &i);GetElem_L(L, i, e);printf(%dn,e);scanf(%d,&i);scanf(%d,&e);ListInsert_L(L, i, e);for(p=L-next;p!=NULL;p=p-next) printf(%d ,p-data);printf(n);scanf(%d, &i);ListDelete_L(L,i,e);printf(%dn,e);for(p=L-next;p!=NULL;p=p-next) printf(%d ,p-data);printf(n);8. 调试第四次显示为：9. 运行显示结果为：10. 但运行后的界面显得很单调；要是忘记下一个算法是什么就容易输入出错，也不适合大众使用；因此为了将程序优化，所以在主函数中增加以下输入输出语句和条件语句；为了让程序更加严谨，因此还加入一些循环语句以及条件语句，那么主函数语句变为：main()LinkList L,p;int i,n,x,y,z;ElemType e;printf(请输入您想构建的链式表的元素个数:n);scanf(%d,&n);printf(请输入您想构建的链式表:n);CreateList_L(L,n);printf(您构建的链式表是:n);for(p=L-next;p!=NULL;p=p-next) printf(%d ,p-data);printf(n);printf(请输入您想查找的元素是第几个元素:n);scanf(%d, &i);for(x=2;(in)&x=0;-x) switch(x) case 2:printf(输入的数字错误,还有两次重新输入符合要求的数字的机会:n);break; case 1:printf(输入的数字错误,还有一次重新输入符合要求的数字的机会:n);break; case 0:printf(输入的数字错误,您的输入机会已经用完n);return ERROR; scanf(%d,&i);GetElem_L(L, i, e);printf(您查找的元素是:n);printf(%dn,e);printf(请输入您想在第几个元素位置前插入元素:n);scanf(%d,&i);for(y=2;(in)&y=0;-y) switch(y) case 2:printf(输入的数字错误,还有两次重新输入符合要求的数字的机会:n);break; case 1:printf(输入的数字错误,还有一次重新输入符合要求的数字的机会:n);break; case 0:printf(输入的数字错误,您的输入机会已经用完n);return ERROR; scanf(%d,&i);printf(请输入您想插入的元素:n);scanf(%d,&e);ListInsert_L(L, i, e);printf(形成的新链式表为:n);for(p=L-next;p!=NULL;p=p-next)printf(%d ,p-data);printf(n);printf(请输入您想删除的元素是第几个元素:n);scanf(%d, &i);for(z=2;(in+1)&z=0;-z) switch(z) case 2:printf(输入的数字错误,还有两次重新输入符合要求的数字的机会:n);break; case 1:printf(输入的数字错误,还有一次重新输入符合要求的数字的机会:n);break; case 0:printf(输入的数字错误,您的输入机会已经用完n);return ERROR; scanf(%d,&i);ListDelete_L(L,i,e);printf(您想删除的元素是:n);printf(%dn,e);printf(形成的新链式表示:n);for(p=L-next;p!=NULL;p=p-next)printf(%d ,p-data);printf(n);return 0;11. 调试第五次显示为：、12. 运行后结果显示为：这样那么程序就完整了，清晰明了，用户运行的时候也易知道自己要输入什么了【实验结论】（结果）【实验小结】（收获体会）1. 实验程序应该多些注释，这样方便人家读懂自己编写的程序。2. 主函数中多增加一些printf函数，方便运行时输入数据3. 编写程序是细心一点，注意大小写，注意单词拼写，还要注意分号4. 努力看书，要看懂算法的功能，结合C语言知识能快速调试并且改正错误5. 要清楚算法不同于程序，算法就相当于C语言中的定义函数功能语句且是不完整的语句。三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include stdio.h#include stdlib.h#define OK 1#define ERROR 0typedef int ElemType;typedef int Status;typedef struct LNode ElemType data; struct LNode *next;LNode,*LinkList;void CreateList_L(LinkList &L, int n)/ 逆位序输入n个元素的值，建立带表头结点的单链线性表L int i; LinkList p; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; / 先建立一个带头结点的单链表 for(i=n;i0;-i) p=(LinkList)malloc(sizeof(LNode);/ 生成新结点 scanf(%d,&p-data);/ 逆位序输入n个元素的值 p-next=L-next; L-next=p;/ 插入到表头 / CreateList_LStatus GetElem_L(LinkList &L,int i, ElemType &e) / 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p; int=j; p = L-next; j = 1; / 初始化，p指向第一个结点，j为计数器 while (p & jnext; +j; / 顺指针向后查找，直到p指向第i个元素或p为空 if ( !p | ji ) return ERROR; / 第i个元素不存在 e = p-data; / 取第i个元素 return OK; / GetElem_Lstatus ListInsert_L(LinkList &L,int i,ElemType e)/ 在带头结点的单链线性表L的第i个元素之前插入元素eint j;LinkList p,s;p=L;j=0;while(p&jnext; +j;if(!p|ji-1)/ i小于1或者大于表长 return ERROR;s=(LinkList)malloc(sizeof(LNode); / 生成新结点s-data=e;s-next=p-next;/ 插入L中p-next=s;return OK;/ LinstInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/ 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值int j;LinkList p,q;p=L;j=0;while(p-next&jnext; +j;if(!p-next|ji-1) return ERROR;/ 删除位置不合理q=p-next;p-next=q-next;e=q-data;free(q);/ 删除并释放结点return OK;/ ListDelete_Lmain()LinkList L,p;int i,n,x,y,z;ElemType e;printf(请输入您想构建的链式表的元素个数:n);scanf(%d,&n);printf(请输入您想构建的链式表:n);CreateList_L(L,n);printf(您构建的链式表是:n);for(p=L-next;p!=NULL;p=p-next) printf(%d ,p-data);printf(n);printf(请输入您想查找的元素是第几个元素:n);scanf(%d, &i);for(x=2;(in)&x=0;-x) switch(x) case 2:printf(输入的数字错误,还有两次重新输入符合要求的数字的机会:n);break; case 1:printf(输入的数字错误,还有一次重新输入符合要求的数字的机会:n);break; case 0:printf(输入的数字错误,您的输入机会已经用完n);return ERROR; scanf(%d,&i);GetElem_L(L, i, e);printf(您查找的元素是:n);printf(%dn,e);printf(请输入您想在第几个元素位置前插入元素:n);scanf(%d,&i);for(y=2;(in)&y=0;-y) switch(y) case 2:printf(输入的数字错误,还有两