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

长沙网站开发招聘/昆明做网站的公司

news 2025/7/5 16:34:30
长沙网站开发招聘,昆明做网站的公司,渭南做网站电话,互联网营销师证书好考吗文章目录 目录 一、双链表的概念 二、双链表的实现 1.初始化 2.尾插 3.头插 4.打印 5.判断双链表是否为空 6.尾删 7.头删 8.查找 9.在指定的位置之后插入数据 10.删除指定位置的数据 11.销毁 三、完整源码 总结 一、双链表的概念 链表的结构非常多样&#xff0…

文章目录

目录

一、双链表的概念

二、双链表的实现

1.初始化

2.尾插

3.头插

4.打印

5.判断双链表是否为空

6.尾删

7.头删

8.查找

9.在指定的位置之后插入数据

10.删除指定位置的数据

11.销毁

三、完整源码

总结

一、双链表的概念

链表的结构非常多样，以下情况组合起来就有8种链表结构，分为带头，不带头，单向，双向，循环，不循环。

今天我们要了解的是带头双向循环链表，即双链表。

二、双链表的实现

双链表的定义

在实现双链表前，先简单了解三个指针：

  1. pcur：当前结点
  2. prev：指向当前结点的前一个结点，简称前驱结点
  3. next：指向当前结点的后一个结点，简称后继结点
//定义双链表结构体
typedef int LTDatatype;
typedef struct ListNode {LTDatatype data;struct ListNode* next;//指向下一个结点，即后继结点struct ListNode* prev;//指向上一个结点，即前驱结点
}LTNode;

1.初始化

代码解析：

初始化链表就需要开辟空间，在堆上申请一个结点的空间，用函数buyNode来进行实现，初始时让next,prev指向自己，并返回头结点

LTNode* buyNode(LTDatatype x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("NULL");exit(1);}node->data = x;node->next = node->prev = node;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = buyNode(-1);return phead;
}

注：在双链表中，phead会自己指向自己，不会在指向下一个结点时而丢失，next、prev的指向的变化不会影响当前结点，即地址不会发生改变，所以实现双链表的函数都用一级指针。

2.尾插

代码解析：因为要新插入一个数据，所以开辟一个结点的空间(要插入几个结点，就开辟几个结点的空间)。先设置新结点，把新结点的位置插入到当前链表中，让newnode->prev指向尾结点(phead->prev)，newnode->next指向头结点(phead)；再更新原链表的指向，把尾结点(phead->prev)的next指向newnode，头结点(phead)的prev指向newnode.

//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

3.头插

代码解析：

和尾插一样需要开辟一个结点大小的空间。先设置新结点，把新结点的位置插入到当前链表中，让newnode->next指向d1(phead->next)，newnode->prev指向头结点(phead)；再改变链表中d1(phead->next)的位置，让d1->prev指向newnode,头结点(phead)的next指向newnode

//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);newnode->next = phead->next;//phead->next为d1newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

注：把newnode插在d1前面是头插，但插在头结点phead前面是尾插

4.打印

代码解析：通过遍历链表来打印结点

//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ->", pcur->data);pcur = pcur->next;}printf("\n");
}

5.判断双链表是否为空

代码解析：

用bool函数判断头结点是否指向自己，是指向自己就为空

//bool类型判断
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

6.尾删

代码解析：

先判断链表是否为空，不为空就对最后一个结点进行删除。创建新指针del先保存当前结点(即尾结点phead->prev)，避免变成野指针；让d2(del->prev)的next指向头结点，phead->prev指向d2->prev；最后对尾结点进行释放并置为NULL

//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

7.头删

代码解析：

和尾删一样，先判断链表是否为空，不为空就对第一个结点进行删除。这里第一个结点不是头结点是d1。创建新指针del保存当前结点d1(phead->next)，改变链表中的位置，让d2(del->next)的prev指向头结点，头结点的next指向d2(del->next)

//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead del del->nextdel->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

8.查找

代码解析：

遍历链表中的结点，找到需要查找的结点就返回当前的结点，找不到就返回NULL

//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{LTNode* pcur = phead->next;while (pcur){if (pcur->data = x){return pcur;}}return NULL;
}

9.在指定的位置之后插入数据

代码解析：

在指定的位置之后插入数据之前，需要用函数LTFind对其进行查找，避免出错。和前面尾插 头插一样需要申请一个结点空间的大小。先设置新结点，把新结点的位置插入到当前链表中，比如在d2的后面插入一个结点，d2=pos，让newnode->next指向d2->next，newnode->prev指向d2；再改变链表结点的位置，让d3(d2->next)的prev指向newnode,d3指向newnode.

void LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = buyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

10.删除指定位置的数据

代码解析：

先断言当前结点是否为空，不为空对其进行删除。比如删除d2,d2=pos,让d2->prev的next指向d2->nxet，在让d2->next的prev指向d2->prev.

void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

11.销毁

代码解析：

创建新指针pcur，让pcur从phead->next开始销毁。循环遍历，又创建一个新指针next,让next从pcur->next开始走，保证next走在pcur前面，对下一个结点pcur->next进行保存，避免删除当前结点pcur时出现野指针的情况；保存好pcur->next就对当前pcur进行释放，让pcur继续往后走pcur=next，一直循环释放，只剩头结点就跳出循环。最后对头结点进行释放并置为空。

void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

三、完整源码

List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义双链表结构体
typedef int LTDatatype;
typedef struct ListNode {LTDatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
LTNode* LTInit();//打印
void LTPrint(LTNode* phead);
//bool类型判断
bool LTEmpty(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDatatype x);//尾插
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);//销毁
void LTDesTroy(LTNode* phead);

List.c

#include"List.h"LTNode* buyNode(LTDatatype x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("NULL");exit(1);}node->data = x;node->next = node->prev = node;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = buyNode(-1);return phead;
}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ->", pcur->data);pcur = pcur->next;}printf("\n");
}//bool类型判断
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);newnode->next = phead->next;//phead->next为d1newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead del del->nextdel->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{LTNode* pcur = phead->next;while (pcur){if (pcur->data = x){return pcur;}}return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = buyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除pos位置数据
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

Test.c

#include"List.h"void test()
{//LTNode* plist = NULL;//LTInit(&plist);//尾插LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插//LTNode* plist = LTInit();//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPushFront(plist, 3);//LTPushFront(plist, 4);//LTPrint(plist);//尾删//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//头删//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//在pos位置之后插入数据//LTNode* find = LTFind(plist, 4);//if (find == NULL)//{//	printf("无\n");//}//else {//	printf("有\n");//}//LTInsert(find, 77);//LTErase(find);//LTPrint(plist);//销毁LTDesTroy(plist);plist = NULL;}int main()
{test();return 0;
}

总结

非常感谢大家阅读完这篇博客。希望这篇文章能够为您带来一些有价值的信息和启示。如果您有任何问题或建议，欢迎在评论区留言，我们一起交流学习。

http://www.whsansanxincailiao.cn/news/30278118.html

相关文章：

  • 网站域名所有权 查询/国内搜索引擎有哪些
  • 办公室装修设计多少费用/短视频关键词优化
  • 优化资源配置/seo外包公司一般费用是多少
  • 浙江微信网站建设/各大网站域名大全
  • 如何优化关键词的排名/郑州seo排名优化
  • 怎样做关于自己的网站/营销策略ppt
  • 做高仿网站/网络培训网站
  • 网站建设群/广州竞价托管代运营
  • 个人定做衣服店/seo翻译
  • 织梦做的网站网速打开慢是怎么回事/百度查询网
  • 长春公司做网站/网络推广公司名字
  • 国外网站推广软件/广告资源网
  • 免费广告行业网站建设/百度首页排名优化平台
  • 权威发布英文/优化网站收费标准
  • 河源网站建设工作室/哈尔滨网络推广优化
  • 西宁最好的建站公司/企业宣传推广方案
  • 新手学建设网站书籍/seo咨询岳阳
  • 邯郸网站设计注册/如何找推广平台
  • 做加盟的网站/口碑营销怎么做
  • 广东微信网站建设哪家专业/外贸网站建设推广
  • ae做网站导航/seo百科大全
  • 最好的网站建设/html静态网页制作
  • 产品做国外网站有哪些/网站排行榜前十名
  • 网站空间租赁500mb/网络推销平台有哪些
  • 计算机网站建设知识/济南优化网站的哪家好
  • 购物网站首页分成几个模块/手机seo关键词优化
  • 企业网站建设应遵守的原则/佛山关键词排名效果
  • 在线教育做网站好还是app好/seo新方法
  • 怎样做触屏版手机网站/住房和城乡建设部官网
  • 站长统计app进入网址/aso优化违法吗