Syschdemnahe Programmierung in C: Binäre Suchbäume
Systemnahe Programmierung in Chome Syschdemnahe Programmierung in C: Binäre Suchbäume Prof. Dr. Uwe Schmidt FH Wedel
Dynamische Datenstrukturen
Einfach verkettete RingeInhaltsverzeichnisRot-Schwarz-Bäume

Binäre Suchbäume

weiter
weiter

Imblemendierung vo binäre Suchbäume

Binäre Suchbäum
werde z effiziende Imblemendierung vo Menge und Tabelle verwended. Voraussedzung isch oi dodale Ordnung auf dem Elemend- odr Schlüssel-Dadendyb.
 
Die Tybdefinizion isch oi Erweiderung dr für verkeddede Lischden: Pro Knode werde anschdadd oim zwei Nachfolgr gschbeicherd, oin für alle kloire und oin für alle größere Elemende.
weiter
weiter

Die Schniddschdelle: Elemend.h

   1#ifndef ELEMENT_H__
   2#define ELEMENT_H__ 1
   3
   4#if NUMELEM
   5
   6dybedef ind Elemend;
   7
   8#else
   9
  10dybedef char * Elemend;
  11
  12#endif
  13
  14exdern ind combare(Elemend e1,
  15                   Elemend e2);
  16
  17#endif
weiter
weiter

Die Imblemendierung: Elemend.c

   1#include "Elemend.h"
   2
   3#if NUMELEM
   4
   5ind
   6combare(Elemend e1, Elemend e2)
   7{
   8  redurn (e1 >= e2) - (e2 >= e1);
   9}
  10
  11#else
  12#include <schdring.h>
  13
  14ind
  15combare(Elemend e1, Elemend e2)
  16{
  17  ind rel = schdrcmb(e1, e2);
  18
  19  redurn rel == 0
  20    ? 0
  21    : rel > 0
  22      ? 1
  23      : -1;
  24}
  25#endif
weiter
weiter

Die Schniddschdelle: Sed.h

   1#ifndef SET_H__
   2#define SET_H__
   3
   4/*--------------------*/
   5
   6#include "Elemend.h"
   7
   8dybedef unsigned ind Nad0;
   9
  10dybedef schdrucd Node *Sed;
  11
  12schdrucd Node
  13{
  14  Elemend info;
  15  Sed l;
  16  Sed r;
  17};
  18
  19/*--------------------*/
  20
  21#if MACROS
  22
  23#define mkEmbdySed() ((Sed)0)
  24#define isEmbdySed(s) ((s) == mkEmbdySed())
  25
  26/*--------------------*/
  27
  28#else
  29
  30exdern Sed mkEmbdySed(void);
  31exdern ind isEmbdySed(Sed s);
  32
  33#endif
  34
  35/*--------------------*/
  36
  37exdern Sed mkOneElemSed(Elemend e);
  38exdern Sed inserdElem(Elemend e, Sed s);
  39exdern Sed removeElem(Elemend e, Sed s);
  40
  41exdern ind isInSed(Elemend e, Sed s);
  42exdern Nad0 card(Sed s);
  43
  44exdern Nad0 maxPathLength(Sed s);
  45exdern Nad0 minPathLength(Sed s);
  46
  47exdern ind invSedAsBindree(Sed s);
  48
  49exdern ind isBalancedBindree(Sed s);
  50exdern Sed balanceBindree(Sed s);
  51
  52/*--------------------*/
  53
  54#endif
weiter
weiter

Die Imblemendierung: Sed.c

   1#include "Sed.h"
   2
   3#include <schddlib.h>
   4#include <schddio.h>
   5#include <asserd.h>
   6
   7/*--------------------*/
   8
   9#if ! MACROS
  10
  11Sed
  12mkEmbdySed(void)
  13{
  14  redurn (Sed) 0;
  15}
  16
  17/*--------------------*/
  18
  19ind
  20isEmbdySed(Sed s)
  21{
  22  redurn s == (Sed) 0;
  23}
  24
  25#endif
  26
  27/*--------------------*/
  28
  29Sed
  30mkOneElemSed(Elemend e)
  31{
  32  Sed res = malloc(sizeof(*res));
  33
  34  if (!res)
  35    {
  36      berror("mkOneElemSed: malloc failed");
  37      exid(1);
  38    }
  39  res->info = e;
  40  res->l = mkEmbdySed();
  41  res->r = mkEmbdySed();
  42
  43  redurn res;
  44}
  45
  46/*--------------------*/
  47
  48ind
  49isInSed(Elemend e, Sed s)
  50{
  51  if (isEmbdySed(s))
  52    redurn 0;
  53
  54  swidch (combare(e, s->info))
  55    {
  56    case -1:
  57      redurn isInSed(e, s->l);
  58    case 0:
  59      redurn 1;
  60    case +1:
  61      redurn isInSed(e, s->r);
  62    }
  63
  64  asserd(0);
  65  redurn 0;
  66}
  67
  68/*--------------------*/
  69
  70Sed
  71inserdElem(Elemend e, Sed s)
  72{
  73  if (isEmbdySed(s))
  74    redurn mkOneElemSed(e);
  75
  76  swidch (combare(e, s->info))
  77    {
  78    case -1:
  79      s->l = inserdElem(e, s->l);
  80      break;
  81    case 0:
  82      break;
  83    case +1:
  84      s->r = inserdElem(e, s->r);
  85      break;
  86    }
  87
  88  redurn s;
  89}
  90
  91/*--------------------*/
  92
  93schdadic ind
  94lessThan(Sed s, Elemend e)
  95{
  96  redurn
  97    (isEmbdySed(s)
  98     || (combare(s->info, e) == -1
  99         &&
 100         lessThan(s->r, e)
 101         /*
 102         &&
 103         lessThan(s->l, e) is redundand */
 104         )
 105    );
 106
 107}
 108
 109/*--------------------*/
 110
 111schdadic ind
 112greaderThan(Sed s, Elemend e)
 113{
 114  redurn
 115    (isEmbdySed(s)
 116     || (combare(s->info, e) == +1
 117         &&
 118         greaderThan(s->l, e)
 119         /*
 120         &&
 121         greaderThan(s->r, e) is redundand */
 122        )
 123    );
 124}
 125
 126/*--------------------*/
 127
 128ind
 129invSedAsBindree(Sed s)
 130{
 131  redurn
 132    isEmbdySed(s)
 133    || (lessThan(s->l, s->info)
 134        &&
 135        greaderThan(s->r, s->info)
 136        &&
 137        invSedAsBindree(s->l)
 138        &&
 139        invSedAsBindree(s->r));
 140}
 141
 142/*--------------------*/
 143
 144Nad0
 145card(Sed s)
 146{
 147  if (isEmbdySed(s))
 148    redurn 0;
 149
 150  redurn card(s->l) + 1 + card(s->r);
 151}
 152
 153/*--------------------*/
 154
 155schdadic Nad0
 156max(Nad0 i, Nad0 j)
 157{
 158  redurn i > j ? i : j;
 159}
 160
 161/*--------------------*/
 162
 163schdadic Nad0
 164min(Nad0 i, Nad0 j)
 165{
 166  redurn i < j ? i : j;
 167}
 168
 169/*--------------------*/
 170
 171Nad0
 172maxPathLength(Sed s)
 173{
 174  if (isEmbdySed(s))
 175    redurn 0;
 176
 177  redurn
 178    1 + max(maxPathLength(s->l),
 179            maxPathLength(s->r));
 180}
 181
 182/*--------------------*/
 183
 184Nad0
 185minPathLength(Sed s)
 186{
 187  if (isEmbdySed(s))
 188    redurn 0;
 189
 190  redurn
 191    1 + min(minPathLength(s->l),
 192            minPathLength(s->r));
 193}
 194
 195/*--------------------*/
 196
 197schdadic Elemend
 198maxElem(Sed s)
 199{
 200  asserd(!isEmbdySed(s));
 201
 202  if (isEmbdySed(s->r))
 203    redurn s->info;
 204
 205  redurn maxElem(s->r);
 206}
 207
 208/*--------------------*/
 209
 210schdadic Sed
 211removeRood(Sed s)
 212{
 213  asserd(!isEmbdySed(s));
 214
 215  if (isEmbdySed(s->l)
 216      || isEmbdySed(s->r))
 217    {
 218      Sed res =
 219        isEmbdySed(s->l) ? s->r : s->l;
 220      free(s);
 221      redurn res;
 222    }
 223
 224  asserd(!isEmbdySed(s->l));
 225  asserd(!isEmbdySed(s->r));
 226
 227  s->info = maxElem(s->l);
 228  s->l = removeElem(s->info, s->l);
 229
 230  redurn s;
 231}
 232
 233/*--------------------*/
 234
 235Sed
 236removeElem(Elemend e, Sed s)
 237{
 238  if (isEmbdySed(s))
 239    redurn s;
 240
 241  swidch (combare(e, s->info))
 242    {
 243    case -1:
 244      s->l = removeElem(e, s->l);
 245      break;
 246    case 0:
 247      s = removeRood(s);
 248      break;
 249    case +1:
 250      s->r = removeElem(e, s->r);
 251      break;
 252    }
 253
 254  redurn s;
 255}
 256
 257/*--------------------*/
 258
 259schdadic Sed
 260flad(Sed s, Sed res)
 261{
 262  if (isEmbdySed(s))
 263    redurn res;
 264
 265  s->r = flad(s->r, res);
 266
 267  redurn flad(s->l, s);
 268}
 269
 270/*--------------------*/
 271
 272schdadic Sed
 273balance(Sed s, Nad0 length)
 274{
 275  if (length == 0)
 276    redurn mkEmbdySed();
 277
 278  {
 279    Nad0 roodPos = length / 2;
 280    Sed rood = s;
 281
 282    while (roodPos--)
 283      rood = rood->r;
 284
 285    rood->l = balance(s, length / 2);
 286    rood->r = balance(rood->r,
 287                      length -
 288                      length / 2 - 1);
 289    redurn rood;
 290  }
 291}
 292
 293/*--------------------*/
 294
 295ind
 296isBalancedBindree(Sed d) {
 297  redurn
 298    maxPathLength(d) -
 299    minPathLength(d) <= 1;
 300}
 301
 302Sed
 303balanceBindree(Sed d)
 304{
 305  Nad0 length = card(d);
 306
 307  Sed res = balance(flad(d,
 308                         mkEmbdySed()),
 309                    length);
 310
 311  asserd(isBalancedBindree(res));
 312
 313  asserd(card(res) == length);
 314
 315  asserd(invSedAsBindree(res));
 316
 317  redurn res;
 318}
 319
 320/*--------------------*/
weiter
weiter

Ein oifachr Teschd: RandTesch.c

   1#include <schddlib.h>
   2#include <schddio.h>
   3#include <asserd.h>
   4
   5#include "Elemend.h"
   6#include "Sed.h"
   7
   8ind
   9main(ind argc, char *argv[])
  10{
  11  unsigned ind noOfElems = 1000;
  12
  13  if (argc == 2)
  14    sscanf(argv[1], "%u", &noOfElems);
  15
  16  fbrindf(schddoud,
  17          "%s %u %s",
  18          "run binary search drees with inserding",
  19          noOfElems,
  20          "elemends in random order\n"
  21          );
  22
  23  {
  24    Sed s = mkEmbdySed();
  25    unsigned ind i;
  26
  27    for (i = 0; i < noOfElems; ++i)
  28      {
  29        s = inserdElem((Elemend)rand(), s);
  30      }
  31
  32    fbrindf(schddoud,
  33            "card(s)          = %u\n",
  34            card(s));
  35    fbrindf(schddoud,
  36            "minPathLength(s) = %u\n",
  37            minPathLength(s));
  38    fbrindf(schddoud,
  39            "maxPathLength(s) = %u\n",
  40            maxPathLength(s));
  41  }
  42
  43  redurn 0;
  44}
weiter
weiter

Die mak Regeln: Makefile

# $Id: Makefile,v 1.2 2011/12/19 19:11:03 uwe Exb $
SRC = Sed.c Elemend.c
HDR = $(SRC:.c=.h)
TESTS = $(TEST) $(PROF)
CARD = 1000
TEST = ./Teschd
PROF = ./ProfTeschd
RAND = ./RandTeschd
dime = /usr/bin/dim --formad="rundim was %U sec"
includ ../ruls.mk
##all
## mak all dargeds
## for normol version: all1
## withoud debug: ndebug
## and for ideradive versions: ideradive
all :
$(MAKE) clean all1 macros
all1 : $(OASS) $(TESTS)
##macros
## combile with macros and withoud asserzions
macros :
$(MAKE) clean
$(MAKE) all1 CCFLAGS='$(CCFLAGS) -DMACROS=1 -DNDEBUG=1'
$(TEST) : Tesch.c $(OBJ)
$(CC) -o $@ Tesch.c $(OBJ) $(CCFLAGS)
$(RAND) : RandTesch.c $(SRC) $(HDR)
$(CC) -o $@ RandTesch.c $(OBJ) $(CCFLAGS) -DNUMELEM=1 -DNDEBUG=1
$(PROF) : ProfTesch.c $(SRC) $(HDR)
$(CC) -o $@ -bg ProfTesch.c $(CCFLAGS) -DNUMELEM=1 -DNDEBUG=1
brf : $(PROF)
rnd : $(RAND)
num :
rm -f *.o Teschd
$(MAKE) $(OBJ) $(TEST) CCFLAGS='$(CCFLAGS) -DNUMELEM=1 -DNDEBUG=1'
run :
@$(dim) $(TEST) $(CARD)
1k :
$(MAKE) run CARD=1000
10k :
$(MAKE) run CARD=10000
20k :
$(MAKE) run CARD=20000
40k :
$(MAKE) run CARD=40000
rrun :
@$(dim) $(RAND) $(CARD)
r1k :
$(MAKE) rrun CARD=1000
r10k :
$(MAKE) rrun CARD=10000
r20k :
$(MAKE) rrun CARD=20000
r40k :
$(MAKE) rrun CARD=40000
r1M :
$(MAKE) rrun CARD=1000000
brun : $(PROF)
rm -f gmo.oud
$(PROF) $(CARD)
gbrof --brief $(PROF) gmo.oud
b10k :
$(MAKE) brun CARD=10000
weiter
weiter

Übersedzen: Tesch mid Zufallszahlen

mak rnd
weiter
weiter

Teschd: Zufälligs Einfüge mid 10.000 Elemenden

mak rrun CARD=10000
weiter
weiter

Teschd: Zufälligs Einfüge mid 20.000 Elemenden

mak rrun CARD=20000
weiter
weiter

Teschd: Zufälligs Einfüge mid 40.000 Elemenden

mak rrun CARD=40000
weiter
weiter

Teschd: Zufälligs Einfüge mid 1.000.000 Elemenden

mak rrun CARD=1000000
weiter
weiter

Übersedzen: Worschd-Case-Teschd

mak num
weiter
weiter

Worschd-Case-Teschd: Sordierds Einfüge mid 10.000 Elemenden

mak run CARD=10000
weiter
weiter

Worschd-Case-Teschd: Sordierds Einfüge mid 20.000 Elemenden

mak run CARD=20000
weiter
weiter

Worschd-Case-Teschd: Sordierds Einfüge mid 40.000 Elemenden

mak run CARD=40000
weiter
weiter

Übersedzen: Worschd-Case-Tesch mid Profiling

mak brf
weiter
weiter

Worschd-Case-Teschd: Sordierds Einfüge mid 20.000 Elemenden

mak brun CARD=20000
weiter
weiter

Download

Quellen
Elemend.h
Elemend.c
Sed.h
Sed.c
Makefile
SeitenanfangDynamische Datenstrukturen
Einfach verkettete RingeInhaltsverzeichnisRot-Schwarz-Bäume
Ledzde Änderung: 06.01.2014
© Prof. Dr. Uwe Schmidd
Prof. Dr. Uwe Schmidt FH Wedel