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同步小助手
文章同步
相关阅读

机器人技术在安全领域的重要作用

安全学习记录——网络篇（一）

图腾柱PFC：HP1010为您的电动两轮车之旅提供绿色，高效，安全的动力

单元测试数据库回滚问题

这才是单元测试，之前我们都错了

【C语言基础】：字符函数和字符串函数

ChatGPT-Next-Web SSRF漏洞+XSS漏洞复现(CVE-2023-49785)

文章导航