home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / lang / pascal / 4899 < prev    next >
Encoding:
Internet Message Format  |  1992-08-18  |  2.8 KB
  1. Path: sparky!uunet!mcsun!sunic!dkuug!daimi!u912080
  2. From: u912080@daimi.aau.dk (Rune Bang Lyngs|)
  3. Newsgroups: comp.lang.pascal
  4. Subject: Help! Dispose pointers in a tree
  5. Message-ID: <1992Aug19.015706.29728@daimi.aau.dk>
  6. Date: 19 Aug 92 01:57:06 GMT
  7. Sender: u912080@daimi.aau.dk (Rune Bang Lyngs|)
  8. Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
  9. Lines: 139
  10.  
  11.  
  12. The following program should make a binartree.
  13. Get it's height and start over again.
  14.  
  15. My problem is that the procedure DelTree maybe not delete the whole tree
  16. (all poineters) as it should.
  17. Anyway the heap-memory is being eating up.
  18. If I write tree 200 2000 I get a heap-overflow after some time - why?
  19. And if I write tree 20000 4 crash - why?
  20. The solution are simple - I believe that but please help me!!!!
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29. Program binaertrae;
  30. Uses crt;
  31.  
  32. Type
  33.  TreePointer = ^Tree;
  34.  Tree = Record
  35.          Element : Word;
  36.          left    : Treepointer;
  37.          right   : Treepointer;
  38.         End;
  39.  
  40. Var
  41.  P : TreePointer;
  42.  Taeller,i,j : Word;
  43.  hs,ss : Longint;
  44.  Kode : Word;
  45.  Antal:Word;
  46.  ghs: real;
  47.  
  48. Function Max(x,y:Word):Word;
  49. Begin
  50. if x>y then Max:=x else Max:=y;
  51. End;
  52.  
  53. Procedure Init(Var TP: TreePointer);
  54. Begin
  55.  New(TP);
  56.  TP:=NIL;
  57. End;
  58.  
  59. Procedure Insert(Var TP: TreePointer;Element: Word;Var a:Word);
  60. Var
  61.  P : TreePointer;
  62.  
  63.  Procedure Insert2(Var TP : TreePointer;EP: TreePointer;Var a:Word);
  64.  Begin
  65.   IF EP^.Element=TP^.Element Then exit;
  66.   If EP^.Element<TP^.Element Then
  67.    If TP^.Left=NIL Then
  68.    Begin
  69.     a:=a+1;
  70.     TP^.Left:=EP;
  71.    End
  72.    else Insert2(TP^.Left,EP,a)
  73.   else
  74.    If TP^.Right=NIL Then
  75.    Begin
  76.     a:=a+1;
  77.     TP^.Right:=EP;
  78.    End
  79.    else Insert2(TP^.Right,EP,a);
  80.   End;
  81.  
  82. Begin
  83.  New(P);
  84.  P^.Element:=Element;
  85.  P^.Left:=NIL;
  86.  P^.Right:=NIL;
  87.  If TP=NIL Then
  88.   TP:=P
  89.  else
  90.   Insert2(TP,P,a);
  91. End;
  92.  
  93. Procedure Print(Var TP : Treepointer);
  94. Begin
  95.  If TP=NIL then exit;
  96.  Print(TP^.Left);
  97.  Write(TP^.Element:8);
  98.  Print(TP^.Right);
  99. End;
  100.  
  101. Function Height(Var TP : TreePointer):Word;
  102. Begin
  103.  If TP=NIL then
  104.  Begin
  105.    Height:=0;
  106.  End
  107.   else
  108.  Height:=1+Max(Height(TP^.Left),Height(TP^.Right));
  109. End;
  110.  
  111. Procedure DelTree(Var Point : TreePointer);
  112. Begin
  113.   If Point=NIL then exit;
  114.   If Point^.Left<>NIL then DelTree(Point^.Left);
  115.   If Point^.Right<>NIL then DelTree(Point^.Right);
  116.   dispose(Point);
  117. End;
  118.  
  119. Begin
  120.  hs:=0;
  121.  ss:=0;
  122.  Val(Paramstr(2),i,kode);
  123.  If ParamCount<2 then exit;
  124.  for j:=1 to i do
  125.  Begin
  126.   Val(Paramstr(1),antal,kode);
  127.   If Paramcount=0 then antal:=10000;
  128.   kode:=1;
  129.   randomize;
  130.   Init(P);
  131.   For taeller:=1 to Antal do
  132.   Begin
  133.    Insert(P,random(65535),kode);
  134.   End;
  135.   {
  136.   Print(P);
  137.   }
  138.   hs:=hs+height(p);
  139.   inc(hs);
  140.   ss:=ss+kode;
  141.   ghs:=1+hs/j;
  142.   DelTree(p);
  143.   clrscr;
  144.   writeln('Average elements=',(ss/j):5:1);
  145.   writeln('Average height=',(ghs):3:2);
  146.   writeln('Loop number:',j);
  147.   writeln('MemAvail=',MemAvail);
  148.  end;
  149. End.
  150.