Exercise 1
在以下六个项目中，需要修改下面定义的 Array 类，使其更像 Python 的 list 类。对于每个解决方案，请包括修改后的 Array 类代码。
-
在
Array类中添加一个实例变量logical_size。这个变量初始值为 0，用于跟踪当前可用的元素数量。然后为Array类添加一个size()方法，该方法应返回数组的逻辑大小。__len__方法仍然返回数组的容量或物理大小。 -
为
Array类的__getitem__和__setitem__方法添加前置条件。每个方法的前置条件为0 <= index < size()。如果前置条件不满足，应引发异常 (IndexError)。 -
在
Array类中添加grow和shrink方法。这些方法应使用本章中讨论的策略来增加或减少数组中列表的长度（增加：double 和 减少：Halve， 即可）。确保数组的物理大小不会缩小到用户指定的容量以下，并且在增加数组大小时，数组的单元格使用填充值。 -
在
Array类中添加insert和pop方法。这些方法应使用本章中讨论的策略，包括必要时调整数组的长度（可以使用grow和shrink方法来调整）。insert方法接受一个位置和一个元素作为参数，并在指定位置插入该元素。如果位置大于或等于数组的逻辑大小，该方法会在当前可用元素的最后一个元素之后插入该元素。pop方法接受一个位置作为参数，删除并返回该位置的元素。pop方法的前置条件是0 <= index < size()。remove方法还应将被删除的数组单元格重置为填充值。 -
为
Array类添加__eq__方法。当Array对象作为==运算符的左操作数时，Python 会调用此方法。如果参数也是一个Array对象，且逻辑大小相同，并且在每个逻辑位置上的元素对相等，则该方法返回True；否则，返回False。 -
小明建议小红移除
Array类当前的__iter__方法，如果它确实表现得像一个列表的话。解释为什么这是一个好的建议，并说明此时应如何修改__str__方法。
1class Array:
2 """数组表示。"""
3
4 def __init__(self, capacity, fill_value=None):
5 """
6 使用给定的容量和填充值初始化数组。
7
8 参数:
9 capacity (int): 数组的静态大小。
10 fill_value (Any, optional): 填充每个位置的值。默认为 None。
11 """
12 self._items = [fill_value] * capacity
13 self._logical_size = 0
14
15 def size(self):
16 """返回数组的逻辑大小。"""
17 pass
18
19 def __len__(self):
20 """返回数组的容量。"""
21 return len(self._items)
22
23 def __str__(self):
24 """返回数组的字符串表示形式。"""
25 return str(self._items[: self._logical_size])
26
27 def __iter__(self):
28 """支持使用 for 循环遍历。"""
29 for index in range(self._logical_size):
30 yield self._items[index]
31
32 def __getitem__(self, index):
33 """
34 访问指定索引处的元素。
35
36 参数:
37 index (int): 要访问的元素的索引。
38
39 返回:
40 Any: 指定索引处的元素。
41
42 异常:
43 IndexError: 如果索引超出范围。
44 """
45 pass
46
47 def __setitem__(self, index, new_item):
48 """
49 用新元素替换指定索引处的元素。
50
51 参数:
52 index (int): 要替换的元素的索引。
53 new_item (Any): 放置在指定索引处的新元素。
54
55 异常:
56 IndexError: 如果索引超出范围。
57 """
58 pass
59
60 def grow(self):
61 """将数组的容量加倍。"""
62 pass
63
64 def shrink(self):
65 """将数组的容量减半。"""
66 pass
67
68 def insert(self, index, item):
69 """
70 在指定索引处插入元素。
71
72 参数:
73 index (int): 插入元素的位置。
74 item (Any): 要插入的元素。
75
76 异常:
77 IndexError: 如果索引超出范围。
78 """
79 pass
80
81 def pop(self, index):
82 """
83 移除并返回指定索引处的元素。
84
85 参数:
86 index (int): 要移除元素的位置。
87
88 返回:
89 Any: 指定索引处的元素。
90
91 异常:
92 IndexError: 如果索引超出范围。
93 """
94 pass
95
96 def __eq__(self, other):
97 """
98 检查两个数组是否相等。
99
100 参数:
101 other (Array): 要比较的另一个数组。
102
103 返回:
104 bool: 如果数组相等则返回 True，否则返回 False。
105 """
106 pass
可以使用如下 main() 函数对以上任务进行测试：
1def main():
2 array = Array(10)
3
4 # 插入数据
5 array.insert(0, 1)
6 array.insert(1, 2)
7 array.insert(2, 3)
8 array.insert(1, 4) # 在位置1插入4
9
10 # 打印数组逻辑大小和物理大小
11 print("数组的逻辑大小:", array.size())
12 print("数组的物理大小:", len(array))
13
14 # 打印数组
15 print("数组:", array)
16
17 # 弹出数据
18 item = array.pop(1) # 从位置1弹出元素
19 print("弹出元素:", item)
20
21 # 打印修改后的数组
22 print("修改后的数组:", array)
23
24 # 检查数组是否相等
25 array2 = Array(10)
26 array2.insert(0, 1)
27 array2.insert(1, 3)
28 print("数组相等:", array == array2)
结果如下：
1数组的逻辑大小: 4
2数组的物理大小: 10
3数组: [1, 4, 2, 3]
4弹出元素: 4
5修改后的数组: [1, 2, 3]
6数组相等: False
Exercise 2
接下来的四个小项目要求定义一些用于操作链表的函数。请使用下面定义的 Node 和 TwowayNode 类。
-
定义一个名为
length的函数（不是len），该函数接受一个单链表作为参数，返回链表中的元素数量。 -
定义一个名为
insert的函数，在给定位置将元素插入单链表中。函数接受三个参数：元素、位置和链表（链表可以为空）。函数返回修改后的链表结构。如果位置大于或等于链表的长度，函数会在链表末尾插入元素。函数调用示例：head = insert(1, data, head)，其中 head 是指向链表第一个节点的变量，可以为空。 -
定义一个名为
pop的函数，从单链表的给定位置删除元素。函数接受一个位置作为第一个参数，前置条件为0 <= position < 链表长度。第二个参数是链表（链表不能为空）。函数返回一个元组，包含修改后的链表结构和被删除的元素。示例调用：head, item = pop(1, head)。 -
定义一个名为
makeTwoWay的函数，接受一个单链表作为参数。函数构建并返回一个包含单链表中元素的双链表（注意：函数不应改变参数链表的结构）。
1class Node:
2 """表示一个单向链表节点。"""
3
4 def __init__(self, data, next_node=None):
5 """
6 使用给定的数据和下一个节点初始化一个节点。
7
8 参数:
9 data (Any): 节点中存储的数据。
10 next_node (Node, optional): 链接到下一个节点。默认为 None。
11 """
12 self.data = data
13 self.next = next_node
14
15
16class TwoWayNode(Node):
17 """表示一个双向链表节点。"""
18
19 def __init__(self, data, previous_node=None, next_node=None):
20 """
21 使用给定的数据、前一个节点和下一个节点初始化一个双向节点。
22
23 参数:
24 data (Any): 节点中存储的数据。
25 previous_node (TwoWayNode, optional): 链接到前一个节点。默认为 None。
26 next_node (TwoWayNode, optional): 链接到下一个节点。默认为 None。
27 """
28 super().__init__(data, next_node)
29 self.previous = previous_node
30
31def length(head):
32 """
33 计算单链表的长度。
34
35 参数:
36 head (Node): 链表的头节点。
37
38 返回:
39 int: 链表中的节点数量。
40 """
41 pass
42
43
44def insert(position, data, head):
45 """
46 在指定位置插入元素到单链表中。
47
48 参数:
49 position (int): 插入位置。
50 data (Any): 插入的数据。
51 head (Node): 链表的头节点。
52
53 返回:
54 Node: 修改后的链表头节点。
55 """
56 pass
57
58
59def pop(position, head):
60 """
61 从单链表的指定位置删除元素。
62
63 参数:
64 position (int): 要删除元素的位置。
65 head (Node): 链表的头节点。
66
67 返回:
68 Tuple[Node, Any]: 修改后的链表头节点和被删除的元素。
69 """
70 pass
71
72
73def makeTwoWay(head):
74 """
75 将单链表转换为双向链表。
76
77 参数:
78 head (Node): 单链表的头节点。
79
80 返回:
81 TwoWayNode: 双向链表的头节点。
82 """
83 pass
可以使用如下 main() 函数对以上任务进行测试：
1def main():
2 head = None
3
4 # 插入数据
5 head = insert(0, 1, head)
6 head = insert(1, 2, head)
7 head = insert(2, 3, head)
8 head = insert(1, 4, head) # 在位置1插入4
9
10 # 打印链表长度
11 print("链表长度:", length(head))
12
13 # 打印链表
14 current = head
15 while current:
16 print(current.data, end=" -> ")
17 current = current.next
18 print("None")
19
20 # 弹出数据
21 head, item = pop(1, head) # 从位置1弹出元素
22 print("弹出元素:", item)
23
24 # 打印修改后的链表
25 current = head
26 while current:
27 print(current.data, end=" -> ")
28 current = current.next
29 print("None")
30
31 # 转换为双向链表并打印
32 two_way_head = makeTwoWay(head)
33 current = two_way_head
34 while current:
35 prev_data = current.previous.data if current.previous else "None"
36 next_data = current.next.data if current.next else "None"
37 print(f"[{prev_data} <- {current.data} -> {next_data}]")
38 current = current.next
结果如下：
1链表长度: 4
21 -> 4 -> 2 -> 3 -> None
3弹出元素: 4
41 -> 2 -> 3 -> None
5[None <- 1 -> 2]
6[1 <- 2 -> 3]
7[2 <- 3 -> None]