數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程

前言

　　1997年5月，一臺名為“深藍(lán)”的超級計算機(jī)將棋盤上的一個兵走到C4位置時，人類有史以來最偉大的國際象棋名家卡斯帕羅夫不得不沮喪地服輸，上世紀(jì)末的一場人機(jī)大戰(zhàn)終于以計算機(jī)的微弱優(yōu)勢取勝。2003年4月14日人類基因組計劃宣告完成，后基因組時代已經(jīng)到來，各種生物學(xué)成果在計算中不斷出現(xiàn)。這些成果使得人們再一次認(rèn)識到計算的重要性。如今，計算技術(shù)已廣泛地應(yīng)用到各個領(lǐng)域，后因特網(wǎng)時代已經(jīng)到來，以信息化帶動工業(yè)化已成為時代的主題。計算機(jī)程序設(shè)計是計算技術(shù)的重要內(nèi)容，而數(shù)據(jù)結(jié)構(gòu)是計算機(jī)程序設(shè)計的重要理論基礎(chǔ)，它不僅是計算機(jī)學(xué)科的核心課程，而且已成為其他專業(yè)的熱門選修課。數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目標(biāo)是學(xué)會分析需要計算機(jī)處理的數(shù)據(jù)對象的特性，以選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，從而選擇相應(yīng)的算法；初步掌握算法性能分析的方法。通過本課程的學(xué)習(xí)，使學(xué)生獲得更進(jìn)一步的程序設(shè)計技能訓(xùn)練，提高編程能力?！　￠L久以來，由于數(shù)據(jù)結(jié)構(gòu)課程自身的抽象性和嚴(yán)密性，以及數(shù)據(jù)結(jié)構(gòu)開設(shè)的時間通常在剛?cè)氪髮W(xué)的第二學(xué)期，教師大都感覺數(shù)據(jù)結(jié)構(gòu)課程難教，學(xué)生普遍反映數(shù)據(jù)結(jié)構(gòu)課程難學(xué)，學(xué)生很難獨立完成算法的實現(xiàn)?；谏鲜鰡栴}，我們在編寫本教材時充分考慮了學(xué)生的知識結(jié)構(gòu)和教師的教學(xué)方法。本教材的編寫宗旨是，既注重原理又注重實踐，既注重抽象思維又注重形象思維，既方便自學(xué)又方便教學(xué)。本書的編寫具有以下特色?！　?.首次嘗試在計算機(jī)專業(yè)的核心基礎(chǔ)課程中增加計算機(jī)科學(xué)知識，使學(xué)生在學(xué)習(xí)本教材的過程中，不但能學(xué)到專業(yè)知識，還能了解計算機(jī)科學(xué)發(fā)展歷史的相關(guān)知識和數(shù)據(jù)結(jié)構(gòu)課程與其他課程的聯(lián)系。對提高學(xué)生學(xué)習(xí)本課程的興趣，拓寬學(xué)生的知識面大有益處。　　2.在教材中使用“A思考”標(biāo)志，提出問題拓展學(xué)生思維。思考不同于習(xí)題，習(xí)題的作用代替不了思考。因為習(xí)題在每個章節(jié)之后，一般要等講完一個章節(jié)才會遇到，因此習(xí)題對于課堂教學(xué)是滯后的。采用提示思考的方式，可以在教學(xué)中恰到好處地啟發(fā)學(xué)生的思維。教材使用“A思考”標(biāo)志通常有三種情況：一種是提醒學(xué)生需要注意的內(nèi)容，一種是啟發(fā)學(xué)生基于當(dāng)前知識基礎(chǔ)進(jìn)一步思考的內(nèi)容，第三種是提示本教材沒有講授的內(nèi)容，以引導(dǎo)學(xué)有余力的學(xué)生拓展自身的知識面。　　3.以學(xué)生為主體設(shè)計數(shù)據(jù)結(jié)構(gòu)課程的實踐內(nèi)容。數(shù)據(jù)結(jié)構(gòu)課程是計算機(jī)專業(yè)的一門重要的基礎(chǔ)課程，其性質(zhì)是實踐性的。如何引導(dǎo)學(xué)生利用所學(xué)概念和算法進(jìn)行實踐是這門課程成敗的關(guān)鍵，為此我們采取了兩個措施：一是注重概念和算法的應(yīng)用背景，對每種數(shù)據(jù)結(jié)構(gòu)都有應(yīng)用實例，有代碼實現(xiàn)：二是在基本運算的實現(xiàn)代碼中留有要求學(xué)生自己實現(xiàn)代碼的部分。這就要求學(xué)生不但要讀懂已經(jīng)實現(xiàn)的部分代碼，還要自己設(shè)計代碼，最后才能得到一個完整實現(xiàn)的系統(tǒng)。這有利于提高學(xué)生對數(shù)據(jù)結(jié)構(gòu)概念和算法的理解，真正提高學(xué)生的編程能力。每章后的上機(jī)實習(xí)就由這兩部分內(nèi)容組成，本書中提供的實現(xiàn)代碼均在VC6.0中編譯通過。　　本書介紹了各種最常用的數(shù)據(jù)結(jié)構(gòu)，闡述了各種數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的邏輯關(guān)系，討論了它們在計算機(jī)中的存儲表示，.以及基于這些數(shù)據(jù)結(jié)構(gòu)的運算和實際的執(zhí)行算法，并對算法的效率進(jìn)行了簡要的分析和討論。

內(nèi)容概要

　　《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》系統(tǒng)地介紹了各種常用的數(shù)據(jù)結(jié)構(gòu)及排序、查找的各種算法，闡述了各種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其基本運算。各數(shù)據(jù)結(jié)構(gòu)類型和基本運算，首先用類C代碼描述，然后用可編譯運行的C語言代碼實現(xiàn)，并給出了詳細(xì)的注釋。全書既注重原理又強(qiáng)調(diào)實踐，配有大量的圖表和習(xí)題，概念講解清楚、邏輯性強(qiáng)、可讀性好?！稊?shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》的特點在于，首次嘗試在基礎(chǔ)課程中介紹計算機(jī)科學(xué)發(fā)展史知識，采用腳注的形式使學(xué)生了解計算機(jī)科學(xué)史知識和數(shù)據(jù)結(jié)構(gòu)課程與其他課程之間的關(guān)系；附有大量以“思考”形式出現(xiàn)的問題，以便在恰當(dāng)?shù)臅r機(jī)引導(dǎo)學(xué)生思考，啟發(fā)思維；以學(xué)生為主體精心設(shè)計了數(shù)據(jù)結(jié)構(gòu)課程的實踐教學(xué)內(nèi)容。

書籍目錄

第1章 緒論1.1 數(shù)據(jù)結(jié)構(gòu)基本概念1.1.1 數(shù)據(jù)結(jié)構(gòu)實例1.1.2 數(shù)據(jù)結(jié)構(gòu)概念1.2 算法分析基本概念1.2.1 算法1.2.2 算法效率分析1.2.3 算法效率評價習(xí)題1第2章 線性表2.1 概念和運算2.1.1 線性表概念2.1.2 線性表基本運算2.2 順序存儲結(jié)構(gòu)2.2.1 順序表2.2.2 順序表基本運算2.3 鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1 線性鏈表2.3.2 線性鏈表基本運算2.4 線性表應(yīng)用2.5 基本運算實現(xiàn)2.5.1 順序表基本運算實現(xiàn)2.5.2 鏈表基本運算實現(xiàn)上機(jī)實習(xí)線性表習(xí)題2第3章 棧3.1 概念和運算3.1.1 棧概念3.1.2 ?；具\算3.2 存儲和實現(xiàn)3.2.1 順序棧3.2.2 鏈棧3.3 棧應(yīng)用3.3.1 數(shù)制轉(zhuǎn)換3.3.2 表達(dá)式求值3.3.3 棧和遞歸3.4 棧基本運算實現(xiàn)3.4.1 順序棧基本運算實現(xiàn)3.4.2 鏈?；具\算實現(xiàn)上機(jī)實習(xí)棧習(xí)題3第4章 隊列4.1 概念和基本運算4.1.1 隊列概念4.1.2 隊列基本運算4.2 順序存儲結(jié)構(gòu)和運算4.3 循環(huán)隊列4.4 鏈隊列4.5 隊列應(yīng)用4.6 隊列基本運算實現(xiàn)4.6.1 循環(huán)隊列運算實現(xiàn)4.6.2 鏈隊列運算實現(xiàn)上機(jī)實習(xí)隊列習(xí)題4第5章 線性結(jié)構(gòu)推廣5.1 串5.1.1 定義5.1.2 基本運算5.1.3 定長順序存儲5.1.4 模式匹配5.1.5 鏈?zhǔn)酱鎯Y(jié)構(gòu)5.2 數(shù)組5.2.1 定義和存儲5.2.2 矩陣壓縮存儲5.3 廣義表5.3.1 定義5.3.2 存儲5.4 串的基本運算實現(xiàn)上機(jī)實習(xí)串習(xí)題5第6章 樹6.1 樹的概念和基本運算6.1.1 定義6.1.2 基本術(shù)語6.1.3 基本運算6.2 樹的存儲6.3 二叉樹的概念和性質(zhì)6.3.1 概念和基本運算6.3.2 性質(zhì)6.3.3 存儲6.4 二叉樹遍歷6.5 線索二叉樹6.6 樹和二叉樹6.6.1 樹與二叉樹的轉(zhuǎn)換6.6.2 二叉樹與森林的轉(zhuǎn)換6.7 哈夫曼樹及其應(yīng)用6.8 二叉樹基本運算6.9 二叉樹基本運算實現(xiàn)上機(jī)實習(xí)二叉樹習(xí)題6第7章圖7.1 概念和基本運算7.1.1 圖的概念7.1.2 圖的基本運算7.2 圖存儲7.2.1 數(shù)組表示法7.2.2 鄰接表7.3 圖遍歷7.3.1 連通圖的深度優(yōu)先搜索遍歷7.3.2 廣度優(yōu)先搜索7.4 最小生成樹7.4.1 Prim算法7.4.2 Kruskal算法7.5 單源點最短路徑7.6 圖的基本運算實現(xiàn)上機(jī)實習(xí)圖習(xí)題7第8章排序8.1 排序基本概念8.2 插入類排序8.2.1 直接插入排序8.2.2 折半插入排序8.2.3 希爾排序8.3 交換類排序8.3.1 冒泡排序8.3.2 快速排序8.4 選擇類排序8.4.1 簡單選擇排序8.4.2 樹型選擇排序8.4.3 堆排序8.5 歸并排序8.6 各種排序方法的綜合比較8.7 外部排序8.8 各類排序算法的綜合實現(xiàn)上機(jī)實習(xí)排序習(xí)題8第9章 查找9.1 基本概念9.2 靜態(tài)查找表9.2.1 順序查找法9.2.2 折半查找法9.2.3 分塊查找法9.3 動態(tài)查找表9.4 哈希表9.4.1 基本概念9.4.2 哈希函數(shù)構(gòu)造方法9.4.3 沖突處理方法9.4.4 哈希表查找9.5 查找表實現(xiàn)上機(jī)實習(xí)查找表習(xí)題9參考文獻(xiàn)

章節(jié)摘錄

　　綜上所述，非數(shù)值計算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是要研究諸如例1.1 、例1.2 和例1.3 所描述的數(shù)據(jù)之間的這些關(guān)系，以及通過數(shù)據(jù)之間的這些關(guān)系可以方便地進(jìn)行何種運算。因此，簡單地說數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)之間的關(guān)系及其運算的學(xué)科?！　?shù)據(jù)結(jié)構(gòu)作為一門獨立的學(xué)科始于1968年，但在此之前有關(guān)內(nèi)容已散見于編譯原理和操作系統(tǒng)的教材之中。1968年，美國的圖靈獎”獲得者克努特（D.E.Knuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他的著作《計算機(jī)程序設(shè)計藝術(shù)》第1卷《基本算法》是第一本比較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。20世紀(jì)60年代末到70年代，出現(xiàn)了大型程序，軟件也相對獨立，結(jié)構(gòu)程序設(shè)計即成為程序設(shè)計的主要內(nèi)容。人們越來越重視數(shù)據(jù)結(jié)構(gòu)，著名的瑞士計算機(jī)科學(xué)家沃斯（N.Wirth）教授指出，算法斗數(shù)據(jù)結(jié)構(gòu)：程序。70年代中期到80年代初，各種版本的數(shù)據(jù)結(jié)構(gòu)著作相繼出現(xiàn)。目前，數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié)，一方面，面向各專門領(lǐng)域中特殊問題的數(shù)據(jù)結(jié)構(gòu)得到研究和發(fā)展，例如多維圖形數(shù)據(jù)結(jié)構(gòu)等；另一方面，從抽象數(shù)據(jù)類型和面向?qū)ο蟮挠^點來討論數(shù)據(jù)結(jié)構(gòu)已成為一種新的趨勢，越來越為人們所重視?！　奈覈嬎銠C(jī)教學(xué)現(xiàn)狀來看，數(shù)據(jù)結(jié)構(gòu)不僅是計算機(jī)專業(yè)教學(xué)計劃中的核心課程之一，而且已逐步成為非計算機(jī)專業(yè)的主要選修課程之一。數(shù)據(jù)結(jié)構(gòu)又是一門介于數(shù)學(xué)、計算機(jī)硬件和計算機(jī)軟件三者之間的一門核心課程。在計算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)不僅是一般非數(shù)值計算程序設(shè)計的基礎(chǔ)，而且是設(shè)計和實現(xiàn)匯編語言、編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)，以及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。打好數(shù)據(jù)結(jié)構(gòu)課程的扎實基礎(chǔ)，對于學(xué)習(xí)計算機(jī)專業(yè)的其他課程，例如操作系統(tǒng)、編譯原理、數(shù)據(jù)庫管理系統(tǒng)、軟件工程和人工智能等都是十分有益的?！　?.1 2數(shù)據(jù)結(jié)構(gòu)概念　　1.數(shù)據(jù)　　數(shù)據(jù)是信息的載體，是對客觀事物的符號表示。通俗地說，凡是能被計算機(jī)識別、存取和加工處理的符號、.字符、圖形、圖像、聲音、視頻信號、程序等一切信息都可以稱為數(shù)據(jù)。數(shù)據(jù)可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。數(shù)值數(shù)據(jù)包括整數(shù)、實數(shù)、浮點數(shù)、復(fù)數(shù)等，主要用于科學(xué)計算和商務(wù)處理等；非數(shù)值數(shù)據(jù)包括文字、符號、圖形、圖像、動畫、語音、視頻信號等。隨著多媒體技術(shù)的飛速發(fā)展，計算機(jī)中處理的非數(shù)值數(shù)據(jù)越來越多?！　?.數(shù)據(jù)元素　　數(shù)據(jù)元素是對現(xiàn)實世界中某獨立個體的數(shù)據(jù)描述，是數(shù)據(jù)的基本單位。在計算機(jī)中，數(shù)據(jù)元素通常作為一個整體來處理。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成，在C程序設(shè)計中一個數(shù)據(jù)元素可以由一個stmct表示。數(shù)據(jù)項是具有獨立意義的最小數(shù)據(jù)單位，是對數(shù)據(jù)元素屬性的描述?！　　?/pre>




編輯推薦
　　《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》可作為高等學(xué)院校非計算機(jī)專業(yè)教材或高孫、高專院校計算機(jī)專業(yè)教材，也可作為成人教育(面授或函授)的教材，還可為參加全國計算機(jī)軟件水平程序員等級考試提供參考，亦可供廣大從事計算機(jī)應(yīng)用的科技人員參考。





圖書封面






評論、評分、閱讀與下載



還沒讀過(11)
勉強(qiáng)可看(823)
一般般(140)
內(nèi)容豐富(5822)
強(qiáng)力推薦(477)


 


    數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程 PDF格式下載