2024-2025-1 学号20241306 《计算机基础与程序设计》第7周学习总结

作业信息

教材学习内容总结

1.数组‌：是一种线性数据结构，将相同类型元素存储在连续的内存空间中。数组支持随机访问，访问效率高，时间复杂度为O(1)。但在插入和删除元素时，可能需要移动后续的所有元素，以保持连续性，导致最坏情况下的时间复杂度为O(n)。数组的空间大小是固定的，不能进行动态扩展，空间利用率较低。
2‌.链表‌：是一种链式存储结构，不要求逻辑上相邻的两个元素在物理位置上也相邻。链表在插入和删除元素时，只需修改相邻节点的指针，时间复杂度为O(1)（但需知道前驱节点）。然而，查找特定元素或访问特定编号的节点需要从头节点开始遍历，时间复杂度为O(n)。链表可以动态扩展，空间利用率较高。
3.基于数组的数据结构
‌栈（Stack）‌：
实现：可以使用数组来实现栈，其中栈顶指针（top）指向数组的最后一个有效元素。
操作：入栈（push）将新元素添加到栈顶，出栈（pop）移除栈顶元素，查看栈顶元素（peek）但不移除。
特点：由于数组支持随机访问，栈的入栈和出栈操作时间复杂度为O(1)。
‌队列（Queue）‌：
实现：可以使用数组来实现队列，其中队头指针（front）指向队列的第一个元素，队尾指针（rear）指向队列的最后一个元素。
操作：入队（enqueue）将新元素添加到队尾，出队（dequeue）移除队头元素。
特点：在循环队列中，通过巧妙地利用数组的空间，可以实现队列的FIFO（先进先出）特性，且入队和出队操作时间复杂度为O(1)。
‌哈希表（Hash Table）‌：
实现：哈希表通常使用数组来存储哈希桶，每个哈希桶可以存储一个链表或其他数据结构来解决哈希冲突。
操作：插入（insert）、查找（search）和删除（delete）元素。
特点：哈希表通过哈希函数将键映射到数组中的某个位置，实现了快速查找，平均时间复杂度为O(1)。
4.基于链表的数据结构
‌单链表（Singly Linked List）‌：
实现：每个节点包含一个数据域和一个指向下一个节点的指针。
操作：插入（可以在任意位置插入新节点）、删除（删除指定节点）、遍历（访问链表中的所有节点）。
特点：单链表在插入和删除操作时，只需修改相关节点的指针，时间复杂度为O(1)（但需知道前驱节点）；查找特定元素需要从头节点开始遍历，时间复杂度为O(n)。
‌双链表（Doubly Linked List）‌：
实现：每个节点包含一个数据域、一个指向下一个节点的指针和一个指向前一个节点的指针。
操作：与单链表类似，但双链表还支持双向遍历。
特点：双链表在插入、删除和查找操作上的性能与单链表相似，但双向遍历提高了灵活性。
‌循环链表（Circular Linked List）‌：
实现：链表的最后一个节点指向头节点，形成一个循环。
操作：与单链表或双链表类似，但循环链表支持循环遍历。
特点：循环链表在某些特定应用场景（如约瑟夫环问题）中具有优势。
5.无序表‌：数据项的排列没有特定顺序，只按照存放位置来索引。例如，一个考试分数的集合“54,26,93,17,77和31”在无序表中就是[54,26,93,17,77,31]。无序表可以采用链表等结构实现，其优点是插入和删除操作灵活，但查找特定元素需要遍历整个表。
‌6.有序表‌：数据项按照某种规则（如递增或递减）排列，表中可存在元素值相同的元素。有序表便于进行二分查找等高效查找操作。在实现上，有序表可能需要采用特定的排序算法来维持其有序性。
7.树（Tree）
‌定义‌：树是一种广泛使用的非线性数据结构，用于表示具有层次关系的数据。它由节点（nodes）和边（edges）组成，其中每个节点可以有零个或多个子节点，但除了根节点外，每个子节点都恰好有一个父节点。
‌类型‌：常见的树结构包括二叉树（每个节点最多有两个子节点）、多叉树（每个节点可以有多个子节点）、搜索树（如二叉搜索树，用于高效查找）、平衡树（如AVL树，用于保持树的高度平衡）等。
‌应用‌：树在文件系统、数据库索引、表达式解析、人工智能等领域有广泛应用。
8.图（Graph）
‌定义‌：图是由节点（或顶点）和连接这些节点的边组成的数据结构。与树不同，图中的节点之间可以有任意数量的连接，包括自连接和环。
‌类型‌：图可以分为有向图（边有方向）和无向图（边没有方向）。还可以根据边的权重分为加权图和非加权图。
‌应用‌：图在计算机网络、交通网络、社交网络分析、最短路径查找、最小生成树等问题中有重要应用。
9.子程序（Subroutine）
‌定义‌：子程序是编程中用于实现特定功能的一段代码块，它可以被主程序或其他子程序调用。子程序通常具有输入参数和输出参数，用于传递数据和返回结果。
‌特点‌：子程序可以提高代码的可重用性和可维护性，使程序更加模块化。通过调用子程序，可以避免重复编写相同的代码，从而减少错误和提高开发效率。
‌应用‌：子程序在软件开发中广泛应用，如函数、过程、方法等。
10.参数（Parameter）
‌定义‌：参数是子程序或函数调用时传递的变量或值。它们用于在调用者和被调用者之间传递数据。
‌类型‌：参数可以分为输入参数（传递给子程序用于处理的数据）和输出参数（子程序处理后返回的数据）。有些编程语言还支持默认参数和可变参数等特性。
‌应用‌：参数在函数调用、方法调用、API接口设计等方面有重要应用。通过合理设计参数，可以确保数据的正确传递和处理，从而实现程序的正确运行和预期功能。

教材学习中的问题和解决过程（先问 AI）

• 问题1：常见的树遍历算法有哪些？

• 问题1解决方案：
  1.前序遍历（PreOrder Traversal）‌：
  按照根、左、右的顺序访问节点。
  可用于创建树的拷贝或获取前缀表达式。
  实现方式有递归和非递归（使用栈）两种。
  2‌.中序遍历（InOrder Traversal）‌：
  按照左、根、右的顺序访问节点。
  在二叉搜索树中，中序遍历结果是有序的。
  ‌3.后序遍历（PostOrder Traversal）‌：
  按照左、右、根的顺序访问节点。
  适用于任何树结构。
  4‌.层序遍历（Level Order Traversal）‌：
  按照树的层次从上到下、从左到右访问节点。
  通常使用队列来实现。

• 问题2：链表的插入操作如何实现

• 问题2解决方案：实现一个基本的链表通常涉及定义链表节点的结构以及提供对链表进行操作的方法。以下是一个使用Python语言实现单向链表（单链表）的基本示例。单向链表的每个节点包含数据部分和指向下一个节点的指针。
  定义链表节点
  首先，我们需要定义一个类来表示链表的节点。每个节点将包含数据（可以是任何类型）和一个指向下一个节点的引用（初始时为None）。
  python
  Copy Code
  class ListNode:
  def init(self, data=0, next=None):
  self.data = data
  self.next = next
  定义链表类
  接下来，我们定义一个类来表示链表本身。链表类将包含一个指向链表头节点的引用（如果链表为空，则为None），并提供一些基本的方法来操作链表，如添加节点、删除节点和打印链表。
  python
  Copy Code
  class LinkedList:
  def init(self):
  self.head = None

  在链表末尾添加节点
  def append(self, data):
  new_node = ListNode(data)
  if not self.head:
  self.head = new_node
  return
  last = self.head
  while last.next:
  last = last.next
  last.next = new_node

  删除链表中的节点（根据值）
  def delete(self, key):
  temp = self.head

     如果头节点本身就是要删除的节点
    if temp and temp.data == key:
        self.head = temp.next
        temp = None
        return
    
    查找要删除的节点
    while temp and temp.data != key:
        prev = temp
        temp = temp.next
    
   如果key不存在于链表中
    if temp is None:
        return
    
   从链表中删除节点
    prev.next = temp.next
    temp = None
  
   打印链表
  

  def print_list(self):
  temp = self.head
  while temp:
  print(temp.data, end=" -> ")
  temp = temp.next
  print("None")

使用链表
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.print_list() # 输出: 1 -> 2 -> 3 -> None

ll.delete(2)
ll.print_list() # 输出: 1 -> 3 -> None
解释
‌ListNode 类‌：表示链表的节点，包含数据和指向下一个节点的指针。
‌LinkedList 类‌：表示链表，包含头节点的引用和操作方法。
append 方法：在链表末尾添加新节点。
delete 方法：根据给定的值删除链表中的节点。
print_list 方法：打印链表的所有节点。
这个基本的链表实现可以根据需要进行扩展，例如添加在链表开头或特定位置插入节点的功能，实现双向链表，循环链表等。

• 问题3：还有哪些数据结构是基于数组实现的？
• 问题3解决方案：基于数组实现的数据结构有多种，主要包括以下几种：
  ‌栈（Stack）‌：栈是一种特殊的线性表，它遵循后进先出（LIFO）的原则。栈可以使用数组来实现，其中数组的起始位置作为栈底，数组的末尾位置作为栈顶。通过维护一个栈顶指针来指示栈顶元素的位置，实现栈的插入（push）和删除（pop）操作‌
  队列（Queue）‌：队列也是一种特殊的线性表，它遵循先进先出（FIFO）的原则。虽然队列更常使用链表来实现，但也可以使用数组来实现，特别是循环队列。循环队列通过维护队头指针和队尾指针，在数组空间被完全利用后从头开始存储数据，从而有效利用数组空间‌
  优先队列‌：优先队列是一种特殊的队列，其中每个元素都有一个优先级，出队时总是移除优先级最高（或最低）的元素。优先队列可以使用数组配合堆（Heap）数据结构来实现，堆本身也是基于数组的一种特殊形式‌
  动态数组（如ArrayList）‌：动态数组是一种能够根据需要自动调整大小的数组。它内部使用数组来存储元素，但提供了动态扩容的机制，以适应元素数量的变化‌
  这些数据结构通过不同的方式利用数组的特性，实现了各自独特的功能和性能优化。
• 问题4：动态数组是如何扩容的？
• 问题4解决方案：计算新容量‌：当数组当前容量不足以存储更多元素时，会根据一定的策略计算新容量。常见的策略是将当前容量增加一定比例（如1.5倍或翻倍）。
  ‌创建新数组‌：根据计算出的新容量，动态分配一个新的数组空间。
  ‌复制元素‌：将原数组中的所有元素复制到新数组中。
  ‌更新引用‌：将动态数组的内部引用从原数组更新为新数组，完成扩容操作。
  需要注意的是，扩容操作可能会相对耗时，因为它涉及到内存的分配和数据的复制。因此，在预知可能需要存储大量元素时，可以通过构造函数指定一个较大的初始容量，以减少扩容操作的次数，从而提高性能‌.

基于AI的学习