Transcript CS 104 Introduction to Computer Science and Graphics Problems

CS 104 Introduction to
Computer Science and
Graphics Problems
Data Structure & Algorithms (4)
Data Structures
11/18/2008
Yang Song
Data Structure
In computer science, a data structure is a way
of storing and organizing data in the computer,
so that the data can be used efficiently.
Some data structures we often use







Linked List
Queue
Stack
Tree
Graph
Linked List

One of the fundamental data structures and can be used
to implement other data structures. It consists of a
sequence of nodes, each node has two kinds of fields:



Data, to store the date
Link, to point to the next node (may have One or Two links)
Basic Operations:



Search
Insertion
Deletion
O(n)
O(1)
O(1)
Linked List (Cont.)

For a linked list, if each node has only one link, which points to its next node,
we call it singly-linked list:

For a linked list, if each node has two links, which point to its next and
previous nodes, we call it doubly-linked list:
Queue

Queue is a common and important data structure in computer science. It can be
described with the analogy of waiting in a line. There is no cutting allowed in the line,
so the first element stored in the line is the fist item to picked out of the line, we call it
First In First Out (FIFO). Recall the memory in Operating Systems, we have FCFS,
they are same.

Basic Operations:



Enqueue: Add new items to the queue, it will add the new items only to the back of
the queue.
Dequeue: Remove items from the queue, it will remove the items only from the
front of the queue.
Example: From an empty Queue, we have following operations: Enqueue (3),
Enqueue (5), Enqueue (7), Dequeue, Dequeue. Result is: (7)
Stack

Stack is an abstract data type and data structure based on the principle of
Last In First Out (LIFO).

Basic Operations:
 Push: Add the new item to the top
 Pop: Get the item from the top
 Example: From an empty Stack, we have the following operations: Push
(3), Push (5), Push (7), Pop, Pop. Result is: (3)
Different from Queue:
 FIFO v.s. LIFO

Tree

A data structure accessed beginning at the root node. Each
node is either a leaf or an interior node. An interior node has one
or more child nodes and is called the parent of its child nodes.
Contrary to a physically real tree, the root is usually at the top of
the structure and the leaves are at the bottom.
Tree (Cont.)




Level, Height
Node: Root, Leaf, Child, Parent, Sibling
Sub-Tree
Basic Operations




Traversal
Insertion
Deletion
Binary Tree


A tree in which each node has AT MOST two children, called Left Child and
Right Child
Traversal: In-Order, Pre-Order, Post-Order




In-Order: Left Child->Root->Right Child
Pre-Order: Root->Left Child->Right Child
Post-Order: Left Child->Right Child->Root
Application: Binary Search Tree, Heap
Binary Search Tree (BST)



A BST is a Binary Tree Data Structure with following properties:
 Each node has a value
 The Left sub-tree of a node contains only values less than the
node’s value
 The Right sub-tree of a node contains only values greater than
the node’s value
A major advantage of BST over other data structures is that the
related sorting algorithms and search algorithms can be very
efficient.
 What kind of traversal do we need to make all the values in BST
be sorted? Why?
A good link to see the animation of insertion, deletion and search:
http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html