当前位置: 首页 > article >正文

从零开始学链表:数据结构的基础与应用

嘿嘿,家人们,今天咱们来详细剖析数据结构中的链表,好啦,废话不多讲,开干!


1:链表

1.1:链表的概念以及结构

1.2:链表的分类

2:无头单向非循环链表的实现

2.1:Single_Linked_List.h

2.2:Single_Linked_List.c

2.2.1:打印链表与创建链表节点

2.2.2:头插与尾插节点

​2.2.3:头删节点与尾删节点 

2.2.4:查找节点与在position位置的前面插入节点

2.2.5:删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点

2.2.6:链表的销毁 

2.3:Test.c

2.3.1:测试打印链表与创建链表节点

2.3.2:测试头插与尾插

2.3.3:测试头删与尾删

2.3.4:测试查找与在position位置的前面添加节点 

2.3.6:测试删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点

2.3.7:测试链表的销毁

3:无头单向非循环链表的总代码

3.1:Single_Linked_List.h

3.2:Single_Linked_List.c

3.3:Test.c

4:带头双向循环链表的实现

4.1:Doubly_Circular_Linked_List.h

4.2:Doubly_Circular_Linked_List.c

4.2.1:初始化与创建节点与尾插

4.2.2:尾删与头插与头删数据

4.2.3:查找节点与在position位置的前面插入节点

4.2.4:删除position位置的节点与销毁链表

4.3:Test.c

4.3.1:测试初始化与创建节点与尾插

4.3.2:测试尾删与头插与头删数据

4.3.3:测试查找节点与在position位置的前面插入节点

4.3.4:测试删除position位置的节点与销毁链表

5:带头双向循环链表的总代码

5.1:Doubly_Circular_Linked_List.h

5.2:Doubly_Circular_Linked_List.c

5.3:Test.c

6:顺序表与链表的区别


1:链表

1.1:链表的概念以及结构

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

 

  • 链表的结构跟火车车厢相似, 淡季时⻋次的⻋厢会相应减少,旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉或者加上,不会影响其他⻋厢,每节⻋厢都是独立存在的.
  • ⻋厢是独立存在的,且每节⻋厢都有车门.可以想象⼀下介样滴的场景,假设每节⻋厢的车门都是锁上的状态,需要不同的钥匙才能解锁,每次只能携带⼀把钥匙的情况下如何从⻋头走到车尾?
最简单的做法:每节车厢里都放一把下⼀节车厢的钥匙.
  1. 从上图我们可以看到,链式结构在逻辑上是连续的,但是在物理上不一定连续.
  2. 现实中的节点一般都是从堆上申请出来的.
  3. 从堆上申请的空间,是按照一定的策略来进行分配的,两次申请的空间可能连续,也可能不连续.
  4. 与顺序表不同的是,链表里的每节"车厢"都是独立申请下来的空间,我们称之为"结点/结点",结点有以下两个组成部分:
  • 图中指针变量 plist保存的是第⼀个节点的地址,我们称plist此时"指向"第⼀个节点,如果我们想要plist“指向”第二个节点时,只需要修改plist保存的内容为0x0012FFB0.  
那么为什么还要指针变量来保存下一个节点的位置呢?
  • 链表中每个节点都是 独立申请 的( 即需要插⼊数据时才去申请⼀块节点的空间 ),我们需要通过指针变量来保存下⼀个节点位置才能从当前节点找到下⼀个节点.
结合前⾯学到的结构体知识,我们可以给出每个节点对应的结构体代码:
假设当前保存的节点为整型.
#include <stdio.h>

struct ListNode
{
	int Value;
	struct ListNode* Next;
};
当我们想要保存⼀个整型数据时,实际是向操作系统申请了⼀块内存,这个内存不仅要保存整型数据,也需要保存下⼀个节点的地址(当下⼀个节点为空时保存的地址为空).
当我们想要从第⼀个节点⾛到最后⼀个节点时,只需要在前⼀个节点拿上下⼀个节点的地址下⼀个节点的钥匙)就可以了.
假设在32位系统上,结点中值域为int类型, 则一个节点的大小为8个字节,则也有可能下面的链表.

1.2:链表的分类

实际中的链表的结构十分多样,组合起来有8种链表结构:

1.单向或双向

2.带头或不带头

3.循环或非循环

虽然链表的结构有如此之多,但实践中最常用的还是两种结构:无头单向非循环链表与带头双向循环链表. 

  1.  无头单向非循环链表:结构简单,⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等.
  2. 带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数据结构,都是带头双向循环链表.

2:无头单向非循环链表的实现

2.1:Single_Linked_List.h

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

//结构声明与函数声明

typedef int LKDataType;

typedef struct SingleList
{
	//存值
	LKDataType data;
	//指向下一个节点的地址
	struct SingleList* next;

}Slist;

//打印链表
void SlistPrint(Slist* phead);

//创建节点
Slist* SlistCreateNode(LKDataType value);

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value);

//头插数据
void SlistPushfront(Slist** pphead, LKDataType value);

//尾删数据
void SlistPopback(Slist** pphead);

//头删数据
void SlistPopfront(Slist** pphead);

//查找节点
Slist* SlistFindNode(Slist* position, LKDataType value);

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist* position, LKDataType value);

//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position);

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value);

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position);

//销毁链表
void SlistDestory(Slist** pphead);

2.2:Single_Linked_List.c

2.2.1:打印链表与创建链表节点

#include "Single_Linked_List.h"
//打印链表
void SlistPrint(Slist* phead)
{
	assert(phead);
	Slist* Current = phead;
	while(Current)
	{
		printf("%d->", Current->data);
		Current = Current->next;
	}
	printf("\n");
}


//创建节点
Slist* SlistCreateNode(LKDataType value)
{
	Slist* NewNode = (Slist *)malloc(sizeof(Slist));
	if(NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->data = value;
	NewNode->next = NULL;
	return NewNode;
}

2.2.2:头插与尾插节点

//头插数据
void SlistPushfront(Slist** pphead, LKDataType value)
{
	//确保plist的地址为有效地址
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//让创建的节点存储最初的头结点的地址;
	NewNode->next = *pphead;
	//让头节点存储新头结点的地址
	*pphead = NewNode;
}

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value)
{
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//链表为空即phead的地址为NULL
	//这里改变的是结构体的指针,一开始plist指向的地址是NULL
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		//先找到最后一个节点
		Slist* Current = *pphead;
		while(Current->next != NULL)
		{
			//这里改变的是结构体的成员
			Current = Current->next;
		}
		//然后在最后一个节点里存放新节点的地址
		Current->next = NewNode;
	}
}

2.2.3:头删节点与尾删节点 

//头删数据
void SlistPopfront(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//记录头节点
	Slist* temp = *pphead;
	//plist指向head的next
	*pphead = (*pphead)->next;
	//释放最初的头结点
	free(temp);
}

//尾删数据
void SlistPopback(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//单独处理一个节点的情况
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//找尾节点的前一个节点
	else
	{
		//记录头节点
		Slist* tail = *pphead;
		Slist* previous = NULL;
		while (tail->next)
		{
			//记录尾节点的前一个节点
			previous = tail;
			//这里改变的是结构体的成员
			tail = tail->next;
		}
		free(tail);
		//找尾之后直接释放(tail可置可不置)
		tail = NULL;
		//将上一个节点的所存储的地址置为空
		previous->next = NULL;
	}

}

2.2.4:查找节点与在position位置的前面插入节点

//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value)
{
	Slist* current = phead;
	while (current != NULL)
	{
		//根据值来进行查找
		if (current->data == value)
		{
			return current;
		}
		else
		{
			current = current->next;
		}
	}
	return NULL;
}

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist * position, LKDataType value)
{
	assert(pphead);
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	Slist* NewNode = SlistCreateNode(value);
	if (NewNode == NULL)
	{
		perror("CreateNode Fail");
		exit(-1);
	}
	//等于头结点,则是头插
	if (position == *pphead)
	{
		SlistPushfront(pphead, value);
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next != position)
		{
			Previous = Previous->next;
		}
		//新节点的next指针指向position位置
		NewNode->next = position;
		//position位置的前一个节点的next指针指向NewNode
		Previous->next = NewNode;
	}
}

有的uu会比较好奇,为什么链表的查找不是像顺序表那样子返回下标呢,

本质原因在于:链表是一种物理存储结构上非连续非顺序的存储结构,而顺序表是物理存储结构上连续的存储结构.

2.2.5:删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点

// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position)
{
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	if (*pphead == position)
	{
		*pphead = position->next;
		free(position);
		position = NULL;
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next  != position)
		{
			Previous = Previous->next;
		}
		Previous->next = position->next;
		free(position);
	}
}

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value)
{
	assert(position);
	Slist* NewNode = SlistCreateNode(value);
	if(NULL == NewNode)
	{
		perror("malloc fail");
		exit(-1);
	}
	NewNode->next = position->next;
	position->next = NewNode;
}

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position)
{
	assert(position);
	Slist* temp = position->next;
	position->next = temp->next;
	free(temp);
}

2.2.6:链表的销毁 

//销毁链表
void SlistDestory(Slist** pphead)
{
	assert(pphead);
	Slist* Current = *pphead;
	while(Current)
	{
		Slist* temp = Current->next;
		free(Current);
		Current = temp;
	}
	*pphead = NULL;
}

2.3:Test.c

2.3.1:测试打印链表与创建链表节点

#include "Single_Linked_List.h"

void TestCreateAndPrint(Slist ** pphead)
{
	*pphead = SlistCreateNode(1);
	(*pphead)->next = SlistCreateNode(2);
	(*pphead)->next->next = SlistCreateNode(3);
	(*pphead)->next->next->next = SlistCreateNode(4);
	(*pphead)->next->next->next->next = SlistCreateNode(5);
	SlistPrint(*pphead);
}

int main()
{
	Slist* phead = NULL;
	TestCreateAndPrint(&phead);
	return 0;
}

2.3.2:测试头插与尾插

#include "Single_Linked_List.h"

void TestPushFrontAndPushBack(Slist** pphead) 
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPrint(*pphead);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
}
int main()
{
	Slist* phead = NULL;
	TestPushFrontAndPushBack(&phead);
	return 0;
}

2.3.3:测试头删与尾删

#include "Single_Linked_List.h"

void TestPopFrontAndPopBack(Slist** pphead)
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
	//头删
	SlistPopfront(pphead);
	SlistPopfront(pphead);
	SlistPopfront(pphead);
	SlistPopfront(pphead);
	SlistPrint(*pphead);
	SlistPopback(pphead);
	SlistPopback(pphead);
	SlistPrint(*pphead);
}
int main()
{
	Slist* phead = NULL;
	TestPopFrontAndPopBack(&phead);
	return 0;
}

2.3.4:测试查找与在position位置的前面添加节点 

#include "Single_Linked_List.h"

void TestFindAndInsert(Slist** pphead)
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
	Slist* postion = SlistFindNode(*pphead, 5);
	SlistInsert(pphead,postion,1);
	postion = SlistFindNode(*pphead, 3);
	SlistInsert(pphead, postion, 0);
	SlistPrint(*pphead);
}

int main()
{
	Slist* phead = NULL;
	TestInsertAndDelete(&phead);
	return 0;
}

2.3.6:测试删除position位置的节点与删除position位置后面的节点以及在position位置后面添加节点

#include "single_linked_list.h"
void TestDeleteAndInsertAfter(Slist ** pphead)
{
	SlistPushfront(pphead, 6);
	SlistPushfront(pphead, 5);
	SlistPushfront(pphead, 4);
	SlistPushfront(pphead, 3);
	SlistPushback(pphead, 7);
	SlistPushback(pphead, 8);
	SlistPushback(pphead, 9);
	SlistPrint(*pphead);
	Slist* position = SlistFindNode(*pphead, 5);
	//删除5这个节点
	SlistDelete(pphead, position);
	position = SlistFindNode(*pphead, 3);
	//删除头节点
	SlistDelete(pphead, position);
	SlistPrint(*pphead);
	printf("-------------------------\n");
	position = SlistFindNode(*pphead, 4);
	SlistInsertAfter(position, 10);
	SlistPrint(*pphead);
	printf("-------------------------\n");
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistPrint(*pphead);
}

int main()
{
	Slist* phead = NULL;
	TestDeleteAndInsertAfter(&phead);
	return 0;
}

2.3.7:测试链表的销毁

#define  _CRT_SECURE_NO_WARNINGS
#include "single_linked_list.h"

//测试头插和尾插
void test1(Slist** list)
{
	printf("头插与尾插:>");
	SlistPushfront(&(*list), 0);
	SlistPushfront(&(*list), 1);
	SlistPushfront(&(*list), 2);
	SlistPushfront(&(*list), 3);
	SlistPushfront(&(*list), 4);
	SlistPushback(&(*list), 5);
	SlistPushback(&(*list), 6);
	SlistPushback(&(*list), 7);
	SlistPrint(*list);
}


int main()
{
	Slist* list = NULL;
	test1(&list);
	SlistDestory(&list);
	return 0;
}

3:无头单向非循环链表的总代码

3.1:Single_Linked_List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
//结构声明与函数声明

typedef int LKDataType;

typedef struct SingleList
{
	//存值
	LKDataType data;
	//指向下一个节点的地址
	struct SingleList* next;

}Slist;

//打印链表
void SlistPrint(Slist* phead);

//创建节点
Slist* SlistCreateNode(LKDataType value);

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value);

//头插数据
void SlistPushfront(Slist** pphead, LKDataType value);

//尾删数据
void SlistPopback(Slist** pphead);

//头删数据
void SlistPopfront(Slist** pphead);

//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value);

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist* position, LKDataType value);

//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position);

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value);

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position);

//销毁链表
void SlistDestory(Slist** pphead);

3.2:Single_Linked_List.c

#include "Single_Linked_List.h"

//打印链表
void SlistPrint(Slist* phead)
{
	assert(phead);
	Slist* Current = phead;
	while(Current)
	{
		printf("%d->", Current->data);
		Current = Current->next;
	}
	printf("\n");
}

//创建节点
Slist* SlistCreateNode(LKDataType value)
{
	Slist* NewNode = (Slist *)malloc(sizeof(Slist));
	if(NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->data = value;
	NewNode->next = NULL;
	return NewNode;
}

//头插数据
void SlistPushfront(Slist** pphead, LKDataType value)
{
	//确保plist的地址为有效地址
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//让创建的节点存储最初的头结点的地址;
	NewNode->next = *pphead;
	//让头节点存储新头结点的地址
	*pphead = NewNode;
}

//尾插数据
void SlistPushback(Slist** pphead, LKDataType value)
{
	assert(pphead);
	Slist* NewNode = SlistCreateNode(value);
	//链表为空即phead的地址为NULL
	//这里改变的是结构体的指针,一开始plist指向的地址是NULL
	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		//先找到最后一个节点
		Slist* Current = *pphead;
		while(Current->next != NULL)
		{
			//这里改变的是结构体的成员
			Current = Current->next;
		}
		//然后在最后一个节点里存放新节点的地址
		Current->next = NewNode;
	}
}


//头删数据
void SlistPopfront(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//记录头节点
	Slist* temp = *pphead;
	//plist指向head的next
	*pphead = (*pphead)->next;
	//释放最初的头结点
	free(temp);
}

//尾删数据
void SlistPopback(Slist** pphead)
{
	assert(pphead);
	//空节点不能删
	assert(*pphead);
	//单独处理一个节点的情况
	if((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//找尾节点的前一个节点
	else
	{
		//记录头节点
		Slist* tail = *pphead;
		Slist* previous = NULL;
		while (tail->next)
		{
			//记录尾节点的前一个节点
			previous = tail;
			//这里改变的是结构体的成员
			tail = tail->next;
		}
		free(tail);
		//找尾之后直接释放(tail可置可不置)
		tail = NULL;
		//将上一个节点的所存储的地址置为空
		previous->next = NULL;
	}

}

//查找节点
Slist* SlistFindNode(Slist* phead, LKDataType value)
{
	Slist* current = phead;
	while (current != NULL)
	{
		//根据值来进行查找
		if (current->data == value)
		{
			return current;
		}
		else
		{
			current = current->next;
		}
	}
	return NULL;
}

//在position位置的前面添加数据
void SlistInsert(Slist** pphead, Slist * position, LKDataType value)
{
	assert(pphead);
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	Slist* NewNode = SlistCreateNode(value);
	if (NewNode == NULL)
	{
		perror("CreateNode Fail");
		exit(-1);
	}
	//等于头结点,则是头插
	if (position == *pphead)
	{
		SlistPushfront(pphead, value);
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next != position)
		{
			Previous = Previous->next;
		}
		//新节点的next指针指向position位置
		NewNode->next = position;
		//position位置的前一个节点的next指针指向NewNode
		Previous->next = NewNode;
	}
}

//删除
// position位置的删除数据
void SlistDelete(Slist** pphead, Slist* position)
{
	//防止一个为空与一个不为空的情况(链表是空的,但是position这一节点不存在)
	assert((!position && !(*pphead)) || (position && *pphead));
	if (*pphead == position)
	{
		*pphead = position->next;
		free(position);
		position = NULL;
	}
	else
	{
		Slist* Previous = *pphead;
		//找到position位置的前一个节点
		while(Previous->next  != position)
		{
			Previous = Previous->next;
		}
		Previous->next = position->next;
		free(position);
	}
}

//postion后面位置的添加数据
void SlistInsertAfter(Slist* position, LKDataType value)
{
	assert(position);
	Slist* NewNode = SlistCreateNode(value);
	if(NULL == NewNode)
	{
		perror("malloc fail");
		exit(-1);
	}
	NewNode->next = position->next;
	position->next = NewNode;
}

//position后面位置的删除数据
void SlistDeleteAfter(Slist* position)
{
	assert(position);
	Slist* temp = position->next;
	position->next = temp->next;
	free(temp);
}


//销毁链表
void SlistDestory(Slist** pphead)
{
	assert(pphead);
	Slist* Current = *pphead;
	while(Current)
	{
		Slist* temp = Current->next;
		free(Current);
		Current = temp;
	}
	*pphead = NULL;
}

3.3:Test.c

#define  _CRT_SECURE_NO_WARNINGS
#include "single_linked_list.h"

//测试头插和尾插
void test1(Slist** list)
{
	printf("头插与尾插:>");
	SlistPushfront(&(*list), 0);
	SlistPushfront(&(*list), 1);
	SlistPushfront(&(*list), 2);
	SlistPushfront(&(*list), 3);
	SlistPushfront(&(*list), 4);
	SlistPushback(&(*list), 5);
	SlistPushback(&(*list), 6);
	SlistPushback(&(*list), 7);
	SlistPrint(*list);
}

//测试头删和尾删
void test2(Slist** list)
{
	printf("头删与尾删:>");
	SlistPopback(&(*list));
	SlistPopback(&(*list));
	SlistPopback(&(*list));
	SlistPopfront(list);
	SlistPopfront(list);
	SlistPrint(*list);
}

//测试查找与任意位置的增加
void test3(Slist** list)
{
	//链表与要插入的位置都为空的情况
	Slist* position = SlistFindNode(*list, 2);
	SlistInsert(&(*list), position, 5);
	SlistPrint(*list);
	position = SlistFindNode(*list, 5);
	SlistInsert(&(*list), position, 8);
	SlistInsert(&(*list), position, 9);
	SlistInsert(&(*list), position, 10);
	SlistPrint(*list);
}

//测试查找与任意位置的删除
void test4(Slist** list)
{

	SlistPushfront(list, 3);
	Slist* position = SlistFindNode(*list, 10);
	SlistPrint(*list);
	SlistDelete(list, position);
	SlistPrint(*list);

	SlistPushback(list, 5);
	SlistPushback(list, 6);
	SlistPushback(list, 7);
	SlistPushfront(list, 4);
	SlistPushfront(list, 3);
	position = SlistFindNode(*list, 5);
	SlistDelete(list, position);
	SlistPrint(*list);
}
//测试在position位置之后的数据添加与删除与链表销毁
void test5(Slist** list)
{
	SlistPushback(list, 5);
	SlistPushback(list, 6);
	SlistPushback(list, 7);
	SlistPushfront(list, 4);
	SlistPushfront(list, 3);
	SlistPrint(*list);

	Slist* position = SlistFindNode(*list, 5);
	SlistInsertAfter(position, 20);
	SlistInsertAfter(position, 30);
	SlistPrint(*list);

	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistDeleteAfter(position);
	SlistPrint(*list);
	SlistDestory(list);
}

int main()
{
	Slist* list = NULL;
	test1(&list);
	test2(&list);
	test3(&list);
	test4(&list);
	test5(&list);
	return 0;
}

4:带头双向循环链表的实现

4.1:Doubly_Circular_Linked_List.h

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

typedef int CircularDatatype;

typedef struct CircularList
{
	struct CircularList* next;
	struct CircularList* previos;
	CircularDatatype value; 
}CircularList;

//创建节点
CircularList* CreateNewnode(CircularDatatype value);

//初始化带头双向循环链表
void CircularListInit(CircularList** phead);

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value);

//尾删数据
void CircularListPopback(CircularList* phead);

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value);

//头删数据
void CircularListPopfront(CircularList* phead);

//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value);

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion,CircularDatatype value);


//删除postion位置的节点
void  CircularListErase(CircularList* phead,CircularList* position);

//销毁链表
void CircularListDestory(CircularList* phead);

//打印带头双向循环链表
void CircularListPrint(CircularList* phead);

4.2:Doubly_Circular_Linked_List.c

4.2.1:初始化与创建节点与尾插

#include "Doubly_Circular_Linked_List.h"

//创建节点
CircularList* CreateNewnode(CircularDatatype value)
{
	CircularList* NewNode = (CircularList *)malloc(sizeof(CircularList));
	if (NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->value = value;
	NewNode->previos = NULL;
	NewNode->next = NULL;
	return NewNode;
}

//打印带头双向循环链表
void CircularListPrint(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		printf("%d->", Current->value);
		Current = Current->next;
	}
}
//初始化带头双向循环链表
void CircularListInit(CircularList** pphead)
{
	//确保传过来的地址是有效地址
	assert(pphead);
	//创建哨兵位的头结点
	*pphead = CreateNewnode(-1);
	//指向自己
	(*pphead)->previos = *pphead;
	(*pphead)->next = *pphead;
}

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	//创建节点
	CircularList* NewNode = CreateNewnode(value);
	if(NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	CircularList* tail = phead->previos;
	//新节点的前驱链接旧链表的尾节点
	NewNode->previos = tail;
	//旧尾节点存储新尾节点的地址
	tail->next = NewNode;
	//哨兵位的前驱节点链接新节点
	phead->previos = NewNode;
	//新节点的next指针指向头结点
	NewNode->next = phead;
}

4.2.2:尾删与头插与头删数据

//尾删数据
void CircularListPopback(CircularList* phead)
{
	assert(phead);
	CircularList* tail = phead->previos;
	//哨兵位的前驱节点指向尾节点的前驱
	phead->previos = tail->previos;
	//尾节点的前驱节点的next指向哨兵位
	tail->previos->next = phead;
	free(tail);
	tail = NULL;
}

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* NewNode = CreateNewnode(value);
	if (NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//记录旧的头结点
	CircularList* OldHead = phead->next;
	//哨兵位的next指针指向NewNode
	phead->next = NewNode;
	//新节点的前驱指向哨兵位
	NewNode->previos = phead;
	//新节点的后驱指向旧的头节点
	NewNode->next = OldHead;
	//旧的头结点的前驱指向NewNode
	OldHead->previos = NewNode;
}

//头删数据
void CircularListPopfront(CircularList* phead)
{
	assert(phead);
	//保存旧的头节点
	CircularList* OldHead = phead->next;
	//哨兵位头节点的next指针指向旧的头节点的next
	phead->next = OldHead->next;
	//旧的头节点的下一个节点的前驱节点指向哨兵位
	OldHead->next->previos = phead;
	free(OldHead);
}

4.2.3:查找节点与在position位置的前面插入节点

//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* Current = phead;
	while(Current->next != phead)
	{
		if (Current->value == value)
			return Current;
		Current = Current->next;
	}
	return NULL;
}

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value)
{
	assert(postion);
	CircularList* NewNode = CreateNewnode(value);
	//新节点的前驱指向posituon位置的前一个节点
	NewNode->previos = postion->previos;
	//新节点的next指向position节点
	NewNode->next = postion;
	//position位置的前一个节点next指向新节点
	postion->previos->next = NewNode;
	//position位置的节点的前驱指向NewNode
	postion->previos = NewNode;
}

4.2.4:删除position位置的节点与销毁链表

//删除postion位置的节点
void  CircularListErase(CircularList* phead, CircularList* position)
{
	assert(phead);
	CircularList* temp = position->previos;
	//temp的next指针指向position的下一个节点
	temp->next = position->next;
	//position的下一个节点的前驱指向temp
	position->next->previos = temp;
}

//销毁链表
void CircularListDestory(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		CircularList* temp = Current->next;
		free(Current);
		Current = temp;
	}
}

4.3:Test.c

4.3.1:测试初始化与创建节点与尾插

#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

void TestInitAndPushBack(CircularList ** List)
{
	CircularListInit(List);
	CircularListPushback(*List,1);
	CircularListPushback(*List,2);
	CircularListPushback(*List,3);
	CircularListPrint(*List);
}

int main()
{
	CircularList* List;
	TestInitAndPushBack(&List);
	return 0;
}

4.3.2:测试尾删与头插与头删数据

#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

void TestPushFrontAndPopFrontAndPopBack(CircularList** List)
{
	CircularListInit(List);
	CircularListPushback(*List, 1);
	CircularListPushback(*List, 2);
	CircularListPushback(*List, 3);
	CircularListPrint(*List);
	CircularListPopback(*List);
	CircularListPopback(*List);
	CircularListPrint(*List);
	CircularListPushfront(*List, 5);
	CircularListPushfront(*List, 4);
	CircularListPushfront(*List, 6);
	CircularListPrint(*List);
	CircularListPopfront(*List);
	CircularListPopfront(*List);
	CircularListPrint(*List);

}

int main()
{
	CircularList* List;
	//TestInitAndPushBack(&List);
	TestPushFrontAndPopFrontAndPopBack(&List);
	return 0;
}

4.3.3:测试查找节点与在position位置的前面插入节点

#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

void TestFindAndInsert(CircularList** List)
{
	CircularListInit(List);
	CircularListPushback(*List, 1);
	CircularListPushback(*List, 2);
	CircularListPushback(*List, 3);

	CircularListPrint(*List);
	CircularList* position = CircularListFind(*List, 2);
	CircularListInsert(position, 4);
	position = CircularListFind(*List, 1);
	CircularListInsert(position, 25);
	CircularListPrint(*List);
}

int main()
{
	CircularList* List;
	TestFindAndInsert(&List);
	return 0;
}

4.3.4:测试删除position位置的节点与销毁链表

#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"


void TestEraseAndDestory(CircularList** List)
{
	CircularListInit(List);
	CircularListPushback(*List, 1);
	CircularListPushback(*List, 2);
	CircularListPushback(*List, 3);

	CircularListPrint(*List);
	CircularList* position = CircularListFind(*List, 2);
	CircularListInsert(position, 4);
	position = CircularListFind(*List, 1);
	CircularListPrint(*List);
	printf("\n");

	CircularListErase(*List, position);
	position = CircularListFind(*List, 2);
	CircularListErase(*List, position);
	CircularListPrint(*List);
	CircularListDestory(*List);
	//释放哨兵位的头结点
	free(*List);
	*List = NULL;
	CircularListPrint(*List);
}

int main()
{
	CircularList* List;
	TestEraseAndDestory(&List);
	return 0;
}

5:带头双向循环链表的总代码

5.1:Doubly_Circular_Linked_List.h

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

typedef int CircularDatatype;

typedef struct CircularList
{
	struct CircularList* next;
	struct CircularList* previos;
	CircularDatatype value;
}CircularList;

//创建节点
CircularList* CreateNewnode(CircularDatatype value);

//初始化带头双向循环链表
void CircularListInit(CircularList** phead);

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value);

//尾删数据
void CircularListPopback(CircularList* phead);

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value);

//头删数据
void CircularListPopfront(CircularList* phead);

//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value);

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value);


//删除postion位置的节点
void  CircularListErase(CircularList* phead, CircularList* position);

//销毁链表
void CircularListDestory(CircularList* phead);

//打印带头双向循环链表
void CircularListPrint(CircularList* phead);

5.2:Doubly_Circular_Linked_List.c

#include "Doubly_Circular_Linked_List.h"

//创建节点
CircularList* CreateNewnode(CircularDatatype value)
{
	CircularList* NewNode = (CircularList *)malloc(sizeof(CircularList));
	if (NewNode == NULL)
	{
		perror("malloc fail\n");
		exit(-1);
	}
	NewNode->value = value;
	NewNode->previos = NULL;
	NewNode->next = NULL;
	return NewNode;
}

//打印带头双向循环链表
void CircularListPrint(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		printf("%d->", Current->value);
		Current = Current->next;
	}
	printf("\n");
}
//初始化带头双向循环链表
void CircularListInit(CircularList** pphead)
{
	//确保传过来的地址是有效地址
	assert(pphead);
	//创建哨兵位的头结点
	*pphead = CreateNewnode(-1);
	//指向自己
	(*pphead)->previos = *pphead;
	(*pphead)->next = *pphead;
}

//尾插数据
void CircularListPushback(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	//创建节点
	CircularList* NewNode = CreateNewnode(value);
	if(NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	CircularList* tail = phead->previos;
	//新节点的前驱链接旧链表的尾节点
	NewNode->previos = tail;
	//旧尾节点存储新尾节点的地址
	tail->next = NewNode;
	//哨兵位的前驱节点链接新节点
	phead->previos = NewNode;
	//新节点的next指针指向头结点
	NewNode->next = phead;
}

//尾删数据
void CircularListPopback(CircularList* phead)
{
	assert(phead);
	CircularList* tail = phead->previos;
	//哨兵位的前驱节点指向尾节点的前驱
	phead->previos = tail->previos;
	//尾节点的前驱节点的next指向哨兵位
	tail->previos->next = phead;
	free(tail);
	tail = NULL;
}

//头插数据
void CircularListPushfront(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* NewNode = CreateNewnode(value);
	if (NewNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	//记录旧的头结点
	CircularList* OldHead = phead->next;
	//哨兵位的next指针指向NewNode
	phead->next = NewNode;
	//新节点的前驱指向哨兵位
	NewNode->previos = phead;
	//新节点的后驱指向旧的头节点
	NewNode->next = OldHead;
	//旧的头结点的前驱指向NewNode
	OldHead->previos = NewNode;
}

//头删数据
void CircularListPopfront(CircularList* phead)
{
	assert(phead);
	//保存旧的头节点
	CircularList* OldHead = phead->next;
	//哨兵位头节点的next指针指向旧的头节点的next
	phead->next = OldHead->next;
	//旧的头节点的下一个节点的前驱节点指向哨兵位
	OldHead->next->previos = phead;
	free(OldHead);
}

//查找节点
CircularList* CircularListFind(CircularList* phead, CircularDatatype value)
{
	assert(phead);
	CircularList* Current = phead;
	while(Current->next != phead)
	{
		if (Current->value == value)
			return Current;
		Current = Current->next;
	}
	return NULL;
}

//在position位置的前面添加数据
void CircularListInsert(CircularList* postion, CircularDatatype value)
{
	assert(postion);
	CircularList* NewNode = CreateNewnode(value);
	//新节点的前驱指向posituon位置的前一个节点
	NewNode->previos = postion->previos;
	//新节点的next指向position节点
	NewNode->next = postion;
	//position位置的前一个节点next指向新节点
	postion->previos->next = NewNode;
	//position位置的节点的前驱指向NewNode
	postion->previos = NewNode;
}

//删除postion位置的节点
void  CircularListErase(CircularList* phead, CircularList* position)
{
	assert(phead);
	CircularList* temp = position->previos;
	//temp的next指针指向position的下一个节点
	temp->next = position->next;
	//position的下一个节点的前驱指向temp
	position->next->previos = temp;
}

//销毁链表
void CircularListDestory(CircularList* phead)
{
	assert(phead);
	CircularList* Current = phead->next;
	while(Current != phead)
	{
		CircularList* temp = Current->next;
		free(Current);
		Current = temp;
	}
}

5.3:Test.c

#define  _CRT_SECURE_NO_WARNINGS
#include "Doubly_Circular_Linked_List.h"

//测试初始化,尾删与尾插
void test1(CircularList* phead)
{
	printf("尾插与尾删:>");
	CircularListInit(&phead);
	CircularListPushback(phead, 1);
	CircularListPushback(phead, 2);
	CircularListPushback(phead, 3);
	CircularListPushback(phead, 4);
	CircularListPushback(phead, 5);
	CircularListPushback(phead, 6);
	CircularListPopback(phead);
	CircularListPopback(phead);
	CircularListPopback(phead);
	CircularListPrint(phead);

}
//测试头插与头删
void test2(CircularList* phead)
{
	printf("头插与头删:>");
	CircularListInit(&phead);
	CircularListPushfront(phead, 0);
	CircularListPushfront(phead, 1);
	CircularListPushfront(phead, 2);
	CircularListPushfront(phead, 3);
	CircularListPushfront(phead, 4);
	CircularListPushfront(phead, 5);
	CircularListPushfront(phead, 6);

	CircularListPopfront(phead);
	CircularListPopfront(phead);
	CircularListPopfront(phead);
	CircularListPopfront(phead);
	CircularListPrint(phead);
}

//测试查找与在position位置的前面添加数据与删除position位置的数据
void test3(CircularList* phead)
{
	CircularListInit(&phead);
	CircularListPushfront(phead, 3);
	CircularListPushfront(phead, 4);
	CircularListPushfront(phead, 5);
	CircularListPushfront(phead, 6);
	CircularListPushfront(phead, 7);
	CircularList* position = CircularListFind(phead, 5);
	if (position != NULL)
	{
		position->value = position->value * 15;
	}
	CircularListInsert(position, 72);
	CircularListInsert(position, 73);
	CircularListInsert(position, 74);
	CircularListPrint(phead);
	if (position != NULL)
	{
		CircularListErase(phead, position);
		position = NULL;
	}
	CircularListPrint(phead);
}
//测试销毁链表
void test4(CircularList* phead)
{
	CircularListInit(&phead);
	CircularListPushfront(phead, 3);
	CircularListPushfront(phead, 4);
	CircularListPushfront(phead, 5);
	CircularListPushfront(phead, 6);
	CircularListPushfront(phead, 7);
	CircularListPrint(phead);
	CircularListDestory(phead);
	phead = NULL;
}

int main()
{
	CircularList* phead = NULL;
	test1(phead);
	test2(phead);
	test3(phead);
	test4(phead);
}

6:顺序表与链表的区别

不同点顺序表链表
存储空间上物理和逻辑上一定连续逻辑上连续,但是物理上不一定连续.

访问方式

随机访问,O(1)不支持随机访问,O(N)
任意位置插入与删除可能需要迁移元素,O(N);只需要修改指针指向
插入动态顺序表,空间不够时需要扩容.没有容量的概念
应用场景
元素高效存储 + 频繁访问
元素高效存储 + 频繁访问
缓存利用率

 好啦,uu们,数据结构链表这部分滴详细内容博主就讲到这里啦,如果uu们觉得博主讲的不错的话,请动动你们滴小手给博主点点赞,你们滴鼓励将成为博主源源不断滴动力,同时也欢迎大家来指正博主滴错误~


http://www.kler.cn/a/373552.html

相关文章:

  • (实战)WebApi第10讲:Swagger配置、RESTful与路由重载
  • 基于Java SpringBoot和Vue社区医院诊所医疗挂号管理系统设计
  • [ 问题解决篇 ] 解决windows虚拟机安装vmtools报错-winserver2012安装vmtools及安装KB2919355补丁 (附离线工具)
  • 10.30学习
  • MFC工控项目实例二十七添加产品参数
  • AI基础:A*算法解八数码问题
  • 如何防止U盘盗取电脑数据?
  • 架构师备考-系统分析与设计(结构化方法)
  • 字符串、字节流与十六进制字符串的转换:Python、C 和 Go 的实现对比20241029
  • 【AI时代】普通程序员想投身AI大模型行业,该如何快速入局
  • 2024 10.25 判断一个矩阵是否对称
  • Centos安装配置Jenkins
  • Mybatis使用和原理
  • matplotlilb画图
  • js实现异步和延时
  • 隨便 20241028 ISR 和 OSR 在 Kafka 中的详细解析
  • Nginx部署前端需要了解的知识
  • EfficientNet-B6模型实现ISIC皮肤镜图像数据集分类
  • 整合SSM框架(2)
  • 雷赛DMC5X10系列脉冲运动控制卡——机械原点和工作原点原理
  • BGP 及 4+ 的一些特性及配置笔记
  • 外包干了7天,技术明显退步。。。。。
  • Go:package
  • 传奇架设教程,M2报错无法找到城堡信息文件的解决方法
  • 【c++篇】:模拟实现string类--探索字符串操作的底层逻辑
  • oracle获取中文拼音/WB