实验一-线性表及其应用（I）

姓名

学号


实验项目
线性表应（I）
实验容
1．实现线性表序存储结构基操作添加输出显示等辅助函数基础实现续两算法
线性表抽象数类型定义参见教材第19页
序存储结构定义参见教材第22页
2．设线性表存放序表A中中n元素递增序请设计算法x插入线性表适位置保持线性表序性（题集第17页211）
3．试写算法实现序表逆置利原表存储空间线性表（a1a2…an）逆置（an an1…a1）（题集第18页221）

算法设计程序实现：
算法分析
次实验目理解掌握线性表序存储结构法解决两基问题元素插入序序表中保持线性表序性二实现序表逆置首先需插入元素序表序需先输入线性表元素进行排序数排序选择起泡排序算法实现插入元素序表插入元素已排序序表中元素进行较进确定插入位置实验容二逆置仅仅需for循环序表中称位置处元素交换
程序设计流程图示：

核心程序
程序中编写头文件面出头文件说明函数中文件包含部分注释处核心程序：
1函数：
#include stdafxh 标准输入输出函数头文件
#include windowsh cmd窗口设置函数头文件
#include ADTh 数结构中相关结构体类型定义相关数类型定义
#include DataStructure_LinearListh 数结构第二章线性表中相关函数定义声明

int main()
{
system(title 数结构实验 实验名称： 线性表应(I)) 设置cmd窗口标题
system(color F1) 设置控制台窗口背景色前景色
system(date T) 输出前日期
system(TIME T) 输出前时间
int iDIR 控制变量
int LIST_MAX 表长
ElemType data 插入元素
SqList L 定义SqList类型变量
InitList_Sq(L) 初始化序表
printf(※1 请输入需建立线性表长度：)
scanf_s(d &LIST_MAX)
printf(※2 请录入数：)
for (i 0 i {
scanf_s(d &(Lelem[i])) 序表中输入数
++Llength 表长增1
}
printf(※3 请选择数排序方式（0：递减1：递增）：)
scanf_s(d &DIR)
if (DIR)
{
BubbleSortList_Sq(L INCREASE) 序表递增排序
printf(※4 数递增排列：)
}
else
{
BubbleSortList_Sq(L DECREASE) 序表递减排序
printf(※4 数递减排列：)
}
PrintfList_Sq(L) 印输出
printf(＼n※5 请输入插入元素：)
scanf_s(d &data)
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头文件ADTh部分程序：
#ifndef ADT_H_
#define ADT_H_

************************************************************
* 常 量 数 类 型 预 定 义
************************************************************
* 函数结果状态代码 *
#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_LinearListh中部分函数定义：
#include
#include
#include ADTh
*
* 函数原型：Status InverseList_Sq(SqList &L)
* 函数功：线性表L逆置
* 入口参数：结构体类型SqList引
* 出口参数：返回函数结果状态
*
Status InverseList_Sq(SqList &L)
{
int i 循环变量
ElemType temp 时变量
for (i 0 i < (Llength + 1) 2 i++) 根称中心进行数交换
{
temp Lelem[i] 缓存需交换数
Lelem[i] Lelem[Llength 1 i] 称位置数交换
Lelem[Llength 1 i] temp
}
return OK
} InverseList_Sq
*
* 函数原型：Status InsertSequentList_Sq(SqList &L ElemType e)
* 函数功：已排序线性表L中插入元素插入位置数线性表关系确定
* 入口参数：结构体类型SqList引插入数
* 出口参数：返回函数结果状态
*
Status InsertSequentList_Sq(SqList &L ElemType e)
{
int ij 位序变量
ElemType *p *q 插入位置指针
ElemType *newbase 动态存储分配新基址指针
if (Llength > Llistsize) 存储空间已满增加分配
{
newbase (ElemType *)realloc(Lelem (Llistsize + LISTINCREMENT)*sizeof(ElemType)) 存储分配
if (newbase) 分配失败返回错误
return OVERFLOW
Lelem newbase 新址指针赋值注：定义指针变量newbaseLelem防止存储分配失败原基址覆盖
Llistsize + LISTINCREMENT 增加存储容量
}
if (Lelem[0] < Lelem[1]) 判断序表否递增
{
for (i 0 i < Llength i++) 序查找
{
if (e > Lelem[i]) 判断插入元素否前位置元素
j i 保存前元素位序
}
p &(Lelem[j+1]) 指满足条件元素位置
for (q &(Lelem[Llength 1]) q > p q) 插入元素位
*(q + 1) *q
*p e 插入元素
++Llength 表长增
}
else
{
for (i 0 i < Llength i++) 序查找
{
if (e < Lelem[i]) 判断插入元素否前位置元素
j i 保存前元素位序
}
p &(Lelem[j + 1]) 指满足条件元素位置
for (q &(Lelem[Llength 1]) q > p q) 插入元素位置元素次移位置
*(q + 1) *q
*p e 插入元素
++Llength 表长增
}
return OK
} InsertSequentList_Sq
*
* 函数原型：Status BubbleSortList_Sq(SqList &LStatus direction)
* 函数功：已数线性表L进行排序排序方式参数direction确定
* 入口参数：已建立序表引&L排序方式directiondirection INC 1时递增反递减
* 出口参数：返回函数结果状态
*
Status BubbleSortList_Sq(SqList &LStatus direction)
{
int ij 循环控制变量
ElemType temp 时缓存变量
if (Llength 0)
{
printf(错误前线性表空请录入数：＼n)
return ERROR 线性表错误
}
if (Llength 1)
return OK
if (Llength > 2) 表中元素少2
{
for (i Llength i > 0 i) 起泡法排序
{
for (j 0 j < i 1 j++)
{
if (Lelem[j]>Lelem[j + 1]) 前元素元素
{
temp Lelem[j] 保持较元素
if (direction) 排序方式递增
{
Lelem[j] Lelem[j + 1] 交换
Lelem[j + 1] temp
}
}
else
{
temp Lelem[j] 保持较元素
if (direction) 排序方式递减
{
Lelem[j] Lelem[j + 1] 交换
Lelem[j + 1] temp
}
}
}
}
}
return OK
} BubbleSortList_Sq
运行结果

实验结果分析：实验运行结果说程序实现实验求基容数输入等操作步骤图简单明出
实验总结
1次实验遇问题编写头文件编译器开出现类型重定义枚举类型变量错误等进报出错误长时间仔细检查搜索知道需头文件放源文件相目录类型重定义少结构体类型名枚举类型报错枚举类型知识牢错误造成错误函数编写逻辑错误等终成功次实验说收货
2次程序中需改进优化方中困扰次输入数时候需先设置表长输入时候次数输入少数想样初始输入表长条件函数判断否数输入结束开始想for循环输入数数输入结束时候判断否输入’＼n’者输入定义数结束标志例’#’等种判断方法容易出现误判断进出现莫名妙数输入数算法没想出
3通次实验学头文件包含typedef定义类型方法结构体类型指针正确总次实验编程帮助

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档