Chapter 8 Outline

8.1 What is Abstract Data Type?

·       Abstract data type (ADT):

o   ADT is a container whose properties (data & operations) are specified independently of any particular implementation.

o   We know their properties and operations and we understand which types of values they can contain, but we have no information about their internal structure or implementation.
(u know what it Is, what it means, but don’t need to see the implementation of it [no need to know how]) Example:

§  Gmail (object)

§  Sign In/Create account (Operations)

§  User no need to look at the details, just do it.

o   The basic idea is that the implementation of these operations is written ONCE in the program, and any other part of the program that needs to perform an operation on the ADT can do so by calling the appropriate function.

o   The goal in design is to reduce complexity thru abstraction.

o   To put concept of ADT into context, we need to look at how we view data.

§  3 Perspectives of viewing data in computing: (How much level u want the user to see it)

w  Application Level (user): The view of data w/thin a particular problem.
(Don’t have to look at anything else, just look at particular problem)

w  Logical Level (Abstract): Abstract view of the data values and the operations that manipulate them.
(Object has behavior) **work w/ differ classes**

w  Implementation Level: The specific representation of the structure that holds the data items and coding of the operations in a programming language.
(You see codes) **Fixing messy codes etc**

§  These 3 views concerned with Data Structures – the implementation of a composite data field in an abstract data type.

w  It is the way of storing the data in a manner so that we can access those data easily at later time.
(Stack, Queue, List, Tree)

§  The ADT are containers which data items are stored and each exhibits specific behaviors these are Containers because their sole purpose is to hold other objects.

w  Containers – Objects whose role is to hold and manipulate others.
(variable, data[], SUM)

o   Logical Implementations:

o   2 logical implementations of containers:

§  Array-Based Implementation – Objects in the container are kept in an array.

§  Link-Based Implementation – Objects in the container are not kept physically together, but each item tells you where to go to get the next one in structure.
(Don’t have to put them together, not need to be together can jump and come back)

·       8.2 Stacks

o   Stack is an abstract composite structure in which accesses are made at only one end.

§  LIFO – Last In First Out    eg: Carts in  the Mall

§  Insert – Push

§  Delete – Pop

·       8.3 Queues

o   Queues are an abstract structure in which items are entered at one and removed from the other end. 

§  FIFO – First In First Out   eg: Drinks sell @7-11

§  Insert – Enqueue/Enq/Enter/Insert

§  Delete – Dequeue/Deque/Deq/Delete/Remove

·       8.4 Lists

o   List is like a container of items.

o   The items are:

§  Homogeneous, Linear, Have vary lengths

o   Logical operations be applied:

§  Add item

§  Remove item

§  Get next item

§  More items

o   Array – Built-In Structure & List – Abstract Structure.

o   A list may be visualized as a Link Structure, this is based on the concept of node

o   Node consist 2 pieces of info: User’s data & a link/pointer that indicates where to find the next node.

§  Link Structure – An implementation of a container where the items are stored together with information on where the next item can be found. 
(Stack and Queue)

o   If the list is an unsorted list, the items will be printed in the order in which they are inserted.

o   If the list is sorted, the items will be printed in sorted order.

o   Stacks, Queues and Lists are LINEAR in nature (items are next to each other) only one relationship is being modeled.

·       8.5 Trees

o   Hierarchical structures, each node in the tree can have more than two children.

o   Binary Trees :

§  An abstract structure in which each node is capable of having 2 successor nodes called children, and so on (tree its branching structure)

§  Beginning of the tree is a unique starting node called root.

w  Binary Trees – An abstract composite structure OR A linked container w/ a unique starting node called the root, in which each node is capable of having two child nodes and in which a unique path exists from the root to every other node.                            

w  Root – The unique starting node in a tree. (1 is the root)

                       

§  A tree node that has no children is Leaf.  (7,8,9,10 are leaf nodes)

§  Every node has a unique (single) parent.      
(2 = left subtree & 3 = right subtree of 1)

§  Any node in the tree can considered the root node of a subtree. (subtree whose root node 2 also includes the node 4 & 7)

o   Binary Search Tree :

§  It is like a sorted list in that there is a semantic ordering in the nodes.

§  A binary tree (shape property) that has the (semantic) property that characterizes the values in a node of a tree:

w  (bigger go right, lesser go left)

o   Build Binary Tree :  Bigger go right, lesser go left

o   Other Operations

§  Binary search tree is an object with the same functionality as a LIST.

·       8.6 Graphs

o   A graph is made up of sets of nodes called vertices and sets of lines called edges (arcs) that connect the nodes.

o   The vertices (dots) in the graph represent objects; the edges (lines) describe relationships among the vertices (dots).

§  Graph – A data structure that consists of a set of nodes and a set of edges that relate the nodes to each other.

§  Vertex – A node in a graph

§  Edge (arc) – A pair of vertices representing a connection between two nodes in a graph.

o   Undirected graph – A graph in which the edges have no direction. (可來回)

§ 

Two vertices that are connected by one edge – Adjacent Vertices

o   Directed graph (digraph) – A graph in which each edge is directed from one vertex to another (or the same) vertex.

§  Path – A sequence of vertices that connects two nodes in a graph.

o   LISTS, STACKS, QUEUES, TREES – All just holding containers.

§  Stacks return the item that has been in the stack the least amount of time.

§  Queue returns the item that has been in the queue the longest amount of time.

§  List & Trees return the info that is requested.

§  Graph has algorithm defined upon it that actually solve classic problems.

o   Graph Algorithms

§  Depth-First Search – Given a starting vertex and an ending vertex, we can develop an algorithm that finds a path from startVertex to endVertex.

w  It is called Depth First search because we start at a given vertex and go to the deepest branch and explore as far down one path before taking alternative choices earlier branches.

§  Breadth-First Search

§  Single-Source Shortest-Path Search

·       8.7 Subprograms

o   How we pass info back and forth btw algorithms and sub-algorithms.

o   We call them subprograms rather than sub-algorithms.

o   Subprograms are available as part of high-level language.

o   Parameter Passing

o   A parameter list is a list of the identifiers or values with which the subprograms is to work.

§  Parameter List – A mechanism for communicating between two parts of a program.

§  Parameters – The identifiers listed in parentheses beside the subprogram name; sometimes called formal parameters.

§  Arguments – The identifiers listed in parentheses on the subprogram call; sometimes called actual parameters.

o   Value and Reference Parameters

o   2 ways of passing parameters:

§  Value Parameter – A parameter that expects a copy of its argument to be passed by the calling unit (put on msg board).
(The calling unit gives a copy of the argument to subprogram)

§  Reference Parameter – A parameter that expects the address of its argument to be passed by the calling unit (put on msg board).
(The calling unit gives the address of the argument to subprogram)