当前位置: 首页 > ops >正文

0724 双向链表

Part 1.双向链表的完成以下要求

1.双向链表的节点创建

双向链表相较于单向链表,函数的指针域多了一个指向前面的prev指针,每个节点的next指向上一个节点,prev指向下一个节点。创建一个结构体嵌套联合体,联合体储存普通节点的data,头节点的len。双向链表的头节点的prev指向NULL,尾节点的next指向NULL。在初始化的时候,直接将新节点的prev和next全指向NULL。

typedef struct Node
{union{int len;datatype data;};struct Node *next;struct Node *prev;
}*doublelinklist;doublelinklist create_node(int flag)
{doublelinklist s = (doublelinklist)malloc(sizeof(struct Node));if(s == NULL){return NULL;}if(flag == 1)s->len = 0;else if(flag == 0)s->data = 0;s->next = s->prev = NULL;return s;
}

2.双向链表的头插

双向链表的头插,需要创建一个新节点将值赋到新节点里,然后让head的next指向新节点,新节点的next指向head->next,新节点的prev指向head,head->next的prev指向新节点,如果新节点是第一个节点,则不需要进行head->next的prev指向新节点操作,因为head->next是NULL,NULL没有prev,不然会报段错误。

int head_insert(doublelinklist head,datatype element)
{if(head == NULL)return Faulse;doublelinklist p = create_node(0);	if(p == NULL)return Faulse;p->data = element;p->next = head->next;p->prev = head;if(head->next != NULL)head->next->prev = p;head->next = p;head->len++;return Sccuess;
}

3.双向链表的遍历

while循环当p没到NULL(链表没到尾的时候),循环输出data,并且下移p = p->next

int output(doublelinklist head)
{	if(head == NULL || head->len == 0)return Faulse;doublelinklist p = head->next;while(p != NULL){printf("%d\t",p->data);p = p->next;}printf("\n");return Sccuess;
}

4.双向链表的尾插

遍历循环找到链表的尾节点,将新节点的prev指向尾节点,尾节点的next指向新节点即可。新节点在申请的时候的next就指向NULL,所以不需要改指向,而尾节点的next为NULL,没有prev,也不需要指向。

int rear_insert(doublelinklist head,datatype element)
{if(head == NULL)return Faulse;doublelinklist p = head;while(p->next != NULL)p = p->next;doublelinklist s = create_node(0);	if(s == NULL)return Faulse;s->data = element;s->prev = p;p->next = s;head->len++;return Sccuess;
}

5.双向链表的头删

定义一个del指针指向首普通节点,将头节点的next指向del->next,判断这个第二个节点是不是NULL,如果是则不需要将del->next->prev指向head,如果不是则需要。

int head_delete(doublelinklist head)
{if(head == NULL || head->len == 0)return Faulse;doublelinklist p = head;doublelinklist del = p->next;p->next = del->next;if(del->next != NULL)del->next->prev = p;free(del);del = NULL;return Sccuess;
}

6.双向链表的尾删

循环找到要删除的节点p,定义一个del指向要删除的节点,p->prev->next指向p->next,释放del就行。

int rear_delete(doublelinklist head)
{	if(head == NULL || head->len == 0)return Faulse;doublelinklist p = head;while(p->next != NULL)p = p->next;doublelinklist del = p;p->prev->next = p->next;free(del);del = NULL;
}

7.双向链表的按位置查找

循环需要的位置次数,每次p下移,找到需要的位置,输出data就行

int position_search(doublelinklist head,int position)
{if(head == NULL || head->len == 0 || position > head->len || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position; i++){p = p->next;}printf("%d\n",p->data);return Sccuess;
}

8.双向链表的按位置删除

找到需要删除的位置的前一个位置p,将del定义为要删除的位置,p的next指向del的next,并判断del是不是最后一位,如果是NULL不需要prev,如果不是,del的next的prev需要指向p。

int position_delete(doublelinklist head,int position)
{if(head == NULL || head->len == 0 || position > head->len || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position-1; i++){p = p->next;}doublelinklist del = p->next;p->next = del->next;if(del->next != NULL)del->next->prev = p;free(del);del = NULL;return Sccuess;
}

9.双向链表的按位置修改

循环找位置p,找到位置修改p->data即可

int position_change(doublelinklist head,int position,datatype element)
{if(head == NULL || head->len == 0 || position > head->len || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position; i++){p = p->next;}p->data = element;return Sccuess;
}

10.双向链表的按位置插入

循环找到要插入的前一个位置p,申请一个新节点s,给s的data赋值,s要插入到p的后面,s的next指向p的next,s的prev指向p,p的next指向s的next,判断要插入的位置是不是在最后一位,如果是则不需要NULL的prev,不是则需要s的下一位的prev指向s。

int position_insert(doublelinklist head,int position,datatype element)
{if(head == NULL || head->len == 0 || position > head->len+1 || position < 1)return Faulse;doublelinklist p = head;for(int i = 0; i < position-1; i++){p = p->next;}doublelinklist s = create_node(0);	if(s == NULL)return Faulse;s->data = element;s->next = p->next;s->prev = p;p->next = s;if(p->next != NULL)p->next->prev = s;return Sccuess;
}

http://www.xdnf.cn/news/16157.html

相关文章:

  • C语言(十)
  • 移动端自动化Appium框架
  • 清除浮动以及原理
  • 2025年6月GESP(C++六级):学习小组
  • wiz2025 挑战赛从 SpringActuator 泄露到 s3 敏感文件获取全解析
  • Linux驱动19 --- FFMPEG
  • 7.3.2 内核内存管理运行机制
  • Lua(迭代器)
  • 现代C++的一般编程规范
  • 论文阅读:《针对多目标优化和应用的 NSGA-II 综述》一些关于优化算法的简介
  • Python生成折线图
  • 二、计算机网络技术——第6章:应用层
  • matrix-breakout-2-morpheus靶场通过
  • 详解FreeRTOS开发过程(五)-- 系统内核控制函数及任务相关API函数
  • 低功耗设计双目协同画面实现光学变焦内带AI模型
  • vs调试C++,无法显示长字符串所有内容
  • 上证50ETF期权的交易时间是什么时候?
  • 模块化商城的快速部署之道:ZKmall开源商城如何让电商功能即插即用
  • rustfs/rustfs基于 Rust 的高性能分布式存储系统
  • 多模态数据处理系统:用AI读PDF的智能助手系统分析
  • 物流仓储自动化升级:Modbus TCP与DeviceNet的协议融合实践
  • EVAL长度限制突破方法
  • java实体类常规校验(字符串不包含空格)
  • mac电脑(m1) - flask断点失效
  • 2025年区块链安全威胁全景:新兴漏洞、攻击向量与防护策略深度解析
  • 【数据结构初阶】--二叉树(二)
  • SAP-MM-采购订单批量创建 excel 版
  • MYOJ_10583:CSP初赛题单7:计算机常识综合练习
  • 人工智能与云计算双轮驱动:元宇宙如何重构全球产业生态
  • linux入门 相关linux系统操作命令(二)--文件管理系统 ubuntu22.04