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

姓名学号实 验 项 目线性表及其应用（I）实 验 内 容1 .实现线性表的顺序存储结构和主要的基本操作，并添加输出显示等辅助函数，在此基础上实现后续两个算法。线性表的抽象数据类型定义参见教材第19页。顺序存储结构的定义参见教材第22页。2 .设线性表存放于顺序表 A中，其中有n个元素，且递增有序，请设一算法，将x插入到线性表的适当位置，以保持线性表的有序性。（题集第17页2.11）3 .试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,an）逆置为（an, an-1,a1）。（题集第18页2.21）算法设计与程序实现：算法分析本次实验的目的是理解和掌握线性表顺序存储结构的用法，要解决两个基本问题一是将元素插入到有序的顺序表中，并保持线性表的有序性； 二是实现顺序表的就地逆置。首先需插入元素的顺序表是有序的，故需先将输入的线性表元素进行排序，至于数据排序，我选择的是起泡排序算法，而实现插入兀素到顺序表，则是将待插入的元素与已排序的顺序表中的每个元素进行比较进而确定插入位置；实验内容二的就地逆置则仅仅只需用一个 for循环将顺序表中对称位置处的元素交换即可。 程序设计流程图如下所示：开始调用 InitList_Sq(SqList &L)函数实现顺序表初始化w输入所需建立的顺序表的表长LIST_MAXT向线性表中录入数据输入选择顺序表的排序方式DIR调用函数BubbleSortList_Sq(SqList&L,Status direction)排序核心程序#include stdafx.h/标准输入输出函数头文件#include windows.h/cmd窗口设置函数头文件调用 PrintfList_Sq(Sqlist&L)函数输出而存表到控制台此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下：1 .主函数如下：#include ADT.h/数据结构中相关结构体类型定义及相关数据类型定义#include DataStructure_LinearList.h /数据结构第二章线性表中相关函数的定义及声明 int main()system( title数据结构实验实验名称：线性表及其应用(I);/设置cm(窗口标题system( color F1 );/设置控制台窗口的背景色和前景色system( date /T);/输出当前的日期system( TIME /T);/输出当前的时间int i,DIR;/控制变量int LIST_MAX;/ElemType data;/待插入元素SqList L;/定义SqList类型变量F InitList_Sq(L);/初始化顺序表printf( X1.请输入所需建立的线性表的长度：）;scanf_s( %d”, &LIST_MAX);printf( X2.请录入数据：);for (i = 0; iLIST_MAX; i+) scanf_s( %d”, &(L.elemi);/ 向顺序表中输入数据+L.length;/ 表长自增 1 printf( 3.请选择数据的排序方式(0:递减，1:递增)：); scanf_s( %d, &DIR); if (DIR)BubbleSortList_Sq(L, INCREASE); / 将顺序表递增排序printf（ X4.数据递增排列：）;elseBubbleSortList_Sq(L, DECREASE); / 将顺序表递减排序 printf( 4.数据递减排列：);PrintfList_Sq(L);/ 打印输出printf( n X5.请输入待插入的元素：)；scanf_s( %d, &data);1InsertSequentList_Sq(L, data);/将数据元素插入到顺序表L中printf（ 6.插入元素后的顺序表：）;PrintfList_Sq(L);/打印输出InverseList Sq(L);/将顺序表就地逆置printf（ n7.就地逆置后的顺序表：);PrintfList_Sq(L);/打印输出printf( nn);return 0;2.头文件ADh”的部分程序如下：#ifndef ADT_H_#define ADT_H/*常量和数据类型预定义*/* 函数结果状态代码 */#define TRUE 1#defineFALSE 0#defineOK1#defineERROR 0#defineINFEASIBLE -1#defineOVERFLOW -2/*排序方式状态-*/ 1#defineINCREASE 1/ 递增#defineDECREASE 0/ 递减/*数据类型预定义-*/typedefint Status ;/函数结果状态类型typedefint _bool;/bool 状态类型/*数据结构类型定义*/*线性表 */*顺序表数据类型定义-*/typedefint ElemType;/顺序表中元素的数据类型/*线性表的动态存储分配初始常量预定义-*/#defineLIST_INIT_SIZE 100/线性表存储空间的初始分配量#defineLISTINCREMENT0/线性表存储空间的分配增量/* -顺序存储结本类型定义-*/typedef structElemType* elem;/存储空间基址intlength;/当前长度intlistsize;/当前分配的存储容量SqList ;/顺序表类型3.头文件DataStructure_LinearList.h”中部分函数定义如下:#include #include #include ADT.h /* 函数原型：Status InverseList Sq(SqList &L)* 函数功能：将线性表L就地逆置* 入口参数：2构体类型SqList的引用* 出口参数：返回函数结果状态* /Status InverseList Sq(SqList &L)int i;/循环变量L.length + 1) / 2; i+)根据对称中心进行数据交换ElemType temp;/ 临时变量for (i = 0; i = 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 = L.elem1)/判断此顺序表是否为递增for (i = 0; i = L.elemi) /判断待插入元素是否大于当前位置元素 j = i;/保存当前元素位序二p = &( L.elemj+1);/指向满足上条件元素的后一个位置for (q = &( L.elem L.length - 1); q = p; -q)/ 将待插入元素位*(q + 1) = *q;*p = e;/插入元素+L.length;/表长自增1elsefor (i = 0; i L.length; i+)/顺序查找| if ( e = 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时，为递 增，反之则为递减* 出口参数：返回函数结果状态* /Status BubbleSortList Sq(SqList &L, Status direction )int i,j;/循环控制变量ElemType temp;/临时缓存变量I if ( L.length = 0) | r printf(错误，当前线性表为空，请录入数据：n); return ERROR/线性表错误if ( L.length = 1)return OKif ( L.length = 2)/表中元素至少多于2个for (i = L.length; i 0; -i)/ 起泡法排序for (j = 0; j L.elemj + 1)/前一个元素大于后一个元素Itemp = L.elemj;/保持较大的元素if ( direction )/排序方式为递增 L.elemj = L.elemj + 1;/ 交换L.elemj + 1 = temp; I|else temp = L.elemj;/保持较小的元素if (! direction )/排序方式为递减L.elemj = L.elemj + 1;/ 交换|L.elemj + 1 = temp; | return OK /BubbleSortList_Sq运行结果实 验 总 结宓数据铝叫实建安卷名称:法性表及司匝用卬-L2 015/10/2 B IM: 06 去;.彼顿人质霄建上的线怪襄的看度：如蛟匕.请录人数有：21 34 54 23 43 57 12 M 34 5 54 10 7 234 653 102 6J 14 89 56强3.靖i用鳌潴间排序方式(e.潴林l诺箱 ，-数/递增弹列.S ? JU 131421 2i 34344? S4 S4 565? G3 ?1322316&3&.清魏诗摘A的元靠t IPG?&*括支元素后的朋诔 57 1W 1214212354344354 S4C657G3898?162132334S3九就地逆署后的即1表：653Z34L32 侬 873?6357564354543434232114121675信按任意健健续 . 实验结果分析：从以上实验运行结果来说，程序可以实现实验要求的基本内容，至于 数据输入等操作步骤从上图可以简单、明了的看出。1、此次实验遇到的问题是自己编写的头文件编译器打不开、出现类型重定义、 枚举类型变量错误等，进而报出来很多的错误，经过长时间的仔细检查和搜索知道， 需将头文件放到与源文件相同的目录下，而类型重定义则是少打了结构体类型名，至于枚举类型报错，则是因为枚举类型知识不牢靠，使用错误造成的，其他的错误则是函数编写逻辑错误等，但最终还是成功了，所以此次实验对我来说收货的很大的。2、此次程序中需要改进和优化的地方还很多，其中困扰我的是每次输入数据的 时候都需要先设置表长， 但输入的时候每次都要数自己输入了多少个数，所以我就想怎样在不初始输入表长的条件下，由函数自己判断是否数据输入结束，开始我想到的是在for循环下输入数据，当数据输入结束的时候判断是否输入n或者输入一些自己定义的数据结束标志，例如 擀，但是这种判断方法很容易出现误判断，进而出现一 些莫名其妙的数据，所以这个输入数据的算法还没有想出了。3、通过此次实验我学的的主要就是头文件的包含、typedef定义类型的方法、结构体类型的使用和指针的正确使用，总之这次实验对我的编程有很大的帮助。