資源描述：
《算法與數(shù)據(jù)結構_嚴蔚敏版--word》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、算法與數(shù)據(jù)結構教材：《數(shù)據(jù)結構(C語言版)》。嚴蔚敏，吳偉民編著。清華大學出版社。參考文獻：1《數(shù)據(jù)結構》。張選平，雷詠梅編，嚴蔚敏審。機械工業(yè)出版社。2《數(shù)據(jù)結構與算法分析》。CliffordA.Shaffer著，張銘，劉曉丹譯。電子工業(yè)出版社。3《數(shù)據(jù)結構習題與解析(C語實言版)》。李春葆。清華大學出版社。4《數(shù)據(jù)結構與算法》。夏克儉編著。國防工業(yè)出版社。說明:除上面所介紹的外,數(shù)據(jù)結構的參考文獻還有許多,在此就不一一列舉.另外,學習《數(shù)據(jù)結構與算法分析》這門課程時上機實驗用C語言實現(xiàn),基本的數(shù)學基礎來源于《離散
2、數(shù)學》,因此,必須熟練地掌握C語言程序設計與調試,《離散數(shù)學》的相關內容.第1章緒論目前，計算機已深入到社會生活的各個領域，其應用已不再僅僅局限于科學計算，而更多的是用于控制，管理及數(shù)據(jù)處理等非數(shù)值計算領域。計算機是一門研究用計算機進行信息表示和處理的科學。這里面涉及到兩個問題：信息的表示，信息的處理。信息的表示和組織又直接關系到處理信息的程序的效率。隨著應用問題的不斷復雜，導致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應用程序的規(guī)模很大，結構又相當復雜。因此，必須分析待處理問題中的對象的特征及各對象之間存在的關系
3、，這就是數(shù)據(jù)結構這門課所要研究的問題。編寫解決實際問題的程序的一般過程：如何用數(shù)據(jù)形式描述問題?—即由問題抽象出一個適當?shù)臄?shù)學模型;問題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關系;如何在計算機中存儲數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關系?處理問題時需要對數(shù)據(jù)作何種運算?所編寫的程序的性能是否良好?上面所列舉的問題基本上由數(shù)據(jù)結構這門課程來回答。計算機求解問題的一般步驟1.1數(shù)據(jù)結構及其概念《算法與數(shù)據(jù)結構》是計算機科學中的一門綜合性專業(yè)基礎課。是介于數(shù)學、計算機硬件、計算機軟件三者之間的一門核心課程，不僅是一般程序設計的基礎，而且是設計和
4、實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序和大型應用程序的重要基礎。41.1.1數(shù)據(jù)結構的例子姓名電話號碼陳海13612345588李四鋒13056112345。。。。。。例1：電話號碼查詢系統(tǒng)設有一個電話號碼薄，它記錄了N個人的名字和其相應的電話號碼，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)分別表示某人的名字和電話號碼。本問題是一種典型的表格問題。如表1-1，數(shù)據(jù)與數(shù)據(jù)成簡單的一對一的線性關系。表1-1線性表結構5要求設計一個算法，當給定任何一個人
5、的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的標志。例2：磁盤目錄文件系統(tǒng)磁盤根目錄下有很多子目錄及文件，每個子目錄里又可以包含多個子目錄及文件，但每個子目錄只有一個父目錄，依此類推：本問題是一種典型的樹型結構問題，如圖1-1，數(shù)據(jù)與數(shù)據(jù)成一對多的關系，是一種典型的非線性關系結構—樹形結構。圖1-1樹形結構例3：交通網(wǎng)絡圖從一個地方到另外一個地方可以有多條路徑。本問題是一種典型的網(wǎng)狀結構問題，數(shù)據(jù)與數(shù)據(jù)成多對多的關系，是一種非線性關系結構。7其他例子：圖書館的
6、書目檢索系統(tǒng)自動化問題教師資料檔案管理系統(tǒng)多叉路口交通燈的管理問題數(shù)據(jù)(Data)：是客觀事物的符號表示。在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素(DataElement)：是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(DataItem)組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。數(shù)據(jù)對象(DataObject)：是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合C={‘A’,’B’,’C,
7、…}。1.1.2基本概念和術語8數(shù)據(jù)對象可以是有限的，也可以是無限的。數(shù)據(jù)結構(DataStructure)：是指相互之間具有(存在)一定聯(lián)系(關系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關系)稱為邏輯結構。數(shù)據(jù)元素之間的邏輯結構有四種基本類型，如圖1-3所示。①集合：結構中的數(shù)據(jù)元素除了“同屬于一個集合”外，沒有其它關系。②線性結構：結構中的數(shù)據(jù)元素之間存在一對一的關系。③樹型結構：結構中的數(shù)據(jù)元素之間存在一對多的關系。④圖狀結構或網(wǎng)狀結構：結構中的數(shù)據(jù)元素之間存在多對多的關系。數(shù)據(jù)結構的形式定義是一個二元組：Da
8、ta-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關系的有限集。例2：設數(shù)據(jù)邏輯結構B=（K，R）K={k1,k2,…,k9}R={，，，，，，，，，，}畫出這邏輯結構的
