數(shù)據(jù)結(jié)構(gòu)

內(nèi)容概要

本書介紹了數(shù)據(jù)結(jié)構(gòu)的基本概念和基本算法。全書共11章，主要內(nèi)容包括：緒論、線性表、棧和隊(duì)列、串、數(shù)組和廣義表、樹、圖、查找、內(nèi)排、文件和上機(jī)實(shí)驗(yàn)等。全書內(nèi)容深入淺出，條理清晰，概念清楚，邏輯推理嚴(yán)謹(jǐn)，內(nèi)容翔實(shí)，既注重?cái)?shù)據(jù)結(jié)構(gòu)和算法原理，又十分強(qiáng)調(diào)程序設(shè)計(jì)訓(xùn)練。書中算法都配有完整的C程序，程序結(jié)構(gòu)清晰，構(gòu)思精巧，所有程序都已在Win-TC2.0下編譯通過并能正確運(yùn)行，它們既是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的很好示例，也是很好的程序設(shè)計(jì)示例。本書配有大量的實(shí)例和圖示，并有豐富的習(xí)題，適于自學(xué)。    本書是供普通高等院校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本、?？茖W(xué)生使用的教材，也可供從事計(jì)算機(jī)工作者和其他希望學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的人員參考。

書籍目錄

第1章  緒論  1.1  什么是數(shù)據(jù)結(jié)構(gòu)  1.2  基本概念和常用術(shù)語(yǔ)  1.3  數(shù)據(jù)抽象和抽象數(shù)據(jù)類型    1.3.1  數(shù)據(jù)抽象    1.3.2  抽象數(shù)據(jù)類型    1.3.3  抽象數(shù)據(jù)類型描述和實(shí)現(xiàn)  1.4　算法和算法分析    1.4.1  算法及其性能標(biāo)準(zhǔn)    1.4.2  算法時(shí)間復(fù)雜度和漸近時(shí)間復(fù)雜度    1.4.3  算法的空間復(fù)雜度  小結(jié)  習(xí)題第2章　線性表  2.1　線性表概念  2.2  線性表的順序表示和實(shí)現(xiàn)    2.2.1  線性表的順序存儲(chǔ)結(jié)構(gòu)    2.2.2  線性表在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算  2.3  線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)    2.3.1  線性鏈表    2.3.2  循環(huán)鏈表    2.3.3  雙向循環(huán)鏈表    2.3.4  順序表和鏈表的比較  2.4  一元多項(xiàng)式的表示及相加　小結(jié)　習(xí)題第3章  棧和隊(duì)列  3.1  棧    3.1.1  棧的定義及其運(yùn)算    3.1.2  順序棧    3.1.3  多棧共享鄰接空間    3.1.4  鏈棧    3.1.5  棧的應(yīng)用舉例    3.1.6  棧與遞歸的實(shí)現(xiàn)  3.2  隊(duì)列    3.2.1  隊(duì)列的定義    3.2.2順序隊(duì)列    3.2.3  鏈隊(duì)列    3.2.4  隊(duì)列應(yīng)用舉例  小結(jié)  習(xí)題第4章  串  4.1  串的類型定義  4.2  串的定長(zhǎng)順序存儲(chǔ)  4.3  串的堆存儲(chǔ)結(jié)構(gòu)    4.3.1  串名存儲(chǔ)映像    4.3.2  堆存儲(chǔ)結(jié)構(gòu)    4.3.3  基于堆結(jié)構(gòu)的基本運(yùn)算  4.4  串的塊鏈存儲(chǔ)結(jié)構(gòu)  4.5  模式匹配  4.6  串的應(yīng)用舉例——正文編輯  小結(jié)  習(xí)題第5章  數(shù)組和廣義表  5.1  數(shù)組類型的定義  5.2  數(shù)組順序存儲(chǔ)和實(shí)現(xiàn)  5.3  矩陣壓縮存儲(chǔ)    5.3.1  對(duì)稱矩陣    5.3.2  三角矩陣    5.3.3  帶狀矩陣  5.4  稀疏矩陣    5.4.1  稀疏矩陣三元組表存儲(chǔ)    5.4.2  稀疏矩陣十字鏈表存儲(chǔ)    5.5  廣義表    5.5.1  廣義表的定義和基本運(yùn)算    5.5.2  廣義表的存儲(chǔ)    5.5.3  廣義表基本操作的實(shí)現(xiàn)  小結(jié)  習(xí)題第6章  樹  6.1  樹的基本概念    6.1.1  樹的定義    6.1.2　樹的邏輯表示方法    6.1.3  樹的基本術(shù)語(yǔ)　　……第7章　圖第8章　查找第9章　內(nèi)排序第10章　文件第11章　上機(jī)實(shí)驗(yàn)題參考文獻(xiàn)

章節(jié)摘錄

　　第1章 緒論　　“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國(guó)外是從1968年才開始設(shè)立的。在這之前，它的某些內(nèi)容曾在其他課程，如表處理語(yǔ)言中有所闡述。1968年在美國(guó)一些大學(xué)的計(jì)算機(jī)系的教學(xué)計(jì)劃中，雖然把數(shù)據(jù)結(jié)構(gòu)規(guī)定為一門課程，但對(duì)課程的范圍仍沒有作明確規(guī)定。當(dāng)時(shí)，數(shù)據(jù)結(jié)構(gòu)幾乎和圖論，特別是和表、樹的理論為同義語(yǔ)。隨后，數(shù)據(jù)結(jié)構(gòu)這個(gè)概念擴(kuò)充到包括網(wǎng)絡(luò)、集合代數(shù)論、格、關(guān)系等方面，從而變成了現(xiàn)在稱之為“離散結(jié)構(gòu)”的內(nèi)容。然而，由于數(shù)據(jù)必須在計(jì)算機(jī)中進(jìn)行處理，因此，不僅考慮數(shù)據(jù)本身的數(shù)學(xué)性質(zhì)，還必須考慮數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，這就進(jìn)一步擴(kuò)大了數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。近年來，隨著數(shù)據(jù)庫(kù)系統(tǒng)的不斷發(fā)展，在“數(shù)據(jù)結(jié)構(gòu)”課程中又增加了文件管理（特別是大型文件的組織等）的內(nèi)容?！　?968年美國(guó)唐．歐?？伺亟淌陂_創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作，從20世紀(jì)60年代末到70年代初，出現(xiàn)了大型程序，軟件也相對(duì)獨(dú)立，結(jié)構(gòu)程序設(shè)計(jì)成為程序設(shè)計(jì)方法學(xué)的主要內(nèi)容，人們就越來越重視數(shù)據(jù)結(jié)構(gòu)，并認(rèn)為程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計(jì)一種好的算法。從20世紀(jì)60年代中期到80年代初，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)?！　∧壳?，在我國(guó)數(shù)據(jù)結(jié)構(gòu)已經(jīng)不僅僅是計(jì)算機(jī)專業(yè)教學(xué)計(jì)劃中的核心課程之一，也是其他非計(jì)算機(jī)專業(yè)的主要選修課程之一?！　?.1 什么是數(shù)據(jù)結(jié)構(gòu)　　什么是數(shù)據(jù)結(jié)構(gòu)？這是一個(gè)難以直接回答的問題。一般來說，用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟：首先要從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（algorithm），最后編出程序、進(jìn)行測(cè)試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。為了說明這個(gè)問題，首先舉一個(gè)例子，然后再給出明確的含義。 假定有一個(gè)學(xué)生通訊錄，記錄了某校全體學(xué)生的姓名和相應(yīng)住址，現(xiàn)在要寫一個(gè)算法，要求當(dāng)給定任何一個(gè)學(xué)生的姓名時(shí)，該算法能夠查出該學(xué)生的住址。這樣一個(gè)算法的設(shè)計(jì)將完全取決于通訊錄中的學(xué)生姓名及相應(yīng)的住址是如何組織的，以及計(jì)算機(jī)是怎樣存儲(chǔ)通訊錄中的信息的。 如果通訊錄中的學(xué)生姓名是隨意排列的，其次序沒有任何規(guī)律，那么當(dāng)給定一個(gè)姓名時(shí)，則只能對(duì)通訊錄從頭開始逐個(gè)與給定的姓名比較，順序查對(duì)，直至找到所給定的姓名為止。這種方法相當(dāng)費(fèi)時(shí)間，效率很低。然而，若我們對(duì)學(xué)生通訊錄進(jìn)行適當(dāng)?shù)慕M織，按學(xué)生所在班級(jí)來排列，并且再造一個(gè)索引表，這個(gè)表用來登記每個(gè)班級(jí)學(xué)生姓名在通訊錄中的起始位置。這樣一來，情況將大為改善。這時(shí)，當(dāng)要查找某學(xué)生的住址時(shí)，則可先從索引表中查到該學(xué)生所在班級(jí)的學(xué)生姓名是從何處起始的，然后就從此起始處開始查找，而不必去查看其他部分的姓名。由于采用了新的結(jié)構(gòu)，于是就可以寫出一個(gè)完全不相同的算法。

編輯推薦

　　《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）》針對(duì)應(yīng)用型本科和高職高專學(xué)生的特點(diǎn)，結(jié)合編者多年的教學(xué)和編程實(shí)踐經(jīng)驗(yàn)，力圖用生動(dòng)、通俗易懂的語(yǔ)言，并結(jié)合大量的算法實(shí)例來講解各個(gè)知識(shí)點(diǎn)，便于讀者理解和掌握。　　《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）》通過各種實(shí)例具體講解如何運(yùn)用各種數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計(jì)方法，使學(xué)生不但可以印證許多基本概念，而且能加深理解，以激發(fā)學(xué)生的學(xué)習(xí)興趣，書中所有實(shí)例程序都己在Win-T02.0下編譯通過并能正確運(yùn)行?！　　稊?shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）》每章都配有小結(jié)和習(xí)題，便于讀者掌握各章的重點(diǎn)和難點(diǎn)，并進(jìn)行必要的訓(xùn)練；為了方便學(xué)生上機(jī)實(shí)訓(xùn)練習(xí)，《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言描述）》還專門設(shè)計(jì)了8套上機(jī)實(shí)驗(yàn)題，供學(xué)生在每章學(xué)習(xí)過后上機(jī)練習(xí)，鞏固所學(xué)知識(shí)。

圖書封面

評(píng)論、評(píng)分、閱讀與下載

---

    數(shù)據(jù)結(jié)構(gòu) PDF格式下載

---