循环链表

Julia999

引言：对于单链表，由于每个结点只存储了向后的指针，到了尾部标识就停止了向后链的操作。也就是说，按照这样的方式，只能索引后继结点不能索引前驱节点所以，不从头结点出发，就无法访问全部结点
解决方法：只需要将单链表中的终端结点的指针端由空指针改为指向头结点，使形成一个环
注意：这里并不是说循环链表就一定要有一个头结点
其实循环链表和单链表的主要差异就是循环判断的空链表的条件上，原来判断head->next是否为null，现在是head->next是否等于head
初始化循环链表：

1. /*初始化循环链表*/
   
2. void ds_init(node **pNode)
   
3. {
   
4.     int item;
   
5.     node *temp;
   
6.     node *target;
   
7. 
   
8.     printf("输入结点的值，输入0完成初始化\n");
   
9. 
   
10.         while(1)
    
11.         {
    
12.         scanf("%d", &item);
    
13.         fflush(stdin);
    
14. 
    
15.                 if(item == 0)
    
16.             return;
    
17. 
    
18.         if((*pNode) == NULL)
    
19.                 { /*循环链表中只有一个结点*/
    
20.                         *pNode = (node*)malloc(sizeof(struct CLinkList));
    
21.                        
    
22.                         if(!(*pNode))
    
23.                                 exit(0);
    
24.                        
    
25.                         (*pNode)->data = item;
    
26.                         (*pNode)->next = *pNode;
    
27.                 }
    
28.         else
    
29.                 {
    
30.             /*找到next指向第一个结点的结点*/
    
31.             for(target = (*pNode); target->next != (*pNode); target = target->next)
    
32.                                 ;
    
33. 
    
34.             /*生成一个新的结点*/
    
35.             temp = (node *)malloc(sizeof(struct CLinkList));
    
36. 
    
37.                         if(!temp)
    
38.                                 exit(0);
    
39. 
    
40.                         temp->data = item;
    
41.             temp->next = *pNode;
    
42.             target->next = temp;
    
43.         }
    
44.     }
    
45. }

复制代码

链表存储结构的定义

1. /*链表存储结构的定义*/
   
2. typedef struct CLinkList
   
3. {
   
4.     int data;
   
5.     struct CLinkList *next;
   
6. }node;
   
7. 
   
8. /*插入结点*/
   
9. /*参数：链表的第一个结点，插入的位置*/
   
10. void ds_insert(node **pNode , int i)
    
11. {
    
12.     node *temp;
    
13.     node *target;
    
14.     node *p;
    
15.     int item;
    
16.     int j = 1;
    
17. 
    
18.     printf("输入要插入结点的值:");
    
19.     scanf("%d", &item);
    
20. 
    
21.     if(i == 1)
    
22.         { //新插入的结点作为第一个结点
    
23.         temp = (node *)malloc(sizeof(struct CLinkList));
    
24. 
    
25.                 if(!temp)
    
26.             exit(0);
    
27. 
    
28.                 temp->data = item;
    
29. 
    
30.         /*寻找到最后一个结点*/
    
31.         for(target = (*pNode); target->next != (*pNode); target = target->next)
    
32.                         ;
    
33. 
    
34.                 temp->next = (*pNode);
    
35.         target->next = temp;
    
36.         *pNode = temp;
    
37.     }
    
38.     else
    
39.         {
    
40.         target = *pNode;
    
41. 
    
42.                 for( ; j < (i-1); ++j )
    
43.                 {
    
44.                         target = target->next;
    
45.                 }  
    
46.                
    
47.                 // target指向第三个元素的
    
48.                
    
49.                 temp = (node *)malloc(sizeof(struct CLinkList));
    
50. 
    
51.                 if(!temp)
    
52.             exit(0);
    
53. 
    
54.                 temp->data = item;
    
55.                
    
56.         p = target->next;
    
57.         target->next = temp;
    
58.         temp->next = p;
    
59.     }
    
60. }

复制代码

返回链表所在的位置：

1. /*返回结点所在位置*/
   
2. int ds_search(node *pNode, int elem)
   
3. {
   
4.     node *target;
   
5.     int i = 1;
   
6. 
   
7.     for(target = pNode; target->data != elem && target->next != pNode; ++i)
   
8.         {
   
9.                 target = target->next;
   
10.         }
    
11.        
    
12.         if(target->next == pNode) /*表中不存在该元素*/
    
13.         return 0;
    
14.     else
    
15.         return i;
    
16. }

复制代码

删除结点：

1. /*删除结点*/
   
2. void ds_delete(node **pNode, int i)
   
3. {
   
4.     node *target;
   
5.     node *temp;
   
6.     int j = 1;
   
7. 
   
8.     if(i == 1)
   
9.         { //删除的是第一个结点
   
10.         /*找到最后一个结点*/
    
11.         for(target = *pNode; target->next != *pNode;target = target->next)
    
12.                         ;
    
13. 
    
14.                 temp = *pNode;
    
15.         *pNode = (*pNode)->next;
    
16.         target->next = *pNode;
    
17.         free(temp);
    
18.     }
    
19.     else
    
20.         {
    
21.         target = *pNode;
    
22. 
    
23.                 for( ; j < i-1; ++j)
    
24.                 {
    
25.                         target = target->next;
    
26.                 }
    
27.                
    
28.                 temp = target->next;
    
29.         target->next = temp->next;
    
30.         free(temp);
    
31.     }
    
32. }

复制代码