“數(shù)據(jù)結(jié)構(gòu)”課程是計(jì)算機(jī)類、電子信息類及相關(guān)專業(yè)的專業(yè)基礎(chǔ)課。它在整個(gè)課程體系中處于承上啟下的核心地位：一方面擴(kuò)展和深化在離散數(shù)學(xué)、程序設(shè)計(jì)語言等課程學(xué)到的基本技術(shù)和方法；另一方面為進(jìn)一步學(xué)習(xí)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫等專業(yè)知識(shí)奠定堅(jiān)實(shí)的理論與實(shí)踐基礎(chǔ)。本課程在教給學(xué)生數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法設(shè)計(jì)的同時(shí)，培養(yǎng)學(xué)生的抽象思維能力、邏輯推理能力和形式化思維方法，增強(qiáng)分析問題、解決問題和總結(jié)問題的能力，更重要的是培養(yǎng)專業(yè)興趣，樹立創(chuàng)新意識(shí)。本教材在內(nèi)容選取上符合人才培養(yǎng)目標(biāo)的要求及教學(xué)規(guī)律和認(rèn)知規(guī)律，在組織編排上體現(xiàn)“先理論、后應(yīng)用、理論與應(yīng)用相結(jié)合”的原則，并兼顧學(xué)科的廣度和深度，力求適用面廣泛。
全書共11章。第1章綜述數(shù)據(jù)、數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型等基本概念及算法描述與分析方法；第2～9章主要從抽象數(shù)據(jù)類型的角度分別討論線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹和二叉樹、圖等基本類型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用；第10章和第11章討論查找和排序的各種方法，著重從時(shí)間性能、應(yīng)用場合及使用范圍方面進(jìn)行分析和比較。本書對(duì)數(shù)據(jù)結(jié)構(gòu)眾多知識(shí)點(diǎn)的來龍去脈做了詳細(xì)解釋和說明；每章后面配有難度各異的習(xí)題，并在附錄中給出習(xí)題的參考答案，供讀者理解知識(shí)及復(fù)習(xí)提高之用。全書采用C語言描述數(shù)據(jù)結(jié)構(gòu)和算法。
從課程性質(zhì)上講，“數(shù)據(jù)結(jié)構(gòu)”是高等院校計(jì)算機(jī)科學(xué)、電子信息科學(xué)及相關(guān)專業(yè)教學(xué)計(jì)劃中的一門專業(yè)基礎(chǔ)課；其教學(xué)要求是學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為實(shí)際應(yīng)用涉及的數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其相應(yīng)的算法，并初步掌握算法的時(shí)空分析技術(shù)。從課程學(xué)習(xí)上講，“數(shù)據(jù)結(jié)構(gòu)”的學(xué)習(xí)是復(fù)雜程序設(shè)計(jì)的訓(xùn)練過程；其教學(xué)目的是著眼于原理與應(yīng)用的結(jié)合，在深化理解和靈活掌握教學(xué)內(nèi)容的基礎(chǔ)上，學(xué)會(huì)把知識(shí)用于解決實(shí)際問題，書寫出符合軟件工程規(guī)范的文件，編寫出結(jié)構(gòu)清晰及正確易讀的程序代碼。可以說，“數(shù)據(jù)結(jié)構(gòu)”比“高級(jí)程序設(shè)計(jì)語言”等課程有著更高的要求，它更注重培養(yǎng)分析抽象數(shù)據(jù)的能力。
本書是編者多年從事該課程教學(xué)工作的教學(xué)成果，編者都是具有副教授以上職稱、有15年以上該課程教學(xué)經(jīng)驗(yàn)的一線教師。本書由任志國擔(dān)任主編、趙傳成、藍(lán)才會(huì)、祁建宏、達(dá)文姣、岳秋菊、劉君擔(dān)任副主編。其中的第1章、第2章、第5章、第7章、第8章、第9章由任志國編寫，第3章由趙傳成編寫，第4章由岳秋菊編寫，第6章由達(dá)文姣編寫，第10章由藍(lán)才會(huì)編寫，第11章由祁建宏編寫，所有章節(jié)習(xí)題部分由劉君編寫。在本書的構(gòu)思與編寫過程中，得到了安天慶教授、黨建武教授、王治和教授的幫助，在算法的實(shí)現(xiàn)與調(diào)試以及插圖的制作過程中，得到了楊業(yè)、史淑娟、宗小兵等研究生的幫助，在此表示感謝。
《數(shù)據(jù)結(jié)構(gòu)（C語言描述）》：
1.2.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示（又稱為映像）稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲(chǔ)結(jié)構(gòu)。它不同于邏輯結(jié)構(gòu)，是依賴計(jì)算機(jī)語言的，是具體的。通常，一個(gè)數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)用一塊連續(xù)的存儲(chǔ)單元來表示。那么，在計(jì)算機(jī)中怎樣存儲(chǔ)表中所有的數(shù)據(jù)元素呢？數(shù)據(jù)結(jié)構(gòu)一般用下面四種基本的存儲(chǔ)結(jié)構(gòu)來表示數(shù)據(jù)元素之間的關(guān)系。
1.順序存儲(chǔ)結(jié)構(gòu)
該方法把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置也相鄰的存儲(chǔ)單元里，數(shù)據(jù)元素之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)主要應(yīng)用于線性結(jié)構(gòu)，非線性結(jié)構(gòu)也可以通過某種線性的方法實(shí)現(xiàn)順序存儲(chǔ)。其優(yōu)點(diǎn)是可以實(shí)現(xiàn)隨機(jī)存取，每個(gè)元素占用最少的存儲(chǔ)空間，即存儲(chǔ)密度大。其缺點(diǎn)是只能使用相鄰的一整塊存儲(chǔ)單元，因此可能產(chǎn)生較多的外部碎片。
2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
該方法不要求邏輯上相鄰的數(shù)據(jù)元素在物理位置上也相鄰，數(shù)據(jù)元素之間的邏輯關(guān)系由附加的指針表示，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。其優(yōu)點(diǎn)是不會(huì)出現(xiàn)碎片現(xiàn)象，可充分利用所有存儲(chǔ)單元。其缺點(diǎn)是每個(gè)元素因存儲(chǔ)指針而占用額外的存儲(chǔ)空間，并且只能實(shí)現(xiàn)順序存取。
3.索引存儲(chǔ)結(jié)構(gòu)
該方法通常在存儲(chǔ)數(shù)據(jù)元素信息的同時(shí)，還建立附加的索引表。索引表由若干索引項(xiàng)組成。索引項(xiàng)的一般形式是：（關(guān)鍵字、地址）。關(guān)鍵字（Key）是能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的那些數(shù)據(jù)項(xiàng)。其優(yōu)點(diǎn)是檢索速度快。缺點(diǎn)是增加附加的索引表占用較多的存儲(chǔ)空間。在增加和刪除數(shù)據(jù)時(shí)要修改索引表，因而花費(fèi)較多的時(shí)間。
4.哈希（散列）存儲(chǔ)結(jié)構(gòu)
該方法的基本思想是根據(jù)數(shù)據(jù)元素的關(guān)鍵字直接計(jì)算出該數(shù)據(jù)元素的存儲(chǔ)地址。其優(yōu)點(diǎn)是檢索、增加、刪除結(jié)點(diǎn)的操作都很快。缺點(diǎn)是如果散列函數(shù)不好，可能出現(xiàn)數(shù)據(jù)元素存儲(chǔ)地址的沖突，而解決沖突會(huì)增加時(shí)間和空間開銷。
這四種基本存儲(chǔ)方法既可以單獨(dú)使用，也可以組合起來對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映像。同一邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)；采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理效率往往不同。選擇何種存儲(chǔ)結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮運(yùn)算方便及算法的時(shí)空要求。
1.2.4數(shù)據(jù)的運(yùn)算
為了有效地處理數(shù)據(jù)，可將數(shù)據(jù)按一定的邏輯結(jié)構(gòu)組織起來，并選擇適當(dāng)?shù)拇鎯?chǔ)方法存儲(chǔ)數(shù)據(jù)，然后再對(duì)數(shù)據(jù)進(jìn)行運(yùn)算。
數(shù)據(jù)的運(yùn)算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)之上的，每一種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合，并指出運(yùn)算的功能，例如，查找、插入、刪除、修改等，這些運(yùn)算實(shí)際上是在數(shù)據(jù)元素上施加的一系列的抽象操作。所謂抽象操作，是只知道這些操作要求“做什么”，而無須考慮“如何做”，只有在確定了存儲(chǔ)結(jié)構(gòu)之后，才考慮如何具體實(shí)現(xiàn)這些運(yùn)算。下面介紹幾種常見的數(shù)據(jù)運(yùn)算。
……
書單推薦
