Похожие презентации:

# 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

19## 20. Run Debugger

20## 21. List of Variables

21## 22. Add variable to be watched

22## 23. Step over/into/out

23Step over

## 24. Step over/into/out

24Step into

## 25. Step over/into/out

25Step out

## 26. Ex 9

26## 27. 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:

29## 30. Q from the exam

30## 31. Q from the exam

31## 32. Q from the exam

32## 33. Q from the exam

33## 34. Q from the exam

34## 35. Q from the exam

35## 36. 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?