Chinaunix首页 | 论坛 | 博客

伊宇凉的博客

首页　| 　博文目录　| 　关于我

伊宇凉

  • 博客访问： 36906
  • 博文数量： 19
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 230
  • 用 户 组： 普通用户
  • 注册时间： 2013-10-13 00:47
文章分类

全部博文（19）

文章存档

2014年（6）

2013年（13）

我的朋友
最近访客
推荐博文
相关博文
可复用性的单循环链表

分类： C/C++

2013-12-16 22:49:23

概念
       循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的域指向，整个链表形成一个环。
分类
循环链表

循环链表

（1）单循环链表——在中，将结点的域NULL改为指向表头结点或开始结点即可。
（2）多重链的循环链表——将表中结点链在多个环上。[1]


//头文件

点击(此处)折叠或打开

  1. #ifndef _CIRCLELIST_H_
  2. #define _CIRCLELIST_H_

  4. typedef void CircleList;
  5. typedef struct _tag_CircleListNode CircleListNode;

  7. struct _tag_CircleListNode
  8. {
  9.     CircleListNode* next;
  10. };

  12. CircleList* CircleList_Create();

  14. void CircleList_Destroy(CircleList* list);

  16. void CircleList_Clear(CircleList* list);

  18. int CircleList_Length(CircleList* list);

  20. int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);

  22. CircleListNode* CircleList_Get(CircleList* list, int pos);

  24. CircleListNode* CircleList_Delete(CircleList* list, int pos);

  26. CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);

  28. CircleListNode* CircleList_Reset(CircleList* list);

  30. CircleListNode* CircleList_Current(CircleList* list);

  32. CircleListNode* CircleList_Next(CircleList* list);

  34. #endif
//C源文件

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include "CircleList.h"

  5. typedef struct _tag_CircleList //定义头结点
  6. {
  7.     CircleListNode header; //定义指针指向第一个元素
  8.     CircleListNode* slider; //游标
  9.     int length; //链表长度
  10. }TCircleList;


  13. /**********************************************/
  14. /**函数名称：CircleList_Create **/
  15. /**入口参数：无 **/
  16. /**出口参数：list **/
  17. /**函数说明：创建链表 **/
  18. /**********************************************/
  19. CircleList* CircleList_Create()
  20. {
  21.     TCircleList* ret = (TCircleList*)malloc(sizeof(TCircleList));
  22.     if( ret != NULL )
  23.     {
  24.         ret->header.next = NULL; //创建链表时，头结点的指针域指向NULL
  25.         ret->slider = NULL;
  26.         ret->length = 0;
  27.     }

  29.     return ret;
  30. }

  32. /**********************************************/
  33. /**函数名称：CircleList_Dstroy **/
  34. /**入口参数：list **/
  35. /**出口参数：无 **/
  36. /**函数说明：销毁链表 **/
  37. /**********************************************/
  38. void CircleList_Destroy(CircleList* list)
  39. {
  40.     free(list);
  41. }

  43. /**********************************************/
  44. /**函数名称：CircleList_Clear **/
  45. /**入口参数：list **/
  46. /**出口参数：无 **/
  47. /**函数说明：清空链表 **/
  48. /**********************************************/
  49. void CircleList_Clear(CircleList* list)
  50. {
  51.     TCircleList* sList = (TCircleList*)list;//把空类型的list强制转化为TCircleList

  53.     if( sList != NULL )
  54.     {
  55.         sList->length = 0;
  56.         sList->slider = NULL;
  57.         sList->header.next = NULL;
  58.     }
  59. }


  62. /**********************************************/
  63. /**函数名称：CircleList_Length **/
  64. /**入口参数：list **/
  65. /**出口参数：list->Length **/
  66. /**函数说明：计算链表长度 **/
  67. /**********************************************/
  68. int CircleList_Length(CircleList* list)
  69. {
  70.     TCircleList* sList = (TCircleList*)list;
  71.     int ret = 0;

  73.     if( sList != NULL )
  74.     {
  75.         ret = sList->length;
  76.     }
  77.     return ret;
  78. }

  80. /**************************************************/
  81. /**函数名称：CircleList_Insert **/
  82. /**入口参数：list，node，pos **/
  83. /**出口参数：插入成功则返回1，否则返回0 **/
  84. /**函数说明：插入结点进链表,游标指向插入的元素**/
  85. /*************************************************/
  86. int CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
  87. {
  88.     TCircleList* sList = (TCircleList*)list;
  89.     int ret = 1;
  90.     int i;

  92.     ret = ret && (sList != NULL);
  93.     ret = ret && (0 <= pos) && (node != NULL);
  94.     //因为循环链表是循环的，所以没必要判断插入位置是否超过链表长度

  96.     if( ret )
  97.     {
  98.         CircleListNode* current = (CircleListNode*)sList;
  99.         for(i=0; (i<pos) && (current->next != NULL); i++)
  100.         {
  101.             current = current->next;
  102.         }
  103.         node->next = current->next;
  104.         current->next = node;
  105.     }
  106.     //当插入第一个数据元素的时候，node->next = node;实现循环
  107.     if(sList->length == 0)
  108.     {
  109.         sList->slider = node;
  110.         node->next = node;
  111.     }

  113.     sList->length++;

  115.     return ret;
  116. }


  119. /************************************************/
  120. /**函数名称：CircleList_Get **/
  121. /**入口参数：list，pos **/
  122. /**出口参数：获得成功则返回结点，否则返回NULL**/
  123. /**函数说明：插入结点进链表 **/
  124. /************************************************/
  125. CircleListNode* CircleList_Get(CircleList* list, int pos)
  126. {
  127.     TCircleList* sList = (TCircleList*)list;
  128.     CircleListNode* ret = NULL;
  129.     int i = 0;

  131.     if( (sList != NULL) && (0 <= pos) && (pos <= CircleList_Length(sList)))
  132.     {
  133.         CircleListNode* current = (CircleListNode*)sList;
  134.         for(i=0; i<pos; i++)
  135.         {
  136.             current = current->next;
  137.         }
  138.         ret = current->next;
  139.     }
  140.     return ret;
  141. }


  144. /************************************************/
  145. /**函数名称：CircleList_Delete **/
  146. /**入口参数：list，pos **/
  147. /**出口参数：删除成功则返回结点，否则返回NULL**/
  148. /**函数说明：删除结点 **/
  149. /************************************************/
  150. CircleListNode* CircleList_Delete(CircleList* list, int pos)
  151. {
  152.     TCircleList* sList = (TCircleList*)list;
  153.     CircleListNode* ret = NULL;
  154.     int i = 0;

  156.     if( (sList != NULL) && (0 <= pos) && (pos <= CircleList_Length(sList)))
  157.     {
  158.         CircleListNode* current = (CircleListNode*)sList;
  159.         CircleListNode* first = sList->header.next;
  160.         CircleListNode* last = (CircleListNode*)CircleList_Get(sList, sList->length-1);

  162.         for(i=0; i<pos; i++)
  163.         {
  164.             current = current->next;
  165.         }
  166.         ret = current->next;
  167.         current->next = ret->next;

  169.         sList->length--;

  171.         if(first == ret)
  172.         {
  173.             sList->header.next = ret->next;
  174.             last->next = ret->next;
  175.         }
  176.         if( sList->slider == ret )
  177.         {
  178.             sList->slider = ret->next;
  179.         }

  181.         if( sList->length == 0 )
  182.         {
  183.             sList->header.next = NULL;
  184.             sList->slider = NULL;
  185.         }
  186.     }

  188.     return ret;
  189. }


  192. /************************************************/
  193. /**函数名称：CircleList_DeleteNode **/
  194. /**入口参数：list，node **/
  195. /**出口参数：删除成功则返回结点，否则返回NULL**/
  196. /**函数说明：根据所给的结点删除结点 **/
  197. /************************************************/
  198. CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
  199. {
  200.     TCircleList* sList = (TCircleList*)list;
  201.     CircleListNode* ret = NULL;
  202.     int i;

  204.     if(sList != NULL)
  205.     {
  206.         CircleListNode* current = (CircleListNode*)sList;
  207.         for(i=0; i<sList->length; i++)
  208.         {
  209.             if(current->next == node)
  210.             {
  211.                 ret = current->next;
  212.                 break;
  213.             }
  214.             current = current->next;
  215.         }
  216.         if(ret != NULL)
  217.         {
  218.             CircleList_Delete(sList,i);
  219.         }
  220.     }

  222.     return ret;
  223. }



  227. /************************************************/
  228. /**函数名称：CircleList_Reset **/
  229. /**入口参数：list **/
  230. /**出口参数：重置成功则返回游标，否则返回NULL**/
  231. /**函数说明：重置游标 **/
  232. /************************************************/
  233. CircleListNode* CircleList_Reset(CircleList* list)
  234. {
  235.     TCircleList* sList = (TCircleList*)list;
  236.     CircleListNode* ret = NULL;

  238.     if(sList != NULL)
  239.     {
  240.         sList->slider = sList->header.next;
  241.         ret = sList->slider;
  242.     }
  243.     return NULL;
  244. }


  247. /****************************************************************/
  248. /**函数名称：CircleList_Current **/
  249. /**入口参数：list **/
  250. /**出口参数：取当前游标所在结点成功则返回结点，否则返回NULL **/
  251. /**函数说明：删除结点 **/
  252. /*****************************************************************/
  253. CircleListNode* CircleList_Current(CircleList* list)
  254. {
  255.     TCircleList* sList = (TCircleList*)list;
  256.     CircleListNode* ret = NULL;

  258.     if(sList != NULL)
  259.     {
  260.         ret = sList->slider;
  261.     }
  262.     return ret;
  263. }

  265. /****************************************************/
  266. /**函数名称：CircleList_Delete **/
  267. /**入口参数：list，pos **/
  268. /**出口参数：游标下移成功则返回结点，否则返回NULL**/
  269. /**函数说明：删除结点 **/
  270. /****************************************************/
  271. CircleListNode* CircleList_Next(CircleList* list)
  272. {
  273.     TCircleList* sList = (TCircleList*)list;
  274.     CircleListNode* ret = NULL;

  276.     if(sList != NULL)
  277.     {
  278.         ret = sList->slider;
  279.         sList->slider = ret->next;
  280.     }
  281.     return ret;
  282. }
//测试文件

点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "CircleList.h"

  5. struct value
  6. {
  7.     CircleListNode header;
  8.     int v;
  9. };

  11. int main()
  12. {
  13.     CircleList* list = CircleList_Create();
  14.     int i = 0;

  16.     struct value v1;
  17.     struct value v2;
  18.     struct value v3;
  19.     struct value v4;
  20.     struct value v5;
  21.     struct value v6;
  22.     struct value v7;
  23.     struct value v8;
  24.     struct value v9;

  26.     v1.v = 1;
  27.     v2.v = 2;
  28.     v3.v = 3;
  29.     v4.v = 4;
  30.     v5.v = 5;
  31.     v6.v = 6;
  32.     v7.v = 7;
  33.     v8.v = 8;
  34.     v9.v = 9;

  36.     CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
  37.     CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
  38.     CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
  39.     CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
  40.     CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
  41.     CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
  42.     CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
  43.     CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));
  44.     CircleList_Insert(list, (CircleListNode*)&v9, CircleList_Length(list));

  46.     for(i=0; i<CircleList_Length(list); i++)
  47.     {
  48.         struct value* pv = (struct value*)CircleList_Get(list, i);

  50.         printf("%d\t",pv->v);
  51.     }
  52.     printf("\n");

  54.     struct value* pv1 = (struct value*)CircleList_Current(list);
  55.     printf("\n%d\n",pv1->v);

  57.     printf("\n");


  60.     while( CircleList_Length(list)>0 )
  61.     {
  62.         struct value* pv = (struct value*)CircleList_Delete(list, 0);
  63.         printf("%d\t",pv->v);
  64.     }
  65.     printf("\n");

  67.     CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
  68.     CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
  69.     CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
  70.     CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
  71.     CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
  72.     CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
  73.     CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
  74.     CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));
  75.     CircleList_Insert(list, (CircleListNode*)&v9, CircleList_Length(list));

  77.     for(i=0; i<3; i++)
  78.     {
  79.         CircleList_Next(list);
  80.     }

  82.     CircleList_Reset(list);
  83.     struct value* pv3 = (struct value*)CircleList_Current(list);
  84.     printf("\n%d\n",pv3->v);
  85.     //CircleList_Next(list);


  88.     struct value* pv2 = (struct value*)CircleList_DeleteNode(list, (CircleListNode*)&v9);
  89.     printf("\n%d\n",pv2->v);


  92.     CircleList_Destroy(list);
  93.     return 0;
  94. }
注意：
①循环链表中没有NULL。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p->next是否为空，而是判别它们是否等于某一指定，如头指针或尾指针等。
②在中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。

阅读(452) | 评论(0) | 转发(0) |
0

上一篇：可复用性的链式存储结构的线性表的实现---单链表

下一篇：MFC中在图片控件中动态添加组合框

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

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

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

16024965号-6