簡介面向C語言學(xué)習(xí)者的數(shù)據(jù)結(jié)構(gòu)與算法完整資料包覆蓋圖與樹存儲(chǔ)結(jié)構(gòu)、查找表、線性表、字符串、數(shù)組與廣義表、棧與隊(duì)列、排序算法等核心模塊包含冒泡、選擇、插入、快速等內(nèi)部排序及外部排序?qū)崿F(xiàn)既有基礎(chǔ)概念講解也提供各算法在C語言中的具體代碼與運(yùn)行驗(yàn)證方式適合初學(xué)者系統(tǒng)入門亦有助于進(jìn)階者鞏固編程思維。壓縮包共558個(gè)文件以c源碼、dev工程、exe可執(zhí)行程序、out輸出、layout界面等類型為主配套readme說明文檔整體約12.92MB目錄結(jié)構(gòu)清晰便于按主題查閱。已有1977人學(xué)習(xí)使用這份資料能幫助讀者理解鄰接矩陣、二叉樹、順序查找、二分查找等關(guān)鍵知識(shí)點(diǎn)也可作為課程設(shè)計(jì)或期末復(fù)習(xí)的實(shí)用參考。1. C語言數(shù)據(jù)結(jié)構(gòu)與算法先別急著刷題把結(jié)構(gòu)和算法在內(nèi)存里跑起來很多人一提到“C語言數(shù)據(jù)結(jié)構(gòu)與算法”第一反應(yīng)是嚴(yán)蔚敏那本綠皮書或者是王道408的復(fù)習(xí)題。但現(xiàn)實(shí)場(chǎng)景是你用Python寫一個(gè)鏈表幾分鐘搞定換成C語言卻卡在“二級(jí)指針到底要不要用”“free之后指針為什么還在”這些細(xì)節(jié)上。C語言的數(shù)據(jù)結(jié)構(gòu)與算法本質(zhì)上不是教你背概念而是逼你回答一個(gè)問題——這段數(shù)據(jù)究竟在內(nèi)存里怎么放、怎么訪問、怎么釋放。理解了這一點(diǎn)不管是考研408、筆試手撕代碼還是嵌入式開發(fā)里需要自己維護(hù)緩沖區(qū)和鏈表都不會(huì)再覺得數(shù)據(jù)結(jié)構(gòu)是“黑匣子”。這篇文章面向的讀者是學(xué)過C語言基礎(chǔ)但數(shù)據(jù)結(jié)構(gòu)一直停留在“看得懂、寫不出”階段的從業(yè)者和學(xué)生。我會(huì)按“理論先立住代碼能復(fù)現(xiàn)坑提前踩掉”的順序把線性表、樹、圖、排序、字符串匹配這些經(jīng)典內(nèi)容用C語言逐一落地并給出一套可以直接復(fù)用的練習(xí)環(huán)境。目標(biāo)只有一個(gè)讓數(shù)據(jù)結(jié)構(gòu)不再是“玄學(xué)”而是你手底下能跑、能調(diào)、能驗(yàn)證的代碼。2. 從嚴(yán)蔚敏到王道408C語言數(shù)據(jù)結(jié)構(gòu)到底在學(xué)什么理論怎么落到代碼2.1 數(shù)據(jù)結(jié)構(gòu)五大件線性表、樹、圖、查找、排序的掌握邊界數(shù)據(jù)結(jié)構(gòu)這門課說到底是圍繞“數(shù)據(jù)怎么組織、怎么操作”展開的。用C語言學(xué)習(xí)時(shí)我習(xí)慣把內(nèi)容拆成五大塊每一塊都有明確的“C語言落地標(biāo)準(zhǔn)”。線性表是基礎(chǔ)包含順序表和鏈表。順序表就是動(dòng)態(tài)數(shù)組要掌握擴(kuò)容策略鏈表要掌握單鏈表、雙鏈表和循環(huán)鏈表。判斷標(biāo)準(zhǔn)能在紙上畫出插入、刪除時(shí)指針的指向變化然后用C語言寫出來并且不出現(xiàn)內(nèi)存泄漏。樹這一塊重點(diǎn)是二叉樹。掌握前中后序遍歷、層序遍歷、二叉搜索樹、堆。對(duì)于C語言來說還要能寫出用遞歸和棧兩種方式實(shí)現(xiàn)遍歷——后者才是面試常考的點(diǎn)。圖的部分相對(duì)抽象重點(diǎn)掌握鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)以及深度優(yōu)先搜索DFS和廣度優(yōu)先搜索BFS的代碼實(shí)現(xiàn)。查找和排序是重頭戲從順序查找、二分查找到哈希表從冒泡排序、插入排序到歸并排序、堆排序、快速排序每一類都要能手寫并且說清楚時(shí)間復(fù)雜度和穩(wěn)定性。至于王道408里要求的“掌握程度”我的經(jīng)驗(yàn)是概念題考的是你能否用一句話說清“什么是?！敝獾纳顚永斫獗热纭盀槭裁碊FS用棧而BFS用隊(duì)列”。代碼題考的是你在白板上寫出的C語言能否直接運(yùn)行。所以不要只背定義把嚴(yán)蔚敏教材里的每一個(gè)ADT抽象數(shù)據(jù)類型用C語言實(shí)現(xiàn)一遍比看十遍“知識(shí)點(diǎn)歸納”都有用。2.2 為什么用C語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)三個(gè)理由和“偽代碼害死人”的真相很多教程喜歡用偽代碼糊弄比如“將p節(jié)點(diǎn)插入鏈表”?？雌饋砗芎枚粍?dòng)手寫C語言就崩。原因在于C語言沒有自動(dòng)垃圾回收你必須自己管理節(jié)點(diǎn)的創(chuàng)建和釋放。用C語言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的第一個(gè)理由就是它能暴露“內(nèi)存生命周期”這個(gè)關(guān)鍵問題——節(jié)點(diǎn)是malloc出來的什么時(shí)候freefree之后指針值不變但指向的內(nèi)存已無效這就是use-after-free的直接來源。第二個(gè)理由是C語言的結(jié)構(gòu)體和指針能讓你一眼看清數(shù)據(jù)對(duì)象在內(nèi)存里的布局。結(jié)構(gòu)體成員有偏移量數(shù)組是連續(xù)內(nèi)存鏈表節(jié)點(diǎn)通過指針串起來這些在高級(jí)語言里被封裝掉了但理解它們才能理解算法為什么“快”或“慢”。第三個(gè)理由是面試和競(jìng)賽環(huán)境的主流仍是C/C。手撕代碼時(shí)C語言不會(huì)給你語法糖寫不出來就是寫不出來反而逼你練真功夫。至于“偽代碼害死人”我見過太多同學(xué)把“if p-next NULL return false”背得滾瓜爛熟但問“p為什么不空”“free之后要不要把p置空”就卡住。偽代碼省略了指針處理和內(nèi)存管理而這兩個(gè)恰恰是C語言的核心。所以我的做法是每個(gè)數(shù)據(jù)結(jié)構(gòu)都寫一份最小可運(yùn)行的程序包含創(chuàng)建、銷毀、插入、刪除、遍歷五個(gè)基本操作跑起來后才算“過”。2.3 最小練習(xí)閉環(huán)用C語言把數(shù)組棧和鏈表?xiàng)８鲗懸槐闂Ｊ侨腴T第一個(gè)數(shù)據(jù)結(jié)構(gòu)同時(shí)也是檢驗(yàn)?zāi)鉉語言基礎(chǔ)是否扎實(shí)的好工具。我建議用兩種方式實(shí)現(xiàn)順序棧數(shù)組和鏈?zhǔn)綏ｆ湵?。先看順序?include stdio.h #include stdlib.h #include stdbool.h // 順序棧結(jié)構(gòu)數(shù)組 棧頂下標(biāo) 容量 typedef struct { int *data; int top; // 棧頂指針指向下一個(gè)可寫入位置 int capacity; // 當(dāng)前容量 } ArrayStack; // 初始化申請(qǐng)初始容量為4的數(shù)組 void initStack(ArrayStack *s) { s-capacity 4; s-data (int *)malloc(sizeof(int) * s-capacity); if (s-data NULL) exit(1); s-top 0; // 空棧時(shí)top0 } // 入棧先檢查容量再寫入數(shù)據(jù) void push(ArrayStack *s, int value) { if (s-top s-capacity) { s-capacity * 2; s-data (int *)realloc(s-data, sizeof(int) * s-capacity); if (s-data NULL) exit(1); } s-data[s-top] value; } // 出棧top先減一再取數(shù)據(jù) int pop(ArrayStack *s) { if (s-top 0) { fprintf(stderr, stack underflow\n); exit(1); } return s-data[--s-top]; } // 銷毀釋放數(shù)組內(nèi)存 void destroyStack(ArrayStack *s) { free(s-data); s-data NULL; s-top s-capacity 0; }這里最容易踩的坑是realloc失敗導(dǎo)致原指針丟失所以先檢查返回值再賦值。另一個(gè)坑是出棧時(shí)--s-top的順序很多初學(xué)者寫成s-top--然后取data[s-top]雖然結(jié)果一樣但可讀性差。我的習(xí)慣是data[--s-top]這樣語義清晰先下移top再讀取。再看鏈?zhǔn)綏：诵氖枪?jié)點(diǎn)結(jié)構(gòu)和入棧出棧時(shí)指針的更新typedef struct Node { int data; struct Node *next; } Node; // 鏈?zhǔn)綏Ｖ恍枰粋€(gè)top指針指向棧頂節(jié)點(diǎn) typedef struct { Node *top; } LinkedStack; // 入棧新建節(jié)點(diǎn)前插到top前面 void pushLinked(LinkedStack *s, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) exit(1); newNode-data value; newNode-next s-top; // 新節(jié)點(diǎn)指向原來的棧頂 s-top newNode; // 更新棧頂 } // 出棧保存舊棧頂top后移free舊節(jié)點(diǎn) int popLinked(LinkedStack *s) { if (s-top NULL) { fprintf(stderr, stack underflow\n); exit(1); } Node *old s-top; int value old-data; s-top old-next; free(old); // 只釋放old節(jié)點(diǎn)不影響新棧頂 return value; }鏈?zhǔn)綏２挥每紤]容量但每個(gè)節(jié)點(diǎn)都要單獨(dú)malloc和free。我建議把兩個(gè)棧都寫一遍然后對(duì)比數(shù)組棧的入棧在擴(kuò)容時(shí)可能觸發(fā)拷貝鏈?zhǔn)綏５拿總€(gè)節(jié)點(diǎn)都有指針開銷。這個(gè)對(duì)比過程能幫你真正理解“空間換時(shí)間”的含義。寫完后用一組隨機(jī)數(shù)壓棧再彈棧檢查輸出是否逆序這就是第一個(gè)可復(fù)現(xiàn)的練習(xí)閉環(huán)。3. 經(jīng)典算法落地冒泡排序、歸并排序、KMP匹配的C語言實(shí)現(xiàn)與測(cè)試3.1 排序算法從冒泡到歸并參數(shù)和邊界條件怎么調(diào)排序是數(shù)據(jù)結(jié)構(gòu)的“試金石”。我要求自己至少能手寫四種冒泡、插入、歸并和堆排序。冒泡排序雖然效率低但用來理解“相鄰元素交換”最直觀。一個(gè)容易忽略的優(yōu)化是如果某輪沒有發(fā)生交換說明已經(jīng)有序可以提前退出。void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; // 本輪是否發(fā)生交換 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) break; // 無交換則提前結(jié)束 } }注意內(nèi)層循環(huán)的范圍是n - 1 - i因?yàn)槊枯喗Y(jié)束后最后i個(gè)元素已經(jīng)是排好序的不需要再比較。歸并排序的難點(diǎn)則在于合并操作必須用臨時(shí)數(shù)組并且要把剩余元素拷貝回去// 合并兩個(gè)有序區(qū)間 [l, mid] 和 [mid1, r] void merge(int arr[], int l, int mid, int r) { int leftSize mid - l 1; int rightSize r - mid; int left[leftSize], right[rightSize]; for (int i 0; i leftSize; i) left[i] arr[l i]; for (int i 0; i rightSize; i) right[i] arr[mid 1 i]; int i 0, j 0, k l; while (i leftSize j rightSize) { if (left[i] right[j]) arr[k] left[i]; else arr[k] right[j]; } // 處理剩余元素 while (i leftSize) arr[k] left[i]; while (j rightSize) arr[k] right[j]; } void mergeSort(int arr[], int l, int r) { if (l r) return; int mid l (r - l) / 2; // 防止整數(shù)溢出 mergeSort(arr, l, mid); mergeSort(arr, mid 1, r); merge(arr, l, mid, r); }mid用l (r - l) / 2而不是(l r) / 2是因?yàn)楫?dāng)l和r接近INT_MAX時(shí)后者的加法會(huì)溢出。這個(gè)細(xì)節(jié)在筆試中不一定考但在真實(shí)內(nèi)存溢出排查中很可能遇到。歸并排序是穩(wěn)定的代價(jià)是額外O(n)空間這也是面試官喜歡追問的點(diǎn)為什么快排不穩(wěn)定而歸并穩(wěn)定。3.2 KMP的next數(shù)組到底怎么求一段C代碼說清字符串匹配字符串匹配是C語言數(shù)據(jù)結(jié)構(gòu)里的“魔王”。KMP算法的核心不是匹配過程而是求next數(shù)組。很多教程用“最長公共前后綴”來解釋但一寫代碼就亂。我的記憶方法是next[j] 表示“在模式串的第j位置發(fā)生失配時(shí)下一次比較應(yīng)該從模式串的哪個(gè)下標(biāo)開始”。求next數(shù)組本質(zhì)上是在模式串自身身上做前綴匹配。#include string.h // 計(jì)算模式串pat的next數(shù)組數(shù)組長度與pat相同 void getNext(const char *pat, int *next) { int len strlen(pat); next[0] -1; // 哨兵表示首字符失配時(shí)主串指針也要前進(jìn) int i 0, j -1; while (i len - 1) { if (j -1 || pat[i] pat[j]) { i; j; next[i] j; } else { j next[j]; // 回溯這是KMP的精髓 } } } // KMP匹配返回pat在text中首次出現(xiàn)的下標(biāo)沒有則返回-1 int kmpSearch(const char *text, const char *pat, const int *next) { int i 0, j 0; int tLen strlen(text), pLen strlen(pat); while (i tLen j pLen) { if (j -1 || text[i] pat[j]) { i; j; } else { j next[j]; } } if (j pLen) return i - j; return -1; }next[0] -1是C語言實(shí)現(xiàn)里的常見做法它讓回溯邏輯統(tǒng)一為j next[j]而不用單獨(dú)處理j0的情況。我見過很多人求next時(shí)把i和j的移動(dòng)順序?qū)戝e(cuò)導(dǎo)致死循環(huán)。建議在紙上手動(dòng)演算一遍“ABCDABD”的next數(shù)組-1,0,0,0,0,1,2再對(duì)照代碼你會(huì)發(fā)現(xiàn)i是模式串的后綴指針j是前綴指針j -1時(shí)就說明前綴已經(jīng)到頭必須同時(shí)前進(jìn)并重置。這道坎跨過去KMP就算真正掌握了。3.3 可復(fù)現(xiàn)的測(cè)試框架用隨機(jī)數(shù)據(jù)對(duì)比不同算法耗時(shí)算法寫對(duì)了沒有不能靠眼睛看。我習(xí)慣用一個(gè)最簡單的測(cè)試框架生成隨機(jī)數(shù)組分別調(diào)用排序函數(shù)對(duì)比結(jié)果和耗時(shí)。這樣既驗(yàn)證正確性也能直觀看到O(n^2)和O(n log n)的差距。#include time.h #include stdlib.h #include stdio.h // 生成一個(gè)長度為n的隨機(jī)數(shù)組范圍[0, maxVal) void genRandomArray(int arr[], int n, int maxVal) { srand(time(NULL)); // 用當(dāng)前時(shí)間做種子 for (int i 0; i n; i) { arr[i] rand() % maxVal; } } // 檢查數(shù)組是否非遞減 int isSorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) return 0; } return 1; } // 計(jì)時(shí)并返回排序函數(shù)執(zhí)行時(shí)間毫秒 long timeSort(void (*sortFunc)(int *, int), int arr[], int n) { clock_t start clock(); sortFunc(arr, n); clock_t end clock(); return (end - start) * 1000 / CLOCKS_PER_SEC; }這里有個(gè)坑clock()測(cè)量的是CPU時(shí)間不是墻鐘時(shí)間在多線程下可能不準(zhǔn)但單線程練習(xí)足夠。另外如果你要對(duì)比多個(gè)排序算法必須復(fù)制一份相同的數(shù)組否則第一個(gè)排序已經(jīng)把它排好了第二個(gè)算法測(cè)出來是0毫秒。這其實(shí)就是“控制變量”的思想也是算法對(duì)比測(cè)試?yán)镒钊菀追嚨牡胤?。KMP的測(cè)試一般是構(gòu)造一個(gè)長文本和一個(gè)模式串用樸素匹配和KMP各跑一遍統(tǒng)計(jì)比較次數(shù)比看耗時(shí)更有說服力——因?yàn)樽址ヅ涞暮臅r(shí)受緩存影響太大。4. C語言數(shù)據(jù)結(jié)構(gòu)避坑指南指針懸掛、越界、遞歸溢出的5個(gè)血淚教訓(xùn)4.1 刪除鏈表節(jié)點(diǎn)后“忘了置空”use-after-free崩潰現(xiàn)象鏈表刪除函數(shù)執(zhí)行后遍歷鏈表時(shí)偶發(fā)段錯(cuò)誤有時(shí)還能打印出已經(jīng)“被刪除”節(jié)點(diǎn)的值。原因free(p)只是釋放了p指向的內(nèi)存但p指針本身的值沒變?nèi)匀恢赶蚰菈K已回收的內(nèi)存。如果后續(xù)代碼繼續(xù)通過p訪問或者另一個(gè)節(jié)點(diǎn)還殘留指向p的next指針就成了懸掛指針。解決刪除節(jié)點(diǎn)時(shí)必須先把前驅(qū)節(jié)點(diǎn)的next指向p-next再釋放p。釋放后把p置為NULL避免誤用。我一般會(huì)在free后加一行p NULL;。更高要求的做法是如果鏈表可能被多處引用刪除后返回新的頭指針并讓調(diào)用方更新。這個(gè)習(xí)慣能規(guī)避大部分use-after-free問題。4.2 數(shù)組下標(biāo)差1排序里最隱蔽的越界現(xiàn)象冒泡排序里內(nèi)層循環(huán)寫成j n - i歸并排序的臨時(shí)數(shù)組大小算錯(cuò)一位結(jié)果要么越界寫壞數(shù)據(jù)要么排序結(jié)果里有一個(gè)元素始終不對(duì)。原因C語言數(shù)組下標(biāo)從0開始長度為n的數(shù)組合法下標(biāo)是0到n-1。排序循環(huán)里“最多需要比較n-1次”和“第i輪需要比較n-1-i次”很容易差1。越界寫內(nèi)存不會(huì)立刻崩潰但會(huì)悄悄篡改相鄰變量導(dǎo)致數(shù)據(jù)錯(cuò)亂。解決寫完排序后用斷言檢查邊界。比如在冒泡內(nèi)層循環(huán)里加一句if (j 1 n) break;運(yùn)行時(shí)立刻暴露問題。我還會(huì)用AddressSanitizer編譯gcc -fsanitizeaddress -g sort.c這樣越界訪問會(huì)直接報(bào)錯(cuò)并給出調(diào)用棧省去大量排查時(shí)間。4.3 遞歸深度過大二叉樹深度優(yōu)先遍歷的棧溢出現(xiàn)象對(duì)一棵深度接近10000的二叉樹做遞歸前序遍歷程序直接段錯(cuò)誤連報(bào)錯(cuò)都沒有。原因遞歸調(diào)用依賴系統(tǒng)調(diào)用棧Linux默認(rèn)棧大小通常為8MB每層遞歸函數(shù)只要分配幾十字節(jié)上下文10000層就可能溢出。數(shù)據(jù)結(jié)構(gòu)教材里的遞歸遍歷在理論上沒問題但真實(shí)生產(chǎn)環(huán)境的樹可能非常深。解決把遞歸改成顯式?；蛘哂肕orris遍歷利用空指針線索。需要保留遞歸寫法時(shí)可以做兩件事一是讓遞歸函數(shù)盡量少用局部變量二是用ulimit -s查看并增大?？臻g。但我的建議是二叉樹的非遞歸遍歷是高頻面試題不如趁著這個(gè)機(jī)會(huì)把“用棧模擬遞歸”練熟一勞永逸。4.4 結(jié)構(gòu)體按值傳參大數(shù)據(jù)結(jié)構(gòu)體為什么慢現(xiàn)象把一個(gè)包含幾萬個(gè)節(jié)點(diǎn)的二叉樹結(jié)構(gòu)體直接傳入函數(shù)編譯不開優(yōu)化時(shí)每次調(diào)用都要拷貝幾十KB數(shù)據(jù)明顯感覺程序卡頓。原因C語言里結(jié)構(gòu)體按值傳參時(shí)實(shí)參會(huì)完整復(fù)制到新棧幀。如果結(jié)構(gòu)體很大復(fù)制開銷遠(yuǎn)大于傳指針。解決傳遞指針并在函數(shù)內(nèi)只修改需要修改的部分。如果函數(shù)不需要修改原結(jié)構(gòu)體傳const Node *node既安全又能讓編譯器優(yōu)化。這個(gè)教訓(xùn)在實(shí)現(xiàn)圖和樹的時(shí)候尤其重要因?yàn)楣?jié)點(diǎn)結(jié)構(gòu)體往往包含多個(gè)數(shù)組或子節(jié)點(diǎn)指針按值傳參等于把整棵子樹復(fù)制一遍純屬浪費(fèi)。4.5 測(cè)試數(shù)據(jù)一鍋端有序、亂序、重復(fù)數(shù)據(jù)下的排序性能假象現(xiàn)象用一組幾乎有序的數(shù)據(jù)測(cè)試快速排序發(fā)現(xiàn)它跑得比冒泡還慢又或者用全相同數(shù)據(jù)測(cè)試有些排序直接段錯(cuò)誤。原因快排在最壞情況下時(shí)間復(fù)雜度為O(n^2)當(dāng)數(shù)據(jù)已經(jīng)有序且選取中間元素作為基準(zhǔn)時(shí)遞歸深度可能接近n導(dǎo)致棧溢出。而冒泡排序?qū)τ行驍?shù)據(jù)反而能提前退出。解決測(cè)試排序算法時(shí)至少要準(zhǔn)備三種輸入隨機(jī)亂序、升序、降序、全相同。針對(duì)快排可以改為“三數(shù)取中”選取基準(zhǔn)或者隨機(jī)選取基準(zhǔn)避免固定邊界導(dǎo)致的最壞情況。我一般會(huì)在測(cè)試框架里生成這四組數(shù)據(jù)分別跑一遍并打印耗時(shí)這樣才能真實(shí)評(píng)估一個(gè)算法的適用場(chǎng)景。5. 工程化練習(xí)環(huán)境VSCode GCC Makefile valgrind 的最小配置5.1 為什么我不用IDE直接寫三行Makefile帶來的確定性很多同學(xué)用Visual Studio或Clion點(diǎn)一下運(yùn)行就能看到輸出。但數(shù)據(jù)結(jié)構(gòu)練習(xí)需要“可復(fù)現(xiàn)、可檢查、可調(diào)試”IDE把這些細(xì)節(jié)藏起來了。我用VSCode配GCC和Makefile理由是編譯命令是可見的調(diào)試參數(shù)是顯式的內(nèi)存檢查是隨手寫的。當(dāng)你親手敲出gcc -g -Wall這幾行你會(huì)開始關(guān)注編譯警告而不是等程序崩了再去猜。VSCode里只需要安裝C/C擴(kuò)展然后用終端命令編譯運(yùn)行。這樣你在面試白板上寫代碼時(shí)也不會(huì)依賴智能提示。我建議不要用一鍵運(yùn)行按鈕而是養(yǎng)成在終端里執(zhí)行make ./main的習(xí)慣。5.2 最小Makefile模板支持調(diào)試與內(nèi)存檢查下面這個(gè)Makefile我用了很久足夠覆蓋數(shù)據(jù)結(jié)構(gòu)練習(xí)的絕大多數(shù)需求CC gcc CFLAGS -Wall -Wextra -g -stdc11 LDFLAGS # 需要根據(jù)實(shí)際文件調(diào)整這里假設(shè)最終目標(biāo)是main SRCS main.c stack.c linkedlist.c OBJS $(SRCS:.c.o) main: $(OBJS) $(CC) $(LDFLAGS) -o $ $^ %.o: %.c $(CC) $(CFLAGS) -c $ -o $ clean: rm -f main $(OBJS) # 內(nèi)存檢查編譯后運(yùn)行valgrind memcheck: main valgrind --leak-checkfull --error-exitcode1 ./main參數(shù)說明-Wall -Wextra開啟嚴(yán)格警告能提示未使用變量、符號(hào)比較等問題-g生成調(diào)試信息供gdb和valgrind使用-stdc11避免一些舊標(biāo)準(zhǔn)下的隱晦行為。%.o: %.c是通用規(guī)則每次新增源文件只需要在SRCS里加一行。運(yùn)行make memcheck時(shí)就會(huì)自動(dòng)編譯并調(diào)用valgrind檢查內(nèi)存泄漏。我第一次跑通這個(gè)模板時(shí)發(fā)現(xiàn)自己冒泡排序里有個(gè)數(shù)組越界是valgrind先報(bào)出來的這感覺比事后查半天舒服多了。5.3 gdb斷點(diǎn)調(diào)試與valgrind內(nèi)存泄漏檢測(cè)的常用命令用gdb調(diào)試鏈表時(shí)我最常用的三條命令是break、next、print。例如在刪除節(jié)點(diǎn)的函數(shù)開頭設(shè)斷點(diǎn)gdb ./main break deleteNode # 在deleteNode函數(shù)入口處暫停 run # 啟動(dòng)程序停在斷點(diǎn) print p-data # 查看當(dāng)前節(jié)點(diǎn)數(shù)據(jù) next # 單步執(zhí)行一行 print p-next # 看next指針指向哪里 continue # 繼續(xù)運(yùn)行這里的print對(duì)指針結(jié)構(gòu)體也能直接展開顯示成員省去手動(dòng)查內(nèi)存地址。而valgrind的命令更簡單valgrind --leak-checkfull --show-leak-kindsall ./main如果輸出里有definitely lost: N bytes說明內(nèi)存泄漏了。定位到具體行號(hào)后回頭檢查malloc和free是否成對(duì)。我見過有些同學(xué)總說“我的鏈表沒內(nèi)存泄漏”直到valgrind報(bào)出一大堆才發(fā)現(xiàn)銷毀函數(shù)只free了頭節(jié)點(diǎn)后面的節(jié)點(diǎn)都丟了。這個(gè)教訓(xùn)讓我養(yǎng)成習(xí)慣每寫一個(gè)涉及malloc的接口就立刻寫對(duì)應(yīng)的free接口并把兩者在注釋里對(duì)應(yīng)起來。6. 讓算法真正長在身上每學(xué)一個(gè)結(jié)構(gòu)先畫圖再寫碼最后用隨機(jī)數(shù)據(jù)驗(yàn)證數(shù)據(jù)結(jié)構(gòu)與算法這門課最怕的就是“眼睛會(huì)了手不會(huì)”。我自己的方法是固定三步走堅(jiān)持三個(gè)月后手寫常見數(shù)據(jù)結(jié)構(gòu)的代碼基本不會(huì)卡殼。第一步是畫圖。學(xué)鏈表時(shí)畫兩個(gè)方框代表節(jié)點(diǎn)用箭頭表示指針學(xué)二叉樹時(shí)畫一棵樹然后標(biāo)出前序、中序、后序遍歷的路徑。畫圖能讓你把“抽象結(jié)構(gòu)”變成“記憶中的畫面”寫代碼時(shí)腦子里就有一個(gè)指針怎么移動(dòng)的動(dòng)畫。我甚至?xí)诓莞寮埳夏M空指針、頭節(jié)點(diǎn)、雙向鏈表prev和next的對(duì)稱性。這一步省不掉尤其是KMP的next數(shù)組不畫圖根本理解不了“回溯”。第二步是寫代碼但不能貼抄。我的習(xí)慣是早上看完原理晚上合上書從空白文件開始寫。寫的過程中不許查教材只許查C語言語法比如realloc的用法。寫完編譯運(yùn)行如果報(bào)錯(cuò)就用gdb定位。這樣折騰出來的代碼比看十遍例題都印象深刻。關(guān)鍵點(diǎn)要畫“記憶錨點(diǎn)”比如KMP的next[0] -1鏈表刪除時(shí)free(p); p NULL;這些是你未來面試手撕時(shí)的條件反射。第三步是用隨機(jī)數(shù)據(jù)驗(yàn)證。這是最容易被新手忽略的。我寫的每個(gè)排序、查找、樹操作都會(huì)配一個(gè)測(cè)試函數(shù)構(gòu)造隨機(jī)數(shù)據(jù)、執(zhí)行操作、檢查結(jié)果是否符合預(yù)期。比如測(cè)試二叉搜索樹插入后中序遍歷應(yīng)該是有序序列測(cè)試棧后彈出序列應(yīng)該等于壓棧逆序。這套驗(yàn)證方法還能幫你發(fā)現(xiàn)隱藏的性能問題——當(dāng)數(shù)據(jù)規(guī)模從100變成100000時(shí)O(n^2)和O(n log n)的耗時(shí)差距會(huì)變得觸目驚心。最后說一個(gè)我最近的教訓(xùn)寫堆排序時(shí)我自認(rèn)為理解了“下沉”操作結(jié)果構(gòu)建堆時(shí)把條件寫反導(dǎo)致排序結(jié)果完全錯(cuò)誤。原因就是我沒畫圖只靠代碼推理。后來我在紙上畫出數(shù)組在完全二叉樹中的對(duì)應(yīng)位置立刻發(fā)現(xiàn)下標(biāo)計(jì)算差了一個(gè)偏移量。這件事讓我更堅(jiān)定數(shù)據(jù)結(jié)構(gòu)不是背出來的是畫出來、寫出來、測(cè)出來的。如果你也正在被“看著都會(huì)一寫就廢”困擾不妨試試我這個(gè)三步法先從今天學(xué)的一個(gè)棧或一個(gè)排序開始。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取