We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you a podcast all about Citrix Workspace, moving to the cloud, and analytics & intelligence. Episode 2 coming soon!Listen Now

x

ADT's

dave1
dave1 asked
on
Medium Priority
227 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.
Comment
Watch Question

Commented:
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

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.