《数据结构:C语言实现双链表》

一、链表的分类

链表的结构非常多样,以下情况组合起来就有八种(2×2×2)链表结构:

在这里插入图片描述

虽然有这么多的链表的结构,但我们实际中最常用的还是两种结构:单链表和双向带头循环链表.

  • 1、无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。
  • 2、带头双向循环链表:结构复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单,后面我们代码实现了就知道了。

二、双向链表

1、概念与结构

在这里插入图片描述

  • 注意:这⾥的“带头”跟前⾯我们说的“头结点”是两个概念,实际前⾯的在单链表阶段称呼不严谨.

带头链表中的头结点,实际为“哨兵位”,哨兵位结点补存储任何有效元素,只是站在这里“放哨的”

三、双向链表实现

1、双向链表要实现的功能

List.h文件中:

#pragma once

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

typedef int LTDateType;

typedef struct ListNode
{
	LTDateType date;
	struct ListNode* next;//存放下个节点的地址
	struct ListNode* prev;//存放上一个结点的地址
}LT;

//初始化哨兵位
void LTInit(LT** pphead);

//初始化哨兵位,串一级指针更方便
LT* LTInit02();

//头插
void LTPushFornt(LT* phead,LTDateType x);

//尾插
void LTPushBack(LT* phead,LTDateType x);

//打印数据
void LTPrint(LT* phead);

//头删
void LTPopFront(LT* phead);

//尾删
void LTPopBack(LT* phead);

//判断链表是否为空
bool LTEmpty(LT* phead);

//返回数据所在结点
LT* LTFind(LT* phead, LTDateType x);

//在pos结点之后插入数据
void LTInsert(LT* pos, LTDateType x);

//删除pos结点的数据
void LTErase(LT* pos);

//销毁结点
void LTDesTroy(LT** pphead);

//穿一级指针销毁,需要手动置空
void LTDeaTroy02(LT* phead);
2、哨兵位初始化
//开辟结点空间
LT* LTBuyNode(LTDateType x)
{
	LT* newnode = (LT*)malloc(sizeof(LT));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->date = x;
	newnode->next = newnode;
	newnode->prev = newnode;
}


//初始化哨兵位
void LTInit(LT** pphead)
{
	assert(pphead != NULL);
	*pphead = LTBuyNode(-1);
}

//初始化哨兵位,串一级指针更方便
LT* LTInit02()
{
	LT* newnode = LTBuyNode(-1);
	return newnode;
}
3、双链表头插数据
//头插
void LTPushFornt(LT* phead, LTDateType x)
{
	assert(phead != NULL);
	LT* newnode = LTBuyNode(x);
	newnode->next = phead->next;
	newnode->prev = phead;
	phead->next->prev = newnode;
	phead->next = newnode;

}
4、判断链表是否为空
//判断链表是否为空
bool LTEmpty(LT* phead)
{
	assert(phead != NULL);

	return phead->prev == phead;
}
5、打印链表数据
//打印数据
void LTPrint(LT* phead)
{
	assert(phead != NULL);
	LT* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->date);
		pcur = pcur->next;
	}
	printf("\n");
}
6、尾插数据
//尾插
void LTPushBack(LT* phead, LTDateType x)
{
	assert(phead != NULL);
	LT* newnode = LTBuyNode(x);
	newnode->prev = phead->prev;
	newnode->next = phead;
	phead->prev->next = newnode;
	phead->prev = newnode;
}
7、头删数据
//头删
void LTPopFront(LT* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LT* del = phead->next;
	phead->next = del->next;
	del->next->prev = phead;
	free(del);
	del = NULL;
}
8、尾删数据
//尾删
void LTPopBack(LT* phead)
{
	assert(phead);
	assert(!LTEmpty(phead));
	LT* del = phead->prev;
	phead->prev = del->prev;
	del->prev->next = phead;
	free(del);
	del = NULL;
}
9、寻找数据所在结点
//返回数据所在结点
LT* LTFind(LT* phead, LTDateType x)
{
	assert(phead);
	LT* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->date == x)
		{
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
10、在任意结点之后插入数据
//在pos结点之后插入数据
void LTInsert(LT* pos, LTDateType x)
{
	assert(pos != NULL);
	LT* newnode = LTBuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}
11、删除任意结点
//删除pos结点的数据
void LTErase(LT* pos)
{
	assert(pos);
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
12、销毁链表
//销毁结点
void LTDesTroy(LT** pphead)
{
	assert(pphead);
	LT* pcur = (*pphead)->next;
	while (pcur != *pphead)
	{
		LT* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(*pphead);
	*pphead = pcur = NULL;
}

//穿一级指针销毁,需要手动置空
void LTDeaTroy02(LT* phead)
{
	assert(phead);
	LT* pcur = phead->next;
	while (pcur != phead)
	{
		LT* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	free(phead);
	phead = pcur =NULL;
}

相关推荐

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 22:20:01       103 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 22:20:01       114 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 22:20:01       93 阅读
  4. Python语言-面向对象

    2024-07-20 22:20:01       99 阅读

热门阅读

  1. 网络安全-网络安全及其防护措施6

    2024-07-20 22:20:01       23 阅读
  2. [C++ 入门基础 - 命名空间]

    2024-07-20 22:20:01       20 阅读
  3. SharedPreferences 和 MMKV 是何方神圣

    2024-07-20 22:20:01       24 阅读
  4. 力扣1942.最小未被占据椅子的编号

    2024-07-20 22:20:01       23 阅读
  5. linux LED代码设计

    2024-07-20 22:20:01       27 阅读
  6. 【深度学习图像】拼接图的切分

    2024-07-20 22:20:01       25 阅读
  7. dp算法第三天(暑期提升)

    2024-07-20 22:20:01       28 阅读
  8. RabbitMQ 全面解析与常见问题解答

    2024-07-20 22:20:01       26 阅读
  9. 关于大数据技术栈的一些总结

    2024-07-20 22:20:01       25 阅读
  10. 酒茶元宇宙:探索科技与传统文化的融合

    2024-07-20 22:20:01       22 阅读