数据结构线性表的顺序表示和实现的实习报告范本

1、 .数学与计算科学学院实 验 报 告实验项目名称线性表的顺序表示与实现所属课程名称 数据结构实 验 类 型 验证型实 验 日 期 班 级 学 号 姓 名 成 绩 一、 实验概述：实验目的1 线性表的逻辑结构特征1.1 以元素在计算机“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。 1.2 有且仅有一个开始结点，没有直接前驱，且仅有一个直接后继；有且仅有一个终结结点，没有直接后继，且仅有一个直接前驱。1.3 其余部结点都有且仅有一个直接前驱和一个直接后继。2 掌握线性表的基本操作在顺序存储结构上的实现。实验原理1 顺序表的特点 1.1 逻辑位置上相邻和物理位置上相邻1.2 是一种随机存储结

2、构，其存储位置可以用一简单直观的公式表示2 顺序表的类C语言表示：#define LIST_INIT_SIZE 9 /线性表存储空间的初始分配量#define LISTINCREMENT 2 /线性表存储空间的分配增量typedef struct ElemType * elem;/存储空间基址 int length;/当前长度 int listsize;/当前分配的存储容量（以sizeof（ElemType）为单位）SqList;实验环境VC+6.0二、实验容实验方案编写主函数，调用顺序表的初始化建空表，插入和删除算法，调试运行得出结果实验过程（实验步骤、记录、数据、分析）8. 先将线性表的动

3、态分配顺序存储结构,算法与主函数编入VC+6.0中typedef struct ElemType * elem; int length; int listsize;SqList;Status InitList_Sq(SqList &L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK;Status ListInsert_Sq(SqList &L,int i,E

4、lemType e) if (i<1|i>L.length+1) return ERROR; if(L.length>=L.listsize) newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType); if(! newbase)exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p>=q;- -p)*(p

5、+1)=*p; *q=e; +L.length; return OK;Status ListDelect_Sq(SqList &L,int i,ElemType &e) if(i<1)|(i>L.length) return ERROR;p=&(L.elemi-1);e=*p; q=L.elem+L.length-1; for(+p;p<=q;+p) *(p-1)=*p; -L.length; return OK;void main() SqList L; int i; InitList_Sq(L);for(i=0;i<LIST_INIT_SIZ

6、E;i+) scanf("%d",&L.elemi); L.length+; for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); ElemType e; scanf("%d%d",&i,&e); ListInsert_Sq(L,i,e); for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); scanf(&quo

7、t;%d",&i); ListDelect_Sq(L,i,e); for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n");2.调试第一次出现的错误：原因：由于许多变量未定义，以与没有头文件与宏定义所以错误许多，还有更多错误没有显示出来3.将以下语句编入程序中：#include "stdio.h"#include "stdlib.h"#define TRUE 1#define FALSE 0#define OK 1#define ER

8、ROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 9 #define LISTINCREMENT 2typedef int ElemType; typedef int Status;4.调试第二次出现以下错误：原因：是在每个算法中有许多变量未定义，导致许多错误5.再将语句: int *newbase; int *q; int *p;写入插入算法中；将语句： int *p; int *q;写入删除算法中；6.调试第三次显示没有错误：7.运行第一次显示结果为：8. 但运行后的界面显得很单调；要是忘记下一个算法是什

9、么就容易输入出错，也不适合大众使用；因此为了将程序优化，所以在主函数中增加以下输入输出语句和条件语句；为了让程序更加严谨，因此还加入一些循环语句。int i,p,q;p=2,q=2;printf("请输入您想构建的顺序表（元素为%d个）:n",LIST_INIT_SIZE);printf("您构建的顺序表是:n");printf("请输入您想在第几个元素位置前插入元素:n",LIST_INIT_SIZE);while(i<=0|i>L.length)&&p>=0)printf("输入的数字错

10、误,（只剩下%d次重新输入符合要求的数字的机会）n",p);-p;if(p<0)printf("原因:您输入数字错误过多,程序终止运行n");return ERROR;scanf("%d",&i);printf("请输入您想插入的数:n");printf("形成的新顺序表为:n");printf("请输入您想删除的是第几个元素:n");while(i<=0|i>L.length)&&q>=0)printf("输入的数字错误,（只

11、剩下%d次重新输入符合要求的数字的机会）n",q);-q;if(q<0)printf("原因:您输入数字错误过多,程序终止运行n");return ERROR;printf("删除的数为:n");printf("%dn",e);printf("形成的新顺序表为:n");将语句scanf("%d%d",&i,&e);变为scanf("%d",&i);scanf("%d",&e);9. 那么主函数包含的语句变为：

12、main()SqList L;int i,p,q;p=2,q=2;InitList_Sq(L);printf("请输入您想构建的顺序表（元素为%d个）:n",LIST_INIT_SIZE);for(i=0;i<LIST_INIT_SIZE;i+) scanf("%d",&L.elemi); L.length+;printf("您构建的顺序表是:n");for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); Elem

13、Type e;printf("请输入您想在第几个元素位置前插入元素:n"); scanf("%d",&i);while(i<=0|i>L.length)&&p>=0)printf("输入的数字错误,（只剩下%d次重新输入符合要求的数字的机会）n",p);-p;if(p<0)printf("原因:您输入数字错误过多,程序终止运行n");return ERROR;scanf("%d",&i);printf("请输入您想插入的数:n&q

14、uot;);scanf("%d",&e);ListInsert_Sq(L,i,e);printf("形成的新顺序表为:n");for(i=0;i<L.length;i+) printf("%d ",L.elemi);printf("n");printf("请输入您想删除的是第几个元素:n"); scanf("%d",&i);while(i<=0|i>L.length)&&q>=0)printf("输入的数字错误

15、,（只剩下%d次重新输入符合要求的数字的机会）n",q);-q;if(q<0)printf("原因:您输入数字错误过多,程序终止运行n");return ERROR;scanf("%d",&i);ListDelect_Sq(L,i,e);printf("删除的数为:n");printf("%dn",e);printf("形成的新顺序表为:n");for(i=0;i<L.length;i+) printf("%d ",L.elemi);printf

16、("n");return 0;10. 调试第四次显示没错误：11. 运行第二次显示结果为：12. 运行第三次显示结果为：13. 运行第四次显示结果为：这样那么程序就完整了，清晰明了，用户运行的时候也容易知道自己要输入什么了实验结论（结果）实验小结（收获体会）1. 实验程序应该多些注释，这样方便人家读懂自己编写的程序。2. 主函数中多增加一些printf函数，方便运行时输入数据3. 编写程序是细心一点，注意大小写，注意单词拼写，还要注意分号4. 努力看书，要看懂算法的功能，结合C语言知识能快速调试并且改正错误5. 要清楚算法不同于程序，算法就相当于C语言中的定义函数功能语句且

17、是不完整的语句。三、指导教师评语与成绩：评 语评语等级优良中与格不与格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序#include "stdio.h"#include "stdlib.h"#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LI

18、ST_INIT_SIZE 9 /线性表存储空间的初始分配量#define LISTINCREMENT 2 /线性表存储空间的分配增量typedef int ElemType; /自定义类型名typedef int Status;typedef struct ElemType * elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量（以sizeof（ElemType）为单位）SqList;Status InitList_Sq(SqList &L)/ 构造一个空的线性表L L.elem=(ElemType*)malloc(LIST_INIT

19、_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); / 存储分配失败 L.length=0;/ 空表长度为0 L.listsize=LIST_INIT_SIZE;/ 初始存储容量return OK;Status ListInsert_Sq(SqList &L,int i,ElemType e)/ 在顺序线性表L的第i个元素之前插入新的元素e , i的合法值为1iListLength_Sq(L)+1int *newbase;int *q;int *p;if (i<1|i>L.length+1) return ERROR;/

20、i值不合法if(L.length>=L.listsize)/ 当前存储空间已满，增加容量 newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof (ElemType);if(! newbase)exit(OVERFLOW);/ 存储分配失败 L.elem=newbase;/ 新基址 L.listsize+=LISTINCREMENT;/ 增加存储容量 q=&(L.elemi-1); / q为插入位置for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p

21、; / 插入位置与之后的元素右移 *q=e;/ 插入e +L.length;/ 表长增1 return OK;Status ListDelect_Sq(SqList &L,int i,ElemType &e)/ 在顺序线性表L中删除第i个元素，并用e返回其值,i的合法值为1iListLength_Sq(L)int *p; int *q;if(i<1)|(i>L.length) return ERROR;/ i值不合法 p=&(L.elemi-1);/ p为被删除元素的位置 e=*p; / 被删除元素的值赋给e q=L.elem+L.length-1;/ 表尾

22、元素的位置 for(+p;p<=q;+p) *(p-1)=*p;/ 被删除元素之后的元素左移 -L.length;/ 表长减1return OK;main() SqList L;int i,p,q; p=2,q=2; InitList_Sq(L); printf("请输入您想构建的顺序表（元素为%d个）:n",LIST_INIT_SIZE);for(i=0;i<LIST_INIT_SIZE;i+) scanf("%d",&L.elemi); L.length+; printf("您构建的顺序表是:n");for(i

23、=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); ElemType e; printf("请输入您想在第几个元素位置前插入元素:n",L.length); scanf("%d",&i);while(i<=0|i>L.length)&&p>=0)printf("输入的数字错误,（只剩下%d次重新输入符合要求的数字的机会）n",p);-p;if(p<0)printf("原因:您输

24、入数字错误过多,程序终止运行n");return ERROR;scanf("%d",&i); printf("请输入您想插入的数:n"); scanf("%d",&e); ListInsert_Sq(L,i,e); printf("形成的新顺序表为:n"); for(i=0;i<L.length;i+) printf("%d ",L.elemi); printf("n"); printf("请输入您想删除的是第几个元素:n",L.length); scanf("%d",&i);w