CS107筆記

概述 ： CS10是斯坦福一門(mén)計(jì)算機(jī)課程，網(wǎng)上有對(duì)應(yīng)的課程鏈接 CS107 此為本人自學(xué)此課程的總結(jié) 當(dāng)然大部分都是課件里面有的，拿出來(lái)分享一下，共同學(xué)習(xí) 下面進(jìn)入正題

Lecture 1（第一節(jié)課 后面省略）

本節(jié)課程計(jì)劃

• CS107課程政策
• Unix和命令行
• C入門(mén)

CS107課程政策

什么是CS107

1. C++和java語(yǔ)言背后是如何表示數(shù)據(jù)的
2. 編程結(jié)構(gòu)如何以位和字節(jié)編碼
3. 如何有效的操作和管理內(nèi)存
4. 使用C語(yǔ)言
5. 編程風(fēng)格與軟件開(kāi)發(fā)實(shí)踐

學(xué)習(xí)目標(biāo)

CS107的目標(biāo)是讓學(xué)生掌握

1. 用復(fù)雜的內(nèi)存和指針編寫(xiě)C程序
2. C程序地址空間和編譯/運(yùn)行行為的精確模型

取得能力

1. 將C轉(zhuǎn)換為/從程序集轉(zhuǎn)換
2. 編寫(xiě)尊重計(jì)算機(jī)算法局限性的程序
3. 識(shí)別瓶頸并提高運(yùn)行時(shí)性能
4. 在Unix開(kāi)發(fā)環(huán)境中有效地工作

接觸到

• 對(duì)計(jì)算機(jī)體系結(jié)構(gòu)基礎(chǔ)的有效理解

課程概述

1. 位和字節(jié)-計(jì)算機(jī)如何表示整數(shù)？
2. 字符和C字符串-計(jì)算機(jī)如何表示和操作更復(fù)雜的數(shù)據(jù)，如文本？
3. 指針、堆棧和堆——如何有效地管理程序中的所有類(lèi)型的內(nèi)存？
4. 泛型-我們?nèi)绾问褂梦覀兊膬?nèi)存和數(shù)據(jù)表示的知識(shí)來(lái)編寫(xiě)可以處理任何數(shù)據(jù)類(lèi)型的代碼？
5. 匯編——計(jì)算機(jī)如何解釋和執(zhí)行C程序？
6. 堆分配器-像malloc和free這樣的核心內(nèi)存分配操作是如何工作的？

另外，它推薦了一本書(shū)

《計(jì)算機(jī)系統(tǒng)：程序員的視角》，Bryant&O'Hallaron著，第3版

其他的都是有關(guān)作業(yè)什么的方案 ，我們無(wú)法按照他的方案進(jìn)行，也無(wú)法獲取他們的作業(yè)，省略

Unix和命令行

什么是Unix

1. Unix：軟件開(kāi)發(fā)中常用的一組標(biāo)準(zhǔn)和工具。

2. macOS和Linux是建立在Unix之上的操作系統(tǒng)

3. 您可以使用命令行（“終端”）導(dǎo)航Unix系統(tǒng)

4. 每個(gè)Unix系統(tǒng)使用相同的工具和命令工作

什么是命令行

命令行是一個(gè)基于文本的界面（即終端界面）來(lái)導(dǎo)航計(jì)算機(jī)，而不是圖形用戶(hù)界面（GUI）。

簡(jiǎn)單的說(shuō)開(kāi)始我們常說(shuō)的黑框框

插一句 因?yàn)槲液ε陆o遺漏掉什么東西，所以會(huì)比較長(zhǎng)甚至啰嗦。大家碰到自己已經(jīng)了解或明白的地方自行跳過(guò) 感謝

命令行進(jìn)而圖形化用戶(hù)界面的區(qū)別

就像GUI文件瀏覽器界面一樣，終端界面

• 在任何時(shí)間顯示計(jì)算機(jī)上的特定位置

• 允許您進(jìn)入文件夾和退出文件夾

• 允許您創(chuàng)建新文件和編輯文件

• 允許您執(zhí)行程序

為什么使用Unix

您可以使用相同的工具和命令導(dǎo)航幾乎任何設(shè)備：

服務(wù)器

筆記本電腦和臺(tái)式機(jī)

嵌入式設(shè)備（樹(shù)莓皮等）

移動(dòng)設(shè)備（Android等）

軟件工程師經(jīng)常使用：

Web開(kāi)發(fā)：在服務(wù)器上運(yùn)行服務(wù)器和Web工具

機(jī)器學(xué)習(xí)：在服務(wù)器上處理數(shù)據(jù)，運(yùn)行算法

系統(tǒng)：編寫(xiě)操作系統(tǒng)、網(wǎng)絡(luò)代碼和嵌入式軟件

移動(dòng)開(kāi)發(fā)：運(yùn)行工具、管理庫(kù)

還有更多…

我們將使用Unix和命令行來(lái)實(shí)現(xiàn)和執(zhí)行我們的程序

上面是課件對(duì)此的描述 說(shuō)白了就是應(yīng)用范圍廣

介紹幾個(gè)常用的命令

cd–更改目錄（…）

ls–列出目錄內(nèi)容

mkdir–生成目錄

emacs–打開(kāi)文本編輯器

rm–刪除文件或文件夾
man- 查看手冊(cè)

這里多少幾句
cd 可以理解為進(jìn)入目錄
cd + 目錄名
cd ../ 進(jìn)入上一級(jí)目錄

ls 就是顯示當(dāng)前目錄下的文件當(dāng)然包括目錄
ls -a 顯示所有文件 包括隱藏文件

mkdir +目錄名 （結(jié)對(duì)路徑或相對(duì)路徑）
emacs 需要你下載對(duì)應(yīng)軟件 更具體的自行搜索

rm +文件名 刪除文件
rm -r +文件夾名 刪除目錄及目錄下的所有文件

man 后面要節(jié)參數(shù) 例如 man -a 等等，太多了自行搜索即可

命令還有很多 就不多說(shuō)了 網(wǎng)上都可以找得到

C入門(mén)

略過(guò) 這部分內(nèi)容主要說(shuō)

1. C的產(chǎn)生 發(fā)展
2. C和C++的比較
3. C的優(yōu)勢(shì)
4. Hello world 程序

這里就不說(shuō)了 可以去課件了解一下
Lecture 1課件
提取密碼 8rdo
鏈接失效記得提醒我

Lecture 2

本節(jié)課程計(jì)劃

1. 比特與字節(jié)
2. 十六進(jìn)制
3. 整數(shù)表示法
4. 無(wú)符號(hào)整數(shù)
5. 有符號(hào)整數(shù)
6. 溢流
7. 轉(zhuǎn)換類(lèi)型和合并類(lèi)型

比特和字節(jié)

1. 了解十進(jìn)制和二進(jìn)制
2. 計(jì)算機(jī)是以0 1 為單位的，計(jì)算機(jī)上所有的數(shù)據(jù)，文件都是二進(jìn)制表示的 一個(gè)二進(jìn)制為為一個(gè)比特位 。一個(gè)字節(jié)=八個(gè)比特位
3. 熟練進(jìn)行十進(jìn)制和二進(jìn)制之間的轉(zhuǎn)換（轉(zhuǎn)換方法不止一種，看自己）
4. 了解基數(shù)的概念 二進(jìn)制的基數(shù)是2，十進(jìn)制的基數(shù)是10
5. 一個(gè)字節(jié)所能表示的數(shù) 最大為 255 最小為0
6. 乘以基數(shù)和除以基數(shù)的運(yùn)算

十六進(jìn)制

1. 我們?cè)谔幚?2位，64位的數(shù)據(jù)是 為了方便要用到，當(dāng)然好多地方
2. 了解十六進(jìn)制的基數(shù)是16 以及各數(shù)對(duì)應(yīng)的數(shù)字或字母
3. 十進(jìn)制 二進(jìn)制 十六進(jìn)制中 對(duì)于0-15 之間的對(duì)應(yīng)關(guān)系
4. 對(duì)于各進(jìn)制的數(shù)我們?yōu)榱吮阌趨^(qū)分 二進(jìn)制前有0b 十進(jìn)制省略 十六進(jìn)制用0x
5. 熟練進(jìn)行十六進(jìn)制和二進(jìn)制和十進(jìn)制之間的轉(zhuǎn)換

整數(shù)表示法

整數(shù)有分有符號(hào)和無(wú)符號(hào)以及浮點(diǎn)數(shù)
本節(jié)先了解一下計(jì)算機(jī)上的32位和64位，以及在這兩種環(huán)境下各類(lèi)型的數(shù)據(jù)分別占多少空間

32位

64位

至于為什么，我把原文的翻譯放在這里

21世紀(jì)初：大多數(shù)計(jì)算機(jī)是32位的。這意味著指針是4個(gè)字節(jié)（32位）。
32位指針存儲(chǔ)從0到232-1的內(nèi)存地址，相當(dāng)于232字節(jié)的可尋址內(nèi)存。這相當(dāng)于4GB，這意味著32位計(jì)算機(jī)最多可以有4GB內(nèi)存（RAM）！
正因?yàn)槿绱?，?jì)算機(jī)轉(zhuǎn)換到64位。這意味著數(shù)據(jù)類(lèi)型被放大了；程序中的指針現(xiàn)在是64位。
64位指針存儲(chǔ)從0到264-1的內(nèi)存地址，相當(dāng)于264字節(jié)的可尋址內(nèi)存。這相當(dāng)于16EB，這意味著64位計(jì)算機(jī)最多可以有102410241024GB的內(nèi)存（RAM）！

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

無(wú)符號(hào)整數(shù)

0或正整數(shù)
范圍 0--2的n次方減一 （n為二進(jìn)制位數(shù)，即位的數(shù)目）

無(wú)符號(hào)整形的表示是呈圈形的
以四位二進(jìn)制表示為例
1111：15 此數(shù)加一為0

圖片的話更形象 課件里面有

有符號(hào)整數(shù)

簡(jiǎn)單點(diǎn)一個(gè)公式
一個(gè)整數(shù)的負(fù)數(shù)表示=其正整數(shù)的二進(jìn)制表示取反加一

例如1：0001
-1 ： 1111

附一句 以四位二進(jìn)制為例
其表示范圍(有符號(hào)整型)-8~7
理解為 -(2的(4-1)次方)--2的(4-1)次方-1
前面的4換成n 就是n位二進(jìn)制所能表示的有符號(hào)整數(shù)范圍

總結(jié) 有符號(hào)整數(shù) 表示
正： 直接轉(zhuǎn)換就好 （原碼）
負(fù)： 補(bǔ)碼（對(duì)應(yīng)正數(shù)的二進(jìn)制表示反碼加一）
0 全是0

這樣利于進(jìn)行加減運(yùn)算 具體的演示 見(jiàn)課件

溢出

溢出則“繞圈” 按照課件上圖示的那樣 ，這里就不上圖了
例如 四位二進(jìn)制有符號(hào)整數(shù)
圈為 0₇（-8）_（-1）0；
端點(diǎn)處的0連接起來(lái) 即為圈
其他的數(shù)據(jù)類(lèi)型 例如 char
其對(duì)應(yīng)的ASC碼也遵循此規(guī)則 只不過(guò) 顯示的時(shí)候是其對(duì)應(yīng)的字符表示

對(duì)于溢出現(xiàn)象 課件有更為詳細(xì)的介紹以及案例，有時(shí)間的可以去了解一下

轉(zhuǎn)換類(lèi)型和合并類(lèi)型

占位符

%d 有符號(hào)32位int
%u 無(wú)符號(hào)32位int
%x 16進(jìn)制表示的32位int

用于在printf中表示要輸出的類(lèi)型
這種占位符 還有很多種
自行搜索 因?yàn)檫@屬于C語(yǔ)言的內(nèi)容

提一個(gè)問(wèn)題

int v = -12345;

unsigned int uv = v;

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

輸出: "v = -12345, uv = 4294954951".
這是為什么呢

另外補(bǔ)充一點(diǎn)
在進(jìn)行 無(wú)符號(hào)整型和有符號(hào)整型的大小比較時(shí)
C講兩數(shù)均轉(zhuǎn)換為無(wú)符號(hào)整形進(jìn)行比較

類(lèi)型轉(zhuǎn)換

有時(shí) 我們會(huì)對(duì)兩個(gè)不同類(lèi)型的數(shù)進(jìn)行比較
此時(shí)，系統(tǒng)會(huì)將兩數(shù)均轉(zhuǎn)換為較大的類(lèi)型 進(jìn)而進(jìn)行比較

這里說(shuō)一下 我們不能將較大的數(shù)據(jù)類(lèi)型轉(zhuǎn)換為小的類(lèi)型 ，但反之是可行的

那么 轉(zhuǎn)換是怎樣進(jìn)行的呢

無(wú)符號(hào) 前面補(bǔ)0
有符號(hào) 前面補(bǔ)符號(hào)位

有時(shí)候我們也會(huì)將大類(lèi)型轉(zhuǎn)化為小類(lèi)型

此時(shí)會(huì)將數(shù)據(jù)的長(zhǎng)度進(jìn)行折斷
忽視高位（左邊）

這段內(nèi)容課件上有配套練習(xí)題 建議去看一下

sizeof 運(yùn)算符

該運(yùn)算符接受一個(gè)變量類(lèi)型，并返回其大小 單位為字節(jié)

//示例

long int_size_bytes=sizeof（int）；//4

long short_size_bytes=sizeof（short）；//2

long char_size_bytes=sizeof（char）；//1

lecyture 3

此節(jié)主要是位運(yùn)算的介紹
補(bǔ)充一句 計(jì)算機(jī)中所有數(shù)據(jù)等 全是用01表示

先介紹一下ASC碼

ASCII是從普通字符（字母、符號(hào)等）到位表示（字符）的編碼

所有大寫(xiě)字母和所有小寫(xiě)字母都按順序表示！

更具體的自行百度

位運(yùn)算符

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

介紹

1. & 同時(shí)為1 結(jié)果為1
2. | 只要有一個(gè)為1 結(jié)果就是1
3. ~ 原來(lái)是1變?yōu)? 原來(lái)是0變?yōu)? （取反）
4. ^ 二者不同（一0一1） 結(jié)果為1 否則為0

-- 學(xué)過(guò)離散數(shù)學(xué)會(huì)更好

應(yīng)用 見(jiàn)課件

比如

如何分離某位

如何修改指定為

如何求位的交集 并集

如何翻轉(zhuǎn) 指定位或所有位

左移運(yùn)算符

所謂左移運(yùn)算符： <<
就是將該數(shù)在內(nèi)存中的二進(jìn)制表示向左移動(dòng)

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

例如 00110111 << 2 返回 11011100
左移簡(jiǎn)單點(diǎn) ，重點(diǎn)是右移

右移運(yùn)算符

移動(dòng)很簡(jiǎn)單 但是用什么來(lái)填充移掉的位置呢
用0 ？？

0是不行的

x=-2；//1111 1111 1111 1110

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

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

OK 我們現(xiàn)在看解決方案

我們用符號(hào)位進(jìn)行填充

例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!

這樣就不會(huì)找成符號(hào)錯(cuò)亂等問(wèn)題

總而言之

右移 有兩種

1. 邏輯右移 用0 補(bǔ)充
2. 算術(shù)右移 用符號(hào)位（高階有效位）補(bǔ)充

一般使用場(chǎng)景

無(wú)符號(hào)數(shù)字使用邏輯右移進(jìn)行右移。

有符號(hào)數(shù)字使用算術(shù)右移進(jìn)行右移。

補(bǔ)充

從技術(shù)上講，C標(biāo)準(zhǔn)并沒(méi)有精確地定義有符號(hào)整數(shù)的右移是邏輯的還是算術(shù)的。

但是 幾乎所有的編譯器/機(jī)器都使用算術(shù)，

還有一點(diǎn) 1<<2+3<<4
例如上面的這種運(yùn)算

要注意??！
加法和減法的優(yōu)先級(jí)高于移位！

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

其余注意點(diǎn)

如果你想要一個(gè)二進(jìn)制位前32位全為1的長(zhǎng)整型

long num = 1 << 32;

這樣是不對(duì)的

默認(rèn)情況下，1是一個(gè)int，并且不能將int移位32，因?yàn)樗挥?2位。必須指定希望1為long。

所以要用

long num==1L<<32;

OK 本課結(jié)束

Lecture 4? C Strings

顯而易見(jiàn) 本節(jié)主要結(jié)束字符串

問(wèn)題 計(jì)算機(jī)如何表示復(fù)雜數(shù)據(jù) 例如 文本

先看大綱

字符

串

常用字符串操作

比較

復(fù)制

串聯(lián)

子字符串

字符 （char）

C語(yǔ)言將每個(gè)字符表示為一個(gè)整數(shù) 起名為ASCII值

ASCII的一般規(guī)則

大寫(xiě)字母按順序編號(hào)

小寫(xiě)字母按順序編號(hào)

數(shù)字按順序編號(hào)

小寫(xiě)字母比大寫(xiě)字母多32個(gè)

舉幾個(gè)例子

char uppercaseA='A'；//實(shí)際上是65

char lowercaseA='a'；//實(shí)際上是97

char zeroDigit='0'；//實(shí)際為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;

通用函數(shù)

注意

這些方法至是返回一個(gè)字符 不會(huì)修改現(xiàn)有字符

示例

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

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

char uppercaseB = toupper('b');

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

字符串

C語(yǔ)言中沒(méi)有字符串的變量類(lèi)型，他是由有特殊符號(hào)的字符數(shù)組來(lái)表示的 '\0'

在數(shù)組中始終要有它的位置

C語(yǔ)言提供了計(jì)算字符串長(zhǎng)度的函數(shù)

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

如果要用這個(gè)值要記得保存

當(dāng)字符串作為參數(shù)傳入函數(shù)中時(shí) ， C傳遞的是字符串的首地址

對(duì)于傳遞過(guò)去的首地址 我們可以像使用字符數(shù)組一樣使用它

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

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

常用的string.h函數(shù)

很多字符串函數(shù)都假定你給的字符串是符合規(guī)范的（有終止符）

不能用<,>，== 等這些符號(hào)對(duì)字符串進(jìn)行比較 ，這樣比較，其實(shí)比較的是地址

不能 用等號(hào)來(lái)進(jìn)行字符串的拷貝 這樣拷貝的是地址

關(guān)于字符串的拷貝這里提供一個(gè)例子

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

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

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

同時(shí)在進(jìn)行字符串拷貝的時(shí)候，我們必須確保目標(biāo)地址有足夠的空間

例如

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

strcpy（strpy，“你好，世界！”）；//覆蓋其他內(nèi)存！

寫(xiě)入超過(guò)內(nèi)存邊界稱(chēng)為“緩沖區(qū)溢出”。它可以允許安全漏洞！

還有規(guī)定數(shù)量的拷貝

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

當(dāng)我們的字符串沒(méi)有空終止符時(shí)，我們將無(wú)法分辨字符串的結(jié)尾在哪里，可能會(huì)繼續(xù)在其他內(nèi)存地址中進(jìn)行讀取

一般情況下，我們可以自行添加一個(gè)空終止符

//復(fù)制“你好”

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

strncpy（str2，“你好，世界！”，5）；//不復(fù)制'\0'！

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

加一個(gè)小題

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;
}

會(huì)輸出什么？？？

不能使用+連接字符串 ，它實(shí)際上的是地址

要使用 strcat

特別注意的是 無(wú)論是strcat 還是strncat都會(huì)去掉舊的空終止符
添加上新的空終止符

舉個(gè)課件上的例子

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!

你還可以通過(guò)自己創(chuàng)建一個(gè)char* 指向字符串的某個(gè)地址 進(jìn)而獲得其子串

還是課件上的一個(gè)例子

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

另外 雖然我們對(duì)指針進(jìn)行了移動(dòng)
但還是指向相同的字符串

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

我們可以通過(guò)char* 指向任何一個(gè)字符 ，并對(duì)其進(jìn)行重新賦值，而char[]是不可以的

例子

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

再加一個(gè)關(guān)于子串的例子

// 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

還可以通過(guò)指針運(yùn)算來(lái)獲得子串

// 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 本課結(jié)束