Keskustelut - C/C++ - Aloittelijan ongelma puurakenteen ja pointtereiden kanssa


editoitu: 15:12 26.3.12
The Savage Sam 15:12 26.3.12 
Terve!

Toivottavasti joku viitsii hieman jeesiä. Rakentelen omaan käyttötarkoitukseen sopivaa tietorakennetta, joka tulee olemaan hieman B-puun tapainen. Käytännössä siis haluan olion (solmun), jonka sisällä on referenssit/osoittimet toisiin samanlaisiin oliohin (solmuihin). Tämä onnistuu kätevästi, kun kyseessä on binääripuu, mutta omat taidot loppuvat kesken, kun yhteen osoittimeen pitää saada kiinni taulukollinen olioita (solmuja), joita ei vielä halutakaan alustaa juurisolmua alustettaessa, vaan ne lisättäisiin myöhemmin käyttäen omaa setChild-funktiotaan.

Mikähän mahtaa olla vikana? Olen koettanut kaikenlaisia versioita, välillä kääntäjä valittaa ja välillä ei, aina tulee kuitenkin vähintään segfault tai aborttaus.



C++
#include <iostream>
#include <string>
#include <limits>

using namespace std;


class TreeNode {       
        string name;          //Name of a tree
        int items;            // Numbers of childs.
        int maxItems;         // Maximum number of childs.
        //HUOM: Mitä seuraavalle riville?
        TreeNode** subTrees;  // Pointer to pointer of subtrees.

public:

        TreeNode(string name, int maxItems=5, int items=0) {    //Konstruktori
                this->name = name;
                this->items = items;
                this->maxItems = maxItems;
                this->subTrees = new TreeNode*[this->maxItems];
        }

        ~TreeNode() { if ( maxItems != 0 ) delete [] subTrees; maxItems = 0; }; //Destruktori

        //Method setting new childs.
        int setChild(TreeNode *tree) {
                if (items < maxItems) {
                        //HUOM: Mitä seuraavalle riville?
                        this->subTrees[this->items] = tree;
                        this->items++;
                } else {
                        cout << this->name << " has too many items." << endl;
                }
                return 0;
        }

        int print() {
                cout << this->name << endl;
                return 0;
        }

};


int main() {
        TreeNode solmu("vitonen",5);
        TreeNode vLapsi("kolme",3);

        solmu.print();
        vLapsi.print();
       
        solmu.setChild(&vLapsi);
       

        delete &solmu;
        delete &vLapsi;
        return 0;
}
LN 15:32 26.3.12 
Jo main-funktiossa on vikaa. Koska solmu- ja vLapsi-muuttujia ei ole varattu new'llä, niitä ei myöskään pidä tuhota deletellä. Niitä ei tarvitse itse tuhota mitenkään tässä tapauksessa.
editoitu: 19:16 30.3.12
pekkakarj 19:54 29.3.12 
Pääset helpommalla jos käytät valmiita kielen ominaisuuksia. Voit tehdä asiat vaikeammin myöhemmin, jos huomaat sen tarpeelliseksi. Usein kuitenkin valmis ratkaisu on riittävän hyvä kaikkeen käyttöön, joten siitä kannattaa aloittaa.

Kirjoitin siis pikaisesti koodista version, joka käyttää vector-standardisäiliötä lapsisolmujen tallentamiseen. Tässä versiossa en ole ottanut poikkeuksia mitenkään huomioon, kuten kuuluu tehdä erityisen huolella tehdyissä C++-ohjelmissa. Ohjelma vaatinee muitakin parannuksia ennen kuin on mitenkään valmis oikeaan käyttöön. Huomaa myös, että rekursiivinen print-metodi voi kuluttaa kaiken pinomuistin, jos tulostat *hyvin* syviä puurakenteita.

EDIT: Tietenkin myös destruktori on tässä esimerkissä rekursiivinen, joten sekin pitää kirjoittaa toisella tavalla jos on oikein paranoidi. Mutta ehkä puut pysyvät tarpeeksi matalina :)

Päätin myös näyttää miten elossa olevien solmujen määrän voi laskea, jotta voin demonstroida, että deletoidessa juurisolmu koko puu katoaa. Tämän takia myös root-solmu käsitellään osoittimen kautta, vaikka se ei vaikuttaisi ihan tarpeelliselta muuten.

New'n ja deleten käyttö pitää osata hyvin, että saat tietorakenteesi toimimaan. Kuten LN jo huomautti, käytit ylimääräisiä deletejä. Joka tapauksessa vektorin käyttö tekisi koodin teostasi paljon helpompaa, ja oman muistinvarauksen käytön voisit jättää sellaisiin tilanteisiin, joissa perustellusti tarvitset sitä. Ja osaat tehdä sen ilman ylimääräisiä deletointeja.

Jos koodissa on virheitä, kertokaa. Se on todellakin hyvin nopeasti tehty ja pyrin vain näyttämään yhden tavan tehdä asia.


C++

#include <iostream>
#include <string>
#include <limits>
#include <vector>

using namespace std;


class TreeNode {       
        string name;          //Name of a tree
        //int items;            // Numbers of childs.
        //int maxItems;         // Maximum number of childs.
        //HUOM: Mitä seuraavalle riville?
        vector<TreeNode*> subTrees;  // Vector of subtrees.
        typedef vector<TreeNode*>::iterator iter;
        static int count; // count of currently existing TreeNodes
public:

        static int getCount() { return count; }

        TreeNode(string n = "unnamed") : name(n) {
                ++count;
        }    //Konstruktori

        ~TreeNode() {
                for (iter i = subTrees.begin(); i != subTrees.end(); ++i)
                        delete *i;
                --count;
        } //Destruktori
               
        //Method adding new children
        void addChild(TreeNode *tree) {
                subTrees.push_back(tree);
        }

        void print(int indent = 0) {
                string prefix = string(indent, ' ');
                cout << prefix << name << endl;
                for (iter i = subTrees.begin(); i != subTrees.end(); ++i)
                        (*i)->print(indent + 2);
        }

};

int TreeNode::count = 0;

int main() {
        TreeNode *root = new TreeNode("the root");
        TreeNode *child = new TreeNode("first child");
        TreeNode *child2 = new TreeNode("second child");

        for (int i=0; i<5; ++i)
                child->addChild(new TreeNode());

        for (int i=0; i<3; ++i)
                child2->addChild(new TreeNode());

        root->addChild(child);
        root->addChild(child2);
        root->print();
        cout << "first count of nodes: " << TreeNode::getCount() << endl;

        delete root;

        cout << "second count of nodes: " << TreeNode::getCount() << endl;
        return 0;
}