274 lines
7.9 KiB
C++
274 lines
7.9 KiB
C++
//##################################################################
|
|
// PROGRAMMERINGSUPPGIFT 2
|
|
// DATASTRUKTURER OCH ALGORITMER
|
|
// AVL TRÄD
|
|
//==================================================================
|
|
// HUVUD.CPP
|
|
// Filen innehåller huvudprogrammet
|
|
// Christian Ohlsson
|
|
// Karlstad 980927
|
|
//==================================================================
|
|
|
|
#include "header.hpp"
|
|
|
|
//###############################################################
|
|
// SÄKER INMATNING AV MENYVAL
|
|
// ser till att bara en character matas in
|
|
// som menyval som dessutom måste vara en siffra
|
|
//===============================================================
|
|
/*
|
|
char mataInChar()
|
|
{
|
|
bool test = FALSE;
|
|
char temp, svar;
|
|
do {
|
|
temp = getch();
|
|
if(isalnum(temp) && test == FALSE) {
|
|
cout << temp;
|
|
svar = temp;
|
|
test = TRUE;
|
|
}
|
|
else if(temp == BACKSPACE && test == TRUE) {
|
|
gotoxy(wherex()-1, wherey());
|
|
cout << " ";
|
|
gotoxy(wherex()-1, wherey());
|
|
test = FALSE;
|
|
}
|
|
}while(temp != ENTER || test == FALSE);
|
|
return svar;
|
|
}
|
|
*/
|
|
//##################################################################
|
|
// SÄTTER IN EN NOD I TRÄD
|
|
// calls: treeClass::insert, treeclass::seek, treeClass::setHeight
|
|
// treeClass::rotation
|
|
//==================================================================
|
|
void _insert(treeClass &myTree)
|
|
{
|
|
nameType oneName;
|
|
numberType number;
|
|
int height=0;
|
|
|
|
cout <<"\n Ange namn: ";
|
|
cin >> oneName;
|
|
if(strlen(oneName) > NAMESIZE)
|
|
cout << "\n Man kan högst ange namnet med " << NAMESIZE << " tecken";
|
|
else {
|
|
if(myTree.seek(myTree.node, oneName) != NULL)
|
|
cout << "\n Du har redan satt in "
|
|
<< oneName << " i katalogen";
|
|
else {
|
|
cout <<"\n Ange telefonnummer: ";
|
|
cin >> number;
|
|
if (strlen(number) > NUMBERSIZE)
|
|
cout << "\n Man kan högst ange nummret med " << NUMBERSIZE << " tecken";
|
|
else {
|
|
myTree.insert(myTree.node,oneName,number,height);
|
|
myTree.setHeight(myTree.node);
|
|
myTree.rotation(myTree.node);
|
|
myTree.setHeight(myTree.node);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
// getch();
|
|
}
|
|
//##################################################################
|
|
// TAR BORT EN NOD UR TRÄD
|
|
// calls: treeClass::del, treeClass::isEmpty, treeclass::seek
|
|
// treeClass::setHeight, treeClass::rotation
|
|
//==================================================================
|
|
void _del(treeClass &myTree)
|
|
{
|
|
if(!myTree.isEmpty()) {
|
|
nameType oneName;
|
|
|
|
cout << "\n Vem vill du ta bort: ";
|
|
cin >> oneName;
|
|
if(strlen(oneName) > NAMESIZE)
|
|
cout << "\n Man kan högst ange namnet med " << NAMESIZE << " tecken";
|
|
else {
|
|
if(myTree.seek(myTree.node, oneName) == NULL)
|
|
cerr << "\n " << oneName << " finns inte i katalogen. ";
|
|
else {
|
|
myTree.del(myTree.node, oneName);
|
|
myTree.setHeight(myTree.node);
|
|
myTree.rotation(myTree.node);
|
|
myTree.setHeight(myTree.node);
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
cerr << "\n Telefonkatalogen är tom... ";
|
|
// getch();
|
|
}
|
|
//##################################################################
|
|
// SKRIVER UT I INORDER
|
|
// calls: treeClass::inOrder, treeClass::isEmpty
|
|
//==================================================================
|
|
void _inOrder(treeClass myTree)
|
|
{
|
|
if(!myTree.isEmpty()) {
|
|
// clrscr();
|
|
cout << setw(NAMESIZE)
|
|
<< "Namn"
|
|
<< setw(NAMESIZE)
|
|
<< "Telefon"
|
|
<< setw(NAMESIZE)
|
|
<< "Höjd \n"
|
|
<< setw(NAMESIZE)
|
|
<< " ------------------------------------------------------------------ \n";
|
|
myTree.inOrder(myTree.node);
|
|
}
|
|
else
|
|
cerr << "\n Telefonkatalogen är tom... ";
|
|
// getch();
|
|
}
|
|
//##################################################################
|
|
// SÖKER I TRÄDET
|
|
// calls: treeClass::seek, treeClass::isEmpty
|
|
//==================================================================
|
|
void _seek(treeClass myTree)
|
|
{
|
|
if(!myTree.isEmpty()) {
|
|
nameType oneName;
|
|
cout << "\n Mata in namn: ";
|
|
cin >> oneName;
|
|
ptrType tempNode = myTree.seek(myTree.node, oneName);
|
|
if(tempNode != NULL)
|
|
cout << "\n " << tempNode->name
|
|
<< " har telefonnummer: "
|
|
<< tempNode->number;
|
|
else
|
|
cout << "\n " << oneName << " fanns inte med i katalogen...";
|
|
}
|
|
else
|
|
cerr << "\n Telefonkatalogen är tom... ";
|
|
// getch();
|
|
}
|
|
//##################################################################
|
|
// SPARAR TRÄDET PÅ FIL
|
|
// calls: treeClass::save, treeClass::isEmpty
|
|
//==================================================================
|
|
void _save(treeClass myTree)
|
|
{
|
|
if(!myTree.isEmpty()) {
|
|
fstream fil;
|
|
char filnamn[FILENAMESIZE];
|
|
cout << "\n Ange filnamn att spara: ";
|
|
cin >> filnamn;
|
|
fil.open(filnamn,ios::out|ios::binary);
|
|
myTree.save(myTree.node, fil);
|
|
fil.close();
|
|
}
|
|
else {
|
|
cerr << "\n Telefonkatalogen är tom...";
|
|
// getch();
|
|
}
|
|
}
|
|
//##################################################################
|
|
// HÄMTAR ETT TRÄD FRÅN EN FIL
|
|
// läser in värdet i varje nod i preorder
|
|
// och sätter in det i trädet i preoder
|
|
// calls treeClass::insert, treeClass::isEmpty, treeClass::setHeight
|
|
// treeClass::rotation
|
|
//==================================================================
|
|
void _load(treeClass &myTree)
|
|
{
|
|
if(myTree.isEmpty()) {
|
|
fstream fil;
|
|
numberType number;
|
|
nameType oneName;
|
|
char filnamn[FILENAMESIZE];
|
|
|
|
cout << "\n Ange filnamn att hämta: ";
|
|
cin >> filnamn;
|
|
fil.open(filnamn,ios::in|ios::binary);
|
|
if(fil)
|
|
while(fil.peek() != EOF) {
|
|
fil.read((char*)&oneName,sizeof(oneName));
|
|
fil.read((char*)&number,sizeof(number));
|
|
myTree.insert(myTree.node, oneName,number,0);
|
|
myTree.setHeight(myTree.node);
|
|
myTree.rotation(myTree.node);
|
|
myTree.setHeight(myTree.node);
|
|
}
|
|
else {
|
|
cerr << "\n Filen finns inte...";
|
|
// getch();
|
|
}
|
|
fil.close();
|
|
}
|
|
else {
|
|
cerr << "\n Det finns redan personer i katalogen. \n"
|
|
<< " Du måste ta bort samtliga personer \n"
|
|
<< " genom att välja detta i menyn. \n";
|
|
// getch();
|
|
}
|
|
}
|
|
//##################################################################
|
|
// DESTROYTREE
|
|
// tar bort hela trädet
|
|
// calls: treeClass::isEmpty, treeClass::destroyTree
|
|
//==================================================================
|
|
void _destroyTree(treeClass &myTree)
|
|
{
|
|
if(!myTree.isEmpty())
|
|
myTree.destroyTree(myTree.node);
|
|
else {
|
|
cerr << "\n Telefonkatalogen är tom...";
|
|
// getch();
|
|
}
|
|
}
|
|
//##################################################################
|
|
// MENY ITEMS
|
|
// skriver ut menyn på skärmen
|
|
//==================================================================
|
|
void meny()
|
|
{
|
|
// clrscr();
|
|
cout << " \n TELEFON KATALOGEN "
|
|
<< " \n ----------------- "
|
|
<< " \n 1. Lägg till person "
|
|
<< " \n 2. Ta bort person "
|
|
<< " \n 3. Sök efter person "
|
|
<< " \n 4. Skriv ut i bokstavsordning "
|
|
<< " \n 5. Spara på fil "
|
|
<< " \n 6. Hämta från fil "
|
|
<< " \n 7. Radera hela trädet "
|
|
<< " \n 0. Avsluta "
|
|
<< " \n ";
|
|
// gotoxy(2,12); //ställer markören under menyn
|
|
}
|
|
//##################################################################
|
|
// MAIN FUNCTION
|
|
// skapar trädet myTree av typen treeClass
|
|
// calls: alla drivrutiner
|
|
//==================================================================
|
|
void main()
|
|
{
|
|
treeClass myTree;
|
|
char val;
|
|
do {
|
|
meny();
|
|
cin >> val;
|
|
// val = mataInChar();;
|
|
switch (val)
|
|
{
|
|
case '1' : _insert(myTree);break;
|
|
case '2' : _del(myTree);break;
|
|
case '3' : _seek(myTree);break;
|
|
case '4' : _inOrder(myTree);break;
|
|
case '5' : _save(myTree);break;
|
|
case '6' : _load(myTree);break;
|
|
case '7' : _destroyTree(myTree);break;
|
|
case '0' : cout << "\n Programmet avslutat";break;
|
|
default : cerr << "\n Felaktigt val";
|
|
// getch();
|
|
}
|
|
}while(val != '0');
|
|
}
|
|
|
|
|