9/11/2008 1 Concept of Data Structure Data Structure:
A means of storing a collection of data.
OR
It is the specification of the elements of the structure, the relationships between them, and the operation that may be performed upon them.

Classification of data structure :

9/11/2008 2 Classification of data structure

Computer Science & Data Structure :

9/11/2008 3 Computer Science & Data Structure Computer science is concern with study of Methods for effectively using a computer to solve problems.
or
In determining exactly the problem to be solved. This process entails:

Computer Science & Data Structure (Continue) :

9/11/2008 4 Computer Science & Data Structure (Continue) Gaining an understanding of the problem.
Translating vague descriptions, goals, and contradictory requests, and often unstated desires, into a precisely formulated conceptual Solution

Computer Science & Data Structure (Continue) :

9/11/2008 5 Computer Science & Data Structure (Continue) Implementing the solution with a computer program. This solution typically consists of two parts: algorithms and data structures:

Computer Science & Data Structure (Continue) :

9/11/2008 6 Computer Science & Data Structure (Continue) Algorithm:
An algorithm is a concise specification of a method for solving a problem.
Data Structure:
A data structure can be viewed as consisting of a set of algorithms for performing operations on the data it stores.

Computer Science & Data Structure (Continue) :

9/11/2008 7 Computer Science & Data Structure (Continue) Data Structure & Algorithm
Algorithms are part of what constitutes a data structure. In constructing a solution to a problem, a data structure must be chosen that allows the data to be operated upon easily in the manner required by the algorithm.In conclusion
Data Structures + Algorithms = Programs

Application of Data Structure :

9/11/2008 8 Application of Data Structure Stacks Applications
Direct applications
Page-visited history in a Web browser
Undo sequence in a text editor
Chain of method calls in the Java Virtual Machine or C++ runtime environment

Stacks Applications :

9/11/2008 9 Stacks Applications Indirect applications
Auxiliary data structure for algorithms
Component of other data structures

Queue Applications :

9/11/2008 10 Queue Applications Direct applications
Waiting lines
Access to shared resources (e.g., printer)
Multiprogramming
Indirect applications
Auxiliary data structure for algorithms
Component of other data structures

Data Structure & Algorithms :

9/11/2008 11 Data Structure & Algorithms “For many applications, the choice of the proper data structure is the only major decision involving the implementation: once the choice is made, the necessary algorithms are simple.”

What is an Algorithm? :

9/11/2008 12 What is an Algorithm? A systematic method of instructing an agent how to accomplish a task
Usually expressed in a step-wise sequential form
May involve alternation, iteration or recursion
Detail and language may depend on the agent

Examples of Algorithms :

9/11/2008 13 Examples of Algorithms Cooking Recipe Route from University to Main Post Office Music Score Knitting Pattern Insertion Sort

Description of an Algorithm :

9/11/2008 14 Description of an Algorithm Numbered steps with indentation commonly used
Different descriptions possible for the same algorithm
Difference between the algorithm description (design) and the completion of the task (implementation)
More than one algorithm possible for the same task

Efficiency of Algorithms :

9/11/2008 15 Efficiency of Algorithms What resources are required to accomplish the task
How one algorithm compares with other algorithms

Efficiency and Complexity :

9/11/2008 16 Efficiency and Complexity Efficiency
How much time or space is required
Measured in terms of common basic operations
Complexity
How efficiency varies with the size of the task
Expressed in terms of standard functions of n
E.g. O(n), O(n2), O(log n), O(n log n)

E.g. Simple Algorithm for xn :

9/11/2008 17 E.g. Simple Algorithm for xn 1. Set r = 1
2. Set i = 1
3. Repeat
3.1 If i=n then terminate loop
3.2 Multiply r by x
3.3 Add 1 to i
4. Exit with result r

Slide 18:

9/11/2008 18

Slide 19:

9/11/2008 19

Abstract Data Types(ADT) :

9/11/2008 20 Abstract Data Types(ADT) What is Abstraction?
To abstract is to ignore some details
of a thing in favor of others.
ADT & Data structure
An Abstract Data Type (ADT) is more a way of looking at a data structure: focusing on what it does and ignoring how it does its job.

Abstract Data Types(ADT) :

9/11/2008 21 Abstract Data Types(ADT) Why need Abstraction?
Abstraction is important in problem solving because it allows problem solvers to focus on essential details while ignoring the inessential, thus simplifying the problem and bringing to attention those aspects of the problem involved in its solution. Once an abstract data type is understood and documented, it serves as a specification that programmers can use to guide their choice of data representation and operation implementation, and as a standard for ensuring program correctness.

Abstract Data Types(ADT) :

9/11/2008 22 Abstract Data Types(ADT) Abstract data types:
Each data structure can be developed around the
concept of an abstract data type that defines both data
organization and data handling operations.
A mathematical entity consisting of a set of values and a collection of operations that manipulate them. For example, the Integer abstract data type consists of a carrier set containing the positive and negative whole numbers and 0, and a collection of operations manipulating these values, such as addition, subtraction, multiplication, equality comparison, and order comparison.

Abstract Data Types(ADT) :

9/11/2008 23 Abstract Data Types(ADT) Abstract data types are important in computer science because they provide a clear and precise way to specify what data a program must manipulate, and how the program must manipulate its data, without regard to details about how data are represented or how operations are implemented.
ADT defines both data organization and data handling operations.
The study of data structure is organized around a collection of abstract data types that includes lists, trees, sets, graphs, and dictionaries.

Abstract Data Types(ADT) :

9/11/2008 24 Abstract Data Types(ADT) ADT is not a part of a program ,since a program written in a programming language requires the definition of data structure, not just the operations on the data structure.
ADT is a useful tool for specifying the logical properties of a data type.
ADT is not concerned with the time/space efficiency of data type.

Specification of ADT :

9/11/2008 25 Specification of ADT ADT consist of 2 parts.
Value Definition.
Operator Definition.

Specification of ADT :

9/11/2008 26 Specification of ADT Value Definition.
It defines the collection of values for the
ADT and consist of two parts.
Definition Clause
Condition Clause
e.g. For ADT RATIONAL
Value definition: it states that RATIONAL value
consist of two integers ,the second of which does not equal
to zero.
The keyword abstract typedef introduce a value definition.

Specification of ADT :

9/11/2008 27 Specification of ADT Condition Clause
Used to specify any conditions on the newly defined type.
The keyword condition is used to specify any conditions on the newly defined type.
For e.g. for RATIONAL ADT
Condition Clause: denominator may not be zero.
Note :The definition clause is required but the
condition clause may not be necessary for every
ADT.

Specification of ADT :

9/11/2008 28 Specification of ADT Operator Definition.
It defines the operations that are to be performed on a data set.
Each operator is defined as an abstract function with three parts:
Header.
Optional preconditions .
Post conditions.

Specification of ADT :

9/11/2008 29 Specification of ADT Operator Definition.
For e.g. :Operator definition for RATIONAL ADT
includes the operations of creation ,addition ,
multiplication and equality.
Now for multiplication operation the operator definition for RATIONAL ADT is.
Abstract RATIONAL mult(a,b)……/*header*/
RATIONAL a, b; ………. /*header*/
mul[0]=a[0]*b[0]; ………………….. /*postcond*/
mul[1]=a[1]*b[1];……………………/postcond*/

Complete example of RATIONL ADT :

9/11/2008 30 Complete example of RATIONL ADT /* value definition*/
Abstract typedef< int , int >RATIONAL;
Condition RATIONAL[1]!=0;
/* Operator definition */
Abstract equal(a,b)
RATIONAL a ,b;
Postcondition equal==(a[0]*b[1]==b[0]*b[1]);
Like this we can declare the other operations.

Classification of Data Structure :

9/11/2008 31 Classification of Data Structure Linear and Non-Linear:
In linear data structure, the data items are arranged in linear sequence. e.g. Array, Stack, Queue, Linked List.
In non-linear data items are not in sequence. e.g. Tree , graph ,Heap

Classification of Data Structure (Continue) :

9/11/2008 32 Classification of Data Structure (Continue) Homogenous and Non-homogenous.
In homogenous data structure ,all the elements are of same type e.g. Array.
In non-homogenous data structure, the elements may or may not be of same type e.g. Record.

Classification of Data Structure (Continue) :

9/11/2008 33 Classification of Data Structure (Continue) Primitive and Non-Primitive:
Primitive data structures constitute the
number and the characters which are built
programs. examples int. reals,pointer
data,charaters data, logical data.

What is STACK or Pushdown List :

9/11/2008 34 What is STACK or Pushdown List A ordered collection of items into which new items may be inserted and from which items may be deleted at one end, called the top of stack.

Operations on STACK :

9/11/2008 35 Operations on STACK PUSH:When item is added in stack
POP:When item is removed from stack
EMPTY:Stack containing no items.
StackTop:Determine what the top item on a stack without removing it.this is a combination of push & pop

Push & Pop in STACK :

9/11/2008 36 Push & Pop in STACK PUSH Operation
PUSH(STACK ,TOP,MAX,ITEM)
STACK--Name given to Array.
TOP----It contains the location of top elements.
MAX---It is maximum size of STACK.
ITEM--->Value that is to be store in stack if top = MAX then stackfull top = top+1 stack(top) = item Return

Push & Pop in STACK :

9/11/2008 37 Push & Pop in STACK POP Operation
POP(STACK ,TOP,ITEM)
if top = 0 then Underflow item = stack(top) top = top-1 Return

Applications of STACK :

9/11/2008 38 Applications of STACK Expression Evaluation
Parenthesis Checker
Recursion

Infix To Postfix Conversion of an Arithmetic Expression :

9/11/2008 39 Infix To Postfix Conversion of an Arithmetic Expression Operator preecedence
^ ---------Higher precedence
*,/--------Next Precedence.
+,_-------Least precedence.

Infix To Postfix Conversion of an Arithmetic Expression :

9/11/2008 40 Infix To Postfix Conversion of an Arithmetic Expression The rules to remember.
Parenthesize the expression starting fro left to right.
During Parenthesizing the
expression the operands associated
with operator having higher
precedence are first parenthesized.

Infix To Postfix Conversion of an Arithmetic Expression :

9/11/2008 41 Infix To Postfix Conversion of an Arithmetic Expression The sub-expression which has been converted into postfix is to be treated as single operand.
Once the expression is converted to postfix form remove the parenthesis.
Example: A+B*C
A+[(B+C)+(D+E)*F]/G
Answer: ABC+DE+F*+G/+

Algorithm for Conversing Infix Expression to Postfix Form :

9/11/2008 42 Algorithm for Conversing Infix Expression to Postfix Form Postfix(Q,P)
Q—>Given Infix expression.
P->Equivalent Postfix expression.
Push “(“ onto STACK and add “)” to the end of Q.
Scan Q from left to right and repeat step 3 to 6 for each element of Q until the STACK is Empty.
If an operand is encountered ,add it to P.
If a left parenthesis is encountered ,push it onto STACK.

Algorithm for Conversing Infix Expression to Postfix Form :

9/11/2008 43 Algorithm for Conversing Infix Expression to Postfix Form If an operator ® is encountered then:
(a) ADD ® to STACK
[End of IF]
(b) Repeatedly pop from STACK and add P each operator which has same precedence as or higher precedence than ®.

Algorithm for Conversing Infix Expression to Postfix Form :

9/11/2008 44 Algorithm for Conversing Infix Expression to Postfix Form If a right parenthesis is encountered then:
(a) Repeatedly pop from STACK and add to P each operator until a left parenthesis is encountered.
(b) Remove the left parenthesis. do not add it of P]
[End of If]
[End of step 2 loop]
Exit.

Converting Infix Expression to Prefix Expression. :

9/11/2008 45 Converting Infix Expression to Prefix Expression. Reverse the input string.
Examine the next element in the input.
If it is operand ,add it to the output string.
If it is closing parenthesis , push it on STACK.

Converting Infix Expression to Prefix Expression. :

9/11/2008 46 Converting Infix Expression to Prefix Expression. If it is operator , then:
i) if STACK is empty, push –operation on STACK.
ii) if the top of the stack is closing parenthesis push operator on STACK.
iii) if it has same or higher priority then the top of STACK, push operator on S.
iv) else pop the operator from the STACK and add it to output string, repeat S.

Converting Infix Expression to Prefix Expression. :

9/11/2008 47 Converting Infix Expression to Prefix Expression. If it is a opening parenthesis , pop operator from STACK and add them to S until a closing parenthesis is encountered. POP and discard the closing parenthesis.
If there is more input go to step 2.
If there is more input , unstack the remaining operators and add them.
Reverse the output string.

Algorithm to Evaluate a Postfix Expression :

9/11/2008 48 Algorithm to Evaluate a Postfix Expression This algorithm finds the value of an
arithmetic expressions P written in
postfix notation. The algorithm uses a
STACK to hold operands , evaluate P.
Add right parenthesis “)” at the end of P.[This acts as sentinel]
Scan P from left to right and repeat step 3 & 4 for each element of P until the sentinel “)” is encountered.

Algorithm to Evaluate a Postfix Expression :

9/11/2008 49 Algorithm to Evaluate a Postfix Expression If an operand is encountered , put it on STACK.
If an operator ® is encountered , then:
A) Remove the two top elements of STACK, Where A is the top element and B is the next-to-top element.
B)Evaluate B ®A.
C)Place the result of (b) back o STACK.
[End of IF]
[End of step 2 loop]
Set value equal to the top element on STACK.
Exit.

Parenthesis Checker :

9/11/2008 50 Parenthesis Checker Read exp
Create empty Stack
For each character C in exp
If(current character is left symbol) then
Push the character C onto Stack.
Elseif(current character C is a right Symbol)then
If(stack is empty)then
Print:”Error:No matching open symbol”
Exit

Parenthesis Checker :

9/11/2008 51 Parenthesis Checker Else
POP a symbol S from the Stack
If (S doesnot correspond to C)then
Print:”Error:Incorrect nesting of symbols”
Exit
Endif
Endif
Endif
End for

Parenthesis Checker :

9/11/2008 52 Parenthesis Checker If (stack is not empty)then
Print:”Error:Missing closing symbols(s)”
Else
Print:”Input expression is ok”
Endif
End

Example of STACK :

9/11/2008 53 Example of STACK Many computer algorithms work best with stacks --- stacks are used for
remembering partially completed tasks, and
undoing (backtracking from) an action.
An example of 1. is described in the next section, where sub expressions of an arithmetic expression are remembered for later computation. Another example is presented in the next lecture, where we see how the Java Virtual Machine uses a stack to remember all of a program's methods that have been called but are not yet finished.
An example of 2. is the ``undo'' button on most text editors, which lets a person undo a typing error, or the ``back'' button on a web browser, which lets a user backtrack to a previous web page. Another example is a searching algorithm, which searches a maze and keeps a history of its moves in a stack. If the algorithm makes a false (bad) move, the move can be undone by retrieving the previous position from the stack.

STACK Implementation :

9/11/2008 54 STACK Implementation Static and dynamic data structures
A stack can be stored in:
• a static data structure
OR
• a dynamic data structure
Static data structures
These define collections of data which are fixed in size when the program is compiled.
An array is a static data structure.
Dynamic data structures
These define collections of data which are variable in size and structure. They are
created as the program executes, and grow and shrink to accommodate the data being
stored.

TRANSPOSE OF SPARSE MATRIX :

9/11/2008 55 TRANSPOSE OF SPARSE MATRIX #include<stdio.h>
#include<conio.h>
// transpose for the sparse matrix
void main()
{
//clrscr();
int a[10][10],b[10][10];
int m,n,p,q,t,col;
int i,j;
printf("enter the no of row and columns :\n");
scanf("%d %d",&m,&n);

TRANSPOSE OF SPARSE MATRIX :

9/11/2008 56 TRANSPOSE OF SPARSE MATRIX // assigning the value of matrix
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
printf("a[%d][%d]= ",i,j);
scanf("%d",&a[i][j]);
}
}

TRANSPOSE OF SPARSE MATRIX :

9/11/2008 57 TRANSPOSE OF SPARSE MATRIX printf("\n\n");
//displaying the matrix
printf("\n\nThe matrix is :\n\n");
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
printf("%d",a[i][j]);
}
printf("\n");
}

TRANSPOSE OF SPARSE MATRIX :

9/11/2008 58 TRANSPOSE OF SPARSE MATRIX t=0;
printf("\n\nthe non zero value matrix are :\n\n");
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
// accepting only non zero value
if(a[i][j]!=0)
{

TRANSPOSE OF SPARSE MATRIX :

9/11/2008 59 TRANSPOSE OF SPARSE MATRIX t=t+1;
b[t][1]=i;
b[t][2]=j;
b[t][3]=a[i][j];
} }
}
b[0][0]=m;
b[0][1]=n;
b[0][2]=t;
// displaying the matrix of non-zero value
printf("\n");
For(i=0;i<=t;i++)
printf(“%d “,a[i][0],a[i][1],a[i][2]);

TRANSPOSE OF SPARSE MATRIX :

9/11/2008 60 TRANSPOSE OF SPARSE MATRIX // transpose of the matrix
printf("\n\nthe transpose of the matrix :\n ");
if(t>0)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=t;j++)
{
if(b[j][2]==i)
{
a[q][1]=b[j][2]; a[q][2]=b[j][1];
a[q][3]=b[j][3]; q=q+1;
} }
} }

Tower of Hanoi(An application of Recursion & Stack) :

9/11/2008 62 Tower of Hanoi(An application of Recursion & Stack) This problem is not specified in terms of recursion but the recursive technique can be used to produce a logical solution .
Problem Definition:
There are three pegs A,B,& C exist, any number of disks (n) of different diameters are placed on peg A so that a larger disk is always below a smaller disk.

Tower of Hanoi(An application of Recursion & Stack) :

9/11/2008 63 Tower of Hanoi(An application of Recursion & Stack) The object is to move n disks to peg C ,using peg B as auxiliary.
Only the top disk on any peg may be moved to any other peg, and a larger disk may never rest on a smaller one.
Note:in general it requires f(n)=2n-1 moves

Recursive solution to tower of Hanoi problem :

9/11/2008 64 Recursive solution to tower of Hanoi problem To move n disks from A to C using B as auxiliary:
If n==1 move the single disk from A to C and stop

Recursive solution to tower of Hanoi problem :

9/11/2008 65 Recursive solution to tower of Hanoi problem Move the top n-1 disks from A to B , using C as auxiliary.
Move the remaining disks from A to C
Move the n-1 disks from B to C,using A as auxiliary.

Recursive Implementation of Tower of Hanoi. :

9/11/2008 66 Recursive Implementation of Tower of Hanoi. main()
{
int n;
scanf (“%d”, &n);
towers (n, ’A’, ’C’ ,’B’);
}

Slide 67:

9/11/2008 67 towers(int n, char frompeg, char topeg,char auxpeg)
{
If (n==1)
{
printf (“\n %s %c %s %c”, “move disk 1 from peg “,frompeg, “to peg”, topeg);
return;
}

9/11/2008 69 Addition of two sparse matrix Sparse Matrix Addition : If we want to add two matrices we need to first check their size to find if they can be added Let S1 and S2 be two sparse matrix stored in array form as described above. We want to add these two sparse matrices and create an net one S. Algorithm for addition is given below.

Addition of two sparse matrix :

9/11/2008 70 Addition of two sparse matrix Add_smat(s1,s2,s)
i=1,j=1,k=1
R1=s1[0][0],c1=s1[0][1]
R2=s2[0][0],C2=s2[0][1]

Addition of two sparse matrix :

9/11/2008 71 Addition of two sparse matrix Ctl= S1[O][2]
Ct2=S2[O][2] // count of nonzero elements in CT1 and CT2
While(i<=ct1 && j<=ct2)
If(s1[i][1]=s2[j][1])//if elements are in same row & column

Addition of two sparse matrix :

9/11/2008 72 Addition of two sparse matrix If(s1[i][2]=s2[j][2])
S[k][0]=s1[i][0]+s2[i][0]
S[k][1]=s1[i][1]
S[k][2]=s1[i][2]

Addition of two sparse matrix :

9/11/2008 73 Addition of two sparse matrix i=i+1;
J=j+1;
K=k+1;
Else
If(s1[i][2]<s2[ j][2])
//elements of Ist matrix are in a precding column.

Addition of two sparse matrix :

9/11/2008 74 Addition of two sparse matrix S[k][0]=s1[i][0]
S[k][1]=s1]i][1]
S[k][2]=s1[i][2]
i=i+1;
K=k+1;

Addition of two sparse matrix :

9/11/2008 75 Addition of two sparse matrix Else //copy s2 value
S[k][0]=s2[j][0]
S[k][1]=s2]j][1]
S[k][2]=s2[j][2]
j=j+1
K=k+1
Endif

Addition of two sparse matrix :

9/11/2008 76 Addition of two sparse matrix Else if(s1[i][1]<s2[j][1])
//elements of first matrix is a proceeding row
S[k][0]=s1[i][0]
S[k][1]=s1]i][1]
S[k][2]=s1[i][2]
i=i+1;
K=k+1;

Addition of two sparse matrix :

9/11/2008 77 Addition of two sparse matrix Else
S[k][0]=s2[j][0]
S[k][1]=s2]j][1]
S[k][2]=s2[j][2]
j=j+1
K=k+1
End if
End while
//if any elements are left

Addition of two sparse matrix :

9/11/2008 78 Addition of two sparse matrix If(i<ct1+1)//elements remain in S1
For(m=I;m<ct1+1;m++)
S[k][0]=s1[m][0]
S[k][1]=s1[m][1]
S[k][2]=s1[m][2]
K=k+1;
End for

Addition of two sparse matrix :

9/11/2008 79 Addition of two sparse matrix //if elements remaining in s2
Elseif(j<ct2+1)
For(m=j;m<ct2+1;m++)
S[k][0]=s2[m][0]
S[k][1]=s2[m][1]
S[k][2]=s2[m][2]
K=k+1
End for
End if

Addition of two sparse matrix :

9/11/2008 80 Addition of two sparse matrix S[0][0]=s1[m][0]
S[0][1]=s1[m][1]
S[0][2]=k-1
return

Queue :

9/11/2008 81 Queue It is a linear list of elements in which deletion can take place only at one end called ‘ head or front ‘ and insertion take place only at the other end called ‘tail or rear’. They are also called First-in-First-Out (FIFO) lists.

Insertion in Linear Queue :

9/11/2008 82 Insertion in Linear Queue Insert( Q, F, R, N, X)
Q=Name of the queue
N=maximum size of the queue
F=Front pointer variable
R=Rear pointer variable
X=element to be inserted

Insertion in Linear Queue :

9/11/2008 83 Insertion in Linear Queue Step 1 :Overflow condition
If R>=N then
Write “overflow” and return
End if
Step 2:Is the queue empty
If F=0 then
F=1
End if

Insertion in Linear Queue :

9/11/2008 84 Insertion in Linear Queue Step 3: Increment rear pointer
R=R+1
Step 4: Insert new element
Q[R]=X
Step 5:Finished
Return

Deletion in Linear Queue :

9/11/2008 85 Deletion in Linear Queue Delete( Q, F, R , X)
Q=Name of the queue
F=Front pointer variable
R=Rear pointer variable
X=variable used to store the deleted element

Deletion in Linear Queue :

9/11/2008 86 Deletion in Linear Queue Step 1:underflow
If f=0 then
Write “underflow” and return
End if
Step2 : delete front element
X=Q(F)

Deletion in Linear Queue :

9/11/2008 87 Deletion in Linear Queue Step 3: Is queue now empty?
If F=R then
[queue has only 1 element]
F=0,R=0 and return
End if

Deletion in Linear Queue :

9/11/2008 88 Deletion in Linear Queue Step 4: Increment front pointer
F=F+1
Step: 5 Finished
return

Limitation of linear Queue :

9/11/2008 89 Limitation of linear Queue In queue insertion are performed at one end while deletions are performed at the other end.a series of insertions and deletions may cause overflow , even though some of the position are empty at front.

Circular Queue or Ring Buffer :

9/11/2008 90 Circular Queue or Ring Buffer The problem of linear queue can be resolved with circular queue, where elements are placed in such a way that the element Q(1) follows the Q(N). Here if list is full but first position is empty than element to be inserted at the first position.

Insertion in Circular Queue :

9/11/2008 91 Insertion in Circular Queue CQ_Insert( Q, F ,R, N,X)
Step 1: Is the queue full ?
If f=1 and R=N then
Write “overflow” and return
Step2 : Is the queue empty ?
If F=0 then
F=1
End if

Insertion in Circular Queue :

9/11/2008 92 Insertion in Circular Queue Step 3: reset rear pointer
If R=N then
R=1
Else
R=R+1
End if

Insertion in Circular Queue :

9/11/2008 93 Insertion in Circular Queue Step 4:insert new element
Q[R]=X
Step 5: finished
Return

Deletion in Circular Queue :

9/11/2008 94 Deletion in Circular Queue CQ-Delete( Q, F, R, X)
Step 1:Is the queue empty?
If F=0 then
Write ‘under flow’ and return
End of IF statement

Deletion in Circular Queue :

9/11/2008 95 Deletion in Circular Queue Step 2:Delete front element
X=Q[F]
Step 3:Is the queue now empty?
If F=R then
F=0 ,R=0 and Return
End if

Deletion in Circular Queue :

9/11/2008 96 Deletion in Circular Queue Step 4: Increment front pointer
If F=N then
F=1
Else
F=F+1
End if
Step 5: Finished
Return

Usage of Queue :

9/11/2008 97 Usage of Queue Queues occur naturally in situations where the rate at which clients’ demand for services can exceed the rate at which these services can be supplied. For example, in a network where many computers share only a few printers, the print jobs may accumulate in a print queue. In an operating system with a GUI, applications and windows communicate using messages, which are placed in message queues until they can be handled.

Double Ended Queue (DEQUE) :

9/11/2008 98 Double Ended Queue (DEQUE) It is homogenous list of elements in which insertion & deletion operations are performed from both ends i.e insertion can take place from the rear end or from the front ends.
Types of DEQUE
Input Restricted Queue
Output Restricted Queue

Priority Queue :

9/11/2008 99 Priority Queue 1-Way list
Multiple queues(Array represntation)

Advantage of Circular linked list over single linked list :

9/11/2008 100 Advantage of Circular linked list over single linked list Using circular linked list every node is reachable from every node ,as the list is circular .so we can traverse the whole list from given node. thus, accessibility of a node is easy by using circular linked list. in single linked list the deletion operation ,maintains two pointers ,

Advantage of Circular linked list over single linked list :

9/11/2008 101 Advantage of Circular linked list over single linked list one which stores the address of the node to be deleted and second one ,stores the address of first node ,in order to traverse the list. that means for deletion two pointers have to be maintained ,but circular linked list overcomes this problem by initiating the search from the given node itself for finding its predecessor.

Advantage of Circular linked list over single linked list :

9/11/2008 102 Advantage of Circular linked list over single linked list Thus, there is no need of giving the address of the first node .operations like splitting , and concatenation of a lists prove to be more efficient in circular linked list than in a single linked list.

Limitation of circular linked list :

9/11/2008 103 Limitation of circular linked list In circular linked list last node points to first node there might be a condition where processing of list leads to the infinite looping. Thus, for avoiding this situation one possible solution is to assign a special node called the head node or list head of circular linked list, which delimits the list.In this case last node points to the head node.

Advantage of header node :

9/11/2008 104 Advantage of header node By using head node , list can never be empty , and most of the algorithms require the testing of the list to see whether it is empty or not. The information of data field of the head node is not used , and is denoted by the shaded area.

Preorder Traversal :

9/11/2008 105 Preorder Traversal Algorithm: Initial Step
Push NULL in Stack & set PTR=ROOT, and then repeat the below steps until PTR#NULL
(a) Process down the left most path rooted at PTR. if a node N has right child then push R(N) into STACK , if Left child process it (PTR=L(N))

Preorder Traversal :

9/11/2008 106 Preorder Traversal (b) if a node N has no left child then go to step 2
a) POP the node N from STACK
b) Assign to PTR ,if PTR=NULL then exit otherwise go to step 1.

Inorder Traversal :

9/11/2008 107 Inorder Traversal Algorithm: Initial Step
Push NULL in Stack & set PTR=ROOT, and then repeat the below steps until NULL is popped from STACK.
Process down the left most path rooted at PTR, Push each left node in STACK, when a node has no L(N) and R(N) then go to step 2.

Inorder Traversal :

9/11/2008 108 Inorder Traversal a) POP a node N from STACK,PTR=N
b) Process this node N
c) If this node N has right child (R(N)) then set PTR=R(N) & go to step 1
d) But if NULL is pop from STACK Then exit.
Note: In this algo a node N is processed only when it is popped from STACK.

Postorder Traversal :

9/11/2008 109 Postorder Traversal Algorithm: Initial Step
Push NULL in Stack & set PTR=ROOT, and then repeat the below steps until NULL is popped from STACK.
a) Process down the left most path rooted at PTR, push each node N in STACK ,but if a node N has R(N) then push –R(N) in the STACK.

Postorder Traversal :

9/11/2008 110 Postorder Traversal b) Stop this process when a node N has no left & right child.
a) POP a node N from STACK.
b) If N is +ve process it
c) If N is –Ve then set PTR=N (i.e +ve N) & go to step 1.
d) if NULL is Popped then Exit.
Note: always push right node before left node

Algorithm for Insertion in MAX Heap :

9/11/2008 111 Algorithm for Insertion in MAX Heap Insert_element(heap,n,item)
1 set n=n+1
2 Set heap [n]=item
3. call reheapify_upward(heap,n)

reheapify_upward function :

9/11/2008 112 reheapify_upward function reheapify_upward(heap,start)
If (start>1)
Parent=start/2
If heap[start] is not a root node then
If (heap [parent]<heap[start]) then

reheapify_upward function :

9/11/2008 113 reheapify_upward function Swap heap[parent] and heap[start]
Call reheapify_upward(heap,parent)
End if
End if
End if

Algorithm for Deletion in MAX Heap :

9/11/2008 114 Algorithm for Deletion in MAX Heap Basic steps are
1. Assign the value of the root to the temporary variable.
2. Bring the last element of the heap to the root node position.
3. reduce the size of the heap by a factor of one
Apply reheapify downward operation from root node

Algorithm for Deletion in MAX Heap :

9/11/2008 115 Algorithm for Deletion in MAX Heap Delete_element(heap,n,item)
1. set item=heap[1]
2. set heap[1]=heap[n]
3. set n=n-1
4. call rehapify_downward(heap,1,n)

reheapify_downward function :

9/11/2008 116 reheapify_downward function reheapify_downward(heap,start,finish)
Heaplinear array
Startit is the index of the element from where reheapify downward operation is to start.
Finishit is the index of the last(bottom) element of the heap.

reheapify_downward function :

9/11/2008 117 reheapify_downward function 1. if heap[start] is not a leaf node then
2.set index=index of the child with the largest value
3. If (heap[start]<heap[index] then
4. Swap heap[start] and heap[index]
5. call
reheapify_downward(heap,index,finish)
End if
End if

General Approach of Heap Sort :

9/11/2008 118 General Approach of Heap Sort 1.From the given array build the initial max heap.
2. interchange the root(maximum) element with the last element
3.use the reheapify_downward operation from root node to rebuild the heap of size one less than the starting

General Approach of Heap Sort :

9/11/2008 119 General Approach of Heap Sort 4. repeat the step1 & step2 until there are no more elements.

Slide 120:

9/11/2008 120 #include<stdio.h>
#include<conio.h>
void heapify(int a[],int i,int elt);
void delmax(int a[], int n);
void adjust(int a[], int i, int m);
void main()
{
int a[10],n,i,elt;
clrscr();

9/11/2008 125 void adjust(int a[], int i, int m)
{
int j, item;
j=2*i+1;
item=a[i];
while(j<=m)
{
if (j<m && a[j]<a[j+1])
j=j+1;
if(item>=a[j])
break;
a[(j-1)/2]=a[j];
j=2*j+1;
}
a[(j-1)/2]=item;
}

Rotation on AVL Tree :

9/11/2008 126 Rotation on AVL Tree The rotations are characterized by the nearest ancestor p, of the inserted node A, whose BF becomes ±2.The following characterization of rotation types is obtained.
LL: new node A is inserted in the left sub tree of the left subtree of p.

Rotation on AVL Tree :

9/11/2008 127 Rotation on AVL Tree LR: new node A is inserted in the right sub tree of the left sub tree of p.
RR: new node A is inserted in the right sub tree of the right sub tree of p.
RL: new node A is inserted in the left sub tree of the right sub tree of p.

Some important Notation for AVL Tree Rotation :

9/11/2008 128 Some important Notation for AVL Tree Rotation A: newly inserted node
p: first ancestor of node A with BF ±2
X: parent of p
q: child of p

Steps to perform LL Rotation :

9/11/2008 129 Steps to perform LL Rotation 1.Replace q as child of X instead of p.
2.Detach the right sub tree of q and make it the left sub tree of p.
3. Make p the right child of q.

Steps to perform RR Rotation :

9/11/2008 130 Steps to perform RR Rotation make the node q the child X instead of p.
Detach the left sub tree of q & make it right sub tree of p.
Make p the left child of q.

Steps to perform LR Rotation :

9/11/2008 131 Steps to perform LR Rotation This type of rotation may become essential when a new node A is to be inserted , the right sub tree of left sub tree of p. let the left sub tree of p be rooted at q & right sub tree of q be rooted at r. the following steps can be used to perform LR rotation.

Steps to perform LR Rotation :

9/11/2008 132 Steps to perform LR Rotation Make r the child of X (parent of p) instead of p, if X is not present , then make r as root.
Add the left child of r (rL) to the right of q.
Add the right child of r (rR)to the left of p.
Make q the left child of r.
Make p the right child of r.

Steps to perform RL Rotation :

9/11/2008 133 Steps to perform RL Rotation This type of rotation may be essential when new node A is to inserted in the left sub tree of right sub tree of p. steps are.here r is the left child of q.
Make r the child of X instead of p
Make right child of r(rR),left child of q.
Make left child of r (rL) ,right child of p.
Make q the right child of r.
Make p the left child of r.

Slide 134:

9/11/2008 134

Slide 135:

9/11/2008 135

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

By: sarax (9 month(s) ago)

could u pl send me this ppt to my mail id - sharaag01@yahoo.com; i would be much obliged.