推 cutekid:你要不要把你的測資貼出來，看看是哪裡有誤呢？ 12/26 20:42
→ s89162504:你確定這種問題你不自己找嗎? 12/27 01:28
開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
問題(Question)：
這個演算法到底有誤嗎~?
追蹤不出最後結果
餵入的資料(Input)：
預期的正確結果(Expected Output)：
錯誤結果(Wrong Output)：
程式碼(Code)：(請善用置底文網頁, 記得排版)
typedef struct node *node_pointer;
typedef struct node {
int vertex;
node_pointer link;
};
typedef struct {
int count;
node_pointer link;
} hdnodes;
hdnodes graph[MAX_VERTICES];
void topsort (hdnodes graph [] , int n)
{
int i, j, k, top;
node_pointer ptr;
/* create a stack of vertices with no predecessors */
top = -1;
for (i = 0; i < n; i++)
if (!graph[i].count) {
graph[i].count = top;
top = i;
}
for (i = 0; i < n; i++)
if (top == -1) {
fprintf(stderr, “\n Network has a cycle. Sort terminated. \n”);
exit(1);
}
else {
j = top; /* unstack a vertex */
top = graph[top].count;
printf(“v%d, “, j);
for (ptr = graph [j]. link; ptr ;ptr = ptr ->link ){
/* decrease the count of the successor vertices of j */
k = ptr ->vertex;
graph[k].count --;
if (!graph[k].count) {
/* add vertex k to the stack*/
graph[k].count = top;
top = k;
}
}
}
}
補充說明(Supplement)：
這是資料結構聖經本上面的演算法,但是我紙筆追蹤了好多次
最後都是造成cycle排序結束
top都會被設成-1
很怪
count是每個節點的indegree
請問到底哪裏出問題呢~?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.240.82