B Baum

uebbaum.cpp

//uebbayer.cpp - Übung zu den Bayer Bäumen
//Philipp Spieß
//28.05.2009

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

#define MAX 4

typedef struct
{
       int k;
       int p;
} Keypointer;

struct Page
{
       int m;
       int p0;
       Keypointer kp[MAX];
};

int searchpage(int wert, int pageptr, struct Page a[100]){
    int i;
    int oldptr;

    for( i = 0; i < a[pageptr].m; i++)
    {
        //printf("\n\nwert = %d\ncmp = %d\ni = %d\n",wert,a[pageptr].kp[i].k,i);
        if(wert < a[pageptr].kp[i].k)
        {
            //puts("wert < cmp\n");
            //take the old ptr
            if(a[pageptr].p0 == 0)
            {
                return -1;
            }
            if(i == 0){
                //printf("jmp to %d\n", a[pageptr].p0);
                return searchpage(wert, a[pageptr].p0, a);
            }else{
                //printf("jmp to %d\n", a[pageptr].kp[oldptr].p);
                return searchpage(wert, a[pageptr].kp[oldptr].p, a);
            }
        }else if(wert == a[pageptr].kp[i].k){
            //puts("wert == cmp\n");

            //printf("Found key at a[%d].kp[%d]\n", pageptr, i);
            return pageptr;
        }else if(i == (a[pageptr].m - 1) && wert > a[pageptr].kp[i].k){
        
            if(a[pageptr].p0 == 0)
            {
                return -1;
            }
            //puts("wert < cmp && i == last\n");
            //printf("jmp to %d\n", a[pageptr].kp[i].p);
            return searchpage(wert, a[pageptr].kp[i].p, a);
        }
        oldptr = i;
    }

    return -1;
    
}

int last_level(int wert, int pageptr, struct Page a[100]){
    int i;
    int oldptr;
    
    for( i = 0; i < a[pageptr].m; i++)
    {
        if(wert < a[pageptr].kp[i].k)
        {
            if(a[pageptr].p0 == 0)
            {
                return pageptr;
            }
            if(i == 0){
                return last_level(wert, a[pageptr].p0, a);
            }else{
                return last_level(wert, a[pageptr].kp[oldptr].p, a);
            }
        }else if(i == (a[pageptr].m - 1) && wert > a[pageptr].kp[i].k){
        
            if(a[pageptr].p0 == 0)
            {
                return pageptr;
            }
            return last_level(wert, a[pageptr].kp[i].p, a);
        }
        oldptr = i;
    }
    return pageptr;
    
}

void sorted_print(int pageptr, struct Page a[100]){
     
     int i;
     if(a[pageptr].p0 != 0) {
         for( i = 0; i < a[pageptr].m; i++)
         {
              if( i == 0 ){
                  sorted_print(a[pageptr].p0, a); // Links von 25
              }
              printf("%d ", a[pageptr].kp[i].k); // 25
              sorted_print(a[pageptr].kp[i].p, a); // rechts von 25
         }
    } else {
      for (i = 0; i < a[pageptr].m; i++)
      {
          printf("%d ", a[pageptr].kp[i].k);
      }    
    }
    if(pageptr == 0)
        printf("\n");
}


int lesser_insert(int wert, struct Page a[100]) {
    int i;
    int pageptr;
    int stelle = -1;
    if(searchpage(wert, 0, a) != -1) {
        printf("Wert existiert bereits!\n");
        return 0;
    }
    
    pageptr = last_level(wert, 0, a); // Das letze level :)
    
    printf("bin in ebene %d\n", pageptr);   
    
    if(a[pageptr].m == MAX ) {
        printf("Kein Platz verfügbar!\n");
        return 0;
    }
    
    for ( i = 0; i < a[pageptr].m; i++ )
    {
        if(stelle == -1)  // er hat seine stelle noch nicht gefunden also muss er weiter zählen
            if(a[pageptr].kp[i].k > wert) {
                stelle = i; // hier ist die stelle xD start shifting
            }             
    }
    
    for ( i = MAX - 1; i > stelle; i--) {
        a[pageptr].kp[i].k = a[pageptr].kp[i - 1].k;
        a[pageptr].kp[i].p = 0;
        
    }

    a[pageptr].kp[stelle].k = wert;
    a[pageptr].kp[stelle].p = 0;
    
    a[pageptr].m++;
    
    /** DEBUG ONLY 
    for ( i = 0; i < MAX; i++)
    {
        printf("%d. [%d|%d]\n", i, a[pageptr].kp[i].k, a[pageptr].kp[i].p);
    }
    */
    
    return 1;

}


int main()
{
    struct Page a[100]={
		 {1, 1, { {25, 2} } },                          // 0
		 {2, 3, { {10,4}, {20,5} } },                   // 1
		 {2, 6, { {30,7}, {40,8} } },                   // 2
		 {4, 0, { {2,0,}, {5,0}, {7,0}, {8,0} } },      // 3
		 {4, 0, { {13,0}, {14,0}, {15,0}, {18,0} } },   // 4
		 {2, 0, { {22,0}, {24,0} } },                   // 5
		 {3, 0, { {26,0}, {27,0}, {28,0} } },           // 6
		 {3, 0, { {32,0}, {35,0}, {38,0} } },           // 7
		 {4, 0, { {42,0}, {42,0}, {45,0}, {46,0} } }    // 8
    };
    
    int auswahl = -1;
    int wert;
    
    do {
        printf("Was willst du tun?\n");
        printf("1. Suchen\n");
        printf("2. Ausgeben\n");
        printf("3. Low Level Einfuegen\n");
        scanf("%d", &auswahl);
        
        switch(auswahl) {
            case 1: 
                    printf("Gib Wert ein: ");
                    scanf("%d", &wert);
                    if(searchpage(wert, 0, a) != -1)
                        printf("gefunden!");
                    else
                        printf("nicht gefunden!");
                    break;
            case 2: 
                    sorted_print(0, a);
                    break;
            case 3: 
                    printf("Gib Wert ein: ");
                    scanf("%d", &wert);
                    lesser_insert(wert, a);
                    break;
        }
    } while(auswahl != 0);

    
    system("PAUSE");
}