Solved

ADT's

Posted on 1997-06-15
1
196 Views
Last Modified: 2010-04-16
Please could anyone can help with this apparantly easy question on ADT's


The generic ADT named DIRECTORY(NI), where NI represents any ADT having a NAME operation returning a STRING. An example of NI is the ADT PERSON that has an operation called NAME which returns the name of a person as an instance of type STRING. The operations of the generic directory are as follows:-
CREATEDIR - creates an empty directory.
RETRIEVE - takes a directory and a name(i.e a string) as source and returns an item of NI as its result.
ADD - takes a directory and an item of NI and returns the directory with that item added.
ISINDIR - takes a directory and a name and returns TRUE if an item with that name is in the directory.
COUNT - takes a directory and return the number of items in that directory.

{THE QUESTION}

Using the constructive approach, write down the semantics of the RETRIEVE and COUNT operations.  Use the ADT BSTree as an underlying model.
0
Comment
Question by:dave1
1 Comment
 

Accepted Solution

by:
kev45 earned 50 total points
ID: 1215380
If I understand your question correctly, NI is a node on a binary tree as follows:

TYPE
  NIptr = ^NIType;
  NIType = RECORD
             Left : ^NIType;
             Right : ^NIType;
             Data : string;    {I'm assuming Turbo Pascal}
           END;
VAR
  NI : NIType;
  DIRECTORY : NIptr;

with a function name as follows:
FUNCTION NAME(N : string) : string;
BEGIN
  NAME := NI.Data;
END;

Therefore Directory's Retrieve would be as follows:

FUNCTION RETRIEVE(N : string) : NIType;
VAR
  Tmp : NIType;

BEGIN
  Tmp.Left := nil;
  Tmp.Right := nil;
  Tmp.Data := N;
  RETRIEVE := Tmp;
END;

And count would be as follows:

FUNCTION Count (D : ^NIType) : integer; {or longint if many nodes}
BEGIN
  IF (D.left = nil) AND (D.right = nil) THEN
    Count := 1
  ELSE
    IF (D.left = nil) THEN
      Count := Count(D.right) + 1
    ELSE
      IF (D.right = nil) THEN
         Count := Count(D.left) + 1
      ELSE
         Count := Count(D.left) + Count(D.right) + 1;
END;  

Kevin
0

Featured Post

Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Delphi XE, DataSnap, JSon and java 8 1,041
Unsigned int64 to unsigned int32 10 1,678
entry point in my program 14 491
How to slide a FMX tabcontrol tabitem up from the bottom 3 1,113
Established in 1997, Technology Architects has become one of the most reputable technology solutions companies in the country. TA have been providing businesses with cost effective state-of-the-art solutions and unparalleled service that is designed…

803 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question