home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / C / OTL-MC7.DMS / in.adf / cppdemo.lha / C++ / lists.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-10-30  |  4.1 KB  |  200 lines
  1. #pragma +
  2. /*
  3.    Doppelt verkettete Listen
  4.  
  5.    Ein kleines Beispiel für dynamische Datenstrukturen in C++,
  6.    aber ohne objektorientierte Programmierung
  7.  
  8.    Verbrochen von Jens Gelhar am 13.01.92
  9. */
  10.  
  11.  
  12. #include <stream.h>
  13. #include <string.h>
  14.  
  15.  
  16. // * * * Datentypen * * *
  17.  
  18. struct Eintrag          // ein einzelner "Telefonbuch"-Eintrag
  19. {
  20.   Eintrag *next, *prev;         // Vorgänger und Nachfolger
  21.  
  22.   char name[30];                // Name und...
  23.   char nummer[20];              // Telefonnummer
  24. };
  25.  
  26.  
  27. struct Liste            // sortierte Liste von Einträgen
  28. {
  29.   Eintrag *anfang, *ende;       // erstes bzw. letztes Listenelement
  30. };
  31.  
  32.  
  33. // * * * Funktionen * * *
  34.  
  35. void Init(Liste &L)
  36.  // Initialisiert eine Listenstruktur, indem sie ihre beiden
  37.  // Pointer auf 0 setzt:
  38.  { L.anfang = 0;
  39.    L.ende   = 0;
  40.  }
  41.  
  42.  
  43. void Ausgabe (const Liste &L)
  44.  // Telefonbuch ausgeben
  45.  {
  46.    for(Eintrag *E = L.anfang; E; E = E->next)
  47.        cout << E->name << ": " << E->nummer << "\n";
  48.  }
  49.  
  50.  
  51. Eintrag *Einfueg(Liste &L, const char Name[], const char Nummer[])
  52.  // fügt einen neuen Eintrag in die Liste ein
  53.  {
  54.   // neues Element erzeugen:
  55.   Eintrag *neu = new Eintrag;
  56.  
  57.   if (!neu) return 0;           // kein Speicher frei!
  58.  
  59.   // neues Element initialisieren:
  60.   strcpy(neu->name, Name);
  61.   strcpy(neu->nummer, Nummer);
  62.  
  63.   // Richtige Position zun Einfügen suchen:
  64.   Eintrag *pos = L.anfang;
  65.  
  66.   while (pos!=0 && strcmp(pos->name, Name) < 0)
  67.     pos = pos->next;
  68.  
  69.   // Element in Liste einhängen, dabei diverse Sonderfälle beachten:
  70.  
  71.   if (pos == 0)
  72.   // Sonderfall: Anfügen an das Ende der Liste
  73.   {
  74.     Eintrag *alt = L.ende;    // altes Listenende
  75.  
  76.     if (alt != 0)
  77.     // allgemeiner Unter-Fall: wirklich anhängen
  78.     {
  79.       alt->next = neu;
  80.       neu->prev = alt;
  81.       neu->next = 0;
  82.       L.ende = neu;
  83.     }
  84.     else
  85.     // spezieller Spezialfall: Liste ist noch leer
  86.     { neu->next = 0;
  87.       neu->prev = 0;
  88.       L.anfang = neu;
  89.       L.ende = neu;
  90.     }
  91.   }
  92.   else
  93.   if (pos->prev == 0)
  94.   // Sonderfall: Neues Element an Listenanfang hängen
  95.   {
  96.     pos->prev = neu;
  97.     neu->next = pos;
  98.     neu->prev = 0;
  99.     L.anfang = neu;
  100.   }
  101.   else
  102.   // allgemeiner Fall: Element in Liste einhängen
  103.   {
  104.     Eintrag *vor = pos->prev;
  105.     // "neu" zwischen "vor" und "pos" einhängen:
  106.     vor->next = neu;
  107.     neu->prev = vor;
  108.     neu->next = pos;
  109.     pos->prev = neu;
  110.   }
  111.  
  112.   // Fertig, Zeiger auf neues Element zurückgeben:
  113.   return neu;
  114.  
  115.  }
  116.  
  117. void AllesLoeschen(Liste &L)
  118.  // löscht sämtliche Listenelemente
  119.  {
  120.   Eintrag *p = L.anfang;
  121.  
  122.   while(p)
  123.     { Eintrag *hilf = p;
  124.       p=p->next;
  125.       delete hilf;
  126.     }
  127.   Init(L);
  128.  }
  129.  
  130. void Loeschen(Liste &L, Eintrag *E)
  131.  // Löscht das Element, auf das "E" zeigt, aus Liste "L"
  132.  {
  133.   // Vorgänger unf Nachfolger des zu löschenden Elements
  134.   Eintrag *vor = E->prev, *nach = E->next;
  135.  
  136.   if (vor)
  137.   // Element hat Vorgänger: Dann dessen Nachfolger umsetzen
  138.     vor->next = nach;
  139.   else
  140.   // kein Vorgänger: Dann Listenanfang aktualisieren
  141.     L.anfang = nach;
  142.  
  143.   if (nach)
  144.   // Element hat Nachfolger: Dann dessen Vorgänger verändern
  145.     nach->prev = vor;
  146.   else
  147.   // kein Nachfolger, also Listenende anpassen
  148.     L.ende = vor;
  149.  
  150.   delete(E);
  151.  }
  152.  
  153.  
  154. Eintrag *Suche(const Liste &L, char *Name)
  155.  // Sucht einen Eintrag mit diesem Namen und gibt Zeiger auf das
  156.  // zugehörige Listenelement zurück, oder 0 bei Fehler
  157.  {
  158.   for( Eintrag *p = L.anfang;
  159.        p && strcmp(p->name, Name);
  160.        p = p->next );
  161.   return p;
  162.  }
  163.  
  164.  
  165. // * * *  Hauptprogram  * * *
  166.  
  167. void main()
  168. {
  169.   // Eine Liste wird deklariert und initialisiert:
  170.  
  171.   Liste l;
  172.   Init(l);
  173.  
  174.   // Ein paar Beispieldaten werden eingefügt:
  175.  
  176.   Einfueg(l, "Harley-Davidson", "001-414/342-4680");
  177.   Einfueg(l, "Boris Becker", "0815/4711");
  178.   Einfueg(l, "James Bond", "007/26731");
  179.   Einfueg(l, "Maxon", "06196/481813");
  180.   Einfueg(l, "Zaphod Beeblebrox", "00042/08154242");
  181.   Einfueg(l, "Luxemburg", "00352");
  182.   Einfueg(l, "Queensr\0377che", "795069");
  183.   Einfueg(l, "Fishbone", "4676152");
  184.  
  185.   // Einen Datensatz suchen und ggf. löschen:
  186.  
  187.   Eintrag *e = Suche(l,"Maxon");
  188.   if (e)
  189.     Loeschen(l, e);
  190.   else
  191.     cout << "Name nicht gefunden!\n";
  192.  
  193.   // restliche Liste ausgeben:
  194.   Ausgabe(l);
  195.  
  196.   // ...und wieder aufräumen:
  197.   AllesLoeschen(l);
  198.  
  199. }
  200.