Solved

ADT's

Posted on 1997-06-15
1
193 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
Comment Utility
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

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

Scam emails are a huge burden for many businesses. Spotting one is not always easy. Follow our tips to identify if an email you receive is a scam.
This article explains how to prepare an HTML email signature template file containing dynamic placeholders for users' Azure AD data. Furthermore, it explains how to use this file to remotely set up a department-wide email signature policy in Office …
This video discusses moving either the default database or any database to a new volume.
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…

772 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now