C语言版本数据结构03：顺序表+链表

今天我们来学习数据结构的第一个顺序结构：顺序表和链表。

1.线性表

线性表是我们要学的第一个结构，我们知道一串连续的数字或者字符想要在内存中存储可以用数组，但是我们又知道数组是静态的，那么如果我想要对这组数据进行增删查改呢？这就显现出线性表的意义了，我们先来看一下线性表的定义吧。

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结 构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物 理上存储时，通常以数组和链式结构的形式存储。

 那么线性表总共分为两类：一个是顺序结构的线性表（顺序表），所谓有顺序也就是我们常说的数组的形式，是用一段物理地址连续的存储单元依次存储数据元素的线性结构；还有一种是链式结构的线性表（链表），每个存储数据的节点额外还要有一个指针来存储此节点的下一个，那么我来用图片的方式帮助大家理解。

2.顺序表

概念讲解

讲完了它们的基本结构，那我们该如何实现一个顺序表结构呢？它应该包含哪些元素呢？我们来梳理一下，首先一个数组是必不可少的，其次我们还需要一个变量来存储数组的大小，有了这些我们就可以利用结构体将这两个元素合成为一个顺序表的结构。

//静态顺序表
#define N 10
typedef int SLDataType;
//将数据类型定义成一个新类型，这样如果以后想改只改这里就好
typedef struct SeqList
{
    SLDataType arr[N];
    size_t size;       
}SL;//结构体重命名

我们可以看到一个静态的顺序表就初始化好了，为什么叫静态呢？因为我们宏定义了N为10，这样当我们用SL创建了一个变量，它再内存中就会像是这样：

因为是静态结构，所以只能存储10个数据，如果有更多的数据那只能更改宏定义的N了，但是顺序表有静态的就有动态的，我们再来看看动态的顺序表是如何定义的吧：

typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* a;
    size_t size;
    size_t capacity;
}SL;

这样以来的话虽然直比上面的静态结构多了一个变量，但是顺序表做到了动态增长，按需索取，如果存储数据到达了capacity的极限，我们只需要调用动态内存开辟函数来继续为我们开辟空间。

接口实现

大家可能对接口二字比较陌生，所谓接口也可以理解为我们自己封装的函数，那么一个顺序表结构需要哪些接口呢？（以动态顺序表为例，静态顺序表有局限，所以我们只做了解）

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
     SLDataType* array; // 指向动态开辟的数组
     size_t size ; // 有效数据个数
     size_t capicity ; // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

我们看到对于一个完整的顺序表来说最基本的接口就这些，初始化销毁必不可少，而对于数据我们必须要有增删查改的功能，还有打印功能，删除指定位置的值，返回指定位置的值，在某位置删除，某位置插入值等等，那我们就来依次完成这接口吧。

void SeqListInit(SL* ps)//初始化函数
{
	ps->a = NULL;//将a指向的空间设为空，代表对于a的初始化
	ps->size = 0;//size和capacity都设置为0，
	ps->capacity = 0;
}
void SeqListDestory(SL* ps)//销毁函数
{
	free(ps->a);//释放a指向的空间，并且size和capacity都置0
	ps->size = 0;
	ps->capacity = 0;
}
void SeqListCheckCapacity(SL* ps)//检查内存函数
{
	if (ps->size == ps->capacity)
	{
		//没有空间or空间满了
		//扩容
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * (sizeof(SLDataType)));//内存开辟函数，当没有开辟内存时，malloc和realloc功能一样
		if (tmp == NULL)//如果开辟失败，要给予提醒
		{
			//realloc失败
			printf("realloc fail");
			exit(-1);
		}
		//扩容成功
		ps->a = tmp;//将新的空间赋值给a
		ps->capacity = newcapacity;//赋值新的内存
	}
}
void SeqListInsert(SL* ps, int pos, SLDataType x)//插入数据函数
{
	assert(pos <= ps->size && pos >= 0);//首先判断ps不可为空
	//if (pos > ps->size || pos < 0)
	//{
	//	printf("pos invalid");
	//	return;
	//}
	SeqListCheckCapacity(ps);//检查内存，如果内存不够用及时扩容
	int end = ps->size - 1;//对于数组来说，最后一个元素的下标是整体大小的-1
	//挪数据
	while (end >= pos)//在某处插入数据后其后面的数据都要向后移动
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;//插入数据
	ps->size++;//调整大小
}
void SeqListErase(SL* ps, int pos)//删除数据函数
{
	assert(pos < ps->size&& pos >= 0);
	int begin = pos + 1;//用一个变量来保存要删除位置的后一个
	while (begin < ps->size)//删除掉该元素后其后面的元素都要向前挪动一个
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;//调整空间
}
void SeqListPushBack(SL* ps, SLDataType x)//尾插
{
	SeqListCheckCapacity(ps);

	//ps->a[ps->size] = x;
	//ps->size++;
	SeqListInsert(ps, ps->size, x);
    //直接调用Insert函数即可，由于尾插只能在最后一位插入，所以pos传入ps->size即可
}
void SeqListPopBack(SL* ps)//尾删
{
    assert(ps->size > 0);
	//if (ps->size > 0)
	//{
	//	//ps->a[ps->size - 1] = 0;
	//	ps->size--;
	//}
	//ps->size--;
	SeqListErase(ps, ps->size-1);//直接调用Erase函数
}
void SeqListPushFront(SL* ps, SLDataType x)//头插
{
	SeqListCheckCapacity(ps);//插入前先要判断内存，没有内存的话要及时增容
	挪数据
	//int end = ps->size - 1;
	//while (end >= 0)
	//{
	//	ps->a[end + 1] = ps->a[end];
	//	end--;
	//}
	//ps->a[0] = x;
	//ps->size++;
	SeqListInsert(ps, ps->size, x);
}
void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size > 0);
	//int begin = 0;
	//while (begin < ps->size - 1)
	//{
	//	ps->a[begin] = ps->a[begin + 1];
	//	begin++;
	//}
	//ps->size--;
	SeqListErase(ps, 0);
}
int SeqListFind(SL* ps, SLDataType x)//找出数据下标的函数
{
	assert(ps->size > 0);
	while (ps->size--)
	{
		if (ps->a[ps->size] == x)
		{
			return x;
		}
	}
	return -1;
}
void SeqListPrint(SL* ps)//打印函数
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

实现了这些接口后，相信大家已经对顺序表已经有了一个大概的了解，接下来有几个问题需要大家考虑：

1. 中间/头部的插入删除，时间复杂度为O(N) 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们 再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

想过这些问题后，大家有没有觉得其实顺序表虽说在某些方面是有它的优势，但是也有一定的缺陷，那么我们就引出我们今天的第二个结构：链表，我们一起来看看链表是如何实现的，再来比较一下链表和顺序表他们的优劣。

3.链表

链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

如我们上面画的图一般，链表之所以叫做链表是因为它不同于顺序表的是它是一个个结点链接而成的，而链接它们的就是后一个结点的地址，我们知道其实在物理层面它们并没有被链接在一起，根本没有这个“链子”，这只是我们想出来的，我们可以拿现实生活中的火车来理解这一例子。

链表的分类

我们所画的呢，是一种用处非常广的单链表，我们学习数据结构最先接触的也是单链表，但是我想告诉大家的是链表其实有很多形式：单链表，双向链表，带头结点的单链表双链表等，循环单链表，循环双向链表等等。 

有这么多的形式，我们用的最多的还是无头不循环单链表和带头循环双向链表，取了两个极端，这样的话链表的所有功能我们都可以实现了。

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向 循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而 简单了，后面我们代码实现了就知道了。

链表的实现

typedef int SLDataType;

typedef struct SListNode
{
	SLDataType data;//存数据
	SLTNode* next;//存下一个结点的地址
}SLTNode;

//单链表要实现的接口
void SListPrint(SLTNode* phead);
void SListInit(SLTNode* phead);
void SListPushBack(SLTNode** pphead, SLDataType x);
void SListPopback(SLTNode** pphead);
void SListPushFront(SLTNode** pphead, SLDataType x);
void SListPopFront(SLTNode** pphead);
SLTNode* SListFind(SLTNode* phead,SLDataType x);
void SListInsert(SLTNode* phead,SLTNode* pos,SLDataType x);
void SListErase(SLTNode** pphead, SLTNode* pos); SLTNode* SListFind(SLTNode* phead, SLDataType x);
void SListDestory(SLTNode* phead);

实现的话就留给大家自己实现了，可以按照上面顺序表的方式来完成这些接口的实现。

双向链表的结构也给大家

typedef int LTDataType;
typedef struct ListNode
{
 LTDataType _data;
 struct ListNode* next;
 struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

4.链表和顺序表的区别

我们学完链表后，我们来看看它们之间有什么区别吧

 好了，关于顺序表和链表的知识就到这里，我们下次再见。