一、定义
顺序表是一种线性的存储结构，采用一段连续的地址存储单元依次存放数据元素，一般采用数组存储。
顺序表一般可分为：
1.静态顺序表：使用定长数组存储元素。
2.动态顺序表：使用动态开辟的数组存储。
二、结构体定义
typedef int SLDateType; typedef struct SeqList { SLDateType* array; int capacity;//顺序表容量，array指向空间最多存储元素个数 int size;//有效元素个数 }SeqList;
这里实现的是动态顺序表。
三、接口实现
void SeqListInit(SeqList* ps, int initCapacity) //顺序表初始化 void ShowListInsert(SeqList* ps) //打印顺序表 void CheckCapacity(SeqList* ps) //判断是否需要扩容 int SeqListFind(SeqList* ps, SLDateType x) //顺序表查找 void SeqListInsert(SeqList* ps, int pos, SLDateType x) //顺序表在pos位置插入x void SeqListErase(SeqList* ps, int pos) //顺序表删除pos位置的值
因为顺序表的基本操作都相对简单，所以这里就直接给出相应操作的代码实现：
1.顺序表初始化
void SeqListInit(SeqList* ps, int initCapacity) {//顺序表初始化 assert(ps); initCapacity = initCapacity <= 0 ? 3 : initCapacity; ps->array = (int*)malloc(sizeof(SLDateType) * initCapacity); if (ps == NULL) { assert(0); return; } ps->capacity = initCapacity; ps->size = 0; }
2.顺序表打印
void ShowListInsert(SeqList* ps) {//打印顺序表 for (int i = 0; i < ps->size; i++) { printf("%d ", ps->array[i]); } }
3.判断是否需要扩容、扩容
void CheckCapacity(SeqList* ps) {//判断是否需要扩容 assert(ps); if (ps->size == ps->capacity) {//判断是否需要扩容 int newcapacity = ps->capacity * 2;//计算空间大小 int* temp = (int*)malloc(sizeof(SLDateType) * newcapacity); if (temp == NULL) {//申请失败 assert(temp); return; } memcpy(temp, ps->array, sizeof(SLDateType) * ps->size);//将数据拷贝到新空间中 free(ps->array); ps->array = temp; ps->capacity = newcapacity; } }
3.顺序表查找
int SeqListFind(SeqList* ps, SLDateType x) {//顺序表查找 assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->array[i] == x) { return i; } } return -1; }
4.顺序表任意位置插入
void SeqListInsert(SeqList* ps, int pos, SLDateType x) {//顺序表在pos位置插入x assert(ps); if (pos<0 || pos>ps->size) { printf("插入位置不合法！\n"); return; } CheckCapacity(ps);//检测是否需要扩容 for (int i = ps->size-1; i >= pos; i--) { ps->array[i+1] = ps->array[i]; } ps->array[pos] = x; ps->size++; }
5.顺序表任意位置删除
void SeqListErase(SeqList* ps, int pos) {//顺序表删除pos位置的值 assert(ps); if (pos<0 || pos>=ps->size) { printf("插入位置不合法！\n"); return; } for (int i = pos + 1; i < ps->size; i++) { ps->array[i - 1] = ps->array[i]; } ps->size--; }
四、测试用例即结果
1.测试用例：
SeqList ps; SeqListInit(&ps, 0); SeqListInsert(&ps, 0, 1); SeqListInsert(&ps, 1, 3); SeqListInsert(&ps, 1, 2); ShowListInsert(&ps); printf("\n"); SeqListErase(&ps, 2); ShowListInsert(&ps);
2.测试结果：
五、完整代码
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<malloc.h> #include<assert.h> #include<string.h> typedef int SLDateType; typedef struct SeqList { SLDateType* array; int capacity;//顺序表容量，array指向空间最多存储元素个数 int size;//有效元素个数 }SeqList; void SeqListInit(SeqList* ps, int initCapacity) {//顺序表初始化 assert(ps); initCapacity = initCapacity <= 0 ? 3 : initCapacity; ps->array = (int*)malloc(sizeof(SLDateType) * initCapacity); if (ps == NULL) { assert(0); return; } ps->capacity = initCapacity; ps->size = 0; } void ShowListInsert(SeqList* ps) {//打印顺序表 for (int i = 0; i < ps->size; i++) { printf("%d ", ps->array[i]); } } void CheckCapacity(SeqList* ps) {//判断是否需要扩容 assert(ps); if (ps->size == ps->capacity) {//判断是否需要扩容 int newcapacity = ps->capacity * 2;//计算空间大小 int* temp = (int*)malloc(sizeof(SLDateType) * newcapacity); if (temp == NULL) {//申请失败 assert(temp); return; } memcpy(temp, ps->array, sizeof(SLDateType) * ps->size);//将数据拷贝到新空间中 free(ps->array); ps->array = temp; ps->capacity = newcapacity; } } int SeqListFind(SeqList* ps, SLDateType x) {//顺序表查找 assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->array[i] == x) { return i; } } return -1; } void SeqListInsert(SeqList* ps, int pos, SLDateType x) {//顺序表在pos位置插入x assert(ps); if (pos<0 || pos>ps->size) { printf("插入位置不合法！\n"); return; } CheckCapacity(ps);//检测是否需要扩容 for (int i = ps->size-1; i >= pos; i--) { ps->array[i+1] = ps->array[i]; } ps->array[pos] = x; ps->size++; } void SeqListErase(SeqList* ps, int pos) {//顺序表删除pos位置的值 assert(ps); if (pos<0 || pos>=ps->size) { printf("插入位置不合法！\n"); return; } for (int i = pos + 1; i < ps->size; i++) { ps->array[i - 1] = ps->array[i]; } ps->size--; } int main() { SeqList ps; SeqListInit(&ps, 0); SeqListInsert(&ps, 0, 1); SeqListInsert(&ps, 1, 3); SeqListInsert(&ps, 1, 2); ShowListInsert(&ps); printf("\n"); SeqListErase(&ps, 2); ShowListInsert(&ps); return 0; }
