数据结构——双链表实现和注释浅解

2024-09-08 03:44
文章标签 实现 数据结构 注释 双链 浅解

本文主要是介绍数据结构——双链表实现和注释浅解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

关于双链表的基础部分增删查改的实现和一点理解，写在注释里~ 

前言 

 

 

 

 

 

 

浅记

 

1. 哨兵位的节点不能被删除，节点的地址也不能发生改变，所以是传一级指针

2. 哨兵位并不存储有效数据，所以它并不是有效节点

3. 双向链表为空时，说明只剩下一个头节点（哨兵位）

 List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{LTDataType data;//存储的数据struct ListNode* next;//指向下一个节点的指针struct ListNode* prev;//指向前一个节点的指针
}LTNode;//声明双向链表中提供的方法//申请节点
LTNode* LTBuyNode(LTDataType x);//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit();
//销毁
void LTDesTroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);//插入数据之前，链表必须初始化到只有一个头结点的情况
// 
//不改变哨兵位的地址，因此传一级即可
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos节点
void LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

 List.c

尾插

//哨兵位的节点不能被删除，节点的地址也不能发生改变，所以是传一级指针//尾插
//phead：哨兵位
void LTPushBack(LTNode* phead, LTDataType x)
{//断言assert(phead);//申请新节点LTNode* newnode = LTBuyNode(x);//phead  phead->prev(前尾节点)  newnode//先将新节点的prev指针指向哨兵位的prev指针(前尾节点)//再把新节点的next指针指向哨兵位newnode->prev = phead->prev;newnode->next = phead;//先将哨兵位的prev指针(前尾节点)指向新节点//再把哨兵位的prev指针指向新节点phead->prev->next = newnode;phead->prev = newnode;}

头插

在第一个存储有效数据的节点之前插入

//头插
//在第一个存储有效数据的节点之前插入
//先去修改不会受到影响的节点，也就是新节点(newnode)
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->next(第一个存储有效数据的节点d1)//新节点的next指针指向第一个存储有效数据的节点d1//新节点的prev指针指向哨兵位newnode->next = phead->next;newnode->prev = phead;//第一个存储有效数据的节点d1的prev指针指向新节点//哨兵位的next指针指向新节点phead->next->prev = newnode;phead->next = newnode;
}

尾删


//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空（只有一个哨兵位）assert(phead && phead->next != phead);//创建一个临时变量del，把最后一个存储有效数据的节点存放进去(d3)LTNode* del = phead->prev;//phead del->prev（d2） del（d3）//将d2的next指针指向哨兵位//把哨兵位的prev指针指向d2del->prev->next = phead;phead->prev = del->prev;//删除del（d3）节点，置为空free(del);del = NULL;
}

 

头删 

删除第一个存储有效数据的节点

//头删
//删除第一个存储有效数据的节点
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);//创建一个临时变量del，把最后一个存储有效数据的节点存放进去(d1)LTNode* del = phead->next;//phead del（d1） del->next（d2）//将哨兵位的next指针指向d2//把d2的prev指针指向哨兵位phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}

 

 汇总

#include"List.h"//data存储的数据
//next指向下一个节点的指针
//prev指向前一个节点的指针//哨兵位的节点不能被删除，节点的地址也不能发生改变，所以是传一级指针
//哨兵位并不存储有效数据，所以它并不是有效节点//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;//node的next指针和prev指针都指向node本身 自循环//哨兵位node->next = node->prev = node;return node;
}//插入数据之前，链表必须初始化到 只有一个头结点 的情况//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit()
{//初始化就是申请一个哨兵位，哨兵位是自循环和LTNode* phead = LTBuyNode(-1);return phead;
}//销毁
void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead，而phead还没有被销毁free(phead);phead = NULL;
}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//哨兵位的节点不能被删除，节点的地址也不能发生改变，所以是传一级指针//尾插
//phead：哨兵位
void LTPushBack(LTNode* phead, LTDataType x)
{//断言assert(phead);//申请新节点LTNode* newnode = LTBuyNode(x);//phead  phead->prev(前尾节点)  newnode//先将新节点的prev指针指向哨兵位的prev指针(前尾节点)//再把新节点的next指针指向哨兵位newnode->prev = phead->prev;newnode->next = phead;//先将哨兵位的prev指针(前尾节点)指向新节点//再把哨兵位的prev指针指向新节点phead->prev->next = newnode;phead->prev = newnode;}//头插
//在第一个存储有效数据的节点之前插入
//先去修改不会受到影响的节点，也就是新节点(newnode)
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->next(第一个存储有效数据的节点d1)//新节点的next指针指向第一个存储有效数据的节点d1//新节点的prev指针指向哨兵位newnode->next = phead->next;newnode->prev = phead;//第一个存储有效数据的节点d1的prev指针指向新节点//哨兵位的next指针指向新节点phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空（只有一个哨兵位）assert(phead && phead->next != phead);//创建一个临时变量del，把最后一个存储有效数据的节点存放进去(d3)LTNode* del = phead->prev;//phead del->prev（d2） del（d3）//将d2的next指针指向哨兵位//把哨兵位的prev指针指向d2del->prev->next = phead;phead->prev = del->prev;//删除del（d3）节点，置为空free(del);del = NULL;
}
//头删
//删除第一个存储有效数据的节点
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);//创建一个临时变量del，把最后一个存储有效数据的节点存放进去(d1)LTNode* del = phead->next;//phead del（d1） del->next（d2）//将哨兵位的next指针指向d2//把d2的prev指针指向哨兵位phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除pos节点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead，但是没有参数phead，无法增加校验assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

Test.c 

#include"List.h"void ListTest01()
{//LTNode* plist = NULL;//LTInit(&plist);LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);LTNode* find = LTFind(plist, 3);//LTInsert(find, 66);LTErase(find);find = NULL;LTPrint(plist);LTDesTroy(plist);//plist = NULL;//if (find == NULL)//{//	printf("找不到！\n");//}//else {//	printf("找到了！\n");//}//LTPushFront(plist, 1);//LTPrint(plist);//LTPushFront(plist, 2);//LTPrint(plist);//LTPushFront(plist, 3);// //测试尾删//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);测试头删//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);
}int main()
{ListTest01();return 0;
}

一点浅解，感谢观看~

这篇关于数据结构——双链表实现和注释浅解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1147018。

相关文章

Python xmltodict实现简化XML数据处理

Python xmltodict实现简化XML数据处理

《Pythonxmltodict实现简化XML数据处理》Python社区为提供了xmltodict库,它专为简化XML与Python数据结构的转换而设计,本文主要来为大家介绍一下如何使用xmltod... 目录一、引言二、XMLtodict介绍设计理念适用场景三、功能参数与属性1、parse函数2、unpa
阅读更多...
C#实现获得某个枚举的所有名称

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi
阅读更多...
Go语言实现将中文转化为拼音功能

Go语言实现将中文转化为拼音功能

《Go语言实现将中文转化为拼音功能》这篇文章主要为大家详细介绍了Go语言中如何实现将中文转化为拼音功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 有这么一个需求：新用户入职 创建一系列账号比较麻烦，打算通过接口传入姓名进行初始化。想把姓名转化成拼音。因为有些账号即需要中文也需要英
阅读更多...
C# 读写ini文件操作实现

C# 读写ini文件操作实现

《C#读写ini文件操作实现》本文主要介绍了C#读写ini文件操作实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录一、INI文件结构二、读取INI文件中的数据在C#应用程序中，常将INI文件作为配置文件，用于存储应用程序的
阅读更多...
C#实现获取电脑中的端口号和硬件信息

C#实现获取电脑中的端口号和硬件信息

《C#实现获取电脑中的端口号和硬件信息》这篇文章主要为大家详细介绍了C#实现获取电脑中的端口号和硬件信息的相关方法,文中的示例代码讲解详细,有需要的小伙伴可以参考一下... 我们经常在使用一个串口软件的时候，发现软件中的端口号并不是普通的COM1，而是带有硬件信息的。那么如果我们使用C#编写软件时候，如
阅读更多...
Python使用qrcode库实现生成二维码的操作指南

Python使用qrcode库实现生成二维码的操作指南

《Python使用qrcode库实现生成二维码的操作指南》二维码是一种广泛使用的二维条码,因其高效的数据存储能力和易于扫描的特点,广泛应用于支付、身份验证、营销推广等领域,Pythonqrcode库是... 目录一、安装 python qrcode 库二、基本使用方法1. 生成简单二维码2. 生成带 Log
阅读更多...
Go语言使用Buffer实现高性能处理字节和字符

Go语言使用Buffer实现高性能处理字节和字符

《Go语言使用Buffer实现高性能处理字节和字符》在Go中,bytes.Buffer是一个非常高效的类型,用于处理字节数据的读写操作,本文将详细介绍一下如何使用Buffer实现高性能处理字节和... 目录1. bytes.Buffer 的基本用法1.1. 创建和初始化 Buffer1.2. 使用 Writ
阅读更多...
基于WinForm+Halcon实现图像缩放与交互功能

基于WinForm+Halcon实现图像缩放与交互功能

《基于WinForm+Halcon实现图像缩放与交互功能》本文主要讲述在WinForm中结合Halcon实现图像缩放、平移及实时显示灰度值等交互功能,包括初始化窗口的不同方式,以及通过特定事件添加相应... 目录前言初始化窗口添加图像缩放功能添加图像平移功能添加实时显示灰度值功能示例代码总结最后前言本文将
阅读更多...
Redis延迟队列的实现示例

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi
阅读更多...
C#实现WinForm控件焦点的获取与失去

C#实现WinForm控件焦点的获取与失去

《C#实现WinForm控件焦点的获取与失去》在一个数据输入表单中,当用户从一个文本框切换到另一个文本框时,需要准确地判断焦点的转移,以便进行数据验证、提示信息显示等操作,本文将探讨Winform控件... 目录前言获取焦点改变TabIndex属性值调用Focus方法失去焦点总结最后前言在一个数据输入表单
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2