前言

本文将介绍数据结构中的线性表与线性表中的顺序表
作为最简单的数据结构，通过本文的学习，你应该可以随意的使用它

一、线性表是什么？

线性表是n个具有相同特征的数据元素的有限序列
其在逻辑结构上是连续存储的，就像一条长长的线
而在实际物理存储中，其并不一定连续，通常以数组与链式结构进行存储

二、顺序表

1.顺序表的介绍

顺序表是一段物理地址连接的存储单元依次存储数据结构的方式。
实际上采用数组存储，并通过对数组实现增删查改来实现对顺序表的增删查改

2.顺序表的定义

代码如下：

typedef int SLDataType;
typedef struct Seplist
{SLDataType *a;
int size;数据个数 
int capacity;容量 
}SL; 

顺序表分为静态存储与动态存储，由于静态顺序表有诸多不便（容量不够，空间浪费…）
所以上示定义直接采用动态顺序表的定义
其中SLDataType为顺序表所存储数据的数据类型，之所以用typedef定义，是为了方便以后在存储新的数据类型时方便修改。

3.对顺序表增删查改函数的定义与实现

对于一个顺序表，我们应实现：初始化，插入数据，删除数据，销毁。
函数定义代码如下：

void SepListFrontInit(SL* ps);//初始化
void SepListPushFront(SL* ps,SLDataType x);//头部增加数据
void SepListPushBack(SL* ps,SLDataType x);//尾部增加数据
void SepListPopFront(SL* ps);//头部删除数据
void SepListPopBack(SL* ps);//尾部删除数据
bool SepList(SL* ps);//判空，为空返回true，不为空返回false
void SepListDestroy(SL* ps);//销毁
int  SepListFind(SL* ps,SLDataType x);//数据的查找,返回值为其在顺序表中的位数（从0开始）
void SepListInsert(SL* psl, int pos, SLDataType x);//在POS位置进行数据插入,不考虑扩容问题
void SepListErase(SL* psl, int pos);//在POS位置删除数据

void SepListInit(SL* ps)//初始化
{	
	assert(ps);//如果地址为空，则中断程序
	ps->size=ps->capacity=0;
	ps->a=NULL;
}

void SepListPushFront(SL* ps,SLDataType x)//头部增加数据
{	
	assert(ps);//如果地址为空，则中断程序
	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");
		return;
		}
		ps->capacity=newcapacity;
	}
	int i=ps->size;
	while(i>0)//对顺序表中数据挪动
	{	
		ps->a[i]=ps->a[i-1];
		i--;
	}
	ps->a[i]=x;
	ps->size++;
}

void SepListPushBack(SL* ps,SLDataType x)//尾部增加数据
{	
	assert(ps);//如果地址为空，则中断程序
	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");
		return;
		}
		ps->capacity=newcapacity;
	}
	//相较于头部插入，其无需挪动数据
	ps->a[ps->size]=x;
	ps->size++;
}

void SepListPopFront(SL* ps)//头部删除数据
{
	assert(ps);//如果地址为空，则中断程序
	assert(ps->size>0);//如果无数据可删，则中断程序
	int i=0;
	while(i<ps->size-1)//对顺序表中数据挪动
	{	
		ps->a[i]=ps->a[i+1];
		i++;
	}
	ps->size--;
}

void SepListPopBack(SL* ps)//尾部删除数据
{
	assert(ps);//如果地址为空，则中断程序
	assert(ps->size>0);//如果无数据可删，则中断程序
	ps->size--;
}

bool SepList(SL* ps)//判空
{
	assert(ps);//如果地址为空，则中断程序
	return ps->size==0;
}

void SepListDestroy(SL* ps)//销毁
{
	assert(ps);//如果地址为空，则中断程序
	ps->size=ps->capacity=0;
	free(ps->a);
	ps->a=NULL;
}

int  SepListFind(SL* ps,SLDataType x)//数据的查找
{
	assert(ps);//如果地址为空，则中断程序
	int i=0;
	while(i<ps->size)
	{
		if(ps->a[i]==x)
		return i;
		i++;
	}
	printf("未查询到X在顺序表中的位数\n");
	return -1;
}

void SepListInsert(SL* psl, int pos, SLDataType x)//在POS位置进行数据插入
{
	assert(ps);//如果地址为空，则中断程序
	assert(ps->size>pos);//如果pos>size，则中断程序
	assert(pos>=0);//如果pos<0，则中断程序
	int i=ps->size;
	while(i>pos)//对顺序表中数据挪动
	{	
		ps->a[i]=ps->a[i-1];
		i--;
	}
	ps->a[i]=x;
	ps->size++;
}

void SepListErase(SL* psl, int pos)//在POS位置删除数据
{
	assert(ps);//如果地址为空，则中断程序
	assert(ps->size>pos);//如果pos>size，则中断程序
	assert(pos>=0);//如果pos<0，则中断程序
	int i=pos;
	while(i<ps->size-1)//对顺序表中数据挪动
	{	
		ps->a[i]=ps->a[i+1];
		i++;
	}
	ps->size--;
}

总结

此文章介绍了线性表的概念，并对线性表中较为简单的一种——顺序表进行了实现
顺序表是数据结构中最简单，最易实现的
希望大家都可以完美的掌握它