期中复习

我发现好久好久没写博客了。
懒狗是这样的。
先传一点笔记吧。

📚 知识点大纲

1. 第1章：程序设计与问题解决概述
   • 1.1 程序与程序设计
   • 1.2 问题解决的阶段
   • 1.3 编程语言的层次
   • 1.4 程序的编译与执行
   • 1.5 基本控制结构
   • 1.6 计算机基本组成
2. 第2章：C语言基础：类型、变量、常量与运算符
   • 2.1 标识符、变量与常量
   • 2.2 数据类型
   • 2.3 运算符与表达式
3. 第3章：控制结构
   • 3.1 选择结构
   • 3.2 循环结构
4. 第4章：函数与程序结构
   • 4.1 函数基础
   • 4.2 参数传递
   • 4.3 作用域、生命周期与存储类型
   • 4.4 递归
   • 4.5 C预处理器
5. 第5章：数组
   • 5.1 一维数组
   • 5.2 数组与函数
   • 5.3 数组算法：排序与搜索
   • 5.4 多维数组

📖 详细知识点

第1章：程序设计与问题解决概述

1.1 程序与程序设计

• 程序 (Program): 由计算机执行的一系列指令。
• 程序设计 (Programming): 为计算机规划一系列执行步骤的过程。

1.2 问题解决的阶段

1.  问题解决阶段:
       * 需求分析与规范。
       * 算法设计 (Algorithm): 在有限的时间内逐步解决问题的过程。
2.  实现阶段:
       * 编码 (Coding): 将算法翻译成编程语言。
       * 调试与测试。
3.  维护阶段:
       * 使用、修正错误、改进功能。

1.3 编程语言的层次

• 机器语言 (Machine Language):
      * 由0和1组成的二进制编码指令。
      * 计算机唯一可以直接理解和执行的语言。
      * 不可移植，可读性差。
• 汇编语言 (Assembly Language):
      * 使用助记符（如 LOAD, ADD）来表示机器指令。
      * 需要汇编器(Assembler)进行翻译。
• 高级语言 (High-level Language):
      * 语言类似自然语言，易于读、写和理解。
      * 可移植性好。
      * 示例：C, C++, Java, Python。

1.4 程序的编译与执行

• 编译器 (Compiler):
      * 将高级语言（源码）一次性翻译成机器语言（目标文件）的程序。
      * 编译型语言执行速度通常更快，源码是私有的。
      * 缺点是不跨平台（C, C++）。
• 解释器 (Interpreter):
      * 逐行解释并执行源代码。
      * 解释型语言通常跨平台，易于调试。
      * 缺点是执行速度较慢，源码是公开的（Python, PHP）。
• C语言的编译执行流程:
      1.  源文件 (Source): 程序员编写的 .c 文件（如 myprog.c）。
      2.  编译器 (Compiler): 将源文件翻译成机器语言的 目标文件 (Object)（如 myprog.o）。
      3.  链接器 (Linker): 将目标文件与库函数等其他代码组合起来，生成 可执行文件 (Executable)（如 myprog.exe）。

1.5 基本控制结构

程序由四种基本的控制结构组成：

1.  顺序结构 (Sequence): 语句按顺序一条接一条地执行。
2.  选择结构 (Selection / Branch): 根据特定条件执行不同的语句（如 if, switch）。
3.  循环结构 (Loop / Repetition): 在满足特定条件时重复执行某些语句（如 while, for）。
4.  子程序 (Subprogram / Function): 将程序分解为更小的单元（函数）。

1.6 计算机基本组成

• 硬件 (Hardware):
      * 中央处理单元 (CPU):
          * 算术逻辑单元 (ALU): 执行算术运算和逻辑比较。
          * 控制单元 (Control Unit): 控制程序指令的执行顺序。
      * 内存单元 (Memory Unit):
          * 有序的存储单元序列，每个单元有唯一地址。
          * 用于存放数据和程序指令。
      * 外围设备 (Peripherals):
          * 输入设备（如键盘、鼠标）。
          * 输出设备（如显示器、打印机）。
          * 辅助存储设备（如硬盘、CD-ROM）。
• 软件 (Software):
      * 系统软件 (System Software): 如操作系统（OS），用于管理计算机资源。
      * 应用软件 (Application): 用户执行特定任务的程序。

第2章：C语言基础：类型、变量、常量与运算符

2.1 标识符、变量与常量

• 变量 (Variable):
      * 程序中用于存放数据的容器（存储区域）。
      * 变量名是内存位置的符号表示。
      * 声明变量时必须指定其名称和数据类型。
• 标识符 (Identifier): (即变量名、函数名等)
      * 命名规则:
          1.  只能包含字母（大小写）、数字和下划线 _。
          2.  必须以字母或下划线 _ 开头（不能是数字）。
          3.  长度：理论上无限制，但某些编译器可能对超过31个字符的名称报错。
      * 命名注意事项:
          1.  应使用有意义的名称（如 firstName 而不是 fn）。
          2.  区分大小写 (如 name 和 Name 是不同的)。
          3.  不能 使用C语言的 关键字 (Reserved words) 作为标识符。
• 常量 (Constant):
      * 字面值常量 (Literal value): 直接写在代码中的值，如 100, 3.14, 'A'。
      * 命名常量 (Named constant):
          1.  使用 const 修饰符：const int VOTING_AGE = 18;。
          2.  使用 #define 预处理指令：#define VOTING_AGE 18。
      * 命名常量的值在程序执行期间不能被更改。
• 声明与赋值:
      * 声明 (Declaration): 将标识符与数据对象（如变量）关联起来。所有标识符在使用前必须声明。
      * 赋值 (Assignment): 使用赋值运算符 = 来给变量一个值。
          * 赋值语句的左侧必须是变量，右侧是值或表达式。

2.2 数据类型

• 数据类型 (Data Type):
      * 指定了变量可以存储的数据类型（如整数、浮点数、字符等）。
      * 每种数据类型需要不同大小的内存。
      * C语言数据类型分为：简单类型、结构类型和地址类型。

• sizeof 运算符:
      * 一个一元运算符，用于获取其操作数（变量或类型）所占用的内存字节大小。
      * 示例：sizeof(int), sizeof(age)。
      * C语言保证的最小大小：sizeof(char) 为 1，short 至少16位，long 至少32位。

• 整型 (Integral Types):
      * 用于表示整数，包括 char, short, int, long。
      * char: 字符类型，用于表示单个字符。
          * 字符在内存中以其 ASCII 码值（整数）存储。
          * 字符常量用单引号 ' ' 括起来，如 'B', '4'。
          * 转义字符 (Escape character): 特殊字符，如 \n (换行), \t (制表符), \\ (反斜杠), \" (双引号)。
      * 整型字面值:
          * 十进制 (Decimal): 正常书写，如 16, 498。
          * 八进制 (Octal): 以 0 开头，如 022。
          * 十六进制 (Hexadecimal): 以 0x 或 0X 开头，如 0xFF。

  以下是在目前最常见的系统（32 位和 64 位）中的典型数值范围。

  类型	存储大小 (Bits)	有符号 (Signed) 范围	无符号 (Unsigned) 范围
  char	8	-128 到 127	0 到 255
  short	16	-32,768 到 32,767	0 到 65,535
  int	32	-2,147,483,648 到 2,147,483,647	0 到 4,294,967,295
  long	64*	-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807	0 到 18,446,744,073,709,551,615
  long long	64	-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807	0 到 18,446,744,073,709,551,615

• 浮点型 (Floating Types):
      * 用于表示带小数点的实数，包括 float, double, long double。
      * 科学计数法: 使用 E 或 e 表示，如 1.84E1 (即 1.84 x 10¹)。
      * 默认类型: 没有后缀的浮点常量（如 94.6）默认为 double 类型。
      * 后缀: F 或 f 表示 float (如 94.6F)；L 或 l 表示 long double。
      * 精度: 计算机不能精确表示所有浮点数。double 的精度高于或等于 float。

  浮点型数据用于存储带有小数的数值。它们的范围和精度是两个主要指标。

  类型	存储大小 (Bits)	典型数值范围 (绝对值)	精度 (有效十进制数字)
  float	32	约 3.4E-38 到 3.4E+38	约 6-7 位
  double	64	约 1.7E-308 到 1.7E+308	约 15-16 位
  long double	80 或 128	范围更大，精度更高 (例如 3.4E-4932 到 1.1E+4932)	约 18-19 位或更高

• 布尔型 (bool):
      * C99标准引入，需要包含头文件 <stdbool.h>。
      * 值只有 true (1) 或 false (0)。

• 字符串型 (String):
      * 用双引号 " " 括起来的字符序列，如 "Hello"。
      * 不是C的内置类型，它本质上是一个 字符数组 (char array)。
      * 以空字符 \0 作为结尾标记。
      * 字符串操作函数（如 strlen）定义在 <string.h> 头文件中。
      * "a" (字符串) 与 'a' (字符) 是不同的。

2.3 运算符与表达式

• 表达式 (Expression): 变量、常量和运算符的有效组合，可被求值以计算出一个值。
• 算术运算符 (Arithmetic):
      * 一元：+ (正), - (负)。
      * 二元：+, -, *。
      * / (除法):
          * 若两个操作数都为整数，则执行整数除法（结果为整数，小数部分被截断）。
          * 若任一操作数为浮点数，则执行浮点除法（结果为浮点数）。
      * % (模/取余):
          * 操作数 只能是整数。
          * 结果是整数除法后的余数。
          * 结果的符号由左操作数决定 (C语言中)。
• 自增/自减运算符:
      * ++ (自增) 和 -- (自减)。
      * 前缀 (Prefix): ++a。先改变（加1或减1），再使用新值参与表达式运算。
      * 后缀 (Postfix): a++。先使用原值参与表达式运算，然后再改变（加1或减1）。
• 赋值运算符 (Assignment):
      * = (赋值)。
      * 复合赋值: +=, -=, *=, /=。例如 age += 3; 等同于 age = age + 3;。
• 关系运算符 (Relational):
      * >, <, >=, <=, == (等于), != (不等于)。
      * 结果为 true (非0) 或 false (0)。
      * 注意：= (赋值) 和 == (等于) 是不同的。
• 逻辑运算符 (Logical):
      * ! (非), && (与), || (或)。
      * 短路求值 (Short-Circuit):
          * 对于 &&：如果左侧为 false (0)，则不再计算右侧。
          * 对于 ||：如果左侧为 true (非0)，则不再计算右侧。
• 条件运算符 (Ternary):
      * C语言中唯一的三元运算符：Expression1 ? Expression2 : Expression3。
      * 如果 Expression1 为 true，则整个表达式的值为 Expression2；否则为 Expression3。
• 位运算符 (Bitwise):
      * 对操作数的二进制位进行操作。
      * & (按位与), | (按位或), ^ (按位异或), ~ (按位非/取反)。
      * << (左移), >> (右移)。
• 逗号运算符 (Comma):
      * expression1, expression2。
      * 从左到右依次求值，整个表达式的值等于最后一个表达式 (expression2) 的值。
      * 优先级是所有运算符中最低的。
• 优先级 (Precedence) 与 结合性 (Associativity):
      * 优先级 决定了哪个运算符先执行（如 * / / 优先于 + / -）。
      * 结合性 决定了同优先级运算符的执行顺序（如 * / % + - 都是左结合，从左到右）。
      * 一元运算符、条件运算符、赋值运算符是 右结合（从右到左）。
      * 可以使用 圆括号 () 来强制改变运算顺序。
• 类型转换 (Type Conversion):
      * 隐式转换 (Coercion): 编译器自动进行的类型转换。
          * 发生在赋值时（如 int i = 4.8; i 变为 4）。
          * 发生在混合类型表达式中。
      * 类型提升 (Promotion): 在表达式中，char 和 short 类型的值会自动提升为 int。
      * 混合运算: 较低类型会临时提升为较高类型（int -> long -> float -> double）。
      * 显式转换 (Casting): 程序员强制进行的类型转换。
          * 语法：(typename) expression。
          * 示例：celsius = (5.0/9.0) * (fahr-32);（对比 5/9 结果为0）。
          * 浮点数转整数时，C99规定向0取整（截断小数）。

第3章：控制结构

3.1 选择结构

• if 语句 (单路选择):
      * 语法：if ( Expression ) Statement。
      * 如果 Expression 为 true (非0)，则执行 Statement。
• if-else 语句 (双路选择):
      * 语法：if ( Expression ) StatementA else StatementB。
      * 如果 Expression 为 true，执行 StatementA；否则执行 StatementB。
• {} 块的使用:
      * if 或 else 后面如果需要执行多条语句，必须使用花括号 {} 将它们括起来形成一个语句块。
      * 如果省略 {}，else 会与最近的未配对的 if 结合（悬垂else问题）。
• if-else if-else 结构 (多路选择):
      * 用于实现多路分支。
      * 按顺序测试每个 Expression，一旦找到为 true 的，就执行其后的 Statement，然后跳出整个结构。
      * 如果所有 if 都不为 true，则执行最后的 else 块（如果存在）。
• switch 语句 (多路选择):
      * 语法：switch ( IntegralExpression ) { ... }。
      * IntegralExpression 必须是整型（char, int, long, enum）。
      * case Constant:：Constant 必须是常量表达式。
      * break:
          * 用于跳出 switch 语句。
          * 如果省略 break，程序会 穿透 (fall-through) 并继续执行下一个 case 的语句。
      * default:
          * 可选。如果没有任何 case 匹配，则执行 default 块。
• 测试:
      * 测试选择结构时，应确保每个分支至少被执行一次（最小完全覆盖）。

3.2 循环结构

• 循环 (Loop): 一种重复执行某个语句块的控制结构。
• while 循环 (当型循环):
      * 语法：while ( Expression ) { ...body... }。
      * 先测试 (Pre-test): 在每次迭代 之前 检查 Expression。
      * 如果 Expression 为 false，循环体可能一次也不执行。
• do-while 循环 (直到型循环):
      * 语法：do { ...body... } while ( Expression );。
      * 后测试 (Post-test): 在每次迭代 之后 检查 Expression。
      * 循环体 至少执行一次。
• for 循环:
      * 语法：for ( initialization ; test_expression ; update ) { ...body... }。
      * initialization：循环开始前执行一次（通常用于初始化循环变量）。
      * test_expression：每次迭代前检查，若为 false 则退出循环。
      * update：每次迭代 之后 执行（通常用于更新循环变量）。
• 循环控制:
      * break: 立即 跳出 并终止其所在的最内层循环（或 switch）。
      * continue: 立即 跳过 当前迭代中剩余的语句，直接进入下一次循环的测试（对于 for 循环，会先执行 update）。
      * goto 和 label:
          * 提供从 goto 到同一函数内 label 的无条件跳转。
          * 不推荐使用，但可用于跳出深度嵌套的结构。
• 嵌套循环 (Nested Loop):
      * 一个循环体内包含另一个循环。
      * break 或 continue 只影响最内层的循环。

第4章：函数与程序结构

4.1 函数基础

• 函数 (Function): 用于实现特定功能的一段程序代码。
• 使用原因: 避免代码重复、使程序结构化、提高可读性。
• 函数声明 (Declaration / Prototype):
      * 告知编译器函数的返回类型、名称和参数类型。
      * 语法：type function_name(type arg1, type arg2, ...);。
      * 必须在使用函数前进行声明（通常放在 main 函数之前）。
• 函数定义 (Definition):
      * 提供函数的具体实现（函数头 + 函数体）。
      * 函数头 (Head): type function_name(type arg1, type arg2, ...)。
      * 函数体 (Body): { ... your code ... }。
• return 语句:
      * 用于从函数返回一个值。
      * 函数最多只能返回 1个 值，该值的类型必须与声明的返回类型匹配。
      * void 函数:
          * 表示函数不返回值。
          * 可以使用 return; 语句立即退出函数。
• 函数调用 (Function Call):
      * 通过函数名和参数列表来执行函数。
      * 程序控制权临时从调用函数转移到被调用函数。
      * 被调用函数执行完毕后，控制权返回到调用点。

4.2 参数传递

• 形参 (Parameter / Formal Parameter): 在函数 定义 或声明中指定的变量。
• 实参 (Argument / Actual Parameter): 在函数 调用 时传递给函数的具体值或变量。
• 传递方式:
      1.  值传递 (Pass by Value):
          * C语言的默认方式。
          * 将实参的 值复制 一份传递给形参。
          * 在函数内部修改形参 不会 影响到函数外部的实参。
      2.  地址/指针传递 (Pass by Address):
          * 将实参的 地址 传递给形参。
          * 形参必须是 指针类型 (如 int *x)。
          * 实参必须是地址（如 &a）。
          * 在函数内部通过指针修改形参所指向的内存，会 影响到函数外部的实参。
      3.  引用传递 (Pass by Reference):
          * 这是 C++ 的特性，C语言不支持。
          * 形参是实参的别名（如 int &x）。

4.3 作用域、生命周期与存储类型

• 作用域 (Scope): 标识符（变量或函数名）在程序中可以被合法使用的区域。
      * 局部作用域 (Local Scope): 标识符在块（{}内）或函数内部声明，其作用域从声明点到块或函数结束。
      * 全局作用域 (Global Scope): 标识符在所有函数之外声明，其作用域从声明点到文件结尾。
      * 名称优先级: 局部变量会“隐藏”同名的全局变量。
• 生命周期 (Lifetime): 程序执行期间，标识符实际拥有内存分配的时间。
• 存储类型:
      * 自动变量 (Automatic):
          * 默认的局部变量存储类型（可省略 auto 关键字）。
          * 存储在 栈 中。
          * 生命周期: 函数调用时创建，函数退出时销毁。
          * 初始化: 若不显式初始化，其值为未定义的（垃圾值）。
      * 外部变量 (External):
          * 即全局变量，定义在所有函数之外。
          * 使用 extern 关键字在其他文件中 声明 （非定义），表示引用一个已在别处定义的全局变量。
          * 生命周期: 整个程序运行期间。
          * 初始化: 若不显式初始化，默认为 0。
      * 静态变量 (Static):
          * 使用 static 关键字声明。
          * 静态全局变量: 作用域被限制在声明它的文件内部，其他文件不可访问。
          * 静态局部变量:
              * 作用域仍是局部的（函数内）。
              * 生命周期: 整个程序运行期间。
              * 只在 第一次 调用函数时初始化一次。
              * 在函数多次调用之间 保持其值。
          * 初始化: 若不显式初始化，默认为 0。
      * 寄存器变量 (Register):
          * 使用 register 关键字，建议编译器将变量存储在CPU寄存器中以提高效率。
          * 初始化: 若不显式初始化，其值为未定义的（垃圾值）。

4.4 递归

• 递归 (Recursion): 一个函数调用其自身的过程。
• 递归的两个要素:
      1.  基本情况 (Base Case): 递归的停止条件，一个无需递归即可解决的简单情况。
      2.  递归步骤 (Recursive Step): 将问题分解为更小的、同类的问题，并通过递归调用来解决。
• 递归 vs. 迭代 (Iteration):
      * 任何递归都可以用迭代（循环）和栈来代替。
      * 迭代（循环）在执行速度和空间占用上通常 优于 递归。

4.5 C预处理器

• 在编译之前对源代码进行处理的程序。
• 文件包含 (#include):
      * #include <filename>: 在标准库目录或系统路径中查找文件。
      * #include "filename": 从源程序当前目录开始搜索（通常用于自定义头文件）。
• 宏替换 (#define):
      * 定义一个宏（一个名称和一段替换文本）。
      * 预处理器会在编译前进行 原样文本替换。
      * 带参数的宏: define max(A,B) ((A) > (B) ? (A) : (B))。
      * 宏的陷阱:
          * 宏是纯文本替换，要注意运算符优先级，因此宏定义中应多用括号。
          * 注意带副作用的参数，如 max(i++, j++)，会导致 i 或 j 被自增多次。
• 条件包含 (#if…):
      * 允许根据预处理时的条件来选择性地编译某段代码。
      * 指令包括：#if, #elif, #else, #endif。
      * #ifndef: “if not defined”，常用于防止头文件被重复包含。

第5章：数组

5.1 一维数组

• 数组 (Array): 存储 相同数据类型 的元素的集合，这些元素在内存中 连续存放。
• 数组声明:
      * 语法：DataType ArrayName [ConstIntExpression];。
      * ConstIntExpression 必须是 常量表达式，指定数组的大小（元素个数）。
      * 数组大小一旦固定，不可更改。
• 数组元素访问:
      * 通过 下标 (Index / Subscript) 访问，下标从 0 开始。
      * temps[0] 是第一个元素，temps[4] 是第五个元素（对于大小为5的数组）。
• 数组名:
      * 数组名（如 temps）本身是一个 指针，其值是数组的 基地址（即第一个元素 temps[0] 的内存地址）。
• 数组初始化:
      * 可以在声明时初始化：int ages[5] = {40, 13, 20, 19, 36};。
      * 可以省略大小，编译器会自动计算：int ages[] = {40, 13, 20};。
      * 部分初始化: int a[5] = { 2 }; 第一个元素为2，其余所有元素自动初始化为 0。
• 数组的限制:
      * 无边界检查 (No Bound Checking): C语言不检查数组下标是否越界。访问 myList[-1] 或 myList[11]（假设大小为4）不会产生编译错误，但会导致运行时错误或未定义行为。
      * 无聚合操作 (No Aggregate Operations): 不能将一个数组整体赋值给另一个数组（如 x = y; 是错误的）。
      * 数组复制必须通过循环逐个元素进行。

5.2 数组与函数

• 数组作为函数参数:
      * 当数组作为参数传递时，传递的是数组的 基地址。
      * 因此，函数参数传递总是 地址传递。
      * 在函数内部对形参数组的修改 会 影响到主调函数中的实参数组。
      * 通常需要传递两个参数：数组的基地址（数组名）和数组中要处理的元素个数（大小）。
• 形参声明:
      * float FindMax(float arr[], int n)
      * float FindMax(float *arr, int n) (等价)
• const 保护数组参数:
      * 如果不希望函数修改数组内容，应在形参声明中使用 const 关键字。
      * 示例：float FindMax(const float arr[], int n)。

5.3 数组算法：排序与搜索

• 选择排序 (Selection Sort):
      * 算法思想:
          1.  从头（passCount = 0）开始。
          2.  在 data[passCount ... length-1] 范围内找到 最小 元素的索引 minIndx。
          3.  将 data[minIndx] 与 data[passCount] 交换。
          4.  passCount 增加1，重复该过程，直到 passCount 达到 length - 2。
• 线性搜索 (Linear / Sequential Search):
      * 适用于 未排序 的数组。
      * 从头到尾（i=0 到 n-1）逐个检查元素，看是否等于目标值 x。
      * 找到则返回索引 i，遍历完未找到则返回 -1。
• 二分搜索 (Binary Search):
    C* 必须 适用于 已排序 的数组。
      * 算法思想:
          1.  设 first = 0, last = arraySize - 1。
          2.  当 last >= first 时循环：
          3.  计算中间索引 mid = (first + last) / 2。
          4.  如果 key == list[mid]，则找到，返回 mid。
          5.  如果 key < list[mid]，则目标在左半边，令 last = mid - 1。
          6.  如果 key > list[mid]，则目标在右半边，令 first = mid + 1。
          7.  循环结束仍未找到，返回 -1。

5.4 多维数组

• 二维数组 (Two-Dimensional Array):
      * 按行和列组织的同类型元素集合。
      * 声明: DataType ArrayName [Rows] [Cols];。
      * 访问: stateHighs[2][7] (访问第3行第8列的元素)。
      * 内存存储: 在内存中按 行优先 (Row Order) 连续存储（第一行所有元素，接着是第二行所有元素…）。
• 多维数组作为函数参数:
      * 传递的仍然是基地址。
      * 必须 指定 除第一维之外 的所有维度的大小。
      * 示例：void FindAverages(const int stateHighs[][NUM_MONTHS], ...)。
• typedef 与数组:
      * 可以使用 typedef 来定义数组类型，使函数原型更简洁明了。
      * 示例：typedef int SalesType[3][12][5]; SalesType sales;。