hash table(哈希表)的拉链法程序

哈希表拉链法，简单，直接看代码：

#include <iostream>
using namespace std;

struct Node
{
    int iData;
    Node* pNext;
};

#define N 10
typedef Node* HashTable[N]; // 指针数组
HashTable hTable;


void createHashTable(int a[], int n)
{
    memset(hTable, 0, sizeof(hTable));

    int i = 0;
	int iRes = 0;
    for(i = 0; i < n; i++)
    {
        iRes = a[i] % N;

        if(NULL == hTable[iRes])
        {
            hTable[iRes] = new Node;
            hTable[iRes]->iData = a[i];
            hTable[iRes]->pNext = NULL;
        }
        else
        {
			Node *p = hTable[iRes];
            while(NULL != p->pNext)
			{
			    p = p->pNext;	
			}

			// 插到尾部
            p->pNext = new Node;
            p->pNext->iData = a[i];
            p->pNext->pNext = NULL;
        }
    }
}


void printHashTable()
{
	int i = 0;
	Node *p = NULL;
	for(i = 0; i < N; i++)
	{
		p = hTable[i];
		if(NULL != p)
		{
			cout << i << ": ";
			while(NULL != p)
			{
				cout << p->iData << " ";
				p = p->pNext;
			}

			cout << endl;
		}
		else
		{
			cout << i << ": no data" << endl;
		}
	}
}


bool hashTableSearch(int x)
{
    //查找，不要改变hTable链表
    int iRes = x % N;
	Node *p = hTable[iRes];
	while(NULL != p)
	{
		if(x == p->iData)
		{
			return true;
		}

		p = p->pNext;
	}
   
	return false;
}


int main()
{
    int a[] = {33, 24, 12, 41, 22, 3, 6, 1, 19, 2, 17, 0, 14, 123, 32, 666};
	int n = sizeof(a) / sizeof(a[0]);

    createHashTable(a, n);
	printHashTable();

	int i = 0;
	for(i = 0; i < 1000; i++)
	{
		if(hashTableSearch(i)) 
		{
			cout << i << " ";
		}
	}

	cout << endl;

    return 0;
}

结果：

0: 0 1: 41 1 2: 12 22 2 32 3: 33 3 123 4: 24 14 5: no data 6: 6 666 7: 17 8: no data 9: 19 0 1 2 3 6 12 14 17 19 22 24 32 33 41 123 666

很好理解， 不多说。