PTA数据结构与算法题目集(中文) 7-42整型关键字的散列映射 (25 分)

PTA数据结构与算法题目集(中文)  7-42整型关键字的散列映射 (25 分)

7-42 整型关键字的散列映射 (25 分)

 

给定一系列整型关键字和素数P，用除留余数法定义的散列函数将关键字映射到长度为P的散列表中。用线性探测法解决冲突。

输入格式:

输入第一行首先给出两个正整数N（≤）和P（≥的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个整型关键字。数字间以空格分隔。

输出格式:

在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3
题目分析:一道基本的散列表的题

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<malloc.h>
 5 #include<math.h>
 6 #define MAXTABLESIZE 100000
 7 typedef enum{Legitimate,Empty,Deleted}EntryType;
 8 typedef struct HashEntry Cell;
 9 struct HashEntry
10 {
11     EntryType Type;
12     int Data;
13 };
14
15 typedef struct HblNode* HashTable;
16 struct HblNode
17 {
18     int TableSize;
19     Cell* Cells;
20 };
21
22 int Hash(int Data, int TableSize)
23 {
24     return Data % TableSize;
25 }
26
27 int NextPrime(int N)
28 {
29     int P = (N % 2) ? N : N + 1;
30     for (; P < MAXTABLESIZE; P += 2)
31     {
32         int i = (int)sqrt(P);
33         for (; i > 2; i--)
34             if (P % i == 0)
35                 break;
36         if (i == 2)
37             break;
38     }
39     return P;
40 }
41
42 HashTable CreateHashTable(int N)
43 {
44     int TableSize = NextPrime(N);
45     HashTable H = (HashTable)malloc(sizeof(struct HblNode));
46     H->TableSize = TableSize;
47     H->Cells = (Cell*)malloc(H->TableSize * sizeof(Cell));
48     for (int i = 0; i < H->TableSize; i++)
49         H->Cells[i].Type = Empty;
50     return H;
51 }
52
53 int Find(int Data, HashTable H)
54 {
55     int NewPos = Hash(Data, H->TableSize);
56     while (H->Cells[NewPos].Type!=Empty&&H->Cells[NewPos].Data!=Data)
57     {
58         NewPos++;
59         if (NewPos >= H->TableSize)
60             NewPos -= H->TableSize;
61     }
62     return NewPos;
63 }
64
65 void Insert(int Data, HashTable H)
66 {
67     int Pos = Find(Data, H);
68     if (H->Cells[Pos].Type != Legitimate)
69     {
70         H->Cells[Pos].Data = Data;
71         H->Cells[Pos].Type = Legitimate;
72     }
73 }
74
75 int main()
76 {
77     int N, P;
78     scanf("%d%d", &N, &P);
79     HashTable H = CreateHashTable(P);
80     int num;
81     for (int i = 0; i < N-1; i++)
82     {
83         scanf("%d", &num);
84         Insert(num,H);
85         printf("%d ", Find(num,H));
86     }
87     scanf("%d", &num);
88     Insert(num, H);
89     printf("%d", Find(num, H));
90     return 0;
91 }

View Code