?
Solved

ADT's

Posted on 1997-06-15
1
Medium Priority
?
201 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
1 Comment
 

Accepted Solution

by:
kev45 earned 100 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

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

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

What's worse than having your data encrypted by ransomware? Getting attacked by a so-called "wiper," which simply destroys the data and offers you no hope of ever seeing it again.
In today's business world, data is more important than ever for informing marketing campaigns. Accessing and using data, however, may not come naturally to some creative marketing professionals. Here are four tips for adapting to wield data for insi…
Visualize your data even better in Access queries. Given a date and a value, this lesson shows how to compare that value with the previous value, calculate the difference, and display a circle if the value is the same, an up triangle if it increased…
In this video, Percona Director of Solution Engineering Jon Tobin discusses the function and features of Percona Server for MongoDB. How Percona can help Percona can help you determine if Percona Server for MongoDB is the right solution for …
Suggested Courses

764 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