C的链表问题~

lzdingzi

如何判断一个单向链表是否存在循环？
需要用算法来实现判断。

网络学习

如何判断一个单向链表是否存在循环？

lzdingzi

网络学习 发表于 2013-10-8 00:23

                               
登录/注册后可看大图

如何判断一个单向链表是否存在循环？

是的~ 就是一个单向的链接，可能最后一个结点或者是中间的结点有指向前面的，或最后一个结点的尾指针又会指到第一个结点的头指针那种情况，如果用算法去判断。

小亮1201

额.......那不成了单循环链表了吗？？？

tsembrace

1. int ListIsCycle(Node *head){
   
2.      Node *p=head->next;
   
3.      Node *q=NULL;
   
4.      int i,k=0;
   
5.      while(p){
   
6.           k++;
   
7.           for(i=0,q=head;i<k;i++,q=q->next){
   
8.                   if(q==p)
   
9.                          return 1;
   
10.           }
    
11.      p=p->next;
    
12.      }
    
13.      return 0;
    
14. }
    
15. 
    
16. 
    

复制代码

lzdingzi

tsembrace 发表于 2013-10-8 10:57

                               
登录/注册后可看大图

您好~ 可以跟我讲讲那个算法吗？

tsembrace

1. 
   
2. int ListIsCycle(Node *head){
   
3. Node *p=head->next;          //p设置为依序next的游标结点
   
4. Node *q=NULL;                    //设置q为遍历查找的游标结点int i,k=0;
   
5. while(p){                               //若p为NULL，则非单向循环
   
6. k++;                                      //每次next,计数器+1
   
7. for(i=0,q=head;i<k;i++,q=q->next){         //使用q遍历查找
   
8. if(q==p)
   
9. return 1;                       //相等则为循环
   
10. }
    
11. p=p->next;               
    
12. }                              //对单向链表，若不循环，则必然会退出while
    
13. return 0;                 //退出后则非循环
    
14. }

复制代码

lzdingzi

tsembrace 发表于 2013-10-8 15:47

                               
登录/注册后可看大图

非常感谢 ~~~

happyin3

学习了。。。。。。

turtlefish

学习了，学到了~~

网络学习

谢谢 见识了

bare

1. # include <stdio.h>
   
2. # include <malloc.h>
   
3. typedef struct node
   
4. {
   
5.         int data;
   
6.         struct node * pnext;   
   
7. } NODE, * PNODE;
   
8. 
   
9. PNODE build_list()
   
10. {
    
11.         int len;
    
12.         int val;
    
13.         PNODE phead = (PNODE)malloc(sizeof(NODE));//构造头节点
    
14.         PNODE tail = phead; //构造永远指向尾节点的tail指针
    
15.     tail->pnext = NULL;//把头节点的指针域清空
    
16.     printf("请输入节点个数：");
    
17.         scanf("%d",&len);
    
18.         for (int i = 0; i < len; ++i)
    
19.         {
    
20.                 PNODE pnew = (PNODE)malloc(sizeof(NODE));
    
21.                 printf("请输入第%d个节点的值：",i + 1);
    
22.                 scanf("%d",&val);
    
23.                 pnew->data = val;
    
24.                 tail->pnext = pnew;
    
25.                 tail = pnew;
    
26.                 tail->pnext = NULL;               
    
27.         }
    
28.         return phead;
    
29. }
    
30. void traverse_list(PNODE phead)  
    
31. {
    
32.         PNODE p;
    
33.         p = phead;
    
34.         while (p->pnext != NULL)
    
35.         {
    
36.                 p = p->pnext;
    
37.                 printf("%d  ",p->data);
    
38.         }
    
39.         printf("\n");
    
40.         return ;
    
41. }
    
42. int long_list(PNODE phead)
    
43. {
    
44.         PNODE p = phead->pnext;
    
45.         int len = 0;
    
46.         while (NULL != p)
    
47.         {
    
48.                 len ++;
    
49.                 p = p->pnext;
    
50.         }
    
51.         return len;
    
52. }
    
53. void sort_list(PNODE phead,int len) //排序
    
54. {
    
55.         int i,j,t;
    
56.         PNODE p,q ;
    
57.         for (i = 0,p = phead->pnext; i < len-1; ++i,p = p->pnext)
    
58.         {
    
59.                 for (j = i + 1,q = p->pnext; j < len; ++j,q = q->pnext)
    
60.                 {
    
61.                         if (q->data < p->data) //a[j] < a[j + 1]
    
62.                         {
    
63.                                 t = q->data;              // t = a[j];
    
64.                                 q->data = p->data;         //a[j] = a[j+1];
    
65.                                 p->data = t;      //a[j+1] = t;
    
66.                         }
    
67.                 }
    
68.         }
    
69. 
    
70. }
    
71. int main(void)
    
72. {
    
73.         PNODE phead ;       
    
74.         phead = build_list();
    
75.         traverse_list(phead);
    
76.         int len = long_list(phead);
    
77. 
    
78.     sort_list(phead,len);
    
79.         traverse_list(phead);
    
80.         return 0;
    
81. }

复制代码

lzdingzi

bare 发表于 2013-10-11 08:16

                               
登录/注册后可看大图

您好~ 感谢写出这么多代码，非常感谢。另外我看这是创建的一个单向并不循环的链表是吧。

bare

lzdingzi 发表于 2013-10-11 08:49

                               
登录/注册后可看大图

您好~ 感谢写出这么多代码，非常感谢。另外我看这是创建的一个单向并不循环的链表是吧。

嗯，这两天在学这个，看到你这个问题我就把写的代码复制给你了。希望可以帮到

lzdingzi

bare 发表于 2013-10-11 23:06

                               
登录/注册后可看大图

嗯，这两天在学这个，看到你这个问题我就把写的代码复制给你了。希望可以帮到

非常感谢～。这个非常用哦~

lzdingzi

bare 发表于 2013-10-11 23:06

                               
登录/注册后可看大图

嗯，这两天在学这个，看到你这个问题我就把写的代码复制给你了。希望可以帮到

不过这个貌似没有加判断是不是单向循环链表的函数的。是吧？

bare

lzdingzi 发表于 2013-10-12 00:00

                               
登录/注册后可看大图

不过这个貌似没有加判断是不是单向循环链表的函数的。是吧？

没有                  

devotedtoc

7楼正解......

lzdingzi

bare 发表于 2013-10-12 01:21

                               
登录/注册后可看大图

没有

如果我想在你那个单向的链表上修改，修改成一个单向的循环链表，这个我该如何做。想着把那个pnext不指向NULL,但尝试了几遍，没弄成功，bare有空的话能否给一个示例呢？

bare

lzdingzi 发表于 2013-10-12 16:36

                               
登录/注册后可看大图

如果我想在你那个单向的链表上修改，修改成一个单向的循环链表，这个我该如何做。想着把那个pnext不指向N ...

1. # include <stdio.h>
   
2. # include <malloc.h>
   
3. # include <stdlib.h>
   
4. typedef struct node
   
5. {
   
6.         int data;
   
7.         struct node * pnext;
   
8. } NODE, * PNODE;
   
9. 
   
10. PNODE create_list(void)
    
11. {
    
12.         int len;
    
13.         int val;
    
14.         PNODE phead = (PNODE)malloc(sizeof(NODE));
    
15.         PNODE tail = phead;
    
16.         tail->pnext = NULL;
    
17.     printf("请输入节点数:");
    
18.         scanf("%d",&len);
    
19.         for (int i = 0; i < len; ++i)
    
20.         {
    
21.                 PNODE pnew = (PNODE)malloc(sizeof(NODE));
    
22.                 printf("请输入第%d个节点的值：",i+1);
    
23.                 scanf("%d",&val);
    
24.                 pnew->data = val;
    
25.                 tail->pnext = pnew;
    
26.                 tail = pnew;
    
27. 
    
28.                 tail->pnext = phead->pnext;                //把最后节点的指针域指向第一个有效节点就是循环链表
    
29.                
    
30.         }
    
31.        
    
32.         return phead;
    
33. }
    
34. void traverse_list(PNODE phead)
    
35. {
    
36.         PNODE p = phead;
    
37.         while ( p->pnext != NULL)
    
38.         {
    
39.                 p = p->pnext;
    
40.                 printf("%d  ",p->data);
    
41.                
    
42.         }
    
43.         printf("\n");
    
44.         return ;
    
45. }
    
46. 
    
47. int main(void)
    
48. 
    
49. {
    
50.         int length;
    
51.         PNODE phead = NULL;
    
52.         phead = create_list();
    
53.         traverse_list(phead);
    
54. //        length = length_list(phead);
    
55.         //sort_list(phead,length);
    
56. //        insert_list(phead,3,88);
    
57.         traverse_list(phead);
    
58.         return 0;
    
59. }
    

复制代码