学步园

  这个,主要体现的是思想.问题在一开始就被定义在了一道已知的习题上,所以并没有什么通用性.实现中,如果在栈中存储名字的同时存储索引,那么,将会省去很多次函数调用.而且,散列在我这个实现中也没有发挥作用,我会去实现的.

  基本的思路,就是这样,理解得还算不错,哈哈.

  可喜可贺的是,好几天没有写代码了.冷不丁一写,成功率出奇地高.和专心程度有关吗?加油吧.留给自己的时间不多了,每一天都要努力!

/* 9-3-12-07-20.06.c -- 第九章第三题 */<br /> #include <stdio.h><br /> #include <stdlib.h></p> <p>typedef char Name ;</p> <p>#include "Stack_ADT.h"<br /> #include "adjacenty_list.h"</p> <p>#define SIZE 11</p> <p>int main (void) ;<br /> int get_index (const Adjacent_List * const padj, const Name name) ;<br /> void topological_sort (Adjacent_List * padj, Name * topological) ;<br /> void print_name (const Name vertex) ;<br /> void print_stack (const Stack_Node * const pstack_node) ;</p> <p>int main (void)<br /> {<br /> Adjacent_List adj ;<br /> int capacity = SIZE, i ;<br /> Name topological[SIZE] ;</p> <p> CreateAdjacent_List (&adj, capacity) ;<br /> InitializeALineOfAdjacent_List (&adj, 0, 's', 0, 3, 'a', 'd', 'g') ;<br /> InitializeALineOfAdjacent_List (&adj, 1, 'a', 1, 2, 'b', 'e') ;<br /> InitializeALineOfAdjacent_List (&adj, 2, 'b', 1, 1, 'c') ;<br /> InitializeALineOfAdjacent_List (&adj, 3, 'c', 3, 1, 't') ;<br /> InitializeALineOfAdjacent_List (&adj, 4, 'd', 2, 2, 'a', 'e') ;<br /> InitializeALineOfAdjacent_List (&adj, 5, 'e', 4, 3, 'c', 'f', 'i') ;<br /> InitializeALineOfAdjacent_List (&adj, 6, 'f', 2, 2, 'c', 't') ;<br /> InitializeALineOfAdjacent_List (&adj, 7, 'g', 1, 3, 'd', 'e', 'h') ;<br /> InitializeALineOfAdjacent_List (&adj, 8, 'h', 1, 2, 'e', 'i') ;<br /> InitializeALineOfAdjacent_List (&adj, 9, 'i', 2, 2, 'f', 't') ;<br /> InitializeALineOfAdjacent_List (&adj, 10, 't', 3, 0) ;<br /> // PrintAdjacent_List (&adj) ;<br /> topological_sort (&adj, topological) ;<br /> for (i = 0; i < 11; i++)<br /> printf ("%c/n", topological[i]) ;<br /> ReleaseForAdjacent_List (&adj) ;</p> <p> return 0 ;<br /> }</p> <p>int get_index (const Adjacent_List * const padj, const Name name)<br /> {<br /> int i, capacity = (*padj) -> capacity ;</p> <p> for (i = 0; i < capacity; i++)<br /> {<br /> if (name == (*padj) -> list[i].name)<br /> return i ;<br /> }<br /> }</p> <p>void topological_sort (Adjacent_List * padj, Name * topological)<br /> {<br /> Stack stack ;<br /> int counter = 0, capacity = (*padj) -> capacity, i ;<br /> Vertex * scan ;<br /> Name v ;</p> <p> InitializeStack (&stack) ;<br /> for (i = 0; i < capacity; i++)<br /> {<br /> if (0 == (*padj) -> indegree[i])<br /> Push (&stack, &(*padj) -> list[i].name) ;<br /> }<br /> while (!StackIsEmpty (&stack))<br /> {<br /> Pop (&stack, &v) ;<br /> topological[counter++] = v ;<br /> scan = (*padj) -> list[get_index (padj, v)].next ;<br /> while (scan)<br /> {<br /> if (0 == --(*padj) -> indegree[get_index (padj, scan -> name)])<br /> Push (&stack, &(*padj) -> list[get_index (padj, scan -> name)].name) ;<br /> scan = scan -> next ;<br /> }<br /> }<br /> if (counter != capacity)<br /> puts ("Graph has cycle.") ;<br /> ReleaseStack (&stack) ;<br /> }</p> <p>void print_name (const Name vertex)<br /> {<br /> printf ("%c ", vertex) ;<br /> }</p> <p>void print_stack (const Stack_Node * const pstack_node)<br /> {<br /> printf ("%c/n", pstack_node -> name) ;<br /> }