实验的一线性表及其应用I

《实验的一线性表及其应用I》由会员分享，可在线阅读，更多相关《实验的一线性表及其应用I（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 = &(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.elem