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

7-43 字符串关键字的散列映射 (25 分)

给定一系列由大写英文字母组成的字符串关键字和素数

发生冲突时请用平方探测法解决。

输入格式:

输入第一行首先给出两个正整数

输出格式:

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

输入样例1:

4 11
HELLO ANNK ZOE LOLI

输出样例1:

3 10 4 0

输入样例2:

6 11
LLO ANNA NNK ZOJ INNK AAA

输出样例2:

3 0 10 9 6 1
题目分析：这是也是一道散列表的基础题

  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 
  8 typedef enum{Legitimate,Empty,Deleted}EntryType;
  9 typedef struct HashEntry Cell;
 10 struct HashEntry
 11 {
 12     EntryType Type;
 13     char Data[9];
 14 };
 15 typedef struct HblNode* HashTable;
 16 struct HblNode
 17 {
 18     int TableSize;
 19     Cell* Cells;
 20 };
 21 
 22 int NextPrime(int N)
 23 {
 24     int P = (N % 2)?N:N + 1;
 25     for (; P < MAXTABLESIZE; P += 2)
 26     {
 27         int i = (int)sqrt(P);
 28         for (; i > 2; i--)
 29             if (P % i == 0)
 30                 break;
 31         if (i == 2)
 32             break;
 33     }
 34     return P;
 35 }
 36 
 37 HashTable CreateHashTable(int N)
 38 {
 39     int TableSize = NextPrime(N);
 40     HashTable H = (HashTable)malloc(sizeof(struct HblNode));
 41     H->TableSize = TableSize;
 42     H->Cells = (Cell*)malloc(H->TableSize * sizeof(Cell));
 43     for (int i = 0; i < H->TableSize; i++)
 44     {
 45         H->Cells[i].Type = Empty;
 46         H->Cells[i].Data[0] = '

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

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

输入格式:

输出格式:

输入样例1:

输出样例1:

输入样例2:

输出样例2:

相关推荐