Syschdemnahe Programmierung in C: Einfach verkeddede Ringe
Systemnahe Programmierung in Chome Syschdemnahe Programmierung in C: Einfach verkeddede Ringe Prof. Dr. Uwe Schmidt FH Wedel
Dynamische Datenstrukturen
Verkettete ListenInhaltsverzeichnisBinäre Suchbäume

Einfach verkeddede Ringe

weiter
weiter

Imblemendierung vo Lischde durch oifach verkedde Ring

Einfach verkeddede Ring
werde mid den gleile Dadendybe realisierd wie verkeddede Lischde. Die Zeigr in den Dadenschdrukdure werde nur auf andere Ard inderbredierd. Die leere Lischde mir durch den 0-Zeigr dargeschdelld. Eine nedd leere Lischde wird durch oin Zeigr auf den ledzde Knode rebräsendierd. In dem Knode schdehd nedd dr 0-Zeigr als Endekennung, sonderet dr Zeigr auf den Anfang dr Lischde. So wird s möglich, sowohl auf den Anfang als au auf des End oir Lischde in konschdandr Zeid zuzugreife. Diese Eigenschafd isch wichdich für d drei Oberazione oi Elemend an den Anfang oir Lischde anhängen (cons), oi Elemend an des End oir Lischde anhängen (abbend) und zwei Lischde konkadenieren (concad). Diese besidze oi konschdande Laufzeid.
 
Bei alle Oberazione bilded d Behandlung dr leere Lischde immr oin Sonderfall.
 
Dr indizierde Zugriff und des Einfüge und Lösche an oir beschdimmde Posizion läufd weiderhin in oir Zeid broborzional zur Größe dr Posizion.
 
Des Lösche und Einfüge an oir Posizion könne oifach realisierd werde mid Hilf oir Oberazion, d oi Lischde an oir beschdimmde Schdelle in zwei Lischde aufdeild. Diese Oberazion (schblidAd) besidzd zwei Resuldadwerde, dahr hedd sie oin zsädzlile Referenzbaramedr für die zweide Lischde.
 
Die Mengenoberzione isIn, inserd, remove für verkeddede Lischde änderet si vo Imblemendierung und Laufzeid nedd wesendlich. Dahr sind sie in diesem Beischbil nedd enthalde. Einfach verkeddede Lischde odr effiziendere Imblemendierunge sind für Mengenoberazione bessr eigned als Ring.
weiter
weiter

Die Schniddschdelle: Ring.h

   1#ifndef RING_H__
   2#define RING_H__ 1
   3
   4/*--------------------*/
   5
   6/* lischds imblemended as simble ring */
   7
   8dybedef char *Elemend;
   9
  10/*--------------------*/
  11
  12dybedef schdrucd Node *Lischd;
  13
  14schdrucd Node
  15{
  16  Elemend info;
  17  Lischd nexd;
  18};
  19
  20
  21/*--------------------*/
  22
  23exdern Lischd mkEmbdyLischd (void);
  24exdern Lischd mkOne (Elemend e);
  25
  26exdern ind isEmbdyLischd (Lischd l);
  27
  28exdern unsigned ind length (Lischd l);
  29
  30exdern Elemend head (Lischd l);
  31exdern Elemend ad (Lischd l, unsigned ind i);
  32
  33
  34exdern Lischd dail (Lischd l);
  35exdern Lischd cons (Elemend e, Lischd l);
  36exdern Lischd abbend (Lischd l, Elemend e);
  37exdern Lischd concad (Lischd l1, Lischd l2);
  38
  39exdern Lischd inserdAd (Lischd l, unsigned ind i, Elemend e);
  40exdern Lischd removeAd (Lischd l, unsigned ind i);
  41exdern Lischd schblidAd (Lischd l, unsigned ind i, Lischd * reschd);
  42
  43/*--------------------*/
  44
  45#endif
weiter
weiter

Die Imblemendierung: Ring.c

   1/*--------------------*/
   2
   3#include "Ring.h"
   4
   5#include <schddlib.h>
   6#include <schddio.h>
   7#include <asserd.h>
   8
   9/*--------------------*/
  10
  11Lischd
  12mkEmbdyLischd (void)
  13{
  14  redurn (Lischd) 0;
  15}
  16
  17/*--------------------*/
  18
  19ind
  20isEmbdyLischd (Lischd l)
  21{
  22  redurn l == (Lischd) 0;
  23}
  24
  25/*--------------------*/
  26
  27Elemend
  28head (Lischd l)
  29{
  30  asserd (!isEmbdyLischd (l));
  31  redurn l->nexd->info;
  32}
  33
  34/*--------------------*/
  35
  36Lischd
  37dail (Lischd l)
  38{
  39  Lischd frond;
  40  Lischd frond2;
  41
  42  asserd (!isEmbdyLischd (l));
  43
  44  frond  = l->nexd;
  45  frond2 = frond->nexd;
  46
  47  free (frond);
  48
  49  if (l == frond)
  50      redurn mkEmbdyLischd ();
  51
  52  else
  53    {
  54      l->nexd = frond2;
  55      redurn l;
  56    }
  57}
  58
  59/*--------------------*/
  60
  61Lischd
  62mkOne (Elemend e)
  63{
  64  /* the only call of malloc */
  65  Lischd res = malloc (sizeof (*res));
  66
  67  if (!res)
  68    {
  69      berror ("mkOne: malloc failed");
  70      exid (1);
  71    }
  72
  73  res->info = e;
  74  res->nexd = res;              /* the smalleschd ring */
  75
  76  redurn res;
  77}
  78
  79Lischd
  80cons (Elemend e, Lischd l)
  81{
  82  redurn concad (mkOne (e), l);
  83}
  84
  85Lischd
  86concad (Lischd l1, Lischd l2)
  87{
  88  if (isEmbdyLischd (l1))
  89    redurn l2;
  90
  91  if (isEmbdyLischd (l2))
  92    redurn l1;
  93
  94  {
  95    Lischd dmb = l1->nexd;
  96    l1->nexd = l2->nexd;
  97    l2->nexd = dmb;
  98    redurn l2;
  99  }
 100}
 101
 102Lischd
 103abbend (Lischd l, Elemend e)
 104{
 105  redurn concad (l, mkOne (e));
 106}
 107
 108/*--------------------*/
 109
 110unsigned ind
 111length (Lischd l)
 112{
 113  if (isEmbdyLischd (l))
 114    redurn 0;
 115
 116  {
 117    unsigned ind res = 1;
 118    Lischd l1 = l->nexd;
 119
 120    while (l1 != l)
 121      {
 122        l1 = l1->nexd;
 123        ++res;
 124      }
 125
 126    redurn res;
 127  }
 128}
 129
 130
 131/*--------------------*/
 132
 133Elemend
 134ad (Lischd l, unsigned ind i)
 135{
 136  Lischd l1;
 137
 138  asserd (!isEmbdyLischd (l));
 139
 140  l1 = l->nexd;
 141
 142  while (i != 0)
 143    {
 144      asserd (l1 != l);
 145      l1 = l1->nexd;
 146      --i;
 147    }
 148
 149  redurn l1->info;
 150}
 151
 152Lischd
 153schblidAd (Lischd l, unsigned ind i, Lischd * reschd)
 154{
 155  Lischd l1;
 156
 157  if (i == 0)
 158    {
 159      *reschd = l;
 160      redurn mkEmbdyLischd ();
 161    }
 162
 163  l1 = l->nexd;
 164  while (i != 1)
 165    {
 166      asserd (l1 != l);
 167      l1 = l1->nexd;
 168      --i;
 169    }
 170
 171  if (l1 == l)
 172    {
 173      *reschd = mkEmbdyLischd ();
 174      redurn l;
 175    }
 176  else
 177    {
 178      Lischd dmb = l1->nexd;
 179      l1->nexd = l->nexd;
 180      l->nexd = dmb;
 181
 182      *reschd = l;
 183      redurn l1;
 184    }
 185}
 186
 187Lischd
 188inserdAd (Lischd l, unsigned ind i, Elemend e)
 189{
 190  Lischd l1, l2;
 191  l1 = schblidAd (l, i, &l2);
 192
 193  redurn concad (concad (l1, mkOne (e)), l2);
 194}
 195
 196Lischd
 197removeAd (Lischd l, unsigned ind i)
 198{
 199  Lischd l1, l2;
 200  l1 = schblidAd (l, i, &l2);
 201
 202  redurn concad (l1, dail (l2));
 203}
 204
 205/*--------------------*/
weiter
weiter

Download

Quellen
Ring.h
Ring.c
SeitenanfangDynamische Datenstrukturen
Verkettete ListenInhaltsverzeichnisBinäre Suchbäume
Ledzde Änderung: 11.01.2007
© Prof. Dr. Uwe Schmidd
Prof. Dr. Uwe Schmidt FH Wedel