求解，数据结构与算法

Answer 1

关键字序列是{19,13,33,02,16,24,7},计算过程如下:

插入关键字19, ç´¢å¼•(哈希值) = 19 mod 11 = 8, å­˜å…¥å“ˆå¸Œè¡¨:

  ä¸‹æ ‡    0   1   2   3   4   5   6   7   8   9   10
  å…³é”®å­—                                 19

插入关键字13, ç´¢å¼•(哈希值) = 13 mod 11 = 2, å­˜å…¥å“ˆå¸Œè¡¨:
 
  ä¸‹æ ‡    0   1   2   3   4   5   6   7   8   9   10
  å…³é”®å­—         13                      19

插入关键字33, ç´¢å¼•(哈希值) = 33 mod 11 = 0, å­˜å…¥å“ˆå¸Œè¡¨:

  ä¸‹æ ‡    0   1   2   3   4   5   6   7   8   9   10
  å…³é”®å­— 33      13                      19

插入关键字02, ç´¢å¼•(哈希值) = 02 mod 11 = 2, æœ‰å†²çª,取新索引2+1=3,没有冲突,存入哈希表:

  ä¸‹æ ‡    0   1   2   3   4   5   6   7   8   9   10
  å…³é”®å­— 33      13   2                  19

插入关键字16, ç´¢å¼•(哈希值) = 16 mod 11 = 5, å­˜å…¥å“ˆå¸Œè¡¨:

  ä¸‹æ ‡    0   1   2   3   4   5   6   7   8   9   10
  å…³é”®å­— 33      13   2      16          19

插入关键字24, ç´¢å¼•(哈希值) = 24 mod 11 = 2, æœ‰å†²çª,取索引2+1=3,仍有冲突,
再取索引3+1=4,没有冲突,存入哈希表:

  ä¸‹æ ‡    0   1   2   3   4   5   6   7   8   9   10
  å…³é”®å­— 33      13   2  24  16          19

插入关键字7, ç´¢å¼•(哈希值) = 7 mod 11 = 7, å­˜å…¥å“ˆå¸Œè¡¨:

  ä¸‹æ ‡    0   1   2   3   4   5   6   7   8   9   10
  å…³é”®å­— 33      13   2  24  16       7  19

这就是最后得到的哈希表.


//C语言测试程序
#include<stdio.h>
#include<stdlib.h>

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 11
#define NULLKEY -1
typedef int Status;

typedef struct
{
    int *elem;
    int count;
}HashTable;

int m=0;

Status InitHashTable(HashTable *H)
{
    int i;
    m=HASHSIZE;
    H->count=m;
    H->elem=(int *)malloc(m*sizeof(int));
    for(i=0;i<m;i++)
    {
        H->elem[i]=NULLKEY;
    }
    return SUCCESS;
}

int Hash(int key)
{
    return key % m;
}

void InsertHash(HashTable *H,int key)
{
    int addr;
    int pos;
    pos=Hash(key);
    addr=pos;
    while(H->elem[addr] != NULLKEY)
    {
        ////////
        printf("索引=%d æœ‰å†²çª.\n",addr);
        ////////
        addr = (addr+1) % m;
        if(addr==pos)
        {
            printf("\n散列表已满!\n");
            exit(1);
        }
    }
    H->elem[addr]=key;
}

Status SearchHash(HashTable H,int key,int *addr)
{
    *addr = Hash(key);
    while(H.elem[*addr] != key)
    {
        *addr = (*addr+1) % m;
        if(H.elem[*addr]==NULLKEY || *addr==Hash(key))
        {
            return UNSUCCESS;
        }
    }
    return SUCCESS;
}

void showHashTable(HashTable *H)
{
    int i;
    for(i=0 ; i < H->count ;i++)
    {
        printf("%4d",i);
    }
    printf("\n");
    for(i=0 ; i < H->count ;i++)
    {
        if(H->elem[i]==NULLKEY)
        {
            printf("%4c",0x20);
        }
        else
        {
            printf("%4d",H->elem[i]);
        }
    }
    printf("\n");
}

int main()
{
    int key[]={19,13,33,02,16,24,7}; 

    int len;
    int i;
    HashTable H;

    InitHashTable(&H);

    len=sizeof(key)/sizeof(key[0]);
    for(i=0;i<len;i++)
    {
        printf("插入 %d, ç´¢å¼•(Hash) = %d\n",key[i],Hash(key[i]));
        InsertHash(&H,key[i]);
        showHashTable(&H);
    }

return 0;
}