Похожие презентации:
Intro2CS. Tirgul 9
1. Intro2CS
INTRO2CSTirgul 9
2. What We’ll Be Seeing Today
2Linked lists
Debugger
Ex 9
Student enrollment system
3.
Linked Lists3
Separate the logical order of items from their
physical order in memory
Each item points to the location of the next item
Dynamically expands list as needed
Linked lists may also be used to implement other
data structures, like queues and stacks
Always remember that when a link to an item is
destroyed – the item can not be reached!
4. Important!
4The two most common mistakes regarding lists are:
Disconnecting
without keeping a pointer to the head/tail of
the list.
Trying to get the next of the trailing None.
5. Class Node
5class Node:
def __init__(self, data=None, next=None):
self.__data = data
self.__next = next
def __str__(self):
return str(self.__data)
def get_data(self):
return self.__data
def get_next(self):
return self.__next
def set_data(self,data):
self.__data = data
def set_next(self,next):
self.__next = next
6. class Linked List
17
class Linked List
6
class LinkedList:
def __init__(self, head=None):
self.__head = head
def get_head(self):
return self.__head
def is_empty(self):
return self.__head == None
def add(self,new_head):
new_head.set_next(self.__head)
self.__head = new_head
7. class Linked List (cont)
77
class LinkedList:
def __len__(self):
current = self.__head
count = 0
while current is not None:
count = count + 1
current = current.get_next()
return count
def r_index(self, item):
return self.index_helper(self.__head, item, 0)
def index_helper(self, head, item, index):
if index >= self.__len__():
return -1
if head.get_data() == item:
return index
return self.index_helper(head.get_next(), item,
index+1)
8. Reversing a list (O(n) complexity)
8class LinkedList:
def rev_list1(self):
current = self.__head
self.__head = None
while current is not None:
next = current.get_next()
self.add(current)
current = next
9. Can we do any better? Improved implementation of linked lists
9Add:
a length variable
in init: self.__length = 0
update in add/remove
append?
hold a pointer to the tail
going backwards?
doubly linked list
10. Doubly-linked list with a tail
10Sometimes it is convenient that we can add and
remove items from both ends of the linked-list (e.g. if
we want to use it both as a stack and a queue)
To support this methods we will need a doublylinked list with both head and a tail
11. A doubly-linked list with a tail
11class Node:
def __init__(self, data, prev=None, next=None):
self.data = data
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.__head = self.__tail = None
self.__length = 0
12. A doubly-linked list with a tail
12def add_first(self, node):
if self.__head is None:
# list was empty
self.__tail = node
else: #connect old head to new node
self.__head.prev = node;
node.next = self.__head
# update head
self.__head = node
self.__length +=1
13. A doubly-linked list with a tail
13def add_last(self, node):
if self.__tail is None:
# list was empty
self.__head = node
else: #connect old tail to new node
self.__tail.next = node;
node.prev = self.__tail
# update tail
self.__tail = node
self.__length+=1
14. A doubly-linked list with a tail
14def remove_first(self):
d = self.__head.data
self.__head = self.__head.next
if self.__head is None: # list is now empty
self.__tail = None
else: # disconnect old head
self.__head.prev.next = None
self.__head.prev = None
self.__length -=1
return d
15. A doubly-linked list with a tail
15def remove_last(self):
d = self.__tail.data
self.__tail = self.__tail.prev
if self.__tail is None: # list is now empty
self.__head = None
else: # disconnect old tail
self.__tail.next.prev = None
self.__tail.next = None
self.__length -=1
return d;
What does this method
assume?
That the list is not empty
16. Linked Lists vs. Python’s List
16Operation
Linked List
Python’s list
Insert at head
O(1)
O(n)
Insert at middle
O(n), O(1) given a reference
O(n)
Remove from head
O(1)
O(n)
Remove from middle
O(n), O(1) given a reference
O(n)
Find k-th element
O(k)
O(1)
Search unsorted
O(n)
O(n)
Search sorted
O(n)
O(log n)
17. Debugging with debugger
17def mult_nums_in_list(numbers, mult):
for num in numbers:
num *= mult
return numbers
def add_to_end_of_list(numbers, addition):
for num in numbers:
new_num = num + addition
numbers.append(new_num)
return numbers
print(add_to_end_of_list(mult_nums_in_list([1,2,3],2),2))
18. Debugging with debugger
18def mult_nums_in_list(numbers, mult):
for num in numbers: #should be for num in range(len(numbers))
num *= mult
# numbers[num] *= mult
return numbers
def add_to_end_of_list(numbers, addition):
for num in numbers:
new_num = num + addition
numbers.append(new_num) # list extends. Endless loop
return numbers
print(add_to_end_of_list(mult_nums_in_list([1,2,3],2),2))
19. Add a break point
1920. Run Debugger
2021. List of Variables
2122. Add variable to be watched
2223. Step over/into/out
23Step over
24. Step over/into/out
24Step into
25. Step over/into/out
25Step out
26. Ex 9
2627. Ex 9 – Playing With Objects
27You will only be given a Screen class that handles
all of the graphics for you
All of the actual design is left to you!
Most of the time games (and programs) are event
driven:
Move right/left if a key pressed.
Fire when requested to.
Reduce HP if got shot.
We will take a more sequential approach.
28. Ex 9 – Game Loop
28We can think that everything happens in the
same time!
All objects (ship, asteroids, torpedoes) move
one after the other.
Only then we fire/accelerate (if requested)
More in the exercise.
Note: Try to implement it step by step (as
described in the exercise description).
29. Question from the exam 2015:
2930. Q from the exam
3031. Q from the exam
3132. Q from the exam
3233. Q from the exam
3334. Q from the exam
3435. Q from the exam
3536. Stacks and Queues
36A stack is a last in, first out (LIFO) data structure
Items
are removed from a stack in the reverse order from
the way they were inserted
A queue is a first in, first out (FIFO) data structure
Items
are removed from a queue in the same order as they
were inserted
37. Queues API
37Queues (LIFO): What would be the API?
what are the functions required in order to use
it?
class MyQueue:
def __init__(self):
def enqueue(self,item):
def dequeue(self):
def get_size(self):
38. Implementing Queue
38class MyQueue:
def __init__(self):
self.__head = None
self.__tail = None
self.__size = 0
def get_size(self):
return self.__size
def is_empty(self):
if self.__size > 0:
return False
else:
return True
39. Adding new item to the queue
39def enqueue(self, item):
if self.__tail == None:
self.__head = Node(item)
self.__tail = self.__head
else:
# adding new item to the end of the list
self.__tail.next = Node(item)
self.__tail = self.__tail.next
self.__size += 1
40. Removing an item from the queue
40def dequeue(self, item):
result = self.__head.data
self.__head = self.__head.next
if self.__head == None:
self.__tail = None
self.__size -= 1
return result
41. Student Enrollment System
41We want to design a system where students could
register to courses
What is the most basic expected behavior from such
a system?
List all courses
Enroll into a course
Withdraw from a course
42. Thinking In Interfaces
42We need to think about the properties of our
enrollment class:
Available courses?
Map students to courses?
Keep track of registered students?
Do we need to think on how we design
students/courses at this stage?
43. Application Programming Interface
43An “Application Programming Interface” (API) is a
way for us to expose the behavior of our objects
without the actual way it was implemented.
Consider the list construct:
The list object exposes a method called “sort” –
does it matter which sort algorithm is used?
Most of the time what interest us is the final result.
44. Student Enrollment System - API
44class EnrollmentSystem:
__init__(self)
add_student(self, student):
add_course(self, course)
get_available_courses(self)
register_student(self, student, course_id)
Class Student:
get_id()
add_course(self, cid)
Class Course
get_id()
is_full()
register(self, sid)
45. Enrollment System Class
45class EnrollmentSystem:
def __init__(self):
self.__courses = {}
self.__students = {}
What are our assumptions?
def add_student(self, student):
# How can we map a student to a student object?
self.__students[ student.get_id() ] = student
def add_course(self, course):
# How can we map a course to a course object?
self.__courses[ course.get_id() ] = course
46. Enrollment System Class
46class EnrollmentSystem:
def __init__(self):
self.__courses = {}
self.__students = {}
…
def get_available_courses(self):
courses = []
for course_id, course in self.__courses.items():
if not course.is_full():
courses.append( ( course_id, course.get_name() ) )
return courses
What are our assumptions?
47. Enrollment System Class
47What about registration?
class EnrollmentSystem:
def __init__(self):
self.__courses = {}
What are our assumptions?
self.__students = {}
…
def register_student(self, student, course_id):
if course_id in self.__courses:
registered = self.__courses[ course_id ].register( student.get_id()
if registered:
student.add_course( course_id )
return registered
48. What did we assume so far?
48Course
get_id()
is_full()
register(sid)
Student
get_id()
add_course(cid)
Do the EnrollmentSystem care how
we implement these methods?
49. Student Class
49Lets implement our basic student class
class Student:
def __init__(self, student_id):
self.__enrolled_courses = set()
self.__id = student_id
def get_id(self):
return self.__id
def add_course(self, course_id):
self.__enrolled_courses.add( course_id )
50. Course Class
50class Course:
def __init__(self, course_id, course_capacity):
self.__enrolled_students = set()
self.__id = course_id
self.__capacity = course_capacity
def get_id(self):
return self.__id
def register(self, student_id):
if student_id not in self.__enrolled_students and not self.is_full():
self.__enrolled_students.add(student_id)
return True
return False
def is_full(self):
return self.__capacity == len(self.__enrolled_students)
51. Putting things together
51We want to create an actual program using our
enrollment system
A user should be able to:
Add courses to the system
Register users to courses
52. Our main loop
52from student import Student
from course import Course
from system import EnrollmentSystem
def get_user_selection():
return int(input(“Enter selection:”) )
def main_loop():
es = EnrollmentSystem()
while True:
option = get_user_selection()
perform_selction(option, es)
…
def perform_selection(option, es):
if option == 1:
print_courses(es)
elif option == 2:
register_new_student(es)
elif option == 3:
create_new_course(es)
elif option == 4:
register_student_to_course(es)
else:
print(“Please insert a valid option”)
53. What’s next?
53Well a lot is missing from the system
Actual implementation of the methods
Withdrawing from a course
Removing a course
Course info?
…
We can always come back and extend our system
54. To OOP or not to OOP? – A word on being cautious
54Not everything should be solved by new objects.
You should always think about the overhead of
working with them.
For example, should you create a class to represent
2D points or could you just use tuples?