《数据结构实验报告剖析》由会员分享，可在线阅读，更多相关《数据结构实验报告剖析（25页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告( 一 ) 提交日期：班级姓 名学号上机号67实验名称线性表测试数据与运行记录线性表是最简单的线性结构。线性表的主要操作特点是可以在任意位置插入和删除一个数据元素。一、 线性表的顺序存储结构线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。我们采用的是含静态一维数组和线性表长的结构体。测试数据与运行记录如下：步骤一，建立线性表。输入 “1”。回车键入,得到“n=?”输入的n即为线性表所要存储的元素长度，由于建立线性表时已规定MAXSIZE=20，因此所输入的n应该小于等于20。此处实验输入n=6。然后，将想要插入的数据
2、元素分别输入数据域data 0到data5。回车键入，程序得出一段由6个数据元素组成的如下图所示的线性链表。链表数据为：1，2，3，4，5，6。测试数据与运行记录步骤二，插入数据元素选择 “2”。回车键入，得到“i，e=？”即输入想在位置i插入的数据元素e。本次测试中分别输入3和6。回车，程序运行得到如下图所展示的一个插入新元素的新链表，即在原数据链表中第3个数据元素所在位置插入新的数据元素“6”，原数据表中的第3个元素及以后的元素序号+1，同时，新链表的长度+1。因此本实验中新的到的数据链表长度为6+1=7，新链表中数据为：1，2，6，3，4，5，6。步骤三，删除数据元素选择 “3”。回车键
3、入，得到“i=？”，即键入想删除的第i个元素，返回该元素的值，使i+1及以后的数据元素的序号-1，同时，数据链表的长度-1。因此本实验中将步骤二中建立的数据链表第3个元素删除，删除后数据链表长度为7-1=6，得到的数据链表中的数据为：1，2，3，4，5，6。步骤四，查找元素选择 “4”。回车键入，得到“e=？”即在步骤三中新生成的数据链表中查找值为e的元素在链表所处的位置。因此本实验中输入e=“4”，程序运行结果为“已找到，元素位置是4”。另外输入数据链表中未存储的数据“10”，程序运行结果为“未找到 -1”，说明程序运行无误。测试数据与运行记录最后，程序运行完毕，回车退出。二、 线性表的链式
4、存储结构线性表链式存储的操作同样包括几个方面：线性表的建立、元素的插入、删除、查询等。其本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中可以不相邻,既地址不连续。根据指针域的不同和结点的构造链的方式不同，链表主要有单链表、单循环链表和双向循环链表。其中，单链表是最经常使用的链表。步骤一，建线性链表选择 “1”。输入元素组成一个链表。链表的建立与顺序表不同，它是一种动态结构。建立线性表的链式存储结构的过程就是一个动态生成链表的过程。因此每输入一个元素即重新分配新的结点，本次实验输入元素为：5，1，2，3，4，5，6，7。步骤二，插入元素链表和顺序表的插入运算不同，顺序表在插入时要
5、移动大量的结点，而链表在插入时不需要移动结点，但需要移动指针来进行位置的查找。先使p指向ai-1，然后生成一个数据域值为x的新结点*s，再进行插入操作。步骤三，删除第i个元素选择 “3”，回车键入，输入想要删掉的第“i”个元素步骤四，查找元素最后，程序运行完毕，回车退出。根据本部分实验总结的程序流程一、线性表的顺序结构存储(1)创建顺序表create_list L并输出表out_list L（注：本程序中未进行顺序表的初始化InitList L，其效果与create_list L的效果一样，对实验无影响。）/* 建立线性表 */void creat_list(SqList *L) int i;
6、 printf(n n=?); scanf(%d,&L-length); for(i=0;ilength;i+) printf(n data %d=?,i); scanf(%d,&(L-ai); /* creat_list */【说明】由于函数中要改变参数L的一维数组MAXSIZE的值，因此参数L应设计为输出型参数，即L设计为SqList的指针类型，否则，一维数组子域的修改值将不能带回去。(2)插入数据元素 insert_sqvoid insert_sq(SqList *L,int i,ElemType e) int j;if (L-length=MAXSIZE) printf(n overf
7、low !); else if(iL-length+1) printf(n erroe i !);根据本部分实验总结的程序流程 else for(j=L-length-1; ji-1; j-) L-aj+1=L-aj; /* 向后移动数据元素 */ L-ai-1=e; /* 插入元素 */ L-length+; /* 线性表长加1 */ /* insert_sq */【说明】数据元素个数size比数组下标，即参数i的值大1，所以插入位置参数i应大于等于0且小于等于宏定义的MAXSIZE 20.当参数i不在上述区间内时，即可判定参数出错。数组的存储空间是有限的，若当前已存满数组的MAXSIZE的
8、存储空间，则不能继续插入。（注：本程序先把存储单元i-1至存储单元i中的数据元素依次后移，然后把数据元素e插入到存储单元i中，最后把数据元素+1.）(3)删除数据元素delete_sqElemType delete_sq(SqList *L, int i) ElemType x; int j; if( L-length=0) printf(n 是空表。underflow !);else if(i L-length) printf(n error i !); x=-1; else x=L-ai-1; for(j=i; jlength-1; j+) L-aj-1=L-aj; L-length-;
9、return(x); /* delete_sq */【说明】若顺序表中当前没有一个数据元素，则无法进行删除，判断为函数调用出错。删除位置参数i应大于等于0且小于等于i-1，当参数i不在上述区间，即为参数出错。删除步骤总结如下：首先把存储单元i中的数据元素，即ai存放到参数x中，然后从前向后依次前移从存储位置i到存储单元i-1中的数据元素，最后把数据元素个数-1。（4）查找数据元素locat_sq(注：此处为按结点值查找方法，另有按结点序号查找get_sq)/* 查找值为 e 的元素，返回它的位置 */int locat_sq(SqList L, ElemType e) int i=0; whi
10、le(i=L.length-1 & L.ai!=e) i+; if(i=L.length-1) return(i+1); else return(-1); /* locat_sq */【说明】在表中按值查找结点，即从链表的开始结点出发，顺链逐个将结点的值和给定的值e进行比较，若遇到相等的，则返回结点的存储位置，否则返回1(按值查找法比按序号查找更为简单，建议使用前者)。三、 线性表的链式存储结构（1） 建立线性链表*creat_L并输出链表out_L根据本部分实验总结的程序流程（1）插入数据元素insert_Lvoid insert_L(LNode *L,int i, ElemType e)
11、LNode *s,*p; int j; p=L; /* 找第i-1个结点 */ j=0; while(p!=NULL & jnext; j+; if(p=NULL | ji-1) printf(n i ERROR !); else s=(LNode *)malloc(sizeof(LNode); s-data=e; s-next=p-next; p-next=s; /* insert_L */【说明】要在带头结点的单链表第i（0isize）个结点前插入一个存放数据元素e的结点，首先在单链表中寻找到第i-1个结点并由p指示，然后动态申请一个结点存储空间并由s指示，并s-data=e，最后修改新结
12、点指针域指向ai：s-next=p-next，并修改ai-1指针域使之指向s，即p-next=s。（2） 删除数据元素delete_L删除运算就是将链表中的第i个结点从表中删去。由于第i个结点的存储位置存储在第i-1个结点的指针域next中，因此要先使p指向第i-1个结点，然后使得p-next指向第i+1个结点，再将第i个结点释放掉。（3） 查找数据元素locat_L在单链表中按值查找结点，就是从链表的开始结点出发，顺链逐个将结点的值和给定的e进行比较，若相等，则返回结点的存储位置，否则程序return（-1）。实验中遇到的问题及解决情况1、 VC6.0自动检测出的错误显示为“getch:un
13、declared identifier”。问题分析：“undeclared identifier”意为未声明的标识符。未声明的标识符有以下两种情况：一为没有声明的语句直接使用；二为没有声明语句，直接使用函数。因此此处可以添加头文件。头文件的作用是避免多个代码文件全局变量（函数），防止定义冲突。因此可以在函数声明处添加#include另外，getch（）函数在此程序中并未起实际作用，可以删去。2、VC6.0检测错误显示“main : function should return a value; void return type assumed”。问题分析：”main：function should return a value”意为主函数没有返回值 ，有三种改正方法：(1) 改为空类型，即把main（）改为void main( )；(2) 不加void的话主函数默认返回值是int，所以可以把main( )改为int main（），再在主函数末尾加入return（0）；(3) 直接只加入re
