1.顺序表的概念
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
1.1 静态顺序表
//静态的顺序表
#define N 10
struct SeqList
{
int a[N];
int size;
};静态顺序表的大小是给定的，不能再变的。不灵活。一般大小未知的不用静态顺序表。
1.2 动态顺序表
//动态的顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;
int size;//存储数据个数
int capacity;//存储空间大小
}SeqList;而动态顺序表的大小是可以改变的，后期通过函数对空间大小进行修改。推荐使用动态顺序表，而且本篇文章就是讲的动态顺序表。
2.顺序表接口的实现
接下来开始实现顺序表，先将要用的到的函数封装到头文件中：
//动态的顺序表
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* a;//指向动态开辟的数组
int size;//存储数据个数
int capacity;//存储空间大小
}SeqList;
void SeqListInit(SeqList* ps1);//初始化顺序表
void SeqListDestroy(SeqList* ps1);//销毁顺序表
void CheckSeqList(SeqList* ps1);//检查空间是否足够，不够会增容
void PrintSeqList(SeqList* psl);//打印顺序表中的内容
void SeqListPushBack(SeqList* ps1, SLDataType x);//尾插
void SeqListPopBack(SeqList* ps1);//尾删
void SeqListPushFront(SeqList* ps1, SLDataType x);//头插
void SeqListPopFront(SeqList* ps1);//头删
//在pos位置插入x
void SeqListInsert(SeqList* ps1, size_t pos, size_t x);
//删除pos位置的数据
void SeqListErase(SeqList* ps1, size_t pos);
//查找数据
int FindSeqList(SeqList* ps1, size_t x);接下来开始实现各种功能：
2.1 初始化、删除函数
//初始化顺序表
void SeqListInit(SeqList* ps1)
{
ps1->size = 0;
ps1->a = NULL;
ps1->capacity = 0;
}
//删除顺序表
void SeqListDestroy(SeqList* ps1)
{
assert(ps1);
free(ps1->a);
ps1->a = NULL;
ps1->size = ps1->capacity = 0;
}
- 在这里要注意，删除顺序表中要free掉指针，因为动态顺序表是动态开辟出的空间，而且在用free函数时可以检测整个运行过程中有没有数组越界的情况！free函数是有这个特点的。不同的环境对函数越界的情况检查方式是不太一样的。编译器对越界错误的检查是随机的，抽查的，也就是说出现了越界问题编译器也不一定会报错。在vs环境中，编译器对越界的检查是比较宽松的。但是不报错就不代表没有错，在学习关于线性表的知识时一定要注意数组越界问题。
?如下是在vs环境下数组越界情况：
?报错的情况
不报错的情况?
2.2 检查线性表是否有足够空间（如果不足扩容）
//检查空间大小
void CheckSeqList(SeqList* ps1)
{
assert(ps1);
if (ps1->size == ps1->capacity)
{
SLDataType* p = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps->capacity * 2);
if (p == NULL)
{
printf("realloc failed\n");
exit(-1);//如果开辟不成功 直接强行退出程序
}
else
{
ps1->a = p;
ps1->capacity *=2 ;
}
}
}
这种方法实际上是不完善的，因为他没有考虑到如果顺序表初始capacity就是0的话怎么处理，如果还按照这种方式就是0*2，还是为0，没有起到如果容量不够扩容的作用。
//完善后的代码
void CheckSeqList(SeqList* ps1)
{
assert(ps1);
if (ps1->size == ps1->capacity)
{
int New_capacity = ps1->size == 0 ? 4 : ps1->capacity * 2;
SLDataType* p = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * New_capacity);
if (p == NULL)
{
printf("realloc failed\n");
exit(-1);
}
else
{
ps1->a = p;
ps1->capacity = New_capacity;
}
}
}?2.3 插入类函数
//头插
void SeqListPushFront(SeqList* ps1, SLDataType x)
{
assert(ps1);
CheckSeqList(ps1);
for (int i = ps1->size; i > 0 ; i--)
{
ps1->a[i] = ps1->a[i - 1];
}
ps1->a[0] = x;
ps1->size++;
}
//尾插
void SeqListPushBack(SeqList* ps1, SLDataType x)
{
assert(ps1);
CheckSeqList(ps1);
*(ps1->a + ps1->size) = x;
ps1->size++;
}
//在pos位置插入x
void SeqListInsert(SeqList* ps1, size_t pos, size_t x)
{
assert(ps1);
CheckSeqList(ps1);
if ((pos - 1) <= (ps1->size - 1))
{
for (int i = ps1->size; i > pos - 1; i--)
{
ps1->a[i] = ps1->a[i - 1];
}
ps1->a[pos - 1] = x;
ps1->size++;
}
else
printf("越界");
}
- 关于尾插和头插比较简单，就是要注意通过调用check函数判断线性表容量是否足够。而且头插实现的方式类似于memmove函数的实现：他们都是从从后向前插入的；(p1)
- 关于在pos位置插入要注意pos一定要小于size或者size-1(依据具体的函数写法而定)，不要越界。实现方式也和头插一样，都是从后向前插；(p2)
- 特殊情况:当pos为0时就是头插，当pos为size时为尾插。
?2.4 删除类函数
//头删
void SeqListPopFront(SeqList* ps1)
{
assert(ps1);
if (ps1->size > 0)
{
for (int i = 0; i < ps1->size - 1; i++)
{
ps1->a[i] = ps1->a[i + 1];
}
ps1->size--;
}
}
//尾删
void SeqListPopBack(SeqList* ps1)
{
assert(ps1);
if (ps1->size > 0)
{
ps1->size--;
}
}
//删除pos位置的数据
void SeqListErase(SeqList* ps1, size_t pos)
{
assert(ps1);
if (ps1->size > 0)
{
for (int i = pos-1; i < ps1->size-1; i++)
{
ps1->a[i] = ps1->a[i + 1];
}
ps1->size--;
}
}
- 删除函数切记一点，一定要在顺序表数据含量size大于0的情况下删除数据，如果不注意的话很有可能造成程序出现bug；
- 头删和删除pos位置的数据函数的实现方式都是从前向后移；(p3)
- 特殊情况：当pos为0时就是头删，pos为size时为尾删。
?2.5 查找函数
int FindSeqList(SeqList* ps1,size_t x)
{
assert(ps1);
for (int i = 0; i < ps1->size; i++)
{
if (ps1->a[i] == x)
return i;
}
return -1;
}