
#define INIT_NUM 10 //初始时数组的大小
#define ADD_NUM  5	//每次增加容量时一次增加的数量
typedef int SLTYPE
typedef struct SequenceList
{
	SLTYPE* pSL;
	size_t size;
	size_t capcity;
}SL;

功能1.初始化该顺序表


//初始化
void SLInit(SL* pSL)
{
	SLTYPE* ret = calloc(INIT_NUM, sizeof(SLTYPE));
	if (ret)
	{
		pSL->SLhead = ret;
	}
	else
	{
		perror("INIT FAIL");
	}
	pSL->capcity = 0;
	pSL->size = 0;
}

功能2. 判断容量是否允许插入数据，否则扩容


//判断容量是否允许插入数据，否则扩容
int SLCheckCapcity(SL* pSL)
{
	if (pSL->capcity == pSL->size)
	{
		SLTYPE* ret = ralloc((pSL->capcity + ADD_NUM) * sizeof(SLTYPE));
		if (ret)
		{
			pSL->SLhead = ret;
			pSL->capcity += ADD_NUM;
			return 0;    //代表增容成功
		}
		else
		{
			perror("PUSH FAIL,ENENOUGH CAPCITY！");
			return 1;  //代表增容失败
		}
	}
}

功能3.在数组头部或者尾部插入数据


//头插 
void SLPushFront(SL* pSL, SLTYPE x)
{
	//判断容量是否允许插入数据，否则扩容
	if (SLCheckCapcity(pSL))
	{
		return;
	}
	// 0 1 2 3    size-1
	for (int i = pSL->size ; i > 0; i--)
	{
		pSL->SLhead[i] = pSL->SLhead[i-1];
 
	}
	pSL->SLhead[0] = x;
	pSL->size++;
}
//尾插 
void SLPushBack(SL* pSL, SLTYPE x)
{
	//判断容量是否允许插入数据，否则扩容
	if (SLCheckCapcity(pSL))
	{
		return;
	}
	pSL->SLhead[pSL->size] = x;
	pSL->size++;
}

功能4.在数组头部或者尾部删除数据


//尾部删除
void SLPopBack(SL* pSL)
{
	if (pSL->size == 0)
	{
		perror("NO DATA TO DELETE");
		return;
	}
	pSL->size--;
}
//头部删除
void SLPopFront(SL* pSL)
{
	if (pSL->size == 0)
	{
		perror("NO DATA TO DELETE");
		return;
	}
	for (int i = 0; i < pSL->size-1; i++)
	{
		pSL->SLhead[i] = pSL->SLhead[i + 1];
	}
	pSL->size--;
 
}

功能5.顺序表打印


//顺序表打印
#define FORMAT "%d "  
void SLPrint(SL* pSL)
{
	for (int i = 0; i < pSL->size; i++)
	{
		printf(FORMAT, pSL->SLhead[i]);
	}
	prinf("\n");
}

功能6.查找指定数据


//查找指定数据
int SLFindIndex(SL* pSL, SLTYPE x)
{
	for (int i = 0; i < pSL->size; i++)
	{
		if (pSL->SLhead[i] == x)
			return i;
	}
	return -1;
}

功能7.在指定下标位置插入删除数据


//在指定下标位置插入数据
void SLInsertIndex(SL* pSL,size_t index ,SLTYPE x)
{
	if (indx > pSL->size)
	{
		printf("INVAILD INDEX!");
		return;
	}
	if (SLCheckCapcity(pSL))
	{
		return;
	}
	for (int i = pSL->size; i > index; i--)
	{
		pSL->SLhead[i] = pSL->SLhead[i - 1];
	}
	pSL->SLhead[index] = x;
	pSL->size++;
}
 
//在指定下标位置删除数据
void SLInsertIndex(SL* pSL, size_t index )
{
	if (indx >= pSL->size)
	{
		printf("INVAILD INDEX!");
		return;
	}
	if (pSL->size == 0)
	{
		printf("NO DATA TO DELETE");
		return;
	}
	for (int i = index; i < pSL->size-1; i++)
	{
		pSL->SLhead[i] = pSL->SLhead[i + 1];
	}
	pSL->size--;
}

功能8.销毁释放顺序表


// 数据销毁
void SLDestroy(SL* pSL)
{
	free(pSL->SLhead);
	pSL->size = 0;
	pSL->capcity = 0;
}

二.链表

1.概念及结构

链表是一种物理存储结构上非连续、非顺序的存储结构，但是逻辑上是顺序的。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：

一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

2.分类

实际中为了拓展链表功能，它的的结构非常多样，按照不同分类依据主要可以分成以下几种基础结构，其中每一种还可以组合在一起构成新结构。

(1)单向或者双向

指针域里指针个数不同，有的可以增加指针来指向前一个节点地址。

(2) 带头或者不带头

不带头的链表，链表第一个节点不存放元素方。带头的链表，链表首节点开始存放第一个元素。 (3)循环或者非循环

(4)多种结合

3.无头单向非循环链表的接口实现

结构体定义：


typedef int SLLDataType;
#define   FORMAT "%d "
typedef struct SLLNode
{
	SLLDataType data;
	struct SLLNode* next;
 
}SLLNode;

功能1.生成新节点以及传入数据一次性生成一个链表


 
//创建节点
SLLNode* CreateNode(SLLDataType x)
{
	SLLNode* p = (SLLNode*)malloc(sizeof(SLLNode));
	if (p)
	{
		p->data = x;
		p->next = NULL;
		return p;
	}
	else
	{
		perror("malloc fail");
		return NULL;
	}
}
//一次初始化n个节点
SLLNode* CreateSLL(int n,SLLDataType* datas)
{
	SLLNode* phead = NULL, *ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLLNode* ret = CreateNode(datas[i]);
		if (ret)
		{
			if (i == 0)
			{
				phead = ptail = ret;
			}
			else
			{
				ptail->next = ret;
				ptail = ret;
			}
		}
		else
		{
			perror("create fail");
			return NULL;
		}
	}
	return phead;
 
}

功能2.打印链表信息


 
//打印
void SLLPrint(SLLNode* pSLL)
{
	if (pSLL == NULL)
	{
		printf("NULL\n");
		return;
	}
	SLLNode* cur = pSLL;
	while (cur)
	{
		printf(FORMAT, cur->data);
		cur = cur->next;
	}
	printf("\n");
}

功能3.添加尾部节点或者删除


 
//尾插
void SLLPushBack(SLLNode** ppSLL, SLLDataType data)
{
	SLLNode* ptail = *ppSLL;
	SLLNode* pnode = CreateNode(data);
	if (!pnode)
	{
		perror("malloc fail\n");
		return;
	}
	if (ptail == NULL)
	{
		*ppSLL = pnode;
	}
	else
	{
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = pnode;
	}
}
 
 
//尾删
void SLLPopBack(SLLNode** ppSLL)
{
	if (*ppSLL == NULL)
	{
		perror("NO DATA TO DELETE");
		return;
	}
	else
	{
		if ((*ppSLL)->next == NULL)
		{
			free(*ppSLL);
			*ppSLL = NULL;
			return;
 
		}
		else
		{
			SLLNode* pre = *ppSLL;
			SLLNode* ptail = pre->next;
			while (ptail->next)
			{
				ptail=ptail->next;
				pre = pre->next;
			}
			pre->next = NULL;
			free(ptail);
		}
 
	}
}

功能4.添加头部节点或者删除


 
//头插
void SLLPushFront(SLLNode** ppSLL, SLLDataType data)
{
	SLLNode* pnode = CreateNode(data);
	if (!pnode)
	{
		perror("malloc fail\n");
		return;
	}
	pnode->next = *ppSLL;
	*ppSLL = pnode;
}
 
//头删
void SLLPopFront(SLLNode** ppSLL)
{
	if (*ppSLL == NULL)
	{
		perror("NO DATD TO DELETE!");
		return;
	}
	else if ((*ppSLL)->next == NULL)
	{
		free(*ppSLL);
		*ppSLL = NULL;
	}
	else
	{
		SLLNode* next = (*ppSLL)->next;
		free(*ppSLL);
		*ppSLL = next;
	}
}

功能5.链表查找节点


 
// 单链表查找
SLLNode* SLLFind(SLLNode* pSLL, SLLDataType data)
{
	if (!pSLL)
	{
		return NULL;
	}
	SLLNode* cur = pSLL;
	while (cur)
	{
		if (cur->data == data)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
 
}

功能6.在特定的节点位置删除或者假如元素


// 单链表在pos位置之后插入x
void SLLInsertAfter(SLLNode* pos, SLLDataType data)
{
	if (!pos)
	{
		perror("POS INVAILD!");
		return;
	}
	if (CreateNode(data))
	{
		SLLNode* newnode = CreateNode(data); 
		newnode->next = pos->next;
		pos->next = newnode;
 
	}
	else
	{
		perror("CREATE NODE FAIL!");
		return;
	}
		
 
}
// 单链表在pos位置之前插入x
void SLLInsertBefore(SLLNode** ppSLL, SLLNode* pos, SLLDataType data)
{
	if (!pos)
	{
		perror("POS INVAILD!");
		return;
	}
	if (*ppSLL == pos)
	{
		SLLPushFront(ppSLL, data);
		return;
	}
	SLLNode* pre = *ppSLL;
	while (pre->next != pos)
	{
		pre = pre->next;
	}
	if (CreateNode(data))
	{
		SLLNode* newnode = CreateNode(data);
		newnode->next = pos;
		pre->next = newnode;
	}
	else
	{
		perror("CREATE NODE FAIL!");
		return;
	}
 
}
 
// 单链表删除pos位置之后的值
void SLLEraseAfter(SLLNode* pos)
{
	if (!pos|| pos->next == NULL)
	{
		perror("POS INVAILD!");
		return;
	}
	SLLNode* ret = pos->next;
	pos->next = ret->next;
	free(ret);
}
// 单链表删除pos位置当前的值
void SLLErase(SLLNode** ppSLL, SLLNode* pos)
{
	if (!pos)
	{
		perror("POS INVAILD!");
		return;
	}
	if (*ppSLL == pos)
	{
		SLLPopFront(ppSLL);
		return;
	}
	else
	{
		SLLNode* pre = *ppSLL;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
	}
}

功能7.销毁数据


// 单链表的销毁
void SListDestroy(SLLNode** ppSLL)
{
	SLLNode* cur = *ppSLL;
	while (cur)
	{
		SLLNode* ret = cur->next;
		free(cur);
		cur = ret;
	}
	*ppSLL = NULL;
}

4.带头双向循环链表的接口实现

结构体和功能声明


typedef int DLLType;
#define FORMAT "%d " 
typedef struct DoubleLinkedListNode
{
	struct DoubleLinkedListNode* pre;
	DLLType val;
	struct DoubleLinkedListNode* next;
}DLLNode;
 
//初始化
void DLLInit(DLLNode* guard);
//创建节点
DLLNode* CreateNode(DLLType x);
 
//打印
void DLLPrint(DLLNode* guard);
 
 
// 查找
DLLNode* DLLFind(DLLNode* guard, DLLType data);
 
// 在pos位置之后插入x
void DLLInsertAfter(DLLNode* pos, DLLType data);
// 在pos位置之前插入x
void DLLInsertBefore(DLLNode* pos, DLLType data);
//头插
void DLLPushFront(DLLNode* guard, DLLType data);
//尾插
void DLLPushBack(DLLNode* guard, DLLType data);
 
 
 
// 删除pos位置之后的值
void DLLEraseAfter(DLLNode* gaurd, DLLNode* pos);
// 删除pos位置当前的值
void DLLErase(DLLNode* gaurd, DLLNode* pos);
//尾删
void DLLPopBack(DLLNode* gaurd);
//头删
void DLLPopFront(DLLNode* gaurd);
 
 
// 单链表的销毁
void DListDestroy(DLLNode* gaurd);

功能实现


//初始化
void DLLInit(DLLNode* guard)
{
	guard->next = guard, guard->pre = guard;
}
//创建节点
DLLNode* CreateNode(DLLType x)
{
	DLLNode* ret = malloc(sizeof(DLLNode));
	assert(ret);
	ret->val = x;
	ret->next = NULL, ret->pre = NULL;
	return ret;
}
 
//打印
void DLLPrint(DLLNode* guard)
{
	if (guard == NULL)
	{
		printf("NULL");
		return;
	}
	DLLNode* ret = guard->next;
	while (ret != guard)
	{
		printf(FORMAT, ret->val);
		ret = ret->next;
	}
	printf("\n");
}
 
// 查找
DLLNode* DLLFind(DLLNode* guard, DLLType data)
{
	assert(guard);
 
	DLLNode* ret = guard->next;
	while (ret != guard)
	{
		if (ret->val == data)
		{
			return ret;
		}
		ret = ret->next;
	}
	return NULL;
}
 
// 在pos位置之后插入x
void DLLInsertAfter(DLLNode* pos, DLLType data)
{
	DLLNode* ret=CreateNode(data);
	ret->next = pos->next;
	pos->next->pre = ret;
	pos->next = ret;
	ret->pre = pos;
 
}
// 在pos位置之前插入x
void DLLInsertBefore(DLLNode* pos, DLLType data)
{
 
	DLLNode* ret = CreateNode(data);
	ret->pre = pos->pre;
	pos->pre->next = ret;
	ret->next = pos;
	pos->pre = ret;
}
 
//头插
void DLLPushFront(DLLNode* guard, DLLType data)
{
 
	DLLInsertAfter(guard,data);
}
//尾插
void DLLPushBack(DLLNode* guard, DLLType data)
{
	DLLInsertBefore(guard, data);
}
 
 
 
// 删除pos位置之后的值
void DLLEraseAfter(DLLNode* gaurd, DLLNode* pos)
{
	assert(pos->next != gaurd);
	DLLNode* ret = pos->next;
	pos->next = ret->next;
	ret->next->pre = pos;
	free(ret);
}
// 删除pos位置当前的值
void DLLErase(DLLNode* gaurd, DLLNode* pos)
{
	assert(pos != gaurd);
	pos->next->pre = pos->pre;
	pos->pre->next = pos->next;
	free(pos);
 
}
 
 
//尾删
void DLLPopBack(DLLNode* gaurd)
{
	assert(gaurd->pre);
	DLLErase(gaurd, gaurd->pre);
}
//头删
void DLLPopFront(DLLNode* gaurd)
{
	assert(gaurd->next);
	DLLErase(gaurd, gaurd->next);
 
}
 
// 链表的销毁
void DListDestroy(DLLNode* gaurd)
{
	DLLNode* ret = gaurd->next;
	DLLNode* tmp = gaurd->next;
	while (ret != gaurd)
	{
		tmp=ret->next;
		free(ret);
		ret = tmp; 
	}
	free(gaurd);
}

三.顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定
元素的删除插入效率	需要移动大量数据，时间复杂度为O(N)	只需要改变各节点的指向关系时间复杂度为O(1)
容量问题	增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。	只需要创建节点再将其链接进入链表即可
空间利用问题	会有所需数据太多开辟不了的的问题，也有可能造成浪费	不会有顺序表可能的问题
随机访问效率	可以通过下标直接访问，实现O(1)	只能挨个遍历，复杂度O(N)
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/560228