Day09_随堂笔记.pdf

### Python进阶知识点详细解析 #### 链表的定义和分类 链表是一种常见的线性数据结构，与顺序表不同，链表的存储单元不要求连续，每个单元由数据域和指针域组成，通过指针将各单元链接起来。链表中的每个节点包含两个部分：一个存储数据的元素域（item），和一个指向下一个节点地址的链接域（next）。链表根据链接方式的不同分为单向链表、单向循环链表、双向链表、双向循环链表。 #### 节点类设计 在Python中设计链表，首先需要定义节点类（`SingleNode`），该类包含两个属性：`item`和`next`。其中，`item`用于存储节点的数值信息，`next`则是指向下一个节点的指针。 ```python class SingleNode(object): def __init__(self, item): self.item = item # 数值域 self.next = None # 地址域 ``` #### 单向链表类设计 单向链表类（`SingleLinkedList`）主要包含以下几个行为方法： - `is_empty()`：判断链表是否为空。 - `length()`：获取链表长度。 - `travel()`：遍历整个链表。 - `add(item)`：在链表头部添加元素。 - `append(item)`：在链表尾部添加元素。 - `insert(pos, item)`：在指定位置添加元素。 - `remove(item)`：删除节点。 - `search(item)`：查找节点是否存在。 ```python class SingleLinkedList(object): def __init__(self, node=None): self.head = node # 头结点 def is_empty(self): return True if self.head == None else False ``` #### 链表操作实现 实现单向链表类的方法是实现链表操作的关键，例如： - 添加元素时，需要创建新节点，并更新相应节点的指针域。 - 删除节点时，需要找到目标节点，并调整前一节点的指针域，使其跳过目标节点。 - 查找节点时，需要从头结点开始遍历链表，逐个检查节点的数值域。 #### 排序和查找算法简介 在文件内容中还提及了常见的排序算法和查找算法，这些都是进阶编程中必须掌握的知识点。排序类的算法包括冒泡排序、选择排序、插入排序和快速排序；查找类的算法包括二分查找的递归和非递归实现。这些算法理解和实现的难度较大，但在解决复杂问题时非常有用。 ###