南昌大学实验报告
（以下主要内容由学生完成）
- 实验项目名称：
顺序表及其应用
- 实验要求
1、 问题描述；
2、 测试结果的分析与讨论，在测试过程中遇到的主要问题及采取的解决措施。
3、 设计与实现过程中的体会，进一步的改进设想。
4、 实现算法的程序清单，应有足够的注释。
- 实验内容
（1） 实现线性表的顺序存储方法，顺序表建立、插入、删除、查找等基本操作。
（2） 基于顺序表的基本操作，编写算法函数ListReverse(SqList& L)，实现顺序表的就地逆置。
- 算法分析
Status InitList(SqList& L) {// 创建顺序表
L.elem = new ElemType[MAXSIZE];// 为顺序表分配空间
if (!L.elem) {// 未分配成功
exit(OVERFLOW);
}
L.length = 0;
return OK;
}
创建顺序表：为顺序表分配空间，如果未成功返回错误值ERROR
Status GetElem(SqList L, int i, ElemType& e) {// 取值
if (i < 0 || i > L.length) {// 判断是否越界
return ERROR;
}
e = L.elem[i - 1];
return OK;
}
取值：时间复杂度O（n）= 1，找到该数据返回OK，未成功返回错误值ERROR
int LocateElem(SqList L, ElemType e) {// 查找
for (int i = 0; i < L.length; i++) {
if (L.elem[i] == e) {
return i + 1;
}
}
return 0;
}
查找：时间复杂度O（n）= n，当找到时返回该数据的序号，未成功返回错误值ERROR
Status ListInsert(SqList& L, int i, ElemType e) {// 插入
if ((i < 1) || (i > L.length + 1)) {// 判断是否越界
return ERROR;
}
if (L.length == MAXSIZE) {
return ERROR;
}
for (int j = L.length - 1; j > i - 1; j--) {
L.elem[j + 1] = L.elem[j];
}
L.elem[i - 1] = e;
++L.length;
return OK;
}
插入：时间复杂度O（n）= n，从最后一个数据开始向后移，一直移到插入序号+1的位置，插入成功返回正确值OK，未成功返回错误值ERROR
Status ListDelete(SqList& L, int i) {// 删除
if ((i < 1) || (i > L.length + 1)) {// 判断是否越界
return ERROR;
}
for (int j = i; j <= L.length - 1; j++) {
L.elem[j - 1] = L.elem[j];
}
--L.length;// 表长减一
return OK;
}
删除：时间复杂度O（n）= n，从最后一个数据开始向前移，一直移到删除序号+1的位置，删除成功返回正确值OK，未成功返回错误值ERROR
Status ListReverse(SqList& L) {// 逆置
if (L.length == 1) {// 长度为一不用逆置
return OK;
}
if (L.length == 0) {
return ERROR;
}
int i;
int j;
for (i = 0, j = L.length - 1; i < j; i++, j--) {
swap(L.elem[i], L.elem[j]);
}
return OK;
}
Status swap(ElemType* a, ElemType* b) {// 交换
ElemType temp = *a;
*a = *b;
*b = temp;
return OK;
}
逆置：时间复杂度O（n）= n，在逆置前判断长度是否为一，是指不用逆置，直接输出。造swap（）交换函数，将顺序表首尾的数据交换之后，头向后移，尾向前移，逆置成功返回正确值OK，未成功返回错误值ERROR
- 实验步骤
在VS2019中编写程序并运行，输出结果。
- 实验结果
- 思考体会
|
