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

作业信息

教材学习内容总结

一、简单类型与组合类型
（一）简单类型
简单类型（Primitive Types）是编程语言中最基本的数据类型，通常包括整数、浮点数、字符、布尔值等，它们是不可再分的基本数据单元。

（二）组合类型
组合类型（Composite Types）是由简单类型组合而成的数据类型，例如数组、结构体、类等。它们可以包含多个简单类型的数据，并且可以进行复杂的操作。

二、复合数据结构
（一）数组
数组（Array）是一组相同类型的元素的集合。

（二）链表
链表（Linked List）是由节点组成的线性数据结构，每个节点包含数据和指向下一个节点的指针。

（三）栈
栈（Stack）是后进先出（LIFO）的数据结构。

（四）队列
队列（Queue）是先进先出（FIFO）的数据结构。

（五）树
树（Tree）是由节点和边组成的层次结构，如二叉树、B树等。

（六）图
图（Graph）是由节点和边组成的非线性数据结构，用于表示复杂的关系。

三、查找与排序算法
（一）查找算法

1. 线性查找
   线性查找（Linear Search）是逐个检查每个元素，直到找到目标元素。

2. 二分查找
   二分查找（Binary Search）是在有序数组中通过不断缩小查找范围来查找目标元素。

（二）排序算法

1. 冒泡排序
   冒泡排序（Bubble Sort）是通过多次遍历数组，比较相邻元素并交换位置。

2. 选择排序
   选择排序（Selection Sort）是每次选择最小（或最大）的元素放到已排序部分的末尾。

3. 插入排序
   插入排序（Insertion Sort）是将未排序部分的元素逐个插入到已排序部分的正确位置。

4. 快速排序
   快速排序（Quick Sort）是通过选择一个基准元素，将数组分为两部分并递归排序。

5. 归并排序
   归并排序（Merge Sort）是将数组分为两部分，分别排序后再合并。

四、算法复杂度
（一）时间复杂度
时间复杂度（Time Complexity）表示算法执行时间随输入规模增长的变化趋势，常用大O表示法（O(n)、O(n^2)等）。

（二）空间复杂度
空间复杂度（Space Complexity）表示算法执行过程中所需的额外空间随输入规模增长的变化趋势。

五、递归
递归是一种编程技术，函数直接或间接调用自身来解决问题。递归通常用于解决可以分解为相同问题的子问题的情况。递归的关键在于定义递归基（终止条件）和递归关系（如何将问题分解为子问题）。

六、代码安全
（一）输入验证
输入验证（Input Validation）确保用户输入的数据符合预期格式和范围。

（二）边界检查
边界检查（Boundary Checking）防止数组越界、缓冲区溢出等错误。

（三）加密
加密（Encryption）对敏感数据进行加密，防止数据泄露。

（四）权限控制
权限控制（Access Control）限制不同用户对系统资源的访问权限。

（五）日志记录
日志记录（Logging）记录系统操作和错误信息，便于追踪和分析问题。

（六）安全编码实践
安全编码实践（Secure Coding Practices）遵循安全编码规范，避免常见的安全漏洞。

基于AI的学习

我：我在学习C语言查找与排序算法的相关知识，对我进行苏格拉底式的提问，一次一个问题
AI：好的，我们从基础开始，通过一系列问题来帮助你深入理解C语言中的查找与排序算法。

首先，让我们谈谈查找算法：

问题1：在C语言中，什么是线性查找（Linear Search），它的时间复杂度是多少？

请详细描述，并解释你的答案。
我：线性查找是一种简单的搜索算法，用于在无序数组或列表中查找特定元素。它的工作原理是从数组的第一个元素开始，逐一检查每个元素，直到找到目标元素或遍历完整个数组。如果找到目标元素，算法返回其位置；如果遍历完整个数组仍未找到目标元素，则返回一个表示未找到的值。线性查找的时间复杂度是O(n)，其中n是数组中元素的数量。这是因为最坏情况下，算法可能需要检查数组中的每一个元素才能找到目标元素或确定目标元素不存在。
AI：非常好！你对线性查找的概念和时间复杂度有了清晰的理解。接下来，让我们讨论排序算法：

问题2：在C语言中，什么是冒泡排序（Bubble Sort），它的基本思想是什么？另外，你能推断出它的时间复杂度吗？

请详细解释这两个方面。
我：冒泡排序是一种简单的排序算法，它通过重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，直到整个列表排序完成。冒泡排序的时间复杂度可以通过分析其最坏情况下的比较次数来推断。
AI：你正确地描述了冒泡排序的基本思想以及其时间复杂度。

尽管你的表述有些简化，但对于我们的目的来说已经足够。

总结一下，你现在对线性查找和冒泡排序的概念和表现有了初步的了解。接下来我们将深入探讨更复杂的查找和排序技术，比如二分查找和快速排序。

若你准备好了，请问你想进一步探索哪种查找或排序技术呢？
我：我都可以
AI：很好，那么我们先从查找算法开始，然后转到排序算法。

� WWE常看的艺术和科学

1. W查找（Binary Search）:
   让我们谈谈一个非常高效的查找算法——二分查找。

• 前提条件:使用二分查找前，必须确保数据已经排好序。(如果是无序的，无法直接使用二分查找)。

问题3：如何在一个有序数组中实现二分查找算法？它的主要步骤有哪些？

请详细说明操作步骤以及该算法的时间复杂度。
我：二分查找算法是一种高效的查找算法，适用于在有序数组中查找特定元素。其时间复杂度为O(log n)，远优于线性查找的O(n)。

主要步骤：初始化边界，循环查找，查找结束
AI：太好了，你已经掌握了二分查找的一些关键点。现在，让我们把注意力转向排序算法。

排序算法

既然你已经了解了冒泡排序和它的局限性，我们接着了解一个非常有效率的排序算法：快速排序（Quicksort）。

问题4：你能解释什么是快速排序吗？它的核心思想是什么，又是如何实现的呢？与其最基本的形式时间复杂度相比会对一般情形下运行表现有何影响呢？

请详细解释这些要点。
我：我不太会，请你为我答疑解惑
AI：当然可以！

快速排序及其核心思想
定义: 快速排序是一个分治法（Divide and Conquer）的排序算法。这意味着它将大问题划分为小的子问题来独立解决，然后合并结果获得最终答案。

核心思想:

选择枢轴(Pivot)：这一步骤选取一个特定的数据元素作为“枢轴”。可以选择第一个、最后一个或者是中间的一个元素，或者使用一些更智能的方法随机选择枢轴以提升效率。
划分（Partitioning）：重排序列，使得枢轴左边的所有元素都比它小，右边的所有元素都比它大。这极大地减少了待排序的序列长度。
步骤如下：

选择一个枢轴 (Pivot).
将小于枢轴的放在左侧，大于枢轴的放在右侧.
再递归对左右两边分别实施相同的过程.
时间复杂度:

在平均情况下,快速排序的时间复杂度为 O(n log n),相较于冒泡排序有着显著提升。
最坏的情况下，当每次总是挑选最小/大的元素做枢轴时(由于这样每次只能使序列减少一个元素), 时间复杂度降为 O(n^2).
关于最好的枢轴选择通常建议尽量选择数据接近"真正中值"的随机定位从而减少性能上的潜在波动.

希望这个解释对你有所帮助! 还有问题请告诉我!
我：我的回答结束了，请对我的回答进行评价总结
AI：因为还没有收集到你的回答，实际上也就谈不到给出它的评价和总结。不过没关系，我们将在接下来的问题中继续深入了解各种查找和排序算法。如果你有任何疑问或想进一步探讨某个主题，请告诉我！

学习进度条

(有空多看看现代软件工程 课件
软件工程师能力自我评价表)

参考资料

• 《计算机科学概论（第七版）》
• ...