0
0

双向带头循环链表C语言版

文章目录

0.前言

带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，同样我们也采用分文件的方式实现。
在这里插入图片描述

1. List.h

#pragmaonce#include<stdio.h>#include<assert.h>#include<stdlib.h>typedefint LTDataType;typedefstructListNode{
    LTDataType data;structListNode* next;structListNode* prev;}LTNode;voidListPrint(LTNode* phead);
LTNode*ListInit();voidListDestroy(LTNode* phead);
LTNode*BuyLTNode(LTDataType x);voidListPushBack(LTNode* phead, LTDataType x);voidListPopBack(LTNode* phead);voidListPushFront(LTNode* phead, LTDataType x);voidListPopFront(LTNode* phead);
LTNode*ListFind(LTNode* phead, LTDataType x);// 在pos之前插入voidListInsert(LTNode* pos, LTDataType x);//void ListInsert(int i, LTDataType x);// 删除pos位置的节点voidListErase(LTNode* pos);

2. List.c

2.1 开辟一个新节点

LTNode*BuyLTNode(LTDataType x){
    LTNode *newnode =(LTNode*)malloc(sizeof(LTNode));if(newnode ==NULL){printf("malloc fail\n");exit(-1);}
    newnode->data = x;
    newnode->prev =NULL;
    newnode->next =NULL;return newnode;}

2.2 初始化链表

在这里插入图片描述

LTNode*ListInit(){
    LTNode* phead =BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}

2.3 摧毁链表

voidListDestroy(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* next = cur->next;free(cur);
        cur = next;}free(phead);
    phead =NULL;}

2.4 尾插

多个节点的情况：
在这里插入图片描述
这种方法也能解决空链表的情况
在这里插入图片描述
代码实现：

voidListPushBack(LTNode* phead, LTDataType x){assert(phead);
    LTNode *tail = phead->prev;
    LTNode *newnode =BuyLTNode(X);
    tail->next = newnode;
    newnode->prev = tail;
    newnode->next = phead;
    phead->prev = newnode;}

2.5 和之前不带哨兵位的单链表传参的区别

带哨兵位的双向循环链表：
在这里插入图片描述
不带哨兵位的单链表：
在这里插入图片描述

2.6 尾删

多个节点：
在这里插入图片描述
这种方法也能解决一个节点的情况：
在这里插入图片描述

voidListPopBack(LTNode* phead){assert(phead);//链表为空assert(phead !=phead->next);
    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;free(tail);
    tail =NULL;
    tail->next = phead;
    phead->prev = tailPrev;}

2.7 打印链表

在这里插入图片描述我们发现

cur

指针再次回到

phead

为结束条件。

voidListPrint(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){printf("%d ",cur->data);
        cur = cur->next;}printf("\n\n");}

2.8 头插

在这里插入图片描述

voidListPushFront(LTNode* phead, LTDateType x){assert(phead);
    LTNode* first = phead->next;
    LTNode* newnode =BuyLTNode(x);
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;}

2.9 头删

在这里插入图片描述

voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* first = phead->next;
    LTNode* second = first->next;free(first);
    phead->next = second;
    second->prev = phead;}

2.10 查找

LTNode*ListFind(LTNode* phead, LTDateType x){assert(phead);

    LTNode* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;}

        cur = cur->next;}returnNULL;}

2.11 在pos之前插入

在这里插入图片描述

voidListInsert(LTNode* pos, LTDataType x){assert(pos);
    LTNode* newnode =BuyLTNode(x);
    LTNode* posPrev = pos->prev;

    newnode->next = pos;
    pos->prev = newnode;
    posPrev->next = newnode;
    newnode->prev = posPrev;}

2.12 删除pos位置的节点

在这里插入图片描述

voidListErase(LTNode* pos){assert(pos);
    LTNode* prev = pos->prev;
    LTNode* next = pos->next;
    prev->next = next;
    next->prev = prev;free(pos);}

2.13 10min实现双向循环链表

//尾插voidListPushBack(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead,x);}//尾删voidListPopBack(LTNode* phead){assert(phead);ListErase(phead->prev);}//头插voidListPushFront(LTNode* phead, LTDataType x){assert(phead);ListInsert(phead,x);}//头删voidListPopFront(LTNode* phead){assert(phead);ListErase(phead->next);}

2.14 List.c完整代码

#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;}voidListPrint(LTNode* phead){assert(phead);

    LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->data);
        cur = cur->next;}printf("\n\n");}voidListDestroy(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* next = cur->next;free(cur);
        cur = next;}free(phead);
    phead =NULL;}

LTNode*ListInit(){
    LTNode* phead =BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}voidListPushBack(LTNode* phead, LTDataType x){//assert(phead);//LTNode* tail = phead->prev;//LTNode* newnode = BuyLTNode(x);//tail->next = newnode;//newnode->prev = tail;//newnode->next = phead;//phead->prev = newnode;ListInsert(phead, x);}voidListPopBack(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;}voidListPushFront(LTNode* phead, LTDateType x){assert(phead);
    LTNode* first = phead->next;
    LTNode* newnode =BuyLTNode(x);
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;}voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* first = phead->next;
    LTNode* second = first->next;free(first);
    phead->next = second;
    second->prev = phead;}

LTNode*ListFind(LTNode* phead, LTDataType x){assert(phead);

    LTNode* cur = phead->next;while(cur != phead){if(cur->data == x){return cur;}

        cur = cur->next;}returnNULL;}voidListInsert(LTNode* pos, LTDataType x){assert(pos);/*LTNode* newnode = BuyLTNode(x);
    pos->prev->next = newnode;
    newnode->prev = pos->prev;

    pos->prev = newnode;
    newnode->next = pos;*/

    LTNode* newnode =BuyLTNode(x);
    LTNode* posPrev = pos->prev;

    newnode->next = pos;
    pos->prev = newnode;
    posPrev->next = newnode;
    newnode->prev = posPrev;}voidListErase(LTNode* pos){assert(pos);
    LTNode* prev = pos->prev;
    LTNode* next = pos->next;
    prev->next = next;
    next->prev = prev;free(pos);}

3.Test.c

#define_CRT_SECURE_NO_WARNINGS1#include"List.h"voidTestList1(){
    LTNode* pList =ListInit();ListPushBack(pList,1);ListPushBack(pList,2);ListPushBack(pList,3);ListPushBack(pList,4);ListPushBack(pList,5);ListPushBack(pList,6);ListPrint(pList);ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);ListPopBack(pList);//ListPopBack(pList);ListPrint(pList);ListDestroy(plist);}voidTestList2(){//LTNode* pList = NULL;//ListInit(&pList);
    LTNode* pList =ListInit();ListPushBack(pList,1);ListPushBack(pList,2);ListPushBack(pList,3);ListPushBack(pList,4);ListPrint(pList);ListPushFront(pList,0);ListPushFront(pList,-1);ListPrint(pList);

    LTNode* pos =ListFind(pList,3);if(pos){ListInsert(pos,30);}ListPrint(pList);}intmain(){TestList1();return0;}

4. 运行结果

在这里插入图片描述

5. 顺序表和链表的区别

不同点顺序表链表存储空间上物理上一定连续逻辑上连续，但物理上不一定连续随机访问支持O(1)不支持：O(N)任意位置插入或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向插入动态顺序表，空间不够时需要扩容没有容量的概念应用场景元素高效存储+频繁访问任意位置插入和删除频繁缓存利用率高低
备注：缓存利用率参考存储体系结构以及局部原理性。
在这里插入图片描述
与程序员相关的cpu缓存知识

标签： c语言 数据结构 链表
本文转载自: https://blog.csdn.net/iwkxi/article/details/123690212
版权归原作者 Yuucho 所有， 如有侵权，请联系我们删除。
登录后发布评论

“双向带头循环链表C语言版”的评论:

还没有评论
关于作者
...
overfit同步小助手
文章同步
相关阅读

Linux 再入门整理：详解 /etc/fstab 文件

HBase Java API编程-学习记录

【大数据技术基础 | 实验十二】Hive实验：Hive分区

【前端】CSS

python 爬虫 入门 五、抓取图片、视频

Docker 中使用环境变量的安全实践

[Linux]——常见指令（中）

文章导航