C语言编程简单却重要的数据结构顺序表全面讲解_C/C++

前言

本文主要介绍顺序表的定义和常见静态顺序表的用法。

一、线性表定义

线性表（line list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串。
线性表在逻辑上是线性结构，也就是说是连续的一条直线。但在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储

二、顺序表实现

1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可表示为：

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

我们以简单的静态顺序表进行引例（与动态顺序表接口函数思想是一样的）
代码如下（示例）：

#define N 10//这里定义宏是为了方便将来如果需要更改空间的大小，而代码中用到的10过于多要更改多次，宏定义直接改N大小即可
typedef int SQDataType;//这里顺序表10个空间都是int型，如果将来要改变类型，可以在这里把int改为所需类型
struct SeqList//单个数据直接定义变量，多个数据定义结构体
{
	SQDataType a[N];//顺序表有10个空间可进行存储
	int size;//顺序表存了几个数据（有10个空间不一定就存10个数据）
};

ps:顺序表的一些要求：
1.连续的物理空间存储-用的是数组
2.数据必须是从头开始，依次存储

2静态顺序表

2.1实现顺序表接口，第一步要对顺序表进行初始化

代码如下（示例）：

#include<stdio.h>
#include<string.h>//memset函数头文件
//增删查改等接口函数
void SeqListInit(struct SeqList *ps)
{
	memset(ps->a, 0, sizeof(SQDataType)*N);//memset是一个初始化函数
	//sl.a表示按字节初始化
	//0表示初始化为0
	//sizeof(SQDataType)表示数组内每个元素大小(之前定义了SQDataType=int)，N表示数组内共有N个元素，两者相乘是数组大小
	ps->size = 0;
}
void TestSeqList1()
{
	struct SeqList sl;//sl是实参，上面的ps是形参,为了实参和形参可以相互影响，这里用的是传址调用
	SeqListInit(&sl);
}
int main()
{
	TestSeqList1();
	return 0;
}
//ps:如果这里你觉得写struct SeqList sl烦，你可以这样改进代码（这里和2.1代码对应）
//typedef struct SeqList//单个数据直接定义变量，多个数据定义结构体
//{
//	SQDataType a[N];//顺序表有10个空间可进行存储
//	int size;//顺序表存了几个数据（有10个空间不一定就存10个数据）
//}SL;
//这样结构体类型就可以直接写成SL

2.2对顺序表的增删查改的接口函数（以尾插为例）

void SeqListPushBack(struct SeqList *ps, SQDataType x)//尾插
{
	if (ps->size >= N)
	{
		printf("SeqList is full");//防止你尾插太多已经大于了顺序表最大容量
		return;
	}
	ps->a[ps->size] = x;
	ps->size++;//存储的数据多了一个，size加1个
}

乍一看代码比较晦涩难懂，我们用图来理解一下这个代码：

C语言编程简单却重要的数据结构顺序表全面讲解

（图片来自比特就业课）

图示顺序表有7个空间，我们放了5个数据，现在要在尾部插入一个数据，该数据下标是5，而ps->size=5（结构体指针相关知识见笔者结构体文章）所以a[5]也就是a[ps->size]恰好是尾部后一个元素，这里的5改成其他数也是同样的道理。

ps->a[ps->size]=x，也就是对尾部后一个元素赋值。

ps->size++是表示顺序表存储的数据又多了一个（原本认定顺序表存储5个数据，你现在添加了一个，认定存储几个数据也要再加1个）
而你在尾插的过程中，可能插入数据多了，甚至多于数组最大容量，这肯定会有问题，所以我们用了一个if进行判断一下。

到这里大家可能就会发现了，在使用静态链表有两个不方便的地方：
1.数组给的空间小了，可能不够用
2.数组给的空间大了，可能浪费空间

3动态顺序表

3.1动态顺序表初始化

代码如下（示例）：

typedef int SQDataType;
struct SeqList
{
	SQDataType*a;
	int size;//有效数据个数
	int capacity;//容量
};
//由于没有数组a了，所以顺序表初始化也要改一下
void SeqListInit(struct SeqList *ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

C语言编程简单却重要的数据结构顺序表全面讲解

（图片来自比特就业课）

3.2动态顺序表-尾插

代码如下（示例）：

void SeqListPushBack(struct SeqList *ps, SQDataType x)
{	
	if (ps->size == ps->capacity)//原先空间满了，无法进行尾插了，需要进行扩容（扩容一般扩2倍）
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;//这个4是可以换其他数的
		//这里是防止原来的容量是0，扩容后的倍数仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止扩容失败，也就是没有剩余空间供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);//退出运行
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	ps->a[ps->size] = x;
	ps->size++;//存储的数据多了一个，size加1个
}

我们在扩容时，是用一个扩容一个吗？这样太浪费时间，一般是扩容所需要的空间的两倍，realloc函数可对指针指向的空间进行扩大或缩小，感兴趣的同学自行了解，这里不作深究。

3.3动态顺序表-头插

了解过尾插，这里讲头插也很容易理解，就是在最前面插入一个内容，如何操作呢？把已有的内容全部向后移动一位，然后最前面会空出一个空间，然后你放入内容
代码如下（示例）：

void SeqListPushFront(struct SeqList *ps, SQDataType x)
{
//原先空间满了需要进行扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;
		//这里是防止原来的容量是0，扩容后的倍数仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止扩容失败，也就是没有剩余空间供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	int end = ps->size - 1;//确定最后一个内容下标
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];//以此把原先的内容往后挪一位
		--end;
	}
	ps->a[0] = x;//把需要插入的内容放在最开始的空间
	ps->size++;
}

这里需要注意的是，头插和尾插都面临一个空间已经满的情况，如果满了都需要扩容，这个不要忘记。如果你嫌麻烦每次都要写扩容，你可以写一个扩容函数，用的时候调用一下即可。

3.4动态顺序表-尾删

代码如下（示例）：

void SeqListPopBack(struct SeqList *ps)
{
	assert(ps->size > 0);
	//要进行删除，首先要有东西可删
	//这里会进行断言，如果没有东西删会报错
	ps->size--;
}

这里为什么size- -即可完成尾部数据的删除？解释是这样的，size- -后，电脑认为的有效数据就少了一个，不管你那个数据还在不在，电脑已经认为它不再是一个所需的数据了，使用顺序表时不会对无效数据进行考虑。

3.5动态顺序表-头删

头删也就是把最前面的数据删除，其他数据下标依次减1即可
代码如下（示例）：

void SeqListPopFront(struct SeqList *ps)
{
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

3.6动态顺序表-任意位置插入数据

我们以下面这个顺序表举例

C语言编程简单却重要的数据结构顺序表全面讲解

我们要在1和2中间插一个数据怎么办？0和1不变，2和3分别向后移
但是考虑到其他的顺序表，假设它原来的数据已经占满了所有空间，你再插是不是有可能空间不够，还有一点，虽说是任意位置插入数据，你能不能在顺序表尾部插入？非法访问了属于是。考虑上面几点，我们有下面的代码。

void SeqListInsert(struct SeqList *ps, int pos, SQDataType x)
//pos表示插入位置的下标
{
	assert(pos < ps->size);//防止在尾部插入构成非法访问
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

3.7动态顺序表-任意位置删除数据

我们仍以下面的图举例，要将2删除怎么办？把3往前挪一位即可。

C语言编程简单却重要的数据结构顺序表全面讲解

void SeqListErase(struct SeqList *ps, int pos)
{
	assert(pos < ps->size);
	int start =pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}