讲解data编程、Python，CS程序语言辅导、Java编程讲解讲解数据库SQL|辅导留学生 Statistics统计、回归、迭代

项目预算：开发周期：发布时间：要求地区：

Default Dictionaries
The following code returns a dictionary with the word count for each word in a list of words.
def count_words(l):
d = {}
for word in l:
if word not in d:
d[word] = 1
else:
d[word] += 1
return d
Notice that we need to have two cases: one for if the word is not in the dictionary, and the other
for if it is.
We can shorten the code by using a default dictionary.
from collections import defaultdict
def count_words2(l):
d = defaultdict(int)
for word in l:
d[word] += 1
return d
When creating a default dictionary, we must pass it the type of the values that will be stored in
the dictionary. We can use any type that we want, including lists. The following code takes a list
of words as an argument and returns a dictionary containing lists of the words that have the same
first letter.
def list_words(dictionary_of_words):
d = defaultdict(list)
for word in dictionary_of_words:
d[word[0]].append(word)
return d
result = list_words(["antelope", "bear", "alligator", "aardvark", "cat", "bee"])
print(result)
1
Deques
So far in this course, we have been working with lists. A list is an object that is built on top of an
array. Arrays store elements in contiguous computer memory. This allows us constant time access
to any element in the array through indexing. Arrays do have a drawback, however. If we remove
the first element in an array, every other element in the array needs to be shifted to the left. In
other words, removing an element from a list can take linear time.
Figure 1: The list before the first element is removed.
Figure 2: The first element is removed.
Figure 3: The remaining elements must be shifted to the left.
A Deque is a double-ended queue which is implemented using a linked-list. Unlike with lists,
you can’t access elements in constant time. However, you can remove the first element of a deque
in constant time. Here is what a doubly linked-list looks like.
2
Figure 4: A doubly link list.
Tp remove the first element, simply remove the links off of the first element and have the headpointer
point to the second element. This can be done is constant time regardless of the length of
the linked list.
Deques can be used as both stacks and queues. Use the methods append() and pop() to emulate
a stack using a deque. The methods append() and popleft() can be used to emulate a queue.
The deque class must be imported before you can use it.
from collections import deque
To create an empty deque use
deque_name = deque()
Homework
1. Write a method called is balanced(s) that take a string of open and closed parentheses and
returns True if the string is balanced, False otherwise. The method should use a deque as a
stack.
For example, the following parentheses are balanced:
()()
(())()
While the following are not:
()(
))()
2. Write a method that implements breadth-first search on an undirected graph. Your method
should be called bfs(graph, start), where graph is a dictionary representation of a graph, and
start is the starting vertex. The vertices of the graph are number 0, 1, 2, 3, . . . , n. The
method should return a list containing the distance from the starting vertex for each vertex
in the graph.
Below is the psuedo-code for the method you will inplement:
Create a list that holds the distance of each vertex from the source vertex. Set distance
of the starting vertex to 0, the rest to infinity.
3
Create a queue and put the starting vertex on the queue.
while the queue has elements in it:
Remove the element at the front of the queue.
For each vertex that the element you removed is adjacent to in the graph, check to see if
that vertex has been visited yet using the distance list from above. If it hasn’t been visited,
then set its distance from the starting vertex and add it to the queue.
When the loop breaks, return the list of distances.
4

讲解data编程、Python，CS程序语言辅导、Java编程讲解 讲解数据库SQL|辅导留学生 Statistics统计、回归、迭代

讲解data编程、Python，CS程序语言辅导、Java编程讲解讲解数据库SQL|辅导留学生 Statistics统计、回归、迭代