C的链表问题~

lzdingzi

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

网络学习

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

lzdingzi

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

                               
登录/注册后可看大图

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

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

小亮1201

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

tsembrace

int ListIsCycle(Node *head){
     Node *p=head->next;
     Node *q=NULL;
     int i,k=0;
     while(p){
          k++;
          for(i=0,q=head;i<k;i++,q=q->next){
                  if(q==p)
                         return 1;
          }
     p=p->next;
     }
     return 0;
}

lzdingzi

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

                               
登录/注册后可看大图

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

tsembrace

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

lzdingzi

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

                               
登录/注册后可看大图

非常感谢 ~~~

happyin3

学习了。。。。。。

turtlefish

学习了，学到了~~

网络学习

谢谢 见识了

bare

# include <stdio.h>
# include <malloc.h>
typedef struct node
{
        int data;
        struct node * pnext;   
} NODE, * PNODE;

PNODE build_list()
{
        int len;
        int val;
        PNODE phead = (PNODE)malloc(sizeof(NODE));//构造头节点
        PNODE tail = phead; //构造永远指向尾节点的tail指针
    tail->pnext = NULL;//把头节点的指针域清空
    printf("请输入节点个数：");
        scanf("%d",&len);
        for (int i = 0; i < len; ++i)
        {
                PNODE pnew = (PNODE)malloc(sizeof(NODE));
                printf("请输入第%d个节点的值：",i + 1);
                scanf("%d",&val);
                pnew->data = val;
                tail->pnext = pnew;
                tail = pnew;
                tail->pnext = NULL;                
        }
        return phead;
}
void traverse_list(PNODE phead)  
{
        PNODE p;
        p = phead;
        while (p->pnext != NULL)
        {
                p = p->pnext;
                printf("%d  ",p->data);
        }
        printf("\n");
        return ;
}
int long_list(PNODE phead)
{
        PNODE p = phead->pnext;
        int len = 0;
        while (NULL != p)
        {
                len ++;
                p = p->pnext;
        }
        return len;
}
void sort_list(PNODE phead,int len) //排序
{
        int i,j,t;
        PNODE p,q ;
        for (i = 0,p = phead->pnext; i < len-1; ++i,p = p->pnext)
        {
                for (j = i + 1,q = p->pnext; j < len; ++j,q = q->pnext) 
                {
                        if (q->data < p->data) //a[j] < a[j + 1]
                        {
                                t = q->data;              // t = a[j];
                                q->data = p->data;         //a[j] = a[j+1];
                                p->data = t;      //a[j+1] = t;
                        }
                }
        }

}
int main(void)
{
        PNODE phead ;        
        phead = build_list();
        traverse_list(phead);
        int len = long_list(phead);

    sort_list(phead,len);
        traverse_list(phead);
        return 0;
}

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 ...

# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
typedef struct node
{
        int data;
        struct node * pnext;
} NODE, * PNODE;

PNODE create_list(void)
{
        int len;
        int val;
        PNODE phead = (PNODE)malloc(sizeof(NODE));
        PNODE tail = phead;
        tail->pnext = NULL;
    printf("请输入节点数:");
        scanf("%d",&len);
        for (int i = 0; i < len; ++i)
        {
                PNODE pnew = (PNODE)malloc(sizeof(NODE));
                printf("请输入第%d个节点的值：",i+1);
                scanf("%d",&val);
                pnew->data = val;
                tail->pnext = pnew;
                tail = pnew;

                tail->pnext = phead->pnext;                //把最后节点的指针域指向第一个有效节点就是循环链表
                
        }
        
        return phead;
}
void traverse_list(PNODE phead)
{
        PNODE p = phead;
        while ( p->pnext != NULL)
        {
                p = p->pnext;
                printf("%d  ",p->data);
                
        }
        printf("\n");
        return ;
}

int main(void)

{
        int length;
        PNODE phead = NULL;
        phead = create_list();
        traverse_list(phead);
//        length = length_list(phead);
        //sort_list(phead,length);
//        insert_list(phead,3,88);
        traverse_list(phead);
        return 0;
}