顺序表的基本操作
任务描述
本关任务：要求针对顺序存储的线性表完成四个操作函数，分别实现线性表中数据的插入、删除与查找等功能。
相关知识
为了完成本关任务，你需要掌握：顺序表的基本操作。
顺序表的基本操作
线性表是最基本、最简单、也是最常用的一种数据结构。线性表结构中，数据元素之间通过一对一首尾相接的方式连接起来。具体实现时，线性表可以采用不同的存储策略。下面给出了两种基于顺序存储的线性表实现方案：
图 1：静态数组数组实现
图 2：动态数组数组实现
本任务关卡采用第二种动态数组将线性表存储在一片连续空间里，并通过 elem 以及 length 这两个属性元素。组织成为一个结构：
elem: 给出线性表存储空间的起始地址
length: 保存线性表中最后一个元素所在的位置
为了讨论简化，我们假设每个数据元素是一个整数:
typedef int ElementType;// 数据元素的数据类型
该线性表的结构定义如下：
typedef struct LNode {
ElementType *elem;
int length; /* 保存线性表中数据元素个数 */
} SqList;
程序中使用到的常量：
#define MAXSIZE 100 /* MAXSIZE，指明线性表存储空间最多可存储的数据元素个数 */
#define ERROR 0
对数据元素进行操作处理是一个数据结构的重要组成部分。线性表涉及的主要操作如下：
创建线性表：创建一个最多可存储 MAXSIZE 个数据元素的顺序存储的线性表，并将其初始状态设置为 length=0。如果申请存储空间失败返回 false，否则返回 true；该操作函数具体定义如下，其返回值为 bool 型：
bool MakeEmpty(SqList &L);
释放线性表存储空间：释放 L.elem 所指向的用于存储线性表数据元素的存储空间。该操作函数具体定义如下：
void Free(SqList &L)
判断线性表是否为空：若当前线性表是空表，则返回 true,否则返回 false。该操作函数具体定义如下：
bool IsEmpty(SqList &L)
判断线性表是否已满：若线性表达到最大长度，则返回 true,否则返回 false。该操作函数具体定义如下：
bool IsFull(SqList &L)
在线性表位置 P 插入数据元素 x： 将 X 插入在位置 P(1≤P≤L.legnth) 并返回true。若空间已满，则打印 FULL 并返回 false；如果参数 P 指向非法位置，则打印 ILLEGAL POSITION 并返回 false；该操作函数具体定义如下：
bool Insert( SqList &L, ElementType X, int P )
删除线性表位置 P 处的数据元素： 删除线性表第 P 个数据元素。将位置 P P(1≤P≤L.length) 的元素删除并返回 true。若参数 P 指向非法位置，则打印 POSITION P EMPTY（其中 P 是参数值）并返回 false。该操作函数具体定义如下：
bool Delete( SqList &L, int P )
查找线性表中第一个值为 x 的数据元素的位置： 找到线性表中第一个值为 x 的数据元素所在下标。若找不到则返回 ERROR。该操作函数具体定义如下：
int Find( SqList L, ElementType X )
删除线性表中第一个值为 x 的数据元素： 删除第一个值为 x 的数据元素，返回该数据元素所在位置 [1,L.length]。如果不存在值为 x 的数据元素，则打印“FINDING ERROR X”（其中 X 是参数值）则返回 ERROR。该操作函数具体定义如下：
int DelValue(SqList &L, ElementType X)
打印线性表： 打印整个线性表。该操作函数具体定义如下：
void Print(SqList &L)
编程要求
根据提示，在右侧编辑器代码文件中的 Begin-End 区间内补充代码，实现 step1/Seqlist.h 中的 Insert、Delete、DelValue 和 Find 四个操作函数，以实现线性表中数据的插入、删除与查找等功能。具体要求如下：
Insert 函数：在线性表位置 P 插入数据元素 x， 将X插入在位置 P(1≤P≤L.length+1) 并返回 true。若空间已满，则打印 FULL 并返回false；如果参数 P 指向非法位置，则打印 ILLEGAL POSITION 并返回 false；
Delete 函数：删除线性表位置 P 处的数据元素，删除线性表第 P 个数据元素。将位置 P P(1≤P≤L.length) 的元素删除并返回 true。若参数 P 指向非法位置，则打印 POSITION P EMPTY（其中 P 是参数值）并返回 false。
Find 函数：查找线性表中第一个值为 x 的数据元素的位置，找到线性表中第一个值为 x 的数据元素所在下标。若找不到则返回 ERROR。
DelValue 函数：删除线性表中第一个值为 x 的数据元素： 删除第一个值为 x 的数据元素，返回该数据元素所在位置 [1,L.length]。如果不存在值为 x 的数据元素，则打印“ FINDING ERROR X ”（其中 X 是参数值）则返回 ERROR。
#include <iostream>
using namespace std;
#define MAXSIZE 100
#define ERROR 0
typedef int ElementType;
typedef struct LNode {
ElementType *elem;
int length; /* 保存线性表中数据元素个数 */
} SqList;
/*顺序表的初始化*/
bool MakeEmpty(SqList &L);
/*释放线性表存储空间：*/
void Free(SqList &L) ;
/* 判断线性表是否为空 */
bool IsEmpty(SqList &L);
/* 判断线性表是否已满*/
bool IsFull(SqList &L);
/* 打印线性表*/
void Print(SqList &L);
/*返回线性表中X第一次出现的位置*/
int Find( SqList L, ElementType X );
/*将X插入在位置P(1≤P≤L.length+1)*/
bool Insert( SqList &L, ElementType X, int P );
/* 删除线性表中第一个值为`x`的数据元素 */
int DeleteValue(SqList &L, ElementType X);
/*将位置P(1≤P≤L.length的元素删除*/
bool Delete( SqList &L, int P ) ;
/*返回线性表中X第一次出现的位置，从1开始。若找不到则返回ERROR；*/
int Find( SqList L, ElementType X ) {
// 请在这里补充代码，完成本关任务
/********** Begin *********/
for (int i = 0; i < L.length; i++) {
if (L.elem[i] == X) {
return i + 1; // 数组索引从0开始，位置从1开始
}
}
return ERROR;
/********** End **********/
}
/*将X插入在位置P((1≤P≤L.length+1))并返回true。若空间已满，则打印“FULL”并返回false；
如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；*/
bool Insert( SqList &L, ElementType X, int P ) {
// 请在这里补充代码，完成本关任务
/********** Begin *********/
if (IsFull(L)) {
cout << "FULL" ;
return false;
}
if (P < 1 || P > L.length + 1) {
cout << "ILLEGAL POSITION" ;
return false;
}
for (int i = L.length; i >= P; i--) {
L.elem[i] = L.elem[i - 1];
}
L.elem[P - 1] = X;
L.length++;
return true;
/********** End **********/
}
/*将位置P((1≤P≤L.length)的元素删除并返回true。若顺序表是空的，则打印“LIST EMPTY” ，并返回false；
若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。*/
bool Delete( SqList &L, int P ) {
// 请在这里补充代码，完成本关任务
/********** Begin *********/
if (IsEmpty(L)) {
cout << "LIST EMPTY" ;
return false;
}
if (P < 1 || P > L.length) {
cout << "POSITION " << P << " EMPTY" ;
return false;
}
for (int i = P; i < L.length; i++) {
L.elem[i - 1] = L.elem[i];
}
L.length--;
return true;
/********** End **********/
}
/* 删除线性表中第一个值为`x`的数据元素： 删除第一个值为`x`的数据元素，
返回该数据元素所在位置`[1,L.length]`。如果不存在值为`x`的数据元素，则打印“FINDING ERROR X”（其中X是参数值）则返回`ERROR`。*/
int DeleteValue(SqList &L, ElementType X){
// 请在这里补充代码，完成本关任务
/********** Begin *********/
int pos = Find(L, X);
if (pos == ERROR) {
cout << "FINDING ERROR " << X;
return ERROR;
}
Delete(L, pos);
return pos;
/********** End **********/
}
两个有序顺序表的归并（不含重复元素）
任务描述
本关任务：已知顺序表 L1，L2 中数据由小到大有序，请用尽可能快的方法将 L1 与 L2 中的数据合并到 L3 中，使数据在 L3 中按升序排列。
注意：本关必读中提及的其他操作已经由平台实现，你只要实现本关任务的 Merge 函数即可。
相关知识
为了完成本关任务，你需要掌握：就地归并两个有序顺序表。
就地归并两个有序顺序表
该方案将线性表存储在一片连续空间里，并通过 data 以及 length 这两个属性元素。组织成为一个结构：
data: 给出线性表存储空间的起始地址
length: 保存线性表中数据元素的个数
为了讨论简化，我们假设每个数据元素是一个整数:
typedef int ElementType;// 数据元素的数据类型
该线性表的结构定义如下：
typedef struct LNode {
ElementType *data;
int length; /* 保存线性表中数据元素的个数 */
} SqList;
程序中使用到的常量：
#define MAXSIZE 100 /* MAXSIZE，指明线性表存储空间最多可存储的数据元素个数 */
以下三个函数程序中已经给出，不需要读者完成：
//顺序表初始化
bool MakeEmpty(SqList &L);
//整体建立有序顺序表
void CreateList(SqList &L) ;
//输出顺序表
void Print(SqList L) ;
本关涉及的代码文件 merge.h 中作函数的代码框架如下：
/* 实现将从小到大有序顺序表L1和L2中的数据合并到L3中，使数据在L3中按升序排列，
并不含重复元素。(其中L1和L2是严格地递增）*/
void Merge(SqList L1,SqList L2,SqList &L3) {
// 请在这里补充代码，完成本关任务
/********** Begin *********/
/********** End **********/
}
注意：
已有的两个有序表顺序存储方式进行存储；
归并以后不允许表中有重复元素；
异地归并。
编程要求
根据提示，在右侧编辑器代码文件中的 Begin-End 区间内补充代码，完成函数：
void Merge(SqList L1,SqList L2,SqList &L3)
Merge 函数：实现将从小到大有序顺序表 L1 和 L2 中的数据合并到 L3 中，使数据在 L3 中按升序排列，并不含重复元素。(其中 L1 和 L2 是严格地递增）。
#include <iostream>
using namespace std;
#define MAXSIZE 50000
typedef int ElementType;
typedef struct LNode {
ElementType *data;
int length; /* 保存线性表中数据元素的个数 */
} SqList;
/* 实现将从小到大有序顺序表L1和L2中的数据合并到L3中，使数据在L3中按升序排列，
并不含重复元素。(其中L1和L2是严格地递增）*/
void Merge(SqList L1,SqList L2,SqList &L3) {
// 请在这里补充代码，完成本关任务
/********** Begin *********/
// 初始化L3
L3.data = new ElementType[MAXSIZE];
L3.length = 0;
int i = 0, j = 0, k = 0; // i, j分别是L1和L2的索引，k是L3的索引
// 遍历L1和L2，将较小的元素添加到L3中
while (i < L1.length && j < L2.length) {
if (L1.data[i] < L2.data[j]) {
if (k == 0 || L1.data[i] != L3.data[k - 1]) { // 检查是否重复
L3.data[k++] = L1.data[i];
}
i++;
} else if (L1.data[i] > L2.data[j]) {
if (k == 0 || L2.data[j] != L3.data[k - 1]) { // 检查是否重复
L3.data[k++] = L2.data[j];
}
j++;
} else { // L1.data[i] == L2.data[j]
if (k == 0 || L1.data[i] != L3.data[k - 1]) { // 检查是否重复
L3.data[k++] = L1.data[i];
}
i++;
j++;
}
}
// 将L1剩余的元素添加到L3中
while (i < L1.length) {
if (k == 0 || L1.data[i] != L3.data[k - 1]) { // 检查是否重复
L3.data[k++] = L1.data[i];
}
i++;
}
// 将L2剩余的元素添加到L3中
while (j < L2.length) {
if (k == 0 || L2.data[j] != L3.data[k - 1]) { // 检查是否重复
L3.data[k++] = L2.data[j];
}
j++;
}
// 设置L3的长度
L3.length = k;
/********** End **********/
}