程序员经验分享-hwhale

数据结构——链表一网打尽

2023-11-17

目录

前言

 函数的传参

不带头单向非循环链表

​ 带头双向循环链表

顺序表与链表的优缺点

单链表源码

带头双向循环链表源码

前言

链表是一种物理存储结构上非连续非线性的结构，数据元素的逻辑顺序通过指针次序链接实现，在逻辑结构上好像通过链子链接起来所以称为链表。

链表的结构多种多样，通过以下情况组合起来有8种结构：

1.带头、不带头

2.单向、双向

3.循环、非循环

但实际中最常用的只有不带头单向非循环和带头双向循环两种结构。

不带头单向非循环：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶等

带头双向循环链表：结构最复杂，一般用在单独存储数据。虽然结构复杂但实现起来非常简单，后面我们实现代码就知道了

关于带头、不带头的问题，就是有无带哨兵位的头节点：

带头就是始终有一个头节点存在，头节点head不存储有效数据，data为随机值不用管。

带哨兵位的头节点需要我们预先开辟，链表使用完后需要释放，而不带头的就不需要创建头节点了，但是每次尾插头插都需要判断链表的头指针是否为空，各有各的优缺点。

下图：假定有一个plist的指针维护链表，头节点head，有效数据存储在头节点之后，如果没有存储数据，头节点的next就指向NULL，这样不管是头插还是尾插都不需要像不带头的链表需要判断头指针是否为空

不带头：没有头节点，plsit直接指向有效数据，链表为空时plist就指向NULL;

双向单向问题：节点的结构不同，单向只有一个指针next存储下一节点的地址，双向有两个指针prev和next，分别存储上一节点和下一节点的地址。

循环非循问题：尾节点的next和头节点的prev是否为空

下图就是双向循环链表，尾节点data3的next指向头节点，头节点的prev指向尾节点，就构成循环

如果是非循环的话，data3的next和头节点的prev就为NULL

 函数的传参

 当然小伙伴还不理解的话也没有关系，相信你了解完下面单链表的实现就懂了。在这之前呢我们再讨论下函数的传参问题，什么时候传一级指针，什么时候传二级指针？

我们通过一个简单的测试来演示

#include <stdio.h>
void Test1(int* ret)
{
	++ret;
}
void Test2(int* ret)
{
	*ret = 10;
}
void Test3(int** pp)
{
	(*pp)++;
}

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	int* p = arr;
	Test1(p);
	printf("%d\n", *p);
	
	Test2(p);
	printf("%d\n", *p);

	Test3(&p);
	printf("%d\n", *p);

	return 0;
}

有一个数组arr，数组名是首元素的地址，让指针p指向第一个元素

Test1中传指针p，形参实参的一份临时拷贝，所以有一个指针ret也指向数组中的1，然后++ret，让ret指向2，但是指针p仍然指向1.

 Test3中传指针p的地址，指针pp指向p，pp通过解引用操作p改变p的指向，所以p指向2

在Test2中，通过指针解引用，将p指向的1改为10. 

那我们就可以得出一个结论：要改变一级指针的指向就要传二级指针，当然还可以用接收返回值的方式改变指针的指向，多级指针以此类推,

如果不改变一级指针的指向，就传一级指针，多级指针以此类推。

不带头单向非循环链表

简称单链表Single List，一般很多oj题都会出这种结构的题目，而实际中是作为其他结构的子结构，如哈希桶等。

先看功能函数的声明     SList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct SingleListNode
{
	DataType data;
	struct SingleListNode* next;
}SListNode;

//打印链表
void SListNodePrint(SListNode* phead);
//链表尾插
void SListNodepushback(SListNode** pphead, DataType x);
//链表头插
void SListNodepushfront(SListNode** pphead, DataType x);
//链表尾删
void SListNodepopback(SListNode** pphead);
//链表头删
void SListNodepopfront(SListNode** pphead);
//寻找链表中数据所在的位置
SListNode* SListNodeFind(SListNode* phead, DataType x);
//链表指定pos位置前插入
void SListNodeInsert(SListNode** pphead, SListNode* pos, DataType x);
//链表指定pos位置后插入
void SListNodeInsertAfter(SListNode* pos, DataType x);
//链表指定pos位置删除数据
void SListNodeErase(SListNode** pphead, SListNode* pos);
//链表销毁
void SListNodeDestroy(SListNode** pphead);

 单链表的基本结构:

节点的结构为：data数据保存值，next保存下一节点地址，通过next找到下一节点，且尾节点的next始终指向NULL

typedef int DataType;

typedef struct SingleListNode
{
	DataType data;
	struct SingleListNode* next;
}SListNode;

我们操作链表传的都是二级指针，因为不管是头删头插，尾删尾插都有可能改变head的指向，只有打印链表不需要改变head的指向，可以传一级指针

首先第一步先创建一个head指针用来指向NULL，此时链表无节点，为NULL

SListNode* head = NULL;

 对于每次头插和尾插都需要在堆上开辟新节点，我们就定义一个create函数，只需要传入要data数据值x，就可以创建一个newnode新节点，然后让next置空

//创建新节点
SListNode* Creatnode(DataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

 头插：第一步先断言pphead始终不为空，如果我们参数传错了，传的是head且head为NULL,而不是head的地址就会断言报错

void SListNodepushfront(SListNode** pphead, DataType x)
{	
	assert(pphead);

	SListNode* newnode = Creatnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

头插不用考虑链表是否为NULL，因为始终要将head指向新的节点

 我们要将新节点的next指向那个data1在的节点，然后然头指针head指向newnode，即使头指针为空，那newnode的next也是指向NULL的

尾插：第一步仍然是断言，然后是创建节点，尾插需要判断头指针是否为空，如果为空的话就要将头指针指向尾插的节点，不为空就直接在当前链表的尾节点后面插入

void SListNodepushback(SListNode** pphead, DataType x)
{	
	assert(pphead);

	SListNode* newnode = Creatnode(x);
	if (*pphead == NULL)
		*pphead = newnode;
	else
	{
		SListNode* ret = *pphead;
		while (ret->next != NULL)
		{
			ret = ret->next;
		}
		ret->next = newnode;
	}
}

 不为空时，定义一个临时指针ret遍历当前链表找到链表的尾节点，因为尾节点的next为空，所以循环结束的条件就是ret->next == NULL,然后让ret的next指向newnode

头删：链表必须有节点才能删除，所以断言head也就是*pphead不能为空，

void SListNodepopfront(SListNode** pphead)
{	
	//链表为空不能删除
	assert(*pphead != NULL);

	SListNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	*pphead = next;
}

如果直接free头节点，那就找不到链表的下一个节点了，所以需要先定义一个next保存头指针的下一个节点，然后在free，这边*pphea置不置空都可以，因为链表也访问不到了，然后然头节点指向next

 尾删：同样链表中有节点才能尾删，所以断言，然后就要判断链表中有一个节点还是一个以上的节点了：

1.只有一个节点，free头head，head指向NULL了

2.有一个以上节点就不需要改变头指针的指向，只需要用指针ret遍历链表找到尾节点删除即可，由于链表是单向的，如果我们让ret直接指向尾节点的话，它的前一个节点就找不到了，所以我们只遍历到尾节点的前一个节点，通过next释放尾节点，然后再让ret->next = NULL

void SListNodepopback(SListNode** pphead)
{	
	//链表为空不能删除
	assert(*pphead != NULL);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//两个及以上节点
	else
	{	
		SListNode* ret = *pphead;
		
		while (ret->next->next != NULL)
		{
			ret = ret->next;
		}
		free(ret->next);
		ret->next = NULL;
	}
}

寻找链表中数据x所在位置：

由于不需要改变head指向，所以传一级指针，仍然要断言链表不能为空，定义一个指针cur遍历链表cur指向节点的data如果为x就返回cur的地址，遍历完链表还未找到就返回NULL，由于链表中可能有多个与x相同的值，这里只取找到的第一个节点的地址

SListNode* SListNodeFind(SListNode* phead, DataType x)
{	
	assert(phead != NULL);

	SListNode* cur = phead;
	//只能返回最开始找到的
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

链表指定pos位置插入：

1、在pos位置之后插入：这种比较方便，通过find函数找到pos位置，然后就可以在pos后插入节点

//从pos后插入
void SListNodeInsertAfter(SListNode* pos, DataType x)
{	
	assert(pos);

	SListNode* newnode = Creatnode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

 2.在pos位置之前插入，首先断言，然后判断是否是在头节点插入，也就是头插了，其他情况的话，需要先找到pos前一个节点posprev，然后让posprev指向newnode，newnode的next指向pos位置

void ChainListInsert(CListNode** pphead, CListNode* pos, DataType x)
{	
 assert(pphead && pos);
 
	CListNode* newnode = Creatnode(x);
	//直接头插
	if (*pphead == pos)
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
	else
	{
		CListNode* posPrev = *pphead;
		//找pos的前一个节点
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		 newnode->next=posPrev->next;
		 posPrev->next = newnode;
	}
}

pos位置的删除：

首先断言pos不为空且链表不为空，然后判断是否为头删，不为头删的话，那么需要找到pos位置的上一个节点，让posprev的next指向pos的next，然后free调pos完成pos位置删除

void SListNodeErase(SListNode**pphead, SListNode* pos)
{
	assert(*pphead && pos);

	//判断是否为头删
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

最后就是链表的销毁了，要将之前malloc的所有节点都free置空，再将head置空，

定义一个next记录下一节点，释放当前节点后就可以找到下一节点，然后遍历链表全部free

void SListNodeDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

还有一个打印函数，打印链表

void SListNodePrint(SListNode* phead)
{	
	while (phead != NULL)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

最后我们测试一下  Test.c

#include "SList.h"

void Test1()
{	
	SListNode* head = NULL;
	
	SListNodepushback(&head, 1);
	SListNodepushback(&head, 2);
	SListNodepushfront(&head, 4);
	SListNodepushfront(&head, 5);

	SListNodePrint(head);
}

void Test2()
{	
	SListNode* head = NULL;

	SListNodepushback(&head, 1);
	SListNodepushback(&head, 2);
	SListNodepushback(&head, 3);
	SListNodepopback(&head);
	SListNodepopback(&head);

	SListNodePrint(head);
}

void Test3()
{
	SListNode* head = NULL;

	SListNodepushback(&head, 1);
	SListNodepushback(&head, 2);
	SListNodepushback(&head, 3);
	SListNodepushback(&head, 4);
	SListNodepushback(&head, 5);
	
	/*SListNode* pos = SListNodeFind(head, 5);
	int i = 1;
	while (pos != NULL)
	{	
		printf("这是第%d个节点%p->%d\n", i++, pos, pos->data);
		if (pos->next == NULL)
			return;
		pos = SListNodeFind(pos->next, 5);
	}*/
	SListNode* pos = SListNodeFind(head, 5);
	if (pos != NULL)
	{
		SListNodeInsertAfter(pos, 10);
	}
	SListNodePrint(head);
}

int main()
{	
	Test1();
	Test2();
	Test3();
	
	return 0;
}

带头双向循环链表

介绍完单链表后我们再来了解一下带头双向循环链表,简称双链表Doubel List，双链表的结构看起来复杂，多了一个指针prev存放上一节点的地址，但是实现起来非常简单

先展示功能函数的定义

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode
{
	DataType data;
	struct ListNode* next; //存放下一个节点
	struct ListNode* prev; //存放前一个节点
}ListNode;

//链表初始化，创建哨兵位头节点
ListNode* ListNodeInit();
//链表打印
void ListNodePrint(ListNode* phead);
//链表尾插
void ListNodePushBack(ListNode* phead, DataType x);
//链表尾删
void ListNodePopBack(ListNode* phead);
//链表头插
void ListNodePushFront(ListNode* phead, DataType x);
//链表头删
void ListNodePopFront(ListNode* phead);
//链表查找
ListNode* ListNodeFind(ListNode* phead, DataType x);
//链表指定pos位置前插入数据
void ListNodeInsert(ListNode* pos, DataType x);
//链表指定pos位置删除数据
void ListNodeErase(ListNode* pos);
//销毁链表
void ListNodeDestroy(ListNode* phead);

双链表的结构

typedef int DataType;

typedef struct ListNode
{
	DataType data;
	struct ListNode* next; //存放下一个节点
	struct ListNode* prev; //存放前一个节点
}ListNode;

链表只有哨兵位的头节点就自己指向自己

 plist指向头节点，因为我们不需要改变plist的指向，所以传一级指针即可，但是我们初始化，创建头节点，需要让pist指向头节点，这里我们直接用返回值接收就不用传二级指针了

ListNode* plist = ListNodeInit();
ListNode* ListNodeInit()
{	
	//创建哨兵位的头节点，方便尾插，对链表操作时也不用传二级指针了
	struct ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->next = phead;
	phead->prev = phead;
	
	return phead;
}

也就是上图的头节点自己指向自己的情况

由于每次都要创建新节点，所以直接封装成create函数，newnode的prev和next都置空

//创建新节点
ListNode* ListNodeCreate(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	
	return newnode;
}

 头插：首先要创建新节点newnode，我们定义定义next指针记录头节点的后一个有节点，然后让phead的next指向newn，newnode的pre指向phead，建立链接关系，再让newnode的next指向next，next的prev指向newnode

void ListNodePushFront(ListNode* phead, DataType x)
{
	assert(phead);

	ListNode* newnode = ListNodeCreate(x);
	ListNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

头删：首先要判断传过来的是节点是否是头节点，不能把头节点删了，然后我们定义一个指针cur记录第一个节点，指针next记录第二个节点

让头节点phead的next指向next，next的prev指向phead，在free释放掉cur指向的节点

void ListNodePopFront(ListNode* phead)
{	
	assert(phead && phead->next != phead); //不能把头节点删了

	ListNode* cur = phead->next;
	ListNode* next = cur->next;
	phead->next = next;
	next->prev = phead;
	free(cur);
}

 尾插：我们上面的单链表尾插需要遍历链表找到尾节点，而循环链表它的头节点phead的prev指向的就是尾节点，先定义一个tail记录尾节点，先让newnode和头节点phead链接，再让newn和tail链接，完成尾插

void ListNodePushBack(ListNode* phead, DataType x)
{	
	assert(phead);
	//创建新节点
	ListNode* newnode = ListNodeCreate(x);
	ListNode* tail = phead->prev;
	
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

尾删：断言传过来的是节点是否是头节点，由于要删除尾节点，那我们定义一个prev记录尾节点的前一个节点 ，然后将prev的next指向头节点phead，phead的prev指向prev所在节点，完成尾删

void ListNodePopBack(ListNode* phead)
{	
	assert(phead && phead->next != phead);//不能把头节点删了
	//找到尾节点
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	
	free(tail);
}

寻找x所在节点位置：

定义指针cur遍历链表，比较data与x是否相等，由于这是循环链表，所以当cur再次指向phead时已经将链表遍历一遍了，跳出循环后就返回NULL


ListNode* ListNodeFind(ListNode* phead, DataType x)
{	
	assert(phead);

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

在pos位置前插入节点

首先断言pos不为空，创建新节点newnode，在定义一个posprev记录pos的前一个节点，然后形成链接关系，这里不在赘述了，当我们定义了这个函数后就可以代替头插尾插了，头插pos的位置为phead->next,尾插pos位置为phead。头插和尾插就可以直接复用Insert函数

void ListNodeInsert(ListNode* pos, DataType x)
{	
	assert(pos);

	ListNode* newnode = ListNodeCreate(x);
	ListNode* posprev = pos->prev;
	posprev->next = newnode;
	newnode->prev = posprev;
	newnode->next = pos;
	pos->prev = newnode;
}

pos位置删除数据 

如果pos->next == pos表是此是只有头节点，没有存储其他节点，所以断言一下，不能把头节点删了，定义两个指针记录pos前一个节点和后一个节点，方便删除pos位置节点。同样的头删和尾删可以直接复用Erase函数

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

销毁链表

通过cur和next两个指针遍历并删除链表，由于我们传的是一级指针，是plist的形参，形参的改变不会影响实参，所以要在主函数里面将plist头指针置空，避免形成野指针

void ListNodeDestroy(ListNode* phead)
{	
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{	
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

最后测试一下双链表

#include "List.h"
void Test2()
{
	ListNode* plist = ListNodeInit();
	ListNodePushFront(plist, 1);
	ListNodePushFront(plist, 2);
	ListNodePushFront(plist, 3);
	ListNodePrint(plist);

	ListNodePopFront(plist);
	ListNodePrint(plist);

	ListNode* pos = ListNodeFind(plist, 2);
	if (pos != NULL)
		ListNodeInsert(pos, 4);
	ListNodePrint(plist);

	pos = ListNodeFind(plist, 2);
	if (pos != NULL)
		ListNodeErase(pos);
	ListNodePrint(plist);

	ListNodeDestroy(plist);
	plist = NULL;
}
int main()
{	
	//Test1();
	Test2();

	return 0;
}

 实现完带头双向循环链表是不是觉得比单链表要简单多了。

顺序表与链表的优缺点

我们上节介绍了线性表中的顺序表，这节介绍了链表，顺序表和链表是相辅相成的两个结构，自己的优点是对方的缺点，我们下面讨论的是顺序表与带头双向循环链表的优缺点

顺序表：

优点：由于是连续的空间，支持随机访问

缺点：1.空间不够时需要扩容的，而扩容是需要付出代价的，为避免频繁扩容，我们一般是扩2倍，这也从一定程度上导致空间浪费，且原空间不够扩容的话，需要将原数据全部迁移再扩容，大大降低了效率。

2.顺序表是从头开始且连续存储数据的，而当我们要在头部或是中间位置插入删除数据时，需要挪动数据，也大大降低了效率。

于是针对顺序表的缺陷设计出了链表

带头双向循环链表：

优点：1、可以任意插入删除数据，不需要挪动数据

          2.按需申请空间，再释放空间，不存在空间浪费

缺点：1、每存一个数据，都要存前后指针（当然也没太大的问题）

          2、每存一个数据就要malloc动态开辟空间

          3、不支持随即访问（硬伤），意味着一些排序，二分查找等在这种结构不适用

针对随机访问的问题，顺序表一白遮百丑，链表一黑毁所有。

同时顺序表的连续存储相比于链表的随即存储在读取速度上也占优势，这就涉及硬件方面的知识了，这里就不赘述了。

单链表源码

SList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct SingleListNode
{
	DataType data;
	struct SingleListNode* next;
}SListNode;

//打印链表
void SListNodePrint(SListNode* phead);
//链表尾插
void SListNodepushback(SListNode** pphead, DataType x);
//链表头插
void SListNodepushfront(SListNode** pphead, DataType x);
//链表尾删
void SListNodepopback(SListNode** pphead);
//链表头删
void SListNodepopfront(SListNode** pphead);
//寻找链表中数据所在的位置
SListNode* SListNodeFind(SListNode* phead, DataType x);
//链表指定pos位置前插入
void SListNodeInsert(SListNode** pphead, SListNode* pos, DataType x);
//链表指定pos位置后插入
void SListNodeInsertAfter(SListNode* pos, DataType x);
//链表指定pos位置删除数据
void SListNodeErase(SListNode** pphead, SListNode* pos);
//链表销毁
void SListNodeDestroy(SListNode** pphead);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

//创建新节点
SListNode* Creatnode(DataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

void SListNodePrint(SListNode* phead)
{	
	while (phead != NULL)
	{
		printf("%d->", phead->data);
		phead = phead->next;
	}
	printf("NULL\n");
}

void SListNodepushback(SListNode** pphead, DataType x)
{	
	assert(pphead);

	SListNode* newnode = Creatnode(x);
	if (*pphead == NULL)
		*pphead = newnode;
	else
	{
		SListNode* ret = *pphead;
		while (ret->next != NULL)
		{
			ret = ret->next;
		}
		ret->next = newnode;
	}
}

void SListNodepushfront(SListNode** pphead, DataType x)
{	
	assert(pphead);

	SListNode* newnode = Creatnode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListNodepopback(SListNode** pphead)
{	
	//链表为空不能删除
	assert(*pphead != NULL);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//两个及以上节点
	else
	{	
		SListNode* ret = *pphead;
		
		while (ret->next->next != NULL)
		{
			ret = ret->next;
		}
		free(ret->next);
		ret->next = NULL;
	}
}

void SListNodepopfront(SListNode** pphead)
{	
	//链表为空不能删除
	assert(*pphead != NULL);

	SListNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = NULL;
	*pphead = next;
}

SListNode* SListNodeFind(SListNode* phead, DataType x)
{	
	assert(phead != NULL);

	SListNode* cur = phead;
	//只能返回最开始找到的
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}
//从pos位置前插入
//void ChainListInsert(CListNode** pphead, CListNode* pos, DataType x)
//{	
// assert(pphead && pos);
// 
//	CListNode* newnode = Creatnode(x);
//	//直接头插
//	if (*pphead == pos)
//	{
//		newnode->next = *pphead;
//		*pphead = newnode;
//	}
//	else
//	{
//		CListNode* posPrev = *pphead;
//		//找pos的前一个节点
//		while (posPrev->next != pos)
//		{
//			posPrev = posPrev->next;
//		}
//		 newnode->next=posPrev->next;
//		 posPrev->next = newnode;
//	}
//}

//从pos后插入
void SListNodeInsertAfter(SListNode* pos, DataType x)
{	
	assert(pos);

	SListNode* newnode = Creatnode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SListNodeErase(SListNode**pphead, SListNode* pos)
{
	assert(*pphead && pos);

	//判断是否为头删
	if (*pphead == pos)
	{
		*pphead = pos->next;
		free(pos);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

void SListNodeDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void Test1()
{	
	SListNode* head = NULL;
	
	SListNodepushback(&head, 1);
	SListNodepushback(&head, 2);
	SListNodepushfront(&head, 4);
	SListNodepushfront(&head, 5);

	SListNodePrint(head);
}

void Test2()
{	
	SListNode* head = NULL;

	SListNodepushback(&head, 1);
	SListNodepushback(&head, 2);
	SListNodepushback(&head, 3);
	SListNodepopback(&head);
	SListNodepopback(&head);

	SListNodePrint(head);
}

void Test3()
{
	SListNode* head = NULL;

	SListNodepushback(&head, 1);
	SListNodepushback(&head, 2);
	SListNodepushback(&head, 3);
	SListNodepushback(&head, 4);
	SListNodepushback(&head, 5);
	
	/*SListNode* pos = SListNodeFind(head, 5);
	int i = 1;
	while (pos != NULL)
	{	
		printf("这是第%d个节点%p->%d\n", i++, pos, pos->data);
		if (pos->next == NULL)
			return;
		pos = SListNodeFind(pos->next, 5);
	}*/
	SListNode* pos = SListNodeFind(head, 5);
	if (pos != NULL)
	{
		SListNodeInsertAfter(pos, 10);
	}
	SListNodePrint(head);
}

int main()
{	
	Test1();
	Test2();
	Test3();
	
	return 0;
}

带头双向循环链表源码

List.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;

typedef struct ListNode
{
	DataType data;
	struct ListNode* next; //存放下一个节点
	struct ListNode* prev; //存放前一个节点
}ListNode;

//链表初始化，创建哨兵位头节点
ListNode* ListNodeInit();
//链表打印
void ListNodePrint(ListNode* phead);
//链表尾插
void ListNodePushBack(ListNode* phead, DataType x);
//链表尾删
void ListNodePopBack(ListNode* phead);
//链表头插
void ListNodePushFront(ListNode* phead, DataType x);
//链表头删
void ListNodePopFront(ListNode* phead);
//链表查找
ListNode* ListNodeFind(ListNode* phead, DataType x);
//链表指定pos位置前插入数据
void ListNodeInsert(ListNode* pos, DataType x);
//链表指定pos位置删除数据
void ListNodeErase(ListNode* pos);
//销毁链表
void ListNodeDestroy(ListNode* phead);

 List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "List.h"

//创建新节点
ListNode* ListNodeCreate(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	
	return newnode;
}
ListNode* ListNodeInit()
{	
	//创建哨兵位的头节点，方便尾插，对链表操作时也不用传二级指针了
	struct ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	phead->next = phead;
	phead->prev = phead;
	
	return phead;
}

void ListNodePrint(ListNode* phead)
{
	assert(phead);
	
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

void ListNodePushBack(ListNode* phead, DataType x)
{	
	assert(phead);
	//创建新节点
	ListNode* newnode = ListNodeCreate(x);
	ListNode* tail = phead->prev;
	
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
void ListNodePopBack(ListNode* phead)
{	
	assert(phead && phead->next != phead);//不能把头节点删了
	//找到尾节点
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;

	prev->next = phead;
	phead->prev = prev;
	
	free(tail);
}

void ListNodePushFront(ListNode* phead, DataType x)
{
	assert(phead);

	ListNode* newnode = ListNodeCreate(x);
	ListNode* next = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = next;
	next->prev = newnode;
}

void ListNodePopFront(ListNode* phead)
{	
	assert(phead && phead->next != phead); //不能把头节点删了

	ListNode* cur = phead->next;
	ListNode* next = cur->next;
	phead->next = next;
	next->prev = phead;
	free(cur);
}

ListNode* ListNodeFind(ListNode* phead, DataType x)
{	
	assert(phead);

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

void ListNodeInsert(ListNode* pos, DataType x)
{	
	assert(pos);

	ListNode* newnode = ListNodeCreate(x);
	ListNode* posprev = pos->prev;
	posprev->next = newnode;
	newnode->prev = posprev;
	newnode->next = pos;
	pos->prev = newnode;
}

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

void ListNodeDestroy(ListNode* phead)
{	
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{	
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	free(phead);
	phead = NULL;
}

Test.c

#include "List.h"

void Test1()
{
	ListNode* plist = ListNodeInit();
	ListNodePushBack(plist, 1);
	ListNodePushBack(plist, 2);
	ListNodePushBack(plist, 3);
	ListNodePushBack(plist, 4);
	ListNodePushBack(plist, 5);
	ListNodePrint(plist);

	ListNodePopBack(plist);
	ListNodePopBack(plist);
	ListNodePopBack(plist);
	ListNodePopBack(plist);
	ListNodePrint(plist);


}
void Test2()
{
	ListNode* plist = ListNodeInit();
	ListNodePushFront(plist, 1);
	ListNodePushFront(plist, 2);
	ListNodePushFront(plist, 3);
	ListNodePushFront(plist, 4);
	ListNodePushFront(plist, 5);
	ListNodePrint(plist);
	
	ListNodePopFront(plist);
	ListNodePopFront(plist);
	ListNodePrint(plist);

	ListNode* pos = ListNodeFind(plist, 3);
	if (pos != NULL)
		ListNodeInsert(pos, 4);
	ListNodePrint(plist);

	pos = ListNodeFind(plist, 2);
	if (pos != NULL)
		ListNodeErase(pos);
	ListNodePrint(plist);

	ListNodeDestroy(plist);
	plist = NULL;
}
int main()
{	
	//Test1();
	Test2();

	return 0;
}

不是看到希望才去坚持，而是坚持了才看到希望，那些看似不起波澜的日复一日，会在某天，让你看到坚持的意义，敬每一位努力奋斗的你和学习编程的你。希望我的文章能对你有所帮助。欢迎

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

链表

c语言

算法

数据结构——链表一网打尽 的相关文章

随机推荐

  • 用python 分析微信好友信息并生成词云

    在知乎上偶然看到有人推荐itchart这个微信接口 抱着好奇的想法尝试了以下 果然非常好玩 官方链接 http itchat readthedocs io zh latest itchat 目录结构 get info py这个类用来爬取好友

  • 超详细Ubuntu安装Anaconda步骤+Anconda常用命令

    目录 1 下载Anconda安装包 方法1 网页手动下载 方法2 wget命令下载 2 安装Anaconda STEP1 使用bash命令安装Anaconda STEP2 阅读并接受安装协议 STEP3 确认安装位置 STEP4 初始化An

  • Java常见排序：(三)快速排序

    快速排序是一种非常快的交换排序方法 思路很简单 将待排的数据序列中任意取一个数据作为分界值 所有比这个值小的放在左边 比他大的放在右边 形成左右两个子序列 左边的值都比分界值小 右边的值都比分界大 接下来对左右两个子序列进行递归 两个子序列

  • flask-项目实操2

    基本目录搭建 apps cms 后台 front 前台 common 共有的 static 静态 css cms front templates 模版html cms front bbs py 程序的入口 config py 配置文件 ma

  • 蓝桥杯——砝码称重（DP求解）

    问题描述 你有一架天平和 N个砝码 这 N个砝码重量依次是 W1 W2 Wn 请你计算一共可以称出多少种不同的重量 注意砝码可以放在天平两边 输入格式 输入的第一行包含一个整数 N 第二行包含 N个整数 W1 W2 W3 WN 输出格式 输

  • Java 截取String类型字符串截掉后两位

    String strhours String valueOf 123456 String strh strhours substring strhours length 2 strhours length 截取 String strm st

  • 2021-04-21--中标麒麟--yum源修改

    在安装 中标麒麟V7 后 执行 yum y update 会提示这样信息 无法拿到更新包 原因出自yum源的问题 而网上的麒麟源好多包都不能用 总结了一下 以下方法最实用 确实最快的 但是要求能够联网 如下 1 前提找到查看版本 查看版本的

  • 【网络安全】远程登陆虚拟专网实验

    远程登陆虚拟专网实验 文章目录 远程登陆虚拟专网实验 01 实验拓扑 02 实验命令 无客户端的SSL 胖客户端的SSL 03 实验过程 先进行无客户端的SSL实验过程 在WIN7上开启telnet服务 在XP上开启telnet服务 在WI

  • 计算机组成原理--基于Logisim的海明校验码解码电路实验的应用（超详细/设计/实验/作业/练习）

    目录 课程名 计算机组成原理 内容 作用 设计 实验 作业 练习 学习 基于Logisim的海明校验码解码电路 一 前言 二 环境与设备 三 内容 四 结果与分析 课程名 计算机组成原理 内容 作用 设计 实验 作业 练习 学习 基于Log

  • VueRouter: this.$route.push跳转,携带参数

    this router push传递参数有2种方式 传递参数 this router push path 路由 query key value 参数取值 this route query key 使用这种方式 传递参数会拼接在路由后面 出现

  • pc计算机参数表示什么,电脑cmos是什么意思？详细介绍cmos

    目前关于到电脑cmos是什么意思 CMOS简介这一类的信息是很多小伙伴们都非常关心的 很多人也是经常在搜索关于电脑cmos是什么意思 CMOS简介方面的信息 那么既然现在大家都想要知道此类的信息 小编就收集了一些相关的信息分享给大家 今天有

  • uniapp + uview —— 上传图片

    index vue

  • 显卡的相关性能参数含义(struct cudaDeviceProp)

    中文译注 英文见下文 struct cudaDeviceProp char name 256 器件的名字size t totalGlobalMem Global Memory 的byte大小size t sharedMemPerBlock

  • 手机报错：config:invalid signature问题；网页开发工具报错：config:fali，Error:系统错误，错误码：63002，invalidsignature问题

    折腾了几天发现是 java老哥单词少了一个字母 官方建议 invalid signature签名错误 建议按如下顺序检查 1 确认签名算法正确 可用http mp weixin qq com debug cgi bin sandbox t

  • spark算子执行位置研究，driver端？executor端？

    参考资料 https cloud tencent com developer article 1545723 前言 spark算子的执行位置 driver端 还是executor端 这些之前其实没有注意过 最近在学流处理 发现这个还是很重要

  • Ubuntu20.04 添加右键新建文件

    1 在主文件夹 模板目录下创建一个文件 如下指令 ubuntu ubuntu Templates sudo gedit 2 创建了文件后 直接点击保存即可 3 这时在其他目录下点击右键就可以看到新建文档

  • oracle比较两个时间

    to char date字段 HH24 MI SS between 07 00 00 and 09 30 00 或者 to char date字段 HH24 MI SS gt 07 00 00 and to char date字段 HH24

  • 在HTML中怎么去掉超链接(标签 a)的下划线？

    转自 http zhidao baidu com question 253614370 html qbl relate question 0 word a 20 C8 A5 CF C2 BB AE CF DF a href 超链接 a

  • 【C++·Qt】Qt信号与槽总结

    信号槽是Qt为我们提供的引以为傲的机制之一 它类似设计模式中的观察者模式 观察者模式是一种对象行为模式 它定义对象间的一种一对多的依赖关系 当一个对象的状态发生改变时 所有依赖于它的对象都得到通知并被自动更新 当某个信号signal发出时

  • 数据结构——链表一网打尽

    目录 前言 函数的传参 不带头单向非循环链表 带头双向循环链表 顺序表与链表的优缺点 单链表源码 带头双向循环链表源码 前言 链表是一种物理存储结构上非连续非线性的结构 数据元素的逻辑顺序通过指针次序链接实现 在逻辑结构上好像通过链子链接起

热门标签