2023-2024 (2) 数据结构题目集

PTA - 2023-2024（2）数据结构题目集

6-01 顺序表操作集

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

题目描述

函数接口定义：

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。

输入样例：

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) * MAXSIZE);
    L->Last = -1;       // -1 代表无效内容, 因为初始是空表
    return L;
}

Position Find( List L, ElementType X ){
    int i = 0;
    
    for (i = 0; i < MAXSIZE; i ++ ) {
        if (X == L->Data[i])
            return i;   // i 和 i ++ 都一样
    }
    
    return ERROR;
}

bool Insert( List L, ElementType X, Position P ) {
    if (L->Last == MAXSIZE - 1) {   // 已满
        printf("FULL");
        return false;
    }
    
    if (P > L->Last + 1 || P < 0) { // 插入可以插在尾部, 但不能插在 L->Last + 1
        printf("ILLEGAL POSITION");
        return false;
    }
    
    for (int i = L->Last; i >= P; i -- ) {  // 以尾开始, 到 P 结束
        L->Data[i + 1] = L->Data[i];
    }
    L->Data[P] = X;
    L->Last ++ ;    // 插入之后 元素数量 ++
    
    return true;
}

bool Delete( List L, Position P ) {
    if (P > L->Last || P < 0) {     // 删除不能 P > L->Last + 1
        printf("POSITION %d EMPTY", P);
        return false;
    }
    
    for (int i = P; i <= L->Last; i++)  {   // 删除从 P 开始, 到尾部结束
        L->Data[i] = L->Data[i + 1];
    }
    L->Last -- ;    // 删除 --
    
    return true;
}

6-02 线性表元素的区间删除

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

题目描述

函数接口定义：

List Delete( List L, ElementType minD, ElementType maxD );

其中List结构定义如下：

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

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较；minD和maxD分别为待删除元素的值域的下、上界。函数Delete应将Data[]中所有值大于minD而且小于maxD的元素删除，同时保证表中剩余元素保持顺序存储，并且相对位置不变，最后返回删除后的表。

输入样例：

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

输出样例：

4 -8 12 5 9 10

大致思路:

先标记满足要求的元素，再重新整理数组，将不满足要求的元素保留在原数组中，最后更新 Last 的值来反映删除元素后的数组长度。

// 要求: 满足的删除, 不满足的保留
List Delete( List L, ElementType minD, ElementType maxD ){
    ElementType s[MAXSIZE] = {0};    // 保存元素标记的桶
    int j = 0; // j 用于记录新数组的下标

    for (int i = 0; i <= L->Last; i++) {
        if (L->Data[i] > minD && L->Data[i] < maxD) {
            s[i] = 1;    // 符合要求标记为 1
        }
    }

    for (int i = 0; i <= L->Last; i++) {
        if (!s[i]) {    // 不满足要求的元素保留
            L->Data[j] = L->Data[i];
            j++;
        }
    }

    L->Last = j - 1; // 更新 L->Last 的值
    return L;
}

6-03 递增的整数序列链表的插入

本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。

题目描述

函数接口定义：

List Insert( List L, ElementType X );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Insert要将X插入L，并保持该序列的有序性，返回插入后的链表头指针。

输入样例：

5
1 2 4 5 6
3

输出样例：

1 2 3 4 5 6

大致思路:

• 因为是严格递增的序列, 所以省了很多事, 不需要找 pos 位置什么的了.
• 依然要判断 p 是否为空, 即 p->Next != NULL , 可简化为 while (p->Next)

List Insert( List L, ElementType X ){
    List p = L;     // 工作指针 p 指向头结点
    while (p->Next && p->Next->Data < X)
        p = p->Next;    // 找到第一个大于(等于)X的结点的前一个结点
    
    List node = (List)malloc(sizeof(struct Node)); 
    node->Data = X;
    node->Next = p->Next;
    p->Next = node;

    return L;
}