舞蹈《我的头我的肩》:一步一步写算法(之双向链表)
来源:百度文库 编辑:偶看新闻 时间:2024/03/29 06:48:55
一步一步写算法(之双向链表)
分类: 数据结构和算法 2011-10-07 20:03 677人阅读 评论(4) 收藏 举报【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
前面的博客我们介绍了单向链表。那么我们今天介绍的双向链表,顾名思义,就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表,主要有下面几个特点:
(1)在数据结构中具有双向指针
(2)插入数据的时候需要考虑前后的方向的操作
(3)同样,删除数据的是有也需要考虑前后方向的操作
那么,一个非循环的双向链表操作应该是怎么样的呢?我们可以自己尝试一下:
(1)定义双向链表的基本结构
view plaincopy to clipboardprint?
- typedef struct _DOUBLE_LINK_NODE
- {
- int data;
- struct _DOUBLE_LINK_NODE* prev;
- struct _DOUBLE_LINK_NODE* next;
- }DOUBLE_LINK_NODE;
- 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;
- }
view plaincopy to clipboardprint?
- 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);
- }
view plaincopy to clipboardprint?
- 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;
- }
view plaincopy to clipboardprint?
- 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;
- }
view plaincopy to clipboardprint?
- 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;
- }
view plaincopy to clipboardprint?
- 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;
- }
view plaincopy to clipboardprint?
- 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;
- }
- }
今天我们讨论的双向链表是非循环的,大家可以考虑一下如果改成循环双向链表,应该怎么写?如果是有序的循环双向链表,又该怎么写?
【预告: 下面我们讨论的是循环单向链表】
谁知道..用C语言描述双向链表的插入的算法
C++ 双向链表
链表 双向链表
解释下java中的双向链表
光纤通信之单纤双向原理
将单向循环链表改成双向链表
数据结构中双向循环链表的ADT表示
链表综合算法设计
设计一个用链表表示的简单选择排序的算法,并实现之(试验报告)
做一个双向连接表
怎样才能把算法写好啊?
写者问题的算法
如何一步一步的提高写公文材料的水平?
链表的冒泡排序算法
把一数学表达式原序列存放在双向链表的左链中,把原序列从小到大的顺序存放在双向链表的右链中
数据结构中单链表、循环链表、双向链表的特点是什么?
帮忙做道C语言的题:双向链表的排序
c语言编程,双向链表,要求建立,插入删除,排序,放学生的学号,成绩
十亿火急,给个C语言双向链表排序流程图!!!!!!!!!!!!
双向推荐表掉了该怎么办
中考语文说明中双向细目表
程序调度(时间片轮转算法)用C语言程序怎么写啊??谢谢
程序调度(时间片轮转算法)用C语言程序怎么写啊??谢谢
程序调度(时间片轮转算法)用C语言程序怎么写啊??谢谢