ok
編程不過是把你所想轉(zhuǎn)為代碼，用堆棧的角度理解指針
第一章 數(shù)組
在C語言中一共有兩種聚合類型：數(shù)組（array）和結(jié)構(gòu)（structure）。本章介紹一維數(shù)組（1.1節(jié)）和多維數(shù)組（1.2節(jié)）的聲明與使用。1.3節(jié)討論了C99中的變長數(shù)組。本章主要討論一維數(shù)組，因為與多維數(shù)組相比，一維數(shù)組在C語言中占有更加重要的角色.
1.1聲明數(shù)組需要指明類型和數(shù)量
?//數(shù)組慣用法逆序輸出
?#include <stdio.h>
?#define N 10
?int main(){
? ? ?int n, a[N];
? ? ?for (int i = 0; i < n; i ++)
? ? ? ? ?scanf("%d", &a[i]);
? ? ?for (int i = N - 1; i >= n; i --)
? ? ? ? ?printf("%d", a[i]);
? ? ? printf("\n");
? ? ?return 0;
?}
下面這個程序用來檢查數(shù)中是否有出現(xiàn)多于一次的數(shù)字。用戶輸入數(shù)后，程序顯示信息Repeated digit或No Repeated digit：數(shù)28212有一個重復(fù)的數(shù)字（即2），而9357這樣的數(shù)則沒有。
?/*
? 程序采用布爾值的數(shù)組跟蹤數(shù)中出現(xiàn)的數(shù)字。名為digit_seen的數(shù)組元素的下標(biāo)索引從0到9，對應(yīng)于10個可能的數(shù)字。最初的時候，每個數(shù)組元素的值都為假。（digit_seen的初始化式為{false}，這實際上只初始化了數(shù)組的第一個元素。編譯器會自動把其他元素初始化為0，0跟false是相等的。）
? 當(dāng)給定數(shù)n時，程序一次一個地檢查n的數(shù)字，并且把每次的數(shù)字存儲在變量digit中，然后用這個數(shù)字作為數(shù)組digit_seen的下標(biāo)索引。如果digit_seen[digit]為真，那么表示digit至少在n中出現(xiàn)了兩次。另一方面，如果digit_seen[digit]為假，那么表示digit之前未出現(xiàn)過，因此程序會把digit_seen[digit]設(shè)置為真并且繼續(xù)執(zhí)行。
?*/
?#include <stdio.h>
?#include <stdbool.h>
?int main(){
? ? ?bool digitSeen[10] = {false};
? ? ?int digit;
? ? ?long n;
? ? ?printf("請輸入一個數(shù):");
? ? ?scanf("%ld", &n);
? ? ?while (n > 0){
? ? ? ? ?digit = n % 10;
? ? ? ? ?if (digitSeen[digit]) break;
? ? ? ? ?digitSeen[digit] = true;
? ? ? ? ?n / 10;
? ? ?}
? ? ?if (n > 0) ?printf("有重復(fù)數(shù)字");
? else printf("沒有重復(fù)數(shù)字");
?}
1.2多維數(shù)組與常量數(shù)組
數(shù)組可以有任意維數(shù)?？梢月暶鳟a(chǎn)生一個二維數(shù)組（或者按數(shù)學(xué)上的術(shù)語稱為矩陣）：
就像for循環(huán)和一維數(shù)組緊密結(jié)合一樣，嵌套的for循環(huán)是處理多維數(shù)組的理想選擇。例如，思考用作單位矩陣的數(shù)組的初始化問題。（數(shù)學(xué)中，單位矩陣在主對角線上的值為1，而其他地方的值為0，其中主對角線上行、列的索引值是完全相同的。）
?#define N 10
?double a[N][N];
?for (int i = 0; i < N; i ++)
? ? ?for (int j = 0; j < N; j ++)
? ? if (i == j) ?a[i][j] = 1.0;
? ?else ? ? ? ? a[i][j] = 0.0;
?
無論一維數(shù)組還是多維數(shù)組，都可以通過在聲明的最開始處加上單詞const而成為“常量”：程序不應(yīng)該對聲明為const的數(shù)組進(jìn)行修改，編譯器能夠檢測到直接修改某個元素的意圖。把數(shù)組聲明為const有兩個主要的好處。它表明程序不會改變數(shù)組，這對于以后閱讀程序的人可能是有價值的信息。它還有助于編譯器發(fā)現(xiàn)錯誤——const會告訴編譯器我們不打算修改數(shù)組。const類型限定符（?18.3節(jié)）不限于數(shù)組，后面將看到，它可以和任何變量一起使用。但是，const在數(shù)組聲明中特別有用，因為數(shù)組經(jīng)常含有一些在程序執(zhí)行過程中不會發(fā)生改變的參考信息。
?const char a[] = {
? 'a', 'b', 'c', 'd', 'e', 'f', 'g'
?};
下面這個程序說明了二維數(shù)組和常量數(shù)組的用法。程序負(fù)責(zé)發(fā)一副標(biāo)準(zhǔn)紙牌。每張標(biāo)準(zhǔn)紙牌都有一個花色（梅花、方塊、紅桃或黑桃）和一個等級（2、3、4、5、6、7、8、9、10、J、Q、K或A）。程序需要用戶指明手里應(yīng)該握有幾張牌：
Enter number of cards in hand: 5 Your hand: 7c 2s 5d as 2h
不能明顯地看出如何編寫這樣一個程序。如何從一副牌中隨機(jī)抽取紙牌呢？如何避免兩次抽到同一張牌呢？下面將分別處理這兩個問題。
為了隨機(jī)抽取紙牌，可以采用一些C語言的庫函數(shù)。time函數(shù)（?26.3節(jié)，來自于<time.h>）返回當(dāng)前的時間，用一個數(shù)表示。srand函數(shù)（?26.2節(jié)，來自于<stdlib.h>）初始化C語言的隨機(jī)數(shù)生成器。通過把time函數(shù)的返回值傳遞給函數(shù)srand可以避免程序在每次運(yùn)行時發(fā)同樣的牌。rand函數(shù)（?26.2節(jié)，來自于< stdlib.h>）在每次調(diào)用時會產(chǎn)生一個看似隨機(jī)的數(shù)。通過采用運(yùn)算符%，可以縮放rand函數(shù)的返回值，使其落在0~3（用于表示牌的花色）的范圍內(nèi)，或者是落在0~12（用于表示紙牌的等級）的范圍內(nèi)。
為了避免兩次都拿到同一張牌，需要記錄已經(jīng)選擇過的牌。為了這個目的，程序?qū)⒉捎靡粋€名為in_hand的二維數(shù)組，數(shù)組有4行（每行表示一種花色）和13列（每列表示一種等級）。換句話說，數(shù)組中的每個元素對應(yīng)著52張紙牌中的一張。在程序開始時，所有數(shù)組元素都為假。每次隨機(jī)抽取一張紙牌時，將檢查數(shù)組in_hand中的對應(yīng)元素為真還是為假。如果為真，那么就需要抽取其他紙牌；如果為假，則把true存儲到與這張紙牌相對應(yīng)的數(shù)組元素中，以提醒我們這張紙牌已經(jīng)抽取過了。
一旦證實紙牌是“新”的（還沒有選取過），就需要把牌的等級和花色數(shù)值翻譯成字符，然后顯示出來。為了把紙牌的等級和花色翻譯成字符格式，程序?qū)⒃O(shè)置兩個字符數(shù)組（一個用于紙牌的等級，另一個用于紙牌的花色），然后用等級和花色對數(shù)組取下標(biāo)。這兩個字符數(shù)組在程序執(zhí)行期間不會發(fā)生改變，所以也可以把它們聲明為const。
?#include <stdio.h>
?#include <stdbool.h>
?#include <time.h>
?#include <stdlib.h>
?
?#define NUM_SUIT 4
?#define NUM_RANKS 13
?
?int main(){
? ? ?bool inHand[NUM_SUIT][NUM_RANKS] = {false};
? ? ?int numCards, rank, suit;
? ? ?const char rankCode[] = {'2', '3', '4','5', '6', '7','8', '9',
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 't', 'j', 'q','k', 'a'};
? ? ?const char suitCode[] = {'c', 'd', 'h','s'};
? ? ?srand((unsigned)time(NULL));
? ? ?printf("輸入你手中卡牌的數(shù)量");
? ? ?scanf("%d", &numCards):
? ? ?printf("你手中的卡牌");
? ? ?while (numCards > 0){
? ?suit = rand() % NUM_SUIT;
? ? ? ? ?rand = rand() % NUM_RANKS;
? ? ? ? ?if (!inHand[suit][rank]){
? ? ? ? ? ? ?inHand[suit][rank] = true;
? ? ? ? ? ? ?numCards --;
? ? ? ? ? ? ?printf("%c%c", rankCode[rank], suitCode[suit]);
? ? ? ? ?}
? ? ?}
? ? ?printf("\n");
? ? ?return 0;
?}
第二章 函數(shù)
函數(shù)是C程序的構(gòu)建塊。每個函數(shù)本質(zhì)上是一個自帶聲明和語句的小程序?？梢岳煤瘮?shù)把程序劃分成小塊，這樣便于人們理解和修改程序,本章講解函數(shù)的調(diào)用聲明與定義，以及數(shù)組參數(shù)的傳遞和遞歸
下面這個程序判斷素數(shù)給定數(shù)n后，is_prime函數(shù)把n除以從2到n的平方根之間的每一個數(shù)；只要有一個余數(shù)為0，n就不是素數(shù)。
?#include <stdio.h>
?#include <stdbool.h>
?bool isPrime(int n){
? ? ?int divisor;
? ? ?if (n <= 1) return false;
? ? ?for (divisor = 2; divisor*divisor <= n; divisor ++){
? ? ? ? ?if (n % divisor == 0) return false;
? ? ?}
? ? ?return true;
?}
?int main(){
? ? ?int n;
? ? ?scanf("%d", &n);
? ? ?if (isPrime(n)) printf("是素數(shù)"):
? ? ?else ? ? ? ? ? ?printf("不是素數(shù)");
? ? ?return 0;
?}
遞歸
?#include <stdio.h>
?
?const int N = 1e6 + 10;
?int n;
?int q[N];
?
?void quick_sort(int q[], int, int);
?void swap(int*, int*);
? ? ?
?int main(){
? ? ?scanf("%d", &n);
? ? ?for (int i = 0; i < n; i ++) scanf("%d", &q[i]);
? ? ?quick_sort(q, 0, n - 1);
? ? ?for (int i = 0; i < n; i ++) printf("%d", q[i]);
?}
?void quick_sort(int q[], int l, int r)
?{
? ? ?if (l >= r) return;
? ? ?int i = l - 1, j = r + 1, x = q[l];
? ? ?while (i < j){
? ? ? ? ?do i ++ ; while (q[i] < x);
? ? ? ? ?do j -- ; while (q[j] > x);
? ? ? ? ?if (i < j) swap(q[i], q[j]);
? ? ?}
? ? ?quick_sort(q, l, j)
? ? ?quick_sort(q, j + 1, r);
?}
?void swap(int*a, int*b){
? ? ?int temp;
? ? ?temp = *a;
? ? ?*a = *b;
? ? ?*b = temp;
?}
第三章 指針，數(shù)組，字符串，指針的高級應(yīng)用
C語言允許使用賦值運(yùn)算符進(jìn)行指針的復(fù)制，前提是兩個指針具有相同的類型。
指針作為參數(shù)
?#include <stdio.h>
?#define N 10
?void max_min(int a[], int n, int*max, int*min);
?int main(){
? ? ?int b[N], big, small;
? ? ?for (int i = 0; i < n; i ++)
? ? ? ? ?scanf("%d", &a[i]);
? ? ?max_min(b, N, &big, &small);
? ? ?printf("%d", big);
? ? ?printf("%d", small);
? ? ?return 0;
?}
?
?void max_min(int a[], int n, int*max, int*min){
? ? ?*max = *min = a[0];
? ? ?for (int i = 0; i < n; i ++){
? ? ? ? ?if (a[i] > *max) *max = a[i];
? ? ? ? ?else if (a[i] < *min) *min = a[i];
? ? ?}
?}
指針作為返回值
?#include <stdio.h>
?int* max(int* a, int* b){
? ? ?if (*a > *b) return a;
? ? ?else ? ?return b;
?}
?int main(){
? ? ?int a, b;
? ? ?max(&a, &b);
?}
C程序員經(jīng)常在處理數(shù)組元素的語句中組合*（間接尋址）運(yùn)算符和++運(yùn)算符。思考一個簡單的例子：把值存入一個數(shù)組元素中，然后前進(jìn)到下一個元素。利用數(shù)組下標(biāo)可以這樣寫：
?a[i++] = j;
如果p指向數(shù)組元素，那么相應(yīng)的語句將會是
?*p++ = j;
通常情況下，a + i等同于&a[i]（兩者都表示指向數(shù)組a中元素i的指針），并且*(a+i)等價于a[i]（兩者都表示元素i本身）。換句話說，可以把數(shù)組的取下標(biāo)操作看成是指針?biāo)阈g(shù)運(yùn)算的一種形式。
?//慣用法
?#include <stdio.h>
?#define N 10
?int main(){
? ? ?int a[N], *p, sum = 0;
? ?printf("輸入%d個數(shù)", N);
? ? ?//a == &a[0]數(shù)組的第一個元素
? ? ?for (p = a; p < a + N; p ++)
? ? ? ? ? sum += *p;
? ? ? ? ? scanf("%d", &N);
? ? ?for (p = N - 1; p >= a; p --)
? ? ? ? ? printf("%d", *p);
? ? ? ?printf("\n");
? ? ?return 0;
?}
用指針作為數(shù)組名
?#define N 10
?int a[N], sum = 0, *p = a;
?for (int i = 0; i < N; i++)
? ? ?sum += p[i];
?//編譯器把p[i]看作*(p+i)
?
字符串字面量是作為數(shù)組來存儲的，那么編譯器會把它看作是char *類型的指針，也是指向第一個元素的地址printf函數(shù)和scanf函數(shù)都接收char *類型的值作為它們的第一個參數(shù)。
只要保證字符串是以空字符結(jié)尾的，任何一維的字符數(shù)組都可以用來存儲字符串。這種方法很簡單，但使用起來有很大難度。有時很難辨別是否把字符數(shù)組作為字符串來使用。如果編寫自己的字符串處理函數(shù)，請千萬注意要正確地處理空字符。而且，要確定字符串長度沒有比逐個字符地搜索空字符更快捷的方法了。
假設(shè)需要用一個變量來存儲最多有80個字符的字符串。由于字符串在末尾處需要有空字符，我們把變量聲明為含有81個字符的數(shù)組：
字符串的長度取決于空字符的位置，而不是取決于用于存放字符串的字符數(shù)組的長度
字符串變量的聲明中可以省略它的長度。這種情況下，編譯器會自動計算長度：
?#define STR_LEN 11
?char str[STR_LEN + 1];
?
?char str2[] = "hello world";
字符數(shù)組與字符指針
?char s1[] = "hello world";
?char* s2 = "hello world";
在聲明為數(shù)組時，就像任意數(shù)組元素一樣，可以修改存儲在date中的字符。在聲明為指針時，date指向字符串字面量，在13.1節(jié)我們已經(jīng)看到字符串字面量是不可以修改的?！ぴ诼暶鳛閿?shù)組時，date是數(shù)組名。在聲明為指針時，date是變量，這個變量可以在程序執(zhí)行期間指向其他字符串。如果希望可以修改字符串，那么就要建立字符數(shù)組來存儲字符串，聲明指針變量就不夠的
在使用p作為字符串之前，必須把p指向字符數(shù)組。一種可能是把p指向已經(jīng)存在的字符串變量：現(xiàn)在p指向了str的第一個字符，所以可以把p作為字符串使用了。另一種可能是讓p指向一個動態(tài)分配的字符串（?17.2節(jié)）。
?char str[STR_LEN + 1], *p;
?p = str;
字符串的讀和寫
使用printf函數(shù)或puts函數(shù)來寫字符串是很容易的。讀字符串卻有點(diǎn)麻煩，主要是因為輸入的字符串可能比用來存儲它的字符串變量長。為了一次性讀入字符串，可以使用scanf函數(shù)或gets函數(shù)，也可以每次讀入一個字符。
用printf函數(shù)和puts函數(shù)寫字符串
?/*
? printf函數(shù)會逐個寫字符串中的字符，直到遇到空字符才停止。（如果空字符丟失，printf函數(shù)會越過字符串 ? ? 的末尾繼續(xù)寫，直到最終在內(nèi)存的某個地方找到空字符為止。）.
? puts函數(shù)總會添加一個額外的換行符，從而前進(jìn)到下一個輸出行的開始處。
?*/
?#include <stdio.h>
?char str[] = "nothing to say";
?
?printf("%s\n", str);
?puts(str);
用scanf函數(shù)和gets函數(shù)讀字符串
gets函數(shù)把讀入的字符放到數(shù)組中，然后存儲一個空字符。然而，在其他方面gets函數(shù)有些不同于scanf函數(shù)。·gets函數(shù)不會在開始讀字符串之前跳過空白字符（scanf函數(shù)會跳過）。gets函數(shù)會持續(xù)讀入直到找到換行符才停止（scanf函數(shù)會在任意空白字符處停止）。此外，gets函數(shù)會忽略掉換行符，不會把它存儲到數(shù)組中，用空字符代替換行符。在把字符讀入數(shù)組時，scanf函數(shù)和gets函數(shù)都無法檢測數(shù)組何時被填滿。因此，它們存儲字符時可能越過數(shù)組的邊界，這會導(dǎo)致未定義的行為。通過用轉(zhuǎn)換說明[插圖]s代替%s可以使scanf函數(shù)更安全。這里的數(shù)字[插圖]指出可以存儲的最多字符數(shù)?？上У氖?，gets函數(shù)天生就是不安全的，fgets函數(shù)（?22.5節(jié)）則是一種好得多的選擇。
逐個字符讀字符串
因為對許多程序而言，scanf函數(shù)和gets函數(shù)都有風(fēng)險且不夠靈活，C程序員經(jīng)常會自己編寫輸入函數(shù)。通過每次一個字符的方式來讀入字符串，這類函數(shù)可以提供比標(biāo)準(zhǔn)輸入函數(shù)更大程度的控制。如果決定設(shè)計自己的輸入函數(shù)，那么就需要考慮下面這些問題?！ぴ陂_始存儲字符串之前，函數(shù)應(yīng)該跳過空白字符嗎？·什么字符會導(dǎo)致函數(shù)停止讀取：換行符、任意空白字符還是其他某種字符？需要存儲這類字符還是忽略掉？·如果輸入的字符串太長以致無法存儲，那么函數(shù)應(yīng)該做些什么：忽略額外的字符還是把它們留給下一次輸入操作？
假定我們所需要的函數(shù)不會跳過空白字符，在第一個換行符（不存儲到字符串中）處停止讀取，并且忽略額外的字符。函數(shù)將有如下原型：
?int readLine(char str[], int n);
read_line函數(shù)主要由一個循環(huán)構(gòu)成。只要str中還有空間，此循環(huán)就會調(diào)用getchar函數(shù)（?7.3節(jié)）逐個讀入字符并把它們存儲到str中。在讀入換行符時循環(huán)終止注意，ch的類型為int而不是char，這是因為getchar把它讀取的字符作為int類型的值返回,
返回之前，read_line函數(shù)在字符串的末尾放置一個空字符。scanf和gets等標(biāo)準(zhǔn)函數(shù)會自動在輸入字符串的末尾放置一個空字符；然而，如果要自己寫輸入函數(shù)，必須手工加上空字符。
?int readLine(char str[], int n){
? int ch, i;
? ? ?while (ch = getchar() != '\n')
? ? ? ? ?if (i < n)
? ? ? ? ? ? ?str[i++] = ch;
? ? ?str[i] = '\0';
? ? ?return i;
?}
訪問字符串中的字符
字符串是以數(shù)組的方式存儲的，因此可以使用下標(biāo)來訪問字符串中的字符。例如，為了對字符串s中的每個字符進(jìn)行處理，可以設(shè)定一個循環(huán)來對計數(shù)器i進(jìn)行自增操作，并通過表達(dá)式s[i]來選擇字符。假定需要一個函數(shù)來統(tǒng)計字符串中空格的數(shù)量。利用數(shù)組取下標(biāo)操作可以寫出如下函數(shù)：
在s的聲明中加上const表明count_spaces函數(shù)不會改變數(shù)組。如果s不是字符串，count_spaces將需要第2個參數(shù)來指明數(shù)組的長度。然而，因為s是字符串，所以count_spaces可以通過測試空字符來定位s的末尾。許多C程序員不會像例子中那樣編寫count_spaces函數(shù)，他們更愿意使用指針來跟蹤字符串中的當(dāng)前位置。就像在12.2節(jié)中見到的那樣，這種方法對于處理數(shù)組來說一直有效，但在處理字符串方面尤其方便。下面用指針?biāo)阈g(shù)運(yùn)算代替數(shù)組取下標(biāo)來重新編寫count_spaces函數(shù)。這次不再需要變量i，而是利用s自身來跟蹤字符串中的位置。通過對s反復(fù)進(jìn)行自增操作，count_spaces函數(shù)可以逐個訪問字符串中的字符。下面是count_spaces函數(shù)的新版本：
注意，const沒有阻止count_spaces函數(shù)對s的修改，它的作用是阻止函數(shù)改變s所指向的字符。而且，因為s是傳遞給count_spaces函數(shù)的指針的副本，所以對s進(jìn)行自增操作不會影響原始的指針。
?int count_spaces(const char *s)
?{
? ?int count = 0;
? ?for (; *s != '\0'; s++)
? ? ?if (*s == ' ')
? ? ? ?count++;
? ?return count;
?}
使用C語言的字符串庫
字符串慣用法
字符串?dāng)?shù)組（二維）
現(xiàn)在來看一個在使用字符串時經(jīng)常遇到的問題：存儲字符串?dāng)?shù)組的最佳方式是什么？最明顯的解決方案是創(chuàng)建二維的字符數(shù)組，然后按照每行一個字符串的方式把字符串存儲到數(shù)組中?？紤]下面的例子：
算法（解決問題的步驟）練習(xí)題
問題步驟寫清楚，搞清楚每個變量數(shù)據(jù)結(jié)構(gòu)的含義，解決實際問題
鏈接語語法
樹就是特殊的圖，算法（思想）相似
經(jīng)典算法《算法第四版》
