數(shù)據(jù)結(jié)構(gòu)C語言版嚴(yán)蔚敏緒論

1、 數(shù)據(jù)結(jié)構(gòu)(C語言版)講授：劉彩霞Email：1祝同學(xué)們新學(xué)期愉快、學(xué)習(xí)進(jìn)步！23數(shù)據(jù)結(jié)構(gòu)課程所處的地位：介于數(shù)學(xué)、計算機硬件和計算機軟件三者之間的一門核心課程。4數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的一門綜合性專業(yè)基礎(chǔ)課是計算機專業(yè)本/專科生必修學(xué)位課程 是計算機研究生/升本入學(xué)考試必考科目 是軟件人員水平考試內(nèi)容是數(shù)學(xué)建模、ACM程序競賽基礎(chǔ)5學(xué)業(yè)基礎(chǔ)先修課程：高級語言程序設(shè)計 (如 C/C+語言)后續(xù)課程：操作系統(tǒng)（例：打印機 隊列管理）、數(shù)據(jù)庫原 理、人工智能等。6 課程安排總學(xué)時：90 (18周*5) 講課學(xué)時：72 實驗學(xué)時：18教學(xué)參考書 教 材：數(shù)據(jù)結(jié)構(gòu)C語言版嚴(yán)蔚敏、吳偉民 -清華大學(xué)出版社

2、數(shù)據(jù)結(jié)構(gòu)C語言篇習(xí)題與解析 李春葆 -清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)自學(xué)考試指導(dǎo)丁寶康等 清華大學(xué)出版社算法與數(shù)據(jù)結(jié)構(gòu)，范策等，機械工業(yè)出版社7 (我院精品課程) (算法+數(shù)據(jù)結(jié)構(gòu): 一個很不錯的站點，有豐富的編程題庫和競賽試題，也有很多有參考價值的文獻(xiàn)。)（北京大學(xué)）（哈爾濱工業(yè)大學(xué)）（安徽工大）（淮海工學(xué)院）(西北大學(xué)) (煙臺大學(xué)）(教學(xué)博客)助學(xué)網(wǎng)站8助學(xué)網(wǎng)站(The Algorithm Design Manual 的作者Steven S. Skiena的主頁，詳細(xì)介紹算法和數(shù)據(jù)結(jié)構(gòu)，十分專業(yè)！)(此網(wǎng)站是一本關(guān)于算法、數(shù)據(jù)結(jié)構(gòu)、以及相關(guān)問題的電子字典，對各種算法有精確的定義和實現(xiàn)方法。)(美

3、國計算機科學(xué)協(xié)會)(易自考) (C語言編程寶典) (C語言學(xué)習(xí))(國內(nèi)最大的互聯(lián)網(wǎng)IT信息服務(wù)和商業(yè)服務(wù)提供商，是賽迪集團旗下唯一的IT垂直商業(yè)門戶網(wǎng)站。) 數(shù)據(jù)結(jié)構(gòu)+精品課程9實 驗實驗環(huán)境:Win-tc 或Turbo c 或VC+實驗項目名稱:一元稀疏多項式的加減運算棧和隊列的抽象數(shù)據(jù)類型實現(xiàn) 二叉樹的建立、遍歷及典型算法實現(xiàn) 圖的建立、遍歷及典型算法實現(xiàn)典型查找算法實現(xiàn)內(nèi)部排序算法實現(xiàn)10課程設(shè)計題目（任選一） : 迷宮問題求解 算術(shù)表達(dá)式求值 校園導(dǎo)游系統(tǒng)圖書管理信息系統(tǒng)的設(shè)計與實現(xiàn) 查找算法綜合比較排序算法綜合比較要求達(dá)到的目標(biāo): 文檔清晰、完整，學(xué)會分析解決問題 程序運行良好 11

4、本課程學(xué)習(xí)要求自覺預(yù)習(xí)、遵守紀(jì)律、認(rèn)真聽課、及時復(fù)習(xí)；按時、獨立、認(rèn)真地完成每次作業(yè)；每一章有作業(yè)題，按時交。每次實驗前做好準(zhǔn)備工作,寫好程序,實驗后交實驗報告（寫在紙上）。期中布置課程設(shè)計3. 積極回答課堂提問；成績評定標(biāo)準(zhǔn)： 平時表現(xiàn)：占30%，包括作業(yè)、課程設(shè)計、提問、學(xué)習(xí)紀(jì)律 期末考試：閉卷筆試，占70%12目 錄Contents 第一章 緒 論 (4學(xué)時) 第二章 線性表 (8學(xué)時) 第三章 棧和隊列 (8學(xué)時)第四章 串、數(shù)組和廣義表 (6學(xué)時) 第五章 樹和二叉樹 (10學(xué)時)第六章 圖 (6學(xué)時)第七章 查找 (6學(xué)時)第八章 排序 (6學(xué)時)13數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一

5、存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴于存儲結(jié)構(gòu)141.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術(shù)語1.3 抽象數(shù)據(jù)類型1.4 算法及算法分析（算法評價）第一章 緒 論15計算機發(fā)展簡史眾所周知，二十世紀(jì)四十年代，電子數(shù)字計算機問世的直接原因是解決彈道學(xué)的計算問題。早期，電子計算機的應(yīng)用范圍，幾乎只局限于科學(xué)和工程的計算，其處理的對象是純數(shù)值性的信息，通常，人們把這類問題稱為數(shù)值計算。16近三十年來，電子計算機的發(fā)展異常迅猛表現(xiàn)在計算機本身運算速度不斷提高、信息存儲量日益擴大、價格逐步下降更重要的是計算機廣泛地應(yīng)用于情報檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠(yuǎn)遠(yuǎn)超出了科技計算的范圍，而滲透到人類社會活動的一切領(lǐng)

6、域計算機發(fā)展簡史17與此相應(yīng)，計算機的處理對象也從簡單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息計算機發(fā)展簡史18“數(shù)據(jù)結(jié)構(gòu)”作為一門獨立的課程在國外是從1968年才開始設(shè)立的。1968年美國唐歐克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計算機程序設(shè)計技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。 “數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學(xué)計算機科學(xué)系的教學(xué)計劃。數(shù)據(jù)結(jié)構(gòu)19D. Knuth 的巨著計算機程序設(shè)計藝術(shù)第一卷“基本算法”第二卷“半數(shù)字算法”第三卷“排序與搜索”1974年獲得圖靈獎，是40屆中唯一因一部影響巨大的書而獲獎數(shù)據(jù)結(jié)構(gòu)20發(fā)展階段：數(shù)據(jù)結(jié)構(gòu)的

7、概念不斷擴充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學(xué)結(jié)構(gòu)”的內(nèi)容。70年代后期，我國高校陸續(xù)開設(shè)該課程。 數(shù)據(jù)結(jié)構(gòu)21 數(shù)據(jù)結(jié)構(gòu)是研究什么的？這是課程最基本的問題，關(guān)系到我們?yōu)槭裁匆獙W(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程1.1 什么是數(shù)據(jù)結(jié)構(gòu)22從應(yīng)用問題涉及的對象來分可分為數(shù)值問題 非數(shù)值問題數(shù)值問題就是我們平時所說的計算問題，如已知圓的半徑，要求圓的面積非數(shù)值問題就是問題中涉及的模型不能用數(shù)學(xué)方程來表達(dá)的那些問題1.1 什么是數(shù)據(jù)結(jié)構(gòu)23例 1（任務(wù)分配問題）某車間有甲、乙兩臺機床，可用于加工三種工件。假定這兩臺車床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用三種

8、不同車床加工單位數(shù)量不同工件所需的臺時數(shù)和加工費用如下表。問怎樣分配車床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？數(shù)值問題與非數(shù)值問題有什么不同1）數(shù)值問題24解 設(shè)在甲車床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，在乙車床上加工工件1、2、3的數(shù)量分別為x4、x5、x6?？山⒁韵戮€性規(guī)劃模型：251）數(shù)值問題例2 已知：游泳池的長length和寬wide，求面積area。分析：1.1 什么是數(shù)據(jù)結(jié)構(gòu)（1）問題涉及的對象： length, wide,area 是實數(shù) 可用數(shù)值表示 ；（2）對象之間的關(guān)系 ： area=lengthwide 可用方程或 函數(shù)表示 ；（3）

9、數(shù)據(jù)存儲： 可用程序設(shè)計語言中的實型變量存儲；（4）問題求解： 用某種計算方法求解；26程序：main() int len, wide ,area ; scanf (“%d %d%n”, &len,&wide); area=len*wide ; printf (“area=%d”,area); 可見，對于數(shù)值問題，對象之間的關(guān)系通?？梢杂梅匠袒蚝瘮?shù)表達(dá)，只要能列出表達(dá)對象之間關(guān)系的方程或函數(shù)，找到求解方程或函數(shù)的方法，就可以編寫程序了。27求一組（n個）整數(shù)中的最大值。算法：基本操作是兩兩比較，求兩個數(shù)的大小模型：？1.1 什么是數(shù)據(jù)結(jié)構(gòu)281.1 什么是數(shù)據(jù)結(jié)構(gòu)2）非數(shù)值問題應(yīng)用舉例1 電話

10、號碼查詢系統(tǒng)應(yīng)用舉例2 學(xué)籍檔案管理應(yīng)用舉例3 全排列問題應(yīng)用舉例4 制定教學(xué)計劃數(shù)值問題與非數(shù)值問題有什么不同29舉例1-電話號碼查詢系統(tǒng) 設(shè)有一個電話號碼薄，它記錄了N個人的名字和其相應(yīng)的電話號碼，假定按如下形式 (a1，b1) (a2，b2) (an，bn) 其中ai，bi(i=1，2n) 分別表示某人的名字和對應(yīng)的電話號碼 要求設(shè)計一個算法，當(dāng)給定任何一個人的名字時，該算法能夠打印出此人的電話號碼;如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的反饋信息30舉例2-學(xué)籍檔案管理假設(shè)一個學(xué)籍檔案管理系統(tǒng)包含如下表1-1所示的學(xué)生信息31表1-1特點?32特點:每個學(xué)生的信息

11、占據(jù)一行，所有學(xué)生的信息按學(xué)號順序依次排列構(gòu)成一張表格表中每個學(xué)生的信息依據(jù)學(xué)號的大小存在著一種前后關(guān)系，這就是線性結(jié)構(gòu)對它的操作通常是插入某個學(xué)生的信息，刪除某個學(xué)生的信息，更新某個學(xué)生的信息，按條件檢索某個學(xué)生的信息等等33 132 213 231 321 312 1234 1243 1324 1342 1423 1432 等舉例3輸出n個對象的全排列34解決圖 1-1 3個對象的全排列過程35(a1) (a2) (a3) (a4) (a5)(a)計算機和人對奕問題l在求解過程中，所處理的數(shù)據(jù)之間具有層次關(guān)系，這是樹形結(jié)構(gòu)l對它的操作有：建立樹形結(jié)構(gòu)，輸出最低層結(jié)點內(nèi)容等等36 在制定教學(xué)

12、計劃時，需要考慮各門課程的開設(shè)順序。有些課程需要先導(dǎo)課程，有些課程則不需要，而有些課程又是其他課程的先導(dǎo)課程。比如，計算機專業(yè)課程的開設(shè)情況如下表1-2所示：舉例4制定教學(xué)計劃37表1-238課程先后關(guān)系的圖形描述形式c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計算機專業(yè)必修課程開設(shè)先后關(guān)系391）問題涉及的對象：課程可用課程名表示 不能用數(shù)值表示2）對象之間的關(guān)系：需要考慮各門課程的開設(shè)順序。有些課程是某些課程的 先導(dǎo)課程。必須先開先導(dǎo)課程，再開后續(xù)課程。 課程之間的這種關(guān)系不能用方程或 函數(shù)表示3）數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系如何存儲？4）如何求解 ？40特點課程之間的先后關(guān)

13、系用圖結(jié)構(gòu)描述通過實施創(chuàng)建圖結(jié)構(gòu)，按要求將圖結(jié)構(gòu)中的頂點進(jìn)行線性排序41從應(yīng)用問題涉及的對象來分可分為數(shù)值問題 非數(shù)值問題數(shù)值問題就是我們平時所說的計算問題，如已知圓的半徑，要求圓的面積非數(shù)值問題就是問題中涉及的模型不能用數(shù)學(xué)方程來表達(dá)的那些問題小結(jié)：42 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象及其之間關(guān)系與操作的學(xué)科。 1.1 什么是數(shù)據(jù)結(jié)構(gòu)43 需求分析 總體設(shè)計 模塊分割 建立數(shù)學(xué)模型 設(shè)計解數(shù)學(xué)模型的算法 程序編制 調(diào)試 結(jié)果數(shù)據(jù)結(jié)構(gòu)涉及到：數(shù)學(xué)模型的建立和對該模型具體實現(xiàn)的對應(yīng)的算法一個課題的解決原則求解梁架結(jié)構(gòu)中應(yīng)力的數(shù)學(xué)模型是線性方程組預(yù)報人口增長情況的數(shù)學(xué)

14、模型是微分方程分析問題提取操作對象找出操作對象之間的關(guān)系用數(shù)學(xué)的語言加以描述4445 數(shù)據(jù)結(jié)構(gòu)研究什么問題數(shù)學(xué)模型實現(xiàn)機外表示即外表示存儲結(jié)構(gòu)實現(xiàn)邏輯結(jié)構(gòu)基本運算處理要求機外表示數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容： (1) 要對所加工的對象進(jìn)行邏輯組織。 (2) 如何把加工對象存儲到計算機中去？ (3) 數(shù)據(jù)運算。建模求精1.1 什么是數(shù)據(jù)結(jié)構(gòu)45 DS主要研究內(nèi)容：數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系并對每種結(jié)構(gòu)定義相適應(yīng)的各種運算設(shè)計出相應(yīng)的算法分析算法的效率常見的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組、棧、隊列、表、串、樹、圖 和文件等1.1 什么是數(shù)據(jù)結(jié)構(gòu)46要求：掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型和相應(yīng)的存儲結(jié)構(gòu)要

15、求學(xué)生掌握典型算法思想及程序?qū)崿F(xiàn)；能針對給定問題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計和分析算法，提高復(fù)雜程序設(shè)計的能力。提高閱讀算法的能力為后繼課的學(xué)習(xí)及從事軟件開發(fā)打好基礎(chǔ)。 1.1 什么是數(shù)據(jù)結(jié)構(gòu)47上節(jié)回顧：邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴于存儲結(jié)構(gòu)48 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象及其之間關(guān)系與操作的學(xué)科。 1.1 什么是數(shù)據(jù)結(jié)構(gòu)49數(shù)據(jù)Data：客觀對象的符號表示。在計算機科學(xué)中,數(shù)據(jù)的含義非常廣泛，把一切能夠輸入到計算機中并被計算機程序處理的信息，包括文字、表格,圖象等，都稱為數(shù)據(jù)。 例如：課程名，地名，書名都是數(shù)據(jù)。 再如，一個個人書庫管理程序

16、所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。數(shù)據(jù) 數(shù)據(jù)元素 數(shù)據(jù)項1.2 基本概念和術(shù)語50表 1-1 個人書庫51 數(shù)據(jù)元素Data Element：數(shù)據(jù)的基本單位。在計算機程序中通常作為一個整體考慮和處理。如，在表1-1所示的個人書庫中，為了便于處理，把其中的每一行（代表一本書）作為一個基本單位來考慮，故該數(shù)據(jù)由10個數(shù)據(jù)元素構(gòu)成。 一般情況下，一個數(shù)據(jù)元素中含有若干個數(shù)據(jù)項.1.2 基本概念和術(shù)語52數(shù)據(jù)對象 結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)對象Data Object具有相同特性的數(shù)據(jù)元素的一個集合,是數(shù)據(jù)的子集.例:整數(shù)數(shù)據(jù)對象是集合0,1,-1,2,-2,撲克牌上的點數(shù)的數(shù)據(jù)對象是2,3,4,

17、5J,Q,K,A字母的數(shù)據(jù)對象是集合A,B,CX,Y,Z1.2 基本概念和術(shù)語53 數(shù)據(jù)對象可以是有限的,也可以是無限的,其中的數(shù)據(jù)不是孤立的,而是彼此相關(guān)聯(lián)的,這種數(shù)據(jù)元素相互之間的關(guān)系稱為結(jié)構(gòu).數(shù)據(jù)結(jié)構(gòu)Data Structure相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,即帶結(jié)構(gòu)的數(shù)據(jù)元素的集合.1.2 基本概念和術(shù)語數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)運算54數(shù)據(jù)元素之間的邏輯關(guān)系分為（數(shù)據(jù)邏輯結(jié)構(gòu)）1)元素之間沒有關(guān)系-集合2)元素之間有線性關(guān)系-線性數(shù)據(jù)結(jié)構(gòu)(線性表結(jié)構(gòu))3)元素之間有層次關(guān)系-層次數(shù)據(jù)結(jié)構(gòu)(樹結(jié)構(gòu))4)元素之間有網(wǎng)狀關(guān)系-網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)(圖結(jié)構(gòu))1.2 基本概念和術(shù)語55例

18、1：某班學(xué)生基本情況登記表，記錄了每個學(xué)生的學(xué)號 姓名專業(yè) 政治 面貌 ，表中的記錄是按學(xué)生的學(xué)號順序排列的. 學(xué)號 姓名 專業(yè) 政治面藐 001 王洪 計算機 黨員 002 孫文 計算機 團員 003 謝軍 計算機 團員 004 李輝 計算機 團員 005 沈祥福 計算機 黨員 006 余斌 計算機 團員 007 鞏力 計算機 團員 008 孔令輝 計算機 團員學(xué)生基本情況登記表的圖示001003002004006005008007學(xué)號關(guān)系是一種線性結(jié)構(gòu)關(guān)系1.2 基本概念和術(shù)語56例2 家族的族譜 家族的族譜反映的是家族成員之間的血緣關(guān)系，假設(shè)某家族有10個成員A， B， C， D， E，

19、 F， G， H，I， J，他們之間的血緣關(guān)系可以用如下圖表示。這種分支結(jié)構(gòu)關(guān)系被稱為樹結(jié)構(gòu)。本例中樹稱為家族樹，它很象一棵倒置的樹，A 是樹的根。JIACBDHGFE家族樹的圖示表示1.2 基本概念和術(shù)語57例3 教學(xué)計劃編排問題58學(xué)生基本情況表的二元組表示（D，S） 二元組表示 二元組表示是用一個二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)， 其中 D 是數(shù)據(jù)元素集合，S 是 D 上關(guān)系的集合。D = 001，002，003，004，005，006，007，008S = R R= , , 1.2 基本概念和術(shù)語59家族的族譜 家族的族譜反映的是家族成員之間的血緣關(guān)系，假設(shè)某家族有10個成員A， B， C

20、， D， E， F， G， H，I， J，他們之間的血緣關(guān)系可以用如下圖表示。JIACBDHGFE家族樹的圖示表示1.2 基本概念和術(shù)語 D = S = R R = 60 家族樹的二元組表示（D，S） D = A，B，C，D，E，F(xiàn)，G，H，I，J S = R R =A,B, , 1.2 基本概念和術(shù)語61課程先后關(guān)系的圖形描述形式c1c9c4c2c12c10c11c5c3c6c7c8圖 1-2 計算機專業(yè)必修課程開設(shè)先后關(guān)系62例假設(shè)我們需要編制一個事務(wù)管理的程序，管理學(xué)?？茖W(xué)研究課題小組的各項事務(wù)，則首先要為程序的操作對象課題小組設(shè)計一個數(shù)據(jù)結(jié)構(gòu)。假設(shè)每個小組由一位教師、一至三名研究生及一

21、至六名本科生組成，小組成員之間的關(guān)系是：教師指導(dǎo)研究生，而由每位研究生指導(dǎo)一至兩名本科生。則可以如下定義數(shù)據(jù)結(jié)構(gòu)： Group = (D，S) 其中: D = T，G1，Gn，S11Snm 1=n=3，1=m=2， S = R1, R2 R1 = | 1=i=n, 1=n=3 R2 = | 1=i=n, 1=j=m, 1=n=3, 1=m=2 63數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(映象),即數(shù)據(jù)結(jié)構(gòu)在計算機中的組織形式.又稱為數(shù)據(jù)的物理結(jié)構(gòu).1.2 基本概念和術(shù)語數(shù)據(jù)元素在計算機中的映射-結(jié)點數(shù)據(jù)項在計算機中的映射-數(shù)據(jù)域641.2 基本概念和術(shù)語數(shù)據(jù)在計算機中的存儲:只有兩種形式順序:

22、數(shù)據(jù)元素逐個連續(xù)存放(通過物理相鄰來確定關(guān)系)非順序:數(shù)據(jù)元素任意存放(通過存儲地址確定關(guān)系)數(shù)據(jù)結(jié)構(gòu)的存儲要把數(shù)據(jù)元素存放起來還必須把數(shù)據(jù)元素之間的邏輯關(guān)系也表示出來65數(shù)據(jù)元素的邏輯關(guān)系要么用數(shù)據(jù)元素在物理上相鄰來表示邏輯關(guān)系要么用數(shù)據(jù)元素的存儲地址(指針)來表示邏輯關(guān)系1.2 基本概念和術(shù)語66存儲結(jié)構(gòu)（Storge Structure): 數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(或稱映象)稱為數(shù)據(jù)的存儲結(jié)構(gòu)，又稱為物理結(jié)構(gòu)。 四種基本的存儲方法： （1）順序存儲方法（順序存儲結(jié)構(gòu)） （2）鏈接存儲方法（鏈?zhǔn)酱鎯Y(jié)構(gòu)） （3）索引存儲方法 （4）散列存儲方法 同一種邏輯結(jié)構(gòu)可采用不同的存儲方法（以上四

23、種之一或組合），這主要考慮的是運算方便及算法的時空要求。67 1 順序存儲將數(shù)據(jù)存儲在連續(xù)存儲區(qū)域M的相鄰的存儲單元中，使得邏輯相鄰的結(jié)點一定是物理位置相鄰 。 對于一個數(shù)據(jù)結(jié)構(gòu)B=（K，R）其中K=k1,k2,k3,k4,k5,k6,k7,k8,k9 R=r r=,它的順序存儲方式如圖所示 68 2 鏈?zhǔn)酱鎯o每個結(jié)點附加一個地址域，一個結(jié)點的地址域所指的是該結(jié)點的后繼的存儲地址，邏輯相鄰的數(shù)據(jù)元素在物理上(內(nèi)存存儲位置)不一定相鄰 。例 數(shù)據(jù)的邏輯結(jié)構(gòu)B=（K，R） 其中 K=k1,k2,k3,k4,k5 R=r R=,這是一個線性結(jié)構(gòu)，鏈?zhǔn)酱鎯θ鐖D所示 69順序存儲結(jié)構(gòu): 用數(shù)據(jù)元素在存

24、儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計算機內(nèi)存仍然相鄰。鏈?zhǔn)酱鎯Y(jié)構(gòu)： 在每一個數(shù)據(jù)元素中增加一個存放地址的指針，用此指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 所有元素存放在可以不連續(xù)的存貯單元中，但元素之間的關(guān)系可以通過地址確定，邏輯上相鄰的元素存放到計算機內(nèi)存后不一定是相鄰的。70 如何描述存儲結(jié)構(gòu)呢？ 我們可以借用高級程序語言中提供的 “數(shù)據(jù)類型”來描述它. 例如:可以用 “一維數(shù)組”類型來描述順序存儲結(jié)構(gòu)，以C語言提供的“指針”來描述鏈?zhǔn)酱鎯Y(jié)構(gòu)。71例：復(fù)數(shù)3.02.3i 的兩種存儲方式：2.303023.0030004

25、1503023.0030004152.3法1：地址 內(nèi)容法2：地址 內(nèi)容2字節(jié)72邏輯結(jié)構(gòu)、存貯結(jié)構(gòu)、運算這三個方面的關(guān)系為： （1）邏輯結(jié)構(gòu)是對數(shù)據(jù)元素之間的邏輯關(guān)系的描述，它可以用一個數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示； 數(shù)據(jù)的邏輯結(jié)構(gòu)獨立于計算機，是數(shù)據(jù)本身所固有的。（2）存貯結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機存貯器中的映像，必須依賴于計算機。（3）運算是指所施加的一組操作總稱。運算的定義直接依賴于邏輯結(jié)構(gòu)，但運算的實現(xiàn)必須依賴于存貯結(jié)構(gòu)。 數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密切相關(guān)的兩個方面，任何一個算法的設(shè)計取決于選定的數(shù)據(jù)(邏輯)結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。73數(shù)據(jù)類型Data

26、 Type一個值的集合和定義在這個值集上的一組操作的總稱.(1)高級語言中的數(shù)據(jù)類型實際上包括:數(shù)據(jù)的邏輯結(jié)構(gòu),數(shù)據(jù)的存儲結(jié)構(gòu)及所定義的操作的實現(xiàn).(2)高級語言中的數(shù)據(jù)類型按值的不同特性分為: 原子類型(如整型,實型,字符型,布爾型) 結(jié)構(gòu)類型(如數(shù)組)1.2 基本概念和術(shù)語74(3)數(shù)據(jù)類型并不局限于高級語言,它實際上是一個廣義的概念.例如:”教師”就是一個數(shù)據(jù)類型,他有值”教齡”,有操作” 教書”等;如果具體說小學(xué)教師,大學(xué)教師,可以看作時一個具體的類型.(4) 可以撇開計算機不考慮,現(xiàn)實中任何一個問題都可以定義為一個數(shù)據(jù)類型-稱為抽象數(shù)據(jù)類型1.2 基本概念和術(shù)語75抽象數(shù)據(jù)類型Abs

27、tract Data Type ADT一個數(shù)學(xué)模型及定義在這個模型上的一組操作(或運算)的總稱.抽象思維方法:舍去復(fù)雜系統(tǒng)中非本質(zhì)的細(xì)節(jié),只把其中某些本質(zhì)的,能反映系統(tǒng)重要宏觀特性的東西提煉出來,構(gòu)成系統(tǒng)的模型,并且深入研究這些特性.76例如:”平房”:本質(zhì)特性包括墻體,門,窗,房頂?shù)?再如:有一堆雞蛋,進(jìn)行了編號,我們可以對它們進(jìn)行如下操作:找出最重的;取走某一個;全部搬走;這是一個抽象的定義,并沒有考慮雞蛋在哪里放著，有多大等等771.3 抽象數(shù)據(jù)類型一.抽象數(shù)據(jù)類型定義抽象數(shù)據(jù)類型=數(shù)學(xué)模型+操作=數(shù)據(jù)結(jié)構(gòu)+操作一個抽象數(shù)據(jù)類型的描述如下:ADT 抽象數(shù)據(jù)類型的名稱數(shù)據(jù)對象 數(shù)據(jù)關(guān)系 基

28、本操作ADT抽象數(shù)據(jù)類型名78什么是類C語言? 類C語言是介于偽碼和C語言的一種描述工具.其語法基本上全部取自標(biāo)準(zhǔn)C語言,因而易于轉(zhuǎn)化為C/C+的程序,但它是簡化的,不嚴(yán)格的,不可以真正在計算機上運行,這主要反映在一下幾點:可以采用偽碼語言取代某些不必確切描述的語句或語句串.省略函數(shù)體中的簡單變量的說明.輸入/輸出函數(shù)只說明輸出什么,不考慮輸入/輸出的格式.強化賦值語句的功能.791.預(yù)定義常量和類型格式: #define 標(biāo)識符 字符串/函數(shù)結(jié)果狀態(tài)代碼 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERF

29、LOW -2*類C語言80數(shù)據(jù)結(jié)構(gòu)的表示（數(shù)據(jù)的存儲結(jié)構(gòu)）用C的類型定義（typedef）描述。數(shù)據(jù)元素類型約定為ElemType, 由用戶在使用該數(shù)據(jù)類型時自行定義 typedef int ElemType; /Status 是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼 typedef int Status;*類C語言81基本操作的算法都用以下形式的函數(shù)描述： 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） /算法說明 語句序列/函數(shù)名 除了函數(shù)的參數(shù)需要說明類型外，算法中使用的輔助變量可以不作變量說明，必要時對其作用給予注釋。一般而言，a、b、c、d、e等用作數(shù)據(jù)元素名，i、j、k、l、m、n等用作整型變量名，p

30、、q、r等用作指針變量名。當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時，函數(shù)定義為Status類型。為了便于算法描述，除了值調(diào)用方式外，增添了C+語言的引用調(diào)用的參數(shù)傳遞方式。在形參表中，以&打頭的參數(shù)即為引用參數(shù)。引用參數(shù)是實參的別名，所謂別名就是同一變量的另外一個名字。82void swap ( int n,int m) /函數(shù)定義/參數(shù)為值參數(shù) int temp; temp=n; n=m; m=temp;void swap& ( int &n,int &m) / 函數(shù)定義,參數(shù)為引用參數(shù) int temp; temp=n; n=m; m=temp;main( ) int a=10,b=20,c=10

31、,d=20;s); /函數(shù)調(diào)用swap&( c,d); /函數(shù)調(diào)用結(jié)果 ：a=10,b=20 c=20,d=10例 交換兩個整數(shù)變量的算法下面通過例子來說明引用參數(shù)的概念，值參和引用參數(shù)的區(qū)別83a10b20調(diào)用函數(shù)Swap()參數(shù)傳遞Swap()體nm1020執(zhí)行Swap()nm2010 值參函數(shù)S)的調(diào)用*類C語言84cd1020調(diào)用函數(shù)Swap&()Swap&()體nm執(zhí)行Swap&()cd2010參數(shù)傳遞nm 引用參數(shù)函數(shù)Swap&()的調(diào)用*類C語言85對于對數(shù)據(jù)有修改作用的操作（函數(shù)），要用引用參數(shù)作形參，而不能用值參作形參*類C語言86賦值語句簡單賦值 變量名=表達(dá)式；串聯(lián)賦值

32、變量名1=變量名2= 變量名k=表達(dá)式;成組賦值（變量名1，變量名k）=（表達(dá)式1，,表達(dá)式k）；結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=（值1，值k）；變量名 =表達(dá)式；變量名起始下標(biāo). .終止下標(biāo)=變量名起始下標(biāo). .終止下標(biāo)；交換賦值 變量名 變量名；條件賦值 變量名=條件表達(dá)式？表達(dá)式T;表達(dá)式F;87條件語句1 if(表達(dá)式)語句； 條件語句2 if（表達(dá)式）語句； else 語句；開關(guān)語句 1 switch（表達(dá)式）case值1：語句序列1；break；case值n：語句序列n；break；default：語句序列n+1；開關(guān)語句2 switch case條件1：語句序列1；break；case條

33、件n：語句序列n；break；default：語句序列n+1；選擇語句88循環(huán)語句for 語句 for （賦初值表達(dá)式序列；條件；修改表達(dá)式序列）語句；while 語句 while(條件)語句；do-while 語句 do語句序列；while (條件);結(jié)束語句函數(shù)結(jié)束語句 return 表達(dá)式； return;case 結(jié)束語句 break;異常結(jié)束語句 exit(異常代碼)89輸入和輸出語句輸入語句scanf (格式串，scanf 變量1,，變量n);輸出語句printf(格式串，表達(dá)式1，表達(dá)式n);通常省略格式串注釋單行注釋 /文字90基本函數(shù)求最大值 max (表達(dá)式1，表達(dá)式n)求

34、最小值 min(表達(dá)式1，表達(dá)式n)求絕對值 abs(表達(dá)式)求不足整數(shù)值 floor(表達(dá)式)求進(jìn)位整數(shù)值 ceil(表達(dá)式)判定文件結(jié)束 eof(文件變量) 或eof判定行束 eoln(文件變量)或eoln91*類C語言邏輯運算約定與運算& &：對于A&B，當(dāng)A的值為0時，不再對B求值?；蜻\算| |：對于A| |B，當(dāng)A的值為非0時，不再對B求值。92* C的數(shù)據(jù)類型在本課程中，數(shù)據(jù)的存儲結(jié)構(gòu)是用C語言的數(shù)據(jù)類型描述(定義)的，主要用到：數(shù)組，結(jié)構(gòu)，指針1 數(shù)組1)數(shù)組類型變量（數(shù)組變量）由一組類型相同的數(shù)據(jù)元素組成2）數(shù)組的類型定義和變量定義typedef 數(shù)組元素類型名 數(shù)組類型名常量

35、表達(dá)式; 數(shù)組類型名 數(shù)組變量名；93例 某班40個學(xué)生的數(shù)學(xué)成績，可以用有40個數(shù)組分量 的整型數(shù)組變量存儲。 Typedef int SCoreType40; SCoreType class1;數(shù)組類型名數(shù)組變量94* C的數(shù)據(jù)類型3）數(shù)組在內(nèi)存中的存儲示意圖 0 1 2 39class數(shù)組變量95* C的數(shù)據(jù)類型4) 數(shù)組分量(數(shù)組元素）的引用 數(shù)組變量下標(biāo)例 ：for ( i=0; i結(jié)構(gòu)變量成員名(指針變量-結(jié)構(gòu)變量的域名）例 typedef struct int no; char title; *BookPtType; BookPtType pbook； pbook-no=1; s

36、canf(“%s”,pbook-title);給pbook所指結(jié)構(gòu)變量的 no成員賦值 1 no titlepbook11021.3 抽象數(shù)據(jù)類型二.抽象數(shù)據(jù)類型舉例例1:擲骰子(色子)游戲.問題描述:每次擲出N個骰子,統(tǒng)計每次的總點數(shù)和每個骰子的點數(shù),看看誰的高.問題分析:該問題的數(shù)據(jù)包括骰子個數(shù),每個骰子的點數(shù) 和總點數(shù);骰子個數(shù)是大于0的整數(shù)N;每個骰 子的點數(shù)是1-6;總點數(shù)是N-6N; 該問題的操作包括擲骰子,求總點數(shù),輸出各 個骰子的點數(shù).1031.3 抽象數(shù)據(jù)類型1041.3 抽象數(shù)據(jù)類型例2:計算圓的周長和面積問題描述:給定圓的半徑,求出周長和面積105例3:復(fù)數(shù)的運算問題描述

37、:在高級語言中,沒有復(fù)數(shù)類型,但是可借助已 有的數(shù)據(jù)類型解決復(fù)數(shù)類型的問題.1061.3 抽象數(shù)據(jù)類型二.數(shù)據(jù)類型的實現(xiàn) 一個問題抽象為一個抽象數(shù)據(jù)類型后,僅是形式上的抽象定義,還沒有達(dá)到問題解決的目的要實現(xiàn)這個目標(biāo),就要把抽象的變成具體的,即抽象數(shù)據(jù)類型在計算機上的實現(xiàn),變?yōu)橐粋€具體的數(shù)據(jù)類型.1071.3 抽象數(shù)據(jù)類型一個數(shù)據(jù)類型的實現(xiàn)一般分為三個階段1.ADT階段,又稱為定義階段2.虛擬數(shù)據(jù)類型階段,又稱為表示階段3.物理數(shù)據(jù)類型階段,又稱為物理實現(xiàn)階段例如: 整數(shù) C語言的整數(shù) 機器整數(shù)108一 算法的概念 算法是對特定問題求解步驟的一種描述,它是指令的有限序列,其中每一條指令表示一種

38、或多種操作。例 求10個正整數(shù) 中的最大數(shù)max的算法。 描述算法的方法有很多流程圖，自然語言，計算機語言用計算機語言表達(dá)的算法就是程序1.4 算法與算法分析109若采用自然語言描述,則如下列步驟所示:(1)給10個元素a0-a9輸入數(shù)值;(2)把第一個元素a0賦給用于保存最大值元素的變量max;(3)把表示下標(biāo)的變量i賦初值1;(4)如果imax,則將ai賦給max,否則不改變max的值,這使得max始終保存著當(dāng)前比較過的所有元素的最大值;(6)使下標(biāo)i增1,以指示下一個元素;(7)轉(zhuǎn)向第(4)步繼續(xù)執(zhí)行.1.4 算法與算法分析110開始為10個元素a0到a9輸入數(shù)值max=a0i=1ima

39、xmax=aii=i+1結(jié)果NYYN求n個元素中的最大值111main() int i,max,a10;printf(“請輸入10個整數(shù):”);for(i=0;i=10;i+) scanf(“%d”,&ai);max=a0;i=1;while(imax) max=ai;i+;printf(“10個整數(shù)中的最大值為:”,max);C語言描述如下:112二 算法的基本特征1）輸入：0個或多個輸入2）輸出：1個或多個輸出3）有窮性：算法必須在有限步內(nèi)結(jié)束4）確定性：組成算法的操作必須清晰無二義性5）可行性：組成算法的操作必須能夠在計算機上實現(xiàn)1.4 算法與算法分析113算法與程序的區(qū)別算法是解決問題

40、的一種方法或一個過程，考慮如何將輸入轉(zhuǎn)換成輸出，一個問題可以有多種算法。程序是用某種程序設(shè)計語言對算法的具體實現(xiàn)。主要區(qū)別在：有窮性、正確性和描述方法 程序可以是無窮的，例如OS，算法是有窮的； 程序可以是錯誤的，算法必須是正確的； 程序是用程序設(shè)計語言描述，在機器上可以執(zhí)行； 算法還可以用框圖、自然語言等方式描述。1.4 算法和算法分析 114二、算法的描述和實現(xiàn)描述-可采用自然語言、數(shù)學(xué)語言或約定的符號語言。實現(xiàn)-必須借助程序設(shè)計語言提供的數(shù)據(jù)類型及其運算。本課的描述-采用C/C+語言。1.4 算法和算法分析 115算法研究涉及兩方面內(nèi)容：設(shè)計技術(shù)：如何設(shè)計一個有效的算法分析技術(shù)：評價和判

41、斷已有算法的優(yōu)劣1.4 算法和算法分析 1161.4 算法與算法分析評價算法的好壞的標(biāo)準(zhǔn)有很多:如算法的正確性:“正確”的含義在通常的用法中有很大的差別，大體可分為四個層次 程序不含語法錯誤程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果117三算法分析衡量的四個尺度：正確性:問題的任何一個實例作為輸入，算法都能得到正確的結(jié)果作為輸出；時間特性:運行所花費的時間；空間特性:所占用存儲空間的大小；其他（可讀性、易調(diào)性、健壯性等）。 時間和空間特性的巨大改進(jìn)源于更

42、好的數(shù)據(jù)結(jié)構(gòu)或算法。1.4 算法和算法分析 正確性、可讀性、健壯性、效率與低存儲量需求118算法效率的度量1.事后統(tǒng)計的方法2.事前分析估算的方法1.4 算法和算法分析 119 算法的時間特性的度量不應(yīng)依賴算法運行的計算機和軟件平臺（操作系統(tǒng)、編程語言和編譯系統(tǒng)），下面幾種度量算法的時間特性的方法被廢棄：算法運行的實際執(zhí)行時間運行過程中所執(zhí)行的指令條數(shù)運行過程中程序循環(huán)的次數(shù)算法的時間特性用執(zhí)行基本操作次數(shù)來度量。1.4 算法和算法分析 120 基本操作：是指算法運行中起主要作用且花費最多時間的操作。 例如：實數(shù)矩陣乘法中，基本操作為實數(shù)元素之間的數(shù)乘； N個整數(shù)排序中，基本操作可以是整數(shù)間的

43、比較或數(shù)據(jù)元素的移動；1.4 算法和算法分析 121122 算法計算量或問題規(guī)模：是指算法運行中，輸入的規(guī)模。 例如：實數(shù)矩陣乘法中，問題規(guī)模為矩陣的階數(shù)（n階方陣）； 排序問題中，問題規(guī)模是待排序元素個數(shù)；1.4 算法和算法分析 一個特定算法”運行工作量”的大小,只依賴于問題的規(guī)模123算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f（n），算法的時間度量記作： T（n）=O（ f（n ）隨問題規(guī)模的增大，算法執(zhí)行時間的增長率和操作執(zhí)行次數(shù)的增長率相同。稱為時間復(fù)雜度。124O（n）O（1）T（n）=T（n）=125判斷一個算法的效率時，函數(shù)中的常數(shù)和其他次要項常常可以忽略，而更應(yīng)該關(guān)注

44、主項（最高階項）的階數(shù)。126算法時間量度T(n)語句頻度 原操作語句重復(fù)執(zhí)行的次數(shù)當(dāng)有若干循環(huán)語句時,算法的時間復(fù)雜度由嵌套層數(shù)最多的語句的頻度決定127例1：程序段 x:=x+1語句頻度 時間復(fù)雜度x:=x+1; 1 O(1) 常數(shù)階FOR i:=1 TO n DO x:=x+1; n O(n) 線性階FOR i:=1 TO n DO n FOR j:= 1 TO n DO x:=x+1; n(n) O(n2) 平方階1.4 算法和算法分析 128例2 分析以下程序段的時間復(fù)雜度for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+)x+; /* 1 *

45、/* 2 * /1.4 算法和算法分析 129分析：語句的頻度指的是該語句重復(fù)執(zhí)行的次數(shù)。一個算法中所有語句的頻度之和構(gòu)成了該算法的運行時間。語句1的頻度是：n-1語句2的頻度是：則該程序段的時間復(fù)雜度：T(n)=1.4 算法和算法分析 130例3 分析以下程序段的時間復(fù)雜度i=1;while (i=n) i=i*2語句1的頻度是：1設(shè)語句2的頻度是f(n)，則有：即 ，取最大值則該程序段的時間復(fù)雜度為：/* 1 * /* 2 * /131當(dāng)有若干循環(huán)語句時,算法的時間復(fù)雜度由嵌套層數(shù)最多的語句的頻度決定132例4x=1;for (i=1;i=n;i+) for (j=1;j=i;j+) fo

46、r (k=1;k=j;k+) x+;由于內(nèi)循環(huán)的執(zhí)行次數(shù)雖與規(guī)模n無直接關(guān)系，但與外循環(huán)的變量取值有關(guān)。因此從內(nèi)層向外層循環(huán)分析執(zhí)行次數(shù)。133常見函數(shù)的時間復(fù)雜度按數(shù)量遞增排列及增長率。P16圖1.7時間復(fù)雜度T(n)按數(shù)量級遞增順序為：復(fù)雜度高復(fù)雜度低1341.4 算法和算法分析例5:有5個算法,A1,A2,A3,A4,A5算法 T(n) 時間復(fù)雜度 結(jié)論:A1 1000n O(n) 2=n=9 A5最好A2 100nlog2n O(nlog2n) 10=n=58 A3最好A3 10n2 O(n2) 59=n1024 A1最好A5 2n O(2n)135當(dāng)n取得很大時，指數(shù)時間算法和多項式

47、時間算法在所需時間上非常懸殊。 因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。1.4 算法和算法分析 136有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如：Public void bubble-sort(int a，int n) for(i=n-1;change=TURE;i1 & change;-i) change=false; for(j=0;jaj+1) aj aj+1; change=TURE; 137最壞情況：1+2+3+n-1 =n(n-1)/2 平均時間復(fù)雜度為:O(n2)最好情況：1次138四、設(shè)計好算法的必要性一方面計算機性能在不斷提高，另一方面用計算機解決應(yīng)用問題也在不斷變化：應(yīng)用的范圍不斷擴張（由字符發(fā)展為多媒體）應(yīng)用問題的規(guī)模不斷增加應(yīng)用問題本身也越來越復(fù)雜1.4 算法和算法分析 139以數(shù)據(jù)搜索為例：50年代，主要用于數(shù)值計算，編譯系統(tǒng)中符號表的規(guī)模不超過1000字節(jié)，即為K級；7