[PDF] Data Structures and Algorithms?3? - edX




Loading...







[PDF] Data Structures and Algorithms Recursion Basics - Tutorialspoint

DATA STRUCTURE - RECURSION BASICS Some computer programming languages allows a module or function to call itself This technique is known as recursion

[PDF] Notes 2: Introduction to data structures - 21 Recursion

We will take only a superficial look at recursion in this course since it provides a very neat way to represent certain useful numerical functions and data 

[PDF] MODULE-I INTRODUCTION TO DATA STRUCTURES

A function is said to be recursive if it calls itself again and again within its body whereas iterative functions are loop based imperative functions 2

[PDF] Data Structures and Algorithms?3? - edX

Ming Zhang“ Data Structures and Algorithms “ Commonly used to deal with data which has recursive Non recursive implementation of recursive algorithm

[PDF] Recursion - Faculty of Computer Science

11 3 Example: recursive implementation of the sum between two integers the stack of ARs is used as a temporary “data structure” in which to store the 

[PDF] Data Structures and Algorithm Analysis - Computer Science

28 mar 2013 · 4 2 4 Implementing Recursion C++ is used here strictly as a tool to illustrate data structures concepts In particu-

[PDF] Exam questions Chapter 1

Which data structure is used by the compiler to implement recursion? (a) hash table (b) priority queue (c) queue (d) search tree (e) stack

[PDF] DATA STRUCTURES USING “C” - CET

Recursion is another, typically more favored, solution, which is actually implemented by a stack Memory Management Any modern computer environment uses a 

[PDF] Data Structures and Algorithms?3? - edX 71784_3chapter3_EN.pdf https://courses.edx.org/courses/PekingX/04830050x/2T2014/

3OTÓ @NGTÓȐ *GRG 9RX[IR[XOY GTJ GRÓUXORNSY Ȑ

Data Structures

and Algorithms"3ͤ

Instructor: Ming Zhang

Textbook Authors: Ming Zhang, Tengjiao Wang and Haiyan Zhao Higher Education Press, 2008.6 (the "Eleventh Five-Year" national planning textbook) 2 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ 澧

Chapter 3 Stacks and Queues

‡Stacks

‡Applications of stacks

²Implementation of Recursion

using Stacks

‡Queues

Stacks and

Queues

Chapter 3

3 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Linear lists with limited operation

‡Stack

²Operation are permitted only on one

end

‡Queue

²Operation are permitted only on two

ends

Stacks and

Queues

Chapter 3

4 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Definition of stack

‡Last In First Out

²A linear list with limited access port

‡Main operation

²push澝pop

‡Applications

²Expression evaluation

²Elimination of recursion

²Depth-first search

3.1 Stacks

k1 ... Ki Ki+1

Stack top

Stack bottom

pop push k0

Stacks and

Queues

Chapter 3

5 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Abstract data type of stacks

3.1 Stacks

template class Stack { public: // Operation set of stacks void clear(); // Change into an empty stack bool push(const T item); // push item into the stackͫreturn true if succeed, otherwise false bool pop(T& item); // pop item out of the stackͫ return true if succeed, otherwise false bool top(T& item); // read item at the top of the stack, return true if succeed, otherwise false bool isEmpty(); // If the stack is empty return true bool isFull(); // If the stack is full return true };

Stacks and

Queues

Chapter 3

6 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Railway station problem

‡Judge whether the trains go out of the station in the right order?

²http://poj.org/problem?id=1363

‡1 PUMLQV QXPNHUHG MV 12"BQ JR LQPR POH PUMLQ LQ RUGHU ͫgiven an arrangementͫjudge whether the trains go out of the station in the right order?

3.1 Stacks

5, 4, 3, 2, 1 1, 2, 3, 4, 5

Railway station

B A

Stacks and

Queues

Chapter 3

7 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Use legal reconstruction to find conflicts

3.1 Stacks

1 2 3 1 2 3 4 4

8 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Question

‡If the order of the item pushed into the stack is

1,2,3,4ͫthen what is the order of the item

popped out of the stack ? ‡There is an original input sequence 1ͫ2ͫ"ͫn ͫyou are required to get the output sequence of p1ͫp2ͫ"ͫpn (They are a permutation of 1ͫ 2 ͫ"ͫn)using a stack. If there exists subscript i ͫjͫkͫwhich meet the condition that iPj legal or not(

3.1 Stacks

9 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Implementation of stacks

‡Array-based Stack

²Implemented by using vectorsͫis a

simplified version of sequential list

‡The size of the stack

²The key point is to make sure which end as

the stack top

²Overflow, underflow problem

‡Linked Stack

²Use single linked list for storageͫin which the direction of the pointer is from stack top down

3.1 Stacks

10 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

The class definition of Array-based Stack

3.1.1 Array-based Stack

template class arrStack : public Stack { private: // storage of Array-based Stack int mSize; // the number of elements that the stack can have at most int top; // stack topͫshould be small than mSize T *st; // array to put stack element public: // implementation of the operation of the Array-based Stack arrStack(int size) { // creates an instance of Array-based Stack with given size mSize = size; top = -1; st = new T[mSize]; } arrStack() {// creates an instance of Array-based Stack top = -1; } ~arrStack() { delete [] st; } void clear() { top = -1; } // clear the stack } 11 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Array-based Stack

‡The index of the last element pushed

into the stack is 4ͫ followed by 3,2,1 in order

3.1.1 Array-based Stack

1 2 3

Stack top

Stack bottom 4 12 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Overflow of Array-based Stack

‡Overflow

²When you perform push operation on a

full stack (that already has maxsize elements), overflow will occur.

‡Underflow

²When you perform pop operation on an

empty stack, underflow will occur.

3.1.1 Array-based Stack

13 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Push

3.1.1 Array-based Stack

bool arrStack::push(const T item) { if (top == mSize-1) { // the stack has been full cout << ȔStack overflow" << endl; return false; } else { //push new element into the stack and modify the pointer of the stack top st[++top] = item; return true; } } 14 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Pop

3.1.1 Array-based Stack

bool arrStack::pop(T & item) { // pop if (top == -1) { // the stack is empty

cout << " 4Š‡ •-ƒ... ‹• ‡"-›ř ›‘— ...ƒŨ-

pop "<< endl; return false; } else { // Get top value and decrease top by 1 item = st[top--]; return true; } } 15 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Definition of Linked Stack

‡Use single linked list for storage ‡The direction of the pointer is from stack top down

3.1.2 Linked Stack

Stack top

Kn-1 Kn-2 K1 K0 16 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Construction of Linked Stack

3.1.2 Linked Stack

template class lnkStack : public Stack { private: // storage for linked stack Link* top; //Pointer which points to the stack top int size; // the number of elements that the stack can have at most public:// implementation of the operation of the linked Stack lnkStack(int defSize) { // constructed function top = NULL; size = 0; } ~lnkStack() { // destructor function clear(); } } 17 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Push

3.1.2 Linked Stack

Link(const T info, Link* nextValue) { // constructed function with 2 parameters data = info; next = nextValue; } // implementation of push operation of linked stack bool lnksStack:: push(const T item) { Link* tmp = new Link(item, top); top = tmp; size++; return true; } 18 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Pop

3.1.2 Linked Stack

// implementation of pop operation of linked stack bool lnkStack:: pop(T& item) { Link *tmp; if (size == 0) { cout << " 7OH VPMŃN LV HPSP\ \RX ŃMQ·P SRS"<< endl; return false; } item = top->data; tmp = top->next; delete top; top = tmp; size--; return true; } 19 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Comparison of Array-based Stack and Linked Stack

‡Time efficiency

²All operations only take constant time

²Array-based Stack and Linked Stack have

almost the same time efficiency

‡Space efficiency

²The length of an Array-based Stack is fixed

²The length of a Linked Stack is variable,

with extra structural cost

3.1 Stacks

20 ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Comparison of Array-based Stack and Linked Stack ‡In real applicationsͫArray-based Stack is more widely used than Linked Stack ²It is easy for Array-based Stack to perform relative replacement according to the position of stack top , quickly position and read the internal element ²The time taken for Array-based Stack to read internal element is O(1). And the Linked stack has to walk along the chain of pointers, and is slower than Array-based Stack . It takes O(k) time to read the kth element.

‡ In general, the stack does not allow the

internal operation, can only operate in the stack top

3.1 Stacks

21
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Question͵ functions about stack in STL

‡Top function gets the element of the stack top and returns the result back to the user

‡Pop function pops a element out of the stack

topͧif the stack is not emptyͨ ²Pop IXQŃPLRQ LV ÓXVP MQ RSHUMPLRQ MQG GRHVQ·P UHPXUQ the result

²pointer = aStack.pop()( Error͜

‡Why does STL divide these two operations(

Why not provide ptop(

3.1 Stacks

22
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Applications of stacks

‡Characteristic of stacks͹last-in first-out

²Embodies the transparency between elements

‡Commonly used to deal with data which

has recursive structure

²DFSevaluate the expression

²Subroutine / function call management

²Elimination of recursion

3.1 Stacks

23
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Evaluate the expression

‡Recursive definition of expressions

²The basic symbol set ͹{0ͫ1ͫ"ͫ9ͫ+ͫ-ͫ*

ͫ/ͫͧͫͨ}

²Grammar set͹{ , ,

, , }

‡The infix expression 23+(34*45)/(5+6+7)

‡Postfix expression 23 34 45 * 5 6 + 7 + / +

3.1 Stacks

24
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Infix expression

‡Infix expression

4 * x * (2 * x + a) ² c

²Operator in the middle

²Need brackets to change

the priority

3.1 Stacks

- + c

4 x a

2 x * * * 25
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Syntax formula for infix expression

3.1 Stacks

Ī= + | - | Ī= < factor > * | < factor > < factor > / | < factor > < factor > Ī= < constant > < constant > Ī= | Ī= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 26
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ Graphical representation for expression recursion

3.1 Stacks

expression term + ͬ term * / factor factor expression ( ) digit 27
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Postfix expression

‡Postfix expression

4 x * 2 x * a + * c ²

²Operators behind

²No need for brackets

3.1 Stacks

- + c

4 x a

2 x * * * 28
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Postfix expression

Ī= + | - | Ī= < factor > * | < factor > < factor > / | < factor > < factor > Ī= < constant > < constant > Ī= | Ī= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

3.1 Stacks

29
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Evaluating a postfix expression

‡ 23 34 45 * 5 6 + 7 + / + = ?

Calculation characteristics ( The main differences between infix and postfix expression ( 23 + 34 * 45 / ( 5 + 6 + 7 ) = ?
23 34 45 * 5 6 + 7 + / + = ?

3.1 Stacks

postfix expression to be handled͵

23 / 45 5 6 7 * ͦ ͦ ͦ 34

change of the stack state

1530 11 18 85 108

calculation result 31
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Evaluating a postfix expression

‡Loop͹read symbol sequences of expressions

ͧMVVXPH ´ µ MV POH HQG RI POH LQSXP VHTXHQŃHͨ

ͫand analyze one by one according to the

element symbol read

1.When an operand is metͫpush

2.When an operator is met, pop twice and get two

operands, calculate them using the operator. And finally push the result into the stack. ‡FRQPLQXH POH SURŃHVV MNRYH XQPLO POH V\PNRO ´ ͼµ LV PHPͫ then the value of the stack top is the value of the input expression

3.1 Stacks

32
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

The class definition of postfix calculator

3.1 Stacks

class Calculator { private: Stack s;//the stack is used for pushing and storing operands // push two operands opd1 and opd2 from the stack top bool GetTwoOperands(double& opd1,double& opd2); // get two operands, and calculate according to op void Compute(char op); public: Calculator(void){} ; // creates calculator instance and construct a new stack void Run(void); // read the postfix expression, ends when meet "=" void Clear(void); // clear the calculator to prepare for the next calculation }; 33
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

The class definition of postfix calculator

3.1 Stacks

template bool Calculator::GetTwoOperands(ELEM& opnd1, ELEM& opnd2) { if (S.IsEmpty()) { cerr << "Missing operand!" < ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

The class definition of postfix calculator

3.1 Stacks

template void Calculator::Compute(char op) { bool result; ELEM operand1, operand2; result = GetTwoOperands(operand1, operand2); if (result == true) switch(op) { case '+' : S.Push(operand2 + operand1); break; case '-' : S.Push(operand2 - operand1); break; case '*' : S.Push(operand2 * operand1); break; case '/' : if (operand1 == 0.0) { cerr << "Divide by 0!" << endl; S.ClearStack(); } else S.Push(operand2 / operand1); break; } else S.ClearStack(); } 35
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

The class definition of postfix calculator

3.1 Stacks

template void Calculator::Run(void) { char c; ELEM newoperand; while (cin >> c, c != '=') { switch(c) { case '+': case '-': case '*': case '/': Compute(c); break; default: cin.putback(c); cin >> newoperand; Enter(newoperand); break; } } if (!S.IsEmpty()) cout << S.Pop() << endl; // print the final result } 36
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Question

‡1. Stack is usually implemented by

using single linked list. Can we use doubly linked list? Which is better(

‡2. Please summarize the properties

of prefix expression, as well as the evaluation process. 37
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3 Stacks and Queues

‡Stacks

‡Application of stacks

²Implementation of Recursion using

Stacks

‡Queues

38
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

Transformation from recursion to non-recursion

‡The principle of recursive function

‡Transformation of recursion

‡The non recursive function after

optimization 39
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

Another study of recursion

The principle of recursive function

‡Factorial

‡Exit of recursion

²End condition of recursion is when the minimal problem is solved

²More than one exits are permitted

‡Rule of recursion

ͧRecursive body + bounded functionͨ ²Divide the original problem into sub problems ²Ensure that the scale of recursion is more and more closer to the end condition 40
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

Non recursive implementation of recursive algorithm

The principle of recursive function

- Establish iteration - Transformation from recursion to non-recursion

‡Non recursive implementation of factorial

‡How about the problem of Hanoi Tower᧻

41
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

Recursion program for Hanoi tower problem

‡hanoi(n,X,Y,Z)

²Move n disk

²Move the disk from pillar X to pillar Z

²X澝Y澝Z can be used to place disks temporarily

‡Big disks cannot be put on small disks

‡Such as hanoi(2 ¶%· ¶F·  ¶$·

²Move 2 disks from pillar B to pillar A

The principle of recursive function

http://www.17yy.com/f/play/89425.html 42
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

void hanoi(int n, char X, char Y, char Z) { if (n <= 1) move(X,Z); else {

22 JUTȑR SU\O RNO RGXÓOYR JOYQ UT L GTJ SU\O RNO ROLR T-1 disk to Y

hanoi(n-1,X,Z,Y); move(X,Z); //move the largest disk on X to Z hanoi(n-1,Y,X,Z); // move the n-1 disk on Y to Z } } void move(char X, char Y) // move the disk on the top of pillar x to pillar Y { cout << "move" << X << "to" << Y << endl; }

3.1.3 Transformation from recursion to non-recursion

43
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

Operating diagram of Hanoi recursive subroutine

3.1.3 Transformation from recursion to non-recursion

Execute the instructions of Hanoi program

Exchange information with subroutine via stack

k1 ... Ki Ki+1

Stack top

Stack bottom

pop push k0 44
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

H

A,B,C

H

A,C,B

Call subroutine

recursively 3 2 H

A,B,C

1

Call subroutine

move(A,C) return move(A,B) H

C,A,B

1 move(C,B) return return move(A,C) H

B,A,C

2 H

B,C,A

1 move(B,A) return move(B,C) H

A,B,C

1 move(A,C) return return complete Hanoi "3,A,B,Cͤ

3.1.3 Transformation from recursion to non-recursion

Call subroutine

Call subroutine

Call subroutine

Call subroutine

recursively 45
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

H

A,B,C

H

A,C,B

3 2 H

A,B,C

1 move(A,C) return move(A,B) H

C,A,B

1 move(C,B) return

Return

move(A,C) H

B,A,C

2 H

B,C,A

1 move(B,A) return move(B,C) H

A,B,C

1 move(A,C) return ૞֚

Complete

Hanoi"3,A,B,Cͤ

Call subroutine

recursively

Call subroutine

Call subroutine

Call subroutine

Call subroutine

Call subroutine

recursively 46
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

3,A,B,C

2,A,C,B

1,A,B,C 1,C,A,B

2,B,A,C

1,B,C,A 1,A,B,C

The status of stack when the recursion is executed

3.1.3 Transformation from recursion to non-recursion

hanoi(3,A,B,C)

㓶嫛move(A,C) 㓶嫛move(A,B) 㓶嫛move(C,B) 㓶嫛move(A,C) 㓶嫛move(B,A) 㓶嫛move(B,C) Perform move(A,C)

hanoi(2,A,C,B) hanoi(1,A,B,C) hanoi(1,C,A,B) hanoi(2,B,A,C) hanoi(1,B,C,A) hanoi(1,A,B,C) 47
ऩڣ Ming Zhang ȐData Structures and Algorithmsȑ

Chapter 3

Stacks and

Queues

A recursive mathematical formula

3.1.3Transformation from recursion to non-recursion