吉林大學(xué)內(nèi)部絕密資料第一序論

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主講教師：賈海洋主講教師：賈海洋教學(xué)計(jì)劃n第一章 緒論n第二章 線性表、堆棧和隊(duì)列n第三章 數(shù)組和字符串n第六章 遞歸n第四章 樹n第五章 圖n第七章 排序n第八章 查找答疑和上機(jī)時(shí)間n答疑q課后+郵件n上機(jī)實(shí)驗(yàn)（5分制：平時(shí)成績 + 上機(jī)考試）q第5-12周（共八次，使用VC+環(huán)境）q周三 5-8節(jié)節(jié)q計(jì)算機(jī)樓實(shí)驗(yàn)室計(jì)算機(jī)樓實(shí)驗(yàn)室 A211為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)n在計(jì)算機(jī)科學(xué)中是一門綜合性的在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課專業(yè)基礎(chǔ)課。n不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是編譯原理、不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是編譯原理、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他專業(yè)課的

2、重要基操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他專業(yè)課的重要基礎(chǔ)礎(chǔ)n數(shù)據(jù)結(jié)構(gòu)課程的目的就是從對(duì)問題抽象和求解數(shù)據(jù)結(jié)構(gòu)課程的目的就是從對(duì)問題抽象和求解的角度來介紹常用的數(shù)據(jù)結(jié)構(gòu)，闡明其內(nèi)在的角度來介紹常用的數(shù)據(jù)結(jié)構(gòu)，闡明其內(nèi)在邏邏輯關(guān)系輯關(guān)系，在計(jì)算機(jī)中的，在計(jì)算機(jī)中的存儲(chǔ)表示存儲(chǔ)表示，以及刻畫施，以及刻畫施加于其上之加于其上之各種操作的算法各種操作的算法第一章第一章 緒論緒論n1.2數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)概念n1.3算 法n1.4算法的正確性證明n1.5算法分析基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史n20世紀(jì)40年代，電子計(jì)算機(jī)剛剛誕生q處理處理純數(shù)值性的信息純數(shù)值性的信息，稱為，稱為數(shù)值計(jì)算數(shù)值計(jì)算30噸！170m2！!數(shù)據(jù)

3、結(jié)構(gòu)的發(fā)展歷史n20世紀(jì)40年代：處理純數(shù)值性的信息純數(shù)值性的信息n20世紀(jì)50年代末q計(jì)算機(jī)大量應(yīng)用于解決非數(shù)值計(jì)算非數(shù)值計(jì)算問題q從簡單的數(shù)值發(fā)展到復(fù)雜數(shù)據(jù)復(fù)雜數(shù)據(jù)q各種高級(jí)程序設(shè)計(jì)語言高級(jí)程序設(shè)計(jì)語言的出現(xiàn)（1951 FORTRAN）q產(chǎn)生了數(shù)組、記錄、串和層次表結(jié)構(gòu)等新的數(shù)據(jù)結(jié)構(gòu)新的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史n20世紀(jì)40年代：處理純數(shù)值性的信息純數(shù)值性的信息n20世紀(jì)50年代末：解決非數(shù)值計(jì)算問題非數(shù)值計(jì)算問題n20世紀(jì)60年代q美國計(jì)算機(jī)界出現(xiàn)了“信息結(jié)構(gòu)”的概念（據(jù)結(jié)構(gòu)概念的前身）1968年，“數(shù)據(jù)結(jié)構(gòu)”列為一門獨(dú)立的課程獨(dú)立的課程q著名計(jì)算機(jī)科學(xué)家克努斯（D. E. Knuth

4、）陸續(xù)出版了包括基本算法、半數(shù)值算法和排序和查找等三卷的曠世之作計(jì)算機(jī)程序設(shè)計(jì)技巧計(jì)算機(jī)程序設(shè)計(jì)技巧(The Art of Computer Programming)/uno//uno/1974年，因其在算法分析和編程語言設(shè)計(jì)方面年，因其在算法分析和編程語言設(shè)計(jì)方面的突出貢獻(xiàn)，的突出貢獻(xiàn)，榮獲美國計(jì)算機(jī)協(xié)會(huì)圖靈獎(jiǎng)，是榮獲美國計(jì)算機(jī)協(xié)會(huì)圖靈獎(jiǎng)，是歷史上最年輕的獲獎(jiǎng)?wù)邭v史上最年輕的獲獎(jiǎng)?wù)摺D靈獎(jiǎng)被稱為計(jì)算機(jī)。圖靈獎(jiǎng)被稱為計(jì)算機(jī)界的諾貝爾獎(jiǎng)。界的諾貝爾獎(jiǎng)。計(jì)算機(jī)程序設(shè)計(jì)

5、藝術(shù)計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)一書一書與牛頓的與牛頓的自然哲學(xué)的數(shù)學(xué)原理自然哲學(xué)的數(shù)學(xué)原理等書一起，等書一起，被評(píng)為被評(píng)為“世界歷史上最偉大的十種科學(xué)著作世界歷史上最偉大的十種科學(xué)著作”之一。之一。他的所有著作都有個(gè)奇特他的所有著作都有個(gè)奇特“附加效應(yīng)附加效應(yīng)”，那，那就是任何人發(fā)現(xiàn)書中的錯(cuò)誤，就是任何人發(fā)現(xiàn)書中的錯(cuò)誤，不論是技術(shù)上不論是技術(shù)上的或是排版上的還是歷史上的錯(cuò)誤，都可以的或是排版上的還是歷史上的錯(cuò)誤，都可以向他指出，并可領(lǐng)取向他指出，并可領(lǐng)取2.56美元！美元！數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史n1972年，著名計(jì)算機(jī)科學(xué)家霍爾（C. A. R. Hoare）在其論文“數(shù)據(jù)結(jié)構(gòu)札記”中，澄清了關(guān)于數(shù)據(jù)結(jié)構(gòu)

6、術(shù)語和概念等方面的雜亂局面，并深刻論述了算法與數(shù)據(jù)結(jié)構(gòu)密不可分的算法與數(shù)據(jù)結(jié)構(gòu)密不可分的關(guān)系關(guān)系；n1976年，著名計(jì)算機(jī)科學(xué)家沃思（N. Wirth）出版了名為算法數(shù)據(jù)結(jié)構(gòu)程序算法數(shù)據(jù)結(jié)構(gòu)程序的專著，不僅形象地描述了數(shù)據(jù)結(jié)構(gòu)、算法與程序之間的關(guān)系，還旗幟鮮明的提出數(shù)據(jù)結(jié)構(gòu)和算法對(duì)程序設(shè)計(jì)的重要性。數(shù)據(jù)結(jié)構(gòu)的發(fā)展歷史n20世紀(jì)40年代：處理純數(shù)值性的信息純數(shù)值性的信息n20世紀(jì)50年代末：解決非數(shù)值計(jì)算問題非數(shù)值計(jì)算問題n20世紀(jì)60年代：數(shù)據(jù)結(jié)構(gòu)列為一門獨(dú)立的課程獨(dú)立的課程n20世紀(jì)70年代后期：隨著數(shù)據(jù)庫技術(shù)的成功應(yīng)用，數(shù)據(jù)結(jié)構(gòu)相應(yīng)地增加了文件組織、存儲(chǔ)和管理文件組織、存儲(chǔ)和管理等方面的內(nèi)

7、容。n20世紀(jì)80年代，隨著面向?qū)ο蟾拍詈兔嫦驅(qū)ο蠹夹g(shù)的興起，數(shù)據(jù)結(jié)構(gòu)增加了抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型等概念數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu) 0101 韓韓 冬冬 0505 楊楊 帆帆 0303 劉禹伯劉禹伯 0404 孫曉東孫曉東 0202 馮馮 明明 0606 遲克遜遲克遜 0909 張?jiān)瓘堅(jiān)?0707 陸靜雅陸靜雅 0808 薛薛 楊楊 1010 張張 雷雷 n什么是數(shù)據(jù)？數(shù)據(jù)n數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等

8、，都稱為數(shù)據(jù)數(shù)據(jù)。數(shù)據(jù)元素(元素、結(jié)點(diǎn)、頂點(diǎn)、Data Element )n數(shù)據(jù)元素?cái)?shù)據(jù)元素是組成數(shù)據(jù)的是組成數(shù)據(jù)的基本單位基本單位。在程序中。在程序中通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和處理。通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和處理。學(xué)號(hào)學(xué)號(hào)姓名姓名5308010153080101韓冬韓冬5308010253080102馮明馮明5308010353080103劉禹伯劉禹伯5308010453080104孫曉東孫曉東5308010553080105楊帆楊帆5308010653080106遲克遜遲克遜5308010753080107陸靜雅陸靜雅53080105 53080105 楊帆楊帆每一行（代表一個(gè)

9、同學(xué)每一行（代表一個(gè)同學(xué)）作為一個(gè)基本單位來考作為一個(gè)基本單位來考慮。慮。數(shù)據(jù)項(xiàng)n一般情況下，一個(gè)數(shù)據(jù)元素含有若干個(gè)一般情況下，一個(gè)數(shù)據(jù)元素含有若干個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng), ,數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)的最小單位。數(shù)據(jù)項(xiàng)是構(gòu)成數(shù)據(jù)的最小單位。n每個(gè)數(shù)據(jù)元素都有學(xué)號(hào)、姓名這兩個(gè)數(shù)據(jù)項(xiàng)構(gòu)每個(gè)數(shù)據(jù)元素都有學(xué)號(hào)、姓名這兩個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。成。數(shù)數(shù) 據(jù)據(jù) 結(jié)結(jié) 構(gòu)構(gòu)什么是結(jié)構(gòu)？HHNNNNNH H N N N N N分子結(jié)構(gòu)什么是結(jié)構(gòu)nAGCT GACT GCAT AGCT ACGT TAGCnDNA的結(jié)構(gòu)的結(jié)構(gòu)：DNA雙螺旋模型數(shù)據(jù)數(shù)據(jù)+結(jié)構(gòu)結(jié)構(gòu)學(xué)號(hào)學(xué)號(hào)姓名姓名5308010153080101韓冬韓冬53080102530

10、80102馮明馮明5308010353080103劉禹伯劉禹伯5308010453080104孫曉東孫曉東5308010553080105楊帆楊帆5308010653080106遲克遜遲克遜5308010753080107陸靜雅陸靜雅5308010853080108薛楊薛楊5308010953080109張?jiān)瓘堅(jiān)?308011053080110張雷張雷線性結(jié)構(gòu)非線性結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)01韓冬02馮明03劉禹伯04孫曉東05楊帆長春市四平市吉林省遼寧省沈陽市大連市中國線性結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)/物理結(jié)構(gòu)物理結(jié)構(gòu)n數(shù)組n鏈表01韓冬02馮明03劉禹伯04孫曉東05楊帆01韓冬02馮

11、明03劉禹伯04孫曉東05楊帆數(shù)據(jù)上的運(yùn)算集合n查找q尋找1班學(xué)號(hào)為20的同學(xué)姓名q查找所有1班姓王的同學(xué)n排序q將8班同學(xué)按照姓名拼音排序q按照專業(yè)課總成績排名數(shù)據(jù)結(jié)構(gòu)的組成：n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)上施加的操作數(shù)據(jù)上施加的操作邏輯結(jié)構(gòu)n數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。n邏輯結(jié)構(gòu)的形式化表示邏輯結(jié)構(gòu)的形式化表示邏輯結(jié)構(gòu)表示為二元組邏輯結(jié)構(gòu)表示為二元組 L=(N, R)，其中，其中N(L)是結(jié)點(diǎn)的有限集合，是結(jié)點(diǎn)的有限集合， R(L)是是N上的關(guān)系集合。上的關(guān)系集合。一般地，一般地，R=r。邏輯結(jié)構(gòu)

12、L=(N,R)， N=a, b, c, d, e , R=r， r=aecdb邏輯結(jié)構(gòu) L=(N,R)， N=a, b, c, d, e , R=r， r=, , , a b c d e L=(N,R)， N=k1，k2，k9 R=r，r=， ， ， ， ， ， ，k1k2k3k4k7k8k5k6k9邏邏輯輯結(jié)結(jié)構(gòu)構(gòu)集合集合線性線性樹樹圖圖邏輯結(jié)構(gòu)的分類邏輯結(jié)構(gòu)的分類線性結(jié)構(gòu)線性結(jié)構(gòu) 結(jié)構(gòu)中有且僅有一個(gè)結(jié)構(gòu)中有且僅有一個(gè)始結(jié)點(diǎn)始結(jié)點(diǎn)和一個(gè)和一個(gè)終結(jié)點(diǎn)終結(jié)點(diǎn)，始結(jié)點(diǎn)只有一個(gè)，始結(jié)點(diǎn)只有一個(gè)后繼結(jié)點(diǎn)后繼結(jié)點(diǎn)，終結(jié)，終結(jié)點(diǎn)只有一個(gè)點(diǎn)只有一個(gè)前趨結(jié)點(diǎn)前趨結(jié)點(diǎn)，每個(gè)，每個(gè)內(nèi)結(jié)點(diǎn)內(nèi)結(jié)點(diǎn)有且僅有且僅有一個(gè)前

13、趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。非線性結(jié)構(gòu)（樹、圖）非線性結(jié)構(gòu)（樹、圖）結(jié)構(gòu)中的結(jié)點(diǎn)可能有多個(gè)前趨結(jié)點(diǎn)結(jié)構(gòu)中的結(jié)點(diǎn)可能有多個(gè)前趨結(jié)點(diǎn)和多個(gè)后繼結(jié)點(diǎn)。和多個(gè)后繼結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)的組成：n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)上施加的操作數(shù)據(jù)上施加的操作存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)v是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中所需的存儲(chǔ)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中所需的存儲(chǔ)空間、空間的構(gòu)成結(jié)構(gòu)及對(duì)該存儲(chǔ)結(jié)構(gòu)的訪空間、空間的構(gòu)成結(jié)構(gòu)及對(duì)該存儲(chǔ)結(jié)構(gòu)的訪問方式等的總稱問方式等的總稱v數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種由邏輯結(jié)構(gòu)到存由邏輯結(jié)構(gòu)到存儲(chǔ)結(jié)構(gòu)的映射儲(chǔ)結(jié)構(gòu)的映射：v建

14、立結(jié)點(diǎn)集合建立結(jié)點(diǎn)集合 N N 到存儲(chǔ)區(qū)域到存儲(chǔ)區(qū)域 M M 的映射：的映射：N-MN-M，中，中每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)j jN N都對(duì)應(yīng)唯一的連續(xù)存儲(chǔ)單元都對(duì)應(yīng)唯一的連續(xù)存儲(chǔ)單元c cM Mv對(duì)于每一個(gè)關(guān)系元組對(duì)于每一個(gè)關(guān)系元組(a(a，b)b) r r，映射為存儲(chǔ)單元，映射為存儲(chǔ)單元的地址順序關(guān)系（或指針的地址指向關(guān)系）的地址順序關(guān)系（或指針的地址指向關(guān)系）存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)v是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中所需的存儲(chǔ)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中所需的存儲(chǔ)空間、空間的構(gòu)成結(jié)構(gòu)及對(duì)該存儲(chǔ)結(jié)構(gòu)的訪空間、空間的構(gòu)成結(jié)構(gòu)及對(duì)該存儲(chǔ)結(jié)構(gòu)的訪問方式等的總稱問方式等的總稱v數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建

15、立一種由邏輯結(jié)構(gòu)到存由邏輯結(jié)構(gòu)到存儲(chǔ)結(jié)構(gòu)的映射儲(chǔ)結(jié)構(gòu)的映射：01韓冬02馮明03劉禹伯04孫曉東05楊帆01韓冬02馮明03劉禹伯04孫曉東05楊帆學(xué)號(hào)學(xué)號(hào)姓名姓名5308010153080101韓冬韓冬5308010253080102馮明馮明5308010353080103劉禹伯劉禹伯5308010453080104孫曉東孫曉東5308010553080105楊帆楊帆存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)v是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中所需的存儲(chǔ)是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中所需的存儲(chǔ)空間、空間的構(gòu)成結(jié)構(gòu)及對(duì)該存儲(chǔ)結(jié)構(gòu)的訪空間、空間的構(gòu)成結(jié)構(gòu)及對(duì)該存儲(chǔ)結(jié)構(gòu)的訪問方式等的總稱問方式等的總稱v數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是建立一種數(shù)據(jù)

16、的存儲(chǔ)結(jié)構(gòu)是建立一種由邏輯結(jié)構(gòu)到存由邏輯結(jié)構(gòu)到存儲(chǔ)結(jié)構(gòu)的映射儲(chǔ)結(jié)構(gòu)的映射：v順序、鏈接、索引和散列四種方法順序、鏈接、索引和散列四種方法數(shù)據(jù)結(jié)構(gòu)的組成：n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)上施加的操作數(shù)據(jù)上施加的操作對(duì)數(shù)據(jù)結(jié)構(gòu)的操作n幾種數(shù)據(jù)結(jié)構(gòu)上的常用的操作：查找、插入、幾種數(shù)據(jù)結(jié)構(gòu)上的常用的操作：查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡單計(jì)算等的操刪除、合并、排序、統(tǒng)計(jì)以及簡單計(jì)算等的操作過程。作過程。n查找查找q尋找尋找1班學(xué)號(hào)為班學(xué)號(hào)為20的同學(xué)姓名的同學(xué)姓名q查找所有查找所有1班姓王的同學(xué)班姓王的同學(xué)n排序排序q將將8班同學(xué)按照姓名拼音排序班同學(xué)按照姓名

17、拼音排序q按照專業(yè)課總成績排名按照專業(yè)課總成績排名數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)研究的主要問題：研究的主要問題：1.按某種邏輯關(guān)系將一批數(shù)據(jù)元按某種邏輯關(guān)系將一批數(shù)據(jù)元素組織起來；素組織起來；2.按一定的存儲(chǔ)方式把它們存儲(chǔ)按一定的存儲(chǔ)方式把它們存儲(chǔ)起來；起來；3.在數(shù)據(jù)上定義需要施加的操作。在數(shù)據(jù)上定義需要施加的操作。第一章第一章 緒論緒論n1.2數(shù)據(jù)結(jié)構(gòu)概念n1.3算算 法法n1.4算法的正確性證明n1.5算法分析基礎(chǔ)n計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟：幾個(gè)步驟：q首先要從具體問題中抽象出一個(gè)適當(dāng)?shù)氖紫纫獜木唧w問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型數(shù)學(xué)模

18、型q然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法算法(Algorithm(Algorithm）q最后編出最后編出程序程序、進(jìn)行測試、調(diào)整直至得到最終解答、進(jìn)行測試、調(diào)整直至得到最終解答n算法就是一個(gè)算法就是一個(gè)有窮規(guī)則的集合有窮規(guī)則的集合，其中的規(guī)則規(guī)定了一個(gè)解，其中的規(guī)則規(guī)定了一個(gè)解決某一特定類型問題的運(yùn)算序列；決某一特定類型問題的運(yùn)算序列；算法有如下算法有如下5 5個(gè)特性：個(gè)特性： (1)(1)有限性：有限性：當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情況，在經(jīng)過當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情況，在經(jīng)過了有限步驟后，這個(gè)算法一定要終止。了有限步驟后，這個(gè)算法一定要終止。 (2)(2)確定性：

19、確定性：算法中的每條指令都必須是清楚的，指令無二算法中的每條指令都必須是清楚的，指令無二義性。義性。 (3)(3)輸入：輸入：具有具有0 0個(gè)或個(gè)或0 0個(gè)以上由外界提供的量。個(gè)以上由外界提供的量。 (4)(4)輸出：輸出：產(chǎn)生產(chǎn)生1 1個(gè)或多個(gè)結(jié)果。個(gè)或多個(gè)結(jié)果。 (5)(5)可行性：可行性：每條指令都十分基本，原則上可由人僅用筆和每條指令都十分基本，原則上可由人僅用筆和紙?jiān)谟邢薜臅r(shí)間內(nèi)也能完成。紙?jiān)谟邢薜臅r(shí)間內(nèi)也能完成。 注意：算法和程序是有區(qū)別的，程序未必能滿足動(dòng)態(tài)有注意：算法和程序是有區(qū)別的，程序未必能滿足動(dòng)態(tài)有 窮。窮。 1.計(jì)算機(jī)處理問題，以適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，制定出計(jì)算機(jī)處理問

20、題，以適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)為基礎(chǔ)，制定出的切實(shí)可行的方法和步驟的切實(shí)可行的方法和步驟計(jì)算機(jī)算法計(jì)算機(jī)算法。1976年，沃斯提出：年，沃斯提出： 算法算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)=程序程序(Algorithm + Data Structures = Programs) 算法描述語言算法描述語言: 算法可以用自然語言、數(shù)學(xué)語言或者約定算法可以用自然語言、數(shù)學(xué)語言或者約定的符號(hào)語言來描述。的符號(hào)語言來描述。如類如類Pascal語言、語言、C語言或偽代碼等。語言或偽代碼等。 類類pascal語言：過多涉及數(shù)據(jù)類型的定義語言：過多涉及數(shù)據(jù)類型的定義 knuth語言：不方便描述遞歸語言：不方便描述遞歸 ADL （Al

21、gorithm Describe Language）：）：直觀方便直觀方便例例1.3 歐幾里得算法 算法算法E ( m , n . n )/* 給定兩個(gè)正整數(shù)m和n，算法E求它們的最大公因子（即能同時(shí)整除m和n的最大正整數(shù)），輸出結(jié)果在n中 */E1. 求余數(shù) r m m/n n . / 有0 r nE2. 余數(shù)為零？ IF r 0 THEN RETURN n. / 若余數(shù)為 0，n即為答案E3. 減少 m n. nr. GOTO E1.2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, ,

22、,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 算法名算法名 是由字母和數(shù)字是由字母和數(shù)字組成的有限字符串，且串中組成的有限字符串，且串中第一個(gè)符號(hào)必須是字母；第一個(gè)符號(hào)必須是字母；在變量表中，變量在變量表中，變量 ik 為輸為輸入變量，入變量，1 k m, m 0，當(dāng)當(dāng)m = 0時(shí)，表示無輸

23、入變時(shí)，表示無輸入變量；變量量；變量 jk 為輸出變量，為輸出變量，1 k n，n 1 . 2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 對(duì)整個(gè)算法進(jìn)行概括說明，應(yīng)包含算法的主要思想、參變量和功能等的解釋.2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/

24、 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 算法的每一步驟都要有名稱，名稱由步驟名：算法名或算法名縮寫數(shù)字.組成；步驟名后緊接（不計(jì)空格）一對(duì)方括號(hào)，該方括號(hào)內(nèi)是該步驟所執(zhí)行操作的高度概括；2.2.算法描述語言算法描述語言 ADL ADL 的格式的格式算法算法 （變量變量i i1 1, , ,變量變量i im m. .變量變量j j1 1, , ,變量變量j jn n）/ 或者或者 /* */ . . 1 J . . 語句序列語句序列. . 本步驟的一系列操作，每個(gè)操作由ADL語句給出，若某操作難于理解則需在其后對(duì)其做出解釋.每個(gè)算法都需要用符號(hào)“”作為其被書寫完畢

25、的結(jié)束符，注意算法不一定在符號(hào)“”處運(yùn)行結(jié)束.例例1.3 歐幾里得算法 算法算法E ( m , n . n )/* 給定兩個(gè)正整數(shù)m和n，算法E求它們的最大公因子（即能同時(shí)整除m和n的最大正整數(shù)），輸出結(jié)果在n中 */E1. 求余數(shù) 置 r m m/n n . / 有0 r nE2. 余數(shù)為零？ IF r 0 THEN RETURN n. / 若余數(shù)為 0，n即為答案E3. 減少 置m n. nr. GOTO E1. 表達(dá)式表達(dá)式算術(shù)運(yùn)算符算術(shù)運(yùn)算符 +,-,*,/,DIV,MOD, , 關(guān)系運(yùn)算符關(guān)系運(yùn)算符=, , 邏輯運(yùn)算符邏輯運(yùn)算符AND，OR，NOT 邏輯常量邏輯常量 true，fal

26、se集合運(yùn)算符集合運(yùn)算符 ， （差），（差）， ， 語句語句 每條語句都用每條語句都用“.”作為結(jié)束符作為結(jié)束符 賦值語句賦值語句 a b. a b. a b c. 條件語句條件語句IF IF THEN THEN （ 語句語句1. 1. . . 語句語句m m ）. . IF IF THEN THEN （ 語句語句1. 1. . . 語句語句m m ）. . ELSE ELSE （ 語句語句1. 1. . . 語句語句n n ）. .CASE DOCASE DO（ : (1: (語句語句1. 1. . .語句語句n n1 1）. . : (m: (語句語句1. 1. . .語句語句n nm m

27、).). 循環(huán)語句循環(huán)語句WHILE DO （語句（語句1. . 語句語句n）. FOR = TO STEP DO （語句（語句1. . 語句語句n）.FOR DO（語句（語句1. . 語句語句n）. 轉(zhuǎn)移語句轉(zhuǎn)移語句 GOTO () . EXIT 語句語句可以提前結(jié)束可以提前結(jié)束WHILE或者或者FOR 循環(huán)的執(zhí)行循環(huán)的執(zhí)行 RETURN 語句語句指出算法執(zhí)行的終點(diǎn)指出算法執(zhí)行的終點(diǎn)其它其它輸入語句為：READ ( x )，表示讀取輸入值賦給變量x輸出語句為：PRINT（輸出信息）例例 A是一個(gè)含有是一個(gè)含有n個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求個(gè)不同元素的實(shí)數(shù)數(shù)組，給出求A中最大和最小元素的算法。

28、中最大和最小元素的算法。 算法算法SM(A,n . max,min) SM1.初始化初始化 maxminA1. SM2.比較比較 FOR i=2 TO n DO /求最大和最小元素求最大和最小元素 ( IF Ai max THEN maxAi. IF Ai max THEN maxAi. IF Ai max THEN maxAi. IF Ai min THEN minAi). 算法算法SMSM的時(shí)間復(fù)雜性為的時(shí)間復(fù)雜性為2(n-1)2(n-1) (i+j)/2 .如果規(guī)定算法如果規(guī)定算法BSBS的基本運(yùn)算亦為元素的的基本運(yùn)算亦為元素的比較，則容易看出算法比較，則容易看出算法BSBS對(duì)不同的輸入

29、對(duì)不同的輸入AiAi到到AjAj都有相同的基本運(yùn)算次數(shù)。設(shè)表示都有相同的基本運(yùn)算次數(shù)。設(shè)表示算法算法BSBS的基本運(yùn)算次數(shù)，根據(jù)算法的基本運(yùn)算次數(shù)，根據(jù)算法BSBS的遞的遞歸過程，有如下的遞歸表達(dá)式：歸過程，有如下的遞歸表達(dá)式：0 1( )1 2( /2)( /2) 2 2nTnnT nT nnv在剛才的遞歸表達(dá)式中，當(dāng)在剛才的遞歸表達(dá)式中，當(dāng)n n是是2 2的冪的冪時(shí)（即存在正整數(shù)時(shí)（即存在正整數(shù)k k，使得，使得n=2n=2k k）有）有()2 *(/ 2 )2TnTn 2 * ( 2 *(/ 4 )2 )2Tn 4 *(/ 4 )42Tn111 . 2*( 2 )2kkiiT1 2223

30、 22kknBS與與SM的比較的比較 雖然算法雖然算法SMSM和算法和算法BSBS的時(shí)間復(fù)雜性的時(shí)間復(fù)雜性均為線性型，但因均為線性型，但因 ，故就計(jì)算時(shí)間而言，算法故就計(jì)算時(shí)間而言，算法BSBS優(yōu)于算法優(yōu)于算法SMSM。 然而算法然而算法BSBS是遞歸算法，因此它是遞歸算法，因此它的實(shí)現(xiàn)需要額外的輔助空間棧。的實(shí)現(xiàn)需要額外的輔助空間棧。32221nn()設(shè)設(shè)f(n)和和g(n)是正整數(shù)集到正實(shí)數(shù)集上的函數(shù)，定是正整數(shù)集到正實(shí)數(shù)集上的函數(shù)，定義：義：稱稱g(n)的階至多為的階至多為f(n)，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)C和和n0，使得對(duì)任意的使得對(duì)任意的nn0，有，有g(shù)(n)

31、C f(n) 記記 g(n)為為 O(f(n)f和和g之間的關(guān)系可以描述為之間的關(guān)系可以描述為“f(n)的階至多為的階至多為 g(n)”或或“f至多與至多與g增長得一樣快增長得一樣快”222232(1)(log log)(log)( )( log)()()(2 )nOOnOnO nO nnO nO nO定義定義2.2 設(shè)設(shè)f(n)和和g(n)是正整數(shù)集到正實(shí)數(shù)集上的是正整數(shù)集到正實(shí)數(shù)集上的函數(shù)，定義：函數(shù)，定義：（1）稱）稱g(n)的階至少為的階至少為f(n)，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)C和和n0，使得對(duì)任意的，使得對(duì)任意的nn0，有，有g(shù)(n) C f(n) 記記 g(n

32、)為為 (f(n)（2）稱）稱g(n)的階至多為的階至多為f(n)，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)，當(dāng)且僅當(dāng)存在一個(gè)正常數(shù)C和和n0，使得對(duì)任意的，使得對(duì)任意的nn0，有，有g(shù)(n) C f(n) 記記 g(n)為為 (f(n)（ 3）稱）稱g(n)的階為的階為f(n)，當(dāng)且僅當(dāng)存在正常數(shù)，當(dāng)且僅當(dāng)存在正常數(shù)C1、C2和和n0，使得對(duì)任意的，使得對(duì)任意的n n0，有，有C1f(n) g(n)C2f(n) 記記 g(n)為為 (f(n)時(shí)間與空間分析時(shí)間與空間分析 一個(gè)算法在一個(gè)算法在不同的執(zhí)行時(shí)間內(nèi)不同的執(zhí)行時(shí)間內(nèi)，它，它占用的內(nèi)存占用的內(nèi)存空間量不一定相等空間量不一定相等，占用空間量，占用空間量y是時(shí)間是時(shí)間x的函數(shù)，即的函數(shù)，即y=f(x)。稱積分。稱積分 為該算法的時(shí)空積分，其中為該算法的時(shí)空積分，其中t是該算法的執(zhí)行時(shí)間?；跁r(shí)空積分，可以比較算法是該算法的執(zhí)行時(shí)間?；跁r(shí)空積分，可以比較算法優(yōu)劣，時(shí)空積分較小的算法較優(yōu)。優(yōu)劣，時(shí)空積分較小的算法較優(yōu)。dxxft0)(807060302010YX效率效率圖圖2.2 時(shí)空分布示意圖時(shí)空分布示意圖 例如，一個(gè)算法執(zhí)行時(shí)間為