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

数学与计算科学学院实 验 报 告实验项目名称 线性表的链式表示和实现 所属课程名称 数据结构 实 验 类 型 验证型 实 验 日 期 2013.10.31 班 级 信计1201 学 号 201253100109 姓 名 成 绩 一、实验概述：【实验目的】1、了解线性表的逻辑结构特征：总存在第一个和最后一个元素；除第一个元素外，每个元素总存在唯一一个直接前驱元素；除最后一个元素外，每个元素总有唯一一个直接后继元素。2、掌握单链表的基本操作在链式存储结构上的实现【实验原理】1、线性链表特点：是一种动态分配存储结构，每一个结点的指示域指向其直接后继结点（尾结点除外）；指针为数据元素之间的逻辑关系的映像。2、线性表的单链表存储结构：typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;【实验环境】VC + 6.0二、实验内容：【实验方案】编写主函数，调用线性链表的初始化建空表、查找、插入和删除算法，调制运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1、输入线性链表的初始化建空表、查找、插入、删除算法以及主函数：/线性表的单链表存储结构typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void CreateList_L(LinkList &L,int n)/逆位序输入n个元素的值，建立带表头结点的单链线性表L。/CreateList_LStatus GetElem_L(LinkList L,int i,ElemType &e)/L为带头结点的单链表的头指针。/当第i个元素存在时，其值赋给e并返回OK,否则返回ERROR/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在带头结点的单链线性表L中第i个位置之前插入元素e/ListInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/在带头结点的单链线性表L中，删除第i个元素，并由e返回其值/ListDelete_Lvoid main()2、保存并开始调试，出现如下错误：error C2065: i : undeclared identifiererror C2065: p : undeclared identifier即i,p未定义，因i是整型，p是链表，故需在前面先进行定义：int i;LinkList p;在scanf(&p-data); /输入元素值 中出现错误：error C2664: scanf : cannot convert parameter 1 from int * to const char *.不能将参数1从int *到 const char *，因p-data表示的是一个数，故需说明输入的是一个十进制数，应修改为：scanf(“%d”,&p-data)；在Status ListInsert_L(LinkList &L,int i,ElemType e)int;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;/ListInsert_L中也出现错误：error C2065: p : undeclared identifier；error C2440: = : cannot convert from struct LNode * to int； error C2065: s : undeclared identifier；主要是由于在该编码中p,s表示的是链表，但没给它们进行定义，不能直接把链表赋给它们，因此需在前面对它们进行定义：LinkList p,s;3、把错误修正过来后，运行：输入一个数5，表示链表空间数，回车，再输入任意五个数字如：1 2 3 4 5，回车，得到：5 4 3 2 1，完成了链表的建立，并把链表倒转过来；输入数字3，表示查找链表中的第三个元素，回车得出结果，完成链表查找算法；输入2 45，表示在链表第二个元素前插入45，回车得结果，完成链表插入算法；再输入4，表示删除链表第四个元素，回车得结果，完成链表的删除算法；最终完成链表的初始化建空表、查找、插入和删除的算法。【实验结论】（结果）【实验小结】（收获体会）在这次上机实验中，在进行调制时，自己慢慢调试，渐渐地了解了那些错误什么意思，如何修改，最终完成了线性表的链式表示和实现，对线性链表的初始化建空表、查找、插入、和删除算法有了进一步了解。三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct LNodeElemType 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); /输入元素值p-next=L-next;L-next=p;/CreateList_LStatus GetElem_L(LinkList L,int i,ElemType &e)/L为带头结点的单链表的头指针。/当第i个元素存在时，其值赋给e并返回OK,否则返回ERRORint j;LinkList p;p=L-next;j=1; /初始化，p指向第一个结点，j为计数器while(p&jnext;+j;if(!p|ji)return ERROR; /第i个元素不存在e=p-data; /取第i个元素return OK;/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在带头结点的单链线性表L中第i个位置之前插入元素eLinkList p,s;int j;p=L; j=0;while(p&jnext;+j; /寻找第i-1个结点if(!p|ji-1) return ERROR; /i小于1或者大于表长加1s=(LinkList)malloc(sizeof(LNode); /生成新结点s-data=e;s-next=p-next; /插入L中p-next=s;return OK;/ListInsert_LStatus ListDelete_L(LinkList &L,int i,ElemType &e)/在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkList p,q;int j;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_Lvoid main()LinkList L;LinkList p; int n,i; 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(e=%dn,e);scanf(%d%d,&i,&e);ListInsert_L(L,i,e); for(p=L-next;p;p=p-next)printf(%d ,p-data);printf(n);scanf(%d,&i);ListDelete_L(L,i,e);for(p=L-next;p;p=p-next)printf(%d ,p-data);printf(n);附录2：实验报告填写说明 1实验项目名称：要求与实验教学大纲一致。2实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3实验原理：简要说明本实验项目所涉及的理论知识。4实验环境：实验用的软、硬件环境。5实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性