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

前言

信息的表示是計算機科學的基礎。大多數(shù)計算機程序的主要目標是存儲和檢索信息。從節(jié)約運行時間和存儲空間的角度來看，這些程序必須精心組織數(shù)據(jù)，以支持高效的信息處理過程。而高效程序的設計是基于良好的信息組織和優(yōu)秀算法。因此研究數(shù)據(jù)結(jié)構(gòu)和算法以有效地支持程序的實現(xiàn)就成了計算機科學的核心問題。本書的目的是講授最基本的數(shù)據(jù)結(jié)構(gòu)，這些基本的數(shù)據(jù)結(jié)構(gòu)形成了一個工具箱。對于許多問題，工具箱里的數(shù)據(jù)結(jié)構(gòu)是理想的選擇。全書共分為8章。第l章介紹了什么是數(shù)據(jù)結(jié)構(gòu)，算法的定義以及如何分析一個算法的優(yōu)劣。第2章介紹線性表及其基本操作的實現(xiàn)。第3章主要介紹了棧和隊列的特點及其操作的實現(xiàn)。在本章中分別通過一個實例介紹棧和隊列的應用。第4章介紹了數(shù)組和稀疏矩陣的概念，以及稀疏矩陣的壓縮存儲、轉(zhuǎn)置和相乘操作的實現(xiàn)。第5章介紹樹與二叉樹的基本知識，以及二叉樹遍歷、哈夫曼樹的生成及哈夫曼編碼的構(gòu)造。第6章全面介紹圖和圖的算法，包括深度優(yōu)先和廣度優(yōu)先遍歷圖的算法，并對最小生成樹、拓撲排序和最短路徑算法做了介紹。第7章和第8章介紹了程序設計中常用的檢索和排序方法，分析比較了各種檢索和排序算法的效率。在介紹每種數(shù)據(jù)結(jié)構(gòu)時，都從其邏輯結(jié)構(gòu)入手，然后討論其不同的存儲結(jié)構(gòu)，接下來運用C語言給出算法的實現(xiàn)，最后解析各種算法。本書除在語言描述上力求深入淺出、通俗易懂外，對介紹的算法，均給出了其c語言實現(xiàn)，且在TURBOC2.0環(huán)境下調(diào)試通過。為方便讀者閱讀，在每行代碼前都加有行號。另外在每章開頭的“教學目標”欄目介紹了這一章的教學目標，告訴讀者本章將要學到什么內(nèi)容，且讓讀者在學習完該章之后可以判斷自己是否達到了這些目標。同時教學目標還幫助讀者建立信心并使學習效果得到鞏固。本書在編寫過程中得到了很多朋友的幫助，在此表示感謝。同時要感謝中國電力出版社以及白立軍編輯的支持和幫助。當然還要感謝這些年來選修數(shù)據(jù)結(jié)構(gòu)課程的學生，是他們給我們提供了很多講授數(shù)據(jù)結(jié)構(gòu)的建議。本書由張振宇、崔青、劉淑嫻、蔣秀英、王鋒共同編寫。其中第1章和第3章由崔青編寫。劉淑嫻編寫了第5章和第7章。張振宇編寫了第2章、第4章、第6章，王鋒和蔣秀英編寫了第8章，并對全書進行了統(tǒng)稿。書中包含了編者講授數(shù)據(jù)結(jié)構(gòu)課程的經(jīng)驗與思考。希望讀者通過對本書的學習，對理解和掌握數(shù)據(jù)結(jié)構(gòu)的概念以及數(shù)據(jù)結(jié)構(gòu)的相關算法，提高分析和解決問題的能力有所幫助。也希望讀者能把自己的體會、經(jīng)驗和意見及時地反饋給我們。由于水平所限，書中不妥之處在所難免，敬請各位專家和讀者批評指正。

內(nèi)容概要

本書介紹了線性表、棧、隊列、樹和圖等幾種最基本的數(shù)據(jù)結(jié)構(gòu)和各種檢索、排序方法。對每一種數(shù)據(jù)結(jié)構(gòu)給出了其C語言實現(xiàn)。    本書除在語言描述上力求深入淺出、簡潔明了、通俗易懂外，對介紹的算法，均給出了其C語言實現(xiàn)，而且在每行代碼前都加有行號，方便讀者閱讀。另外在每章開頭的“教學目標”介紹了這一章的教學目標，告訴讀者本章將要學到什么內(nèi)容，并且讓讀者在學習完該章之后可以判斷自己是否達到了這些目標。同時教學目標還幫助讀者建立信心并使學習效果得到鞏固。    本書可作為高等本科學校、高等?？茖W校、成人高等學校及本科院校舉辦的二級職業(yè)技術(shù)學院、繼續(xù)教育學院的教材，還可作為數(shù)據(jù)結(jié)構(gòu)愛好者的自學參考書。

書籍目錄

前言第1章　緒論　1.1  概述　1.2　基本概念　1.3　算法與算法分析　1.4  習題第2章　線性表　2.1  線性表　2.2　線性表的順序存儲結(jié)構(gòu)及其實現(xiàn)　　2.2.1　順序表描述　　2.2.2　順序表基本操作的實現(xiàn)　2.3　單鏈表　　2.3.1　單鏈表描述　　2.3.2　單鏈表基本操作的實現(xiàn)　2.4　雙向鏈表　2.5　循環(huán)鏈表　2.6  習題第3章　棧和隊列　3.1  ?！　?.1.1  順序棧　　3.1.2　鏈式?！　?.1.3　棧應用舉例　　3.1.4　棧與遞歸　3.2  隊列　　3.2.1  順序隊列　　3.2.2　鏈式隊列　　3.2.3  隊列應用舉例  3.3  習題第4章　數(shù)組與稀疏矩陣  4.1  數(shù)組  4.2　稀疏矩陣　　4.2.1　矩陣的壓縮存儲　　4.2.2　稀疏矩陣運算的實現(xiàn)  4.3  習題第5章　樹與二叉樹　5.1  樹　　5.1.1　樹的基本概念　　5.1.2　樹的存儲結(jié)構(gòu)　5.2　二叉樹　　5.2.1  定義及主要特性　　5.2.2　二叉樹的存儲結(jié)構(gòu)  5.3　遍歷二叉樹  5.4　線索二叉樹  5.5　哈夫曼樹　　5.5.1　基本概念　　5.5.2　哈夫曼算法　　5.5.3　哈夫曼編碼　5.6  習題第6章  圖　6.1  圖的基本概念和存儲結(jié)構(gòu)　　6.1.1  圖的定義及術(shù)語　　6.1.2  圖的存儲結(jié)構(gòu)　6.2  圖的遍歷　　6.2.1　深度優(yōu)先遍歷　　6.2.2　廣度優(yōu)先遍歷  6.3　最小生成樹　　6.3.1　Prim算法　　6.3.2　Kruskal算法　6.4　拓撲排序　6.5  最短路徑　　6.5.1　單源最短路徑　　6.5.2　每對頂點之間的最短路徑　6.6  習題第7章　檢索　7.1  概述　7.2　順序檢索　7.3　二分法檢索　7.4　二叉排序樹　　7.4.1　二叉排序樹　　7.4.2　平衡二叉樹　7.5  散列方法　　7.5.1　散列表與散列函數(shù)　　7.5.2　處理沖突的辦法　　……第8章　排序參考文獻

章節(jié)摘錄

插圖：第4章　數(shù)組與稀疏矩陣數(shù)組是一種常見的數(shù)據(jù)結(jié)構(gòu)。幾乎所有的高級程序設計語言都將數(shù)組類型作為固有類型。本章在4.1節(jié)介紹數(shù)組的順序存儲結(jié)構(gòu)和數(shù)組元素的尋址公式推導過程。4.2節(jié)首先介紹特殊矩陣和稀疏矩陣的壓縮存儲，以節(jié)省存儲空間。然后介紹在壓縮存儲表示方式下，稀疏矩陣的轉(zhuǎn)置和相乘運算的實現(xiàn)。4.1　數(shù)組直觀上看，數(shù)組可看成是一組偶對，即下標和值。對每一個有定義的下標，都有一個與該下標相關聯(lián)的值。一維數(shù)組的值對應一個下標，二維數(shù)組則對應兩個，依此類推，n維數(shù)組的值對應n個下標。數(shù)組是一種“均勻”結(jié)構(gòu)，即數(shù)組中每個元素必須具有同樣的類型。數(shù)組又是一種隨機存取結(jié)構(gòu)，只要給定一組下標，就可以訪問與這組下標相關聯(lián)的值。就數(shù)組而言，我們所關心的操作主要是值檢索和值存儲。在內(nèi)存中，數(shù)組元素是連續(xù)存儲的。數(shù)組的第一個元素的地址稱為基地址，也稱為數(shù)組的起始地址。當用一組連續(xù)的存儲單元存放多維數(shù)組的元素時會碰到一個次序問題。

編輯推薦

《數(shù)據(jù)結(jié)構(gòu)》由中國電力出版社出版的。

圖書封面

評論、評分、閱讀與下載

---

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

---