数据结构初阶：详解线性表之顺序表

这样一来，对于动态顺序表而言，我们就能实现**'想要多少给多少'**的功能需求了，不会因为数组的固定长度而担忧了。

既然对明白了顺序表的基本结构，那我们现在就来对顺序表进行实现吧。

2.3. 顺序表的实现

在实现顺序表之前，我们要先将头文件写好：

#include<stdio.h>
#include<stdlib.h> //为了使用 malloc、realloc 函数
#include<assert.h> //为了对指针进行断言操作
// #include<windows.h> //为了使用 Sleep() 函数，纯属个人喜好
#define INIT_SIZE 100 //预分配空间
#define INSERT_SIZE 200 //空间不够时要增加的空间
//现在将整形变量重命名为
typedef int Elemtype; //为了便于以后修改数据类型

在对某个数据结构进行实现之前，我们都可以围绕四个大方向进行操作：增、删、查、改。

2.3.1. 顺序表的初始化

不管对哪个数据结构，在进行操作之前都要记得对其进初始化哟~

void Init_Sqlist(Sqlist* pSqlist) {
    //为顺序表申请一个空间
    Elemtype* data = (Elemtype*)malloc(INIT_SIZE * sizeof(int));
    if (data == NULL) {
        printf("空间申请失败，同时顺序表初始化失败!\n");
        return;
    }
    pSqlist->data = data;
    pSqlist->length = 0;
    pSqlist->size = INIT_SIZE;
}

初始化是对顺序表结构当中的三个结构元素进行初始化：

1. 为 data 数组申请一块事先预定好的空间大小，将 data 指针指向这块空间;
2. 将表中的元素个数置为 0;
3. 将表长设置为预先设定好的长度 INIT_SIZE

2.3.2. 顺序表的插入操作

在顺序表中，对于插入操作我们有三种类型：头部插入，尾部插入，指定位置插入。

2.3.2.1. 头部插入

头部插入操作，实现的是一个陷进去的元素排在最后，最后进去的元素排在第一个的功能，可以通过下面的步骤进行实现：

1. 先对传进来的结构体指针进行判空 (这是一个重要的操作，基本上每个操作之前都会用到，所以后面都是默认进行此操作)
2. 判断当前顺序表的有效元素个数是否超过或者等于表长，如果是，那就重新申请空间
3. 将当前顺序表中的元素全部向后移动一位，为表头提供容纳下一个数据的位置
4. 将表头赋值上新的元素，记得将元素个数 length+1

下面是具体的代码：

void Push_Front(Sqlist* pSqlist, Elemtype num) {
    //想要在头部插入数据 2，就要先判断这个顺序表现在是否溢出:
    //如果溢出，那就扩容
    assert(pSqlist);
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("新空间申请失败，无法进行头部操作...\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    for (int i = pSqlist->length - 1; i >= 0; i--) {
        *(pSqlist->data + i + 1) = *(pSqlist->data + i);
    }
    *(pSqlist->data + 0) = num;
    pSqlist->length++;
}

这里要注意的是，我们在向后移动元素的时候，习惯上从最后一个元素开始，如果从第一个元素开始的话，会将后面的元素覆盖：

2.3.2.2. 尾部插入

尾部插入相对于头部插入就简单了许多，只需要在顺序表的最尾部进行插入即可，可按照下面的步骤进行，详细代码如下：

//现在是尾部的插入
void Push_Back(Sqlist* pSqlist, Elemtype num) {
    //依旧判断
    assert(pSqlist);
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("空间申请失败，无法进行尾部操作...\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    *(pSqlist->data + pSqlist->length) = num;
    pSqlist->length++; //一定要记得将顺序表中元素的个数进行 +1 操作，不然后面的操作会出问题!!
}

2.3.2.3. 指定位置 pos 插入

指定位置其实就相当于高级一点的头部插入，步骤与头部插入差不多，只不过是将头部的下标改成 pos 值而已，这里直接上代码。

void Push_pos(Sqlist* pSqlist, Elemtype num, int pos) {
    assert(pSqlist);
    //先检查 pos 值:
    if (pos < 0 || pos > pSqlist->length) {
        printf("pos 值不合法...\n");
        return;
    }
    //再检查是否溢出
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("申请空间失败，无法进行 pos 位置插入的相关操作...\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    //将 pos 位置后面的元素向后面移动
    for (int i = pSqlist->length - 1; i >= pos; i--) {
        *(pSqlist->data + i + 1) = *(pSqlist->data + i);
    }
    *(pSqlist->data + pos) = num;
    pSqlist->length++;
}

插入讲完了，那我们现在来讲讲删除操作。

2.3.3. 顺序表的删除操作

删除操作与插入操作一样，也分为头部删除，尾部删除，指定位置 pos 删除。

2.3.3.1. 头部删除

头部删除，不用想的太复杂，我们只需要将后面的数据元素向前移动一位，把第一个数据元素覆盖掉就行，再将有效数据个数进行 -1 操作即可，下面是代码：

void Pop_Front(Sqlist* pSqlist) {
    assert(pSqlist);
    for (int i = 0; i < pSqlist->length; i++) {
        *(pSqlist->data + i) = *(pSqlist->data + i + 1);
    }
    pSqlist->length--;
}

覆盖操作的话我们可以从第一个元素开始，将后面的数据元素往前'拉'。

2.3.3.2. 尾部删除

尾部删除比头部删除更加简单，因为 pSqlist->length 记录的是顺序表中有效的元素个数，我们只用将这个变量 -1 就行，不需要过多的操作：

void Pop_Back(Sqlist* pSqlist) {
    pSqlist->length--;
}

这样我们就完成了尾部删除的操作。

2.3.3.3. 指定位置 pos 删除

指定位置 pos 删除与头部删除相似，是将 pos 位置之后的数据元素全部向前移动一位，再将 pSqlist->length-1 即可。

//现在是 pos 位置删除
void Pop_pos(Sqlist* pSqlist, int pos) {
    assert(pSqlist);
    for (int i = pos; i < pSqlist->length; i++) {
        *(pSqlist->data + i - 1) = *(pSqlist->data + i);
    }
    pSqlist->length--;
}

在这里我们为了与现实逻辑一样，我们就认为输入的 pos 是从 1 开始，但实际上在顺序表中，是从 0 开始，所以在这里我们要将 pos-1，让下标逻辑与顺序表中相同。

2.3.4. 顺序表的查找

想要在顺序表中实现查找某个元素的功能，我们常用的就是遍历，当然，如果这个顺序表是有序的话，那我们可以使用二分查找法，这样会快很多，先买你是普通遍历查找的代码：

//现在是查找元素
void Search_elem(Sqlist* pSqlist, Elemtype num) {
    int flag = 0;
    for (int i = 0; i < pSqlist->length; i++) {
        if (*(pSqlist->data + i) == num) {
            printf("找到了\n");
            flag = 1;
            break;
        }
    }
    if (flag == 0) {
        printf("找不到哦\n");
    }
}

想要输出这个元素在顺序表中的位置，只用将 i 的值一起输出即可。

2.3.5. 顺序表的修改

我们来到了最后一个操作---修改，对于这个操作我们要传入你想要修改的位置 pos 以及修改之后的数据值，要先判断 pos 值是否合理，再将 pos 位置的值直接修改即可，代码如下：

//现在是修改元素
void Change_num(Sqlist* pSqlist, Elemtype num, int pos) {
    assert(pSqlist);
    if (pos < 0 || pos > pSqlist->length) {
        printf("pos 不合法，无法查找\n");
        return;
    }
    *(pSqlist->data + pos) = num;
    printf("pos 位置的值已经修改成%d\n", num);
}

2.3.6. 顺序表的打印

打印顺序表，我们只用将顺序表进行遍历，输出每个元素的值即可。

//现在是打印顺序表函数
void my_printf(Sqlist* pSqlist) {
    assert(pSqlist);
    for (int i = 0; i < pSqlist->length; i++) {
        printf("%d ", *(pSqlist->data + i));
    }
}

2.3.7. 顺序表的销毁操作

在进行完一系列操作之后，我们要将顺序表手动进行销毁，不要让他一直占用内存空间。我们只用将指向数组的指针 data 置为空即可：

void Destory_Sqlist(Sqlist* pSqlist) {
    assert(pSqlist);
    free(pSqlist->data);
    pSqlist->data = NULL;
}

以上就是实现顺序表基本功能的全部代码了，但还是缺少主函数，下面我就进行个汇总吧。

3. 代码总和

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// #include<windows.h>
#define INIT_SIZE 100
#define INSERT_SIZE 200
//现在将整形变量重命名为
typedef int Elemtype;
//现在定义顺序表结构体
typedef struct SqList {
    Elemtype* data;
    int length;
    int size;
}Sqlist;

//现在对顺序表进行初始化:
void Init_Sqlist(Sqlist* pSqlist) {
    //为顺序表申请一个空间
    Elemtype* data = (Elemtype*)malloc(INIT_SIZE * sizeof(int));
    if (data == NULL) {
        printf("空间申请失败，同时顺序表初始化失败!\n");
        return;
    }
    pSqlist->data = data;
    pSqlist->length = 0;
    pSqlist->size = INIT_SIZE;
}

//对顺序表有以下操作：插入，删除，查找，修改
//插入：头插，尾插，pos 位置
//删除：头删，尾删，pos 位置
//查找:
//修改
//现在对顺序表进行增加操作：头插
void Push_Front(Sqlist* pSqlist, Elemtype num) {
    //想要在头部插入数据 2，就要先判断这个顺序表现在是否溢出:
    //如果溢出，那就扩容
    assert(pSqlist);
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("新空间申请失败，无法进行头部操作...\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    for (int i = pSqlist->length - 1; i >= 0; i--) {
        *(pSqlist->data + i + 1) = *(pSqlist->data + i);
    }
    *(pSqlist->data + 0) = num;
    pSqlist->length++;
}

//现在是尾部的插入
void Push_Back(Sqlist* pSqlist, Elemtype num) {
    //依旧判断
    assert(pSqlist);
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("空间申请失败，无法进行尾部操作...\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    *(pSqlist->data + pSqlist->length) = num;
    pSqlist->length++;
}

//现在是 pos 位置的插入:
void Push_pos(Sqlist* pSqlist, Elemtype num, int pos) {
    assert(pSqlist);
    //先检查 pos 值:
    if (pos < 0 || pos > pSqlist->length) {
        printf("pos 值不合法...\n");
        return;
    }
    //再检查是否溢出
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, INSERT_SIZE * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("申请空间失败，无法进行 pos 位置插入的相关操作...\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    //将 pos 位置后面的元素向后面移动
    for (int i = pSqlist->length - 1; i >= pos; i--) {
        *(pSqlist->data + i + 1) = *(pSqlist->data + i);
    }
    *(pSqlist->data + pos) = num;
    pSqlist->length++;
}

//现在是删除操作：头删
void Pop_Front(Sqlist* pSqlist) {
    assert(pSqlist);
    for (int i = 0; i < pSqlist->length; i++) {
        *(pSqlist->data + i) = *(pSqlist->data + i + 1);
    }
    pSqlist->length--;
}

//现在是尾删
void Pop_Back(Sqlist* pSqlist) {
    pSqlist->length--;
}

//现在是 pos 位置删除
void Pop_pos(Sqlist* pSqlist, int pos) {
    assert(pSqlist);
    for (int i = pos; i < pSqlist->length; i++) {
        *(pSqlist->data + i - 1) = *(pSqlist->data + i);
    }
    pSqlist->length--;
}

//现在是查找元素
void Search_elem(Sqlist* pSqlist, Elemtype num) {
    int flag = 0;
    for (int i = 0; i < pSqlist->length; i++) {
        if (*(pSqlist->data + i) == num) {
            printf("找到了\n");
            flag = 1;
            break;
        }
    }
    if (flag == 0) {
        printf("找不到哦\n");
    }
}

//现在是修改元素
void Change_num(Sqlist* pSqlist, Elemtype num, int pos) {
    assert(pSqlist);
    if (pos < 0 || pos > pSqlist->length) {
        printf("pos 不合法，无法查找\n");
        return;
    }
    *(pSqlist->data + pos) = num;
    printf("pos 位置的值已经修改成%d\n", num);
}

//现在是打印顺序表函数
void my_printf(Sqlist* pSqlist) {
    assert(pSqlist);
    for (int i = 0; i < pSqlist->length; i++) {
        printf("%d ", *(pSqlist->data + i));
    }
}

void Destory_Sqlist(Sqlist* pSqlist) {
    assert(pSqlist);
    free(pSqlist->data);
    pSqlist->data = NULL;
}

//现在是打印菜单函数
void printf_menu() {
    printf("=============================\n");
    printf("你可以进行以下操作:\n");
    printf("1.头插 2.尾插 3.pos 位置插\n");
    printf("4.头删 5.尾删 6.pos 位置删\n");
    printf("7.查找元素 8.修改元素\n");
    printf("=============================\n");
    printf("\n");
}

//现在是主函数
int main() {
    Sqlist L;
    Sqlist* pSqlist = &L;
    Init_Sqlist(pSqlist);
    int choose = 0;
    do {
        // system("cls");
        printf_menu();
        printf("当前的顺序表为:\n");
        my_printf(pSqlist);
        printf("\n");
        printf("请输入你的选择 (按 -1 结束程序):\n");
        scanf("%d", &choose);
        if (choose == -1) {
            break;
        }
        switch (choose) {
        case 1: {
            printf("请输入你想输入的元素个数:\n");
            int num_num = 0;
            scanf("%d", &num_num);
            printf("请输入你想要插入的元素:\n");
            Elemtype num;
            for (int i = 0; i < num_num; i++) {
                scanf("%d", &num);
                Push_Front(pSqlist, num);
            }
            printf("插入成功!!!\n");
            break;
        }
        case 2: {
            printf("请输入你想输入的元素个数:\n");
            int num_num = 0;
            scanf("%d", &num_num);
            printf("请输入你想要插入的元素:\n");
            Elemtype num;
            for (int i = 0; i < num_num; i++) {
                scanf("%d", &num);
                Push_Back(pSqlist, num);
            }
            printf("插入成功!!!\n");
            break;
        }
        case 3: {
            printf("请输入你想要输入的位置:\n");
            int pos = 0;
            scanf("%d", &pos);
            printf("请输入你想要输入的元素:\n");
            Elemtype num = 0;
            scanf("%d", &num);
            Push_pos(pSqlist, num, pos);
            printf("插入成功!!!\n");
            break;
        }
        case 4: {
            Pop_Front(pSqlist);
            printf("删除成功!!!\n");
            break;
        }
        case 5: {
            Pop_Back(pSqlist);
            printf("删除成功!!!\n");
            break;
        }
        case 6: {
            printf("请输入你想要删除的位置:\n");
            int pos = 0;
            scanf("%d", &pos);
            Pop_pos(pSqlist, pos);
            printf("删除成功!!!\n");
            break;
        }
        case 7: {
            printf("请输入你想要查找的元素:\n");
            Elemtype num;
            scanf("%d", &num);
            Search_elem(pSqlist, num);
            printf("查找完成!!!\n");
            break;
        }
        case 8: {
            printf("请输入你想要修改的位置:\n");
            int pos = 0;
            scanf("%d", &pos);
            printf("请输入你想要修改成的元素:\n");
            Elemtype num = 0;
            scanf("%d", &num);
            Change_num(pSqlist, num, pos);
            printf("修改成功!!!\n");
            break;
        }
        default: {
            printf("choose 的值不合法，请重新输入!!!\n");
            break;
        }
        }
    } while (choose != -1);
    //最后释放内存
    Destory_Sqlist(pSqlist);
    return 0;
}

以上就是我对线性表之一的顺序表的全部分享内容了，有不对的地方希望大佬们指出来~~~