TREE

CSE 326: Data Structures
Lecture #0
Introduction
Bart Niswonger
Summer Quarter 2001
Come up and say hello!
Today’s Outline
• Administrative Cruft
• Overview of the Course
• Queues
• Stacks
• Project #1
Course Information
• Instructor: Bart Niswonger
226D Sieg Hall
bart@cs.washington.edu
Office hours: M 11:50-12:50, W 1:50-2:50 &
whenever door is open
• TA:
Ashish Sabharwal ashish@cs
Office hours: Tues 10:50-11:50 in 226A/B
• Text: Data Structures & Algorithm Analysis in
C++, 2nd edition, by Mark Allen Weiss
Tutorials
• Unix I
– Tuesday, June 19th
– 10:50-11:50 + lab time, Sieg 322
• Templates
– Thursday, June 21st REQUIRED
– 10:50-11:50 + lab time, GUG 410
• In place of section
• Unix Development
– Tuesday, June 26th
– 10:50-11:50 + lab time, Sieg 322
Course Policies
• Roughly weekly written homework due at the
start of class on the due date
• Projects (4 total) due by 10PM on the due
date
– you have 4 late days for projects
• Grading
– homework: 15%
– projects: 25%
– midterm: 20% PARTICIPATION!
– final: 30%
– best of these: 10%
Course Mechanics
• 326 Web page:
www/education/courses/326/01su
• 326 course directory: /cse/courses/cse326
• 326 mailing list: cse326@cs.washington.edu
– subscribe to the mailing list using majordomo, see
homepage
• Course labs are 232 and 329 Sieg Hall
– lab has NT machines w/X servers to access UNIX
• All programming projects graded on
UNIX/g++
Goals of the Course
• Become familiar with some of the fundamental
data structures in computer science
• Improve ability to solve problems abstractly
– data structures are the building blocks
• Improve ability to analyze your algorithms
– prove correctness
– gauge (and improve) time complexity
• Become modestly skilled with the UNIX
operating system and X-windows (you’ll need this in
upcoming courses)
Observation
• All programs manipulate data
– programs process, store, display, gather
– data can be information, numbers, images, sound
• Each program must decide how to store data
• Choice influences program at every level
– execution speed
– memory requirements
– maintenance (debugging, extending, etc.)
What is a Data Structure?
data structure -
What is an Abstract Data Type?
Abstract Data Type (ADT) -
1) An opportunity for an acronym
2) Mathematical description of an object

and the set of operations on the object
Data Structures : Algorithms
• Algorithm
– A high level, language independent
description of a step-by-step process for
solving a problem
• Data Structure
– A set of algorithms which implement an
ADT
Why so many data structures?
Ideal data structure: Dictionary ADT
fast, elegant, memory – list
efficient
– binary search tree
Generates tensions: – AVL tree
– time vs. space – Splay tree
– performance vs. – Red-Black tree
elegance
– generality vs. simplicity – hash table
– one operation’s
performance vs.
another’s
Code Implementation
• Theoretically
– abstract base class describes ADT
– inherited implementations implement data
structures
– can change data structures transparently (to client
code)
• Practice
– different implementations sometimes suggest
different interfaces (generality vs. simplicity)
– performance of a data structure may influence
form of client code (time vs. space, one operation
vs. another)
ADT Presentation Algorithm
• Present an ADT
• Motivate with some applications
• Repeat until browned entirely through
– develop a data structure for the ADT
– analyze its properties
• efficiency
• correctness
• limitations
• ease of programming
• Contrast data structure’s strengths and
weaknesses
– understand when to use each one
Queue ADT
• Queue operations
– create
– destroy
dequeue
– enqueue G enqueue FEDCB A
– dequeue
– is_empty
• Queue property: if x is enQed before y is
enQed, then x will be deQed before y is
deQed
FIFO: First In First Out
Applications of the Q
• Hold jobs for a printer
• Store packets on network routers
• Hold memory “freelists”
• Make waitlists fair
• Breadth first search
Circular Array Q Data Structure
0
Q size - 1
b c d e f
front back
void enqueue(Object x) { When is the Q empty?

Q[back] = x
back = (back + 1) % size Are there error situations this
}
code will not catch?
Object dequeue() {
x = Q[front] What are some limitations of
front = (front + 1) % size
this structure?
return x
}
This is pseudocode. Do not correct my semicolons.

Q Example
enqueue R
enqueue O
dequeue
enqueue T
enqueue A
enqueue T
dequeue
dequeue
enqueue E
dequeue
Linked List Q Data Structure
b c d e f
front back
void enqueue(Object x) { Object dequeue() {

if (is_empty()) assert(!is_empty)
front = back = new Node(x) return_data = front->data
else temp = front
back->next = new Node(x) front = front->next
back = back->next delete temp
} return temp->data
}
Circular Array vs. Linked List
LIFO Stack ADT
• Stack operations A E D C BA
– create
– destroy B
– push C
– pop D
– top E
– is_empty F F
• Stack property: if x is on the stack before y is
pushed, then x will be popped after y is
popped
LIFO: Last In First Out
Stacks in Practice
• Function call stack
• Removing recursion
• Balancing symbols (parentheses)
• Evaluating Reverse Polish Notation
• Depth first search
Array Stack Data Structure
0
S size - 1
f e d c b
back
void push(Object x) { Object pop() {

assert(!is_full()) back--
S[back] = x return S[back]
back++ }
}
Object top() {
bool is_full() {
assert(!is_empty())
return back == size
return S[back - 1]
} }
Linked List Stack Data Structure
b c d e f
back
void push(Object x) { Object pop() {

temp = back assert(!is_empty())
back = new Node(x) return_data = back->data
back->next = temp temp = back
} back = back->next
Object top() { return return_data
assert(!is_empty()) }
return back->data
}
Data structures you should
already know
• Arrays
• Linked lists
• Trees
• Queues
• Stacks
To Do
• Sign up on the cse326 mailing list
• Check out the web page
• Log on to a PC in the course labs and
access an instructional UNIX server
• Read Chapters 1 and 3 in the book
Coming Up
• Unix Tutorial
– Tuesday (tomorrow) 10:50, Sieg 322
• Multi-Lists
• Priority Queues and Heaps
• Templates Tutorial
• First homework

TREE

Uploaded by

Copyright:

Available Formats

TREE

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

TREE

Uploaded by

Copyright:

Available Formats

CSE 326: Data Structures

Abstract Data Type (ADT) -

1) An opportunity for an acronym

2) Mathematical description of an object

void enqueue(Object x) { When is the Q empty?

This is pseudocode. Do not correct my semicolons.

void enqueue(Object x) { Object dequeue() {

void push(Object x) { Object pop() {

void push(Object x) { Object pop() {

You might also like