数据结构：双向带头循环链表的增删查改

embedded/2024/12/20 13:26:41/

 先构建一个结构体，对其链表进行初始化，尾插，尾删，头插，头删，查找，修改，中间插入，删除等相关操作。

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
//创建一个结点
typedef struct SListNode
{
    //int data;
    LTDataType data;
    struct SListNode* next;//创建一个指针存下一个结点的地址
    struct SListNode* prev;
}LTNode;


//初始化
LTNode* ListInit();
//void ListInit(LTNode** phead);

LTNode* BuyListNode(LTDataType x);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);

LTNode* ListFind(LTNode* phead, LTDataType x);//找到了就返回链表的指针

//在pos前面插入x
void ListInsert(LTNode* pos, LTDataType x);
void ListErase(LTNode* pos);

void ListClear(LTNode* phead);

void ListDestory(LTNode** pphead);

void ListPrint(LTNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
LTNode* ListInit()
{
    //带哨兵位的头结点
    //不存储有效数字，啥都不存
    LTNode*  phead = (LTNode*)malloc(sizeof(LTNode));
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

//void ListInit(LTNode** pphead)
//{
//    //带哨兵位的头结点
//    //不存储有效数字，啥都不存
//    *pphead = BuyListNode(0);
//    (*pphead)->next = *pphead;
//    (*pphead)->prev = *pphead;
//}

LTNode* BuyListNode( LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

void ListPushBack(LTNode* phead, LTDataType x)
{
    //assert(phead);
    //LTNode* tail = phead->prev;
    //LTNode* newnode = BuyListNode(x);
     phead   tail  newnode
    //tail->next = newnode;
    //newnode->next = phead;
    //phead->prev = newnode;
    ListInsert(phead,x );
}

//void ListPopBack(LTNode* phead)
//{
//    assert(phead);
//    assert(phead->next != phead);
//    LTNode* tail = phead->prev;
//    LTNode* tailPrev = tail->prev;
//    tailPrev->next = phead;
//    phead->prev = tailPrev;
//    //tailPrev->next = phead;             // 将尾节点的前一个节点的next指向头节点
//    //phead->prev = tailPrev;             // 将头节点的prev指向新的尾节点
//    free(tail);
//    tail = NULL;
//    //为什么不是phead->prev = tailPrev->next; 而是phead->prev = tailPrev，
//    // 应该是尾指向头才对啊
//    //在双向循环链表中，尾节点的 next 始终指向头节点 phead，而头节点的 prev 始终指向尾节点。
//    //因此，在删除尾节点时，关键是要确保头节点的 prev 被正确地更新为新的尾节点（即 tailPrev）。
//    //那么我们应该如何理解这两个不同的表达式呢？
//    //双向循环链表的结构：
//
//    //头节点 phead 的 next 指向第一个元素，prev 指向尾节点。
//    //尾节点的 prev 指向倒数第二个元素，next 指向头节点。
//    //在这种情况下，尾节点总是指向头节点，而头节点的 prev 始终指向尾节点。
//
//    //删除尾节点的操作：
//
//    //首先，获得尾节点 tail，并且获得尾节点的前驱节点 tailPrev。
//    //然后，我们需要做的是：
//    //将尾节点前驱节点 tailPrev 的 next 设置为 phead，
//    //即让 tailPrev 的 next 指向头节点，保持链表的循环结构。
//    //更新头节点 phead 的 prev 为 tailPrev，让 phead 的 prev 指向新的尾节点。
//    
//    //为什么不能是 phead->prev = tailPrev->next：
//    //tailPrev->next 是 尾节点的 next，它指向头节点 phead。
//    //如果你将 phead->prev 设置为 tailPrev->next，
//    //这就意味着 phead->prev 会被设置为 phead，从而破坏链表的双向连接关系。
//    //你应该将 phead->prev 设置为 tailPrev，让头节点的 prev 指向新的尾节点。
//}
//


void ListPopBack(LTNode* phead)
{
    //assert(phead);
    //assert(phead->next != phead);
    //LTNode* tail = phead->prev;
    //LTNode* tailPrev = tail->prev;
    //tailPrev->next = phead;
    //phead->prev = tailPrev;
    tailPrev->next = phead;             // 将尾节点的前一个节点的next指向头节点
    phead->prev = tailPrev;             // 将头节点的prev指向新的尾节点
    //free(tail);
    //tail = NULL;

    ListErase(phead->prev);
}

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

void ListPushFront(LTNode* phead, LTDataType x)
{
    /*assert(phead);
    LTNode* first = phead->next;
    LTNode* newnode = BuyListNode(x);

    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;*/
    ListInsert(phead->next, x);

}


void ListPopFront(LTNode* phead)
{
    /*assert(phead);
    assert(phead->next != phead);
    LTNode* first = phead->next;
    LTNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;*/
    ListErase(phead->next);
}

LTNode* ListFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;;
        }
        cur = cur->next;
    }
    return NULL;
}


void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    LTNode* posPrev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;
    posPrev->next = newnode;
    newnode->prev = posPrev;
}

void ListErase(LTNode* pos)
{
    assert(pos);

    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}

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

void ListDestory(LTNode** pphead)
{
    assert(*pphead);
    //销毁
    ListClear(*pphead);
    free(*pphead);
    *pphead = NULL;
}
test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
TestList()
{
    //LTNode* phead = NULL;
    //ListInit(&phead);
    LTNode* phead = ListInit();
    ListPushBack(phead, 1);
    ListPushBack(phead, 2);
    ListPushBack(phead, 3);
    ListPushBack(phead, 4);
    ListPrint(phead);

    ListPopBack(phead);
    ListPopBack(phead);
    ListPopBack(phead);
    ListPrint(phead);

    ListPushFront(phead, 1);
    ListPushFront(phead, 2);
    ListPushFront(phead, 3);
    ListPushFront(phead, 4);
    ListPrint(phead);

    ListPopFront(phead);
    //ListPopFront(phead);
    //ListPopFront(phead);
    
    ListPrint(phead);

    LTNode* pos = ListFind(phead, 3);
    pos->data = 300;
    ListInsert( pos, 30);
    ListPrint(phead);

    pos = ListFind(phead, 2);
    ListErase(pos);
    ListPrint(phead);
    ListDestory(&phead);
}

int main()
{
    TestList();
    return 0;
}

先尾插 1 2 3 4，然后尾删三个数，头插 4个数，头删两个数，找到3将其改成300，并在300前面插入30，最后删除2


http://www.ppmy.cn/embedded/147287.html

相关文章

SSM 寝室管理系统：为住宿生活保驾护航

SSM 寝室管理系统：为住宿生活保驾护航

摘 要 寝室管理设计是高校为学生提供第二课堂&#xff0c;而我们所在学院多采用半手工管理学生寝室的方式&#xff0c;所以有必要开发寝室管理系统来对进行数字化管理。既可减轻学院宿舍长工作压力&#xff0c;比较系统地对宿舍通告、卫生上的各项服务和信息进行管理&#xff…
阅读更多...
《Vue3实战教程》5：响应式基础

《Vue3实战教程》5：响应式基础

如果您有疑问&#xff0c;请观看视频教程《Vue3实战教程》 响应式基础​ API 参考 本页和后面很多页面中都分别包含了选项式 API 和组合式 API 的示例代码。现在你选择的是 组合式 API。你可以使用左侧侧边栏顶部的“API 风格偏好”开关在 API 风格之间切换。 声明响应式状态…
阅读更多...
计算机组成原理课后习题答案：第九章

计算机组成原理课后习题答案：第九章

第九章控制单元功能 9.1设CPU内有这些部件:PC、IR、MAR、MDR、AC、CU。 (1)写出取指周期的全部微操作。 (2)写出减法指令“SUB X”、取数指令“LDA X”、存数指令“STA X”(X均为主存地址)在执行阶段所需全部微操作。 (3)当上述指令为间接寻址时,写出执行这些指令所需的全部…
阅读更多...
linux 内核数据包处理中的一些坑和建议

linux 内核数据包处理中的一些坑和建议

1、获取IP头部 iph ip_hdr(skb); struct sk_buff { ...... sk_buff_data_t transport_header; /* Transport layer header */ sk_buff_data_t network_header; /* Network layer header */ sk_buff_data_t mac_header; /* Link layer header */ ...... } 1&#xff0…
阅读更多...
【mybatis】缓存

【mybatis】缓存

目录 1. mybatis的运行 1.1 引言 1.2 具体运行&#xff1a; 1.3 sqlSession 介绍local catch 2. 缓存 2.1 概念 2.2 使用缓存的原因 2.3 什么样的数据能使用缓存 3. Mybatis缓存 3.1 一级缓存 3.1.1 测试一级缓存 3.1.2 缓存失效的四种情况 $1 sqlSession不同 $…
阅读更多...
[Effective C++]条款35 virtual函数替换方案

[Effective C++]条款35 virtual函数替换方案

本文初发于 “天目中云的小站”&#xff0c;同步转载于此。 条款35 : 考虑virtual函数以外的其他选择 我们都知道使用virtual函数是有代价的, 它会带来额外的开销, 譬如占用内存, 降低效率, 不好控制安全性等问题, 因此如果我们想构建一个逻辑缜密且标准的项目, 可以考虑一些vi…
阅读更多...
vivado 高亮相同变量名_显示选定词的匹配项

vivado 高亮相同变量名_显示选定词的匹配项

一、引言 之前使用vivado2018.8的时候双击变量后&#xff0c;相同变量名的变量都会被高亮。但是下载vivado2022.2版本之后&#xff0c;并没有高亮相同变量。如图所示。 二、修改设置 打开设置&#xff0c;选择“Text Editor”&#xff0c;并勾选上"Display matches for th…
阅读更多...
uniapp-微信小程序调用摄像头

uniapp-微信小程序调用摄像头

1.uniapp中的index.vue代码 <template><view class"content"><view class"container"><!-- 摄像头组件 --><camera id"camera" device-position"front" flash"off" binderror"onCameraErr…
阅读更多...
最新文章

Copyright @ 2022~2023