Chinaunix首页 | 论坛 | 博客

特殊借口

首页　| 　博文目录　| 　关于我

特殊借口

  • 博客访问： 251771
  • 博文数量： 52
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 1538
  • 用 户 组： 普通用户
  • 注册时间： 2013-04-24 07:45
个人简介

生活就像海洋，只有意志坚强的人，才能到达彼岸。

文章分类

全部博文（52）

文章存档

2013年（52）

我的朋友
最近访客
推荐博文
相关博文
双向链表的实现（国嵌学习笔记）

分类： C/C++

2013-08-15 18:03:18

1>双向链表的定义

    在单链表的结点中增加一个指向其前驱的的pre指针。

2>双向链表的操作

a、创建链表，b、销毁链表，c、获取链表长度，d、清空链表，e、获取第pos个元素操作，

f、插入元素到位置pos，g、删除位置pos处的元素。

3>双向链表的插入操作

current->next = node;

node->next = next;

next->pre = node;

node->pre = current;

4>双向链表的删除操作

current->next = next;

next-pre = current;


5>双向链表的新操作

    *获取当前游标指向的数据元素

    *将游标重置指向链表中的第一个数据元素

    *将游标移动指向到链表中的下一个数据元素

    *将游标移动指向到链表中的上一个数据元素

    *直接指定删除链表中的某个数据元素

DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

DLinkListNode* DLinkList_Reset(DLinkList* list);

DLinkListNode* DLinkList_Current(DLinkList* list);

DLinkListNode* DLinkList_Next(DLinkList* list);

DLinkListNode* DLinkList_Pre(DLinkList* list);

点击(此处)折叠或打开

  1. /***************************************************************/
  2. /*DLinkList.h*/

  4. #ifndef _DLINKLIST_H_
  5. #define _DLINKLIST_H_

  7. typedef void DLinkList;
  8. typedef struct _tag_DLinkListNode DLinkListNode;
  9. struct _tag_DLinkListNode
  10. {
  11.     DLinkListNode* next;
  12.     DLinkListNode* pre;
  13. };

  15. DLinkList* DLinkList_Create();

  17. void DLinkList_Destroy(DLinkList* list);

  19. void DLinkList_Clear(DLinkList* list);

  21. int DLinkList_Length(DLinkList* list);

  23. int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos);

  25. DLinkListNode* DLinkList_Get(DLinkList* list, int pos);

  27. DLinkListNode* DLinkList_Delete(DLinkList* list, int pos);

  29. DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node);

  31. DLinkListNode* DLinkList_Reset(DLinkList* list);

  33. DLinkListNode* DLinkList_Current(DLinkList* list);

  35. DLinkListNode* DLinkList_Next(DLinkList* list);

  37. DLinkListNode* DLinkList_Pre(DLinkList* list);

  39. #endif

  41. /******************************************************************************/

  43. /*DLinkList.c*/

  45. #include <stdio.h>
  46. #include <malloc.h>
  47. #include "DLinkList.h"

  49. typedef struct _tag_DLinkList
  50. {
  51.     DLinkListNode header;
  52.     DLinkListNode* slider;
  53.     int length;
  54. } TDLinkList;

  56. DLinkList* DLinkList_Create() // O(1)
  57. {
  58.     TDLinkList* ret = (TDLinkList*)malloc(sizeof(TDLinkList));
  59.     
  60.     if( ret != NULL )
  61.     {
  62.         ret->length = 0;
  63.         ret->header.next = NULL;
  64.         ret->header.pre = NULL;
  65.         ret->slider = NULL;
  66.     }
  67.     
  68.     return ret;
  69. }

  71. void DLinkList_Destroy(DLinkList* list) // O(1)
  72. {
  73.     free(list);
  74. }

  76. void DLinkList_Clear(DLinkList* list) // O(1)
  77. {
  78.     TDLinkList* sList = (TDLinkList*)list;
  79.     
  80.     if( sList != NULL )
  81.     {
  82.         sList->length = 0;
  83.         sList->header.next = NULL;
  84.         sList->header.pre = NULL;
  85.         sList->slider = NULL;
  86.     }
  87. }

  89. int DLinkList_Length(DLinkList* list) // O(1)
  90. {
  91.     TDLinkList* sList = (TDLinkList*)list;
  92.     int ret = -1;
  93.     
  94.     if( sList != NULL )
  95.     {
  96.         ret = sList->length;
  97.     }
  98.     
  99.     return ret;
  100. }

  102. int DLinkList_Insert(DLinkList* list, DLinkListNode* node, int pos) // O(n)
  103. {
  104.     TDLinkList* sList = (TDLinkList*)list;
  105.     int ret = (sList != NULL) && (pos >= 0) && (node != NULL);
  106.     int i = 0;
  107.     
  108.     if( ret )
  109.     {
  110.         DLinkListNode* current = (DLinkListNode*)sList;
  111.         DLinkListNode* next = NULL;
  112.         
  113.         for(i=0; (i<pos) && (current->next != NULL); i++)
  114.         {
  115.             current = current->next;
  116.         }
  117.         next = current->next;
  118.         current->next = node;
  119.         node->next = next;
  120.         
  121.         if( next != NULL )
  122.         {
  123.             next->pre = node;    
  124.         }
  125.         
  126.         node->pre = current;
  127.         
  128.         if( sList->length == 0)
  129.         {
  130.             node->pre = NULL;
  131.             sList->slider = node;    
  132.         }
  133.         
  134.         sList->length++;
  135.     }
  136.     
  137.     return ret;
  138. }

  140. DLinkListNode* DLinkList_Get(DLinkList* list, int pos) // O(n)
  141. {
  142.     TDLinkList* sList = (TDLinkList*)list;
  143.     DLinkListNode* ret = NULL;
  144.     int i = 0;
  145.     
  146.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
  147.     {
  148.         DLinkListNode* current = (DLinkListNode*)sList;
  149.         
  150.         for(i=0; i<pos; i++)
  151.         {
  152.             current = current->next;
  153.         }
  154.         
  155.         ret = current->next;
  156.     }
  157.     
  158.     return ret;
  159. }

  161. DLinkListNode* DLinkList_Delete(DLinkList* list, int pos) // O(n)
  162. {
  163.     TDLinkList* sList = (TDLinkList*)list;
  164.     DLinkListNode* ret = NULL;
  165.     int i = 0;
  166.     
  167.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )
  168.     {
  169.         DLinkListNode* current = (DLinkListNode*)sList;
  170.         DLinkListNode* next = NULL;
  171.         
  172.         for(i=0; i<pos; i++)
  173.         {
  174.             current = current->next;
  175.         }
  176.         
  177.         ret = current->next;
  178.         next = ret->next;
  179.         
  180.         current->next = next;
  181.         
  182.         if( next != NULL )
  183.         {
  184.             next->pre = current;
  185.             
  186.             if( current == (DLinkListNode*)sList )
  187.             {
  188.                 next->pre = NULL;    
  189.             }    
  190.         }
  191.         
  192.         if(sList->slider == ret)
  193.         {
  194.             sList->slider = next;    
  195.         }
  196.         
  197.         sList->length--;
  198.     }
  199.     
  200.     return ret;
  201. }
  202. DLinkListNode* DLinkList_DeleteNode(DLinkList* list, DLinkListNode* node)
  203. {
  204.     TDLinkList* sList = (TDLinkList*)list;
  205.     DLinkListNode* ret = NULL;
  206.     int i = 0;
  207.     
  208.     if( sList != NULL)
  209.     {
  210.         DLinkListNode* current = (DLinkListNode*)sList;
  211.         
  212.         for(i=0; i<sList->length; i++)
  213.         {
  214.             if(current->next == node)
  215.             {
  216.                 ret = current->next;
  217.                 break;    
  218.             }    
  219.             
  220.             current = current->next;
  221.         }    
  222.         
  223.         if(ret != NULL)
  224.         {
  225.             DLinkList_Delete(sList,i);    
  226.         }
  227.     }
  228.     
  229.     return ret;
  230. }

  232. DLinkListNode* DLinkList_Reset(DLinkList* list)
  233. {
  234.     TDLinkList* sList = (TDLinkList*)list;
  235.     DLinkListNode* ret = NULL;
  236.     
  237.     if( sList != NULL )
  238.     {
  239.         sList->slider = sList->header.next;
  240.         ret = sList->slider;    
  241.     }
  242.     
  243.     return ret;
  244. }

  246. DLinkListNode* DLinkList_Current(DLinkList* list)
  247. {
  248.     TDLinkList* sList = (TDLinkList*)list;
  249.     DLinkListNode* ret = NULL;
  250.     
  251.     if( sList != NULL )
  252.     {
  253.         ret = sList->slider;    
  254.     }
  255.     
  256.     return ret;
  257. }

  259. DLinkListNode* DLinkList_Next(DLinkList* list)
  260. {
  261.     TDLinkList* sList = (TDLinkList*)list;
  262.     DLinkListNode* ret = NULL;
  263.     
  264.     if( (sList != NULL) && (sList->slider != NULL) )
  265.     {
  266.         ret = sList->slider;
  267.         sList->slider = ret->next;    
  268.     }
  269.     
  270.     return ret;
  271. }

  273. DLinkListNode* DLinkList_Pre(DLinkList* list)
  274. {
  275.     TDLinkList* sList = (TDLinkList*)list;
  276.     DLinkListNode* ret = NULL;
  277.     
  278.     if( (sList != NULL) && (sList->slider != NULL) )
  279.     {
  280.         ret = sList->slider;
  281.         sList->slider = ret->pre;    
  282.     }
  283.     
  284.     return ret;
  285. }

  287. /***************************************************************/
  288. /*main.c*/

  290. #include <stdio.h>
  291. #include <stdlib.h>
  292. #include "DLinkList.h"
  293. /* run this program using the console pauser or add your own getch, system("pause") or input loop */

  295. struct Value
  296. {
  297.     DLinkListNode header;
  298.     int v;
  299. };

  301. int main(int argc, char *argv[])
  302. {
  303.     int i = 0;
  304.     DLinkList* list = DLinkList_Create();
  305.     
  306.     struct Value* pv = NULL;
  307.     struct Value v1;
  308.     struct Value v2;
  309.     struct Value v3;
  310.     struct Value v4;
  311.     struct Value v5;
  312.     
  313.     v1.v = 1;
  314.     v2.v = 2;
  315.     v3.v = 3;
  316.     v4.v = 4;
  317.     v5.v = 5;
  318.     
  319.     DLinkList_Insert(list,(DLinkListNode*)&v1,DLinkList_Length(list));
  320.     DLinkList_Insert(list,(DLinkListNode*)&v2,DLinkList_Length(list));
  321.     DLinkList_Insert(list,(DLinkListNode*)&v3,DLinkList_Length(list));
  322.     DLinkList_Insert(list,(DLinkListNode*)&v4,DLinkList_Length(list));
  323.     DLinkList_Insert(list,(DLinkListNode*)&v5,DLinkList_Length(list));
  324.     
  325.     for(i=0; i<DLinkList_Length(list); i++)
  326.     {
  327.         pv = (struct Value*)DLinkList_Get(list,i);
  328.         
  329.         printf("%d\n", pv->v);    
  330.     }
  331.     
  332.     printf("\n");
  333.     
  334.     DLinkList_Delete(list, DLinkList_Length(list)-1);
  335.     DLinkList_Delete(list,0);
  336.     
  337.     for(i=0; i<DLinkList_Length(list); i++)
  338.     {
  339.         pv = (struct Value*)DLinkList_Next(list);
  340.         
  341.         printf("%d\n", pv->v);    
  342.     }

  344.     printf("\n");
  345.     
  346.     DLinkList_Reset(list);
  347.     DLinkList_Next(list);
  348.     
  349.     pv = (struct Value*)DLinkList_Current(list);
  350.     
  351.     printf("%d\n",pv->v);
  352.     printf("\n");
  353.     
  354.     DLinkList_DeleteNode(list,(DLinkListNode*)pv);
  355.     
  356.     pv = (struct Value*)DLinkList_Current(list);
  357.     
  358.     printf("%d\n",pv->v);
  359.     
  360.     printf("\n");
  361.     
  362.     DLinkList_Pre(list);
  363.     
  364.     pv = (struct Value*)DLinkList_Current(list);
  365.     
  366.     printf("%d\n",pv->v);
  367.     
  368.     DLinkList_Destroy(list);
  369.     
  370.     return 0;
  371. }
双向链表在单链表的基础上增加了指向前驱的指针，功能上双向链表可以完全取代单链表的使用，双向链表的Next，pre和Current操作可

以高效的遍历表中的所有元素
阅读(1699) | 评论(0) | 转发(0) |
0

上一篇：内核开发基础（国嵌学习笔记）

下一篇：栈的定义与实现

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6