[PDF] [PDF] Introduction to Data Structures and Algorithms

[PDF] Introduction to Data Structure

24 nov 2015 · Array, Stacks, linked list, queue Eg tree, graph Implementation is easy Implementation is difficult Operation on Data Structures

[PDF] Data Structures and Algorithms - School of Computer Science

Introduction These lecture notes cover the key ideas involved in designing algorithms We shall see how they depend on the design of suitable data structures, 

[PDF] Basics of Data Structures Introduction to Data Structures

Data Structure is an arrangement of data in a computer's memory (or sometimes on a disk) Data structures include arrays, linked lists, stacks, binary trees, and 

[PDF] Data Structures Lecture 1: Introduction - Everything Computer Science

What is a Data Structure Anyway? What kind of operations should your data structure(s) support? http://www cs umd edu/~mount/420/Lects/420lects pdf

[PDF] Introduction to Data Structures and Algorithms

Overview on simple data structures Typical Examples of Elementary Data Structures i e a certain data structure is a stack if the respective axioms hold

[PDF] Basic Introduction into Algorithms and Data Structures

As fundamental data structures, we in- troduce linked lists, trees and graphs Implementations are given in the programming language C Contents 1 Introduction

[PDF] A Practical Introduction to Data Structures and Algorithm Analysis

3 jan 2011 · Steven S Skiena's The Algorithm Design Manual [Ski98] pro- vides pointers to many implementations for data structures and algorithms that 

[PDF] LECTURE NOTES ON DATA STRUCTURES - IARE

Y Daniel Liang, “Introduction to Programming using Python”, Pearson 2 Benjamin Baka, David Julian, “Python Data Structures and Algorithms”, Packt Publishers, 

[PDF] Notes 2: Introduction to data structures

Notes 2: Introduction to data structures 2 1 Recursion 2 1 1 Recursive functions Recursion is a central concept in computation in which the solution of a 

[PDF] Data Structures and Algorithms Using Python

We do this by placing the focus on the data structures and algorithms, while designing the examples to allow the introduction of object-oriented programming if 

[PDF] introduction to database

[PDF] introduction to database concepts pdf

[PDF] introduction to design patterns pdf

[PDF] introduction to digital filters pdf

[PDF] introduction to econometrics (3rd edition solutions chapter 2)

[PDF] introduction to econometrics (3rd edition solutions chapter 5)

[PDF] introduction to econometrics 3rd edition solutions chapter 3

[PDF] introduction to econometrics 3rd edition solutions chapter 4

[PDF] introduction to emu8086

[PDF] introduction to financial management questions and answers pdf

[PDF] introduction to financial statements pdf

[PDF] introduction to food and beverage service

[PDF] introduction to french pronunciation pdf

[PDF] introduction to functions pdf

[PDF] introduction to geographic information systems pdf

Lehrstuhl Informatik 7 (Prof. Dr.-Ing. Reinhard German)

Martensstraße 3, 91058 Erlangen

Introduction to

Data Structures and AlgorithmsChapter:

Elementary Data Structures(1)

Data Structuresand Algorithms(1)

Overview on simple data structures

for representing dynamic sets of data records

Main operations on thes

e data structures are

Insertionand deletionof an element

searchingfor an element finding the minimu mor maximumelement finding the successoror the predecessorof an element

And similar operations ...

These data structures are often implementedusing dynamically allocated objectsand pointers

Elementary Data Structures

Data Structuresand Algorithms(1)

Typical Examples of Elementary Data Structures

Array Stack Queue

Linked List

Tree

Elementary Data Structures

Data Structuresand Algorithms(1)

Stack A stackimplements the LIFO (last-in, first-out) policy like a stack of plates, where you can either place an extra plate at the top or remove the topmost plate

For a stack,

the insert operation is called Push and the delete operation is called Pop

Elementary Data Structures

Data Structuresand Algorithms(1)

Where are Stacks used?

A call stack

that is used for the proper execution of a computer program with subroutine or function calls

Analysis of

context free languages(e.g. properly nested brackets) Properly nested: (()(()())), Wrongly nested: (()((())

Reversed Polish notation of terms

Compute 2 + 3*5 䌑 㻞㻌㻼㼡㼟㼔㻌㻟㻌㻼㼡㼟㼔㻌㻡㻌㻖㻌㻗

Elementary Data Structures

Data Structuresand Algorithms(1)

Properties of a Stack

Stacks can be defined by axio

ms based on the stack operations, i.e. a certain data structure is a stack if the respective axioms hold

For illustration some examples fo

r such axioms - the "typical" axioms are (where S is a Stack which can hold elements x of some set㼄㻕 If not full(S): Pop(S) o (Push(S,x)) = x for all x 䌞㼄

Elementary Data Structures

Data Structuresand Algorithms(1)

Typical Implementation of a Stack

A typical implementation of a stack of size

n is based on an array

S[1...n]

䌑so it can hold at most n elements top(S) is the index of the most recentlyins erted element

The stack consists of elementsS[1 ...

top(S)], where

S[1] is the element at the bottom of the stack,

and S[top(S)] is the element at the top.

The unused elements S[top(S)+1 ... n

are not in the stack

Elementary Data Structures

STopPush Pop

4 3 2 1

Data Structuresand Algorithms(1)

Stack

Elementary Data Structures

Data Structuresand Algorithms(1)

Elementary Data Structures

Example (Stack Manipulation)

Start with stack given,

denote changes of "stack state"

Push(S, 17)

Pop(S), Pop(S), Pop(S), Push(S, 5)

Pop(S), Pop(S)

Pop(S)

S

1234567

3 3 23
top(S)

Data Structuresand Algorithms(1)

Elementary Data Structures

S:S: S:S:

7 6 5 4 3 2 1765
4 3 2 176
5 4 3 2 176
5 4 3 2 1

Top[S]=3

Top=4 Top=2 Top=0 33
3 3 23
235

317push(S,17)

pop (S) 17 pop (S) 3 pop (S) 23 push(S,5) pop (S) 5 pop (S) 3 pop (S)

Error:underflow

Data Structuresand Algorithms(1)

Pseudo Code for Stack Operations

Number of elements

Elementary Data Structures

NumElements (S)

return top[S]

Data Structuresand Algorithms(1)

Pseudo Code for Stack Operations

Test for emptiness

Test for "stack full"

Elementary Data Structures

Stack_Empty(S)

if top[S]=0 then return true else return false

Stack_Full (S)

if top[S]=n then return true else return false

Data Structuresand Algorithms(1)

Pseudo Code for Stack Operations

Pushing and Popping

Elementary Data Structures

Push(S,x)

if Stack_Full(S) then error "overflow" else top[S] := top[S]+1

S[top[S]] := x

Pop(S)

if Stack_Empty(S) then error "underflow" else top[S] := top[S]-1 return S[top[S]+1]

This pseudo code contains

error handling functionality

Data Structuresand Algorithms(1)

Pseudo Code for Stack Operations

(Asymptotic) Runtime

NumElements:

number of operations independent of size n of stack

Stack_Emptyand Stack_Full:

number of operations independent of size n of stack

Pushand Pop:

number of operations independent of size n of stack

Elementary Data Structures

Data Structuresand Algorithms(1)

Queue A queueimplements the FIFO (first-in, first-out) policy Like a line of people at the post office or in a shop

For a queue,

the insert operation is called

Enqueue

(=> place at the tail of the queue) and the delete operation is called

Dequeue

(=> take from the head of the queue)

Elementary Data Structures

tailhead dequeueenqueue

Data Structuresand Algorithms(1)

Where are Queues used?

In multi-tasking systems (communication, synchronization) In communication systems (store-and-forward networks) In servicing systems (queue in front of the servicing unit) Queuing networks (performance evaluation of computer andcommunication networks)

Elementary Data Structures

Data Structuresand Algorithms(1)

Typical Implementation of a Queue

A typical implementation of a queue consisting of at most n-1 elements is based on an array

Q[1 ... n]

Its attribute head(Q)points to the head of the queue.

Its attribute tail(Q)points to the pos

ition where a new element will be ins e rted into the queue (i.e. one position behind the last element of the queue).

The elements in the queu

e are in positions head(Q), head(Q)+1, ..., tail(Q)-1, where we wrap around the array boundary in the sense that Q[1] immediately follows Q[n]

Elementary Data Structures

Data Structuresand Algorithms(1)

Elementary Data Structures

Q

12345678910

head(Q)tail(Q)

Example (1)

Insert a new element (4.)

1. 2. 3. (n = length (Q) = 10) Q

12345678910

head(Q)tail(Q) 1. 2. 3. 4.

Data Structuresand Algorithms(1)

Elementary Data Structures

Q

12345678910

head(Q)tail(Q)

Example (2)

Insert one more element (5.)

And again: Insert one more element (6.)

1. 2. 3. 4. Q

12345678910

head(Q)tail(Q) 1. 2. 3. 4. 5. Q

12345678910

head(Q)tail(Q) 1. 2. 3. 4. 5. 6.

Data Structuresand Algorithms(1)

Elementary Data Structures

Typical Implementation of a Queue

Number of elements in queue

If tail > head:

NumElements(Q) = tail - head

If tail < head:

NumElements(Q) = tail - head + n

If tail = head:

NumElements(Q) = 0

Initially:

head[Q] = tail[Q] = 1

Position of elements in queue

The x. element of a queue Q (1 x NumElements(Q)

is mapped to array position head(Q) + (x - 1) if x n - head +1 (no wrap around) head(Q) + (x - 1) - n if x > n - head +1 (wrap around)

Data Structuresand Algorithms(1)

Elementary Data Structures

Typical Implementation of a Queue

Remark:

A queue implemented by a n-element array

can hold at most n-1 elements otherwise we could not distinguish between an empty and a full queue

A queue Q is empty:

䋽NumElements(Q) = 0) if head(Q) = tail(Q)

A queue Q is full:

䋽NumElements(Q) = n-1) if head(Q) = (tail(Q) + 1) (head(Q) > tail(Q)) if head(Q) = (tail(Q) - n + 1) (head(Q) < tail(Q))

Data Structuresand Algorithms(1)

Elementary Data Structures

Q

12345678910

head(Q) tail(Q)

Example (Queue Manipulation)

Start with queue given, denote changes of "queue state"

Enqueue(Q, 2), Enqueue(Q, 3), Enqueue(Q, 7)

Dequeue(Q)

4 12 4

Data Structuresand Algorithms(1)

Queue Operations

Enqueue and Dequeue

Elementary Data Structures

Enqueue(Q,x)

Q[tail[Q]] := x

if tail[Q]=length[Q] then tail[Q] := 1 else tail[Q] := tail[Q]+1

Dequeue(Q)

x := Q[head[Q]] if head[Q]=length[Q] then head[Q] := 1 else head[Q] := head[Q]+1 return x

Precondition: queue not full

Precondition: queue not empty

This pseudo code does not contain

error handling functionality (see stack push and pop)

Data Structuresand Algorithms(1)

Pseudo Code for Queue Operations

(Asymptotic) Runtime

Enqueueand Dequeue:

number of operations independent of size n of queue

Elementary Data Structures

Lehrstuhl Informatik 7 (Prof. Dr.-Ing. Reinhard German)

Martensstraße 3, 91058 Erlangen

Introduction to

Data Structures and AlgorithmsChapter:

Elementary Data Structures(2)

Data Structuresand Algorithms(1)

Typical Examples of Elementary Data Structures

Array Stack Queue

Linked List

Tree

Elementary Data Structures

Data Structuresand Algorithms(1)

Linked List

In a linked list, the elements are arranged in a linear order, i.e. each element (except the first one) has a predecessor and each element (except the last one) has a successor. Unlike an array, elements are not addressed by an index, but by a pointer(a reference).

There are

singlylinked lists and doublylinked lists.

A list may be sorted or unsorted.

A list may be circular (i.e. a ring of elements).

Here we consider mainly unsorted, doubly linked lists

Elementary Data Structures

Data Structuresand Algorithms(1)

Linked List

Each element x of a (doubly) linked list has three fields

A pointer prevto the previous element

A pointer next to the next element

A field that contains a key(value of a certain type) Possibly a field that contains satellite data (ignored in the following)

Pointer fields that contain no poi

nter pointing to another element contain the spec ial pointer NIL(䌪 The pointer head[L] points to the first element of the linked list

If head[L] = NIL the list L is an empty list

Elementary Data Structures

prev key next

One element x :

(consist of 3 fields)

Data Structuresand Algorithms(1)

Linked List

In a linked list, the insert operation is called List_Insert, and the delete operation is called List_Delete. In a linked list we may search for an element with a certain key k by calling List_Search.

Elementary Data Structures

Linked List Example

dynamic set {11, 2 ,7 , 13} head[L]

117132prev

keynext Notice:prev[head] = NIL and next[tail] = NIL

Data Structuresand Algorithms(1)

Some Examples for the Use of Linked Lists

Lists of passengers of a plane or a hotel

Elementary Data Structures

Data Structuresand Algorithms(1)

Searching a Linked List

The procedure List_search (L, k)

finds the first element with key k in list L and returns a pointer to that element.

If no element with key k is found,

the special pointer NIL is returned.

Elementary Data Structures

List_Search(L,k)

x := head[L] while x!=NIL and key[x]!=k do x := next[x] return x

Data Structuresand Algorithms(1)

Inserting into a Linked List

The procedure List_insert(L,x)

inserts a new element x as the new head of list L The runtime for List_Insert on a list of lengt is constant (O(1))

Elementary Data Structures

head[L]

List_Insert(L,x)

next[x] := head[L] if head[L]!=NIL then prev[head[L]] := x head[L] := xquotesdbs_dbs20.pdfusesText_26