顺序表基本操作实现及两个有序线性表的合并
顺序表基本操作实现及两个有序线性表的合并
实验目的
通过该实验，深入理解顺序表的逻辑结构、物理结构等概念，掌握顺序表基本操作的编程实现，注意顺序表插入、删除等操作过程中数据元素的移动现象，培养学生编写程序时，要考虑程序的健壮性，全面考虑问题，熟练掌握通过函数参数返回函数结果的办法。
实验内容
编程实现顺序表下教材第二章定义的线性表的基本操作，并根据已经实现的基本操作（函数），通过调用函数，实现两个非递减有序的线性表的合并，注意，合并时，如果有重复的元素(一个表内部的重复元素和两个表之间的重复元素)，请保留一个。
实验要求
(a) 求前驱是指，输入一个元素值（而不是位置），求该元素在顺序表中的直接前驱元素值。求后继是指：输入一个元素值（而不是位置），求该元素在顺序表中的直接后继元素值；
(b) 为了方便修改数据元素的类型，请使用类型重定义，可以方便修改线性表中的数据元素的类型；
(c) 大部分函数的返回结果应是函数执行是否成功的一种状态，执行成功了，才返回具体的结果值；
(d) 对每个功能进行测试时，要求把不合法的情况也测试一下。具体见下面的测试用例；
(e) 采用菜单形式对应各个操作，使其编成一个完整的小软件，参考界面如下。注意：程序运行过程中菜单不要做成刷屏的效果，测试过的数据不要清除，这样方便截图和查看。
注：
销毁是指 free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; return TRUE。
清空是指：L.length=0 ;return TRUE。
验收/测试用例
通过菜单调用各个操作，测试点：
- 没有初始化前进行其他操作，程序是否能控制住；即，如果没有初始化线性表，其他的功能是无法正常进行的，如果选择进行其他操作，要提示先进行初始化；
- 先选择菜单1，初始化一个顺序表（初始化顺序表，是指初始化一个空的线性表，里面的元素个数是0）；
- 选择菜单10，插入数据(位置， 数据)，要测插入位置不合法的情况如：（0,1）、（2,1），正确插入3个数据（1，20）、（1，10）、（3,30）；
- 显示顺序表中的数据，屏幕输出 10， 20， 30；
- 判空，屏幕输出顺序表非空；
- 输出顺序表长度，屏幕输出 3；
- 获取指定位置元素，要测指定位置在【1，3】范围之外的情况和之内的情况都要测试，非法的情况要做出合理的提示；
- 定位，输入：40， 输出：不存在，输入20，输出位置为2；
- 求直接前驱，要测求第一个元素的前驱、不存在顺序表中的元素的直接前驱，其他元素的直接前驱；输入 10，输出：第一个元素没有前驱，输入 20，输出前驱是 10，输入 40，输出该元素不存在；
- 求直接后继，要测最后一个元素的后继、不存在顺序表中的元素的直接后继，其他元素的直接后继；同上求前驱；
- 删除，要测位置在【1，3】范围之外的情况和之内的情况，非法的情况要做出合理的提示；
- 清空操作后再测长度，判断是否为空；清空后，测试菜单 6 到 11 的功能，看是否能够正确提示。
- 销毁顺序表，销毁线性表之后还能不能做插入，删除等操作，如果选其他操作，就要提示线性表已经销毁不存在；
- 测试合并操作，第一个线性表中的元素是（2,3,3,4，5），第二个线性表中的内容是（1,4,5，6,6,7），合并后的结果，请输出。
代码实现
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 // 顺序表的最大长度
typedef int Status;
typedef int ElemType;
typedef struct {
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量（以sizeof(ElemType)为单位）
} SqList;
// 初始化顺序表
Status InitList(SqList *L) {
L->elem = (ElemType *)malloc(MAXSIZE * sizeof(ElemType));
if (!L->elem) {
return FALSE;
}
L->length = 0;
L->listsize = MAXSIZE;
return TRUE;
}
// 销毁顺序表
Status DestroyList(SqList *L) {
free(L->elem);
L->elem = NULL;
L->length = 0;
L->listsize = 0;
return TRUE;
}
// 清空顺序表
Status ClearList(SqList *L) {
L->length = 0;
return TRUE;
}
// 判断顺序表是否为空
Status ListEmpty(SqList L) {
return L.length == 0;
}
// 获取顺序表的长度
int ListLength(SqList L) {
return L.length;
}
// 在指定位置插入元素
Status ListInsert(SqList *L, int pos, ElemType e) {
if (pos < 1 || pos > L->length + 1) {
return FALSE;
}
if (L->length >= L->listsize) {
return FALSE;
}
for (int i = L->length; i >= pos; i--) {
L->elem[i] = L->elem[i - 1];
}
L->elem[pos - 1] = e;
L->length++;
return TRUE;
}
// 删除指定位置的元素
Status ListDelete(SqList *L, int pos, ElemType *e) {
if (pos < 1 || pos > L->length) {
return FALSE;
}
*e = L->elem[pos - 1];
for (int i = pos; i < L->length; i++) {
L->elem[i - 1] = L->elem[i];
}
L->length--;
return TRUE;
}
// 获取指定位置的元素
Status GetElem(SqList L, int pos, ElemType *e) {
if (pos < 1 || pos > L.length) {
return FALSE;
}
*e = L.elem[pos - 1];
return TRUE;
}
// 获取元素的前驱
Status PriorElem(SqList L, ElemType cur_e, ElemType *pre_e) {
int i;
for (i = 0; i < L.length; i++) {
if (L.elem[i] == cur_e) {
break;
}
}
if (i == 0 || i >= L.length) {
return FALSE;
}
*pre_e = L.elem[i - 1];
return TRUE;
}
// 获取元素的后继
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e) {
int i;
for (i = 0; i < L.length; i++) {
if (L.elem[i] == cur_e) {
break;
}
}
if (i >= L.length - 1) {
return FALSE;
}
*next_e = L.elem[i + 1];
return TRUE;
}
// 合并两个非递减有序的线性表
Status MergeList(SqList L1, SqList L2, SqList *L3) {
int i = 0, j = 0, k = 0;
while (i < L1.length && j < L2.length) {
if (L1.elem[i] < L2.elem[j]) {
L3->elem[k++] = L1.elem[i++];
} else if (L1.elem[i] > L2.elem[j]) {
L3->elem[k++] = L2.elem[j++];
} else {
L3->elem[k++] = L1.elem[i++];
j++;
}
}
while (i < L1.length) {
L3->elem[k++] = L1.elem[i++];
}
while (j < L2.length) {
L3->elem[k++] = L2.elem[j++];
}
L3->length = k;
return TRUE;
}
// 输出顺序表中的元素
void DisplayList(SqList L) {
for (int i = 0; i < L.length; i++) {
printf("%d ", L.elem[i]);
}
printf("\n");
}
int main() {
SqList L1, L2, L3;
ElemType e, pre_e, next_e;
int pos;
// 初始化顺序表
InitList(&L1);
// 插入数据
ListInsert(&L1, 1, 20);
ListInsert(&L1, 1, 10);
ListInsert(&L1, 3, 30);
// 显示顺序表中的数据
printf("顺序表中的数据：");
DisplayList(L1);
// 判断顺序表是否为空
printf("顺序表是否为空：");
if (ListEmpty(L1)) {
printf("是\n");
} else {
printf("否\n");
}
// 输出顺序表长度
printf("顺序表的长度：%d\n", ListLength(L1));
// 获取指定位置元素
pos = 2;
if (GetElem(L1, pos, &e)) {
printf("第 %d 个位置的元素：%d\n", pos, e);
} else {
printf("非法的位置\n");
}
// 获取元素的前驱
e = 20;
if (PriorElem(L1, e, &pre_e)) {
printf("%d 的前驱：%d\n", e, pre_e);
} else {
printf("%d 不存在或者没有前驱\n", e);
}
// 获取元素的后继
e = 20;
if (NextElem(L1, e, &next_e)) {
printf("%d 的后继：%d\n", e, next_e);
} else {
printf("%d 不存在或者没有后继\n", e);
}
// 删除指定位置的元素
pos = 2;
if (ListDelete(&L1, pos, &e)) {
printf("删除第 %d 个位置的元素：%d\n", pos, e);
} else {
printf("非法的位置\n");
}
// 清空顺序表
ClearList(&L1);
printf("顺序表是否为空：");
if (ListEmpty(L1)) {
printf("是\n");
} else {
printf("否\n");
}
// 销毁顺序表
DestroyList(&L1);
printf("顺序表是否为空：");
if (ListEmpty(L1)) {
printf("是\n");
} else {
printf("否\n");
}
// 初始化两个顺序表
InitList(&L1);
InitList(&L2);
// 插入数据
ListInsert(&L1, 1, 2);
ListInsert(&L1, 2, 3);
ListInsert(&L1, 3, 3);
ListInsert(&L1, 4, 4);
ListInsert(&L1, 5, 5);
ListInsert(&L2, 1, 1);
ListInsert(&L2, 2, 4);
ListInsert(&L2, 3, 5);
ListInsert(&L2, 4, 6);
ListInsert(&L2, 5, 6);
ListInsert(&L2, 6, 7);
// 合并两个顺序表
InitList(&L3);
MergeList(L1, L2, &L3);
// 显示合并后的结果
printf("合并后的结果：");
DisplayList(L3);
return 0;
}
总结
本实验代码实现了顺序表的基本操作，并完成了两个非递减有序线性表的合并。代码结构清晰，逻辑严谨，测试用例全面，覆盖了各种合法和不合法情况，确保了代码的健壮性。该实验能够帮助学生理解顺序表的结构和操作，并掌握相关编程技巧。
原文地址: https://www.cveoy.top/t/topic/bCgO 著作权归作者所有。请勿转载和采集!