Chinaunix首页 | 论坛 | 博客
  • 博客访问: 34957
  • 博文数量: 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_

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

  5. struct _tag_CircleListNode
  6. {
  7.     CircleListNode* next;
  8. };

  9. CircleList* CircleList_Create();

  10. void CircleList_Destroy(CircleList* list);

  11. void CircleList_Clear(CircleList* list);

  12. int CircleList_Length(CircleList* list);

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

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

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

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

  17. CircleListNode* CircleList_Reset(CircleList* list);

  18. CircleListNode* CircleList_Current(CircleList* list);

  19. CircleListNode* CircleList_Next(CircleList* list);

  20. #endif
//C源文件

点击(此处)折叠或打开

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

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


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

  25.     return ret;
  26. }

  27. /**********************************************/
  28. /**函数名称:CircleList_Dstroy **/
  29. /**入口参数:list **/
  30. /**出口参数:无 **/
  31. /**函数说明:销毁链表 **/
  32. /**********************************************/
  33. void CircleList_Destroy(CircleList* list)
  34. {
  35.     free(list);
  36. }

  37. /**********************************************/
  38. /**函数名称:CircleList_Clear **/
  39. /**入口参数:list **/
  40. /**出口参数:无 **/
  41. /**函数说明:清空链表 **/
  42. /**********************************************/
  43. void CircleList_Clear(CircleList* list)
  44. {
  45.     TCircleList* sList = (TCircleList*)list;//把空类型的list强制转化为TCircleList

  46.     if( sList != NULL )
  47.     {
  48.         sList->length = 0;
  49.         sList->slider = NULL;
  50.         sList->header.next = NULL;
  51.     }
  52. }


  53. /**********************************************/
  54. /**函数名称:CircleList_Length **/
  55. /**入口参数:list **/
  56. /**出口参数:list->Length **/
  57. /**函数说明:计算链表长度 **/
  58. /**********************************************/
  59. int CircleList_Length(CircleList* list)
  60. {
  61.     TCircleList* sList = (TCircleList*)list;
  62.     int ret = 0;

  63.     if( sList != NULL )
  64.     {
  65.         ret = sList->length;
  66.     }
  67.     return ret;
  68. }

  69. /**************************************************/
  70. /**函数名称:CircleList_Insert **/
  71. /**入口参数:list,node,pos **/
  72. /**出口参数:插入成功则返回1,否则返回0 **/
  73. /**函数说明:插入结点进链表,游标指向插入的元素**/
  74. /*************************************************/
  75. int CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
  76. {
  77.     TCircleList* sList = (TCircleList*)list;
  78.     int ret = 1;
  79.     int i;

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

  83.     if( ret )
  84.     {
  85.         CircleListNode* current = (CircleListNode*)sList;
  86.         for(i=0; (i<pos) && (current->next != NULL); i++)
  87.         {
  88.             current = current->next;
  89.         }
  90.         node->next = current->next;
  91.         current->next = node;
  92.     }
  93.     //当插入第一个数据元素的时候,node->next = node;实现循环
  94.     if(sList->length == 0)
  95.     {
  96.         sList->slider = node;
  97.         node->next = node;
  98.     }

  99.     sList->length++;

  100.     return ret;
  101. }


  102. /************************************************/
  103. /**函数名称:CircleList_Get **/
  104. /**入口参数:list,pos **/
  105. /**出口参数:获得成功则返回结点,否则返回NULL**/
  106. /**函数说明:插入结点进链表 **/
  107. /************************************************/
  108. CircleListNode* CircleList_Get(CircleList* list, int pos)
  109. {
  110.     TCircleList* sList = (TCircleList*)list;
  111.     CircleListNode* ret = NULL;
  112.     int i = 0;

  113.     if( (sList != NULL) && (0 <= pos) && (pos <= CircleList_Length(sList)))
  114.     {
  115.         CircleListNode* current = (CircleListNode*)sList;
  116.         for(i=0; i<pos; i++)
  117.         {
  118.             current = current->next;
  119.         }
  120.         ret = current->next;
  121.     }
  122.     return ret;
  123. }


  124. /************************************************/
  125. /**函数名称:CircleList_Delete **/
  126. /**入口参数:list,pos **/
  127. /**出口参数:删除成功则返回结点,否则返回NULL**/
  128. /**函数说明:删除结点 **/
  129. /************************************************/
  130. CircleListNode* CircleList_Delete(CircleList* list, int pos)
  131. {
  132.     TCircleList* sList = (TCircleList*)list;
  133.     CircleListNode* ret = NULL;
  134.     int i = 0;

  135.     if( (sList != NULL) && (0 <= pos) && (pos <= CircleList_Length(sList)))
  136.     {
  137.         CircleListNode* current = (CircleListNode*)sList;
  138.         CircleListNode* first = sList->header.next;
  139.         CircleListNode* last = (CircleListNode*)CircleList_Get(sList, sList->length-1);

  140.         for(i=0; i<pos; i++)
  141.         {
  142.             current = current->next;
  143.         }
  144.         ret = current->next;
  145.         current->next = ret->next;

  146.         sList->length--;

  147.         if(first == ret)
  148.         {
  149.             sList->header.next = ret->next;
  150.             last->next = ret->next;
  151.         }
  152.         if( sList->slider == ret )
  153.         {
  154.             sList->slider = ret->next;
  155.         }

  156.         if( sList->length == 0 )
  157.         {
  158.             sList->header.next = NULL;
  159.             sList->slider = NULL;
  160.         }
  161.     }

  162.     return ret;
  163. }


  164. /************************************************/
  165. /**函数名称:CircleList_DeleteNode **/
  166. /**入口参数:list,node **/
  167. /**出口参数:删除成功则返回结点,否则返回NULL**/
  168. /**函数说明:根据所给的结点删除结点 **/
  169. /************************************************/
  170. CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
  171. {
  172.     TCircleList* sList = (TCircleList*)list;
  173.     CircleListNode* ret = NULL;
  174.     int i;

  175.     if(sList != NULL)
  176.     {
  177.         CircleListNode* current = (CircleListNode*)sList;
  178.         for(i=0; i<sList->length; i++)
  179.         {
  180.             if(current->next == node)
  181.             {
  182.                 ret = current->next;
  183.                 break;
  184.             }
  185.             current = current->next;
  186.         }
  187.         if(ret != NULL)
  188.         {
  189.             CircleList_Delete(sList,i);
  190.         }
  191.     }

  192.     return ret;
  193. }



  194. /************************************************/
  195. /**函数名称:CircleList_Reset **/
  196. /**入口参数:list **/
  197. /**出口参数:重置成功则返回游标,否则返回NULL**/
  198. /**函数说明:重置游标 **/
  199. /************************************************/
  200. CircleListNode* CircleList_Reset(CircleList* list)
  201. {
  202.     TCircleList* sList = (TCircleList*)list;
  203.     CircleListNode* ret = NULL;

  204.     if(sList != NULL)
  205.     {
  206.         sList->slider = sList->header.next;
  207.         ret = sList->slider;
  208.     }
  209.     return NULL;
  210. }


  211. /****************************************************************/
  212. /**函数名称:CircleList_Current **/
  213. /**入口参数:list **/
  214. /**出口参数:取当前游标所在结点成功则返回结点,否则返回NULL **/
  215. /**函数说明:删除结点 **/
  216. /*****************************************************************/
  217. CircleListNode* CircleList_Current(CircleList* list)
  218. {
  219.     TCircleList* sList = (TCircleList*)list;
  220.     CircleListNode* ret = NULL;

  221.     if(sList != NULL)
  222.     {
  223.         ret = sList->slider;
  224.     }
  225.     return ret;
  226. }

  227. /****************************************************/
  228. /**函数名称:CircleList_Delete **/
  229. /**入口参数:list,pos **/
  230. /**出口参数:游标下移成功则返回结点,否则返回NULL**/
  231. /**函数说明:删除结点 **/
  232. /****************************************************/
  233. CircleListNode* CircleList_Next(CircleList* list)
  234. {
  235.     TCircleList* sList = (TCircleList*)list;
  236.     CircleListNode* ret = NULL;

  237.     if(sList != NULL)
  238.     {
  239.         ret = sList->slider;
  240.         sList->slider = ret->next;
  241.     }
  242.     return ret;
  243. }
//测试文件

点击(此处)折叠或打开

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

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

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

  13.     struct value v1;
  14.     struct value v2;
  15.     struct value v3;
  16.     struct value v4;
  17.     struct value v5;
  18.     struct value v6;
  19.     struct value v7;
  20.     struct value v8;
  21.     struct value v9;

  22.     v1.v = 1;
  23.     v2.v = 2;
  24.     v3.v = 3;
  25.     v4.v = 4;
  26.     v5.v = 5;
  27.     v6.v = 6;
  28.     v7.v = 7;
  29.     v8.v = 8;
  30.     v9.v = 9;

  31.     CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
  32.     CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
  33.     CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
  34.     CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
  35.     CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
  36.     CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
  37.     CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
  38.     CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));
  39.     CircleList_Insert(list, (CircleListNode*)&v9, CircleList_Length(list));

  40.     for(i=0; i<CircleList_Length(list); i++)
  41.     {
  42.         struct value* pv = (struct value*)CircleList_Get(list, i);

  43.         printf("%d\t",pv->v);
  44.     }
  45.     printf("\n");

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

  48.     printf("\n");


  49.     while( CircleList_Length(list)>0 )
  50.     {
  51.         struct value* pv = (struct value*)CircleList_Delete(list, 0);
  52.         printf("%d\t",pv->v);
  53.     }
  54.     printf("\n");

  55.     CircleList_Insert(list, (CircleListNode*)&v1, CircleList_Length(list));
  56.     CircleList_Insert(list, (CircleListNode*)&v2, CircleList_Length(list));
  57.     CircleList_Insert(list, (CircleListNode*)&v3, CircleList_Length(list));
  58.     CircleList_Insert(list, (CircleListNode*)&v4, CircleList_Length(list));
  59.     CircleList_Insert(list, (CircleListNode*)&v5, CircleList_Length(list));
  60.     CircleList_Insert(list, (CircleListNode*)&v6, CircleList_Length(list));
  61.     CircleList_Insert(list, (CircleListNode*)&v7, CircleList_Length(list));
  62.     CircleList_Insert(list, (CircleListNode*)&v8, CircleList_Length(list));
  63.     CircleList_Insert(list, (CircleListNode*)&v9, CircleList_Length(list));

  64.     for(i=0; i<3; i++)
  65.     {
  66.         CircleList_Next(list);
  67.     }

  68.     CircleList_Reset(list);
  69.     struct value* pv3 = (struct value*)CircleList_Current(list);
  70.     printf("\n%d\n",pv3->v);
  71.     //CircleList_Next(list);


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


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

阅读(413) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~