Question

C语言 数据结构 文件及查找问题

已知散列函数为H（k）=（3*k）MOD11,并采用线性探测再散列法处理冲突。请对下列关键字值序列构造一个散列地址空间为【0，10】的散列表
（22，41，53，8，46，30，1，31，66）

Answer 1

关键字序列是{22,41,53,8,46,30,1,31,66}, 计算过程如下:

插入关键字22, 索引(散列值) = 3*22 mod 11 = 0, 存入散列表:

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

插入关键字41, 索引(散列值) = 3*41 mod 11 = 2, 存入散列表:

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

插入关键字53, 索引(散列值) = 3*53 mod 11 = 5, 存入散列表:

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

插入关键字8, 索引(散列值) = 3*8 mod 11 = 2, 有冲突,取索引2+1=3,没有冲突,存入散列表:

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

插入关键字46, 索引(散列值) = 3*46 mod 11 = 6, 存入散列表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字 22      41   8      53  46

插入关键字30, 索引(散列值) = 3*30 mod 11 = 2, 有冲突,取索引2+1=3,仍有冲突,
取索引3+1=4,没有冲突,存入散列表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字 22      41   8  30  53  46

插入关键字1, 索引(散列值) = 3*1 mod 11 = 3, 有冲突,依次取索引4,5,6,均有冲突,
取索引7,没有冲突,存入散列表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字 22      41   8  30  53  46   1

插入关键字31, 索引(散列值) = 3*31 mod 11 = 5, 有冲突,依次取索引6,7,均有冲突,
取索引8,没有冲突,存入散列表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字 22      41   8  30  53  46   1  31

插入关键字66, 索引(散列值) = 3*66 mod 11 = 0, 有冲突,取索引0+1=1,没有冲突,存入散列表:

  下标    0   1   2   3   4   5   6   7   8   9   10
  关键字 22  66  41   8  30  53  46   1  31

这就是最后得到的散列表.


//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 (3*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[]={22,41,53,8,46,30,1,31,66};

    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

1Status其实是：typedefintstatus;
2sub[1...len]表示名为sub的数组的元素序号是1到len共len个元素
3看你用的什么编译器，要是好一点的编译器，你右键单击那条语句，会有个转到头文件或是什么类似的选项，如果没有的话，安装文件夹下找include或inc文件夹
over