ardalahmet.com

Home > CE-242 > CE242-Spring’09-Homework#5

CE242-Spring’09-Homework#5

June 9th, 2009 Ahmet Ardal Leave a comment Go to comments

CE242 Data Structures and Algorithms Course @KHas – Spring 2009 – Homework #5 questions and solutions.
CE242 Data Structures and Algorithms course description is available here.

Download questions and solutions

Note: “ce242-spring09-hw5-q1.cpp”, “ce242-spring09-hw5-q2.cpp” and “ce242-spring09-hw5-q3.cpp” need “BTree.cpp” module, so link them together while building the code.

Source files:

[BTree.h] | show

// ==================================================
// - File______: BTree.h ____________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef BTREE_H_
#define BTREE_H_

struct TNode
{
    void  *pData;
    TNode *pRight;
    TNode *pLeft;
};

#define TNodeData(pNode)    (pNode)->pData
#define TNodeRight(pNode)   (pNode)->pRight
#define TNodeLeft(pNode)    (pNode)->pLeft

#ifndef CALLBACKFUNC_DEFINED
# define CALLBACKFUNC_DEFINED
typedef void (*CallbackFunc)(void *pData, void *pCallbackData);
#endif

typedef int (*CompareFunc)(const void *pData1, const void *pData2);

struct BTree
{
    TNode *pRoot;
    CompareFunc compare;
};

#define BTreeRoot(pTree)    (pTree)->pRoot

BTree *BTreeCreate(CompareFunc compare);
TNode *BTreeInsert(BTree *pTree, const void *pData);
TNode *BTreeSearch(BTree *pTree, const void *pKey);
bool   BTreeRemove(BTree *pTree, const void *pKey);
bool   BTreeRemove2(BTree *pTree, const void *pKey);
void   BTreeRotateRight(TNode **ppRoot);
void   BTreeRotateLeft(TNode **ppRoot);
TNode *BTreeInsertRoot(BTree *pTree, const void *pData);
void   BTreeForeachAsc(BTree *pTree, CallbackFunc callback, void *pCallbackData);
void   BTreeForeachDesc(BTree *pTree, CallbackFunc callback, void *pCallbackData);
void   BTreeDestroy(BTree *pTree);

#endif  // BTREE_H_

[BTree.cpp] | show

// ==================================================
// - File______: BTree.cpp __________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <cstdlib>
#include "BTree.h"

// -------------------------------------------------
// --- private functions ---------------------------
// -------------------------------------------------

static TNode *createNode(const void *pData);
static void   truncateTree(TNode *pNode);
static TNode *insertRecursive(TNode *pRoot, const void *pData, CompareFunc compare);
static TNode *getInorderSuccessor(const TNode *pRoot);
static TNode *getInorderPredecessor(const TNode *pRoot);
static TNode *removeRecursive(TNode *pRoot, const void *pKey, CompareFunc compare);
static TNode *removeRecursive2(TNode *pRoot, const void *pKey, CompareFunc compare);
static void insertRootRecursive(TNode **ppRoot, const void *pData, CompareFunc compare);
static void foreachAscRecursive(TNode *pRoot, CallbackFunc callback, void *pCallbackData);
static void foreachDescRecursive(TNode *pRoot, CallbackFunc callback, void *pCallbackData);

static TNode *createNode(const void *pData)
{
    TNode *pNode = new TNode;

    pNode->pData  = (void *) pData;
    pNode->pRight = NULL;
    pNode->pLeft  = NULL;

    return pNode;
}

static void truncateTree(TNode *pNode)
{
    if (pNode->pLeft != NULL)
    {
        truncateTree(pNode->pLeft);
    }

    if (pNode->pRight != NULL)
    {
        truncateTree(pNode->pRight);
    }

    delete pNode;
}

static TNode *insertRecursive(TNode *pRoot, const void *pData, CompareFunc compare)
{
    int result;

    if ((result = compare(pRoot->pData, pData)) > 0)
    {
        if (pRoot->pLeft == NULL)
        {
            pRoot->pLeft = createNode(pData);
            return pRoot->pLeft;
        }
        return insertRecursive(pRoot->pLeft, pData, compare);
    }
    else if (result < 0)
    {
        if (pRoot->pRight == NULL)
        {
            pRoot->pRight = createNode(pData);
            return pRoot->pRight;
        }
        return insertRecursive(pRoot->pRight, pData, compare);
    }
    else
    {
        return NULL;
    }
}

static TNode *getInorderSuccessor(const TNode *pRoot)
{
    TNode *pNodeTmp;

    for (TNode *pNode = (TNode *) pRoot; pNode != NULL; )
    {
        pNodeTmp = pNode;
        pNode = pNode->pLeft;
    }

    return pNodeTmp;
}

static TNode *getInorderPredecessor(const TNode *pRoot)
{
    TNode *pNodeTmp;

    for (TNode *pNode = (TNode *) pRoot; pNode != NULL; )
    {
        pNodeTmp = pNode;
        pNode = pNode->pRight;
    }

    return pNodeTmp;
}

static TNode *removeRecursive(TNode *pRoot, const void *pKey, CompareFunc compare)
{
    int result;
    TNode *pNodeSuccessor, *pNodeDelete;

    if (pRoot != NULL)
    {
        if ((result = compare(pRoot->pData, pKey)) > 0)
        {
            pRoot->pLeft = removeRecursive(pRoot->pLeft, pKey, compare);
        }
        else if (result < 0)
        {
            pRoot->pRight = removeRecursive(pRoot->pRight, pKey, compare);
        }
        else
        {
            if (pRoot->pLeft == NULL)
            {
                pNodeDelete = pRoot;
                pRoot = pRoot->pRight;
                delete pNodeDelete;
            }
            else if (pRoot->pRight == NULL)
            {
                pNodeDelete = pRoot;
                pRoot = pRoot->pLeft;
                delete pNodeDelete;
            }
            else
            {
                pNodeSuccessor = getInorderSuccessor(pRoot->pRight);
                pRoot->pData   = pNodeSuccessor->pData;
                pRoot->pRight  = removeRecursive(pRoot->pRight, pNodeSuccessor->pData, compare);
            }
        }
        return pRoot;
    }
    else
    {
        return NULL;
    }
}

static TNode *removeRecursive2(TNode *pRoot, const void *pKey, CompareFunc compare)
{
    int result;
    TNode *pNodePredecessor, *pNodeDelete;

    if (pRoot != NULL)
    {
        if ((result = compare(pRoot->pData, pKey)) > 0)
        {
            pRoot->pLeft = removeRecursive2(pRoot->pLeft, pKey, compare);
        }
        else if (result < 0)
        {
            pRoot->pRight = removeRecursive2(pRoot->pRight, pKey, compare);
        }
        else
        {
            if (pRoot->pLeft == NULL)
            {
                pNodeDelete = pRoot;
                pRoot = pRoot->pRight;
                delete pNodeDelete;
            }
            else if (pRoot->pRight == NULL)
            {
                pNodeDelete = pRoot;
                pRoot = pRoot->pLeft;
                delete pNodeDelete;
            }
            else
            {
                pNodePredecessor = getInorderPredecessor(pRoot->pLeft);
                pRoot->pData   = pNodePredecessor->pData;
                pRoot->pLeft  = removeRecursive2(pRoot->pLeft, pNodePredecessor->pData, compare);
            }
        }
        return pRoot;
    }
    else
    {
        return NULL;
    }
}

static void insertRootRecursive(TNode **ppRoot, const void *pData, CompareFunc compare)
{
    // base case
    if (*ppRoot == NULL)
    {
        *ppRoot = createNode(pData);
        return;
    }

    // general case
    if (compare((*ppRoot)->pData, pData) > 0)
    {
        insertRootRecursive(&(*ppRoot)->pLeft, pData, compare);
        BTreeRotateRight(ppRoot);
    }
    else
    {
        insertRootRecursive(&(*ppRoot)->pRight, pData, compare);
        BTreeRotateLeft(ppRoot);
    }
}

static void foreachAscRecursive(TNode *pRoot, CallbackFunc callback, void *pCallbackData)
{
    if (pRoot->pLeft != NULL)
    {
        foreachAscRecursive(pRoot->pLeft, callback, pCallbackData);
    }

    callback(pRoot->pData, pCallbackData);

    if (pRoot->pRight != NULL)
    {
        foreachAscRecursive(pRoot->pRight, callback, pCallbackData);
    }
}

static void foreachDescRecursive(TNode *pRoot, CallbackFunc callback, void *pCallbackData)
{
    if (pRoot->pRight != NULL)
    {
        foreachDescRecursive(pRoot->pRight, callback, pCallbackData);
    }

    callback(pRoot->pData, pCallbackData);

    if (pRoot->pLeft != NULL)
    {
        foreachDescRecursive(pRoot->pLeft, callback, pCallbackData);
    }
}

// -------------------------------------------------
// --- public functions ----------------------------
// -------------------------------------------------

BTree *BTreeCreate(CompareFunc compareCb)
{
    if (compareCb == NULL)
    {
        return NULL;
    }

    BTree *pTree   = new BTree;
    pTree->pRoot   = NULL;
    pTree->compare = compareCb;

    return pTree;
}

// -------------------------------------------------------
// --- iterative version ---------------------------------
// -------------------------------------------------------
//TNode *BTreeInsert(BTree *pTree, const void *pData)
//{
//    // if the tree is empty
//    if (pTree->pRoot == NULL)
//    {
//        pTree->pRoot = createNode(pData);
//        return pTree->pRoot;
//    }
//
//    // traverse the tree to find an appropriate position to insert the new node
//    int result;
//    TNode *pNodeTmp;
//    for (TNode *pNode = pTree->pRoot; pNode != NULL; )
//    {
//        if ((result = pTree->compare(pNode->pData, pData)) > 0)
//        {
//            pNodeTmp = pNode;
//            pNode    = pNode->pLeft;
//        }
//        else if (result < 0)
//        {
//            pNodeTmp = pNode;
//            pNode    = pNode->pRight;
//        }
//        else
//        {
//            // do not allow duplicate data
//            return NULL;
//        }
//    }
//
//    if (result > 0)
//    {
//        pNodeTmp->pLeft = createNode(pData);
//        return pNodeTmp->pLeft;
//    }
//    else
//    {
//        pNodeTmp->pRight = createNode(pData);
//        return pNodeTmp->pRight;
//    }
//}

// -------------------------------------------------------
// --- recursive version ---------------------------------
// -------------------------------------------------------
TNode *BTreeInsert(BTree *pTree, const void *pData)
{
    // if the tree is empty
    if (pTree->pRoot == NULL)
    {
        pTree->pRoot = createNode(pData);
        return pTree->pRoot;
    }

    return insertRecursive(pTree->pRoot, pData, pTree->compare);
}

TNode *BTreeSearch(BTree *pTree, const void *pKey)
{
    int result;

    for (TNode *pNode = pTree->pRoot; pNode != NULL; )
    {
        if ((result = pTree->compare(pNode->pData, pKey)) > 0)
        {
			pNode = pNode->pLeft;
        }
		else if (result < 0)
        {
			pNode = pNode->pRight;
        }
		else
        {
            return pNode;
        }
    }

    return NULL;
}

bool BTreeRemove(BTree *pTree, const void *pKey)
{
    return (removeRecursive(pTree->pRoot, pKey, pTree->compare) != NULL);
}

bool BTreeRemove2(BTree *pTree, const void *pKey)
{
    return (removeRecursive2(pTree->pRoot, pKey, pTree->compare) != NULL);
}

void BTreeRotateRight(TNode **ppRoot)
{
    TNode *pPivot = (*ppRoot)->pLeft;

    if (pPivot == NULL)
    {
        return;
    }

    (*ppRoot)->pLeft = pPivot->pRight;
    pPivot->pRight   = *ppRoot;
    *ppRoot          = pPivot;
}

void BTreeRotateLeft(TNode **ppRoot)
{
    TNode *pPivot = (*ppRoot)->pRight;

    if (pPivot == NULL)
    {
        return;
    }

    (*ppRoot)->pRight = pPivot->pLeft;
    pPivot->pLeft     = *ppRoot;
    *ppRoot           = pPivot;
}

TNode *BTreeInsertRoot(BTree *pTree, const void *pData)
{
    // check for duplicate key
    if (BTreeSearch(pTree, pData) != NULL)
    {
        return NULL;
    }

    insertRootRecursive(&pTree->pRoot, pData, pTree->compare);
    return pTree->pRoot;
}

void BTreeForeachAsc(BTree *pTree, CallbackFunc callback, void *pCallbackData)
{
    foreachAscRecursive(pTree->pRoot, callback, pCallbackData);
}

void BTreeForeachDesc(BTree *pTree, CallbackFunc callback, void *pCallbackData)
{
    foreachDescRecursive(pTree->pRoot, callback, pCallbackData);
}

void BTreeDestroy(BTree *pTree)
{
    truncateTree(pTree->pRoot);
    delete pTree;
}

[ce242-spring09-hw5-q1.cpp] | show

// ==================================================
// - File______: ce242-spring09-hw5-q1.cpp __________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <fstream>
#include <cstring>
#include "BTree.h"

using namespace std;

const int WORD_LEN_MAX = 64;
const int DEF_LEN_MAX  = 256;

struct WordDef
{
    char word[WORD_LEN_MAX];
    char definition[DEF_LEN_MAX];
};

int cmpWordDefsCb(const void *pData1, const void *pData2)
{
    return strcmp(((WordDef *) pData1)->word, ((WordDef *) pData2)->word);
}

void deleteWordDefsCb(void *pData, void *pCallbackData)
{
    delete (WordDef *) pData;
}

int main()
{
    char line[512];
    char *pcDef;
    WordDef *pWordDef;
    BTree *pTrDict;

    // open the file
    ifstream f("forex-terms-data.txt");

    if (!f)
    {
        cerr << "cannot open file..." << endl;
        return EXIT_FAILURE;
    }

    // create the dictionary tree
    pTrDict = BTreeCreate(cmpWordDefsCb);

    // read file and construct the dictionary
    while (true)
    {
        f.getline(line, 512);
        if (f.eof())
        {
            break;
        }

        // split the line into two tokens as the word and its definition
        pcDef  = strchr(line, ':');
        *pcDef = '\0';

        // create a WordDef object and insert it to the dictionary
        pWordDef = new WordDef;
        strcpy(pWordDef->word, line);
        strcpy(pWordDef->definition, (pcDef + 1));
        BTreeInsert(pTrDict, pWordDef);
    }
    // close the file
    f.close();

    // search for words in the dictionary
    WordDef wd;
    while (true)
    {
        // get input
        cout << "Enter a word to search(enter --- to exit): ";
        cin.getline(wd.word, 64);

        // if "---" is entered then exit
        if (!strcmp(wd.word, "---"))
        {
            break;
        }

        // search the word in the dictionary
        TNode *pNode = BTreeSearch(pTrDict, &wd);

        cout << endl;
        if (pNode != NULL)
        {
            cout << ((WordDef *) TNodeData(pNode))->definition << endl;
        }
        else
        {
            cout << "not found..." << endl;
        }
    }

    // delete WordDef objects and the tree
    BTreeForeachAsc(pTrDict, deleteWordDefsCb, NULL);
    BTreeDestroy(pTrDict);

    return 0;
}

[ce242-spring09-hw5-q2.cpp] | show

// ==================================================
// - File______: ce242-spring09-hw5-q2.cpp __________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <fstream>
#include <cstring>
#include "BTree.h"

using namespace std;

void printDictAscending(TNode *pRoot);
void printDictDescending(TNode *pRoot);

const int WORD_LEN_MAX = 64;
const int DEF_LEN_MAX  = 256;

struct WordDef
{
    char word[WORD_LEN_MAX];
    char definition[DEF_LEN_MAX];
};

int cmpWordDefsCb(const void *pData1, const void *pData2)
{
    return strcmp(((WordDef *) pData1)->word, ((WordDef *) pData2)->word);
}

void deleteWordDefsCb(void *pData, void *pCallbackData)
{
    delete (WordDef *) pData;
}

int main()
{
    char line[512];
    char *pcDef;
    WordDef *pWordDef;
    BTree *pTrDict;

    // open the file
    ifstream f("forex-terms-data.txt");

    if (!f)
    {
        cerr << "cannot open file..." << endl;
        return EXIT_FAILURE;
    }

    // create the dictionary tree
    pTrDict = BTreeCreate(cmpWordDefsCb);

    // read file and construct the dictionary
    while (true)
    {
        f.getline(line, 512);
        if (f.eof())
        {
            break;
        }

        // split the line into two tokens as the word and its definition
        pcDef  = strchr(line, ':');
        *pcDef = '\0';

        // create a WordDef object and insert it to the dictionary
        pWordDef = new WordDef;
        strcpy(pWordDef->word, line);
        strcpy(pWordDef->definition, (pcDef + 1));
        BTreeInsert(pTrDict, pWordDef);
    }
    // close the file
    f.close();

    cout << "Printing dictionary in ascending order:" << endl;
    printDictAscending(pTrDict->pRoot);
    cout << endl << "==================================" << endl << endl;
    cout << "Printing dictionary in descending order:" << endl;
    printDictDescending(pTrDict->pRoot);

    // delete WordDef objects and the tree
    BTreeForeachAsc(pTrDict, deleteWordDefsCb, NULL);
    BTreeDestroy(pTrDict);

    return 0;
}

void printDictAscending(TNode *pRoot)
{
    if (TNodeLeft(pRoot) != NULL)
    {
        printDictAscending(TNodeLeft(pRoot));
    }

    WordDef *pWd = (WordDef *) pRoot->pData;
    cout << pWd->word << ":\n" << pWd->definition << endl;
    cout << "-----------------------------------" << endl;

    if (TNodeRight(pRoot) != NULL)
    {
        printDictAscending(TNodeRight(pRoot));
    }
}

void printDictDescending(TNode *pRoot)
{
    if (TNodeRight(pRoot) != NULL)
    {
        printDictDescending(TNodeRight(pRoot));
    }

    WordDef *pWd = (WordDef *) pRoot->pData;
    cout << pWd->word << ":\n" << pWd->definition << endl;
    cout << "-----------------------------------" << endl;

    if (TNodeLeft(pRoot) != NULL)
    {
        printDictDescending(TNodeLeft(pRoot));
    }
}

[ce242-spring09-hw5-q3.cpp] | show

// ==================================================
// - File______: ce242-spring09-hw5-q3.cpp __________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <fstream>
#include <cstring>
#include "BTree.h"

using namespace std;

const int WORD_LEN_MAX = 64;
const int DEF_LEN_MAX  = 256;

struct WordDef
{
    char word[WORD_LEN_MAX];
    char definition[DEF_LEN_MAX];
};

struct WordInterval
{
    char *word1;
    char *word2;
};

int cmpWordDefsCb(const void *pData1, const void *pData2)
{
    return strcmp(((WordDef *) pData1)->word, ((WordDef *) pData2)->word);
}

void printIntervalCb(void *pData, void *pCallbackData)
{
    WordDef      *pWd = (WordDef *)      pData;
    WordInterval *pWi = (WordInterval *) pCallbackData;

    // check whether or not the word is between word1 and word2
    if ((strcmp(pWd->word, pWi->word1) >= 0) && (strcmp(pWd->word, pWi->word2) <= 0))
    {
        cout << pWd->word << endl;
    }
}

void deleteWordDefsCb(void *pData, void *pCallbackData)
{
    delete (WordDef *) pData;
}

int main()
{
    char line[512];
    char *pcDef;
    WordDef *pWordDef;
    BTree *pTrDict;

    // open the file
    ifstream f("forex-terms-data.txt");

    if (!f)
    {
        cerr << "cannot open file..." << endl;
        return EXIT_FAILURE;
    }

    // create the dictionary tree
    pTrDict = BTreeCreate(cmpWordDefsCb);

    // read file and construct the dictionary
    while (true)
    {
        f.getline(line, 512);
        if (f.eof())
        {
            break;
        }

        // split the line into two tokens as the word and its definition
        pcDef  = strchr(line, ':');
        *pcDef = '\0';

        // create a WordDef object and insert it to the dictionary
        pWordDef = new WordDef;
        strcpy(pWordDef->word, line);
        strcpy(pWordDef->definition, (pcDef + 1));
        BTreeInsert(pTrDict, pWordDef);
    }
    // close the file
    f.close();

    //WordInterval wi = {"Arbitration", "Envelope"};
    WordInterval wi = {"Cabinet Crowd", "Efficiency"};
    BTreeForeachAsc(pTrDict, printIntervalCb, &wi);

    // delete WordDef objects and the tree
    BTreeForeachAsc(pTrDict, deleteWordDefsCb, NULL);
    BTreeDestroy(pTrDict);

    return 0;
}

Categories: CE-242 Tags: binary tree, cpp, data structure, dictionary, function pointer, tree traversal

Comments (0) Trackbacks (0) Leave a comment Trackback

No comments yet.

No trackbacks yet.

CE242-Spring’09-Homework#6 CE242-Spring’09-Homework#4

CE242-Spring’09-Homework#5

Subscribe

Categories

Recent Posts

Links

Meta