学步园

  话说,这个东西我写了前前后后4天有余, 光今天就写了10小时.终于写完了.感触颇多啊.!

  新的数据结构需要以前的数据结构结合使用,我沿着思路,进行设计,之后开始动笔,呵呵.开始写,就是.

  从Hash表,到邻接表,再到二叉堆,磕磕绊绊,自己写得比较着急,结果我还没有那么熟练,无法快速完成.能够完成,我就已经很高兴了.呵呵.

  很多概念,是随着写代码灵光起来的.写着写着,想起来书上原来有讲过,呵呵.

  对于Hash表和二叉堆的理解,总是在渐渐深刻,主要是那两章学得比较着急.所以,现在就到难受的时候了,呵呵.还算凑合,虽然有些繁琐,.

  对于多文件编译,感觉比较陌生,在今后的编码过程中总结经验,去阅读相关的书籍.

  邻接表实现文件是一个新的,因为是赋权图,被迫修改的.比较有通用性,用着也比较方便.

  不想多说了,脖子疼.去睡觉了准备.开始贴代码.哈哈.

/* 9-9(b)-12-12-12.12.c -- 第九章第九题 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "binary_heap.h"</p> <p>int main (void) ;<br /> int dijkstra (const Adjacenty_List * padj, const Hash_Table * const pht, const int start) ;</p> <p>int main (void)<br /> {<br /> Adjacenty_List adj ;<br /> Hash_Table ht ;<br /> int capacity = 11 ;</p> <p> Initialize_H (&ht, capacity * 2) ;<br /> Initialize_A (&adj, capacity) ;<br /> InitializeALine_A (&adj, &ht, 0, 's', 0, 6, 'a', 1, 'd', 4, 'g', 6) ;<br /> InitializeALine_A (&adj, &ht, 1, 'a', 2, 4, 'b', 2, 'e', 2) ;<br /> InitializeALine_A (&adj, &ht, 2, 'b', 1, 2, 'c', 2) ;<br /> InitializeALine_A (&adj, &ht, 3, 'c', 3, 2, 't', 4) ;<br /> InitializeALine_A (&adj, &ht, 4, 'd', 2, 4, 'a', 3, 'e', 3) ;<br /> InitializeALine_A (&adj, &ht, 5, 'e', 4, 6, 'c', 2, 'f', 3, 'i', 3) ;<br /> InitializeALine_A (&adj, &ht, 6, 'f', 2, 4, 'c', 1, 't', 3) ;<br /> InitializeALine_A (&adj, &ht, 7, 'g', 1, 6, 'd', 2, 'e', 1, 'h', 6) ;<br /> InitializeALine_A (&adj, &ht, 8, 'h', 1, 4, 'e', 2, 'i', 3) ;<br /> InitializeALine_A (&adj, &ht, 9, 'i', 2, 4, 'f', 1, 't', 4) ;<br /> InitializeALine_A (&adj, &ht, 10, 't', 3, 0) ;<br /> dijkstra (&adj, &ht, 0) ;<br /> PrintAdjacenty_List_A (&adj, &ht) ;</p> <p> Release_H (&ht) ;<br /> Release_A (&adj) ;</p> <p> return 0 ;<br /> }</p> <p>int dijkstra (const Adjacenty_List * padj, const Hash_Table * const pht, const int start)<br /> {<br /> Binary_Heap bh ;<br /> Vertex * v ;<br /> Adjoin_To_Vertex * w ;<br /> int capacity = (*padj) -> capacity, i ;</p> <p> Initialize_B (&bh, capacity * 2) ;<br /> (*padj) -> list[start].dist = 0 ;<br /> for (i = 0; i < capacity; i++)<br /> Insert_B (&bh, (*padj) -> list + i) ;<br /> while (1)<br /> {<br /> do<br /> {<br /> v = DeleteMin_B (&bh) ;<br /> if (NEGATIVEINFINITY == v -> dist)<br /> break ;<br /> }<br /> while (TRUE == (*pht) -> lists[v -> hash_value].be_deleted)<br /> ;<br /> if (NEGATIVEINFINITY == v -> dist)<br /> break ;<br /> (*pht) -> lists[v -> hash_value].be_deleted = TRUE ;<br /> v -> known = TRUE ;<br /> w = v -> adjoin_to ;<br /> while (w)<br /> {<br /> if (FALSE == (*padj) -> list[(*pht) -> lists[w -> hash_value].index_in_adjacenty_list].known)<br /> {<br /> if (v -> dist + w -> cvw < (*padj) -> list[(*pht) -> lists[w -> hash_value].index_in_adjacenty_list].dist)<br /> {<br /> (*padj) -> list[(*pht) -> lists[w -> hash_value].index_in_adjacenty_list].dist = v -> dist + w -> cvw ;<br /> Insert_B (&bh, (*padj) -> list + (*pht) -> lists[w -> hash_value].index_in_adjacenty_list) ;<br /> (*padj) -> list[(*pht) -> lists[w -> hash_value].index_in_adjacenty_list].path = (*pht) -> lists[v -> hash_value].name ;<br /> }<br /> }<br /> w = w -> next ;<br /> }<br /> }<br /> Release_B (&bh) ;</p> <p> return 1 ;<br /> }