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__方法。
class Array:
"""数组表示。"""
def __init__(self, capacity, fill_value=None):
"""
使用给定的容量和填充值初始化数组。
参数:
capacity (int): 数组的静态大小。
fill_value (Any, optional): 填充每个位置的值。默认为 None。
"""
self._items = [fill_value] * capacity
self._logical_size = 0
def size(self):
"""返回数组的逻辑大小。"""
pass
def __len__(self):
"""返回数组的容量。"""
return len(self._items)
def __str__(self):
"""返回数组的字符串表示形式。"""
return str(self._items[: self._logical_size])
def __iter__(self):
"""支持使用 for 循环遍历。"""
for index in range(self._logical_size):
yield self._items[index]
def __getitem__(self, index):
"""
访问指定索引处的元素。
参数:
index (int): 要访问的元素的索引。
返回:
Any: 指定索引处的元素。
异常:
IndexError: 如果索引超出范围。
"""
pass
def __setitem__(self, index, new_item):
"""
用新元素替换指定索引处的元素。
参数:
index (int): 要替换的元素的索引。
new_item (Any): 放置在指定索引处的新元素。
异常:
IndexError: 如果索引超出范围。
"""
pass
def grow(self):
"""将数组的容量加倍。"""
pass
def shrink(self):
"""将数组的容量减半。"""
pass
def insert(self, index, item):
"""
在指定索引处插入元素。
参数:
index (int): 插入元素的位置。
item (Any): 要插入的元素。
异常:
IndexError: 如果索引超出范围。
"""
pass
def pop(self, index):
"""
移除并返回指定索引处的元素。
参数:
index (int): 要移除元素的位置。
返回:
Any: 指定索引处的元素。
异常:
IndexError: 如果索引超出范围。
"""
pass
def __eq__(self, other):
"""
检查两个数组是否相等。
参数:
other (Array): 要比较的另一个数组。
返回:
bool: 如果数组相等则返回 True，否则返回 False。
"""
pass
可以使用如下 main() 函数对以上任务进行测试：
def main():
array = Array(10)
# 插入数据
array.insert(0, 1)
array.insert(1, 2)
array.insert(2, 3)
array.insert(1, 4) # 在位置1插入4
# 打印数组逻辑大小和物理大小
print("数组的逻辑大小:", array.size())
print("数组的物理大小:", len(array))
# 打印数组
print("数组:", array)
# 弹出数据
item = array.pop(1) # 从位置1弹出元素
print("弹出元素:", item)
# 打印修改后的数组
print("修改后的数组:", array)
# 检查数组是否相等
array2 = Array(10)
array2.insert(0, 1)
array2.insert(1, 3)
print("数组相等:", array == array2)
结果如下：
数组的逻辑大小: 4
数组的物理大小: 10
数组: [1, 4, 2, 3]
弹出元素: 4
修改后的数组: [1, 2, 3]
数组相等: False
接下来的四个项目要求你定义一些用于操作链表的函数。你应使用本章中定义的 Node 和 TwowayNode 类。
-
定义一个名为
length的函数（不是len），该函数接受一个单链表作为参数，返回链表中的元素数量。 -
定义一个名为
insert的函数，在给定位置将元素插入单链表中。函数接受三个参数：元素、位置和链表（链表可以为空）。函数返回修改后的链表结构。如果位置大于或等于链表的长度，函数会在链表末尾插入元素。函数调用示例：head = insert(1, data, head)，其中 head 是指向链表第一个节点的变量，可以为空。 -
定义一个名为
pop的函数，从单链表的给定位置删除元素。函数接受一个位置作为第一个参数，前置条件为0 <= position < 链表长度。第二个参数是链表（链表不能为空）。函数返回一个元组，包含修改后的链表结构和被删除的元素。示例调用：head, item = pop(1, head)。 -
定义一个名为
makeTwoWay的函数，接受一个单链表作为参数。函数构建并返回一个包含单链表中元素的双链表（注意：函数不应改变参数链表的结构）。
class Node:
"""表示一个单向链表节点。"""
def __init__(self, data, next_node=None):
"""
使用给定的数据和下一个节点初始化一个节点。
参数:
data (Any): 节点中存储的数据。
next_node (Node, optional): 链接到下一个节点。默认为 None。
"""
self.data = data
self.next = next_node
class TwoWayNode(Node):
"""表示一个双向链表节点。"""
def __init__(self, data, previous_node=None, next_node=None):
"""
使用给定的数据、前一个节点和下一个节点初始化一个双向节点。
参数:
data (Any): 节点中存储的数据。
previous_node (TwoWayNode, optional): 链接到前一个节点。默认为 None。
next_node (TwoWayNode, optional): 链接到下一个节点。默认为 None。
"""
super().__init__(data, next_node)
self.previous = previous_node
def length(head):
"""
计算单链表的长度。
参数:
head (Node): 链表的头节点。
返回:
int: 链表中的节点数量。
"""
pass
def insert(position, data, head):
"""
在指定位置插入元素到单链表中。
参数:
position (int): 插入位置。
data (Any): 插入的数据。
head (Node): 链表的头节点。
返回:
Node: 修改后的链表头节点。
"""
pass
def pop(position, head):
"""
从单链表的指定位置删除元素。
参数:
position (int): 要删除元素的位置。
head (Node): 链表的头节点。
返回:
Tuple[Node, Any]: 修改后的链表头节点和被删除的元素。
"""
pass
def makeTwoWay(head):
"""
将单链表转换为双向链表。
参数:
head (Node): 单链表的头节点。
返回:
TwoWayNode: 双向链表的头节点。
"""
pass
可以使用如下 main() 函数对以上任务进行测试：
def main():
head = None
# 插入数据
head = insert(0, 1, head)
head = insert(1, 2, head)
head = insert(2, 3, head)
head = insert(1, 4, head) # 在位置1插入4
# 打印链表长度
print("链表长度:", length(head))
# 打印链表
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 弹出数据
head, item = pop(1, head) # 从位置1弹出元素
print("弹出元素:", item)
# 打印修改后的链表
current = head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
# 转换为双向链表并打印
two_way_head = makeTwoWay(head)
current = two_way_head
while current:
prev_data = current.previous.data if current.previous else "None"
next_data = current.next.data if current.next else "None"
print(f"[{prev_data} <- {current.data} -> {next_data}]")
current = current.next
结果如下：
链表长度: 4
1 -> 4 -> 2 -> 3 -> None
弹出元素: 4
1 -> 2 -> 3 -> None
[None <- 1 -> 2]
[1 <- 2 -> 3]
[2 <- 3 -> None]