首页 > 编程语言 >数据结构与算法——双链表的实现

数据结构与算法——双链表的实现

时间：2024-10-24 14:45:45浏览次数：9  
标签：node 结点 ListNode struct int next 算法 双链 数据结构

上次学习了单链表，这次来学习双链表。二者之间的区别是，单链表中的每个结点只存有后继结点的地址，而双链表中则存了两个地址，一个是前驱结点的地址，一个是后继结点的地址。

结构体

struct ListNode{
	int element;                       //数据域
	struct ListNode *next;		       //后继结点的地址
	struct ListNode *prev;             //前驱结点的地址
};

这里的结构体中存有了两个链表结点ListNode类型的指针，一个指向前驱结点，一个指向后继结点。头结点的prev置空，尾结点的next置空。

初始化链表

void InitListNode(struct ListNode *head){
	head->next=NULL;
	head->prev=NULL;
}

初始化链表就是对现有的头结点进行准备操作。头结点的数据域我们一般不会用到，所以可以不用管数据域。将next和prev置空，后续需要插入元素时，再对next进行操作。

插入操作

int InsertListNode(struct ListNode *head,int element,int index){
	if (index<1) return 0;           //判断插入位置是否合法
	struct ListNode *p=head;      
	while(index>1){                 //循环操作将指针移至待插入位置的前驱结点
		p=p->next;
		if (p==NULL) return 0;
		index--;
	}
	struct ListNode *node =malloc(sizeof(struct ListNode));  //分配新结点的内存空间
	if (node==NULL) return 0;         //判断空间是否分配成功
	node->element=element;
	if (p->next==NULL){              //第一种情况，插入在链表尾端
		p->next=node;                
		node->prev=p;
		node->next=NULL;
	}else{                           //第二种情况，插入不在尾端
		node->prev=p;
		node->next=p->next;
		p->next=node;
		node->next->prev=node;
	}
	return 1;
}

插入操作中，与单链表不同的是，我按插入位置是否在链表尾端分成了两种情况来讨论，这样便于理解。
第一种情况，插入位置在尾端，当指针通过循环到达指定位置的前驱结点时，因为下一个结点为空，也就意味着当前结点时尾结点，在此节点后再插入结点就是新的尾结点，而当前结点p就是待插入结点的前驱结点。这种情况逻辑上较为简单，只用将当前结点的next连向待插入结点，然后将新的尾结点的prev指向前驱结点，next置空。
第二种情况，插入位置不在尾端，循环结束后，如果下一结点非空，就代表当前结点不是尾结点，这时的p是待插入结点的前驱结点。这种情况稍微复杂一点，需要反复理解。第一步，先将待插入结点的next和prev分别指向p和p的后继结点。第二步，将p的next指向新的node结点，再将node的后继结点的prev指向node，这里注意node的后继结点的寻找方法，需要先用刚刚第一步中的node->next来找到后继结点，因为当p->next改变，不再指向这个结点时，现在只有node->next指向该结点，否则通过其它结点无法找到该结点，这里注意理解。
这里还需要注意的是，第一步和第二步的顺序不能颠倒。如果先操作第二步，将会出现的问题是，node->prev和node->next找不到前后两段需要连接的链表。

删除操作

int DeleteListNode(struct ListNode *head,int index){
	struct ListNode *p=head;
	if (index<1) return 0;                
	while(index>1){           //循环操作找到前驱结点
		p=p->next;
		if(p==NULL) return 0;
		index--;
	}
	if(p->next->next){            //需要删除的结点不是尾结点
		struct ListNode *q=p->next;
		p->next=p->next->next;
		p->next->prev=p;	
		free(q);
	}else{                      //需要删除的结点是尾结点
		struct ListNode *q=p->next;
		p->next=NULL;
		q->prev=NULL;
		free(q);
	}
	return 0;
}

删除操作为了便于理解，也按照是否为尾结点分成了两种情况。第一种情况，因为p是前驱结点，所以p->next是需要删除的结点，而判断p->next->next则是看需要删除的结点是否有后继结点，如果p->next->next存在，说明需要删除的结点后面仍存在结点，所以需要删除的结点不是尾结点，否则是尾结点。
当不是尾结点时，用一个新的指针指向需要删除的结点，否则当链表的指针跳过该结点连接后，会找不到该节点。当该结点是尾结点时，用一个新的指针标记后，直接将前驱结点的next置空即可。两种情况的最后，都需要使用free()函数释放被删除结点的内存，完成删除。

获取操作

int GetListNode(struct ListNode *head,int index){
	if(index<1) return 0;
	struct ListNode *p=head;
	while (index>1){
		p=p->next;
		index--;
	}
	return p->next->element;
}

这里单链表一样，通过循环操作，将指针移到前一个结点，返回该结点的后继结点的数据域。

查找操作

int FindListNode(struct ListNode *head,int target){
	struct ListNode *p=head;
	int i=0;
	while(p->next){
		p=p->next;
		i++;
		if(p->element==target) return i; 
	}
	return 0;
}

通过循环，遍历链表上的每一个结点，比较数据域和待查找元素，如果相等，返回该结点的位序，如果循环结束，还没有找到，那就返回错误信息0，代表未找到该元素。

获取链表长度

int ListNodeSize(struct ListNode *head){
	struct ListNode *p=head;
	int i=0;
	while(p->next){
		p=p->next;
		i++;
	}
	return i;
}

通过循环，遍历链表元素，每遍历一个，计数器自增一次，最后计数器计的数值就是链表长度，直接返回计数器就可以。

打印链表

void PrintListNode(struct ListNode *head){
	struct ListNode *p=head;
	while(p->next){
		p=p->next;
		printf("%d ",p->element);
	}
	printf("\n");
}

同样，为了方便查看链表情况，我们编写此函数来从头打印链表的每一个元素。

完整代码

#include <stdio.h>
#include <stdlib.h>

struct ListNode{
	int element;
	struct ListNode *next;
	struct ListNode *prev;
};

void InitListNode(struct ListNode *head){
	head->next=NULL;
	head->prev=NULL;
}

int InsertListNode(struct ListNode *head,int element,int index){
	if (index<1) return 0;
	struct ListNode *p=head;
	while(index>1){
		p=p->next;
		if (p==NULL) return 0;
		index--;
	}
	struct ListNode *node =malloc(sizeof(struct ListNode));
	if (node==NULL) return 0;
	node->element=element;
	if (p->next==NULL){
		p->next=node;
		node->prev=p;
		node->next=NULL;
	}else{
		p->next->prev=node;
		node->next=p->next;
		p->next=node;
		node->prev=p;
	}
	return 1;
}

int DeleteListNode(struct ListNode *head,int index){
	struct ListNode *p=head;
	if (index<1) return 0;
	while(index>1){
		p=p->next;
		if(p==NULL) return 0;
		index--;
	}
	
	if(p->next->next){
		struct ListNode *q=p->next;
		p->next=p->next->next;
		p->next->prev=p;	
		free(q);
	}else{
		struct ListNode *q=p->next;
		p->next=NULL;
		q->prev=NULL;
		free(q);
	}
	return 0;
}

int GetListNode(struct ListNode *head,int index){
	if(index<1) return 0;
	struct ListNode *p=head;
	while (index>1){
		p=p->next;
		index--;
	}
	return p->next->element;
}

int FindListNode(struct ListNode *head,int target){
	struct ListNode *p=head;
	int i=0;
	while(p->next){
		p=p->next;
		i++;
		if(p->element==target) return i; 
	}
	return 0;
}

int ListNodeSize(struct ListNode *head){
	struct ListNode *p=head;
	int i=0;
	while(p->next){
		p=p->next;
		i++;
	}
	return i;
}


void PrintListNode(struct ListNode *head){
	struct ListNode *p=head;
	while(p->next){
		p=p->next;
		printf("%d ",p->element);
	}
	printf("\n");
}


int main(){
	...
	return 0;
}

标签：node,结点,ListNode,struct,int,next,算法,双链,数据结构
From： https://blog.csdn.net/messcodeab/article/details/143207818

相关文章

  • 基于Fluent和深度学习算法驱动的流体力学计算与应用
    机器学习与流体力学入门一、流体力学基础理论与编程实战1、流体力学的发展概述2、不可压缩流体力学的基本方程3、偏微分方程数值求解介绍4、傅里叶变换和流体的尺度分析5、伪谱法求解不可压缩流体力学方程案例实践：1、Matlab编程实现有限差分（案例数据与代码提供给学员）2......
  • python C3算法
    PythonMROC3算法是python当中计算类继承顺序的一个算法，从python2.3以后就一直使用此算法了。c3linearization算法称为c3线性化算法C3算法原理首先定义几个符号的意义：符号意义L针对一个类进行解析用L进行表示，例如L(A)表示对类A进行解析merge合并操作的一个函......
  • 栈的理解及相关算法
    一、栈的基础概念1、栈的定义栈（Stack）：是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。栈顶（Top）：线性表允许进行插入删除的那一端。栈底（Bottom）：固定的，不允许进行插入和删除的另一端。空栈：不含任何元素的空表。栈又......
  • 单向循环链表的实现及相关算法
    1.单向循环链表特点：每一个节点除了数据域，还有一个next指针域指向下一个节点(存储了下一个节点的地址)，末尾节点的指针域指向了头节点1.1实现过程1.1.1、构建结点structNode{ Node(intvalue=0): val(value), next(nullptr) {} intval; Node*next;};1......
  • C#常见的四种经典查找算法
    前言在编程领域，数据结构与算法是构建高效、可靠和可扩展软件系统的基石。它们对于提升程序性能、优化资源利用以及解决复杂问题具有至关重要的作用。今天大姚给大家分享四种C#中常见的经典查找算法。C#数据结构与算法实战入门指南：https://mp.weixin.qq.com/s/XPRmwWmoZa4zq29K......
  • 数据结构懒标记时间戳差异问题
    对于数据结构打lazytag后节点时空不统一问题的解决可以看看之前写的一篇文章线段树初步理解，里头初步介绍了懒标记的作用与使用懒标记所带来的时空不统一的问题。实际上是可以将懒标记拓展到其他数据结构上的。就以经典的毛毛虫链剖分举例子，就是现在我要给树上的与给定......
  • 代码随想录算法训练营第九天|leetcode151.翻转字符串里的单词、卡码网55.右旋字符串
    1leetcode151.翻转字符串里的单词题目链接：151.反转字符串中的单词-力扣（LeetCode）文章链接：代码随想录视频链接：字符串复杂操作拿捏了！|LeetCode:151.翻转字符串里的单词_哔哩哔哩_bilibili自己的思路：直接将空格去掉，然后分割字符串为列表，在列表中进行翻转，不在字符串内部操作，......
  • 烟火检测视频分析网关算法定制烟火识别技术在沿街商铺消防安全管理中的应用
    在沿街商铺的消防安全管理中，烟火检测视频分析网关算法的应用显得尤为重要。随着城市化进程的加快，沿街商铺数量激增，这些商铺在为居民生活带来便利的同时，也因店主安全意识不足、消防管理松散等问题，成为火灾隐患的高发区。因此，采用智能化的烟火识别技术，对于提升消防安全管理水平、预......
  • Photoshop图像算法（四）（代码在每个原理后面）
    色彩均衡化色彩均衡化（或称为直方图均衡化）是一种图像处理技术，目的是改善图像的对比度，使图像中的细节更加明显。它通过重新分配颜色通道的像素值，使得图像的直方图分布更均匀。以下是其基本原理：原理直方图计算：首先计算图像的颜色直方图，即统计每个像素值出现的频率。对于每个......
  • 局部路径规划(Local planning)算法之——TEB轨迹规划
    1TEB算法原理TEB全程为TimeElasticBand(时间弹力带)，通过对给定的全局轨迹进行修正，从而优化机器人的局部运动轨迹。他是常用的局部路径规划方法之一。TEB是基于图优化的方法，以g2o优化框架实现，它以机器人在各个离散时间的位姿和离散时刻之间的时间间隔为顶点，通过多目标优化，包括......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99