Transcript Power Point Slides for Lecture 22

CISC181 Introduction to
Computer Science
Dr. McCoy
Lecture 22
November 17, 2009
1
Linked List – Concord List Nodes
• See Example:
~/Class/cisc181/examples/concord-list
• Driver Program
• Header files for both node and list
• Implementation files for both
• Fun with linked lists – adding, deleting,
walking through,…
2
3
Insert at front
a)
firstPtr
7
11
newPtr
12
b)
firstPtr
7
11
newPtr
12
firstPtr = newPtr
If list empty, then
firstPtr = lastPtr = newPtr
 2003 Prentice Hall, Inc. All rights reserved.
newPtr->nextPtr = firstPtr
4
Insert at back
a)
firstPtr
12
b)
lastPtr
7
firstPtr
12
11
lastPtr
7
11
newPtr
5
newPtr
5
lastPtr->nextPtr = newPtr
lastPtr = newPtr
If list empty, then
firstPtr = lastPtr = newPtr
 2003 Prentice Hall, Inc. All rights reserved.
5
Remove from front
a)
firstPtr
12
b)
lastPtr
7
11
5
firstPtr
lastPtr
tempPtr = firstPtr
12
tempPtr
delete tempPtr
 2003 Prentice Hall, Inc. All rights reserved.
7
11
5
firstPtr = firstPtr->next
If there are no more nodes,
firstPtr = lastPtr = 0
6
Remove from back
"Walk" list until get next-to-last node, until
currentPtr->nextPtr = lastPtr
a)
firstPtr
12
b)
lastPtr
currentPtr
firstPtr
12
11
7
7
5
lastPtr
11
5
tempPtr = lastPtr
lastPtr = currentPtr
tempPtr
delete tempPtr
 2003 Prentice Hall, Inc. All rights reserved.
7
17.4 Linked Lists
• Types of linked lists
– Singly linked list (used in example)
• Pointer to first node
• Travel in one direction (null-terminated)
– Circular, singly-linked
• As above, but last node points to first
– Doubly-linked list
• Each node has a forward and backwards pointer
• Travel forward or backward
• Last node null-terminated
– Circular, double-linked
• As above, but first and last node joined
 2003 Prentice Hall, Inc. All rights reserved.
Display 17.3
Adding a Node
to the Head of
a Linked List
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-8
Lost Nodes Pitfall:
Display 17.5 Lost Nodes
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-9
Display 17.6 Inserting in the Middle of a
Linked List (1 of 2)
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-10
Display 17.6 Inserting in the Middle of a
Linked List (2 of 2)
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-11
Display 17.7
Removing
a Node
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-12
Searching a Linked List
• Function with two arguments:
IntNodePtr search(IntNodePtr head, int target);
//Precondition: pointer head points to head of
//linked list. Pointer in last node is NULL.
//If list is empty, head is NULL
//Returns pointer to 1st node containing target
//If not found, returns NULL
• Simple "traversal" of list
– Similar to array traversal
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-13
Pseudocode for search Function
• while (here doesn’t point to target node or
last node)
{
Make here point to next node in list
}
if (here node points to target)
return here;
else
return NULL;
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-14
Algorithm for search Function
• while (here->getData() != target &&
here->getLink() != NULL)
here = here->getLink();
if (here->getData() == target)
return here;
else
return NULL;
• Must make "special" case for empty list
– Not done here
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-15
16
17.5 Stacks
• Stack
– Nodes can be added/removed from top
• Constrained version of linked list
• Like a stack of plates
– Last-in, first-out (LIFO) data structure
– Bottom of stack has null link
• Stack operations
– Push: add node to top
– Pop: remove node from top
• Stores value in reference variable
 2003 Prentice Hall, Inc. All rights reserved.
A Stack—Graphic:
Display 17.12 A Stack
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-17
Stack Push and Pop
• Adding data item to stack  push
– Considered "pushing" data onto stack
– Recall: goes to "top" of stack
• Removing data item from stack  pop
– Considered "popping" item off stack
– Recall: removed from "top" of stack
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-18
19
17.5 Stacks
• Upcoming program
– Create stack from list
• insertAtFront, removeFromFront
– Software reusability
• Inheritance
– Stack inherits from List
• Composition
– Stack contains a private List object
– Performs operations on that object
– Makes stack implementation simple
 2003 Prentice Hall, Inc. All rights reserved.
20
17.6 Queues
• Queue
–
–
–
–
Like waiting in line
Nodes added to back (tail), removed from front (head)
First-in, first-out (FIFO) data structure
Insert/remove called enqueue/dequeue
• Applications
– Print spooling
• Documents wait in queue until printer available
– Packets on network
– File requests from server
 2003 Prentice Hall, Inc. All rights reserved.
21
17.6 Queues
• Upcoming program
– Queue implementation
– Reuse List as before
• insertAtBack (enqueue)
• removeFromFront (dequeue)
 2003 Prentice Hall, Inc. All rights reserved.
22
17.7 Trees
• Linear data structures
– Lists, queues, stacks
• Trees
– Nonlinear, two-dimensional
– Tree nodes have 2 or more links
– Binary trees have exactly 2 links/node
• None, both, or one link can be null
 2003 Prentice Hall, Inc. All rights reserved.
Trees Introduction
• Trees can be complex data structures
• Only basics here:
– Constructing, manipulating
– Using nodes and pointers
• Recall linked list: nodes have only one
pointer  next node
• Trees have two, & sometimes more,
pointers to other nodes
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-23
24
17.7 Trees
• Terminology
– Root node: first node on tree
– Link refers to child of node
• Left child is root of left subtree
• Right child is root of right subtree
– Leaf node: node with no children
– Trees drawn from root downwards
B
A
D
C
 2003 Prentice Hall, Inc. All rights reserved.
Tree Structure:
Display 17.35 A Binary Tree (1 of 2)
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-25
Tree Structure:
Display 17.35 A Binary Tree (2 of 2)
Copyright © 2010 Pearson Addison-Wesley. All rights
reserved.
17-26
Tree Properties
• Notice paths
– From top to any node
– No "cycles" – follow pointers, will reach "end"
• Notice here each node has two links
– Called binary tree
– Most common type of tree
• Root node
– Similar to linked list’s head
• Leaf nodes
– Both link variables are NULL (no subtrees)
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-27
Trees and Recursion
• Note tree’s "recursive structure"
• Each tree has two subtrees
– Each subtree has two subtrees
• Etc., etc.
• Makes trees amenable to recursive
algorithms
– For searching especially!
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-28
Tree Processing
•
Preorder Processing:
1. Process data in root node
2. Process left subtree
3. Process right subtree
•
In-order Processing:
1. Process left subtree
2. Process data in root
3. Process right subtree
•
Postorder Processing:
1. Process left subtree
2. Process right subtree
3. Process data in root
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-29
Tree Storage
•
Our example stored values in special way:
– Called binary search tree storage rule:
1. values in left subtree less than root value
2. values in right subtree greater than root
3. rule applies recursively to each subtree
•
Trees using this storage mechanism:
– Called binary search tree (BST)
– Traversals:
Inorder
 values "in order"
Preorder
 "prefix" notation
Postorder
 "postfix" notation
Copyright © 2010 Pearson Addison-Wesley. All rights reserved.
17-30
31
17.7 Trees
• Binary search tree
– Values in left subtree less than parent node
– Values in right subtree greater than parent
• Does not allow duplicate values (good way to remove them)
– Fast searches, log2n comparisons for a balanced tree
47
25
77
11
7
17
43
31 44
 2003 Prentice Hall, Inc. All rights reserved.
65
68
93
32
17.7 Trees
• Inserting nodes
–
–
–
–
Use recursive function
Begin at root
If current node empty, insert new node here (base case)
Otherwise,
• If value > node, insert into right subtree
• If value < node, insert into left subtree
• If neither > nor <, must be =
– Ignore duplicate
 2003 Prentice Hall, Inc. All rights reserved.
33
17.7 Trees
• Upcoming program
– Create 2 template classes
– TreeNode
• data
• leftPtr
• rightPtr
– Tree
• rootPtr
• Functions
– InsertNode
– inOrderTraversal
– preOrderTraversal
– postOrderTraversal
 2003 Prentice Hall, Inc. All rights reserved.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
34
// Fig. 17.17: treenode.h
// Template TreeNode class definition.
#ifndef TREENODE_H
#define TREENODE_H
Outline
treenode.h (1 of 2)
// forward declaration of class Tree
template< class NODETYPE > class Tree;
template< class NODETYPE >
class TreeNode {
friend class Tree< NODETYPE >;
public:
// constructor
TreeNode( const NODETYPE &d )
: leftPtr( 0 ),
data( d ),
rightPtr( 0 )
{
// empty body
Binary trees have two
pointers.
} // end TreeNode constructor
 2003 Prentice Hall, Inc.
All rights reserved.
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// return copy of node's data
NODETYPE getData() const
{
return data;
35
Outline
treenode.h (2 of 2)
} // end getData function
private:
TreeNode< NODETYPE > *leftPtr; // pointer to left subtree
NODETYPE data;
TreeNode< NODETYPE > *rightPtr; // pointer to right subtree
}; // end class TreeNode
#endif
 2003 Prentice Hall, Inc.
All rights reserved.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Fig. 17.18: tree.h
// Template Tree class definition.
#ifndef TREE_H
#define TREE_H
36
Outline
tree.h (1 of 6)
#include <iostream>
using std::endl;
#include <new>
#include "treenode.h"
template< class NODETYPE >
class Tree {
public:
Tree();
void insertNode( const NODETYPE & );
void preOrderTraversal() const;
void inOrderTraversal() const;
void postOrderTraversal() const;
private:
TreeNode< NODETYPE > *rootPtr;
 2003 Prentice Hall, Inc.
All rights reserved.
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// utility functions
void insertNodeHelper(
TreeNode< NODETYPE > **, const NODETYPE & );
void preOrderHelper( TreeNode< NODETYPE > * ) const;
void inOrderHelper( TreeNode< NODETYPE > * ) const;
void postOrderHelper( TreeNode< NODETYPE > * ) const;
37
Outline
tree.h (2 of 6)
}; // end class Tree
// constructor
template< class NODETYPE >
Tree< NODETYPE >::Tree()
{
rootPtr = 0;
} // end Tree constructor
// insert node in Tree
template< class NODETYPE >
void Tree< NODETYPE >::insertNode( const NODETYPE &value )
{
insertNodeHelper( &rootPtr, value );
} // end function insertNode
 2003 Prentice Hall, Inc.
All rights reserved.
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
// utility function called by insertNode; receives a pointer
// to a pointer so that the function can modify pointer's value
template< class NODETYPE >
void Tree< NODETYPE >::insertNodeHelper(
TreeNode< NODETYPE > **ptr, const NODETYPE &value )
{
// subtree is empty; create new TreeNode containing value
if ( *ptr == 0 )
*ptr = new TreeNode< NODETYPE >( value );
else
// subtree is not empty
// data to insert is less than data in current node
if ( value < ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->leftPtr ), value );
else
// data to insert is greater than data in current node
if ( value > ( *ptr )->data )
insertNodeHelper( &( ( *ptr )->rightPtr ), value );
38
Outline
tree.h (3 of 6)
Recursive function to insert a
new node. If the current node
is empty, insert the new node
here.
If new value greater than
current node (ptr), insert
into right subtree.
If less, insert into left subtree.
If neither case applies, node is
a duplicate -- ignore.
else // duplicate data value ignored
cout << value << " dup" << endl;
} // end function insertNodeHelper
 2003 Prentice Hall, Inc.
All rights reserved.
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
39
Outline
// begin preorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::preOrderTraversal() const
{
preOrderHelper( rootPtr );
tree.h (4 of 6)
} // end function preOrderTraversal
// utility function to perform preorder
template< class NODETYPE >
void Tree< NODETYPE >::preOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
cout << ptr->data << ' ';
preOrderHelper( ptr->leftPtr );
preOrderHelper( ptr->rightPtr );
traversal of Tree
Preorder: print, left, right
// process node
// go to left subtree
// go to right subtree
} // end if
} // end function preOrderHelper
 2003 Prentice Hall, Inc.
All rights reserved.
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
40
// begin inorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::inOrderTraversal() const
{
inOrderHelper( rootPtr );
Outline
tree.h (5 of 6)
} // end function inOrderTraversal
// utility function to perform inorder
template< class NODETYPE >
void Tree< NODETYPE >::inOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
inOrderHelper( ptr->leftPtr );
cout << ptr->data << ' ';
inOrderHelper( ptr->rightPtr );
traversal of Tree
In order: left, print, right
// go to left subtree
// process node
// go to right subtree
} // end if
} // end function inOrderHelper
 2003 Prentice Hall, Inc.
All rights reserved.
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
41
// begin postorder traversal of Tree
template< class NODETYPE >
void Tree< NODETYPE >::postOrderTraversal() const
{
postOrderHelper( rootPtr );
Outline
tree.h (6 of 6)
} // end function postOrderTraversal
// utility function to perform postorder
template< class NODETYPE >
void Tree< NODETYPE >::postOrderHelper(
TreeNode< NODETYPE > *ptr ) const
{
if ( ptr != 0 ) {
postOrderHelper( ptr->leftPtr );
postOrderHelper( ptr->rightPtr );
cout << ptr->data << ' ';
traversal of Tree
Postorder: left, right, print
// go to left subtree
// go to right subtree
// process node
} // end if
} // end function postOrderHelper
#endif
 2003 Prentice Hall, Inc.
All rights reserved.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// Fig. 17.19: fig17_19.cpp
// Tree class test program.
#include <iostream>
42
Outline
fig17_19.cpp
(1 of 3)
using std::cout;
using std::cin;
using std::fixed;
#include <iomanip>
using std::setprecision;
#include "tree.h"
// Tree class definition
int main()
{
Tree< int > intTree;
int intValue;
// create Tree of int values
cout << "Enter 10 integer values:\n";
for( int i = 0; i < 10; i++ ) {
cin >> intValue;
intTree.insertNode( intValue );
} // end for
 2003 Prentice Hall, Inc.
All rights reserved.
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
43
cout << "\nPreorder traversal\n";
intTree.preOrderTraversal();
cout << "\nInorder traversal\n";
intTree.inOrderTraversal();
Outline
fig17_19.cpp
(2 of 3)
cout << "\nPostorder traversal\n";
intTree.postOrderTraversal();
Tree< double > doubleTree;
double doubleValue;
// create Tree of double values
cout << fixed << setprecision( 1 )
<< "\n\n\nEnter 10 double values:\n";
for ( int j = 0; j < 10; j++ ) {
cin >> doubleValue;
doubleTree.insertNode( doubleValue );
} // end for
cout << "\nPreorder traversal\n";
doubleTree.preOrderTraversal();
 2003 Prentice Hall, Inc.
All rights reserved.
51
52
53
54
55
56
57
58
59
60
61
cout << "\nInorder traversal\n";
doubleTree.inOrderTraversal();
cout << "\nPostorder traversal\n";
doubleTree.postOrderTraversal();
44
Outline
fig17_19.cpp
(3 of 3)
cout << endl;
return 0;
} // end main
 2003 Prentice Hall, Inc.
All rights reserved.
Enter 10 integer values:
50 25 75 12 33 67 88 6 13 68
Preorder traversal
50 25 12 6 13 33 75 67 68 88
Inorder traversal
6 12 13 25 33 50 67 68 75 88
Postorder traversal
6 13 12 33 25 68 67 88 75 50
45
Outline
fig17_19.cpp
output (1 of 1)
Enter 10 double values:
39.2 16.5 82.7 3.3 65.2 90.8 1.1 4.4 89.5 92.5
Preorder traversal
39.2 16.5 3.3 1.1 4.4 82.7 65.2 90.8 89.5 92.5
Inorder traversal
1.1 3.3 4.4 16.5 39.2 65.2 82.7 89.5 90.8 92.5
Postorder traversal
1.1 4.4 3.3 16.5 65.2 89.5 92.5 90.8 82.7 39.2
 2003 Prentice Hall, Inc.
All rights reserved.