NOJ-構造哈希表-西工大資料結構

    今天上課講了哈希表，回來寫了一下。題目如下：

    看一下題，他說用最簡單的方法建一個最簡單的哈希表，然後輸出平均查找長度，毫無難度。。。

    我哈希表用了一個struct指針，如果要存東西，就申請一個節點并把節點位址塞裡面，否則就是NULL，可以節省一點空間（雖然毫無必要。。。）。

    我步數在建表的時候就算完了，最後算個和就行，當然也可以單純建表，然後查找并記錄步數，再求和，其實都差不多。。。 

    我的實作如下：

#include <stdio.h>
#include <stdlib.h>

struct hashTableNode
{
    int data;
    int flag;
};

struct hashTableNode *T[11];
int dataList[8] = {22, 41, 53, 46, 30, 13, 01, 67};

void run();
void getHashTable();
int H(int data);
struct hashTableNode *createHashTableNode(int data, int flag);
void putOutAverageSearchLength();

int main()
{
    run();
    return 0;
}

void run()
{
    getHashTable();
    putOutAverageSearchLength();
}

void getHashTable()
{
    int i, pos, flag;
    for(i = 0; i <= 7; i++)
    {
        flag = 1;
        pos = H(dataList[i]);
        while(T[pos] != NULL) ++pos, ++flag;
        T[pos] = createHashTableNode(dataList[i], flag);
    }
}

int H(int data)
{
    return (3 * data) % 11;
}

struct hashTableNode *createHashTableNode(int data, int flag)
{
    struct hashTableNode *p;
    p = (struct hashTableNode *)malloc(sizeof(struct hashTableNode));
    p->data = data;
    p->flag = flag;
    return p;
}

void putOutAverageSearchLength()
{
    int i, sum;
    for(i = 0, sum = 0; i <= 10; i++)
    {
        if(T[i] != NULL)
        {
            sum += T[i]->flag;
        }
    }
    printf("%d\n", sum / 8);
}
           

    以下是各函數的注釋：

void run()
{
    getHashTable();//建立哈希表
    putOutAverageSearchLength();//輸出查找平均長度
}
           

void getHashTable()
{
    int i, pos, flag;
    for(i = 0; i <= 7; i++)//周遊關鍵字序列
    {
        flag = 1;//初始查找步數為1；
        pos = H(dataList[i]);//通過哈希映射函數後的位置
        while(T[pos] != NULL) ++pos, ++flag;//找到映射位置起的第一個空位，同時增加查找步數
        T[pos] = createHashTableNode(dataList[i], flag);//建立節點塞進去
    }
}
           

int H(int data)
{
    return (3 * data) % 11;//哈希映射函數
}
           

struct hashTableNode *createHashTableNode(int data, int flag)
{
    struct hashTableNode *p;
    p = (struct hashTableNode *)malloc(sizeof(struct hashTableNode));//建立節點并指派
    p->data = data;
    p->flag = flag;
    return p;
}
           

void putOutAverageSearchLength()
{
    int i, sum;
    for(i = 0, sum = 0; i <= 10; i++)//周遊哈希表
    {
        if(T[i] != NULL)//非空
        {
            sum += T[i]->flag;//步數和增加
        }
    }
    printf("%d\n", sum / 8);//輸出平均
}
           

    以上就是我的實作。