Coming soon. Dasselbe Programm gibt es auch in VisualBasic. Demnächst hier.
Datenstrukturen und Algorithmen sind sehr eng miteinander verbunden. Einige Datenstrukturen treten so haeufig in Algorithmen auf, dass man sie als elementar bezeichnen kann. Felder, Stapel und Schlangen oder verkettete Listen sind von wesentlicher Bedeutung fuer die Programmierung. Im Folgenden werden Sie deshalb diese Datenstrukturen naeher kennenlernen.
Eine sehr wichtige Datenstruktur, die in den meisten Programmiersprachen schon als grundlegender Datentyp zur Verfuegung steht sind Felder. Ein Feld ist eine Folge von gleichen Datentypen, die zusammenhaengend gespeichert werden. Die einzelnen Elemente dieses Feldes werden ueber Indizes angesprochen. Das Feld wird haeufig auch als Vektor oder Array bezeichnet. Wir kennen diese Datenstruktur aus dem Kapitel Arrays.
Das Arbeiten mit Feldern soll das folgende Beispiel verdeutlichen. Es wird ein Feld zur Aufnahme von 10 Strings angelegt. Anschliessend werden Zeichenketten in dieses Feld eingelesen. Nachdem das Array gefuellt ist, werden die einzelnen Strings wieder ausgelesen und ausgegeben.
#include#define ZEILENZAHL 10 #define ZEILENLAENGE 80 int main() { char text[10][80]; char (*zeile)[80]; int i; zeile=text; printf("Bitte geben Sie nun %d Zeilen Text ein:\n",ZEILENZAHL); fflush(stdin); for(i=0;i<10;i++){ printf("%d >> ",i); gets(text[i]); } printf("Ihr Text war der folgende:\n"); while(zeile < ( char (*)[80] ) text[ZEILENZAHL]) printf("%s\n",zeile++); printf("Und einmal zurueck\n"); while(zeile > text) printf("%s\n",--zeile); return(0); }
#includeint main() { char s1[80],s2[80],s3[80]; char *array[3]; int i; array[0] = s1; array[1] = s2; array[2] = s3; for(i=0;i<3;i++){ printf("Ein Satz: "); gets(array[i]); } printf("Wenn Sie eine 0 eingeben, endet das Programm! \n"); while((i = getchar() - '0')!=0){ printf("Satz %d : %s\n",i,array[i]); fflush(stdin); } return(0); }
Die Stapel sind eine besondere Form, Daten zu sortieren. Man stelle
sich einen Stapel Blaetter vor, die auf dem Schreibtisch liegen. Um an
das unterste Blatt heranzukommen, muss ich schon alle anderen Blaetter
vorher wegnehmen.-
Der Stapel in der Informationstechnik findet sich z.Bsp. im
Hauptspeicher des Rechners. Z.Bsp. Ruecksprungadressen von
Funktionen werden hier abgelegt und auch der Reihe nach wieder
heruntergenommen. Last in, First out. lifo-Prinzip. Im hier zu
besprechenden Beispiel wollen wir einen mathematischen Ausdruck
berechnen. In normaler Schreibweise (Infix-Notation) wuerde man
sagen:
5*4+3 (5*(4+3))
in der Praefix-Notation, sieht das
folgendermassen aus:
+*543 (*5+43) und in der Postfix-Schreibweise:
543+* (54+3*)
Die Berechnung eines Postfix-Ausdrucks kann leicht mit einem Programm
realisiert werden, das sich eines Stapel-Alogerithmuses bedient.
_________________________________________________________________
| n = 1 |
_________________________________________________________________
| Solange n <= Laenge des Strings Postfix |
| _______________________________________________________________
| | Postfix ist |
| |-------------------------------------------------------------|
| | eine | ein | |
| | Ziffer | Operator | sonstiges |
| |______________________________________________________________
| | Zifferfolge lesen | Operanden A und B | / |
| | und Zahl | vom Stapel holen | / |
| | zusammenfuegen | | / |
| |______________________________________________________________
| | Zahl auf den | Operator auf A | / |
| | Stapel legen | und B anwenden | / |
| | |_______________________| |
| | | Ergebnis auf den | |
| | | Stapel legen | |
|________________________________________________________________
| Ergebnis vom Stapel nehmen |
_________________________________________________________________
_________________________________________________________________
Stapel Postfix-Term Operation
_________________________________________________________________
45*67*+ 4 auf den Stapel legen
4 5*67*+ 5 auf den Stapel legen
5,4 *67*+ Die beiden obersten Werte vom
Stapel nehmen und per *
verknuepfen (4*5) und das Ergebnis
20 auf den Stapel legen.
20 67*+ 6 auf den Stapel legen
6,20 7*+ 7 auf den Stapel legen
7,6,20 *+ Die beiden obersten Werte vom
Stapel nehmen und per * (7*6)
verknuepfen und das Ergebnis 42
auf den Stapel legen.
42,20 + Die beiden obersten Werte vom
Stapel nehmen und per +
verknuepfen und das Ergebnis auf
den Stapel legen.
62 Ergebnis vom Stapel nehmen.
__________________________________________________________________
#include#include char postfix[20],c; // Eine Zeichenkette int n,m,x,tos,stack[20]; //Auf den Stapel werden nur Zahlen gelegt // Umwandeln eines Zeichens in eine int-Zahl (Zeichen - '0') liefert das int atoi(char c) { int i; i= c - '0'; return i; } void init_stack() { tos=0; } void push(x) if(tos == 200) { printf("Stapelueberlauf\n"); } else { //an der Stelle(tos) wird der neue Wert in den Stapel gelegt. stack[tos]=x; //danach wird der Wert von tos um 1 erhoeht, so das ich //einen neuen Wert auf den Stapel ablegen kann. tos = tos +1; } } int pop() if(tos == 0) { printf("Stapelunterlauf\n"); } else { //tos zeigt auf eine freie Stelle im Stapel tos = tos -1; //an dieser Stelle soll der Stapel einen neuen Wert aufnehmen } return(stack[tos]); }
Auswahl: Wenn eine Zahl vorliegt, dann Zahl auf den Stapel legen. Falls
ein Operand gefunden wird, die letzten beiden Operanden vom Stapel
nehmen und mit dem Operator verknuepfen und das Ergebnis auf den
Stapel legen.-
Hauptroutine
int main()
{
printf("Ein Ausdruck: ");
scanf("%s",postfix);
init_stack();
m=strlen(postfix);
n=0;
while(n kleiner m)
{
switch(postfix[n])
{
case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
c=postfix[n];
x=atoi(c);
break;
case '+':
x=pop()+pop();
break;
case '-':
x=pop();
x=pop()-x;
break;
case '*':
x=pop()*pop();
break;
case '/':
x=pop();
x=pop()/x;
break;
} //end switch
push(x);
n++;
} //end while n kleiner m
x=pop(); // Ergebnis vom Stapel nehmen.
printf("Das Ergebnis: %d\n",x);
return(0);
}
Die Stapelroutinen sind als Funktionen realisiert. Dies sind
init_stack fuer die Initialisierung des Stapels, push fuer das Ablegen
eines Wertes und pop fuer das Herunternehmen vom Stapel.
Ausserdem musste ich eine Routine schreiben fuer das Umwandel eines
Strings in Zahlen. Die Funktion atoi(x). Am einfachsten kann char -
'0' dies leisten.-
Ausserdem sollte fuer die Rechenoperation beachtet werden, das der
zweite Operand vor dem ersten im Stapel liegt und daher voruebergehend
in x gespeichert werden muss.
Der Stapel selbst wird als Array stack[] initialisiert, das maximal
200 Elemente aufnehmen kann. Die Variable tos enthaelt immer den Index
der Zelle im Stack, die als naechstes gefuellt werden kann.
init_stack setzt die Variable tos auf null.
Bei den Routinen pop und push ist zu beachten, das der Stapel ueber
oder unterlaufen kann. Daher die Sicherheitsabfrage mit if().
Die Auswahlentscheidung treffen wir mit switch.