B-strom – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

B-strom – C / C++ – Fórum – Programujte.comB-strom – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Siggi0
Návštěvník
24. 4. 2015   #1
-
0
-

Tak tady jsem totálně bezradný. Teoreticky to zvládám a i překreslit do sešitu, ale jak to mám naimplementovat do C, tak jsem v háji. 3H projíždím google, jestli tam není podobný kód, ale nenašel jsem nic pěkného.

http://pastebin.com/FtQR9MKE

Funkce na porovnání, nebylo co zkazit.
In,Pre,Post-order si nevím rady, protože tam nemám ukazatel left ani right, ale pouze children. Nechápu proč to tak ztěžují v té škole. Jsem z toho dost špatnej.
Funkce na vkládání, tam jsem zkoušel přepsat pseudo kód ze slidů, ale taky neuspěšně.

Nahlásit jako SPAM
IP: 46.229.123.–
Reklama
Reklama
Siggi0
Návštěvník
24. 4. 2015   #2
-
0
-

   

void splitChild(Node *node, int i){
    int t = 3;
    Node *z = (Node*)malloc(sizeof(Node));
    Node *y = node->children[i];
    z->leaf = y->leaf;
    z->n = t - 1;
    for(int j = 1; j < (t-1); j++){
        z->keys[j] = y->keys[j+t];
    }
    if(y->leaf == false){
        for(int j = 1; j < t; j++){
            z->children[j] = y->children[j+t];
        }
    }
    y->n = t - 1;
    for(int j = node->n+1; j > i+1; j--){
        node->children[j+1] = node->children;
    }
    node->children[i+1] = z;
    for(int j = node->n; j > i; j--){
        node->keys[j+1] = node->keys[j];
    }
    node->keys[i] = y->keys[t];
    node->n = node->n+1;
}

void insertNonFull(Node *node, int k){
    Node *i = node->n;
    int t = 3;
    if(node->leaf == true){
        while(i >= 1 && k < node->keys[i]){
            node->keys[i+1] = node->keys[i];
            i--;
        }
        node->keys[i+1] = k;
        node->n = node->n+1;
    }else{
        while(i >= 1 && k < node->keys[i]){
            i--;
        }
        i++;
        if(node->children[i]->n == 2*t-1){
            splitChild(node, i);
            if(k > node->keys[i]){
                i++;
            }
        }
        insertNonFull(node->children[i], k);
    }
}

void insertBTree(BTree *tree, int key)
{
    Node *node = tree;
    int t = 3;

    if(node->n == 2*t-1){
        Node *s = mallocNode(0, false);
        tree->root = s;
        s->children[1] = node;
        splitChild(s, 1);
        insertNonFull(s, key);
    }else{
        insertNonFull(node, key);
    }
}

Tak nějak má vypadat funkce pro insert, je tam plno chyb a u parametru t si nejsem jist jaká má být hodnota.

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
24. 4. 2015   #3
-
0
-

Stromy a ADT já rád. Když to nevyřešíš do zítřka, během dne se ti na to podívám :-).

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
24. 4. 2015   #4
-
0
-

#3 ondrej39
Haldy a Binární vyhledávací stromy jsem docela zvládal a bylo to docela lehké na pochopení, ale červeno černé stromy ty jsem nepobral vůbec. B-stromy si myslím, že umím obstojně tužkou a papírem, ale implementací vůbec. Zatím stále nad tím sedím a čtu slidy a strýčka googla.

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
24. 4. 2015   #5
-
0
-

#4 Siggi
Mrkni se tady na web na moc hezký vizualizace, pokud jsi ten web ještě neviděl. https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
24. 4. 2015   #6
-
0
-

#5 ondrej39
Tuto stránku znám, ukazoval nám ji i náš cvičící. Je dobré, že si navolíš i preventivní rozdělení, protože to tak musíme používat z přednášky. Jak říkám, ta vizualizace je dobrá a na papíře to zvládnu, horší je to naimplementovat. Proto se více bojím závěrečného implementačního testu než zkoušky, kde je většinou tužka, papír a teorie + něco málo implementace.

Nahlásit jako SPAM
IP: 46.229.123.–
ondrej39+1
Věrný člen
25. 4. 2015   #7
-
0
-

#6 Siggi
No hele, nebudu to sám vymýšlet, ale inspiroval bych se touto implementací.

Každopádně už funkci pro rozdělování potomků máš špatně. Ten původní kód je psaný v C++ a funkce splitChild je metoda třídy BTreeNode. To znamená, že jako taková má přístup k atributům objektu, na němž se metoda spouští (void BTreeNode::splitChild(int i, BTreeNode *y)).

Když se podíváš na zdroják té metody, tak tam pracuje se třemi proměnnými typu BTreeNode. První, nejlépe viditelný, je ten y, předávaný jako parametr, druhý je Uzel vytvořený přímo v metodě, uzel z, a třetí uzel je ten objekt, který metodu invokuje, this. Pokud tuto funkci budeš přepisovat do C, tam žádné objekty nejsou, ale ty ten třetí, this, objekt nějak do funkce dostat musíš, a potřebuješ proto ještě další parametr.

Nahlásit jako SPAM
IP: 46.39.172.–
Inject all the dependencies!
Siggi0
Návštěvník
25. 4. 2015   #8
-
0
-

#7 ondrej39
 

void splitChild(Node **node, int i){
    int t = 2;
    Node *z = (Node*)malloc(sizeof(Node));
    Node *y = (*node)->children[i];
    z->leaf = y->leaf;
    z->n = t - 1;

    for(int j = 0; j < (t-1); j++){
        z->keys[j] = y->keys[j+t];
    }
    if(y->leaf == false){
        for(int j = 0; j < t; j++){
            z->children[j] = y->children[j+t];
        }
    }
    y->n = t - 1;
    for(int j = (*node)->n; j >= (i+1); j--){
        (*node)->children[j+1] = (*node)->children[j];
    }
    (*node)->children[i+1] = z;
    for(int j = (*node)->n; j > i; j--){
        (*node)->keys[j+1] = (*node)->keys[j];
    }
    (*node)->keys[i] = y->keys[t-1];
    (*node)->n = (*node)->n+1;
}

void insertNonFull(Node **node, int key){
    int i = (*node)->n;
    int t = 2;
    if((*node)->leaf == true){
        while(i >= 1 && (*node)->keys[i] > key){
            (*node)->keys[i+1] = (*node)->keys[i];
            i--;
        }
        (*node)->keys[i+1] = key;
        (*node)->n = (*node)->n+1;
    }else{
        while(i >= 1 && (*node)->keys[i] > key){
            i--;
        }
        i++;
        if((*node)->children[i]->n == 2*t-1){
            splitChild(*node, i);
            if((*node)->keys[i] < key){
                i++;
            }
        }
        insertNonFull((*node)->children[i], key);
    }
}
void insertBTnode(Node **node, int key){
    int t = 2;
    if(*node == NULL){
        *node = mallocNode(t, true);
        (*node)->keys[0] = key;
        (*node)->n = 1;
    }else{
        if((*node)->n == 2*t-1){
            Node *s = (Node*)malloc(sizeof(Node));
            *node = s;
            s->leaf = false;
            s->n = 0;
            s->children[1] = *node;
            splitChild(s, 1);
            insertNonFull(s, key);
        }else{
            insertNonFull(*node, key);
        }
    }
}

void insertBTree(BTree *tree, int key)
{
    insertBTnode(&tree->root, key);
}

Chyba u funkce insertNonFull u  (*node)->keys[i+1] = key; ... stejnak se v tom ztrácím

Nahlásit jako SPAM
IP: 46.229.123.–
Siggi0
Návštěvník
25. 4. 2015   #9
-
0
-

#8 Siggi
Tak to jsem vyřešil. U těch pomocných jsem oddělal ukazatel na ukazatel a nechal jen jeden, ale dál už jsem nepokročil.

Už mi to nepřemýšlí, zítra zase na to kouknu.

Nahlásit jako SPAM
IP: 46.229.123.–
Siggi0
Návštěvník
26. 4. 2015   #10
-
0
-

   

void splitChild(Node *node, int i){
    int t = 2;
    Node *y = node->children[i];
    Node *z = mallocNode(t, y->leaf);
    z->n = (t - 1);

    for(int j = 0; j < (t-1); j++){             // nejpravejsi prvek na rozdeleni
        z->keys[j] = y->keys[j+t];
    }
    if(node->leaf == false){
        for(int j = 0; j < t; j++){
            z->children[j] = y->children[j+t];
        }
    }
    y->n = (t - 1);
    for(int j = node->n; j >= (i+1); j--){
        node->children[j+1] = node->children[j];
    }
    node->children[i+1] = z;
    for(int j = node->n; j > i; j--){
        node->keys[j+1] = node->keys[j];
    }
    node->keys[i] = y->keys[t-1];
    node->n = node->n+1;
}

void insertNonFull(Node *node, int key){
    int i = node->n-1;
    int t = 2;
    if(node->leaf == true){
        while(i >= 0 && node->keys[i] > key){
            node->keys[i+1] = node->keys[i];
            i--;
        }
        node->keys[i+1] = key;
        node->n = node->n+1;
    }else{
        while(i >= 0 && node->keys[i] > key){
            i--;
        }
        if(node->children[i+1]->n == 2*t-1){
            splitChild(node, (i+1));
            if(node->keys[i+1] < key){
                i++;
            }
        }
        insertNonFull(node->children[i+1], key);
    }
}
void insertBTnode(Node **root, int key){
    int t = 2;
    Node *node = *root;

    if(*root == NULL){
         *root = mallocNode(t, true);
        (*root)->keys[0] = key;
        (*root)->n = 1;
    }else{
        if(node->n == 2*t-1){
            Node *s = mallocNode(t, false);
            *root = s;
            s->children[0] = node;
            splitChild(s, 0);
            insertNonFull(s, key);
        }else{
            insertNonFull(node, key);
        }
    }
}

void insertBTree(BTree *tree, int key)
{
    insertBTnode(&tree->root, key);
}

už fakt nevím

Nahlásit jako SPAM
IP: 46.229.123.–
Siggi0
Návštěvník
26. 4. 2015   #11
-
0
-

Čas vypršel.

Nahlásit jako SPAM
IP: 46.229.123.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 111 hostů

Podobná vlákna

2-3-4 strom v C — založil SpartakusCZ

Binární strom — založil garamond

Strom složek — založil Míra

Binarny strom — založil gogo0152

Binární strom — založil Tomáš

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý