作业信息
| 这个作业属于哪个课程 | 2024-2025-1-计算机基础与程序设计 |
|---|---|
| 这个作业要求在哪里 | https://www.cnblogs.com/rocedu/p/9577842.html#WEEK07 |
| 这个作业的目标 | 数组与链表 基于数组和基于链表实现数据结构 无序表与有序表 树 图 子程序与参数 |
| 作业正文 | https://www.cnblogs.com/wchxx/p/18537248 |
教材学习内容总结
1. 数组与链表
数组：
- 存储方式：数组中的元素在内存中是连续存放的，这意味着你可以快速地通过索引找到任何一个元素。
- 优点：访问速度快，因为可以直接计算出元素的内存地址。
- 缺点：大小固定，一旦创建就不能改变；在进行插入和删除操作时，可能需要移动大量元素，效率较低。
链表：
- 存储方式：链表中的元素通过指针连接，每个元素包含数据和指向下一个元素的指针。
- 优点：大小动态，可以随时添加或删除元素；插入和删除操作不需要移动元素，只需要改变指针。
- 缺点：访问速度慢，因为需要从头开始遍历链表；额外的指针占用了内存空间。
2. 基于数组和基于链表实现数据结构
基于数组的数据结构：
- 动态数组：可以动态扩展大小，如C++的
vector和Java的ArrayList。 - 栈：后进先出的结构，只能在一端（栈顶）进行添加和删除操作。
- 队列：先进先出的结构，一端添加元素，另一端删除元素。
基于链表的数据结构：
- 单链表：每个节点指向下一个节点，适合实现栈和队列。
- 双链表：每个节点指向前一个和后一个节点，适合实现需要双向遍历的数据结构。
- 循环链表：最后一个节点的指针指向第一个节点，形成闭环，适合实现循环队列。
3. 无序表与有序表
无序表：
- 哈希表：通过哈希函数将键映射到表中的一个位置，不支持顺序访问，但查找速度快。
有序表：
- 排序数组：元素按照一定的顺序排列，支持快速的二分查找。
- 二叉搜索树：每个节点的左子树包含更小的元素，右子树包含更大的元素，适合查找、插入和删除操作。
4. 树
- 二叉树：每个节点最多有两个子节点，适合实现二叉搜索树。
- 平衡树：自动保持树的平衡，如AVL树，确保操作的时间复杂度为O(log n)。
- 红黑树：自平衡的二叉搜索树，适合实现关联数组。
- B树和B+树：用于数据库和文件系统，支持多关键字的查找和范围查询。
- 堆：完全二叉树，最大堆或最小堆，适合实现优先队列。
5. 图
- 表示方法：可以用邻接矩阵或邻接表来表示图。
- 遍历算法：深度优先搜索（DFS）和广度优先搜索（BFS）是两种基本的图遍历算法。
- 最短路径算法：Dijkstra算法、Bellman-Ford算法等，用于在图中找到最短路径。
6. 子程序与参数
子程序（函数/方法）：
- 定义：一段可以重复使用的代码块，用于执行特定的任务。
- 作用：提高代码的复用性和模块化，简化复杂问题的解决。
参数：
- 输入参数：传递给子程序的值，用于影响子程序的行为。
- 输出参数：子程序返回的结果，可以是单个值或多个值。
- 作用：控制子程序的行为，传递数据，返回结果。
《C语言程序设计》第七周学习总结：
模块化设计
概念：
模块化设计是一种将复杂程序分解成小的、可管理的单元（模块）的方法。每个模块执行一个特定的任务，并且模块之间通过定义好的接口进行通信。
优点：
- 可维护性：每个模块相对独立，修改一个模块时不会影响到其他模块。
- 可重用性：模块可以在不同的程序中使用，提高了代码的重用性。
- 可读性：代码结构清晰，易于理解和阅读。
- 可测试性：可以单独测试每个模块，简化了测试过程。
实现：
- 函数：C语言中的基本模块是函数。每个函数执行一个特定的任务，并可以通过返回值和参数与程序的其他部分交互。
- 头文件：用于声明模块中可用的函数、宏和变量，使得模块可以在不同的文件中使用。
- 源文件：包含函数的具体实现，通常每个模块对应一个源文件。
数组
概念：
数组是一种基本的数据结构，用于存储相同类型的多个元素。在C语言中，数组的元素在内存中是连续存储的。
声明：
type arrayName[arraySize];
type是数组中元素的数据类型。arrayName是数组的名称。arraySize是数组中元素的数量。
访问：
通过索引访问数组中的元素，索引从0开始。
arrayName[index];
特点：
- 固定大小：数组的大小在声明时确定，之后不能改变。
- 连续内存：数组的元素在内存中连续存储，这使得访问速度快，但可能导致内存浪费。
- 同类型元素：数组中的所有元素必须是相同的数据类型。
操作：
- 遍历：使用循环结构遍历数组中的每个元素。
- 排序：使用排序算法（如冒泡排序、快速排序）对数组元素进行排序。
- 搜索：使用搜索算法（如线性搜索、二分搜索）在数组中查找特定元素。
注意事项：
- 越界：访问数组时，确保索引不会超出数组的界限，否则会导致未定义行为。
- 内存分配：静态数组在编译时分配内存，动态数组（如使用
malloc或calloc分配的数组）在运行时分配内存，并需要手动释放。
教材学习中的问题和解决过程
问题：链表的用途
解答：
动态内存管理：
链表可以根据需要动态地增长和缩小，不需要预先定义大小。
高效的插入和删除操作：
在链表中插入或删除节点只需要改变指针，不需要移动其他元素，这使得这些操作的时间复杂度为O(1)。
灵活的数据组织：
链表可以轻松地实现各种复杂的数据结构，如双向链表、循环链表等。
无序数据存储：
链表不需要元素按顺序存储，适合存储无序数据。
通过使用链表，C语言程序可以更灵活地处理数据，特别是在数据大小不确定或需要频繁修改数据结构的情况下。
基于AI的学习
om/blog/3525518/202411/3525518-20241109203838769-1858489350.png)
计划学习时间:
2小时
实际学习时间:
2小时
改进情况：