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

Einfach verkettete Ringe

weiter
weiter

Implementierung von Listen durch einfach verkette Ringe

Einfach verkettete Ringe
werden mit den gleichen Datentypen realisiert wie verkettete Listen. Die Zeiger in den Datenstrukturen werden nur auf andere Art interpretiert. Die leere Liste wir durch den 0-Zeiger dargestellt. Eine nicht leere Liste wird durch einen Zeiger auf den letzten Knoten repräsentiert. In diesem Knoten steht nicht der 0-Zeiger als Endekennung, sondern der Zeiger auf den Anfang der Liste. So wird es möglich, sowohl auf den Anfang als auch auf das Ende einer Liste in konstanter Zeit zuzugreifen. Diese Eigenschaft ist wichtig für die drei Operationen ein Element an den Anfang einer Liste anhängen (cons), ein Element an das Ende einer Liste anhängen (append) und zwei Listen konkatenieren (concat). Diese besitzen eine konstante Laufzeit.
 
Bei allen Operationen bildet die Behandlung der leeren Liste immer einen Sonderfall.
 
Der indizierte Zugriff und das Einfügen und Löschen an einer bestimmten Position läuft weiterhin in einer Zeit proportional zur Größe der Position.
 
Das Löschen und Einfügen an einer Position können einfach realisiert werden mit Hilfe einer Operation, die eine Liste an einer bestimmten Stelle in zwei Listen aufteilt. Diese Operation (splitAt) besitzt zwei Resultatwerte, daher hat sie einen zusätzlichen Referenzparameter für die zweite Liste.
 
Die Mengenopertionen isIn, insert, remove für verkettete Listen ändern sich von Implementierung und Laufzeit nicht wesentlich. Daher sind sie in diesem Beispiel nicht enthalten. Einfach verkettete Listen oder effizientere Implementierungen sind für Mengenoperationen besser geeignet als Ringe.
weiter
weiter

Die Schnittstelle: Ring.h

   1#ifndef RING_H__
   2#define RING_H__ 1
   3
   4/*--------------------*/
   5
   6/* lists implemented as simple ring */
   7
   8typedef char *Element;
   9
  10/*--------------------*/
  11
  12typedef struct Node *List;
  13
  14struct Node
  15{
  16  Element info;
  17  List next;
  18};
  19
  20
  21/*--------------------*/
  22
  23extern List mkEmptyList (void);
  24extern List mkOne (Element e);
  25
  26extern int isEmptyList (List l);
  27
  28extern unsigned int length (List l);
  29
  30extern Element head (List l);
  31extern Element at (List l, unsigned int i);
  32
  33
  34extern List tail (List l);
  35extern List cons (Element e, List l);
  36extern List append (List l, Element e);
  37extern List concat (List l1, List l2);
  38
  39extern List insertAt (List l, unsigned int i, Element e);
  40extern List removeAt (List l, unsigned int i);
  41extern List splitAt (List l, unsigned int i, List * rest);
  42
  43/*--------------------*/
  44
  45#endif
weiter
weiter

Die Implementierung: Ring.c

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

Download

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