003
09.03.2008, 13:37 Uhr
~urilaiberl
Gast
|
Teil 2 des Quelltextes
| C++: |
//********************* Neuen Satz erzeugen ***********
void satz:: satz_erzeugen() // vor zeigt auf vorgänger
{char*n=input("suchbegriff eingeben ");
char*b= input ("Bemerkung eingeben ");
satz_neu(n,b);
}
void satz::satz_neu(char*n,char* b)
{
satz *x=new satz(); // (satz *)malloc(sizeof(satz));
x->name=n;x->bem=b;x->kl=x->gr=0;
if (ROOT==0){x->z=0;ROOT=x;err=0;return; } //nur bei Neuaufbau der ROOT
satz *vor=x->z=einbaustelle(ROOT,x->name); //Vorgänger suchen und im Rückzeiger einbauen
//Zeiger des Vorgängers aktualisieren
if(strcmp(vor->name,x->name)>0) // Vorgängername größer als akt daher Kleinerzweig
vor->kl=x; // Kleinerzeiger des Vorgängers setzen
else vor->gr=x; //Sonst Größerzeiger
/* kürzer
x->z=einbaustelle(ROOT,x->name);
if(strcmp((x->z)->name,x->name)>0)(x->z)->kl=x; //Vorgänger > akt ->Kleinerzweig
else (x->z)->gr=x; //Sonst Größerzeiger
*/
akt=x; //neuer Satz =aktueller
}
satz * satz::einbaustelle(satz *x,char *such) //Suche nach diesen Satz bis zum Zweigende
{satz *i=x=ROOT;
while (x) //solange ein Zeiger auf Datensatz existiert
{i=x; //merkt sich den Datensatzzeiger vor der Neusetzung da dieser zurückgeliefert wird
if (strcmp(x->name,such)<=0)x=x->gr; // Struct auf GrößerZeiger
else x=x->kl; // Struct auf KleinerZeiger
}
return i; //Rückgabe des Zeigers letzten gefundenen Datensatzes (=Vorgänger)
}
// *************Datensatz suchen****************
void satz::satz_suchen(char *such)
{
satz *x=ROOT;
while (x) //solange ein Zeiger existiert
{if (strcmp(x->name,such)==0){akt=x;err=5;return; }//gefunden
else if (strcmp(x->name,such)<0)x=x->gr; // Struct auf GrößerZeiger
else x=x->kl; // Struct auf KleinerZeiger
} //ende while Folgezeiger existiert
err=4;
}
// **** sequentiell vorwärts nächst größerer im Baum ***************
satz * satz::naechster()
{
satz *i=akt;
if (!i)return 0; //kein aktueller Datensatz zum weiterlesen
char *verg=i->name; //aktuellen Vergleichswert retten
if( i->gr){ i=i->gr; // gibt es einen größerzeiger dann nachsetzen
while(i->kl)i=i->kl; // solange kleinerzeiger vorhanden nachsetzen
akt=i; // gefunden
return i;
}
else { // es gibt keinen Gößerzeiger daher im Baum zurück
while (i->z){i=i->z; //Vorgänger laden wenn es einer im Baum ist
if (strcmp(i->name,verg)>0) //ist Vorgänger > Vergleich
{akt=i; return i;} //dann gefunden
}
err=1;return 0; // nicht gefunden da bei Root von größer angek.
}
}
// **** sequentiell rückwärts nächst kleinerer im Baum ***************
/* der nächst kleinere Datensatz ist, wenn es einen Kleiner-Zeiger gibt
am Ende des Größer-Zweiges. Existiert kein Größerzweig, dann ist
der unmittelbar auf den Kleinerzeiger folgende Satz
*/
satz * satz::vorher()
{
satz *i=akt;
if (!i)return 0; //kein aktueller Datensatz zum weiterlesen
char *verg=i->name; //aktuellen Vergleichswert retten
if( i->kl){i=i->kl; // wenn es einen kleinerzeiger gibt dann dort
while(i->gr)i=i->gr; // an das Ende des Größerzweiges
akt=i;return i; // dort ist der nächst kleinere
} //Ende if es gibt einen Kleinerzeiger
else // es gibt keinen Kleinerzeiger daher im Baum zurück
{
while(i->z){i=i->z; // solange es einen Vorgänger im Baum gibt
if (strcmp(i->name,verg)<=0) {akt=i; return 0;} //gefunden
//ist Vorgänger kleiner als Vergl dann war Vergl im Größerzweig
//der mögliche Kleinerzweig kann nur kleinere Werte als der Knoten
//haben daher ist der Knoten der nächst kleinere --> gefunden
} //Ende while es gibt keinen Rückzeiger mehr
err=3;return 0; // nicht gefunden da bei Root von Kleinerzweig angek.
}// ende else
}
// **** sequentiell erster im Baum ***************
satz * satz::erster()
{
satz *i=ROOT; if(!ROOT)return 0; //kein aktueller Datensatz
while(i->kl)i=i->kl; // solange Kleinerzeiger vorhanden nachsetzen
akt=i; // gefunden
return i;
}
// **** sequentiell letzter im Baum ***************
char * satz::letzter()
{
satz *i=ROOT; if(!ROOT)return 0; //kein aktueller Datensatz
while(i->gr)i=i->gr; // solange Größerzeiger vorhanden nachsetzen
akt=i; // gefunden
return 0;
}
void satz::alle()
{long nr; satz*i=erster();
char zeile[80];
for(nr=1;i;i=naechster(),nr++)
{sprintf(zeile,"%2i %10s %10s i=%p gr=%p kl=%p z=%p", nr,i->name,i->bem,i,i->gr,i->kl,i->z);
puts (zeile);
if (!(nr%10)){ cout<<"\nweiter mit Taste \n";getch(); }
}
}
void satz::ausgabe ()
{
cout <<endl<< error[err]<<endl;
err=0;
if (akt) {cout<<"aktueller satz = "<<akt->name<<'\t'<<akt->bem<<endl; }
cout<<"\nsuchen -> s\tweiter -> +\tvorher -> -\terster -> 1\tletzter -> l\n"
<< "Neu -> n\tAlle -> a\tEnde -> ESC"<<endl;
}
FILE *satz:: in=0; FILE *satz::out=0;
satz *satz::akt=0;
char satz::error[9][16]={ " ","dateiende ","Dateifehler ",
"dateianfang ","nicht gefunden","wurde gefunden",
" "," "," "};
int satz::err=0;
satz *satz::ROOT=0;
void main (void)
{
satz x;
char* such,w;
x.laden();// in konstruktor nicht möglich,da bei jeder Anlage laden aufgerufen wird;
do{
x.ausgabe();
switch (w=getch())
{ case 'n':x.satz_erzeugen();break;
case 's':such=input("suchbegriff eingeben ");
x.satz_suchen(such);
free(such);
break;
case '+':x.naechster();break;
case '-':x.vorher();break;
case '1':x.erster();break;
case 'l':x.letzter();break;
case 'a':x.alle();break;
case 27: break;
}
}while(w!=27);
}
|
Wenn ich dieses Beispiel sehe wird mir echt kotzübel. Das kann doch nicht sein das sowas in einem Tutorial erklärt wird das den Leuten einen Binärbaum näher bringen möchte?
Gruß
Uri |
