diff options
Diffstat (limited to 'Data_Structures_and_Algorithms_in_Java/ch2.ipynb')
| -rw-r--r-- | Data_Structures_and_Algorithms_in_Java/ch2.ipynb | 374 |
1 files changed, 356 insertions, 18 deletions
diff --git a/Data_Structures_and_Algorithms_in_Java/ch2.ipynb b/Data_Structures_and_Algorithms_in_Java/ch2.ipynb index 545d8433..ffbe7f1a 100644 --- a/Data_Structures_and_Algorithms_in_Java/ch2.ipynb +++ b/Data_Structures_and_Algorithms_in_Java/ch2.ipynb @@ -1,6 +1,7 @@ { "metadata": { - "name": "ch2" + "name": "", + "signature": "sha256:aab97f08438f435b57ec8f21a4d063e7bb3805bfb2401a475b716ab779bcb766" }, "nbformat": 3, "nbformat_minor": 0, @@ -11,25 +12,64 @@ "cell_type": "heading", "level": 1, "metadata": {}, - "source": "Chapter 2 : Arrays" + "source": [ + "Chapter 2 : Arrays" + ] }, { "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 2.1 Page no :41" + "source": [ + "Example 2.1 Page no :41" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 2.1\ndemonstrates arrays/lists\n'''\n\nnElems = 0\narr = [77,99,44,55,22,88,11,00,66,33]\n\nfor j in range(len(arr)):\n # display items\n print arr[j] ,\nprint ''\n\nsearchKey = 66\n# find item with key 66\nfor j in range(len(arr)):\n if(arr[j] == searchKey):\n break\nif(j == len(arr)):\n print 'Cant find ', searchKey\nelse:\n print 'Found ' ,searchKey\n\nsearchKey = 55\nfor j in arr:\n if(j == searchKey):\n arr.remove(searchKey)\n\n\nfor j in range(len(arr)):\n # display items\n print arr[j] ,\nprint ''\n", + "input": [ + " \n", + "\n", + "nElems = 0\n", + "arr = [77,99,44,55,22,88,11,00,66,33]\n", + "\n", + "for j in range(len(arr)):\n", + " # display items\n", + " print arr[j] ,\n", + "print ''\n", + "\n", + "searchKey = 66\n", + "# find item with key 66\n", + "for j in range(len(arr)):\n", + " if(arr[j] == searchKey):\n", + " break\n", + "if(j == len(arr)):\n", + " print 'Cant find ', searchKey\n", + "else:\n", + " print 'Found ' ,searchKey\n", + "\n", + "searchKey = 55\n", + "for j in arr:\n", + " if(j == searchKey):\n", + " arr.remove(searchKey)\n", + "\n", + "\n", + "for j in range(len(arr)):\n", + " # display items\n", + " print arr[j] ,\n", + "print ''\n" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "77 99 44 55 22 88 11 0 66 33 \nFound 66\n77 99 44 22 88 11 0 66 33 \n" + "text": [ + "77 99 44 55 22 88 11 0 66 33 \n", + "Found 66\n", + "77 99 44 22 88 11 0 66 33 \n" + ] } ], "prompt_number": 1 @@ -38,19 +78,83 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 2.2 Page No : 44" + "source": [ + "Example 2.2 Page No : 44" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 2.2\n'''\n\nclass LowArray:\n def __init__(self,size):\n self.a = []\n for i in range(size):\n self.a.append(0.0)\n \n def setElem(self,index,value):\n # set value\n self.a[index] = value\n\n def getElem(self,index):\n return self.a[index]\n\narr = LowArray(100)\narr.setElem(0,77)\narr.setElem(1,99)\narr.setElem(2,44)\narr.setElem(3,55)\narr.setElem(4,22)\narr.setElem(5,88)\narr.setElem(6,11)\narr.setElem(7,00)\narr.setElem(8,66)\narr.setElem(9,33)\nnElems = 10\n\n# now 10 items in array\nfor j in range(nElems):\n # display items\n print arr.getElem(j) ,\n\nprint ''\n\nsearchKey = 26\nfind = False\n# search for data item\nfor j in range(nElems):\n # for each element,\n if(arr.getElem(j) == searchKey): # found item?\n find = True\n break\nif(not find):\n print \"Can't find \" , searchKey\nelse:\n print \"Found \" , searchKey\n\nfor j in range(nElems):\n if(arr.getElem(j) == 55):\n arr.a.remove(55)\n nElems -= 1\n\nfor j in range(nElems):\n # display items\n print arr.getElem(j) ,\n ", + "input": [ + " \n", + "\n", + "class LowArray:\n", + " def __init__(self,size):\n", + " self.a = []\n", + " for i in range(size):\n", + " self.a.append(0.0)\n", + " \n", + " def setElem(self,index,value):\n", + " # set value\n", + " self.a[index] = value\n", + "\n", + " def getElem(self,index):\n", + " return self.a[index]\n", + "\n", + "arr = LowArray(100)\n", + "arr.setElem(0,77)\n", + "arr.setElem(1,99)\n", + "arr.setElem(2,44)\n", + "arr.setElem(3,55)\n", + "arr.setElem(4,22)\n", + "arr.setElem(5,88)\n", + "arr.setElem(6,11)\n", + "arr.setElem(7,00)\n", + "arr.setElem(8,66)\n", + "arr.setElem(9,33)\n", + "nElems = 10\n", + "\n", + "# now 10 items in array\n", + "for j in range(nElems):\n", + " # display items\n", + " print arr.getElem(j) ,\n", + "\n", + "print ''\n", + "\n", + "searchKey = 26\n", + "find = False\n", + "# search for data item\n", + "for j in range(nElems):\n", + " # for each element,\n", + " if(arr.getElem(j) == searchKey): # found item?\n", + " find = True\n", + " break\n", + "if(not find):\n", + " print \"Can't find \" , searchKey\n", + "else:\n", + " print \"Found \" , searchKey\n", + "\n", + "for j in range(nElems):\n", + " if(arr.getElem(j) == 55):\n", + " arr.a.remove(55)\n", + " nElems -= 1\n", + "\n", + "for j in range(nElems):\n", + " # display items\n", + " print arr.getElem(j) ,\n", + " " + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "77 99 44 55 22 88 11 0 66 33 \nCan't find 26\n77 99 44 22 88 11 0 66 33\n" + "text": [ + "77 99 44 55 22 88 11 0 66 33 \n", + "Can't find 26\n", + "77 99 44 22 88 11 0 66 33\n" + ] } ], "prompt_number": 2 @@ -59,19 +163,81 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 2.3 Page No : 49" + "source": [ + "Example 2.3 Page No : 49" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 2.3\n'''\n\nclass HighArray:\n def __init__(self,size):\n self.a = []\n self.nElems = 0\n for i in range(size):\n self.a.append(0.0)\n \n def insert(self,value):\n # set value\n self.a[self.nElems] = value\n self.nElems += 1\n\n def find(self,searchKey):\n for j in range(self.nElems):\n if(self.a[j] == searchKey):\n return True\n return False\n \n def delete(self,value):\n for j in range(self.nElems):\n # look for it\n if (value == self.a[j]):\n self.a.remove(value)\n self.nElems -= 1\n \n def display(self):\n for j in range(self.nElems+1):\n print self.a[j] , \n print ''\n\narr = HighArray(100)\narr.insert(77)\narr.insert(99)\narr.insert(44)\narr.insert(55)\narr.insert(22)\narr.insert(88)\narr.insert(11)\narr.insert(00)\narr.insert(66)\narr.insert(33)\n\narr.display()\n\nsearchKey = 35\nif( arr.find(searchKey) ):\n print \"Found \" , searchKey\nelse:\n print \"Can't find \" , searchKey\narr.delete(00)\narr.delete(55)\narr.delete(99)\narr.display()", + "input": [ + " \n", + "\n", + "class HighArray:\n", + " def __init__(self,size):\n", + " self.a = []\n", + " self.nElems = 0\n", + " for i in range(size):\n", + " self.a.append(0.0)\n", + " \n", + " def insert(self,value):\n", + " # set value\n", + " self.a[self.nElems] = value\n", + " self.nElems += 1\n", + "\n", + " def find(self,searchKey):\n", + " for j in range(self.nElems):\n", + " if(self.a[j] == searchKey):\n", + " return True\n", + " return False\n", + " \n", + " def delete(self,value):\n", + " for j in range(self.nElems):\n", + " # look for it\n", + " if (value == self.a[j]):\n", + " self.a.remove(value)\n", + " self.nElems -= 1\n", + " \n", + " def display(self):\n", + " for j in range(self.nElems+1):\n", + " print self.a[j] , \n", + " print ''\n", + "\n", + "arr = HighArray(100)\n", + "arr.insert(77)\n", + "arr.insert(99)\n", + "arr.insert(44)\n", + "arr.insert(55)\n", + "arr.insert(22)\n", + "arr.insert(88)\n", + "arr.insert(11)\n", + "arr.insert(00)\n", + "arr.insert(66)\n", + "arr.insert(33)\n", + "\n", + "arr.display()\n", + "\n", + "searchKey = 35\n", + "if( arr.find(searchKey) ):\n", + " print \"Found \" , searchKey\n", + "else:\n", + " print \"Can't find \" , searchKey\n", + "arr.delete(00)\n", + "arr.delete(55)\n", + "arr.delete(99)\n", + "arr.display()" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "77 99 44 55 22 88 11 0 66 33 0.0 \nCan't find 35\n77 44 22 88 11 66 33 \n" + "text": [ + "77 99 44 55 22 88 11 0 66 33 0.0 \n", + "Can't find 35\n", + "77 44 22 88 11 66 33 \n" + ] } ], "prompt_number": 3 @@ -80,19 +246,92 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 2.4 Page no : 59" + "source": [ + "Example 2.4 Page no : 59" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 2.4\n'''\n\nclass OrdArray:\n def __init__(self,m):\n self.a = []\n self.nElems = 0\n \n def size(self):\n return self.nElems\n\n def find(self,searchKey):\n lowerBound = 0\n upperBound = self.nElems-1\n while True:\n curIn = (lowerBound + upperBound ) / 2\n if(self.a[curIn]==searchKey):\n return curIn\n elif(lowerBound > upperBound):\n return self.nElems\n else:\n if(self.a[curIn] < searchKey):\n lowerBound = curIn + 1\n else:\n upperBound = curIn - 1 \n\n def insert(self,value):\n self.a.append(value)\n self.a.sort()\n self.nElems += 1\n\n def delete(self,value):\n j = self.find(value)\n if(j==self.nElems):\n return False\n else:\n self.a.remove(value)\n self.nElems -=1\n \n def display(self):\n for i in self.a:\n print i ,\n print ''\n\nmaxSize = 100\narr = OrdArray(maxSize)\narr.insert(77)\narr.insert(99) \narr.insert(44) \narr.insert(55) \narr.insert(22) \narr.insert(88) \narr.insert(11) \narr.insert(00) \narr.insert(66) \narr.insert(33) \nsearchKey = 55\nif( arr.find(searchKey) != arr.size() ):\n print 'Found ' , searchKey\nelse:\n print \"Can't find \" , searchKey\n \narr.display()\narr.delete(00)\narr.delete(55) \narr.delete(99) \narr.display()", + "input": [ + " \n", + "\n", + "class OrdArray:\n", + " def __init__(self,m):\n", + " self.a = []\n", + " self.nElems = 0\n", + " \n", + " def size(self):\n", + " return self.nElems\n", + "\n", + " def find(self,searchKey):\n", + " lowerBound = 0\n", + " upperBound = self.nElems-1\n", + " while True:\n", + " curIn = (lowerBound + upperBound ) / 2\n", + " if(self.a[curIn]==searchKey):\n", + " return curIn\n", + " elif(lowerBound > upperBound):\n", + " return self.nElems\n", + " else:\n", + " if(self.a[curIn] < searchKey):\n", + " lowerBound = curIn + 1\n", + " else:\n", + " upperBound = curIn - 1 \n", + "\n", + " def insert(self,value):\n", + " self.a.append(value)\n", + " self.a.sort()\n", + " self.nElems += 1\n", + "\n", + " def delete(self,value):\n", + " j = self.find(value)\n", + " if(j==self.nElems):\n", + " return False\n", + " else:\n", + " self.a.remove(value)\n", + " self.nElems -=1\n", + " \n", + " def display(self):\n", + " for i in self.a:\n", + " print i ,\n", + " print ''\n", + "\n", + "maxSize = 100\n", + "arr = OrdArray(maxSize)\n", + "arr.insert(77)\n", + "arr.insert(99) \n", + "arr.insert(44) \n", + "arr.insert(55) \n", + "arr.insert(22) \n", + "arr.insert(88) \n", + "arr.insert(11) \n", + "arr.insert(00) \n", + "arr.insert(66) \n", + "arr.insert(33) \n", + "searchKey = 55\n", + "if( arr.find(searchKey) != arr.size() ):\n", + " print 'Found ' , searchKey\n", + "else:\n", + " print \"Can't find \" , searchKey\n", + " \n", + "arr.display()\n", + "arr.delete(00)\n", + "arr.delete(55) \n", + "arr.delete(99) \n", + "arr.display()" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "Found 55\n0 11 22 33 44 55 66 77 88 99 \n11 22 33 44 66 77 88 \n" + "text": [ + "Found 55\n", + "0 11 22 33 44 55 66 77 88 99 \n", + "11 22 33 44 66 77 88 \n" + ] } ], "prompt_number": 4 @@ -101,19 +340,118 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 2.5 Page no : 66" + "source": [ + "Example 2.5 Page no : 66" + ] }, { "cell_type": "code", "collapsed": false, - "input": "'''\nexample 2.5\n'''\n\nclass Person:\n def __init__(self,last,first,a):\n self.lastName = last\n self.firstName = first\n self.age = a\n\n def displayPerson(self):\n print \"Last name: \" , self.lastName ,\", First name: \" , self.firstName ,\n print \", Age: \" , self.age\n\n def getLast(self):\n return self.lastName\n\nclass ClassDataArray:\n def __init__(self,m):\n self.a = []\n self.nElems = 0\n\n def find(self,searchName):\n f = False\n for j in range(self.nElems):\n if( self.a[j].getLast() ==searchName ) :\n f = True\n break \n if(not f):\n return None\n else:\n return self.a[j]\n\n def insert(self,last,first,age):\n self.a.append(Person(last, first, age))\n self.nElems += 1\n\n def delete(self,searchName):\n f = False\n for j in range(self.nElems):\n if( self.a[j].getLast() == searchName) :\n self.a.remove(self.a[j])\n f = True\n self.nElems -= 1\n break\n if(not f):\n return False\n else:\n return True\n \n def displayA(self):\n for j in range(self.nElems):\n self.a[j].displayPerson()\n\nmaxSize = 100\narr = ClassDataArray(maxSize)\narr.insert(\"Evans\", \"Patty\", 24)\narr.insert(\"Smith\", \"Lorraine\", 37)\narr.insert(\"Yee\", \"Tom\", 43)\narr.insert(\"Adams\", \"Henry\", 63)\narr.insert(\"Hashimoto\", \"Sato\", 21)\narr.insert(\"Stimson\", \"Henry\", 29)\narr.insert(\"Velasquez\", \"Jose\", 72)\narr.insert(\"Lamarque\", \"Henry\", 54)\narr.insert(\"Vang\", \"Minh\", 22)\narr.insert(\"Creswell\", \"Lucinda\", 18)\narr.displayA()\nsearchKey = \"Stimson\"\nfound=arr.find(searchKey)\nif(found != None ):\n print \"Found \" ,\n found.displayPerson()\nelse:\n print \"Can't find \" , searchKey\nprint \"Deleting Smith, Yee, and Creswell\"\narr.delete(\"Smith\")\narr.delete(\"Yee\")\narr.delete(\"Creswell\")\narr.displayA()", + "input": [ + " \n", + "class Person:\n", + " def __init__(self,last,first,a):\n", + " self.lastName = last\n", + " self.firstName = first\n", + " self.age = a\n", + "\n", + " def displayPerson(self):\n", + " print \"Last name: \" , self.lastName ,\", First name: \" , self.firstName ,\n", + " print \", Age: \" , self.age\n", + "\n", + " def getLast(self):\n", + " return self.lastName\n", + "\n", + "class ClassDataArray:\n", + " def __init__(self,m):\n", + " self.a = []\n", + " self.nElems = 0\n", + "\n", + " def find(self,searchName):\n", + " f = False\n", + " for j in range(self.nElems):\n", + " if( self.a[j].getLast() ==searchName ) :\n", + " f = True\n", + " break \n", + " if(not f):\n", + " return None\n", + " else:\n", + " return self.a[j]\n", + "\n", + " def insert(self,last,first,age):\n", + " self.a.append(Person(last, first, age))\n", + " self.nElems += 1\n", + "\n", + " def delete(self,searchName):\n", + " f = False\n", + " for j in range(self.nElems):\n", + " if( self.a[j].getLast() == searchName) :\n", + " self.a.remove(self.a[j])\n", + " f = True\n", + " self.nElems -= 1\n", + " break\n", + " if(not f):\n", + " return False\n", + " else:\n", + " return True\n", + " \n", + " def displayA(self):\n", + " for j in range(self.nElems):\n", + " self.a[j].displayPerson()\n", + "\n", + "maxSize = 100\n", + "arr = ClassDataArray(maxSize)\n", + "arr.insert(\"Evans\", \"Patty\", 24)\n", + "arr.insert(\"Smith\", \"Lorraine\", 37)\n", + "arr.insert(\"Yee\", \"Tom\", 43)\n", + "arr.insert(\"Adams\", \"Henry\", 63)\n", + "arr.insert(\"Hashimoto\", \"Sato\", 21)\n", + "arr.insert(\"Stimson\", \"Henry\", 29)\n", + "arr.insert(\"Velasquez\", \"Jose\", 72)\n", + "arr.insert(\"Lamarque\", \"Henry\", 54)\n", + "arr.insert(\"Vang\", \"Minh\", 22)\n", + "arr.insert(\"Creswell\", \"Lucinda\", 18)\n", + "arr.displayA()\n", + "searchKey = \"Stimson\"\n", + "found=arr.find(searchKey)\n", + "if(found != None ):\n", + " print \"Found \" ,\n", + " found.displayPerson()\n", + "else:\n", + " print \"Can't find \" , searchKey\n", + "print \"Deleting Smith, Yee, and Creswell\"\n", + "arr.delete(\"Smith\")\n", + "arr.delete(\"Yee\")\n", + "arr.delete(\"Creswell\")\n", + "arr.displayA()" + ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", - "text": "Last name: Evans , First name: Patty , Age: 24\nLast name: Smith , First name: Lorraine , Age: 37\nLast name: Yee , First name: Tom , Age: 43\nLast name: Adams , First name: Henry , Age: 63\nLast name: Hashimoto , First name: Sato , Age: 21\nLast name: Stimson , First name: Henry , Age: 29\nLast name: Velasquez , First name: Jose , Age: 72\nLast name: Lamarque , First name: Henry , Age: 54\nLast name: Vang , First name: Minh , Age: 22\nLast name: Creswell , First name: Lucinda , Age: 18\nFound Last name: Stimson , First name: Henry , Age: 29\nDeleting Smith, Yee, and Creswell\nLast name: Evans , First name: Patty , Age: 24\nLast name: Adams , First name: Henry , Age: 63\nLast name: Hashimoto , First name: Sato , Age: 21\nLast name: Stimson , First name: Henry , Age: 29\nLast name: Velasquez , First name: Jose , Age: 72\nLast name: Lamarque , First name: Henry , Age: 54\nLast name: Vang , First name: Minh , Age: 22\n" + "text": [ + "Last name: Evans , First name: Patty , Age: 24\n", + "Last name: Smith , First name: Lorraine , Age: 37\n", + "Last name: Yee , First name: Tom , Age: 43\n", + "Last name: Adams , First name: Henry , Age: 63\n", + "Last name: Hashimoto , First name: Sato , Age: 21\n", + "Last name: Stimson , First name: Henry , Age: 29\n", + "Last name: Velasquez , First name: Jose , Age: 72\n", + "Last name: Lamarque , First name: Henry , Age: 54\n", + "Last name: Vang , First name: Minh , Age: 22\n", + "Last name: Creswell , First name: Lucinda , Age: 18\n", + "Found Last name: Stimson , First name: Henry , Age: 29\n", + "Deleting Smith, Yee, and Creswell\n", + "Last name: Evans , First name: Patty , Age: 24\n", + "Last name: Adams , First name: Henry , Age: 63\n", + "Last name: Hashimoto , First name: Sato , Age: 21\n", + "Last name: Stimson , First name: Henry , Age: 29\n", + "Last name: Velasquez , First name: Jose , Age: 72\n", + "Last name: Lamarque , First name: Henry , Age: 54\n", + "Last name: Vang , First name: Minh , Age: 22\n" + ] } ], "prompt_number": 5 @@ -121,7 +459,7 @@ { "cell_type": "code", "collapsed": false, - "input": "", + "input": [], "language": "python", "metadata": {}, "outputs": [] |