学步园

/* hash.c -- 哈希表实现文件 */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include "hash.h"</p> <p>/* 局部函数声明 */</p> <p>static int Get_A_Prime (const int number) ;<br /> static int Is_A_Prime (const int number) ;<br /> static int Square (const int i) ;</p> <p>/* 接口函数定义 */</p> <p>int Hash (const Hash_Table * const pht, const Name * const pname)<br /> {<br /> return *pname * PRIME % (*pht) -> capacity ;<br /> }</p> <p>int Initialize_H (Hash_Table * const pht, const int capacity)<br /> {<br /> int real_capacity, i ;</p> <p> if (capacity <= 0)<br /> return 0 ;<br /> real_capacity = Get_A_Prime (capacity) ;<br /> *pht = (struct hash_table *) malloc (sizeof (struct hash_table)) ;<br /> if (NULL == *pht)<br /> return 0 ;<br /> (*pht) -> lists = (Cell *) malloc (sizeof (Cell) * real_capacity) ;<br /> if (NULL == (*pht) -> lists)<br /> {<br /> free (*pht) ;<br /> return 0 ;<br /> }<br /> for (i = 0; i < real_capacity; i++)<br /> {<br /> (*pht) -> lists[i].entry = EMPTY ;<br /> (*pht) -> lists[i].name = NUL ;<br /> (*pht) -> lists[i].be_deleted = FALSE ;<br /> }<br /> (*pht) -> current = 0 ;<br /> (*pht) -> capacity = real_capacity ;</p> <p> return 1 ;<br /> }</p> <p>Cell * Find_H (const Hash_Table * const pht, const Name * const pname)<br /> {<br /> int hash_value, i = 1, capacity = (*pht) -> capacity ;</p> <p> hash_value = Hash (pht, pname) ;<br /> while (LEGITIMATE == (*pht) -> lists[hash_value].entry && (*pht) -> lists[hash_value].name != *pname)<br /> {<br /> putchar ('/a') ;<br /> hash_value = (hash_value + Square (i++)) % capacity ;<br /> }</p> <p> return (*pht) -> lists + hash_value ;<br /> }</p> <p>int Insert_H (const Hash_Table * const pht, const Name * const pname, const int index)<br /> {<br /> Cell * p ;</p> <p> if ((*pht) -> current > (*pht) -> capacity / 2 + 1)<br /> return FAILED ;<br /> p = Find_H (pht, pname) ;<br /> if (EMPTY == p -> entry || DELETED == p -> entry)<br /> {<br /> p -> entry = LEGITIMATE ;<br /> p -> name = *pname ;<br /> p -> index_in_adjacenty_list = index ;<br /> }<br /> (*pht) -> current++ ;</p> <p> return (p - (*pht) -> lists) / sizeof (Cell) ;<br /> }</p> <p>int Delete_H (const Hash_Table * const pht, const Name * const pname)<br /> {<br /> Cell * p ;</p> <p> p = Find_H (pht, pname) ;<br /> if (*pname == p -> name && LEGITIMATE == p -> entry)<br /> {<br /> p -> entry = DELETED ;<br /> (*pht) -> current-- ;<br /> return 1 ;<br /> }<br /> else<br /> return 0 ;<br /> }</p> <p>void Release_H (const Hash_Table * const pht)<br /> {<br /> free ((*pht) -> lists) ;<br /> free (*pht) ;<br /> }</p> <p>/* 局部函数定义 */</p> <p>static int Get_A_Prime (const int number)<br /> {<br /> int result = number ;</p> <p> while (!Is_A_Prime (result))<br /> result++ ;</p> <p> return result ;<br /> }</p> <p>static int Is_A_Prime (const int number)<br /> {<br /> int i, limit ;</p> <p> for (i = 2, limit = number / 2 + 1; i <= limit; i++)<br /> {<br /> if (0 == number % i)<br /> return 0 ;<br /> }</p> <p> return 1 ;<br /> }</p> <p>static int Square (const int i)<br /> {<br /> return i * i ;<br /> }