Transcript Chapter 16 PowerPoint

Chapter 16 – Data Structures
and Recursion
Data Structures
 Built-in
– Array
– struct
 User
–
–
–
–
developed
linked list
stack
queue
tree
Lesson 16.1
Programmer-defined Linked List Class
 Data
members (could be different types)
stored in (usually) contiguous block of
memory
– One of the data members is a pointer variable

Address stored points to the next object
 Data
member that has address creates link
between objects
 Each object referred to as a node
Lesson 16.1
Linked List
Representation
Head node
Object 2
FactObjects
that link
address
in
points
tovariable
next
Pointer
value
linked
list object
Object 3
Object 4
Lesson 16.1
Actions on Linked List
 Must
go node to node from head node
 Can delete node by making address that points
to one to be deleted to next object
 Can insert node by changing address stored in
pointer variable for node preceding location of
insertion
 Can move node from one location to another
 Must keep track of current node and head
node
Lesson 16.1
Linked List Classes
 Use
two classes to create linked list
– Node class
Holds only the data
 All data members public because no function
members

– Second used to manipulate nodes
One variable holds address of first object in list
 Another variable holds current node address

Lesson 16.1
Node Class
 General
form:
Class name
class Node
{
public:
Data types
type member1;
Identifiers
representing
(not necessarily
type
member2;
Nameallfor
node
data
thestoring
same)
…
address of next
Node*
next_node;
node in list
};
Lesson 16.1
Second Class


Used to manipulate
the nodes
Data only pointer
variables used to
hold addresses
Lesson 16.1
Address of node
being manipulated
Address of
first object
class Llist
{
private:
Node* head;
Node* current;
public:
void make_list ( );
void show_list ( );
};
Stack
 Data
structure created using linked list model
 With stack can perform only two fundamental
operations
– Push

Insert node immediately after the head
– Pop

Retrieve and delete node immediately after head
 Only
work with nodes at top
Lesson 16.2
Stack Classes
 Two
classes create stack
– One class holds only data
Same form as linked list
 one member must be pointer variable

– Second class used to manipulate nodes
Data only pointer variables used to hold addresses of
nodes
 Nodes of interest for stack are head and tail
 Function members initialize, push and pop items

Lesson 16.2
Stack Class
class Stack
Address of head node
{
and last node
private:
Node* head;
Node* tail;
public:
Stack ( );
void push (int);
int pop ( );
};
Lesson 16.2
Stack Classes
 Create
empty stack by initializing a head and
tail node
– Allow finding top and bottom of stack
 Should
not pop from an empty stack
 LIFO
– Last In First Out

Last node pushed is first node popped off
Lesson 16.2
Queue Class
 Can
create with linked list form
– Must have a head and tail node
 FIFO
– First node inserted into queue is first node
removed
 Nodes
are inserted at tail of queue and
removed from head of queue
Lesson 16.3
Queue Class
class Queue
{
Class Node
private:
{
Node* head;
public:
Node* tail;
type member;
public:
Node* next_node;
Queue ( );
};
void insert (int);
int remov ( );
};
Lesson 16.3
Types of Queues
 Dequeue
- "double-ended queue"
– Nodes can be inserted at either end and removed
from either end
 Output
restricted dequeue
– Insertion allowed at both ends but removal
allowed at only one end
 Input
restricted dequeue
– Removal allowed at both ends, insertion allowed
at only one end
 Priority
queue
– Priority for each node – highest priority
processed first
Lesson 16.3
Binary Tree
 Tree
is particular type
of graph
– Binary tree is
particular type of tree
 Graph
is data structure
that includes nodes
– each node can have
more than one pointer
Linked List
Lesson 16.4
Graph
Graph Terminology
 Nodes
can also be called vertices or points
 Connections between nodes called edges or
arcs
 Two nodes considered adjacent of neighbors
if edge connects them
 Path between one node and another indicated
by list of connect nodes between two
 Simple path is path with no repeated nodes
Lesson 16.4
Graphs
 Weighted
graph
– Assign length or cost of each edge
 Tree
– graph with characteristic that there is only one path
between any two nodes
– Rooted tree
Tree with one node specified to be root
 Root traditionally shown at top of diagram

– Binary tree

Tree in which no node has more than two children
Lesson 16.4
Tree Class


Similar to linked
list and stack
classes
Two classes
– One class holds
content of nodes
– Second class
manipulates the
nodes
Lesson 16.4
class Tree_node
{
public:
type member;
Tree_node* left_child;
Tree_node* right_child;
};
Recursion
 Within
function body there is call to
function with identical name and signature
 Basic action which is repeated until it
reaches the final iteration of the basic action
Lesson 16.5
Summary
Learned how to:
 Create
a linked list
 Create
a stack
 Create
a queue
 Create
a binary tree
 Identify
recursive functions