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

作业信息

教材学习内容总结

Polya的解决问题四步法
1.理解问题：

识别已知和未知：仔细阅读问题，找出所有已给出的条件和要求，以及需要解决的具体问题。
定义目标：清晰地表达你希望达成的目标结果，确保可以量化或明确判断。
2.制定计划：

选择策略：根据问题的性质，选择合适的解题策略，比如分而治之、动态规划、贪心算法等。
考虑相似问题：回忆并思考是否有曾经解决过的类似问题及其解决方法，可以借鉴的地方。
计划步骤：明确每一步的操作，可能需要的计算，以及需要用到的数据结构。
3.实施计划：

实现解决方案：根据计划一步一步执行，注意每一步的正确性，确保逻辑上的连贯性。
调试与调整：在实施过程中，及时发现和纠正错误，必要时可以调整初步计划。
4.回顾与反思：

评估结果：检查解决方案的有效性，是否达到了目标。
总结经验：记录下有效的策略和方法，反思可改进的地方，比如是否有更简洁或高效的方法。
简单类型与组合类型
简单类型：

常见的简单类型包括整数（int）、浮点数（float）、字符（char）和布尔值（bool）。
这些原始数据类型在内存中使用固定的大小，占用的空间与数据类型直接相关。
组合类型：

可以将简单类型组合成更复杂的数据结构。例如：
数组：一组相同类型的元素，内存连续存储，可以通过索引访问。
结构体（Struct）：用户定义的数据类型，它可以包含多种类型的字段。这在需要将不同类型的数据绑定在一起时很有用。
类（Class）：面向对象编程中的核心，包含属性和方法的用户定义数据类型，支持封装和继承。
元组（Tuple）：不可变的有序集合，允许储存不同类型的元素。
复合数据结构
复合数据结构由简单及组合类型构成，广泛用于存储和组织数据：

链表：动态数据结构，节点包含数据和指向下一个节点的指针，便于插入和删除操作。
树：由节点组成的层级结构，每个节点可以有多个子节点，适用于表示分层数据（如文件系统）。
二叉树：每个节点最多有两个子节点。
平衡树（如红黑树、AVL树）：自保持平衡的二叉树，保证操作的高效性。
图：由节点和边组成，可以表示复杂关系，包括无向图、有向图和加权图等。
查找与排序算法
查找算法：

线性查找：最简单的查找方法，遍历每一个元素，时间复杂度为O(n)。
二分查找：在有序数组中，通过比较中间元素来不断缩小查找范围，时间复杂度为O(log n)。需事先排序的数组。
排序算法：

冒泡排序：邻接元素对比交换，将最大（或最小）元素“沉”到数组末尾，时间复杂度为O(n^2)。
选择排序：每轮选择未排序部分的最小元素放到已排序部分末尾，时间复杂度为O(n^2)。
插入排序：将数组分为已排序和未排序部分，每次将未排序部分的首元素插入到已排序部分中，适合小规模数据，时间复杂度为O(n^2)。
快速排序：选择一个“基准”元素，分割出两个子数组，分别递归排序，时间复杂度平均为O(n log n)。
归并排序：递归地将数组分成两半，分别排序后合并，时间复杂度为O(n log n)。
算法复杂度
算法复杂度是评估算法效率的重要工具：

时间复杂度：表示算法执行时间与输入规模的关系，通常用大O符号描述。

常见复杂度：

O(1)（常数时间）
O(log n)（对数时间）
O(n)（线性时间）
O(n log n)（线性对数时间，常见于高效排序）
O(n^2)（平方时间，常见于简单排序）
空间复杂度：表示算法执行所需的额外空间与输入规模的关系。

递归
递归是一种强大的编程技巧，常用于解决可以被分解成更小子问题的问题：

基本构成：

基线条件（Base Case）：明确解决的最小问题情境，防止无限递归。
递推关系（Recursive Case）：将问题转化为一个或多个子问题，通过递归方式解决。

代码安全
代码安全是软件开发中不可忽视的重要方面，防止安全漏洞和攻击：

输入验证：

检查用户输入的合法性，防止SQL注入、XSS等攻击。
错误处理：

使用异常处理程序捕获和处理运行时错误，保证程序稳定性，不泄露敏感信息。
权限管理：

确保权限模型合理，只有授权用户才能执行敏感操作。
数据加密：

使用加密技术保护存储和传输的敏感数据，确保数据在未授权访问时的安全性。
代码审计与测试：

定期审计代码和进行安全测试，及时发现和修复潜在的安全问题。
这样确保系统和用户数据的安全性和隐私。
《计算机科学概论》：

1. 分治法 (Divide and Conquer)
   分治法是一种算法设计策略，通过将一个复杂问题分解为若干个规模较小的子问题，分别解决这些子问题，然后将它们的解合并来得到原问题的解。通常包括以下几个步骤：

分解：将原问题分为若干个子问题。
解决：递归地解决这些子问题。
合并：将子问题的解合并成原问题的解。
例子：归并排序和快速排序。

2. 算法 (Algorithm)
   算法是解决特定问题的一系列明确的指令和步骤。良好的算法具有明确性、有限性、可行性和效率等特性。算法可以是数学公式、伪代码或编程语言中的代码实现。

3. 简单变量的算法 (Algorithms with Simple Variables)
   这种算法通常涉及基本数据类型（如整型、浮点型等）以及简单的控制结构（如循环和条件语句）。它们的复杂性相对较低，通常用于处理较简单的问题。

例子：求一个数组的最大值或最小值的算法。

4. 复杂变量的算法 (Algorithms with Complex Variables)
   复杂变量的算法涉及数据结构如数组、链表、树、图等更复杂的类型。算法的设计和实现通常需要考虑更多的数据管理和访问策略。

例子：树的遍历（如前序遍历、中序遍历、后序遍历）或图的遍历（如深度优先搜索、广度优先搜索）。

5. 搜索算法 (Search Algorithms)
   搜索算法专门用于在数据结构中查找特定数据。不同的搜索算法适用于不同的数据结构和应用场景。

例子：

线性搜索：逐个检查元素，适合未排序数据。
二分搜索：在有序数组中利用分治法高速查找，时间复杂度为O(log n)。
6. 排序算法 (Sorting Algorithms)
排序算法用于将一组数据按照特定顺序（如升序或降序）进行排列。不同的排序算法有不同的性能特点和应用场景。

例子：

冒泡排序：通过重复交换相邻元素来排序，简单但效率低（O(n^2)）。
快速排序：利用分治法，选择一个基准进行分割，效率较高（O(n log n)）。
7. 递归算法 (Recursive Algorithms)
递归算法是指在算法的定义中调用自身的一种方法。递归通常用于解决具有重复性质的问题，需保证有基准情况以避免无限递归。
《C语言程序设计》:

1. 选择结构 (Selection Structure)
   选择结构是控制程序执行流程的基本结构，主要用于根据特定条件的真值选择执行的代码块。选择结构通常分为两种主要类型：

• if 语句
  if 语句用于执行条件判断。它首先检查指定的布尔表达式。如果该表达式为真，则执行其包含的代码块。如果为假且存在 else 部分，则执行 else 中的代码。if 语句可以扩展为多个条件，通过链式结构将多个 if 语句连接起来，使用 else if 来处理更多情况。这种结构允许开发者根据复杂条件进行处理。

• switch 语句
  switch 语句用于根据一个变量的值（通常是整数或字符）执行不同的代码路径。开发者可以定义多个 case，每个 case 代表一个可能的值，并指定对应的代码段。在每个 case 的结尾，使用 break 语句可以阻止执行后续的 case。如果所有 case 都不匹配，可以使用 default 语句来处理其他未列出的情况。这种结构特别适合处理离散的、有限的特定值。

2. 关系运算符和关系表达式
   关系运算符用于比较两个值之间的关系，并返回布尔结果（真或假）。这些运算符可以用于条件表达式和循环控制中，判断某个条件是否成立。主要的关系运算符包括：

== （等于）：用于检查两个值是否相等。
!= （不等于）：用于检查两个值是否不相等。

（大于）：用于判断左侧值是否大于右侧值。
< （小于）：用于判断左侧值是否小于右侧值。
= （大于等于）：用于判断左侧值是否大于或等于右侧值。
<= （小于等于）：用于判断左侧值是否小于或等于右侧值。
这些运算符在程序逻辑中经常与条件语句组合使用，以实现决策过程。

3. 逻辑运算符和逻辑表达式
   逻辑运算符用于组合一个或多个布尔表达式，生成复合布尔结果。常见的逻辑运算符有：

&& （逻辑与）：只有当所有操作数均为真时，结果才为真。
|| （逻辑或）：只要有一个操作数为真，结果即为真。
! （逻辑非）：用于反转布尔值，即如果条件为真，则结果为假，反之亦然。
逻辑运算符通常在条件表达式中使用，以构造更复杂的逻辑判断，允许对多个条件进行综合评估。

4. 条件运算符和条件表达式
   条件运算符（或称三元运算符）是一种用于简化条件判断的运算符，能够在单行中实现简单的条件选择。基本语法结构包括一个布尔条件、一个在条件为真时执行的表达式和一个在条件为假时执行的表达式。条件运算符根据条件的真假返回对应的结果。

这种运算符通常用于简化代码，使得赋值或返回值的操作更加简洁。与 if-else 结构相比，条件运算符在某些情况下使代码更为简明，但在复杂条件下使用时可能影响可读性。

基于AI的学习

学习进度条