论坛 › C\C++交流 › C的链表问题~

lzdingzi 发表于 2013-10-7 23:06:27

C的链表问题~

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

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

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

lzdingzi 发表于 2013-10-8 00:39:03

网络学习 发表于 2013-10-8 00:23 static/image/common/back.gif
如何判断一个单向链表是否存在循环？

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

小亮1201 发表于 2013-10-8 09:45:24

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

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

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 发表于 2013-10-8 15:22:14

tsembrace 发表于 2013-10-8 10:57 static/image/common/back.gif


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

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

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 发表于 2013-10-8 21:41:15

tsembrace 发表于 2013-10-8 15:47 static/image/common/back.gif


非常感谢 ~~~

happyin3 发表于 2013-10-9 13:07:43

学习了。。。。。。

turtlefish 发表于 2013-10-9 13:19:41

学习了，学到了~~

网络学习 发表于 2013-10-10 00:38:17

谢谢 见识了

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

# 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 < a
                        {
                                t = q->data;            // t = a;
                                q->data = p->data;         //a = a;
                                p->data = t;      //a = 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 发表于 2013-10-11 08:49:52

bare 发表于 2013-10-11 08:16 static/image/common/back.gif


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

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

lzdingzi 发表于 2013-10-11 08:49 static/image/common/back.gif
您好~ 感谢写出这么多代码，非常感谢。另外我看这是创建的一个单向并不循环的链表是吧。

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

lzdingzi 发表于 2013-10-11 23:43:48

bare 发表于 2013-10-11 23:06 static/image/common/back.gif
嗯，这两天在学这个，看到你这个问题我就把写的代码复制给你了。希望可以帮到

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

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

bare 发表于 2013-10-11 23:06 static/image/common/back.gif
嗯，这两天在学这个，看到你这个问题我就把写的代码复制给你了。希望可以帮到

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

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

lzdingzi 发表于 2013-10-12 00:00 static/image/common/back.gif
不过这个貌似没有加判断是不是单向循环链表的函数的。是吧？

没有                  

devotedtoc 发表于 2013-10-12 07:32:51

7楼正解......

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

bare 发表于 2013-10-12 01:21 static/image/common/back.gif
没有

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

bare 发表于 2013-10-12 22:41:42

lzdingzi 发表于 2013-10-12 16:36 static/image/common/back.gif
如果我想在你那个单向的链表上修改，修改成一个单向的循环链表，这个我该如何做。想着把那个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;
}

查看完整版本: C的链表问题~