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

作业信息

教材学习内容总结

.数组‌：是一种线性数据结构，将相同类型元素存储在连续的内存空间中。数组支持随机访问，访问效率高，时间复杂度为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：在程序设计语言的翻译过程中，编译器和解释器各自的优缺点是什么？
解答：
编译器优点：编译后的程序执行效率高，因为它是把整个源程序一次性翻译为机器语言，后续执行时计算机可以直接运行机器语言代码，不需要额外的翻译过程。例如对于大型的、计算密集型的程序，如科学计算软件，使用编译器可以让程序运行得更快。
编译器缺点：调试相对困难。因为编译器是对整个程序进行翻译，如果程序在运行时出现错误，定位错误的难度可能较大。并且，每次修改源程序后都需要重新编译整个程序才能运行。
解释器优点：具有良好的平台可移植性，只要目标平台有对应的解释器，就可以运行程序。而且调试方便，因为是逐行解释执行，当出现错误时可以比较容易地定位到出错的行。例如一些脚本语言，在不同操作系统上，只要安装了相应的解释器就能运行，而且开发过程中如果代码出错能很快发现问题所在。
解释器缺点：执行效率较低，由于是逐行翻译并执行，相比编译后的程序，它需要花费更多的时间在翻译代码这个过程上，对于大型程序或者性能要求高的程序不太适用。
问题2：在C语言的嵌套循环中，如何正确地控制内循环和外循环的执行次数，以实现打印一个九九乘法表？
解答：
九九乘法表是一个典型的二维结构，外循环控制行数，内循环控制列数。

基于AI的学习