Ds 2p4mf

Scilab Textbook Companion for Data Structures Using C And C++ by Y. Langsam, M. Augenstein And A. M. Tenenbaum1 Created by Dharmesh Majethiya B.Tech (pursuing) Computer Engineering NIT Tiruchirappalli College Teacher Mr.Kunwar Singh Cross-Checked by Siddharth Jain August 12, 2013

1 Funded

by a grant from the National Mission on Education through ICT, http://spoken-tutorial.org/NMEICT-Intro. This Textbook Companion and Scilab codes written in it can be ed from the ”Textbook Companion Project” section at the website http://scilab.in

Book Description Title: Data Structures Using C And C++ Author: Y. Langsam, M. Augenstein And A. M. Tenenbaum Publisher: Prentice - Hall Of India Pvt. Ltd. Edition: 2 Year: 2006 ISBN: 81-203-1177-9

1

Scilab numbering policy used in this document and the relation to the above book. Exa Example (Solved example) Eqn Equation (Particular equation of the above book) AP Appendix to Example(Scilab Code that is an Appednix to a particular Example of the above book) For example, Exa 3.51 means solved example 3.51 of this book. Sec 2.3 means a scilab code whose theory is explained in Section 2.3 of the book.

2

Contents List of Scilab Codes

4

1 Introduction To Data Structures

6

2 Stacks

21

3 Recursion

33

4 Queues and linked list

40

5 Trees

65

6 Sorting

79

7 Searching

86

8 Graphs

89

3

List of Scilab Codes Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa

1.1 1.1.4 1.1.5 1.1.7 1.2 1.2.1 1.2.6 1.3 1.3.1 1.3.6 1.3.7 1.4 1.5 1.6 2.1 2.1.2 2.2 2.2.3 2.3 2.4 3.1 3.2 3.3 3.4 3.5 3.6 3.7 4.1

To calcualte Average And Deviation . . . . . . . . . Decimal form of given no represented variably . . . . Add Substract And Multiply binary numbers . . . . TO Convert Binary To Ternary . . . . . . . . . . . . String Manipulations . . . . . . . . . . . . . . . . . . Calculate Median And Mode Of an Array . . . . . . Finding the adress in a row major array . . . . . . . Writing name from structure and counting alphabets Implementing Complex Numbers by structure . . . . Adding Substracting and multiplying Rational Nos . Checking Equality Of 2 Rational Numbers . . . . . . Raising the salary of employee . . . . . . . . . . . . Reducing the given rational number . . . . . . . . . Equality check of 2 rational nos by reduction . . . . To determine the syntacticaly valid string . . . . . . To determine the syntacticaly valid string . . . . . . Implementing Stack using union . . . . . . . . . . . Check if string is of certain form . . . . . . . . . . . Implementing Push And Pop Functions . . . . . . . Convering an infix expression to a Postfix Express . Multiplication of 2 numbers . . . . . . . . . . . . . . Factorial of a number . . . . . . . . . . . . . . . . . Fibbonacci series . . . . . . . . . . . . . . . . . . . . Binary Search . . . . . . . . . . . . . . . . . . . . . Tower Of Hanoi . . . . . . . . . . . . . . . . . . . . Prefix To Postfix Conversion . . . . . . . . . . . . . Simulating Factorial By Non recursion . . . . . . . . Implementing Singly Connected Linked List . . . . . 4

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

6 7 9 10 10 11 13 14 15 16 17 17 18 19 21 22 24 25 27 28 33 33 34 35 36 36 39 40

Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa Exa

4.2 4.3 4.4 4.5 4.6 5.1 5.2 5.3 5.4 6.1 6.2 6.3 6.4 6.5 6.6 6.7 7.1 7.2 7.3 8.1 8.2 8.3 8.4 8.5 8.6 8.7 8.8

Implementing Queue Operarions . . . . . . . . . . . . Implementing Circular Linked List . . . . . . . . . . . Implementing Doubly connected Linked List . . . . . . Implementing Stack using circular Linked list . . . . . Implementing Priority Queue Using Lists . . . . . . . Implementing Binary Tree . . . . . . . . . . . . . . . . Tree Trversal Techniques . . . . . . . . . . . . . . . . Implementing And traversing a Binary Search Tree . . Checking the duplicate number using BST . . . . . . . Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . Selection Sort . . . . . . . . . . . . . . . . . . . . . . . Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . Shell sort . . . . . . . . . . . . . . . . . . . . . . . . . Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . Binary Tree Sort . . . . . . . . . . . . . . . . . . . . . Sequential Search . . . . . . . . . . . . . . . . . . . . Sorted sequential search . . . . . . . . . . . . . . . . . Binary Search . . . . . . . . . . . . . . . . . . . . . . Simple Graph Functions . . . . . . . . . . . . . . . . . Finding The Number Of Paths From One VertexToOther Finding The Number Of Simple Paths From One Point Finding Transitive Closure . . . . . . . . . . . . . . . Warshalls Algorithm . . . . . . . . . . . . . . . . . . . Depth First Search Traversal . . . . . . . . . . . . . . BFS Traversal . . . . . . . . . . . . . . . . . . . . . . Dijkstras Algorithm . . . . . . . . . . . . . . . . . . .

5

45 46 50 55 61 65 68 72 76 79 80 80 81 81 82 84 86 86 87 89 90 90 91 93 94 95 96

Chapter 1 Introduction To Data Structures

Scilab code Exa 1.1 To calcualte Average And Deviation 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

// S o l v e d Example 1 // : To c a l c u a l t e A v e r a g e And D e v i a t i o n function [ avg ]= average ( a ) i =1; [j , k ]= size ( a ) ; j =0; for i =1: k j=j+a(i); end avg = j / k ; dev =0; disp ( avg , ” A v e r a g e =” ) ; disp ( ” The d e v i a t i o n s a r e : ” ) ; for i =1: k dev = a ( i ) - avg ; disp ( dev ) ; end endfunction // C a l l i n g r o u t i n e 6

20 a =[3 223 212 343] 21 avg = average ( a )

Scilab code Exa 1.1.4 Decimal form of given no represented variably 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

// E x e r c i s e 1 . 1 Example . 1 . 1 . 4 //To c a l c u l a t e D e c i m a l No . o f a g i v e n Number // T r e a t i n g them a s i ) Normal b i n a r y n o s ( i i ) Twos complemented i i i )BCD: function [ c ]= twos1 ( a1 ) [ j1 , i1 ]= size ( a1 ) i4 =1 c = -( a1 ( i4 ) *2^( i1 -1) ) ; i1 = i1 -1; while ( i1 >=1) i4 = i4 +1; c = c + a1 ( i4 ) *2^( i1 -1) ; i1 = i1 -1; end disp ( a1 , ” D e c i m a l form o f t h e Twos Complement Number” ) ; disp (c , ” i s ” ) ; endfunction function [ d ]= binary_dec ( a2 ) [ j2 , i2 ]= size ( a2 ) ; k = modulo ( i2 ,4) ; d =0; if ( k ==0) e = i2 /4; i3 =1 while ( i3 <= i2 ) l =3 m =0 while (l >=0) m = m +( a2 ( i3 ) *2^ l ) ; 7

29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66

l =l -1; i3 = i3 +1; end if (m >9) d = -1; disp ( ” Cannot be c o d e d i n t h i s form ” ) break ; end if (m <=9) d = d + m *10^( e -1) e =e -1; end end end disp ( a2 , ” D e c i m a l form o f BCD number ” ) ; disp (d , ” i s ” ) ; endfunction // Given Example : // (A) p1 =[1 0 0 1 1 0 0 1]; p2 = base2dec ([ ’ 1 0 0 1 1 0 0 1 ’ ] ,2) p2 = twos1 ( p1 ) p2 = binary_dec ( p1 ) // ( b ) p3 =[1 0 0 1]; p4 = base2dec ([ ’ 1 0 0 1 ’ ] ,2) p4 = twos1 ( p3 ) p4 = binary_dec ( p3 ) // (C) p5 =[0 0 0 1 0 0 0 1 0 0 0 1]; p6 = base2dec ([ ’ 0 0 0 1 0 0 0 1 0 0 0 1 ’ ] ,2) p6 = twos1 ( p5 ) p6 = binary_dec ( p5 ) // ( d ) p7 =[0 1 1 1 0 1 1 1]; p8 = base2dec ([ ’ 0 1 1 1 0 1 1 1 ’ ] ,2) p8 = twos1 ( p7 ) p8 = binary_dec ( p7 ) 8

67 68 69 70 71 72 73 74 75 76

// ( e ) p9 =[0 1 0 1 0 1 0 1]; p10 = base2dec ([ ’ 0 1 0 1 0 1 0 1 ’ ] ,2) p10 = twos1 ( p9 ) p10 = binary_dec ( p9 ) // ( F ) p11 =[1 0 0 0 0 0 0 1 0 1 0 1]; p12 = base2dec ([ ’ 1 0 0 0 0 0 0 1 0 1 0 1 ’ ] ,2) p12 = twos1 ( p11 ) p12 = binary_dec ( p11 )

Scilab code Exa 1.1.5 Add Substract And Multiply binary numbers 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

// E x e r c i s e 1 . 1 e x a m p l e 1 . 1 . 5 //Add , S u b s t r a c t And M u l t i p l y b i n a r y numbers function [ a ]= add (b , c ) d = base2dec (b ,2) e = base2dec (c ,2) a=d+e a = dec2bin ( a ) disp (a , ” R e s u l t o f a d d i t i o n ” ) endfunction function [ a ]= subtract (b , c ) d = base2dec (b ,2) e = base2dec (c ,2) a =d - e a = dec2bin ( a ) disp (a , ” R e s u l t o f s u b t r a c t i o n ” ) endfunction function [ a ]= multiply (b , c ) d = base2dec (b ,2) e = base2dec (c ,2) a=d*e a = dec2bin ( a ) disp (a , ” R e s u l t o f m u l t i p l i c a t i o n ”); 9

23 24 25 26 27 28 29

endfunction // C a l l i n g R o u t i n e : b=” 11001 ”; c=” 10011 ”; a = add (b , c ) a = subtract (b , c ) a = multiply (b , c )

Scilab code Exa 1.1.7 TO Convert Binary To Ternary 1 // E x e r c i s e 1 . 1 Example 1 . 1 . 7 2 //TO C o n v e r t B i n a r y To T e r n a r y 3 function [ t ]= bin_ter ( a ) 4 b =0 5 b = base2dec (a ,2) ; 6 disp ( b ) ; 7 [j , i ]= size ( a ) ; 8 t =[]; 9 while ( b ~=0) 10 m = modulo (b ,3) ; 11 t =[ t (: ,:) m ]; 12 b = b /3; 13 b =b - modulo (b ,10) ; 14 end 15 disp (t , ” T e r n a r y E q u i v a l e n t ” ) ; 16 endfunction 17 // C a l l i n g R o u t i n e : 18 a = ” 1 0 0 1 0 1 1 0 1 1 1 0 ” 19 disp (a , ” i n p u t s t r i n g i s ” ) ; 20 b = bin_ter ( a )

Scilab code Exa 1.2 String Manipulations 10

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// S o l v e d Example 2 // : S t r i n g M a n i p u l a t i o n s funrot (0) function [ l ]= strlen ( str ) i =1; l =0; [j , k ]= size ( str ) for i =1: k l = l + length ( str ( i ) ) ; end disp (l , ” s t r i n g l e n g t h i s ” ) ; endfunction // C a l l i n g R o u t i n e : str = ” H e l l o World ” ; l = strlen ( str ) function [ c ]= strcat1 (a , b ) disp ( strcat ([ a b ]) ,” A f t e r c o n c a t i n a t i o n ” ) ; c = strcat ([ a b ]) ; endfunction // C a l l i n g R o u t i n e : a=” h e l l o ”; b=” world ”; c = strcat1 (a , b ) ;

Scilab code Exa 1.2.1 Calculate Median And Mode Of an Array 1 2 3 4 5 6 7 8 9

// E x e r c i s e Example 1 . 2 . 1 // C a l c u l a t e s Median And Mode Of an // (A) function [ y ]= median1 ( a ) p = mtlb_sort ( a ) ; [j , i ]= size ( a ) ; y =0 j = modulo (i ,2) ; if ( j ==0) 11

Array

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

y =(( a ( i /2) + a ( i /2+1) ) /2) ; end if ( j ==1) i = i /2; i =i - modulo (i ,10) ; y = a ( i +1) ; end disp (y , ” median i s ” ) ; endfunction // (B) function [ z ]= mode1 ( a ) p = mtlb_sort ( a ) ; disp ( p ) q =1; r =1; i =1; [j , i1 ]= size ( a ) ; if ( i1 >1) for i =1: i1 -1 if ( p ( i ) ~= p ( i +1) ) q =[ q (: ,:) i +1]; r =[ r (: ,:) 1]; else [c , d ]= size ( r ) ; r ( d ) = r ( d ) +1; end end q1 = mtlb_sort ( r ) ; [j , i1 ]= size ( q1 ) if ( q1 ( i1 -1) == q1 ( i1 ) ) z = -1; disp ( ”Mode d o e s n o t e x i s t ” ) ; break ; else c = q1 ( i1 ) ; k =1; while ( r ( k ) ~= c ) k = k +1; 12

48 end 49 z=p(q(k)); 50 end 51 end 52 if ( i1 ==1) 53 z = a (1) ; 54 end 55 disp (z , ” mode i s ” ) ; 56 endfunction 57 a =[223 12 233322 121] 58 y = median1 ( a ) ; 59 z = mode1 ( a ) ;

Scilab code Exa 1.2.6 Finding the adress in a row major array 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// E x e r c i s e 1 . 2 Example 1 . 2 . 6 // F i n d i n g t h e a d r e s s i n a row m a j o r a r r a y function []= add (m , n ) printf ( ” A d r e s s i s %d\n ” ,m + n *20) ; endfunction // ( a ) add (10 ,0) ; // ( b ) add (100 ,0) ; // ( c ) add (0 ,0) ; // ( d ) add (2 ,1) ; // ( e ) add (5 ,1) ; // ( f ) add (1 ,10) ; // ( g ) add (2 ,10) ; 13

21 // ( h ) 22 add (5 ,3) ; 23 // ( i ) 24 add (9 ,19) ;

Scilab code Exa 1.3 Writing name from structure and counting alphabets 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

// S o l v e d Example 5 : // W r i t i n g a name from t h e g i v e n s t r u c t u r e and // c o u n t i n g t h e number o f a l p h a b e t s p r i n t e d function [ l ]= strlen ( str ) i =1; l =0; [j , k ]= size ( str ) for i =1: k l = l + length ( str ( i ) ) ; end endfunction function [ count ]= writename ( name ) printf ( ” \n ” ) ; printf ( ”%s” , name . first ) ; printf ( ”%c” , ’ ’ ); printf ( ”%s” , name . midinit ) ; printf ( ” \ t ” ) ; printf ( ”%s” , name . last ) ; printf ( ” \n ” ) ; a = string ( name . first ) ; count = strlen ( a ) ; a = string ( name . midinit ) ; count = count + strlen ( a ) ; a = string ( name . last ) ; count = count + strlen ( a ) ; disp ( count , ” Count i s : ” ) ; endfunction 14

// C a l l i n g R o u t i n e name = struct ( ’ f i r s t ’ , ’ p r a v e e n ’ , ’ m i d i n i t ’ , ’ r a j e e v ’ , ’ l a s t ’ , ’ chauhan ’ ) ; 31 count = writename ( name ) 29 30

Scilab code Exa 1.3.1 Implementing Complex Numbers by structure 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

// E x e r c i s e 1 . 3 // Example 1 . 3 . 1 // I m p l e m e n t i n g Complex Numbers by s t r u c t u r e function []= complexmanu ( x1 , x2 , x3 , x4 ) com1 = struct ( ’ r e a l ’ ,x1 , ’ c o m p l e x ’ , x2 ) ; com2 = struct ( ’ r e a l ’ ,x3 , ’ c o m p l e x ’ , x4 ) ; // a d d i n g 2 numbers add = struct ( ’ r e a l ’ , x1 + x3 , ’ c o m p l e x ’ , x2 + x4 ) ; disp ( add . complex , ”+ i ” , add . real , ” A d d i t i o n r e s u l t i s ”); // S u b s t r a c t sub = struct ( ’ r e a l ’ ,x1 - x3 , ’ c o m p l e x ’ ,x2 - x4 ) ; disp ( sub . complex , ”+ i ” , sub . real , ” S u b s t r a c t i o n r e s u l t i s ”); // N e g a t i n g neg = struct ( ’ r e a l ’ ,-x1 , ’ c o m p l e x ’ ,- x2 ) ; disp ( neg . complex , ”+ i ” , neg . real , ” N e g a t i o n r e s u l t f o r the f i r s t i s ”); // M u l t i p l i c a t i o n mul = struct ( ’ r e a l ’ , x1 * x3 - x2 * x4 , ’ c o m p l e x ’ , x2 * x3 + x4 * x1 ) ; disp ( mul . complex , ”+ i ” , mul . real , ” M u l t i p l i c a t i o n r e s u l t i s ”); endfunction x1 =3; x2 =5; x3 =5; 15

24 25

x4 =6; complexmanu ( x1 , x2 , x3 , x4 ) ;

Scilab code Exa 1.3.6 Adding Substracting and multiplying Rational Nos 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

// E x e r c i s e 1 . 3 // Example 1 . 3 . 6 // Adding , S u b t r a c t i n g and m u l t i p l y i n g R a t i o n a l Numbers function []= rational ( x1 , x2 , x3 , x4 ) rational1 = struct ( ’ n u m e r a t o r ’ ,x1 , ’ d e n o m i n a t o r ’ , x2 ) ; disp ( rational1 ) ; rational2 = struct ( ’ n u m e r a t o r ’ ,x3 , ’ d e n o m i n a t o r ’ , x4 ) ; disp ( rational2 ) ; //Add x5 = int32 ([ x2 x4 ]) ; x5 = lcm ( x5 ) ; x6 = x1 *( x5 / x2 ) + x3 *( x5 / x4 ) ; rational3 = struct ( ’ n u m e r a t o r ’ ,x6 , ’ d e n o m i n a t o r ’ , x5 ) ; disp ( rational3 , ” A f t e r a d d i t i o n ” ) ; // s u b t r a c t x6 = x1 *( x5 / x2 ) - x3 *( x5 / x4 ) rational4 = struct ( ’ n u m e r a t o r ’ ,x6 , ’ d e n o m i n a t o r ’ , x5 ) ; disp ( rational4 , ” A f t e r S u b t r a c t i o n ” ) ; // M u l t i p l y x7 = x1 * x3 ; x8 = x2 * x4 ; rational5 = struct ( ’ n u m e r a t o r ’ ,x7 , ’ d e n o m i n a t o r ’ , x8 ) ; disp ( rational5 , ” A f t e r m u l t i p l i c a t i o n ” ) ; endfunction x1 =43; x2 =32; x3 =233; x4 =33; rational ( x1 , x2 , x3 , x4 ) ; 16

Scilab code Exa 1.3.7 Checking Equality Of 2 Rational Numbers 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

// E x e r c i s e 1 . 3 // Example 1 . 3 . 7 // C h e c k i n g E q u a l i t y Of 2 R a t i o n a l Numbers Without R e d u c i n g Them function []= rational_equal ( x1 , x2 , x3 , x4 ) rational1 = struct ( ’ n u m e r a t o r ’ ,x1 , ’ d e n o m i n a t o r ’ , x2 ) ; disp ( rational1 ) ; rational2 = struct ( ’ n u m e r a t o r ’ ,x3 , ’ d e n o m i n a t o r ’ , x4 ) ; disp ( rational2 ) ; if ( x1 * x4 == x2 * x3 ) disp ( ” Equal ” ) ; break ; else disp ( ” Not Equal ” ) ; break ; end endfunction // C a l l i n g R o u t i n e : x1 =32; x2 =45; x3 =43; x4 =55; rational_equal ( x1 , x2 , x3 , x4 ) ;

Scilab code Exa 1.4 Raising the salary of employee 1 2 3

// S o l v e d Example 6 //To R a i s e The s a l a r y o f an e m p l o y e e function [ employee1 ]= raise ( employee , n ) // e m p l o y e e i s the l i s t of employees 17

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

for i =1: n if ( employee ( i ) (1) . year <=2000) employee ( i ) (2) = employee ( i ) (2) *1.1; else employee ( i ) (2) = employee ( i ) (2) *1.05; end end employee1 = employee ; disp ( ” A f t e r R a i s i n g ” ) ; for i =1: n printf ( ” Employee no %d\n ” ,i ) ; disp ( employee ( i ) (1) ) ; disp ( employee ( i ) (2) ) ; end

endfunction // C a l l i n g R o u t i n e : datehired = struct ( ’ y e a r ’ ,1993 , ’ month ’ ,12) ; employee1 = list ( datehired ,14000) ; datehired = struct ( ’ y e a r ’ ,1998 , ’ month ’ ,12) ; employee2 = list ( datehired ,17000) ; datehired = struct ( ’ y e a r ’ ,2003 , ’ month ’ ,12) ; employee3 = list ( datehired ,25000) ; datehired = struct ( ’ y e a r ’ ,2002 , ’ month ’ ,12) ; employee4 = list ( datehired ,35000) ; datehired = struct ( ’ y e a r ’ ,2006 , ’ month ’ ,12) ; employee5 = list ( datehired ,13000) ; employee = list ( employee1 , employee2 , employee3 , employee4 , employee5 ) ; 32 employee = raise ( employee ,5)

Scilab code Exa 1.5 Reducing the given rational number 1 2

// S o l v e d Example 7 : // R e d u c i n g The Given R a t i o n a l Number 18

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

funrot (0) function [ y ]= reduce ( nm , dn ) rational1 = struct ( ’ n u m e r a t o r ’ ,nm , ’ d e n o m i n a t o r ’ , dn ) y =0 if ( rational1 . numerator > rational1 . denominator ) a = rational1 . numerator ; b = rational1 . denominator ; else a = rational1 . denominator ; b = rational1 . numerator ; end while ( b ~=0) rem = modulo (a , b ) ; a=b; b = rem ; end y = struct ( ’ n u m e r a t o r ’ , nm /a , ’ d e n o m i n a t o r ’ , dn / a ) ; disp ( y ) ; endfunction nm =22; dn =44; y = reduce ( nm , dn )

Scilab code Exa 1.6 Equality check of 2 rational nos by reduction 1 2 3 4 5 6 7 8 9

// S o l v e d Example 8 : // C h e c k i n g f o r t h e e q u a l i t y o f 2 r a t i o n a l numbers by r e d u c i n g them function []= equal ( x1 , x2 , x3 , x4 ) rational1 = struct ( ’ n u m e r a t o r ’ ,x1 , ’ d e n o m i n a t o r ’ , x2 ) rational2 = struct ( ’ n u m e r a t o r ’ ,x3 , ’ d e n o m i n a t o r ’ , x4 ) y =0 if ( rational1 . numerator > rational1 . denominator ) a = rational1 . numerator ; b = rational1 . denominator ; 19

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

else a = rational1 . denominator ; b = rational1 . numerator ; end while ( b ~=0) rem = modulo (a , b ) ; a=b; b = rem ; end y = struct ( ’ n u m e r a t o r ’ , x1 /a , ’ d e n o m i n a t o r ’ , x2 / a ) ; y1 =0 if ( rational2 . numerator > rational2 . denominator ) a = rational2 . numerator ; b = rational2 . denominator ; else a = rational2 . denominator ; b = rational2 . numerator ; end while ( b ~=0) rem = modulo (a , b ) ; a=b; b = rem ; end y1 = struct ( ’ n u m e r a t o r ’ , x3 /a , ’ d e n o m i n a t o r ’ , x4 / a ) ; if ( y == y1 ) disp ( ” Equal ” ) break ; else disp ( ” Not Equal ” ) break ; end endfunction x1 =5; x2 =7; x3 =35; x4 =49; equal ( x1 , x2 , x3 , x4 ) ;

20

Chapter 2 Stacks

Scilab code Exa 2.1 To determine the syntacticaly valid string 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

// S o l v e d Example 1 //To d e t e r m i n e t h e s y n t a c t i c a l y v a l i d s t r i n g function [ l ]= strlen ( x ) i =1; l =0; [j , k ]= size ( x ) for i =1: k l = l + length ( x ( i ) ) ; end endfunction function []= stringvalid ( str ) str = string ( str ) ; stack = struct ( ’ a ’ , ’ 0 ’ , ’ t o p ’ ,0) ; l1 = strlen ( str ) ; valid =1; l =1; while (l <= l1 ) if ( str ( l ) == ’ ( ’ | str ( l ) == ’ [ ’ | str ( l ) == ’ { ’ ) if ( stack . top ==0) stack . a = str ( l ) ; stack . top = stack . top +1; 21

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

else stack . a =[ stack . a (: ,:) str ( l ) ]; stack . top = stack . top +1; end end if ( str ( l ) == ’ ) ’ | str ( l ) == ’ ] ’ | str ( l ) == ’ } ’ ) if ( stack . top ==0) valid =0; break ; else i = stack . a ( stack . top ) ; stack . top = stack . top -1; symb = str ( l ) ; if ((( symb == ’ ) ’ ) &( i == ’ ( ’ ) ) |(( symb == ’ ] ’ ) &( i == ’ [ ’ ) ) |(( symb == ’ } ’ ) &( i == ’ { ’ ) ) ) else valid =0; break ; end end end l = l +1; end if ( stack . top ~=0) valid =0; end if ( valid ==0) disp ( ” I n v a l i d S t r i n g ” ) ; else disp ( ” V a l i d S t r i n g ” ) ; end endfunction // C a l l i n g R o u t i n e : stringvalid ([ ’H ’ ’E ’ ’ L ’ ’ L ’ ’O ’ ])

22

Scilab code Exa 2.1.2 To determine the syntacticaly valid string 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// S o l v e d Example 1 //To d e t e r m i n e t h e s y n t a c t i c a l y v a l i d s t r i n g function [ l ]= strlen ( x ) i =1; l =0; [j , k ]= size ( x ) for i =1: k l = l + length ( x ( i ) ) ; end endfunction function []= stringvalid ( str ) str = string ( str ) ; stack = struct ( ’ a ’ , ’ 0 ’ , ’ t o p ’ ,0) ; l1 = strlen ( str ) ; valid =1; l =1; while (l <= l1 ) if ( str ( l ) == ’ ( ’ | str ( l ) == ’ [ ’ | str ( l ) == ’ { ’ ) if ( stack . top ==0) stack . a = str ( l ) ; stack . top = stack . top +1; else stack . a =[ stack . a (: ,:) str ( l ) ]; stack . top = stack . top +1; end disp ( stack ) ; end if ( str ( l ) == ’ ) ’ | str ( l ) == ’ ] ’ | str ( l ) == ’ } ’ ) if ( stack . top ==0) valid =0; break ; else i = stack . a ( stack . top ) ; b = stack . a (1) ; for i1 =2: stack . top -1 b =[ b (: ,:) stack . a ( i1 ) ] 23

37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

end stack . a = b ; stack . top = stack . top -1; symb = str ( l ) ; disp ( stack ) ; if ((( symb == ’ ) ’ ) &( i == ’ ( ’ ) ) |(( symb == ’ ] ’ ) &( i = ’ [ ’ ) ) |(( symb = ’ } ’ ) &( i = ’ { ’ ) ) ) else valid =0; break ; end end end l = l +1; end if ( stack . top ~=0) valid =0; end if ( valid ==0) disp ( ” I n v a l i d S t r i n g ” ) ; else disp ( ” V a l i d S t r i n g ” ) ; end endfunction // C a l l i n g R o u t i n e : stringvalid ([ ’ ( ’ ’A ’ ’+ ’ ’B ’ ’ } ’ ’ ) ’ ]) stringvalid ([ ’ { ’ ’ [ ’ ’A ’ ’+ ’ ’B ’ ’ ] ’ ’− ’ ’ [ ’ ’ ( ’ ’C ’ ’− ’ ’D ’ ’ ) ’ ’ ] ’ ]) stringvalid ([ ’ ( ’ ’A ’ ’+ ’ ’B ’ ’ ) ’ ’− ’ ’ { ’ ’C ’ ’+ ’ ’ D ’ ’ } ’ ’− ’ ’ [ ’ ’ F ’ ’+ ’ ’G ’ ’ ] ’ ]) stringvalid ([ ’ ( ’ ’ ( ’ ’H ’ ’ ) ’ ’ ∗ ’ ’ { ’ ’ ( ’ ’ [ ’ ’ J ’ ’ + ’ ’K ’ ’ ] ’ ’ ) ’ ’ } ’ ’ ) ’ ]) stringvalid ([ ’ ( ’ ’ ( ’ ’ ( ’ ’A ’ ’ ) ’ ’ ) ’ ’ ) ’ ])

Scilab code Exa 2.2 Implementing Stack using union 24

1 // S o l v e d Example 2 : 2 // I m p l e m e n t i n g S t a c k u s i n g u n i o n : 3 function [ stack ]= sta_union ( etype , a ) 4 stackelement = struct ( ’ e t y p e ’ , etype ) ; 5 [k , l ]= size ( a ) ; 6 select stackelement . etype , 7 case ’ i n t ’ then 8 a = int32 ( a ) ; 9 stack = struct ( ’ t o p ’ ,l , ’ i t e m s ’ ,a ) ; , 10 case ’ f l o a t ’ then 11 a = double ( a ) ; 12 stack = struct ( ’ t o p ’ ,l , ’ i t e m s ’ ,a ) ; , 13 case ’ c h a r ’ then 14 a = string ( a ) ; 15 stack = struct ( ’ t o p ’ ,l , ’ i t e m s ’ ,a ) ; , 16 end 17 disp ( stack , ” S t a c k i s : ” ) ; 18 endfunction 19 a =[32 12.34 232 32.322] 20 stack = sta_union ( ’ f l o a t ’ ,a ) 21 stack = sta_union ( ’ i n t ’ ,a ) 22 stack = sta_union ( ’ c h a r ’ ,a )

Scilab code Exa 2.2.3 Check if string is of certain form 1 2 3 4 5 6 7 8 9 10

function [ l ]= strlen ( x ) i =1; l =0; [j , k ]= size ( x ) for i =1: k l = l + length ( x ( i ) ) ; end endfunction function []= str ( st ) stack = struct ( ’ a ’ ,0 , ’ t o p ’ ,0) ; 25

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

st = string ( st ) ; l =1; l1 = strlen ( st ) ; symb = st ( l ) ; valid =1; while (l < l1 ) while ( symb ~= ’C ’ ) if ( stack . top ==0) stack . a = st ( l ) ; stack . top = stack . top +1; else stack . a =[ stack . a (: ,:) st ( l ) ]; stack . top = stack . top +1; end l = l +1; symb = st ( l ) ; end i = st ( l +1) ; if ( stack . top ==0) valid =0; break ; else symb1 = stack . a ( stack . top ) ; stack . top = stack . top -1; if ( i ~= symb1 ) valid =0; break ; end end l = l +1; end if ( stack . top ~=0) valid =0; end if ( valid ==0) disp ( ” Not o f t h e g i v e n f o r m a t ” ) ; else disp ( ” S t r i n g Of t h e Given Format ” ) ; 26

49 50 51 52 53 54 55

end endfunction // C a l l i n g R o u t i n e : st =[ ’A ’ ’A ’ ’B ’ ’A ’ ’C ’ ’A ’ ’B ’ ’A ’ ’A ’ ] str ( st ) st =[ ’A ’ ’A ’ ’B ’ ’A ’ ’C ’ ’A ’ ’B ’ ’A ’ ] str ( st )

Scilab code Exa 2.3 Implementing Push And Pop Functions 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

// S o l v e d Example 3 : // I m p l e m e n t i n g Push And Pop F u n c t i o n s : function [y , sta1 ]= empty ( sta ) y =0; sta1 =0; if ( sta . top ==0) y =0; else y =1; end sta1 = sta endfunction function [ sta ]= push ( stac , ele ) sta =0; if ( empty ( stac ) ==0) stac . a = ele ; stac . top = stac . top +1; else stac . a =[ stac . a (: ,:) ele ] stac . top = stac . top +1; end disp ( stac ) ; sta = stac ; endfunction 27

26 27 function [ ele , sta ]= pop ( stack ) 28 ele = ’−1 ’ ; 29 if ( empty ( stack ) ==0) 30 disp ( ” S t a c k U n d e r f l o w ” ) ; 31 break ; 32 else 33 ele = stack . a ( stack . top ) ; 34 stack . top = stack . top -1; 35 if ( stack . top ~=0) 36 b = stack . a (1) ; 37 for i2 =2: stack . top 38 b =[ b (: ,:) stack . a ( i2 ) ]; 39 end 40 stack . a = b ; 41 else 42 stack . a = ’ 0 ’ ; 43 end 44 end 45 disp ( stack ) ; 46 sta = stack ; 47 endfunction 48 global stack 49 // C a l l i n g R o u t i n e : 50 stack = struct ( ’ a ’ ,0 , ’ t o p ’ ,0) ; 51 stack = push ( stack ,4) ; 52 stack = push ( stack ,55) ; 53 stack = push ( stack ,199) ; 54 stack = push ( stack ,363) ; 55 [ ele , stack ]= pop ( stack ) ; 56 disp ( stack , ” A f t e r t h e a b o v e o p e r a t i o n s

s t a c k i s : ”);

Scilab code Exa 2.4 Convering an infix expression to a Postfix Express 1

// S o l v e d Example 5 : 28

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

// C o n v e r i n g an i n f i x e x p r e s s i o n t o a P o s t f i x Expression : function [ sta ]= push ( stac , ele ) sta =0; if ( stac . top ==0) stac . a = ele ; stac . top = stac . top +1; else stac . a =[ stac . a (: ,:) ele ] stac . top = stac . top +1; end disp ( stac ) ; sta = stac ; endfunction function [ ele , sta ]= pop ( stack ) ele = ’−1 ’ ; if ( stack . top ==0) disp ( ” S t a c k U n d e r f l o w ” ) ; break ; else ele = stack . a ( stack . top ) ; stack . top = stack . top -1; if ( stack . top ~=0) b = stack . a (1) ; for i2 =2: stack . top b =[ b (: ,:) stack . a ( i2 ) ]; end stack . a = b ; else stack . a = ’ 0 ’ ; end end sta = stack ; endfunction function [ l ]= strlen ( x ) i =1; l =0; 29

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

[j , k ]= size ( x ) for i =1: k l = l + length ( x ( i ) ) ; end endfunction function [ p ]= pre ( s1 , s2 ) i1 =0; select s1 , case ’+ ’ then i1 =5; case ’− ’ then i1 =5; case ’ ∗ ’ then i1 =9; case ’ / ’ then i1 =9; end i2 =0; select s2 , case ’+ ’ then i2 =5; case ’− ’ then i2 =5; case ’ ∗ ’ then i2 =9; case ’ / ’ then i2 =9; end p =0; p = i1 - i2 ; if ( s1 == ’ ( ’ ) p = -1; end if ( s2 == ’ ( ’ & s1 ~= ’ ) ’ ) p = -1; end if ( s1 ~= ’ ( ’ & s2 == ’ ) ’ ) p =1; end endfunction function [ a2 ]= intopo ( a1 , n ) stack = struct ( ’ a ’ ,0 , ’ t o p ’ ,0) ; l1 =1; l2 = strlen ( a1 (1) ) for i =2: n 30

77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113

l2 = l2 + strlen ( a1 ( i ) ) end a2 = list () ; while ( l1 <= l2 ) symb = a1 ( l1 ) ; if ( isalphanum ( string ( a1 ( l1 ) ) ) ) a2 = list ( a2 , symb ) ; else while ( stack . top ~=0&( pre ( stack . a ( stack . top ) , symb ) >=0) ) [ topsymb , stack ]= pop ( stack ) ; if ( topsymb == ’ ) ’ | topsymb == ’ ( ’ ) a2 = a2 ; else a2 = list ( a2 , topsymb ) ; end end if ( stack . top ==0| symb ~= ’ ) ’ ) stack = push ( stack , symb ) ; else [ ele , stack ]= pop ( stack ) ; end end l1 = l1 +1; end while ( stack . top ~=0) [ topsymb , stack ]= pop ( stack ) ; if ( topsymb == ’ ) ’ | topsymb == ’ ( ’ ) a2 = a2 ; else a2 = list ( a2 , topsymb ) ; end end disp ( a2 ) ; endfunction // C a l l i n g R o u t i n e : a1 =[ ’ ( ’ ’ 2 ’ ’+ ’ ’ 3 ’ ’ ) ’ ’ ∗ ’ ’ ( ’ ’ 5 ’ ’− ’ ’ 4 ’ ’ ) ’ ] a2 = intopo ( a1 ,11) 31

32

Chapter 3 Recursion

Scilab code Exa 3.1 Multiplication of 2 numbers 1 // M u l t i p l i c a t i o n o f 2 numbers 2 funrot (0) 3 function [ val ]= mul (a , b ) 4 if ( b ==1) 5 val = a ; 6 else 7 val = a + mul (a ,b -1) ; 8 end 9 endfunction 10 // C a l l i n g R o u t i n e : 11 a =4; 12 b =3; 13 val = mul (4 ,3) 14 printf ( ” P r o d u c t o f %d and %d i s %d” ,a ,b , val ) ;

Scilab code Exa 3.2 Factorial of a number 1

// F u n c t i o n To C a l u c u l a t e f a c t o r i a l o f a g i v e n number 33

2 function [ value ]= fact ( a ) 3 value = -1; 4 if (a <0| a >170) 5 disp ( ” I n v a l i d v a l u . ” ) ; 6 break ; 7 else 8 if ( a ==1| a ==0) 9 value =1; 10 else 11 value = a * fact (a -1) ; 12 end 13 end 14 endfunction 15 // C a l l i n g R o u t i n e : 16 a =5; 17 val = fact ( a ) ; 18 printf ( ”%d f a c t o r i a l i s %d” ,a , val ) ;

Scilab code Exa 3.3 Fibbonacci series 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

function [ fib ]= fibbo ( n ) fib = -1; if (n <0) disp ( ” I n v a l i d Entry ” ) ; else if (n <=1) fib = n ; else fib = fibbo (n -1) + fibbo (n -2) ; end end endfunction function [ l ]= fibbon ( n ) x =0; 34

16 l =( fibbo (0) ) ; 17 for x =1: n -1 18 l =[ l (: ,:) , fibbo ( x ) ]; 19 end 20 disp ( l ) ; 21 endfunction 22 // C a l l i n g R o u t i n e : 23 n =5; 24 l = fibbon ( n )

Scilab code Exa 3.4 Binary Search 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

function [ b ]= bsear (a ,l ,u , n ) if (l > u ) b = -1; else mid = int32 (( l + u ) /2) ; if ( n == a ( mid ) ) b=n; else if (n > a ( mid ) ) mid = int32 (( l + u ) /2) ; b = bsear (a , mid +1 ,u , n ) ; else mid = int32 (( l + u ) /2) ; b = bsear (a ,l , mid -1 , n ) ; end end end endfunction function [ b ]= bsearc (a ,l ,u , n ) b = bsear (a ,l ,u , n ) ; if ( b == -1) disp ( ” The e l e m e n t i s n o t t h e r e ” ) ; 35

24 end 25 if ( b == n ) 26 disp ( ” The e l e m e n t i s t h e r e ” ) ; 27 end 28 endfunction 29 // C a l l i n g R o u t i n e : 30 a =[12 122 3233 12121] // Must be s o r t e d : 31 b = bsearc (a ,1 ,4 ,12)

Scilab code Exa 3.5 Tower Of Hanoi 1 function []= towe (n , from , to , aux ) 2 if ( n ==1) ; 3 disp ( to , ” t o ” , from , ”Move peg 1 from ” ) ; 4 else 5 towe (n -1 , from , aux , to ) ; 6 disp ( to , ” t o ” , from , ” from ” ,n , ”Move Peg ” ) ; 7 towe (n -1 , aux , to , from ) ; 8 end 9 endfunction 10 11 function []= tower ( from , to , aux ) 12 n = input ( ” E n t e r n” ) ; 13 towe (n , from , to , aux ) ; 14 endfunction 15 // C a l l i n g R o u t i n e : 16 n =3 // Number o f d i s k s 17 towe (n , ’ a ’ , ’ b ’ , ’ c ’ )

Scilab code Exa 3.6 Prefix To Postfix Conversion 1 2

funrot (0) function [ y ]= find1 ( g ) 36

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

length1 = strlen ( g ) ; if ( length1 ==0) y =0; else if ( isalphanum ( g (1) ) ) y =1; else if ( length1 <2) y =0; else s = strsplit (g ,1) ; s = s (2) ; m = find1 ( s ) ; if ( m ==0| length1 == m ) y =0; else e = strsplit (g , m +1) ; e = e (2) ; n = find1 ( e ) ; if ( n ==0) y =0; else y = m + n +1; end end end end end endfunction function [ l ]= strlen ( x ) i =1; l =0; [j , k ]= size ( x ) for i =1: k l = l + length ( x ( i ) ) ; end endfunction function [ po ]= pr2po ( pr ) 37

41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

length1 = strlen ( pr ) ; if ( length1 ==1) if ( isalphanum ( pr ) ) po (1) = pr (1) ; else disp ( ” I n v a l i d s t r i n g \n ” ) ; end else s = strsplit ( pr ,1) ; g = s (2) ; m = find1 ( g ) ; s = strsplit ( pr , m +1) ; g1 = s (2) ; n = find1 ( g1 ) ; f = strsplit ( pr ,1) ; c = f (1) ; if (( c ~= ’+ ’ & c ~= ’− ’ & c ~= ’ / ’ & c ~= ’ ∗ ’ ) | m ==0| n ==0| m + n +1~= length1 ) printf ( ” I n v a l i d s t r i n g \n ” ) ; else s = strsplit ( pr ,1) ; s = strsplit ( s (2) ,m ) ; opnd1 = s (1) ; s = strsplit ( pr , m +1) ; opnd2 = s (2) ; post1 = pr2po ( opnd1 ) ; post2 = pr2po ( opnd2 ) ; post =[ post1 (: ,:) post2 (: ,:) ] f = strsplit ( pr ,1) ; c = f (1) ; post3 =[ post (: ,:) c ]; po = post3 ; end end endfunction // C a l l i n g R o u t i n e : s1 = ”+−∗abcd ” ; // no s p a c e s b e t w e e n 38

78 79 80 81 82

po = pr2po ( s1 ) ; disp ( po , ” p o s t f i x i s ” ) ; s1 = ”+−∗/+−∗/ a b c d e f g h i ” po = pr2po ( s1 ) ; disp ( po , ” p o s t f i x i s ” ) ;

Scilab code Exa 3.7 Simulating Factorial By Non recursion 1 2 function []= simu_fact ( n ) ; 3 a =1; 4 while (n >0) 5 a=a*n; 6 n =n -1; 7 end 8 disp (a , ” F a c t o r i a l i s ” ) ; 9 endfunction 10 // C a l l i n g R o u t i n e : 11 a =9 12 simu_fact ( a )

39

Chapter 4 Queues and linked list

Scilab code Exa 4.1 Implementing Singly Connected Linked List 1 2 3

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

//SINGLY CONNECTED LINKED LIST : function [ link2 ]= append ( ele , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; if ( link1 (1) (1) . add ==0) link1 (1) (1) . data = ele ; link1 (1) (1) . add =1; link1 (1) (1) . nexadd =0; link2 (1) = link1 (1) (1) ; else if ( link1 (1) (1) . nexadd ==0) lin2 = link1 (1) (1) ; lin2 . data = ele ; lin2 . add = link1 (1) (1) . add +1; link1 (1) (1) . nexadd = lin2 . add ; lin2 . nexadd =0; link2 (1) = link1 (1) (1) ; link2 (2) = lin2 ; else lin2 = link1 (1) (1) ; 40

20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

42 43 44 45 46 47 48 49 50 51 52 53 54 55

i =1; while ( link1 ( i ) (1) . nexadd ~=0) i = i +1; end j=i; lin2 . data = ele ; lin2 . add = link1 ( i ) . add +1; lin2 . nexadd =0; link1 ( i ) . nexadd = lin2 . add ; link2 (1) = link1 (1) (1) ; i =2; while ( link1 ( i ) . nexadd ~= lin2 . add ) link2 ( i ) =( link1 ( i ) ) ; i = i +1; end link2 ( i ) = link1 ( i ) ; link2 ( i +1) = lin2 ; end end endfunction function [ link2 ]= add ( ele , pos , link1 ) ; link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; while (i <= pos ) if ( link1 ( i ) . nexadd ==0) break ; else i = i +1; end end if ( link1 ( i ) . nexadd ~=0) i =i -1; lin2 . data = ele ; lin2 . add = i ; j=i; while ( link1 ( j ) . nexadd ~=0) 41

56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93

link1 ( j ) . add = link1 ( j ) . add +1; link1 ( j ) . nexadd = link1 ( j ) . nexadd +1; j = j +1; end link1 ( j ) . add = link1 ( j ) . add +1; lin2 . nexadd = link1 ( i ) . add ; link1 (i -1) . nexadd = lin2 . add ; k =1; while (k < i ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; k = k +1; link2 ( k ) = link1 (k -1) ; k = k +1 l =k -1; while ( k ~= j ) link2 ( k ) = link1 ( l ) ; k = k +1; l = l +1; end link2 ( j ) = link1 (j -1) ;; link2 ( j +1) = link1 ( j ) ; else if ( i == pos & i ~=1) k =1; lin2 . data = ele ; lin2 . add = link1 (i -1) . add +1; link1 ( i ) . add = link1 ( i ) . add +1; lin2 . nexadd = link1 ( i ) . add ; k =1; while (k < pos ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; link2 ( k +1) = link1 ( k ) 42

94 95 96 97 98 99 100 101 102

103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129

end if ( i == pos & i ==1) link2 = append ( ele , link1 ) ; return link2 ; end end endfunction function [ link2 ]= delete1 ( pos , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; while (i <= pos ) if (( link1 ( i ) . nexadd ==0) ) break ; else i = i +1; end end if ( link1 ( i ) . nexadd ~=0) i =i -1; j =1; if ( i ==1) j =1; while ( link1 ( j ) . nexadd ~=0) link2 ( j ) = link1 ( j ) ; j = j +1; end link2 ( j ) = link1 ( j ) ; else link1 (i -1) . nexadd = link1 ( i +1) . add ; while ( link1 ( j ) . nexadd ~= link1 ( i +1) . add ) link2 ( j ) = link1 ( j ) ; j = j +1; end if ( j ~= i -1) link2 ( j ) = link1 ( j ) ; link2 ( j +1) = link1 ( j +1) ; 43

130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165

k = i +1; l =2; else link2 ( j ) = link1 ( j ) ; k = i +1; l =1; end while ( link1 ( k ) . nexadd ~=0) link2 ( j + l ) = link1 ( k ) ; k = k +1; l = l +1; end link2 ( j + l ) = link1 ( k ) ; end else if ( i == pos ) j =1; link1 (i -1) . nexadd =0; while (j <= i -1) link2 ( j ) = link1 ( j ) ; j = j +1; end end end endfunction

// C a l l i n g R o u t i n e : link1 = struct ( ’ d a t a ’ ,0 , ’ add ’ ,0 , ’ nexadd ’ ,0) ; // C r e a t e s empty l i s t link1 = append (4 , link1 ) link1 = append (6 , link1 ) link1 = add (7 ,2 , link1 ) link1 = append (8 , link1 ) link1 = delete1 (4 , link1 ) disp ( link1 , ” The l i n k e d l i s t a f t e r t h e a b o v e m o d i f i c a t i o n s i s : ”); 44

Scilab code Exa 4.2 Implementing Queue Operarions 1 // Queue Operations 2 function [ q2 ]= push ( ele , q1 ) 3 if ( q1 . rear == q1 . front ) 4 q1 . a = ele ; 5 q1 . rear = q1 . rear +1; 6 else 7 q1 . a =[ q1 . a (: ,:) ele ]; 8 q1 . rear = q1 . rear +1; 9 end 10 q2 = q1 ; 11 endfunction 12 function [ ele , q2 ]= pop ( q1 ) 13 ele = -1; 14 q2 =0; 15 if ( q1 . rear == q1 . front ) 16 disp ( ” Queue U n d e r f l o w ” ) ; 17 return ; 18 else 19 ele = q1 . a ( q1 . rear - q1 . front ) ; 20 q1 . front = q1 . front +1; 21 i =1; 22 a = q1 . a (1) ; 23 for i =2:( q1 . rear - q1 . front ) 24 a =[ a (: ,:) q1 . a ( i ) ]; 25 end 26 q1 . a = a ; 27 end 28 q2 = q1 ; 29 endfunction 30 // C a l l i n g R o u t i n e : 31 q1 = struct ( ’ a ’ ,0 , ’ r e a r ’ ,0 , ’ f r o n t ’ ,0) 32 q1 = push (3 , q1 )

45

33 34 35 36 37 38 39 40 41

q1 = push (22 , q1 ) ; q1 = push (21 , q1 ) ; disp ( q1 , ” Queue a f t e r i n s e r t i o n ” ) ; [ ele , q1 ]= pop ( q1 ) disp ( ele , ” poped e l e m e n t ” ) ; disp ( q1 , ” Queue a f t e r p o p i n g ” ) ; [ ele , q1 ]= pop ( q1 ) ; [ ele , q1 ]= pop ( q1 ) ; [ ele , q1 ]= pop ( q1 ) ; // U n d e r f l o w C o n d i t i o n

Scilab code Exa 4.3 Implementing Circular Linked List 1 2 3

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

//CIRCULAR LINKED LIST function [ link2 ]= append ( ele , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; if ( link1 (1) (1) . add ==0) link1 (1) (1) . data = ele ; link1 (1) (1) . add =1; link1 (1) (1) . nexadd =1; link2 (1) = link1 (1) (1) ; else if ( link1 (1) (1) . nexadd == link1 (1) (1) . add ) lin2 = link1 (1) (1) ; lin2 . data = ele ; lin2 . add = link1 (1) (1) . add +1; link1 (1) (1) . nexadd = lin2 . add ; lin2 . nexadd = link1 (1) (1) . add ; link2 (1) = link1 (1) (1) ; link2 (2) = lin2 ; else lin2 = link1 (1) (1) ; i =1; while ( link1 ( i ) (1) . nexadd ~= link1 (1) (1) . add ) 46

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

i = i +1; end j=i; lin2 . data = ele ; lin2 . add = link1 ( i ) . add +1; lin2 . nexadd = link1 (1) (1) . add ; link1 ( i ) . nexadd = lin2 . add ; link2 (1) = link1 (1) (1) ; i =2; while ( link1 ( i ) . nexadd ~= lin2 . add ) link2 ( i ) =( link1 ( i ) ) ; i = i +1; end link2 ( i ) = link1 ( i ) ; link2 ( i +1) = lin2 ; end end endfunction function [ link2 ]= add ( ele , pos , link1 ) ; link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; while (i <= pos ) if ( link1 ( i ) . nexadd == link1 (1) (1) . add ) break ; else i = i +1; end end if ( link1 ( i ) . nexadd ~= link1 (1) (1) . add ) i =i -1; lin2 . data = ele ; lin2 . add = i ; j=i; while ( link1 ( j ) . nexadd ~= link1 (1) (1) . add ) link1 ( j ) . add = link1 ( j ) . add +1; link1 ( j ) . nexadd = link1 ( j ) . nexadd +1; 47

58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95

j = j +1; end link1 ( j ) . add = link1 ( j ) . add +1; lin2 . nexadd = link1 ( i ) . add ; link1 (i -1) . nexadd = lin2 . add ; k =1; while (k < i ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; k = k +1; link2 ( k ) = link1 (k -1) ; k = k +1 l =k -1; while ( k ~= j ) link2 ( k ) = link1 ( l ) ; k = k +1; l = l +1; end link2 ( j ) = link1 (j -1) ;; link2 ( j +1) = link1 ( j ) ; else if ( i == pos ) k =1; lin2 . data = ele ; lin2 . add = link1 (i -1) . add +1; link1 ( i ) . add = link1 ( i ) . add +1; lin2 . nexadd = link1 ( i ) . add ; link1 ( i ) . nexadd = link1 (1) (1) . add ; k =1; while (k < pos ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; link2 ( k +1) = link1 ( k ) end 48

96 97 98 99 100

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

end endfunction function [ link2 ]= delete1 ( pos , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; j =1; while (i < pos ) if (( link1 ( j ) . nexadd == link1 (1) (1) . add ) ) j =1; i = i +1; else i = i +1; j = j +1; end end if ( link1 ( j ) . nexadd ~= link1 (1) (1) . add ) k =1; if ( j ==1) k =2; while ( link1 ( k ) . nexadd ~= link1 (1) (1) . add ) link2 (k -1) = link1 ( k ) ; k = k +1; end link2 (k -1) = link1 ( k ) ; link2 (k -1) . nexadd = link2 (1) . add ; else lin2 = link1 ( j ) ; link1 (j -1) . nexadd = link1 ( j +1) . add ; k =1; while ( link1 ( k ) . nexadd ~= link1 ( j +1) . add ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = link1 ( k ) ; k = k +2; 49

132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154

while ( link1 ( k ) . nexadd ~= link1 (1) (1) . add ) link2 (k -1) = link1 ( k ) ; k = k +1; end link2 (k -1) = link1 ( k ) ; end else link1 (j -1) . nexadd = link1 (1) (1) . add ; l =1; while ( link1 ( l ) . nexadd ~= link1 (1) (1) . add ) link2 ( l ) = link1 ( l ) ; l = l +1; end link2 ( l ) = link1 ( l ) ; end endfunction // C a l l i n g R o u t i n e : link1 = struct ( ’ d a t a ’ ,0 , ’ add ’ ,0 , ’ nexadd ’ ,0) ; link1 = append (4 , link1 ) ; // T h i s w i l l a c t u a l y c r e a t e a l i s t and 4 a s s t a r t link1 = append (6 , link1 ) ; link1 = add (10 ,2 , link1 ) ; link1 = delete1 (4 , link1 ) ; // As t h e l i s t i s c i r c u l a r t h e 4 ’ t h e l e m e n t r e f e r s t o a c t u a l y t h e 1 ’ s t one disp ( link1 , ” A f t e r t h e a b o v e m a n u p l a t i o n s t h e l i s t i s ”);

Scilab code Exa 4.4 Implementing Doubly connected Linked List //DOUBLE LINKED LIST : function [ link2 ]= append ( ele , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; 4 if ( link1 (1) (1) . add ==0) 1 2 3

50

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

link1 (1) (1) . data = ele ; link1 (1) (1) . add =1; link1 (1) (1) . nexadd =0; link1 (1) (1) . prevadd =0; link2 (1) = link1 (1) (1) ; else if ( link1 (1) (1) . nexadd ==0) lin2 = link1 (1) (1) ; lin2 . data = ele ; lin2 . add = link1 (1) (1) . add +1; link1 (1) (1) . nexadd = lin2 . add ; lin2 . nexadd =0; lin2 . prevadd = link1 (1) (1) . add ; link2 (1) = link1 (1) (1) ; link2 (2) = lin2 ; else lin2 = link1 (1) (1) ; i =1; while ( link1 ( i ) (1) . nexadd ~=0) i = i +1; end j=i; lin2 . data = ele ; lin2 . add = link1 ( i ) . add +1; lin2 . nexadd =0; link1 ( i ) . nexadd = lin2 . add ; lin2 . prevadd = link1 ( i ) . add ; link2 (1) = link1 (1) (1) ; i =2; while ( link1 ( i ) . nexadd ~= lin2 . add ) link2 ( i ) =( link1 ( i ) ) ; i = i +1; end link2 ( i ) = link1 ( i ) ; link2 ( i +1) = lin2 ; end end endfunction 51

43 44

45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

function [ link2 ]= add ( ele , pos , link1 ) ; link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; while (i <= pos ) if ( link1 ( i ) . nexadd ==0) break ; else i = i +1; end end if ( link1 ( i ) . nexadd ~=0) i =i -1; lin2 . data = ele ; lin2 . add = i ; j=i; while ( link1 ( j ) . nexadd ~=0) link1 ( j ) . prevadd = link1 ( j ) . prevadd +1; link1 ( j ) . add = link1 ( j ) . add +1; link1 ( j ) . nexadd = link1 ( j ) . nexadd +1; j = j +1; end link1 ( j ) . prevadd = link1 ( j ) . prevadd +1; link1 ( j ) . add = link1 ( j ) . add +1; lin2 . nexadd = link1 ( i ) . add ; link1 ( i ) . prevadd = lin2 . add ; lin2 . prevadd = link1 (i -1) . add ; link1 (i -1) . nexadd = lin2 . add ; k =1; while (k < i ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; k = k +1; link2 ( k ) = link1 (k -1) ; k = k +1 52

79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

109 110 111 112 113 114

l =k -1; while ( k ~= j ) link2 ( k ) = link1 ( l ) ; k = k +1; l = l +1; end link2 ( j ) = link1 (j -1) ;; link2 ( j +1) = link1 ( j ) ; else if ( i == pos ) k =1; lin2 . data = ele ; lin2 . add = link1 (i -1) . add +1; link1 ( i ) . add = link1 ( i ) . add +1; lin2 . nexadd = link1 ( i ) . add ; link1 ( i ) . prevadd = lin2 . add ; lin2 . prevadd = link1 (i -1) . add ; k =1; while (k < pos ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; link2 ( k +1) = link1 ( k ) end end endfunction function [ link2 ]= delete1 ( pos , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; while (i <= pos ) if (( link1 ( i ) . nexadd ==0) ) break ; else i = i +1; 53

115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152

end end if ( link1 ( i ) . nexadd ~=0) i =i -1; j =1; if ( i ==1) j =1; while ( link1 ( j ) . nexadd ~=0) link2 ( j ) = link1 ( j ) ; j = j +1; end link2 ( j ) = link1 ( j ) ; else link1 (i -1) . nexadd = link1 ( i +1) . add ; link1 ( i +1) . prevadd = link1 (i -1) . add ; while ( link1 ( j ) . nexadd ~= link1 ( i +1) . add ) link2 ( j ) = link1 ( j ) ; j = j +1; end if ( j ~= i -1) link2 ( j ) = link1 ( j ) ; link2 ( j +1) = link1 ( j +1) ; k = i +1; l =2; else link2 ( j ) = link1 ( j ) ; k = i +1; l =1; end while ( link1 ( k ) . nexadd ~=0) link2 ( j + l ) = link1 ( k ) ; k = k +1; l = l +1; end link2 ( j + l ) = link1 ( k ) ; end else if ( i == pos ) 54

153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168

j =1; link1 (i -1) . nexadd =0; while (j <= i -1) link2 ( j ) = link1 ( j ) ; j = j +1; end end end endfunction // C a l l i n g R o u t i n e : link1 = struct ( ’ d a t a ’ ,0 , ’ add ’ ,0 , ’ nexadd ’ ,0) ; link1 = append (4 , link1 ) ; link1 = append (6 , link1 ) ; link1 = add (10 ,2 , link1 ) ; link1 = delete1 (3 , link1 ) ; disp ( link1 , ” A f t e r t h e a b o v e m a n u p l a t i o n s t h e l i s t ”);

is

Scilab code Exa 4.5 Implementing Stack using circular Linked list 1 2 3 4

5 6 7 8 9 10 11 12 13

//STACK USING CIRCULAR LINKED LIST funrot (0) function [ link2 ]= append ( ele , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; if ( link1 (1) (1) . add ==0) link1 (1) (1) . data = ele ; link1 (1) (1) . add =1; link1 (1) (1) . nexadd =1; link2 (1) = link1 (1) (1) ; else if ( link1 (1) (1) . nexadd == link1 (1) (1) . add ) lin2 = link1 (1) (1) ; lin2 . data = ele ; 55

14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

43 44 45 46 47 48 49

lin2 . add = link1 (1) (1) . add +1; link1 (1) (1) . nexadd = lin2 . add ; lin2 . nexadd = link1 (1) (1) . add ; link2 (1) = link1 (1) (1) ; link2 (2) = lin2 ; else lin2 = link1 (1) (1) ; i =1; while ( link1 ( i ) (1) . nexadd ~= link1 (1) (1) . add ) i = i +1; end j=i; lin2 . data = ele ; lin2 . add = link1 ( i ) . add +1; lin2 . nexadd = link1 (1) (1) . add ; link1 ( i ) . nexadd = lin2 . add ; link2 (1) = link1 (1) (1) ; i =2; while ( link1 ( i ) . nexadd ~= lin2 . add ) link2 ( i ) =( link1 ( i ) ) ; i = i +1; end link2 ( i ) = link1 ( i ) ; link2 ( i +1) = lin2 ; end end endfunction function [ link2 ]= add ( ele , pos , link1 ) ; link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; while (i <= pos ) if ( link1 ( i ) . nexadd == link1 (1) (1) . add ) break ; else i = i +1; end 56

50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87

end if ( link1 ( i ) . nexadd ~= link1 (1) (1) . add ) i =i -1; lin2 . data = ele ; lin2 . add = i ; j=i; while ( link1 ( j ) . nexadd ~= link1 (1) (1) . add ) link1 ( j ) . add = link1 ( j ) . add +1; link1 ( j ) . nexadd = link1 ( j ) . nexadd +1; j = j +1; end link1 ( j ) . add = link1 ( j ) . add +1; lin2 . nexadd = link1 ( i ) . add ; link1 (i -1) . nexadd = lin2 . add ; k =1; while (k < i ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; k = k +1; link2 ( k ) = link1 (k -1) ; k = k +1 l =k -1; while ( k ~= j ) link2 ( k ) = link1 ( l ) ; k = k +1; l = l +1; end link2 ( j ) = link1 (j -1) ;; link2 ( j +1) = link1 ( j ) ; else if ( i == pos ) k =1; lin2 . data = ele ; lin2 . add = link1 (i -1) . add +1; link1 ( i ) . add = link1 . add +1; lin2 . nexadd = link1 ( i ) . add ; 57

88 89 90 91 92 93 94 95 96 97 98 99 100 101

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

link1 ( i ) . nexadd = link1 (1) (1) . add ; k =1; while (k < pos ) link2 ( k ) = link1 ( k ) ; k = k +1; end link2 ( k ) = lin2 ; link2 ( k +1) = link1 ( k ) end end endfunction function [ link2 ]= delete1 ( pos , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; if ( link1 (1) (1) . add ==0) disp ( ” I n v a l i d ” ) ; else if ( link1 (1) (1) . nexadd == link1 (1) (1) . add ) link1 (1) (1) . add =0; link1 (1) (1) . nexadd =0; link1 (1) (1) . data =0; link2 (1) = link1 (1) (1) ; else while (i <= pos ) if (( link1 ( i ) . nexadd == link1 (1) (1) . add ) ) break ; else i = i +1; end end if ( link1 ( i ) . nexadd ~= link1 (1) (1) . add ) i =i -1; j =1; if ( i ==1) j =1; 58

124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161

while ( link1 ( j ) . nexadd ~= link1 (1) (1) . add ) link2 ( j ) = link1 ( j ) ; j = j +1; end link2 ( j ) = link1 ( j ) ; else link1 (i -1) . nexadd = link1 ( i +1) . add ; while ( link1 ( j ) . nexadd ~= link1 ( i +1) . add ) link2 ( j ) = link1 ( j ) ; j = j +1; end if ( j ~= i -1) link2 ( j ) = link1 ( j ) ; link2 ( j +1) = link1 ( j +1) ; k = i +1; l =2; else link2 ( j ) = link1 ( j ) ; k = i +1; l =1; end while ( link1 ( k ) . nexadd ~= link1 (1) (1) . add ) link2 ( j + l ) = link1 ( k ) ; k = k +1; l = l +1; end link2 ( j + l ) = link1 ( k ) ; end else if ( i == pos ) j =1; link1 (i -1) . nexadd = link1 (1) (1) . add ; while (j <= i -1) link2 ( j ) = link1 ( j ) ; j = j +1; end end end 59

162 end 163 end 164 165 endfunction 166 function [ sta ]= push ( ele , stack ) 167 if ( stack . top ==0) 168 stack . a = ele ; 169 stack . top = stack . top +1; 170 sta = stack ; 171 else 172 i =1; 173 link1 = struct ( ’ d a t a ’ ,0 , ’ add ’ ,0 , ’ nexadd ’ ,0) ; 174 while (i <= stack . top ) 175 link1 = append ( stack . a ( i ) , link1 ) ; 176 i = i +1; 177 end 178 link1 = append ( ele , link1 ) ; 179 stack . top = stack . top +1; 180 a =[ stack . a (: ,:) link1 ( stack . top ) . data ]; 181 stack . a = a ; 182 sta = stack ; 183 end 184 endfunction 185 function [ ele , sta ]= pop ( stack ) 186 ele = -1; 187 sta =0; 188 if ( stack . top ==0) 189 disp ( ” S t a c k U n d e r f l o w ” ) ; 190 return ; 191 else 192 i =1; 193 link1 = struct ( ’ d a t a ’ ,0 , ’ add ’ ,0 , ’ nexadd ’ ,0) ; 194 while (i <= stack . top ) 195 link1 = append ( stack . a ( i ) , link1 ) ; 196 i = i +1; 197 end 198 ele = link1 ( stack . top ) . data ; 199 link1 = delete1 ( stack . top , link1 ) ;

60

200 stack . top = stack . top -1; 201 i =2; 202 a = link1 (1) (1) . data 203 while (i <= stack . top ) 204 a =[ a (: ,:) link1 ( i ) . data ]; 205 i = i +1; 206 end 207 stack . a = a ; 208 sta = stack ; 209 end 210 endfunction 211 function [ stack ]= empty () 212 stack = struct ( ’ a ’ ,0 , ’ t o p ’ ,0) ; 213 endfunction 214 // C a l l i n g R o u t i n e : 215 stack = empty () // C r e a t e an empty s t a c k 216 stack = push (4 , stack ) ; 217 stack = push (55 , stack ) ; 218 stack = push (199 , stack ) ; 219 stack = push (363 , stack ) ; 220 [ ele , stack ]= pop ( stack ) ; 221 disp ( stack , ” A f t e r t h e a b o v e o p e r a t i o n s

s t a c k i s : ”);

Scilab code Exa 4.6 Implementing Priority Queue Using Lists 1 2 3 4

5 6 7 8

// I m p l e m e n t i n g P r i o r i t y Queue U s i n g L i s t s funrot (0) function [ link2 ]= insert_pri ( ele , link1 ) link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; if ( link1 (1) (1) . add ==0) link1 (1) (1) . data = ele ; link1 (1) (1) . add =1; link1 (1) (1) . nexadd =1; 61

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

link2 (1) = link1 (1) (1) ; else if ( link1 (1) (1) . nexadd == link1 (1) (1) . add ) if ( ele >= link1 (1) (1) . data ) t = ele ; p = link1 (1) (1) . data ; else t = link1 (1) (1) . data ; p = ele ; end link1 (1) (1) . data = t ; lin2 = link1 (1) (1) ; lin2 . data = p ; lin2 . add =2; lin2 . nexadd = link1 (1) (1) . add ; link1 (1) (1) . nexadd = lin2 . add ; link2 (1) = link1 (1) (1) ; link2 (2) = lin2 ; else i =1; a =[]; while ( link1 ( i ) . nexadd ~= link1 (1) (1) . add ) a =[ a (: ,:) link1 ( i ) . data ]; i = i +1; end a =[ a (: ,:) link1 ( i ) . data ]; a = gsort ( a ) ; j =1; while (j <= i ) link1 ( j ) . data = a ( j ) ; j = j +1; end k =1; while ( link1 ( k ) . data >= ele ) if ( link1 ( k ) . nexadd == link1 (1) (1) . add ) break ; else link2 ( k ) = link1 ( k ) ; 62

47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

k = k +1; end end if ( link1 ( k ) . nexadd ~= link1 (1) (1) . add ) lin2 = link1 ( k ) ; lin2 . data = ele ; lin2 . add = link1 ( k ) . add ; j=k; y = link1 (1) (1) . add ; while ( link1 ( k ) . nexadd ~= y ) link1 ( k ) . add = link1 ( k ) . add +1; link1 ( k ) . nexadd = link1 ( k ) . nexadd +1; k = k +1; end link1 ( k ) . add = link1 ( k ) . add +1; lin2 . nexadd = link1 ( j ) . add ; link2 ( j ) = lin2 ; j = j +1; while (j <= k +1) link2 ( j ) = link1 (j -1) ; j = j +1; end else lin2 = link1 ( k ) ; lin2 . data = ele ; lin2 . nexadd = link1 (1) (1) . add ; lin2 . add = link1 ( k ) . add +1; link1 ( k ) . nexadd = lin2 . add ; j =1; while (j <= k ) link2 ( j ) = link1 ( j ) ; j = j +1; end link2 ( j ) = lin2 ; end end end endfunction 63

85 86

87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119

function [ ele , link2 ]= extract_min ( link1 ) ; link2 = list (0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 , ,0 ,0) ; i =1; ele = -1; if ( link1 (1) (1) . add ==0) disp ( ” U n d e r f l o w ” ) ; return ; else if ( link1 (1) (1) . nexadd == link1 (1) (1) . add ) link1 (1) (1) . add =0; link1 (1) (1) . nexadd =0; ele = link1 (1) (1) . data ; link1 (1) (1) . data =0; link2 (1) = link1 (1) (1) ; else i =1; while ( link1 ( i ) . nexadd ~= link1 (1) (1) . add ) link2 ( i ) = link1 ( i ) ; i = i +1; end ele = link1 ( i ) . data ; link2 (i -1) . nexadd = link2 (1) . add ; end end endfunction // C a l l i n g R o u t i n e : link1 = struct ( ’ d a t a ’ ,0 , ’ add ’ ,0 , ’ nexadd ’ ,0) ; link1 = insert_pri (3 , link1 ) ; link1 = insert_pri (4 , link1 ) ; link1 = insert_pri (22 , link1 ) ; link1 = insert_pri (21 , link1 ) ; link1 = insert_pri (11 , link1 ) ; disp ( link1 , ” L i s t A f t e r I n s e r t i o n s ” ) ; [ ele , link1 ]= extract_min ( link1 ) disp ( ele , ” Element a f t e r t h e min e x t r a c t i o n ” ) ;

64

Chapter 5 Trees

Scilab code Exa 5.1 Implementing Binary Tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

funrot (0) ; function [ tree ]= maketree ( x ) tree = zeros (30 ,1) ; for i =1:30 tree ( i ) = -1; end tree (1) = x ; tree (2) = -2; endfunction function [ tree1 ]= setleft ( tree , tre , x ) tree1 =[]; i =1; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >2* j ) tree (2* j ) = x ; 65

22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

else tree (2* j ) = x ; tree (2* j +1) = -2; for l = i :2* j -1 tree ( i ) = -1; end end tree1 = tree ; endfunction function [ tree1 ]= setright ( tree , tre , x ) tree1 =[]; i =1; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >2* j +1) tree (2* j +1) = x ; else tree (2* j +1) = x ; tree (2* j +2) = -2; for l = i :2* j tree ( i ) = -1; end end tree1 = tree ; endfunction function [ x ]= isleft ( tree , tre ) i =1; x =0; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end 66

60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

if (i >=2* j ) if (( tree (2* j ) ~= -1) |( tree (2* j ) ~= -2) ) x =1; return 1; else return 0; end else x =0; return x ; end endfunction function [ x ]= isright ( tree , tre ) i =1; x =0; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >=2* j +1) if (( tree (2* j +1) ~= -1) |( tree (2* j +1) ~= -2) ) x =1; return 1; else return 0; end else x =0; return x ; end endfunction // C a l l i n g R o u t i n e : tree = maketree (3) ; disp ( tree , ” T r e e made ” ) ; tree = setleft ( tree ,3 ,1) ; disp ( tree , ” A f t e r s e t t i n g 1 t o l e f t o f 3 ” ) ; 67

98 tree = setright ( tree ,3 ,2) ; 99 disp ( tree , ” A f t e r s e t t i n g 2 t o r i g h t o f 3 ” ) ; 100 tree = setright ( tree ,2 ,4) ; 101 tree = setleft ( tree ,2 ,5) ; 102 tree = setright ( tree ,1 ,6) ; 103 tree = setright ( tree ,5 ,8) ; 104 disp ( tree , ” A f t e r a b o v e o p e r a t i o n s : ” ) ; 105 x = isright ( tree ,3) ; 106 disp (x , ” C h e c k i n g f o r t h e r i g h t s o n o f 3 y e s i f 1

e l s e no ” ) ; 107 x = isleft ( tree ,2) ; 108 disp (x , ” Check f o r l e f t s o n o f 2 ” ) ;

Scilab code Exa 5.2 Tree Trversal Techniques 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

funrot (0) ; function [ tree ]= maketree ( x ) tree = zeros (30 ,1) ; for i =1:30 tree ( i ) = -1; end tree (1) = x ; tree (2) = -2; endfunction function [ tree1 ]= setleft ( tree , tre , x ) tree1 =[]; i =1; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >2* j ) tree (2* j ) = x ; 68

21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

else tree (2* j ) = x ; tree (2* j +1) = -2; for l = i :2* j -1 tree ( i ) = -1; end end tree1 = tree ; endfunction function [ tree1 ]= setright ( tree , tre , x ) tree1 =[]; i =1; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >2* j +1) tree (2* j +1) = x ; else tree (2* j +1) = x ; tree (2* j +2) = -2; for l = i :2* j tree ( i ) = -1; end end tree1 = tree ; endfunction function [ x ]= isleft ( tree , tre ) i =1; x =0; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end 69

59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96

if (i >=2* j ) if (( tree (2* j ) ~= -1) |( tree (2* j ) ~= -2) ) x =1; return 1; else return 0; end else x =0; return x ; end endfunction function [ x ]= isright ( tree , tre ) i =1; x =0; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >=2* j +1) if (( tree (2* j +1) ~= -1) |( tree (2* j +1) ~= -2) ) x =1; return 1; else return 0; end else x =0; return x ; end endfunction funrot (0) ; function []= inorder ( tree , p ) if ( tree ( p ) == -1| tree ( p ) == -2) return ; else 70

97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131

inorder ( tree ,2* p ) ; printf ( ”%d\ t ” , tree ( p ) ) ; inorder ( tree ,2* p +1) ; end endfunction function []= preorder ( tree , p ) if ( tree ( p ) == -1| tree ( p ) == -2) return ; else printf ( ”%d\ t ” , tree ( p ) ) ; preorder ( tree ,2* p ) ; preorder ( tree ,2* p +1) ; end endfunction function []= postorder ( tree , p ) if ( tree ( p ) == -1| tree ( p ) == -2) return ; else postorder ( tree ,2* p ) ; postorder ( tree ,2* p +1) ; printf ( ”%d\ t ” , tree ( p ) ) ; end endfunction // C a l l i n g R o u t i n e : tree = maketree (3) ; tree = setleft ( tree ,3 ,1) ; tree = setright ( tree ,3 ,2) ; tree = setleft ( tree ,2 ,4) ; tree = setright ( tree ,2 ,5) ; disp ( ” I n o r d e r t r a v e r s a l ” ) ; inorder ( tree ,1) ; disp ( ” P r e o r d e r t r a v e r s a l ” ) ; preorder ( tree ,1) ; disp ( ” P o s t o r d e r t r a v e r s a l ” ) ; postorder ( tree ,1) ;

71

Scilab code Exa 5.3 Implementing And traversing a Binary Search Tree 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

funrot (0) ; function [ tree ]= maketree ( x ) tree = zeros (1 ,30) ; for i =1:30 tree ( i ) = -1; end tree (1) = x ; tree (2) = -2; endfunction function [ tree1 ]= setleft ( tree , tre , x ) tree1 =[]; i =1; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >2* j ) tree (2* j ) = x ; else tree (2* j ) = x ; tree (2* j +1) = -2; for l = i :2* j -1 tree ( i ) = -1; end end tree1 = tree ; endfunction function [ tree1 ]= setright ( tree , tre , x ) tree1 =[]; i =1; 72

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >2* j +1) tree (2* j +1) = x ; else tree (2* j +1) = x ; tree (2* j +2) = -2; for l = i :2* j tree ( i ) = -1; end end tree1 = tree ; endfunction function [ x ]= isleft ( tree , tre ) i =1; x =0; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >=2* j ) if (( tree (2* j ) ~= -1) |( tree (2* j ) ~= -2) ) x =1; return 1; else return 0; end else x =0; return x ; end endfunction 73

71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

function [ x ]= isright ( tree , tre ) i =1; x =0; while ( tree ( i ) ~= -2) if ( tree ( i ) == tre ) j=i; end i = i +1; end if (i >=2* j +1) if (( tree (2* j +1) ~= -1) |( tree (2* j +1) ~= -2) ) x =1; return 1; else return 0; end else x =0; return x ; end endfunction funrot (0) ; function []= inorder ( tree , p ) if ( tree ( p ) == -1| tree ( p ) == -2) return ; else inorder ( tree ,2* p ) ; disp ( tree ( p ) ,” ” ) ; inorder ( tree ,2* p +1) ; end endfunction function []= preorder ( tree , p ) if ( tree ( p ) == -1| tree ( p ) == -2) return ; else disp ( tree ( p ) ,” ” ) ; preorder ( tree ,2* p ) ; preorder ( tree ,2* p +1) ; 74

109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146

end endfunction function []= postorder ( tree , p ) if ( tree ( p ) == -1| tree ( p ) == -2) return ; else postorder ( tree ,2* p ) ; postorder ( tree ,2* p +1) ; disp ( tree ( p ) ,” ” ) ; end endfunction function [ tree1 ]= binary ( tree , x ) p =1; while ( tree ( p ) ~= -1& tree ( p ) ~= -2) q=p; if ( tree ( p ) >x ) p =2* p ; else p =2* p +1; end end i =1; while ( tree ( i ) ~= -2) i = i +1; end if ( tree ( q ) >x ) if ( i ==2* q ) tree (2* q ) = x ; tree (2* q +1) = -2 else if (i <2* q ) tree ( i ) = -1; tree (2* q +1) = -2; tree (2* q ) = x ; end end else 75

147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167

if ( i ==2* q +1) tree (2* q +1) = x ; tree (2* q +2) = -2; else if (i <2* q +1) tree ( i ) = -1; tree (2* q +1) = x ; tree (2* q +2) = -2; end end end tree1 = tree ; endfunction // C a l l i n g R o u t i n e : tree = maketree (3) ; tree = binary ( tree ,1) ; tree = binary ( tree ,2) ; tree = binary ( tree ,4) ; tree = binary ( tree ,5) ; disp ( tree , ” B i n a r y t r e e t h u s o b t a i n e by i n s e r t i n g 1 , 2 , 4 and5 i n t r e e r o o t e d 3 i s : ” ) ;

Scilab code Exa 5.4 Checking the duplicate number using BST 1 2 3 4 5 6 7 8 9 10

function [ tree1 ]= binary ( tree , x ) p =1; while ( tree ( p ) ~= -1& tree ( p ) ~= -2) q=p; if ( tree ( p ) >x ) p =2* p ; else p =2* p +1; end end 76

11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

if ( tree ( q ) >x ) if ( tree (2* q ) == -2) tree (2* q ) = x ; tree (2* q +1) = -2; else tree (2* q ) = x ; end else if ( tree (2* q +1) == -2) tree (2* q +1) = x ; tree (2* q +2) = -2; else tree (2* q +1) = x ; end end tree1 = tree ; endfunction funrot (0) ; function [ tree ]= maketree ( x ) tree = zeros (40 ,1) ; for i =1:40 tree ( i ) = -1; end tree (1) = x ; tree (2) = -2; endfunction function []= duplicate1 (a , n ) tree = maketree ( a (1) ) ; q =1; p =1; i =2; x=a(i) while (i < n ) while ( tree ( p ) ~= x & tree ( q ) ~= -1& tree ( q ) ~= -2) p=q; if ( tree ( p ) <x ) q =2* p ; else 77

49 q =2* p +1; 50 end 51 end 52 if ( tree ( p ) == x ) 53 disp (x , ” D u p l i c a t e ” ) ; 54 else 55 tree = binary ( tree , x ) ; 56 end 57 i = i +1; 58 x=a(i); 59 end 60 while ( tree ( p ) ~= x & tree ( q ) ~= -1& tree ( q ) ~= -2) 61 p=q; 62 if ( tree ( p ) <x ) 63 q =2* p ; 64 else 65 q =2* p +1; 66 end 67 end 68 if ( tree ( p ) == x ) 69 disp (x , ” D u p l i c a t e ” ) ; 70 else 71 tree = binary ( tree , x ) ; 72 end 73 endfunction 74 // C a l l i n g A d r e s s : 75 a =[22 11 33 22 211 334] 76 duplicate1 (a ,6) 77 a =[21 11 33 22 22 334] 78 duplicate1 (a ,6)

78

Chapter 6 Sorting

Scilab code Exa 6.1 Bubble Sort 1 function [ a1 ]= bubble (a , n ) 2 i =1; 3 j =1; 4 temp =0; 5 for i =1: n -1 6 for j =1: n - i 7 if ( a ( j ) >a ( j +1) ) 8 temp = a ( j ) ; 9 a ( j ) = a ( j +1) ; 10 a ( j +1) = temp ; 11 end 12 j = j +1; 13 end 14 i = i +1; 15 end 16 a1 = a ; 17 disp ( a1 , ” S o r t e d a r r a y i s : ” ) ; 18 endfunction 19 // C a l l i n g R o u t i n e : 20 a =[23 21 232 121 2324 1222433 1212] 21 disp (a , ” Given Array ” ) ;

79

22 a1 = bubble (a ,7)

Scilab code Exa 6.2 Quick Sort 1 function [ a1 ]= quick ( a ) ; 2 a = gsort ( a ) ; // IN BUILT QUICK SORT FUNCTION 3 n = length ( a ) ; 4 a1 =[]; 5 for i =1: n 6 a1 =[ a1 (: ,:) a ( n +1 - i ) ]; 7 end 8 disp ( a1 , ” S o r t e d a r r a y i s : ” ) ; 9 endfunction 10 // C a l l i n g R o u t i n e : 11 a =[23 21 232 121 2324 1222433 1212] 12 disp (a , ” Given Array ” ) ; 13 a1 = quick ( a )

Scilab code Exa 6.3 Selection Sort 1 2 3 4 5 6 7 8 9 10 11 12 13

function [ a1 ]= selection (a , n ) i=n; while (i >=1) large = a (1) ; indx =1; for j =1: i if ( a ( j ) > large ) large = a ( j ) ; indx = j ; end end a ( indx ) = a ( i ) ; a ( i ) = large ; 80

14 i =i -1; 15 end 16 a1 = a ; 17 disp ( a1 , ” S o r t e d a r r a y i s : ” ) ; 18 endfunction 19 // C a l l i n g R o u t i n e : 20 a =[23 21 232 121 2324 1222433 1212] 21 disp (a , ” Given Array ” ) ; 22 a1 = selection (a ,7)

Scilab code Exa 6.4 Insertion Sort 1 function [ a1 ]= insertion (a , n ) 2 for k =1: n 3 y=a(k); 4 i=k; 5 while (i >=1) 6 if (y < a ( i ) ) 7 a ( i +1) = a ( i ) ; 8 a(i)=y; 9 end 10 i =i -1; 11 end 12 end 13 a1 = a ; 14 disp ( a1 , ” S o r t e d a r r a y i s : ” ) ; 15 endfunction 16 // C a l l i n g R o u t i n e : 17 a =[23 21 232 121 2324 1222433 1212] 18 disp (a , ” Given Array ” ) ; 19 a1 = insertion (a ,7)

Scilab code Exa 6.5 Shell sort 81

1 function [ a1 ]= shell (a ,n , incr , nic ) 2 for i =1: nic 3 span = incr ( i ) ; 4 for j = span +1: n 5 y=a(j); 6 k =j - span ; 7 while (k >=1& y < a ( k ) ) 8 a ( k + span ) = a ( k ) ; 9 k =k - span ; 10 end 11 a ( k + span ) = y ; 12 end 13 end 14 a1 = a ; 15 disp ( a1 , ” S o r t e d a r r a y i s : ” ) ; 16 endfunction 17 // C a l l i n g R o u t i n e : 18 a =[23 21 232 121 2324 1222433 1212] 19 disp (a , ” Given Array ” ) ; 20 incr =[5 3 1] // must a l w a y s end w i t h 1 21 a1 = shell (a ,7 , incr ,3)

Scilab code Exa 6.6 Merge Sort 1 2 3 4 5 6 7 8 9 10 11

function [ a1 ]= mergesort (a ,p , r ) if (p < r ) q = int (( p + r ) /2) ; a = mergesort (a ,p , q ) ; a = mergesort (a , q +1 , r ) ; a = merge (a ,p ,q , r ) ; else a1 = a ; return ; end a1 = a ; 82

12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

endfunction function [ a1 ]= merge (a ,p ,q , r ) n1 =q - p +1; n2 =r - q ; left = zeros ( n1 +1) ; right = zeros ( n2 +1) ; for i =1: n1 left ( i ) = a ( p +i -1) ; end for i1 =1: n2 right ( i1 ) = a ( q + i1 ) ; end left ( n1 +1) =999999999; right ( n2 +1) =999999999; i =1; j =1; k=p; for k = p : r if ( left ( i ) <= right ( j ) ) a ( k ) = left ( i ) ; i = i +1; else a ( k ) = right ( j ) ; j = j +1; end end a1 = a ; endfunction // C a l l i n g R o u t i n e : a =[23 21 232 121 26324 1222433 14212] disp (a , ” Given Array ” ) ; a1 = mergesort (a ,1 ,7) disp ( a1 , ” S o r t e d a r r a y i s : ” ) ; a =[232 11212 3443 23221 123424 32334 12212 2443 232] disp (a , ” Given Array ” ) ; a1 = mergesort (a ,1 ,9) ; disp ( a1 , ” S o r t e d Array ” ) ;

83

Scilab code Exa 6.7 Binary Tree Sort 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

function [ tree1 ]= binary ( tree , x ) p =1; while ( tree ( p ) ~= -1& tree ( p ) ~= -2) q=p; if ( tree ( p ) >x ) p =2* p ; else p =2* p +1; end end if ( tree ( q ) >x ) tree (2* q ) = x ; else tree (2* q +1) = x ; end tree1 = tree ; endfunction funrot (0) ; function [ tree ]= maketree ( x ) tree = zeros (100 ,1) ; for i =1:100 tree ( i ) = -1; end tree (1) = x ; tree (2) = -2; endfunction function []= inorder ( tree , p ) if ( tree ( p ) == -1| tree ( p ) == -2) return ; else inorder ( tree ,2* p ) ; printf ( ”%d\ t ” , tree ( p ) ) ; 84

33 inorder ( tree ,2* p +1) ; 34 end 35 endfunction 36 function []= binsort (a , n ) 37 a1 = maketree ( a (1) ) 38 for i =2: n 39 a1 = binary ( a1 , a ( i ) ) ; 40 end 41 disp ( ” S o r t e d a r r a y i s : ” ) ; 42 inorder ( a1 ,1) ; 43 endfunction 44 // C a l l i n g R o u t i n e : 45 a =[23 21 232 121 2324 1222433 1212] 46 disp (a , ” Given Array ” ) ; 47 a1 = binsort (a ,7)

85

Chapter 7 Searching

Scilab code Exa 7.1 Sequential Search 1 function []= search (a ,n , ele ) 2 i =1; 3 j =0; 4 for i =1: n 5 if ( a ( i ) == ele ) 6 printf ( ” Found %d AT %d\n ” ,ele , i ) ; 7 j =1; 8 end 9 end 10 if ( j ==0) 11 disp ( ”%d NOT FOUND” , ele ) ; 12 end 13 endfunction 14 // C a l l i n g R o u t i n e : 15 a =[2 33 22 121 23 233 222] 16 disp (a , ” Given a r r a y ” ) ; 17 search (a ,7 ,23)

Scilab code Exa 7.2 Sorted sequential search 86

1 function []= sortedsearch (a ,n , ele ) 2 if ( a (1) > ele | a ( n ) < ele ) 3 disp ( ”NOT IN THE LIST ” ) ; 4 else 5 i =1; 6 j =0; 7 for i =1: n 8 if ( a ( i ) == ele ) 9 printf ( ”FOUND %d AT %d” ,ele , i ) ; 10 j =1; 11 else 12 if ( a ( i ) > ele ) 13 break ; 14 end 15 end 16 end 17 if ( j ==0) 18 disp ( ”%d NOT FOUND” , ele ) ; 19 end 20 end 21 endfunction 22 // C a l l i n g R o u t i n e : 23 a =[2 22 23 33 121 222 233] // a s h o u l d be 24 disp (a , ” Given a r r a y ” ) ; 25 search (a ,7 ,23)

Scilab code Exa 7.3 Binary Search 1 2 3 4 5 6 7

function []= binsearch (a ,n , i ) l =1; h=n; while (l <= h ) mid = int (( l + h ) /2) ; if ( a ( mid ) == i ) printf ( ”FOUND %d AT %d” ,i , mid ) ; 87

sorted

8 break ; 9 else 10 if ( a ( mid ) >i ) 11 h = mid -1; 12 else 13 l = mid +1; 14 end 15 end 16 end 17 endfunction 18 // C a l l i n g R o u t i n e : 19 a =[2 22 23 33 121 222 233] // a s h o u l d be 20 disp (a , ” Given a r r a y ” ) ; 21 search (a ,7 ,23)

88

sorted

Chapter 8 Graphs

Scilab code Exa 8.1 Simple Graph Functions 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// S i m p l e Graph F u n c t i o n s function []= graph () ; i =1 , j =1; adj = zeros (10000) ; for i =1: n for j =1: n adj (( i -1) * n + j ) = temp ; end end for i =1: n for j =1: n if (( adj (( i -1) * n + j ) ) ==1) printf ( ” V e r t e x %d i s c o n n e c t e d t o v e r t e x %d\ n ” ,i , j ) ; end end end endfunction 89

Scilab code Exa 8.2 Finding The Number Of Paths From One VertexToOther 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

// F i n d i n g The Number Of P a t h s From One V e r t e x To A n o t h e r Of A Given Length function [ b ]= path (k ,n , adj ,i , j ) b =0; if ( k ==1) b = adj (( i -1) * n + j ) ; else for c =1: n if ( adj (( i -1) * n + c ) ==1) b = b + path (k -1 ,n , adj ,c , j ) ; end end end printf ( ”Number o f p a t h s from v e r t e x %d t o %d o f l e n g t h %d a r e %d” ,i ,j ,k , b ) ; return b ; endfunction // C a l l i n g R o u t i n e : n =3; adj =[0 1 1 0 0 1 0 0 0] b = path (1 ,n , adj ,1 ,3)

Scilab code Exa 8.3 Finding The Number Of Simple Paths From One Point 1

// F i n d i n g The Number Of S i m p l e P a t h s From One P o i n t To A n o t h e r I n A Given Graph 90

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

funrot (0) function []= sim_path (n , adj ,i , j ) ; l =0; m =1; for m =1: n l = l + path (m ,n , adj ,i , j ) ; end printf ( ” There a r e %d s i m p l e p a t h s from %d t o %d i n t h e g i v e n g r a p h \n ” ,l ,i , j ) ; endfunction function [ b ]= path (k ,n , adj ,i , j ) b =0; if ( k ==1) b = adj (( i -1) * n + j ) ; else for c =1: n if ( adj (( i -1) * n + c ) ==1) b = b + path (k -1 ,n , adj ,c , j ) ; end end end return b ; endfunction n =3; adj =[0 1 1 0 0 1 0 0 0]; b = sim_path (n , adj ,1 ,3)

Scilab code Exa 8.4 Finding Transitive Closure 1 2 3 4 5 6

// F i n n d i n g T r a n s i t i v e C l o s u r e funrot (0) function [ path ]= Tranclose ( adj , n ) ; i =1 , j =1; path = zeros ( n *n ,1) ; path = tranclose ( adj , n ) ; 91

7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

printf ( ” T r a n s i t i v e C l o s u r e Of Given Graph i s : \ n ” ) ; for i =1: n printf ( ” For V e r t e x %d\n ” ,i ) ; for j =1: n printf ( ” %d %d i s %d\n ” ,i ,j , path (( i -1) * n + j ) ) ; end end endfunction function [ path ]= tranclose ( adj , n ) adjprod = zeros ( n *n ,1) ; k =1; newprod = zeros ( n *n ,1) ; for i =1: n for j =1: n path (( i -1) * n + j ) = adj (( i -1) * n + j ) ; adjprod (( i -1) * n + j ) = path (( i -1) * n + j ) ; end end for i =1: n newprod = prod1 ( adjprod , adj , n ) ; for j =1: n for k =1: n path (( j -1) * n + k ) = path (( j -1) * n + k ) | newprod (( j -1) * n + k ) ; end end for j =1: n for k =1: n adjprod (( j -1) * n + k ) = newprod (( j -1) * n + k ) ; end end end endfunction function [ c ]= prod1 (a ,b , n ) for i =1: n for j =1: n val =0 92

44 for k =1: n 45 val = val |( a (( i -1) * n + k ) & b (( k -1) * n + j ) ) ; 46 end 47 c (( i -1) * n + j ) = val ; 48 end 49 end 50 endfunction 51 // C a l l i n g R o u t i n e : 52 n =3; 53 adj =[0 1 0 0 0 1 0 0 0] 54 path = Tranclose ( adj , n )

Scilab code Exa 8.5 Warshalls Algorithm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

// W a r s h a l l ’ s A l g o r i t h m funrot (0) function [ path ]= transclose ( adj , n ) for i =1: n for j =1: n path (( i -1) * n + j ) = adj (( i -1) * n + j ) ; end end for k =1: n for i =1: n if ( path (( i -1) * n + k ) ==1) for j =1: n path (( i -1) * n + j ) = path (( i -1) * n + j ) | path (( k -1) *n+j); end end end end printf ( ” T r a n s i t i v e c l o s u r e f o r t h e g i v e n g r a p h i s : \ n”); for i =1: n 93

20 printf ( ” For v e r t e x %d \n ” ,i ) ; 21 for j =1: n 22 printf ( ”%d %d i s %d\n ” ,i ,j , path (( i -1) * n + j ) ) ; 23 end 24 end 25 endfunction 26 // C a l l i n g R o u t i n e : 27 n =3; 28 adj =[0 1 0 0 0 1 0 0 0] 29 path = Tranclose ( adj , n )

Scilab code Exa 8.6 Depth First Search Traversal 1 // Depth F i r s t S e a r c h T r a v e r s a l 2 funrot (0) 3 function []= Dfs ( adj , n ) ; 4 i =1 , j =1; 5 colour =[]; 6 for i =1: n 7 for j =1: n 8 colour =[ colour (: ,:) 0]; 9 end 10 end 11 disp ( ” The DFS t r a v e r s a l i s ” ) ; 12 dfs ( adj , colour ,1 , n ) ; 13 endfunction 14 function []= dfs ( adj , colour ,r , n ) 15 colour ( r ) =1; 16 disp (r , ” ” ) ; 17 for i =1: n 18 if ( adj (( r -1) * n + i ) &( colour ( i ) ==0) ) 19 dfs ( adj , colour ,i , n ) ; 20 end 21 end 22 colour ( r ) =2;

94

23 endfunction 24 // C a l l i n g R o u t i n e : 25 n =4; 26 adj =[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] 27 Dfs ( adj , n )

Scilab code Exa 8.7 BFS Traversal 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

// //BFS T r a v e r s a l funrot (0) function [ q2 ]= push ( ele , q1 ) if ( q1 . rear == q1 . front ) q1 . a = ele ; q1 . rear = q1 . rear +1; else q1 . a =[ q1 . a (: ,:) ele ]; q1 . rear = q1 . rear +1; end q2 = q1 ; endfunction function [ ele , q2 ]= pop ( q1 ) ele = -1; q2 =0; if ( q1 . rear == q1 . front ) return ; else ele = q1 . a ( q1 . rear - q1 . front ) ; q1 . front = q1 . front +1; i =1; a = q1 . a (1) ; for i =2:( q1 . rear - q1 . front ) a =[ a (: ,:) q1 . a ( i ) ]; end q1 . a = a ; end 95

28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

q2 = q1 ; endfunction function []= Bfs ( adj , n ) ; i =1 , j =1; colour =[]; for i =1: n for j =1: n colour =[ colour (: ,:) 0]; end end disp ( ” The BFS T r a v e r s a l i s ” ) ; bfs ( adj , colour ,1 , n ) ; endfunction function []= bfs ( adj , colour ,s , n ) colour ( s ) =1; q = struct ( ’ r e a r ’ ,0 , ’ f r o n t ’ ,0 , ’ a ’ ,0) ; q = push (s , q ) ; while (( q . rear ) -( q . front ) >0) [u , q ]= pop ( q ) ; disp (u , ” ” ) ; for i =1: n if ( adj (( u -1) * n + i ) &( colour ( i ) ==0) ) colour ( i ) =1; q = push (i , q ) ; end end colour ( u ) =2; end endfunction // C a l l i n g R o u t i n e : n =4; adj =[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0] Bfs ( adj , n )

96

Scilab code Exa 8.8 Dijkstras Algorithm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// D i j k s t r a s A l g o r i t h m funrot (0) function [ l ]= short ( adj ,w , i1 , j1 , n ) for i =1: n for j =1: n if ( w (( i -1) * n + j ) ==0) w (( i -1) * n + j ) =9999; end end end distance =[]; perm =[]; for i =1: n distance =[ distance (: ,:) 99999]; perm =[ perm (: ,:) 0]; end perm ( i1 ) =1; distance ( i1 ) =0; current = i1 ; while ( current ~= j1 ) smalldist =9999; dc = distance ( current ) ; for i =1: n if ( perm ( i ) ==0) newdist = dc + w (( current -1) * n + i ) ; if ( newdist < distance ( i ) ) distance ( i ) = newdist ; end if ( distance ( i ) < smalldist ) smalldist = distance ( i ) ; k=i; end end end current = k ; 97

37 38 39 40 41 42 43 44 45 46

perm ( current ) =1; end l = distance ( j1 ) ; printf ( ” The s h o r t e s t p a t h b e t w e e n %d and %d i s %d ” ,i1 , j1 , l ) ; endfunction // C a l l i n g R o u t i n e : n =3; adj =[0 1 1 0 0 1 0 0 0] // A d j a c e n c y List w =[0 12 22 0 0 9 0 0 0] // w e i g h t l i s t f i l l 0 f o r no edge short ( adj ,w ,1 ,3 , n ) ;

98