数据结构——顺序表

🐨0. 前言

• 线性表是一种最常用且最简单的一种数据结构。简单来说线性表是n个具有相同特性的数据元素的有序序列，即存在唯一的开始元素和一个终止元素，除开始元素和终止元素外，每个元素都有一个前驱元素和一个后继元素。
• 线性表是一种在实际中广发使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串…
• 线性表是在逻辑上是线性结构，但在物理结构上不一定连续，线性表在物理上存储时，通常以数组和链式结构的形式进行存储。

本篇文章则讲解的是顺序表。

🎈1. 顺序表的概念及定义

顺序表指的是用一组地址连续的存储单元依次存储元素的线性结构，一般情况采用数组存储。
数组存储的是类型相同的元素，那顺序表，则完全符合要求。所以我们的顺序采用数组来进行存储。

顺序表可分为两种：

1. 静态顺序表：使用定长数组存储元素。
2. 动态顺序表：使用开辟动态的数组存储。

那么用哪种更好一点呢？如果用静态顺序表存储，假设指定数组的长度为1000，那么如果想要存放2000个数据，则无法存放；那假设指定长度为2000，那确实可以存放2000个数据，但是，如果我们只存储100个数据呢？这是不是就造成了空间的浪费。这使得我们十分难受，开多了资源浪费，开少了不够用。动态顺序表则可以很好的解决这个问题，可以按需申请。本篇主要讲解的动态顺序表的实现。

🪁2. 接口的声明

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//动态顺序表
typedef int SLDateType;
#define INIT_CAPACITY 4 //初始化容量
typedef struct SeqList
{SLDateType* a;SLDateType size;//有效数据个数SLDateType capacity;//空间容量
}SL;//增删查改//初始化顺序表
void SLInit(SL* s); 
//销毁顺序表
void SLDestroy(SL* s);
//打印顺序表
void SLPrint(SL* s);
//尾插
void SLPushBack(SL* s, SLDateType x);
//尾删
void SLPopBack(SL* s);
//头插
void SLPushFront(SL* s,SLDateType x);
//头删
void SLPopFront(SL* s);
//指定位置插入
void SLInsert(SL* s, int pos, SLDateType x);
//指定位置删除
void SLErase(SL* s, int pos);
//查找元素
int SLFind(SL* s, SLDateType x);

这个顺序表不是结构体，而是结构体里面的a，指向了顺序表向内存申请的空间，size表示当前顺序表里面已经存放了多少个数据，capacity表示当前顺序表的总容量。

🪄3. 接口的实现

🍅3.1 为何使用断言？

这里如果传空指针，程序会继续执行，那么最后会挂掉。然而我们不知道程序是在哪出错，还得一步一步调试找出问题。使用断言则会直接报错，并告诉我们错误所出现的位置。

使用断言的好处：
帮助程序员发现并修复程序中的错误，提高代码质量和可读性，同时也可以帮助程序员更好地设计程序，提高程序的正确性和可靠性。

🍒3.2 初始化与销毁

//初始化
void SLInit(SL* s)
{aassert(s);s->a = (SLDateType*)malloc(sizeof(SLDateType) * INIT_CAPACITY);if (s->a == NULL){perror("malloc fail");return;}s->size = 0;s->capacity = INIT_CAPACITY;
}//销毁顺序表
void SLDestroy(SL* s)
{assert(s);free(s->a);s->a = NULL;s->capacity = 0;s->size = 0;
}

🍓3.3 尾插与尾删

//容量检查
void SLCheackCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){//扩容//用临时变量接收，防止扩容失败，导致之前的数据丢失SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * 2 * ps->capacity);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}
}//尾插
void SLPushBack(SL* ps, SLDateType x)
{assert(ps);//检查容量SLCheackCapacity(ps);ps->a[ps->size] = x;ps->size++;
}//尾删
void SLPopBack(SL* ps)
{assert(ps->size);ps->size--;
}

📝小贴士：
1.因为是动态顺序表，所以每次添加数据的时候需要确实容量是否够用。
2.在进行尾删的时候，如果顺序表里面，没有内容，则不必进行删除，所以需要断言判断，顺序表里面是否还有数据。

🍉3.4 头插与头删

//头插
void SLPushFront(SL* ps, SLDateType x)
{assert(ps);SLCheackCapacity(ps);int end = ps->size - 1;while (end >= 0){//将顺序表元素往后偏移ps->a[end + 1] = ps->a[end];end--;}//直接覆盖ps->a[0] = x;ps->size++;
}//头删
void SLPopFront(SL* ps)
{assert(ps);assert(ps->size > 0);int start = 0;while (start < ps->size-1){ps->a[start] = ps->a[start+1];start++;}ps->size--;
}

头插和头删，每次都需要挪动数据，效率比较低，由此看来，顺序表并不是很适合头插与头删。

头插/头删时间复杂度：O(n²)
尾插/尾删时间复杂度：O(n)

🍹3.5 指定位置插入与删除

//指定位置插入
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);assert(pos >= 0 && pos <= ps->size);SLCheackCapacity(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(pos >= 0 && pos < ps->size);int start = pos;while (start < ps->size - 1){ps->a[start] = ps->a[start + 1];start++;}ps->size--;
}

其实当我们实现指定位置插入删除之后，那么就可以取代我们前面写的头插（删）、尾插（删）。

//尾插
SLInsert(ps, ps->size, x);
//尾删
SLErase(ps, ps->size - 1);
//头插
SLInsert(ps, 0, x);
//头删
SLInsert(ps, 0, x);

🥂3.6 查找元素

//查找元素
int SLFind(SL* ps, SLDateType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->a[i] == x){return i;}}return -1;
}

🥊4. 接口测试

我们在实现各个接口功能的时候，如果一次性写完，这很难以保证不出bug，所以我们可以编写边测试，以便于我们更清楚的知道程序每个功能是否完善。

#include"SeqList.h"void TestSeqList1()
{SL s;//初始化测试SLInit(&s);//尾插测试for (int i = 0; i < 10; i++){SLPushBack(&s, i);}SLPrint(&s);//尾删测试for (int i = 0; i < 10; i++){SLPopBack(&s);}SLPrint(&s);//头插测试for (int i = 0; i < 10; i++){SLPushFront(&s, i);}SLPrint(&s);//头删测试/*for (int i = 0; i < 10; i++){SLPopFront(&s);SLPrint(&s);}*///指定插入测试for (int i = 0; i < 5; i++){SLInsert(&s, i+1, i);}SLPrint(&s);//指定删除测试SLErase(&s, 2);SLPrint(&s);SLErase(&s, 3);SLPrint(&s);//查找元素测试printf("%d\n", SLFind(&s, 5));
}int main()
{TestSeqList1();return 0;
}