计算机导论——CS50

0.1 关于CS50对进制的介绍——二进制、八进制、十六进制。

二进制（Binary）：0、1组成的数，以 2 为基数。base-2
八进制（Octal）：0~7组成的数，以 8 为基数。base-8
十进制（Decimal）：0~9组成的数，以 10 为基数。base-10
十六进制（Hexadecimal）：0_9、AF（大小写皆可）组成的数，以 16 为基数。base-16

0.2 计算机的组成结构——计算机由硬件和软件组成。

硬件：计算机的硬件由处理器（中央处理器Central Processing Unit，CPU）、内存（Random Access Memory，RAM）、输入输出设备（Input/Output Device，I/O Device）、显示器（Display）、键盘、鼠标、硬盘等组成。）存储设备等组成。

软件：计算机的软件由操作系统、应用软件、网络软件等组成。

0.3 计算机的运行原理

基于二进制的。
计算机的每一个指令都是一个二进制的数字，每一个数据都是一个二进制的数字。

0.4 计算机的编程语言

C、C++、Java、Python、JavaScript、PHP、SQL、HTML、CSS、XML、JSON等。

0.5 计算机的操作系统

计算机的操作系统有Windows、Mac OS、Linux、Unix等。

0.6 计算机的网络

有TCP/IP协议、HTTP协议、FTP协议、SMTP协议等。

0.7 编译（complier）:

将高级语言编译成机器语言。
汇编语言（assembly language）：机器语言的助记符。

0.8虚拟机（Virtual Machine）：

模拟计算机的运行环境。

虚拟机可以运行各种操作系统，包括Windows、Mac OS、Linux等。

虚拟机可以运行各种编程语言，包括C、C++、Java、Python、JavaScript、PHP、SQL、HTML、CSS、XML、JSON等。

0.9 数据库（Database）：

关系型数据库：MySQL、Oracle、SQL Server等。存储、管理、检索数据。

0.10 云计算（Cloud Computing）

利用网络提供的计算资源。

Week-1-2 C语言概述

C
基础且底层的编程语言。

1.1 基本数据类型与变量：

1.1.1 数据类型：

int（整型）：

用于表示整数，有不同的取值范围，如 short int、int、long int 和 long long int，具体的范围取决于编译器和系统。

例如，在常见的 32 位系统中，int 类型通常占用 4 个字节，取值范围是 -2147483648 到 2147483647。

float、double（浮点型）：

用于表示带有小数部分的数字。float 一般占用 4 个字节，提供大约 6 到 7 位有效数字的精度；double 通常占用 8 个字节，精度更高，大约 15 到 16 位有效数字。

char（字符型）：

用于存储单个字符，实际上是用整数来表示字符的 ASCII 码值。
例如，字符 ‘A’ 的 ASCII 码值是 65，在内存中 char 类型的变量存储的就是 65 这个整数。

1.1.2 变量定义与初始化：

变量必须先定义后使用，定义时要指定变量的类型和名称。
例如：int num; 定义了一个名为 num 的整型变量。

可以在定义变量的同时进行初始化，如 int count = 0;。如果没有初始化，变量的值是不确定的，使用未初始化的变量可能会导致程序出现错误的结果。

1.2 运算符与表达式：

算术运算符：
+、-、*、/ 分别表示加、减、乘、除运算。需要注意的是，整数除法会舍去小数部分，
例如 5 / 2 的结果是 2。

% 是取模运算符，用于求两个整数相除的余数，
例如 7 % 3 的结果是 1。

关系运算符：
==（等于）、!=（不等于）、>（大于）、<（小于）、>=（大于等于）、<=（小于等于）用于比较两个值的大小关系，返回的结果是 true（真）或 false（假），在 C 语言中分别用整数 1 和 0 表示。
例如：if (a > b) 中的条件如果成立，a > b 的结果就是 1，否则是 0。

逻辑运算符：

&&（逻辑与）：只有当两个操作数都为真时，结果才为真。
例如：if (a > 0 && b > 0) 表示当 a 和 b 都大于 0 时，条件成立。

||（逻辑或）：只要两个操作数中有一个为真，结果就为真。
例如：if (a > 0 || b > 0) 表示只要 a 或 b 中有一个大于 0，条件就成立。

!（逻辑非）：用于对一个逻辑值取反。
例如：if (!flag) 表示当 flag 为假时，条件成立。

赋值运算符：
= 是基本的赋值运算符，用于将一个值赋给一个变量。
例如：x = 10; 把 10 赋给变量 x。

还有复合赋值运算符，如 +=、-=、*=、/=、%= 等，它们是将运算和赋值操作组合在一起。
例如：x += 5; 相当于 x = x + 5;。

1.3 控制流语句：

1.3.1 条件语句（if-else）：

if 语句用于根据一个条件来决定是否执行一段代码。

		if (score >= 60) { printf("及格"); } 如果 score 变量的值大于等于 60，就会输出 "及格"。

if-else 语句可以在条件不满足时执行另外一段代码。

		if (age >= 18) { printf("成年人"); } else { printf("未成年人"); } 根据 age 变量的值判断是成年人还是未成年人。

if-else if-else 结构来处理多个条件的情况。

		if (score >= 90) { printf("优秀"); } else if (score >= 80) { printf("良好"); } else if (score >= 60) { printf("及格"); } else { printf("不及格"); }

1.4 循环语句：

1.4.1 for 循环：

for (初始化表达式; 条件表达式; 更新表达式) { 循环体 }。初始化表达式在循环开始时执行一次，用于初始化循环变量；条件表达式在每次循环开始前进行判断，如果为真则执行循环体，否则结束循环；更新表达式在每次循环体执行完后执行，用于更新循环变量。
for (int i = 0; i < 10; i++) { printf("%d ", i); }
会输出 0 到 9 的数字。

1.4.2 while 循环：

while (条件表达式) { 循环体 }。只要条件表达式为真，就会一直执行循环体。
int i = 0; while (i < 10) { printf("%d ", i); i++; } 与前面的 for 循环效果相同。

1.4.3 do-while 循环：

**do { 循环体 } while (条件表达式);。**先执行一次循环体，然后再判断条件表达式，如果为真则继续循环，否则结束循环。这种循环至少会执行一次循环体。例如：int i = 0; do { printf("%d ", i); i++; } while (i < 10);
跳转语句：

1.4.4 break：

用于跳出循环或 switch 语句。在循环中遇到 break 时，会立即结束循环；在 switch 语句中，用于跳出当前 case 分支。

1.4.5 continue：

用于跳过当前循环的剩余部分，直接进入下一次循环。例如：在一个循环中，如果某个条件满足，使用 continue 可以跳过后续的代码，直接进行下一次循环。

1.5 数组与字符串：

1.5.1 数组(Array)：

定义数组时需要指定数组的类型、名称和大小。例如：int arr[10]; 定义了一个包含 10 个整数的数组。
数组的下标从 0 开始，访问数组元素时可以使用下标。例如：arr[0] 表示数组 arr 的第一个元素。索引从0开始
可以通过循环来遍历数组，对数组中的元素进行操作。例如：for (int i = 0; i < 10; i++) { arr[i] = i * 2; } 给数组 arr 的每个元素赋值。

1.5.2 字符串(String)：

C 语言中没有专门的字符串类型，而是使用字符数组来表示字符串。例如：char str[] = “Hello”; 定义了一个字符串 str。string==char*
字符串以 ‘\0’ 作为结束标志，在处理字符串时需要注意字符串的长度和结束标志。计算长度时要+1
有一些字符串操作的函数，如 strlen() 用于计算字符串的长度（不包括结束标志 ‘\0’）、strcpy() 用于复制字符串、strcmp() 用于比较两个字符串等。例如：strcpy(dest, src); 将 src 字符串复制到 dest 字符数组中。

1.6 指针：

1.6.1 指针的概念：

指针是一个变量，它存储的是另一个变量的地址。通过指针可以间接访问变量的值。例如：int a = 10; int *p; p = &a; 定义了一个整型变量 a 和一个整型指针 p，并将 p 指向 a 的地址，那么 *p 就表示 a 的值，即 10。

1.6.2 指针的运算：

指针可以进行加减运算，但是指针的加减运算不是简单的数值加减，而是根据指针所指向的数据类型的大小来进行偏移。例如，如果 p 是一个指向 int 类型的指针，那么 p + 1 会指向数组的下一个 int 类型的元素的地址。
两个指向同一个数组的指针可以相减，结果是两个指针之间的元素个数的差值。

1.6.3指针与数组的关系：

数组名可以看作是一个指向数组第一个元素的指针。例如，对于数组 int arr[10];，arr 和 &arr[0] 是等价的，都表示数组的首地址。可以使用指针来访问数组元素，例如 int *p = arr; 后，p[i] 和 arr[i] 是等价的。

1.6.4 指针作为函数参数：

可以将指针作为函数的参数，这样可以在函数内部修改调用者传递的变量的值。例如：
调用 swap(&x, &y); 可以交换 x 和 y 的值。

1.7 函数：

1.7.1 函数的定义与调用：

1.7.1.1 函数的定义

包括函数的返回类型、函数名、参数列表和函数体。例如：int add(int a, int b) { return a + b; } 定义了一个名为 add 的函数，它接受两个 int 类型的参数，返回它们的和。

1.7.1.2函数的调用

需要提供与函数定义中参数列表相匹配的参数。例如：int result = add(3, 5); 调用 add 函数，并将 3 和 5 作为参数传递给函数，函数返回的结果赋值给 result 变量。

1.7.2 函数的参数传递：

1,7.2.1值传递：

在函数调用时，将实参的值复制给形参，函数内部对形参的修改不会影响到实参的值。

1.7.2.2引用传递（通过指针实现）：

将实参的地址传递给形参，函数内部通过指针可以修改实参的值。

1.7.2.3 函数的返回值：

函数可以返回一个值，也可以没有返回值（返回类型为 void）。如果函数有返回值，在函数体中必须使用 return 语句返回一个值。

1.8 结构体与共用体：

关于点操作符（.）的使用：

用于访问结构体的成员：

// 定义一个结构体类型
struct Person {
    char name[20];
    int age;
    float height;
};

int main() {
    // 创建一个结构体变量并初始化
    struct Person person = {"Alice", 25, 1.65};

    // 使用点操作符访问结构体成员并输出
    printf("Name: %s\n", person.name);
    printf("Age: %d\n", person.age);
    printf("Height: %.2f\n", person.height);

    // 修改结构体成员的值
    person.age = 26;
    person.height = 1.70;

    // 再次输出结构体成员的值
    printf("\nAfter modification:\n");
    printf("Name: %s\n", person.name);
    printf("Age: %d\n", person.age);
    printf("Height: %.2f\n", person.height);

    return 0;
}

1.8.1 结构体：

typedef struct { int age; char name[20]; float score; } Student;

结构体是一种用户自定义的数据类型，可以将不同类型的变量组合在一起。例如：
定义了一个名为 Student 的结构体类型，包含 name、age 和 score 三个成员。
可以定义结构体变量，并访问结构体成员。

例如

struct Student stu; stu.age = 20; strcpy(stu.name, "John"); stu.score = 85.5;

1.8.2共用体：

共用体是一种特殊的结构体，所有成员共享同一块内存空间，同一时间只能存储一个成员的值。例如：
定义了一个名为 Data 的共用体类型，它的成员 i、f 和 c 共享同一块内存空间。

1.9 文件操作：

1.9.1文件的打开与关闭：

使用 fopen() 函数打开文件，返回一个文件指针；
使用 fclose() 函数关闭文件。
例如：FILE *fp = fopen("data.txt", "r"); 以只读方式打开名为 data.txt 的文件，如果打开成功，fp 指向该文件；操作完成后，使用 fclose(fp); 关闭文件。

1.9.2 文件的读写操作：

fscanf() 和 fprintf() 函数用于格式化的文件读写，类似于 scanf() 和 printf() 函数。
例如：fscanf(fp, “%d”, &num); 从文件 fp 中读取一个整数并存储到 num 变量中；fprintf(fp, “%d”, num); 将 num 变量的值写入到文件 fp 中。
fgetc() 和 fputc() 函数用于逐个字符的文件读写。
例如：char ch = fgetc(fp); 从文件 fp 中读取一个字符并赋值给 ch；fputc(ch, fp); 将字符 ch 写入到文件 fp 中。

*关于对文件的操作，还有一些常用的函数：
“r”：以只读方式打开文件。
“w”：以写方式打开文件，并覆盖原有内容。
“a”：以追加模式打开文件，在文件末尾添加内容。
“r+”：以读写方式打开文件。
“w+”：以读写方式打开文件，并覆盖原有内容。
“a+”：以读写方式打开文件，在文件末尾添加内容。
“b”：以二进制模式打开文件。
“t”：以文本模式打开文件。
“|”：用于设置文件操作的选项。
*

Week-3 Algorithms

3.0关于CS50对此的介绍——即上界与下界的概念。

上界：指的是算法的最高可能的输入值。用O表示法（Big O notation）
下界：指的是算法的最低可能的输入值。用Ω表示法（Omega notation）
当O=Ω时，表示算法的输入值范围是确定的。用θ表示法（Theta notation）

3.1 算法的基本概念：

定义：

算法是解决特定问题的一系列明确的、可执行的步骤。它是一种逻辑上的解决方案，用于指导计算机完成特定的任务。

3.2 效率衡量：

3.2.1 时间复杂度：

衡量算法运行时间随输入规模增长的速度。常见的时间复杂度有 O(1)（常数时间）、O(n)（线性时间）、O(n^2)（平方时间）、O(nlogn)（线性对数时间）O(logn)（对数时间）等。

3.2.2 空间复杂度：

衡量算法在运行过程中所占用的额外存储空间。算法可能需要额外的空间来存储中间结果、数据结构等。

3.3 常见的搜索算法：

3.3.1 线性搜索（顺序搜索）：

原理：

按顺序遍历列表中的每个元素，将其与目标元素进行比较，直到找到匹配的元素或遍历完整个列表。

特点：

简单直观，适用于小型数据集或未排序的数据集，但效率较低，时间复杂度为O(n) 。

3.3.2 二分查找（折半查找）：

原理：

适用于已排序的数据集。每次将数据集分成两半，根据目标元素与中间元素的大小关系，确定在左半部分还是右半部分继续查找，重复这个过程直到找到目标元素或确定目标元素不存在。

特点：

效率较高，时间复杂度为O(nlogn) ，但要求数据集必须是有序的。
常见的排序算法：

3.3.3 冒泡排序：

原理：

通过多次比较相邻的两个元素，将较大（或较小）的元素交换到正确的位置。每次遍历都会将当前未排序部分中的最大（或最小）元素移动到末尾。

特点：

简单易懂，但效率较低，时间复杂度为**O(n^2) **。

3.3.4 选择排序：

原理：

每次从未排序的部分中选择最小（或最大）的元素，将其与未排序部分的第一个元素交换，逐步构建已排序的部分。

特点:

与冒泡排序相比，交换次数较少，但时间复杂度仍为O(n^2) 。

3.3.5 插入排序：

原理：

将未排序的元素逐个插入到已排序的部分中，保持已排序部分的有序性。

特点：

对于接近有序的数据集效率较高，平均时间复杂度为O(n^2) ，但在最好情况下可以达到O(n) 。

3.3.6合并排序（归并排序）：

原理：

采用分治策略，将数据集分成较小的子数据集，分别进行排序，然后将已排序的子数据集合并成一个完整的有序数据集。

特点：

时间复杂度为O(nlogn) ，空间复杂度为O(n) ，具有较高的效率和稳定性，适用于大型数据集。

4.递归：

定义：

递归是一种函数调用自身的技术。在递归函数中，问题被分解为更小的子问题，直到子问题可以直接解决，然后将子问题的解组合起来得到原问题的解。

特点：

可以使代码简洁、清晰，但如果递归深度过大，可能会导致栈溢出等问题。例如，使用递归实现的斐波那契数列计算，代码简洁，但对于较大的输入可能会非常耗时。

分治策略：

概念：

分治策略是将一个大问题分解为多个较小的、相互独立的子问题，分别解决子问题，然后将子问题的解合并起来得到原问题的解。合并排序就是分治策略的一个典型应用。

优点：

可以降低问题的复杂度，提高算法的效率，适用于解决具有重复性结构的问题。

算法的分析与优化：

分析：

通过对算法的时间复杂度和空间复杂度进行分析，可以评估算法的效率和资源占用情况。在实际应用中，需要根据问题
的规模和资源限制选择合适的算法。

优化：

可以通过改进算法的逻辑、选择更合适的数据结构、减少不必要的操作等方式来优化算法，提高算法的性能。例如，对于频繁查找操作，可以使用哈希表等数据结构来提高查找效率

Week-4 Memory

4.1 内存地址与表示：

4.1.1 内存地址的概念：

内存是以字节为单位的一片连续存储空间，每个字节都有唯一的编号，这个编号就是内存的 “地址”。计算机系统通过内存地址来对内存进行管理，地址从 0 开始顺序依次编号。在 C 语言中，使用十六进制数来表示内存地址会更方便，通常会看到类似 “0x7ffc3a7cffbc” 这样的十六进制地址表示形式。

4.1.2 取地址操作符：

在 C 语言中，“&” 是取地址操作符。例如 &n 可以获取变量 n 的内存地址。而 %p 是用于打印地址（指针）的格式化说明符，在 printf 函数中可以使用 **%p **来打印变量的内存地址。

4.2动态内存分配（Dynamic Memory Allocation）：

4.2.1 malloc 函数：

malloc 是 C 语言中的一个标准库函数，用于在程序运行时动态地分配内存空间。例如 int *x = malloc(sizeof(int)) 表示请求系统为一个 int 类型的变量分配内存空间，并将返回的内存地址赋给指针 x。使用 malloc 函数时，需要包含 <stdlib.h> 头文件。

4.2.2 内存的释放：

当不再需要使用通过 malloc 分配的内存空间时，必须使用 **free **函数释放内存，否则会导致内存泄漏。例如 free(x) 可以释放指针 x 所指向的内存空间。

4.3 数据结构与内存：

4.3.1数组与指针的关系：

数组名在很多情况下会被隐式地转换为指向数组第一个元素的指针。这意味着可以通过指针来操作数组，例如可以使用指针来遍历数组元素。但需要注意的是，数组的大小在声明时就已经确定，无法在运行时动态地改变数组的大小。

4.3.2 链表等动态数据结构：

由于指针的存在，可以实现像链表这样的动态数据结构。链表中的每个节点都包含一个数据部分和一个指向下一个节点的指针部分，这样可以根据需要在运行时动态地添加或删除节点，克服了数组无法动态改变大小的限制。

4.4 内存相关的错误与调试：

4.4.1 内存泄漏：

如果程序中不断地使用 malloc 分配内存，但没有及时使用 free 释放，就会导致内存泄漏。随着程序的运行，系统的可用内存会越来越少，最终可能导致程序崩溃。

4.4.2 缓冲区溢出（Buffer Overflow）:

当向一个缓冲区（例如数组）写入的数据超过了缓冲区的大小，就会发生缓冲区溢出。这可能会导致程序出现异常行为，甚至可能被攻击者利用来执行恶意代码。

4.5使用工具调试：

CS50 课程中可能会介绍一些工具来帮助调试内存相关的问题，例如 valgrind。valgrind 可以分析程序的内存使用情况，检测是否存在内存泄漏、缓冲区溢出等问题。
关于对指针（Pointer）的介绍，请看上文。