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;
     }
 }

私はあなたのコードを調べました。ここでのアルゴリズムの議論と比較すると、問題ないようです。しかし、charNULLかどうかを確認できるように、ポインターを返さない理由を返しています。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 に割り当てようとしていますが、繰り返し実行しているため、リストを作成せず、ぶら下がっているノードの束だけを作成します。

シード ノードとして追加の外部で開始するノードを 1 つ作成し、それを渡す必要があります。

于 2013-01-15T02:45:32.253 に答える