# DS Introduction2015 .pdf

### File information

Original filename: DS-Introduction2015.pdf
Title: Operating Systems CSC 522
Author: Sameh Elsharkawy

This PDF 1.5 document has been generated by Microsoft® PowerPoint® 2013, and has been sent on pdf-archive.com on 05/11/2015 at 21:41, from IP address 41.37.x.x. The current document download page has been viewed 569 times.
File size: 919 KB (32 pages).
Privacy: public file

DS-Introduction2015.pdf (PDF, 919 KB)

### Document preview

Algorithms vs. programs (1)
• Algorithms:
– can be performed by humans or machines
– can be expressed in any suitable language
– may be as abstract as we like.
• Programs:
– must be performed by machines
– must be expressed in a programming
language
– must be detailed and specific.

Data structures
• A data structure is a systematic way of organizing a
collection of data.
• A static data structure is one whose capacity is
fixed at creation.
E.g.: array.
• A dynamic data structure is one whose capacity is
variable, so it can expand or contract at any time.
• For each data structure we need algorithms for
insertion, deletion, searching, etc.

Overview of the Array
• Insert a new data item.
• Search for a specified item.
• Delete a specified item.

What is the difference between Order
Array and Unorder Array?
• Is Insert Function will Change?
• Is Find Function will Change?
• Is Delete Function will Change?

Stacks
• Stacks often are drawn vertically:

pop

push

top

12

Stack Operations
• Some stack operations:
– push - add an item to the top of the stack
– pop - remove an item from the top of the
stack
– peek - retrieves the top item without
removing it
– empty - returns true if the stack is empty

Queue Operations
• We can define the operations for a queue
– enqueue - add an item to the rear of the queue
– dequeue (or serve) - remove an item from the front of the
queue
– empty - returns true if the queue is empty
An Abstract Picture
enqueue
dequeue
front

A link is an object of a class called something like Link.
Each link object contains a pointer (which we’ll call
pNext) to the next link in the list.

Binary Trees
• Why Use Binary Trees?
• You can search a tree quickly, as you can an ordered
array, and you can also insert &amp; delete items
quickly, as you can with a linked list.
• What Is a Tree?