0
0

【最强链表结构】双向带头循环链表——C实现

前言🎆

笔者也仅是大一萌新，写博客为了记录和巩固知识✨

赠人玫瑰，手留余香，欢迎各位读者进行交流和建议🥰

能与大家一起学习，一起进步是我的荣幸🌹

如果这篇文章有帮助到您，还请留个赞支持一下哦🤞

✨往期文章✨

🎃顺序表🎃

🎃单链表🎃

目录🎆

链表的种类✨

1.单向或双向

image-20220404154008438

2.带头或者不带头

image-20220404154101653

3.循环或者非循环

image-20220404154141771

其中，它们可以任意组合成8种类型的链表，如单向带头循环，双向带头非循环
单向—不带头—非循环链表结构最简单，OJ题中经常出现，并且也是复杂数据结构的子结构（哈希桶/图的临接表）
双向—带头—循环链表结构最复杂，但是它是最实用的链表结构，具有很优秀的结构性能

链表的实现✨

image-20220404160906387

代码声明🎨

#pragmaonce#include<stdio.h>#include<assert.h>#include<stdio.h>#include<string.h>#include<stdlib.h>typedefint LTDataType;typedefstructListNode{
    LTDataType data;structListNode* next;structListNode* prev;}LTNode;//void ListInit(LTNode* phead);
LTNode*ListInit();//初始化voidListPrint(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);//查找voidListInsert(LTNode* pos, LTDataType x);//Pos前删voidListErase(LTNode* pos);//pos删voidListDestroy(LTNode* pos);//清空

初始化🎨

LTNode*ListInit()//因为带哨兵位，所以我们不需要检测{
    LTNode* phead =BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;//返回哨兵位，如果用void来写需要传入二级指针}

打印函数🎨

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

扩容函数🎨

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;}

尾插尾删🎨

voidListPushBack(LTNode* phead, LTDataType x){assert(phead);
    LTNode* tail = phead->prev;//尾节点就是头结点的上一个
    LTNode* newnode =BuyLTNode(x);//扩容
    tail->next = newnode;//newnode成为新的尾节点
    newnode->prev = tail;//找到尾节点的前一个节点防止丢失
    newnode->next = phead;//尾再指向头形成循环
    phead->prev = newnode;//头指向新的尾//ListInsert(phead, x); //Insert快速头删，这也是结构的优势}voidListPopBack(LTNode* phead){assert(phead);//链表为空assert(phead->next != phead);//仅有哨兵位就不能删除
    LTNode* tail = phead->prev;//tail找到尾
    LTNode* tailPrev = tail->prev;//找到尾节点的上一个节点使其变成尾节点free(tail);//释放之前的尾节点
    tail =NULL;//置空
    tailPrev->next = phead;//老样子，循环操作
    phead->prev = tailPrev;//ListErase(phead->prev);    //Erase快速尾删}

头插头删🎨

voidListPushFront(LTNode* phead, LTDataType x){assert(phead);
    ListNode* head = phead->next;
    LTNode* newnode =BuyLTNode(x);//扩容
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = head;
    head->prev = newnode;//ListInsert(phead->next, x);}voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* p = phead->next;//p记录phead->next
    LTNode* n = p->next;//n记录phead->next->next
    phead->next = n;//让phead和n连接
    n->prev = phead;free(p);//释放p
    p =NULL//ListErase(phead->next);}

查找函数🎨

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;}

pos之前插和pos删（结构优势的体现）🎨

//当写好Insert后，尾插头插都可以直接用此函数(注意这里pos为下标)//当pos等于phead->next时，就是头插//当pos等于phead时，就是尾插voidListInsert(LTNode* pos, LTDataType x){assert(pos);//更推荐的写法
    LTNode* newnode =BuyLTNode(x);
    LTNode* posPrev = pos->prev;//用来储存pos的上一个节点
    newnode->next = pos;
    pos->prev = newnode;
    posPrev->next = newnode;
    newnode->prev = posPrev;//只用两个指针需要考虑交换顺序，防止找不到节点/*LTNode* newnode = BuyLTNode(x);
    pos->prev->next = newnode;
    newnode->prev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;*/}//当pos等于phead->next时，就是头删//当pos等于phead->prev时，就是尾删voidListErase(LTNode* pos){assert(pos);
    LTNode* p = pos->prev;
    LTNode* n = pos->next;free(pos);//在这里置空只会改变形参的值，不改变实参的值
    p->next = n;
    n->prev = p;}

清空函数🎨

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

总代码🎨

#include"SeqList.h"intmain(){/*LTNode* plist = NULL;*//*ListInit(&plist);*/
    LTNode* plist =ListInit();ListPushBack(plist,2);ListPushBack(plist,3);ListPushBack(plist,1);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);printf("\n");ListPrint(plist);

    LTNode* pos =ListFind(plist,2);if(pos){printf("\n");ListInsert(pos,5);ListPrint(plist);printf("\n");ListErase(pos);
        pos =NULL;ListPrint(plist);}elseprintf("not have this number!");printf("\n");ListPushFront(plist,100);ListPrint(plist);printf("\n");ListPopFront(plist);ListPrint(plist);ListDestory(plist);
    phead =NULL;return0;}

#pragmaonce#include<stdio.h>#include<assert.h>#include<stdio.h>#include<string.h>#include<stdlib.h>typedefint LTDataType;typedefstructListNode{
    LTDataType data;structListNode* next;structListNode* prev;}LTNode;//void ListInit(LTNode* phead);
LTNode*ListInit();voidListPrint(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);voidListInsert(LTNode* pos, LTDataType x)voidListErase(LTNode* pos);voidListDestroy(LTNode* pos);

#include"SeqList.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);//    (*pphead)->next = *pphead;//    (*pphead)->prev = *pphead;//}
LTNode*ListInit(){
    LTNode* phead =BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}voidListPrint(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){printf("%d ", cur->data);
        cur = cur->next;}}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)//删除pos前一个值{assert(pos);
    LTNode* p = pos->prev;
    LTNode* n = pos->next;free(pos);//在这里置空只会改变形参的值，不改变实参的值
    p->next = n;
    n->prev = p;}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);//仅有哨兵位ListErase(phead->prev);/*LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;
    free(tail);
    tail = NULL;
    tailPrev->next = phead;
    phead->prev = tailPrev;*/}voidListPushFront(LTNode* phead, LTDataType x){assert(phead);
    ListNode* head = phead->next;
    LTNode* newnode =BuyLTNode(x);//扩容
    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = head;
    head->prev = newnode;//ListInsert(phead->next, x);}voidListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);
    LTNode* p = phead->next;//p记录phead->next
    LTNode* n = p->next;//n记录phead->next->next
    phead->next = n;//让phead和n连接
    n->prev = phead;free(p);//释放p
    p =NULL//ListErase(phead->next);}
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;}voidListDestory(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* next = cur->next;ListErase(cur);
        cur = next;}free(phead);}
ev = phead;free(p);//释放p
    p =NULL//ListErase(phead->next);}
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;}voidListDestory(LTNode* phead){assert(phead);
    LTNode* cur = phead->next;while(cur != phead){
        LTNode* next = cur->next;ListErase(cur);
        cur = next;}free(phead);}
标签： c语言 数据结构 链表
本文转载自: https://blog.csdn.net/m0_63816268/article/details/123957711
版权归原作者 A.A呐 所有， 如有侵权，请联系我们删除。
登录后发布评论

“【最强链表结构】双向带头循环链表&mdash;&mdash;C实现”的评论:

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

通过SSH操作Linux虚拟机

C#学习笔记（三）Visual Studio安装与使用

JPA基础教程：实体操作和数据库交互实践

开源低代码-Microi吾码报表引擎

HiveSQL：提取json串内容（含key为中文情况）——get_json_oject和json_tuple

Spring Cloud Stream 3.x+kafka 3.8整合

【大数据·hadoop】项目实践：IDEA实现WordCount词频统计项目

文章导航