实验一 线性表及其应用(I)

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循环将顺序表中对称位置处的元素交换即可。程序设计流程图如下所示：核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下：1.主函数如下：#include "std

3、afx.h" /标准输入输出函数头文件#include "windows.h" /cmd窗口设置函数头文件#include "ADT.h" /数据结构中相关结构体类型定义及相关数据类型定义#include "DataStructure_LinearList.h" /数据结构第二章线性表中相关函数的定义及声明int main()system("title 数据结构实验 实验名称： 线性表及其应用(I)"); /设置cmd窗口标题system("color F1"); /设置控制台窗口的背

4、景色和前景色system("date /T"); /输出当前的日期system("TIME /T"); /输出当前的时间int i,DIR; /控制变量int LIST_MAX; /表长ElemType data; /待插入元素SqList L; /定义SqList类型变量InitList_Sq(L); /初始化顺序表printf("1. 请输入所需建立的线性表的长度：");scanf_s("%d", &LIST_MAX);printf("2. 请录入数据：");for (i = 0;

5、i<LIST_MAX; i+)scanf_s("%d", &(L.elemi); /向顺序表中输入数据 +L.length; /表长自增1printf("3. 请选择数据的排序方式（0：递减，1：递增）：");scanf_s("%d", &DIR);if (DIR)BubbleSortList_Sq(L, INCREASE); /将顺序表递增排序printf("4. 数据递增排列：");elseBubbleSortList_Sq(L, DECREASE); /将顺序表递减排序printf(&q

6、uot;4. 数据递减排列：");PrintfList_Sq(L); /打印输出printf("n5. 请输入待插入的元素：");scanf_s("%d", &data);InsertSequentList_Sq(L, data); /将数据元素插入到顺序表L中printf("6. 插入元素后的顺序表：");PrintfList_Sq(L); /打印输出InverseList_Sq(L); /将顺序表就地逆置printf("n7. 就地逆置后的顺序表：");PrintfList_Sq(L); /打

7、印输出printf("nn");return 0;2.头文件”ADT.h”的部分程序如下：#ifndef ADT_H_#define ADT_H_/* 常 量 和 数 据 类 型 预 定 义*/* -函数结果状态代码- */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/* -排序方式状态- */#define INCREASE 1 /递增#define DECREASE 0 /递减/* -数据类型预定义- */typedef i

8、nt Status; /函数结果状态类型typedef int _bool; /bool状态类型/* 数 据 结 构 类 型 定 义*/*线 性 表*/* -顺序表数据类型定义- */typedef int ElemType; /顺序表中元素的数据类型/* -线性表的动态存储分配初始常量预定义- */#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量/* -顺序存储结构类型定义- */typedef structElemType * elem; /存储空间基址int length; /当

9、前长度int listsize; /当前分配的存储容量SqList; /顺序表类型3.头文件”DataStructure_LinearList.h”中部分函数定义如下：#include <stdio.h>#include <malloc.h>#include "ADT.h"/* 函数原型：Status InverseList_Sq(SqList &L)* 函数功能：将线性表L就地逆置* 入口参数：结构体类型SqList的引用* 出口参数：返回函数结果状态*/Status InverseList_Sq(SqList &L) int i;

10、 /循环变量ElemType temp; /临时变量for (i = 0; i <= (L.length + 1) / 2; i+) /根据对称中心进行数据交换temp = L.elemi; /缓存需要交换的数据L.elemi = L.elemL.length - 1 - i; /对称位置数据交换L.elemL.length - 1 - i = temp;return OK; /InverseList_Sq/* 函数原型：Status InsertSequentList_Sq(SqList &L, ElemType e);* 函数功能：向已经过排序的线性表L中插入元素，插入位置由

11、数据在线性表的大小关系确定* 入口参数：结构体类型SqList的引用，待插入的数据* 出口参数：返回函数结果状态*/Status InsertSequentList_Sq(SqList &L, ElemType e)int i,j; /位序变量 ElemType *p, *q; /插入位置指针ElemType *newbase; /动态存储分配新基址指针if (L.length >= L.listsize) /当存储空间已满，增加分配newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(

12、ElemType); /存储再分配if (!newbase) /分配失败，返回错误return OVERFLOW;L.elem = newbase; /将新的地址指针赋值，注：另定义一个指针变量newbase,而不用L.elem，是因为防止存储分配失败，使原基址被覆盖L.listsize += LISTINCREMENT; /增加存储容量if (L.elem0 <= L.elem1) /判断此顺序表是否为递增for (i = 0; i < L.length; i+) /顺序查找if (e >= L.elemi) /判断待插入元素是否大于当前位置元素j = i; /保存当前元素

13、位序p = &(L.elemj+1); /指向满足上条件元素的后一个位置for (q = &(L.elemL.length - 1); q >= p; -q) /将待插入元素位*(q + 1) = *q;*p = e; /插入元素+L.length; /表长自增elsefor (i = 0; i < L.length; i+) /顺序查找if (e <= L.elemi) /判断待插入元素是否小于当前位置元素j = i; /保存当前元素位序p = &(L.elemj + 1); /指向满足上条件元素的后一个位置for (q = &(L.elem

14、L.length - 1); q >= p; -q) /将待插入元素位置后的元素依次后移一个位置*(q + 1) = *q;*p = e; /插入元素+L.length; /表长自增return OK; /InsertSequentList_Sq/* 函数原型：Status BubbleSortList_Sq(SqList &L,Status direction)* 函数功能：将已有数据的线性表L进行排序，排序方式由参数direction确定* 入口参数：已建立顺序表的引用&L，排序方式direction，当direction = INC = 1时，为递增，反之则为递减*

15、 出口参数：返回函数结果状态*/Status BubbleSortList_Sq(SqList &L,Status direction)int i,j; /循环控制变量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) /起泡法排序for (j = 0; j &

16、lt; i - 1; j+)if (L.elemj>L.elemj + 1) /前一个元素大于后一个元素temp = L.elemj; /保持较大的元素if (direction) /排序方式为递增L.elemj = L.elemj + 1;/交换L.elemj + 1 = temp;elsetemp = L.elemj; /保持较小的元素 if (!direction) /排序方式为递减L.elemj = L.elemj + 1; /交换L.elemj + 1 = temp;return OK; /BubbleSortList_Sq运行结果实验结果分析：从以上实验运行结果来说，程序可以实现实验要求的基本内容，至于数据输入等操作步骤从上图可以简单、明了的看出。实验总结1、此次实验遇到的问题是自己编写的头文件编译器打不开、出现类型重定义、枚举类型变量错误等，进而报出来很多的错误，经过长时间的仔细检查和搜索知道，需将头文件放到与源文件相同的目录下，而类型重定义则是少打了结构体类型名，至于枚举类型报错，则是因为枚举类型知识不牢靠，使用错误造成的，其他的错误则是函数编写逻辑错误等，但最终还是成功了，所以此次实验对我来说收货的很大的。2、此次程序中需要改进和优化的地方还很