CS107笔记

概述 ： CS10是斯坦福一门计算机课程，网上有对应的课程链接 CS107 此为本人自学此课程的总结 当然大部分都是课件里面有的，拿出来分享一下，共同学习 下面进入正题

Lecture 1（第一节课 后面省略）

本节课程计划

• CS107课程政策
• Unix和命令行
• C入门

CS107课程政策

什么是CS107

1. C++和java语言背后是如何表示数据的
2. 编程结构如何以位和字节编码
3. 如何有效的操作和管理内存
4. 使用C语言
5. 编程风格与软件开发实践

学习目标

CS107的目标是让学生掌握

1. 用复杂的内存和指针编写C程序
2. C程序地址空间和编译/运行行为的精确模型

取得能力

1. 将C转换为/从程序集转换
2. 编写尊重计算机算法局限性的程序
3. 识别瓶颈并提高运行时性能
4. 在Unix开发环境中有效地工作

接触到

• 对计算机体系结构基础的有效理解

课程概述

1. 位和字节-计算机如何表示整数？
2. 字符和C字符串-计算机如何表示和操作更复杂的数据，如文本？
3. 指针、堆栈和堆——如何有效地管理程序中的所有类型的内存？
4. 泛型-我们如何使用我们的内存和数据表示的知识来编写可以处理任何数据类型的代码？
5. 汇编——计算机如何解释和执行C程序？
6. 堆分配器-像malloc和free这样的核心内存分配操作是如何工作的？

另外，它推荐了一本书

《计算机系统：程序员的视角》，Bryant&O'Hallaron著，第3版

其他的都是有关作业什么的方案 ，我们无法按照他的方案进行，也无法获取他们的作业，省略

Unix和命令行

什么是Unix

1. Unix：软件开发中常用的一组标准和工具。

2. macOS和Linux是建立在Unix之上的操作系统

3. 您可以使用命令行（“终端”）导航Unix系统

4. 每个Unix系统使用相同的工具和命令工作

什么是命令行

命令行是一个基于文本的界面（即终端界面）来导航计算机，而不是图形用户界面（GUI）。

简单的说开始我们常说的黑框框

插一句 因为我害怕给遗漏掉什么东西，所以会比较长甚至啰嗦。大家碰到自己已经了解或明白的地方自行跳过 感谢

命令行进而图形化用户界面的区别

就像GUI文件浏览器界面一样，终端界面

• 在任何时间显示计算机上的特定位置

• 允许您进入文件夹和退出文件夹

• 允许您创建新文件和编辑文件

• 允许您执行程序

为什么使用Unix

您可以使用相同的工具和命令导航几乎任何设备：

服务器

笔记本电脑和台式机

嵌入式设备（树莓皮等）

移动设备（Android等）

软件工程师经常使用：

Web开发：在服务器上运行服务器和Web工具

机器学习：在服务器上处理数据，运行算法

系统：编写操作系统、网络代码和嵌入式软件

移动开发：运行工具、管理库

还有更多…

我们将使用Unix和命令行来实现和执行我们的程序

上面是课件对此的描述 说白了就是应用范围广

介绍几个常用的命令

cd–更改目录（…）

ls–列出目录内容

mkdir–生成目录

emacs–打开文本编辑器

rm–删除文件或文件夹
man- 查看手册

这里多少几句
cd 可以理解为进入目录
cd + 目录名
cd ../ 进入上一级目录

ls 就是显示当前目录下的文件当然包括目录
ls -a 显示所有文件 包括隐藏文件

mkdir +目录名 （结对路径或相对路径）
emacs 需要你下载对应软件 更具体的自行搜索

rm +文件名 删除文件
rm -r +文件夹名 删除目录及目录下的所有文件

man 后面要节参数 例如 man -a 等等，太多了自行搜索即可

命令还有很多 就不多说了 网上都可以找得到

C入门

略过 这部分内容主要说

1. C的产生 发展
2. C和C++的比较
3. C的优势
4. Hello world 程序

这里就不说了 可以去课件了解一下
Lecture 1课件
提取密码 8rdo
链接失效记得提醒我

Lecture 2

本节课程计划

1. 比特与字节
2. 十六进制
3. 整数表示法
4. 无符号整数
5. 有符号整数
6. 溢流
7. 转换类型和合并类型

比特和字节

1. 了解十进制和二进制
2. 计算机是以0 1 为单位的，计算机上所有的数据，文件都是二进制表示的 一个二进制为为一个比特位 。一个字节=八个比特位
3. 熟练进行十进制和二进制之间的转换（转换方法不止一种，看自己）
4. 了解基数的概念 二进制的基数是2，十进制的基数是10
5. 一个字节所能表示的数 最大为 255 最小为0
6. 乘以基数和除以基数的运算

十六进制

1. 我们在处理32位，64位的数据是 为了方便要用到，当然好多地方
2. 了解十六进制的基数是16 以及各数对应的数字或字母
3. 十进制 二进制 十六进制中 对于0-15 之间的对应关系
4. 对于各进制的数我们为了便于区分 二进制前有0b 十进制省略 十六进制用0x
5. 熟练进行十六进制和二进制和十进制之间的转换

整数表示法

整数有分有符号和无符号以及浮点数
本节先了解一下计算机上的32位和64位，以及在这两种环境下各类型的数据分别占多少空间

32位

C Declaration	Size (Bytes)
int	4
double	8
float	4
char	1
char *	4
short	2
long	4

64位

C Declaration	Size (Bytes)
int	4
double	8
float	4
char	1
char *	8
short	2
long	8

至于为什么，我把原文的翻译放在这里

21世纪初：大多数计算机是32位的。这意味着指针是4个字节（32位）。
32位指针存储从0到232-1的内存地址，相当于232字节的可寻址内存。这相当于4GB，这意味着32位计算机最多可以有4GB内存（RAM）！
正因为如此，计算机转换到64位。这意味着数据类型被放大了；程序中的指针现在是64位。
64位指针存储从0到264-1的内存地址，相当于264字节的可寻址内存。这相当于16EB，这意味着64位计算机最多可以有102410241024GB的内存（RAM）！

有链接，自己看就好了 ，了解即可

无符号整数

0或正整数
范围 0--2的n次方减一 （n为二进制位数，即位的数目）

无符号整形的表示是呈圈形的
以四位二进制表示为例
1111：15 此数加一为0

图片的话更形象 课件里面有

有符号整数

简单点一个公式
一个整数的负数表示=其正整数的二进制表示取反加一

例如1：0001
-1 ： 1111

Decimal	Positive	Negative
0	0000	0000
1	0001	1111
2	0010	1110
3	0011	1101
4	0100	1100
5	0101	1011
6	0110	1010
7	0111	1001
8	####	1000

附一句 以四位二进制为例
其表示范围(有符号整型)-8~7
理解为 -(2的(4-1)次方)--2的(4-1)次方-1
前面的4换成n 就是n位二进制所能表示的有符号整数范围

总结 有符号整数 表示
正： 直接转换就好 （原码）
负： 补码（对应正数的二进制表示反码加一）
0 全是0

这样利于进行加减运算 具体的演示 见课件

溢出

溢出则“绕圈” 按照课件上图示的那样 ，这里就不上图了
例如 四位二进制有符号整数
圈为 0₇（-8）_（-1）0；
端点处的0连接起来 即为圈
其他的数据类型 例如 char
其对应的ASC码也遵循此规则 只不过 显示的时候是其对应的字符表示

对于溢出现象 课件有更为详细的介绍以及案例，有时间的可以去了解一下

转换类型和合并类型

占位符

%d 有符号32位int
%u 无符号32位int
%x 16进制表示的32位int

用于在printf中表示要输出的类型
这种占位符 还有很多种
自行搜索 因为这属于C语言的内容

提一个问题

int v = -12345;

unsigned int uv = v;

printf("v = %d, uv = %u\n", v, uv);

输出: "v = -12345, uv = 4294954951".
这是为什么呢

另外补充一点
在进行 无符号整型和有符号整型的大小比较时
C讲两数均转换为无符号整形进行比较

类型转换

有时 我们会对两个不同类型的数进行比较
此时，系统会将两数均转换为较大的类型 进而进行比较

这里说一下 我们不能将较大的数据类型转换为小的类型 ，但反之是可行的

那么 转换是怎样进行的呢

无符号 前面补0
有符号 前面补符号位

有时候我们也会将大类型转化为小类型

此时会将数据的长度进行折断
忽视高位（左边）

这段内容课件上有配套练习题 建议去看一下

sizeof 运算符

该运算符接受一个变量类型，并返回其大小 单位为字节

//示例

long int_size_bytes=sizeof（int）；//4

long short_size_bytes=sizeof（short）；//2

long char_size_bytes=sizeof（char）；//1

lecyture 3

此节主要是位运算的介绍
补充一句 计算机中所有数据等 全是用01表示

先介绍一下ASC码

ASCII是从普通字符（字母、符号等）到位表示（字符）的编码

所有大写字母和所有小写字母都按顺序表示！

更具体的自行百度

位运算符

有哪些： &, |, ~, ^,

介绍

1. & 同时为1 结果为1
2. | 只要有一个为1 结果就是1
3. ~ 原来是1变为0 原来是0变为1 （取反）
4. ^ 二者不同（一0一1） 结果为1 否则为0

-- 学过离散数学会更好

应用 见课件

比如

如何分离某位

如何修改指定为

如何求位的交集 并集

如何翻转 指定位或所有位

左移运算符

所谓左移运算符： <<
就是将该数在内存中的二进制表示向左移动

用新的最高位去取代最高位 低位用0替换

例如 00110111 << 2 返回 11011100
左移简单点 ，重点是右移

右移运算符

移动很简单 但是用什么来填充移掉的位置呢
用0 ？？

0是不行的

x=-2；//1111 1111 1111 1110

x>>=1；//0111 1111 1111 1111

printf（“%d\n”，x）；//32767！
多余的例子就不举了

OK 我们现在看解决方案

我们用符号位进行填充

例1

x=2；//0000 0000 0000 0010

x>=1；//0000 0000 0000 0001

printf（“%d\n”，x）；//1

例2

x = -2; // 1111 1111 1111 1110

x >>= 1; // 1111 1111 1111 1111

printf("%d\n", x); // -1!

这样就不会找成符号错乱等问题

总而言之

右移 有两种

1. 逻辑右移 用0 补充
2. 算术右移 用符号位（高阶有效位）补充

一般使用场景

无符号数字使用逻辑右移进行右移。

有符号数字使用算术右移进行右移。

补充

从技术上讲，C标准并没有精确地定义有符号整数的右移是逻辑的还是算术的。

但是 几乎所有的编译器/机器都使用算术，

还有一点 1<<2+3<<4
例如上面的这种运算

要注意！！
加法和减法的优先级高于移位！

等效为 1<<（2+3）<<4

其余注意点

如果你想要一个二进制位前32位全为1的长整型

long num = 1 << 32;

这样是不对的

默认情况下，1是一个int，并且不能将int移位32，因为它只有32位。必须指定希望1为long。

所以要用

long num==1L<<32;

OK 本课结束

Lecture 4� C Strings

显而易见 本节主要结束字符串

问题 计算机如何表示复杂数据 例如 文本

先看大纲

字符

串

常用字符串操作

比较

复制

串联

子字符串

字符 （char）

C语言将每个字符表示为一个整数 起名为ASCII值

ASCII的一般规则

大写字母按顺序编号

小写字母按顺序编号

数字按顺序编号

小写字母比大写字母多32个

举几个例子

char uppercaseA='A'；//实际上是65

char lowercaseA='a'；//实际上是97

char zeroDigit='0'；//实际为48

bool areEqual = 'A' == 'A'; // true

bool earlierLetter = 'f' < 'c'; // false

char uppercaseB = 'A' + 1;

int diff = 'c' - 'a'; // 2

int numLettersInAlphabet = 'z' – 'a' + 1;

// or

int numLettersInAlphabet = 'Z' – 'A' + 1;

通用函数

Function	Description（说明）
isalpha(ch)	如果ch是'a'到'z'或'A'到'Z' 返回true
islower(ch)	如果ch是'a'到'z' 返回true
isupper(ch)	如果ch是'A'到'Z' 返回true
isspace(ch)	如果ch是空格、制表符、换行符等,返回true
isdigit(ch)	如果ch是'0'到'z'或'A'到'9'，返回true
toupper(ch)	返回ch对应的大写字母
tolower(ch)	返回ch对应的小写字母

注意

这些方法至是返回一个字符 不会修改现有字符

示例

bool isLetter = isalpha('A'); // true

bool capital = isupper('f'); // false

char uppercaseB = toupper('b');

bool isADigit = isdigit('4'); // true

字符串

C语言中没有字符串的变量类型，他是由有特殊符号的字符数组来表示的 '\0'

在数组中始终要有它的位置

C语言提供了计算字符串长度的函数

int length=strlen（myStr）；//例如13

如果要用这个值要记得保存

当字符串作为参数传入函数中时 ， C传递的是字符串的首地址

对于传递过去的首地址 我们可以像使用字符数组一样使用它

str[0] = 'c'; // modifies original string!

printf("%s\n", str); // prints cello

常用的string.h函数

Function	Description（说明）
strlen(str)	返回字符串分（不包括终止字符）
strcmp(str1, str2), strncmp(str1, str2, n)	比较两个字符串，如果str1大于str2返回1，如果str小于str2，返回-1，相等返回0，n表示最多在n个字符后停止比较
strchr(str, ch)，strrchr(str, ch)	字符查找，strchr 返回str中第一个指向ch字符出现的位置，strrchr 则是返回最后一个，没有找到返回null
strstr(haystack, needle)	字符串搜索，返回一个指针，指向haystack中第一次出现needle的开始，如果在haystack中没有找到needle，则返回NULL
strcpy(dst, src),strncpy(dst, src, n)	字符串拷贝将src中的字符串拷贝到dst中，包括终止符，strncpy最多在拷贝n个字符之后停止，并且不添加null终止字符。
strcat(dst, src),strncat(dst, src, n)	字符串连接，一个是全部链接，另一个strncat是最多连接n个字符之后停止连接 总是会在结尾添加终止符
strspn(str, accept),strcspn(str, reject)	strspn 返回一个长度n，该长度表示在str的前n个字符在accept中都能找到，setcspn也返回一个长度，该长度表示在str中前n个字符在accept中都找不到

很多字符串函数都假定你给的字符串是符合规范的（有终止符）

不能用<,>，== 等这些符号对字符串进行比较 ，这样比较，其实比较的是地址

不能 用等号来进行字符串的拷贝 这样拷贝的是地址

关于字符串的拷贝这里提供一个例子

char str1[6];
strcpy(str1, "hello");

char str2[6];
strcpy(str2, str1);
str2[0] = 'c';

printf("%s", str1);   // hello
printf("%s", str2);   // cello

同时在进行字符串拷贝的时候，我们必须确保目标地址有足够的空间

例如

char str2[6]；//空间不足！

strcpy（strpy，“你好，世界！”）；//覆盖其他内存！

写入超过内存边界称为“缓冲区溢出”。它可以允许安全漏洞！

还有规定数量的拷贝

// copying "hello"
char str2[5];               
strncpy(str2, "hello, world!", 5);  // doesn’t copy '\0'!

当我们的字符串没有空终止符时，我们将无法分辨字符串的结尾在哪里，可能会继续在其他内存地址中进行读取

一般情况下，我们可以自行添加一个空终止符

//复制“你好”

char str2[6]；//字符串和“\0”的空间

strncpy（str2，“你好，世界！”，5）；//不复制'\0'！

str2[5]='\0'；//添加空终止字符

加一个小题

int main(int argc, char *argv[]) {
    char str[9];
     strcpy(str, "Hi earth");
    str[2] = '\0';
    printf("str = %s, len = %lu\n",�               str, strlen(str));
    return 0;
}

会输出什么？？？

不能使用+连接字符串 ，它实际上的是地址

要使用 strcat

特别注意的是 无论是strcat 还是strncat都会去掉旧的空终止符
添加上新的空终止符

举个课件上的例子

char str1[13];      // enough space for strings + '\0' 
strcpy(str1, "hello "); 
strcat(str1, "world!"); // removes old '\0', adds new '\0' at end
printf("%s", str1);     // hello world!

你还可以通过自己创建一个char* 指向字符串的某个地址 进而获得其子串

还是课件上的一个例子

char chars[8];
strcpy(chars, "racecar");
char *str1 = chars;
char *str2 = chars + 4;
printf("%s\n", str1);       // racecar
printf("%s\n", str2);       // car

另外 虽然我们对指针进行了移动
但还是指向相同的字符串

char chars[8];
strcpy(chars, "racecar");
char *str1 = chars;
char *str2 = chars + 4;
str2[0] = 'f';
printf("%s %s\n", chars, str1);       // racefar racefar
printf("%s\n", str2);               // far

我们可以通过char* 指向任何一个字符 ，并对其进行重新赋值，而char[]是不可以的

例子

char myString[6];
strcpy(myString, "Hello");
myString = "Another string";            // not allowed!

再加一个关于子串的例子

// Want just "race"
char str1[8];
strcpy(str1, "racecar");

char str2[5];
strncpy(str2, str1, 4);
str2[4] = '\0';
printf("%s\n", str1);       // racecar
printf("%s\n", str2);       // race

还可以通过指针运算来获得子串

// Want just "ace"
char str1[8];
strcpy(str1, "racecar");

char str2[4];
strncpy(str2, str1 + 1, 3);
str2[3] = '\0';
printf("%s\n", str1);       // racecar
printf("%s\n", str2);       // ace

OK 本课结束