數(shù)據(jù)結(jié)構(gòu)好學(xué)嗎

我曾經(jīng)推薦一個(gè)學(xué)生到某知名公司，沒(méi)多久，學(xué)生向我說(shuō)了應(yīng)聘的事情：“我介紹我開(kāi)發(fā)了企業(yè)管理系統(tǒng)、在線商城系統(tǒng)等，沒(méi)想到他問(wèn)我使用了什么數(shù)據(jù)結(jié)構(gòu)和算法，我懂很多技術(shù)，那么多功能我都實(shí)現(xiàn)了，他不問(wèn)，卻問(wèn)我使用了什么數(shù)據(jù)結(jié)構(gòu)和算法，你說(shuō)搞笑不?數(shù)據(jù)結(jié)構(gòu)和算法我早就忘了，我會(huì)開(kāi)發(fā)軟件還不行嗎?”人力資源總監(jiān)也反饋過(guò)來(lái)意見(jiàn)：“很搞笑，這個(gè)學(xué)生做了不少系統(tǒng)，卻說(shuō)根本沒(méi)用到數(shù)據(jù)結(jié)構(gòu)和算法。”

既然雙方都覺(jué)得這是一件搞笑的事情，那么我們就攤開(kāi)來(lái)看，數(shù)據(jù)結(jié)構(gòu)到底是什么。

撥云見(jiàn)日，看清數(shù)據(jù)結(jié)構(gòu)

當(dāng)我們遇到一個(gè)實(shí)際問(wèn)題時(shí)，首先需要解決兩件事：

(1)如何將數(shù)據(jù)存儲(chǔ)在計(jì)算機(jī)中;

(2)用什么方法和策略解決問(wèn)題。

前者是數(shù)據(jù)結(jié)構(gòu)，后者是算法。只有數(shù)據(jù)結(jié)構(gòu)沒(méi)有算法，相當(dāng)于只把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，而沒(méi)有有效的方法去處理，就像一幢只有框架的爛尾樓;若只有算法，沒(méi)有數(shù)據(jù)結(jié)構(gòu)，就像沙漠里的海市蜃樓，只不過(guò)是空中樓閣罷了。

數(shù)據(jù)是一切能輸入計(jì)算機(jī)中的信息的總和，結(jié)構(gòu)是指數(shù)據(jù)之間的關(guān)系。數(shù)據(jù)結(jié)構(gòu)就是將數(shù)據(jù)及其之間的關(guān)系有效地存儲(chǔ)在計(jì)算機(jī)中并進(jìn)行基本操作。算法是對(duì)特定問(wèn)題求解步驟的一種描述，通俗講就是解決問(wèn)題的方法和策略。

在遇到一個(gè)實(shí)際問(wèn)題時(shí)，要充分利用自己所學(xué)的數(shù)據(jù)結(jié)構(gòu)，將數(shù)據(jù)及其之間的關(guān)系有效地存儲(chǔ)在計(jì)算機(jī)中，然后選擇合適的算法策略，并用程序高效地實(shí)現(xiàn)。這就是Niklaus Wirth教授所說(shuō)的：“數(shù)據(jù)結(jié)構(gòu)+算法=程序”。

為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

高校的計(jì)算機(jī)專業(yè)為本科生都開(kāi)設(shè)了數(shù)據(jù)結(jié)構(gòu)課程，它是計(jì)算機(jī)學(xué)科知識(shí)結(jié)構(gòu)的核心和技術(shù)體系的基石，在研究生考試中也是必考科目。隨著科學(xué)技術(shù)的飛速發(fā)展，數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)性地位不僅沒(méi)有動(dòng)搖，反而因近年來(lái)算法工程師的高薪形勢(shì)，而得到了業(yè)內(nèi)空前的重視。很多人認(rèn)為基本的數(shù)據(jù)結(jié)構(gòu)及操作已經(jīng)在高級(jí)語(yǔ)言(如C++、Java語(yǔ)言)中封裝，棧、隊(duì)列、排序、優(yōu)先隊(duì)列等都可以直接調(diào)用庫(kù)函數(shù)，學(xué)會(huì)怎么調(diào)用就好了，為什么要重復(fù)“造輪子”?那么到底有沒(méi)有必要好好學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)呢?

先看學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用處。

(1)學(xué)習(xí)有效存儲(chǔ)數(shù)據(jù)的方法。很多學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，問(wèn)我要不要把單鏈表插入、刪除背下來(lái)?要不合上書就不會(huì)寫了。我非常詫異，為什么要背?理工科技術(shù)知識(shí)很少需要記憶的，是用的，用的!學(xué)習(xí)知識(shí)不能只靠死記硬背，更重要的是學(xué)習(xí)處理問(wèn)題的方法。如何有效地存儲(chǔ)數(shù)據(jù)，不同的數(shù)據(jù)結(jié)構(gòu)產(chǎn)生什么樣的算法復(fù)雜性，有沒(méi)有更好的存儲(chǔ)方法提高算法的效率?

(2)處理具有復(fù)雜關(guān)系的數(shù)據(jù)?，F(xiàn)實(shí)中很多具有復(fù)雜關(guān)系的數(shù)據(jù)無(wú)法通過(guò)簡(jiǎn)單的庫(kù)函數(shù)調(diào)用實(shí)現(xiàn)。如同現(xiàn)在很多芯片高度集成，完全不需要知道芯片內(nèi)部如何，直接使用就行了。但是，如果在現(xiàn)實(shí)中遇到一個(gè)復(fù)雜問(wèn)題，現(xiàn)有的芯片根本無(wú)法解決，或者一個(gè)芯片只能完成其中一個(gè)功能，而我們需要的是完成該復(fù)雜問(wèn)題的一個(gè)集成芯片，這時(shí)就需要運(yùn)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識(shí)來(lái)高效處理具有復(fù)雜關(guān)系的數(shù)據(jù)。

(3)提高算法效率。很多問(wèn)題的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)運(yùn)行效率較低，需要借助高級(jí)數(shù)據(jù)結(jié)構(gòu)或通過(guò)改進(jìn)數(shù)據(jù)結(jié)構(gòu)來(lái)提高算法效率。

通過(guò)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，更加準(zhǔn)確和深刻地理解不同數(shù)據(jù)結(jié)構(gòu)之間的共性和聯(lián)系，學(xué)會(huì)選擇和改進(jìn)數(shù)據(jù)結(jié)構(gòu)，高效地設(shè)計(jì)并實(shí)現(xiàn)各種算法，這才是數(shù)據(jù)結(jié)構(gòu)的精髓。

數(shù)據(jù)結(jié)構(gòu)為什么那么難

網(wǎng)絡(luò)上太多的同學(xué)吐槽被“虐”，如“滔滔江水連綿不絕”，數(shù)據(jù)結(jié)構(gòu)太難了!真的很難嗎?其實(shí)數(shù)據(jù)結(jié)構(gòu)只是講了3部分內(nèi)容：線性結(jié)構(gòu)、樹(shù)和圖。到底難在哪里呢?我通過(guò)調(diào)查，了解到數(shù)據(jù)結(jié)構(gòu)難學(xué)大概有以下4個(gè)原因。

(1)無(wú)法接受它的描述方式。數(shù)據(jù)結(jié)構(gòu)的描述大多是抽象的形式，我們習(xí)慣了使用自然語(yǔ)言表達(dá)，難以接受數(shù)據(jù)結(jié)構(gòu)的抽象表達(dá)。不止一個(gè)學(xué)生問(wèn)我，書上的“ElemType”到底是什么類型?運(yùn)行時(shí)怎么經(jīng)常提示錯(cuò)誤。它的意思就是“元素類型”，只是這樣來(lái)描述，你需要什么類型就寫什么類型，例如int。這樣的表達(dá)方式會(huì)讓不少人感到崩潰。

(2)不知道它有什么用處。盡管很多人學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，但目的各不相同。有的人是應(yīng)付考試，有的人是參加算法競(jìng)賽需要，而很多人不太清楚學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)有什么用處，迷迷糊糊看書、做題、考試。

(3)體會(huì)不到其中的妙處。由于教材、教師等各種因素影響，很多學(xué)生沒(méi)有體會(huì)到數(shù)據(jù)結(jié)構(gòu)處理數(shù)據(jù)的妙處，經(jīng)常為學(xué)不會(huì)而焦頭爛額，學(xué)習(xí)重在體會(huì)其中的樂(lè)趣，有樂(lè)趣才有興趣，興趣是最好的驅(qū)動(dòng)力。

(4)語(yǔ)言基礎(chǔ)不好。我一直強(qiáng)調(diào)先看圖解，理清思路，再上機(jī)?？蛇€是有很多同學(xué)已經(jīng)理解了思路后，因?yàn)槿鄙賛ain函數(shù)，輸入/輸出格式不對(duì)，缺少括號(hào)等各種語(yǔ)言問(wèn)題卡殼，而這一切都被戴上了“數(shù)據(jù)結(jié)構(gòu)太難了”的大帽子。

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)秘籍

在講學(xué)習(xí)秘籍之前，我們首先了解一下數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的3種境界。

(1)會(huì)數(shù)據(jù)結(jié)構(gòu)的基本操作。學(xué)會(huì)各種數(shù)據(jù)結(jié)構(gòu)的基本操作，即取值、查找、插入、刪除等，是最基礎(chǔ)的要求。先看圖解，理解各種數(shù)據(jù)結(jié)構(gòu)的定義，操作方法，然后看代碼，嘗試自己動(dòng)手上機(jī)運(yùn)行，逐漸掌握基本操作。在初學(xué)時(shí)，要想理解數(shù)據(jù)結(jié)構(gòu)，一定要學(xué)會(huì)畫圖。通過(guò)畫圖形象表達(dá)，能更好地體會(huì)其中的數(shù)據(jù)結(jié)構(gòu)關(guān)系。因此，初學(xué)階段學(xué)習(xí)利器是：畫圖、理解、畫圖。

(2)會(huì)利用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題。在掌握了書中的基本操作之后，就可以嘗試?yán)脭?shù)據(jù)結(jié)構(gòu)解決一些實(shí)際問(wèn)題了。先學(xué)經(jīng)典應(yīng)用問(wèn)題的解決方法，體會(huì)數(shù)據(jù)結(jié)構(gòu)的使用方法，再做題，獨(dú)立設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)解決問(wèn)題。要想熟練應(yīng)用就必須做大量的題，在做題的過(guò)程中體會(huì)其中的方法。最好進(jìn)行專項(xiàng)練習(xí)，比如線性表問(wèn)題、二叉樹(shù)問(wèn)題、圖問(wèn)題。這一階段的學(xué)習(xí)利器是：做題、反思、做題。

(3)熟練使用和改進(jìn)數(shù)據(jù)結(jié)構(gòu)，優(yōu)化算法。這是最高境界了，也是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的精髓所在，單獨(dú)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是無(wú)法達(dá)到這種境界的。數(shù)據(jù)結(jié)構(gòu)與算法相輔相成，需要在學(xué)習(xí)算法的過(guò)程中慢慢修煉。在學(xué)習(xí)算法的同時(shí)，逐步熟練應(yīng)用、改進(jìn)數(shù)據(jù)結(jié)構(gòu)，慢慢體會(huì)不同數(shù)據(jù)結(jié)構(gòu)和算法策略的算法復(fù)雜性，最終學(xué)會(huì)利用數(shù)據(jù)結(jié)構(gòu)改進(jìn)和優(yōu)化算法。這一階段已經(jīng)在數(shù)據(jù)結(jié)構(gòu)之上，可以通過(guò)在ACM測(cè)試系統(tǒng)上刷各種算法題，體會(huì)數(shù)據(jù)結(jié)構(gòu)在算法設(shè)計(jì)中的應(yīng)用。這一階段的學(xué)習(xí)利器是：刷題、總結(jié)、刷題。

它讓數(shù)據(jù)結(jié)構(gòu)變得簡(jiǎn)單

趣學(xué)數(shù)據(jù)結(jié)構(gòu)　陳小玉 著

本書特色

本書具有五大特色。

(1)完美圖解，通俗易懂。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)最好的辦法就是畫圖、畫圖、畫圖。本書中的每一個(gè)基本操作和演示都有圖解，有了圖解，一切就都變得簡(jiǎn)單，迎刃而解。

(2)實(shí)例豐富，簡(jiǎn)單有趣。本書結(jié)合大量實(shí)例，講述如何利用數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題，使復(fù)雜難懂的問(wèn)題變得簡(jiǎn)單有趣，給讀者帶來(lái)巨大的閱讀樂(lè)趣，使讀者在閱讀中不知不覺(jué)地學(xué)會(huì)數(shù)據(jù)結(jié)構(gòu)知識(shí)，體會(huì)數(shù)據(jù)結(jié)構(gòu)的妙處。

(3)深入淺出，透析本質(zhì)。本書采用簡(jiǎn)潔易懂的代碼描述，抓住本質(zhì)，通俗描述及注釋使代碼更加易懂。本書不僅對(duì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和操作描述全面細(xì)致，而且有復(fù)雜性分析過(guò)程。

(4)實(shí)戰(zhàn)演練，循序漸進(jìn)。本書在每一個(gè)數(shù)據(jù)結(jié)構(gòu)講解清楚后，進(jìn)行實(shí)戰(zhàn)演練，使讀者在實(shí)戰(zhàn)中體會(huì)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和操作，增強(qiáng)自信，從而提高了讀者獨(dú)立思考、自己動(dòng)手實(shí)踐的能力。豐富的練習(xí)題和思考題及時(shí)檢驗(yàn)對(duì)所學(xué)知識(shí)的掌握情況，為讀者從小問(wèn)題出發(fā)，逐步解決大型復(fù)雜性問(wèn)題奠定基礎(chǔ)。

(5)網(wǎng)絡(luò)資源，技術(shù)支持。本書為讀者提供本書所有范例程序的源代碼、練習(xí)題以及答案解析，這些源代碼可以自由修改編譯，以符合自己的需要。本書提供源代碼執(zhí)行、調(diào)試說(shuō)明書，提供博客、QQ群技術(shù)支持，為讀者答疑解惑。

本書內(nèi)容

本書包括10章。

第1章是基礎(chǔ)知識(shí)，介紹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)和算法復(fù)雜性的計(jì)算方法。

第2～5章是線性結(jié)構(gòu)，講解線性表、棧和隊(duì)列、字符串、數(shù)組等的基本操作和應(yīng)用。

第6章是樹(shù)形結(jié)構(gòu)，講解樹(shù)、二叉樹(shù)、線索二叉樹(shù)、樹(shù)和森林以及樹(shù)的經(jīng)典應(yīng)用。

第7章是圖形結(jié)構(gòu)，講解圖的存儲(chǔ)、遍歷以及圖的經(jīng)典應(yīng)用。

第8～9章是數(shù)據(jù)結(jié)構(gòu)的基本應(yīng)用，講解查找、排序的方法和算法復(fù)雜性比較。

第10章是高級(jí)數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用，講解優(yōu)先隊(duì)列、并查集、B-樹(shù)、B+樹(shù)、紅黑樹(shù)等。