C语言超详细讲解数据结构中双向带头循环链表

2024-09-29 08:46:03

一、概念

前文我们已经学习了单向链表，并通过oj题目深入了解了带头节点的链表以及带环链表，来画张图总体回顾下：

在我们学习的链表中，其实总共有8种，都是单双向和带不带头以及带不带环的任意组合

今儿要学习的是双向 - 带头 - 循环链表，听名字就觉着结构很复杂，要比曾经学的单向 - 不带头 - 不循环链表的结构复杂的多，确实也是。先来画张图整体感受下：

解释：

双向：就要确保每个数据存两个指针next和prev。next指向下一个节点，prev指向上一个节点
带头：带一个哨兵位的头节点在数据的最前头。
循环：尾节点的next指向哨兵位头节点，而哨兵位的上一个节点prev指向尾节点，构成循环。

正文开始：

二、必备工作

2.1、创建双向链表结构

因为是双向链表，所以在结构体里头必然有两个指针，一个next指向下一个节点，一个prev指向上一个节点。

List.h 文件：

//创建双向链表结构
typedef int LTDataType;   //方便后续更改数据类型，本文以int整型为主
typedef struct ListNode
{
	LTDataType data; //存储数据
	struct ListNode* next; //指向下一个
	struct ListNode* prev; //指向上一个
}LTNode; //方便后续使用，不需要重复些struct

2.2、初始化链表

思路：

在初始化的时候要传地址，因为形参的改变不会影响实参，pphead的改变不会影响pList，要传pList的地址，用**pphead来接收，此时就要assert断言了，因为二级指针地址不可能位空。因为是双向循环链表，所以要将创建好的哨兵位节点的next和prev均指向自己。

List.h 文件：（1）

//初始化链表（二级指针版）
void ListInit(LTNode* pphead);

List.c 文件：（1）

//初始化链表（二级指针版）
void ListInit(LTNode** pphead)
{
	//传二级指针，那么当然要断言
	assert(pphead);
	*pphead = BuyLTNode(0);//因为是带哨兵位的头节点，所以一开始就要给一个节点
	//为了循环，要让哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意优先级，*pphead要加括号
	(*pphead)->prev = *pphead;
}

注意：

上一种方法我们传的是二级指针，那么可以传一级指针吗，其实也是可以的，只需写个函数返回指针即可

List.h 文件：（2）

//初始化链表（一级指针版本）
LTNode* ListInit();

List.c 文件：（2）

//初始化链表（一级指针版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.3、动态申请节点

List.c 文件：

//创建新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新创建的节点
}

2.4、打印链表

思路：

既然是打印，首先要搞明白一点，哨兵位不用来存放有效数据，那么就不需要打印，定义一个cur指针来迭代，那么应该从phead的next开始打印，当cur走完一遍，重又回到phead的时候停止

List.h 文件：

//打印链表
void ListPrint(LTNode* phead);

List.c 文件：

//打印链表
void ListPrint(LTNode* phead)
{
	assert(phead);//断言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.5、销毁链表

思路：

既然是销毁链表了，那么自然是要把链表的所有元素包括哨兵位都给销毁掉，但毕竟刚开始传phead的时候是不能为空的，所以要断言，在把所有有效数据销毁后最后再销毁哨兵位即可。

法一：遍历

定义一个指针cur，从phead的next第一个有效数据开始free，保存下一个，再free，依次遍历下去

法二：附用ListErase函数

此法也可以，不过每次Erase完，都会把前后两个节点再链接起来，虽说最后都会销毁，但duck不必多此一举，所有直接采用法一比较好

List.h 文件：

//销毁链表
void ListDestory(LTNode* phead);

List.c 文件：

//销毁链表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//销毁从第一个节点到尾部的数据
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位节点phead
	free(phead);
	phead = NULL;
}

Test.c 文件：

void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//销毁链表
	ListDestory(pList);
	pList = NULL;
}

三、主要功能

3.1、在pos节点前插入数据

思路：

假设我们已经进行了尾插4个数字，现在想在数字3的前面插入30，那么首先就要查找有无数字3，若有，则插入。注意：这里需要用到后文才讲到的查找函数，这里直接引用了，详解看后文即可，问题不大！

首先，将30放到新创建的节点newnode里头，为了实现双向，要先把3的前一个数据2的next指向新节点newnode，把newnode的prev指向2，newnode的next指向3，3的prev指向newnode。

List.h 文件：

//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x);

List.c 文件：

//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//创建插入数据的新节点
	LTNode* newnode = BuyLTNode(x);
	//链接左侧
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//链接右侧
	newnode->next = pos;
	pos->prev = newnode;
}

Test.c 文件：

void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到数字3就插入
	}
	ListPrint(pList);//打印
}

效果如下：

尾插

思路：

首先，因为此链表是带哨兵位的头节点，所以头节点必然不为空，刚开始就要assert断言。其次，单链表尾插需要找尾，双向链表虽然也需要，不过非常简单，不需要再遍历链表了，因为哨兵位头节点的phead的上一个节点指向的就是尾，这就充分体现了双向循环的好处，找到了尾节点就需要再创建一个节点存储插入数据，方便尾插。

List.h 文件：

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

List.c 文件：1.0

//尾插1.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //断言，防止头节点为空
	LTNode* tail = phead->prev; //找到尾节点，便于后续插入数据
	LTNode* newnode = BuyLTNode(x);//创建新节点
	//将此新插入的尾节点与上一个节点链接起来
	tail->next = newnode;
	newnode->prev = tail;
	//将尾节点与哨兵位phead链接起来构成循环
	newnode->next = phead;
	phead->prev = newnode;
}

Test.c 文件：

void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
}

效果如下：

注意：

在上文中，我们学习了在pos前插入数据，那么设想一下，当pos就等于phead的时候，它（phead）的前不就是链表的尾部吗，那么理所应当，尾插也可以这样完成：

List.c 文件：2.0

//尾插2.0
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead, x);
}

头插

思路：

前面我们已经学习了在pos前插入数据，那么头插的实现就尤为简单了，当pos为原第一个数据phead->next时，此时就是在其之前插入数据，那么实现的不久是头插吗，如下：

List.h 文件：

//头插
void ListPushFront(LTNode* phead, LTDataType x);

List.c 文件：

//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

Test.c 文件：

void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //头插3个数字
	}
	ListPrint(pList);//打印
}

效果如下：

3.2、删除pos处节点数据

思路：

删除pos处数据其实也很简单，有点类似于把pos处直接忽略的思想，或者说是绕过去。首先，需要找到pos的上一个节点prev和下一个节点next，将prev和next互相链接即可，直接跳过了pos，这样就实现了删除pos处节点的数据，记得把pos处给free释放掉。这里我们以pos为2示例：

List.h 文件：

//删除pos处数据
void ListErase(LTNode* pos);

List.c 文件：

//删除pos处数据
void ListErase(LTNode* pos)
{
	assert(pos);
	//定义两个指针保存pos两边的节点
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//将prev和next链接起来
	prev->next = next;
	next->prev = prev;
	//free释放
	free(pos);
	pos = NULL;
}

Test.c 文件：

void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //删除pos处数据
		pos = NULL; //形参的改变不会影响实参，最好在这置空pos
	}
	ListPrint(pList);//打印
}

效果如下：

尾删

思路：

双向循环链表的特点将再次得以体现，根据其特性，我们知道phead的prev指向尾节点，用tail指针保存，再定义一个指针tailPrev指向tail的prev，现仅需将tailPrev的next指向哨兵位节点phead，再把哨兵位phead的prev重新置成tailPrev即可，但是别忘记把删掉的尾节点给释放掉，得free(tail)。记得要断言链表不能为空，因为不能删除哨兵位节点。

List.H 文件：

//尾删
void ListPopBack(LTNode* phead);

List.c 文件：1.0

//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能为空，要断言
	assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//释放尾节点
	free(tail);
	tail = NULL;
	//将链表循环起来
	tailPrev->next = phead;
	phead->prev = tailPrev;
}

Test.c 文件：

void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//尾删两次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}

效果如下：

注意：

前文我们已经学了删除pos处节点的数据，那么当pos为phead->prev时，删除的是不是就是尾节点，所以，尾删理所应当可以这样写：

List.c 文件：2.0

//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能为空，要断言
	assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点
	ListErase(phead->prev);
}

头删

思路：

有了上文之鉴，我们可以直接利用前面写的删除pos处数据的函数来完成，当pos为phead->prev时，pos的位置就是尾，此时删除的就是尾。当然还得注意一点，需要额外assert断言防止删除的数据为哨兵位的节点。

List.h 文件：

//头删
void ListPopFront(LTNode* phead);

List.c 文件：

//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止删除哨兵位节点
	ListErase(phead->next);
}

Test.c 文件：

void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//头插3个数字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾删3个数字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//头删3个数字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
}

效果如下：

3.3、查找数据

思路：

查找数据其实也比较简单，首先，定义一个指针cur指向哨兵位phead的next，依次遍历cur看cur->data是否为查找的数据x，如果是，则返回cur，否则继续（cur=cur->next），若找不到则返回NULL。

List.h 文件：

//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x);

List.c 文件：

//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}

四、总代码

List.h 文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//创建双向链表结构
typedef int LTDataType;   //方便后续更改数据类型，本文以int整型为主
typedef struct ListNode
{
	LTDataType data; //存储数据
	struct ListNode* next; //指向下一个
	struct ListNode* prev; //指向上一个
}LTNode; //方便后续使用，不需要重复些struct

//初始化链表（二级指针版本）
/*void ListInit(LTNode** pphead);*/
//初始化链表（一级指针版本）
LTNode* ListInit();

//打印链表
void ListPrint(LTNode* phead);
//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
//销毁链表
void ListDestory(LTNode* phead);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);
//尾删
void ListPopBack(LTNode* phead);
//头插
void ListPushFront(LTNode* phead, LTDataType x);
//头删
void ListPopFront(LTNode* phead);

//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x);
//删除pos处数据
void ListErase(LTNode* pos);

List.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//创建新节点
LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode; //返回新创建的节点
}
//初始化链表（二级指针版）
/*void ListInit(LTNode** pphead)
{
	//传二级指针，那么当然要断言
	assert(pphead);
	*pphead = BuyLTNode(0);//因为是带哨兵位的头节点，所以一开始就要给一个节点
	//为了循环，要让哨兵位的next和prev均指向自己
	(*pphead)->next = *pphead; //注意优先级，*pphead要加括号
	(*pphead)->prev = *pphead;
}*/
//初始化链表（一级指针版）
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

//打印链表
void ListPrint(LTNode* phead)
{
	assert(phead);//断言
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//链表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur; //找到就返回cur
		}
		cur = cur->next;
	}
	return NULL; //找不到就返回空
}
//销毁链表
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	//销毁从第一个节点到尾部的数据
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
	//置空哨兵位节点phead
	free(phead);
	phead = NULL;
}

//尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead); //断言，防止头节点为空
	/*
	法一：
	LTNode* tail = phead->prev; //找到尾节点，便于后续插入数据
	LTNode* newnode = BuyLTNode(x);//创建新节点
	//将此新插入的尾节点与上一个节点链接起来
	tail->next = newnode;
	newnode->prev = tail;
	//将尾节点与哨兵位phead链接起来构成循环
	newnode->next = phead;
	phead->prev = newnode;
	*/
	//法二：
	ListInsert(phead, x);
}
//尾删
void ListPopBack(LTNode* phead)
{
	assert(phead);//本身就有哨兵位，不能为空，要断言
	assert(phead->next != phead); //防止链表为空，导致删除哨兵位节点
	/*
	法一：
	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	//释放尾节点
	free(tail);
	tail = NULL;
	//将链表循环起来
	tailPrev->next = phead;
	phead->prev = tailPrev;
	*/
	//法二：
	ListErase(phead->prev);
}

//头插
void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
//头删
void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead); //防止删除哨兵位节点
	ListErase(phead->next);
}

//在pos前插入数据
void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
	//创建插入数据的新节点
	LTNode* newnode = BuyLTNode(x);
	//链接左侧
	pos->prev->next = newnode;
	newnode->prev = pos->prev;
	//链接右侧
	newnode->next = pos;
	pos->prev = newnode;
}
//删除pos处数据
void ListErase(LTNode* pos)
{
	assert(pos);
	//定义两个指针保存pos两边的节点
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	//将prev和next链接起来
	prev->next = next;
	next->prev = prev;
	//free释放
	free(pos);
	pos = NULL;
}

Test.c 文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void TestList1()
{
	//初始化（法一）
	/*LTNode* pList = NULL;
	ListInit(&pList);*/
	//初始化（法二）
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
}

void TestList2()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//尾删两次
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//再次打印
}

void TestList3()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListInsert(pos, 30); //找到数字3就插入
	}
	ListPrint(pList);//打印
}

void TestList4()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	for (int i = -2; i <= 0; i++)
	{
		ListPushFront(pList, i); //头插3个数字
	}
	ListPrint(pList);//打印
}

void TestList5()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数据
	}
	ListPrint(pList);//打印尾插的7个
	//寻找数字
	LTNode* pos = ListFind(pList, 3);
	if (pos)
	{
		ListErase(pos); //删除pos处数据
		pos = NULL; //形参的改变不会影响实参，最好在这置空pos
	}
	ListPrint(pList);//打印
}

void TestList6()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//头插3个数字
	ListPushFront(pList, 0);
	ListPushFront(pList, -1);
	ListPushFront(pList, -2);
	ListPrint(pList);//打印
	//尾删3个数字
	ListPopBack(pList);
	ListPopBack(pList);
	ListPopBack(pList);
	ListPrint(pList);//打印
	//头删3个数字
	ListPopFront(pList);
	ListPopFront(pList);
	ListPopFront(pList);
	ListPrint(pList);//打印
	//销毁链表
	ListDestory(pList);
	pList = NULL;
}

void TestList7()
{
	LTNode* pList = ListInit();
	for (int i = 1; i <= 7; i++)
	{
		ListPushBack(pList, i); //尾插7个数字
	}
	ListPrint(pList);//打印
	//销毁链表
	ListDestory(pList);
	pList = NULL;
}
int main()
{
	//TestList1();
	//TestList2();
	//TestList3();
	//TestList4();
	//TestList5();
	//TestList6();
	TestList7();
	return 0;
}

五、拓展

对比顺序表和链表

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除数据
缓存利用率	高	低

优缺点对比：

顺序表

链表

优点

1、物理空间是连续的，方便用下标随机访问。

2、CPU高速缓存命中率会更高。（补充）

1、按需申请释放空间。

2、任意位置可以O(1)插入删除数据。

缺点

1、正因为物理空间连续，空间不够需要扩容，扩容本身又一定消耗，其次扩容机制还存在一定的空间浪费。

2、头部或者中部插入删除，挪动数据，效率低，O(N)。

1、不支持下标的随机访问。

2、有些算法不适合在它上面进行，如：二分查找、排序等。

到此这篇关于C语言超详细讲解数据结构中双向带头循环链表的文章就介绍到这了,更多相关C语言双向带头循环链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C语言编程数据结构带头双向循环链表全面详解

目录前言一.什么是带头循环双向链表二.链表初始化三.链表接口函数 1.尾插 2.头插 3.头删 4.尾删 5.任意位置插入数据 6.任意位置删除数据四.打印链表总结前言上一篇数据结构专栏:C语言数据结构单链表接口函数全面讲解教程我们介绍了单链表的各个接口函数,大家可能会发现单链表存在一些缺陷:比如它一个节点要存储数据+下一个节点地址,占用的空间要远多于顺序表:并且由于单链表是无法从后往前找的,如果你想进行尾删这样的操作,你必须从第一个节点往后找,你的时间复杂度一定是O(n).
C语言实现带头双向循环链表

目录前言 1. 创建结构体 2.malloc新节点 3.创建哨兵位节点 4.尾插 5.打印 6.尾删 7.头插 8.在指定位置pos的前面进行插入 9. 删除指定位置pos节点 10.销毁链表前言在实际生活中最常用的就是这两种链表.无头单向非循环链表.和带头双向循环链表.无头单向非循环链表:结构简单,一般不会单独用来存数据.实际中更多是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.另外这种结构在笔试面试中出现很多.带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数
C语言实现带头双向循环链表的接口

本文实例为大家分享了C语言实现带头双向循环链表的接口,供大家参考,具体内容如下各函数功能如下申请空间 ListNode* BuyListNode(LTDataType x) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->next = NULL; node->prev = NULL; node->data = x; return node; } 初始化 ListNode* ListInit() { ListN
C语言超详细介绍与实现线性表中的带头双向循环链表

目录一.本章重点二.带头双向循环链表介绍 2.1什么是带头双向循环链表? 2.2最常用的两种链表结构三.带头双向循环链表常用接口实现 3.1结构体创建 3.2带头双向循环链表的初始化 3.3创建新节点 3.4尾插 3.5打印链表 3.6头插 3.7尾删 3.8头删 3.9查找data(返回data的节点地址) 3.10在pos位置之前插入节点 3.11删除pos位置的节点四.实现接口总结五.在线oj训练与详解一.本章重点带头双向循环链表介绍带头双向循环链表常用接口实现实现接
C语言超详细讲解数据结构中双向带头循环链表

目录一.概念二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表三.主要功能 3.1.在pos节点前插入数据尾插头插 3.2.删除pos处节点数据尾删头删 3.3.查找数据四.总代码 List.h 文件 List.c 文件 Test.c 文件五.拓展一.概念前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带
C语言超详细讲解数据结构中的线性表

目录前言一.分文件编写 1.分文件编写概念 2.代码展示二.动态分布内存malloc 1.初识malloc 2.使用方法三.创建链表并进行增删操作 1.初始化链表 2.在链表中增加数据 3.删除链表中指定位置数据四.代码展示与运行效果 1.代码展示 2.运行效果总结前言计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,
Java 超详细讲解数据结构中的堆的应用

目录一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度二.堆的插入和删除 1.堆的插入 2.堆的删除三.堆的应用 1.堆排序 2.top-k问题 [求最小的K个数] 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size,
Java 超详细讲解数据结构中的堆的应用

目录一.堆的创建 1.向下调整(以小堆为例) 2.创建堆 3.创建堆的时间复杂度二.堆的插入和删除 1.堆的插入 2.堆的删除三.堆的应用 1.堆排序 2.top-k问题(求最小的K个数) 四.常用接口的介绍 1.PriorityQueue的特性 2.优先级队列的构造一.堆的创建 1.向下调整(以小堆为例) 让parent标记需要调整的节点,child标记parent的左孩子(注意:parent如果有孩子一定先是有左孩子) 如果parent的左孩子存在,即:child < size, 进
C语言超详细讲解栈的实现及代码

目录前言栈的概念栈的结构栈的实现创建栈结构初始化栈销毁栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空总代码 Stack.h 文件 Stack.c 文件 Test.c 文件前言栈的概念栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.有点类似于手枪弹夹,后压进去的子弹总是最先打出,除非枪坏了. 压栈:栈的插入
C语言超详细讲解指向函数的指针

目录一.函数的指针二.指向函数的指针变量三.调用函数的两种方式四.指向函数的指针的作用五.用指向函数的指针作函数参数(重点) 六.为什么要将指向函数的指针变量作为函数的形参(重点) 一.函数的指针首先,函数名代表函数的起始地址,调用函数时,程序会从函数名获取到函数起始地址,并从该地址起执行函数中的代码,函数名就是函数的指针,所以我们可以定义一个指向函数的指针变量,用来存放函数的起始地址,这样一来,就可以通过该变量来调用其所指向的函数. 二.指向函数的指针变量定义指向函数的指针变量
C语言超详细讲解库函数

目录 1 返回整数的getchar函数 2 更新顺序文件 3 缓冲输出与内存分配 4 库函数练习 1 返回整数的getchar函数代码: #include<stdio.h> int main() { char c; while((c = getchar())!=EOF)//getchar函数的返回值为整型 putchar(c); return 0; } 上述代码有三种可能: 某些合法的输入字符在被"截断"后使得c的取值与EOF相同,程序将在复制的中途停止. c根本不可能
C语言超详细讲解算法的时间复杂度和空间复杂度

目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit
C语言超详细讲解字符串相乘

目录前言一. 分析思路二.使用步骤 1.代码如下 2.memset函数三.总结前言我们已经知道,正常的两位整形数据通过*相乘,C语言中int为4字节,32bit(字节),其机器码第一位为符号位,余下31位表示数字,表示范围:-2^31(-2147483648)~2^31-1(2147483647),但超过了这个范围我们该如何做呢? 提示:将数字以字符串的形式进行操作一. 分析思路示例: 我们把每一个数都看成是一个字符串,每一个元素为十进制数字所对应的字符,由于是后面的元素先进行
C语言超详细讲解排序算法上篇

目录 1.直接插入排序 2.希尔排序(缩小增量排序) 3.直接选择排序 4.堆排序进入正式内容之前,我们先了解下初阶常见的排序分类 :我们今天讲前四个! 1.直接插入排序基本思想:当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移! 直接插入排序的特性总结: 1. 元素集