当前位置： 首页 > news >正文

网站建站ddp南昌网站seo外包服务

news 2025/7/17 4:52:47
网站建站ddp,南昌网站seo外包服务,潍坊网络推广个人合作,国内最新新闻内容个人主页 ： 个人主页 个人专栏 ： 《数据结构》 《C语言》 文章目录 前言 一、实现思路1.节点的结构(ListNode)2.新节点的创建(BuyListNode)3.头结点的创建(ListCreate)4.双向链表的销毁(ListDestroy)5.双向链表的打印(ListPrint)6.双向链表的尾插(ListPu…

在这里插入图片描述

个人主页 ： 个人主页
个人专栏 ： 《数据结构》 《C语言》

文章目录

    • 前言
  • 一、实现思路
    • 1.节点的结构(ListNode)
    • 2.新节点的创建(BuyListNode)
    • 3.头结点的创建(ListCreate)
    • 4.双向链表的销毁(ListDestroy)
    • 5.双向链表的打印(ListPrint)
    • 6.双向链表的尾插(ListPushBack)
    • 7.双向链表的尾删(ListPopBack)
    • 8.双向链表的头插(ListPushFront)
    • 9.双向链表的头删(ListPopFront)
    • 10.双向链表的查找(ListFind)
    • 11.双向链表在pos前插入(ListInsert)
    • 12.双向链表删除pos位置处的节点(ListErase)
  • 二、代码实现
  • 总结

前言

本篇博客，将要实现的是带头双向循环链表，该结构实现尾插，尾删只需要O(1)的时间复杂度。
其结构如下所示：

在这里插入图片描述

一、实现思路

1.节点的结构(ListNode)

既然要实现的链表是双向循环的，那么对于指针域，我们就需要指向节点上一个的指针和指向节点下一个的指针。至于双向循环，我们只需要尾节点的next指向头结点，头结点的prev指向尾节点，即可实现双向循环。
如下：
在这里插入图片描述

typedef int LTDataType;//方便以后修改数据类型typedef struct ListNode
{LTDataType data;struct ListNode* next;struct ListNode* prev;
}ListNode;

2.新节点的创建(BuyListNode)

动态开辟一块空间，使该节点的prev，next都指向自己(方便头结构的创建)，再为data赋值，返回该空间地址。

在这里插入图片描述

//创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}

3.头结点的创建(ListCreate)

复用BuyListNode函数，使头结点的data为无效数据(这里即为-1)。

//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}

4.双向链表的销毁(ListDestroy)

要销毁链表，我们就要遍历链表，那么如何遍历链表？

  • 以遍历到头节点为结束条件
  • 从头结点的下一个节点开始遍历

如上，我们就可以循环遍历链表。
销毁节点，我们需要两指针变量，一个记录要free的节点(cur)，一个记录要free的节点的下一个节点(curNext)。每次free(cur)，使cur = curNext。
在这里插入图片描述

//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* curNext = cur->next;free(cur);cur = curNext;}free(pHead);
}

5.双向链表的打印(ListPrint)

我们只有遍历打印链表即可。

  • 以遍历到头节点为结束条件
  • 从头结点的下一个节点开始遍历
//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("head<=>");while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("head\n");
}

6.双向链表的尾插(ListPushBack)

我们只需要让尾节点(tail)的next指向newnode，newnode的prev指向尾节点(tail)，newnode的next指向头结点，头结点的prev指向newnode.
我们知道该链表是双向循环的，那么头结点的上一个节点就是尾节点。(与单链表相比该链表实现尾插并不需要遍历找尾，时间复杂度是O(1) )。
在这里插入图片描述

//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyListNode(x);ListNode* tail = pHead->prev;tail->next = newnode;newnode->prev = tail;pHead->prev = newnode;newnode->next = pHead;
}

7.双向链表的尾删(ListPopBack)

我们只需要两个指针tail (指向尾节点)，tailPrev (指向尾节点的上一个节点)。
free掉tail，使tailPrev的next指向头结点，头结点的prev指向tailPrev。

  • 注意：head->next == head 时，链表无有效数据，不能尾删数据。

在这里插入图片描述

//双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead->next == pHead时，链表没有元素assert(pHead->next != pHead);ListNode* tail = pHead->prev;ListNode* tailPrev = tail->prev;pHead->prev = tailPrev;tailPrev->next = pHead;free(tail);
}

8.双向链表的头插(ListPushFront)

我们只需要一个指针 first (头结点的下一个节点)，使first的prev指向newnode，newnode的next指向first，head的next指向newnode，newnode的prev指向head。

在这里插入图片描述
head节点是哨兵位，不存储有效数据。

//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* newnode = BuyListNode(x);ListNode* first = pHead->next;newnode->next = first;first->prev = newnode;newnode->prev = pHead;pHead->next = newnode;
}

9.双向链表的头删(ListPopFront)

我们需要两个指针frist (指向头结点的下一个节点)，second (指向头结点的下一个的下一个节点)。
free掉first，使second的prev指向头结点，头结点的next指向second。

  • 注意：如果head->next == head，表示链表为空，不能头删。

在这里插入图片描述

//双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);ListNode* first = pHead->next;ListNode* second = first->next;second->prev = pHead;pHead->next = second;free(first);
}

10.双向链表的查找(ListFind)

我们需要遍历链表，比较链表元素是否是要查找对象。如果找到了，返回该节点的地址。如果找不到，返回NULL。

//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}

11.双向链表在pos前插入(ListInsert)

我们需要一个指针 posPrev (指向pos前一个节点)。
pos的prev指向newnode，newnode的next指向pos；posPrev的next指向newnode，newnode的prev指向posPrev。

  • 如果pos指向头结点(哨兵位)，那么ListInsert相当与完成尾插。
  • 如果pos指向头结点(哨兵位)的下一个节点，那么ListInsert相当于头插。

在这里插入图片描述

//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}

12.双向链表删除pos位置处的节点(ListErase)

我们需要两个指针posPrev(记录pos的上一个节点的地址)，posNext(记录pos的下一个节点的地址)。free掉pos，使posNext的prev指向posPrev，posPrev的next指向posNext。

  • 如果pos指向头结点的下一个，那么ListErase相当于头删。
  • 如果pos指向头结点的上一个(也就是尾节点)，那么ListErase相当于尾删。

在这里插入图片描述


//双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext = pos->next;ListNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}

二、代码实现

对于头插，尾插函数，我复用了ListInsert函数。
对于头删，尾删函数，我复用了ListErase函数。

//Lish.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;
}ListNode;//创建返回链表的头结点
ListNode* ListCreate();//创建新节点
ListNode* BuyListNode(LTDataType x);//双向链表的销毁
void ListDestroy(ListNode* pHead);//双向链表的打印
void ListPrint(ListNode* pHead);//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x);//双向链表的尾删
void ListPopBack(ListNode* pHead);//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x);//双向链表的头删
void ListPopFront(ListNode* pHead);//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x);//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x);//双向链表删除pos位置的节点
void ListErase(ListNode* pos);
//Lish.c  文件#include "List.h"//创建返回链表的头结点
ListNode* ListCreate()
{return BuyListNode(-1);
}//创建新节点
ListNode* BuyListNode(LTDataType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = newnode;newnode->prev = newnode;return newnode;
}//双向链表的打印
void ListPrint(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;printf("head<=>");while (cur != pHead){printf("%d<=>", cur->data);cur = cur->next;}printf("head\n");
}//双向链表的尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode = BuyListNode(x);ListNode* tail = pHead->prev;tail->next = newnode;newnode->prev = tail;pHead->prev = newnode;newnode->next = pHead;*/ListInsert(pHead, x);
}//双向链表的尾删
void ListPopBack(ListNode* pHead)
{assert(pHead);//pHead->next == pHead时，链表没有元素assert(pHead->next != pHead);/*ListNode* tail = pHead->prev;ListNode* tailPrev = tail->prev;pHead->prev = tailPrev;tailPrev->next = pHead;free(tail);*/ListErase(pHead->prev);
}//双向链表的头插
void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);/*ListNode* newnode = BuyListNode(x);ListNode* first = pHead->next;newnode->next = first;first->prev = newnode;newnode->prev = pHead;pHead->next = newnode;*/ListInsert(pHead->next, x);
}//双向链表的头删
void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->next != pHead);/*ListNode* first = pHead->next;ListNode* second = first->next;second->prev = pHead;pHead->next = second;free(first);*/ListErase(pHead->next);
}//双向链表的查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}//双向链表在pos前进行插入
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* posPrev = pos->prev;newnode->prev = posPrev;posPrev->next = newnode;newnode->next = pos;pos->prev = newnode;
}//双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{assert(pos);ListNode* posNext = pos->next;ListNode* posPrev = pos->prev;posPrev->next = posNext;posNext->prev = posPrev;free(pos);
}//双向链表的销毁
void ListDestroy(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->next;while (cur != pHead){ListNode* curNext = cur->next;free(cur);cur = curNext;}free(pHead);
}

总结

以上就是双向链表的实现！！！
在这里插入图片描述

http://www.ds6.com.cn/news/34495.html

相关文章：

  • 北京市城乡和住房建设委员会网站seo优化工具有哪些
  • 网站开发用JAVA还是net新浪博客seo
  • 国外做批发的网站有哪些手续营销推广渠道有哪些
  • 东莞常平学校网站建设泰州seo网络公司
  • 校园网站建设方案免费收录平台
  • 中国充电网络公司排名网站关键词排名优化客服
  • 网站图片轮播怎么做的bt磁力兔子引擎
  • 织梦网站程序网站建设与管理是干什么的
  • 做一个企业网站多少钱外国人b站
  • 有没有专门做二手车网站怎么免费创建自己的网站
  • 网站建设saas排名优化防控措施
  • 广告设计专业就业方向谷歌seo推广
  • 网站qq客服怎么做想做电商怎么入手
  • 响应式网站文章公司推广方法有哪些
  • 关于茶网站模板怎么做推广和宣传
  • 山西做网站多少钱百度搜索引擎seo
  • 目前最好的免费网站站长工具外链查询
  • 保定 营销型网站建设谷歌外链代发
  • wordpress 链接打不开夫唯seo怎么样
  • 芜湖网站建设哪家好app推广工作是做什么的
  • 企业网站功能清单网络媒体广告代理
  • 龙岗微信网站制作黄山网站建设
  • nas搭建wordpress博客网站深圳搜狗seo
  • 学校学生网站模板下载seo排名优化方法
  • 重庆做网站人才长尾关键词挖掘工具
  • 台州招聘网站建设阿里云搜索引擎入口
  • 网站建设计划谷歌推广seo
  • 桂林有哪些做网站的电话怎么做电商生意
  • 重庆网站建设找承越91关键词
  • 漂流瓶做任务网站seo矩阵培训