Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- """Den ska innehålla klassen UnorderedList.
- UnorderedList klassen ska följa klassdiagrammet ovanför.
- Minst de metoderna och attributen måste finnas i din implementation.
- Det är Ok att lägga till mer. """
- import random
- from node import Node
- from errors import IndexException, ValueException
- class UnorderedList:
- """ Class docstring for list uppgiften """
- def __init__(self):
- """ konstruktor för klass UnorderedList """
- self.head = None
- self.tail = None
- def is_empty(self):
- """ Metod kollar om massiv Ul är tomt """
- return self.head is None
- def add(self, data):
- """ Lägg till nytt element/nod sist i listan.(ett kädjelänken
- med data from Node) """
- if self.head is None:
- self.head = Node(data)
- self.tail = self.head
- else:
- self.tail.next = Node(data)
- self.tail = self.tail.next
- def insert(self, index, data):
- """Metod insert Lägg till nytt element/nod på specifikt index.
- Om index inte finns lyftas exception. """
- counter = 0
- previous = None
- current = self.head
- # next_node = None
- if self.head is None:
- self.head = Node(data)
- self.tail = self.head
- return
- if counter == index:
- current = self.head
- self.head = Node(data)
- self.head.next = current
- return
- if self.size() == index:
- self.tail.next = Node(data)
- self.tail = self.tail.next
- return
- if self.size() > index:
- while True:
- if counter == index:
- if previous and current.next:
- previous.next = Node(data)
- previous.next.next = current
- return
- counter += 1
- if counter:
- previous = current
- current = current.next
- else:
- raise IndexException()
- def set(self, index, data):
- """ Metod set:Skrivas över element med ny data som finns på index.
- Om index inte finns lyftas exception. """
- counter = 0
- current = self.head
- if self.head is None:
- raise IndexException()
- if self.size() > index:
- while True:
- if counter == index:
- current.data = data
- if current.next is None:
- break
- current = current.next
- counter += 1
- else:
- raise IndexException()
- def size(self):
- """Returnera antaler element i listan. """
- current = self.head
- if current is None:
- return 0
- count = 1
- while current.next != None:
- current = current.next
- count += 1
- return count
- def get(self, index):
- """ Returnerar värde på index. Om index inte finns lyftas exception."""
- count = 0
- current = self.head
- while True:
- if count == index:
- return current.data
- if current.next is None:
- raise IndexException()
- current = current.next
- count += 1
- def index_of(self, data):
- """ Om data finns i listan returnera dess index.
- Om nod med data inte finns lyftas exception. """
- current = self.head
- index = 0
- if current is None:
- pass
- else:
- while True:
- if current.data == data:
- return index
- if current.next is None:
- break
- current = current.next
- index += 1
- raise ValueException()
- def print_list(self):
- """ Skrivas ut listans innehåll av alla elementer. """
- current = self.head
- string = "["
- if current != None:
- while current.next != None:
- string += str(current.data) + ", "
- current = current.next
- string += str(current.data)
- else:
- pass
- string += "]"
- print(string)
- def remove(self, data):
- """ Ta bort nod med samma data.
- Om nod med data inte finns lyftas exception. """
- counter = 0
- previous = None
- current = self.head
- next_node = None
- if current is None:
- return
- while True:
- if current.next:
- next_node = current.next
- if current.data == data:
- if previous and next_node:
- previous.next = next_node
- if previous and not current.next:
- previous.next = None
- if not previous and next_node:
- self.head = next_node
- return
- counter += 1
- if current.next is None:
- raise ValueException()
- if counter:
- previous = current
- current = current.next
- def insertion_sort(self,):
- head = self.head
- if not head:
- return head
- dummy = Node(0)
- dummy.next = head
- lastSorted = head
- while lastSorted.next:
- if lastSorted.next.data < lastSorted.data:
- tmp = dummy
- while tmp.next.data < lastSorted.next.data:
- tmp = tmp.next
- nextToSort = lastSorted.next
- lastSorted.next = nextToSort.next
- nextToSort.next = tmp.next
- tmp.next = nextToSort
- else:
- lastSorted = lastSorted.next
- self.head = dummy.next
- def bubble_sort(self):
- flags = False
- current = self.head
- if current is None:
- return
- if current.next is None:
- return
- while True:
- next_node = current.next
- if next_node:
- if current.data > next_node.data:
- temp_curr = current.data
- temp_next = next_node.data
- current.data = temp_next
- next_node.data = temp_curr
- flags = True
- current = current.next
- if current.next is None:
- if flags:
- self.bubble_sort()
- break
- if __name__ == '__main__':
- unolist = UnorderedList()
- for _ in range(10):
- unolist.add(random.randint(1, 10))
- unolist.print_list()
- print("=============")
- # unolist.bubble_sort()
- unolist.insertion_sort()
- unolist.print_list()
- print(unolist.tail.data)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement