《实验的一线性表及其应用I.doc》由会员分享，可在线阅读，更多相关《实验的一线性表及其应用I.doc（7页珍藏版）》请在三一办公上搜索。
1、某某学号实验项目线性表与其应用I实验内容1实现线性表的顺序存储结构和主要的根本操作，并添加输出显示等辅助函数，在此根底上实现后续两个算法。线性表的抽象数据类型定义参见教材第19页。顺序存储结构的定义参见教材第22页。2设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将x插入到线性表的适当位置，以保持线性表的有序性。题集第17页2.113试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表a1,a2,an逆置为an, an-1,a1。题集第18页2.21算法设计与程序实现：算法分析本次实验的目的是理解和掌握线性表顺序存储结构的用法，要解决两个根本问题一是将元素插入到
2、有序的顺序表中，并保持线性表的有序性；二是实现顺序表的就地逆置。首先需插入元素的顺序表是有序的，故需先将输入的线性表元素进展排序，至于数据排序，我选择的是起泡排序算法，而实现插入元素到顺序表，如此是将待插入的元素与已排序的顺序表中的每个元素进展比拟进而确定插入位置；实验内容二的就地逆置如此仅仅只需用一个for循环将顺序表中对称位置处的元素交换即可。程序设计流程图如下所示：核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明如此在主函数中文件包含局部的注释处，核心程序如下：1.主函数如下：#includestdafx.h/标准输入输出函数头文件#includewindows.h/
3、cmd窗口设置函数头文件#includeADT.h/数据结构中相关结构体类型定义与相关数据类型定义#includeDataStructure_LinearList.h/数据结构第二章线性表中相关函数的定义与声明int main()system(title 数据结构实验实验名称：线性表与其应用(I); /设置cmd窗口标题system(color F1); /设置控制台窗口的背景色和前景色system(date /T); /输出当前的日期system(TIME /T); /输出当前的时间int i,DIR; /控制变量int LIST_MAX; /表长ElemType data; /待插入元素S
4、qList L; /定义SqList类型变量InitList_Sq(L); /初始化顺序表printf(1. 请输入所需建立的线性表的长度：);scanf_s(%d, &LIST_MAX);printf(2. 请录入数据：);for (i = 0; iLIST_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.
5、数据递增排列：);elseBubbleSortList_Sq(L, DECREASE); /将顺序表递减排序printf(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); /打印
6、输出printf(nn);return 0;2.头文件ADT.h的局部程序如下：#ifndef ADT_H_#defineADT_H_/* 常量和数据类型预定义*/* -函数结果状态代码- */#defineTRUE 1#defineFALSE 0#defineOK 1#defineERROR 0#defineINFEASIBLE -1#defineOVERFLOW -2/* -排序方式状态- */#defineINCREASE 1 /递增#defineDECREASE 0 /递减/* -数据类型预定义- */typedefintStatus; /函数结果状态类型typedefint_bool
7、; /bool状态类型/* 数据结构类型定义*/*线性表*/* -顺序表数据类型定义- */typedefintElemType; /顺序表中元素的数据类型/* -线性表的动态存储分配初始常量预定义- */#defineLIST_INIT_SIZE 100 /线性表存储空间的初始分配量#defineLISTINCREMENT 10 /线性表存储空间的分配增量/* -顺序存储结构类型定义- */typedefstructElemType * elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量SqList; /顺序表类型3.头文件DataS
8、tructure_LinearList.h中局部函数定义如下：#include#include#includeADT.h/* 函数原型：Status InverseList_Sq(SqList &L)* 函数功能：将线性表L就地逆置* 入口参数：结构体类型SqList的引用* 出口参数：返回函数结果状态*/Status InverseList_Sq(SqList &L) int i; /循环变量ElemType temp; /临时变量for (i = 0; i = L.listsize) /当存储空间已满，增加分配newbase = (ElemType *)realloc(L.elem, (L
9、.listsize + LISTINCREMENT)*sizeof(ElemType); /存储再分配if (!newbase) /分配失败，返回错误returnOVERFLOW;L.elem = newbase; /将新的地址指针赋值，注：另定义一个指针变量newbase,而不用L.elem，是因为防止存储分配失败，使原基址被覆盖L.listsize += LISTINCREMENT; /增加存储容量if (L.elem0 = L.elem1) /判断此顺序表是否为递增for (i = 0; i = L.elemi) /判断待插入元素是否大于当前位置元素j = i; /保存当前元素位序p =
10、 &(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 = p; -q) /将待插入元素位置后的元素依次后移一个位置*(q + 1) = *q;*p = e; /插入元素+L.length; /表长自增returnOK; /InsertSequentList_Sq/* 函数原型：Status BubbleSortLis
11、t_Sq(SqList &L,Status direction)* 函数功能：将已有数据的线性表L进展排序，排序方式由参数direction确定* 入口参数：已建立顺序表的引用&L，排序方式direction，当direction = INC = 1时，为递增，反之如此为递减* 出口参数：返回函数结果状态*/Status BubbleSortList_Sq(SqList &L,Statusdirection)int i,j; /循环控制变量ElemType temp; /临时缓存变量if (L.length = 0)printf(错误,当前线性表为空,请录入数据：n);returnERROR;
12、 /线性表错误if (L.length = 1)returnOK;if (L.length = 2) /表中元素至少多于2个for (i = L.length; i 0; -i) /起泡法排序for (j = 0; j 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
13、; /交换L.elemj + 1 = temp;returnOK; /BubbleSortList_Sq运行结果实验结果分析：从以上实验运行结果来说，程序可以实现实验要求的根本内容，至于数据输入等操作步骤从上图可以简单、明了的看出。实验总结1、此次实验遇到的问题是自己编写的头文件编译器打不开、出现类型重定义、枚举类型变量错误等，进而报出来很多的错误，经过长时间的仔细检查和搜索知道，需将头文件放到与源文件一样的下，而类型重定义如此是少打了结构体类型名，至于枚举类型报错，如此是因为枚举类型知识不牢靠，使用错误造成的，其他的错误如此是函数编写逻辑错误等，但最终还是成功了，所以此次实验对我来说收货的很大的。2、此次程序中需要改良和优化的地方还很多，其中困扰我的是每次输入数据的时候都需要先设置表长，但输入的时候每次都要数自己输入了多少个数，所以我就想怎样在不初始输入表长的条件下，由函数自己判断是否数据输入完毕，开始我想到的是在for循环下输入数据，当数据输入完毕的时候判断是否输入n或者输入一些自己定义的数据完毕标志，例如#等,但是这种判断方法很容易出现误判断，进而出现一些莫名其妙的数据，所以这个输入数据的算法还没有想出了。3、通过此次实验我学的的主要就是头文件的包含、typedef定义类型的方法、结构体类型的使用和指针的正确使用，总之这次实验对我的编程有很大的帮助。
