C语言中带头双向循环链表基本操作的实现详解

目录
  • 一、概念与结构
  • 二、基本操作的实现
    • 1.创建结点
    • 2.初始化链表
    • 3.打印链表
    • 4.尾插
    • 5.尾删
    • 6.头插
    • 7.头删
    • 8.查找某个数并返回其指针
    • 9.在某个位置之前插入
    • 10.删除某个位置
    • 11.判断链表是否为空
    • 12.计算链表中有效值的个数
    • 13.销毁链表
  • 三、测试代码

一、概念与结构

无头单向非循环链表结构简单,一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。而带头双向循环链表的结构较为复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表,虽然它的结构复杂但是因为结构优势用代码实现起来会变得简单。

二、基本操作的实现

1.创建结点

LTNode* BuyListNode(ListDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    if (newnode == NULL)
    {
        perror("malloc");
        exit(-1);
    }
    newnode->val = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

2.初始化链表

void ListInit(LTNode** pphead)//初始化
{
    *pphead = (LTNode*)malloc(sizeof(LTNode));
    *pphead = BuyListNode(-1);
    (*pphead)->next = *pphead;
    (*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
//    LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1;
//    phead->next = phead;
//    phead->prev = phead;
//    return phead;
//}

初始化链表有两种方式,一种是有返回类型(注释部分),另一种是在初始化函数中给结构体开辟空间(不过注意参数要为二级指针)。因为是带头结点的循环链表,所以prev和next指针都指向自己。

3.打印链表

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

注意while循环的结束条件,保证能够打印链表中的所有有效值。要对头结点进行assert判断,不能为空。

4.尾插

void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
    assert(phead);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = phead->prev;
    newnode->next = tail->next;
    phead->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;
    //ListInsert(phead, x);
}

5.尾删

void ListPopBack(LTNode* phead)//尾删
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* prevnode = phead->prev;
    prevnode->prev->next = phead;
    phead->prev = prevnode->prev;
    free(prevnode);
    //ListErase(phead->prev);
}

尾删时要注意判断phead->next != phead,不能删除头结点,同时记得要free(prevnode)释放删除后的空间。

6.头插

void ListPushFront(LTNode* phead, ListDataType x)//头插
{
    assert(phead);
    LTNode* tail = phead->next;
    LTNode* newnode = BuyListNode(x);
    tail->prev = newnode;
    newnode->next = tail;
    newnode->prev = phead;
    phead->next = newnode;
    //ListInsert(phead->next,x);
}

7.头删

void ListPopFront(LTNode* phead)//头删
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* tail = phead->next;
    phead->next = tail->next;
    tail->next->prev = phead;
    //ListErase(phead->next);
}

8.查找某个数并返回其指针

LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->val == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

9.在某个位置之前插入

void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    LTNode* tail = pos->prev;
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = pos;
    pos->prev = newnode;
}

10.删除某个位置

void ListErase(LTNode* pos)//删除pos位置
{
    assert(pos);
    LTNode* prevnode = pos->prev;
    LTNode* nextnode = pos->next;
    free(pos);
    prevnode->next = nextnode;
    nextnode->prev = prevnode;
    /*pos->next->prev = pos->prev;
    pos->prev->next = pos->next;
    free(pos);*/
}

11.判断链表是否为空

bool ListEmpty(LTNode* phead)//判断是否为空,如果是空,返回true
{
    assert(phead);
    return phead->next == phead;
}

12.计算链表中有效值的个数

size_t ListSize(LTNode* phead)//计算链表中有效值的个数
{
    assert(phead);
    size_t size = 0;
    LTNode* tail = phead->next;
    while (tail != phead)
    {
        size++;
        tail = tail->next;
    }
    return size;
}

13.销毁链表

void ListDestroy(LTNode* phead)//销毁链表
{
    assert(phead);
    LTNode* tail = phead->next;
    while (tail != phead)
    {
        LTNode* nextnode = tail->next;
        free(tail);
        tail = nextnode;
    }
    free(phead);
}

销毁链表时要注意要保证每个结点都释放,同时最后也要将头结点释放free(phead)。

三、测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int ListDataType;
typedef struct ListNode {
	ListDataType val;
	struct ListNode* prev;
	struct ListNode* next;
}LTNode;
LTNode* BuyListNode(ListDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->prev = NULL;
	newnode->next = NULL;
	return newnode;
}
void ListInit(LTNode** pphead)//初始化
{
	*pphead = (LTNode*)malloc(sizeof(LTNode));
	*pphead = BuyListNode(-1);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;
}
//LTNode* ListInit()//初始化
//{
//	LTNode* phead = BuyListNode(-1);//初始化时将头结点置为-1;
//	phead->next = phead;
//	phead->prev = phead;
//	return phead;
//}

void ListPrint(LTNode* phead)//打印
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->val);
		cur = cur->next;
	}
	printf("\n");
}
void ListPushBack(LTNode* phead, ListDataType x)//尾插
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;
	newnode->next = tail->next;
	phead->prev = newnode;
	newnode->prev = tail;
	tail->next = newnode;
	//ListInsert(phead, x);
}
void ListPopBack(LTNode* phead)//尾删
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* prevnode = phead->prev;
	prevnode->prev->next = phead;
	phead->prev = prevnode->prev;
	free(prevnode);
	//ListErase(phead->prev);
}
void ListPushFront(LTNode* phead, ListDataType x)//头插
{
	assert(phead);
	LTNode* tail = phead->next;
	LTNode* newnode = BuyListNode(x);
	tail->prev = newnode;
	newnode->next = tail;
	newnode->prev = phead;
	phead->next = newnode;
	//ListInsert(phead->next,x);
}
void ListPopFront(LTNode* phead)//头删
{
	assert(phead);
	assert(phead->next != phead);
	LTNode* tail = phead->next;
	phead->next = tail->next;
	tail->next->prev = phead;
	//ListErase(phead->next);
}
LTNode* ListFind(LTNode* phead, ListDataType x)//找某个数返回其指针
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void ListInsert(LTNode* pos, ListDataType x)//在pos之前插入
{
	assert(pos);
	LTNode* newnode = BuyListNode(x);
	LTNode* tail = pos->prev;
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = pos;
	pos->prev = newnode;
}
void ListErase(LTNode* pos)//删除pos位置
{
	assert(pos);
	LTNode* prevnode = pos->prev;
	LTNode* nextnode = pos->next;
	free(pos);
	prevnode->next = nextnode;
	nextnode->prev = prevnode;
	/*pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);*/
}
bool ListEmpty(LTNode* phead)//判断是否为空,如果是空,返回true
{
	assert(phead);
	return phead->next == phead;
}
size_t ListSize(LTNode* phead)//计算链表中有效值的个数
{
	assert(phead);
	size_t size = 0;
	LTNode* tail = phead->next;
	while (tail != phead)
	{
		size++;
		tail = tail->next;
	}
	return size;
}
void ListDestroy(LTNode* phead)//销毁链表
{
	assert(phead);
	LTNode* tail = phead->next;
	while (tail != phead)
	{
		LTNode* nextnode = tail->next;
		free(tail);
		tail = nextnode;
	}
	free(phead);
}
void TestList()
{
	//LTNode* plist = ListInit(&plist);
	LTNode* plist = NULL;
	ListInit(&plist);
	ListPushBack(plist, 100);
	ListPushBack(plist, 200);
	ListPushBack(plist, 300);
	ListPushBack(plist, 400);
	ListPushBack(plist, 500);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPopBack(plist);
	ListPrint(plist);
	ListPushFront(plist, 1000);
	ListPushFront(plist, 2000);
	ListPushFront(plist, 3000);
	ListPopFront(plist);
	ListPopFront(plist);
	ListPrint(plist);
	LTNode* pos = ListFind(plist, 1000);
	if (pos != NULL)
	{
		ListInsert(pos, 500);
		ListErase(pos);
	}
	ListPrint(plist);
	if (!ListEmpty(plist))
		printf("%d\n", ListSize(plist));
}
int main()
{
	TestList();
	return 0;
}

以上就是C语言中带头双向循环链表基本操作的实现详解的详细内容,更多关于C语言 带头双向循环链表的资料请关注我们其它相关文章!

(0)

相关推荐

  • 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语言详解如何实现带头双向循环链表

    目录 创建链表存储结构 创建结点 链表的初始化 双向链表的打印 双向链表尾插 双向链表尾删 双向链表头插 双向链表头删 双向链表查找 双向链表pos前插入结点 双向链表删除pos位置的结点 双向链表的销毁 顺序表和链表的区别 2022042311415360.{C}{C}png" /> 创建链表存储结构 我们需要创建一个结构体来存储一个链表结点的相关信息. typedef int ListDataType;//将ListDataType先定义为int类型,根据需要可以改为不同的类型 //创

  • C语言手把手带你掌握带头双向循环链表

    目录 前言 带头双向循环链表的结构 代码操作 前言 关于链表这一块,写了多篇博客,学习了顺序表.单链表.及其一些练习题 顺序表:传送门:顺序表 单链表:传送门:单链表1   链表2 链表OJ:传送门:链表OJ 今天,我又来水一水博客, 介绍关于双链表. 带头双向循环链表的结构 实际上,单链表也存在一个比较大的缺陷: 1.不能从后往前遍历 2.无法找到前驱 除了单链表之外,我们自然还有双向链表,我们要说的就是带头双向循环链表,简单理解为:带头结点的,有两个方向的.循环的.结构图如下: 结构虽然比较

  • C语言带头双向循环链表的示例代码

    目录 前言 结构分析 链表的基本操作实现 创建节点 初始化链表 链表销毁 打印链表 链表尾插 链表尾删 链表头插 链表头删 链表查找 链表pos位置前面去插入 删除pos位置 链表判空 代码复用 总代码及头文件 前言 对于链表来说,不只有单链表这一个品种: 链表有很多种形态 按方向分:单向.双向 按带不带头:带头.不带头 按循环:循环.不循环 1.单向或则双向: 2.带头或者不带头: 3.循环或者不循环: 组合排列一下的话,链表一共有8种形态!!! 今天我们就来学习一下结构最复杂的带头双向循环链

  • C语言实现带头双向循环链表

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

  • 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语言如何实现双向带头循环链表

    目录 一.双向循环链表与顺序表的区别 二.List.h 三.List.c 1.带头双向循环链表的初始化 2.带头双向循环链表的销毁 3.带头双向循环链表的打印 4.动态开辟一个节点 5.带头双向循环链表的判空 6.带头双向循环链表的尾插.尾删 7.带头双向循环链表的头插.头删 8.带头双向循环链表的长度 9.带头双向循环链表的查找.任意位置插入.删除 一.双向循环链表与顺序表的区别 不同点 顺序表 双向带头循环链表 在内存中的存储方式 连续存储 不一定连续 随机访问 支持随机访问 不支持随访问

  • C语言中带头双向循环链表基本操作的实现详解

    目录 一.概念与结构 二.基本操作的实现 1.创建结点 2.初始化链表 3.打印链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个数并返回其指针 9.在某个位置之前插入 10.删除某个位置 11.判断链表是否为空 12.计算链表中有效值的个数 13.销毁链表 三.测试代码 一.概念与结构 无头单向非循环链表结构简单,一般不会单独用来存数据.实际中更多的是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.而带头双向循环链表的结构较为复杂,一般用在单独存储数据.实际中使用的链表数据结构,都

  • C语言实现顺序表的基本操作的示例详解

    目录 一.认识顺序表 1.线性表 2.顺序表的概念及结构 二.顺序表的基本操作(接口实现) 1.初始化顺序表 2.打印顺序表 3.尾插 4.尾删 5.扩容 6.头插 7.头删 8.任意位置插入 9.任意位置删除 10.查找某个数的位置 三.顺序表演示及代码(含源码) 1.演示效果 2.完整源代码 一.认识顺序表 1.线性表 线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表有顺序表.链表.栈.队列.字符串……线性表在逻辑上是线性结构,也就是说是一条

  • C语言中函数参数的入栈顺序详解及实例

    C语言中函数参数的入栈顺序详解及实例 对技术执着的人,比如说我,往往对一些问题,不仅想做到"知其然",还想做到"知其所以然".C语言可谓博大精深,即使我已经有多年的开发经验,可还是有许多问题不知其所以然.某天某地某人问我,C语言中函数参数的入栈顺序如何?从右至左,我随口回答.为什么是从右至左呢?我终究没有给出合理的解释.于是,只好做了个作业,于是有了这篇小博文. #include void foo(int x, int y, int z) { printf(&quo

  • C语言中 值传递和指针传递实例详解

    C语言中 值传递和指针传递实例详解 在C语言中,函数的参数和返回值的传递方式有两种:值传递和指针传递. 值传递和指针传递初学者总会有一种朦胧的感觉,所以建议把指针传递的概念摸透,才能熟练应用. 值传递示例:x其实是n的一份临时拷贝,所以并不会改变n的值. #include <stdio.h> #include <windows.h> void Fun(int x) { x = 1; } int main() { int n = 2; Fun(n); printf("%d\

  • C语言中的指针以及二级指针代码详解

    很多初学者都对C中的指针很迷糊,希望这篇blog能帮助到大家: 1.什么是"指针": 在执行C程序的时候,由于我们的数据是存储在内存中的.所以对于C程序本身来说,如果想找到相应被调用的数据,就要知道存储该数据的内存地址是多少,换言之,C程序通过已知的内存地址到相应的内存位置存储数据. 这里简单说一下内存管理(对于初学者来说.为了避免专业术语引发的理解问题,下面的叙述尽量避免专业定义:),对于现代计算机系统来说,内存空间分为两个区域,一个是"数据区",一个是"

  • C++ 双向循环链表类模版实例详解

    目录 1.插入某个节点流程 2.构造函数修改 3.重新实现append和prepend函数 4.修改迭代器类 5.LinkedList.h代码如下 6.测试运行 总结 在上章C++图解单向链表类模板和iterator迭代器类模版详解 我们学习了单链表,所以本章来学习双向循环链表 我们在上个文章代码上进行修改, 由于双向循环链表在我们之前学的单链表上相对于较为复杂,所以需要注意的细节如下所示. 1.插入某个节点流程 如下图所示: 对应代码如下所示: /*插入一个新的节点*/ bool insert

  • C语言中炫酷的文件操作实例详解

    目录 什么是文件 程序文件 数据文件 (本文重点) 文件名 文件的打开和关闭 文件指针 文件函数 相对路径与绝对路径 输入输出流 二进制读写 fwirte fread 总结 什么是文件 磁盘上的文件是文件 但是在程序设计中,我们一般谈的文件有两种:程序文件和数据文件(从文件功能的角度来分类). 程序文件 包括源程序文件(例如.c文件)目标文件(windows环境后缀为.obj)可执行程序(windos环境后缀为exe). 数据文件 (本文重点) 文件的内容不一定是程序,而是程序运行时读写的数据,

  • C语言中字符串的两种定义方式详解

    目录 方式1 方式2 总结 我们知道C语言中是没有字符串这种数据类型的,我们只能依靠数组进行存储,即字符数组,而我们定义并且初始化数组有两种方式.下面将给大家介绍这两种方式并且介绍这两种方式的区别: 方式1 前两种是正确的定义方式,第一种之所以没有指定字符数组长度的原因是编译器能够自己推断出其长度,无需程序员自己设定,这也是我们比较推荐的一种定义方式,但注意内存长度编译器一经判定就无法再次更改,接下来我们分析一下第三种编译器为什么会出现乱码. 相信大家都知道,字符串是以'\0'字符为结束标志的,

随机推荐