SUCHE MIT Google
Web virtualuniversity.ch
HOME DIDAKTIK ECDL ELEKTRONIK GUIDES HR MANAGEMENT MATHEMATIK SOFTWARE TELEKOM
DIENSTE
Anmeldung
Newsletter abonnieren
Sag's einem Freund!
VirtualUniversity als Startseite
Zu den Favoriten hinzufügen
Feedback Formular
e-Learning für Lehrer
Spenden
Autoren login
KURSE SUCHEN
Kurse veröffentlichen

Suche nach Datum:

Suche mit Schlüsselwort:

Suche nach Land:

Suche nach Kategorie:
PARTNER
ausbildung24.ch - Ausbildungsportal, Seminare, Kursen... 

 
HTMLopen.de - Alles was ein Webmaster braucht

 
PCopen.de - PC LAN Netze und Netzwerke - alles was ein IT Profi und Systemtechnicker braucht

SOFTWARE
Manchmal ist es wichtig, das erste Vorkommen eines Schlüssel zu finden (also 4). Außerdem kann es vorkommen, daß ein Schlüssel gar nicht gefunden wird. Die vorgestellten Funktionen signalisieren dies, indem sie den Index -1 zurückgeben.

Lineare Suche

Wenn man nichts über die Anordnung der Komponenten im Array weiß, bleibt einem nichts anderes übrig, als sie beginnend bei der ersten Komponente linear zu durchsuchen, bis man entweder die gesuchte Komponente gefunden hat, oder bis das Ende des Arrays erreicht wurde. Im statistischen Mittel werden bei N Tabelleineinträgen N/2 Suchschritte benötigt, im günstigsten Fall nur einer und im schlechtsten Fall N Schritte.
Um nicht jedesmal prüfen zu müssen, ob das Ende des Arrays schon erreicht ist, wenden wir einen kleinen Trick an: Am Ende des Arrays fügen wir noch ein Element an, das genau dem gesuchten Wert entspricht - auf diese Weise wird dann jedesmal ein Wert gefunden. Natürlich muß anschließend geprüft werden, ob der gefundene Wert nun ein "echter" Treffer oder die eigene Endemarke war. Diese Endemarke wird "Sentinel" genannt. Die Konstante Tablesize muß entsprechend großzügig gewählt werden.
Die Funktion LinSearch hat als Parameter den Suchschlüssel und gibt den gefundenen Index zurück:
                                       int LinSearch(int Key, int Table[])
                                         {
                                         int Index;
                                         Table[TableSize] := Key;
                                         Index := 0;
                                         while (Table[Index] != Key) 
                                           Index++;
                                         if (Index = TableSize) 
                                           Index := -1;
                                         return(Index);
                                         }
                                       
Wie man sieht, wird im ersten Schritt der Sentinel gesetzt, dann wird der Index auf 0 initialisiert und dann so lange erhöht, bis der Key gefunden wurde. Zum Schluß wird noch geprüft, ob der Index außerhalb des gültigen Bereichs liegt. In diesem Fall wird der Index auf -1 korrigiert, denn das ist der Wert für "nicht gefunden". Daß der Algorithmus stets das erste Vorkommen des Keys findet, ist offensichtlich.

Binäre Suche

Um die Suche zu beschleunigen, müssen die Elemente in der Tabelle sortiert vorliegen. Dies kann man entweder durch eines der später beschriebenen Sortierverfahren erreichen, oder indem man neue Elemente gleich an der richtigen Stelle einfügt. Beides benötigt zusätzlichen Aufwand, spart aber Zeit beim Suchen. Wie nutzt man nun die Ordnung in der Tabelle aus?

Man sucht das mittlere Element der Tabelle und prüft, ob es größer oder kleiner als dder Key ist. Ist es größer oder gleich, braucht man nur noch in der unteren Hälfte der Tabelle zu suchen, ist es kleiner, sucht man nur noch in der oberen Hälfte. Irgendwann ist die Größe des Suchintervalls auf 1 geschrumpft, und dann hat man das gesuchte Element gefunden, oder es ist nicht vorhanden. Die Zahl der Suchschritte reduziert sich bei N Tabelleneinträgen auf ln(N) (ln: Logarithmus zur Basis 2).

Der folg}e Algorithmus benutzt die Variablen L(inks) und R(echts), um den Suchbereich zu definieren, sowie Middle, um die Mitte zu markieren. Soll oberhalb der Mitte weitergesucht werden, wird L zu Middle + 1, wird im unteren Teil weitergesucht, so ergibt sich R = Middle.

                                       int BinSearch (int Key, int Table[])
                                         {
                                         int L, R, Middle;
                                       
                                         L := 1;
                                         R := TableSize + 1;
                                         while (L < R)
                                           {
                                           Middle := (L + R) / 2;
                                           if (Table[Middle] < Key) L := Middle + 1;
                                           else                        R := Middle;
                                           }
                                         if (Table[R] == Key) return(R);
                                         else                 return(-1);
                                         }
                                       
Wenn die Funktion das gesuchte Element früher als erwartet findet (z. B. wenn es genau in der Mitte liegt), könnte sie eigentlich abbrechen. Es ist dann nicht mehr garantiert, daß man das erste Vorkommen von Key findet.

Sortieren von Tabellen

Das Sortieren ist eines der wichtigsten Gebiete der Datenverarbeitung. Etwa 25% aller Rechenzeit im kommerziellen Bereich wird auf das Sortieren von Daten verwendent. An Beispielen zum Sortieren mangelt es nicht:
  • Statistiken
  • Telefonbücher, Wörterbücher
  • Listen, ...
Die Problemstellung: Gegeben ist ein Array mit Komponenten, die nach ihrem Schlüssel sortiert werden können, über deren momentane Anordnung jedoch nichts bekannt ist (das heißt auch, daß sie theoretisch schon sortiert sein oder in der umgekehrten Reihenfolge vorliegen könnten). Der Sortieralgorithmus soll die Elemente in die richtige Reihenfolge bringen.

Definition:

"Unter Sortieren versteht man allgemein den Prozess des Anordnens einer gegebenen Menge von Objekten in einer bestimmten Ordnung."

Das Sortieren ist ebenfalls einer der Grundalgorithmen in der Informatik insbesondere für die effiziente Speicherung von Informationen hinsichtlich der Auswertung bzw. Suche. Bei den Sortierverfahren unterscheidet man die

  • interne Sortierung: als Bearbeitung von Listen im Hauptspeicher,

  • externe Sortierung: als Bearbeitung von Listen, die sich auch auf externen Speichermedien (Magnetband, Festplatte) befinden können.

Bubblesort

Bubblesort ist einer der einfachsten Sortieralgorithmen. Im ersten Durchgang wird das Array vom Ende bis zum Anfang bearbeitet und bei jedem Schritt die aktuelle Komponente mit der nächsten verglichen. Ist die untere Komponente kleiner als die obere, werden die beiden vertauscht. Die größere Komponente behält also ihren Platz und die jeweils kleinere wandert weiter nach oben.
Im nächsten Durchlauf wird dann die zweitkleinste Komponente gesucht und nach oben durchgereicht. Logischerweise muß dieser Durchlauf nicht ganz bis zum Anfang gehen, sondern nur bis Index 1. der dritte Durchlauf läuft nur noch bis Index 2, usw. - bis das Verfahren abgeschlossen ist. Der Name "Bubblesort" kommt daher, daß die kleineren Komponente aufsteigen wie Blasen in einer Flüssigkeit.
                                       void Bubblesort (int Table[])
                                         {
                                         int x;
                                         int Run, Index;
                                         for (Run = 1;  Run < TableSize; Run++)
                                           {
                                           for (Index = TableSize; Index >= Run; Index--)
                                             {
                                       	  if (Table[Index] < Table[Index - 1])
                                       	    {
                                       	    x := Table[Index];
                                       	    Table[Index] := Table[Index - 1];
                                       	    Table[Index - 1] := x;
                                       	    }
                                       	  }
                                       	}
                                         }
                                       
Deutlich zu erkennen ist der Vertauschungsvorgang, bei dem die "untere" Komponente zunächst in der Variablen x zwischengespeichert wird, dann den Wert der "oberen" zugewiesen bekommt und anschließend x im "oberen" Index gespeichert wird.

Bubblesort genießt keinen besonders guten Ruf, weil es sehr langsam ist. Trotzdem ist es häufig anzutreffen, nicht zuletzt wegen seines hohen Bekanntheitsgrades.

Sortieren durch Auswählen

Selectionsort ist ebenfalls ein sehr einfacher Algorithmus. Das Prinzip dahinter besteht darin, daß das Array von vorn nach hinten durchlaufen wird, und für jeden Platz die passende Komponente herausgesucht wird.

Man beginnt mit Table[0] und durchläft dann das Array.Dabei merkt sich die Funktion das kleinste Element. Dieses vertauscht sie dann mit der ersten Komponente, so daß nun die kleinste Komponente ganz vorne steht. Im nächsten Durchgang beginnt man bei Table[1] und durchsucht wieder das Array nach der kleinsten Komponente, wobei natürlich Table[0] unberücksichtigt bleibt. Im dritten Durchgang bleiben dann die ersten beiden Tabellenelemente unberührt usw.

                                       void SelectionSort (int Table[])
                                         {
                                         int Komponente, Smallest;
                                         int Index, Smallidx;
                                       
                                         for (Komponente = 0; Komponente < TableSize; Komponente++)
                                           {
                                           Smallidx := Komponente;
                                           Smallest := Table[Smallidx];
                                           for (Index = Komponente + 1; Index <= TableSize; Index++)
                                             {
                                       	  if (Table[Index] < Smallest)
                                       	    {
                                       	    Smallest := Table[Index];
                                       	    Smallidx := Index;
                                       	    }
                                             }
                                           if (Smallidx != Komponente)
                                             {
                                       	  Table[Smallidx] := Table[Komponente];
                                       	  Table[Komponente] := Smallest;
                                             }
                                           }
                                         }
                                       
In der Variablen Smallest merkt sich der Algorithmus den Wert die bislang kleinste Komponente, in Smallidx ihre Positeon. Beide werden zunächst auf die Komponente initialisiert, deren Positeon besetzt werden soll. Dann wird das übrige Array durchsucht, und beim Auftauchen einer kleineren Komponente entsprechend aktualisiert. Die Vertauschungsvorgang wird nur ausgeführt, wenn tatsächlich eine neue Positeon gefunden wurde. Selectionsort ist schneller als Bubblesort (ca. Faktor 2).

Sortieren durch Einfügen

Es wird angenommen, daß ein Teil am Anfang des Arrays schon sortiert ist (zu Beginn ist dieser Teil natürlich 0 Komponenten groß!). Nun wird die erste Komponente aus dem unsortierten Teil genommen und an der richtigen Stelle in den sortierten Teil eingefügt. Der sortierte Teil wächst dabei natürlich um eine Komponente, bleibt aber sortiert, wohingegen der unsortierte Teil um eine Komponente schrumpft.

Der Algorithmus durchläft die Arraykomponenten von Anfang bis Ende. Für jede Komponente geschieht nun folgendes: Von seiner Positeon aus bewegt er sich im sortierten Teil in Richtung Tabellenanfang, solange die Komponenten noch größer oder gleich der in Frage stehenden Komponente sind.

Dabei wird jede Komponente, die "überquert" wird, nach hinten verschoben. So entsteht an der jeweils aktuellen Positeon eine freie Array-Komponente. Diese "Lücke" wird dann an der richtigen Positeon mit dem einzufügenden Wert gefüllt. Auf diese Weise verbindet der Algorithmus die Suche nach der richtigen Positeon mit dem Verschieben der darüberliegenden Komponenten.

                                       void InsertionSort (int Table[])
                                         {
                                          int x;
                                          int Komponente, Index;
                                       
                                          for (Komponente = 1; Komponente <= TableSize; Komponente++)
                                            {
                                            x := Table[Komponente];
                                            Index := Komponente;
                                            while ((Index > 0) && (Table[Index - 1] >= x))
                                              {
                                       	   Table[Index] := Table[Index - 1];
                                       	   Index--;
                                              }
                                            Table[Index] := x;
                                            }
                                         }
                                       
Wie man sieht, wird die aktuelle Komponente in x gespeichert. Dann beginnt das Verschieben, bis entweder eine Komponente gefunden wird, die kleiner als x ist, oder bis man bei Index 0 angelangt ist. Im letzteren Fall hat man offenbar keine kleinere Komponente im sortierten Teil und plaziert die Komponente an Positeon 0.

Shellsort

Shellsort ist ein Kompromiß aus Einfachheit und Geschwindigkeit. Das Array wird zunächst in mehrere Gruppen aufgeteilt, zwischen deren Mitgliedern der gleiche Abstand besteht. Angenommen, man verwendet den Abstand 3, dann gehören die Komponenten 1, 4, 7, ... in eine Gruppe, genauso 2, 5, 8, ..., 3, 6, 9, ... usw. Diese Gruppen werden nun einzeln sortiert, dann wird der Abstand verringert und die Vorgehensweise wiederholt. Das macht man so lange, bis der Abstand 1 ist, so daß im letzten Schritt gar keine Unterteilung mehr stattfindet.

Zum Sortieren der Gruppen wird ein Bubblesort-ähnlicher Algorithmus verwendet. Für jeden Schritt gibt die Variable Gap den Abstand zwischen den Komponenten an. Die Variable Index läuft dann von Gap + 1 bis zum Ende der Tabelle durch. Für jeden Wert von Index wird ein Sortierlauf gestartet, mit Index als oberer Grenze. Welche Gruppe dabei sortiert wird, hängt also von Index ab. Die Variable j wird auf die nächstkleinere Komponente der Gruppe initialisiert (also Index - Gap), dann wird es mit der nächsthöheren verglichen und gegebenenfalls vertauscht. Dann geht j wieder einen Schritt nach unten (Schrittweite Gap), usw., bis j kleiner 0 ist.

Wenn Index auf die n-te Komponente einer Gruppe verweist, sind alle Komponenten (dieser Gruppe) unterhalb von Index sortiert. Ist Index bis zum Ende des Arrays durchlaufen, sind auch alle Gruppen sortiert.

                                       void ShellSort (int Table[])
                                         {
                                         int x;
                                         int Gap, Index, j;
                                         Gap := TableSize / 2;
                                         while (Gap > 0) do
                                           {
                                           for (Index = Gap + 1;  Index <= TableSize; Index++)
                                             {
                                       	  j := Index - Gap;
                                       	  while (j > 0)
                                       	    {
                                       	    if (Table[j] <= Table[j + Gap]) 
                                       	      j := 0;
                                       	    else
                                       	      {
                                       	      x := Table[j];
                                       	      Table[j] := Table[j + Gap];
                                       	      Table[j + Gap] := x;
                                       	      }
                                       	    j = J - Gap;
                                       	    }
                                             }
                                           Gap := Gap / 2;
                                           }
                                         }
                                       
Shellsort zählt zu den schnelleren Algorithmen. Leider kommt es mit sehr großen Arrays überhaupt nicht zurecht.

Quicksort

Quicksort ist in den meisten Fällen der schnellste Algorithmus. Man greift sich eine beliebige Komponente des Arrays heraus - beispielsweise die mittlere - und teilt das Array in zwei Gruppen: Eine mit den Komponenten, die größer sind als die herausgegriffene, und eine mit den kleineren (oder gleichen). Diese beiden Hälften übergibt man wieder an Quicksort. Es handelt sich also um eine rekursive Funktion. Irgendwann sind die Arrays nur noch eine Komponente groß und damit sortiert. Um nicht bei jedem Aufruf immer Arrays erzeugen zu müssen, arbeitet Quicksort mit linker und rechter Grenze. Dafür müssen dann natürlich alle Komponenten, die größer sind als die herausgegriffene, in den unteren Teil verschoben werden, die anderen in den oberen Teil. Darin besteht die eigentliche Arbeit von Quicksort:
                                       void QSort (int Links, int Rechts, int Table[])
                                         {
                                         int i, j;
                                         int x, w;
                                       
                                         i := Links;
                                         j := Rechts;
                                         x := Table[(Links + Rechts) / 2];
                                         do
                                           {
                                           while (Table[i] < x) i++;
                                           while (Table[j] > x) j--;
                                           if (i <= j)
                                             { /* Element vertauschen */
                                             w := Table[i];
                                             Table[i] := Table[j];
                                             Table[j] := w;
                                             i++; j--;
                                             }
                                           }
                                         while (i <= j);
                                         if (Links < j) QSort (Links, j, Table);
                                         if (Rechts > i) QSort (i,Rechts, Table);
                                         }
                                       

Quicksort ist, wie eingangs gesagt, in der Regel das schnellste Suchverfahren. Im schlimmsten Fall jedoch, wenn das Array bereits sortiert ist, fällt Quicksort leider auf das Niveau von Bubblesort herab.

Praktischer Einsatz von Sortierverfahren

In den vorangegangenen Abschnitten befanden sich die Algorithmen immer in einer sehr "sterilen" Umgebung, um sie von allem Beiwerk, das nicht unmittelbar zum Algorithmus gehört, zu befreien. In der Praxis hat man es mit unterschiedlichsten Bedingungen zu tun: Mal möchte man Strings sortieren, mal Zahlen, mal eine komplexe Struktur. Auch wünscht man sich manchmal, die Sortierreihenfolge (auf- oder absteigend) angeben zu können. Das Sortierverfahren muß zudem unbekannte Datentypen vergleichen können. Es muß also eine Funktion existieren, die für zwei Elementen des Arrays festlegt, welches von beiden größer ist.

Erweitern wir Quicksort zuerst auf das Sortieren von Strings. Da die Eingabestrings unterschiedlich lang sind, wird durch Speicherung von Strings fester Länge sehr viel Speicherplatz verschwendet. Für 1000 Zeichenketten mit maximal 150 Zeichen Länge müßte man definieren:

                                            char feld[1000][150]. 
                                       
Das Feld würde 1000*150 = 150'000 Bytes belegen ­ unabhängig von der wirklichen Länge der eingelesenen Zeilen. Daher sollte man für die Speicherung und Sortierung ein Feld von Zeigern auf Strings verwenden und den Platz für die aktuellen Zeile jeweils ihrer Länge entsprechend mit malloc reservieren. Das sieht dann etwa, so aus:
                                       #define MAX 1000                  /* Maximalzahl Feldelemente */
                                       
                                       ...
                                       
                                       char *feld[MAX];                  /* Feld mit String-Zeigern */
                                       char *ptr;                        /* Zeiger zum Prüfen auf EOF */
                                       char puffer[151];                 /* Puffer für akt. String */
                                       
                                           ...
                                           ptr = gets(puffer);                /* String einlesen */
                                           if (ptr != NULL)                   /* EOF,wenn (ptr rr NULL) */
                                             {                                /* Platz reservieren */
                                             feld[i] = (char *) malloc(strlen(puffer) + 1)
                                            /* Platz für den String einschl. des Zeichens '\0' am Ende */
                                             strcpy(feld[i],puffer);          /* String in feld kopieren */
                                             }
                                           ...
                                       
Auch bei Sortieren ist das Zeigerfeld günstiger, denn beim Vertauschen müssen nur Zeiger und nicht die ganzen Strings bewegt werden.

Diesmal wurde nicht nur Quicksort definiert, sondern auch das ganze Tetsprogramm:

                                       #include <stdio.h>
                                       #include <string.h>
                                       
                                       #define MAX 1000                       /* Maximalzahl Feldelemente */
                                       #define TRUE 1                         /* Wahrheitswerte */
                                       #define FALSE 0
                                       
                                       /* globale Variable */
                                       /* ---------------- */
                                       
                                       char *string_feld[MAX];                /* Feld mit String-Zeigern */
                                       int count;                             /* Anzahl der eingeg. Strings */
                                       int aufsteigend;                       /* aufsteigend/absteigend */
                                       
                                       /* Funktions-Prototypen */
                                       /* -------------------- */
                                       
                                       int  einlesen(char *feld[]);           /* Eingabefunktion */
                                       void ausgabe(int anzahl,char *feld[]); /* Ausgabefunktion */
                                       void quicksort(char *feld[],int auf, int links, int rechts);
                                       				       /* Quicksort-Routine */
                                       
                                       
                                       /* Hauptprogramm */
                                       /* ------------- */
                                       main(int argc,char *argv[])
                                         {
                                         aufsteigend = TRUE;                  /* Voreinstellung */
                                         if (argc == 2)                       /* Argument pruefen */
                                           aufsteigend = (strcmp(argv[1],"auf") == 0);
                                       
                                         count = einlesen(string_feld);
                                         quicksort(string_feld,aufsteigend,0,count-1);
                                         ausgabe(count,string_feld);
                                         }
                                       
                                       
                                       /* Funktions-Definitionen */
                                       /* ---------------------- */
                                       
                                       int einlesen(char *feld[])
                                         /* Liest Strings auf die Variable feld ein, liefert Anzahl zurueck */
                                         {
                                         int i;	                           /* Zaehler fuer Strings */
                                         char *ptr;                           /* Zeiger zum Pruefen auf EOF */
                                         char puffer[151];                    /* Puffer fuer akt. String */
                                         i = 0;
                                         do
                                           {
                                           ptr = fgets(puffer,150,stdin);     /* String einlesen */
                                           if (ptr != NULL)                   /* EOF == (ptr == NULL) */
                                             {                                /* Platz reservieren */
                                             feld[i] = (char *) malloc(strlen(puffer) + 1);
                                                                              /* einschl. '\0' am Ende */
                                             strcpy(feld[i],puffer);          /* String in feld kopieren */
                                             i++;                             /* Zaehler erhoehen */
                                             }
                                           }
                                         while (ptr != NULL);                 /* lesen bis EOF */
                                         return(i);
                                         }
                                       
                                       void ausgabe(int anzahl,char *feld[])
                                         /* Ausgabe der Strings in feld, der Parameter gbt die Anzahl an */
                                         {
                                         int i;
                                         puts("\n");                          /* Leerzeile */
                                         for (i=0; i<anzahl; i++)
                                           puts(feld[i]);                     /* haengt \n automatisch an */
                                         }
                                       
                                       
                                       void quicksort(char *feld[],int auf, int links, int rechts)
                                         /* Quicksort-Routine: feld wird im Bereich [lins,rechts] sortiert */
                                         {
                                         int i, j;  			               /* Hilfsvariable */
                                         char *x, *y;                         /* Hilfszeiger fuer Tausch */
                                         i = links; j = rechts;
                                         x = feld[(i + j)/2];                 /* mittleres Element */
                                         do
                                           {                                  /* partitionieren */
                                           if(auf)                            /* aufsteigend sortieren */
                                             {
                                             while(strcmp(feld[i],x) < 0 && i < rechts) i++;
                                             while(strcmp(feld[j],x) > 0 && j > links) j--;
                                             }
                                           else                               /* absteigend sortieren */
                                             {
                                             while(strcmp(feld[i],x) > 0 && i < rechts) i++;
                                             while(strcmp(feld[j],x) < 0 && j > links) j--;
                                             }
                                           if (i <= j)
                                             {                                /* Zeiger-Tausch! */
                                             y = feld[i];                     /* Die Strings bleiben an der */
                                             feld[i] = feld[j];               /* urspruenglichen Positeon */
                                             feld[j] = y;
                                             i++; j--;
                                             }
                                           }
                                         while (i <= j);
                                         if (links < j) quicksort(feld,auf,links,j);
                                         if (rechts > i) quicksort(feld,auf,i,rechts);
                                         }
                                       

Suchen mit bsearch

Die Bibliotheksfunktion bsearch() führt eine binäre Suche in einem Datenarray durch, wobei sie nach einem Array-Element Ausschau hält, das mit einem gesuchten Wert (dem Schlüssel oder "key") übereinstimmt. Um bsearch() anwenden zu können, muß das Array in aufsteigender Reihenfolge sortiert sein. Außerdem muß das Programm die Vergleichsfunktion bereitstellen, die bsearch() benötigt, um festzustellen, ob ein Datenelement größer, kleiner oder gleich einem anderen Element ist. Der Prototyp von bsearch() steht in stdlib.h und lautet:
                                       void *bsearch(const void *key, const void *base, size_t num, size_t size,
                                            int (*cmp)(void *elem1, void *elem2));
                                       
Dieser Prototyp ist ziemlich komplex. Deshalb sollten Sie ihn sorgfältig studieren. Das Argument key ist ein Zeiger auf das gesuchte Datenelement und base ein Zeiger auf das erste Element in dem zu durchsuchenden Array. Beide werden mit dem Typ void deklariert, so daß sie auf irgendein beliebiges C-Datenobjekt zeigen können.

Das Argument num ist die Anzahl der Arraykomponenten und size die Größe einer Komponente in Byte. Üblicherweise wird der sizeof()-Operator verwendet, um die Werte für num und size anzugeben.

cmp ist ein Zeiger auf die Vergleichsfunktion. Dabei kann es sich um eine vom Programmierer aufgesetzte Funktion handeln, oder - wenn Stringdaten durchsucht werden - um die Bibliotheksfunktion strcmp(). Die Vergleichsfunktion muß die folgenden zwei Kriterien erfüllen:

  • Sie muß Zeiger auf zwei Datenelemente übernehmen.
  • Sie muß einen der folgenden int-Werte zurückgeben:
    • < 0: Parameter 1 ist kleiner als Parameter 2.
    • 0: Parameter 1 ist gleich Parameter 2.
    • > 0: Parameter 1 ist größer als Parameter 2.
Der Rückgabewert von bsearch() ist ein Zeiger vom Typ void. Die Funktion gibt einen Zeiger auf die erste Array-Komponente zurück, die dem Schlüssel entspricht, oder NULL, wenn keine Übereinstimmung gefunden wird. Der Typ des zurückgegebenen Zeigers muß entsprechend umgewandelt werden, bevor der Zeiger verwendet werden kann.

Der sizeof()-Operator kann die num- und size-Argumente wie folgt bereitstellen. Wenn array[] das zu durchsuchende Array ist, dann liefert die Anweisung

                                       sizeof(array[0]);
                                       
den Wert für size, das heißt die Größe eines Array-Elements in Byte. Da der Ausdruck sizeof(array) die Größe eines ganzen Arrays in Byte zurückliefert, können Sie mit der folgenden Anweisung den Wert von num, der Anzahl der Elemente im Array, ermitteln:
                                       sizeof(array)/sizeof(array[0])
                                       

Sortieren mit qsort

Die Bibliotheksfunktion qsort() ist eine Implementierung des Quicksort-Algorithmus, der von C.A.R. Hoare erfunden wurde. Diese Funktion sortiert ein Array in eine vorgegebene Reihenfolge. Normalerweise wird aufsteigend sortiert, aber qsort() kann auch absteigend sortieren. Der Prototyp dieser Funktion ist in stdlib.h definiert und lautet:
                                       void qsort(void *base, size_t num, size_t size,
                                                  int (*cmp)(void *elem1, void *elem2));
                                       
Das Argument base zeigt auf das erste Element in dem Array, num ist die Anzahl der Komponenten im Array und size die Größe einer Array-Komponente in Byte. Das Argument cmp ist eine Zeiger auf eine Vergleichsfunktion. Für diese Vergleichsfunktion gelten die gleichen Regeln wie bei bsearch(). Oft verwendet man für bsearch() und qsort() die gleiche Vergleichsfunktion. Die Funktion qsort() hat keinen Rückgabewert.

Das folgende Listing veranschaulicht den Einsatz von qsort() und bsearch(). Das Programm sortiert und durchsucht ein Array von Integer-Werten. Zu Beginn des Programms können Sie bis zu MAX Werte eingeben. Die Werte werden sortiert und dann in der neuen Reihenfolge ausgegeben. Danach können Sie einen Wert eingeben, nach dem im Array gesucht werden soll. Eine abschließende Meldung informiert Sie darüber, ob der Wert im Array gefunden wurde oder nicht.

                                       #include <stdio.h>
                                       #include <stdlib.h>
                                       
                                       #define MAX 20
                                       
                                       int intvgl(const void *v1, const void *v2)
                                          { return (*(int *)v1 - *(int *)v2); }
                                       
                                       int main(void)
                                         {
                                         int arr[MAX], count, suche, *zgr;
                                       
                                         /* Werte einlesen */
                                         printf("Geben Sie %d Integer-Werte ein.\n", MAX);
                                         for (count = 0; count < MAX; count++)
                                           scanf("%d", &arr[count]);
                                       
                                         /* Sortiert das Array in aufsteigender Reihenfolge */
                                         qsort(arr, MAX, sizeof(arr[0]), intvgl);
                                       
                                         /* Gibt das sortierte Array aus. */
                                         for (count = 0; count < MAX; count++)
                                           printf("\narr[%d] = %d.", count, arr[count]);
                                       
                                         /* Suchwert eingeben */
                                         printf("Geben Sie einen Wert für die Suche ein: ");
                                         scanf("%d", &suche);
                                       
                                         /* Suche durchfuehren */
                                         zgr = (int *)bsearch(&suche, arr, MAX, sizeof(arr[0]),intvgl);
                                       
                                         if ( zgr != NULL )
                                           printf("%d bei arr[%d] gefunden.\n", suche, (zgr - arr));
                                         else
                                           printf("%d nicht gefunden.\n", suche);
                                         return(0);
                                         }
                                       

Das nächste Listing macht im Prinzip das Gleiche wie das vorstehende, nur daß diesmal Strings sortiert und gesucht werden. Die Strings werden sortieren, indem das Array der Zeiger sortiert wird. Dazu muß allerdings die Vergleichsfunktion angepasst werden. Der Vergleichsfunktion werden Zeiger auf die zwei Elemente in dem Array übergeben, die verglichen werden. Sie wollen jedoch das Array von Zeigern nicht nach den Werten der Zeiger selbst, sondern nach den Werten der Strings, auf die die Zeiger verweisen, sortieren.

Deshalb müssen Sie eine Vergleichsfunktion verwenden, der Zeiger auf Zeiger übergeben werden. Jedes Argument an vergl() ist ein Zeiger auf eine Array-Komponente und da jede Komponente selbst ein Zeiger auf einen String ist, so ist das Argument ein Zeiger auf einen Zeiger. Innerhalb der Funktion selbst dereferenzieren Sie die Zeiger, so daß der Rückgabewert von vergl() von den Werten der Strings abhängt, auf die verwiesen wird.

Die Tatsache, daß die Argumente, die vergl() übergeben werden, Zeiger auf Zeiger sind, schafft auch noch in anderer Hinsicht Probleme. Sie speichern den Suchbegriff in puffer[] und Sie wissen auch, daß der Name eines Arrays (in diesem Fall puffer) ein Zeiger auf das Array ist. Sie müssen jedoch nicht puffer selbst übergeben, sondern einen Zeiger auf puffer. Das Problem dabei ist, daß puffer eine Zeigerkonstante ist und keine Zeigervariable. puffer selbst hat keine Adresse im Speicher; es ist ein Symbol, das zur Adresse des Arrays auswertet. Deshalb können Sie keinen Zeiger erzeugen, der auf puffer zeigt, indem Sie den Adressoperator vor puffer (wie in &puffer) verwenden.

Wie verhält man sich in einem solchen Fall? Zuerst erzeugen Sie eine Zeigervariable und weisen ihr den Wert von puffer zu. In unserem Programm trägt diese Zeigervariable den Namen suche. Da suche eine Zeigervariable ist, hat sie eine Adresse, und Sie können einen Zeiger erzeugen, der diese Adresse als Wert aufnimmt. Wenn Sie schließlich bsearch() aufrufen, übergeben Sie als erstes Argument suche1 - einen Zeiger auf einen Zeiger auf den Suchstring. Die Funktion bsearch() übergibt das Argument an vergl(), und alles läuft wie geschmiert.

                                       #include <stdio.h>
                                       #include <stdlib.h>
                                       #include <string.h>
                                       
                                       #define MAX 20
                                       
                                       int vergl(const void *s1, const void *s2)
                                         { return (strcmp(*(char **)s1, *(char **)s2)); }
                                       
                                       int main(void)
                                         {
                                         char *daten[MAX], puffer[80], *zgr, *suche;
                                         int count;
                                       
                                         /* Eine Liste von Wörtern einlesen. */
                                         printf("Geben  Sie %d Wörter ein.\n",MAX);
                                         for (count = 0; count < MAX; count++)
                                           {
                                           printf("Wort %d: ", count+1);
                                           fgets(puffer,80,stdin);
                                           puffer[strlen(puffer)-1] = '\0';
                                           daten[count] = malloc(strlen(puffer)+1);
                                           strcpy(daten[count], puffer);
                                           }
                                       
                                         /* Sortiert die Woerter (genauer: die Zeiger) */
                                         qsort(daten, MAX, sizeof(daten[0]), vergl);
                                       
                                         /* Die sortierten Woerter ausgeben */
                                         for (count = 0; count < MAX; count++)
                                           printf("\n%d: %s", count+1, daten[count]);
                                       
                                         /* Suchbegriff einlesen */
                                         printf("\n\nGeben Sie einen Suchbegriff ein: ");
                                         fgets(puffer,80,stdin);
                                         puffer[strlen(puffer)-1] = '\0';
                                       
                                         /* Fuehrt die Suche durch */
                                         /* &suche ist Zeiger auf den Zeiger auf den Suchbegriff.*/
                                         suche = puffer;
                                         zgr = bsearch(&suche, daten, MAX, sizeof(daten[0]), vergl);
                                         if (zgr != NULL)
                                           printf("%s gefunden.\n", puffer);
                                         else
                                           printf("%s nicht gefunden.\n", puffer);
                                         return(0);
                                         }
                                       

Boyer-Moore-Suche

Diesen Algorithmus basiert auf der Idee, daß es eigentlich unsinnig ist, nach jedem Fehlschlag beim Durchsuchen eines Strings wieder ganz von vorne anzufangen. Wenn man z. B. auf ein Zeichen trifft, das überhaupt nicht im Suchmuster vorkommt, lohnt es sich erst hinter dem Zeichen weiterzusuchen. Kommt das Zeichen im Suchmuster vor, aber nicht an der aktuellen Stelle, kann das Muster mehrere Stellen nach rechts verschoben werden.

Die Boyer-Moore-Suche geht dabei das Suchmuster von rechts nach links durch. Wenn sie dabei auf ein Zeichen im Text trifft, das ungleich dem korrespondierenden Zeichen im Suchmuster ist, gibt es drei verschiedene Möglichkeiten:

  1. Das Zeichen im Text kommt im Suchmuster gar nicht vor. In diesem Fall kann das Suchmuster bis hinter dieses Zeichen nach rechts verschoben werden.
  2. Das Zeichen im Text steht weiter vorne im Suchmuster (betrachtet wird sein letztes Vorkommen im Muster). In diesem Fall können wir das Suchmuster so weit nach rechts verschieben, daß das Zeichen im Suchmuster unter dem identischen Zeichen im Text steht.
  3. Das Zeichen im Text steht weiter hinten im Suchmuster. In diesem Fall können wir lediglich das Muster um eine Positeon nach rechts schieben.
Anschließend wird das Suchmuster erneut von hinten nach vorne durchsucht. Das wird so lange gemacht, bis entweder das Suchmuster das Ende des Textes erreicht hat (ohne daß es gefunden wurde), oder die Überprüfung erfolgreich bis zum Anfang des Suchmusters war (es also gefunden wurde). Es bleibt nun noch die Frage, wie man effizient die letze Positeon eines Zeichens im Suchmuster findet. Dies geschieht üblicherweise über eine Tabelle, in der zu jedem Zeichen einmal die entsprechende Positeon eingetragen wird, und dann später nur noch nachgesehen wird. Das Eintragen kann in einem Durchgang erfolgen, wobei ein Vorkommen eines Zeichens das jeweils vorhergehende Vorkommen dieses Zeichens überschreibt. Die Positeon -1 steht für "Zeichen nicht vorhanden".
                                       int BMSearch(char *Pat, char *Txt)
                                         {
                                         int PosTable[256];
                                         int PatLen, TxtLen, Index, PatIndex, Positeon;
                                         if (strlen(Pat) == 0) return (0);
                                         PatLen = strlen(Pat);
                                         TxtLen = strlen(Txt);
                                         for (PatIndex = 0; PatIndex < 256; PatIndex++) 
                                           PosTable[PatIndex] := -1;
                                         for (PatIndex = 0; PatIndex <= PatLen; PatIndex++)
                                             PosTable[(int) Pat[PatIndex]] := PatIndex;
                                         Index := 0;
                                         while (PatIndex >= 0) && (Index <= (TxtLen - PatLen)))
                                           {
                                           PatIndex := PatLen;
                                           while ((Pat[PatIndex] == Txt[Index + PatIndex]) && (PatIndex > 0))
                                       	  PatIndex--;
                                           if (PatIndex >= 0)
                                             {
                                       	  Positeon := PosTable[(char) Txt[Index + PatIndex]];
                                       	  if (Positeon == -1) Index = Index + PatIndex;
                                             else 
                                               if (Positeon > PatIndex) Index++;
                                               else Index = Index + PatIndex - Positeon;
                                             }
                                           }
                                          if (PatIndex < 0) return (Index + 1); 
                                          else return(0);
                                         }
                                       
Es gibt auch noch weiter verbesserte Versionen dieses Algorithmus; dieser sollte jedoch für die meisten Fälle ausreichen.

Sortieren von linearen Listen

Die oben behandelten Algorithmen lassen sich nicht nur auf Tabellen (Arrays) anwenden, sondern auch auf andere Datenstrukturen adaptieren. Beispielhaft soll hier die Portierung zweier Verfahren auf lineare Listen gezeigt werden. Wenn Elemente in eine lineare Liste eingefügt werden sollen, dann tut man dies am besten gleich an der "richtigen" Stelle. Dies zeigt die Funktion InsertionSort im folgenden Listing.

Für das nachträgliche Sortieren einer linearen Liste wurde die Funktion BubbleSort gewählt, da hier der Algorithmuns sehr übersichtlich ist. Die anderen Sortierverfahren lassen sich nach dem gleichen Schema implementieren.

                                       
                                       #include <stdio.h>
                                       #include <stdlib.h>
                                       
                                       struct LineareListe 
                                         { 
                                         double Element; 
                                         struct LineareListe *next;
                                         };
                                       
                                       typedef struct LineareListe LinList;
                                       
                                       /*Insertion Sort mit verketteter Liste
                                        * Werte werden bei jedem Aufruf in der Liste eingereiht
                                        * Uebergeben werden Liste und einzureihendes Element
                                        */
                                       
                                       LinList *InsertionSort ( LinList *Liste, double Wert ) 
                                         {
                                         LinList *temp = Liste;
                                         LinList *neu = malloc(sizeof(LinList));
                                         neu->Element = Wert;
                                         neu->next = NULL;
                                       
                                         if(Liste == NULL) return neu;
                                         
                                         /* Liste durchwandern, notfalls einreihen */
                                         while (temp->next != NULL)
                                           {
                                           if (temp->next->Element > Wert)
                                             {
                                             neu->next  = temp->next;
                                             temp->next  = neu;
                                             return Liste;
                                             }
                                           temp = temp->next;
                                           } 
                                         /* Am Ende angelangt, Element einreihen */
                                         temp->next  = neu;
                                         /* Wenn letztes Element > neues Element, 
                                              dann vertauschen */
                                         if (temp->Element > Wert)
                                           {
                                           neu->Element  = temp->Element;
                                           temp->Element  = Wert;
                                           }
                                         /* Listenanfang zurückgeben */
                                         return Liste;
                                         }
                                       
                                       
                                       /*Bubble Sort mit Liearen Listen
                                        * Es wird bei einer Liste erst das erste und dann alle nachfolgenden
                                        * Elemente mit der Restliste verglichen und mit kleineren Elementen vertauscht
                                        */
                                       
                                       LinList *BubbleSort (LinList *Liste)
                                         {
                                         LinList *Rest, *Akt = Liste;
                                         double swap;
                                         /* Liste ist leer oder hat nur ein Element */
                                         if ((Liste == NULL) || (Liste->next == NULL)) return Liste;
                                         /* Sortierverfahren Bubblesort */
                                         do
                                           {
                                           Rest = Akt;
                                           do 
                                             {
                                             Rest = Rest->next;
                                             /* Wenn der Restwert kleiner als Vergleichswert, dann vertauschen */
                                             if (Rest->Element < Akt->Element)
                                               {
                                               swap = Rest->Element;
                                               Rest->Element = Akt->Element;
                                               Akt->Element = swap;
                                               }
                                             } while (Rest->next != NULL);
                                           Akt = Akt->next;
                                           } while (Akt->next != NULL);
                                         return Liste;
                                         }
                                       

Soundex-Verfahren

Der Soundex-Code für einen Begriff wird wie folgt berechnet:
  1. Entferne alle Vokale und die Konsonanten H, W, Y. Von aufeinanderfolgenden gleichen Zeichen bleibt nur eins erhalten. Das erste Zeichen bleibt erhalten.
  2. Entwickle den Soundex-Code für den ersten und die darauffolgenden maximal 3 Zeichen nach der Soundex-Tabelle.
    Buchstaben Ziffern Erzeugung der Laute
    b, f, p, v 1 Lippen, öffnend
    c, g, j, k, q, s, x, z 2 Rachen, Zunge
    d, t 3 Zunge, Zähne
    l 4 Zunge, Gaumen
    m, n 5 Lippen, geschlossen
    r 6 Zunge, rollend

    Der Soundex-Algorithmus basiert auf der Annahme, daß Worte, die ähnlich klingen, auch von der Semantik her ähnlich sind. Soundex reduziert jedes Wort auf einen eindeutigen maximal vier Zeichen langen Code.
    In der letzten Spalte wird die Erzeugung der Laute klassifiziert. Wir sehen, daß die Zusammenfassung sich an der Erzeugung orientiert. Somit ergibt sich immer eine Kombination aus einem Buchstaben und einer dreistelligen Zahl, die maximal 666 erreichen kann.
    Die Verbesserungen bzw. - vorsichtiger ausgedrückt - die Variationen können sich z. B. auf die Behandlung des Anfangsbuchstabens beziehen, indem wir ihn wie die anderen Buchstaben behandeln. Dieser Algorithmus wird als Extended Soundex Algorithmus bezeichnet. Hier ergibt sich eine vierstellige Zahl, die 6666 nicht überschreitet, so daß sie in max. 2 Byte abgespeichert werden kann, was bei sehr großen Dateien natürlich erheblichen Speicherplatz einspart.
    Wir können nun versuchen, Verbesserungen vorzunehmen. Diese müssen sich aber immer am Sprachverständnis der erfassenden Person orientieren.

    Beispiele:

    StringZwischenschrittSoundex-Code
    Stadtstdt2333
    stattst23
    Staatst23

    Soundex ist leicht in relationalen Datenbanken implementierbar. Der Soundex-Code sollte für jeden Begriff in der Datenbank in einer Relation abgespeichert werden. Die Suche nach Begriffen, die ähnlich zu einem Suchwort sind, kann man über den invertierten Index der Soundex-Codes realisieren. Soundex liefert aufgrund seiner Einfachheit vergleichsweise schlechte Ergebnisse. Die folgende Implementierung hat zwei Parameter, instr ist ein beliebiger Eingabstring, outstr liefert den erzeugten Soundex-String. Dies ist auch gleichzeitig der Return-Wert der Funktion. Da der Standard-Soundex nur für ASCCI (ohne Umlaute) geeignet ist, sind die Umlaute auf die entsprechenden Vokale umcodiert wirden.

                                           char *Soundex(char *instr, char *outstr)
                                             {           /* ABCDEFGHIJKLMNOPQRSTUVWXYZ */
                                             char *table = "01230120022455012623010202";
                                             char *outptr = outstr;
                                             int count = 0;
                                           
                                             while(!isalpha(instr[0]) && instr[0] != '\0') ++instr;
                                             if(instr[0] == '\0') return(NULL); /* Stringende */
                                           
                                             if(toupper(instr[0]) == 'P' && toupper(instr[1]) == 'H')
                                               {
                                               instr[0] = 'F';
                                               instr[1] = 'A';
                                               }
                                           
                                             *outptr++ = (char)toupper(*instr++);
                                           
                                             while((*instr != '\0') && (count < 5))
                                               {
                                               if(isalpha(*instr) && (*instr != *(instr-1)))
                                                 {
                                                 switch (instr[0])
                                                   {
                                                   case 'ä': instr[0] = 'a'; break;
                                                   case 'ö': instr[0] = 'o'; break;
                                                   case 'ü': instr[0] = 'u'; break;
                                                   case 'Ä': instr[0] = 'A'; break;
                                                   case 'Ö': instr[0] = 'O'; break;
                                                   case 'Ü': instr[0] = 'U'; break;
                                                   case 'ß': instr[0] = 's'; break;
                                                   default: break;
                                                   }
                                                 *outptr = table[toupper(instr[0]) - 'A'];
                                                 if(*outptr != '0')
                                                   {
                                                    ++outptr;
                                                    ++count;
                                                   }
                                                 }
                                               ++instr;
                                               }
                                           
                                             *outptr = '\0';
                                             return(outstr);
                                             }
                                           

    Die folgende, etwas komplexere Variante von Soundex eignet sich besser für die Indizierung von Namen. Das Original stammt von Joe Celko ("The C Gazette" Vol. 4 Nr. 2). Dieser Algorithmus hat folgende Eigenschaften:

    • der erste Buchstabe bleibt erhalten
    • Umlaute werden konvertiert
    • Kleinbuchstaben werden in Großbuchstaben konvertiert
    • Konvertiert die ersten N Buchstaben zu Soundex-Codes (N ist Parameter)
    Es wäre möglich gewesen, etliche Konvertierunge in einer Schleife zusammenzufassen. Joe Celko hat etwas "großzügiger" programmiert, um Änderungen leichter zu machen.

                                           #define WBUFSIZE 512
                                           
                                           void soundex4(const char *instr, char *outstr, int N)
                                             {
                                             char *p, *p1;
                                             int i;
                                             char workbuf[WBUFSIZE + 1];
                                             char priorletter;
                                           
                                             /* Make a working copy */
                                             strncpy(workbuf, instr, WBUFSIZE);
                                             workbuf[WBUFSIZE] = '\0';
                                           
                                             /* Konvertieren zu Grossbuchstaben und Umlaute */
                                             for (p = workbuf; *p; ++p)
                                               {
                                               *p = toupper(*p);
                                               switch (*p)
                                                 {
                                                 case 'ä': *p = 'A'; break;
                                                 case 'ö': *p = 'O'; break;
                                                 case 'ü': *p = 'U'; break;
                                                 case 'Ä': *p = 'A'; break;
                                                 case 'Ö': *p = 'O'; break;
                                                 case 'Ü': *p = 'U'; break;
                                                 case 'ß': *p = 'S'; break;
                                                 default: break;
                                                 }
                                               }
                                             /* Konvertieren alle Vokale zu 'A' */
                                             for (p = workbuf; *p; ++p)
                                               if (strchr("AEIOUY", *p)) *p = 'A';
                                           
                                             /* Praefix-Transformation: Nur am Anfang des Namens */
                                             if (strncmp(workbuf, "MAC", 3) == NULL)          /* MAC to MCC */
                                               workbuf[1] = 'C';
                                             else if (strncmp(workbuf, "KN", 2) == NULL)  /* KN to NN */
                                               workbuf[0] = 'N';
                                             else if (workbuf[0] == 'K')                      /* K to C */
                                               workbuf[0] = 'C';
                                             else if (strncmp(workbuf, "PF", 2) == NULL)  /* PF to FF */
                                               workbuf[0] = 'F';
                                             else if (strncmp(workbuf, "SCH", 3) == NULL) /* SCH to SSS */
                                              workbuf[1] = workbuf[2] = 'S';
                                           
                                             /*Infix-Transformationen: ab dem 2. Buchstaben,
                                              * von links nach rechts                                   */
                                             while ((p = strstr(workbuf, "DG")) > workbuf)   /* DG to GG */
                                               p[0] = 'G';
                                             while ((p = strstr(workbuf, "CAAN")) > workbuf) /* CAAN to TAAN */
                                               p[0] = 'T';
                                             while ((p = strchr(workbuf, 'D')) > workbuf)    /* D to T */
                                               p[0] = 'T';
                                             while ((p = strstr(workbuf, "NST")) > workbuf)  /* NST to NSS */
                                               p[2] = 'S';
                                             while ((p = strstr(workbuf, "AV")) > workbuf)   /* AV to AF */
                                               p[1] = 'F';
                                             while ((p = strchr(workbuf, 'Q')) > workbuf)    /* Q to G */
                                               p[0] = 'G';
                                             while ((p = strchr(workbuf, 'Z')) > workbuf)    /* Z to S */
                                               p[0] = 'S';
                                             while ((p = strchr(workbuf, 'M')) > workbuf)    /* M to N */
                                               p[0] = 'N';
                                             while ((p = strstr(workbuf, "KN")) > workbuf)   /* KN to NN */
                                               p[0] = 'N';
                                             while ((p = strchr(workbuf, 'K')) > workbuf)    /* K to C */
                                               p[0] = 'C';
                                             while ((p = strstr(workbuf, "AH")) > workbuf)   /* AH to AA */
                                               p[1] = 'A';
                                             while ((p = strstr(workbuf, "HA")) > workbuf)   /* HA to AA */
                                               p[0] = 'A';
                                             while ((p = strstr(workbuf, "AW")) > workbuf)   /* AW to AA */
                                               p[1] = 'A';
                                             while ((p = strstr(workbuf, "PH")) > workbuf)   /* PH to FF */
                                               p[0] = p[1] = 'F';
                                             while ((p = strstr(workbuf, "SCH")) > workbuf)  /* SCH to SSS */
                                               p[0] = p[1] = 'S';
                                           
                                             /*Suffix-Transformationen: am Wortende */
                                             /* (1) 'A's und 'S's am Ende weg */
                                             for (i = strlen(workbuf) - 1;
                                               (i > 0) && ((workbuf[i] == 'A') || (workbuf[i] == 'S'));
                                               --i)
                                                 workbuf[i] = '\0';
                                             /* (2) NT -&lt; TT */
                                             for (i = strlen(workbuf) - 1;
                                               (i > 1) && ('N' == workbuf[i - 1] || 'T' == workbuf[i]);
                                               --i)
                                                 workbuf[i - 1] = 'T';
                                             /* Nun alle Vokale weg (bis auf den ersten) */
                                             p = p1 = workbuf;
                                             while ((*p1++ = *p++) != '\0')
                                               while (*p == 'A') ++p;
                                             /* Dubletten weg */
                                             p = p1 = workbuf;
                                             priorletter = '\0';
                                             do 
                                               {
                                               while (*p == priorletter) ++p;
                                               priorletter = *p;
                                               } while ((*p1++ = *p++) != '\0');
                                           
                                             strncpy(outstr, workbuf, N);
                                             outstr[N] = '\0';
                                             }
                                           

DIPLOMARBEITEN UND BÜCHER

Diplomarbeiten zum Runterladen:

Suche im Katalog:
Architektur / Raumplanung
Betriebswirtschaft - Funktional
Erziehungswissenschaften
Geowissenschaften
Geschichtswissenschaften
Informatik
Kulturwissenschaften
Medien- und Kommunikationswissenschaften
Medizin
Psychologie
Physik
Rechtswissenschaft
Soziale Arbeit
Sozialwissenschaften


JOBS
HOME | E-LEARNING | SITEMAP | LOGIN AUTOREN | SUPPORT | FAQ | KONTAKT | IMPRESSUM
Virtual University in: Italiano - Français - English - Español
VirtualUniversity, WEB-SET Interactive GmbH, www.web-set.com, 6301 Zug

Partner:   Seminare7.de - PCopen.de - HTMLopen.de - WEB-SET.com - YesMMS.com - Ausbildung24.ch - Manager24.ch - Job und Karriere