//拉链法

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

#define DATATYPE int
#define FORM "%d"
#define MAX 17

typedef struct TableNode
{
    DATATYPE data;
    struct TableNode *next;
} TNode;

int InsertNode(TNode **T,DATATYPE elem)
{
    TNode *temp=NULL;
    if(*T==NULL)
    {
        *T=(TNode *)malloc(sizeof(TNode));
        if(*T==NULL) return 0;
        (*T)->data=elem;
        (*T)->next=NULL;
        return 1;
    }
    temp=*T;
    while(temp->next) temp=temp->next;
    if((temp->next=(TNode *)malloc(sizeof(TNode)))==NULL) return 0;
    temp->next->data=elem;
    temp->next->next=NULL;

    return 1;
}

int search(TNode *T,DATATYPE elem)
{
    if(!T) return 0;

    while(T)
    {
        if(T->data==elem)
            return 1;
        T=T->next;
    }
    return 0;
}

int main()
{
    int i=0;
    DATATYPE elem;
    TNode *HashTable[MAX];

    memset(HashTable,NULL,sizeof(HashTable));
    printf("开始添加元素...\n");
    while(i<100000)
    {
        //if(scanf(FORM,&elem)!=1) break;
        i++;
        srand(i);
        elem=rand();
        if(!InsertNode(&HashTable[elem%MAX],elem))
        {
            printf("元素添加失败!\n");
            break;
        }
        printf("已添加%d个元素。\r",i);
    }
    while(1)
    {
        printf("请输入要查询的元素:");
        fflush(stdin);
        if(scanf(FORM,&elem)!=1)
        {
            printf("输入有误,");
            continue;
        }
        if(search(HashTable[elem%MAX],elem))
        {
            printf("在第%d个表内找到元素!\n",elem%MAX+1);
            getch();
        }
        else
        {
            printf("没找到此元素。\n");
            if(!InsertNode(&HashTable[elem%MAX],elem))
                printf("添加失败。\n");
            else
                printf("已添加。\n");
            getch();
        }
    }

    return 0;
}

 

 

 

//线性探测再散列

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

#define MAX_LENGTH 11
#define DATATYPE int

const char *NAME[]= {"aa","bb","cc","dd","ee","ff","gg","hh","ii","j","kk"};
const char *BIRTHDAY[]= {"1993.5.9","1993.12.30","1993.1.7","1991.10.21","1992.11.12","1994.9.2","1990.3.2",\
                         "1992.11.2","1993.1.12","1993.11.2","1993.12.2",
                        };

typedef struct
{
    char name[10];
    char birthday[15];
} Friend;

void importInfo(Friend *table)
{
    int i,j,n;
    Friend temp;

    for(i=0; i<MAX_LENGTH; i++)
    {
        memset(&temp,NULL,sizeof(Friend));
        memcpy(temp.name,NAME[i],strlen(NAME[i]));
        memcpy(temp.birthday,BIRTHDAY[i],strlen(BIRTHDAY[i]));
        for(j=n=0; j<strlen(temp.name); j++)
            n+=temp.name[j];
        if(*(char *)&table[n%MAX_LENGTH]==NULL)
        {
            printf("无冲突:%s\n",temp.name);
            //当前元素值为空
            table[n%MAX_LENGTH]=temp;
        }
        else
        {
            printf("有冲突:%s\n",temp.name);
            //线性探测再散列
            j=n%MAX_LENGTH;
            do
            {
                j++;
                if(j==MAX_LENGTH)
                    j=0;
                if(*(char *)&table[j]==NULL)
                {
                    table[j]=temp;
                    break;
                }
            }
            while(j!=n%MAX_LENGTH);
        }
    }
    return;
}

int CreateHashTable(Friend **table)
{
    *table=(Friend *)malloc(sizeof(Friend)*MAX_LENGTH);
    if(!*table) return 0;
    memset(*table,NULL,sizeof(Friend)*MAX_LENGTH);
    importInfo(*table);

    return 1;
}

Friend *search(Friend *table,char *name)
{
    int i,n;

    for(i=n=0; i<strlen(name); i++)
        n+=name[i];

    if(!strcmp(table[n%MAX_LENGTH].name,name))
        return &table[n%MAX_LENGTH];

    i=n%MAX_LENGTH;
    do
    {
        i++;
        if(i==MAX_LENGTH)
            i=0;
        if(!strcmp(table[i].name,name))
            return &table[i];
    }
    while(i!=n%MAX_LENGTH);

    return NULL;
}

int main()
{
    Friend *HashTable=NULL,*find=NULL;
    char str[20];

    CreateHashTable(&HashTable);
    int i;
    for(i=0; i<11; i++)
        printf("%s\n",HashTable[i].name);
    printf("请输入查找人的姓名:");
    fflush(stdin);
    gets(str);
    if(find=search(HashTable,str))
        printf("在Hash表中找到，生日是:%s\n",find->birthday);
    else
        printf("在Hash表中不存在。\n");

    return 0;
}


 

 

 

 

打赏

微信扫一扫，打赏作者吧～