顺序表

2024/9/18 数据结构数据结构 C语言顺序表

顺序表的概念

顺序表是一种线性的数据结构，其中数据元素按照特定的顺序依次存储在连续的内存空间中。它由一系列元素组成，每个元素都与唯一的索引（或者叫下标）相关联，索引从0开始递增。

顺序表中的元素可以是整数、浮点数等任意类型，包括结构体或者对象等等。

以下代码展示了初始化、销毁顺序表及返回顺序表size。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 定义顺序表的结构
typedef struct {
int* list;
size_t size;
// size_t是一种用于表示对象大小或数组索引的无符号整数类型
size_t capacity;
} SequentialList;

// 初始化顺序表
void SequentialList_Init(SequentialList* sl, size_t capacity) {
sl->list = (int*)malloc(sizeof(int) * capacity);
sl->size = 0;
sl->capacity = capacity;
return;
}

// 销毁顺序表
void SequentialList_Destroy(SequentialList* sl) {
if (sl->list != NULL) {
free(sl->list);
sl->list = NULL;
}
return;
}

// 获取顺序表的大小
size_t SequentialList_Size(const SequentialList* sl) {
return sl->size;
}

顺序表元素的插入

顺序表的元素插入，就是给定一个索引和一个元素，将这个元素插入到对应的索引位置，这个位置后的所有元素要往后挪一位。

例如要将元素5插入到索引3上，我们需要如图所示进行插入。

元素插入的步骤

判断插入位置是否合法（索引是否小于0或者大于size），如果不合法则抛出异常。
判断顺序表容量是否已满（即size=capacity），如果满了则倍增容量。
将插入位置及后面的元素往后面移动一位。
插入新元素。
更新顺序表的大小。

// 往顺序表里插入元素
void SequentialList_Insert(SequentialList* sl, int index, int element) {
if (index < 0 || index > sl->size) {
printf("Invalid index\n");
return;
}

if (sl->size == sl->capacity) {
int* new_list = (int*)realloc(sl->list, sizeof(int) * sl->capacity * 2);
if (new_list == NULL) {
printf("Failed to allocate memory\n");
return;
}
sl->list = new_list;
sl->capacity *= 2;
}

for (size_t i = sl->size; i > index; i--) {
sl->list[i] = sl->list[i - 1];
}
sl->list[index] = element;
sl->size++;

return;
}

顺序表元素删除

顺序表元素删除，就是给定一个索引，将这个索引上的元素删除并且将后面的元素往前移动一位。

例如要删除索引为3的元素，也就是5，操作如图。

元素删除的步骤

判断删除位置是否合法，如果不合法则抛出异常。
如果删除的为最后一个元素，顺序表大小直接减1。
如果删除位置不是最后一个元素，则将删除位置后的元素往前移动并覆盖要删除的元素。
更新顺序表大小。

// 删除顺序表中的某个元素
void SequentialList_Delete(SequentialList* sl, int index) {
if (index < 0 || index >= sl->size) {
printf("Invalid index\n");
return;
}

for (size_t i = index; i < sl->size; i++) {
sl->list[i] = sl->list[i + 1];
}
sl->size--;

return;
}

顺序表的元素查找

顺序表元素查找，就是给定元素，让我们查找是否存在于顺序表中，如果存在返回索引，不存在返回-1。在顺序表中，我们需要遍历表对比元素，时间复杂度为O(n)。

例如我们要查找值为7的元素，则遍历所有元素并返回索引。

顺序表查找步骤

遍历整个顺序表，如果和查找元素相同，返回索引。
没查到对应元素，返回-1。

// 查找顺序表中的某个元素
int SequentialList_Find(SequentialList* sl, int element) {
for (size_t i = 0; i < sl->size; i++) {
if (sl->list[i] == element) {
return i;
}
}
return -1;
}

顺序表元素索引

顺序表元素索引，即给定索引值，直接获取对应元素，时间复杂度O(1)。

例如给定索引5，通过下标访问直接获取7这个元素。

元素索引步骤

直接下标访问

// 查找顺序表某个索引对应的元素
int SequentialList_Index(SequentialList* sl, int index) {
if (index < 0 || index >= sl->size) {
printf("Invalid index\n");
return -1;
}
return sl->list[index];
}

顺序表的元素修改

修改顺序表元素，就是给定索引，将对应索引值更新为新值。

如图，给定5索引，改为9。

元素修改步骤

直接通过索引修改对应值

// 修改顺序表中某个索引对应的元素
void SequentialList_Change(SequentialList* sl, int index, int element) {
if (index < 0 || index >= sl->size) {
printf("Invalid index\n");
return;
}
sl->list[index] = element;
return;
}

顺序表打印

顺序表打印就是返回当前顺序表的size、capacity和各个元素值。

// 打印目前顺序表中的内容
void SequentialList_printf(SequentialList* sl) {
printf("Size: %zu\n", SequentialList_Size(sl));
printf("Capacity: %zu\n", sl->capacity);
printf("Element:");
for (size_t i = 0; i < sl->size; i++) {
printf("%d ", sl->list[i]);
}
printf("\n");
printf("内容打印完毕\n");
}

实验

实验代码正确性，要保证稳健。

// 实验
int main() {
// 初始化
printf("\n开始初始化顺序表\n");
SequentialList sl;
SequentialList_Init(&sl, 5);
SequentialList_printf(&sl);

// 插入元素
printf("\n开始插入元素\n");
for (int i = 0; i < 15; i++) {
SequentialList_Insert(&sl, i, i);
}
SequentialList_printf(&sl);

// 设置随机种子
srand(time(NULL));

// 随机删除3个元素
printf("\n开始删除元素\n");
for (int i = 0; i < 3; i++) {
// 生成1到50之间的随机整数
int random_number = (rand() % 15) + 1;
printf("删除的索引: %d 删除的元素: %d", random_number, SequentialList_Index(&sl, random_number));
SequentialList_Delete(&sl, random_number);
}
SequentialList_printf(&sl);

// 随机修改3个元素为-
printf("\n开始修改元素\n");
for (int i = 0; i < 3; i++) {
int random_number = (rand() % 15) + 1;
printf("删除的索引: %d 修改的元素: %d\n", random_number, SequentialList_Index(&sl, random_number));
SequentialList_Change(&sl, random_number, -99);
}
SequentialList_printf(&sl);

// 查找0到14还剩哪些数字
printf("\n开始查找0到14剩余元素\n");
for (int i = 0; i < 15; i++) {
printf("查找数字%d:", i);
int index = SequentialList_Find(&sl, i);
if (index != -1) {
printf("数字索引为%d\n", index);
}
else {
printf("没找到索引\n");
}
}

//销毁顺序表
SequentialList_Destroy(&sl);

return 0;
}

References

整理于英雄哪里出来知识星球内容

LOADING

顺序表