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

內(nèi)容概要

　　《國家精品課程主講教材·數(shù)據(jù)結(jié)構(gòu)：題解與拓展》總結(jié)了主教材各章的主要內(nèi)容以及重點(diǎn)難點(diǎn)，并對主教材中的習(xí)題進(jìn)行了分析和解答。作為對主教材的補(bǔ)充，本書在大多數(shù)章中都增加了一個拓展部分，使學(xué)有余力的學(xué)生能夠進(jìn)一步深入地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。本書概念清楚，內(nèi)容豐富，通過學(xué)習(xí)，可以幫助學(xué)生進(jìn)一步鞏固數(shù)據(jù)結(jié)構(gòu)的知識?！　　秶揖氛n程主講教材·數(shù)據(jù)結(jié)構(gòu)：題解與拓展》可作為高等學(xué)校計算機(jī)及相關(guān)專業(yè)“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)輔導(dǎo)教材，也可以作為全同計算機(jī)專業(yè)碩士研究生入學(xué)考試的輔導(dǎo)用書。

作者簡介

　　翁惠玉，畢業(yè)子上海交通大學(xué)，獲博士學(xué)位?，F(xiàn)為上海交通大學(xué)計算機(jī)系副教授，主要從事計算機(jī)網(wǎng)絡(luò)和信息系統(tǒng)的研究，并長期承擔(dān)程序設(shè)計的教學(xué)工作，主講計算機(jī)系A(chǔ)CM試點(diǎn)班和電信學(xué)院大平臺的程序設(shè)計課程，該課程于2004年被評為上海市精品課程。

書籍目錄

第1章 緒論1.1 重點(diǎn)難點(diǎn)1.2 主要內(nèi)容1.2.1 數(shù)據(jù)的邏輯結(jié)構(gòu)1.2.2 數(shù)據(jù)結(jié)構(gòu)的存儲實(shí)現(xiàn)1.2.3 算法分析1.3 習(xí)題解答1.3.1 簡答題1.3.2 程序設(shè)計題1.4 進(jìn)一步拓展1.4.1 最大公因子問題1.4.2 遞歸函數(shù)的時間復(fù)雜度的計算第2章 線性表2.1 重點(diǎn)難點(diǎn)2.2 主要內(nèi)容2.2.1 線性表的定義及基本運(yùn)算2.2.2 線性表的順序?qū)崿F(xiàn)2.2.3 線性表的鏈接實(shí)現(xiàn)2.3 習(xí)題解答.2.3.1 簡答題2.3.2 程序設(shè)計題2.4 進(jìn)一步拓展2.4.1 字符串的存儲與匹配2.4.2 模擬動態(tài)內(nèi)存分配第3章 棧3.1 重點(diǎn)難點(diǎn)3.2 主要內(nèi)容3.2.1 棧的基本概念3.2.2 棧的順序?qū)崿F(xiàn)3.2.3 棧的鏈接實(shí)現(xiàn)3.3 習(xí)題解答3.3.1 簡答題3.3.2 程序設(shè)計題3.4 進(jìn)一步拓展3.4.1 基于線性表的棧的實(shí)現(xiàn)3.4.2 迷宮問題第4章 隊(duì)列4.1 重點(diǎn)難點(diǎn)4.2 主要內(nèi)容4.2.1 隊(duì)列的概念4.2.2 隊(duì)列的順序?qū)崿F(xiàn)4.2.3 隊(duì)列的鏈接實(shí)現(xiàn)4.3 習(xí)題解答4.3.1 簡答題4.3.2 程序設(shè)計題4.4 進(jìn)一步拓展4.4.1 迷宮問題4.4.2 火車車廂重排第5章 樹5.1 重點(diǎn)難點(diǎn)5.2 主要內(nèi)容5.2.1 樹的定義和基本概念5.2.2 二叉樹的基本概念5.2.3 二叉樹的順序?qū)崿F(xiàn)5.2.4 二叉樹的鏈接實(shí)現(xiàn)5.2.5 二叉樹遍歷的非遞歸實(shí)現(xiàn)5.2.6 哈夫曼樹和哈夫曼編碼5.2.7 樹、森林和二叉樹5.3 習(xí)題解答5.3.1 簡答題5.3.2 程序設(shè)汁題5.4 進(jìn)一步拓展5.4.1 中序線索樹5.4.2 中序線索樹的存儲5.4.3 構(gòu)造中序穿線5.4.4 遍歷二叉線索樹第6章 優(yōu)先級隊(duì)列6.1 重點(diǎn)難點(diǎn)6.2 主要內(nèi)容6.2.1 優(yōu)先級隊(duì)列的概念6.2.2 二叉堆6.2.3 貝努里隊(duì)列6.3 習(xí)題解答6.3.1 簡答題6.3.2 程序設(shè)計題6.4 進(jìn)一步拓展6.4.1 雙端隊(duì)列6.4.2 最小語言集第7章 集合與靜態(tài)查找表7.1 重點(diǎn)難點(diǎn)7.2 主要內(nèi)容7.2.1 集合的基本概念7.2.2 查找及靜態(tài)查找表7.2.3 無序表的查找7.2.4 有序表的查找7.3 習(xí)題解答7.3.1 簡答題7.3.2 程序設(shè)計題第8章 查找樹8.1 重點(diǎn)難點(diǎn)8.2 主要內(nèi)容8.2.1 二叉查找樹8.2.2 avl樹8.2.3 紅黑樹8.2.4 伸展樹8.2.5 b+樹8.3 習(xí)題解答8.3.1 簡答題8.3.2 程序設(shè)計題8.4 進(jìn)一步拓展8.4.1 線段樹8.4.2 道路問題第9章 散列表9.1 重點(diǎn)難點(diǎn)9.2 主要內(nèi)容9.2.1 散列函數(shù)9.2.2 碰撞的解決9.3 習(xí)題解答9.3.1 簡答題9.3.2 程序設(shè)計題9.4 進(jìn)一步拓展第10章 排序10.1 重點(diǎn)難點(diǎn)10.2 主要內(nèi)容10.2.1 基本概念10.2.2 插入排序10.2.3 選擇排序10.2.4 交換排序10.2.5 歸并排序10.2.6 外排序10.3 習(xí)題解答10.3.1 簡答題10.3.2 程序設(shè)計題10.4 進(jìn)一步拓展10.4.1 基數(shù)排序的思想10.4.2 基數(shù)排序的實(shí)現(xiàn)10.4.3 基數(shù)排序的性能第11章 不相交集11.1 重點(diǎn)難點(diǎn)11.2 主要內(nèi)容11.2.1 不相交集的定義11.2.2 不相交集的實(shí)現(xiàn)11.3 習(xí)題解答11.3.1 簡答題11.3.2 程序設(shè)計題11.4 進(jìn)一步拓展第12章 圖12.1 重點(diǎn)難點(diǎn)12.2 主要內(nèi)容12.2.1 圖的定義及術(shù)語12.2.2 圖的存儲12.2.3 圖的遍歷12.3 習(xí)題解答12.3.1 簡答題12.3.2 程序設(shè)計題12.4 進(jìn)一步拓展12.4.1 逆鄰接表12.4.2 十字鏈表12.4.3 鄰接多重表第13章 最小生成樹13.1 重點(diǎn)難點(diǎn)13.2 主要內(nèi)容13.2.1 kruslal算法13.2.2 prim算法13.3 習(xí)題解答13.3.1 簡答題13.3.2 程序設(shè)計題13.4 進(jìn)一步拓展第14章 最短路徑問題14.1 重點(diǎn)難點(diǎn)14.2 主要內(nèi)容14.2.1 單源最短路徑14.2.2 所有結(jié)點(diǎn)對的最短路徑14.3 習(xí)題解答14.3.1 簡答題14.3.2 程序設(shè)計題第15章 算法設(shè)計基礎(chǔ)15.1 重點(diǎn)難點(diǎn)15.2 主要內(nèi)容15.2.1 枚舉法15.2.2 貪婪法15.2.3 分治法15.2.4 動態(tài)規(guī)劃15.2.5 回溯法15.2.6 隨機(jī)算法15.3 習(xí)題解答15.3.1 簡答題15.3.2 程序設(shè)計題參考文獻(xiàn)

章節(jié)摘錄

　　15.2.5 回溯法　　回溯法也稱試探法。該方法首先暫時放棄問題規(guī)模大小的限制，從最小規(guī)模開始將問題的候選解按某種順序逐一枚舉和檢驗(yàn)。當(dāng)發(fā)現(xiàn)候選解不可能是解時，就選擇下一候選解。如果當(dāng)前候選解雖不滿足規(guī)模要求，但滿足其他所有要求，則繼續(xù)擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探。如果當(dāng)前的候選解滿足包括問題規(guī)模在內(nèi)的所有要求，該候選解就是問題的一個解。尋找下一候選解的過程稱為回溯。擴(kuò)大當(dāng)前候選解的規(guī)模，并繼續(xù)試探的過程稱為向前試探。　　15.2.6 隨機(jī)算法　　所謂的隨機(jī)算法，是指在算法中至少有一個地方使用隨機(jī)數(shù)做決策。例如，在快速排序中，很重要的一個步驟是選擇中間元素。前面介紹過用第一個元素作為中間元素，也可以選擇一個樣本，讓樣本的中值作為中間元素。也可以隨機(jī)選擇一個元素作為中間元素，那么，快速排序就成為一個隨機(jī)算法。此外，在　　第11章中的迷宮問題中，采用隨機(jī)數(shù)來確定選擇哪一堵墻。因此，迷宮問題也是用隨機(jī)算法實(shí)現(xiàn)的。正是因?yàn)榻鉀Q迷宮問題的算法是一個隨機(jī)算法，這個程序每次運(yùn)行才能得到不同的迷宮?！　‰S機(jī)算法的時間復(fù)雜度一般用期望的運(yùn)行時間來表示?！　　?/pre>








圖書封面



圖書標(biāo)簽Tags
無




評論、評分、閱讀與下載



還沒讀過(85)
勉強(qiáng)可看(621)
一般般(105)
內(nèi)容豐富(4393)
強(qiáng)力推薦(360)


 


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