zadatak 4 strukture podataka - C++ Snipplr Social Repository

Revision: 38905

at January 10, 2011 07:43 by anton_kvesic

Updated Code

#include <iostream>

using namespace std;

typedef int labeltype;
struct cvor {
    labeltype label;
    bool used;
};

struct bt {
    cvor elementi[10000];
};

typedef bt btree;
typedef int node;

void InitB(labeltype x, btree *T) {
    for (int i = 1; i < 10000; i++) {
        T->elementi[i].used = false;
    }
    T->elementi[1].used = true;
    T->elementi[1].label = x;
}

labeltype LabelB(node n, btree *T) {
    return T->elementi[n].label;
}

void ChangeLabelB(labeltype x, node n, btree *T) {
    T->elementi[n].label = x;
}

node RootB(btree *T) { 
    return 1;
}

node LeftChildB(node n, btree *T) {
    if (T->elementi[n*2].used == true) 
        return n*2;
    else
        return 0;
}

node RightChildB(node n, btree *T) {
    if (T->elementi[n*2+1].used == true) 
        return n*2+1;
    else
        return 0;
}

node ParentB(node n, btree *T) {
   return n/2;
}

void CreateLeftB(labeltype x, node n, btree *T) {
    if (T->elementi[n*2].used == true) 
        cout << "Taj cvor vec postoji!" << endl;
    else {
        T->elementi[n*2].used = true;
        T->elementi[n*2].label = x;
    }
}

void CreateRightB(labeltype x, node n, btree *T) {
    if (T->elementi[n*2+1].used == true) 
        cout << "Taj cvor vec postoji!" << endl;
    else {
        T->elementi[n*2+1].used = true;
        T->elementi[n*2+1].label = x;
    } 
}

void DeleteB(node n, btree *T) {
    T->elementi[n].used = false;
    if (T->elementi[n*2].used == true) 
        DeleteB(n*2, T);
    if (T->elementi[n*2+1].used == true)
        DeleteB(n*2+1, T);  
}



#include <iostream>
#include <deque>

using namespace std;

typedef int labeltype;
struct cvor {
    labeltype label;
    cvor *left, *right; //
};

typedef cvor *node;
typedef cvor btree;

void InitB(labeltype x, btree *T) {
    T->label = x;
    T->left = T->right = NULL;
}

labeltype LabelB(node n, btree *T) {
    return n->label; 
}

void ChangeLabelB(labeltype x, node n, btree *T) {
    n->label = x;
}

node RootB(btree *T) { return T; }

node LeftChildB(node n, btree *T) {
    return n->left;
}

node RightChildB(node n, btree *T) {
    return n->right;
}

node ParentB(node n, btree *T) {
    // ako zelis parent od korijena, odmah gotovo
    if (n == T)
        return NULL;
    // ako ne, idemo traziti
    deque<node> red;
    red.push_back(RootB(T));
    node temp;
    // Ovdje njime simuliramo red, dodajemo nepregledane
    // cvorove na kraj, a s pocetka pregledavamo i vadimo
    while (red.size()) {
        temp = red[0];
        red.pop_front();

        // je li temp roditelj nasemu n?
        if (temp->left == n || temp->right == n) 
            return temp;
        // ako nije, gledaj dalje potomstvo...
        // na kraj reda dodajemo djecu temp-a da se njih pregleda
        if (temp->left) 
            red.push_back(temp->left);
        if (temp->right)
            red.push_back(temp->right);
    }

    // ako nije nadjeno (nepostojeci cvor zadan)
    return NULL;    
}

void CreateLeftB(labeltype x, node n, btree *T) {
    if (n->left != NULL) {
        cout << "LeftChild vec postoji" << endl;
        return;
    }
    else {
        node temp = new cvor;
        temp->label = x;
        temp->left = temp->right = NULL;
        n->left = temp;
    }
}

void CreateRightB(labeltype x, node n, btree *T) {
    if (n->right != NULL) {
        cout << "RightChild vec postoji" << endl;
        return;
    }
    else {
        node temp = new cvor;
        temp->label = x;
        temp->left = temp->right = NULL;
        n->right = temp;
    }
}

void DeleteB(node n, btree *T) {
    if (n->left)
        DeleteB(n->left, T);
    if (n->right)
        DeleteB(n->right, T);

    node r = ParentB(n, T);
    if (r->right == n)
        r->right = NULL;
    else
        r->left = NULL;

    delete n;
}


#include "c.h"
//#include "b.h"

int main() {
    
    cout << endl << "Testiranje b i c zadatka: binarno stablo." << endl;
    btree bin;
    cout << "*Inicijalizacija*" << endl;
    InitB(100, &bin);
    ChangeLabelB(200, RootB(&bin), &bin);
    cout << "Treba pisati 200: " << LabelB(RootB(&bin), &bin) << endl;
    cout << "*Dodavanje djece.*" << endl;
    CreateRightB(300, RootB(&bin), &bin);
    CreateLeftB(301, RootB(&bin), &bin);
    node bin_root_lchild = LeftChildB(RootB(&bin), &bin);
    node bin_root_rchild = RightChildB(RootB(&bin), &bin);
    CreateRightB(311, bin_root_lchild, &bin);
    CreateLeftB(321, bin_root_lchild, &bin);
    CreateRightB(310, bin_root_rchild, &bin);
    CreateLeftB(320, bin_root_rchild, &bin);
    cout << "Treba pisati 300: " << LabelB(bin_root_rchild, &bin) << endl;
    cout << "Treba pisati 301: " << LabelB(bin_root_lchild, &bin) << endl;
    cout << "*Brisanje*" << endl;
    cout << "Adresa lchilda korijena: " << LeftChildB(bin_root_lchild, &bin) << endl;
    DeleteB(bin_root_lchild, &bin);
    cout << "Adresa lchilda korijena (nakon brisanja): " << LeftChildB(bin_root_lchild, &bin) << endl;
    cout << "Ima li root sad lchild: ";
    if (LeftChildB(RootB(&bin), &bin)) {
        cout << "ima" << endl;
    }
    else {
        cout << "nema" << endl;
    }
system ("pause");
return 0;
}

Revision: 38904

at January 10, 2011 07:43 by anton_kvesic

Updated Code

#include <iostream>

using namespace std;

typedef int labeltype;
struct cvor {
    labeltype label;
    bool used;
};

struct bt {
    cvor elementi[10000];
};

typedef bt btree;
typedef int node;

void InitB(labeltype x, btree *T) {
    for (int i = 1; i < 10000; i++) {
        T->elementi[i].used = false;
    }
    T->elementi[1].used = true;
    T->elementi[1].label = x;
}

labeltype LabelB(node n, btree *T) {
    return T->elementi[n].label;
}

void ChangeLabelB(labeltype x, node n, btree *T) {
    T->elementi[n].label = x;
}

node RootB(btree *T) { 
    return 1;
}

node LeftChildB(node n, btree *T) {
    if (T->elementi[n*2].used == true) 
        return n*2;
    else
        return 0;
}

node RightChildB(node n, btree *T) {
    if (T->elementi[n*2+1].used == true) 
        return n*2+1;
    else
        return 0;
}

node ParentB(node n, btree *T) {
   return n/2;
}

void CreateLeftB(labeltype x, node n, btree *T) {
    if (T->elementi[n*2].used == true) 
        cout << "Taj cvor vec postoji!" << endl;
    else {
        T->elementi[n*2].used = true;
        T->elementi[n*2].label = x;
    }
}

void CreateRightB(labeltype x, node n, btree *T) {
    if (T->elementi[n*2+1].used == true) 
        cout << "Taj cvor vec postoji!" << endl;
    else {
        T->elementi[n*2+1].used = true;
        T->elementi[n*2+1].label = x;
    } 
}

void DeleteB(node n, btree *T) {
    T->elementi[n].used = false;
    if (T->elementi[n*2].used == true) 
        DeleteB(n*2, T);
    if (T->elementi[n*2+1].used == true)
        DeleteB(n*2+1, T);  
}



#include <iostream>
#include <deque>

using namespace std;

typedef int labeltype;
struct cvor {
    labeltype label;
    cvor *left, *right; //
};

typedef cvor *node;
typedef cvor btree;

void InitB(labeltype x, btree *T) {
    T->label = x;
    T->left = T->right = NULL;
}

labeltype LabelB(node n, btree *T) {
    return n->label; 
}

void ChangeLabelB(labeltype x, node n, btree *T) {
    n->label = x;
}

node RootB(btree *T) { return T; }

node LeftChildB(node n, btree *T) {
    return n->left;
}

node RightChildB(node n, btree *T) {
    return n->right;
}

node ParentB(node n, btree *T) {
    // ako zelis parent od korijena, odmah gotovo
    if (n == T)
        return NULL;
    // ako ne, idemo traziti
    deque<node> red;
    red.push_back(RootB(T));
    node temp;
    // http://en.wikipedia.org/wiki/Tree_traversal#Example
    // level-order, fuckyeah
    // deque je "double ended queue"
    // Ovdje njime simuliramo red, dodajemo nepregledane
    // cvorove na kraj, a s pocetka pregledavamo i vadimo
    while (red.size()) {
        temp = red[0];
        red.pop_front();

        // je li temp roditelj nasemu n?
        if (temp->left == n || temp->right == n) 
            return temp;
        // ako nije, gledaj dalje potomstvo...
        // na kraj reda dodajemo djecu temp-a da se njih pregleda
        if (temp->left) 
            red.push_back(temp->left);
        if (temp->right)
            red.push_back(temp->right);
    }

    // ako nije nadjeno (nepostojeci cvor zadan)
    return NULL;    
}

void CreateLeftB(labeltype x, node n, btree *T) {
    if (n->left != NULL) {
        cout << "LeftChild vec postoji" << endl;
        return;
    }
    else {
        node temp = new cvor;
        temp->label = x;
        temp->left = temp->right = NULL;
        n->left = temp;
    }
}

void CreateRightB(labeltype x, node n, btree *T) {
    if (n->right != NULL) {
        cout << "RightChild vec postoji" << endl;
        return;
    }
    else {
        node temp = new cvor;
        temp->label = x;
        temp->left = temp->right = NULL;
        n->right = temp;
    }
}

void DeleteB(node n, btree *T) {
    if (n->left)
        DeleteB(n->left, T);
    if (n->right)
        DeleteB(n->right, T);

    node r = ParentB(n, T);
    if (r->right == n)
        r->right = NULL;
    else
        r->left = NULL;

    delete n;
}


#include "c.h"
//#include "b.h"

int main() {
    
    cout << endl << "Testiranje b i c zadatka: binarno stablo." << endl;
    btree bin;
    cout << "*Inicijalizacija*" << endl;
    InitB(100, &bin);
    ChangeLabelB(200, RootB(&bin), &bin);
    cout << "Treba pisati 200: " << LabelB(RootB(&bin), &bin) << endl;
    cout << "*Dodavanje djece.*" << endl;
    CreateRightB(300, RootB(&bin), &bin);
    CreateLeftB(301, RootB(&bin), &bin);
    node bin_root_lchild = LeftChildB(RootB(&bin), &bin);
    node bin_root_rchild = RightChildB(RootB(&bin), &bin);
    CreateRightB(311, bin_root_lchild, &bin);
    CreateLeftB(321, bin_root_lchild, &bin);
    CreateRightB(310, bin_root_rchild, &bin);
    CreateLeftB(320, bin_root_rchild, &bin);
    cout << "Treba pisati 300: " << LabelB(bin_root_rchild, &bin) << endl;
    cout << "Treba pisati 301: " << LabelB(bin_root_lchild, &bin) << endl;
    cout << "*Brisanje*" << endl;
    cout << "Adresa lchilda korijena: " << LeftChildB(bin_root_lchild, &bin) << endl;
    DeleteB(bin_root_lchild, &bin);
    cout << "Adresa lchilda korijena (nakon brisanja): " << LeftChildB(bin_root_lchild, &bin) << endl;
    cout << "Ima li root sad lchild: ";
    if (LeftChildB(RootB(&bin), &bin)) {
        cout << "ima" << endl;
    }
    else {
        cout << "nema" << endl;
    }
system ("pause");
return 0;
}

Revision: 38903

at January 10, 2011 07:42 by anton_kvesic

Initial Code

#include <iostream>

using namespace std;

typedef int labeltype;
struct cvor {
    labeltype label;
    bool used;
};

struct bt {
    cvor elementi[10000];
};

typedef bt btree;
typedef int node;

void InitB(labeltype x, btree *T) {
    for (int i = 1; i < 10000; i++) {
        T->elementi[i].used = false;
    }
    T->elementi[1].used = true;
    T->elementi[1].label = x;
}

labeltype LabelB(node n, btree *T) {
    return T->elementi[n].label;
}

void ChangeLabelB(labeltype x, node n, btree *T) {
    T->elementi[n].label = x;
}

node RootB(btree *T) { 
    return 1;
}

node LeftChildB(node n, btree *T) {
    if (T->elementi[n*2].used == true) 
        return n*2;
    else
        return 0;
}

node RightChildB(node n, btree *T) {
    if (T->elementi[n*2+1].used == true) 
        return n*2+1;
    else
        return 0;
}

node ParentB(node n, btree *T) {
   return n/2;
}

void CreateLeftB(labeltype x, node n, btree *T) {
    if (T->elementi[n*2].used == true) 
        cout << "Taj cvor vec postoji!" << endl;
    else {
        T->elementi[n*2].used = true;
        T->elementi[n*2].label = x;
    }
}

void CreateRightB(labeltype x, node n, btree *T) {
    if (T->elementi[n*2+1].used == true) 
        cout << "Taj cvor vec postoji!" << endl;
    else {
        T->elementi[n*2+1].used = true;
        T->elementi[n*2+1].label = x;
    } 
}

void DeleteB(node n, btree *T) {
    T->elementi[n].used = false;
    if (T->elementi[n*2].used == true) 
        DeleteB(n*2, T);
    if (T->elementi[n*2+1].used == true)
        DeleteB(n*2+1, T);  
}

Initial URL

Initial Description

Initial Title

zadatak 4 strukture podataka

Initial Tags

podataka

Initial Language

C++

Choose a language for easy browsing: