详解C语言如何实现双向带头循环链表

目录
  • 一、双向循环链表与顺序表的区别
  • 二、List.h
  • 三、List.c
    • 1、带头双向循环链表的初始化
    • 2、带头双向循环链表的销毁
    • 3、带头双向循环链表的打印
    • 4、动态开辟一个节点
    • 5、带头双向循环链表的判空
    • 6、带头双向循环链表的尾插、尾删
    • 7、带头双向循环链表的头插、头删
    • 8、带头双向循环链表的长度
    • 9、带头双向循环链表的查找、任意位置插入、删除

一、双向循环链表与顺序表的区别

不同点 顺序表 双向带头循环链表
在内存中的存储方式 连续存储 不一定连续
随机访问 支持随机访问 不支持随访问
任意元素插入或删除 尾插O(1),其他O(N),可能需要挪动元素 通过修改指针指向即可
应用场景 元素高效存储、频繁访问 任意位置插入删除频繁
三级缓存命中率

寄存器的速度远快于主存,所以需要三级缓存先将数据取出,寄存器读取时将相邻地址的数据进行读取,所以顺序表内存地址连续的特点使其三级缓存命中率高。

双向带头循环链表虽然在链表中结构最复杂,但是解决了单链表找前一个节点需要遍历、要判断头结点是否为空的缺点。

二、List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int ListDateType;
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    ListDateType date;
}ListNode;
ListNode* ListInit();//初始化
void ListDestroy(ListNode* phead);//销毁
void PrintList(ListNode* phead);//打印
bool ListEmpty(ListNode* phead);//判断链表是否为空(只有头节点)

void ListPushBack(ListNode* phead, ListDateType x);//尾插
void ListPopback(ListNode* phead);//尾删
void ListPushFront(ListNode* phead, ListDateType x);//头插
void ListPopFront(ListNode* phead);//头删
size_t ListSize(ListNode* phead);//有效节点个数
ListNode* ListFind(ListNode* phead, ListDateType x);//查找(可用于修改)
void ListInsert(ListNode* pos, ListDateType x);//pos位置插入
void ListErase(ListNode* pos);//删除pos位置

结构体内包含指向下一个节点的指针next、指向上一个节点的指针prev和本节点存储的数据date

三、List.c

1、带头双向循环链表的初始化

ListNode* ListInit()//初始化,返回带哨兵位的头结点
{
    ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
    if (guard == NULL)
    {
        perror("ListInit fail:\n");
        exit(-1);
    }
    guard->next = guard;
    guard->prev = guard;
    return guard;
}

malloc一个哨兵位的头结点,并将其next和prev指针置空。

2、带头双向循环链表的销毁

void ListDestroy(ListNode* phead)//销毁,传一级指针调用方需要在外部将头结点指针置空
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)//释放非头结点
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);//再释放头结点
}

为了保持接口的一致性,形参用一级指针,所以需要调用者在外部对头指针置空。

先释放非头结点,再释放头结点。

3、带头双向循环链表的打印

void PrintList(ListNode* phead)//打印
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d<=>", cur->date);
        cur = cur->next;
    }
    printf("\n");
}

从头结点的next开始,遍历打印

4、动态开辟一个节点

ListNode* BuyNode(ListDateType x)//动态开辟一个节点
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("BuyNode:\n");
        exit(-1);
    }
    newnode->date = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

将值放入这个节点,并将两个指针置空

5、带头双向循环链表的判空

bool ListEmpty(ListNode* phead)//判断链表是否只有头节点
{
    assert(phead);
    return phead->next == phead;
}

只有哨兵位这一个头结点即为空

6、带头双向循环链表的尾插、尾删

void ListPushBack(ListNode* phead, ListDateType x)//尾插
{
    assert(phead);
    ListNode* tail = phead->prev;
    ListNode* newnode = BuyNode(x);
    newnode->next = phead;
    newnode->prev = tail;
    tail->next = newnode;
    phead->prev = newnode;
}
void ListPopback(ListNode* phead)//尾删
{
    assert(phead);
    assert(!ListEmpty(phead));
    ListNode* tail = phead->prev;
    ListNode* prev = tail->prev;
    free(tail);
    prev->next = phead;
    phead->prev = prev;
}

注意尾删前需要判空

7、带头双向循环链表的头插、头删

void ListPushFront(ListNode* phead, ListDateType x)//头插
{
    assert(phead);
    ListNode* cur = phead->next;
    ListNode* newnode = BuyNode(x);
    newnode->next = cur;
    newnode->prev = phead;
    cur->prev = newnode;
    phead->next = newnode;
}
void ListPopFront(ListNode* phead)//头删
{
    assert(phead);
    assert(!ListEmpty(phead));
    ListNode* cur = phead->next;
    ListNode* next = cur->next;
    free(cur);
    phead->next = next;
    next->prev = phead;
}

注意头删前需要判空

8、带头双向循环链表的长度

size_t ListSize(ListNode* phead)//有效节点个数
{
    assert(phead);
    ListNode* cur = phead->next;
    size_t count = 0;
    while (cur != phead)
    {
        cur = cur->next;
        ++count;
    }
    return count;
}

循环计数即可,哨兵位不算

9、带头双向循环链表的查找、任意位置插入、删除

ListNode* ListFind(ListNode* phead, ListDateType x)//查找(可用于修改)
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur!=phead)
    {
        if (cur->date == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
void ListInsert(ListNode* pos, ListDateType x)//pos位置之前插入
{
    assert(pos);
    ListNode* newnode = BuyNode(x);
    ListNode* prev = pos->prev;
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}
void ListErase(ListNode* pos)//删除pos位置
{
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;
    free(pos);
    prev->next = next;
    next->prev = prev;
}

查找:遍历链表,返回第一个date==x的节点指针,查找通常配合下面两个接口使用

任意位置插入、删除:使用pos位置进行插入删除操作。

头插、头删、尾插、尾删接口可以复用上面三个接口

到此这篇关于详解C语言如何实现双向带头循环链表的文章就介绍到这了,更多相关C语言双向带头循环链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

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

  • 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语言数据结构之双向循环链表的实例

    数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

  • C语言详解如何实现带头双向循环链表

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

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

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

  • 详解C语言中双向循环链表的实现

    目录 实现细节 辅助理解图 具体实现代码 1.对链表进行初始化 2.任意位置前的插入 3.任意位置的删除 4.头插和尾删 完整代码 头文件 具体函数 测试 实现细节 1.带一个哨兵位(哨兵节点,初始节点,不存储有效数据,用来方便后期数据的存储与查找) 2.与单向链表不同的是,双向链表中每个数据节点包含两个指针,分别指向前后两个节点 3.双向链表是循环的,其尾节点后不是空指针,而是与头部的哨兵节点通过指针相连 辅助理解图 具体实现代码 1.对链表进行初始化 初始化:哨兵位的前后指针均指向哨兵节点本

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

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

  • 详解C语言如何实现双向带头循环链表

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

  • 详解go语言的并发

    1.启动go语言的协程 package main   import (     "fmt"     "runtime" )   //runtime包   func main() {     //runtime.Gosched() 用于让出cpu时间片,让出这段cpu的时间片,让调度器重新分配资源       //写一个匿名函数     s := "test"     go func(s string) {         for i :=0;i

  • 详解C语言中二级指针与链表的应用

    目录 前言 二级指针讲解 链表的应用 定义双链表的结构体 创建双链表 前言 这篇文章即将解决你看不懂或者不会写链表的基本操作的问题,对于初学者而言,有很多地方肯定是费解的.比如函数的参数列表的多样化,动态分配内存空间函数malloc等,其实这些知识和指针联系紧密,尤其是二级指针.那么开始好好的学习这篇文章吧! 二级指针讲解 简述:其实就是一个指针指向另一个指针的地址. 我们都知道指针指向地址,但是指针自身也是一个变量,当然也可以被二级指针所指向. 语法:形如 int x = 10; int *q

  • Vuejs第一篇之入门教程详解(单向绑定、双向绑定、列表渲染、响应函数)

    什么是组件? 组件(Component)是 Vue.js 最强大的功能之一.组件可以扩展 HTML 元素,封装可重用的代码.在较高层面上,组件是自定义元素,Vue.js 的编译器为它添加特殊功能.在有些情况下,组件也可以是原生 HTML 元素的形式,以 is 特性扩展. 接下来给大家介绍vuejs单向绑定.双向绑定.列表渲染.响应函数基础知识,具体详情如下所示: (一)单向绑定 <div id="app"> {{ message }} </div> <sc

  • 详解C语言函数返回值解析

    详解C语言函数返回值解析 程序一: int main() { int *p; int i; int*fun(void); p=fun(); for(i=0;i<3;i++) { printf("%d\n",*p); p++; } return 0; }; int* fun(void) { static int str[]={1,2,3,4,5}; int*q=str; return q; } //不能正确返回 虽然str是在动态变量区,而该动态变量是局部的,函数结束时不保留的.

  • 详解C语言 三大循环 四大跳转 和判断语句

    三大循环for while 和 do{ }while; 四大跳转 : 无条件跳转语句 go to; 跳出循环语句 break; 继续跳出循环语句 continue; 返回值语句 return 判断语句 if,if else,if else if else if...else ifelse 组合 if(0 == x) if(0 == y) error(): else{ //program code } else到底与那个if配对 C语言有这样的规定: else 始终与同一括号内最近的未匹配的if语

  • 详解C语言gets()函数与它的替代者fgets()函数

    在c语言中读取字符串有多种方法,比如scanf() 配合%s使用,但是这种方法只能获取一个单词,即遇到空格等空字符就会返回.如果要读取一行字符串,比如: I love BIT 这种情况,scanf()就无能为力了.这时我们最先想到的是用gets()读取. gets()函数从标准输入(键盘)读入一行数据,所谓读取一行,就是遇到换行符就返回.gets()函数并不读取换行符'\n',它会吧换行符替换成空字符'\0',作为c语言字符串结束的标志. gets()函数经常和puts()函数配对使用,puts

  • 详解C 语言项目中.h文件和.c文件的关系

    详解C 语言项目中.h文件和.c文件的关系 在编译器只认识.c(.cpp))文件,而不知道.h是何物的年代,那时的人们写了很多的.c(.cpp)文件,渐渐地,人们发现在很多.c(.cpp)文件中的声明语句就是相同的,但他们却不得不一个字一个字地重复地将这些内容敲入每个.c(.cpp)文件.但更为恐怖的是,当其中一个声明有变更时,就需要检查所有的.c(.cpp)文件. 于是人们将重复的部分提取出来,放在一个新文件里,然后在需要的.c(.cpp)文件中敲入#include XXXX这样的语句.这样即

随机推荐