【数据结构】顺序表

前言 顺序表是线性表的一种，而线性表是一种数据结构。顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。顺序表主要特点是内存存储是连续的，数据元素都是首尾相接的。

---

文章目录 一、顺序表介绍二、动态顺序表的实现2.1 动态顺序表的定义2.2 初始化和销毁2.3 扩容2.4 插入2.5 删除2.6 查找2.7 打印2.8 主函数 三、完整代码"SeqList.h""SeqList.c""main.c"

一、顺序表介绍

顺序表分为静态顺序表和动态顺序表。

静态顺序表： 顺序表大小固定

typedef int SLDataType; #define N 7 typedef struct SeqList { SLDataType a[N];//定长数组 int size;//有效数据个数 }SL;

动态顺序表： 通过动态开辟内存，可随时扩大容量

typedef int SLDataType; typedef struct SeqList { SLDataType* a; //定长数组 int size; //有效数据个数 int capacity; //当前数据容量 }SL;

---

二、动态顺序表的实现

顺序表通常有以下操作:

插入：在指定位置插入一个新元素。删除：删除指定位置的元素。查找：查找指定元素并返回其位置。遍历：访问线性表中的每一个元素。

---

2.1 动态顺序表的定义

顺序表通常有三个属性，data指向动态分配数组的指针，用于存储元素，size表中当前存储的元素数量，capacity是当前分配的数组容量。 因为不同的人用顺序表存储的元素的类型不一定一样，为了方便使用，应将数据类型重命名，再次使用时只需要将 typedef int SLDataType 中的 int 改成需要的类型。

//动态顺序表 typedef int SLDataType;//数据类型重命名，方便重复使用顺序表 typedef struct SequenceList { SLDataType* data; int size; //顺序表中有效的数据个数 int capacity; //顺序表当前的空间大小 }SList; 2.2 初始化和销毁

初始化 初始化时，选择为list动态分配内存的好处是，对于需要大量内存的数据结构，使用堆通常是唯一的选择 list存放在栈中的好处是，不需要在使用完List后释放空间，还有栈上的内存分配和释放通常比堆上的快

//初始化 void initSeqList(SList* list) { assert(list); //SList *list = (SList*)malloc(sizeof(SList)); list->data = (int*)malloc(sizeof(int)); list->size = 0; list->capacity = 1; }

销毁 在销毁要注意的是，在释放空间后，不要忘记给list赋NULL

//销毁 void destroySeqList(SList* list) { assert(list); if (list->data) { free(list->data); // 释放动态数组的内存 list->data = NULL; // 防止野指针 } list = NULL; // 防止野指针 }

---

2.3 扩容

通常扩容选择原容量的1.5倍或者2倍进行扩容

//扩容 int resizeSeqList(SList* list) { assert(list); int newCapacity = list->capacity * 2;//通常扩容选择1.5倍或者2倍进行扩容 int* newData = (int*)realloc(list->data, sizeof(int) * newCapacity); if (newData == NULL) { printf("内存分配失败\n"); return -1; } list->data = newData; list->capacity = newCapacity; return 0; }

---

2.4 插入 // 插入 int insertSeqList(SList* list, int index, int value) { assert(list); if (index < 0 || index > list->size) { return -1; } if (list->size >= list->capacity) { //如果容量不足，进行扩容 if (resizeSeqList(list) == -1) { return -1; // 扩容失败 } } for (int i = list->size; i > index; i--) {//将数据插入该位置，该位置及后面的数据向后移 list->data[i] = list->data[i - 1]; } list->data[index] = value; list->size++; //有效数据+1 return 0; }

---

2.5 删除 // 删除 int deleteSeqList(SList* list, int index) { assert(list); if (index < 0 || index >= list->size) { return -1; } for (int i = index; i < list-> size ; i++) {//将要删除的数据后面的数据往前移 list->data[i] = list->data[i + 1]; } list->size--; return 0; }

---

2.6 查找 // 查找 int findSeqList(SList* list, int value) { assert(list); for (int i = 0; i < list->size; i++) { if (list->data[i] == value) { printf("找到目标数据，在第%d个\n", i + 1); return i; } } printf("未找到目标数据\n"); return -1; }

---

2.7 打印 // 打印 void printSeqList(SList* list) { assert(list); for (int i = 0; i < list->size; i++) { printf("%d ", list->data[i]); } printf("\n");

---

2.8 主函数 #include"SeqList.h" int main() { SList list; initSeqList(&list); insertSeqList(&list, 0, 1); insertSeqList(&list, 1, 2); insertSeqList(&list, 2, 3); printSeqList(&list); deleteSeqList(&list, 1); printSeqList(&list); findSeqList(&list,2); destroySeqList(&list); return 0; }

运行结果：

---

三、完整代码 “SeqList.h” #include<stdio.h> #include<stdlib.h> #include<assert.h> //动态顺序表 typedef int SLDataType;//数据类型重命名，方便重复使用顺序表 typedef struct SequenceList { SLDataType* data; int size; //顺序表中有效的数据个数 int capacity; //顺序表当前的空间大小 }SList; // 对顺序表进行初始化 void initSeqList(SList* list); // 扩容 int resizeSeqList(SList* list); // 插入 int insertSeqList(SList* list, int index, int value); // 删除 int deleteSeqList(SList* list, int index); // 查找 int findSeqList(SList* list, int value); // 打印 void printSeqList(SList* list); //销毁 void destroySeqList(SList* list);

---

“SeqList.c” #include"SeqList.h" //初始化 void initSeqList(SList* list) { assert(list); list->data = (int*)malloc(sizeof(int) * 2); list->size = 0; list->capacity = 2; } //扩容 int resizeSeqList(SList* list) { assert(list); int newCapacity = list->capacity * 2; int* newData = (int*)realloc(list->data, sizeof(int) * newCapacity);//通常扩容选择1.5倍或者2倍进行扩容 if (newData == NULL) { printf("内存分配失败\n"); return -1; } list->data = newData; list->capacity = newCapacity; return 0; } // 插入 int insertSeqList(SList* list, int index, int value) { assert(list); if (index < 0 || index > list->size) { return -1; } if (list->size >= list->capacity) { //如果容量不足，进行扩容 if (resizeSeqList(list) == -1) { return -1; // 扩容失败 } } for (int i = list->size; i > index; i--) {//将数据插入该位置，该位置及后面的数据向后移 list->data[i] = list->data[i - 1]; } list->data[index] = value; list->size++; //有效数据+1 return 0; } // 删除 int deleteSeqList(SList* list, int index) { assert(list); if (index < 0 || index >= list->size) { return -1; } for (int i = index; i < list-> size ; i++) {//将要删除的数据后面的数据往前移 list->data[i] = list->data[i + 1]; } list->size--; return 0; } // 查找 int findSeqList(SList* list, int value) { assert(list); for (int i = 0; i < list->size; i++) { if (list->data[i] == value) { printf("找到目标数据，在第%d个\n", i + 1); return i; } } printf("未找到目标数据\n"); return -1; } // 打印 void printSeqList(SList* list) { assert(list); for (int i = 0; i < list->size; i++) { printf("%d ", list->data[i]); } printf("\n"); } //销毁 void destroySeqList(SList* list) { assert(list); if (list->data) { free(list->data); // 释放动态数组的内存 list->data = NULL; // 防止野指针 } list = NULL; // 防止野指针 }

---

“main.c” #include"SeqList.h" int main() { SList list; initSeqList(&list); insertSeqList(&list, 0, 1); insertSeqList(&list, 1, 2); insertSeqList(&list, 2, 3); printSeqList(&list); deleteSeqList(&list, 1); printSeqList(&list); findSeqList(&list,2); destroySeqList(&list); return 0; }

---

如果你喜欢这篇文章，点赞👍+评论+关注⭐️哦！ 欢迎大家提出疑问，以及不同的见解。