数据结构，在线求答案

Question

如题所述

Answer 1

关键字序列是{23,36,16,28,40,87,49,60,62},计算过程如下:

插入关键字23, 索引(哈希值) = 23 % 11 = 1, 存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23                          

插入关键字36, 索引(哈希值) = 36 % 11 = 3, 存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23      36

插入关键字16, 索引(哈希值) = 16 % 11 = 5, 存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23      36      16

插入关键字28, 索引(哈希值) = 28 % 11 = 6, 存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23      36      16  28

插入关键字40, 索引(哈希值) = 40 % 11 = 7, 存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23      36      16  28  40

插入关键字87, 索引(哈希值) = 87 % 11 = 10, 存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23      36      16  28  40           87

插入关键字49, 索引(哈希值) = 49 % 11 = 5, 有冲突,取索引5+1=6,仍有冲突,
再取索引6+1=7,仍有冲突,取索引7+1=8,没有冲突,存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23      36      16  28  40  49       87

插入关键字60, 索引(哈希值) = 60 % 11 = 5, 有冲突,依次取索引6,7,8,均有冲突,
取索引9,没有冲突,存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字     23      36      16  28  40  49  60   87

插入关键字62, 索引(哈希值) = 62 % 11 = 7, 有冲突,依次取索引8,9,10,均有冲突,
取索引0,没有冲突,存入哈希表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字 62  23      36      16  28  40  49  60   87

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


//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[]={23,36,16,28,40,87,49,60,62};

    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;
}

Answer 2

百度答案搜索什么的有