试验一线性表和应用I

1、完美 WORD格式编辑姓名学号实 验 项 目线性表及其应用（1）实 验 内 容1实现线性表的顺序存储结构和主要的基本操作，并添加输出显示等辅助函数，在 此基础上实现后续两个算法。线性表的抽象数据类型定义参见教材第19页。顺序存储结构的定义参见教材第22页。2设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将x插入到线性表的适当位置，以保持线性表的有序性。（题集第17页2.11 ）3.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表 （a1,a2,an ）逆置为（an, an-1,a1 ）。（题集第 18 页 2.21 ）算法设计与程序实现：算法 分 析本次实验

2、的目的是理解和掌握线性表顺序存储结构的用法，要解决两个基本问题一是将元素插入到有序的顺序表中，并保持线性表的有序性；二是实现顺序表的就地逆置。首先需插入元素的顺序表是有序的，故需先将输入的线性表元素进行排序，至于数据排序，我选择的是起泡排序算法，而实现插入兀素到顺序表，则是将待插入的元素与已排序的顺序表中的每个元素进行比较进而确定插入位置；实验内容二的就地逆置则仅仅只需用一个 for循环将顺序表中对称位置处的元素交换即可。程序设计流程图如下所示：学习指导参考资料开始调用 lnitList_Sq(SqList &L)函数实现顺序表初始化输入需插入的元素data输入所需建立的顺序表的表长L

3、IST_MAX向线性表中录入数据输入选择顺序表的排序方式DIR调用函数BubbleSortList_Sq(SqList & L,Status direction)排序调用 PrintfList_Sq(Sqlist&L)函数输出顺序表到控制台核心 程 序此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下：1.主函数如下：#i nclude"stdafx.h"/标准输入输岀函数头文件#i nclude"wi ndows.h"cmd窗口设置函数头文件#i nclude"ADT.h&

4、quot;/数据结构中相关结构体类型定义及相关数据类型定义#in clude"DataStructure_Li nearList.h"/数据结构第二章线性表中相关函数的定义及声明int main()system( "title 数据结构实验实验名称：线性表及其应用(I)");system( "color F1");/设置控制台窗口的背景色和前景色system( "date /T");/输岀当前的日期system( "TIME /T");/输岀当前的时间int i,DIR;/控制变量int LIS

5、T MAX;/表长/设置cm(窗口标题ElemType data;/待插入元素SqList L;/定义SqList类型变量In itList_Sq(L);/初始化顺序表printf（"探1.请输入所需建立的线性表的长度:");seanf_s( "%d", &LIST_MAX);printf（"探2.请录入数据："）；for (i = 0; i<LIST MAX; i+)seanf_s( "%d", &(L.elemi);/ 向顺序表中输入数据+L.length;/ 表长自增 1printf(

6、" % 3.请选择数据的排序方式(0:递减，1:递增)：");seanf s( "%d", &DIR);if (DIR) elseBubbleSortList_Sq（L, DECREASE）; / 将顺序表递减排序 printf（"探4.数据递减排列："）；Prin tfList_Sq(L);/打印输出printf（ "n探5.请输入待插入的元素："）；seanf s( "%d", &data);In sertSeque ntList_Sq(L, data);/将数据元素插入到顺

7、序表L 中printf（"探6.插入元素后的顺序表："）；Prin tfList Sq(L);/打印输出In verseList_Sq(L);/将顺序表就地逆置printf（ "n探7.就地逆置后的顺序表："）；Prin tfList Sq(L);/打印输出printf("nn");return 0;2.头文件” ADTh ”的部分程序如下：#ifndef ADT H#define ADT_H/*常量和数据类型预定义*/* -函数结果状态代码 */#defi ne TRUE 1#defi ne FALSE 0#defi ne OK 1

8、#defi ne ERROR 0 #defi ne INFEASIBLE -1#defi ne OVERFLOW -2 /* - 排序方式状态 */#define INCREASE 1/ 递增#define DECREASE 0/ 递减/* -数据类型预定义-*/typedef int Status ;/函数结果状态类型typedef int _bool;/bool状态类型*数据结构类型定义*/*线丿j性表 */* -顺序表数据类型定义-*/typedef int ElemType;顺序表中元素的数据类型/* -线性表的动态存储分配初始常量预定义-*/#defi neLIST INIT SIZ

9、E 100/线性表存储空间的初始分配量#defi neLISTINCREMENT0/线性表存储空间的分配增量/* -顺序存储结构类型定义-*/typedef structElemType * elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量SqList ;顺序表类型3.头文件” DataStructure_丄in earList.h”中部分函数定义如下：#i nclude <stdio.h>#in elude <malloc.h> #i nclude "ADT.h"/* 函数原型：Status I

10、nverseList_Sq(SqList &L)*函数功能：将线性表L就地逆置*入口参数：结构体类型SqList的引用*岀口参数：返回函数结果状态*/Status InverseList Sq(SqList &L)int i;/循环变量ElemType temp;临时变量for (i = 0; i <= (L.length + 1) / 2; i+)/根据对称中心进行数据交换temp = L.elemi;/缓存需要交换的数据L.elemi = L.elem L.length - 1 - i;/ 对称位置数据交换L.elem L.length - 1 - i = temp;

11、return OK /In verseList Sq/* 函数原型：Status InsertSequentList_Sq(SqList &L, ElemType e);*函数功能：向已经过排序的线性表 L中插入元素，插入位置由数据在线性表的大小关系确定*入口参数：结构体类型SqList的引用，待插入的数据*岀口参数：返回函数结果状态*/Status InsertSequentList_Sq( SqList &L, ElemType e)int i,j;/位序变量ElemType *p, *q;/插入位置指针ElemType *newbase;/动态存储分配新基址指针if (

12、L.length >= L.listsize) /当存储空间已满，增加分配newbase = ( ElemType *)realloc( L.elem, ( L.listsize +LISTINCREMENTsizeof (ElemType); / 存储再分配if (!newbase)/分配失败，返回错误return OVERFLOWL.elem = newbase;/将新的地址指针赋值，注：另定义一个指针变量newbase,而不用L.elem，是因为防止存储分配失败，使原基址被覆盖L.listsize += LISTINCREMENT/ 增加存储容量if ( L.elem0 <=

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

14、lt;= L.elemi)/判断待插入元素是否小于当前位置元素j = i;/保存当前兀素位序p = &( L.elemj + 1);/指向满足上条件元素的后一个位置for (q = &(L.elem L.length - 1); q >= p; -q)/将待插入元素位置后的元素依次后移一个位置*(q +1) = *q;*p = e;/插入元素+L .len gth;/表长自增return OK /InsertSequentList Sq * 函数原型：Status BubbleSortList_Sq(SqList &L,Status direction)*函数功能

15、：将已有数据的线性表L进行排序，排序方式由参数direction确定*入口参数：已建立顺序表的引用&L，排序方式direction ，当direction = INC = 1时，为递增，反之则为递减*岀口参数：返回函数结果状态*/Status BubbleSortList_Sq( SqList &L, Status directi on )int i,j;/循环控制变量ElemType temp;临时缓存变量if ( L.length = 0)printf("错误，当前线性表为空，请录入数据：n");return ERROR/线性表错误if ( L.leng

16、th = 1)return OKif ( L.length >= 2)/表中元素至少多于2个for (i = L.length; i > 0; -i)/ 起泡法排序for (j = 0; j < i - 1; j+)if ( L.elemj> L.elemj + 1)/前一个元素大于后一个元素temp = L.elemj;/保持较大的元素if ( directi on )/排序方式为递增L.elemj =L.elemj +1;/交换L.elemj + 1 = temp;elsetemp = L.elem。;/保持较小的元素if (! directi on )/排序方式为

17、递减L.elemj =L.elemj + 1;/交换L.elemj + 1 = temp; |return OK BubbleSortList_Sq运行结果吐址呂称：我性表风做朗90)2015710/2B"Z蠶1«57 G3 S? fl?紹磧駆巻届人的元恚e LW2播入兀素肓的順P袜，571»GJ 少 B? 1B2 132234阴 H17-就地谀着百的師序耒：65323132JL即87 B9&4£44342321141?1©?5请按任意键继塚， 雷建立的线性表的长度：谿:21 34 54 23 43 57 12

18、&9 34 5 54 10 7 2J* 勺排序方式(e.n .W , 17 1U 13142123 M132234 佃 3实 验 总 结实验结果分析：从以上实验运行结果来说，程序可以实现实验要求的基本内容，至于数据输入等操作步骤从上图可以简单、明了的看出。1、此次实验遇到的问题是自己编写的头文件编译器打不开、出现类型重定义、 枚举类型变量错误等，进而报出来很多的错误，经过长时间的仔细检查和搜索知道，需将头文件放到与源文件相同的目录下，而类型重定义则是少打了结构体类型名，至于枚举类型报错，则是因为枚举类型知识不牢靠，使用错误造成的，其他的错误则是函数编写逻辑错误等，但最终还是成功了，所以此次实验对我来说收货的很大的。2、此次程序中需要改进