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