散列表又叫哈希表，它是为了减少搜索空间，但又考虑到时间上设立的。
http://codeplayer.org/2013/11/210 参考网页
#include <stdlib.h>#include <stdio.h> #define m 17//#define HASH(k) k % m //除法散列法 #define A 0.85//#define HASH(k) (int)(m * (k * A - (int)(k * A))) //乘法散列法 #define c1 7#define c2 5//#define h(k, i) (HASH(k) + i) % m //线性探查//#define h(k, i) (HASH(i) + c1 * i + c2 * i * i) % m //二次探查 #define h1(k) k % m#define h2(k) 1 + (k % (m - 1))#define h(k, i) (h1(k) + i * h2(k)) % m //双重散列 #define DEL -65535 inthash_insert(int *T, int k){ /* * 在散列表中插入一个元素，不断的探查 * 以找到一个空槽可以插入，或者探查了 * 整个散列表，输出错误信息并退出 */ int i, j; for (i = 0; i != m; i++) { j = h(k, i); if (T[j] == NULL || T[j] == DEL) { T[j] = k; return(j); } } fprintf(stderr, "hash table overflow\n"); exit(1);} inthash_search(int *T, int k){ /* * 在散列表中查找一个元素，不断进行 * 探查，直到找到该元素，或者探查到 * 了一个空槽，或者找遍了整个散列表 */ int i, j; for (i = 0; i != m; i++) { j = h(k, i); if (T[j] == k) { printf("found value: %d in key: %d\n", k, j); return(j); } else if (T[j] == NULL) { break; } } fprintf(stderr, "can't find value: %d\n", k); return(NULL);} inthash_delete(int *T, int k){ /* * 删除一个元素的时候并不将它置为NULL， * 因为这有可能会使得在查找的时候找不到 * 后续的元素，查找在删除的地方就中断了。 * 可以在删除的时候将其置为一个特殊的值， * 以避免这种情况。这里用的是DEL。 */ int i, j; for (i = 0; i != m; i++) { j = h(k, i); if (T[j] == k) { T[j] = DEL; return(0); } } fprintf(stderr, "can't find %d in hashtable\n", k); exit(1);} voidprint_hash(int *T){ int i; printf("---------------hashtable---------------\n"); for (i = 0; i < m; i++) { if (T[i] != NULL && T[i] != DEL) printf("key: %2d, value: %4d\n", i, T[i]); else printf("key: %2d, value: NULL\n", i); } printf("------------------end------------------\n\n");} intmain(void){ /* * 用数组实现的简单的开放寻址法的散列表 */ int i; int T[m]; for (i = 0; i < m; i++) { T[i] = NULL; } hash_insert(T, 28); hash_insert(T, 438); hash_insert(T, 923); hash_insert(T, 239); hash_insert(T, 29); hash_insert(T, 31); hash_insert(T, 32); hash_insert(T, 39); hash_insert(T, 2); hash_insert(T, 24); hash_insert(T, 432); print_hash(T); hash_delete(T, 239); hash_delete(T, 31); hash_delete(T, 28); printf("\nafter delete 239, 31, 28...\n\n"); print_hash(T); hash_search(T, 438); hash_search(T, 239); exit(0);}
#include<iostream>#include<string>#define m 17#define A 0.85#define c1 7#define c2 5#define h1(k) k%m#define h2(k) 1+(k%(m-1))#define h(k,i) (h1(k) + i * h2(k)) % m //#define h(k,i) (h1(k)+i)%m //这是一个一次线性查找。#define DEL -65535int hash_insert(int *T,int k){ //插入数据，得找位置进行插入。 int i,j; for(int i=0;i<m; i++){ j=h(k,i); if(T[j]==NULL||T[j]==DEL){ //因为如果中间我们删了一些数据，那么我们标为DEL了，于是我们就可以再在这里插入。 T[j]=k; return (j); } } if(i==m){//如果数组越界，则结束。 std::cout<<"error,out of range"<<std::endl; return DEL; }}bool hash_search(int *T,int k){ //这里我们进行查找 int i=0,j; for(int i=0;i<m; i++){ j=h(k,i); if(T[j]==k){ //如果找到就可以了，找不到就返回 std::cout<<j<<std::endl; return true; } else if(T[j]=NULL){// 如果找到一个NULL，因为我们插入是“顺序”插入的，因此找到一个NULL，则后面也是没有了的。 break; } } if(i==m||T[j]==NULL){ std::cout<<"not found"<<std::endl; return false; }}bool delete_Hash(int *T,int k){ int i,j; for(int i=0;i<m; i++){ j=h(k,i); if(T[j]==k){ T[j]=DEL; //用特殊符号进行标志，说明这里删除了一个数。 return true; } } if(i==m){ //如果越界了，则说明数组完了。 std::cout<<"not found"<<std::endl; return false; }}void hash_print(int *T){ for(int i=0;i<m; i++){ std::cout<<T[i]<<","; } std::cout<<std::endl; }int main(){ int i; int T[m]; for (i = 0; i < m; i++) { T[i] = NULL; } hash_insert(T, 28); hash_insert(T, 438); hash_insert(T, 923); hash_insert(T, 239); hash_insert(T, 29); hash_insert(T, 31); hash_insert(T, 32); hash_insert(T, 39); hash_insert(T, 2); hash_insert(T, 24); hash_insert(T, 432); std::cout<<hash_search(T,2)<<std::endl; hash_print(T); hash_search(T,11); }
来自为知笔记(Wiz)
转载于:https://www.cnblogs.com/yml435/p/4655565.html
相关资源：数据结构—成绩单生成器
