您的位置：首页 > 房产 > 家装 > 珠海网站优化培训_深圳全网推广公司_免费个人自助建站_长春网站优化服务

珠海网站优化培训_深圳全网推广公司_免费个人自助建站_长春网站优化服务

2025/4/22 16:57:34 来源：https://blog.csdn.net/graceyun/article/details/145975896  浏览:  次   关键词：珠海网站优化培训_深圳全网推广公司_免费个人自助建站_长春网站优化服务
珠海网站优化培训_深圳全网推广公司_免费个人自助建站_长春网站优化服务

目录

  • 1 带头双向循环链表的实现
  • 3. 5 带头+双向+循环链表增删查改接口实现
      • 3.5.0 申请新结点
      • 3.5.1双向链表的初始化
      • 3.5.2双向链表销毁
      • 3.5.3 双向链表打印
      • 3.5.4 双向链表尾插
      • 3.5.5 双向链表尾删
      • 3.5.6 双向链表头插
      • 3.5.7 双向链表头删
      • 3.5.8 双向链表查找
      • 3.5.9 双向链表删除pos位置的结点
      • 3.5.10 双向链表在pos的前面进行插入
  • 4.顺序表和链表的区别
  • 附录：双向带头循环链表接口实现源代码
    • 5.1 .h文件
    • 5.2 .c文件
    • 5.3 test.c文件

学习带头双向循环链表之前，建议先学习下顺序表，和单向不带头不循环链表。
这是博主之前的文章，欢迎学习交流
初阶数据结构（C语言实现）——3.1顺序表详解（初始化、增、删、查、改）
初阶数据结构（C语言实现）——3.3单向非循环链表详解（定义、增、删、查、改）

1 带头双向循环链表的实现

在VS2022中新建一个工程

  • List.h（带头双向循环链表的类型定义、接口函数声明、引用的头文件）
  • List.c（带头双向循环链表接口函数的实现）
  • Test.c（主函数、测试顺序表各个接口功能）

在这里插入图片描述

3. 5 带头+双向+循环链表增删查改接口实现

图示
在这里插入图片描述

特点
在这里插入图片描述

  • 实现内容

typedef int LTDataType;
typedef struct HDLListNode
{
struct HDLListNode* next;
struct HDLListNode* prve;
LTDataType data;
}HDLListNode;

//双向链表的初始化
HDLListNode* HDLListInit();
//申请一个新结点
HDLListNode* BuyListNode(LTDataType x);
//链表销毁
void HDLLDestroy(HDLListNode* phead);
//双向链表的打印
void HDLListPrint(HDLListNode* phead);
//双向链表尾插
void HDLListPushBack(HDLListNode* phead, LTDataType x);
//双向链表尾删
void HDLListPopBack(HDLListNode* phead);
//双向链表头插
void HDLListPushFront(HDLListNode* phead, LTDataType x);
//双向链表头删
void HDLListPupFront(HDLListNode* phead);
//双向链表查找
HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x);
//双向链表删除pos位置的结点
HDLListNode* HDLListErase(HDLListNode* pos);
// 双向链表在pos的前面进行插入
HDLListNode* HDLListInsert(HDLListNode* pos, LTDataType x);

3.5.0 申请新结点

  • 申请新结点图解

在这里插入图片描述

  • 申请新结点代码实现
HDLListNode* BuyListNode(LTDataType x)
{HDLListNode* newNode = (HDLListNode*)malloc(sizeof(HDLListNode)); //申请空间if (newNode == NULL){perror("BuyListNode::malloc fail!"); //如果申请失败报错return NULL;//返回NULL}//对新申请的结点进行初始化newNode->next = NULL;newNode->prve = NULL;newNode->data = x;return newNode;//返回新结点
}

3.5.1双向链表的初始化

  • 双向链表初始化图解

在这里插入图片描述

  • 双向链表初始化代码实现
HDLListNode* HDLListInit()
{HDLListNode* phead = BuyListNode(-1);//申请新结点phead->next = phead;phead->prve = phead;return phead;//返回头结点
}

3.5.2双向链表销毁

  • 双向链表销毁图解

在这里插入图片描述

  • 双向链表销毁代码实现
void HDLLDestroy(HDLListNode* phead)
{assert(phead);HDLListNode* cur = phead->next;//让cur从带哨兵的头结点之后的第一个有效结点开始遍历while (cur!=phead)//遍历一遍链表，一个节点一个节点的释放{HDLListNode* next = cur->next;//记录cur的下一个结点free(cur);//释放结点cur = next;//cur往后走}free(phead);//最后释放哨兵头结点}

3.5.3 双向链表打印

因为头结点不带有效数值，所以让cur指针不要指向头结点，指向头结点的下一个结点，然后遍历链表打印。下次到头的时候cur =phead。

  • 双向链表打印代码实现
//双向链表的打印
void HDLListPrint(HDLListNode* phead)
{assert(phead);//断言，确保传入参数正确printf("<=head=>");HDLListNode* cur = phead->next;while (cur != phead){printf("%d=>", cur->data);cur = cur->next;//cur继续往后走}//最后全部打印完之后，换行。printf("\n");
}

3.5.4 双向链表尾插

  • 图解尾插

在这里插入图片描述

  • 双向链表的尾插代码实现
void HDLListPushBack(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListNode* newnode = BuyListNode(x); //申请一个新结点HDLListNode* tail = phead->prve;//尾结点直接就能找到tail->next = newnode;//让尾结点指向要插入的结点newnode->next = phead;//让新插入的结点指向头结点phead->prve = newnode;//让头结点的prve指向新的尾结点}
  • 代码验证

在这里插入图片描述

3.5.5 双向链表尾删

  • 尾删图解

在这里插入图片描述

  • 尾删代码实现
bool isEmpty(HDLListNode* phead)
{assert(phead);//if (phead == NULL)//{//	return true;//}//else//{//	return false;//}//上面几行代码可以直接写成下面这一句return phead->next == phead; //如果相等就是true}void HDLListPopBack(HDLListNode* phead)
{assert(phead);//断言//还需要确定该链表非空assert(!isEmpty(phead));HDLListNode* tail = phead->prve;//找尾HDLListNode* tailPrve = tail->prve;//找到尾结点的前一个结点tailPrve->next = phead;//让新尾结点的next指向头结点phead->prve = tailPrve;//让头结点的peve指向新尾结点free(tail);//释放之前的尾结点tail = NULL;
}
  • 尾删验证

在这里插入图片描述

3.5.6 双向链表头插

  • 双向链表头插图解

在这里插入图片描述

  • 方式1：有先后顺序必须先执行12，再执行34，如果不按顺序来，就找不到后面d1节点了

void HDLListPushFront(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListNode* newnode = BuyListNode(x);//申请一个要插入的结点newnode//方式1 ：有先后顺序HDLListNode* cur = phead->next; //先找到要插入的结点位置 newnode->next = cur; //让新结点的next指向cur结点cur->prve = newnode;//让cur 的prve指向newnodephead->next = newnode;//让头结点的next指向新插入的newnode结点newnode->prve = phead;//让新插入的newnode结点的peve指向头结点
}
  • 方式1验证

在这里插入图片描述

  • 方式2，不需要有先后顺序，因为我们先找了一个first结点记录了下一个结点d1的位置
void HDLListPushFront(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListNode* newnode = BuyListNode(x);//申请一个要插入的结点newnode//方式1 ：有先后顺序//HDLListNode* cur = phead->next; //先找到要插入的结点位置 //newnode->next = cur; //让新结点的next指向cur结点//cur->prve = newnode;//让cur 的prve指向newnode//phead->next = newnode;//让头结点的next指向新插入的newnode结点//newnode->prve = phead;//让新插入的newnode结点的peve指向头结点//方式2：先记录下要插入位置结点，不需要有先后顺序HDLListNode* first = phead->next; //记录下要插入结点位置firstphead->next = newnode; //让头结点指向newnodenewnode->prve = phead;//让newnode的prve 指向头结点newnode->next = first;//让newnode 的next指向firstfirst->prve = newnode;//让first的peve指向newnode
}
  • 方式2验证

在这里插入图片描述

3.5.7 双向链表头删

  • 双向链表头删图解

在这里插入图片描述

  • 双向链表头删代码实现
void HDLListPuopFront(HDLListNode* phead)
{assert(phead);//断言//还需要确定该链表非空assert(!isEmpty(phead));HDLListNode* delNode = phead->next;//找到要删除的结点HDLListNode* cur = delNode->next; //找到要删除节点的后一个结点curphead->next = cur;//让头结点的next直接指向curcur->prve = phead;//让cur的prve直接指向pheadfree(delNode);//释放要删除的结点delNode = NULL;
}
  • 头删验证

在这里插入图片描述

3.5.8 双向链表查找

  • 双向链表查找代码实现
HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListNode* cur = phead->next; //让cur结点从头结点的下一个结点位置出发，while (cur != phead)//遍历完整个链表，就是从头结点下一个结点出发再次回到头结点{while (cur->data == x)//如果查找到了{return cur;//返回查找到的结点}cur = cur->next; //cur一直往后遍历}return NULL;
}
  • 双向链表查找验证

在这里插入图片描述

3.5.9 双向链表删除pos位置的结点

  • 双向链表删除pos位置的结点图解

在这里插入图片描述

  • 双向链表删除pos位置的结点代码实现
HDLListNode* HDLListErase(HDLListNode* pos)
{assert(pos);HDLListNode* posPrve = pos->prve;//找到pos的前一个结点HDLListNode* posNext = pos->next;//找到pos的后一个结点posPrve->next = posNext;//让前一个结点的next直接指向pos的后一个结点posNext->prve = posPrve;//让后一个结点的prve直接指向pos的前一个结点free(pos);//释放pos结点
}
  • 双向链表删除pos位置的结点，功能验证
void test()
{HDLListNode* plist = HDLListInit();HDLListPushBack(plist, 1);HDLListPushBack(plist, 2);HDLListPushBack(plist, 3);HDLListPushBack(plist, 4);HDLListPrint(plist);HDLListNode* pos = HDLListFind(plist, 2);if (pos){HDLListErase(pos);pos = NULL;}HDLListPrint(plist);
}
int main()
{test();return 0;
}

在这里插入图片描述

  • 实现了这个函数，我们的尾删直接调用这个函数就行，删除phead->prve
void HDLListPopBack(HDLListNode* phead)
{assert(phead);//断言//还需要确定该链表非空assert(!isEmpty(phead));HDLListErase(phead->prve);
}

在这里插入图片描述

  • 实现了这个函数，我们的头删也可以直接调用这个函数，删除phead->next
void HDLListPopFront(HDLListNode* phead)
{assert(phead);//断言//还需要确定该链表非空assert(!isEmpty(phead));HDLListErase(phead->next);
}

在这里插入图片描述

3.5.10 双向链表在pos的前面进行插入

  • 双向链表在pos的前面进行插入代码实现
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* prve = pos->prve;LTNode* newNode = BuyListNode(x);prve->next = newNode;newNode->prve = prve;newNode->next = pos;pos->prve = newNode;
}
  • 双向链表在pos的前面进行插入功能验证

在这里插入图片描述

  • 实现了这个函数，我们的头插直接调用这个函数就行，插入到phead->next位置
void HDLListPushFront(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListInsert(phead->next, x);
}

在这里插入图片描述

  • 尾插入同理，插入到phead位置
void HDLListPushBack(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListInsert(phead, x);
}

在这里插入图片描述

4.顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，但物理上不一定连续
随机访问支持O(1)不支持：O(N)
任意位置插入或者删除元素可能需要搬移元素，效率低O(N)只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

附录：双向带头循环链表接口实现源代码

5.1 .h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct HDLListNode
{struct HDLListNode* next;struct HDLListNode* prve;LTDataType data;
}HDLListNode;//双向链表的初始化
HDLListNode* HDLListInit();
//申请一个新结点
HDLListNode* BuyListNode(LTDataType x);
//链表销毁
void HDLLDestroy(HDLListNode* phead);
//双向链表的打印
void HDLListPrint(HDLListNode* phead);
//双向链表尾插
void HDLListPushBack(HDLListNode* phead, LTDataType x);
//双向链表尾删
void HDLListPopBack(HDLListNode* phead);
//双向链表头插
void HDLListPushFront(HDLListNode* phead, LTDataType x);
//双向链表头删
void HDLListPupFront(HDLListNode* phead);
//双向链表查找
HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x);
//双向链表删除pos位置的结点
HDLListNode* HDLListErase(HDLListNode* pos);
// 双向链表在pos的前面进行插入
HDLListNode* HDLListInsert(HDLListNode* pos, LTDataType x);

5.2 .c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"HDLList20250307.h"HDLListNode* BuyListNode(LTDataType x)
{HDLListNode* newNode = (HDLListNode*)malloc(sizeof(HDLListNode)); //申请空间if (newNode == NULL){perror("BuyListNode::malloc fail!"); //如果申请失败报错return NULL;//返回NULL}//对新申请的结点进行初始化newNode->next = newNode;newNode->prve = newNode;newNode->data = x;return newNode;//返回新结点
}HDLListNode* HDLListInit()
{HDLListNode* phead = BuyListNode(-1);//申请新结点phead->next = phead;phead->prve = phead;return phead;//返回头结点
}void HDLLDestroy(HDLListNode* phead)
{assert(phead);HDLListNode* cur = phead->next;//让cur从带哨兵的头结点之后的第一个有效结点开始遍历while (cur!=phead)//遍历一遍链表，一个节点一个节点的释放{HDLListNode* next = cur->next;//记录cur的下一个结点free(cur);//释放结点cur = next;//cur往后走}free(phead);//最后是否哨兵头结点}
//双向链表的打印
void HDLListPrint(HDLListNode* phead)
{assert(phead);//断言，确保传入参数正确printf("<=head=>");HDLListNode* cur = phead->next;while (cur != phead){printf("%d=>", cur->data);cur = cur->next;//cur继续往后走}//最后全部打印完之后，换行。printf("\n");
}
void HDLListPushBack(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListNode* newnode = BuyListNode(x); //申请一个新结点HDLListNode* tail = phead->prve;//尾结点直接就能找到tail->next = newnode;//让尾结点指向要插入的结点newnode->prve = tail;//让新插入发结点的prve指向之前的尾结点newnode->next = phead;//让新插入的结点的next指向头结点phead->prve = newnode;//让头结点的prve指向新的尾结点//HDLListInsert(phead, x);
}bool isEmpty(HDLListNode* phead)
{assert(phead);//if (phead == NULL)//{//	return true;//}//else//{//	return false;//}//上面几行代码可以直接写成下面这一句return phead->next == phead; //如果相等就是true}void HDLListPopBack(HDLListNode* phead)
{assert(phead);//断言//还需要确定该链表非空assert(!isEmpty(phead));HDLListNode* tail = phead->prve;//找尾HDLListNode* tailPrve = tail->prve;//找到尾结点的前一个结点tailPrve->next = phead;//让新尾结点的next指向头结点phead->prve = tailPrve;//让头结点的peve指向新尾结点free(tail);//释放之前的尾结点tail = NULL;//HDLListErase(phead->prve);
}void HDLListPushFront(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListInsert(phead->next, x);//HDLListNode* newnode = BuyListNode(x);//申请一个要插入的结点newnode//方式1 ：有先后顺序//HDLListNode* cur = phead->next; //先找到要插入的结点位置 //newnode->next = cur; //让新结点的next指向cur结点//cur->prve = newnode;//让cur 的prve指向newnode//phead->next = newnode;//让头结点的next指向新插入的newnode结点//newnode->prve = phead;//让新插入的newnode结点的peve指向头结点//方式2：先记录下要插入位置结点，不需要有先后顺序//HDLListNode* first = phead->next; //记录下要插入结点位置first//phead->next = newnode; //让头结点指向newnode//newnode->prve = phead;//让newnode的prve 指向头结点//newnode->next = first;//让newnode 的next指向first//first->prve = newnode;//让first的peve指向newnode
}void HDLListPopFront(HDLListNode* phead)
{assert(phead);//断言//还需要确定该链表非空assert(!isEmpty(phead));HDLListNode* delNode = phead->next;//找到要删除的结点HDLListNode* cur = delNode->next; //找到要删除节点的后一个结点curphead->next = cur;//让头结点的next直接指向curcur->prve = phead;//让cur的prve直接指向pheadfree(delNode);//释放要删除的结点delNode = NULL;//HDLListErase(phead->next);
}HDLListNode* HDLListFind(HDLListNode* phead, LTDataType x)
{assert(phead);HDLListNode* cur = phead->next; //让cur结点从头结点的下一个结点位置出发，while (cur != phead)//遍历完整个链表，就是从头结点下一个结点出发再次回到头结点{while (cur->data == x)//如果查找到了{return cur;//返回查找到的结点}cur = cur->next; //cur一直往后遍历}return NULL;
}HDLListNode* HDLListErase(HDLListNode* pos)
{assert(pos);HDLListNode* posPrve = pos->prve;//找到pos的前一个结点HDLListNode* posNext = pos->next;//找到pos的后一个结点posPrve->next = posNext;//让前一个结点的next直接指向pos的后一个结点posNext->prve = posPrve;//让后一个结点的prve直接指向pos的前一个结点free(pos);//释放pos结点
}HDLListNode* HDLListInsert(HDLListNode* pos, LTDataType x)
{assert(pos);HDLListNode* newnode = BuyListNode(x);//申请一个新结点HDLListNode* posPrve = pos->prve;//找到pos的前一个位置posPrveposPrve->next = newnode;//posPrve的next直接指向新结点newnodenewnode->prve = posPrve;//让newnode的prve指向posPrvenewnode->next = pos;//让newnode的next指向pospos->prve = newnode;//让pos的prve指向newnode
}

5.3 test.c文件

#define _CRT_SECURE_NO_WARNINGS 1
#include"HDLList20250307.h"
void test()
{HDLListNode* plist = HDLListInit();HDLListPushBack(plist, 1);HDLListPushBack(plist, 2);HDLListPushBack(plist, 3);HDLListPushBack(plist, 4);HDLListPrint(plist);/*  HDLListPopBack(plist);*/HDLListPopFront(plist);HDLListPrint(plist);//HDLListPushFront(plist, 5);//HDLListPushFront(plist, 6);//HDLListPrint(plist);//HDLListPrint(plist);//HDLListNode* ret = HDLListFind(plist, 2);//ret->data *=2;//HDLListPrint(plist);//HDLListNode* pos = HDLListFind(plist, 2);//if (pos)//{//    HDLListErase(pos);//    pos = NULL;//}//HDLListPrint(plist);//HDLListNode* pos = HDLListFind(plist, 2);//if (pos)//{//    HDLListInsert(pos,7);//    pos = NULL;//}//HDLListPrint(plist);
}
int main()
{test();return 0;
}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

Darkreader插件导致B站评论区“更多评论”不显示 node.js途牛旅游网站数据可视化分析与设计程序+论文 可用于毕业设计 django基于Django的交友网站 测绘类（遥感）投稿期刊（卓越期刊、EI、CSCD、核心期刊）汇总，内附投稿链接 基于springboot的英语学习平台(springboot+ssm+html+mysql)含运行文档 Linux-常用命令（3）

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989