顺序表的概念及其结构
基本概念
顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构，一般情况下采用数组存储，在数组中完成增删查改。如图，它有如下特点:
- 存储空间连续，既允许元素的顺序访问,又可以随机访问
- 要访问指定元素，可以使用索引(下标)来访问，时间复杂度为O(1)
- 要在其中增加或者删除一个元素，都要涉及后面所有元素的向前或向后移动，时间复杂度为O（n）;
- 可以方便的存储表中的任一结点，存储速度快；
- 长度固定，分配内存之前必须知道数组的长度；
- 无需为表示结点间的逻辑关系而增加额外的存储空间，存储利用率提高；
存储结构:
顺序表一般可以分为:
1.静态顺序表:使用定长数组存储；
2.动态顺序表:使用动态开辟的数组存储；
静态分配和动态分配有什么不同?其实就是数组的不同。在静态分配时，我们在编写的时候，就已经确定了数组的大小。而动态分配时，没有确定它的大小，是根据动态分配语句在运行时才将它的大小进行分配。这样有一点好处就是，在静态分配时，当我想要存放顺序表的数据元素超过100时候则会产生错误溢出，而动态分配时，如果一旦超过了分配的空间大小，可以再重新分配一块内存空间，把旧的空间和所增加的数据元素转移到新申请的空间上，这样就不会产生溢出的问题了。这是动态分配的一个优点。
代码如下:
//顺序表的静态存储 #define N 8 typedef int SLDataType; typedef struct SeqList { SLDataType array[N];//定长数组 size_t size;//有效数组的个数 }SeqList; //顺序表的动态存储 typedef int SLDataType; typedef struct SeqList { SLDataType* array;//指向动态开辟的数组 size_t size;//有效数据的个数 size_t capacity;//空间容量的大小 }SeqList; /*注解:我们发现这里用的是指针,指针是存放一个存储单元地址的.顺序表根据第一个数据元素的地址和数据元素的大小,就可以算出任意数据元素的位置.即只定义第一个元素的指针即可，描述整个顺序表。但它仅仅是个地址，没有确切的空间，因此我们使用是要开辟空间; SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType)); 详细代码下面讲解;*/
静态顺序表的定长数组导致N定长，空间开少了不够用，开多了浪费，所以现实中都是使用动态顺序表，使用倍增-复制的办法来支持动态扩容，将顺序表变成了"可变长度"的，下面我将实现动态顺序表；
初始化顺序表
对顺序表进行初始化
void SeqListInit(SeqList* ps) { assert(ps); ps->array = NULL;//顺序表指针NULL ps->size = 0;//起始元素个数为0 ps->capacity = 0;//容量为0 }
销毁顺序表
因为顺序表所用的内存空间是动态开辟在堆区的，所以我们在使用完后需要及时对其进行释放，避免造成内存泄漏。
//销毁顺序表 void SeqListDestory(SeqList* ps) { assert(ps); free(ps->a);//释放顺序表指针指向的空间 ps->a = NULL;//及时置空 ps->size = 0;//元素个数置0 ps->capacity = 0;//容量置0 }
若需要对数据进行保存，可以使用文件操作函数将数据保存到一个文件中，下次使用顺序表的时候先读取文件数据即可
打印顺序表
void SeqListPrint(SeqList* ps) { assert(ps); for (int i = 0; i < ps->size; i++) { printf("%d", ps->array[i]); } printf("\n"); }
增加数据
头插
每一次在顺序表最前方插入，其他数据后移
void SeqListPushFront(SL* ps, SLDataType x) { //如果没有空间，或者空间不足，我们可以增容 if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//对数组进行二倍增容,使用三目运算符是为了防止0这种情况 SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity); //判断是否增容成功 if(tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } //从最后一个元素开始向前遍历到第一个元素，分别将它们向后移动一个位置 for (int i = ps->size - 1; i >= 0; i--) { ps->a[i + 1] = ps->a[i]; } ps->a[0] = x;//将要插入的数据插入到头部 ps->size++;//表长加1 }
尾插
顺序表的末尾增加数据,其他元素不用改变
void SeqListPushBack(SL* ps, SLDataType x) { if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } ps->a[ps->size] = x; ps->size++; }
指定下标位置插入
从最后一个元素开始向前遍历到第指定位置，分别将它们向后移动一个位置
void SeqListInsert(SL* ps, int pos, SLDataType x) { //因为顺序表连续存储,所以首先要判断插入位置是否合法; assert(pos >= 0 && pos <= ps->size); //增容 if (ps->size == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->a = tmp; ps->capacity = newcapacity; } //从最后一个元素开始向前遍历到第指定位置，分别将它们向后移动一个位置 for (int i = ps->size - 1; i >= pos; i--) { ps->a[i + 1] = ps->a[i]; } //将x插入到指定位置 ps->a[pos] = x; //表长加1 ps->size++; }
删除数据
头删
从删除位置遍历到最后一个元素的位置,将他们依次向前移一个位置;
void SeqListPopFront(SeqList* ps) { assert(ps->size > 0); for (int i = 1; i < ps->size; i++) { ps->array[i-1] = ps->array[i]; } ps->size--; }
尾删
将表长减去1即可;
void SeqListPopBack(SL* ps) { assert(ps->size > 0); ps->size--; }
删除指定位置
首先判断指定位置是否合法然后从指定位置的下一个元素依次向前移动一步
void SeqListErase(SL* ps, int pos) { assert(pos >= 0 && pos < ps->size); for (int i = pos + 1; i < ps->size; i++) { ps->a[i - 1] = ps->a[i]; } ps->size--; }
查找数据
顺序表的一端开始，依次将每个元素的关键字同给定值 K 进行比较，直到相等或比较完毕还未找到.
int SeqListFind(SL* ps, SLDataType x) { for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; }
修改数据
//修改指定下标位置元素 void SeqListModify(SeqList* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0 && pos < ps->size);//检查输入下标的合法性 ps->a[pos] = x;//修改数据 }
