看算法导论补了一下散列表,也就是hash表,hash表还是很好用的,兼顾了空间和时间,查找操作只要O(n/m),基本的难点在散列函数这里,全域散列这里看不太懂,初步敲了一下除法散列法和乘法散列法的实现,基本没啥好说的,看完开放寻址法以后找两道OJ题做做。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int hashnum = 7;
const double multipy = (sqrt(5.0) - 1) / 2;struct hashnode
{int data;hashnode *next;
};
struct hashlist
{int count;hashnode *front;
};
hashlist HASH[hashnum];int HashFunction(int num);
void Initialization();
void HashInsert(int num);
void HashSearch(int num);
void HashPrint();int main()
{int n,num;cout << "Enter the total number of what your want to enter" << endl;cin >> n;int *a = new int[n];Initialization();for (int i = 0; i < n; i++){cin >> a[i];HashInsert(a[i]);}HashPrint();cout << "Enter the number you want to search" << endl;cin >> num;HashSearch(num);delete[] a;return 0;
}int HashFunction(int num)//除法散列法or乘法散列法
{//return num%hashnum;double A = num*multipy - (int)(num*multipy);return (int)(hashnum*A);
}
void Initialization()
{for (int i = 0; i < hashnum; i++){HASH[i].count = 0;HASH[i].front = NULL;}
}
void HashInsert(int num)
{int pos = HashFunction(num);hashnode *p = new hashnode;HASH[pos].count++;p->data = num;p->next = HASH[pos].front;HASH[pos].front = p;
}
void HashSearch(int num)
{int pos = HashFunction(num);hashnode *p=HASH[pos].front;bool result = false;while (p!=NULL){if (p->data == num){result = true;break;}p = p->next;}if (result)cout << "This number is existed" << endl;elsecout << "The list does not has this number" << endl;
}
void HashPrint()
{for (int i = 0; i < hashnum; i++){hashnode *p = HASH[i].front;cout << "NO "<<i << " has "<<HASH[i].count<<" numbers :";while (p!=NULL){cout << p->data<<" ";p = p->next;}cout << endl;}
}