顺序表的概念及结构

在了解顺序表之前，得先知道一个东西：线性表。线性表（linear list）是n个具有相同特性的数据元素的有限序列。简单理解就是：线性表指的是具有部分相同特性的一类数据结构的集合。例如：蔬菜分为绿叶类、瓜类、菌菇类。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。 如何理解逻辑结构和物理结构？我们去超市买东西的时候，去付款时要排队，假设有很多人，也就意味着我们需要排成一条对去付款。这是在逻辑上就是一条线性的（我们下意识认为，是理想的），但是实际上在站队时不一定是线性的（现实情况）。但是顺序表在逻辑结构和物理结构上都是线性的。这是因为顺序表的底层实现逻辑是数组。我们知道数组在内存上是连续存放的（实际情况）。

注意：顺序表的底层虽然是数组，但是却是在数组的基础之上对数组进行了封装，实现了增删查改的一些功能。

顺序表的分类

我们知道数组有两种：一种是定长数组，也就是空间大小不可变化，是固定的；还有一种是变长数组，这个变长数组是我们用动态内存开辟函数申请来的（注意区分C99中引入的变长数组）。

根据数组的不同，顺序表也分为两种：静态顺序表（大小不可变），动态顺序表（大小可变）。

顺序表的实现 

这两种顺序表一比较，肯定是第二种的优势明显一些，同样在项目中，动态顺序表的应用远远大于静态顺序表。下面我们就来学习动态顺序表的实现。

首先创建三个文件：SeqList.h  —— 顺序表的头文件  SeqList.c  —— 顺序表的实现  test.c——>测试顺序表

顺序表的创建：

typedef struct SeqList
{
	SLDataType* arr;//数组指针
	int size;//记录当前有效的空间大小
	int capacity;//记录当前总空间大小
}SL;//由于struct SeqList太长，比较麻烦，因此就重新定义

由于数组的类型是暂定为int，后续如果要改动的话，不是很方便，因此也是重定义。

typedef int SLDataType;//数组不一定是int类型

顺序表创建完了之后，就得开始实现它的基本功能：增 删 查 改。

在实现上面那些基本功能之前，我们肯定得把这个顺序表进行初始化。 

//初始化顺序表
void InitSeqList(SL* ps)//由于要改变顺序表，所以传地址
{
	ps->arr = NULL;//没为数组分配内存空间
	ps->capacity = 0;
	ps->size = 0;
}

在顺序表中增加数据 

接下来就开始实现增加数据，这个增加稍微有所不同：是在指定的位置增加数据。

我们先来实现两种特殊的情况：头插和尾插。头插是在顺序表的第一个位置（数组下标为0的位置）插入（增加）数据；尾插是在顺序表的有效数据的末尾插入（增加）数据。

首先，来实现头插：（数据从后往前覆盖）

//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给BASE(4)个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}

注意：在比较大型的项目中，我们写一些功能代码时，一定要去检查功能是否完整。比如：这里我们写这个头插功能的代码时，写完之后一定要去打印结果，看看是否满足我们的要求。 

头插写完就开始写尾插了。

//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->capacity == ps->size)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)//还没分配空间
		{
			newcapacity = BASE;
		}
		else
		{
			newcapacity = 2 * ps->capacity;
		}
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}
		ps->arr = tmp;
		tmp = NULL;
		ps->capacity = newcapacity;
	}
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}

通过观察上面两个代码，我们会发现那个判断是否需要增容的部分是一样的，因此我们就可以把这个判断是否需要增容的部分写成一个函数（可以只判断，也可以把增容的部分也写进去）。

那么上面的代码就可以简化成下面的样子。 

//判断是否需要增容（如果需要，则直接自动增容）
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给4个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}


//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}


//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}

两种特殊的插入写完之后，就得开始写指定插入，就是说在指定的位置插入数据。 （和头插一样，从后往前覆盖）

//在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//arr[2] = arr[1]; 
	}
	ps->arr[pos] = x;
	ps->size++;
}

在顺序表中删除数据 

接下来就是删除数据。同样删除数据也根据上面的方式来先实现特殊方式：头删和尾删。 

注意删除数据时，一定要判断是否有数据。

先来看头删。（数据从前往后覆盖）

void SLPopFront(SL* ps)
{
    assert(ps);
    assert(ps->size);//看看有没有数据
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

尾删就比较简单了。 

void SLPopBack(SL* ps)
{
    assert(ps);
    assert(ps->size);
	//ps->arr[size-1] = 0; //这一步可有可无
	ps->size--;
}

接下来就是写在指定位置删除数据。 

在顺序表中查找数据 

最后，我们就要实现在顺序表中查找数据。 

找数据的话，就是简单的循环找就行了。

//在顺序表中查找数据
int SLFind(SL* ps, SLDataType x)
{
    assert(ps);
   	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到
}

上面就是顺序表的全部逻辑以及实现。

顺序表源码

下面是顺序表的源码：

SeqList.c

#include "SeqList.h"

//初始化顺序表
void InitSeqList(SL* ps)
{
	ps->arr = NULL;//没为数组分配内存空间
	ps->capacity = 0;
	ps->size = 0;
}


//销毁顺序表
void SLDestroy(SL* ps)
{
	if (ps->arr)//有可能我们还没有使用（为空）
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}


//打印顺序表
void SLPrint(const SL* ps)//只是打印不想被更改数据
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->arr[i]);
	}
	printf("\n");//可以选择换行，不写也没关系
}


//判断是否需要增容（如果需要，则直接自动增容）
void SLCheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//数组满了
	{
		int newcapacity = 0;
		if (ps->capacity == 0)
		{
			newcapacity = BASE;//如果空间为0，先给4个空间
		}
		else
		{
			newcapacity = 2 * ps->capacity;//扩容后为扩容前的两倍
		}
		//上面这个if...else语句，也可以写成下面这样
		//int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity*sizeof(SLDataType));
		if (tmp == NULL)//扩容失败
		{
			perror("realloc");
			exit(1);//直接退出程序不在执行（异常退出）
			//return 1; //这样写也是可以的
		}
		//扩容成功
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}


//在顺序表的头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	//判断是否需要扩容
	SLCheckCapacity(ps);//ps是一个指针（没有&，因此也是一个值）
	//头插数据
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//size[1] = size[0]; //根据边界来推上面的判断条件
	}
	ps->arr[0] = x;
	ps->size++;
}


//在顺序表的末尾插入数据
void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	//尾插数据
	ps->arr[ps->size++] = x;
	//上面也可以转为下面的写法
	//ps->arr[ps->size] = x;
	//ps->size++;
}


//在指定位置插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	SLCheckCapacity(ps);
	for (int i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
		//arr[2] = arr[1]; 
	}
	ps->arr[pos] = x;
	ps->size++;
}


//删除顺序表头部的数据
void SLPopFront(SL* ps)
{
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}


//删除顺序表尾部的数据
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);
	//ps->arr[size-1] = 0; //这一步可有可无
	ps->size--;
}


//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(ps->size);
	for (int i = pos; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}


//在顺序表中查找数据
int SLFind(SL* ps, SLDataType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
		{
			return i;//找到了，返回x在顺序表中的下标
		}
	}
	return -1;//没找到
}

SeqList.h 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define BASE 4

typedef int SLDataType;//数组不一定是int类型

typedef struct SeqList
{
	SLDataType* arr;//数组指针（）
	int size;//记录当前有效的空间大小
	int capacity;//记录当前总空间大小
}SL;


void InitSeqList(SL* ps);//初始化顺序表

void SLDestroy(SL* ps);//销毁顺序表

void SLPrint(const SL* ps);//打印顺序表的数据

void SLPushFront(SL* ps, SLDataType x);//在顺序表的头部插入数据

void SLPushBack(SL* ps, SLDataType x);//在顺序表的末尾插入数据

void SLInsert(SL* ps, int pos, SLDataType x);//在指定位置插入数据

void SLPopFront(SL* ps);//删除顺序表头部的数据

void SLPopBack(SL* ps);//删除顺序表尾部的数据

void SLErase(SL* ps, int pos);//删除指定位置的数据

int SLFind(SL* ps, SLDataType x);//在顺序表中查找数据

好啦！本期数据结构顺序表的学习就到此为止啦！我们下一期再一起学习吧！