/* 局部函数声明 */
Vertex * Make_Vertex (const Name vertex) ;
/* 接口函数定义 */
int CreateAdjacent_List (Adjacent_List * const padj, const int capacity)
{
int lenth_list = sizeof (Vertex), lenth_indegree = sizeof (int) ;
if (capacity <= 0)
return 0 ;
*padj = (struct adjacency_list *) malloc (sizeof (struct adjacency_list)) ;
if (NULL == *padj)
return 0 ;
(*padj) -> list = (Vertex *) malloc (lenth_list * capacity) ;
if (NULL == (*padj) -> list)
{
free (*padj) ;
return 0 ;
}
(*padj) -> indegree = (int *) malloc (lenth_indegree * capacity) ;
if (NULL == (*padj) -> indegree)
{
free ((*padj) -> list) ;
free (*padj) ;
return 0 ;
}
(*padj) -> capacity = capacity ;
return 1 ;
}
int InitializeALineOfAdjacent_List (const Adjacent_List * const padj, const int index, const Name name, const int indegree, const int sub, ...)
{
va_list ap ;
Vertex * temp ;
Name others ;
int i ;
if (index >= (*padj) -> capacity || sub < 0)
return 0 ;
va_start (ap, sub) ;
(*padj) -> indegree[index] = indegree ;
(*padj) -> list[index].name = name ;
(*padj) -> list[index].known = UNKNOWN ;
(*padj) -> list[index].dist = INFINITY ;
(*padj) -> list[index].path = UNKNOWN ;
if (0 == sub)
{
(*padj) -> list[index].next = NULL ;
va_end (ap) ;
return 1 ;
}
else
{
others = va_arg (ap, Name) ;
temp = (*padj) -> list[index].next = Make_Vertex (others) ;
if (NULL == temp)
{
va_end (ap) ;
return 0 ;
}
for (i = 1; i < sub; i++)
{
others = va_arg (ap, Name) ;
temp -> next = Make_Vertex (others) ;
temp = temp -> next ;
}
va_end (ap) ;
return 1 ;
}
}
void PrintAdjacent_List (const Adjacent_List * const padj)
{
Vertex scan ;
int i, capacity ;
capacity = (*padj) -> capacity ;
for (i = 0; i < capacity; i++)
{
printf ("Indegree:%-2d", (*padj) -> indegree[i]) ;
scan = (*padj) -> list[i] ;
while (scan.next)
{
printf ("%c ", scan.name) ;
scan = *scan.next ;
}
printf ("%c ", scan.name) ;
scan = (*padj) -> list[i] ;
printf ("%-10s vertex:%c known:%d dist:%d path:%c", " ", scan.name, scan.known, scan.dist, scan.path) ;
putchar ('/n') ;
}
}
void ReleaseAdjacent_List (const Adjacent_List * const padj)
{
Vertex * scan, * temp ;
int i, capacity ;
capacity = (*padj) -> capacity ;
for (i = 0; i < capacity; i++)
{
scan = (*padj) -> list[i].next ;
while (scan)
{
temp = scan ;
scan = scan -> next ;
free (temp) ;
}
}
free ((*padj) -> list) ;
free ((*padj) -> indegree) ;
free (*padj) ;
}
/* 局部函数定义 */
Vertex * Make_Vertex (const Name vertex)
{
Vertex * new_vertex = (Vertex *) malloc (sizeof (Vertex)) ;
if (new_vertex)
{
new_vertex -> name = vertex ;
new_vertex -> known = UNKNOWN ;
new_vertex -> dist = INFINITY ;
new_vertex -> path = UNKNOWN ;
new_vertex -> next = NULL ;
}
return new_vertex ;
}
int main (void) ;
void Unweightd (Adjacent_List * const padj) ;
int get_index (const Adjacent_List * const padj, const Name name) ;
int main (void)
{
Adjacent_List adj ;
int capacity = 9 ;
CreateAdjacent_List (&adj, capacity) ;
InitializeALineOfAdjacent_List (&adj, 0, 's', 0, 3, 'a', 'd', 'g') ;
InitializeALineOfAdjacent_List (&adj, 1, 'a', 1, 2, 'b', 'e') ;
InitializeALineOfAdjacent_List (&adj, 2, 'b', 1, 1, 'c') ;
InitializeALineOfAdjacent_List (&adj, 3, 'c', 3, 1, 't') ;
InitializeALineOfAdjacent_List (&adj, 4, 'd', 2, 2, 'a', 'e') ;
InitializeALineOfAdjacent_List (&adj, 5, 'e', 4, 3, 'c', 'f', 'i') ;
InitializeALineOfAdjacent_List (&adj, 6, 'f', 2, 2, 'c', 't') ;
InitializeALineOfAdjacent_List (&adj, 7, 'g', 1, 3, 'd', 'e', 'h') ;
InitializeALineOfAdjacent_List (&adj, 8, 'h', 1, 2, 'e', 'i') ;
InitializeALineOfAdjacent_List (&adj, 9, 'i', 2, 2, 'f', 't') ;
InitializeALineOfAdjacent_List (&adj, 10, 't', 3, 0) ;
PrintAdjacent_List (&adj) ;
putchar ('/n') ;
Unweightd (&adj) ;
PrintAdjacent_List (&adj) ;
ReleaseAdjacent_List (&adj) ;
return 1 ;
}
void Unweightd (Adjacent_List * const padj)
{
Queue queue ;
Vertex * v, *w, * scan ;
InitializeQueue (&queue) ;
v = &(*padj) -> list[0] ;
EnQueue (&queue, &v) ;
while (!QueueIsEmpty (&queue))
{
DeQueue (&queue, &v) ;
v -> known = KNOWN ;
scan = v -> next ;
while (scan)
{
w = &(*padj) -> list[get_index (padj, scan -> name)] ;
if (INFINITY == w -> dist)
{
w -> dist = v -> dist + 1 ;
w -> path = v -> name ;
EnQueue (&queue, &w) ;
}
scan = scan -> next ;
}
}
ReleaseQueue (&queue) ;
}
int get_index (const Adjacent_List * const padj, const Name name)
{
Vertex * temp = (*padj) -> list ;
if (name == temp[0].name)
return 0 ;
else if (name == temp[1].name)
return 1 ;
else if (name == temp[2].name)
return 2 ;
else if (name == temp[3].name)
return 3 ;
else if (name == temp[4].name)
return 4 ;
else if (name == temp[5].name)
return 5 ;
else if (name == temp[6].name)
return 6 ;
else if (name == temp[7].name)
return 7 ;
else if (name == temp[8].name)
return 8 ;
else if (name == temp[9].name)
return 9 ;
else
return 10 ;
}
单发点无权最短路径问题.实现的思想就是从发点开始,对所有临界到发点的顶点做出改变,并且放入队列中.从而依次处理到所有顶点的最短路径.
实现思想就是这样,实现的过程中遇到一些问题,但都还是解决了.最近感觉到,代码写的比较枯燥.没办法,还没有达到做出产品的程度,必须忍耐.
首先是邻接表的ADT,接口没有变,只是数据域多了几个.
#define INFINITY (~(1 << 31))
#define UNKNOWN 0
#define KNOWN 1
/* 数据类型定义 */
typedef char Name ;
typedef struct vertex
{
Name name ;
int known ;
int dist ;
Name path ;
struct vertex * next ;
} Vertex ;
typedef struct adjacency_list
{
Vertex * list ;
int * indegree ;
int capacity ;
} * Adjacent_List ;
/* 接口函数声明 */
/* 操作: 为一个邻接表分配存储空间 */
/* 操作前: padj 指向一个邻接表, capacity 指示邻接表的大小 */
/* 操作后: 如果 capacity > 0 && 内分分配成功, 创建该邻接表, 返回1; 否则返回0 */
/* 时间复杂度: O(1) */
int CreateAdjacent_List (Adjacent_List * const padj, const int capacity) ;
/* 操作: 初始化邻接表的第 index 行 */
/* 操作前: padj 指向一个已创建的邻接表, index 指示行的索引, name 指示表头顶点名字, indegree 指示该顶点的入度, sub 指示参数的个数, ... 指示邻接到该顶点的顶点 */
/* 操作后: 如果该邻接表存在第 index 行, 参数无误, 则初始化该行, 返回1; 否则返回0 */
/* 时间复杂度: O(N) */
int InitializeALineOfAdjacent_List (const Adjacent_List * const padj, const int index, const Name name, const int indegree, const int sub, ...) ;
/* 操作: 从低索引向高索引依次打印邻接表中所有顶点1次 */
/* 操作前: padj 指向一个已创建完毕的邻接表 */
/* 操作后: 该邻接表中的所有顶点依次被打印1次 */
/* 时间复杂度: O(N * N) */
void PrintAdjacent_List (const Adjacent_List * const padj) ;
/* 操作: 释放一个邻接表所占用的内存空间 */
/* 操作前: padj 指向一个已创建的邻接表 */
/* 操作后: 该邻接表所占用的内存空间被释放 */
/* 时间复杂度: O(N * N) */
void ReleaseAdjacent_List (const Adjacent_List * const padj) ;
接下来是队列的ADT,写得比较顺利.很是欣慰.
/* 数据类型定义 */
typedef Vertex * Queue_Item ;
typedef struct queue_node
{
Queue_Item queue_item ;
struct queue_node * next ;
} Queue_Node ;
typedef struct queue
{
Queue_Node * front ;
Queue_Node * rear ;
} * Queue ;
/* 接口函数声明 */
/* 操作: 创建并初始化一个队列 */
/* 操作前: pqueue 指向一个队列 */
/* 操作后: 如果内存分配成功, 队列被创建并被初始化为空, 返回1; 否则返回0 */
/* 时间复杂度: O(1) */
int InitializeQueue (Queue * const pqueue) ;
/* 操作: 确定一个队列是否为空 */
/* 操作前: pqueue 指向一个已初始化的队列 */
/* 操作后: 如果该队列为空, 返回1; 否则返回0 */
/* 时间复杂度: O(1) */
int QueueIsEmpty (const Queue * const pqueue) ;
/* 操作: 向队列中添加数据域为指定数据的元素 */
/* 操作前: pqueue 指向一个已初始化的队列, pqueue_item 指向被添加的数据 */
/* 操作后: 如果内存分配成功, 数据域为 *pqueue_item 的元素被添加到队列中, 返回1; 否则返回0 */
/* 时间复杂度: O(1) */
int EnQueue (Queue * const pqueue, const Queue_Item * const pqueue_item) ;
/* 操作: 从队列中删除一个元素 */
/* 操作前: pqueue 指向一个已初始化的队列, pqueue_item 是一个Queue_Item *类型的变量 */
/* 操作后: 如果队列不为空, 从队列中删除一个元素, 并将该元素的数据赋予 *pqueue_item 返回1; 否则返回0 */
/* 时间复杂度: O(1) */
int DeQueue (Queue * const pqueue, Queue_Item * const pqueue_item) ;
/* 操作: 释放一个队列所占用的内存空间 */
/* 操作前: pqueue 指向一个已初始化的队列 */
/* 操作后: 该队列所占用的内存空间被释放 */
/* 时间复杂度: O(N) */
void ReleaseQueue (Queue * const pqueue) ;
/* 局部函数声明 */
static Queue_Node * Make_Queue_Node (const Queue_Item * const pqueue_item) ;
/* 接口函数定义 */
int InitializeQueue (Queue * const pqueue)
{
*pqueue = (struct queue *) malloc (sizeof (struct queue)) ;
if (*pqueue)
{
(*pqueue) -> front = (*pqueue) -> rear = NULL ;
return 1 ;
}
else
return 0 ;
}
int QueueIsEmpty (const Queue * const pqueue)
{
return NULL == (*pqueue) -> front ;
}
int EnQueue (Queue * const pqueue, const Queue_Item * const pqueue_item)
{
Queue_Node * new_queue_node ;
new_queue_node = Make_Queue_Node (pqueue_item) ;
if (NULL == new_queue_node)
return 0 ;
if (QueueIsEmpty (pqueue))
(*pqueue) -> front = (*pqueue) -> rear = new_queue_node ;
else
(*pqueue) -> rear = (*pqueue) -> rear -> next = new_queue_node ;
return 1 ;
}
int DeQueue (Queue * const pqueue, Queue_Item * const pqueue_item)
{
Queue_Node * temp ;
if (QueueIsEmpty (pqueue))
return 0 ;
*pqueue_item = (*pqueue) -> front -> queue_item ;
if ((*pqueue) -> front == (*pqueue) -> rear)
{
free ((*pqueue) -> front) ;
(*pqueue) -> front = (*pqueue) -> rear = NULL ;
}
else
{
temp = (*pqueue) -> front ;
(*pqueue) -> front = (*pqueue) -> front -> next ;
free (temp) ;
}
return 1 ;
}
void ReleaseQueue (Queue * const pqueue)
{
Queue_Node * temp, * scan = (*pqueue) -> front ;
while (scan)
{
temp = scan ;
scan = scan -> next ;
free (temp) ;
}
free (*pqueue) ;
}
/* 局部函数定义 */
static Queue_Node * Make_Queue_Node (const Queue_Item * const pqueue_item)
{
Queue_Node * new_queue_node ;
new_queue_node = (Queue_Node *) malloc (sizeof (Queue_Node)) ;
if (new_queue_node)
{
new_queue_node -> queue_item = *pqueue_item ;
new_queue_node -> next = NULL ;
}
return new_queue_node ;
}
其实对于多文件编译的情况,我还是需要学习很多,怎样会使改变尽可能的少.呵呵,这似乎是简单的逻辑问题,但我现在还不会.