Home / Data Structure

Stack With Recursive Algorithm Implementation:

* or /  returns 2.

+ or  returns 1. ( or )  returns 0.


4.3.4. Stack with recursive algorithm implementation:‌

The implementation of a recursive algorithm is organized in memory in the form of a Stack. Specifically: When a recursive subroutine is called from the main program, we say the subroutine is executed at level 1. And in the subroutine, when it encounters its own call, the subroutine is executed in turn at levels 2, 3, ..., level k (level k must be completed before level k1 can be executed again).

When going from level i to level i+1, there may be some parameters, local variables, and return addresses corresponding to level i that will be reserved so that when returning, they will be restored for continued use.

Local variable parameters and return addresses that are saved later are restored first.

Use Stack in implementing recursive subroutines in the following form:

When there is a call to itself, the Stack will be added an element (a record consisting of fields: parameters, local variables, and return address).

When exiting a level, an element at the top of the Stack will be removed (restored to the previous required value).

 We can summarize these steps as follows:

Step 1: Initial step (essentially Push): Preserve parameters, local variables and return addresses.

Step 2: Body step. Divided into 2 cases:

If degenerate case occurs, perform the termination part. Go to

Step 3.

If not, perform the partial calculation and go to step 1.

Step 3: End step. Restore parameters, local variables and rollback address (pop). And move to this rollback address.

Note: Based on this principle, Stack is often used to transform a recursive algorithm into a non-recursive algorithm.

Example 1 : Hanoi Tower problem :

structure Rec

{


int nn;

char aa, bb, cc;

};


int T;

char a, b, c;

Rec r;

rec S[100];

Rec rr;


void BoVao(rec r;int n;char a;char b;char c)

{

r.nn= n; r.aa=a; r.bb=b; r.cc=c; T=T+1; S[T]=r;


}


void LayOut(Rec r)

{

r=S[T];

T=T-1;

}


void main()

{

cin >> n;

a='A'; b='B'; c='C'; T=0;

BoVao(r, n, a, b, c); do

{

LayRa(rr);

if (rr.nn==1) cout << rr.aa << ”” << rr.cc; else. else

{

BoVao(r, rr.nn-1, rr.bb, rr.aa, rr.cc);

BoVao(r, 1, rr.aa, rr.bb, rr.cc);

BoVao(r, rr.nn-1, rr.aa, rr.cc, rr.bb);

}

}

while (T!=0);

}


Example 2:

The following program describes the algorithm for calculating n! recursively but using a Stack: an array whose elements are each records consisting of two fields: a Para field (parameter) and an Addr field (return address).

struct Rec {

int Para; int Addr;

};


int n, T; Rec a[100]; float Kq; Rec TempRec;


void Push(Rec TempRec){


T=T+1;

a[T]=TempRec;

}


void Pop(Rec &TempRec){


TempRec=a[T];

T=T-1;

}


void main()

{

cin >> n;

T=0;

TempRec.Para=n; TempRec.Addr=5; 1: Push(TempRec);

2: if (a[T].Para==0)

{


}

else

{


}

Kq=1;

goto 4;


TempRec.Para=a[T].Para-1; TempRec.Addr=3;

goto 1;

3: Kq=Kq*a[T].Para;

4: Pop(TempRec); switch (TempRec.Addr){

case 3: goto 3;break; case 5: goto 5;break;

}

5: cout << Kq;

}

4.4. Queue:‌‌‌

4.4.1. Definition:

A queue is a linear list where additions are performed at one end (called the rear) and removals are performed at the other end (the front).

Comment : The structure of Queue is like a queue: first in first out. Therefore Queue is also called FIFO (First In First Out) list .

4.4.2. Storing Queue using array:

We can use a one-dimensional array Q with n elements as the storage structure of a queue. To process Q we use two variables:

+ Variable R to keep track of Q's backdoor position.

+ Variable F to keep track of Q's front position.

Note:

When Q (Queue) is empty, we assume: F = R = 0.

When an element is added, R increases by 1 (R=R+1). When an element is removed, F increases by 1 (F=F+1).

1 2 3 4

Exit

FR

Entrance


However, with this organization, there may be a situation where at some point no more elements can be added but the memory space of array Q still has room. To overcome this, we consider Q as a circular array, that is, consider Q[1] to be after Q[n].

With this organization we have:

 Algorithm to add element x to Queue (with front position F and back position R):

void Insert_Queue(&Q, &F, &R, &X) //Q, R, F: parameter if ((R % n)+1=F)

// Equivalent: if ((R<n) && (R+1=F)) || ((R=n) && (F=1))

cout << “The queue is full!” else

{


}

return;

R=(R % n)+1;

Q[R]=X;

if (F==0) F=1;

 Algorithm to remove an element from the Queue (front-end F, back-end is

R) and the removed element is assigned to a variable X:

void Delete_Queue(&Q, &F, &R, &X) //Q, F, R, X: parameters if (F==0) pritnf(“The queue is running out!”);

else

{


}

return;

X=Q[F];

if (F==R) F=R=0;

else F=(F % n)+1;


Exercise:

1) Calculate the value of an infix expression whose tokens have 2 types (Constants, operators: +, , *, /) using the following method:

11

+

2

*

3

Read tokens from left to right, all put into queue. For example: 11 + 2 * 3:


Take out one at a time to put into a second list. Remember: if you encounter the * or / operator, take an element from the queue and take out an element from the second list to perform this operation, and put the result back into the second list.

11

+

2



2 * 3

2) Same as exercise 1, but tokens can have '(' or ')', using the following method:

Example: 1 + (2 * (3 + 4))


1

(

2

*

(

3

+

4



Maybe you are interested!

Stack With Recursive Algorithm Implementation:

3

4

Read tokens from left to right to push into a Stack until you encounter a ')', then take elements from this Stack and put them into a second list (put from the left) until you encounter a '('.


+

At that time, we process this second list (calculate) based on the procedure built in exercise 1). The result is put back into the original Stack.


1

+

(

2

*

7


Then continue until this expression is exhausted.


1

+

14


At that time, we consider this Stack as a queue to use the procedure in exercise 1 to process.

Remark : A Stack can also be viewed as a Queue or a linear list in general. The important thing is that we need to use 2 variables to keep track of the positions of the 2 ends of this list so that we can perform addition or removal operations accordingly.


CHAPTER 5: LINKED LIST


5.1. Single Link List:‌‌‌

5.1.1. Organization of singly linked list:

Each element of the list is called a node, which is a record consisting of two parts:

Info section: Contains information about the element (can have more than one field).

Next: This is a field that contains the address of the element immediately following it (which is a pointer). This field has a pointer data type.

Nodes can be scattered throughout memory.

To access every element of the list, we must access the first node. Therefore, we must have a First pointer to point to the first element of the list. From the first node, through the Next field, we will go to the second node and so on, we can iterate through all the elements in the list.

The last element in the list has a Next field that does not contain the address of any element, which we call NULL.

When the list is empty, we assume First = NULL;

We denote:

p = new <type>; is a procedure to create a free memory area to contain a node and this node is pointed to by the pointer p (p contains the address of this node).

delete p; is the procedure to free the memory area of ​​the node pointed to by pointer p from memory.

Use the symbol pointed to by p.

For example:

Structure Nut

{

to access variables that are fields contained in a node

int Info;

Nut* Next;

};

Nut* First;

Nut* p;‌

5.1.2. Some operations on singly linked lists:

5.1.2.1. Insert a new node with content X into the list after the node pointed to by p:

void Insert_Node(&First, p, X); //First: parameter Tam= new Nut;

Tam->Info=X;

if (First==NULL)

{

First=Tam;

First->Next=NULL;

return;// exit the subroutine

}

Tam->Next=p->Next; P->Next=Tam;

return;

5.1.2.2. Remove a node pointed to by p from the list:

void Delete_Node(&First, p); //First: parameter if (First==NULL)

{

cout << “Empty list”; return;

}

if (First==p)

{

First=First->Next; delete p;

return;

}

q=First;

while (q->Next!=p) q=q->Next; q->Next=p->Next;

delete p; return;

5.1.2.3. Merge the two lists pointed to by first1 and first2 into one list pointed to by first1:

void Combine(&First1, First2); //First1: parameter if (First1==NULL)

{

First1=First2; return;

}

if (First2==NULL) return; p=First1;

while (p->Next!=NULL) p=p->Next; p->Next=First2;

return;


Exercise:

3

Name(6 characters) Age

Orchid 25

Le 20

An 18

............

Create a text file named VB.TXT with the following structure:

Comment


Agree Privacy Policy *