-----------------------------------

ringo

Wed Apr 06, 2005 7:28 am


modify a record in a tree

-----------------------------------

hi i'm doing a little dictionnary ,and i want to add a procedure that modifies a word by deleting it and inserting the new one with new spelling.
i want to use a tree. how can i proceed ?
anybody have any suggestion to help me please ?

here is my beginning  :lol: 


type Entry :
  record
    english   : string( 50 )
    definition : array 1..10 of string( 100 )
    n     : int
  end record




-----------------------------------

Martin

Wed Apr 06, 2005 8:30 am



-----------------------------------

Well, are you familiar with binary search trees? For now, don't worry about making the tree balanced, as balancing a search tree can seem complicated at first.

Using numbers, here is how a binary search tree works:

We insert a value, let's say 10. Since the tree is initially empty, this becomes the root of the tree. Our tree now looks like this:
10
Now, we insert a value 5. Because 5 is less than 10, it goes to the left of 10. Our tree now looks like this:

   10
   /
 5

Now, we insert the value 7. 7 is less than 10, so it goes to the left of 10. 7 is greater than 5 though, so it goes to the right of 5. Our tree looks like this:

   10
   /
 5
   \
    7

The basic idea is that whenever you want to insert a value into the tree, you do the following:

Make a pointer to the root of the tree, call it current.
set value to the value you want to insert.
loop
   if current.data > value then
      if current.left not= NULL then
           current = current.left  %move down the tree
      else %it's null, insert it here
           %insert the new node to the left
           exit
      end if
    elsif current.data < value then
       %do the same as above, only moving right
        ...
    end if
end loop

Searching is done in a similar fasion to inserting. Now, to delete an element in a tree, simply find it in a tree, get rid of it, and reinsert all of the values that would get severed.


-----------------------------------

ringo

Wed Apr 06, 2005 11:10 am



-----------------------------------

thank you martin , i'm working on it with this method


-----------------------------------

ringo

Fri Apr 08, 2005 5:38 am



-----------------------------------

sorry for my english
hi i want to change the spelling of a word without getting rid of the definitions , is it possible without a delete function and without loading the entry record in an array ?
or if someone have a better idea ,it would be good 
thank you

here is my updated code and i'm lost with the proc modify


proc Wait
  put "Press a key to continue ..." ..
  var s : string( 1 )
  getch( s )
  put skip
end Wait

type entry :
  record
    english    : string( 30 )
    definition : array 1..5 of string( 50 )
    n     : int
  end record

function emptyentry : entry
  var RetVal : entry
  RetVal.english := ""
  for i:lower( RetVal.definition )..upper( RetVal.definition )
    RetVal.definition( i ) := ""
  end for
  RetVal.n := 0
  result RetVal
end emptyentry

function valid( e : entry ) : boolean
  result e.english not= ""
end valid

function GetEntry( bGetInfo : boolean ) : entry
  var e : entry := emptyentry
  put "enter the english word : " ..
  get e.english:*
  if bGetInfo and valid( e ) then
    var i : int := 1
    loop
      exit when i > upper( e.definition )
      var d : string( 100 )
      put "Enter the definition no ", i, "- " ..
      get d:*
      exit when d = ""
      e.definition( i ) := d
      i += 1
    end loop
  end if
  result e
end GetEntry

procedure PutEntry( e : entry )
  if valid( e ) then
    var i : int := 1
    put e.english
    put "Definitions:"
    loop
      exit when i > upper( e.definition )
      exit when e.definition( i ) = ""
      put "\t", i, "- ", e.definition( i )
      i += 1
    end loop
  end if
end PutEntry

type DocEntry :
  record
    info : entry
    g    : pointer to DocEntry
    d    : pointer to DocEntry
  end record

type DocType : pointer to DocEntry

function Empty: DocType
  result nil
end Empty

function isnil( Doc : DocType ) : boolean
  result Doc = nil
end isnil

function root( Doc : DocType ) : entry
  pre not isnil( Doc )
  result Doc->info
end root

function left( Doc : DocType ) : DocType
  pre not isnil( Doc )
  result Doc->g
end left

function right( Doc : DocType ) : DocType
  pre not isnil( Doc )
  result Doc->d
end right

function cons( e : entry, g, d : DocType ) : DocType
  var nn : DocType
  new nn
  nn->info := e
  nn->g    := g
  nn->d    := d
  result nn
end cons

function insert( e : entry, Doc : DocType ) : DocType
  if Doc = nil then
    result cons( e, Doc, Doc )
  elsif e.english info.english then
    result cons( Doc->info, insert( e, Doc->g ), Doc->d )
  else
    result cons( Doc->info, Doc->g, insert( e, Doc->d ) )
  end if
end insert

function GetBow( e : entry, Doc : DocType ) : DocType
  if Doc = nil or Doc->info.english = e.english then
    result Doc
  elsif Doc->info.english > e.english then
    result GetBow( e, Doc->g )
  else
    result GetBow( e, Doc->d )
  end if
end GetBow

procedure FreeDoc( Doc : DocType )
  if Doc not= nil then
    var n : DocType := Doc
    FreeDoc( n->g )
    FreeDoc( n->d )
    free n
  end if
end FreeDoc

function depth( Doc : DocType ) : int
  if Doc = nil then
    result 0
  else
    result max( depth( Doc->g ), depth( Doc->d ) ) + 1
  end if
end depth


const DicoFile : string := "C:\\Documents and Settings\\...\\dico.txt"


function Initialise : DocType
  var Doc : DocType := Empty

  
  var nFile : int
  open: nFile, DicoFile, read
  if nFile not= 0 then
    loop
      exit when eof( nFile )
      var e : entry
      read: nFile, e
      Doc := insert( e, Doc )
    end loop
    close: nFile
  end if
  put "depth of the document is ", depth( Doc )
  Wait
  result Doc  
end Initialise

procedure SaveDocument( Doc : DocType, nFile : int )
  if not isnil( Doc ) then
    var e : entry := root( Doc )
    write: nFile, e
    SaveDocument( Doc->g, nFile )
    SaveDocument( Doc->d, nFile )
  end if
end SaveDocument

procedure EditDocument( Doc : DocType )
  if not isnil( Doc ) then
    EditDocument( Doc->g )
    PutEntry( Doc->info )
    EditDocument( Doc->d )
  end if
end EditDocument


procedure Quit( Doc : DocType )
  put "Exit"
  var nFile : int

  open: nFile, DicoFile, write
  if nFile not= 0 then
    SaveDocument( Doc, nFile )
    close: nFile
  end if
  FreeDoc( Doc )
end Quit

procedure add( var Doc : DocType )
  
  loop
    var e : entry := GetEntry( true )
    exit when not valid( e )
    Doc := insert( e, Doc )
  end loop
end add

procedure display( Doc : DocType )
  
  EditDocument( Doc )
  loop
    var e : entry := GetEntry( false )
    exit when not valid( e )
    var bow : DocType := GetBow( e, Doc )
    
    if isnil( bow ) then
      put "not found "
      Wait
    else
      PutEntry( root( bow ) )
    end if
  end loop
end display

%-----------------------------------MODIFY--------------------
procedure modify(var Doc:DocType)
var nFile:int
open:nFile,DicoFile,write,mod

    EditDocument(Doc)
    var k:entry

var e:entry:=GetEntry(true)
    
    
    put "Enter new Name: " ..
                get k.english: *
                for i : 1 .. (15 - length (k.english))
                    k.english:= e.english+ ""
                   
                    
                    
                    end for
    Doc:=insert(k,Doc)
    close :nFile
  
end modify
%-------------------------------------

procedure putMenu
  cls
  put "1-display"
  put "2-add a word"
  put "3-modify"
  put "4-quit"
  put "your choice : " ..
end putMenu

function choice : int
  loop
    putMenu
    var choice : string( 1 )
    getch( choice )
    put skip
    case choice( 1 ) of
      label '1':
        result 1
      label '2':
        result 2
      label '3':
        result 3
      label '4':
        result 0
      label:
    end case
  end loop
end choice


var Document : DocType := Initialise


loop
  var nChoice : int := choice
  exit when nChoice = 0
  case nChoice of
    label 1:
      display( Document )
    label 2:
      add( Document )
    label 3:
      modify(Document)
    label:
  end case
  Wait
end loop


Quit( Document )



-----------------------------------

Martin

Fri Apr 08, 2005 8:27 am



-----------------------------------

Don't modify a record, just delete it and insert the new record into the tree. Modifying it runs the potential of ruining your tree.

I'll check it out more when I get home.


-----------------------------------

ringo

Fri Apr 08, 2005 11:20 am



-----------------------------------

thank u martin

i know how to delete the whole text file ,and to insert a new record , 
but i don't know how to delete only one record ????
i have some problems when i open the file to write on it ,everything erase
somebody has an idea  please ?