循環鏈表的循環開始節點

我試圖實現一個程序來查找循環鏈表的起始節點。我的代碼是 -循環鏈表的循環開始節點

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

這是我的代碼。我沒有得到任何回報t->數據部分的價值，或者我無法找到循環墨跡列表的開始節點。任何幫助？

來源

2013-01-15 Amit_T

這段代碼旨在確定名單正好是一圈又回到某處列表（即，一個節點連接兩次）？如果是這樣，並假設你修復了似乎導致這個問題的NULL值，那麼看起來你可能會陷入最後的'while'循環中，'r'無休止地追着't'。 –

不是圓形鏈表中「起始節點」的想法有點...任意？我認爲他們*全部*可能是一個開始節點。或者你是否打算找到指向*的節點*？我們是否假定'* q'有一個指向* some *節點的指針，而你想要的那個是*之前的那個*？ – WhozCraig

這甚至意味着什麼，找到一個循環列表的起始節點？創建列表的代碼應該提供一個指向元素的指針，幾乎總是第一個創建的元素。這是切入點。之後，從概念上講，沒有真正的開始或結束。這就是爲什麼它是循環的。 –

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

我已經通過您的代碼了。與算法討論here比較，它似乎是確定的。但是你要返回一個char爲什麼不返回一個指針，以便檢查它是否爲NULL。如果它不是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-15 02:05:12 hmatar

是的，你是對的我面臨同樣的問題，但我怎麼能忽略它？ –

請看我的代碼，我已經添加了適當的代碼部分進行修改。 – hmatar

作爲回報t-> data，我沒有得到任何價值。它應該返回起始節點。爲什麼？ –

...

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

...

您試圖指派爲NULL，其中附加的把手，但你反覆做，這意味着你不會打表，只是一堆懸掛的節點。

你需要做一個節點開始，追加之外，作爲你的種子節點，並傳遞英寸

來源

2013-01-15 02:45:32

循環鏈表的循環開始節點

回答

相關問題