Chinaunix首页 | 论坛 | 博客

GP-Kinggpking.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

gongping11

  • 博客访问： 1891600
  • 博文数量： 152
  • 博客积分： 3730
  • 博客等级： 上尉
  • 技术积分： 3710
  • 用 户 组： 普通用户
  • 注册时间： 2011-06-02 14:36
个人简介

减肥，运动，学习，进步...

文章分类

全部博文（152）

文章存档

2016年（14）

2015年（17）

2014年（16）

2013年（4）

2012年（66）

2011年（35）

我的朋友
最近访客
推荐博文
相关博文
散列的C语言实现

分类： C/C++

2012-08-28 11:55:55

散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的，而不像在数组中的遍历过程，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置，这样的访问速度就省去了遍历数组的实现，因此时间复杂度可以认为为O(1),而数组遍历的时间复杂度为O(n)。

 

散列是能一种快速实现访问的存储方式。通常作为检索部分的数据项是整形或者字符串，当是字符串时，字符串的数量要远远大于数组的长度，这时候就会有多个字符串映射到一个存储位置的情况，这就是所谓的冲突问题，而且冲突时肯定存在的，这时候如何实现数据的存储又是需要解决的。

目前主要的解决方式有两大类，第一种采用链表的形式，将所有冲突的数据项采用链表的形式链接起来，这样搜索数据的复杂度就包含了链表的遍历问题，特别是当所有的项都链接到一个链表下时，这时候实际上就是遍历链表，复杂度并不一定有很大的进步，但是这种链表链接的方式有很高的填充率。第二种就是充分利用没有实现的存储空间，利用探测法探测空闲的空间，进而实现数据的存储，目前有三种探测方式：线性探测法、平方探测法，以及双散列法，三种方式中平方探测法运用比较多，但是都存在各种各样的优缺点，这时候的散列搜索优势就没有理想情况下那么明显。有时候甚至比遍历数组更加的慢。但是确实不失为一种处理方式。

映射函数可选择的比较多，其实完全可以定义自己的映射函数，但是有时候为了降低冲突的概率设置了一些比较好的映射函数，比如求和取余，或者乘以一定的系数再求和取余等。

 

本文采用平方探测法解决了冲突问题，具体的实现如下所示：

1、结构体定义

点击(此处)折叠或打开

  1. #ifndef __HASHMAP_H_H_
  2. #define __HASHMAP_H_H_

  4. #include "list.h"

  6. #define TABSIZE    101

  8. /*状态变量*/
  9. typedef enum STATE{EMPTY = 0, ACTIVE = 1, DELETED = 2} State;

  11. /*键值结构体*/
  12. typedef struct _pair
  13. {
  14.     char *key;
  15.     char *value;
  16. }Pair_t, *Pair_handle_t;

  18. /*每一个实际的存储对象*/
  19. typedef struct _hashEntry
  20. {
  21.     Pair_handle_t pair;
  22.     State state;
  23. }HashEntry_t, *HashEntry_handle_t;

  25. /*哈希表结构体，便于创建*/
  26. typedef struct _hashmap
  27. {
  28.     HashEntry_t *map;
  29.     /*存储实际的存储量*/
  30.     int size;
  31.     /*容量*/
  32.     int capacity;
  33. }Hashmap_t, *Hashmap_handle_t;

  35. /*隐射函数类型定义*/
  36. typedef int(*hashfunc)(const char *, int);

  38. #ifdef __cplusplus
  39. extern "C"
  40. {
  41. #endif

  43. bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity);
  44. bool init_hashmap(Hashmap_handle_t hashmap, int capacity);
  45. bool insert_hashnode(Hashmap_handle_t hashmap, const char *key, const char *value);
  46. Pair_handle_t search_hashnode(Hashmap_handle_t hashmap, const char *key);
  47. char *GetValue(Hashmap_handle_t hashmap, const char *key);
  48. bool delete_hashnode(Hashmap_handle_t hashmap, const char *key);
  49. int Length(Hashmap_handle_t hashmap);
  50. int Capacity(Hashmap_handle_t hashmap);
  51. void delete_hashmap(Hashmap_handle_t hashmap);
  52. void free_hashmap(Hashmap_handle_t *hashmap);
  53. char *key_pair(Pair_handle_t pair);
  54. char *value_pair(Pair_handle_t pair);
  55. Hashmap_handle_t copy_hashmap(Hashmap_handle_t hashmap);
  56. bool resize(Hashmap_handle_t hashmap);

  58. #ifdef __cplusplus
  59. }
  60. #endif
  61. #endif
实现表的分配和创建，采用了动态分配的方式实现，这样可能在性能上比不上静态数据，但是为了实现数组大小的调整，我选择了动态分配的实现方式。

点击(此处)折叠或打开

  1. /*分配一个新的对象，可以实现自动分配*/
  2. bool alloc_hashmap(Hashmap_handle_t *hashmap, int capacity)
  3. {
  4.     HashEntry_handle_t temp = NULL;
  5.     Hashmap_t * map = NULL;

  7.     if(*hashmap == NULL)
  8.     {
  9.         /*分配一个散列对象*/
  10.         map = (Hashmap_handle_t)malloc(sizeof(Hashmap_t));
  11.         if(map == NULL)
  12.             return false;
  13.         /*指针指向当前对象*/
  14.         *hashmap = map;
  15.         map = NULL;

  17.         /*分配一个数组空间，大小可以控制*/
  18.         temp = (HashEntry_handle_t)malloc(
  19.             sizeof(HashEntry_t)*capacity);
  20.         if(temp != NULL)
  21.         {
  22.             /*散列对象的指针指向数组*/
  23.             (*hashmap)->map = temp;
  24.             temp = NULL;
  25.             /*设置参数*/
  26.             (*hashmap)->capacity = capacity;
  27.             (*hashmap)->size = 0;
  28.             /*初始化分配的数组空间*/
  29.             Tabinital((*hashmap)->map,capacity);
  30.             return true;
  31.         }
  32.     }
  33.     return false;
  34. }

  36. /*初始化一个新的对象，这个对象已经创建，只是没有初始化而已*/
  37. bool init_hashmap(Hashmap_handle_t hashmap, int capacity)
  38. {
  39.     HashEntry_handle_t temp = NULL;
  40.     
  41.     if(hashmap != NULL)
  42.     {
  43.         /*分配数组空间*/
  44.         temp = (HashEntry_handle_t)malloc(
  45.                 sizeof(HashEntry_t)*capacity);
  46.         if(temp != NULL)
  47.         {
  48.             /*完成对象的填充操作*/
  49.             hashmap->map = temp;
  50.             temp = NULL;
  51.             hashmap->capacity = capacity;
  52.             hashmap->size = 0;
  53.             /*初始化数组对象*/
  54.             Tabinital(hashmap->map,capacity);
  55.             return true;
  56.         }
  57.     }
  58.     return false;
  59. }
关于数组中对象的创建，和释放操作，如下所示：

点击(此处)折叠或打开

  1. /*分配一个pair对象*/
  2. static bool make_pair(Pair_handle_t *pair, const char *key, const char *value)
  3. {
  4.     Pair_handle_t newpair =(Pair_handle_t)malloc(sizeof(Pair_t));
  5.     char *newstr = NULL;

  7.     if(newpair == NULL)
  8.         return false;
  9.     
  10.     newstr = (char *)malloc(strlen(key) + 1);
  11.     if(newstr == NULL)
  12.         return false;

  14.     strcpy(newstr, key);
  15.     newstr[strlen(key)] = '\0';
  16.     newpair->key = newstr;
  17.     newstr = NULL;

  19.     newstr = (char *)malloc(strlen(value) + 1);
  20.     if(newstr == NULL)
  21.         return false;

  23.     strcpy(newstr, value);
  24.     newstr[strlen(value)] = '\0';
  25.     newpair->value = newstr;
  26.     newstr = NULL;
  27.     
  28.     (*pair) = newpair;
  29.     return true;
  30. }

  32. /*释放一个对象pair*/
  33. static void delete_pair(Pair_handle_t *pair)
  34. {
  35.     Pair_handle_t temp = NULL;
  36.     if(*pair == NULL)
  37.         return ;

  39.     temp = *pair;
  40.     free(temp->key);
  41.     temp->key = NULL;
  42.     free(temp->value);
  43.     temp->value = NULL;

  45.     free(temp);
  46.     temp = NULL;
  47.     *pair = NULL;
  48. }
数组元素的基本操作：

点击(此处)折叠或打开

  1. /*完成数组对象的初始化操作*/
  2. static void Tabinital(HashEntry_t *tab, int size)
  3. {
  4.     int i = 0;
  5.     for(; i < size; ++ i)
  6.     {
  7.         tab[i].pair = NULL;
  8.         tab[i].state = EMPTY;
  9.     }    
  10. }

  12. static void delete_array(HashEntry_handle_t *array, int size)
  13. {
  14.     int i = 0;

  16.     if(*array != NULL)
  17.     {
  18.         for(i = 0; i < size; ++ i)
  19.         {
  20.             if((*array)[i].state == ACTIVE)
  21.             {
  22.                 delete_pair(&((*array)[i].pair));
  23.                 (*array)[i].state = DELETED;
  24.             }
  25.         }
  26.         free(*array);
  27.         *array = NULL;
  28.     }
  29. }
插入元素的操作、有两个函数的创建，其中一个为了便于后期大小的调整操作。

点击(此处)折叠或打开

  1. /*插入数据到散列中，采用了二次探测的实现方式，并设置了退出条件*/
  2. static bool insert_data(Hashmap_handle_t hashmap,
  3.     const char *key, const char *value, hashfunc func)
  4. {
  5.     int hashval = func(key,hashmap->capacity);
  6.     int index = 0;
  7.     char * newstr = NULL;

  9.     Pair_handle_t newpair = NULL;

  11.     while(hashmap->map[hashval].state != EMPTY)
  12.     {
  13.         if((hashmap->map[hashval].state == ACTIVE)
  14.         && (strcmp(hashmap->map[hashval].pair->key,key) == 0))
  15.             break;

  17.         index ++;
  18.         hashval += index * index;
  19.         hashval %= hashmap->capacity;
  20.         if(index == 200)
  21.             break;
  22.     }
  23.     
  24.     if(hashmap->map[hashval].state == EMPTY)
  25.     {
  26.         if(make_pair(&newpair,key,value))
  27.         {
  28.             hashmap->map[hashval].state = ACTIVE;
  29.             hashmap->map[hashval].pair = newpair;
  30.             newpair = NULL;
  31.             hashmap->size ++;
  32.             return true;
  33.         }
  34.     }

  36.     else if((hashmap->map[hashval].state == ACTIVE)
  37.         && (strcmp(hashmap->map[hashval].pair->key, key) == 0))
  38.     {
  39.         newstr = (char *)malloc(strlen(value) + 1);
  40.         if(newstr != NULL)
  41.         {
  42.             strcpy(newstr,value);
  43.             newstr[strlen(value)] = '\0';
  44.             free(hashmap->map[hashval].pair->value);
  45.             hashmap->map[hashval].pair->value = newstr;
  46.             newstr = NULL;

  48.             return true;
  49.         }
  50.     }
  51.     return false;
  52. }

  54. static bool insert2map(HashEntry_handle_t map,
  55.     const char *key, const char *value,
  56.     hashfunc func, int size)
  57. {
  58.     int hashval = func(key,size);
  59.     int index = 0;
  60.     char *newstr = NULL;
  61.     Pair_handle_t newpair = NULL;

  63.     if(map != NULL)
  64.     {
  65.         while(map[hashval].state != EMPTY)
  66.         {
  67.             if((map[hashval].state == ACTIVE)
  68.             && (strcmp(map[hashval].pair->key, key) == 0))
  69.                 break;
  70.             
  71.             index ++;
  72.             hashval += index * index;
  73.             hashval %= size;
  74.             /*防止死循环*/
  75.             if(index == 200)
  76.                 break;
  77.         }
  78.         
  79.         if(map[hashval].state == EMPTY)
  80.         {
  81.             if(!make_pair(&newpair,key,value))
  82.                 return false;
  83.             map[hashval].pair = newpair;
  84.             map[hashval].state = ACTIVE;
  85.             newpair = NULL;
  86.             return true;
  87.         }
  88.         else if((map[hashval].state == ACTIVE) &&
  89.             (strcmp(map[hashval].pair->key, key) == 0))
  90.         {
  91.             newstr = (char *)malloc(strlen(value) +1);
  92.             if(newstr != NULL)
  93.             {
  94.                 free(map[hashval].pair->value);
  95.                 map[hashval].pair->value = NULL;
  96.                 strcpy(newstr, value);
  97.                 newstr[strlen(value)] = '\0';
  98.                 map[hashval].pair->value = newstr;
  99.                 return true;
  100.             }
  101.         }            
  102.     }
  103.     return false;
  104. }

调整大小和插入的实际操作。

点击(此处)折叠或打开

  1. bool resize(Hashmap_handle_t hashmap)
  2. {
  3.     int i = 0;
  4.     HashEntry_handle_t newarray = NULL;    

  6.     int size = next_prime(2*hashmap->capacity);

  8.     if(hashmap != NULL)
  9.     {
  10.         newarray = (HashEntry_handle_t)malloc(sizeof(HashEntry_t)
  11.                     *size);
  12.         if(newarray == NULL)
  13.             return false;

  15.         /*这一步至关重要*/
  16.         Tabinital(newarray, size);
  17.         for(; i < hashmap->capacity ; ++ i)
  18.         {
  19.             if(hashmap->map[i].state == ACTIVE)
  20.             {
  21.                 if(!insert2map(newarray,
  22.                     hashmap->map[i].pair->key,
  23.                     hashmap->map[i].pair->value,
  24.                     HashFunc, size))
  25.                     return false;
  26.             }
  27.         }
  28.         delete_array(&hashmap->map,hashmap->capacity);
  29.         hashmap->map = newarray;
  30.         hashmap->capacity = size;
  31.         return true;
  32.     }

  34.     return false;
  35. }

  37. bool insert_hashnode(Hashmap_handle_t hashmap,
  38.     const char *key, const char *value)
  39. {
  40.     if(hashmap->size < hashmap->capacity)
  41.     {
  42.         if(insert_data(hashmap,key,value,HashFunc))
  43.         {
  44.             //hashmap->size ++;
  45.         }
  46.     
  47.         return true;
  48.     }
  49.     else /*增加容量*/
  50.     {
  51.         if(!resize(hashmap))
  52.             return false;

  54.         if(insert_data(hashmap,key,value,HashFunc))
  55.         {
  56.             //hashmap->size ++;
  57.         }
  58.         return true;
  59.     }
  60.     return false;
  61. }
搜索操作

点击(此处)折叠或打开

  1. static Pair_handle_t search_data(Hashmap_handle_t hashmap, const char *key, hashfunc func)
  2. {
  3.     int hashval = func(key, hashmap->capacity);
  4.     int index = 0;
  5.     
  6.     while(hashmap->map[hashval].state != EMPTY)
  7.     {
  8.         if((hashmap->map[hashval].state == ACTIVE)
  9.         && (strcmp(hashmap->map[hashval].pair->key,key) == 0))
  10.             break;

  12.         index ++;
  13.         hashval += index * index;
  14.         hashval %= hashmap->capacity;
  15.         if(index == 200)
  16.             break;
  17.     }

  19.     if((hashmap->map[hashval].state == ACTIVE)
  20.         && (strcmp(hashmap->map[hashval].pair->key, key) == 0))
  21.     {
  22.         return hashmap->map[hashval].pair;
  23.     }
  24.     
  25.     return NULL;
  26. }

  28. Pair_handle_t search_hashnode(Hashmap_handle_t hashmap, const char * key)
  29. {
  30.     return search_data(hashmap,key,HashFunc);
  31. }
删除操作

点击(此处)折叠或打开

  1. static bool delete_node(Hashmap_handle_t hashmap,const char *key,hashfunc func)
  2. {
  3.     int hashval = func(key, hashmap->capacity);
  4.     int index = 0;
  5.     
  6.     /**********************************************
  7.       *退出循环的条件是找到空闲的单元，或者关键字匹配
  8.      *********************************************/
  9.     while(hashmap->map[hashval].state != EMPTY)
  10.     {
  11.         if((hashmap->map[hashval].state == ACTIVE)
  12.         && strcmp(hashmap->map[hashval].pair->key,key) == 0)
  13.             break;

  15.         index ++;
  16.         hashval += index * index;
  17.         hashval %= hashmap->capacity;
  18.     
  19.         if(index == 200)
  20.             break;
  21.     }

  23.     /*判断删除条件*/
  24.     if((hashmap->map[hashval].state == ACTIVE) &&
  25.         (strcmp(hashmap->map[hashval].pair->key, key) == 0))
  26.     {
  27.         hashmap->map[hashval].state = DELETED;
  28.         delete_pair(&(hashmap->map[hashval].pair));
  29.         hashmap->map[hashval].pair = NULL;    
  30.         
  31.         return true;
  32.     }

  34.     return false;
  35. }

  37. bool delete_hashnode(Hashmap_handle_t hashmap, const char *key)
  38. {
  39.     if(delete_node(hashmap, key, HashFunc))
  40.     {
  41.         hashmap->size --;
  42.         return true;
  43.     }

  45.     return false;
  46. }

参数获取函数；

点击(此处)折叠或打开

  1. int Length(Hashmap_t *map)
  2. {

  4.     return map->size;
  5. }

  7. int Capacity(Hashmap_t *map)
  8. {
  9.     return map->capacity;
  10. }

  12. void delete_hashmap(Hashmap_handle_t hashmap)
  13. {    
  14.     int i = 0;
  15.     int size = hashmap->capacity;

  17.     if(hashmap != NULL)
  18.     {
  19.         for(; i < size; ++ i)    
  20.         {
  21.             if(hashmap->map[i].state == ACTIVE)
  22.             {
  23.                 delete_pair(&(hashmap->map[i].pair));
  24.                 hashmap->map[i].state = DELETED;
  25.                 hashmap->map[i].pair = NULL;
  26.                 hashmap->size --;
  27.             }
  28.         }
  29.         free(hashmap->map);
  30.         hashmap->map = NULL;
  31.     }
  32. }

  34. void free_hashmap(Hashmap_handle_t *hashmap)
  35. {
  36.     delete_hashmap(*hashmap);
  37.     free(*hashmap);
  38.     *hashmap = NULL;
  39. }

  41. char *key_pair(Pair_handle_t pair)
  42. {
  43.     if(pair != NULL)
  44.     {
  45.         return pair->key;
  46.     }
  47.     return NULL;
  48. }

  50. char *value_pair(Pair_handle_t pair)
  51. {
  52.     if(pair != NULL)
  53.     {
  54.         return pair->value;
  55.     }
  56.     return NULL;
  57. }

  59. /*复制散列操作，相当于创建了一个新的散列对象，而不是指针复制*/
  60. Hashmap_handle_t copy_hashmap(Hashmap_handle_t hashmap)
  61. {
  62.     Hashmap_handle_t newhashmap = NULL;
  63.     int i = 0;
  64.     if(hashmap == NULL)
  65.         return NULL;
  66.     
  67.     /*采用动态分配的方式实现*/
  68.     if(!alloc_hashmap(&newhashmap,hashmap->capacity))
  69.         return NULL;
  70.     
  71.     for(; i < hashmap->capacity ; ++ i)
  72.     {
  73.         if(hashmap->map[i].state == ACTIVE)
  74.         {
  75.             /*得到当前中的值实现插入操作*/
  76.             insert_hashnode(newhashmap,
  77.                 hashmap->map[i].pair->key,
  78.                 hashmap->map[i].pair->value);
  79.         }
  80.         else if(hashmap->map[i].state == DELETED)
  81.         {
  82.             newhashmap->map[i].state = DELETED;
  83.         }
  84.     }

  86.     return newhashmap;
  87. }


测试函数：

点击(此处)折叠或打开

  1. #include "hashmap.h"
  2. #include <time.h>

  4. #define CAPACITY    13

  6. char *keys[] = {
  7. "abcd",
  8. "defh",
  9. "abcd",
  10. "12345",
  11. "a1b2c3",
  12. "12345",
  13. "a1b2c3",
  14. "23456",
  15. "hijhk",
  16. "test1",
  17. "test1",
  18. "789123",
  19. "Input",
  20. };

  22. char *values[] = {
  23. "abcd",
  24. "defh",
  25. "abcd",
  26. "12345",
  27. "a1b2c3",
  28. "12345",
  29. "a1b2c3",
  30. "23456",
  31. "hijhk",
  32. "test1",
  33. "test1",
  34. "789123",
  35. "Input",
  36. };

  38. int myhashFunc(const char *key, int Tabsize)
  39. {
  40.         int hashVal = 0;
  41.         int i = 0;

  43.         int len = strlen(key);
  44.         for(; i < len ; ++ i )
  45.                 hashVal += 37 *hashVal + key[i];
  46.     
  47.         hashVal %= Tabsize;

  49.         if(hashVal < 0)
  50.                 hashVal += Tabsize;

  52.         return hashVal;
  53. }
  54.   

  56. int main()
  57. {
  58.     int i = 0;
  59.     char str1[13];
  60.     char str2[13];

  62.     Hashmap_t mymap ;
  63.     Hashmap_handle_t map = NULL;
  64.     Hashmap_handle_t doubmap = NULL;
  65.     
  66.     Pair_handle_t pair;
  67.     /*静态分配*/
  68.     srand((int)time(0));

  70.     printf("init and alloc test:\n");
  71.     if(!init_hashmap(&mymap,13))
  72.     {
  73.         return false;
  74.     }

  76.     /*动态分配*/
  77.     if(!alloc_hashmap(&map,13))
  78.     {
  79.         return false;
  80.     }    
  81.     printf("Sucessed!\n");
  82.     /*插入测试*/
  83.     printf("insert test:\n");
  84.     for(i = 0; i < CAPACITY + 10; ++ i)
  85.     {
  86.         sprintf(str1,"%d%d",rand()%10+1,rand()%10+1);
  87.         sprintf(str2,"%d%d",rand()%10+1,rand()%10+1);
  88.         
  89.         printf("%s->-f(%s)->%d->%s\n",str1,str1,
  90.             myhashFunc(str1,CAPACITY),str2);

  92.     //    sprintf(str1,"%s",keys[i]);
  93.     //    sprintf(str2,"%s",values[i]);
  94.         if(!insert_hashnode(&mymap,str1,str2))
  95.         {
  96.             printf("i = %d, insert to mymap failed\n", i);
  97.             break;
  98.         }
  99.         if(!insert_hashnode(map,str1,str2))
  100.         {
  101.             printf("i = %d, insert to map failed\n", i);
  102.             break;
  103.         }
  104.     }    
  105.     printf("Sucessed!\n");
  106.     /*查找测试*/
  107.     printf("search test:\n");
  108.     if((pair = search_hashnode(&mymap,str1)) != NULL)
  109.     {
  110.         printf("%s->%s\n",key_pair(pair),value_pair(pair));
  111.     }
  112.     if((pair = search_hashnode(map,str1)) != NULL)
  113.     {
  114.         printf("%s->%s\n",key_pair(pair),value_pair(pair));
  115.     }
  116.     printf("Sucessed!\n");
  117.     
  118.     /*delete*/
  119.     printf("delete test:\n");
  120.     if(delete_hashnode(&mymap,str1))
  121.     {
  122.         printf("Deleted success!!\n");
  123.     }
  124.     else
  125.     {
  126.         printf("Sorry, Failed!!\n");
  127.     }
  128.     if(delete_hashnode(map,str1))
  129.     {
  130.         printf("Deleted success!!\n");
  131.     }
  132.     else
  133.     {
  134.         printf("Sorry, Failed!!\n");
  135.     }
  136.     
  137.     printf("Valid length : %d, Capacity : %d\n",
  138.         Length(&mymap),Capacity(&mymap));
  139.     printf("Valid length : %d, Capacity : %d\n",
  140.         Length(map),Capacity(map));
  141.     
  142.     /*改变长度*/
  143.     printf("resize test:\n");
  144.     if(resize(&mymap))
  145.         printf("Sucessed!\n");
  146.     if(resize(map))    
  147.         printf("Sucessed!\n");

  149.     /*长度*/
  150.     printf("Valid length : %d, Capacity : %d\n",
  151.         Length(&mymap),Capacity(&mymap));
  152.     printf("Valid length : %d, Capacity : %d\n",
  153.         Length(map),Capacity(map));

  155.     printf("Valid length : %d, Capacity : %d\n",
  156.         Length(&mymap),Capacity(&mymap));
  157.     printf("Valid length : %d, Capacity : %d\n",
  158.         Length(map),Capacity(map));
  159.     
  160.     printf("copy test:\n");
  161.     doubmap = copy_hashmap(&mymap);
  162.     printf("Valid length : %d, Capacity : %d\n",
  163.         Length(doubmap),Capacity(doubmap));
  164.     printf("Sucessed!\n");
  165.     
  166.     /*释放内存*/
  167.     printf("free test:\n");
  168.     delete_hashmap(&mymap);
  169.     free_hashmap(&map);
  170.     free_hashmap(&doubmap);
  171.     printf("Valid length : %d, Capacity : %d\n",
  172.         Length(&mymap),Capacity(&mymap));
  173.     printf("Sucessed!\n");
  174.     
  175.     return 0;
  176. }
测试结果：

点击(此处)折叠或打开

  1. [gong@Gong-Computer newversion]$ ./main
  2. init and alloc test:

  4. insert test:
  5. 48->-f(48)->4->49
  6. 108->-f(108)->5->910
  7. 78->-f(78)->1->98
  8. 87->-f(87)->12->73
  9. 36->-f(36)->3->109
  10. 59->-f(59)->4->98
  11. 32->-f(32)->12->48
  12. 210->-f(210)->10->91
  13. 105->-f(105)->2->22
  14. 41->-f(41)->10->82
  15. 1010->-f(1010)->11->69
  16. 19->-f(19)->8->64
  17. 25->-f(25)->3->45
  18. 28->-f(28)->6->104
  19. 16->-f(16)->5->83
  20. 44->-f(44)->0->86
  21. 85->-f(85)->10->72
  22. 51->-f(51)->9->27
  23. 54->-f(54)->12->57
  24. 107->-f(107)->4->210
  25. 73->-f(73)->9->27
  26. 1010->-f(1010)->11->61
  27. 63->-f(63)->10->63

  29. search test:
  30. 63->63
  31. 63->63

  33. delete test:
  34. Deleted
  35. Deleted
  36. Valid length : 21, Capacity : 29
  37. Valid length : 21, Capacity : 29
  38. resize test:


  41. Valid length : 21, Capacity : 59
  42. Valid length : 21, Capacity : 59
  43. Valid length : 21, Capacity : 59
  44. Valid length : 21, Capacity : 59
  45. copy test:
  46. Valid length : 21, Capacity : 59

  48. free test:
  49. Valid length : 0, Capacity : 59
从实验效果可知，基本上实现了散列的基本操作。








阅读(4668) | 评论(0) | 转发(3) |
0

上一篇：error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__‘问题解决

下一篇：比较型排序算法总结

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6