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

前言

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

書籍目錄

第1章 緒論1.1 數(shù)據(jù)結(jié)構(gòu)基本概念1.1.1 數(shù)據(jù)結(jié)構(gòu)實(shí)例1.1.2 數(shù)據(jù)結(jié)構(gòu)概念1.2 算法分析基本概念1.2.1 算法1.2.2 算法效率分析1.2.3 算法效率評價(jià)習(xí)題1第2章 線性表2.1 概念和運(yùn)算2.1.1 線性表概念2.1.2 線性表基本運(yùn)算2.2 順序存儲結(jié)構(gòu)2.2.1 順序表2.2.2 順序表基本運(yùn)算2.3 鏈?zhǔn)酱鎯Y(jié)構(gòu)2.3.1 線性鏈表2.3.2 線性鏈表基本運(yùn)算2.4 線性表應(yīng)用2.5 基本運(yùn)算實(shí)現(xiàn)2.5.1 順序表基本運(yùn)算實(shí)現(xiàn)2.5.2 鏈表基本運(yùn)算實(shí)現(xiàn)上機(jī)實(shí)習(xí)線性表習(xí)題2第3章 棧3.1 概念和運(yùn)算3.1.1 棧概念3.1.2 棧基本運(yùn)算3.2 存儲和實(shí)現(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 ?；具\(yùn)算實(shí)現(xiàn)3.4.1 順序棧基本運(yùn)算實(shí)現(xiàn)3.4.2 鏈?；具\(yùn)算實(shí)現(xiàn)上機(jī)實(shí)習(xí)棧習(xí)題3第4章 隊(duì)列4.1 概念和基本運(yùn)算4.1.1 隊(duì)列概念4.1.2 隊(duì)列基本運(yùn)算4.2 順序存儲結(jié)構(gòu)和運(yùn)算4.3 循環(huán)隊(duì)列4.4 鏈隊(duì)列4.5 隊(duì)列應(yīng)用4.6 隊(duì)列基本運(yùn)算實(shí)現(xiàn)4.6.1 循環(huán)隊(duì)列運(yùn)算實(shí)現(xiàn)4.6.2 鏈隊(duì)列運(yùn)算實(shí)現(xiàn)上機(jī)實(shí)習(xí)隊(duì)列習(xí)題4第5章 線性結(jié)構(gòu)推廣5.1 串5.1.1 定義5.1.2 基本運(yùn)算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 串的基本運(yùn)算實(shí)現(xiàn)上機(jī)實(shí)習(xí)串習(xí)題5第6章 樹6.1 樹的概念和基本運(yùn)算6.1.1 定義6.1.2 基本術(shù)語6.1.3 基本運(yùn)算6.2 樹的存儲6.3 二叉樹的概念和性質(zhì)6.3.1 概念和基本運(yùn)算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 二叉樹基本運(yùn)算6.9 二叉樹基本運(yùn)算實(shí)現(xiàn)上機(jī)實(shí)習(xí)二叉樹習(xí)題6第7章圖7.1 概念和基本運(yùn)算7.1.1 圖的概念7.1.2 圖的基本運(yùn)算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 單源點(diǎn)最短路徑7.6 圖的基本運(yùn)算實(shí)現(xiàn)上機(jī)實(shí)習(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 各類排序算法的綜合實(shí)現(xiàn)上機(jī)實(shí)習(xí)排序習(xí)題8第9章 查找9.1 基本概念9.2 靜態(tài)查找表9.2.1 順序查找法9.2.2 折半查找法9.2.3 分塊查找法9.3 動(dòng)態(tài)查找表9.4 哈希表9.4.1 基本概念9.4.2 哈希函數(shù)構(gòu)造方法9.4.3 沖突處理方法9.4.4 哈希表查找9.5 查找表實(shí)現(xiàn)上機(jī)實(shí)習(xí)查找表習(xí)題9參考文獻(xiàn)

章節(jié)摘錄

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

編輯推薦

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

圖書封面

評論、評分、閱讀與下載

---

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

---