0
0

【数据结构初阶】双链表

双链表

1.双链表的实现

1.1结口实现

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint LTDateType;typedefstructListNode{structListNode* next;structListNode* prev;
    LTDateType date;}LTNode;//创造结点
LTNode*BuyLTNode(LTDateType x);//初始化双链表
LTNode*LTInit();//打印双链表voidLTPrint(LTNode* phead);//尾插voidLTPushBack(LTNode* phead, LTDateType x);//尾删voidLTPopBack(LTNode* phead);//头插voidLTPushFront(LTNode* phead, LTDateType x);//头删voidLTPopFront(LTNode* phead);//计算intLTSize(LTNode* phead);//查找
LTNode*LTFind(LTNode* phead, LTDateType x);//pos位置插入voidLTInsert(LTNode* pos, LTDateType x);//删除pos位置voidLTErase(LTNode* pos);//销毁双链表voidLTDestroy(LTNode* phead);

1.2申请结点

//创造结点
LTNode*BuyLTNode(LTDateType x){
    LTNode* node =(LTNode*)malloc(sizeof(LTNode));if(node ==NULL){perror("malloc fail");exit(-1);}
    node->date = x;
    node->next =NULL;
    node->prev =NULL;return node;}

1.3初始化双链表

//初始化双链表
LTNode*LTInit(){
    LTNode* phead =BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}

1.4打印双链表

//打印双链表voidLTPrint(LTNode* phead){assert(phead);printf("phead<=>");
    LTNode* cur = phead->next;while(cur != phead){printf("%d<=>", cur->date);
        cur = cur->next;}printf("\n");}

1.5尾插

在这里插入图片描述

//尾插voidLTPushBack(LTNode* phead, LTDateType x){assert(phead);
    LTNode* tail = phead->prev;
    LTNode* newnode =BuyLTNode(x);

    newnode->prev = tail;
    tail->next = newnode;

    newnode->next = phead;
    phead->prev = newnode;}

1.6尾删

在这里插入图片描述

//尾删voidLTPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);

    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;}

1.7头插

在这里插入图片描述

//头插voidLTPushFront(LTNode* phead, LTNode* x){assert(phead);

    LTNode* newnode =BuyLTNode(x);
    LTNode* first = phead->next;

    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;}

1.8头删

在这里插入图片描述

//头删voidLTPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);

    LTNode* first = phead->next;
    LTNode* second = first->next;free(first);
    phead->next = second;
    second->prev = phead;}

1.9计算大小

//计算intLTSize(LTNode* phead){assert(phead);int size =0;
    LTNode* cur = phead->next;while(cur != phead){
        size++;
        cur = cur->next;}return size;}

1.10查找

//查找
LTNode*LTFind(LTNode* phead, LTDateType x){assert(phead);

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

1.11pos位置插入

在这里插入图片描述

//在pos位置插入voidLTInsert(LTNode* pos, LTDateType x){assert(pos);

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

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

1.12删除pos位置

在这里插入图片描述

//删除pos位置voidLTErase(LTNode* pos){assert(pos);
    LTNode* posNext = pos->next;
    LTNode* posPrev = pos->prev;free(pos);
    posPrev->next = posNext;
    posNext->prev = posPrev;}

1.12删除双链表

//销毁双链表voidLTDestroy(LTNode* phead){assert(phead);

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

全部码源

List.h

#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefint LTDateType;typedefstructListNode{structListNode* next;structListNode* prev;
    LTDateType date;}LTNode;//创造结点
LTNode*BuyLTNode(LTDateType x);//初始化双链表
LTNode*LTInit();//打印双链表voidLTPrint(LTNode* phead);//尾插voidLTPushBack(LTNode* phead, LTDateType x);//尾删voidLTPopBack(LTNode* phead);//头插voidLTPushFront(LTNode* phead, LTDateType x);//头删voidLTPopFront(LTNode* phead);//计算intLTSize(LTNode* phead);//查找
LTNode*LTFind(LTNode* phead, LTDateType x);//pos位置插入voidLTInsert(LTNode* pos, LTDateType x);//删除pos位置voidLTErase(LTNode* pos);//销毁双链表voidLTDestroy(LTNode* phead);

List.c

#include"List.h"//创造结点
LTNode*BuyLTNode(LTDateType x){
    LTNode* node =(LTNode*)malloc(sizeof(LTNode));if(node ==NULL){perror("malloc fail");exit(-1);}
    node->date = x;
    node->next =NULL;
    node->prev =NULL;return node;}//初始化双链表
LTNode*LTInit(){
    LTNode* phead =BuyLTNode(0);
    phead->next = phead;
    phead->prev = phead;return phead;}//打印双链表voidLTPrint(LTNode* phead){assert(phead);printf("phead<=>");
    LTNode* cur = phead->next;while(cur != phead){printf("%d<=>", cur->date);
        cur = cur->next;}printf("\n");}//尾插voidLTPushBack(LTNode* phead, LTDateType x){assert(phead);
    LTNode* tail = phead->prev;
    LTNode* newnode =BuyLTNode(x);

    newnode->prev = tail;
    tail->next = newnode;

    newnode->next = phead;
    phead->prev = newnode;}//尾删voidLTPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);

    LTNode* tail = phead->prev;
    LTNode* tailPrev = tail->prev;free(tail);
    tailPrev->next = phead;
    phead->prev = tailPrev;}//头插voidLTPushFront(LTNode* phead, LTNode* x){assert(phead);

    LTNode* newnode =BuyLTNode(x);
    LTNode* first = phead->next;

    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;}//头删voidLTPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);

    LTNode* first = phead->next;
    LTNode* second = first->next;free(first);
    phead->next = second;
    second->prev = phead;}//计算intLTSize(LTNode* phead){assert(phead);int size =0;
    LTNode* cur = phead->next;while(cur != phead){
        size++;
        cur = cur->next;}return size;}//查找
LTNode*LTFind(LTNode* phead, LTDateType x){assert(phead);

    LTNode* cur = phead->next;while(cur != phead){if(cur->date == x)return cur;
        cur = cur->next;}returnNULL;}//在pos位置插入voidLTInsert(LTNode* pos, LTDateType x){assert(pos);

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

    posPrev->next = newnode;
    newnode->prev = posPrev;
    newnode->next = pos;
    pos->prev = newnode;}//删除pos位置voidLTErase(LTNode* pos){assert(pos);
    LTNode* posNext = pos->next;
    LTNode* posPrev = pos->prev;free(pos);
    posPrev->next = posNext;
    posNext->prev = posPrev;}//销毁双链表voidLTDestroy(LTNode* phead){assert(phead);

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

test.c

#include"List.h"voidTestList1(){
    LTNode* plist =LTInit();LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushBack(plist,4);LTPushBack(plist,5);LTPrint(plist);LTPopBack(plist);LTPrint(plist);LTPushFront(plist,20);LTPrint(plist);}voidTestList2(){
    LTNode* plist =LTInit();LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushBack(plist,4);LTPushBack(plist,5);LTPrint(plist);LTPopFront(plist);LTPrint(plist);LTSize(plist);}voidTestList3(){
    LTNode* plist =LTInit();LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushBack(plist,4);LTPushBack(plist,5);LTPrint(plist);
    LTNode* pos =LTFind(plist,3);LTInsert(pos,20);LTPrint(plist);}voidTestList4(){
    LTNode* plist =LTInit();LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPushBack(plist,4);LTPushBack(plist,5);LTPrint(plist);
    LTNode* pos =LTFind(plist,3);LTErase(pos);LTPrint(plist);}intmain(){TestList4();return0;}

💘不知不觉，【数据结构初阶】双链表 以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学习共同奋进!!!

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

“【数据结构初阶】双链表”的评论:

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

249基于java ssm springboot安全生产培训管理系统学习课件（源码+文档+运行视频+讲解视频）

【Linux庖丁解牛】—软件安装&vim！

【花雕学编程】Arduino LVGL 之在不同平台创建相同的用户界面

基于电商大数据的商品推荐系统

UE5.4像素流及前端接入

Unity中接入讯飞语音（实时语音转写）WebAPI（非SDK）

springboot实现获取客户端IP地址

文章导航