首页 > 代码库 > 一步一步写算法(之双向链表)
一步一步写算法(之双向链表)
原文: 一步一步写算法(之双向链表)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱: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 = http://www.mamicode.com/value;> (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 =http://www.mamicode.com/= pNode->data)> (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; }}注意:今天我们讨论的双向链表是非循环的,大家可以考虑一下如果改成循环双向链表,应该怎么写?如果是有序的循环双向链表,又该怎么写?
【预告: 下面我们讨论的是循环单向链表】
一步一步写算法(之双向链表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。