实验一 线性表及其应用(I)
姓名
学号
}
2. 头文件”ADT.h ”的部分程序如下:
#ifndef ADT_H_
#define ADT_H_
/************************************************************
* 常 量 和 数 据 类 型 预 定 义
************************************************************/
/* ------函数结果状态代码------ */
#define TRUE 1 ElemType data; //待插入元素 SqList L; //定义SqList 类型变量 InitList_Sq(L); //初始化顺序表 printf(" ※1. 请输入所需建立的线性表的长度:" ); scanf_s("%d", &LIST_MAX); printf(" ※2. 请录入数据:" ); for (i = 0; i
#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 &L)
* 函数功能:将线性表L 就地逆置
* 入口参数:结构体类型SqList 的引用
* 出口参数:返回函数结果状态
*/
Status InverseList_Sq(SqList &L )
{
int i; //循环变量 ElemType temp; //临时变量 for (i = 0; i
/*
* 函数原型:Status InsertSequentList_Sq(SqList &L, ElemType e);
* 函数功能:向已经过排序的线性表L 中插入元素,插入位置由数据在线性表的大小关系确定 * 入口参数:结构体类型SqList 的引用,待插入的数据
* 出口参数:返回函数结果状态
*/
Status InsertSequentList_Sq(SqList &L , ElemType e )
{
int i,j; //位序变量 ElemType *p, *q; //插入位置指针 ElemType *newbase; //动态存储分配新基址指针 if (L .length >= L .listsize) //当存储空间已满,增加分配 { } if (L .elem[0] = p; --q) //将待插入元素位 *(q + 1) = *q; *p = e ; //插入元素 ++L .length; //表长自增 if (e >= L .elem[i]) //判断待插入元素是否大于当前位置元素 j = i; //保存当前元素位序 newbase = (ElemType *)realloc(L .elem, (L .listsize + if (!newbase) //分配失败,返回错误 return OVERFLOW ; L .elem = newbase; //将新的地址指针赋值,注:另定义一个指针变量L .listsize += LISTINCREMENT ; //增加存储容量 } return OK ; temp = L .elem[i]; //缓存需要交换的数据 L .elem[i] = L .elem[L .length - 1 - i]; //对称位置数据交换 L .elem[L .length - 1 - i] = temp; } //InverseList_Sq LISTINCREMENT )*sizeof (ElemType )); //存储再分配 newbase, 而不用L.elem ,是因为防止存储分配失败,使原基址被覆盖
/*
* 函数原型:Status BubbleSortList_Sq(SqList &L,Status direction)
* 函数功能:将已有数据的线性表L 进行排序,排序方式由参数direction 确定
* 入口参数:已建立顺序表的引用&L,排序方式direction ,当direction = INC = 1时,为递增,反之则为递减
* 出口参数:返回函数结果状态
*/
Status BubbleSortList_Sq(SqList &L , Status direction )
{
int i,j; //循环控制变量 ElemType temp; //临时缓存变量 if (L .length == 0) { } if (L .length == 1) { 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]; //交换 L .elem[j + 1] = temp; return OK ; if (L .length >= 2) //表中元素至少多于2个 printf(" 错误, 当前线性表为空, 请录入数据:\n"); return ERROR ; //线性表错误 } return OK ; } p = &(L .elem[j + 1]); //指向满足上条件元素的后一个位置 for (q = &(L .elem[L .length - 1]); q >= p; --q) //将待插入元素位置后的元 *(q + 1) = *q; if (e