1、电子信息工程学院 2013 级数据结构实验报告姓名 学号实验项目线性表及其应用（I）实验内容1实现线性表的顺序存储结构和主要的基本操作，并添加输出显示等辅助函数，在此基础上实现后续两个算法。线性表的抽象数据类型定义参见教材第 19 页。顺序存储结构的定义参见教材第 22 页。2设线性表存放于顺序表 A 中，其中有 n 个元素，且递增有序，请设计一算法，将 x 插入到线性表的适当位置，以保持线性表的有序性。 （题集第 17 页 2.11）3试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,an）逆置为（an, an-1,a1） 。 （题集第 18 页 2.21）算法设计
2、与程序实现：算法分析本次实验的目的是理解和掌握线性表顺序存储结构的用法，要解决两个基本问题一是将元素插入到有序的顺序表中，并保持线性表的有序性；二是实现顺序表的就地逆置。首先需插入元素的顺序表是有序的，故需先将输入的线性表元素进行排序，至于数据排序，我选择的是起泡排序算法，而实现插入元素到顺序表，则是将待插入的元素与已排序的顺序表中的每个元素进行比较进而确定插入位置；实验内容二的就地逆置则仅仅只需用一个 for 循环将顺序表中对称位置处的元素交换即可。程序设计流程图如下所示：电子信息工程学院 2013 级数据结构实验报告开 始调 用 InitList_Sq(SqList /设置cmd窗口标题s
3、ystem(“color F1“); /设置控制台窗口的背景色和前景色system(“date /T“); /输出当前的日期system(“TIME /T“); /输出当前的时间int i,DIR; /控制变量电子信息工程学院 2013 级数据结构实验报告int LIST_MAX; /表长ElemType data; /待插入元素SqList L; /定义SqList类型变量InitList_Sq(L); /初始化顺序表printf(“1. 请输入所需建立的线性表的长度：“);scanf_s(“%d“, printf(“2. 请录入数据：“);for (i = 0; i#include #in
4、clude “ADT.h“/* 函数原型：Status InverseList_Sq(SqList /循环变量ElemType temp; /临时变量电子信息工程学院 2013 级数据结构实验报告for (i = 0; i = L.listsize) /当存储空间已满，增加分配newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType); /存储再分配if (!newbase) /分配失败，返回错误return OVERFLOW;L.elem = newbase; /将新的地址指针赋值，注
5、：另定义一个指针变量newbase,而不用L.elem，是因为防止存储分配失败，使原基址被覆盖L.listsize += LISTINCREMENT; /增加存储容量if (L.elem0 = L.elemi) /判断待插入元素是否大于当前位置元素j = i; /保存当前元素位序p = /指向满足上条件元素的后一个位置for (q = q = p; -q) /将待插入元素位*(q + 1) = *q;*p = e; /插入元素+L.length; /表长自增else电子信息工程学院 2013 级数据结构实验报告for (i = 0; i = p; -q) /将待插入元素位置后的元素依次后移一个
6、位置*(q + 1) = *q;*p = e; /插入元素+L.length; /表长自增return OK; /InsertSequentList_Sq/* 函数原型：Status BubbleSortList_Sq(SqList /循环控制变量ElemType temp; /临时缓存变量if (L.length = 0)printf(“错误,当前线性表为空,请录入数据：n“);return ERROR; /线性表错误if (L.length = 1)return OK;if (L.length = 2) /表中元素至少多于2个for (i = L.length; i 0; -i) /起泡法
7、排序for (j = 0; j L.elemj + 1) /前一个元素大于后一个元素temp = L.elemj; /保持较大的元素if (direction) /排序方式为递增L.elemj = L.elemj + 1; /交换电子信息工程学院 2013 级数据结构实验报告L.elemj + 1 = temp;elsetemp = L.elemj; /保持较小的元素 if (!direction) /排序方式为递减L.elemj = L.elemj + 1; /交换L.elemj + 1 = temp;return OK; /BubbleSortList_Sq运行结果实验结果分析：从以上实验
8、运行结果来说，程序可以实现实验要求的基本内容，至于数据输入等操作步骤从上图可以简单、明了的看出。实验总结1、此次实验遇到的问题是自己编写的头文件编译器打不开、出现类型重定义、枚举类型变量错误等，进而报出来很多的错误，经过长时间的仔细检查和搜索知道，需将头文件放到与源文件相同的目录下，而类型重定义则是少打了结构体类型名，至于枚举类型报错，则是因为枚举类型知识不牢靠，使用错误造成的，其他的错误则是函数编写逻辑错误等，但最终还是成功了，所以此次实验对我来说收货的很大的。2、此次程序中需要改进和优化的地方还很多，其中困扰我的是每次输入数据的时候都需要先设置表长，但输入的时候每次都要数自己输入了多少个数，所以我就想怎样在不初始输入表长的条件下，由函数自己判断是否数据输入结束，开始我想到的是在 for 循环下输入数据，当数据输入结束的时候判断是否输入n或者输入一些自己定义的数据结束标志，例如#等,但是这种判断方法很容易出现误判断，进而出现一些莫名其妙的数据，所以这个输入数据的算法还没有想出了。3、通过此次实验我学的的主要就是头文件的包含、typedef 定义类型的方法、结构体类型的使用和指针的正确使用，总之这次实验对我的编程有很大的帮助。电子信息工程学院 2013 级数据结构实验报告
