This chapter introduces the concept of -
Clarify the meaning of an
**abstract****data****type**(ADT) -
Explain the design of a
**linked****list**ADT -
Explain the design of a
**queue**ADT -
Explain the design of a
**binary****tree**ADT
## Concepts:
An ADT packages methods and data representations together in a way that is
One ADT is a
An ADT specifies two types of information: a set of - Initialize list to empty
- Determine if list is empty
- Determine if list is full
- Determine number of items in list
- Add item to end of list
- Traverse list, processing each item in the list.
The three step process in creating an ADT moves from the -
Provide an
**abstract****description**of the type's properties and of the**operations**you can perform on the type. -
Develop a
**programming****interface**that implements the ADT. -
Write
**code**to implement the interface.
Building the #define TSIZE 45 struct film { char title[TSIZE]; int rating; }; typedef struct film Item;
This defines
A - Initialize queue to empty
- Determine whether queue is empty
- Determine whether queue is full
- Determine number of items in the queue
- Add item to rear of queue
- Remove and recover item from front of queue
A primary difference between a linked list Node and a queue Node is as follows: typedef struct node { Item item; struct node * next; } NODE; typedef struct queue { Node * front; Node * rear; int items; } Queue;
With a
Comparing a linked list to an
With a linked list, a search must be performed
Each node in a - A tree is either an empty set of nodes or a set of nodes with one node designated as the root.
- Each node has exactly two trees, called subtrees, descending from it.
- Each subtree is itself a binary tree, which include the possibility of an empty tree.
- A binary search tree is an ordered binary tree in which each node contains an item, in which all items in the left subtree precede the root item and in which the root item precedes all items in the right subtree.
The - Determine if the tree is empty
- Determine if the tree is full
- Determine the number of items in the tree
- Add an item to the tree
- Remove an item from the tree
- Search the tree for an item
- Visit each item in the tree
A binary tree is efficient only if it is |