Transcript Data Structures

Data Types
•
Every data type has two characteristics:
1. Domain - set of all possible values
2. set of allowable operations
•
•
Built-in
ADT - Abstract Data Type
cosc237/data structures
1
Data Types
• Simple data type, atomic data type
– cannot be broken down
– int, float, char
• structured data type
– components can be atomic or structured
– rules that define how the components relate to
each other
– Arrays, structs
cosc237/data structures
2
C++ Array
Domain:Each C++ array consists of
1. A collection of a fixed number of component
values each of the same type
2. A set of index values that are nonnegative integers
Structure: There is a one-to-one relationship between
each index and an array element
Operations:
• Retrieve the value of the array eleemnt asociated
with index I
• Store a value into the array element associated
with index i
cosc237/data structures
3
Data Structures
• Linear (ordered)
– Direct Access
• Homogeneous components – Array
• Heterogeneous components – Record
– Sequential Access
• General – List
• Last-in, first-out – Stack
• First-in, first-out – Queue
• Nonlinear (unordered) - Set
cosc237/data structures
4
Array
• Components
– array elements
• Access individual elements by
– index or subscript
• Direct access to a component through index
• Homogeneous components
cosc237/data structures
5
Array as ADT
Domain:Each array consists of
1. A collection of a fixed number of component
values each of the same type
2. A set of index values that are nonnegative integers
Structure: linear, direct access structure with one-toone relationship between each index and an array
element
Operations:
• ValueAt(i) – retrieve value of array element
associated with index i
• Store(i,v) - Store value v into the array element
associated with index i
cosc237/data structures
6
Record
• Components
– fields
• Access individual elements by
– field name or field identifier
• Direct access to a component via field name
• Heterogeneous components
cosc237/data structures
7
Record as ADT
Domain:Each record consists of
1. A collection of a fixed number of component
values which may be of different types
2. A set of identifiers (field names) for selecting each
component
Structure: linear, direct access structure with one-toone relationship between each field name and a
field of the record
Operations:
• ValueAt(fname) – retrieve value of field whose
name is fname
• Store(i,v) - Store value v into the field whose
name is fname
cosc237/data structures
8
List
• Components
– list items or list elements
• Access individual elements
– Sequentially
•
•
•
•
Head or front – first item in the list
Tail, back, end – last item in the list
Varying length
sequential access to a component through implicit
list cursor
• Homogeneous components
cosc237/data structures
9
List as ADT
Domain:Each list consists of
1. A collection of component values each of
the same type
2. An implicit list cursor in the range 1
through n + 1, where n is the length of the
list
Structure: linear, sequential access structure
of varying length
cosc237/data structures
10
List cont'd
Operations:
• Create(); // empty list created
• Boolean IsEmpty();
• Boolean IsFull();
• void Reset(); // cursor set to front of list
• Boolean EndOfList();
• void Advance(); // advance cursor to next item
• ItemType CurrentItem(); //return item at list cursor
• void InsertBefore();
• void InsertAfter();
• void Delete();// delete item at list cursor
cosc237/data structures
11
Lists vs Arrays
• Advantages of lists
– easier to perform insertions & deletions
• Disadvantage of lists
– No direct access
cosc237/data structures
12
Stacks
• Restricted list where insertions or deletions
occur at one end
• LIFO – Last-In, First-Out
• Top – end where insertions or deletion take
place
• Push, Pop, Top
• Run-time stack
cosc237/data structures
13
Stack as ADT
Domain:Each stack is a collection of
component values each of the same type
Structure: list maintained in LIFO order so
only most recently inserted item is
accessible
cosc237/data structures
14
Stack cont'd
Operations:
• Create(); // empty stack created
• Boolean IsEmpty();
• Boolean IsFull();
• void Push(/* in */ ItemType newItem); //
newItem is at top of stack
• ItemType Top(); //return item at top of stack
• void Pop(); // Top item removed from stack
cosc237/data structures
15
Queues
• Restricted list
– Insertions occur at the tail of the list - tail
– deletions occur at the head - front
•
•
•
•
•
•
FIFO – First-In, First-Out
Enqueue – appends item to rear of queue
Dequeue – removes item from front of queue
Front – inspects first item
Top – end where insertions or deletion take place
Buffered input, printer queue
cosc237/data structures
16
Queue as ADT
Domain:Each queue is a collection of
component values each of the same type
Structure: list maintained in FIFO order so
insertions take place at the rear and
deletions take place at the front
cosc237/data structures
17
Queue cont'd
Operations:
• Create(); // empty queue created
• Boolean IsEmpty();
• Boolean IsFull();
• void Enqueue(/* in */ ItemType newItem); //
newItem is at rear of queue
• ItemType Front(); //return item at front of queue
• void Dequeue(); // front item removed from queue
cosc237/data structures
18