數(shù)據(jù)結(jié)構(gòu)-1資料

1、計算機核心專業(yè)(zhuny)基礎(chǔ)課程序設(shè)計人員的必修課數(shù) 據(jù) 結(jié) 構(gòu)Data Structure主講：鄧沌華信息管理學院(xuyun) 軟件工程系共六十頁計算機系統(tǒng)=軟件系統(tǒng) + 硬件系統(tǒng)軟件=程序(chngx)+文檔 (軟件工程的觀點)程序=算法+數(shù)據(jù)結(jié)構(gòu) (Niklaus Wirth，圖靈獎獲得者)數(shù)據(jù)結(jié)構(gòu)=計算機程序設(shè)計技巧 (Knuth，圖靈獎獲得者)熟悉c語言寫出好的程序?qū)W習數(shù)據(jù)結(jié)構(gòu)=編寫高水平的程序數(shù)據(jù)結(jié)構(gòu)：計算機類專業(yè)8大核心課程之一 教育部計算機教指委認定的8大核心課程：計算機語言、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學、計算機網(wǎng)絡(luò)、計算機組成原理、操作系統(tǒng)、數(shù)據(jù)庫、軟件工程 課程(kchng)背

2、景共六十頁共六十頁為什么要學習(xux)數(shù)據(jù)結(jié)構(gòu)計算機軟件與理論學科的專業(yè)基礎(chǔ)課程后續(xù)專業(yè)課程學習的必要知識與技能準備 編譯原理要使用棧、散列表及語法樹操作系統(tǒng)中用隊列、存儲管理表及目錄樹數(shù)據(jù)庫系統(tǒng)運用線性表、多鏈表、及索引樹增強求解復(fù)雜程序設(shè)計問題(wnt)的能力基礎(chǔ)課理論課程序設(shè)計課方法課學位課考試課共六十頁教學(jio xu)目的掌握常用的基本數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用學會合理地組織數(shù)據(jù), 有效地表示數(shù)據(jù), 有效地處理數(shù)據(jù)基本掌握算法的設(shè)計分析技術(shù)(jsh)提高程序設(shè)計的質(zhì)量共六十頁教材(jioci)及參考書教材數(shù)據(jù)結(jié)構(gòu)(sh j ji u)(C語言版)清華大學出版社 嚴蔚敏編著參考書目1、數(shù)據(jù)結(jié)

3、構(gòu)教程 清華大學出版社 李春葆2、數(shù)據(jù)結(jié)構(gòu)(C語言描述) 清華大學出版社 殷人昆3、數(shù)據(jù)結(jié)構(gòu)(C語言版) Ellis Horowitz Sartaj Sahni Susan Anderson-Freed 機械工業(yè)出版社4、數(shù)據(jù)結(jié)構(gòu)(C語言版) R Krishnamoorthy ，G Indirani Kumaravel 清華大學出版社5、數(shù)據(jù)結(jié)構(gòu) 西安電子科技大學出版社 楊秀金6、數(shù)據(jù)結(jié)構(gòu)與算法 高等教育出版社 張銘另：參考名校的數(shù)據(jù)結(jié)構(gòu)精品課程網(wǎng)站共六十頁作業(yè)(zuy) 每章講完后布置書面作業(yè)(zuy)：課后習題，或通過網(wǎng)絡(luò)布置；布置完作業(yè)(zuy)一周后上交； 實驗報告：每次實驗后按指定格

4、式書寫實驗報告；實驗完一周后上交。師生交流 郵箱(快樂學習計算機)： klxxjsj 密碼：klxxjsj期末總評平時成績(作業(yè)/實驗/出勤)30期末70共六十頁北大學生學習數(shù)據(jù)結(jié)構(gòu)(sh j ji u)平時作業(yè)要附加“誠實代碼” / 我真誠地保證：/ 我自己獨立地完成了整個程序從分析、設(shè)計到編碼的所有工作。 / 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序?qū)嵙晥蟾嬷?/ 詳細地列舉我所遇到的問題，以及別人給我的提示。 / 在此，我感謝 XXX, , XXX 對我的啟發(fā)和幫助。下面的報告中，我還會具體地提到/ 他們在各個方法對我的幫助。 / 我的程序里中凡是引用到其他程序或文

5、檔之處， / 例如教材、課堂筆記、網(wǎng)上的源代碼以及其他參考書上的代碼段 , / 我都已經(jīng)在程序的注釋里很清楚地注明了引用的出處。 / 我從未抄襲過別人的程序，也沒有盜用(doyng)別人的程序， / 不管是修改式的抄襲還是原封不動的抄襲。 / 我編寫這個程序，從來沒有想過要去破壞或妨礙其他計算機系統(tǒng)的正常運轉(zhuǎn)。共六十頁第一章 緒論(xln)教學內(nèi)容1.1 概述1.2 數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的基本概念及術(shù)語1.3 算法及算法描述語言1.4 算法分析教學重難點1. 數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念及術(shù)語2. 算法分析評價技術(shù)共六十頁1.1 概 述計算機的發(fā)展數(shù)值(shz)運算問題與非數(shù)值(shz)運算問

6、題本課程的形成與發(fā)展共六十頁 計算機的發(fā)展(fzhn)整數(shù)(zhngsh)、實數(shù)字符、表格、圖形、圖象、聲音 + - * / 控制、管理、數(shù)據(jù)處理等 功能上的發(fā)展：早期：科學計算 現(xiàn)今主要：信息處理 處理對象的改變：早期：數(shù)值型數(shù)據(jù) 現(xiàn)今主要：各種信息 主要操作的變化：早期：科學計算 現(xiàn)今主要：信息的加工處理共六十頁1.1 概 述計算機的發(fā)展(fzhn)數(shù)值運算問題與非數(shù)值運算問題本課程的形成與發(fā)展共六十頁 數(shù)值(shz)運算問題與非數(shù)值(shz)運算問題數(shù)值計算問題的一般解決步驟： 抽象出數(shù)學模型-設(shè)計解數(shù)學模型的算法-選擇計算機語言-編出程序-測試解答數(shù)值計算的關(guān)鍵是 構(gòu)建數(shù)學模型(數(shù)學方

7、程、方程組、微分方程等)程序設(shè)計(chn x sh j)人員比較關(guān)注程序設(shè)計(chn x sh j)的技巧例：雞兔同籠問題雞和兔總頭數(shù)為h，總腳數(shù)為f，求籠中雞兔各多少？ x+y=h x=(4h-f)/2 2x+4y=f y=(f-2h)/2共六十頁非數(shù)值計算問題數(shù)據(jù)元素之間的相互關(guān)系一般無法用數(shù)學方程描述。對非數(shù)值數(shù)據(jù)的處理：分析數(shù)據(jù)的邏輯特征-抽象出合適的數(shù)學模型-合理地存儲到計算機-設(shè)計出算法(sun f)-編寫出程序共六十頁例1 學生(xu sheng)基本信息管理這張表就是這個問題的數(shù)學模型。關(guān)注的問題：這張表如何構(gòu)造？在計算機內(nèi)如何存儲？如何進行查找算法的設(shè)計(shj)？如何提高算

8、法的效率？共六十頁例2：計算機與人類對弈(du y)問題井字棋格局示意圖共六十頁例3 多叉路口交通燈管理(gunl)頂點表示一條通路連線表示兩端通路不能同時通行(tngxng)對圖的頂點的染色問題每個頂點染一色，有線相連兩頂點不能同色，總色數(shù)盡可能少3號色燈亮時，DA、DB通行共六十頁例4 排課系統(tǒng)(xtng) 計算機專業(yè)學生的必修課程課程編號課程名稱需要的先導課程編號C1程序設(shè)計基礎(chǔ)無C2離散數(shù)學C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語言C1C5算法分析與設(shè)計C3，C4C6計算機組成原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學無C10線性代數(shù)C9C11普通物理C9C12數(shù)值

9、分析C9，C10，C1共六十頁 課程先后關(guān)系(gun x)的圖型描述c1c9c4c2c12c10c11c5c3c6c7c8共六十頁小結(jié)(xioji)非數(shù)值運算問題操作的數(shù)據(jù)量大，數(shù)據(jù)間關(guān)系復(fù)雜。要進行的操作不再(b zi)是單純的數(shù)值計算，更多的是非數(shù)值問題求解，需要對數(shù)據(jù)(不是數(shù)值)進行組織、管理(增、刪、查、改)及分析。必須對數(shù)據(jù)進行有效的組織、存儲，才能對數(shù)據(jù)進行有效的操作。共六十頁數(shù)據(jù)結(jié)構(gòu)(sh j ji u)是一門討論“非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作等”的學科。P.3程序設(shè)計的實質(zhì)(shzh)是對實際問題選擇一個好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計一個好的算法。

10、而好的算法在很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。通俗的講，數(shù)據(jù)結(jié)構(gòu)是一門研究怎樣合理的組織數(shù)據(jù)、建立合適的數(shù)據(jù)結(jié)構(gòu)、提高計算機執(zhí)行程序時所用的時間效率和空間效率的學科。 共六十頁1.1 概 述計算機的發(fā)展(fzhn)數(shù)值運算問題與非數(shù)值運算問題本課程的形成與發(fā)展共六十頁本課程(kchng)的形成與發(fā)展數(shù)據(jù)結(jié)構(gòu)(sh j ji u)作為一門獨立的課程最早是美國的一些大學開設(shè)的 。1968年美國D.E.Knuth教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的計算機程序設(shè)計技巧第一卷基本算法是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。 瑞士計算機科學家，PASCAL之父，結(jié)構(gòu)化程序設(shè)計的

11、首創(chuàng)者尼克勞斯沃思(Niklaus Wirth)教授曾指出：算法+數(shù)據(jù)結(jié)構(gòu)=程序，認為程序設(shè)計的實質(zhì)是對確定的問題選擇一種好的結(jié)構(gòu)，加上設(shè)計一種好的算法。 從70年代中期到80年代初，各種版本的數(shù)據(jù)結(jié)構(gòu)著作就相繼出現(xiàn)。到20世紀80年代初期數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)研究已日臻成熟。 共六十頁數(shù)據(jù)結(jié)構(gòu)(sh j ji u)所處的地位：共六十頁1.2 基本概念和術(shù)語(shy)數(shù)據(jù)：對客觀事物的符號表示，在計算機科學中是指所有能輸入(shr)到計算機中并能被計算機程序處理的符號的總稱。 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機程序中通常被作為一個整體來進行考慮和處理，也稱為結(jié)點、記錄、頂點、 元素。數(shù)據(jù)項：有獨立含

12、義的數(shù)據(jù)的最小單位，也叫字段或域。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項所組成，也可以僅含一個數(shù)據(jù)項。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。共六十頁例 學生(xu sheng)信息檢索系統(tǒng)學號姓名性別專 業(yè)年 級980001吳承志男計算機科學與技術(shù)98級980002李淑芳女信息與計算科學98級990301劉 麗女數(shù)學與應(yīng)用數(shù)學99級990302張會友男信息與計算科學99級990303石寶國男計算機科學與技術(shù)99級000801何文穎女計算機科學與技術(shù)2000級000802趙勝利男數(shù)學與應(yīng)用數(shù)學2000級000803崔文靖男信息與計算科學2000級010601劉 麗女計算機科學與技術(shù)2001級010602魏永鳴

13、男數(shù)學與應(yīng)用數(shù)學2001級數(shù)據(jù)元素數(shù)據(jù)項共六十頁數(shù)據(jù)結(jié)構(gòu)：相互之間存在著一種(y zhn)或多種特定關(guān)系的數(shù)據(jù)元素的集合。構(gòu)成數(shù)據(jù)結(jié)構(gòu)的兩大要素(yo s)：數(shù)據(jù)元素和數(shù)據(jù)元素間的關(guān)系。數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯上的聯(lián)系，即還沒有考慮數(shù)據(jù)在計算機中的存儲形式，而基于人的思維和習慣抽象出來的數(shù)據(jù)的組織形式。數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。共六十頁四類(s li)常見邏輯結(jié)構(gòu)：元素關(guān)系元素間無關(guān)系，一盤散沙一對一線性序列(xli)一對多層次分支多對多任意復(fù)雜P.5 例1-4 1-5共六十頁 數(shù)據(jù)的存儲結(jié)構(gòu)：數(shù)據(jù)的邏輯結(jié)構(gòu)用計算機語言(yyn)的實現(xiàn)，即數(shù)據(jù)在計算機內(nèi)的表示方

14、式。存儲結(jié)構(gòu)應(yīng)包含兩方面的內(nèi)容：數(shù)據(jù)元素本身、元素間的邏輯關(guān)系。常見的存儲(cn ch)結(jié)構(gòu)：1、順序存儲結(jié)構(gòu)2、鏈接存儲結(jié)構(gòu)存什么？存數(shù)據(jù)，存數(shù)據(jù)間的關(guān)系。123456123456共六十頁 數(shù)據(jù)運算：對數(shù)據(jù)施加(shji)的操作，最常用的基本運算有：檢索、插入、刪除、更新、排序等。注意：運算在邏輯結(jié)構(gòu)(jigu)上定義，在存儲結(jié)構(gòu)(jigu)上實現(xiàn)。什么意思？通俗的說：要編程序?qū)崿F(xiàn)任何一種功能，必須先確定待處理數(shù)據(jù)的存儲結(jié)構(gòu)。本學期我們編程序主要要做的事情共六十頁 數(shù)據(jù)(shj)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(cn ch)結(jié)構(gòu) 數(shù)據(jù)的運算：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 順序存

15、儲 鏈式存儲 線性表棧隊列樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究的三個方面：串數(shù)組及廣義表本學期我們教與學的總綱！小結(jié)共六十頁 數(shù)據(jù)類型：一個值的集合和在這個集合上定義的一組操作的總稱。在一種程序設(shè)計(chn x sh j)語言中，變量所具有的數(shù)據(jù)種類即數(shù)據(jù)類型。 例：C語言中的整型、實型等；可以把數(shù)據(jù)類型看成是程序設(shè)計語言已實現(xiàn)(shxin)的數(shù)據(jù)結(jié)構(gòu)。 抽象數(shù)據(jù)類型(Abstract Data Type，簡稱ADT) ：一個數(shù)學模型及定義在該模型上的一組操作。共六十頁抽象數(shù)據(jù)類型的定義(dngy)ADT抽象數(shù)據(jù)類型名 數(shù)據(jù)(shj)對象： 數(shù)據(jù)關(guān)系： 基本運算 ： ADT抽象數(shù)據(jù)類型名ADT常用定義

16、格式抽象數(shù)據(jù)類型可以用以下的三元組來表示： ADT = (D，S，P) 數(shù)據(jù)對象 D上的關(guān)系集 D上的基本運算集 共六十頁例 ADT Linear_list 數(shù)據(jù)元素：所有ai屬于同一數(shù)據(jù)對象， i=1,2,n n=0； 關(guān)系 ：所有數(shù)據(jù)元素ai存在(cnzi)次序關(guān)系 ,a1無前驅(qū)，an無后繼 基本運算：Initial(L) 初始化空線性表； Length(L) 求表長； Get(L,i) 取線性表的第i個元素； ADT Linear_list共六十頁1.3 算法(sun f)和算法(sun f)描述語言算法的定義及特性算法與程序(chngx)的區(qū)別算法的描述與實現(xiàn)共六十頁算法(sun f)

17、的定義及特性算法：是對特定問題求解步驟的描述，是指令的有限序列。每條指令表示(biosh)一個或多個操作。(1)有窮性 一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。(2)確定性 算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。(3)可行性 一個算法是可行的。算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。(4)輸入 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。(5)輸出 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。 P.13 算法的五大基本特性：共六十頁1.3 算法(sun f)和算法(su

18、n f)描述語言算法(sun f)的定義及特性算法與程序的區(qū)別算法的描述與實現(xiàn)共六十頁算法與程序(chngx)的區(qū)別一個程序不一定滿足有窮性(死循環(huán))，另外，程序中的指令必須(bx)是機器可執(zhí)行的，而算法中的指令則無此限制。一個算法若用計算機語言來書寫，則它就可以是一個程序。程序算法數(shù)據(jù)結(jié)構(gòu)共六十頁1.3 算法(sun f)和算法(sun f)描述語言算法的定義(dngy)及特性算法與程序的區(qū)別算法的描述與實現(xiàn)共六十頁算法(sun f)的描述與實現(xiàn)描述-可采用(ciyng)自然語言、數(shù)學語言或約定的符號語言。實現(xiàn)-必須借助程序設(shè)計語言提供的數(shù)據(jù)類型及其運算。本課程中算法的描述-采用“C及C的整

19、合”語言。共六十頁1.4 算法(sun f)分析算法設(shè)計的要求算法效率的度量方法空間(kngjin)復(fù)雜度的計算時間復(fù)雜度的計算共六十頁算法(sun f)設(shè)計的要求(1) 正確性(Correctness ) 算法(sun f)應(yīng)滿足具體問題的需求。(2)可讀性(Readability) 算法應(yīng)該好讀。以有利于閱讀者對程序的理解，便于調(diào)試和修改。(3)健壯性(Robustness) 算法應(yīng)具有容錯處理。當輸入非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。(4)效率與存儲量需求 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般，這兩者與問題的規(guī)模有關(guān)。

20、共六十頁1.4 算法(sun f)分析算法設(shè)計(shj)的要求算法效率的度量方法空間復(fù)雜度的計算時間復(fù)雜度的計算共六十頁算法效率(xio l)的度量方法事后統(tǒng)計(tngj)方法通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低。缺陷：必須依賴事先編制好的測試程序。依賴計算機硬件和軟件等環(huán)境因素。測試數(shù)據(jù)設(shè)計困難。共六十頁算法效率(xio l)的度量方法事前分析估算方法在計算機程序編制前，依據(jù)統(tǒng)計方法對算法進行估算。程序的運行時間取決于下列因素：1、計算機硬件。機器執(zhí)行指令的速度。2、程序設(shè)計語言(yyn)。3、編譯產(chǎn)生的代碼質(zhì)量。4、問題

21、的規(guī)模。即輸入量的多少。共六十頁1.4 算法(sun f)分析算法設(shè)計的要求算法效率的度量(dling)方法時間復(fù)雜度的計算空間復(fù)雜度的計算共六十頁時間(shjin)復(fù)雜度的計算大量實驗證實：一個算法的運行時間與算法中基本操作的執(zhí)行次數(shù)(csh)成正比例，即哪個算法中基本操作執(zhí)行次數(shù)多，它花費時間就多。一個算法中的某語句的執(zhí)行次數(shù)稱為該語句的語句頻度或時間頻度。一個算法的運行時間大致可認為是該算法中所有語句的頻度之和，記做T(n)。共六十頁例：請計算(j sun)以下算法的執(zhí)行時間#define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn

22、) int i,j,k; for (i=1;i=n;+i) for (j=1;j=n;+j) Cij=0; for (k=1;k1/2 ，它的時間復(fù)雜度為O(n ), 即T(n)與n 數(shù)量級相同。222共六十頁 求時間(shjin)復(fù)雜度的意義時間復(fù)雜度往往不是精確的執(zhí)行次數(shù)，而是估算的數(shù)量級，體現(xiàn)的是隨問題規(guī)模的增大，算法執(zhí)行時間的增長變化趨勢。O (f(n)表示(biosh)當問題的規(guī)模由1增至n時，該算法的時間開銷將隨f(n)的變化趨勢而變化。即隨著問題規(guī)模n的增大，該算法執(zhí)行時間的增長率和f(n)的增長率相同。共六十頁 求時間(shjin)復(fù)雜度的方法1、用常數(shù)1取代運行時間中的所有加

23、法常數(shù)；2、在修改(xigi)后的運行次數(shù)函數(shù)中，只保留最高階項；3、如果最高階項存在且不是1，則去除與此項相乘的常數(shù)。得到的結(jié)果就是大O階。共六十頁例：請計算(j sun)以下算法的時間復(fù)雜度#define n 100 void MatrixMultiply(int Ann,int Bnn,int Cnn) int i,j,k for (i=1;i=n;+i) for (j=1;j=n;+j) Cij=0; for (k=1;k=n;k+) Cij=Cij+aik*bkj; n+1 n*(n+1) n2 n *(n+1)2 n3運行時間：T(n)=2n +3n +2n+132時間復(fù)雜度：T(n)=O(f(n)=O(n )3 f(n)=n3共六十頁強化訓練例1：x=x+1; T(n)=O(1) 常量(chngling)階 例2：for（j=1;j=n;j+） x=x+1; T(n)=O(n) 線性階 例3：for(j=1;j=n;j+) for(k=1;k=n;k+) x=x+1; T(n)=O(n )2平