小伙伴们好啊！
今天开设了数据结构专栏，我会定期更新数据结构知识点，更完为止！一起来学习吧！

一、顺序表

1.1概念及结构

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

1.1.1静态顺序表

所谓静态，就是说用来存储元素的数组的长度是固定的，不能减小或增大。

#define N 7//给数组设定长度
typedef int SLDataType;//对int重命名，方便以后的代码中改变存储数据的类型
typedef struct SepList
{
	SLDataType array[N];//创建定长数组
	int size;//用来记录有效信息的个数
}SepList;

对于静态的顺序表，它的定义和使用比较简单，但是它的缺点是开辟的空间是固定的，很可能出现空间不够用或空间浪费的情况。

1.1.2动态顺序表

动态就是可以改变存储数据的数组的大小，即使用动态开辟的数组存储数据。

typedef int SLDataType;
typedef struct SepList
{
	SLDataType* array;//指向动态开辟的数组
	int size;//有效信息的个数
	int capacity;//目前数组中能存储数据的个数
}SepList;

动态表虽然比静态表稍稍复杂那么一点儿，但是却很好地解决了空间可变性不强的问题，可以对空间随时增容。

1.2动态顺序表接口实现

这里我列举了10个大家会经常用到的接口类型，学会了这10种接口就可以应对学校里的课程设计中的很多功能的实现了！
下面就来一一学习吧！

1.2.1初始化

初始化过程中需要将指向存储数据的数组的指针先指向空，并将容量和有效数据的个数都初始化为0.

#include 

typedef int SLDataType;
typedef struct SepList
{
	SLDataType* array;
	int size;
	int capacity;
}SepList;

void InitSepList(SepList* p)
{
	//在初始化中将指向数组的指针指向空，将容量和有效数据个数初始化为0
	p->array = NULL;
	p->size = 0;
	p->capacity = 0;
}
int main()
{
	SepList sep;
	InitSepList(&sep);
	return 0;
}

因为在初始化过程中要对结构体内容进行改变，所以要采用传址的方法。在其他的需要改变内容的接口中也要传址哦！

1.2.3检查顺序表空间是否已满

在存储数据时，首先要检查所给数组是否已经存满，若存满，就要对其扩容，所以在进行后面的插入操作之前必须要进行这一步！

void CheckCapacity(SepList* p)
{
	if (p->capacity == p->size)
	{
		//判断当前容量是否为0，若为0，则先开辟四个结构体空间，若不为0，则将空间扩大两倍
		int NewCapacity = p->capacity == 0 ? 4 : p->capacity * 2;
		//将开辟后的空间的地址赋给tmp
		SLDataType* tmp = realloc(p->array, sizeof(SLDataType) * NewCapacity);
		if (tmp == NULL)//判断开辟空间是否成功
		{
			printf(\"Realloc failed\\n\");
			exit(-1);
		}
		else
		{
			//将新的空间赋给array
			p->array = tmp;
			p->array = NewCapacity;
		}
	}
}

那么到底开辟空间是否成功呢？接下来通过调试看一下


可见开辟空间成功

1.2.4头插

头插顾名思义就是在顺序表的开头，也就是第一个元素的位置插入一个元素。相应的，顺序表中所有的元素都要向后挪动一个位置。

void SepListPushFront(SepList* p, int val)
{
	assert(p);
	CheckCapacity(p);//先检查是否已满，若满，则进行增容
	int end = p->size - 1;//得到最后一个元素的下标
	while (end >= 0)
	{
		//将元素从后向前依次挪动
		p->array[end + 1] = p->array[end];
		end--;
	}
	p->array[0] = val;//将第一个元素改为需要插入的元素
	p->size++;
}

1.2.5尾插

与头插相比，尾插就简单多了，直接在最后一个元素的下一个元素的位置插入需要插入的元素即可。

void SepListPushBack(SepList* p, int val)
{
	assert(p);
	CheckCapacity(p);
	p->array[p->size] = val;//直接在最后一个元素后面插入元素
	p->size++;//再将size的大小+1
}

1.2.6头删

头删就是删除第一个元素，也就是将数组中元素从前向后依次向前挪动一个位置，用后面的元素覆盖前面的元素，如此就可以达到删除第一个元素的效果。

void SepListPopFront(SepList* p)
{
	assert(p);
	if (p->size > 0)
	{
		//判断该数组是否具有首元素，是否需要头删
		int begin = 1;
		while (begin < p->size)
		{
			//将元素依次向前挪动，覆盖前面的元素
			p->array[begin - 1] = p->array[begin];
			begin++;
		}
		p->size--;//将有效数据个数-1
	}
}

1.2.7尾删

与头删相同，尾删与尾插相比也要简单一点。直接将有效元素的个数-1即可。

void SepListPopBack(SepList* p)
{
	assert(p);
	if (p->size > 0)
		p->size--;
}

1.2.8在指定位置插入

若要在下标为pos处插入元素val，则需要将pos及后面的元素从后向前依次向后挪动一个位置，再将pos处的值改为val，最后将size+1即可。

void SepListInsert(SepList* p, int pos, int val)
{
	assert(p);
	CheckCapacity(p);
	int end = p->size - 1;
	while (end > pos)
	{
		//将pos及后面的元素向后挪动
		p->array[end + 1] = p->array[end];
		end--;
	}
	p->array[pos] = val;//改变pos处的值
	p->size++;
}

1.2.9在指定位置删除

删除比插入简单那么一丢丢，只需将pos后面的元素向前挪动一个位置，覆盖前面的元素，再将size-1即可。

void SepListErase(SepList* p, int pos)
{
	assert(p);
	assert(pos < p->size);//判断pos处是否为有效数据
	int begin = pos + 1;
	while (begin < p->size)
	{
		//将pos后面的元素依次向前挪动
		p->array[begin - 1] = p->array[begin];
		begin++;
	}
	p->size--;
}

1.2.10打印

打印应该是这几个功能中最简单的了，只需遍历数组，将数组中元素一一打印出来即可。

void Print(SepList* p)
{
	for (int i = 0; i < p->size; i++)
	{
		printf(\"%d \", p->array[i]);
	}
	printf(\"\\n\");
}

二、单链表

2.1概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表中的每一个元素不要求在内存中连续存储，各个元素都可以分布在内存中的任意位置，结点与结点之间通过指针可以找到彼此，也就可以无形地串联起来。

而链表中的每个结点通常都包含两部分----数据存储部分和下一个结点的地址存储部分

注意：

1、链式结构在逻辑上是连续的，但是在物理上不一定连续。
2、现实中的结点一般都是从堆区中申请的。
3、从堆区中申请的空间是按照一定策略分配的，它们的内存位置可能连续，也可能不联系。

下面，我们来定义一个单链表的结构体：

typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;//用于存储数据
	struct SListNode* next;//存放下一个节点的地址
}SLTNODE;

2.2接口实现

单链表的接口类型和顺序表是一样的，但其定义和使用又有一些区别，下面就来学习单链表吧！✨

2.2.1创建结点

创建结点也可以理解为开辟新的空间，即增长链表的长度，并对其进行初始化。

SLTNODE* CreateNode(SLTDataType val)
{
	SLTNODE* newnode = (SLTNODE*)malloc(sizeof(SLTNODE));//为结点开辟一个结构体大小的空间
	newnode->data = val;//将结构体中存入指定数据
	newnode->next = NULL;//将指向下一个结点的指针指向空
	return newnode;//返回创建的结点的地址
}

2.2.3查找

在上面的顺序表中，我们多次用到了查找功能。相同的，单链表也需要多次查找操作。所以我们对这个功能进行一次封装，以便后面调用。

SLTNODE* SListFind(SLTNODE* phead, SLTDataType val)
{
	SLTNODE* plist = phead;//获得第一个结点的位置，依次向后查找
	while (plist != NULL)//判断结点是否为空
	{
		if (plist->data == val)//判断该结点中所存数据是否为val
		{
			return plist;//如果找到，就返回该结点的位置
		}
	}
	return NULL;//若找不到，则返回空
}

2.2.4头插

要实现头插，就要将现在的phead指向新开辟的那一个结点，然后将新开辟的结点的next指向现在的第一个结点。

void SListPushFront(SLTNODE** pphead, SLTDataType val)
{
	SLTNODE* newnode = CreateNode(val);
	pnew->next = *pphead;
	*pphead = newnode;
}

2.2.5尾插

尾插需要将最后一个结点的next指向新开辟的空间，然后将新开辟的空间的next指向NULL。但是注意，如果链表结点数为0，则相当于直接将phead指向新开辟的空间。

void SListPushBack(SLTNODE** pphead, SLTDataType val)
{
	SLTNODE* newnode = CreateNode(val);
	if (*pphead == NULL)
	{
		//判断链表的结点数是否为0
		*pphead = newnode;
	}
	else
	{
		SLTNODE* tail = *pphead;//先将尾结点指向phead
		while (tail->next != NULL)
		{
			//寻找最后一个结点，将其地址赋给tail
			tail = tail->next;
		}
		tail->next = newnode;//将尾结点的next指向新开辟的结点
	}
}

2.2.6头删

要达到头删的效果，就需要将phead指向
phead->next，再将最初的phead释放掉。
切记，不可先释放phead，否则将无法找到后面的结点！

void SListPopFront(SLTNODE** pphead)
{
	assert(*pphead);
	SLTNODE* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

2.2.7尾删

尾删要考虑的情况比头删多一点
首先，链表结点数为0时，不删。
第二，链表只有一个结点时，直接将phead释放即可。
第三，有两个及以上结点个数时，用两个指针分别指向尾结点和尾结点前面的一个结点，将尾结点释放之后，将前面的一个结点记为尾结点。

void SListPopBack(SLTNODE** pphead)
{
	assert(*pphead);//排除链表为空的情况
	if ((*pphead)->next == NULL)
	{
		//若链表只有一个结点，则直接将其释放
		free(*pphead);
		*pphead = NULL;
	}
	//链表有两个及以上结点时
	SLTNODE* prev = NULL;
	SLTNODE* tail = *pphead;
	while (tail->next != NULL)
	{
		//找到尾结点和尾结点的前一个结点
		prev = tail;
		tail = tail->next;
	}
	free(tail);//释放尾结点
	prev->next = NULL;
}

2.2.8在指定位置插入

需要注意的是，插入时也有两种情况
当需要插入的位置是第一个结点时，则变为头插
当需要插入的位置不是第一个结点时，将phead指向新开辟的结点，将新开辟的结点的next指向原来的第一个结点

void SListInsert(SLTNODE** pphead, SLTNODE* pos, SLTDataType val)
{//在第pos个结点的前面插入一个结点，结点中存储数据是val
	if (*pphead == pos)
	{
		//如果pos为第一个结点，则直接调用头插函数
		SListPushFront(pphead, val);
	}
	SLTNODE* prev = *pphead;//若pos不为头结点，则找到pos的前一个结点
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	SLTNODE* newnode = CreateNode(val);
	prev->next = newnode;
	newnode->next = pos;
}

2.2.9在指定位置删除

删除就比较简单了，思路上面已经有了，这里就不再赘述了

void SListErase(SLTNODE** pphead, SLTNODE* pos)
{
	if (*pphead == pos)
	{
		//如果pos为第一个结点，则直接调用头删函数
		SListPopFront(pphead);
	}
	SLTNODE* prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}//若不为头结点，则将pos前的一个结点的next指向pos后第二个结点
	prev->next = prev->next->next;
}

三、顺序表与单链表的比较

对于顺序表，它的操作比较简单，但是它的功能比较僵硬。也就是说，它的空间不够弹性，很容易造成空间不够或空间浪费的情况。另外，当进行删除和插入操作时，需要挪动其他的很多元素，会造成时间复杂度太高的情况。这是它的缺点所在。
但是当插入或删除时，直接引用对应下标即可，比较简单，这是它的优点。

对于单链表，它可能理解起来不太简单，但是当进行插入删除时，不用改变其他元素的位置。它的空间也比较弹性，不会造成浪费。也不要求每个结点在内存中必须连续。这是它的优点。
但当进行尾插时需要遍历每一个元素，才能找到最后一个结点，比较麻烦。这是它的缺点所在。

四、总结

顺序表与单链表都有各自的优缺点，都不太完美，但是都能实现很多接口。
大家也不要着急，在以后的学习中，我们会介绍更好的方法，会慢慢地减少缺点！
顺序表和单链表的知识就讲到这里了，希望对大家有帮助！我们下次再见！