C语言深入浅出讲解顺序表的实现

顺序表简介

顺序表是一种线性表的存储结构，它是由连续的内存空间来存储线性表中的元素。

顺序表的特点是支持查找、插入和删除操作，操作效率较高，但需要提前分配足够大的内存空间。当顺序表空间不足时，需要扩容，移动数据较为麻烦。

顺序表的实现

数据结构定义

顺序表的数据结构定义包含以下几个成员：

• 数据元素数组 data，存储线性表中的元素
• 当前线性表中的元素个数 length
• 顺序表中容纳的元素个数 size

#define MAX_SIZE 100 // 定义最大容纳元素个数

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
    int size;
} SqList;

初始化顺序表

初始化一个空的顺序表，需要将元素个数 length 置为 0，容纳元素的个数 size 置为指定的容量 max_size。

void init(SqList *list, int max_size) {
    list->length = 0;
    list->size = max_size;
}

插入元素

向顺序表中插入一个元素，需要将该元素插入到指定的位置，并将该位置后的元素向后移动一位。

bool insert(SqList *list, int index, int value) {
    if (list->length >= list->size) {
        return false;
    }
    if (index < 0 || index > list->length) {
        return false;
    }
    // 从末尾向指定位置移动元素
    for (int i = list->length - 1; i >= index; i--) {
        list->data[i + 1] = list->data[i];
    }
    // 在指定位置插入元素
    list->data[index] = value;
    list->length++;
    return true;
}

删除元素

从顺序表中删除一个元素，需要将该位置后的元素向前移动一位。

bool remove(SqList *list, int index) {
    if (index < 0 || index >= list->length) {
        return false;
    }
    // 从指定位置向后移动元素
    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return true;
}

查找元素

在顺序表中查找指定元素时，需要遍历所有元素逐个比较。

int find(SqList *list, int value) {
    for (int i = 0; i < list->length; i++) {
        if (list->data[i] == value) {
            return i;
        }
    }
    return -1;
}

示例说明

示例一：插入元素

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
    int size;
} SqList;

void init(SqList *list, int max_size) {
    list->length = 0;
    list->size = max_size;
}

bool insert(SqList *list, int index, int value) {
    if (list->length >= list->size) {
        return false;
    }
    if (index < 0 || index > list->length) {
        return false;
    }
    // 从末尾向指定位置移动元素
    for (int i = list->length - 1; i >= index; i--) {
        list->data[i + 1] = list->data[i];
    }
    // 在指定位置插入元素
    list->data[index] = value;
    list->length++;
    return true;
}

int main() {
    SqList list;
    int value = 3;
    init(&list, MAX_SIZE);
    insert(&list, 0, 1);
    insert(&list, 1, 2);
    insert(&list, 2, value);
    for (int i = 0; i < list.length; i++) {
        printf("%d ", list.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

1 2 3

示例二：删除元素

#include <stdio.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct SqList {
    int data[MAX_SIZE];
    int length;
    int size;
} SqList;

void init(SqList *list, int max_size) {
    list->length = 0;
    list->size = max_size;
}

bool remove(SqList *list, int index) {
    if (index < 0 || index >= list->length) {
        return false;
    }
    // 从指定位置向后移动元素
    for (int i = index; i < list->length - 1; i++) {
        list->data[i] = list->data[i + 1];
    }
    list->length--;
    return true;
}

int main() {
    SqList list;
    init(&list, MAX_SIZE);
    insert(&list, 0, 1);
    insert(&list, 1, 2);
    insert(&list, 2, 3);
    remove(&list, 1);
    for (int i = 0; i < list.length; i++) {
        printf("%d ", list.data[i]);
    }
    printf("\n");
    return 0;
}

输出结果：

1 3