84 lines
3.1 KiB
C++
84 lines
3.1 KiB
C++
//##################################################################
|
|
// PROGRAMMERINGSUPPGIFT 3
|
|
// DATASTRUKTURER OCH ALGORITMER
|
|
// HASH TABELL
|
|
//==================================================================
|
|
// HEADER.HPP
|
|
// Filen innehåller definition som används i programmet
|
|
// Christian Ohlsson
|
|
// Ingela Johansson
|
|
// Anna-Maria Haglund
|
|
// Karlstad 981007
|
|
//==================================================================
|
|
#ifndef _header_
|
|
#define _header_
|
|
|
|
#include <iostream.h> //för in och utmatning
|
|
#include <fstream.h> //för filhantering
|
|
#include <iomanip.h> //för textmanipulation
|
|
#include <string.h> //för strängmanipulation
|
|
#include <conio.h> //för getch()
|
|
#include <ctype.h> //för isalnum
|
|
#include <stdlib.h> //för en massa saker
|
|
|
|
const int FALSE = 0; //boolsk variabel
|
|
const int TRUE = !FALSE //boolsk variabel
|
|
const int FILENAMESIZE = 8; //för MS-DOS 6.0
|
|
const int NAMESIZE = 20; //antal tecken som kan matas in som namn
|
|
const int NUMBERSIZE = 20; //antal tecken som kan matas in som nummer
|
|
const int ENTER = 13; //ASCII kod för enter
|
|
const int BACKSPACE = 8; //ASCII kod för backspace
|
|
const int PRIMEARRAYSIZE = 30; //storlek på primtalsarrayen
|
|
const int DEFAULTSIZE = 11; //hasharrayens defaultstorlek
|
|
const int TABSIZE = 20; //antal steg som motsvarar TAB
|
|
const int STEPSIZE = 7; //antal steg hash2 max stegar fram
|
|
const int DEFAULTPRIMENUMBER = 4; //minsta primtalet i arrayen
|
|
const int FIRSTPRIME = 3; //första talet som man jämför med
|
|
const int STARTPRIME = 2; //första primtalet i arrayen
|
|
const int PRIMESTEP = 2; //antal steg som man hoppar fram
|
|
const float INSERTFACTOR = 0.8; //ger en omhashning när 80% är upptaget
|
|
const float DELETEFACTOR = 0.3; //ger en omhashning när 30% är märkta deleted
|
|
|
|
typedef int bool; //definierar boolesk variabel
|
|
typedef char nameType[NAMESIZE]; //sätter nametypen till char
|
|
typedef char numberType[NUMBERSIZE]; //sätter numberTypen till char
|
|
|
|
struct hashNode{ //en nod
|
|
nameType name;
|
|
numberType number;
|
|
bool exist;
|
|
};
|
|
|
|
class hashClass
|
|
{
|
|
public:
|
|
hashClass();
|
|
~hashClass();
|
|
bool search(nameType name);
|
|
hashNode getNode(nameType &oneName);
|
|
int hash1(nameType name);
|
|
int hash2(int key);
|
|
int getSize();
|
|
void newHashArray();
|
|
void reHash(int oldSize);
|
|
void print();
|
|
void prime();
|
|
int checkOccupied();
|
|
void destroyHash(int oldSize);
|
|
bool biggerHash();
|
|
bool anotherHash();
|
|
void del(int location);
|
|
void insert(int location, hashNode &newNode);
|
|
void save(fstream &fil);
|
|
hashNode *hashPtr;
|
|
int nextPrime();
|
|
private:
|
|
void delHash(int location);
|
|
bool isPrime(int nummer, int antal, int primeArray[PRIMEARRAYSIZE]);
|
|
int ARRAYSIZE;
|
|
int primeArray[];
|
|
int PRIMENUMBER;
|
|
};
|
|
#endif
|
|
|