`
java-mans
  • 浏览: 11339819 次
文章分类
社区版块
存档分类
最新评论

一步一步写算法(之双向链表)

 
阅读更多

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】


前面的博客我们介绍了单向链表。那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表,主要有下面几个特点:

(1)在数据结构中具有双向指针

(2)插入数据的时候需要考虑前后的方向的操作

(3)同样,删除数据的是有也需要考虑前后方向的操作

那么,一个非循环的双向链表操作应该是怎么样的呢?我们可以自己尝试一下:

(1)定义双向链表的基本结构

typedef struct _DOUBLE_LINK_NODE
{
	int data;
	struct _DOUBLE_LINK_NODE* prev;
	struct _DOUBLE_LINK_NODE* next;
}DOUBLE_LINK_NODE;
(2)创建双向链表节点
DOUBLE_LINK_NODE* create_double_link_node(int value)
{
	DOUBLE_LINK_NODE* pDLinkNode = NULL;
	pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
	assert(NULL != pDLinkNode);

	memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));
	pDLinkNode->data = value;
	return pDLinkNode;
}
(3)删除双向链表

void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)
{
	DOUBLE_LINK_NODE* pNode;
	if(NULL == *pDLinkNode)
		return ;

	pNode = *pDLinkNode;
	*pDLinkNode = pNode->next;
	free(pNode);
	delete_all_double_link_node(pDLinkNode);
}
(4)在双向链表中查找数据

DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data)
{
	DOUBLE_LINK_NODE* pNode = NULL;
	if(NULL == pDLinkNode)
		return NULL;

	pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
	while(NULL != pNode){
		if(data == pNode->data)
			return pNode;
		pNode = pNode ->next;
	}
	
	return NULL;
}
(5)双向链表中插入数据

STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
	DOUBLE_LINK_NODE* pNode;
	DOUBLE_LINK_NODE* pIndex;

	if(NULL == ppDLinkNode)
		return FALSE;

	if(NULL == *ppDLinkNode){
		pNode = create_double_link_node(data);
	    assert(NULL != pNode);
		*ppDLinkNode = pNode;
		(*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;
		return TRUE;
	}

	if(NULL != find_data_in_double_link(*ppDLinkNode, data))
		return FALSE;

	pNode = create_double_link_node(data);
	assert(NULL != pNode);

	pIndex = *ppDLinkNode;
	while(NULL != pIndex->next)
		pIndex = pIndex->next;

	pNode->prev = pIndex;
	pNode->next = pIndex->next;
	pIndex->next = pNode;
	return TRUE;
}
(6)双向链表中删除数据

STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
	DOUBLE_LINK_NODE* pNode;
	if(NULL == ppDLinkNode || NULL == *ppDLinkNode)
		return FALSE;

	pNode = find_data_in_double_link(*ppDLinkNode, data);
	if(NULL == pNode)
		return FALSE;

	if(pNode == *ppDLinkNode){
		if(NULL == (*ppDLinkNode)->next){
			*ppDLinkNode = NULL;
		}else{
			*ppDLinkNode = pNode->next;
			(*ppDLinkNode)->prev = NULL;
		}

	}else{
		if(pNode->next)
		    pNode->next->prev = pNode->prev;
	    pNode->prev->next = pNode->next;
	}

	free(pNode);
	return TRUE;
}
(7)统计双向链表中数据的个数

int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode)
{
	int count = 0;
	DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

	while(NULL != pNode){
		count ++;
		pNode = pNode->next;
	}
	return count;
}
(8)打印双向链表中数据

void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode)
{
	DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

	while(NULL != pNode){
		printf("%d\n", pNode->data);
		pNode = pNode ->next;
	}
}
注意:

今天我们讨论的双向链表是非循环的,大家可以考虑一下如果改成循环双向链表,应该怎么写?如果是有序的循环双向链表,又该怎么写?


【预告: 下面我们讨论的是循环单向链表】


分享到:
评论

相关推荐

    数据结构与算法.xmind

    双向链表 一个节点有两个指针域 自由主题 循环链表 能通过任何一个节点找到其他所有的节点,将两种(双向/单向)链表的最后一个结点指向第一个结点从而实现循环 常见操作 添加数据到...

    基于arm的车载娱乐系统.zip

    音乐播放函数:主要利用递归读取目录把读到的.mp3后缀名的文件的路径名用双向循环链表存放起来,利用madplay相关命令进行播放,暂停等操作。 视频播放函数:主要利用递归读取目录把读到的.mp4或者.avi...

    leetcode题库-algorithm:基于Java和TypeScript的数据结构,LeetCode题解,欢迎star~

    双向链表 二分搜索树 基于二分搜索树的集合 基于链表的集合 基于链表的映射 基于二分搜索树的映射 线段树 字典树 并查集(基于数组索引) 并查集(基于树) 并查集(使用节点size优化) 并查集(使用rank优化) 平衡...

    leetcode中国-Algorithm:力扣&PAT&

    leetcode中国 做过的算法题和一些记录的笔记 nowcoder 牛客网 fudan PAT LeetCode ...和 lc-plug 下是中国站的题目 ...算法: ...算法题笔记 ...算法 ...贪心算法 分治算法 ...通过快慢双指针,一个每次走...双向链表 可以很方面的检索其

    数据结构(C++)有关练习题

    9、 已知f为单链表的表头指针,链表中存储的都是整型数据,试写出实现下列运算的递归算法: a. 求链表中的最大整数; b. 求链表的结点个数; c. 求所有整数的平均数; 告要求: 写出能运行的完整...

    C语言通用范例开发金典.part2.rar

    范例1-52 双向链表元素值的查询 129 ∷相关函数:GetElemP函数 1.3.22 稀疏矩阵的建立 136 范例1-53 稀疏矩阵的建立 136 ∷相关函数:Create函数 1.3.23 稀疏矩阵的删除 138 范例1-54 稀疏矩阵的删除 138 ∷...

    C语言通用范例开发金典.part1.rar

    范例1-52 双向链表元素值的查询 129 ∷相关函数:GetElemP函数 1.3.22 稀疏矩阵的建立 136 范例1-53 稀疏矩阵的建立 136 ∷相关函数:Create函数 1.3.23 稀疏矩阵的删除 138 范例1-54 稀疏矩阵的删除 138 ∷...

    C 开发金典

    范例1-52 双向链表元素值的查询 129 ∷相关函数:GetElemP函数 1.3.22 稀疏矩阵的建立 136 范例1-53 稀疏矩阵的建立 136 ∷相关函数:Create函数 1.3.23 稀疏矩阵的删除 138 范例1-54 稀疏矩阵的删除 138 ∷...

    leetcode不会-Competitive-Programming-Resources:可以帮助您开始/练习竞争性编程的东西

    双向链表: 树木: 图表: Trie(我几乎没有使用过): Ordered_maps/地图: Unordered_maps/hashmaps/dictionary: 订购套装/套装: 无序集/哈希集: Priority_queue/heaps(最小/最大): 下一步应该是掌握 C++ ...

    计算机二级公共基础知识

    这样的表称为双向链表。 在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数据元素的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除,不需要移动链表中的元素。 线性单链表中,HEAD称为头...

    oracle学习文档 笔记 全面 深刻 详细 通俗易懂 doc word格式 清晰 连接字符串

    ORACLE数据库系统是美国ORACLE公司(甲骨文)提供的以分布式数据库为核心的一组软件产品,是目前最流行的客户/服务器(CLIENT/SERVER)或B/S体系结构的数据库之一。  拉里•埃里森  就业前景 从就业与择业的...

Global site tag (gtag.js) - Google Analytics