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