顺序表SeqList（c语言）（动态顺序表）

前言：

顺序表是一种数据结构，是内存中存储数据的一种方式，他的内存连续性使得它有较高的缓存利用率，它在内存中广泛使用，比如数组，就是典型的顺序表。

实现思路：

一般是建立三个文件，test.c（负责测试）、SeqList.c（书写函数）、SeqList.h（负责函数申明和头文件引用和#define定义等等）。

顺序表的函数主要分为：初始化，销毁，打印，头插尾插，头删尾删，pos位置的插入和删除。这里实现的顺表是动态的，不是静态的。动态顺序表一般运用比较广。我们使用结构体来模拟实现这种动态顺序表。

具体实现：

SeqList.h文件：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;int capacity;int size;
}SL;
//初始化与销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
//打印
void SLPrint(SL* ps);
//检查空间
void SLCheckCapacity(SL* ps);
//头插尾插
void SLPushFront(SL* ps, SLDataType x); 
void SLPushBack(SL* ps, SLDataType x);
//头删尾删
void SLPopFront(SL* ps);
void SLPopBack(SL* ps);
//pos插入和删除
void SLInsert(SL* ps, int pos, SLDataType x); 
void SLErase(SL* ps, int pos);

这里包含了结构体创建，函数引用、#define等等

结构体创建

SeqList.c文件：

初始化


void SLInit(SL* ps)
{assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->a == NULL){perror("Malloc Failed");return;}ps->capacity = 4;ps->size = 0;
}

这里你可以把他想成一个指针，使用malloc在堆区动态开辟了一块内存，并把这块内存的起始地址赋值给了a，使用a来维护和调用这块内存。和数组是高低相似的，只不过数组的开辟和收回是由系统完成的，而这里是由你自己开辟和收回。动态开辟的内存有可能失败，所以要检查。在开始的地方为了严谨，有必要加一个assert，防止传一个NULL。

这里初始化开辟的空间也可以#define定义，没必要像我这样写成4，把他写死。下面这样也是很好的。

void SLInit(SL* ps)
{assert(ps);ps->a = (SLDateType*)malloc(INIT_CAPACITY*sizeof(SLDateType));if (ps->a == NULL){perror("Malloc Failed");return;}ps->size = 0;ps->capacity = INIT_CAPACITY;}

销毁

void SLDestroy(SL* ps)
{assert(ps);assert(ps->a);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}

这里销毁是很简单的，直接释放掉，置空就好了。当然，理论上一个空的顺序表销毁是没有意义的。虽然释放掉一个NULL，也不会有什么影响，但是为了严谨还是加一个assert判断是否为NULL。释放完注意把size和capacity赋值为0。

打印

void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}
}

这里打印和数组的打印一样的，c语言打印数组使用for循环，一个一个打印。

头插尾插

这里头插尾插之前需要考虑一个事，空间是否够。如果不够，是需要扩容的。所以我们可以考虑把扩容单独做成一个函数，这里我就是采用的这种做法。

扩容

void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SL* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("Realloc Failed");return;}ps->a = tmp;ps->capacity *= 2;}
}

检查空间是否够，如果有效数据等于容量，那就说明空间不够，需要扩容。使用realloc扩容，

把得到的新地址赋值给a，再把容量改为扩容之后的容量。

头插

void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);int end = ps->size - 1;while (end>=0){ps->a[end+1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}

首先检查扩容，再开始插入，从头部插入一个数据，也就是在下标为0的地址处插入一个数据，需要把原先的数据依次向右边移动。这里用从后往前依次赋值来实现这种效果。如果从前往后复制数据，会丢失数据。

尾插

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}

尾插很简单，只需要检查扩容，再把赋值，再把size(有效数据)++就欧克了

头删尾删

头删

void SLPopFront(SL* ps)
{assert(ps->a);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;}

头删的思路其实把头插的思路反过来就行了，头插是以此向右边移动，从后往前赋值，那我们头删就从前往后赋值，刚好可以把头部的数据通过赋值而实现删除效果。

尾删

void SLPopBack(SL* ps)
{assert(ps->a);ps->size--;
}

尾删很简单，只需把size--，就可以了。这里就不画图了，因为实在简单

pos位置插入和删除

pos位置插入

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size - 1);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end+1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}

pos位置插入和头插一个原理，只不过头插是pos=0而亦。所以我们只用把pos（包括pos）之后的数据向右移动就可以了，pos之前的数据原封不动。

pos位置删除

void SLErase(SL* ps, int pos)
{assert(ps);assert(ps->a);assert(pos >= 0 && pos <= ps->size - 1);int begin = pos+1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}

pos位置删除和头删的思路也是一样的，只不过头删的pos是0，是固定的，而pos位置删除，pos是非固定的而已。所以，我们就照猫画虎，只把pos之后的的数据从前往后向左移动就可以了。pos之前的数据原封不动。

test.c文件：

SL s;
void test1()
{//测试初始化SLInit(&s);//测试头插尾插SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushFront(&s, 3);SLPushFront(&s, 2);SLPushFront(&s, 1);//1 2 3 1 2 3//测试头删尾删SLPopBack(&s);SLPopFront(&s);//2 3 1 2//测试pos位置插入和删除SLInsert(&s, 1, 100); //2 100 3 1 2SLErase(&s, 2);//2 100 1 2
}
int main()
{test1();SLPrint(&s);//测试销毁SLDestroy(&s);return 0;
}

代码：

void SLInit(SL* ps)
{//assert(ps);ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps->a == NULL){perror("Malloc Failed");return;}ps->capacity = 4;ps->size = 0;
}
void SLDestroy(SL* ps)
{assert(ps);assert(ps->a);free(ps->a);ps->a = NULL;ps->capacity = ps->size = 0;
}
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->a[i]);}
}
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){SL* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * ps->capacity * 2);if (tmp == NULL){perror("Realloc Failed");return;}ps->a = tmp;ps->capacity *= 2;}
}void SLPushFront(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);int end = ps->size - 1;while (end>=0){ps->a[end+1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;
}
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);SLCheckCapacity(ps);ps->a[ps->size++] = x;
}
void SLPopFront(SL* ps)
{assert(ps->a);int begin = 1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;}
void SLPopBack(SL* ps)
{assert(ps->a);ps->size--;
}void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size - 1);SLCheckCapacity(ps);int end = ps->size - 1;while (end >= pos){ps->a[end+1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;
}
void SLErase(SL* ps, int pos)
{assert(ps);assert(ps->a);assert(pos >= 0 && pos <= ps->size - 1);int begin = pos+1;while (begin < ps->size){ps->a[begin - 1] = ps->a[begin];begin++;}ps->size--;
}