{ "metadata": { "name": "", "signature": "sha256:0f4233c9bc3c7a3995f155be01ebee4b829ac86b3935e6b7d37705fb0fea5376" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Chapter 12: Data Structures" ] }, { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Example 12.1, page no. 442" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import numpy\n", "arr = numpy.zeros((2, 2, 2))\n", "\n", "print \"Reading the elements of an array: \"\n", "for i in range(2):\n", " for j in range(2):\n", " for k in range(2):\n", " arr[i][j][k] = int(raw_input())\n", "\n", "print \"Displaying the elements of an array: \"\n", "for i in range(2):\n", " print \"\\n\\t\"\n", " for j in range(2):\n", " for k in range(2):\n", " print \"\\t %3d \" %(arr[i][j][k]),\n", " print \"\\n\\t\"" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Reading the elements of an array: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "15\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "25\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "26\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "13\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "71\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "9\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "8\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Displaying the elements of an array: \n", "\n", "\t\n", "\t 15 \t 25 \n", "\t\n", "\t 26 \t 13 \n", "\t\n", "\n", "\t\n", "\t 71 \t 9 \n", "\t\n", "\t 1 \t 8 \n", "\t\n" ] } ], "prompt_number": 1 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.2, page no. 442" ] }, { "cell_type": "code", "collapsed": false, "input": [ "str1 = raw_input(\"Input the first string: \")\n", "str2 = raw_input(\"Input the second string: \")\n", "print \"The concatenated string is ...\"\n", "print str1+str2" ], "language": "python", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Input the first string: Tejaswi \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Input the second string: Venugopal\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The concatenated string is ...\n", "Tejaswi Venugopal\n" ] } ], "prompt_number": 3 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.3, page no. 443" ] }, { "cell_type": "code", "collapsed": false, "input": [ "class record:\n", " name = ''\n", " regno = ''\n", " avg = 0.0\n", " rank = 0\n", "i = 0\n", "students = []\n", "while True:\n", " print \"Processing student %d record...\" %(i+1)\n", " print \"Student name ?(END to terminate): \"\n", " stud = record()\n", " stud.name = raw_input()\n", " if stud.name == 'END':\n", " break\n", " else:\n", " stud.regno = raw_input(\"Reg. no? \")\n", " stud.avg = float(raw_input(\"Average marks? \"))\n", " students.append(stud)\n", " i+=1\n", "n = i\n", "for i in range(n-1):\n", " for j in range(i+1, n):\n", " if students[i].avg < students[j].avg:\n", " students[i], students[j] = students[j], students[i]\n", "for i in range(n):\n", " students[i].rank = i+1\n", "print \"Student records after assigning ranks: \"\n", "print \"%s%20s%20s%20s\" %(\"Name\",\"REGISTER_NUMBER\",\"AVERAGE\",\"RANK\")\n", "print \"------------------------------------------------------------------\"\n", "for i in range(n):\n", " print students[i].name, \"\\t\\t\", students[i].regno, \"\\t\\t\\t\", students[i].avg, \"\\t\\t\\t\", students[i].rank" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 1 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Asha\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak001\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 67.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 2 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Bina\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak003\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 34.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 3 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Anand\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak004\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 67.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 4 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Sudeep\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak005\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 78.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 5 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Tejaswi\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak006\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 89.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 6 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Maya\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak007\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 89.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 7 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Prakash\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak008\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 89.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 8 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Raju\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak009\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 82.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 9 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Geetha\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak010\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 85.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 10 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Gopi\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak011\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 45.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 11 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Ganesh\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Reg. no? ak012\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Average marks? 89.00\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Processing student 12 record...\n", "Student name ?(END to terminate): \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "END\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Student records after assigning ranks: \n", "Name REGISTER_NUMBER AVERAGE RANK\n", "------------------------------------------------------------------\n", "Tejaswi \t\tak006 \t\t\t89.0 \t\t\t1\n", "Maya \t\tak007 \t\t\t89.0 \t\t\t2\n", "Prakash \t\tak008 \t\t\t89.0 \t\t\t3\n", "Ganesh \t\tak012 \t\t\t89.0 \t\t\t4\n", "Geetha \t\tak010 \t\t\t85.0 \t\t\t5\n", "Raju \t\tak009 \t\t\t82.0 \t\t\t6\n", "Sudeep \t\tak005 \t\t\t78.0 \t\t\t7\n", "Anand \t\tak004 \t\t\t67.0 \t\t\t8\n", "Asha \t\tak001 \t\t\t67.0 \t\t\t9\n", "Gopi \t\tak011 \t\t\t45.0 \t\t\t10\n", "Bina \t\tak003 \t\t\t34.0 \t\t\t11\n" ] } ], "prompt_number": 17 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.4, page no. 446" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import numpy\n", "arr = numpy.zeros((3,3))\n", "print \"Reading the elements of 2-D array: \"\n", "for i in range(3):\n", " for j in range(3):\n", " arr[i][j] = int(raw_input())\n", "print \"Displaying the elements of 2-D array: \"\n", "p = arr\n", "for i in range(3):\n", " for j in range(3):\n", " print \"arr[%d][%d] = %d\" %(i, j, p[i][j]),\n", " print \"\\tAddress of arr[%d][%d] = %d\" %(i, j, id(p[i][j]))" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Reading the elements of 2-D array: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "5\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "6\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "7\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "8\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "9\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Displaying the elements of 2-D array: \n", "arr[0][0] = 1 \tAddress of arr[0][0] = 52403744\n", "arr[0][1] = 2 \tAddress of arr[0][1] = 57791200\n", "arr[0][2] = 3 \tAddress of arr[0][2] = 55892528\n", "arr[1][0] = 4 \tAddress of arr[1][0] = 55892528\n", "arr[1][1] = 5 \tAddress of arr[1][1] = 55892528\n", "arr[1][2] = 6 \tAddress of arr[1][2] = 51486976\n", "arr[2][0] = 7 \tAddress of arr[2][0] = 58587952\n", "arr[2][1] = 8 \tAddress of arr[2][1] = 50218032\n", "arr[2][2] = 9 \tAddress of arr[2][2] = 50218032\n" ] } ], "prompt_number": 21 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.5, page no. 449" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import sys\n", "\n", "class node:\n", " def __init__(self, data=0, link=None):\n", " self.data = data\n", " self.link = link\n", "\n", "start = None\n", " \n", "def add_front(data):\n", " global start\n", " tmp = node(data)\n", " if(start == None):\n", " start = tmp\n", " else:\n", " tmp.link = start\n", " start = tmp\n", "\n", "def del_pos(pos):\n", " global start\n", " if (pos == 0):\n", " tmp = start\n", " start = start.link\n", " return\n", " q = start\n", " count = 1\n", " while(q.link != None):\n", " if(count == pos):\n", " tmp = q.link\n", " q.link = tmp.link\n", " return\n", " count += 1\n", " q = q.link\n", " print \"\\n\\nThere is no element at %d position\" %pos\n", " \n", "def del_elem(data):\n", " global start\n", " if (start.data == data):\n", " tmp = start\n", " start = start.link\n", " return\n", " q = start\n", " while(q.link.link != None):\n", " if(q.link.data == data):\n", " tmp = q.link\n", " q.link = tmp.link\n", " return\n", " q = q.link\n", " if(q.link.data == data):\n", " tmp = q.link;\n", " q.link = None\n", " return\n", " print \"\\n\\nThere is no element whose value is %d\" %data\n", "\n", "def display_list():\n", " global start\n", " if(start == None):\n", " print \"\\n\\nList empty\"\n", " return\n", " q=start\n", " print \"\\nThe List is...\"\n", " while(q != None):\n", " print q.data,\n", " q = q.link\n", " print \"\\n\"\n", "\n", "def get_data():\n", " data = int(raw_input(\"Enter the data: \"))\n", " return data\n", "\n", "while(1):\n", " print \"\\n1.Insert at the beginning of the list\"\n", " print \"2.Delete an element at a give position\"\n", " print \"3.Delete an element with a give value\"\n", " print \"4.Quit\"\n", " print \"Choice: \",\n", " choice =int(raw_input())\n", " if choice == 1:\n", " data = get_data()\n", " add_front(data)\n", " elif choice == 2:\n", " if (start == None):\n", " print \"\\nList empty\"\n", " continue\n", " print \"\\n\\nEnter the position:\"\n", " pos = int(raw_input())\n", " del_pos(pos)\n", " elif choice == 3:\n", " if (start == None):\n", " print \"\\nList empty\"\n", " continue\n", " data = get_data()\n", " del_elem(data)\n", " elif choice == 4:\n", " break\n", " display_list()" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "The List is...\n", "0 \n", "\n", "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: 1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "The List is...\n", "1 0 \n", "\n", "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: 2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "The List is...\n", "2 1 0 \n", "\n", "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: 3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "The List is...\n", "3 2 1 0 \n", "\n", "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: 4\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "The List is...\n", "4 3 2 1 0 \n", "\n", "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "\n", "Enter the position:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "The List is...\n", "4 2 1 0 \n", "\n", "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: 1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "The List is...\n", "4 2 0 \n", "\n", "\n", "1.Insert at the beginning of the list\n", "2.Delete an element at a give position\n", "3.Delete an element with a give value\n", "4.Quit\n", "Choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n" ] } ], "prompt_number": 22 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.6, page no. 454" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import sys\n", "\n", "class node:\n", " def __init__(self, info=None, link=None):\n", " self.info = info\n", " self.link = link\n", "\n", "last = None\n", "class Circular_Linked:\n", " def create(self, num):\n", " global last\n", " q = node()\n", " tmp = node()\n", " tmp.info = num\n", " if (last == None):\n", " last = tmp\n", " tmp.link = last\n", " else:\n", " tmp.link = last.link\n", " last.link = tmp\n", " last = tmp\n", "\n", " def insert(self, num, pos):\n", " global last\n", " q = node()\n", " tmp = node()\n", " q = last.link\n", " for i in range(0, pos-1):\n", " q = q.link\n", " if (q == last.link):\n", " print \"There are less than \", pos, \" elements\"\n", " return\n", " tmp.link = q.link\n", " tmp.info = num\n", " q.link = tmp\n", " if(q==last):\n", " last=tmp\n", "\n", " def delete(self):\n", " global last\n", " if(last == None):\n", " print \"LIST EMPTY - CANNOT DELETE\"\n", " return\n", " print \"Data item to be deleted:\"\n", " num = int(raw_input())\n", " q = node()\n", " tmp = node()\n", " if( last.link == last and last.info == num):\n", " tmp = last\n", " last = None\n", " return\n", " q = last.link\n", " if(q.info == num):\n", " tmp = q\n", " last.link = q.link\n", " return\n", " while(q.link != last):\n", " if(q.link.info == num):\n", " tmp = q.link\n", " q.link = tmp.link\n", " print num, \" deleted\"\n", " q = q.link\n", " if(q.link.info == num):\n", " tmp = q.link\n", " q.link = last.link\n", " last = q\n", " return\n", " print \"Element not found\"\n", "\n", " def display(self):\n", " global last\n", " q = node()\n", " if(last == None):\n", " print \"List is empty\"\n", " return\n", " q = last.link\n", " print \"List is:\"\n", " while(q != last):\n", " print q.info,\n", " q = q.link\n", " print last.info\n", " \n", "co = Circular_Linked()\n", "while(1):\n", " print \"\\n1.Create Circular Linked List\"\n", " print \"2.Insert an item\"\n", " print \"3.Delete an item\"\n", " print \"4.STOP\"\n", " print \"Enter your choice:\"\n", " choice = int(raw_input())\n", " if choice == 1:\n", " print \"How many nodes you want:\",\n", " n = int(raw_input())\n", " for i in range(n):\n", " print \"\\nEnter the element:\",\n", " m = int(raw_input())\n", " co.create(m)\n", " elif choice == 2:\n", " print \"\\nEnter the element:\",\n", " m = int(raw_input())\n", " print \"\\nEnter the position after which this element is inserted:\",\n", " po = int(raw_input())\n", " co.insert(m,po)\n", " elif choice == 3:\n", " co.delete()\n", " elif choice == 4:\n", " break\n", " else:\n", " print \"Error - Try again\"\n", " co.display()" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " \n", "1.Create Circular Linked List\n", "2.Insert an item\n", "3.Delete an item\n", "4.STOP\n", "Enter your choice:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "How many nodes you want:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "Enter the element:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "Enter the element:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "Enter the element:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "Enter the element:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " List is:\n", "1 2 3 4\n", "\n", "1.Create Circular Linked List\n", "2.Insert an item\n", "3.Delete an item\n", "4.STOP\n", "Enter your choice:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "How many nodes you want:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "Enter the element:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "5\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " List is:\n", "1 2 3 4 5\n", "\n", "1.Create Circular Linked List\n", "2.Insert an item\n", "3.Delete an item\n", "4.STOP\n", "Enter your choice:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "Enter the element:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " \n", "Enter the position after which this element is inserted:" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " List is:\n", "1 0 2 3 4 5\n", "\n", "1.Create Circular Linked List\n", "2.Insert an item\n", "3.Delete an item\n", "4.STOP\n", "Enter your choice:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Data item to be deleted:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "0 deleted\n", "Element not found\n", "List is:\n", "1 2 3 4 5\n", "\n", "1.Create Circular Linked List\n", "2.Insert an item\n", "3.Delete an item\n", "4.STOP\n", "Enter your choice:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Data item to be deleted:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "7\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Element not found\n", "List is:\n", "1 2 3 4 5\n", "\n", "1.Create Circular Linked List\n", "2.Insert an item\n", "3.Delete an item\n", "4.STOP\n", "Enter your choice:\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] } ], "prompt_number": 5 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.7, page no. 461" ] }, { "cell_type": "code", "collapsed": false, "input": [ "MAXSIZE = 100\n", "\n", "class stack:\n", " def __init__(self):\n", " self.stack = []\n", " self.top = -1\n", "\n", "def push(pu):\n", " if(pu.top == MAXSIZE-1):\n", " print \"The stack is full\"\n", " else:\n", " print \"Enter the element to be inserted: \"\n", " item = int(raw_input())\n", " pu.stack.append(item)\n", " pu.top += 1\n", "\n", "def pop(po):\n", " if(po.top == -1):\n", " print \"Stack is empty\"\n", " else:\n", " item = po.stack[po.top]\n", " po.top-=1\n", " print \"The popped element is: %d\" %item\n", "\n", "\n", "def display(pt):\n", " if(pt.top == -1):\n", " print \"Stack is empty\"\n", " else:\n", " print \"The element(s) of the stack are: \"\n", " i = pt.top\n", " while(i>=0):\n", " print \"%d\" %pt.stack[i],\n", " i-=1\n", "\n", "ps = stack()\n", "ch = 'y'\n", "\n", "while(1):\n", " print \"\\n1. Push into the stack\"\n", " print \"2. POP\"\n", " print \"3. View elements of the stack\"\n", " print \"4. Exit\"\n", " print \"Enter your choice: \"\n", " choice = int(raw_input())\n", " if(choice == 1):\n", " push(ps)\n", " elif(choice == 2):\n", " pop(ps)\n", " elif(choice == 3):\n", " display(ps)\n", " elif(choice == 4):\n", " break\n", " else:\n", " print \"Invalid Choice\"" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Push into the stack\n", "2. POP\n", "3. View elements of the stack\n", "4. Exit\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the element to be inserted: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "12\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Push into the stack\n", "2. POP\n", "3. View elements of the stack\n", "4. Exit\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the element to be inserted: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "23\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Push into the stack\n", "2. POP\n", "3. View elements of the stack\n", "4. Exit\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the element to be inserted: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "67\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Push into the stack\n", "2. POP\n", "3. View elements of the stack\n", "4. Exit\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The popped element is: 67\n", "\n", "1. Push into the stack\n", "2. POP\n", "3. View elements of the stack\n", "4. Exit\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the element to be inserted: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "88\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Push into the stack\n", "2. POP\n", "3. View elements of the stack\n", "4. Exit\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The element(s) of the stack are: \n", "67 23 12 \n", "1. Push into the stack\n", "2. POP\n", "3. View elements of the stack\n", "4. Exit\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] } ], "prompt_number": 10 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.8, page no. 463" ] }, { "cell_type": "code", "collapsed": false, "input": [ "class node:\n", " def __init__(self, link=None):\n", " self.data = None\n", " self.link = link\n", " \n", "start = None\n", "\n", "\n", "def push(top):\n", " new = node()\n", " print \"Enter element to be pushed: \",\n", " pushed_item = int(raw_input())\n", " new.data = pushed_item\n", " new.link = top\n", " top = new\n", " return top\n", "\n", "def pop(top):\n", " tmp = node()\n", " if(top == None):\n", " print \"Stack is empty...\" \n", " else:\n", " tmp = top\n", " print \"Popped item is: \", tmp.data\n", " top = top.link\n", " tmp.link = None\n", " return top\n", "\n", "def display(top):\n", " if(top == None):\n", " print \"Stack is empty...\"\n", " else:\n", " while(top.link != None):\n", " print top.data,\n", " top = top.link\n", " \n", "Top = node()\n", "while(1):\n", " print \"\\n1.PUSH\"\n", " print \"2.POP\"\n", " print \"3.END\"\n", " print \"Enter your choice: \",\n", " choice = int(raw_input())\n", " if choice == 1:\n", " Top = push(Top)\n", " print \"STACK after pushing: \"\n", " display(Top)\n", " elif choice == 2:\n", " Top=pop(Top)\n", " print \"STACK after popping: \"\n", " display(Top)\n", " elif choice == 3:\n", " print \"End of comutation\"\n", " break\n", " else:\n", " print \"Invalid Choice\"" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Enter element to be pushed: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "23\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " STACK after pushing: \n", "23 \n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Enter element to be pushed: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "12\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " STACK after pushing: \n", "12 23 \n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Enter element to be pushed: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "67\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " STACK after pushing: \n", "67 12 23 \n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Popped item is: 67\n", "STACK after popping: \n", "12 23 \n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Popped item is: 12\n", "STACK after popping: \n", "23 \n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Enter element to be pushed: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "88\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " STACK after pushing: \n", "88 23 \n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Popped item is: 88\n", "STACK after popping: \n", "23 \n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Popped item is: 23\n", "STACK after popping: \n", "\n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Popped item is: None\n", "STACK after popping: \n", "Stack is empty...\n", "\n", "1.PUSH\n", "2.POP\n", "3.END\n", "Enter your choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " End of comutation\n" ] } ], "prompt_number": 2 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.9, page no. 467" ] }, { "cell_type": "code", "collapsed": false, "input": [ "stck = []\n", "\n", "def push(sp,ch):\n", " if sp==100:\n", " print \"Error : Stack overflow\"\n", " else:\n", " sp += 1\n", " stck.append(ch)\n", "\n", "def pop(sp):\n", " if sp < 0:\n", " print \"Error : Stack underflow\"\n", " return 0\n", " else:\n", " sp -= 1\n", " return stck[sp+1]\n", "\n", "def alpha(ch):\n", " if (ch>='A' and ch<=\"Z\") or (ch>='a' and ch<=\"z\"):\n", " return True\n", " else:\n", " return False\n", "\n", "def num(ch):\n", " if ch>='0' and ch<=\"9\":\n", " return True\n", " else:\n", " return False\n", "\n", "def oper(ch):\n", " oparray = ['+','-','*','/','^']\n", " if ch in oparray:\n", " return True\n", " else:\n", " return False\n", " \n", "def precedence(ch):\n", " if ch=='(':\n", " i = 0\n", " elif ch=='+' or ch=='-':\n", " i = 1\n", " elif ch=='*' or ch=='/':\n", " i = 2\n", " elif ch=='^':\n", " i = 3\n", " return i\n", "\n", "def printerror(n,ifp):\n", " if n==1:\n", " print \"Error_1_: Missing operator\",\n", " elif n==2:\n", " print \"Error_2_: Missing Operand\",\n", " elif n==3:\n", " print \"Error_3_: Mismatched parentehses\",\n", " elif n==4:\n", " print \"Error_4_: Illegal character in expression\",\n", " elif n==5:\n", " print \"Error_5_: Multiletter variable\",\n", " print \"Column %2d\"%ifp\n", " \n", "\n", "def parse (infix,suffix,error):\n", " ch =''\n", " last = '('\n", " i = 0\n", " sp=-1\n", " bracket = 1\n", " ifp = 0\n", " sfp = 0\n", " \n", " push(sp,'(')\n", " \n", " while True:\n", " while infix[i] == \" \":\n", " i += 1\n", " ifp = i\n", " ch = infix[ifp]\n", " \n", " if ch == \"(\":\n", " if alpha(last) or num(last) or last==')':\n", " error = 1\n", " printerror(1,ifp+1)\n", " bracket +=1 \n", " push(sp,ch)\n", " elif ch==\"+\" or ch==\"-\" or ch==\"*\" or ch==\"/\" or ch==\"^\":\n", " if oper(last) or (not alpha(last) and not num(last) and last!=\")\"):\n", " error=1\n", " printerror(2,ifp+1)\n", " while precedence(stck[sp]) >= precedence(ch):\n", " suffix.append(pop(sp))\n", " sfp+=1\n", " push(sp,ch)\n", " elif ch==\")\":\n", " if oper(last):\n", " error=1\n", " printerror(2,ifp+1)\n", " if last==\"(\":\n", " error=1\n", " printerror(2,ifp+1)\n", " printerror(1,ifp+1)\n", " while stck[sp] != \"(\" and sp > 0:\n", " suffix.append(pop(sp))\n", " sfp += 1\n", " sp -= 1\n", " bracket -= 1\n", " elif ch == ' ':\n", " while infix[ifp+1] == \" \" and not infix[ifp] :\n", " ifp += 1\n", " else:\n", " if alpha(last) or num(last):\n", " error = 1 \n", " printerror(1,ifp+1)\n", " printerror(5,ifp+1)\n", " if alpha(ch):\n", " print ch,\n", " suffix.append(infix[ifp])\n", " sfp += 1\n", " elif num(ch):\n", " while num(infix[ifp]):\n", " suffix.append(infix[ifp])\n", " ifp += 1\n", " sfp += 1\n", " ifp -= 1\n", " else:\n", " printerror(4,ifp+1)\n", " last = infix[ifp]\n", " ifp += 1\n", " i = ifp\n", " print ifp,\n", " try:\n", " if not infix[ifp]:\n", " break;\n", " except:\n", " break\n", " \n", " if bracket:\n", " error = 1\n", " printerror(3,ifp-1)\n", " return infix,suffix,error\n", "def readexpression():\n", " i = 0\n", " print \"The given infix expression is\"\n", " infix = list(raw_input())\n", " infix.append(\")\")\n", " \n", " return infix\n", "\n", "\n", "suffix = [] \n", "error = 0\n", "infix = readexpression()\n", "infix,suffix,error = parse(infix,suffix,error)\n", "if not error:\n", " print \"The suffix form of the given expression is \"\n", " print suffix" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "The given infix expression is\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "(a+b)\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "1 Error_3_: Mismatched parentehses Column 0\n", "a 2 Error_3_: Mismatched parentehses Column 1\n", "3 Error_3_: Mismatched parentehses Column 2\n", "b 4 Error_3_: Mismatched parentehses Column 3\n", "5 Error_3_: Mismatched parentehses Column 4\n", "6\n" ] } ], "prompt_number": 2 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.10, page no. 472" ] }, { "cell_type": "code", "collapsed": false, "input": [ "MAX = 50\n", "queue_arr = []\n", "rear = [-1]\n", "front = [-1]\n", "\n", "def add_element():\n", " if (rear[0] == MAX-1):\n", " print \"Queue is full...\"\n", " return\n", " else:\n", " if(front[0] == -1):\n", " front[0] = 0\n", " print \"Enter the new element: \"\n", " added_item = int(raw_input())\n", " rear[0] = rear[0]+1\n", " queue_arr.append(added_item)\n", "\n", "def remove_element():\n", " if(front[0] == -1 or front[0]>rear[0]):\n", " print \"Queue is empty...\"\n", " return\n", " else:\n", " dell = front[0]\n", " print queue_arr[dell], \" is removed from the Queue\"\n", " front[0] = front[0]+1\n", "\n", "def display():\n", " if(front[0] == -1 or front[0]>rear[0]):\n", " print \"Queue is empty...\"\n", " return\n", " else:\n", " print \"Queue is: \"\n", " for i in range(front[0],rear[0]+1):\n", " print queue_arr[i],\n", "\n", "while(1):\n", " print \"\\n1. Insert an element\"\n", " print \"2. Display all the elements of the queue\"\n", " print \"3. Remove elements from the queue\"\n", " print \"4. Exit from the program\"\n", " print \"Enter your choice: \"\n", " choice = raw_input()\n", " if choice == '1':\n", " add_element()\n", " elif choice == '2':\n", " display()\n", " elif choice == '3':\n", " remove_element()\n", " elif choice == '4':\n", " break\n", " else:\n", " print \"Reenter the choice\"" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the new element: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "23\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the new element: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "34\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the new element: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "45\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "23 is removed from the Queue\n", "\n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "34 is removed from the Queue\n", "\n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Enter the new element: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "45\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Queue is: \n", "45 45 \n", "1. Insert an element\n", "2. Display all the elements of the queue\n", "3. Remove elements from the queue\n", "4. Exit from the program\n", "Enter your choice: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] } ], "prompt_number": 3 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.11, page no. 477" ] }, { "cell_type": "code", "collapsed": false, "input": [ "class node:\n", " def __init__(self, link=None):\n", " self.info = None\n", " self.link = link\n", "\n", "def enqueue(rear):\n", " new_node = node()\n", " print \"Enter the new element: \",\n", " new_node.info = int(raw_input())\n", " new_node.link = None\n", " if (rear != None):\n", " rear.link = new_node\n", " rear = new_node\n", " return rear\n", "\n", "def del_queue(f, r):\n", " if f == None:\n", " print \"The Queue is empty\"\n", " else:\n", " print \"The element removed is: \", f.info\n", " if f != r:\n", " f = f.link\n", " else:\n", " f = None\n", " return f\n", "\n", "def display(fr, re):\n", " if fr == None:\n", " print \"The Queue is empty\"\n", " else:\n", " print \"The queue is: \"\n", " while fr != re:\n", " print fr.info,\n", " fr = fr.link\n", " print fr.info,\n", "\n", "rear = None\n", "front = None\n", "while(1):\n", " print \"\\n1.Insert\"\n", " print \"2.Delete\"\n", " print \"3.Quit\"\n", " print \"Enter choice: \",\n", " choice = int(raw_input())\n", " if choice == 1:\n", " rear = enqueue(rear)\n", " if front == None:\n", " front = rear\n", " elif choice == 2:\n", " front = del_queue(front, rear)\n", " if front == None:\n", " rear = None\n", " elif choice == 3:\n", " break\n", " display(front, rear)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " \n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Enter the new element: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "23\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " The queue is: \n", "23 \n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Enter the new element: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "34\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " The queue is: \n", "23 34 \n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " Enter the new element: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "45\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " The queue is: \n", "23 34 45 \n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " The element removed is: 23\n", "The queue is: \n", "34 45 \n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " The element removed is: 34\n", "The queue is: \n", "45 \n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " The element removed is: 45\n", "The Queue is empty\n", "\n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ " The Queue is empty\n", "The Queue is empty\n", "\n", "1.Insert\n", "2.Delete\n", "3.Quit\n", "Enter choice: " ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n" ] } ], "prompt_number": 6 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 12.12, page no. 480" ] }, { "cell_type": "code", "collapsed": false, "input": [ "import numpy\n", "\n", "qsize = 50\n", "rear = 0\n", "front = 0\n", "qu = numpy.zeros(50, dtype=numpy.int)\n", "def insert():\n", " global rear\n", " global front\n", " global qsize\n", " if rear == qsize:\n", " rear = 1\n", " else:\n", " rear += 1\n", " if front != rear:\n", " item = int(raw_input(\"Enter item to be inserted: \"))\n", " qu[rear] = item\n", " if front == 0:\n", " front += 1\n", " else:\n", " print \"Overflow\"\n", "def delete():\n", " global front\n", " global rear\n", " global qsize\n", " if front != 0:\n", " item = qu[front]\n", " if front == rear:\n", " front = 0\n", " rear = 0\n", " return item\n", " if front == qsize:\n", " front = 1\n", " else:\n", " front += 1\n", " return item\n", " else:\n", " print \"Underflow\"\n", "def display():\n", " global front\n", " global rear\n", " for i in range(front, rear+1):\n", " print qu[i],\n", "\n", "choice = 0\n", "while(choice != 3):\n", " print \"\\n1 - Insert an element into Cqueue\"\n", " print \"2 - Delete an element into Cqueue\"\n", " print \"3 - Quit\"\n", " choice = int(raw_input())\n", " if choice == 1:\n", " insert()\n", " print \"\\nCqueue after insertion is: \"\n", " display()\n", " elif choice == 2:\n", " item = delete()\n", " print \"Item deleted id: \", item\n", " print \"\\nCqueue after deletion is: \"\n", " display()\n", " else:\n", " break" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ " \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter item to be inserted: 23\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "Cqueue after insertion is: \n", "23 \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter item to be inserted: 34\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "Cqueue after insertion is: \n", "23 34 \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter item to be inserted: 45\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "Cqueue after insertion is: \n", "23 34 45 \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Item deleted id: 23\n", "\n", "Cqueue after deletion is: \n", "34 45 \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Item deleted id: 34\n", "\n", "Cqueue after deletion is: \n", "45 \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Item deleted id: 45\n", "\n", "Cqueue after deletion is: \n", "0 \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "Underflow\n", "Item deleted id: None\n", "\n", "Cqueue after deletion is: \n", "0 \n", "1 - Insert an element into Cqueue\n", "2 - Delete an element into Cqueue\n", "3 - Quit\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] } ], "prompt_number": 22 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Exmaple 9.13, page no. 484" ] }, { "cell_type": "code", "collapsed": false, "input": [ "class node:\n", " data = ''\n", " next = None\n", "class queue:\n", " front = None\n", " nremovals = 0\n", "\n", "class prique:\n", " queues = []\n", " nqueues = 0\n", " npromote = 0\n", "\n", "def add(que, new_node):\n", " new_node.next = 0\n", " if not que.front:\n", " que.front = new_node\n", " else:\n", " cur = que.front\n", " while(cur.next):\n", " cur = cur.next\n", " cur.next = new_node\n", " return que\n", "\n", "def remove_node(que):\n", " removed_node = que.front\n", " if que.front:\n", " que.front = que.front.next\n", " return removed_node\n", "\n", "def priq_add(priq, priority, data):\n", " if priority >= priq.nqueues:\n", " print \"Error: priority number given is invalid!\"\n", " return priq\n", " new_node = node()\n", " new_node.data = data\n", " priq.queues[priority] = add(priq.queues[priority], new_node)\n", " return priq\n", "\n", "def priq_remove(priq, priority):\n", " removed_char = ''\n", " if priority >= priq.nqueues:\n", " print \"Error: priority number given is invalid!\"\n", " return\n", " removed = remove_node(priq.queues[priority])\n", " if not removed:\n", " if priority < priq.nqueues-1:\n", " return priq_remove(priq, priority+1)\n", " else:\n", " return priq, 0\n", " else:\n", " lower_elm = ''\n", " priq.queues[priority].nremovals += 1\n", " if priq.queues[priority].nremovals == priq.npromote:\n", " lower_elm = priq_remove(priq, priority+1)\n", " if lower_elm:\n", " priq_add(priq, priority, lower_elm)\n", " priq.queues[priority].nremovals = 0\n", " removed_char = removed.data\n", " return priq, removed_char\n", "\n", " \n", "def create_priq(nqueues, npromote):\n", " priq = prique()\n", " priq.nqueues = nqueues\n", " for i in range(nqueues):\n", " priq.queues.append(queue())\n", " priq.npromote = npromote\n", " return priq\n", "\n", "def get_option():\n", " print \"\\n1: Insert an element\"\n", " print \"2: Remove an element\"\n", " print \"3: Quit\"\n", " print \"Choose: \"\n", " option = int(raw_input())\n", " return option\n", "\n", "def get_data():\n", " data = raw_input(\"Enter the data: \")\n", " return data\n", "\n", "def get_priority():\n", " priority = int(raw_input(\"Enter the priority: \"))\n", " return priority\n", "\n", "def display_prique(priq):\n", " print \"The priority queue is ...\"\n", " for i in range(priq.nqueues):\n", " que = priq.queues[i]\n", " cur = que.front\n", " print i,\n", " while cur:\n", " print cur.data,\n", " if cur.next:\n", " print \"->\",\n", " cur = cur.next\n", " print \"\"\n", " print \"\"\n", "\n", "print \"No of priority levels: \"\n", "nlevels = int(raw_input())\n", "print \"No of consecutive removls for proirity promotion: \"\n", "nremovals = int(raw_input())\n", "priq = create_priq(nlevels, nremovals)\n", "while True:\n", " option = get_option()\n", " if option == 1:\n", " data = get_data()\n", " priority = get_priority()\n", " priq = priq_add(priq, priority, data)\n", " elif option == 2:\n", " priority = get_priority()\n", " priq, data = priq_remove(priq, priority)\n", " if data == 0:\n", " print \"No elements to remove\"\n", " else:\n", " print data, \" was removed\"\n", " elif option == 3:\n", " break\n", " else:\n", " print \"BYE\"\n", " break\n", " display_prique(priq)" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "No of priority levels: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "No of consecutive removls for proirity promotion: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: q\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The priority queue is ...\n", "0 q \n", "1 \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: w\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The priority queue is ...\n", "0 q -> w \n", "1 \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: e\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The priority queue is ...\n", "0 q -> w -> e \n", "1 \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: r\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The priority queue is ...\n", "0 q -> w -> e -> r \n", "1 \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the data: z\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "The priority queue is ...\n", "0 q -> w -> e -> r \n", "1 z \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "q was removed\n", "The priority queue is ...\n", "0 w -> e -> r \n", "1 z \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "w was removed\n", "The priority queue is ...\n", "0 e -> r \n", "1 z \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "No elements to remove\n", "The priority queue is ...\n", "0 e -> r \n", "1 z \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "e was removed\n", "The priority queue is ...\n", "0 r \n", "1 z \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "Enter the priority: 0\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "r was removed\n", "The priority queue is ...\n", "0 \n", "1 z \n", "2 \n", "3 \n", "\n", "\n", "1: Insert an element\n", "2: Remove an element\n", "3: Quit\n", "Choose: \n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] } ], "prompt_number": 5 }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Example 9.14, page no. 495" ] }, { "cell_type": "code", "collapsed": false, "input": [ "class Node:\n", " def __init__(self, data):\n", " self.data = data\n", " self.left = None\n", " self.right = None\n", "\n", " def insert(self, data):\n", " if data < self.data:\n", " if self.left is None:\n", " self.left = Node(data)\n", " else:\n", " self.left.insert(data)\n", " elif data > self.data:\n", " if self.right is None:\n", " self.right = Node(data)\n", " else:\n", " self.right.insert(data)\n", "\n", " def inorder(self, tree):\n", " solution = []\n", " def recurse(node):\n", " if not node:\n", " return\n", " recurse(node.left)\n", " solution.append(node.data)\n", " recurse(node.right)\n", " recurse(tree)\n", " return solution\n", " def preorder(self, tree):\n", " solution = []\n", " def recurse(node):\n", " if not node:\n", " return\n", " solution.append(node.data)\n", " recurse(node.left)\n", " recurse(node.right)\n", " recurse(tree)\n", " return solution\n", " def postorder(self, tree):\n", " solution = []\n", " def recurse(node):\n", " if not node:\n", " return\n", " recurse(node.left)\n", " recurse(node.right)\n", " solution.append(node.data)\n", "\n", " recurse(tree)\n", " return solution\n", "\n", "print \"Type numbers, one per line\"\n", "print \"-999 for terminating\"\n", "num = int(raw_input())\n", "tree = Node(num)\n", "while num != -999:\n", " num = int(raw_input())\n", " if num == -999:\n", " break\n", " tree.insert(num)\n", "choice = 0\n", "while choice != 4:\n", " print \"\\nType of TRAVERSAL ?\"\n", " print \"1 - Inorder\"\n", " print \"2 - Preorder\"\n", " print \"3 - Postorder\"\n", " print \"4 - STOP\"\n", " choice = int(raw_input())\n", " if choice == 1:\n", " print \"INORDER traversal: \"\n", " sol = tree.inorder(tree)\n", " for ele in sol:\n", " print ele,\n", " elif choice == 2:\n", " print \"PREORDER traversal: \"\n", " sol = tree.preorder(tree)\n", " for ele in sol:\n", " print ele,\n", " elif choice == 3:\n", " print \"POSTORDER traversal: \"\n", " sol = tree.postorder(tree)\n", " for ele in sol:\n", " print ele,\n", " else:\n", " print \"BYE\"" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Type numbers, one per line\n", "-999 for terminating\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "10\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "9\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "3\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "6\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "8\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "5\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "-999\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "\n", "Type of TRAVERSAL ?\n", "1 - Inorder\n", "2 - Preorder\n", "3 - Postorder\n", "4 - STOP\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "1\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "INORDER traversal: \n", "1 2 3 4 5 6 8 9 10 \n", "Type of TRAVERSAL ?\n", "1 - Inorder\n", "2 - Preorder\n", "3 - Postorder\n", "4 - STOP\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "2\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "PREORDER traversal: \n", "4 1 3 2 10 9 6 5 8 \n", "Type of TRAVERSAL ?\n", "1 - Inorder\n", "2 - Preorder\n", "3 - Postorder\n", "4 - STOP\n" ] }, { "name": "stdout", "output_type": "stream", "stream": "stdout", "text": [ "4\n" ] }, { "output_type": "stream", "stream": "stdout", "text": [ "BYE\n" ] } ], "prompt_number": 11 } ], "metadata": {} } ] }