I Can't Get This Sorting Function In This LinkedList Code To Work - Printable Version +- Python Forum (https://python-forum.io) +-- Forum: Python Coding (https://python-forum.io/forum-7.html) +--- Forum: Homework (https://python-forum.io/forum-9.html) +--- Thread: I Can't Get This Sorting Function In This LinkedList Code To Work (/thread-7410.html) Pages:
1
2
|
I Can't Get This Sorting Function In This LinkedList Code To Work - JayJayOi - Jan-09-2018 Hi everyone, I am new here and the question that I am posting here is part of my School Assignment For Data And Algorithms. This Is The Question For The Assignment Uncle Tom started his Secondhand Bookstore in 2000. Over The Years, the amount of books in his store increased significantly. He Has asked you to develop A Program In Python To assist him in managing his book inventory. Your program should fulfill the following requirement: a. AddBookToFront(newBook) : This method will create a new Node with the new Book object as its data value and then add the newly created node to the front of the linked list. b. AddBookAtPosition(newBook, n) : This method will create a new Node with the new Book object as its data value and then add the newly created node at position n of the linked list. Assume that the first node of the linked list has a position number of 0 and the second node has a position number of 1 and so on. c. RemoveBookAtPosition(n): This method will remove the node at position n in the linked list. Assume that the first node of the linked list has a position number of 0 and the second node has a position number of 1 and so on. d. DisplayBook(): This method will traverse the linked list from its first node to its last node and print the data value (i.e., the id, bookName and authorName of the Book object) of each node. e. SortByAuthorName(): This method will sort the linked list by the book author’s name in ascending order. Notes: • You are allowed to make changes to the LinkedList and Node classes as you deemed fit. • You are not allowed to use List for this question. • You are not allowed to use any existing Python libraries to do sorting. • Your solution should use objects and classes effectively. • You are to write your own script to test your solutions. Current Completion Status: I have completed all the objectives except the sortByAuthorName objective that I have tried to code but am still unable to get the code to run. My Current Completed Code class Node: def __init__(self, val, next_ref): self.val = val; self.next = next_ref; head= None; class LinkedList: def AddBookToFront(val): global head; new_node = Node(val, None) new_node.next = head head = new_node # inserts new node at specific position in singly linked list. def AddBookAtPosition(val, position): global head; current_node = head; while(position > 1): position -= 1; current_node = current_node.next; temp_next = current_node.next; node = Node(val, temp_next); current_node.next = node; # prints singly linked list values. def DisplayBook(): global head; print("Single linked list"); current_node = head; print ("head -->",); while(current_node is not None): print (current_node.val, "-->",); current_node = current_node.next; print ("End"); def RemoveBookAtPosition(position): global head; # If linked list is empty if head == None: return # Store head node temp = head # If head needs to be removed if position == 0: head = temp.next temp = None return # Find previous node of the node to be deleted for i in range(position -1 ): temp = temp.next if temp is None: break # If position is more than number of nodes if temp is None: return if temp.next is None: return # Node temp.next is the node to be deleted # store pointer to the next of node to be deleted next = temp.next.next # Unlink the node from linked list temp.next = None temp.next = next def mergeLists(l1, l2): temp = None if l1 is None: return l2 if l2 is None: return l1 if l1.data <= l2.data: temp = l1 temp.next = mergeLists(l1.next, l2) else: temp = l2 temp.next = mergeLists(l1, l2.next) return temp # Defining function which will sort the linked list using mergeSort def mergeSort(): global head; if head is None or head.next is None: return head l1, l2 = divideList(head) l1 = mergeSort(l1) l2 = mergeSort(l2) head = mergeLists(l1, l2) return head # Defining function which will divide a linked list into two equal linked lists def divideList(): global head; slow = head # slow is a pointer to reach the mid of linked list fast = head # fast is a pointer to reach the end of the linked list if fast: fast = fast.next while fast: fast = fast.next # fast is incremented twice while slow is incremented once per loop if fast: fast = fast.next slow = slow.next mid = slow.next slow.next = None return head, mid ll=LinkedList ll.AddBookToFront(10); ll.AddBookToFront(20); ll.DisplayBook(); ll.AddBookToFront(30); ll.DisplayBook(); ll.AddBookAtPosition(45, 2); print ("After insert node at 2"); ll.DisplayBook(); ll.RemoveBookAtPosition(2) print ("After removal of node @ 2nd position"); ll.DisplayBook(); ll.mergeSort()Output Log: Single linked list head --> 20 --> 10 --> End Single linked list head --> 30 --> 20 --> 10 --> End After insert node at 2 Single linked list head --> 30 --> 20 --> 45 --> 10 --> End After removal of node @ 2nd position Single linked list head --> 30 --> 20 --> 10 --> End Traceback (most recent call last): File "C:\Users\TP_baseline\Desktop\DSAG\ProjecTest4.py", line 124, in <module> ll.mergeSort() File "C:\Users\TP_baseline\Desktop\DSAG\ProjecTest4.py", line 90, in mergeSort l1, l2 = divideList(head) NameError: name 'divideList' is not defined I have been trying to fix this issue for the whole day but to no avail. Any guidance or advise to guide me to rectifying this error would be greatly appreciated. RE: I Can't Get This Sorting Function In This LinkedList Code To Work - mpd - Jan-09-2018 First of all, you're doing your class kind of wrong. Every class method has a self argument with which you reference variables and methods within that class.So instead of: head = None class Linked: def foo(): global head head = Node()You should have this: class Linked: def __init__(self): """This is the class constructor. You can initialize "member variables" here. """ self.head = None def AddBookToFront(self, val): # you can reference head with self.head tmp = self.head self.head = Node() self.head.next = tmpThen to reference other methods within the same class, you also use self: class Linked: def __init__(self): """This is the class constructor. You can initialize "member variables" here. """ self.head = None def mergeSort(self): # do stuff... self.divideList(self.head)In any event you can't call divideList because it's part of the LinkedList class. It might work if you call LinkedList.divideList(head) but you should really consider making the other changes I mentioned because that's the correct way to write classes in Python.Edited to add: You don't create class instances ("instantiate") a class with ll = LinkedList ; that just creates an alias or another way to refer to LinkedList.You create a class instance with: ll = LinkedList() which invokes the constructor.
RE: I Can't Get This Sorting Function In This LinkedList Code To Work - JayJayOi - Jan-09-2018 (Jan-09-2018, 12:58 PM)mpd Wrote: First of all, you're doing your class kind of wrong. Every class method has a Thanks MPD, still trying to figure my way through Python. Would you mind if I PM you my rectified code after I have it rectified ? Thanks A Million Jay RE: I Can't Get This Sorting Function In This LinkedList Code To Work - mpd - Jan-09-2018 Quote:Would you mind if I PM you my rectified code after I have it rectified ?If the code works, you don't have to do anything. If you're still having problems you should keep posting in this thread. RE: I Can't Get This Sorting Function In This LinkedList Code To Work - JayJayOi - Jan-09-2018 Hi Everyone, Just An Update Here, I have followed the First Answer By MPD and corrected my code and this is the corrected code as per my understanding from MPD's answer.. class Node: def __init__(self, val): self.val = val; self.next = None; class LinkedList: def __init__(self): self.head = None def AddBookToFront(self,val): # 1 & 2: Allocate the Node & # Put in the data new_node = Node(val) # 3. Make next of new Node as head new_node.next = self.head # 4. Move the head to point to new Node self.head = new_node # inserts new node at specific position in singly linked list. def AddBookAtPosition(self, val, position): current_node = self.head; while(position > 1): position -= 1; current_node = current_node.next; temp_next = current_node.next; node = Node(val, temp_next); current_node.next = node; # prints singly linked list values. def DisplayBook(self): print("Single linked list"); current_node = self.head; print ("head -->",); while(current_node is not None): print (current_node.val, "-->",); current_node = current_node.next; print ("End"); def RemoveBookAtPosition(self,position): # If linked list is empty if self.head == None: return # Store head node temp = self.head # If head needs to be removed if position == 0: self.head = temp.next temp = None return # Find previous node of the node to be deleted for i in range(position -1 ): temp = temp.next if temp is None: break # If position is more than number of nodes if temp is None: return if temp.next is None: return # Node temp.next is the node to be deleted # store pointer to the next of node to be deleted next = temp.next.next # Unlink the node from linked list temp.next = None temp.next = next def mergeLists(l1, l2): temp = None if l1 is None: return l2 if l2 is None: return l1 if l1.data <= l2.data: temp = l1 temp.next = mergeLists(l1.next, l2) else: temp = l2 temp.next = mergeLists(l1, l2.next) return temp # Defining function which will sort the linked list using mergeSort def mergeSort(self): if self.head is None or self.head.next is None: return head l1, l2 = self.divideList(self.head) l1 = mergeSort(l1) l2 = mergeSort(l2) head = mergeLists(l1, l2) return head # Defining function which will divide a linked list into two equal linked lists def divideList(self): slow = self.head # slow is a pointer to reach the mid of linked list fast = self.head # fast is a pointer to reach the end of the linked list if fast: fast = fast.next while fast: fast = fast.next # fast is incremented twice while slow is incremented once per loop if fast: fast = fast.next slow = slow.next mid = slow.next slow.next = None return head, mid ll=LinkedList() ll.AddBookToFront(10); ll.AddBookToFront(20); ll.DisplayBook(); ll.AddBookToFront(30); ll.DisplayBook(); ll.AddBookAtPosition(45,2) print ("After insert node at 2"); ll.DisplayBook(); ll.RemoveBookAtPosition(2) print ("After removal of node @ 2nd position"); ll.DisplayBook(); ll.mergeSort(ll.head)The Areas Of Code That Are Showing Up As Errors Are def AddBookAtPosition(self, val, position): current_node = self.head; while(position > 1): position -= 1; current_node = current_node.next; temp_next = current_node.next; node = Node(val, temp_next); current_node.next = node;And def mergeLists(l1, l2): temp = None if l1 is None: return l2 if l2 is None: return l1 if l1.data <= l2.data: temp = l1 temp.next = mergeLists(l1.next, l2) else: temp = l2 temp.next = mergeLists(l1, l2.next) return temp # Defining function which will sort the linked list using mergeSort def mergeSort(self): if self.head is None or self.head.next is None: return head l1, l2 = self.divideList(self.head) l1 = mergeSort(l1) l2 = mergeSort(l2) head = mergeLists(l1, l2) return head # Defining function which will divide a linked list into two equal linked lists def divideList(self): slow = self.head # slow is a pointer to reach the mid of linked list fast = self.head # fast is a pointer to reach the end of the linked list if fast: fast = fast.next while fast: fast = fast.next # fast is incremented twice while slow is incremented once per loop if fast: fast = fast.next slow = slow.next mid = slow.next slow.next = None return head, midError Indications When I try To Use The AddBoookToPosition command I get this error message... When I try to run the sorting system My Code Output Is Thanks In Advance For Any Guidance For Me To Solve The Problem
RE: I Can't Get This Sorting Function In This LinkedList Code To Work - mpd - Jan-09-2018 Don't end your lines with semi-colons and look at how you're instantiating the Node in AddBookToPosition Also, your mergeLists methods should also be made into class methods. RE: I Can't Get This Sorting Function In This LinkedList Code To Work - JayJayOi - Jan-09-2018 def AddBookAtPosition(self, val, position): current_node = self.head while(position > 1): position -= 1 current_node = current_node.next temp_next = current_node.next node = Node(val, temp_next) current_node.next = nodeIs this code correct for the AddBookTo Position Code ? Also is there a mistake with the instantiating of the AddBookToPosition ? Thanks Again Jay RE: I Can't Get This Sorting Function In This LinkedList Code To Work - mpd - Jan-09-2018 What version of python are you running and on which OS? I don't know why it's complaining about AddBookToPosition it looks correct. When I copy/pasted your code and ran it in Python 2 and 3, I got this error:
RE: I Can't Get This Sorting Function In This LinkedList Code To Work - JayJayOi - Jan-10-2018 Hi MPD, I am using Python 3.6 on Windows 10 RE: I Can't Get This Sorting Function In This LinkedList Code To Work - mpd - Jan-10-2018 I get the same error on Windows as Linux: Look at how you've defined the __init__ method in Node and then how you're invoking it (i.e., creating a new Node object) at line 27 in AddBookAtPosition.
|