Transcript List

Chapter 8
Data Abstractions
Chapter 8: Data Abstractions






8.1
8.2
8.3
8.4
8.5
8.6
Data Structure Fundamentals
Implementing Data Structures
A Short Case Study
Customized Data Types
Classes and Objects
Pointers in Machine Language
2
Basic Data Structures



Homogeneous array
Heterogeneous array
List



Stack
Queue
Tree
3
Figure 8.1 Lists, stacks, and
queues
4
Terminology for lists



List = collection of data whose entries
are arranged sequentially
Head = beginning of the list
Tail = end of the list
5
Terminology for stacks






Stack = a list in which entries are
removed and inserted only at the head
LIFO = last-in-first-out
Top = head of list
Bottom or base = tail of list
Pop = remove entry from the top
Push = insert entry at the top
6
Terminology for queues


Queue = a list in which entries are
removed at the head and are inserted
at the tail
FIFO = first-in-first-out
7
Terminology for a tree




Tree = a collection of data whose
entries have a hierarchical organization
Node = an entry in a tree
Binary tree = tree in which every
node has at most two children
Depth = number of nodes in longest
path from root to leaf
8
Terminology for a tree (continued)







Root node = the node at the top
Terminal or leaf node = a node at the
bottom
Parent of a node = the node immediately
above the specified node
Child of a node = a node immediately below
the specified node
Ancestor = parent, parent of parent, etc.
Descendent = child, child of child, etc.
Siblings = nodes sharing a common parent
9
Figure 8.1 An example of an organization
chart
10
Figure 8.2 Tree terminology
11
Basic data structures

Homogeneous array



is an array of entries of the same type.
List The unique feature of arrays is that their
size and shape are constant.
For the group with dynamic population
(members join/leave), lists structure employs
the concept of a pointer to accommodate
such variations on membership.
12
Nature of data structures






Static: size of data structure does not change
Dynamic: size of data structure can change
Pointer:Main memory location of an data item A is
identified by its numeric address, which value can be
saved in another memory location P.
Such P is called a pointer to the data item A.
The program counter is indeed the instruction
pointer.
URLs(Uniform resource Locator) used to link
hypertext contents are also like the pointers.
13
Figure 8.3 Novels arranged by title but linked
according to authorship
14
1.Give examples of each of the following structures
in daily life:
List
Stack
Queue
Tree
2.Suppose a tree has four nodes A,B,C,and D. If A and C
are siblings and D’s parent is A, which nodes are leaf
Nodes? Which is root node?
15
Storing homogeneous arrays



Requires enough contiguous memory to hold
all data
Int readings [24]; reading[4] <- 67;
Two dimensional arrays

Row-major order: each row is stored together


Address polynomial: A[r,c] = (r-1)(# columns) + (c-1)
Column-major order: each column is stored
together
16
Figure 8.4 The array of temperature readings
stored in memory starting at address x
17
Figure 8.5 A two-dimensional array with four rows
and five columns stored in row major order
18
Figure 8.7 Storing the
heterogeneous array Employee
19
Storing lists


Contiguous list = list stored in a
homogeneous array
Linked list = list in which each node
points to the next one


Head pointer = pointer to first entry in
list
NIL pointer = non-pointer value used to
indicate end of list
20
Figure 8.6 Names stored in memory as a
contiguous list
21
Figure 8.7 The structure of a linked list
22
Figure 8.8 Deleting an entry from a linked list
23
Figure 8.9 Inserting an entry into a linked list
24
Storing stacks and queues


Can use same mechanisms as for lists
Circular queue = homogeneous array
where the first array entry is treated as
immediately following the last array
entry

Prevents a queue from crawling out of its
allotted storage space
25
Figure 8.10 A stack in memory
26
Figure 8.11 A queue implementation with head and tail
pointers. Note how the queue crawls through memory as
entries are inserted and removed.
27
Problems with Pointers
Pointers in Queue may grow out of the
region of the specified memory region
In Java to advance pointer
redirect Next to the next list entry
In C
Assign Next the value Next +1
What is the problem in C?
28
Storing a binary tree

Linked structure



Each node = data cell + two child pointers
Accessed through a pointer to root node
Mapped to a contiguous array




A[1] = root node
A[2],A[3] = children of A[1]
A[4],A[5],A[6],A[7] = children of A[2] and A[3]
…
29
Figure 8.12 The structure of a node in a
binary tree
30
Figure 8.13 The conceptual and actual organization of
a binary tree using a linked storage system
31
Figure 8.14 A tree stored without pointers
32
Figure 8.15 A sparse, unbalanced tree shown in its
conceptual form and as it would be stored without
pointers
33
Manipulating data structures

Ideally, a data structure should be
manipulated solely by pre-defined
procedures.


Example: A stack typically needs at least
push and pop procedures.
The data structure along with these
procedures constitutes a complete abstract
tool.
34
Figure 8.16 A procedure for printing a linked
list
35
What condition indicates a linked list is empty?
What about Stack and Queue?
36
A Case Study
Store the letters in a binary tree
1. The middle of the entry the root node
2. The middle of the remaining first half of the list
the root’s left child
3. The middle of the remaining second half of the list
the root’s right child
A,B,C,D,E,F,G,H,I,J,K,L,M
Then 3 operations to be performed
Search for the presence of an entry
Print the list in alphabetical order
Insert a new entry
37
Figure 8.17 The letters A
through M arranged in an
ordered tree
38
Figure 8.18 The binary search as
it would appear if the list were implemented as a linked binary tree
39
Figure 8.19 The successively smaller trees considered by the procedure
in Figure 8.18 when searching for the letter J
40
Figure 8.20 Printing a search tree in
alphabetical order
41
Figure 8.21 A procedure for printing the data in a
binary tree
42
Figure 8.22 Inserting the entry
M into the list B, E, G, H, J, K, N, P stored as a tree
43
Figure 8.23 A procedure for inserting a new entry in a
list stored as a binary tree
44
Non-recursive way for serach
procedure BinarySearch (Tree, TargetValue)
CurrentPointer ¬ root pointer of Tree;
*The node pointed to by CurrentPointer
will be called the current node*
Found ¬ false;
while (Found is false and CurrentPointer
is not NIL) do
(Perform the activity associated with the
appropriate
case below:
45
Non-recursive way for serach
case 1, TargetValue = current node:
(Found ¬ true)
case 2, TargetValue < current node:
(CurrentPointer ¬ current node's left
child pointer)
case 3, TargetValue > current node:
(CurrentPointer ¬ current node's right
child pointer)
)
if (Found = false) then (declare the
search a failure)
else (declare the search a success)
46
Customized data types

User-defined data type = template for a
heterogeneous structure
define type EmployeeType to be
{ char Name[8];
Int Age ;
real SkillRating;
}
EmployeeType DistManager;
DistManager.name=John;
DistManager.age=30;
47
Customized data types

Abstract data type = user-defined data
type with methods for access and
manipulation
define type StackType to be
{int StackEntries[20];
int StackPointer = 0;
Procedure push(value)
{StackEnties[StackPointer]=value;
Stackpointer++;}
Procedure pop…..
}
StackType Stackone; Stackone.push(25);
48
Customized data types





What should be considered when building an abstract
data type for a list.
1 insert, delete, find the entry
2. Ways of implementing a list—
Contiguous or linked list
3. The choice of either way is invisible to users
49
Customized data types

Class and Objects
Class = abstract data type with extra
features



Characteristics can be inherited
Contents can be encapsulated
Constructor methods to initialize new
objects
50
Figure 8.24 A stack of integers implemented
in Java and C#
51
Pointers in machine language



Immediate addressing: instruction
contains the data to be accessed
Direct addressing: instruction
contains the address of the data to be
accessed
Indirect addressing: instruction
contains the location of the address of
the data to be accessed
52
Figure 8.25 Our first attempt at expanding the machine language
in Appendix C to take advantage of pointers
DRXY—load register R with contents of the memory cells
whose address is found at address XY
Need to change Stack pointer(load to register,-1,then53load)
Figure 8.26 Loading a register from a memory cell that is located
by means of a pointer stored in a register
DR0S—load register R with the contents of the memory cells
Pointed by register S
54
Figure 8.26 Loading a register from a memory cell that is located
by means of a pointer stored in a register
DR0S—load register R with the contents of the memory cells
Pointed by register S
Write a complete machine language routine to perform a
Pop operation.
Assume stack pointer is in register F
And Top of the stack is to be pooped into register 5.
55
Push operation
ER0S—store the contents of register R in the memory cells
Pointed by register S
DRXS:load register R with the data pointed by the value in
register S plus the value X
EX: If register F contained 0x04, then DE2F will
Load register E with the content of the memory cell at
address ?. The value of register F remains ?
What advantage of this instruction has when used in linked
list data structure?
Each entry has two memory cells(data+pointer)
DR0S can be used to retrieve the data
56
DR1S can be used to retrieve the pointer