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.