1-1 顺序表操作集

分数 5

作者陈越

单位浙江大学

本题要求实现顺序表的操作集。

函数接口定义：

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

各个操作函数的定义为：

List MakeEmpty()：创建并返回一个空的线性表；

Position Find( List L, ElementType X )：返回线性表中X的位置。若找不到则返回ERROR；

bool Insert( List L, ElementType X, Position P )：将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；否则，如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false；

bool Delete( List L, Position P )：将位置P的元素删除并返回true。若参数P指向非法位置，则打印“POSITION P EMPTY”（其中P是参数值）并返回false。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 5
#define ERROR -1
typedef enum {false, true} bool;
typedef int ElementType;
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List MakeEmpty(); 
Position Find( List L, ElementType X );
bool Insert( List L, ElementType X, Position P );
bool Delete( List L, Position P );

int main()
{
    List L;
    ElementType X;
    Position P;
    int N;

    L = MakeEmpty();
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        if ( Insert(L, X, 0)==false )
            printf(" Insertion Error: %d is not in.\n", X);
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &X);
        P = Find(L, X);
        if ( P == ERROR )
            printf("Finding Error: %d is not in.\n", X);
        else
            printf("%d is at position %d.\n", X, P);
    }
    scanf("%d", &N);
    while ( N-- ) {
        scanf("%d", &P);
        if ( Delete(L, P)==false )
            printf(" Deletion Error.\n");
        if ( Insert(L, 0, P)==false )
            printf(" Insertion Error: 0 is not in.\n");
    }
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

6
1 2 3 4 5 6
3
6 5 1
2
-1 6

输出样例：

FULL Insertion Error: 6 is not in.
Finding Error: 6 is not in.
5 is at position 0.
1 is at position 4.
POSITION -1 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.
POSITION 6 EMPTY Deletion Error.
FULL Insertion Error: 0 is not in.

解析

List MakeEmpty()
{
    List L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
    return L;
}

bool Insert( List L, ElementType X, Position P )
{
    if (L->Last >= MAXSIZE -1)
    {
        printf("FULL");
        return false;
    }
    else if (P < 0 || P > L->Last + 1)
    {
        printf("ILLEGAL POSITION");
        return false;
    }
    else
    {
        for (int i = L->Last; i >= P; i--)
        {
            L->Data[i + 1] = L->Data[i];
        }
        L->Data[P] = X;
        L->Last++;
        return true;
    }
}

Position Find( List L, ElementType X )
{
    int i;
    for (i = 0; i <= L->Last; i++)
    {
        if (L->Data[i] == X)
            return i;
    }
    return ERROR;
}

bool Delete( List L, Position P )
{
    if (P < 0 || P > L->Last)
    {
        printf("POSITION %d EMPTY", P);
        return false;
    }
    else
    {
        for (int i = P; i < L->Last; i++)
        {
            L->Data[i] = L->Data[i + 1];
        }
        L->Last--;
        return true;
    }
}

注意

一、关于 `LNode` 中数组的核心特性

数组的固定大小限制LNode 中的 Data 是大小为 MAXSIZE 的静态数组（题目中 MAXSIZE=5），这意味着顺序表的最大容量固定。
- 满表判断：当 Last == MAXSIZE - 1 时，数组已满，无法插入新元素（Insert 需先检查此条件）。
- 空表判断：当 Last == -1 时，数组中无任何元素（MakeEmpty 初始化为此状态）。
有效元素的范围数组中有效元素仅存储在 0 ~ Last 索引范围内，超出 Last 的位置（如 Last+1 及以后）是未使用的「空闲空间」，而小于 0 的位置是非法的。
- 例如：Last=2 时，有效元素在 Data[0]、Data[1]、Data[2]，Data[3]、Data[4]（若 MAXSIZE=5）为空闲。

二、各操作函数的关键注意事项

1. `MakeEmpty()`：创建空表

必须通过 malloc 为 struct LNode 分配内存，返回的 List 是合法指针（非 NULL）。
初始化 Last = -1 是「空表」的唯一标志，不可设为其他值（如 0 会被误认为有元素）。

2. `Find(List L, ElementType X)`：查找元素

遍历范围严格限定为 0 ~ L->Last：超出 Last 的位置无有效元素，无需遍历（否则可能访问垃圾值）。
若未找到元素，必须返回 ERROR（题目定义为 -1），不可返回其他值（如 -2 会导致判断错误）。

3. `Insert(List L, ElementType X, Position P)`：插入元素

位置合法性判断：合法位置P必须满足0 ≤ P ≤ L->Last + 1。
- 若 P < 0 或 P > L->Last + 1，属于「非法位置」，需打印 ILLEGAL POSITION。
- 例：空表（Last=-1）时，唯一合法插入位置是 P=0（L->Last + 1 = 0）。
元素后移方向：必须从Last开始，依次将元素移到i+1位置for (i = Last; i >= P; i–），避免覆盖未移动的元素。
- 错误示例：若从 P 开始向后移，会导致 Data[P] 被 Data[P+1] 覆盖，丢失原数据。
插入成功后必须更新 Last（Last++），否则表尾标记错误，后续操作会出错。

4. `Delete(List L, Position P)`：删除元素

位置合法性判断：合法位置P必须满足0 ≤ P ≤ L->Last（仅有效元素位置可删除）。
- 若 P < 0 或 P > L->Last，属于「位置为空」，需打印 POSITION P EMPTY（P 为传入的具体值）。
- 错误示例：若判断条件写成 P > L->Last + 1，会误判 P = Last + 1 为合法位置，导致无意义操作。
元素前移方向：必须从 P+1 开始，依次将元素移到 i-1 位置（for (i = P+1; i <= Last; i--)），覆盖待删除元素。
删除成功后必须更新 Last（Last--），否则表尾标记错误，后续查找 / 插入会访问无效位置。

三、其他通用注意事项

错误提示的严格性题目对错误输出格式有明确要求，必须严格匹配：
- 满表：FULL（无多余字符）
- 非法插入位置：ILLEGAL POSITION
- 非法删除位置：POSITION P EMPTY（P 需替换为实际传入的位置值）。
边界条件处理
- 空表（Last=-1）时：插入仅 P=0 合法，删除任何 P 都非法。
- 满表（Last=MAXSIZE-1）时：任何插入都失败，删除后可恢复空闲位置。
顺序表的连续性顺序表依赖数组的连续性存储元素，插入 / 删除时必须通过「移动元素」维持连续性，不可跳过或遗漏元素移动（否则会出现数据断裂或重复）。

掌握以上要点可有效避免常见错误，确保顺序表操作的正确性和健壮性。

1-2 数组元素的区间删除

分数 5

作者 DS课程组

单位浙江大学

给定一个顺序存储的线性表，请设计一个函数删除所有值大于min而且小于max的元素。删除后表中剩余元素保持顺序存储，并且相对位置不能改变。

函数接口定义：

int Delete( int A[], int L, int minA, int maxA );

其中A是整型数组，存储原始线性表的元素；L是表长，即A中元素的个数；minA和maxA分别为待删除元素的值域的下、上界。函数Delete应将A中所有值大于minA而且小于maxA的元素删除，同时保证表中剩余元素保持顺序存储，并且相对位置不变，最后返回删除后的表长。

裁判测试程序样例：

#include <stdio.h>

#define MAXN 20

int Delete( int A[], int L, int minA, int maxA );

int main()
{
    int A[MAXN], L, minA, maxA, i;

    scanf("%d", &L);
    for (i=0; i<L; i++) scanf("%d", &A[i]);
    scanf("%d %d", &minA, &maxA);
    L = Delete(A, L, minA, maxA);
    for (i=0; i<L; i++) printf("%d ", A[i]);
    printf("\n");

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

10
4 -8 2 12 1 5 9 3 3 10
0 4

输出样例：

4 -8 12 5 9 10

解析

int Delete( int A[], int L, int minA, int maxA )
{
    int i, j;
    for (i = 0, j = 0; i < L; i++)
    {
        if (A[i] <= minA || A[i] >= maxA)
        {
            A[j] = A[i];
            j++;
        }
    }
    return j;
}

注意

一、核心需求理解：明确 “删除 / 保留” 的边界定义

这是最容易出错的基础环节，必须严格区分 “删除范围” 与 “保留范围”：

删除范围

：题目要求删除的是minA < A[i] < maxA的元素（仅 “严格大于下界且严格小于上界” 的元素）。
- 例：若minA=0、maxA=4，则1、2、3需删除，0、4需保留（因不满足 “严格大于且严格小于”）。
保留范围

：与删除范围完全对立，即A[i] ≤ minA 或 A[i] ≥ maxA的元素。
- 常见错误：遗漏 “等于 minA 或等于 maxA” 的情况（如写成A[i] < minA || A[i] > maxA），导致A[i] == minA或A[i] == maxA的元素被误删，与题目要求不符。

二、实现方法：双指针法的正确使用（确保顺序与效率）

推荐使用 “双指针遍历” 实现，这是兼顾 “顺序不变” 与 “高效” 的核心方法，需注意以下细节：

双指针的职责划分：
- 指针i：遍历原始数组（范围0 ~ L-1），负责 “筛选元素”（判断当前元素是否需保留）。
- 指针j：记录 “保留元素的存储位置”（初始为 0），仅当A[i]需保留时，才将A[i]赋值给A[j]，并让j自增 1。
- 本质：j的最终值就是 “删除后的表长”（因每保留一个元素，j就计数一次）。
避免 “覆盖未遍历元素”：

由于i始终领先或等于j（i从 0 开始，j仅在保留元素时移动），赋值A[j] = A[i]时，不会覆盖i尚未遍历的元素（未遍历元素在i右侧，j在i左侧或同位置），确保原始数据不丢失。
禁止 “暴力删除后移位”：若先找到需删除元素，再通过循环将后续元素前移（如for(k=i;k<L-1;k++) A[k]=A[k+1]），会导致时间复杂度变为O(n²)（极端情况如全需删除，需多次移位），效率远低于双指针O(n)，不推荐使用。

三、边界情况处理：覆盖特殊输入场景

需考虑 “删除范围不存在”“全保留”“全删除” 等极端情况，确保代码无漏洞：

minA ≥ maxA：删除范围无效

此时 “minA < A[i] < maxA” 的区间不存在（如minA=5、maxA=3），所有元素均需保留。双指针会将所有A[i]

赋值给A[j]，j最终等于L，返回原表长，无需额外处理。
全表元素需保留（如minA=-10、maxA=0，数组元素均为-20、-15）双指针遍历后，j等于L，返回L，数组内容不变，符合 “相对位置不变” 要求。
全表元素需删除（如minA=0、maxA=10，数组元素均为1、2、3）双指针遍历后，j=0，返回0，此时裁判程序会打印 “空内容”（符合预期）。

四、返回值与数组状态：确保与裁判程序适配

返回值的意义：函数返回的j必须是 “保留元素的个数”（即删除后的表长）。裁判程序会根据此返回值，从A[0]

开始打印j个元素，若返回值错误（如多算 / 少算），会导致打印 “垃圾值” 或 “漏打元素”。
- 例：若实际保留 6 个元素，却返回 5，裁判程序仅打印前 5 个，丢失最后 1 个；若返回 7，会打印前 6 个有效元素 + 1 个未初始化的垃圾值。
无需修改原数组长度参数L：输入参数L是 “原始表长”，仅用于遍历原始数组（i < L），修改L无意义（裁判程序通过函数返回值获取新表长，不依赖传入的L）。

五、代码规范：避免语法与逻辑冗余

变量初始化：i和j需初始化为 0（双指针起始位置均为数组首元素），若未初始化（如int i,j;后直接使用），可能因初始值随机导致遍历异常。
无额外空间开销：

题目要求 “顺序存储且相对位置不变”，双指针法直接在原数组上覆盖存储保留元素，无需额外开辟数组（若使用额外数组，虽逻辑正确，但不符合 “原地操作” 的隐含要求，且浪费空间）。
避免条件冗余：

保留元素的条件仅需
A[i] ≤ minA || A[i] ≥ maxA
，无需拆分复杂逻辑（如
!(A[i] > minA && A[i] < maxA)
，虽等价，但可读性略差，推荐直接写保留条件）

1-1 顺序表操作集

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

解析

注意

一、关于 LNode 中数组的核心特性

二、各操作函数的关键注意事项

1. MakeEmpty()：创建空表

2. Find(List L, ElementType X)：查找元素

3. Insert(List L, ElementType X, Position P)：插入元素

4. Delete(List L, Position P)：删除元素

三、其他通用注意事项

1-2 数组元素的区间删除

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

解析

注意

一、核心需求理解：明确 “删除 / 保留” 的边界定义

二、实现方法：双指针法的正确使用（确保顺序与效率）

三、边界情况处理：覆盖特殊输入场景

四、返回值与数组状态：确保与裁判程序适配

五、代码规范：避免语法与逻辑冗余

一、关于 `LNode` 中数组的核心特性

1. `MakeEmpty()`：创建空表

2. `Find(List L, ElementType X)`：查找元素

3. `Insert(List L, ElementType X, Position P)`：插入元素

4. `Delete(List L, Position P)`：删除元素