线性表的链式表示和实现

1、数学与计算科学学院实 验 报 告实验项目名称 线性表的链式表示和实现 所属课程名称 数据结构 实 验 类 型 验证型 实 验 日 期 2013.10.31 班 级 信计1201 学 号 201253100109 姓 名 成 绩 一、实验概述：【实验目的】1、了解线性表的逻辑结构特征：总存在第一个和最后一个元素；除第一个元素外，每个元素总存在唯一一个直接前驱元素；除最后一个元素外，每个元素总有唯一一个直接后继元素。2、掌握单链表的基本操作在链式存储结构上的实现【实验原理】1、线性链表特点：是一种动态分配存储结构，每一个结点的指示域指向其直接后继结点（尾结点除外）；指针为数据元素之间的逻辑关系的映

2、像。2、线性表的单链表存储结构：typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;【实验环境】VC + 6.0二、实验内容：【实验方案】编写主函数，调用线性链表的初始化建空表、查找、插入和删除算法，调制运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1、输入线性链表的初始化建空表、查找、插入、删除算法以及主函数：/线性表的单链表存储结构typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;void CreateLi

3、st_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 &

4、;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

5、' : 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&&j<i-1)p=p->nex

6、t;+j; if(!p|j>i-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:

7、 '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，表示删除链表第四个元素，回车得结果，完成链表的删除算法；

8、最终完成链表的初始化建空表、查找、插入和删除的算法。【实验结论】（结果）【实验小结】（收获体会）在这次上机实验中，在进行调制时，自己慢慢调试，渐渐地了解了那些错误什么意思，如何修改，最终完成了线性表的链式表示和实现，对线性链表的初始化建空表、查找、插入、和删除算法有了进一步了解。三、指导教师评语及成绩：评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include<stdio.h>#include

9、<stdlib.h>#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;LinkL

10、ist p;L=(LinkList) malloc(sizeof(LNode);L->next=NULL; /先建立一个代表头结点的单链表for(i=n;i>0;-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个元素存在时

11、，其值赋给e并返回OK,否则返回ERRORint j;LinkList p;p=L->next;j=1; /初始化，p指向第一个结点，j为计数器while(p&&j<i) /顺指针向后查找，直到p指向第i个元素或p为空p=p->next;+j;if(!p|j>i)return ERROR; /第i个元素不存在e=p->data; /取第i个元素return OK;/GetElem_LStatus ListInsert_L(LinkList &L,int i,ElemType e)/在带头结点的单链线性表L中第i个位置之前插入元素eLinkL

12、ist p,s;int j;p=L; j=0;while(p&&j<i-1)p=p->next;+j; /寻找第i-1个结点if(!p|j>i-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)/在带头结点

13、的单链线性表L中，删除第i个元素，并由e返回其值LinkList p,q;int j;p=L;j=0;while(p->next &&j<i-1) /寻找第i个结点，并令p指向其前趋p=p->next;+j;if(!(p->next)|j>i-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

14、; 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

15、->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实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法