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

前言

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

內(nèi)容概要

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

作者簡(jiǎn)介

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

書籍目錄

出版者的話序言前言教學(xué)建議第1章 緒論1.1 計(jì)算機(jī)問題求解過程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 線性表的順序存儲(chǔ)2.1.3 線性表的鏈?zhǔn)酱鎯?chǔ)2.1.4 鏈表的各種變形2.1.5 線性表的應(yīng)用2.2 線2.2.1 線的定義2.2.2 線的順序存儲(chǔ)2.2.3 線的鏈?zhǔn)酱鎯?chǔ)2.2.4 線的應(yīng)用2.3 隊(duì)列2.3.1 隊(duì)列的定義2.3.2 隊(duì)列的順序存儲(chǔ)2.3.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)2.3.4 優(yōu)先隊(duì)列2.3.5 隊(duì)列的應(yīng)用2.4 數(shù)組2.4.1 數(shù)組的定義2.4.2 數(shù)組的表示和實(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 二叉樹的存儲(chǔ)結(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 樹和森林的存儲(chǔ)結(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 圖簡(jiǎn)介4.1.1 基本概念和術(shù)語4.1.2 圖的應(yīng)用4.2 圖的存儲(chǔ)結(jié)構(gòu)4.2.1 圖的順序存儲(chǔ)結(jié)構(gòu)4.2.2 圖的鏈?zhǔn)酱鎯?chǔ)結(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 一義表的存儲(chǔ)結(jié)構(gòu)4.5.3 義表的遍歷4.5.4 廣義表的運(yùn)算4.6 本章小結(jié)4.7 習(xí)題第5章 算法設(shè)計(jì)策略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 動(dòng)態(tài)規(guī)劃法5.5.1 動(dòng)態(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 簡(jiǎn)單選擇排序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é)摘錄

　　性表的存儲(chǔ)方式除了常用的順序存儲(chǔ)外，鏈?zhǔn)酱鎯?chǔ)也是一種常見的方式。本小節(jié)將介紹一般線性表的幾種鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)方式，如單鏈表、帶頭結(jié)點(diǎn)的單鏈表、循環(huán)鏈表等?！　【€性表的鏈?zhǔn)酱鎯?chǔ)是指用一組任意的存儲(chǔ)單元（可以連續(xù)也可以不連續(xù)）存儲(chǔ)線性表中　的數(shù)據(jù)元素。數(shù)據(jù)元素在存儲(chǔ)空間表示時(shí)通常稱為結(jié)點(diǎn)?！　∏懊嬗懻摰捻樞虮碛梦锢砦恢蒙系南噜応P(guān)系來表示結(jié)點(diǎn)之間的邏輯關(guān)系，這使得可以隨機(jī)存取表中任一指定位置的數(shù)據(jù)元素，但同時(shí)導(dǎo)致插入和刪除運(yùn)算進(jìn)行大量的數(shù)據(jù)元素移動(dòng)。采用線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)能解決這個(gè)問題，基于它的插入和刪除運(yùn)算不需要移動(dòng)數(shù)據(jù)元素，從而使得時(shí)間復(fù)雜度從順序表的0（2）變?yōu)?（1）?！　≡阪?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，每個(gè)結(jié)點(diǎn)不僅要存放數(shù)據(jù)元素本身，還需要一些額外的存儲(chǔ)空間來存放和它有關(guān)系的數(shù)據(jù)元素的地址，即需要存放指向其他元素的指針（或鏈）。稱指向第一個(gè)結(jié)點(diǎn)的指針為頭指針，一個(gè)鏈表由頭指針唯一確定。一旦知道頭指針，就可以沿著指針訪問其他數(shù)據(jù)元素?！　】梢愿鶕?jù)不同的標(biāo)準(zhǔn)對(duì)鏈表進(jìn)行分類。例如，根據(jù)結(jié)點(diǎn)中指針數(shù)量的多少，可以將鏈表分為單鏈表、雙向鏈表和多重鏈表；根據(jù)是否在鏈表的第一個(gè)元素前附加額外的結(jié)點(diǎn)，可以將鏈表分為帶頭結(jié)點(diǎn)的鏈表和不帶頭結(jié)點(diǎn)的鏈表；根據(jù)頭指針是指向第一個(gè)結(jié)點(diǎn)還是最后一個(gè)結(jié)點(diǎn)，可以將鏈表分為帶頭指針的鏈表和帶尾指針的鏈表等等?！　≡阪?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，由于線性表中的數(shù)據(jù)元素在存儲(chǔ)單元中的存放順序與邏輯順序不一定一致，因此在對(duì)線性表操作時(shí)，只能通過頭指針進(jìn)入鏈表，并通過每個(gè)結(jié)點(diǎn)的指針域向后掃描其余結(jié)點(diǎn)，這樣就會(huì)造成尋找第一個(gè)結(jié)點(diǎn)和尋找最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等，具有這種特點(diǎn)的存取方式稱為順序存取方式。因此，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)失去了隨機(jī)存取數(shù)據(jù)元素的功能，但換來了操作的方便性：進(jìn)行插入和刪除時(shí)無需移動(dòng)數(shù)據(jù)元素?！　?hellip;…

編輯推薦

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

圖書封面

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

---

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

---