自己写的一个哈希表的实现

现在的位置: 首页 > 综合 > 正文

RSS

自己写的一个哈希表的实现

2013年10月07日 ⁄ 综合 ⁄ 共 6053字 ⁄ 字号小中大 ⁄ 评论关闭

哈希表是数组、链表及数学算法的一个综合应用，无论在理论上还是实践上都是非常有价值的。废话不多说了，贴上自己的实现吧，以供参考，有错误之处，恳请指出。还需要做的一个工作是，为实现中用到的链表和哈希表设计详尽苛刻的测试。

该哈希表包括四个文件： common.h , LinkList.c, Hashtable.c , main.c . 将它们放在同一个文件夹中，按照下面的方式编译运行

$ gcc -Wall *.c -o main

$ main

或者一个简单的 makefile 文件：

OBJS = Hashtable.o main.o LinkList.o
mhash: $(OBJS)
[tab]cc -o mhash $(OBJS)
HashSearch.o: Hashtable.c common.h
[tab]cc -c Hashtable.c
main.o: main.c common.h
[tab]cc -c main.c
LinkList.o: LinkList.c common.h
[tab]cc -c LinkList.c
.PHONY: clean
clean:
[tab]-rm $(OBJS) mhash

$ make

$ mhash

下面是各个文件的具体实现：

common.h

/*
 * common.h
 * 关于哈希查找和链表结构的声明和定义。
 *
 * 哈希查找法： 
 * 采用字符串散列函数的哈希函数和链地址法的冲突解决方案
 *
 */

enum { OK = 1, ERROR = 0, TRUE = 1, FALSE = 0, FAILURE = 1, LEN_OF_TABLE = 13, RECORD_NUM = 95 }; 

typedef struct {          /* 记录类型 */
         char  *key;
	 int   value; 
} Record;

typedef struct node *LLNptr;

typedef struct node {     /*  链表结点类型 */
     Record  data;
     LLNptr  next;  
} LLNode;

typedef int  Status;

/* 单链表的函数声明，主要依照严蔚敏老师《数据结构C语言版》中的描述 */
 
Status  InitList(LLNptr *list);              /* 创建带头结点的单链表 */    
int     IsEmpty(LLNptr list);                /* 判断单链表是否为空   */
int     ListLength(LLNptr list);             /* 返回链表长度，即记录的数目(不含头结点) */
Status  GetRecord(LLNptr list, int i, Record *e);      /* 返回链表中第 i 个位置上的结点，并保存在 e 中 */
Status  ListInsert(LLNptr list, int i, Record e);      /* 将记录 e 插入到链表 list 中的第 i 个位置上 */
Status  ListDelete(LLNptr list, int i, Record *e);     /* 将链表 list 中的第 i 个位置上的记录删除，并用 e 返回 */
Status  ListTraverse(LLNptr list, void (*visit)(Record *e));  /* 使用 visit 遍历链表 */
Status  ListPrint(LLNptr list);                        /* 打印链表内容 */      
void  printRecord(Record *e);                          /* 打印记录内容 */
int   Equal(Record *e1, Record *e2);                   /* 判断记录的相等性 */

/* 返回链表 list 中与 e 满足 compare 关系的记录的指针; 如果不存在，返回 NULL */
Record*  PLocateRecord(LLNptr list, Record e, int (*compare)(Record *e1, Record *e2));

/* 哈希查找的函数声明  */

int hash(char* key);     /* 计算关键字的哈希值 */
Status InitTable(LLNptr hashtable[]);    /* 初始化哈希表 hashtable */
Status HashInsert(LLNptr hashtable[], Record e);   /* 将记录插入哈希表 hashtable 中 */
Record* HashSearch(LLNptr hashtable[], Record e);      /* 根据记录关键字查找：若有则返回指向该记录的指针，否则返回 NULL */
Status HashTraverse(LLNptr hashtable[]);           /* 遍历哈希表 */

LinkList.c

/*  LinkList.c  */
/*  带头结点的单链表实现，头结点存储表长信息  */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "common.h"

Status  InitList(LLNptr* list)
{ 
	 LLNptr head = (LLNptr)malloc(sizeof(LLNode));
	 if (!head) {
         	  fprintf(stderr, "Error: fail to allocate memory!\n"); 
         	  return ERROR;
         }         
	 head->data.value = 0;      /* 头结点的 value 域存储表长 */  
         head->data.key = NULL;     /* 头结点的 key 域 未用     */  
	 head->next = NULL;
         *list = head;
	 return  OK;	
}  

int  IsEmpty(LLNptr list)
{
	return list->data.value == 0;
}

int  ListLength(LLNptr list)
{
	return list->data.value;
}

Status GetRecord(LLNptr list, int i, Record *e)
{
	  /* 取得表list中的第i个元素， 并用e返回 */
	  
	  LLNptr p = list->next;   /* p 指向第一个记录结点 */
	  
          if (IsEmpty(list)) {
	  	 fprintf(stderr, "Error: list empty!\n");
	  	 return  ERROR;
	  }
	  if (i < 1 || i > ListLength(list)) {
	  	 fprintf(stderr, "Error: position parameter %d out of range!\n", i);
	  	 return  ERROR;
	  }
	  while(--i) p = p->next;  /* p 指向第i个元素 */
	  *e = p->data;
	  return OK;   
}

Record* PLocateRecord(LLNptr list, Record e, int (*compare)(Record *e1, Record *e2))
{
	  
	  /* 返回表list中与给定元素e满足compare关系的记录指针 */
	  
	  LLNptr p = list->next;
	   
	  while (p) {
	     if (compare(&p->data, &e))
	  	  return &p->data;
	     p = p->next;
	  }
	  return NULL;	  
}	

Status  ListInsert(LLNptr list, int i, Record e)
{
	  /* 将记录 e 插入表list中的第 i 个位置上 */
	
	  LLNptr s, p = list;
	  int j = 0;    /* j 作计数器 */
	  
          if (i < 1 || i > ListLength(list)+1) {
	  	 fprintf(stderr, "Error: position parameter %d out of range!\n", i);
	  	 return  ERROR;
	  }
	  while (p && j < i-1) { p = p->next; j++; }
	  s = (LLNptr)malloc(sizeof(LLNode));
	  if (!s) {
	  	  fprintf(stderr, "Error: fail to allocate memory!\n");
	  	  return ERROR;
	  }
	  s->data = e; s->next = p->next;
	  p->next = s;
	  list->data.value++;
	  return OK;
}

Status  ListDelete(LLNptr list, int i, Record *e)
{
	  /* 删除表list中的第i个位置上的记录，并用 e 返回 */
	  
	  LLNptr p1 = list;
	  LLNptr p2;
	  int j = 0;  /* j 作计数器 */
	  
	  if (IsEmpty(list)) {
	  	 printf("Error: list empty!\n");
	  	 return  ERROR;
	  }
	  if (i < 1 || i > ListLength(list)) {
	  	 printf("Error: invalid index!\n");
	  	 return  ERROR;
	  }
	  while (p1->next && j < i-1) { /* p1 指向第 i-1 个元素 */
	  	  p1 = p1->next;
	  	  j++;
	  }
	  p2 = p1->next;         /* p2 指向第 i 个元素 */
          *e = p2->data;
          p1->next = p2->next;
          free(p2);
          list->data.value--;
	  return OK;
	  
}

Status  ListTraverse(LLNptr list, void (*visit)(Record *e))
{
	/* 用visit函数遍历表list中的元素有且仅有一次 */
	
	 LLNptr p = list->next;
	 
	 if (IsEmpty(list)) {
	  	 printf("list empty!\n");
	  	 return  ERROR;
	  }
	 while (p) {
	 	 visit(&p->data);
	 	 p = p->next;
	 }
	 return OK;
}

Status ListPrint(LLNptr list)
{
    return ListTraverse(list, printRecord);
}

void  printRecord(Record *e)
{
	 printf("(%s, %d)\n", e->key, e->value);
}

int   Equal(Record *e1, Record *e2)
{
	 return strcmp(e1->key,e2->key)==0;
}

Hashtable.c

// Hashtable.c
// 哈希函数的实现

#include <stdio.h>
#include "common.h" 

int hash(char* key)
{
	 char *p = key;
         int hash = 17;
         while (*p) {
            hash = hash * 37 + (*p);
            p++;
         }
         printf("key = %s\thash = %d , hash %% %d = %d\n" , key, hash, LEN_OF_TABLE, hash % LEN_OF_TABLE);
	 return hash % LEN_OF_TABLE;
}

Status InitTable(LLNptr table[])
{
	 int i;
	 for (i = 0; i < LEN_OF_TABLE; i++) {
	    if (!InitList(&table[i])) {
                return ERROR;
            }
	 }
	 return OK;
}

Status HashInsert(LLNptr table[], Record e)
{      
	 int t_index = hash(e.key);
         if (PLocateRecord(table[t_index], e, Equal)) {  /* 哈希表中已存在该记录 */
             printf("Record exists, nothing to do.");
             return OK;
         }
	 int ins_pos = ListLength(table[t_index]) + 1;
	 if (!ListInsert(table[t_index], ins_pos, e)) {
             return ERROR;
         } 
	 return OK;
}

Record* HashSearch(LLNptr table[], Record e)
{  
	 int t_index = hash(e.key);
	 return PLocateRecord(table[t_index], e, Equal);
}

Status HashTraverse(LLNptr table[])
{
	int i;
        printf("The hash table:\n");
	for (i = 0; i < LEN_OF_TABLE; i++) {
           printf("List[%d]:\n", i); 
	   ListPrint(table[i]);
	   printf("\n");
	}
	return OK; 
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "common.h"

char* toString(int i);

int main()
{
         printf("Program start up ...\n");
        
	 /* 表长为LEN_OF_TABLE的哈希表，每个元素为一个单链表指针 */
         LLNptr hashtable[LEN_OF_TABLE];
         
         Record rds[RECORD_NUM];
         Record* pe;
         Record* qe;
	 int i;

	 if (!InitTable(hashtable)) {
	    fprintf(stderr, "Error: fail to initialize the hashtable!\n");
	    exit(FAILURE);
	 }

         printf("initialize the hashtable successfully!\n");
         HashTraverse(hashtable);
  
         for (i = 0; i < RECORD_NUM; i++) {
              rds[i].key = toString(i);
              rds[i].value = i;
              printf("Record: (%s %d) \n", rds[i].key, rds[i].value);
              printf("prepare to insert ...");
              if (!HashInsert(hashtable, rds[i])) {
                 printf("failed to insert record!");
              }    
         }
	 HashTraverse(hashtable);

         pe = (Record* ) malloc(sizeof(Record));
         pe->key = "11111";
         qe = HashSearch(hashtable, *pe);
         if (qe != NULL) {
            printRecord(qe);
         }
         else {
            printf("Record Not Found.\n");
         }
         
         pe->key = "11112";
         qe = HashSearch(hashtable, *pe);
         if (qe != NULL) {
            printRecord(qe);
         }
         else {
            printf("Record Not Found.\n");
         } 

	 return 0;
}

char* toString(int i)
{
   char *p = (char *)malloc(5*sizeof(char) + 1);
   char *q;
   if (!p) {
      fprintf(stderr, "Error, fail to allocate memory.");
      exit(FAILURE);
   }
   q = p;
   while (q < p+5) {
       *q = i + ' ';
       q++;   
   }
   *q = '\0';
   return p;
}

【上篇】基金理财学会借基生蛋
【下篇】别为大公司拼命

作者: capping

该日志由 capping 于11年前发表在综合分类下，最后更新于 2013年10月07日.
转载请注明: 自己写的一个哈希表的实现 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

自己写的一个哈希表的实现

作者: capping

书签

最新文章New

本站推荐

返回首页