顺序表是一种线性表的存储结构，它使用一组地址连续的存储单元依次存储线性表的数据元素。在顺序表中，逻辑上相邻的元素在物理存储上也相邻，通常采用数组来实现这种存储方式。
前言：
顺序表格的特点：
- 随机访问：可以通过首地址和元素序号在常数时间内找到指定的元素。
- 存储密度高：由于每个结点只存储数据元素，没有额外开销，因此存储密度较高。
- 物理位置相邻：物理位置和逻辑位置一致，保持相邻，但这也意味着插入和删除操作可能涉及到大量元素的移动。
顺序表简单介绍：
- 顺序表主要分为动态和静态，由于静态局限性，在这主要实现动态顺序表。
- 动态顺序表主要运用malloc()和realloc()函数对内存进行动态开辟。
- 动态顺序表主要涉及初始化，销毁，增容，插入，删除，查找。
准备工作；
#include <stdlib.h> #include <assert.h> typedef int SLDataType; #define Initcapacity 3 typedef struct SeqList { SLDataType* a; int size; int capacity; }SL;
定义：
结构体 SL；重定义int类型；包含所需要的头文件
一、初 始 化（malloc）
//初始化顺序表 void InitSL(SL* ps) { assert(ps); ps->a = (SLDataType*)malloc(sizeof(SLDataType) * Initcapacity); if (ps->a == NULL) { perror("malloc fail"); return; } ps->capacity = Initcapacity; ps->size = 0; }
二、销 毁 （free）
//空间销毁 void SLDestory(SL* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->size = 0; ps->capacity = 0; }
三、增 容（realloc）
//检查容量并增加 void CheckCapacity(SL* ps) { if (ps->size == ps->capacity) { SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2); if (tmp == NULL) { perror("realloc fail"); return; } ps->capacity *= 2; ps->a = tmp; } }
四、插入
4.1 头 插
//头插 void SeqListPushFront(SL* ps, SLDataType x) { assert(ps); CheckCapacity(ps); int end = ps->size - 1; if (ps->size > 0) { while (end >= 0) { ps->a[end + 1] = ps->a[end]; end--; } } ps->a[0] = x; ps->size++; }
4.2 尾 插
void SeqListPushBack(SL* ps, SLDataType x) { assert(ps); CheckCapacity(ps); ps->a[ps->size] = x; ps->size++; }
4.3 指 定 位 置 插 入
// insert 元素 void SeqListInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size - 1); CheckCapacity(ps); int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end + 1]; end--; } ps->a[pos] = x; }
五、删除
5.1 头 删
// 头删 void SeqListPopFront(SL* ps) { assert(ps); assert(ps->size > 0); int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
5.3 尾 删
//尾删 void SeqListPopBack(SL* ps) { assert(ps); assert(ps->size > 0); ps->size--; }
5.3 指 定 位 置 删 除
//指定位置删元素 void SeqListErase(SL* ps, int pos) { assert(ps); assert(ps >= 0 && pos < ps->size); int begin = pos - 1; while (begin < ps->size - 1) { ps->a[begin] = ps->a[begin + 1]; begin++; } ps->size--; }
六、查 找
//暴力查找 int SeqListFind(SL* ps, SLDataType x) { assert(ps); int pos = 0; for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { pos = i; break; } } return pos; }
