【数据结构】王道课后习题（线性表）（一）（可直接运行）

• 1.01 删除最小值
• • 1.1算法实现
  • 1.2 完整代码
• 2.02 逆置
• • 2.1算法实现
  • 2.2 完整代码
• 3.03 删除所有指定元素
• • 3.1算法实现
  • 3.2 完整代码

完整题目如下：

显然，只需要遍历找到最小值，并用最后一个元素覆盖即可。
具体实现如下：

// 算法实现
bool popMinNum(SeqList &L, int &e) {
    // 判断表是否为空
    if(L.length == 0) {
        printf("The list is empty!");
        return false;
    }
    // 首先需要找到最小的数
    // 预设变量用于存储最小值及下标
    int min_num = L.data[0];
    int index = 0;
    for(int i = 1;i < L.length;i++) {
        if(L.data[i] < min_num) {
            min_num = L.data[i];
            index = i;
        }
    }
    // 删除元素并填入最后一个元素
    L.data[index] = L.data[L.length - 1];
    // 注意长度减一
    L.length -= 1;
    e = min_num;
    return true;
}

#include
#include

#define InitSize 10

typedef struct {
    int *data;  // 数据
    int MaxSize;    // 最大容量
    int length; // 目前长度
} SeqList;

// 初始化
void InitList(SeqList &L) {
    // 为了方便，这里选择初始化时填入1-10
    // 申请10个整型的空间
    L.data = (int *)malloc(InitSize * sizeof(int));
    // 数据填入
    for(int i = 0;i < InitSize;i++) {
        L.data[i] = i + 1;
    }
    L.length = 10;
    L.MaxSize = InitSize;
}

// 算法实现
bool popMinNum(SeqList &L, int &e) {
    // 判断表是否为空
    if(L.length == 0) {
        printf("The list is empty!");
        return false;
    }
    // 首先需要找到最小的数
    // 预设变量用于存储最小值及下标
    int min_num = L.data[0];
    int index = 0;
    for(int i = 1;i < L.length;i++) {
        if(L.data[i] < min_num) {
            min_num = L.data[i];
            index = i;
        }
    }
    // 删除元素并填入最后一个元素
    L.data[index] = L.data[L.length - 1];
    // 注意长度减一
    L.length -= 1;
    e = min_num;
    return true;
}

// 判空操作
bool Empty(SeqList L) {
    // 直接根据长度判断即可
    if(L.length == 0) {
        return true;
    }
    return false;
}

// 顺序表的输出操作
bool PrintList(SeqList L) {
    // 若表为空，则不能输出
    if(Empty(L)) {
        return false;
    }
    // 循环遍历输出
    for(int i = 0;i < L.length;i++) {
        printf("data[%d]=%dn", i, L.data[i]);
    }
    return true;
}

int main() {
    SeqList L;
    InitList(L);
    PrintList(L);
    printf("-------------------------------n");
    int e;
    popMinNum(L, e);
    PrintList(L);
    printf("the delete num is %dn", e);
}

完整题目如下：

要求空间复杂度为O(1)，时间复杂度无要求，那么只需要循环换位即可实现。
代码如下：

// 算法实现
void reverse(SeqList &L) {
    for(int i = 0;i <= L.length / 2;i++) {
        // 中间变量
        int temp;
        // 交换次序
        temp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

#include
#include

#define InitSize 10

typedef struct {
    int *data;  // 数据
    int MaxSize;    // 最大容量
    int length; // 目前长度
} SeqList;

// 初始化
void InitList(SeqList &L) {
    // 为了方便，这里选择初始化时填入1-10
    // 申请10个整型的空间
    L.data = (int *)malloc(InitSize * sizeof(int));
    // 数据填入
    for(int i = 0;i < InitSize;i++) {
        L.data[i] = i + 1;
    }
    L.length = 10;
    L.MaxSize = InitSize;
}

// 算法实现
void reverse(SeqList &L) {
    for(int i = 0;i <= L.length / 2;i++) {
        // 中间变量
        int temp;
        // 交换次序
        temp = L.data[i];
        L.data[i] = L.data[L.length - i - 1];
        L.data[L.length - i - 1] = temp;
    }
}

// 判空操作
bool Empty(SeqList L) {
    // 直接根据长度判断即可
    if(L.length == 0) {
        return true;
    }
    return false;
}

// 顺序表的输出操作
bool PrintList(SeqList L) {
    // 若表为空，则不能输出
    if(Empty(L)) {
        return false;
    }
    // 循环遍历输出
    for(int i = 0;i < L.length;i++) {
        printf("data[%d]=%dn", i, L.data[i]);
    }
    return true;
}

int main() {
    SeqList L;
    InitList(L);
    PrintList(L);
    printf("-------------------------------n");
    reverse(L);
    PrintList(L);
    return 0;
}

完整题目如下：

分析题目，要求时间复杂度O(n)，那么就不能使用最简单的即找即删。可以设定一个变量k用于记录非x的个数，如果该元素不是x，那么就把它放到第k个，同时k+1，这样前k个即全部是非x，再将length设为k，即可以视为已经删除了所有x，且次序未改变。
代码如下：

// 算法实现
void deleteAllX(SeqList &L, int x) {
    int k = 0;  // 用于记录非x的个数
    for(int i = 0;i < L.length;i++) {
        // 如果该元素不是x，那么就把它放到第k个，同时k+1
        // k即是非x的个数，在遍历时，把非x的赋值给顺序表第k个位置
        // 这样前k个即全部是非x，再将length设为k，即可以视为已经删除了所有x，且次序未改变
        if(L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

#include
#include

#define InitSize 10

typedef struct {
    int *data;  // 数据
    int MaxSize;    // 最大容量
    int length; // 目前长度
} SeqList;

// 初始化
void InitList(SeqList &L) {
    // 为了方便，这里选择初始化时填入1-10
    // 申请10个整型的空间
    L.data = (int *)malloc(InitSize * sizeof(int));
    // 数据填入
    for(int i = 0;i < InitSize;i++) {
        L.data[i] = i + 1;
    }
    L.length = 10;
    L.MaxSize = InitSize;
}

// 算法实现
void deleteAllX(SeqList &L, int x) {
    int k = 0;  // 用于记录非x的个数
    for(int i = 0;i < L.length;i++) {
        // 如果该元素不是x，那么就把它放到第k个，同时k+1
        // k即是非x的个数，在遍历时，把非x的赋值给顺序表第k个位置
        // 这样前k个即全部是非x，再将length设为k，即可以视为已经删除了所有x，且次序未改变
        if(L.data[i] != x) {
            L.data[k] = L.data[i];
            k++;
        }
    }
    L.length = k;
}

// 判空操作
bool Empty(SeqList L) {
    // 直接根据长度判断即可
    if(L.length == 0) {
        return true;
    }
    return false;
}

// 顺序表的输出操作
bool PrintList(SeqList L) {
    // 若表为空，则不能输出
    if(Empty(L)) {
        return false;
    }
    // 循环遍历输出
    for(int i = 0;i < L.length;i++) {
        printf("data[%d]=%dn", i, L.data[i]);
    }
    return true;
}

int main() {
    SeqList L;
    InitList(L);
    PrintList(L);
    printf("-------------------------------n");
    deleteAllX(L, 3);
    PrintList(L);
    return 0;
}