- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Intro2CS. Tirgul 9 презентация
Содержание
- 1. Intro2CS. Tirgul 9
- 2. What We’ll Be Seeing Today Linked lists
- 3. Linked Lists Separate the logical order of
- 4. Important! The two most common mistakes regarding
- 5. Class Node 5 class Node:
- 6. class Linked List 17 class LinkedList:
- 7. class Linked List (cont) class LinkedList:
- 8. Reversing a list (O(n) complexity) class LinkedList:
- 9. Can we do any better? Improved implementation
- 10. Doubly-linked list with a tail Sometimes it
- 11. A doubly-linked list with a tail class
- 12. A doubly-linked list with a tail
- 13. A doubly-linked list with a tail
- 14. A doubly-linked list with a tail
- 15. A doubly-linked list with a tail
- 16. Linked Lists vs. Python’s List
- 17. Debugging with debugger def mult_nums_in_list(numbers, mult):
- 18. Debugging with debugger def mult_nums_in_list(numbers, mult):
- 19. Add a break point
- 20. Run Debugger
- 21. List of Variables
- 22. Add variable to be watched
- 23. Step over/into/out Step over
- 24. Step over/into/out Step into
- 25. Step over/into/out Step out
- 26. Ex 9
- 27. Ex 9 – Playing With Objects You
- 28. Ex 9 – Game Loop We can
- 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 A stack is a
- 37. Queues API Queues (LIFO): What would be
- 38. Implementing Queue class MyQueue: def
- 39. Adding new item to the queue def
- 40. Removing an item from the queue def
- 41. Student Enrollment System We want to design
- 42. Thinking In Interfaces We need to think
- 43. Application Programming Interface An “Application Programming Interface”
- 44. Student Enrollment System - API class EnrollmentSystem:
- 45. Enrollment System Class class EnrollmentSystem:
- 46. Enrollment System Class class EnrollmentSystem:
- 47. Enrollment System Class What about registration? class
- 48. What did we assume so far? Course
- 49. Student Class class Student: def
- 50. Course Class class Course: def
- 51. Putting things together We want to create
- 52. Our main loop from student import Student
- 53. What’s next? Well a lot is missing
- 54. To OOP or not to OOP? –
What We’ll Be Seeing Today Linked lists Debugger Ex 9 Student enrollment system
Слайд 3Linked Lists
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!
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!
Слайд 4Important!
The 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.
Trying to get the next of the trailing None.
Слайд 5Class Node
5
class 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
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
Слайд 6class Linked List
17
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
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
6
Слайд 7class Linked List (cont)
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)
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)
7
Слайд 8Reversing a list (O(n) complexity)
class 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
while current is not None:
next = current.get_next()
self.add(current)
current = next
Слайд 9Can we do any better?
Improved implementation of linked lists
Add:
a length variable
in init: self.__length = 0
update in add/remove
append?
hold a pointer to the tail
going backwards?
doubly linked list
Слайд 10Doubly-linked list with a tail
Sometimes 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 doubly-linked list with both head and a tail
To support this methods we will need a doubly-linked list with both head and a tail
10
Слайд 11A doubly-linked list with a tail
class 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
self.data = data
self.prev = prev
self.next = next
class DoublyLinkedList:
def __init__(self):
self.__head = self.__tail = None
self.__length = 0
Слайд 12A doubly-linked list with a tail
def 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
# 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
Слайд 13A doubly-linked list with a tail
def 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
# 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
Слайд 14A doubly-linked list with a tail
def 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
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
Слайд 15A doubly-linked list with a tail
def 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;
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;
Слайд 17Debugging with debugger
def 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))
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))
Слайд 18Debugging with debugger
def 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))
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))
Слайд 27Ex 9 – Playing With Objects
You 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.
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.
Слайд 28Ex 9 – Game Loop
We 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).
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).
Слайд 36Stacks and Queues
A 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
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
36
Слайд 37Queues API
Queues (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):
Слайд 38Implementing Queue
class 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
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
38
Слайд 39Adding new item to the queue
def 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
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
39
Слайд 40Removing an item from the queue
def dequeue(self, item):
result =
self.__head.data
self.__head = self.__head.next
if self.__head == None:
self.__tail = None
self.__size -= 1
return result
self.__head = self.__head.next
if self.__head == None:
self.__tail = None
self.__size -= 1
return result
40
Слайд 41Student Enrollment System
We 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
What is the most basic expected behavior from such a system?
List all courses
Enroll into a course
Withdraw from a course
Слайд 42Thinking In Interfaces
We 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?
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?
Слайд 43Application Programming Interface
An “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.
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.
Слайд 44Student Enrollment System - API
class 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)
Class Course
get_id()
is_full()
register(self, sid)
Слайд 45Enrollment System Class
class EnrollmentSystem:
def __init__(self):
self.__courses
= {}
self.__students = {}
def add_student(self, student):
# How can we map a student to a student object?
def add_course(self, course):
# How can we map a course to a course object?
self.__students = {}
def add_student(self, student):
# How can we map a student to a student object?
def add_course(self, course):
# How can we map a course to a course object?
self.__students[ student.get_id() ] = student
self.__courses[ course.get_id() ] = course
What are our assumptions?
Слайд 46Enrollment System Class
class 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
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?
Слайд 47Enrollment System Class
What about registration?
class EnrollmentSystem:
def __init__(self):
self.__courses =
{}
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
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
What are our assumptions?
Слайд 48What did we assume so far?
Course
get_id()
is_full()
register(sid)
Student
get_id()
add_course(cid)
Do the EnrollmentSystem care how we
implement these methods?
Слайд 49Student 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 )
return self.__id
def add_course(self, course_id):
self.__enrolled_courses.add( course_id )
Lets implement our basic student class
Слайд 50Course Class
class 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)
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)
Слайд 51Putting things together
We 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
A user should be able to:
Add courses to the system
Register users to courses
Слайд 52Our main loop
from 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 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”)
Слайд 53What’s next?
Well 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
Withdrawing from a course
Removing a course
Course info?
…
We can always come back and extend our system
Слайд 54To OOP or not to OOP? – A word on being
cautious
Not 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?
