Transcript Abstract Data Types

ECE 103 Engineering Programming
Chapter 61
Abstract Data Types
Herbert G. Mayer, PSU CS
Status 6/4/2014
Initial content copied verbatim from
ECE 103 material developed by
Professor Phillip Wong @ PSU ECE
Syllabus






Introduction
Linear List
Stack
Queue
Tree
Implementation
Abstract Data Structures

A data structure is a method or mechanism for
representing and storing data in a computer.

Data structure design depends on:




the type of data being stored
how the data is organized
how the data should be accessed
Many commonly used data structures are examples
of graphs.
2

Graph → abstract data structure in which a set of
nodes (or vertices) are connected together by a set
of links (or edges)

Link connections represent node relationships.

A node contains:


Data
Link(s)
(i.e., which other nodes it is connected to)
3

Examples of different graph sub-classes:
General Graph
General Tree
Any node may
connect to any
other node and
cycles are allowed
A graph in which
no cycles are
allowed

Hierarchical Tree
(Binary version)
Each node descends
from one parent node
and has zero or more
child nodes
Ring
Linear List
A list that
forms a
closed
loop
A sequential
set of nodes
Abstract data structures are used to model:



Computer and communication networks (graphs)
Binary search and heaps (trees)
Stacks and queues (lists)
4
Operations on Abstract Data Structures

Typical types of operations performed on an abstract
data structure include:






Create node
Insert node
Remove node
Traverse nodes
Search nodes
Check if node is empty
5
Linear List
Insert and remove operations can occur anywhere
within the list.
list
A
list
A
list
A
list
A
B
B
B
B
C
C
D
D
D
C
C
C
list
A
D
Linear List
“insert” operation
“remove” operation
6
Stack – Last In, First Out (LIFO)
Insert (“push”) and remove (“pop”) operations can only
occur at the top of the stack.
D
top
top
A
D
top
D
A
A
A
B
B
B
B
B
C
C
C
C
C
Stack
top
“push” operation
top
A
“pop” operation
7
Queue – First In, First Out (FIFO)
Insert (“enqueue”) operations occur at the tail, while
remove (“dequeue”) operations occur at the head.
head
A
head
B
tail
C
tail
A
head
A
head
A
B
B
B
C
C
C
tail
D
tail
D
head
B
C
tail
D
D
Queue
“enqueue” operation
“dequeue” operation
8
Graphs and Trees
Insert and remove
operations are more
complicated, especially
if a balanced structure
is required.
9
Implementation of Abstract Data Structures

The C language’s struct type is used to represent
a node.

The structure’s member variables contain:
 Data
 Link information
10

Ways to implement abstract data structures:

Array of nodes




The maximum number of nodes is fixed at compile-time
(though run-time allocation can get around this).
Any node can be directly accessed via the array index.
Link information is the array index of another node.
Nodes connected by pointers



The maximum number of nodes is determined at runtime
(can grow or shrink).
Nodes must be accessed sequentially via pointer links.
Link information is a pointer to another node.
11

Conceptual implementations of data structures:
NULL
0
data
next: 1
1
data
next: 3
3
data
p
data
next
next prev
data
data
next
next prev
data
p
left right
data
next: 2
2
p
data
data
data
next
next prev
data
data
next
next prev
next: -1
NULL
Singly-linked List
(array)
Singly-linked List
(pointer)
data
data
left right
left right
NULL NULL
NULL
data
left
right
NULL NULL
NULL
Doubly-linked List
(pointer)
Binary Tree
(pointer)
12