數(shù)據(jù)結構

內容概要

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

作者簡介

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

書籍目錄

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

章節(jié)摘錄

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








圖書封面



圖書標簽Tags
無




評論、評分、閱讀與下載



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


 


    數(shù)據(jù)結構 PDF格式下載