阅读量:0
目录
实现链表类
挑战介绍
实现链表的插入，增加，查找，删除，查看长度和打印的方法。链表的介绍如下：
- 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
- 链表中每一个元素称为结点，链表由一系列结点组成，结点可以在运行时动态生成。
- 链表的每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
挑战内容
本次挑战中，你需要在 linkedlist.py 文件中补充类 Node 和类 LinkedList 的空缺部分。
Node类是定义的结点类。Node中的__init__方法用于初始化结点，结点包含数据元素data和指向下一个结点地址的指针next_node。Node中的__str__方法用于返回当使用print输出对象时打印的信息，它需要返回结点的数据元素。LinkedList类是定义的链表类。LinkedList中的__init__方法用于初始化链表，参数head为链表头的指针。LinkedList中的__len__方法用于返回链表的结点个数，它需要返回一个数字。LinkedList中的insert_to_front方法用于在链表前面插入结点，参数data用于指定结点的数据元素，它需要返回插入的结点。如果data为None则返回None。LinkedList中的append方法用于在链表后面增加结点，参数data用于指定结点的数据元素，它需要返回增加的结点。如果data为None则返回None。LinkedList中的find方法用于查找链表中包含指定数据元素的结点，参数data用于指定结点的数据元素，它需要返回找到的结点。如果无法找到数据，则返回None。LinkedList中的delete方法用于删除链表中包含指定数据元素的结点，参数data用于指定结点的数据元素，它不需要返回任何值。如果链表没有结点，或者指定元素不在链表中，则不进行删除操作。LinkedList中的print_list方法用于打印链表所有结点的数据元素。它需要使用print函数从链表头至链表尾依次打印出结点的数据元素。LinkedList中的get_all_data方法用于将链表转化为数组，数组的元素为链表结点的数据元素，它需要返回一个数组。
挑战要求
- 代码必须写入
linkedlist.py文件中，且不能修改示例代码中出现的类名和函数名。 - 请自行在环境主目录下新建
linkedlist.py文件，并复制示例代码到文件中完成补充。补充完整后点击「提交检测」，系统将会给出判定结果。
示例代码
class Node(object): def __init__(self, data, next_node=None): ### 补充代码 ### pass def __str__(self): ### 补充代码 ### pass class LinkedList(object): def __init__(self, head=None): ### 补充代码 ### pass def __len__(self): ### 补充代码 ### pass def insert_to_front(self, data): ### 补充代码 ### pass def append(self, data): ### 补充代码 ### pass def find(self, data): ### 补充代码 ### pass def delete(self, data): ### 补充代码 ### pass def print_list(self): ### 补充代码 ### pass def get_all_data(self): ### 补充代码 ### pass 版权说明
内容编译自 Donne Martin 的开源项目，该项目使用 Apache 2.0 LICENSE，我们修改了部分解题和单元测试代码以适应实验楼在线环境。
参考答案
class Node(object): def __init__(self, data, next=None): self.next = next self.data = data def __str__(self): return self.data class LinkedList(object): def __init__(self, head=None): self.head = head def __len__(self): curr = self.head counter = 0 while curr is not None: counter += 1 curr = curr.next return counter def insert_to_front(self, data): if data is None: return None node = Node(data, self.head) self.head = node return node def append(self, data): if data is None: return None node = Node(data) if self.head is None: self.head = node return node curr_node = self.head while curr_node.next is not None: curr_node = curr_node.next curr_node.next = node return node def find(self, data): if data is None: return None curr_node = self.head while curr_node is not None: if curr_node.data == data: return curr_node curr_node = curr_node.next return None def delete(self, data): if data is None: return if self.head is None: return if self.head.data == data: self.head = self.head.next return prev_node = self.head curr_node = self.head.next while curr_node is not None: if curr_node.data == data: prev_node.next = curr_node.next return prev_node = curr_node curr_node = curr_node.next def print_list(self): curr_node = self.head while curr_node is not None: print(curr_node.data) curr_node = curr_node.next def get_all_data(self): data = [] curr_node = self.head while curr_node is not None: data.append(curr_node.data) curr_node = curr_node.next return data代码分析：
上述代码定义了两个类：Node 和 LinkedList，它们共同实现了一个简单的单向链表结构。下面是对这两个类及其方法的详细分析：
Node 类
Node 类表示链表中的节点。每个节点包含两个属性：
data：存储节点的数据。next：指向链表中下一个节点的引用，如果这是链表的最后一个节点，则此引用为None。
Node 类还定义了一个 __str__ 方法，该方法返回节点的数据，使得在打印节点对象时，输出的是节点的数据值而不是默认的对象表示。
LinkedList 类
LinkedList 类表示整个链表，并提供了一系列方法来操作链表，包括插入、追加、查找、删除节点以及打印和获取链表中的所有数据。
方法分析
__init__(self, head=None)：构造函数，初始化链表的头节点。如果调用时没有提供头节点，则链表为空。__len__(self)：返回链表中节点的数量。通过遍历链表并计数来实现。insert_to_front(self, data)：在链表的前端插入一个新节点。如果插入的数据为None，则不进行任何操作。此方法通过创建一个新节点，并将其next指向当前的头节点，然后将新节点设置为新的头节点。append(self, data)：在链表的末尾追加一个新节点。如果链表为空，则新节点成为头节点。否则，遍历链表直到最后一个节点，并将其next指向新节点。find(self, data)：在链表中查找具有指定数据的节点。如果找到，则返回该节点；否则返回None。delete(self, data)：从链表中删除具有指定数据的节点。如果头节点就是要删除的节点，则更新头节点为下一个节点。否则，遍历链表找到要删除的节点的前一个节点，并将其next指向要删除节点的下一个节点，从而实现删除。print_list(self)：遍历链表并打印每个节点的数据。get_all_data(self)：遍历链表并将所有节点的数据收集到一个列表中返回。
总结
这段代码实现了一个基本的单向链表结构，并提供了一系列操作链表的方法。这些方法涵盖了链表的常见操作，如插入、删除、查找、遍历等。此外，还通过 __len__ 和 __str__ 方法增强了链表对象的可用性和可读性。不过，需要注意的是，delete 方法在删除节点时没有直接处理被删除节点的内存释放（在Python中，由于垃圾回收机制，这通常不是问题），但在其他语言或特定情况下可能需要注意内存管理。
删除链表的重复项
挑战介绍
实现一个算法来删除链表中数据元素重复的结点。要求如下：
- 对于链表中有相同数据元素的结点，删除后面的重复结点。
挑战内容
本次挑战中，你需要在 removedupes.py 文件中补充函数 remove_dupes 的空缺部分。
MyLinkedList类继承“实现链表类”挑战中的LinkedList类。MyLinkedList类的remove_dupes方法用于删除链表的重复项，它没有输入，也没有返回值。- 如果链表没有结点，则不进行操作。
挑战要求
- 在终端中输入以下命令下载链表类文件
linked_list.py到主目录下:
wget -nc https://labfile.oss.aliyuncs.com/courses/1512/linked_list.py - 代码必须写入
removedupes.py文件中，且不能修改示例代码中出现的类名和函数名。 - 请自行在环境主目录下新建
removedupes.py文件，并复制示例代码到文件中完成补充。补充完整后点击「提交检测」，系统将会给出判定结果。
示例代码
from linked_list import LinkedList class MyLinkedList(LinkedList): def remove_dupes(self): ### 补充代码 ### pass 版权说明
内容编译自 Donne Martin 的开源项目，该项目使用 Apache 2.0 LICENSE，我们修改了部分解题和单元测试代码以适应实验楼在线环境。
参考答案
from linked_list import LinkedList class MyLinkedList(LinkedList): def remove_dupes(self): if self.head is None: return node = self.head seen_data = set() while node is not None: if node.data not in seen_data: seen_data.add(node.data) prev = node node = node.next else: prev.next = node.next node = node.next代码分析：
这段代码定义了一个名为 MyLinkedList 的类，它继承自一个名为 LinkedList 的基类。MyLinkedList 类中添加了一个名为 remove_dupes 的方法，旨在移除链表中的重复元素。
下面是 remove_dupes 方法的详细分析：
- 检查链表是否为空：
- 首先，方法检查链表的头节点（
self.head）是否为None。如果是，表示链表为空，方法直接返回，不执行任何操作。
- 首先，方法检查链表的头节点（
- 初始化变量：
- 定义一个名为
node的变量，初始化为链表的头节点（self.head）。这个变量将用于遍历链表。 - 定义一个名为
seen_data的集合，用于存储遍历过程中遇到的唯一数据值。
- 定义一个名为
- 遍历链表：
- 使用一个
while循环遍历链表，直到node变为None（即遍历到链表的末尾）。
- 使用一个
- 检查并移除重复元素：
- 在每次循环中，检查当前节点（
node）的数据（node.data）是否已经在seen_data集合中。 - 如果不在，说明这是一个新的唯一数据，将其添加到
seen_data集合中，并更新prev变量为当前节点，然后移动到下一个节点。 - 如果已经在
seen_data集合中，说明这是一个重复的数据，需要从链表中移除。通过将prev.next更新为node.next来移除当前节点，然后移动到下一个节点。
- 在每次循环中，检查当前节点（
通过这种方式，remove_dupes 方法能够有效地遍历链表，并移除所有重复的元素，只保留唯一的元素。注意，这个方法修改了原始链表，而不是创建一个新的链表。
寻找链表倒数第 k+1 个结点
挑战介绍
实现一个算法来寻找离链表最后一个结点 k 个距离的结点，即链表倒数第 k+1 个结点，并得到此结点的数据元素。
挑战内容
本次挑战中，你需要在 kth_to_last.py 文件中补充函数 kth_to_last_elem 的空缺部分。
MyLinkedList类继承“实现链表类”挑战中的LinkedList类。MyLinkedList类的kth_to_last_elem方法用于寻找离链表最后一个结点k个距离的结点，参数k用于指定距离，它需要返回结点的数据元素。- 如果链表没有结点，则返回
None；如果k大于或等于链表的长度，也返回None。
挑战要求
- 在终端中输入以下命令下载链表类文件
linked_list.py到主目录下:
wget -nc https://labfile.oss.aliyuncs.com/courses/1512/linked_list.py - 代码必须写入
kth_to_last.py文件中，且不能修改示例代码中出现的类名和函数名。 - 请自行在环境主目录下新建
kth_to_last.py文件，并复制示例代码到文件中完成补充。补充完整后点击「提交检测」，系统将会给出判定结果。
示例代码
from linked_list import LinkedList class MyLinkedList(LinkedList): def kth_to_last_elem(self, k): ### 补充代码 ### pass 版权说明
内容编译自 Donne Martin 的开源项目，该项目使用 Apache 2.0 LICENSE，我们修改了部分解题和单元测试代码以适应实验楼在线环境。
参考答案
from linked_list import LinkedList class MyLinkedList(LinkedList): def kth_to_last_elem(self, k): if self.head is None: return None fast = self.head slow = self.head # Give fast a headstart, incrementing it # once for k = 1, twice for k = 2, etc for _ in range(k): fast = fast.next # If k >= num elements, return None if fast is None: return None # Increment both pointers until fast reaches the end while fast.next is not None: fast = fast.next slow = slow.next return slow.data代码分析
这段代码定义了一个名为 MyLinkedList 的类，它继承自 LinkedList 类。MyLinkedList 类中添加了一个名为 kth_to_last_elem 的方法，该方法用于找到链表中倒数第 k 个元素的值。
方法解析
检查链表是否为空：首先，方法检查链表的头节点
self.head是否为None，即链表是否为空。如果为空，则直接返回None。初始化两个指针：接着，方法初始化两个指针
fast和slow，都指向链表的头节点self.head。给
fast指针一个“头开始”：通过循环，fast指针先向前移动k步。这个步骤是为了确保fast和slow指针之间有k个节点的距离。如果在这个过程中fast指针到达链表末尾（即fast变为None），则说明链表中的元素数量少于k，因此方法返回None。同时移动两个指针：当
fast指针成功移动k步后，fast和slow指针同时向前移动，直到fast指针到达链表末尾。这时，slow指针指向的节点就是链表中倒数第k个节点。返回结果：最后，方法返回
slow指针指向的节点的数据值，即链表中倒数第k个元素的值。
总结
这段代码通过双指针技巧有效地解决了找到链表中倒数第 k 个元素的问题。它首先确保链表不为空，并且 k 的值不超过链表的长度。然后，通过移动两个指针来找到目标节点，并返回其数据值。这种方法的时间复杂度为 O(n)，其中 n 是链表的长度，因为它需要遍历整个链表。
删除链表的结点
挑战介绍
实现一个算法来删除链表的结点。
挑战内容
本次挑战中，你需要在 del_node.py 文件中补充函数 delete_node 的空缺部分。
MyLinkedList类继承“实现链表类”挑战中的LinkedList类。MyLinkedList类的delete_node方法用于删除链表的结点，参数node用于指定需要删除的结点，它没有返回值。- 如果要删除的结点位于链表末尾，则将链表最后一个结点的数据元素替换为
None。 - 如果链表没有结点，或者要删除的结点为
None，则不进行删除操作。
挑战要求
- 在终端中输入以下命令下载链表类文件
linked_list.py到主目录下:
wget -nc https://labfile.oss.aliyuncs.com/courses/1512/linked_list.py - 代码必须写入
del_node.py文件中，且不能修改示例代码中出现的类名和函数名。 - 请自行在环境主目录下新建
del_node.py文件，并复制示例代码到文件中完成补充。补充完整后点击「提交检测」，系统将会给出判定结果。
示例代码
from linked_list import LinkedList class MyLinkedList(LinkedList): def delete_node(self, node): ### 补充代码 ### pass 版权说明
内容编译自 Donne Martin 的开源项目，该项目使用 Apache 2.0 LICENSE，我们修改了部分解题和单元测试代码以适应实验楼在线环境。
参考答案
from linked_list import LinkedList class MyLinkedList(LinkedList): def delete_node(self, node): if node is None: return if node.next is None: node.data = None else: node.data = node.next.data node.next = node.next.next代码分析：
这段代码定义了一个名为 MyLinkedList 的类，它继承自一个名为 LinkedList 的类。MyLinkedList 类中添加了一个名为 delete_node 的方法，用于删除链表中的一个节点。下面是对这个方法的详细分析：
- 参数：
node：这是delete_node方法的唯一参数，表示要删除的节点。
- 方法逻辑：
- 首先，检查传入的
node是否为None。如果是，那么方法直接返回，不执行任何操作。 - 接下来，检查
node.next是否为None，即判断该节点是否为链表的最后一个节点。如果是，那么将该节点的数据设置为None，这实际上并没有从链表中移除节点，只是清空了节点中的数据。 - 如果
node不是最后一个节点，那么将node的数据更新为node.next的数据，并将node.next更新为node.next.next。这样，实际上是将node的下一个节点的数据移动到了node中，并跳过了node的下一个节点，从而在逻辑上“删除”了node的下一个节点。
- 首先，检查传入的
- 潜在问题：
- 如果链表中存在对特定数据的引用或依赖，直接修改节点数据而不是删除节点可能会导致问题。
- 清空最后一个节点的数据而不是完全移除节点可能会导致链表末尾出现“空洞”，即包含无效数据的节点。
- 这种方法没有处理链表的头节点删除情况，如果需要删除头节点，可能需要额外的逻辑。
- 总结：
- 这个方法提供了一种在链表中“删除”节点的非传统方式，通过修改节点数据来间接实现删除操作。
- 这种方法在某些特定场景下可能是有用的，但需要注意其潜在的问题和限制。
