《数据结构实验报告剖析》由会员分享,可在线阅读,更多相关《数据结构实验报告剖析(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