ps1-solutions.pdf

Stirling’s approximation

image.png
image.png

Problem 1-3. [20 points] Binder Bookmarks

这个问题有意思

Problem 1-4. [44 points] Doubly Linked List

  1. class Doubly_Linked_List_Node:
  2.     def __init__(self, x):
  3.         self.item = x
  4.         self.prev = None
  5.         self.next = None
  7.     def later_node(self, i):
  8.         if i == 0: return self
  9.         assert self.next
  10.         return self.next.later_node(i - 1)
  12. class Doubly_Linked_List_Seq:
  13.     def __init__(self):
  14.         self.head = None
  15.         self.tail = None
  17.     def __iter__(self):
  18.         node = self.head
  19.         while node:
  20.             yield node.item
  21.             node = node.next
  23.     def __str__(self):
  24.         return '-'.join([('(%s)' % x) for x in self])
  26.     def build(self, X):
  27.         for a in X:
  28.             self.insert_last(a)
  30.     def get_at(self, i):
  31.         node = self.head.later_node(i)
  32.         return node.item
  34.     def set_at(self, i, x):
  35.         node = self.head.later_node(i)
  36.         node.item = x
  38.     def insert_first(self, x):
  39.         ###########################
  40.         # Part (a): Implement me! #
  41.         ###########################
  42.         item = Doubly_Linked_List_Node(x)
  43.         if self.head is None:
  44.             self.head = item
  45.             self.tail = item
  46.         else:
  47.             item.next = self.head
  48.             self.head.prev = item
  49.             self.head = item
  51.     def insert_last(self, x):
  52.         ###########################
  53.         # Part (a): Implement me! #
  54.         ###########################
  55.         item = Doubly_Linked_List_Node(x)
  56.         if self.tail is None:
  57.             self.head = item
  58.             self.tail = item
  59.         else:
  60.             item.prev = self.tail
  61.             self.tail.next = item
  62.             self.tail = item
  64.     def delete_first(self):
  65.         assert self.head
  66.         x = self.head.item
  67.         ###########################
  68.         # Part (a): Implement me! #
  69.         ###########################
  70.         self.head = self.head.next
  71.         if self.head is None:
  72.             self.tail = None
  73.         else:
  74.             self.head.prev = None
  75.         return x
  77.     def delete_last(self):
  78.         assert self.tail
  79.         x = self.tail.item
  80.         ###########################
  81.         # Part (a): Implement me! #
  82.         ###########################
  83.         self.tail = self.tail.prev
  84.         if self.tail is None:
  85.             self.head = None
  86.         else:
  87.             self.tail.next = None
  88.         return x
  90.     def remove(self, x1, x2):
  91.         L2 = Doubly_Linked_List_Seq()
  92.         ###########################
  93.         # Part (b): Implement me! # 
  94.         ###########################
  95.         L2.head = x1
  96.         L2.tail = x2
  97.         if x1 == self.head:
  98.             self.head = x2.next
  99.         else:
  100.             x1.prev.next = x2.next
  101.         if x2 == self.tail:
  102.             self.tail == x1.prev
  103.         else:
  104.             x2.next.prev = x1.prev
  105.         x1.prev = None
  106.         x2.next = None
  107.         return L2
  109.     def splice(self, x, L2):
  110.         ###########################
  111.         # Part (c): Implement me! # 
  112.         ###########################
  113.         xn = x.next
  114.         x1 = L2.head
  115.         x2 = L2.tail
  116.         L2.tail = None
  117.         L2.head = None
  118.         x1.prev = x
  119.         x.next = x1
  120.         x2.next = xn
  121.         if xn is None:
  122.             self.tail = x2
  123.         else:
  124.             xn.prev = x2