Jan-09-2018, 12:14 PM
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
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.
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.