Transcript Data Structures

Data Structures
Chapter 15
1
2
What You Will Learn
Lists
Stacks
Queues
Trees
3
Introduction
Previously used fixed sized data structures
arrays
structs
Now we will use dynamic data structures
they will grow and shrink during execution
Examples
stacks
queues
binary trees
4
Self-Referential Classes
A self-referential class contains a pointer
member that points to a class object of the
same class type
class Part_node {
public:
Part_node ( );
…
private:
char part_num[8], descrip[20];
int qty; float price;
Part_node *next_part; } ;
5
Self-Referential Classes
This pointer to an object of the type being
declared enables class objects to be linked
together in various ways
This is how we get linked lists, stacks, queues
0
Pointer
variable
Pointer
Member
Link
Null
Pointer
6
Dynamic Memory Allocation
If the data structures are to be dynamic, then
dynamic memory allocation is required
operators new and delete are essential
part_node *newPtr = new part_node;
0
Creates the
new pointer Allocates the space for
a new part node
7
Dynamic Memory Allocation
The delete operator deallocates memory
allocated with the new
Note: newPtr is not itself deleted -- rather the
space newPtr points to
delete newPtr;
0
8
Linked Lists
Definition <=> A list of self-referential class
objects
called nodes
connected by pointer links (thus, a "linked" list)
Subsequent nodes accessed via link-pointer
member stored in each member
Link pointer in last node set to null (zero)
marks the end of the list
Nodes created dynamically, as needed
9
Lists and Linked Lists
Criteria for choosing linked list
must be linear, homogeneous data
rules out sets & records
ordering does not depend on time of insertion
rules out FIFO, LIFO
sequential access is sufficient
rules out need for array
frequent insert, delete and requirement for sorting
10
Linked List
Collection of structs (called nodes)
One member is the data member
At least one other member of the struct gives
location of next member
This makes it self referential
head
4
7
-3
/
11
Linked List
Nodes do not necessarily occupy consecutive
memory locations
Two ways to implement
Dynamic data with pointers (this is what our text
is advocating)
Also possible to use built in arrays
12
Linked List
Abstractions that are implemented using
built-in types
Implementation Hierarchy for a list ADT
List
Built-in Array
Linked List
Built-in Dynamic
data and pointers
Built-in Array
13
Declaration for a Linked List
// Declaration
struct NodeType;
typedef Nodetype* NodePtr;
struct NodeType{
SomeDataType data;
NodePtr
link; };
NodePtr head;
NodePtr visitPtr;
Forward
(incomplete)
declaration
Complete
declaration
Dynamic Allocation of List
Nodes
// Allocate a new dynamic object
head = new NodeType;
(*head).data = 345;
Newly allocated object is a struct with 2
members
345
head
data
link
14
15
Dynamic Allocation
(*head).data
 (*head) is pointer dereferencing
 .data is struct selection
Equivalent (and easier to use)
 head ->data
Thus we could have said
head->data =345;
16
Linking Nodes Together
345
head
Head->link refers to …
data Thus
head->link = new NodeType
link will allocate a second
NodeType struct, pointed to by
the link element of the first
Then think what happens ...
head->link->data = 12;
head->link->link = NULL;
Characteristics of Singly Linked
Lists
17
In previous slide, head is a pointer only, not a
node on the list
*head is the struct pointed to by the head
head->link or (*head).link is the address of the
second struct
*(head->link) or *((*head).link) is the entire
second struct
head->link->data is the data member of the
second struct
18
Constructing a List
Algorithm
head = new NodeType;
currentPtr = head;
do {
currentPtr->link = NULL;
// do something with currentPtr->data
if (! done) {
currentPtr->link = new NodeType;
currentPtr =currentPtr->link; }
} while (! done);
19
Constructing List (version 2)
ReadCities (/*out*/ CityPtr& cityList)
{
CityPtr inNode;
CityName tempName;
cityList = Null;
while (cin >> tempName) {
inNode = new CityNode;
strcpy (inNode->name, tempName);
cin >> inNode->population;
cin >> inNode->numVoters;
inNode->next = cityList;
cityList = inNode;
}
}
20
Constructing a List (Version 2)
inNode
Longview
75
50
NULL
cityList
21
Constructing a List (Version 2)
inNode
Longview
Tyler
75
80
50
60
NULL
cityList
22
Constructing a List (Version 2)
inNode
Longview
Tyler
Dallas
75
80
1000
50
60
500
NULL
cityList
23
Constructing a List (Version 2)
inNode
Longview
Tyler
Dallas
Hallsville
75
80
1000
2
50
60
500
1
NULL
cityList
(Remember this is a
reference parameter)
24
Traversing a List
General algorithm
visitPtr = head;
while (visitPtr != NULL) {
// do something with the visitPtr -> data
visitPtr = visitPtr -> link;
}
25
Recursive List Traversal
Recursive routine
void visit_list ( /* in */ visit_ptr NodePtr)
{ if (visit_ptr != NULL)
Recursive
Call
{ visit_list (visit_ptr->link);
cout << visit_ptr -> data; }
}
Note that data is printed in reverse order of
original input
26
Linked Lists
Manipulate pointers to insert links into the list
(here at the beginning of the list)
First store address of block with 7 in new
block
Then change contents of firstPtr to point to
the block with the 12
27
Insertions
Assume we wish to insert a node with address
insPtr between two other nodes already linked
(the virst at prevPtr)
insPtr-> link = prevPtr-> link;
prev_ptr->link = insPtr;
prevPtr
insPtr
28
Linked Lists - Removing Nodes
Create tempPtr pointing to 1st node
Change where firstPtr points to (2nd node in
list)
Delete node pointed to by tempPtr
Before
After
29
Deletions
Assume delete node after link pointed to by
prevPtr
tempPtr = prevPtr->link;
prevPtr->link = tempPtr->link;
delete tempPtr; // deallocates memory
prevPtr
tempPtr
30
Linked Lists
Node can contain data of any type
Consider nodes with base class pointers
can have a linked list of derived objects
use virtual function calls to process different
objects polymorphically
Other related structures
stacks, queues are constrained versions of linked
lists (they are linear)
trees are non linear data structures
31
Linked Lists
Advantages of linked lists (over arrays)
when number of data elements in a list is
unpredictable
size of conventional array in C++ is fixed
Can be maintained n sorted order by inserting
new elements at proper point in list
simply a matter of adjusting pointers
Need not be contiguously stored in memory
are only contiguous logically
Note figure 15.3, pg 746 -- text CD audio
Disadvantages of Dynamic
Linked List
Algorithms sometimes more complex,
harder to read
harder to debug
Pointer space must be considered overhead
especially expensive when data portion of node is
small
Allocation, deallocation requires run-time
overhead
32
33
Head Nodes
First node is a special case
pointed to by head pointer
not pointed to by another node
requires special case algorithm
Can be solved by having a special “head
node”
pointed to by head pointer
has null data
next node has actual data
34
Doubly Linked Lists
Minimize need for list traversals
Has two link members
one to next node
another to previous node
Wherever you are in the list, you can go
either forward or backward to find the desired
node
instead of always traversing from head for each
search
35
Circular Linked Lists
Nodes identical to singly linked list
Pointer of last node always points to first
node
(as does the head pointer)
head
4
7
-3
36
Circular Linked List
Useful when no particular first or last item
Head pointer could point at any node
Logically the list is still the same
Special case processing when circular linked
list is empty
solved by having a special “head node”
37
Stacks
Constrained version of a linked list
New nodes can be added to or removed from
the list only at the top (front) of the list
Referred to as last in, first out structure
LIFO
Add
4
7
3
Remove
38
Stacks
The functions which accomplish addition to
and removal from are referred to as
push
pop
s.Push (4)
4
7
3
Stack s
cout << s.Pop()
4
39
Stacks -- Applications
Programming language keeps a stack of
functions called
functions call other functions, etc.
Stacks contain space created for automatic
variables on each function invocation
Used by compilers in processing evaluations
of expressions
See the Stack
Note : we can use a LinkedExample
list classFig
to 15.9
on CD Rom
implement a Stack class
40
Queues
Another constricted linked list -- the list can
be added to only at the end and deleted from
only at the beginning
First In - First Out … FIFO
The insert (or add) is known as the enqueue
function
The remove (or delete) is known as the
dequeue
41
Queues -- Applications
For keeping track of multiple users on a
single computer
To support printing -- many print jobs, one
printer
Handling information packets in networks
File server in a computer network
Note example in Figure 15.12, pg 763
Listen to text CD audio
42
Trees
Nonlinear, two dimensional data
structure
contrast to lists, stacks, queues
Every node contains two (or
multiple) links
Each link in root node refers to a
child (there will be a right and left
child)
43
Trees
Note the double pointers in each node
End nodes called leaf nodes
First node called root node
44
Trees
Binary search tree
no duplicated node values
values in any left sub tree are less than value in
parent node
values in any right sub tree are greater than value
in parent node
Note Fig 15.16
hear text CD audio