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