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

前言

　　近20年里，計算機學(xué)科有了很大的發(fā)展，人們普遍認(rèn)為，“計算機科學(xué)”這個名字已經(jīng)難以涵蓋該學(xué)科的內(nèi)容，因此，改稱其為計算學(xué)科（Computing Discipline）。在我國本科教育中，1996年以前曾經(jīng)有計算機軟件專業(yè)和計算機及應(yīng)用專業(yè)，之后被合并為計算機科學(xué)與技術(shù)專業(yè)。2004年以來，教育部計算機科學(xué)與技術(shù)專業(yè)教學(xué)指導(dǎo)分委員會根據(jù)我國計算機專業(yè)教育和計算學(xué)科的現(xiàn)狀，為更好地滿足社會對計算機專業(yè)人才的需求，發(fā)布了《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范（試行）》（以下簡稱《規(guī)范》），提出在計算機科學(xué)與技術(shù)專業(yè)名稱之下，構(gòu)建計算機科學(xué)、計算機工程、軟件工程和信息技術(shù)四大專業(yè)方向。《規(guī)范》中四大專業(yè)方向的分類，在于鼓勵辦學(xué)單位根據(jù)自己的情況設(shè)定不同的培養(yǎng)方案，以培養(yǎng)更具針對性和特色的計算機專業(yè)人才?！　榕浜稀兑?guī)范》的實施，落實中央“提高高等教育質(zhì)量”的精神，我們規(guī)劃了“面向計算機科學(xué)與技術(shù)專業(yè)規(guī)范系列教材”。本系列教材面向全新的計算學(xué)科，針對我國高等院校逐步向新的計算機科學(xué)與技術(shù)專業(yè)課程體系過渡的趨勢編寫，在知識選擇、內(nèi)容組織和教學(xué)方法等方面滿足《規(guī)范》的要求，并與國際接軌。本套教材具有以下幾個特點：　?。?）體現(xiàn)《規(guī)范》的基本思想，滿足其課程要求。為使教材符合我國高等院校的教學(xué)實際，編委會根據(jù)《規(guī)范》的要求規(guī)劃本套教材，廣泛征集在國內(nèi)知名高校中從事一線教學(xué)和科研工作、經(jīng)驗豐富的優(yōu)秀教師承擔(dān)編寫任務(wù)?！　。?）圍繞“提高教育質(zhì)量”的宗旨開發(fā)教材。為了確保“精品”，本系列教材的出版不走盲目擴大的路子，每本教材的選題都將由編委會集體論證，并由一名編委擔(dān)任責(zé)任編委，最大程度地保證這套教材的編寫水準(zhǔn)和出版質(zhì)量。　?。?）教材內(nèi)容的組織科學(xué)、合理。體系得當(dāng)。本套教材的編寫注重研究學(xué)科的新發(fā)展和新成果，能夠根據(jù)不同類型人才培養(yǎng)需求，合理地進(jìn)行內(nèi)容取舍、組織和敘述，還精心設(shè)計了配套的實驗體系和練習(xí)體系?！　。?）教材風(fēng)格鮮明。本套教材按4個專業(yè)方向統(tǒng)一規(guī)劃，分批組織，陸續(xù)出版。教材的編寫體現(xiàn)了現(xiàn)代教育理念，探討先進(jìn)的教學(xué)方法。　?。?）開展教材立體化建設(shè)。根據(jù)需要配合主教材的建設(shè)適時開發(fā)實驗教材、教師參考書、學(xué)生參考書、電子參考資料等教輔資源，為教學(xué)實現(xiàn)多方位服務(wù)?！　∥覀冎孕南Ｍ鞠盗薪滩哪軌驗槲覈叩仍盒Ｓ嬎銠C科學(xué)與技術(shù)等專業(yè)的教學(xué)作出貢獻(xiàn)，歡迎廣大讀者廣為選用。

內(nèi)容概要

《數(shù)據(jù)結(jié)構(gòu)與算法》以基本數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計策略為知識單元，系統(tǒng)地介紹了數(shù)據(jù)結(jié)構(gòu)的知識與應(yīng)用、計算機算法的設(shè)計與分析方法，主要內(nèi)容包括線性表、樹、圖和廣義表、算法設(shè)計策略以及查找與排序算法等?！稊?shù)據(jù)結(jié)構(gòu)與算法》注重理論與實踐相結(jié)合，內(nèi)容深入淺出，可以作為高等院校計算機學(xué)科工程碩士及相關(guān)層次的教材或參考書，同時對計算機科技工作者也有參考價值。

作者簡介

　　吳躍，四川省學(xué)術(shù)和技術(shù)帶頭人、國務(wù)院政府特殊津貼專家、教育部計算機科學(xué)與技術(shù)專業(yè)教學(xué)指導(dǎo)委員會委員、四川省教學(xué)名師、四川省高等學(xué)校省級教學(xué)團(tuán)隊計算機專業(yè)核心課程教學(xué)團(tuán)隊帶頭人，從事數(shù)據(jù)結(jié)構(gòu)與算法課程的教學(xué)工作20余年，主持了國家863教育部博士點基金、國防重點和省科技攻關(guān)等十余項科研項目，發(fā)表學(xué)術(shù)論文（70余篇，獲省部級科研獎5項、國家級教學(xué)成果獎2項、已編著出版《計算機操作系統(tǒng)》教材一部。

書籍目錄

出版者的話序言前言教學(xué)建議第1章 緒論1.1 計算機問題求解過程1.2 迷宮問題1.3 數(shù)據(jù)結(jié)構(gòu)1.3.1 數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容1.3.2 數(shù)據(jù)結(jié)構(gòu)概念1.4 算法1.4.1 算法概念及特性1.4.2 算法描述1.4.3 算法分析1.5 本章小結(jié)1.6 習(xí)題第2章 線性表2.1 線性表2.1.1 線性表的定義2.1.2 線性表的順序存儲2.1.3 線性表的鏈?zhǔn)酱鎯?.1.4 鏈表的各種變形2.1.5 線性表的應(yīng)用2.2 線2.2.1 線的定義2.2.2 線的順序存儲2.2.3 線的鏈?zhǔn)酱鎯?.2.4 線的應(yīng)用2.3 隊列2.3.1 隊列的定義2.3.2 隊列的順序存儲2.3.3 隊列的鏈?zhǔn)酱鎯?.3.4 優(yōu)先隊列2.3.5 隊列的應(yīng)用2.4 數(shù)組2.4.1 數(shù)組的定義2.4.2 數(shù)組的表示和實現(xiàn)2.4.3 數(shù)組的應(yīng)用2.5 本章小結(jié)2.6 習(xí)題第3章 樹3.1 二叉樹3.1.1 二叉樹的基本概念和性質(zhì)3.1.2 二叉樹的存儲結(jié)構(gòu)3.1.3 二叉樹的遍歷3.2 二叉樹的變形3.2.1 線索二叉樹3.2.2 二叉排序樹3.2.3 平衡二叉樹3.2.4 赫夫曼樹及赫夫曼編碼3.3 樹和森林3.3.1 樹和森林的定義3.3.2 樹和森林的存儲結(jié)構(gòu)3.3.3 樹和森林的基本操作3.4 樹的變形3.4.1 四叉樹3.4.2 B樹3.4.3 2-3樹3.5 樹的應(yīng)用3.5.1 算術(shù)表達(dá)式3.5.2 堆排序3.5.3 決策分析3.6 本章小結(jié)3.7 習(xí)題第4章 圖和廣義表4.1 圖簡介4.1.1 基本概念和術(shù)語4.1.2 圖的應(yīng)用4.2 圖的存儲結(jié)構(gòu)4.2.1 圖的順序存儲結(jié)構(gòu)4.2.2 圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)4.3 圖的遍歷4.3.1 深度優(yōu)先遍歷4.3.2 廣度優(yōu)先遍歷4.4 圖的應(yīng)用4.4.1 最小生成樹4.4.2 拓?fù)渑判?.4.3 關(guān)鍵路徑4.4.4 最短路徑4.5.1 一義表4.5.1 一義表的定義4.5.2 一義表的存儲結(jié)構(gòu)4.5.3 義表的遍歷4.5.4 廣義表的運算4.6 本章小結(jié)4.7 習(xí)題第5章 算法設(shè)計策略5.1 算法分析技術(shù)5.2 直接法5.2.1 窮舉法5.2.2 遞推法5.2.3 迭代法5.3 分治法5.3.1 分治法的基本思想5.3.2 斯特拉森矩陣乘法5.4 貪心法5.4.1 貪心法的基本思想5.4.2 背包問題5.5 動態(tài)規(guī)劃法5.5.1 動態(tài)規(guī)劃法的基本思想5.5.2 矩陣連乘問題5.6 回溯法5.6.1 回溯法的基本思想5.6.2 回溯法的形式化描述5.6.3 k皇后問題5.7 分支限界法5.7.1 分支限界法的基本思想5.7.2 貨郎擔(dān)問題5.8 本章小結(jié)5.9 習(xí)題第6章 查找6.1 順序表的查找6.1.1 傾序查找6.1.2 分查找6.2 索引表的查找6.2.1 索引表的基本概念6.2.2 索引表的順序查找6.2.3 索引表的二分查找6.2.4 索引表的樹組織查找6.3 散列表的查找6.3.1 基本概念6.3.2 散列函數(shù)6.3.3 突處理6.3.4 散列查找與性能分析6.4 本章小結(jié)6.5 習(xí)題第7章 排序7.1 排序的基本概念7.2 插入排序7.2.1 直接插入排序7.2.2 分插入排序7.2.3 希爾排序7.3 交換排序7.3.1 冒泡排序7.3.2 快速排序7.4 選擇排序7.4.1 簡單選擇排序7.4.2 樹形選擇排序7.52 路歸并排序7.6 基數(shù)排序7.6.1 多關(guān)鍵字排序7.6.2 鏈?zhǔn)交鶖?shù)排序7.7 各排序方法的比較7.8 本章小結(jié)7.9 題參考文獻(xiàn)

章節(jié)摘錄

　　性表的存儲方式除了常用的順序存儲外，鏈?zhǔn)酱鎯σ彩且环N常見的方式。本小節(jié)將介紹一般線性表的幾種鏈?zhǔn)酱鎯崿F(xiàn)方式，如單鏈表、帶頭結(jié)點的單鏈表、循環(huán)鏈表等。　　線性表的鏈?zhǔn)酱鎯κ侵赣靡唤M任意的存儲單元（可以連續(xù)也可以不連續(xù)）存儲線性表中　的數(shù)據(jù)元素。數(shù)據(jù)元素在存儲空間表示時通常稱為結(jié)點。　　前面討論的順序表用物理位置上的相鄰關(guān)系來表示結(jié)點之間的邏輯關(guān)系，這使得可以隨機存取表中任一指定位置的數(shù)據(jù)元素，但同時導(dǎo)致插入和刪除運算進(jìn)行大量的數(shù)據(jù)元素移動。采用線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)能解決這個問題，基于它的插入和刪除運算不需要移動數(shù)據(jù)元素，從而使得時間復(fù)雜度從順序表的0（2）變?yōu)?（1）?！　≡阪?zhǔn)酱鎯Y(jié)構(gòu)中，為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，每個結(jié)點不僅要存放數(shù)據(jù)元素本身，還需要一些額外的存儲空間來存放和它有關(guān)系的數(shù)據(jù)元素的地址，即需要存放指向其他元素的指針（或鏈）。稱指向第一個結(jié)點的指針為頭指針，一個鏈表由頭指針唯一確定。一旦知道頭指針，就可以沿著指針訪問其他數(shù)據(jù)元素。　　可以根據(jù)不同的標(biāo)準(zhǔn)對鏈表進(jìn)行分類。例如，根據(jù)結(jié)點中指針數(shù)量的多少，可以將鏈表分為單鏈表、雙向鏈表和多重鏈表；根據(jù)是否在鏈表的第一個元素前附加額外的結(jié)點，可以將鏈表分為帶頭結(jié)點的鏈表和不帶頭結(jié)點的鏈表；根據(jù)頭指針是指向第一個結(jié)點還是最后一個結(jié)點，可以將鏈表分為帶頭指針的鏈表和帶尾指針的鏈表等等。　　在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，由于線性表中的數(shù)據(jù)元素在存儲單元中的存放順序與邏輯順序不一定一致，因此在對線性表操作時，只能通過頭指針進(jìn)入鏈表，并通過每個結(jié)點的指針域向后掃描其余結(jié)點，這樣就會造成尋找第一個結(jié)點和尋找最后一個結(jié)點所花費的時間不等，具有這種特點的存取方式稱為順序存取方式。因此，鏈?zhǔn)酱鎯Y(jié)構(gòu)失去了隨機存取數(shù)據(jù)元素的功能，但換來了操作的方便性：進(jìn)行插入和刪除時無需移動數(shù)據(jù)元素?！　?hellip;…

編輯推薦

在計算機科學(xué)技術(shù)的各個領(lǐng)域，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是一個重要問題。通過數(shù)據(jù)結(jié)構(gòu)與算法的學(xué)習(xí)，讀者能進(jìn)一步提高軟件設(shè)計與程序編寫的能力.提高應(yīng)用計算機技術(shù)解決宴際問題的能力?！稊?shù)據(jù)結(jié)構(gòu)與算法》是根據(jù)《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)公共核心知識體系與課程》的指導(dǎo)思想編寫而成的.涵蓋了“”數(shù)據(jù)結(jié)構(gòu)“”公共核心課程的知識單元?！稊?shù)據(jù)結(jié)構(gòu)與算法》以基本數(shù)據(jù)結(jié)構(gòu)和算法設(shè)計策略為知識單元.系統(tǒng)地介紹了數(shù)據(jù)結(jié)構(gòu)的知識與應(yīng)用、計算機算法的設(shè)計與分析方法書中分為數(shù)據(jù)結(jié)構(gòu)和算法兩大部分其中，數(shù)據(jù)結(jié)構(gòu)部分（第1～4章）按數(shù)據(jù)元素之間存在的對應(yīng)關(guān)系進(jìn)行劃分，分為表示一對一關(guān)系的線性表表示一對多關(guān)系的樹以及表示多對多關(guān)系的圖和廣義表：算法部分（第5～7章）以查找和排序算法作為常用算法.所以該部分由算法設(shè)計策略、查找和排序組成。

圖書封面

評論、評分、閱讀與下載

---

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

---