Transcript Software Engineering Syllabus

Chapter 8
Data Abstractions
Introduction to CS
1st Semester, 2014 Sanghyun Park
Outline






Data Structure Basics
Arrays
Lists
Stacks
Queues
Trees
Data Structure Basics

The topic of data structures explores ways in which users
can be ________ from the details of actual data storage
(__________)

The shape or size of data structures may or may not
change over time (dynamic vs. static structures);
____ structures are easier to manage than dynamic ones

A ______ is a memory cell that contains the address of
another memory cell; the value in the pointer tells us
where to find the data
Single Dimensional Arrays

If the first reading is at address x,
the ith reading is located at address ________
Two Dimensional Arrays
x


Row major order vs. column major order
If we let c represent the number of columns in an array,
then the address of the entry in the ith row and jth column
will be ________________
Contiguous Lists




List is a collection of entries that appear in a _____ order
Lists appear in both static and dynamic forms
Let us consider techniques for storing a list of names
in a machine’s main memory
The simplest structure is a ___________ list
Linked Lists


A contiguous list suffers disadvantages
when implementing ________ lists
The problem encountered can be simplified
if we use _______ lists
Deleting an Entry From Linked List
Inserting an Entry Into Linked List
Supporting The Conceptual List

To support the ________ to the list structure,
the programmer should write a collection of __________
for performing such activities as inserting a new entry and
searching for an entry

The users do not concern whether the list structure is
implemented as a contiguous structure or a linked one;
the users only call the procedure like PrintList(CSI2106)
Stacks

A _____ is a list in which all insertions and deletions are
performed at the _____ end of the structure

The last entry entered will always be the first entry
removed – last-in, first-out (______) structure

The end of a stack at which entries are inserted and
deleted are called the ____ of the stack

The process of inserting an entry on the stack is called a
____ operation, and the process of deleting an entry is
called a ____ operation
Backtracking


A classic application of a stack occurs when a program
unit requests the execution of a ________
As each procedure is called, a ______ to the return
location is pushed on a stack; as each procedure is
completed, the top entry from the stack is extracted
Printing a Linked List
in Reverse Order (1/3)
Printing a Linked List
in Reverse Order (2/3)
Printing a Linked List
in Reverse Order (3/3)
Stack Implementation


Push operation needs a test if stack is ____
Pop operation needs a test if stack is _____
Queues

A _____ is a list in which all insertions are performed at
____ end while all deletions are made at the ____ end

The concept of a queue is inherent in any system in
which objects are served in the same order in which
they arrive - first-in, first-out (_____) structure

The end at which entries are removed is called the ____

The end at which new entries are added is called the ___
Queue Implementation
Queue “Crawling” Through Memory
Circular Queue
An Example of an Organization Chart
Representation of a Tree
Tree Terminology
Binary Trees

Binary trees are trees in which each node has at most
___ children

Such trees normally are stored in memory using a
______ structure similar to that of linked lists
Examples of Binary Trees
A Binary Tree Using
a Linked Storage System
A Binary Tree Stored Without Pointers
A Sparse Binary Tree
Stored Without Pointers
Binary Search Using Binary Trees
Binary Search Example
Depth-First Traversal
Preorder Traversal
Inorder Traversal
Postorder Traversal
Breadth-First Traversal