数据结构——C语言实现链表

目录

一. 链表的概念

二. 单链表的增删查改

1.单链表的定义

2.单链表的头插与头删

3.单链表的尾插与尾删

4.单链表的中间插入删除

5.单链表的查找

三. 带头循环双向链表的增删查改

1.带头循环双向链表的定义

2.带头循环双向链表的头插与头删

3.带头循环双向链表的尾插与尾删

4.带头循环双向链表的中间插入删除

5.带头循环双向链表的查找

---

一. 链表的概念

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

在这里介绍链表中的两种结构

无头单向非循环列表：结构简单，一般不会单独用来存放数据。实际中更多是作为其他数据结构的子结构，比如说哈希桶等等。
带头双向循环链表：结构最复杂，一般单独存储数据。实际中经常使用的链表数据结构，都是带头双向循环链表。这个结构虽然复杂，但是使用代码实现后会发现这个结构会带来很多优势，实现反而简单了。

二. 单链表的增删查改

1.单链表的定义

在C语言中我们一般创建一个结构体来作为链表的结点

typedef int SLDataType;
typedef struct SListNode
{
	SLDataType data;
	struct SListNode* next;
}SListNode;

 创建初始化一个节点：

void SListInitNode(SListNode** plist, SLDataType x)
{
	assert(plist);
	*plist = (SListNode*)malloc(sizeof(SListNode));
	assert(*plist);
	(*plist)->data = x;
	(*plist)->next = NULL;
}

2.单链表的头插与头删

1.头插

void SListPushFront(SListNode** plist, SLDataType x)
{
	assert(plist);
	SListNode* ptr = *plist;
	SListInitNode(plist, x);
	(*plist)->next = ptr;
}

2.头删

void SListPopFront(SListNode** plist)
{
	assert(*plist);
	assert(plist);
	SListNode* ptr = (*plist)->next;
	free(*plist);
	*plist = ptr;
}

3.单链表的尾插与尾删

1.尾插

void SListPushBack(SListNode** plist, SLDataType x)
{
	assert(plist);
	if (*plist == NULL)
	{
		SListInitNode(plist, x);
	}
	else
	{
		SListNode* ptr = *plist;
		while (ptr->next)
		{
			ptr = ptr->next;
		}
		SListInitNode(&(ptr->next), x);
	}
}

2.尾删

void SListPopBack(SListNode** plist)
{
	assert(plist);
	assert(*plist);
	if ((*plist)->next == NULL)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		SListNode* ptr = *plist;
		while (ptr->next->next)
		{
			ptr = ptr->next;
		}
		free(ptr->next);
		ptr->next = NULL;
	}
}

4.单链表的中间插入删除

1.在pos位置之后插入

为什么不在pos位置之前插入？

在pos位置之前插入需要传单链表的二级指针，

1.用来解决pos指向单链表的头部出现的头插情况

2.用来寻找插入位置的前一个位置，以改变其指向

void SListInsertAfter(SListNode* pos, SLDataType x)
{
	assert(pos);
	SListNode* ptr = NULL;
	ptr = (SListNode*)malloc(sizeof(SListNode));
	assert(ptr);
	ptr->data = x;
	ptr->next = pos->next;
	pos->next = ptr;
}

2.在pos位置之后删除

为什么不删除pos位置？
删除pos位置同样需要传入单链表的二级指针，

1.用来解决pos指向单链表的头部出现的单链表指针指向的改变

2.用来寻找pos位置的前一个位置，以改变其指向

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* ptr = pos->next;
	pos->next = pos->next->next;
	free(ptr);
	ptr = NULL;
}

5.单链表的查找

SListNode* SListFind(SListNode* plist, SLDataType x)
{
	assert(plist);
	while (plist)
	{
		if (plist->data == x)
			return plist;
		plist = plist->next;
	}
	return NULL;
}

三. 带头循环双向链表的增删查改

1.带头循环双向链表的定义

在C语言中我们一般创建一个结构体来作为链表的结点

typedef int LDataType;
typedef struct ListNode
{
	LDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

创建一个节点：

ListNode* BuyListNode()
{
	ListNode* tmp = (ListNode*)malloc(sizeof(ListNode));
	if (tmp == NULL)
	{
		perror("malloc");
	}
	return tmp;
}

2.带头循环双向链表的头插与头删

1.头插

void ListPushfront(ListNode* phead, LDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode();
	ListNode* tail = phead->next;
	phead->next = newnode;
	newnode->next = tail;
	newnode->prev = phead;
	tail->prev = newnode;
	newnode->data = x;
	//ListInsert(phead->next, x);
}

2.头删

void ListPopFront(ListNode* phead)
{
	assert(phead);
	ListNode* tail = phead->next;
	tail->next->prev = phead;
	phead->next = tail->next;
	free(tail);
	//ListErase(phead->next);
}

3.带头循环双向链表的尾插与尾删

1.尾插

void ListPushBack(ListNode* phead, LDataType x)
{
	ListNode* plist = BuyListNode();
	ListNode* tail = phead->prev;
	tail->next = plist;
	plist->prev = tail;
	plist->next = phead;
	phead->prev = plist;
	plist->data = x;
	//ListInsert(phead, x);
}

2.尾删

void ListPopBack(ListNode* phead)
{
	assert(phead);
	ListNode* tail = phead->prev;
	tail->prev->next = phead;
	phead->prev = tail->prev;
	free(tail);
	//ListErase(phead->prev);
}

4.带头循环双向链表的中间插入删除

1.插入

void ListInsert(ListNode* pos, LDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode();
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
	newnode->data = x;
}

2.删除

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
}

5.带头循环双向链表的查找

ListNode* ListFind(ListNode* phead, LDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (phead != cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}