1

我正在尝试实现一个程序来查找循环链表的起始节点。我的代码是-

struct node
{
char data;
struct node *link;
} ;

char FindStartNode(struct node **q)
{
    struct node *r,*t;
 r = *q; 
 t = *q;
 while(t->link != NULL)
 {
     r = r->link;
     t = t->link->link;
     if(r == t)
     {
         break;
     }
 }
 if(t == NULL )
     return NULL;
 r = *q;
 while(r != t)
 {
     t = t->link;
     r = r->link;
 }
 return t->data;
}


int main()
{
struct node *p;
p = NULL;
char num;
Append(&p,'A');
Append(&p,'B');
Append(&p,'C');
Append(&p,'D');
Append(&p,'E');
Append(&p,'C');
Display(p);
 num = FindStartNode(&p);
printf("\nStarting node of the cycle linked list is:- %c",num);
_getch();
return 0;
}


int Append(struct node **q, char data)
{
struct node *r,*t;
r = (struct node *)malloc(sizeof(struct node));
r->data = data;
r->link = NULL;
if(*q == NULL)
    *q = r;
else
{
  t = *q;
  while(t->link != NULL)
  {
      t = t->link;
  }
  t->link = r;
    }
return 0;
}
int Display(struct node *q)
{
while(q != NULL)
{
    printf("%c\t",q->data);
    q = q->link;
}
return 0;
}

这是我的代码。我在 return t->data 部分没有得到任何值，或者我无法找到循环墨水列表的起始节点。有帮助吗？

4

2 回答 2

3 
 t = t->link->link; // t->link can be null 
   //so t = t->link->link can be a crash or illegal reference

将循环更改为：

 while(t != NULL)
 {
     r = r->link;
     t = t->link;
     if(t == NULL)
       break; // or return no circle
     else t = t->link;
     if(r == t)
     {
         break;
     }
 }

我已经浏览了你的代码。与这里的算法讨论相比，它似乎还可以。但是您正在返回一个char为什么不返回一个指针，以便您可以检查它是否为 NULL。如果它不为空，则发出 pt->tada。这更有意义。

我检查了你的代码，似乎你没有在Append(). 我在下面为您提供了一个有效的实现。看看我是如何修改的Append()

#include <stdio.h>
#include <stdlib.h>

struct node
{
char data;
struct node *link;
} ;

char FindStartNode(struct node **q)
{
    struct node *r,*t;
 r = *q;
 t = *q;
 while(t->link != NULL)
 {
     r = r->link;
     t = t->link->link;
     if(r == t)
     {
         break;
     }
 }
 if(t == NULL )
     return NULL;
 r = *q;
 while(r != t)
 {
     t = t->link;
     r = r->link;
 }
 return t->data;
}

int Append(struct node **q, char data);
int main()
{
struct node *p;
p = NULL;
char num;
Append(&p,'A');
Append(&p,'B');
Append(&p,'C');
Append(&p,'D');
Append(&p,'E');
Append(&p,'C');
//Display(p);
 num = FindStartNode(&p);
printf("\nStarting node of the cycle linked list is:- %c\n",num);
//_getch();
return 0;
}

int Append(struct node **q, char data)
{

struct node *r,*t, *startOfcycle=NULL;
r = (struct node *)malloc(sizeof(struct node));
r->data = data;


r->link = NULL;
if(*q == NULL)
    *q = r;
else
{
  t = *q;
  while(t->link != NULL)
  {
      if(t->data == data)
         startOfcycle = t;

      t = t->link;
  }


  if(startOfcycle == NULL)
  t->link = r;
  else {// there is a cycle point to the start of cycle
     t->link = startOfcycle;
     free(r);
  }
    }
return 0;
}
int Display(struct node *q)
{
while(q != NULL)
{
    printf("%c\t",q->data);
    q = q->link;
}

请注意，该Display函数也是错误的，因为运行链表的无限循环是循环的。我没有修改它，因为它与你的问题无关。谢谢。

于 2013-01-15T02:05:12.190 回答
0

...

 p = NULL;
 char num;
 Append(&p,'A');

...

您正在尝试分配给 Append 处理的 NULL，但您正在重复执行此操作，这意味着您不会创建列表，只是一堆悬空节点。

您需要在附加之外启动一个节点作为种子节点，然后将其传入。

于 2013-01-15T02:45:32.253 回答