本章の末尾に記述するアルゴリズム(ハッシュ加速)を用いてワードパズルを実現する
4451 ワード
データ構造とアルゴリズム分析——c言語記述練習5.13 a答え
hashQuad.h
hashQuad.cpp
main.cpp
hashQuad.h
typedef char* ElementType;
#ifndef _HashQuad_H
#define _HashQuad_H
typedef unsigned int Index;
typedef Index Position;
struct HashTbl;
typedef struct HashTbl* HashTable;
HashTable initializeTable(int tableSize);
void destroyTable(HashTable h);
Position find( const char * key, HashTable h);
HashTable insert(ElementType key, HashTable h);
HashTable rehash(HashTable h);
ElementType retrive(Position p, HashTable h);
int isLegitimate(Position pos, HashTable h);
#endif
hashQuad.cpp
#include"hashQuad.h"
#include"fatal.h"
#include<math.h>
#include<string.h>
#define MinTableSize 10
enum KindOfEntry { Legitimate, Empty, Deleted };
struct HashEntry {
ElementType element;
enum KindOfEntry info;
};
typedef struct HashEntry Cell;
struct HashTbl {
int tableSize;
int hasInsertedNum;
Cell *theCells;//
};
static int hash(const char * key, int tableSize) {
unsigned int hashVal = 0;
while (*key != '\0')
hashVal = (hashVal << 5) + *key++;
return hashVal % (tableSize);
}
static int isPrime(int num) {
for (int i = 2; i <= sqrt(num); i++)
if (num%i == 0)
return 0;
return 1;
}
static int nextPrime(int num) {
int i = num;
while (!isPrime(i))
i++;
return i;
}
int isLegitimate(Position pos, HashTable h) {
return h->theCells[pos].info == Legitimate;
}
HashTable initializeTable(int tableSize) {
HashTable h;
int i;
if (tableSize < MinTableSize) {
Error("Table size too small");
return NULL;
}
h = (HashTable)malloc(sizeof(struct HashTbl));
if (h == NULL)
FatalError("Out of space!!!");
h->tableSize = nextPrime(tableSize);
h->theCells = (Cell*)malloc(sizeof(Cell)*h->tableSize);
h->hasInsertedNum = 0;
if (h->theCells == NULL)
FatalError("Out of space!!!");
for (i = 0; i < h->tableSize; i++) {
h->theCells[i].info = Empty;
}
return h;
}
void destroyTable(HashTable h) {
for (int i = 0; i < h->tableSize; i++)
if (h->theCells[i].info == Legitimate)
free(h->theCells[i].element);
free(h->theCells);
free(h);
}
Position find(const char *key , HashTable h) {
Position currentPos = hash(key, h->tableSize);
while (h->theCells[currentPos].info != Empty && strcmp(h->theCells[currentPos].element, key) != 0) {
currentPos = (currentPos + 1) % h->tableSize;
}
return currentPos;
}
HashTable insert(ElementType key, HashTable h) {
if ((double)h->hasInsertedNum / h->tableSize > 0.5)
h = rehash(h);
Position pos = find(key, h);
if (h->theCells[pos].info != Legitimate) {
h->theCells[pos].element =(char *) malloc(sizeof(char)*strlen(key) + 1);
strcpy(h->theCells[pos].element, key);
h->theCells[pos].info = Legitimate;
h->hasInsertedNum++;
}
return h;
}
HashTable rehash(HashTable h) {
HashTable newH = initializeTable(h->tableSize * 2);
for (int i = 0; i < h->tableSize; i++)
if (h->theCells[i].info == Legitimate)
insert(h->theCells[i].element, newH);
destroyTable(h);
return newH;
}
ElementType retrive(Position p, HashTable h) {
return h->theCells[p].element;
}
main.cpp
#include<stdio.h>
#include<string>
#include<algorithm>
#include"hashQuad.h"
#define MAXN 100
char dictionary[MAXN][MAXN];
char table[MAXN][MAXN];//
//
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { 1,1,0,-1,-1,-1,0,1 };
int dic_num, n;
int main() {
int i;
HashTable h = initializeTable(100);
scanf("%d%d", &dic_num, &n);
for (i = 0; i < dic_num; i++) {
scanf("%s", dictionary[i]);
h = insert(dictionary[i], h);
}
for (i = 0; i < n; i++) {
scanf("%s", table[i]);
}
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
for (int d = 0; d < 8; d++) {
std::string s;
int rr = r;
int cc = c;
for (int l = 1; l <= n; l++) {
s += table[rr][cc];
rr += dx[d];
cc += dy[d];
/*
for (int i = 0; i < dic_num; i++) {
if (strcmp(s.c_str(), dictionary[i]) == 0) {
printf("%s
", s.c_str());
break;
}
}
*/
Position pos = find(s.c_str(), h);
if(isLegitimate(pos,h))
printf("%s
", s.c_str());
}
}
}
}
}