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

 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 }