内容发布更新时间 : 2024/5/20 7:12:56星期一 下面是文章的全部内容请认真阅读。
电子信息工程学院2013级《数据结构》实验报告
姓名
学号
实验线性表及其应用（I） 项目 实验内容 1．实现线性表的顺序存储结构和主要的基本操作，并添加输出显示等辅助函数，在此基础上实现后续两个算法。 线性表的抽象数据类型定义参见教材第19页。 顺序存储结构的定义参见教材第22页。 2．设线性表存放于顺序表A中，其中有n个元素，且递增有序，请设计一算法，将x插入到线性表的适当位置，以保持线性表的有序性。（题集第17页2.11） 3．试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an, an-1,…,a1）。（题集第18页2.21） 算法设计与程序实现： 算法分析 本次实验的目的是理解和掌握线性表顺序存储结构的用法，要解决两个基本问题一是将元素插入到有序的顺序表中，并保持线性表的有序性；二是实现顺序表的就地逆置。首先需插入元素的顺序表是有序的，故需先将输入的线性表元素进行排序，至于数据排序，我选择的是起泡排序算法，而实现插入元素到顺序表，则是将待插入的元素与已排序的顺序表中的每个元素进行比较进而确定插入位置；实验内容二的就地逆置则仅仅只需用一个for循环将顺序表中对称位置处的元素交换即可。 程序设计流程图如下所示： 电子信息工程学院2013级《数据结构》实验报告 开始调用InitList_Sq(SqList &L)函数实现顺序表初始化输入需插入的元素data输入所需建立的顺序表的表长LIST_MAX调用有序插入函数InsertSequentList_Sq(SqList &L, ElemType e)插入数据data向线性表中录入数据调用PrintfList_Sq(Sqlist &L)函数输出顺序表到控制台输入选择顺序表的排序方式DIR调用InverseLIst_Sq(SqList &L)函数对顺序表进行就地逆置调用函数BubbleSortList_Sq(SqList &L,Status direction)排序调用PrintfList_Sq(Sqlist &L)函数输出顺序表到控制台调用PrintfList_Sq(Sqlist &L)函数输出顺序表到控制台结束 核心程序 此程序中用到的自己编写的头文件以在下面给出，而头文件的说明则在主函数中文件包含部分的注释处，核心程序如下： 1.主函数如下： #include \ //标准输入输出函数头文件 #include \ //cmd窗口设置函数头文件 #include \ //数据结构中相关结构体类型定义及相关数据类型定义 #include \ //数据结构第二章线性表中相关函数的定义及声明 int main() { system(\数据结构实验 实验名称： 线性表及其应用(I)\); system(\); //设置控制台窗口的背景色和前景色 system(\); //输出当前的日期 system(\); //输出当前的时间 int i,DIR; //控制变量 int LIST_MAX; //表长 //设置cmd窗口标题 电子信息工程学院2013级《数据结构》实验报告
}
2.头文件”ADT.h”的部分程序如下： #ifndef ADT_H_ #define ADT_H_
/************************************************************ * 常 量 和 数 据 类 型 预 定 义
************************************************************/ /* ------函数结果状态代码------ */ #define TRUE 1
ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf(\※1. 请输入所需建立的线性表的长度：\); scanf_s(\, &LIST_MAX); printf(\※2. 请录入数据：\); for (i = 0; i printf(\※3. 请选择数据的排序方式（0：递减，1：递增）：\); scanf_s(\, &DIR); if (DIR) { } else { } PrintfList_Sq(L); //打印输出 printf(\※5. 请输入待插入的元素：\); scanf_s(\, &data); InsertSequentList_Sq(L, data); //将数据元素插入到顺序表L中 printf(\※6. 插入元素后的顺序表：\); PrintfList_Sq(L); //打印输出 InverseList_Sq(L); //将顺序表就地逆置 printf(\※7. 就地逆置后的顺序表：\); PrintfList_Sq(L); //打印输出 printf(\); return 0; BubbleSortList_Sq(L, DECREASE); //将顺序表递减排序 printf(\※4. 数据递减排列：\); BubbleSortList_Sq(L, INCREASE); //将顺序表递增排序 printf(\※4. 数据递增排列：\); scanf_s(\, &(L.elem[i])); //向顺序表中输入数据 ++L.length; //表长自增1 电子信息工程学院2013级《数据结构》实验报告 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 /* ------排序方式状态------ */ #define INCREASE 1 //递增 #define DECREASE 0 //递减 /* ------数据类型预定义------ */ typedef int Status; //函数结果状态类型 typedef int _bool; //bool状态类型 /************************************************************ * 数 据 结 构 类 型 定 义 ************************************************************/ /************************线 性 表*************************/ /* ------顺序表数据类型定义------ */ typedef int ElemType; //顺序表中元素的数据类型 /* ------线性表的动态存储分配初始常量预定义------ */ #define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 /* ------顺序存储结构类型定义------ */ typedef struct { ElemType * elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 }SqList; //顺序表类型 3.头文件”DataStructure_LinearList.h”中部分函数定义如下： #include * 函数原型：Status InverseList_Sq(SqList &L) * 函数功能：将线性表L就地逆置 * 入口参数：结构体类型SqList的引用 * 出口参数：返回函数结果状态 */ Status InverseList_Sq(SqList &L) { int i; //循环变量 ElemType temp; //临时变量 for (i = 0; i <= (L.length + 1) / 2; i++) //根据对称中心进行数据交换