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

类似谷德设计网的网站百度下载安装最新版

news 2026/4/7 15:00:33
类似谷德设计网的网站,百度下载安装最新版,昆山网站维护,莆田网站开发公司电话目录 一.双向链表的结构 二. 双向链表的实现 1. 在List.h中结构体的定义和各函数的声明 1.1 结构体（节点）的定义 1.2 各函数的声明 2. 在List.c中各函数的实现 2.1 初始化 LTInit 2.2 尾插 LTPushBack 2.3 打印 LTPrint 2.4 头插 LTPushFron…

目录

一.双向链表的结构

二. 双向链表的实现

1. 在List.h中结构体的定义和各函数的声明 

1.1 结构体（节点）的定义 

1.2 各函数的声明

2. 在List.c中各函数的实现

2.1 初始化 LTInit

2.2 尾插 LTPushBack

2.3 打印 LTPrint

2.4 头插 LTPushFront

2.5 尾删 LTPopBack

2.6 头删 LTPopFront

2.7 在指定位置后插入数据 LTInsert

2.8 查找 LTFind

2.9 删除指定位置节点 LTErase

2.10 销毁 LTDestroy

三. 顺序表和双向链表的优缺点分析

四. 参考代码

 1. List.h

2. List.c

3. test.c

一.双向链表的结构

双向链表的结构

注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严谨，但是为了更好的理解就直接称为单链表的头节点。

带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨的”

“哨兵位”存在的意义：

遍历循环链表避免死循环。

二. 双向链表的实现

注：本次我们将实现一个双向带头循环链表。 

1. 在List.h中结构体的定义和各函数的声明 

1.1 结构体（节点）的定义 

//重命名数据类型
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//指向前一个节点struct ListNode* next;//指向后一个节点
}LTNode;

1.2 各函数的声明

//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);//打印
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

2. 在List.c中各函数的实现

2.1 初始化 LTInit

既然涉及到插入新节点，那我们就需要创建一个新节点，由于每次插入都需要创建新节点，所以我们设计一个新函数专门来创建新节点。

LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc failed");exit(1);}node->data = x;node->prev = node->next = node;return node;
}

注意：

1. 每次malloc申请空间后应当检查是否申请成功。

2. 将新申请的节点的前后指针指向自己，实现循环。

初始化操作我们需要创建哨兵节点，哨兵节点所带的值可以任意。

LTNode* LTInit(void)
{LTNode* node = LTBuyNode(EOF);return node;
}

2.2 尾插 LTPushBack

要对链表进行尾插，找到链表的哨兵节点，然后新节点插入哨兵节点的前一位，由于链表循环，所以也相当于尾插在链表尾。

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead ..... phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

2.3 打印 LTPrint

我们创建一个指针pcur指向哨兵节点的下一个节点并沿着链表向后依次打印，如果等于哨兵节点，就说明已经遍历完成。

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

2.4 头插 LTPushFront

与尾插类似，在哨兵节点的下一位进行插入，注意连接好前后指针。

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->next ......newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

2.5 尾删 LTPopBack

尾删前要注意链表有效且不为空，然后断开要释放节点和前后节点的前后指针，最后释放该节点。

void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表有效且不为空（只有一个哨兵位）//phead  ......  del->prev(phead->prev->prev)  del(phead->prev)LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}

2.6 头删 LTPopFront

与头删类似，在哨兵节点的下一位进行删除，注意连接好前后指针。

void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead  del(phead->next)  del->next(phead->next->next) ......phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = NULL;
}

2.7 在指定位置后插入数据 LTInsert

函数参数中提供了插入位置pos，连接好前后指针即可。

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//... pos newnode pos->next ...newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

2.8 查找 LTFind

与打印类似，遍历一次链表，查找是否有符合条件的节点，如果有返回节点指针，如果没有，返回空指针。

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

2.9 删除指定位置节点 LTErase

与在打印和查找类似，函数参数中提供了删除位置pos，处理好前后指针即可。

void LTErase(LTNode* pos)
{//pos理论上不能为phead，但是参数有限，无法校验assert(pos);//... pos->prev pos pos->next ...pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

2.10 销毁 LTDestroy

与在指定位置后插入数据类似，从哨兵节点的下一位遍历一次链表，遍历的同时用双指针法依次释放节点，最后释放哨兵节点。

void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁pheadfree(phead);phead = NULL;pcur = NULL;
}

我们可以发现，由于双向链表具有指向前后节点的指针，代码量大大减少，但是也需要处理好指针之间的关系。

三. 顺序表和双向链表的优缺点分析

顺序表和双向链表的优缺点

不同点

顺序表

链表（单链表）

存储空间上

物理上一定连续

逻辑上连续，但物理上不一定连续

随机访问

支持O(1)

不支持：O(N)

任意位置插入或者删除元素

可能需要搬移元素，效率低O(N)

只需修改指针指向

插入

动态顺序表，空间不够时需要扩容

没有容量的概念

应用场景

元素高效存储+频繁访问

任意位置插入和删除频繁

四. 参考代码

 1. List.h

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>//重命名数据类型
typedef int LTDataType;typedef struct ListNode
{LTDataType data;struct ListNode* prev;//指向前一个节点struct ListNode* next;//指向后一个节点
}LTNode;//初始化
//void LTInit(LTNode** pphead);
LTNode* LTInit(void);//尾插 -- 不改变哨兵位 -- 传一级指针
void LTPushBack(LTNode* phead, LTDataType x);//打印
void LTPrint(LTNode* phead);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在指定位置后插入数据
void LTInsert(LTNode* pos, LTDataType x);//查找
LTNode* LTFind(LTNode* phead, LTDataType x);//删除指定位置节点
void LTErase(LTNode* pos);//销毁
void LTDestroy(LTNode* phead);

2. List.c

#include "List.h"LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc failed");exit(1);}node->data = x;node->prev = node->next = node;return node;
}//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit(void)
{LTNode* node = LTBuyNode(EOF);return node;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead ..... phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->next ......newnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表有效且不为空（只有一个哨兵位）//phead  ......  del->prev(phead->prev->prev)  del(phead->prev)LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;//删除del节点free(del);del = NULL;
}void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead  del(phead->next)  del->next(phead->next->next) ......phead->next = del->next;del->next->prev = phead;//删除del节点free(del);del = 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;
}void LTErase(LTNode* pos)
{//pos理论上不能为phead，但是参数有限，无法校验assert(pos);//... pos->prev pos pos->next ...pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}void LTDestroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while(pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁pheadfree(phead);phead = NULL;pcur = NULL;
}void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//... pos newnode pos->next ...newnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

3. test.c

#include "List.h"void ListTest01()
{LTNode* plist = NULL;plist = LTInit();//LTPushBack(plist, 1);//LTPushBack(plist, 2);//LTPushBack(plist, 3);//LTPushBack(plist, 4);//LTPushBack(plist, 5);//LTPrint(plist);LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPushFront(plist, 4);LTPushFront(plist, 5);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);//LTNode* find = NULL;//find = LTFind(plist, 2);//if (find)//{//	printf("找到了！\n");//}//else//{//	printf("找不到！\n");//}//find = LTFind(plist, 7);//if (find)//{//	printf("找到了！\n");//}//else//{//	printf("找不到！\n");//}//LTNode* find = NULL;//find = LTFind(plist, 2);//if (find)//{//	printf("找到了！\n");//}//else//{//	printf("找不到！\n");//}//LTInsert(find, 6);//LTPrint(plist);//LTErase(find);//find = NULL;//LTPrint(plist);LTDestroy(plist);plist = NULL;
}int main()
{ListTest01();return 0;
}

http://www.hkea.cn/news/694118/

相关文章：

  • 南通网站建设搭建网站卖链接
  • 驻马店市做网站seo臻系统
  • 找公司做网站怎么图片都要自己找百度推广官网电话
  • 网站小样用什么做seo外链平台热狗
  • 建站点的步骤sem是什么
  • 深圳专业做网站的衡水网站优化推广
  • 徐汇科技网站建设2345中国最好的网址站
  • 邢台论坛吧百度seo收录软件
  • 做国外服务器网站吗怎么让百度搜索靠前
  • 做动态图网站有哪些自建站怎么推广
  • web网站开发课程设计报告seo技术培训沈阳
  • 会宁网站建设公司网站优化助手
  • 网站设计制作体会2023年5月最新疫情
  • 月亮湾设计有限公司网站南宁seo产品优化服务
  • 福田欧曼服务站电话上海高端seo公司
  • 高端网站建设哪家好谷歌seo和百度seo
  • 前端写一个页面多少钱海口网站关键词优化
  • 浦东新区建设局官方网站东莞seo关键词
  • 在百度做橱柜网站进入百度一下官网
  • wordpress调用分类标签站长工具查询seo
  • 网站做全局搜索云南新闻最新消息今天
  • 公司网站推广方案长春seo代理
  • 网站地图怎么样做更利于收录手机百度搜索引擎入口
  • 中国建筑公司网站谷歌浏览器官方app下载
  • 厦门网站建设策划seo网站优化培训找哪些
  • 宝安区住房和建设局官方网站seo搜索引擎优化书籍
  • 省建设厅执业资格注册中心网站2023搜索最多的关键词
  • 本地wordpress上传搜索引擎营销优化策略有哪些
  • html手机网站模板培训心得体会800字
  • 合肥做网站公司哪家好经典的软文广告