6-2顺序表操作集

题目描述

实现顺序表的操作集，也就是对顺序表进行增删改查。

回忆一下什么叫做顺序表？是线性表的一种，但是是顺序存储的方式，和数组非常接近。

在处理的时候可以看作数组来处理。需要注意的是这里面所有元素都是"紧挨"着的。

题目地址为:https://pintia.cn/problem-sets/15/problems/725

List结构定义 

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

创建一个新表

要求

创建并返回一个空的线性表。

显然需要使用到malloc函数来创建一个新空间。

LNode其实就是整个顺序表了，虽然不知道他为什么要这么来命名。第一次写代码的时候就因为这个弄错了。

具体代码

1
2
3
4
5
List MakeEmpty() {
    List L = (List)malloc(sizeof(struct LNode));
    L->Last = -1; //数组是从0开始数的，这里要保证为空就设置为-1
    return L;
}

查询元素

要求

返回线性表中X的位置。若找不到则返回ERROR。

没办法的啊，顺序表就只有上BF了，又不是排序完的数组可以用二分。

具体代码

1
2
3
4
5
6
7
8
Position Find( List L, ElementType X ) {
    for(int i = 0 ; i <= L->Last ; i++) {
        if (L->Data[i] == X) {
            return i;
        }
    }
    return ERROR;
}

插入元素

要求

将X插入在位置P并返回true。若空间已满，则打印“FULL”并返回false；如果参数P指向非法位置，则打印“ILLEGAL POSITION”并返回false。

首先对判满的判断那就是Last和MAXSIZE的比较，也就是Last + 1 == MAXSIZE就满了。

其次对非法位置的判断，大于 Last + 1 或者 小于 0 的都属于非法位置

最后再来实现插入操作

  • 从插入位置开始，所有元素向后移动一位

  • 插入位置替换为新元素

！！！这道题最打脑壳的就是你必须要先判满再判非法位置，否则过不了测试

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool Insert( List L, ElementType X, Position P ) {
    if (L->Last + 1 == MAXSIZE) {
        printf("FULL");
        return false;
    }

    if (P > L->Last + 1 || P < 0) {
        printf("ILLEGAL POSITION");
        return false;
    }

    for(int i = L->Last ; i >= P ; i--) { //这里需要注意的是插入操作从后往前覆盖
        L->Data[i+1] = L->Data[i];
    }

    L->Data[P] = X;
    L->Last++;
    return true;
}

删除元素

要求

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

判非法位置就是 P > Last || P < 0

删除操作就是把后面的向前覆盖，然后修改Last的值就可以让最后一个元素不需要处理。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
bool Delete( List L, Position P ) {
    if (P > L->Last || P < 0) {
        printf("POSITION %d EMPTY",P);
        return false;
    }

    for(int i = P ; i <= L->Last ; i++) { //这里需要注意的是删除操作从前往后覆盖
        L->Data[i] = L->Data[i+1];
    }
    L->Last--;
    return true;
}