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

电子信息工程学院电子信息工程学院 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 设置cmd窗口标题 system color F1 设置控制台窗口的背景色和前景色 system date T 输出当前的日期 system TIME T 输出当前的时间 int i DIR 控制变量 电子信息工程学院电子信息工程学院 2013 级级 数据结构数据结构 实验报告实验报告 int LIST MAX 表长 ElemType data 待插入元素 SqList L 定义SqList类型变量 InitList Sq L 初始化顺序表 printf 1 请输入所需建立的线性表的长度 scanf s d printf 2 请录入数据 for i 0 i LIST MAX i scanf s d 向顺序表中输入数据 L length 表长自增1 printf 3 请选择数据的排序方式 0 递减 1 递增 scanf s d if DIR BubbleSortList Sq L INCREASE 将顺序表递增排序 printf 4 数据递增排列 else BubbleSortList Sq L DECREASE 将顺序表递减排序 printf 4 数据递减排列 PrintfList Sq L 打印输出 printf n 5 请输入待插入的元素 scanf s d InsertSequentList Sq L data 将数据元素插入到顺序表L中 printf 6 插入元素后的顺序表 PrintfList Sq L 打印输出 InverseList Sq L 将顺序表就地逆置 printf n 7 就地逆置后的顺序表 PrintfList Sq L 打印输出 printf n n return 0 2 头文件 ADT h 的部分程序如下 ifndef ADT H define ADT H 常 量 和 数 据 类 型 预 定 义 函数结果状态代码 电子信息工程学院电子信息工程学院 2013 级级 数据结构数据结构 实验报告实验报告 define TRUE 1 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 include include ADT h 函数原型 Status InverseList Sq SqList 循环变量 ElemType temp 临时变量 电子信息工程学院电子信息工程学院 2013 级级 数据结构数据结构 实验报告实验报告 for i 0 i L listsize 当存储空间已满 增加分配 newbase ElemType realloc L elem L listsize LISTINCREMENT sizeof ElemType 存储再分配 if newbase 分配失败 返回错误 return OVERFLOW L elem newbase 将新的地址指针赋值 注 另定义一个指针变量 newbase 而不用L elem 是因为防止存储分配失败 使原基址被覆盖 L listsize LISTINCREMENT 增加存储容量 if L elem 0 L elem 1 判断此顺序表是否为递增 for i 0 i L elem i 判断待插入元素是否大于当前位置元素 j i 保存当前元素位序 p 指向满足上条件元素的后一个位置 for q q p q 将待插入元素位 q 1 q p e 插入元素 L length 表长自增 else 电子信息工程学院电子信息工程学院 2013 级级 数据结构数据结构 实验报告实验报告 for 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 循环控制变量 ElemType temp 临时缓存变量 if L length 0 printf 错误 当前线性表为空 请录入数据 n return ERROR 线性表错误 if L length 1 return OK if L length 2 表中元素至少多于2个 for i L length i 0 i 起泡法排序 for j 0 j L elem j 1 前一个元素大于后一个元素 temp L elem j 保持较大的元素 if direction 排序方式为递增 L elem j L elem j 1 交换 电子信息工程学院电子信息工程学院 2013 级级 数据结构数据结构 实验报告实验报告 L elem j 1 temp else temp L elem j 保持较小的元素 if direction 排序方式为递减 L elem j L elem j 1 交换 L elem j 1 temp return OK BubbleSortList Sq 运运 行行 结结 果果 实验结果分析 从以上实验运行结果来说 程序可以实现实验要求的基本内容 至 于数据输入等操作步骤从上图可以简单 明了的看出 实实 验验 总总 结结 1 此次实验遇到的问题是自己编写的头文件编译器打不开 出现类型重定义 枚举类型变量错误等 进而报出来很多的错误 经过长时间的仔细检查和搜索知道 需将头文件放到与源文件相同的目录下 而类型重定义则是少打了结构体类型名 至于枚举类型报错 则是因为枚举类型知识不牢靠 使用错误造成的 其他的错误 则是函数编写逻辑错误等 但最终还是成功了 所以此次实验对我来说收货的很大 的 2 此次程序中需要改进和优化的地方还很多 其中困扰我的是每次输入数据的 时候都需要先设置表长 但输入的时候每次都要数自己输入了多少个数 所以我就 想怎样在不初始输入表长的条件下 由函数自己判断是否数据输入结束 开始我想 到的是在 for 循环下输入数据 当数据输入结束的时候判断是否输入 n 或