概述
什么是动态顺序表？
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。静态顺序表需要提前开好固定大小的数组空间，而动态顺序表的数组空间大小可以依据实际随时调整。
接口实现
动态顺序表，根据需要动态的分配空间 大小，所以下面我们实现动态顺序表。首先对头文件的定义：
// SeqList.h #pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> // 顺序表的动态存储 typedef int SLDateType; typedef struct SeqList { SLDateType* a; // 指向动态开辟的数组 int size; // 定义有效数据个数，便于统计 int capacity; // 容量空间的大小 }SeqList; // 基本增删查改接口 // 对数据的管理:增删查改 void SeqListInit(SeqList* ps); // 顺序表初始化 void SeqListDestroy(SeqList* ps); // 检查空间，如果满了，进行增容 void SeqListPrint(SeqList* ps); //顺序表打印 void SeqListPushBack(SeqList* ps, SLDateType x); // 顺序表尾插 void SeqListPushFront(SeqList* ps, SLDateType x); //顺序表头插 void SeqListPopFront(SeqList* ps); //顺序表头删 void SeqListPopBack(SeqList* ps); //顺序表尾删 // 顺序表查找 int SeqListFind(SeqList* ps, SLDateType x); // 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, int pos, SLDateType x); // 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, int pos);
对数据的管理:增删查改实现
下面是对于顺序表的初始化，销毁，打印，检测空间容量函数的具体实现：
#include "SeqList.h" void SeqListInit(SeqList* ps) { assert(ps); //断言ps是否空指针，assert为断言函数 ps->a = NULL; ps->size = 0; ps->capacity = 0; } void SeqListDestroy(SeqList* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->size = ps->capacity = 0; } void SeqListPrint(SeqList* ps) { assert(ps); for (inti = 0; i < ps->size; ++i) { printf("%d ", ps->a[i]); } printf("%\n"); } void CheckCacpity(SeqList* ps) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //这里巧用三目运算符解决 ps->a = (SLDateType*)realloc(ps->a, newcapacity*sizeof(SLDateType)); ps->capacity = newcapacity; } }
在做完Insert（pos位置插入x）和Erase（删除pos位置x值）函数功能后，对于增删功能我们可以复用Insert和Erase函数，以下几个接口先讲不复用Insert和Erase的实现，最后再讲复用实现：
注：注释选中行为不复用相关实现
尾插尾删
void SeqListPushBack(SeqList* ps, SLDateType x) { //assert(ps); //CheckCacpity(ps); //检查增容 //ps->a[ps->size] = x; //ps->size++; SeqListInsert(ps, ps->size, x); } void SeqListPopBack(SeqList* ps) { assert(ps); //ps->a[ps->size - 1] = 0; //ps->size--; SeqListErase(ps, ps->size - 1); }
头插头删
头插相对于尾插稍多些步骤，因为在表头插入，表中的数据都要往后挪动一位。
void SeqListPushFront(SeqList* ps, SLDateType x) { assert(ps); /*CheckCacpity(ps); int end = ps->size; while (end > 0) { ps->a[end] = ps->a[end - 1]; --end; } ps->a[0] = x; ++ps->size;*/ SeqListInsert(ps, 0, x); } void SeqListPopFront(SeqList* ps) { assert(ps); //int start = 0; //while (start < ps->size-1) //{ // ps->a[start] = ps->a[start + 1]; // ++start; //} //int start = 1; //while (start < ps->size) //{ // ps->a[start-1] = ps->a[start]; // ++start; //} //--ps->size; SeqListErase(ps, 0); }
顺序表查找
因为顺序表本身为数组，查找的实现相对简单，我们从begain位置开始遍历即可：
int SeqListFind(SeqList* ps, SLDateType x) { for (int i = 0; i < ps->size; ++i) { if (ps->a[i] == x) { return i; } } return -1; }
在任意pos位置插入和删除数据
对pos位置的插入和删除，需要注意pos位置必须是在数组的有效范围内。
顺序表在pos位置插入x
实现思路：我们将pos位置之后的数据全部向后挪动（复制)一位(包括原pos位置值），，然后对pos位置进行赋值x（实际是对原pos位置值进行覆盖）
// 顺序表在pos位置插入x void SeqListInsert(SeqList* ps, size_t pos, SLDateType x) { assert(ps); assert(pos <= ps->size); //检查pos位置值是否越界 CheckCacpity(ps); //int end = ps->size - 1; //while (end >= pos) //{ // ps->a[end + 1] = ps->a[end]; // --end; //} int end = ps->size ; while (end > pos) //挪动数据 { ps->a[end] = ps->a[end - 1]; --end; } ps->a[pos] = x; ps->size++; }
顺序表删除pos位置的值
实现思路：我们将pos位置值用后一位数据值进行覆盖，后一位用其后一位的数据值进行覆盖，如此遍历整个pos位置后数据即可
// 顺序表删除pos位置的值 void SeqListErase(SeqList* ps, int pos) { assert(ps && pos < ps->size); //int start = pos; //while (start < ps->size-1) //{ // ps->a[start] = ps->a[start + 1]; // ++start; //} int start = pos+1; while (start < ps->size) //进行数据覆盖 { ps->a[start-1] = ps->a[start]; ++start; } ps->size--; //最后对size标记值减一 }
总结
顺序表的优缺点
优点：顺序表相对于链表拥有连续物理空间，可以实现下标随机访问（随机读取）。
缺点：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
对于实际，我们通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表则选择链式存储。
本节完
