数据结构线性表的顺序表示和实现的实习报告(共17页).doc

《数据结构线性表的顺序表示和实现的实习报告(共17页).doc》由会员分享，可在线阅读，更多相关《数据结构线性表的顺序表示和实现的实习报告(共17页).doc（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、和物理位置上相邻1.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二、【实验内容】【实验方案】编写主函数，调用顺序表的初始化建空表，插入和删除算法，调试运行得出结果【实

3、验过程】（实验步骤、记录、数据、分析）8. 先将线性表的动态分配顺序存储结构,算法与主函数编入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

4、_Sq(SqList &L,int i,ElemType e) if (iL.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+1)=*p

5、; *q=e; +L.length; return OK;Status ListDelect_Sq(SqList &L,int i,ElemType &e) if(iL.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;iLIST_INIT_SIZE;i+) scanf(%d,&L.elemi); L.length+; fo

6、r(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n); ElemType e; scanf(%d%d,&i,&e); ListInsert_Sq(L,i,e); for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n); scanf(%d,&i); ListDelect_Sq(L,i,e); for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n);2.调试第一次出现的错误：原因：由于许多变量未定义，以及没有头文件与宏定义所以错误许多，还有更多错误没有

7、显示出来3.将以下语句编入程序中：#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 LIST_INIT_SIZE 9 #define LISTINCREMENT 2typedef int ElemType; typedef int Status;4.调试第二次出现以下错误：原因：是在每个算法中有许多变量未定义，导致许多错误5.再将语句: int *newbase; int

8、*q; int *p;写入插入算法中；将语句： int *p; int *q;写入删除算法中；6.调试第三次显示没有错误：7.运行第一次显示结果为：8. 但运行后的界面显得很单调；要是忘记下一个算法是什么就容易输入出错，也不适合大众使用；因此为了将程序优化，所以在主函数中增加以下输入输出语句和条件语句；为了让程序更加严谨，因此还加入一些循环语句。int i,p,q;p=2,q=2;printf(请输入您想构建的顺序表（元素为%d个）:n,LIST_INIT_SIZE);printf(您构建的顺序表是:n);printf(请输入您想在第几个元素位置前插入元素:n,LIST_INIT_SIZE);

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

10、RROR;printf(删除的数为:n);printf(%dn,e);printf(形成的新顺序表为:n);将语句scanf(%d%d,&i,&e);变为scanf(%d,&i);scanf(%d,&e);9. 那么主函数包含的语句变为：main()SqList L;int i,p,q;p=2,q=2;InitList_Sq(L);printf(请输入您想构建的顺序表（元素为%d个）:n,LIST_INIT_SIZE);for(i=0;iLIST_INIT_SIZE;i+) scanf(%d,&L.elemi); L.length+;printf(您构建的顺序表是:n);for(i=0;iL.

11、length;i+) printf(%d ,L.elemi); printf(n); ElemType e;printf(请输入您想在第几个元素位置前插入元素:n); scanf(%d,&i);while(iL.length)&p=0)printf(输入的数字错误,（只剩下%d次重新输入符合要求的数字的机会）n,p);-p;if(p0)printf(原因:您输入数字错误过多,程序终止运行n);return ERROR;scanf(%d,&i);printf(请输入您想插入的数:n);scanf(%d,&e);ListInsert_Sq(L,i,e);printf(形成的新顺序表为:n);for

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

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

14、法不同于程序，算法就相当于C语言中的定义函数功能语句且是不完整的语句。三、指导教师评语及成绩：评 语评语等级优良中及格不及格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

15、 LIST_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_

16、INIT_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)+1 int *newbase; int *q; int *p; if (iL.length+1) return ERROR;/ i值不合法

17、 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; / 插入位置及之后的元素右移 *q

18、=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(iL.length) return ERROR;/ i值不合法 p=&(L.elemi-1);/ p为被删除元素的位置 e=*p; / 被删除元素的值赋给e q=L.elem+L.length-1;/ 表尾元素的位置 for(+p;p=q;+p) *(p-1)=*p;/ 被删除元素之后的

19、元素左移 -L.length;/ 表长减1 return OK;main() SqList L; int i,p,q; p=2,q=2; InitList_Sq(L); printf(请输入您想构建的顺序表（元素为%d个）:n,LIST_INIT_SIZE); for(i=0;iLIST_INIT_SIZE;i+) scanf(%d,&L.elemi); L.length+; printf(您构建的顺序表是:n); for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n); ElemType e; printf(请输入您想在第几个元素位置前插入元

20、素:n,L.length); scanf(%d,&i); while(iL.length)&p=0)printf(输入的数字错误,（只剩下%d次重新输入符合要求的数字的机会）n,p);-p;if(p0)printf(原因:您输入数字错误过多,程序终止运行n);return ERROR;scanf(%d,&i); printf(请输入您想插入的数:n); scanf(%d,&e); ListInsert_Sq(L,i,e); printf(形成的新顺序表为:n); for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n); printf(请输入您想

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

22、0;附录2：实验报告填写说明 1实验项目名称：要求与实验教学大纲一致。2实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3实验原理：简要说明本实验项目所涉及的理论知识。4实验环境：实验用的软、硬件环境。5实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。6实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。7实验结论（结果）：根据实验过程中得到的结果，做出结论。8实验小结：本次实验心得体会、思考和建议。9指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。专心-专注-专业