diff options
Diffstat (limited to 'Data_Structures_Using_C_And_C_by_Y_Langsam')
8 files changed, 4155 insertions, 0 deletions
diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/1-Introduction_To_Data_Structures.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/1-Introduction_To_Data_Structures.ipynb new file mode 100644 index 0000000..6c4718b --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/1-Introduction_To_Data_Structures.ipynb @@ -0,0 +1,745 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 1: Introduction To Data Structures" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.1_4: Decimal_form_of_given_no_represented_variably.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise1.1 Example.1.1.4\n", +"//To calculate Decimal No. of a given Number\n", +"//Treating them as i)Normal binary nos(ii)Twos complemented iii)BCD:\n", +"function[c]=twos1(a1)\n", +" [j1,i1]=size(a1)\n", +" i4=1\n", +" c=-(a1(i4)*2^(i1-1));\n", +" i1=i1-1;\n", +" while(i1>=1)\n", +" i4=i4+1;\n", +" c=c+a1(i4)*2^(i1-1);\n", +" i1=i1-1;\n", +" end\n", +" disp(a1,'Decimal form of the Twos Complement Number');\n", +" disp(c,' is');\n", +"endfunction\n", +"function[d]=binary_dec(a2)\n", +" [j2,i2]=size(a2);\n", +" k=modulo(i2,4);\n", +" d=0;\n", +" if(k==0)\n", +" e=i2/4;\n", +" i3=1\n", +" while(i3<=i2)\n", +" l=3\n", +" m=0\n", +" while(l>=0)\n", +" m=m+(a2(i3)*2^l);\n", +" l=l-1;\n", +" i3=i3+1;\n", +" end\n", +" if(m>9)\n", +" d=-1;\n", +" disp('Cannot be coded in this form')\n", +" break;\n", +" end\n", +" if(m<=9)\n", +" d=d+m*10^(e-1)\n", +" e=e-1;\n", +" end\n", +" end\n", +" end\n", +" disp(a2,'Decimal form of BCD number');\n", +" disp(d,'is');\n", +"endfunction\n", +"//Given Example:\n", +"//(A)\n", +"p1=[1 0 0 1 1 0 0 1];\n", +"p2=base2dec(['10011001'],2)\n", +"p2=twos1(p1)\n", +"p2=binary_dec(p1)\n", +"//(b)\n", +"p3=[1 0 0 1];\n", +"p4=base2dec(['1001'],2)\n", +"p4=twos1(p3)\n", +"p4=binary_dec(p3)\n", +"//(C)\n", +"p5=[0 0 0 1 0 0 0 1 0 0 0 1];\n", +"p6=base2dec(['000100010001'],2)\n", +"p6=twos1(p5)\n", +"p6=binary_dec(p5)\n", +"//(d)\n", +"p7=[0 1 1 1 0 1 1 1];\n", +"p8=base2dec(['01110111'],2)\n", +"p8=twos1(p7)\n", +"p8=binary_dec(p7)\n", +"//(e)\n", +"p9=[0 1 0 1 0 1 0 1];\n", +"p10=base2dec(['01010101'],2)\n", +"p10=twos1(p9)\n", +"p10=binary_dec(p9)\n", +"//(F)\n", +"p11=[1 0 0 0 0 0 0 1 0 1 0 1];\n", +"p12=base2dec(['100000010101'],2)\n", +"p12=twos1(p11)\n", +"p12=binary_dec(p11)\n", +" " + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.1_5: Add_Substract_And_Multiply_binary_numbers.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise 1.1 example 1.1.5\n", +"//Add,Substract And Multiply binary numbers\n", +"function[a]=add(b,c)\n", +" d=base2dec(b,2)\n", +" e=base2dec(c,2)\n", +" a=d+e\n", +" a=dec2bin(a)\n", +" disp(a,'Result of addition')\n", +"endfunction\n", +"function[a]=subtract(b,c)\n", +" d=base2dec(b,2)\n", +" e=base2dec(c,2)\n", +" a=d-e\n", +" a=dec2bin(a)\n", +" disp(a,'Result of subtraction')\n", +"endfunction\n", +"function[a]=multiply(b,c)\n", +" d=base2dec(b,2)\n", +" e=base2dec(c,2)\n", +" a=d*e\n", +" a=dec2bin(a)\n", +" disp(a,'Result of multiplication');\n", +"endfunction\n", +"//Calling Routine:\n", +"b='11001';\n", +"c='10011';\n", +"a=add(b,c)\n", +"a=subtract(b,c)\n", +"a=multiply(b,c)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.1_7: TO_Convert_Binary_To_Ternary.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise 1.1Example 1.1.7\n", +"//TO Convert Binary To Ternary\n", +"function[t]=bin_ter(a)\n", +" b=0\n", +" b=base2dec(a,2);\n", +" disp(b);\n", +" [j,i]=size(a);\n", +" t=[];\n", +" while(b~=0)\n", +" m=modulo(b,3);\n", +" t=[t(:,:) m];\n", +" b=b/3;\n", +" b=b-modulo(b,10);\n", +" end\n", +" disp(t,'Ternary Equivalent');\n", +"endfunction\n", +"//Calling Routine:\n", +"a='100101101110'\n", +"disp(a,'input string is');\n", +"b=bin_ter(a)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.1: To_calcualte_Average_And_Deviation.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 1\n", +"//:To calcualte Average And Deviation\n", +"function[avg]=average(a)\n", +" i=1;\n", +" [j,k]=size(a);\n", +" j=0;\n", +" for i=1:k\n", +" j=j+a(i);\n", +" end\n", +" avg=j/k;\n", +" dev=0;\n", +" disp(avg,'Average =');\n", +" disp('The deviations are:');\n", +" for i=1:k\n", +" dev=a(i)-avg;\n", +" disp(dev);\n", +" end\n", +"endfunction\n", +"//Calling routine\n", +"a=[3 223 212 343]\n", +"avg=average(a)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.2_1: Calculate_Median_And_Mode_Of_an_Array.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise Example 1.2.1\n", +"//Calculates Median And Mode Of an Array\n", +"//(A)\n", +"function[y]=median1(a)\n", +" p=mtlb_sort(a);\n", +" [j,i]=size(a);\n", +" y=0\n", +" j=modulo(i,2);\n", +" if(j==0)\n", +" y=((a(i/2)+a(i/2+1))/2);\n", +" end\n", +" if(j==1)\n", +" i=i/2;\n", +" i=i-modulo(i,10);\n", +" y=a(i+1);\n", +" end\n", +" disp(y,'median is');\n", +"endfunction\n", +"//(B)\n", +"function[z]=mode1(a)\n", +" p=mtlb_sort(a);\n", +" disp(p)\n", +" q=1;\n", +" r=1;\n", +" i=1;\n", +" [j,i1]=size(a);\n", +" if(i1>1)\n", +" for i=1:i1-1\n", +" if(p(i)~=p(i+1))\n", +" q=[q(:,:) i+1];\n", +" r=[r(:,:) 1];\n", +" else\n", +" [c,d]=size(r);\n", +" r(d)=r(d)+1;\n", +" end\n", +" end\n", +" q1=mtlb_sort(r);\n", +" [j,i1]=size(q1)\n", +" if(q1(i1-1)==q1(i1))\n", +" z=-1;\n", +" disp('Mode does not exist');\n", +" break;\n", +" else\n", +" c=q1(i1);\n", +" k=1;\n", +" while(r(k)~=c)\n", +" k=k+1;\n", +" end\n", +" z=p(q(k));\n", +" end\n", +" end \n", +" if(i1==1)\n", +" z=a(1);\n", +" end\n", +" disp(z,'mode is');\n", +"endfunction\n", +"a=[223 12 233322 121]\n", +"y=median1(a);\n", +"z=mode1(a); " + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.2_6: Finding_the_adress_in_a_row_major_array.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise1.2 Example 1.2.6\n", +"//Finding the adress in a row major array\n", +"function[]=add(m,n)\n", +" printf('Adress is %d\n',m+n*20);\n", +"endfunction\n", +"\n", +"//(a)\n", +"add(10,0);\n", +"//(b)\n", +"add(100,0);\n", +"//(c)\n", +"add(0,0);\n", +"//(d)\n", +"add(2,1);\n", +"//(e)\n", +"add(5,1);\n", +"//(f)\n", +"add(1,10);\n", +"//(g)\n", +"add(2,10);\n", +"//(h)\n", +"add(5,3);\n", +"//(i)\n", +"add(9,19);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.2: String_Manipulations.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 2\n", +"//:String Manipulations\n", +"funcprot(0)\n", +"function[l]=strlen(str)\n", +" i=1;\n", +" l=0;\n", +" [j,k]=size(str)\n", +" for i=1:k\n", +" l=l+length(str(i));\n", +" end\n", +" disp(l,'string length is');\n", +"endfunction\n", +"//Calling Routine:\n", +"str='Hello World';\n", +"l=strlen(str)\n", +"function[c]=strcat1(a,b)\n", +" disp(strcat([a b]),'After concatination');\n", +" c=strcat([a b]);\n", +"endfunction\n", +"//Calling Routine:\n", +"a='hello ';\n", +"b='world';\n", +"c=strcat1(a,b);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.3_1: Implementing_Complex_Numbers_by_structure.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise 1.3\n", +"//Example 1.3.1\n", +"//Implementing Complex Numbers by structure\n", +"function[]=complexmanu(x1,x2,x3,x4)\n", +" \n", +" com1=struct('real',x1,'complex',x2);\n", +" com2=struct('real',x3,'complex',x4);\n", +" //adding 2 numbers\n", +" add=struct('real',x1+x3,'complex',x2+x4);\n", +" disp(add.complex,'+ i',add.real,'Addition result is ');\n", +" //Substract\n", +" sub=struct('real',x1-x3,'complex',x2-x4);\n", +" disp(sub.complex,'+ i',sub.real,'Substraction result is ');\n", +" //Negating \n", +" neg=struct('real',-x1,'complex',-x2);\n", +" disp(neg.complex,'+ i',neg.real,'Negation result for the first is ');\n", +" //Multiplication\n", +" mul=struct('real',x1*x3-x2*x4,'complex',x2*x3+x4*x1);\n", +" disp(mul.complex,'+ i',mul.real,'Multiplication result is ');\n", +" endfunction\n", +" x1=3;\n", +" x2=5;\n", +" x3=5;\n", +" x4=6;\n", +" complexmanu(x1,x2,x3,x4);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.3_6: Adding_Substracting_and_multiplying_Rational_Nos.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise 1.3\n", +"//Example 1.3.6\n", +"//Adding,Subtracting and multiplying Rational Numbers\n", +"function[]=rational(x1,x2,x3,x4)\n", +"rational1=struct('numerator',x1,'denominator',x2);\n", +"disp(rational1);\n", +"rational2=struct('numerator',x3,'denominator',x4);\n", +"disp(rational2);\n", +"//Add\n", +"x5=int32([x2 x4]);\n", +"x5=lcm(x5);\n", +"x6=x1*(x5/x2)+x3*(x5/x4);\n", +"rational3=struct('numerator',x6,'denominator',x5);\n", +"disp(rational3,'After addition');\n", +"//subtract\n", +"x6=x1*(x5/x2)-x3*(x5/x4)\n", +"rational4=struct('numerator',x6,'denominator',x5);\n", +"disp(rational4,'After Subtraction');\n", +"//Multiply\n", +"x7=x1*x3;\n", +"x8=x2*x4;\n", +"rational5=struct('numerator',x7,'denominator',x8);\n", +"disp(rational5,'After multiplication');\n", +"endfunction\n", +"x1=43;\n", +"x2=32;\n", +"x3=233;\n", +"x4=33;\n", +"rational(x1,x2,x3,x4);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.3_7: Checking_Equality_Of_2_Rational_Numbers.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Exercise 1.3\n", +"//Example 1.3.7\n", +"//Checking Equality Of 2 Rational Numbers Without Reducing Them\n", +"function[]=rational_equal(x1,x2,x3,x4)\n", +"rational1=struct('numerator',x1,'denominator',x2);\n", +"disp(rational1);\n", +"rational2=struct('numerator',x3,'denominator',x4);\n", +"disp(rational2);\n", +"if(x1*x4==x2*x3)\n", +" disp('Equal');\n", +" break;\n", +"else\n", +" disp('Not Equal');\n", +" break;\n", +"end\n", +"endfunction\n", +"//Calling Routine:\n", +"x1=32;\n", +"x2=45;\n", +"x3=43;\n", +"x4=55;\n", +"rational_equal(x1,x2,x3,x4);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.3: Writing_name_from_structure_and_counting_alphabets.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 5:\n", +"//Writing a name from the given structure and \n", +"//counting the number of alphabets printed\n", +"function[l]=strlen(str)\n", +" i=1;\n", +" l=0;\n", +" [j,k]=size(str)\n", +" for i=1:k\n", +" l=l+length(str(i));\n", +" end\n", +"endfunction\n", +"function[count]=writename(name)\n", +" printf('\n');\n", +" printf('%s',name.first);\n", +" printf('%c',' ');\n", +" printf('%s',name.midinit);\n", +" printf('\t');\n", +" printf('%s',name.last);\n", +" printf('\n');\n", +" \n", +" a=string(name.first);\n", +" count=strlen(a);\n", +" a=string(name.midinit);\n", +" count=count+strlen(a);\n", +" a=string(name.last);\n", +" count=count+strlen(a);\n", +" disp(count,'Count is:');\n", +"endfunction\n", +"//Calling Routine\n", +"name=struct('first','praveen','midinit','rajeev','last','chauhan');\n", +"count=writename(name)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.4: Raising_the_salary_of_employee.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 6\n", +"//To Raise The salary of an employee\n", +"function[employee1]=raise(employee,n)//employee is the list of employees\n", +" for i=1:n\n", +" if(employee(i)(1).year<=2000)\n", +" employee(i)(2)=employee(i)(2)*1.1;\n", +" else\n", +" employee(i)(2)=employee(i)(2)*1.05;\n", +" end\n", +" end\n", +" employee1=employee;\n", +" disp('After Raising');\n", +" for i=1:n\n", +" printf('Employee no %d\n',i);\n", +" disp(employee(i)(1));\n", +" disp(employee(i)(2));\n", +" end\n", +" \n", +"endfunction\n", +"//Calling Routine:\n", +"datehired=struct('year',1993,'month',12);\n", +"employee1=list(datehired,14000);\n", +"datehired=struct('year',1998,'month',12);\n", +"employee2=list(datehired,17000);\n", +"datehired=struct('year',2003,'month',12);\n", +"employee3=list(datehired,25000);\n", +"datehired=struct('year',2002,'month',12);\n", +"employee4=list(datehired,35000);\n", +"datehired=struct('year',2006,'month',12);\n", +"employee5=list(datehired,13000);\n", +"employee=list(employee1,employee2,employee3,employee4,employee5);\n", +"employee=raise(employee,5)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.5: Reducing_the_given_rational_number.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 7:\n", +"//Reducing The Given Rational Number\n", +"funcprot(0)\n", +"function[y]=reduce(nm,dn)\n", +"rational1=struct('numerator',nm,'denominator',dn)\n", +"y=0\n", +"if(rational1.numerator>rational1.denominator)\n", +" a=rational1.numerator;\n", +" b=rational1.denominator;\n", +"else\n", +" a=rational1.denominator;\n", +" b=rational1.numerator;\n", +"end\n", +"while(b~=0)\n", +" rem=modulo(a,b);\n", +" a=b;\n", +" b=rem;\n", +"end\n", +"y=struct('numerator',nm/a,'denominator',dn/a);\n", +"disp(y);\n", +"endfunction\n", +"nm=22;\n", +"dn=44;\n", +"y=reduce(nm,dn)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 1.6: Equality_check_of_2_rational_nos_by_reduction.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 8:\n", +"//Checking for the equality of 2 rational numbers by reducing them\n", +"function[]=equal(x1,x2,x3,x4)\n", +" rational1=struct('numerator',x1,'denominator',x2)\n", +" rational2=struct('numerator',x3,'denominator',x4)\n", +" y=0\n", +"if(rational1.numerator>rational1.denominator)\n", +" a=rational1.numerator;\n", +" b=rational1.denominator;\n", +"else\n", +" a=rational1.denominator;\n", +" b=rational1.numerator;\n", +"end\n", +"while(b~=0)\n", +" rem=modulo(a,b);\n", +" a=b;\n", +" b=rem;\n", +"end\n", +"y=struct('numerator',x1/a,'denominator',x2/a);\n", +"y1=0\n", +"if(rational2.numerator>rational2.denominator)\n", +" a=rational2.numerator;\n", +" b=rational2.denominator;\n", +"else\n", +" a=rational2.denominator;\n", +" b=rational2.numerator;\n", +"end\n", +"while(b~=0)\n", +" rem=modulo(a,b);\n", +" a=b;\n", +" b=rem;\n", +"end\n", +"y1=struct('numerator',x3/a,'denominator',x4/a);\n", +"if(y==y1)\n", +" disp('Equal')\n", +" break;\n", +"else\n", +" disp('Not Equal')\n", +" break;\n", +"end\n", +"endfunction\n", +"x1=5;\n", +"x2=7;\n", +"x3=35;\n", +"x4=49;\n", +"equal(x1,x2,x3,x4);" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/2-Stacks.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/2-Stacks.ipynb new file mode 100644 index 0000000..c5cd8ad --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/2-Stacks.ipynb @@ -0,0 +1,504 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 2: Stacks" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 2.1_2: To_determine_the_syntacticaly_valid_string.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 1\n", +"//To determine the syntacticaly valid string\n", +"function[l]=strlen(x)\n", +" i=1;\n", +" l=0;\n", +" [j,k]=size(x)\n", +" for i=1:k\n", +" l=l+length(x(i));\n", +" end\n", +"endfunction\n", +"function[]=stringvalid(str)\n", +" str=string(str);\n", +" stack=struct('a','0','top',0);\n", +" l1=strlen(str);\n", +" valid=1;\n", +" l=1;\n", +" while(l<=l1)\n", +" if(str(l)=='('|str(l)=='['|str(l)=='{')\n", +" if(stack.top==0)\n", +" stack.a=str(l);\n", +" stack.top=stack.top+1;\n", +" else\n", +" stack.a=[stack.a(:,:) str(l)];\n", +" stack.top=stack.top+1;\n", +" end\n", +" disp(stack);\n", +" end\n", +" if(str(l)==')'|str(l)==']'|str(l)=='}')\n", +" if(stack.top==0)\n", +" valid=0;\n", +" break;\n", +" else\n", +" i=stack.a(stack.top);\n", +" b=stack.a(1);\n", +" for i1=2:stack.top-1\n", +" b=[b(:,:) stack.a(i1)]\n", +" end\n", +" stack.a=b;\n", +" stack.top=stack.top-1;\n", +" symb=str(l);\n", +" disp(stack);\n", +" if(((symb==')')&(i=='('))|((symb==']')&(i='['))|((symb='}')&(i='{')))\n", +" else\n", +" valid=0;\n", +" break;\n", +" end\n", +" end\n", +" end\n", +" l=l+1;\n", +" end\n", +" if(stack.top~=0)\n", +" valid=0;\n", +" end\n", +" if(valid==0)\n", +" disp('Invalid String');\n", +" else\n", +" disp('Valid String');\n", +" end\n", +" endfunction\n", +" //Calling Routine:\n", +" stringvalid(['(' 'A' '+' 'B' '}' ')'])\n", +" stringvalid(['{' '[' 'A' '+' 'B' ']' '-' '[' '(' 'C' '-' 'D' ')' ']'])\n", +" stringvalid(['(' 'A' '+' 'B' ')' '-' '{' 'C' '+' 'D' '}' '-' '[' 'F' '+' 'G' ']'])\n", +" stringvalid(['(' '(' 'H' ')' '*' '{' '(' '[' 'J' '+' 'K' ']' ')' '}' ')'])\n", +" stringvalid(['(' '(' '(' 'A' ')' ')' ')'])" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 2.1: To_determine_the_syntacticaly_valid_string.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 1\n", +"//To determine the syntacticaly valid string\n", +"function[l]=strlen(x)\n", +" i=1;\n", +" l=0;\n", +" [j,k]=size(x)\n", +" for i=1:k\n", +" l=l+length(x(i));\n", +" end\n", +"endfunction\n", +"function[]=stringvalid(str)\n", +" str=string(str);\n", +" stack=struct('a','0','top',0);\n", +" l1=strlen(str);\n", +" valid=1;\n", +" l=1;\n", +" while(l<=l1)\n", +" if(str(l)=='('|str(l)=='['|str(l)=='{')\n", +" if(stack.top==0)\n", +" stack.a=str(l);\n", +" stack.top=stack.top+1;\n", +" else\n", +" stack.a=[stack.a(:,:) str(l)];\n", +" stack.top=stack.top+1;\n", +" end\n", +" end\n", +" if(str(l)==')'|str(l)==']'|str(l)=='}')\n", +" if(stack.top==0)\n", +" valid=0;\n", +" break;\n", +" else\n", +" i=stack.a(stack.top);\n", +" stack.top=stack.top-1;\n", +" symb=str(l);\n", +" if(((symb==')')&(i=='('))|((symb==']')&(i=='['))|((symb=='}')&(i=='{')))\n", +" else\n", +" valid=0;\n", +" break;\n", +" end\n", +" end\n", +" end\n", +" l=l+1;\n", +" end\n", +" if(stack.top~=0)\n", +" valid=0;\n", +" end\n", +" if(valid==0)\n", +" disp('Invalid String');\n", +" else\n", +" disp('Valid String');\n", +" end\n", +" endfunction\n", +" //Calling Routine:\n", +"stringvalid(['H' 'E' 'L' 'L' 'O'])" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 2.2_3: Check_if_string_is_of_certain_form.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[l]=strlen(x)\n", +" i=1;\n", +" l=0;\n", +" [j,k]=size(x)\n", +" for i=1:k\n", +" l=l+length(x(i));\n", +" end\n", +"endfunction\n", +"function[]=str(st)\n", +" stack=struct('a',0,'top',0);\n", +" st=string(st);\n", +" l=1;\n", +" l1=strlen(st);\n", +" symb=st(l);\n", +" valid=1;\n", +" while(l<l1)\n", +" while(symb~='C')\n", +" if(stack.top==0)\n", +" stack.a=st(l);\n", +" stack.top=stack.top+1;\n", +" else\n", +" stack.a=[stack.a(:,:) st(l)];\n", +" stack.top=stack.top+1;\n", +" end\n", +" l=l+1;\n", +" symb=st(l);\n", +" end\n", +" i=st(l+1);\n", +" if(stack.top==0)\n", +" valid=0;\n", +" break;\n", +" else\n", +" symb1=stack.a(stack.top);\n", +" stack.top=stack.top-1;\n", +" if(i~=symb1)\n", +" valid=0;\n", +" break;\n", +" end\n", +" end\n", +" l=l+1;\n", +" end\n", +" if(stack.top~=0)\n", +" valid=0;\n", +" end\n", +" if(valid==0)\n", +" disp('Not of the given format');\n", +" else\n", +" disp('String Of the Given Format');\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"st=['A' 'A' 'B' 'A' 'C' 'A' 'B' 'A' 'A']\n", +"str(st) \n", +"st=['A' 'A' 'B' 'A' 'C' 'A' 'B' 'A' ]\n", +"str(st)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 2.2: Implementing_Stack_using_union.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 2:\n", +"//Implementing Stack using union:\n", +"function[stack]=sta_union(etype,a)\n", +" stackelement=struct('etype',etype);\n", +" [k,l]=size(a);\n", +"select stackelement.etype,\n", +"case 'int' then\n", +" a=int32(a);\n", +" stack=struct('top',l,'items',a);,\n", +" case 'float' then\n", +" a=double(a);\n", +" stack=struct('top',l,'items',a);,\n", +" case 'char' then\n", +" a=string(a);\n", +" stack=struct('top',l,'items',a);,\n", +"end\n", +"disp(stack,'Stack is:');\n", +"endfunction\n", +"a=[32 12.34 232 32.322]\n", +"stack=sta_union('float',a)\n", +"stack=sta_union('int',a)\n", +"stack=sta_union('char',a)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 2.3: Implementing_Push_And_Pop_Functions.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 3:\n", +"//Implementing Push And Pop Functions:\n", +"function[y,sta1]=empty(sta)\n", +" y=0;\n", +" sta1=0;\n", +" if(sta.top==0)\n", +" y=0;\n", +" else\n", +" y=1;\n", +" end\n", +" sta1=sta\n", +"endfunction\n", +"\n", +"function[sta]=push(stac,ele)\n", +" sta=0;\n", +" if(empty(stac)==0)\n", +" stac.a=ele;\n", +" stac.top=stac.top+1;\n", +" else\n", +" stac.a=[stac.a(:,:) ele]\n", +" stac.top=stac.top+1;\n", +" end\n", +" disp(stac);\n", +" sta=stac;\n", +"endfunction\n", +"\n", +"function[ele,sta]=pop(stack)\n", +" ele='-1';\n", +" if(empty(stack)==0)\n", +" disp('Stack Underflow');\n", +" break;\n", +" else\n", +" ele=stack.a(stack.top);\n", +" stack.top=stack.top-1;\n", +" if(stack.top~=0)\n", +" b=stack.a(1);\n", +" for i2=2:stack.top\n", +" b=[b(:,:) stack.a(i2)];\n", +" end\n", +" stack.a=b;\n", +" else\n", +" stack.a='0';\n", +" end\n", +" end\n", +" disp(stack);\n", +" sta=stack;\n", +"endfunction\n", +"global stack\n", +"//Calling Routine:\n", +"stack=struct('a',0,'top',0);\n", +"stack=push(stack,4);\n", +"stack=push(stack,55);\n", +"stack=push(stack,199);\n", +"stack=push(stack,363);\n", +"[ele,stack]=pop(stack);\n", +"disp(stack,'After the above operations stack is:');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 2.4: Convering_an_infix_expression_to_a_Postfix_Express.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Solved Example 5:\n", +"//Convering an infix expression to a Postfix Expression:\n", +"function[sta]=push(stac,ele)\n", +" sta=0;\n", +" if(stac.top==0)\n", +" stac.a=ele;\n", +" stac.top=stac.top+1;\n", +" else\n", +" stac.a=[stac.a(:,:) ele]\n", +" stac.top=stac.top+1;\n", +" end\n", +" disp(stac);\n", +" sta=stac;\n", +"endfunction\n", +"\n", +"function[ele,sta]=pop(stack)\n", +" ele='-1';\n", +" if(stack.top==0)\n", +" disp('Stack Underflow');\n", +" break;\n", +" else\n", +" ele=stack.a(stack.top);\n", +" stack.top=stack.top-1;\n", +" if(stack.top~=0)\n", +" b=stack.a(1);\n", +" for i2=2:stack.top\n", +" b=[b(:,:) stack.a(i2)];\n", +" end\n", +" stack.a=b;\n", +" else\n", +" stack.a='0';\n", +" end\n", +" end\n", +" sta=stack;\n", +"endfunction\n", +"function[l]=strlen(x)\n", +" i=1;\n", +" l=0;\n", +" [j,k]=size(x)\n", +" for i=1:k\n", +" l=l+length(x(i));\n", +" end\n", +"endfunction\n", +"function[p]=pre(s1,s2)\n", +" i1=0;\n", +" select s1,\n", +" case '+' then i1=5;\n", +" case '-' then i1=5;\n", +" case '*' then i1=9;\n", +" case '/' then i1=9;\n", +" end\n", +" i2=0;\n", +" select s2,\n", +" case '+' then i2=5;\n", +" case '-' then i2=5;\n", +" case '*' then i2=9;\n", +" case '/' then i2=9;\n", +" end\n", +" p=0;\n", +" p=i1-i2;\n", +" if(s1=='(')\n", +" p=-1;\n", +" end\n", +" if(s2=='('&s1~=')')\n", +" p=-1;\n", +" end\n", +" if(s1~='('&s2==')')\n", +" p=1;\n", +" end\n", +" \n", +" endfunction\n", +"function[a2]=intopo(a1,n)\n", +" stack=struct('a',0,'top',0);\n", +" l1=1;\n", +" l2=strlen(a1(1))\n", +" for i=2:n\n", +" l2=l2+strlen(a1(i))\n", +" end\n", +" a2=list();\n", +" while(l1<=l2)\n", +" symb=a1(l1); \n", +" if(isalphanum(string(a1(l1))))\n", +" a2=list(a2,symb);\n", +" else\n", +" while(stack.top~=0&(pre(stack.a(stack.top),symb)>=0))\n", +" [topsymb,stack]=pop(stack);\n", +" if(topsymb==')'|topsymb=='(')\n", +" a2=a2;\n", +" else\n", +" a2=list(a2,topsymb);\n", +" end\n", +" end\n", +" if(stack.top==0|symb~=')')\n", +" stack=push(stack,symb);\n", +" else\n", +" [ele,stack]=pop(stack);\n", +" end\n", +" end\n", +" l1=l1+1;\n", +" end\n", +" while(stack.top~=0)\n", +" [topsymb,stack]=pop(stack);\n", +" if(topsymb==')'|topsymb=='(')\n", +" a2=a2;\n", +" else\n", +" a2=list(a2,topsymb);\n", +" end\n", +" end\n", +" disp(a2);\n", +"endfunction\n", +"//Calling Routine:\n", +"a1=['(' '2' '+' '3' ')' '*' '(' '5' '-' '4' ')']\n", +"a2=intopo(a1,11)" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/3-Recursion.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/3-Recursion.ipynb new file mode 100644 index 0000000..4d270b6 --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/3-Recursion.ipynb @@ -0,0 +1,355 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 3: Recursion" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 3.1: Multiplication_of_2_numbers.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Multiplication of 2 numbers\n", +"funcprot(0)\n", +"function[val]=mul(a,b)\n", +" if(b==1)\n", +" val=a;\n", +" else\n", +" val=a+mul(a,b-1);\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"a=4;\n", +"b=3;\n", +"val=mul(4,3)\n", +"printf('Product of %d and %d is %d',a,b,val);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 3.2: Factorial_of_a_number.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Function To Caluculate factorial of a given number\n", +"function[value]=fact(a)\n", +" value=-1;\n", +" if(a<0|a>170)\n", +" disp('Invalid valu.');\n", +" break;\n", +" else\n", +" if(a==1|a==0)\n", +" value=1;\n", +" else\n", +" value=a*fact(a-1);\n", +" end\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"a=5;\n", +"val=fact(a);\n", +"printf('%d factorial is %d',a,val);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 3.3: Fibbonacci_series.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[fib]=fibbo(n)\n", +" fib=-1;\n", +" if(n<0)\n", +" disp('Invalid Entry');\n", +" else\n", +" if(n<=1)\n", +" fib=n;\n", +" else\n", +" fib=fibbo(n-1)+fibbo(n-2);\n", +" end\n", +" end\n", +"endfunction\n", +"\n", +"function[l]=fibbon(n)\n", +" x=0;\n", +" l=(fibbo(0));\n", +" for x=1:n-1\n", +" l=[l(:,:),fibbo(x)];\n", +" end\n", +" disp(l);\n", +"endfunction\n", +"//Calling Routine:\n", +"n=5;\n", +"l=fibbon(n)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 3.4: Binary_Search.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[b]=bsear(a,l,u,n)\n", +" if(l>u)\n", +" b=-1;\n", +" else\n", +" mid=int32((l+u)/2);\n", +" if(n==a(mid))\n", +" b=n;\n", +" else\n", +" if(n>a(mid))\n", +" mid=int32((l+u)/2);\n", +" b=bsear(a,mid+1,u,n);\n", +" else\n", +" mid=int32((l+u)/2);\n", +" b=bsear(a,l,mid-1,n);\n", +" end\n", +" end\n", +" end\n", +"endfunction\n", +"\n", +"function[b]=bsearc(a,l,u,n)\n", +" b=bsear(a,l,u,n);\n", +" if(b==-1)\n", +" disp('The element is not there');\n", +" end\n", +" if(b==n)\n", +" disp('The element is there');\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[12 122 3233 12121]//Must be sorted:\n", +"b=bsearc(a,1,4,12)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 3.5: Tower_Of_Hanoi.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[]=towe(n,from,to,aux)\n", +" if(n==1);\n", +" disp(to,'to ',from,'Move peg 1 from');\n", +" else\n", +" towe(n-1,from,aux,to);\n", +" disp(to,'to',from,'from',n,'Move Peg');\n", +" towe(n-1,aux,to,from);\n", +" end\n", +"endfunction\n", +"\n", +"function[]=tower(from,to,aux)\n", +" n=input('Enter n');\n", +" towe(n,from,to,aux);\n", +"endfunction\n", +"//Calling Routine:\n", +"n=3//Number of disks\n", +"towe(n,'a','b','c')" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 3.6: Prefix_To_Postfix_Conversion.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"funcprot(0)\n", +"function[y]=find1(g)\n", +" length1=strlen(g);\n", +" if(length1==0)\n", +" y=0;\n", +" else\n", +" if(isalphanum(g(1)))\n", +" y=1;\n", +" else\n", +" if(length1<2)\n", +" y=0;\n", +" else\n", +" s=strsplit(g,1);\n", +" s=s(2);\n", +" m=find1(s);\n", +" if(m==0|length1==m)\n", +" y=0;\n", +" else\n", +" e=strsplit(g,m+1);\n", +" e=e(2);\n", +" n=find1(e);\n", +" if(n==0)\n", +" y=0;\n", +" else\n", +" y=m+n+1;\n", +" end\n", +" end\n", +" end\n", +" end\n", +" end\n", +" endfunction\n", +" function[l]=strlen(x)\n", +" i=1;\n", +" l=0;\n", +" [j,k]=size(x)\n", +" for i=1:k\n", +" l=l+length(x(i));\n", +" end\n", +"endfunction\n", +"function[po]=pr2po(pr)\n", +" length1=strlen(pr);\n", +" if(length1==1)\n", +" if(isalphanum(pr))\n", +" po(1)=pr(1);\n", +" else\n", +" disp('Invalid string\n');\n", +" end\n", +" else\n", +" s=strsplit(pr,1);\n", +" g=s(2);\n", +" m=find1(g);\n", +" s=strsplit(pr,m+1);\n", +" g1=s(2);\n", +" n=find1(g1);\n", +" f=strsplit(pr,1);\n", +" c=f(1);\n", +" if((c~='+'&c~='-'&c~='/'&c~='*')|m==0|n==0|m+n+1~=length1)\n", +" printf('Invalid string\n');\n", +" else\n", +" s=strsplit(pr,1);\n", +" s=strsplit(s(2),m);\n", +" opnd1=s(1);\n", +" s=strsplit(pr,m+1);\n", +" opnd2=s(2);\n", +" post1=pr2po(opnd1);\n", +" post2=pr2po(opnd2);\n", +" post=[post1(:,:) post2(:,:)]\n", +" f=strsplit(pr,1);\n", +" c=f(1);\n", +" post3=[post(:,:) c];\n", +" po=post3;\n", +" end\n", +" end \n", +" endfunction\n", +" //Calling Routine:\n", +" \n", +" s1='+-*abcd';//no spaces between\n", +" po=pr2po(s1);\n", +" disp(po,'postfix is');\n", +" s1='+-*/+-*/abcdefghi'\n", +" po=pr2po(s1);\n", +" disp(po,'postfix is');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 3.7: Simulating_Factorial_By_Non_recursion.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"\n", +"function[]=simu_fact(n);\n", +" a=1;\n", +" while(n>0)\n", +" a=a*n;\n", +" n=n-1;\n", +" end\n", +" disp(a,'Factorial is ');\n", +"endfunction\n", +"//Calling Routine:\n", +"a=9\n", +"simu_fact(a)" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/4-Queues_and_linked_list.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/4-Queues_and_linked_list.ipynb new file mode 100644 index 0000000..6cf4a6d --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/4-Queues_and_linked_list.ipynb @@ -0,0 +1,1008 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 4: Queues and linked list" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 4.1: Implementing_Singly_Connected_Linked_List.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//SINGLY CONNECTED LINKED LIST:\n", +"function[link2]=append(ele,link1)\n", +" 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);\n", +" if(link1(1)(1).add==0)\n", +" link1(1)(1).data=ele;\n", +" link1(1)(1).add=1;\n", +" link1(1)(1).nexadd=0;\n", +" link2(1)=link1(1)(1);\n", +" else\n", +" if(link1(1)(1).nexadd==0)\n", +" lin2=link1(1)(1);\n", +" lin2.data=ele;\n", +" lin2.add=link1(1)(1).add+1;\n", +" link1(1)(1).nexadd=lin2.add;\n", +" lin2.nexadd=0;\n", +" link2(1)=link1(1)(1);\n", +" link2(2)=lin2;\n", +" else\n", +" lin2=link1(1)(1);\n", +" i=1;\n", +" while(link1(i)(1).nexadd~=0)\n", +" i=i+1;\n", +" end\n", +" j=i;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i).add+1;\n", +" lin2.nexadd=0;\n", +" link1(i).nexadd=lin2.add;\n", +" link2(1)=link1(1)(1);\n", +" i=2;\n", +" while(link1(i).nexadd~=lin2.add)\n", +" link2(i)=(link1(i));\n", +" i=i+1;\n", +" end\n", +" link2(i)=link1(i);\n", +" link2(i+1)=lin2;\n", +" end\n", +" end\n", +"endfunction\n", +"function[link2]=add(ele,pos,link1);\n", +" 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);\n", +" i=1;\n", +" while(i<=pos)\n", +" if(link1(i).nexadd==0)\n", +" break;\n", +" else\n", +" i=i+1;\n", +" end\n", +" end\n", +" if(link1(i).nexadd~=0)\n", +" i=i-1;\n", +" lin2.data=ele;\n", +" lin2.add=i;\n", +" j=i;\n", +" while(link1(j).nexadd~=0)\n", +" link1(j).add=link1(j).add+1;\n", +" link1(j).nexadd=link1(j).nexadd+1;\n", +" j=j+1;\n", +" end\n", +" link1(j).add=link1(j).add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" link1(i-1).nexadd=lin2.add;\n", +" k=1;\n", +" while(k<i)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" k=k+1;\n", +" link2(k)=link1(k-1);\n", +" k=k+1\n", +" l=k-1;\n", +" while(k~=j)\n", +" link2(k)=link1(l);\n", +" k=k+1;\n", +" l=l+1;\n", +" end\n", +" link2(j)=link1(j-1);;\n", +" link2(j+1)=link1(j);\n", +" else\n", +" if(i==pos&i~=1)\n", +" k=1;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i-1).add+1;\n", +" link1(i).add=link1(i).add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" k=1;\n", +" while(k<pos)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" link2(k+1)=link1(k)\n", +" end\n", +" if(i==pos&i==1)\n", +" link2=append(ele,link1);\n", +" return link2;\n", +" end\n", +" end\n", +"endfunction\n", +"function[link2]=delete1(pos,link1)\n", +" 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);\n", +" i=1;\n", +" while(i<=pos)\n", +" if((link1(i).nexadd==0))\n", +" break;\n", +" else\n", +" i=i+1;\n", +" end\n", +" end\n", +" if(link1(i).nexadd~=0)\n", +" i=i-1;\n", +" j=1;\n", +" if(i==1)\n", +" j=1;\n", +" while(link1(j).nexadd~=0)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" link2(j)=link1(j);\n", +" else\n", +" link1(i-1).nexadd=link1(i+1).add;\n", +" while(link1(j).nexadd~=link1(i+1).add)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" if(j~=i-1)\n", +" link2(j)=link1(j);\n", +" link2(j+1)=link1(j+1);\n", +" k=i+1;\n", +" l=2;\n", +" else\n", +" link2(j)=link1(j);\n", +" k=i+1;\n", +" l=1;\n", +" end\n", +" while(link1(k).nexadd~=0)\n", +" link2(j+l)=link1(k);\n", +" k=k+1;\n", +" l=l+1;\n", +" end \n", +" link2(j+l)=link1(k);\n", +" end\n", +" else\n", +" if(i==pos)\n", +" j=1;\n", +" link1(i-1).nexadd=0;\n", +" while(j<=i-1)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" end\n", +" end\n", +"endfunction\n", +"\n", +" \n", +"\n", +"//Calling Routine:\n", +"link1=struct('data',0,'add',0,'nexadd',0);//Creates empty list\n", +"link1=append(4,link1)\n", +"link1=append(6,link1)\n", +"link1=add(7,2,link1)\n", +"link1=append(8,link1)\n", +"link1=delete1(4,link1)\n", +"disp(link1,'The linked list after the above modifications is:');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 4.2: Implementing_Queue_Operarions.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Queue Operations\n", +"function[q2]=push(ele,q1)\n", +" if(q1.rear==q1.front)\n", +" q1.a=ele;\n", +" q1.rear=q1.rear+1;\n", +" else\n", +" q1.a=[q1.a(:,:) ele];\n", +" q1.rear=q1.rear+1;\n", +" end\n", +" q2=q1;\n", +"endfunction\n", +"function[ele,q2]=pop(q1)\n", +" ele=-1;\n", +" q2=0;\n", +" if(q1.rear==q1.front)\n", +" disp('Queue Underflow');\n", +" return;\n", +" else\n", +" ele=q1.a(q1.rear-q1.front);\n", +" q1.front=q1.front+1;\n", +" i=1;\n", +" a=q1.a(1);\n", +" for i=2:(q1.rear-q1.front)\n", +" a=[a(:,:) q1.a(i)];\n", +" end\n", +" q1.a=a;\n", +" end\n", +" q2=q1;\n", +"endfunction\n", +"//Calling Routine:\n", +"q1=struct('a',0,'rear',0,'front',0)\n", +"q1=push(3,q1)\n", +"q1=push(22,q1);\n", +"q1=push(21,q1);\n", +"disp(q1,'Queue after insertion');\n", +"[ele,q1]=pop(q1)\n", +"disp(ele,'poped element');\n", +"disp(q1,'Queue after poping');\n", +"[ele,q1]=pop(q1);\n", +"[ele,q1]=pop(q1);\n", +"[ele,q1]=pop(q1);//Underflow Condition" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 4.3: Implementing_Circular_Linked_List.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//CIRCULAR LINKED LIST\n", +"function[link2]=append(ele,link1)\n", +" 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);\n", +" if(link1(1)(1).add==0)\n", +" link1(1)(1).data=ele;\n", +" link1(1)(1).add=1;\n", +" link1(1)(1).nexadd=1;\n", +" link2(1)=link1(1)(1);\n", +" else\n", +" if(link1(1)(1).nexadd==link1(1)(1).add)\n", +" lin2=link1(1)(1);\n", +" lin2.data=ele;\n", +" lin2.add=link1(1)(1).add+1;\n", +" link1(1)(1).nexadd=lin2.add;\n", +" lin2.nexadd=link1(1)(1).add;\n", +" link2(1)=link1(1)(1);\n", +" link2(2)=lin2;\n", +" else\n", +" lin2=link1(1)(1);\n", +" i=1;\n", +" while(link1(i)(1).nexadd~=link1(1)(1).add)\n", +" i=i+1;\n", +" end\n", +" j=i;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i).add+1;\n", +" lin2.nexadd=link1(1)(1).add;\n", +" link1(i).nexadd=lin2.add;\n", +" link2(1)=link1(1)(1);\n", +" i=2;\n", +" while(link1(i).nexadd~=lin2.add)\n", +" link2(i)=(link1(i));\n", +" i=i+1;\n", +" end\n", +" link2(i)=link1(i);\n", +" link2(i+1)=lin2;\n", +" end\n", +" end\n", +"endfunction\n", +"function[link2]=add(ele,pos,link1);\n", +" 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);\n", +" i=1;\n", +" while(i<=pos)\n", +" if(link1(i).nexadd==link1(1)(1).add)\n", +" break;\n", +" else\n", +" i=i+1;\n", +" end\n", +" end\n", +" if(link1(i).nexadd~=link1(1)(1).add)\n", +" i=i-1;\n", +" lin2.data=ele;\n", +" lin2.add=i;\n", +" j=i;\n", +" while(link1(j).nexadd~=link1(1)(1).add)\n", +" link1(j).add=link1(j).add+1;\n", +" link1(j).nexadd=link1(j).nexadd+1;\n", +" j=j+1;\n", +" end\n", +" link1(j).add=link1(j).add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" link1(i-1).nexadd=lin2.add;\n", +" k=1;\n", +" while(k<i)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" k=k+1;\n", +" link2(k)=link1(k-1);\n", +" k=k+1\n", +" l=k-1;\n", +" while(k~=j)\n", +" link2(k)=link1(l);\n", +" k=k+1;\n", +" l=l+1;\n", +" end\n", +" link2(j)=link1(j-1);;\n", +" link2(j+1)=link1(j);\n", +" else\n", +" if(i==pos)\n", +" k=1;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i-1).add+1;\n", +" link1(i).add=link1(i).add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" link1(i).nexadd=link1(1)(1).add;\n", +" k=1;\n", +" while(k<pos)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" link2(k+1)=link1(k)\n", +" end\n", +" end\n", +" \n", +"endfunction\n", +"function[link2]=delete1(pos,link1)\n", +" 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);\n", +" i=1;\n", +" j=1;\n", +" while(i<pos)\n", +" if((link1(j).nexadd==link1(1)(1).add))\n", +" j=1;\n", +" i=i+1;\n", +" else\n", +" i=i+1;\n", +" j=j+1;\n", +" end\n", +" end\n", +" if(link1(j).nexadd~=link1(1)(1).add)\n", +" k=1;\n", +" if(j==1)\n", +" k=2;\n", +" while(link1(k).nexadd~=link1(1)(1).add)\n", +" link2(k-1)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k-1)=link1(k);\n", +" link2(k-1).nexadd=link2(1).add;\n", +" else\n", +" lin2=link1(j);\n", +" link1(j-1).nexadd=link1(j+1).add;\n", +" k=1;\n", +" while(link1(k).nexadd~=link1(j+1).add)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=link1(k);\n", +" k=k+2;\n", +" while(link1(k).nexadd~=link1(1)(1).add)\n", +" link2(k-1)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k-1)=link1(k);\n", +" end\n", +" else\n", +" link1(j-1).nexadd=link1(1)(1).add;\n", +" l=1;\n", +" while(link1(l).nexadd~=link1(1)(1).add)\n", +" link2(l)=link1(l);\n", +" l=l+1;\n", +" end\n", +" link2(l)=link1(l);\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"link1=struct('data',0,'add',0,'nexadd',0);\n", +"link1=append(4,link1);//This will actualy create a list and 4 as start\n", +"link1=append(6,link1);\n", +"link1=add(10,2,link1);\n", +"link1=delete1(4,link1);//As the list is circular the 4'th element refers to actualy the 1'st one\n", +"disp(link1,'After the above manuplations the list is');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 4.4: Implementing_Doubly_connected_Linked_List.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//DOUBLE LINKED LIST:\n", +"function[link2]=append(ele,link1)\n", +" 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);\n", +" if(link1(1)(1).add==0)\n", +" link1(1)(1).data=ele;\n", +" link1(1)(1).add=1;\n", +" link1(1)(1).nexadd=0;\n", +" link1(1)(1).prevadd=0;\n", +" link2(1)=link1(1)(1);\n", +" else\n", +" if(link1(1)(1).nexadd==0)\n", +" lin2=link1(1)(1);\n", +" lin2.data=ele;\n", +" lin2.add=link1(1)(1).add+1;\n", +" link1(1)(1).nexadd=lin2.add;\n", +" lin2.nexadd=0;\n", +" lin2.prevadd=link1(1)(1).add;\n", +" link2(1)=link1(1)(1);\n", +" link2(2)=lin2;\n", +" else\n", +" lin2=link1(1)(1);\n", +" i=1;\n", +" while(link1(i)(1).nexadd~=0)\n", +" i=i+1;\n", +" end\n", +" j=i;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i).add+1;\n", +" lin2.nexadd=0;\n", +" link1(i).nexadd=lin2.add;\n", +" lin2.prevadd=link1(i).add;\n", +" link2(1)=link1(1)(1);\n", +" i=2;\n", +" while(link1(i).nexadd~=lin2.add)\n", +" link2(i)=(link1(i));\n", +" i=i+1;\n", +" end\n", +" link2(i)=link1(i);\n", +" link2(i+1)=lin2;\n", +" end\n", +" end\n", +"endfunction\n", +"function[link2]=add(ele,pos,link1);\n", +" 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);\n", +" i=1;\n", +" while(i<=pos)\n", +" if(link1(i).nexadd==0)\n", +" break;\n", +" else\n", +" i=i+1;\n", +" end\n", +" end\n", +" if(link1(i).nexadd~=0)\n", +" i=i-1;\n", +" lin2.data=ele;\n", +" lin2.add=i;\n", +" j=i;\n", +" while(link1(j).nexadd~=0)\n", +" link1(j).prevadd=link1(j).prevadd+1;\n", +" link1(j).add=link1(j).add+1;\n", +" link1(j).nexadd=link1(j).nexadd+1;\n", +" j=j+1;\n", +" end\n", +" link1(j).prevadd=link1(j).prevadd+1;\n", +" link1(j).add=link1(j).add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" link1(i).prevadd=lin2.add;\n", +" lin2.prevadd=link1(i-1).add;\n", +" link1(i-1).nexadd=lin2.add;\n", +" k=1;\n", +" while(k<i)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" k=k+1;\n", +" link2(k)=link1(k-1);\n", +" k=k+1\n", +" l=k-1;\n", +" while(k~=j)\n", +" link2(k)=link1(l);\n", +" k=k+1;\n", +" l=l+1;\n", +" end\n", +" link2(j)=link1(j-1);;\n", +" link2(j+1)=link1(j);\n", +" else\n", +" if(i==pos)\n", +" k=1;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i-1).add+1;\n", +" link1(i).add=link1(i).add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" link1(i).prevadd=lin2.add;\n", +" lin2.prevadd=link1(i-1).add;\n", +" k=1;\n", +" while(k<pos)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" link2(k+1)=link1(k)\n", +" end\n", +" end\n", +" \n", +"endfunction\n", +"function[link2]=delete1(pos,link1)\n", +" 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);\n", +" i=1;\n", +" while(i<=pos)\n", +" if((link1(i).nexadd==0))\n", +" break;\n", +" else\n", +" i=i+1;\n", +" end\n", +" end\n", +" if(link1(i).nexadd~=0)\n", +" i=i-1;\n", +" j=1;\n", +" if(i==1)\n", +" j=1;\n", +" while(link1(j).nexadd~=0)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" link2(j)=link1(j);\n", +" else\n", +" link1(i-1).nexadd=link1(i+1).add;\n", +" link1(i+1).prevadd=link1(i-1).add;\n", +" while(link1(j).nexadd~=link1(i+1).add)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" if(j~=i-1)\n", +" link2(j)=link1(j);\n", +" link2(j+1)=link1(j+1);\n", +" k=i+1;\n", +" l=2;\n", +" else\n", +" link2(j)=link1(j);\n", +" k=i+1;\n", +" l=1;\n", +" end\n", +" while(link1(k).nexadd~=0)\n", +" link2(j+l)=link1(k);\n", +" k=k+1;\n", +" l=l+1;\n", +" end \n", +" link2(j+l)=link1(k);\n", +" end\n", +" else\n", +" if(i==pos)\n", +" j=1;\n", +" link1(i-1).nexadd=0;\n", +" while(j<=i-1)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" end\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"link1=struct('data',0,'add',0,'nexadd',0);\n", +"link1=append(4,link1);\n", +"link1=append(6,link1);\n", +"link1=add(10,2,link1);\n", +"link1=delete1(3,link1);\n", +"disp(link1,'After the above manuplations the list is');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 4.5: Implementing_Stack_using_circular_Linked_list.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//STACK USING CIRCULAR LINKED LIST\n", +"funcprot(0)\n", +"function[link2]=append(ele,link1)\n", +" 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);\n", +" if(link1(1)(1).add==0)\n", +" link1(1)(1).data=ele;\n", +" link1(1)(1).add=1;\n", +" link1(1)(1).nexadd=1;\n", +" link2(1)=link1(1)(1);\n", +" else\n", +" if(link1(1)(1).nexadd==link1(1)(1).add)\n", +" lin2=link1(1)(1);\n", +" lin2.data=ele;\n", +" lin2.add=link1(1)(1).add+1;\n", +" link1(1)(1).nexadd=lin2.add;\n", +" lin2.nexadd=link1(1)(1).add;\n", +" link2(1)=link1(1)(1);\n", +" link2(2)=lin2;\n", +" else\n", +" lin2=link1(1)(1);\n", +" i=1;\n", +" while(link1(i)(1).nexadd~=link1(1)(1).add)\n", +" i=i+1;\n", +" end\n", +" j=i;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i).add+1;\n", +" lin2.nexadd=link1(1)(1).add;\n", +" link1(i).nexadd=lin2.add;\n", +" link2(1)=link1(1)(1);\n", +" i=2;\n", +" while(link1(i).nexadd~=lin2.add)\n", +" link2(i)=(link1(i));\n", +" i=i+1;\n", +" end\n", +" link2(i)=link1(i);\n", +" link2(i+1)=lin2;\n", +" end\n", +" end\n", +"endfunction\n", +"function[link2]=add(ele,pos,link1);\n", +" 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);\n", +" i=1;\n", +" while(i<=pos)\n", +" if(link1(i).nexadd==link1(1)(1).add)\n", +" break;\n", +" else\n", +" i=i+1;\n", +" end\n", +" end\n", +" if(link1(i).nexadd~=link1(1)(1).add)\n", +" i=i-1;\n", +" lin2.data=ele;\n", +" lin2.add=i;\n", +" j=i;\n", +" while(link1(j).nexadd~=link1(1)(1).add)\n", +" link1(j).add=link1(j).add+1;\n", +" link1(j).nexadd=link1(j).nexadd+1;\n", +" j=j+1;\n", +" end\n", +" link1(j).add=link1(j).add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" link1(i-1).nexadd=lin2.add;\n", +" k=1;\n", +" while(k<i)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" k=k+1;\n", +" link2(k)=link1(k-1);\n", +" k=k+1\n", +" l=k-1;\n", +" while(k~=j)\n", +" link2(k)=link1(l);\n", +" k=k+1;\n", +" l=l+1;\n", +" end\n", +" link2(j)=link1(j-1);;\n", +" link2(j+1)=link1(j);\n", +" else\n", +" if(i==pos)\n", +" k=1;\n", +" lin2.data=ele;\n", +" lin2.add=link1(i-1).add+1;\n", +" link1(i).add=link1.add+1;\n", +" lin2.nexadd=link1(i).add;\n", +" link1(i).nexadd=link1(1)(1).add;\n", +" k=1;\n", +" while(k<pos)\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" link2(k)=lin2;\n", +" link2(k+1)=link1(k)\n", +" end\n", +" end\n", +" \n", +"endfunction\n", +"function[link2]=delete1(pos,link1)\n", +" 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);\n", +" i=1;\n", +" if(link1(1)(1).add==0)\n", +" disp('Invalid');\n", +" else\n", +" if(link1(1)(1).nexadd==link1(1)(1).add)\n", +" link1(1)(1).add=0;\n", +" link1(1)(1).nexadd=0;\n", +" link1(1)(1).data=0;\n", +" link2(1)=link1(1)(1);\n", +" else\n", +" while(i<=pos)\n", +" if((link1(i).nexadd==link1(1)(1).add))\n", +" break;\n", +" else\n", +" i=i+1;\n", +" end\n", +" end\n", +" if(link1(i).nexadd~=link1(1)(1).add)\n", +" i=i-1;\n", +" j=1;\n", +" if(i==1)\n", +" j=1;\n", +" while(link1(j).nexadd~=link1(1)(1).add)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" link2(j)=link1(j);\n", +" else\n", +" link1(i-1).nexadd=link1(i+1).add;\n", +" while(link1(j).nexadd~=link1(i+1).add)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" if(j~=i-1)\n", +" link2(j)=link1(j);\n", +" link2(j+1)=link1(j+1);\n", +" k=i+1;\n", +" l=2;\n", +" else\n", +" link2(j)=link1(j);\n", +" k=i+1;\n", +" l=1;\n", +" end\n", +" while(link1(k).nexadd~=link1(1)(1).add)\n", +" link2(j+l)=link1(k);\n", +" k=k+1;\n", +" l=l+1;\n", +" end \n", +" link2(j+l)=link1(k);\n", +" end\n", +" else\n", +" if(i==pos)\n", +" j=1;\n", +" link1(i-1).nexadd=link1(1)(1).add;\n", +" while(j<=i-1)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" end\n", +" end\n", +"end\n", +"end\n", +"\n", +"endfunction\n", +"function[sta]=push(ele,stack)\n", +" if(stack.top==0)\n", +" stack.a=ele;\n", +" stack.top=stack.top+1;\n", +" sta=stack;\n", +" else\n", +" i=1;\n", +" link1=struct('data',0,'add',0,'nexadd',0);\n", +" while(i<=stack.top)\n", +" link1=append(stack.a(i),link1);\n", +" i=i+1;\n", +" end\n", +" link1=append(ele,link1);\n", +" stack.top=stack.top+1;\n", +" a=[stack.a(:,:) link1(stack.top).data];\n", +" stack.a=a;\n", +" sta=stack;\n", +" end\n", +"endfunction\n", +"function[ele,sta]=pop(stack)\n", +" ele=-1;\n", +" sta=0;\n", +" if(stack.top==0)\n", +" disp('Stack Underflow');\n", +" return;\n", +"else\n", +" i=1;\n", +" link1=struct('data',0,'add',0,'nexadd',0);\n", +" while(i<=stack.top)\n", +" link1=append(stack.a(i),link1);\n", +" i=i+1;\n", +" end\n", +" ele=link1(stack.top).data;\n", +" link1=delete1(stack.top,link1);\n", +" stack.top=stack.top-1;\n", +" i=2;\n", +" a=link1(1)(1).data\n", +" while(i<=stack.top)\n", +" a=[a(:,:) link1(i).data];\n", +" i=i+1;\n", +" end\n", +" stack.a=a;\n", +" sta=stack;\n", +" end\n", +"endfunction\n", +"function[stack]=empty()\n", +" stack=struct('a',0,'top',0);\n", +"endfunction\n", +"//Calling Routine:\n", +"stack=empty()//Create an empty stack\n", +"stack=push(4,stack);\n", +"stack=push(55,stack);\n", +"stack=push(199,stack);\n", +"stack=push(363,stack);\n", +"[ele,stack]=pop(stack);\n", +"disp(stack,'After the above operations stack is:');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 4.6: Implementing_Priority_Queue_Using_Lists.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Implementing Priority Queue Using Lists\n", +"funcprot(0)\n", +"function[link2]=insert_pri(ele,link1)\n", +" 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);\n", +" if(link1(1)(1).add==0)\n", +" link1(1)(1).data=ele;\n", +" link1(1)(1).add=1;\n", +" link1(1)(1).nexadd=1;\n", +" link2(1)=link1(1)(1);\n", +" else\n", +" if(link1(1)(1).nexadd==link1(1)(1).add)\n", +" if(ele>=link1(1)(1).data)\n", +" t=ele;\n", +" p=link1(1)(1).data;\n", +" else\n", +" t=link1(1)(1).data;\n", +" p=ele;\n", +" end\n", +" link1(1)(1).data=t;\n", +" lin2=link1(1)(1);\n", +" lin2.data=p;\n", +" lin2.add=2;\n", +" lin2.nexadd=link1(1)(1).add;\n", +" link1(1)(1).nexadd=lin2.add;\n", +" link2(1)=link1(1)(1);\n", +" link2(2)=lin2;\n", +" else\n", +" i=1;\n", +" a=[];\n", +" while(link1(i).nexadd~=link1(1)(1).add)\n", +" a=[a(:,:) link1(i).data];\n", +" i=i+1;\n", +" end\n", +" a=[a(:,:) link1(i).data];\n", +" a=gsort(a);\n", +" j=1;\n", +" while(j<=i)\n", +" link1(j).data=a(j);\n", +" j=j+1;\n", +" end\n", +" k=1;\n", +" while(link1(k).data>=ele)\n", +" if(link1(k).nexadd==link1(1)(1).add)\n", +" break;\n", +" else\n", +" link2(k)=link1(k);\n", +" k=k+1;\n", +" end\n", +" end\n", +" if(link1(k).nexadd~=link1(1)(1).add)\n", +" lin2=link1(k);\n", +" lin2.data=ele;\n", +" lin2.add=link1(k).add;\n", +" j=k;\n", +" y=link1(1)(1).add;\n", +" while(link1(k).nexadd~=y)\n", +" link1(k).add=link1(k).add+1;\n", +" link1(k).nexadd=link1(k).nexadd+1;\n", +" k=k+1;\n", +" end\n", +" link1(k).add=link1(k).add+1;\n", +" lin2.nexadd=link1(j).add;\n", +" link2(j)=lin2;\n", +" j=j+1;\n", +" while(j<=k+1)\n", +" link2(j)=link1(j-1);\n", +" j=j+1;\n", +" end\n", +" else\n", +" lin2=link1(k);\n", +" lin2.data=ele;\n", +" lin2.nexadd=link1(1)(1).add;\n", +" lin2.add=link1(k).add+1;\n", +" link1(k).nexadd=lin2.add;\n", +" j=1;\n", +" while(j<=k)\n", +" link2(j)=link1(j);\n", +" j=j+1;\n", +" end\n", +" link2(j)=lin2;\n", +" end\n", +" end\n", +" end\n", +" endfunction\n", +" function[ele,link2]=extract_min(link1);\n", +" 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);\n", +" i=1;\n", +" ele=-1;\n", +" if(link1(1)(1).add==0)\n", +" disp('Underflow');\n", +" return;\n", +" else\n", +" if(link1(1)(1).nexadd==link1(1)(1).add)\n", +" link1(1)(1).add=0;\n", +" link1(1)(1).nexadd=0;\n", +" ele=link1(1)(1).data;\n", +" link1(1)(1).data=0;\n", +" link2(1)=link1(1)(1);\n", +" else\n", +" i=1;\n", +" while(link1(i).nexadd~=link1(1)(1).add)\n", +" link2(i)=link1(i);\n", +" i=i+1;\n", +" end\n", +" ele=link1(i).data;\n", +" link2(i-1).nexadd=link2(1).add;\n", +" end\n", +" end\n", +" endfunction\n", +" //Calling Routine:\n", +" link1=struct('data',0,'add',0,'nexadd',0);\n", +" link1=insert_pri(3,link1);\n", +" link1=insert_pri(4,link1);\n", +" link1=insert_pri(22,link1);\n", +" link1=insert_pri(21,link1);\n", +" link1=insert_pri(11,link1);\n", +" disp(link1,'List After Insertions');\n", +" [ele,link1]=extract_min(link1)\n", +" disp(ele,'Element after the min extraction');\n", +" " + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/5-Trees.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/5-Trees.ipynb new file mode 100644 index 0000000..c2dbea9 --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/5-Trees.ipynb @@ -0,0 +1,587 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 5: Trees" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 5.1: Implementing_Binary_Tree.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"\n", +"funcprot(0);\n", +"function[tree]=maketree(x)\n", +" tree=zeros(30,1);\n", +" for i=1:30\n", +" tree(i)=-1;\n", +" end\n", +" tree(1)=x;\n", +" tree(2)=-2;\n", +"endfunction\n", +"function[tree1]=setleft(tree,tre,x)\n", +" tree1=[];\n", +" i=1;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>2*j)\n", +" tree(2*j)=x;\n", +" else\n", +" tree(2*j)=x;\n", +" tree(2*j+1)=-2;\n", +" for l=i:2*j-1\n", +" tree(i)=-1;\n", +" end\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"function[tree1]=setright(tree,tre,x)\n", +" tree1=[];\n", +" i=1;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>2*j+1)\n", +" tree(2*j+1)=x;\n", +" else\n", +" tree(2*j+1)=x;\n", +" tree(2*j+2)=-2;\n", +" for l=i:2*j\n", +" tree(i)=-1;\n", +" end\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"function[x]=isleft(tree,tre)\n", +" i=1;\n", +" x=0;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>=2*j)\n", +" if((tree(2*j)~=-1)|(tree(2*j)~=-2))\n", +" x=1;\n", +" return 1;\n", +" else\n", +" return 0;\n", +" end\n", +" else\n", +" x=0;\n", +" return x;\n", +" end\n", +"endfunction\n", +"function[x]=isright(tree,tre)\n", +" i=1;\n", +" x=0;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>=2*j+1)\n", +" if((tree(2*j+1)~=-1)|(tree(2*j+1)~=-2))\n", +" x=1;\n", +" return 1;\n", +" else\n", +" return 0;\n", +" end\n", +" else\n", +" x=0;\n", +" return x;\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"tree=maketree(3);\n", +"disp(tree,'Tree made');\n", +"tree=setleft(tree,3,1);\n", +"disp(tree,'After setting 1 to left of 3');\n", +"tree=setright(tree,3,2);\n", +"disp(tree,'After setting 2 to right of 3');\n", +"tree=setright(tree,2,4);\n", +"tree=setleft(tree,2,5);\n", +"tree=setright(tree,1,6);\n", +"tree=setright(tree,5,8);\n", +"disp(tree,'After above operations:');\n", +"x=isright(tree,3);\n", +"disp(x,'Checking for the right son of 3 yes if 1 else no');\n", +"x=isleft(tree,2);\n", +"disp(x,'Check for left son of 2');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 5.2: Tree_Trversal_Techniques.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"funcprot(0);\n", +"function[tree]=maketree(x)\n", +" tree=zeros(30,1);\n", +" for i=1:30\n", +" tree(i)=-1;\n", +" end\n", +" tree(1)=x;\n", +" tree(2)=-2;\n", +"endfunction\n", +"function[tree1]=setleft(tree,tre,x)\n", +" tree1=[];\n", +" i=1;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>2*j)\n", +" tree(2*j)=x;\n", +" else\n", +" tree(2*j)=x;\n", +" tree(2*j+1)=-2;\n", +" for l=i:2*j-1\n", +" tree(i)=-1;\n", +" end\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"function[tree1]=setright(tree,tre,x)\n", +" tree1=[];\n", +" i=1;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>2*j+1)\n", +" tree(2*j+1)=x;\n", +" else\n", +" tree(2*j+1)=x;\n", +" tree(2*j+2)=-2;\n", +" for l=i:2*j\n", +" tree(i)=-1;\n", +" end\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"function[x]=isleft(tree,tre)\n", +" i=1;\n", +" x=0;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>=2*j)\n", +" if((tree(2*j)~=-1)|(tree(2*j)~=-2))\n", +" x=1;\n", +" return 1;\n", +" else\n", +" return 0;\n", +" end\n", +" else\n", +" x=0;\n", +" return x;\n", +" end\n", +"endfunction\n", +"function[x]=isright(tree,tre)\n", +" i=1;\n", +" x=0;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>=2*j+1)\n", +" if((tree(2*j+1)~=-1)|(tree(2*j+1)~=-2))\n", +" x=1;\n", +" return 1;\n", +" else\n", +" return 0;\n", +" end\n", +" else\n", +" x=0;\n", +" return x;\n", +" end\n", +"endfunction\n", +"funcprot(0);\n", +"function[]=inorder(tree,p)\n", +" if(tree(p)==-1|tree(p)==-2)\n", +" return;\n", +" else\n", +" inorder(tree,2*p);\n", +" printf('%d\t',tree(p));\n", +" inorder(tree,2*p+1);\n", +" end\n", +"endfunction\n", +"function[]=preorder(tree,p)\n", +" if(tree(p)==-1|tree(p)==-2)\n", +" return;\n", +" else\n", +" printf('%d\t',tree(p));\n", +" preorder(tree,2*p);\n", +" preorder(tree,2*p+1);\n", +" end\n", +"endfunction\n", +"function[]=postorder(tree,p)\n", +" if(tree(p)==-1|tree(p)==-2)\n", +" return;\n", +" else\n", +" postorder(tree,2*p);\n", +" postorder(tree,2*p+1);\n", +" printf('%d\t',tree(p));\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"tree=maketree(3);\n", +"tree=setleft(tree,3,1);\n", +"tree=setright(tree,3,2);\n", +"tree=setleft(tree,2,4);\n", +"tree=setright(tree,2,5);\n", +"disp('Inorder traversal');\n", +"inorder(tree,1);\n", +"disp('Preorder traversal');\n", +"preorder(tree,1);\n", +"disp('Postorder traversal');\n", +"postorder(tree,1);" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 5.3: Implementing_And_traversing_a_Binary_Search_Tree.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"funcprot(0);\n", +"function[tree]=maketree(x)\n", +" tree=zeros(1,30);\n", +" for i=1:30\n", +" tree(i)=-1;\n", +" end\n", +" tree(1)=x;\n", +" tree(2)=-2;\n", +"endfunction\n", +"function[tree1]=setleft(tree,tre,x)\n", +" tree1=[];\n", +" i=1;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>2*j)\n", +" tree(2*j)=x;\n", +" else\n", +" tree(2*j)=x;\n", +" tree(2*j+1)=-2;\n", +" for l=i:2*j-1\n", +" tree(i)=-1;\n", +" end\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"function[tree1]=setright(tree,tre,x)\n", +" tree1=[];\n", +" i=1;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>2*j+1)\n", +" tree(2*j+1)=x;\n", +" else\n", +" tree(2*j+1)=x;\n", +" tree(2*j+2)=-2;\n", +" for l=i:2*j\n", +" tree(i)=-1;\n", +" end\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"function[x]=isleft(tree,tre)\n", +" i=1;\n", +" x=0;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>=2*j)\n", +" if((tree(2*j)~=-1)|(tree(2*j)~=-2))\n", +" x=1;\n", +" return 1;\n", +" else\n", +" return 0;\n", +" end\n", +" else\n", +" x=0;\n", +" return x;\n", +" end\n", +"endfunction\n", +"function[x]=isright(tree,tre)\n", +" i=1;\n", +" x=0;\n", +" while(tree(i)~=-2)\n", +" if(tree(i)==tre)\n", +" j=i;\n", +" end\n", +" i=i+1;\n", +" end\n", +" if(i>=2*j+1)\n", +" if((tree(2*j+1)~=-1)|(tree(2*j+1)~=-2))\n", +" x=1;\n", +" return 1;\n", +" else\n", +" return 0;\n", +" end\n", +" else\n", +" x=0;\n", +" return x;\n", +" end\n", +"endfunction\n", +"funcprot(0);\n", +"function[]=inorder(tree,p)\n", +" if(tree(p)==-1|tree(p)==-2)\n", +" return;\n", +" else\n", +" inorder(tree,2*p);\n", +" disp(tree(p),' ');\n", +" inorder(tree,2*p+1);\n", +" end\n", +"endfunction\n", +"function[]=preorder(tree,p)\n", +" if(tree(p)==-1|tree(p)==-2)\n", +" return;\n", +" else\n", +" disp(tree(p),' ');\n", +" preorder(tree,2*p);\n", +" preorder(tree,2*p+1);\n", +" end\n", +"endfunction\n", +"function[]=postorder(tree,p)\n", +" if(tree(p)==-1|tree(p)==-2)\n", +" return;\n", +" else\n", +" postorder(tree,2*p);\n", +" postorder(tree,2*p+1);\n", +" disp(tree(p),' ');\n", +" end\n", +"endfunction\n", +"function[tree1]=binary(tree,x)\n", +" p=1;\n", +" while(tree(p)~=-1&tree(p)~=-2)\n", +" q=p;\n", +" if(tree(p)>x)\n", +" p=2*p;\n", +" else\n", +" p=2*p+1;\n", +" end\n", +" end\n", +" i=1;\n", +" while(tree(i)~=-2)\n", +" i=i+1;\n", +" end\n", +" if(tree(q)>x)\n", +" if(i==2*q)\n", +" tree(2*q)=x;\n", +" tree(2*q+1)=-2\n", +" else\n", +" if(i<2*q)\n", +" tree(i)=-1;\n", +" tree(2*q+1)=-2;\n", +" tree(2*q)=x;\n", +" end\n", +" end\n", +" \n", +" else\n", +" if(i==2*q+1)\n", +" tree(2*q+1)=x;\n", +" tree(2*q+2)=-2;\n", +" else\n", +" if(i<2*q+1)\n", +" tree(i)=-1;\n", +" tree(2*q+1)=x;\n", +" tree(2*q+2)=-2;\n", +" end\n", +" end\n", +" \n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"//Calling Routine:\n", +"tree=maketree(3);\n", +"tree=binary(tree,1);\n", +"tree=binary(tree,2);\n", +"tree=binary(tree,4);\n", +"tree=binary(tree,5);\n", +"disp(tree,'Binary tree thus obtaine by inserting 1,2,4and5 in tree rooted 3 is:');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 5.4: Checking_the_duplicate_number_using_BST.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[tree1]=binary(tree,x)\n", +" p=1;\n", +" while(tree(p)~=-1&tree(p)~=-2)\n", +" q=p;\n", +" if(tree(p)>x)\n", +" p=2*p;\n", +" else\n", +" p=2*p+1;\n", +" end\n", +" end\n", +" if(tree(q)>x)\n", +" if(tree(2*q)==-2)\n", +" tree(2*q)=x;\n", +" tree(2*q+1)=-2;\n", +" else\n", +" tree(2*q)=x;\n", +" end\n", +" else\n", +" if(tree(2*q+1)==-2)\n", +" tree(2*q+1)=x;\n", +" tree(2*q+2)=-2;\n", +" else\n", +" tree(2*q+1)=x;\n", +" end\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"funcprot(0);\n", +"function[tree]=maketree(x)\n", +" tree=zeros(40,1);\n", +" for i=1:40\n", +" tree(i)=-1;\n", +" end\n", +" tree(1)=x;\n", +" tree(2)=-2;\n", +"endfunction\n", +"function[]=duplicate1(a,n)\n", +" tree=maketree(a(1));\n", +" q=1;\n", +" p=1;\n", +" i=2;\n", +" x=a(i)\n", +" while(i<n)\n", +" while(tree(p)~=x&tree(q)~=-1&tree(q)~=-2)\n", +" p=q;\n", +" if(tree(p)<x)\n", +" q=2*p;\n", +" else\n", +" q=2*p+1;\n", +" end\n", +" end\n", +" if(tree(p)==x)\n", +" disp(x,' Duplicate ');\n", +" else\n", +" tree=binary(tree,x);\n", +" end\n", +" i=i+1;\n", +" x=a(i);\n", +" end\n", +" while(tree(p)~=x&tree(q)~=-1&tree(q)~=-2)\n", +" p=q;\n", +" if(tree(p)<x)\n", +" q=2*p;\n", +" else\n", +" q=2*p+1;\n", +" end\n", +" end\n", +" if(tree(p)==x)\n", +" disp(x,' Duplicate ');\n", +" else\n", +" tree=binary(tree,x);\n", +" end\n", +"endfunction\n", +"//Calling Adress:\n", +"a=[22 11 33 22 211 334]\n", +"duplicate1(a,6)\n", +"a=[21 11 33 22 22 334]\n", +"duplicate1(a,6)" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/6-Sorting.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/6-Sorting.ipynb new file mode 100644 index 0000000..180a02c --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/6-Sorting.ipynb @@ -0,0 +1,349 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 6: Sorting" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 6.1: Bubble_Sort.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[a1]=bubble(a,n)\n", +" i=1;\n", +" j=1;\n", +" temp=0;\n", +" for i=1:n-1\n", +" for j=1:n-i\n", +" if(a(j)>a(j+1))\n", +" temp=a(j);\n", +" a(j)=a(j+1);\n", +" a(j+1)=temp;\n", +" end\n", +" j=j+1;\n", +" end\n", +" i=i+1;\n", +" end\n", +" a1=a;\n", +" disp(a1,'Sorted array is:');\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[23 21 232 121 2324 1222433 1212]\n", +"disp(a,'Given Array');\n", +"a1=bubble(a,7)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 6.2: Quick_Sort.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[a1]=quick(a);\n", +" a=gsort(a);//IN BUILT QUICK SORT FUNCTION\n", +" n=length(a);\n", +" a1=[];\n", +" for i=1:n\n", +" a1=[a1(:,:) a(n+1-i)];\n", +" end\n", +" disp(a1,'Sorted array is:');\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[23 21 232 121 2324 1222433 1212]\n", +"disp(a,'Given Array');\n", +"a1=quick(a)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 6.3: Selection_Sort.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[a1]=selection(a,n)\n", +" i=n;\n", +" while(i>=1)\n", +" large=a(1);\n", +" indx=1;\n", +" for j=1:i\n", +" if(a(j)>large)\n", +" large=a(j);\n", +" indx=j;\n", +" end\n", +" end\n", +" a(indx)=a(i);\n", +" a(i)=large;\n", +" i=i-1;\n", +" end\n", +" a1=a;\n", +" disp(a1,'Sorted array is:');\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[23 21 232 121 2324 1222433 1212]\n", +"disp(a,'Given Array');\n", +"a1=selection(a,7)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 6.4: Insertion_Sort.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[a1]=insertion(a,n)\n", +" for k=1:n\n", +" y=a(k);\n", +" i=k;\n", +" while(i>=1)\n", +" if(y<a(i))\n", +" a(i+1)=a(i);\n", +" a(i)=y;\n", +" end\n", +" i=i-1;\n", +" end\n", +" end\n", +" a1=a;\n", +" disp(a1,'Sorted array is:');\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[23 21 232 121 2324 1222433 1212]\n", +"disp(a,'Given Array');\n", +"a1=insertion(a,7) " + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 6.5: Shell_sort.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[a1]=shell(a,n,incr,nic)\n", +" for i=1:nic\n", +" span=incr(i);\n", +" for j=span+1:n\n", +" y=a(j);\n", +" k=j-span;\n", +" while(k>=1&y<a(k))\n", +" a(k+span)=a(k);\n", +" k=k-span;\n", +" end\n", +" a(k+span)=y;\n", +" end\n", +" end\n", +" a1=a;\n", +" disp(a1,'Sorted array is:');\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[23 21 232 121 2324 1222433 1212]\n", +"disp(a,'Given Array');\n", +"incr=[5 3 1]//must always end with 1\n", +"a1=shell(a,7,incr,3)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 6.6: Merge_Sort.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[a1]=mergesort(a,p,r)\n", +" if(p<r)\n", +" q=int((p+r)/2);\n", +" a=mergesort(a,p,q);\n", +" a=mergesort(a,q+1,r);\n", +" a=merge(a,p,q,r);\n", +" else\n", +" a1=a;\n", +" return;\n", +" end\n", +" a1=a;\n", +"endfunction\n", +"function[a1]=merge(a,p,q,r)\n", +" n1=q-p+1;\n", +" n2=r-q;\n", +" left=zeros(n1+1);\n", +" right=zeros(n2+1);\n", +" for i=1:n1\n", +" left(i)=a(p+i-1);\n", +" end\n", +" for i1=1:n2\n", +" right(i1)=a(q+i1);\n", +" end\n", +" left(n1+1)=999999999;\n", +" right(n2+1)=999999999;\n", +" i=1;\n", +" j=1;\n", +" k=p;\n", +" for k=p:r\n", +" if(left(i)<=right(j))\n", +" a(k)=left(i);\n", +" i=i+1;\n", +" else\n", +" a(k)=right(j);\n", +" j=j+1;\n", +" end\n", +" end\n", +" a1=a;\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[23 21 232 121 26324 1222433 14212]\n", +"disp(a,'Given Array');\n", +"a1=mergesort(a,1,7)\n", +"disp(a1,'Sorted array is:');\n", +"a=[232 11212 3443 23221 123424 32334 12212 2443 232]\n", +"disp(a,'Given Array');\n", +"a1=mergesort(a,1,9);\n", +"disp(a1,'Sorted Array');" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 6.7: Binary_Tree_Sort.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[tree1]=binary(tree,x)\n", +" p=1;\n", +" while(tree(p)~=-1&tree(p)~=-2)\n", +" q=p;\n", +" if(tree(p)>x)\n", +" p=2*p;\n", +" else\n", +" p=2*p+1;\n", +" end\n", +" end\n", +" if(tree(q)>x)\n", +" tree(2*q)=x;\n", +" else\n", +" tree(2*q+1)=x;\n", +" end\n", +" tree1=tree;\n", +"endfunction\n", +"funcprot(0);\n", +"function[tree]=maketree(x)\n", +" tree=zeros(100,1);\n", +" for i=1:100\n", +" tree(i)=-1;\n", +" end\n", +" tree(1)=x;\n", +" tree(2)=-2;\n", +"endfunction\n", +"function[]=inorder(tree,p)\n", +" if(tree(p)==-1|tree(p)==-2)\n", +" return;\n", +" else\n", +" inorder(tree,2*p);\n", +" printf('%d\t',tree(p));\n", +" inorder(tree,2*p+1);\n", +" end\n", +"endfunction\n", +"function[]=binsort(a,n)\n", +" a1=maketree(a(1))\n", +" for i=2:n\n", +" a1=binary(a1,a(i));\n", +" end\n", +" disp('Sorted array is:');\n", +" inorder(a1,1);\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[23 21 232 121 2324 1222433 1212]\n", +"disp(a,'Given Array');\n", +"a1=binsort(a,7)" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/7-Searching.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/7-Searching.ipynb new file mode 100644 index 0000000..f5c2634 --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/7-Searching.ipynb @@ -0,0 +1,148 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 7: Searching" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 7.1: Sequential_Search.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[]=search(a,n,ele)\n", +" i=1;\n", +" j=0;\n", +" for i=1:n\n", +" if(a(i)==ele)\n", +" printf('Found %d AT %d\n',ele,i);\n", +" j=1;\n", +" end\n", +" end\n", +" if(j==0)\n", +" disp('%d NOT FOUND',ele);\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[2 33 22 121 23 233 222]\n", +"disp(a,'Given array');\n", +"search(a,7,23)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 7.2: Sorted_sequential_search.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[]=sortedsearch(a,n,ele)\n", +" if(a(1)>ele|a(n)<ele)\n", +" disp('NOT IN THE LIST');\n", +" else\n", +" i=1;\n", +" j=0;\n", +" for i=1:n\n", +" if(a(i)==ele)\n", +" printf('FOUND %d AT %d',ele,i);\n", +" j=1;\n", +" else\n", +" if(a(i)>ele)\n", +" break;\n", +" end\n", +" end\n", +" end\n", +" if(j==0)\n", +" disp('%d NOT FOUND',ele);\n", +" end\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[2 22 23 33 121 222 233]//a should be sorted\n", +"disp(a,'Given array');\n", +"search(a,7,23)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 7.3: Binary_Search.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"function[]=binsearch(a,n,i)\n", +" l=1;\n", +" h=n;\n", +" while(l<=h)\n", +" mid=int((l+h)/2);\n", +" if(a(mid)==i)\n", +" printf('FOUND %d AT %d',i,mid);\n", +" break;\n", +" else\n", +" if(a(mid)>i)\n", +" h=mid-1;\n", +" else\n", +" l=mid+1;\n", +" end\n", +" end\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"a=[2 22 23 33 121 222 233]//a should be sorted\n", +"disp(a,'Given array');\n", +"search(a,7,23)" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} diff --git a/Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb b/Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb new file mode 100644 index 0000000..d5edadd --- /dev/null +++ b/Data_Structures_Using_C_And_C_by_Y_Langsam/8-Graphs.ipynb @@ -0,0 +1,459 @@ +{ +"cells": [ + { + "cell_type": "markdown", + "metadata": {}, + "source": [ + "# Chapter 8: Graphs" + ] + }, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.1: Simple_Graph_Functions.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Simple Graph Functions\n", +"function[]=graph();\n", +" \n", +" i=1,j=1;\n", +" adj=zeros(10000);\n", +" for i=1:n\n", +" for j=1:n\n", +" \n", +" adj((i-1)*n+j)=temp;\n", +" end\n", +" end\n", +" for i=1:n\n", +" for j=1:n\n", +" if((adj((i-1)*n+j))==1)\n", +" printf('Vertex %d is connected to vertex %d\n',i,j);\n", +" end\n", +" end\n", +" end\n", +" \n", +"endfunction" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.2: Finding_The_Number_Of_Paths_From_One_VertexToOther.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Finding The Number Of Paths From One Vertex To Another Of A Given Length\n", +"\n", +"function[b]=path(k,n,adj,i,j)\n", +" b=0;\n", +" if(k==1)\n", +" b=adj((i-1)*n+j);\n", +" else\n", +" for c=1:n\n", +" if(adj((i-1)*n+c)==1)\n", +" b=b+path(k-1,n,adj,c,j);\n", +" end\n", +" end\n", +" end\n", +" printf('Number of paths from vertex %d to %d of length %d are %d',i,j,k,b);\n", +" return b;\n", +"endfunction\n", +"//Calling Routine:\n", +"n=3;\n", +"adj=[0 1 1 0 0 1 0 0 0]\n", +"b=path(1,n,adj,1,3)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.3: Finding_The_Number_Of_Simple_Paths_From_One_Point.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Finding The Number Of Simple Paths From One Point To Another In A Given Graph\n", +"funcprot(0)\n", +"function[]=sim_path(n,adj,i,j);\n", +" l=0;\n", +" m=1;\n", +" for m=1:n\n", +" l=l+path(m,n,adj,i,j);\n", +" end\n", +" printf('There are %d simple paths from %d to %d in the given graph\n',l,i,j);\n", +"endfunction\n", +"function[b]=path(k,n,adj,i,j)\n", +" b=0;\n", +" if(k==1)\n", +" b=adj((i-1)*n+j);\n", +" else\n", +" for c=1:n\n", +" if(adj((i-1)*n+c)==1)\n", +" b=b+path(k-1,n,adj,c,j);\n", +" end\n", +" end\n", +" end\n", +" return b;\n", +"endfunction\n", +"n=3;\n", +"adj=[0 1 1 0 0 1 0 0 0];\n", +"b=sim_path(n,adj,1,3)\n", +"" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.4: Finding_Transitive_Closure.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Finnding Transitive Closure\n", +"funcprot(0)\n", +"function[path]=Tranclose(adj,n);\n", +" i=1,j=1;\n", +" path=zeros(n*n,1);\n", +" path=tranclose(adj,n);\n", +" printf('Transitive Closure Of Given Graph is:\n');\n", +" for i=1:n\n", +" printf('For Vertex %d\n',i);\n", +" for j=1:n\n", +" printf(' %d %d is %d\n',i,j,path((i-1)*n+j));\n", +" end\n", +" end\n", +" \n", +"endfunction\n", +"function[path]=tranclose(adj,n)\n", +" adjprod=zeros(n*n,1);\n", +" k=1;\n", +" newprod=zeros(n*n,1);\n", +" for i=1:n\n", +" for j=1:n\n", +" path((i-1)*n+j)=adj((i-1)*n+j);\n", +" adjprod((i-1)*n+j)= path((i-1)*n+j);\n", +" end\n", +" end\n", +" for i=1:n\n", +" newprod=prod1(adjprod,adj,n);\n", +" for j=1:n\n", +" for k=1:n\n", +" path((j-1)*n+k)=path((j-1)*n+k)|newprod((j-1)*n+k);\n", +" end\n", +" end\n", +" for j=1:n\n", +" for k=1:n\n", +" adjprod((j-1)*n+k)=newprod((j-1)*n+k);\n", +" end\n", +" end\n", +" end\n", +"endfunction\n", +"function[c]=prod1(a,b,n)\n", +" for i=1:n\n", +" for j=1:n\n", +" val=0\n", +" for k=1:n\n", +" val=val|(a((i-1)*n+k)&b((k-1)*n+j));\n", +" end\n", +" c((i-1)*n+j)=val;\n", +" end\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"n=3;\n", +"adj=[0 1 0 0 0 1 0 0 0]\n", +"path=Tranclose(adj,n)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.5: Warshalls_Algorithm.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Warshall's Algorithm\n", +"funcprot(0)\n", +"function[path]=transclose(adj,n)\n", +" for i=1:n\n", +" for j=1:n\n", +" path((i-1)*n+j)=adj((i-1)*n+j);\n", +" end\n", +" end\n", +" for k=1:n\n", +" for i=1:n\n", +" if(path((i-1)*n+k)==1)\n", +" for j=1:n\n", +" path((i-1)*n+j)=path((i-1)*n+j)|path((k-1)*n+j);\n", +" end\n", +" end\n", +" end\n", +" end\n", +" printf('Transitive closure for the given graph is:\n');\n", +" for i=1:n\n", +" printf('For vertex %d \n',i);\n", +" for j=1:n\n", +" printf('%d %d is %d\n',i,j,path((i-1)*n+j));\n", +" end\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"n=3;\n", +"adj=[0 1 0 0 0 1 0 0 0]\n", +"path=Tranclose(adj,n)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.6: Depth_First_Search_Traversal.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Depth First Search Traversal\n", +"funcprot(0)\n", +"function[]=Dfs(adj,n);\n", +" i=1,j=1;\n", +" colour=[];\n", +" for i=1:n\n", +" for j=1:n\n", +" colour=[colour(:,:) 0];\n", +" end\n", +" end\n", +" disp('The DFS traversal is');\n", +"dfs(adj,colour,1,n); \n", +"endfunction\n", +"function[]=dfs(adj,colour,r,n)\n", +" colour(r)=1;\n", +" disp(r,' ');\n", +" for i=1:n\n", +" if(adj((r-1)*n+i)&(colour(i)==0))\n", +" dfs(adj,colour,i,n);\n", +" end\n", +" end\n", +" colour(r)=2;\n", +"endfunction\n", +"//Calling Routine:\n", +"n=4;\n", +"adj=[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]\n", +"Dfs(adj,n)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.7: BFS_Traversal.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"////BFS Traversal\n", +"funcprot(0)\n", +"function[q2]=push(ele,q1)\n", +" if(q1.rear==q1.front)\n", +" q1.a=ele;\n", +" q1.rear=q1.rear+1;\n", +" else\n", +" q1.a=[q1.a(:,:) ele];\n", +" q1.rear=q1.rear+1;\n", +" end\n", +" q2=q1;\n", +"endfunction\n", +"function[ele,q2]=pop(q1)\n", +" ele=-1;\n", +" q2=0;\n", +" if(q1.rear==q1.front)\n", +" return;\n", +" else\n", +" ele=q1.a(q1.rear-q1.front);\n", +" q1.front=q1.front+1;\n", +" i=1;\n", +" a=q1.a(1);\n", +" for i=2:(q1.rear-q1.front)\n", +" a=[a(:,:) q1.a(i)];\n", +" end\n", +" q1.a=a;\n", +" end\n", +" q2=q1;\n", +"endfunction\n", +"\n", +"function[]=Bfs(adj,n);\n", +" i=1,j=1;\n", +" colour=[];\n", +" for i=1:n\n", +" for j=1:n\n", +" colour=[colour(:,:) 0];\n", +" end\n", +" end\n", +" disp('The BFS Traversal is');\n", +"bfs(adj,colour,1,n); \n", +"endfunction\n", +"function[]=bfs(adj,colour,s,n)\n", +" colour(s)=1;\n", +" q=struct('rear',0,'front',0,'a',0);\n", +" q=push(s,q);\n", +" while((q.rear)-(q.front)>0)\n", +" [u,q]=pop(q);\n", +" disp(u,' ');\n", +" for i=1:n\n", +" if(adj((u-1)*n+i)&(colour(i)==0))\n", +" colour(i)=1;\n", +" q=push(i,q);\n", +" end\n", +" end\n", +" colour(u)=2;\n", +" end\n", +"endfunction\n", +"//Calling Routine:\n", +"n=4;\n", +"adj=[0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0]\n", +"Bfs(adj,n)" + ] + } +, +{ + "cell_type": "markdown", + "metadata": {}, + "source": [ + "## Example 8.8: Dijkstras_Algorithm.sci" + ] + }, + { +"cell_type": "code", + "execution_count": null, + "metadata": { + "collapsed": true + }, + "outputs": [], +"source": [ +"//Dijkstras Algorithm\n", +"funcprot(0)\n", +"function[l]=short(adj,w,i1,j1,n)\n", +" for i=1:n\n", +" for j=1:n\n", +" if(w((i-1)*n+j)==0)\n", +" w((i-1)*n+j)=9999;\n", +" end\n", +" end\n", +" end\n", +" \n", +" distance=[];\n", +" perm=[];\n", +" for i=1:n\n", +" distance=[distance(:,:) 99999];\n", +" perm=[perm(:,:) 0];\n", +" end\n", +" perm(i1)=1;\n", +" distance(i1)=0;\n", +" current=i1;\n", +" while(current~=j1)\n", +" smalldist=9999;\n", +" dc=distance(current);\n", +" for i=1:n\n", +" if(perm(i)==0)\n", +" newdist=dc+w((current-1)*n+i);\n", +" if(newdist<distance(i))\n", +" distance(i)=newdist;\n", +" end\n", +" if(distance(i)<smalldist)\n", +" smalldist=distance(i);\n", +" k=i;\n", +" end\n", +" end \n", +" end\n", +" current=k;\n", +" perm(current)=1;\n", +" end\n", +" l=distance(j1);\n", +" printf('The shortest path between %d and %d is %d',i1,j1,l);\n", +"endfunction\n", +"//Calling Routine:\n", +"n=3;\n", +"adj=[0 1 1 0 0 1 0 0 0]//Adjacency List\n", +"w=[0 12 22 0 0 9 0 0 0]//weight list fill 0 for no edge\n", +"short(adj,w,1,3,n);" + ] + } +], +"metadata": { + "kernelspec": { + "display_name": "Scilab", + "language": "scilab", + "name": "scilab" + }, + "language_info": { + "file_extension": ".sce", + "help_links": [ + { + "text": "MetaKernel Magics", + "url": "https://github.com/calysto/metakernel/blob/master/metakernel/magics/README.md" + } + ], + "mimetype": "text/x-octave", + "name": "scilab", + "version": "0.7.1" + } + }, + "nbformat": 4, + "nbformat_minor": 0 +} |