1、算法和數(shù)據(jù)結(jié)構(gòu),1,算法數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu),劉宇 2001年,算法和數(shù)據(jù)結(jié)構(gòu),2,程序=算法+數(shù)據(jù)結(jié)構(gòu),軟件：刻畫現(xiàn)實(shí)世界，解決現(xiàn)實(shí)世界中的問(wèn)題 語(yǔ)言：實(shí)現(xiàn)的工具 算法：解的描述（日常的：如魔方） 數(shù)據(jù)結(jié)構(gòu)：現(xiàn)實(shí)世界的數(shù)據(jù)模型 程序=算法+數(shù)據(jù)結(jié)構(gòu),第一章：概論,算法和數(shù)據(jù)結(jié)構(gòu),3,幾個(gè)例子（問(wèn)題）,表達(dá)式解釋 6+5*4=？ 字符串匹配 串“ABCAC”出現(xiàn)在另一個(gè)串“ABCABCACAC”的第幾個(gè)位置上 排序 一個(gè)序列，如何最快地對(duì)其進(jìn)行排序 壓縮編碼 AAAABBBCDDE? 圖的最短路徑 地理研究中的交通網(wǎng)絡(luò),第一章：概論,算法和數(shù)據(jù)結(jié)構(gòu),4,課程講述的內(nèi)容,上述問(wèn)題的答案，包括 一些常用

2、的數(shù)據(jù)結(jié)構(gòu)類型以及其應(yīng)用 與這些數(shù)據(jù)結(jié)構(gòu)的有關(guān)算法 空間數(shù)據(jù)結(jié)構(gòu),第一章：概論,算法和數(shù)據(jù)結(jié)構(gòu),5,數(shù)據(jù)結(jié)構(gòu)（一）,作為學(xué)科的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間關(guān)系和操作等等的學(xué)科。 非數(shù)值計(jì)算 操作對(duì)象（數(shù)組）,第一章：概論,算法和數(shù)據(jù)結(jié)構(gòu),6,作為研究對(duì)象的數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù) 數(shù)據(jù)項(xiàng)目 數(shù)據(jù)對(duì)象 數(shù)據(jù)結(jié)構(gòu) 存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 集合 關(guān)系 Data_Structure = (D,S) D:數(shù)據(jù)元素的有限集合 S:關(guān)系,第一章：概論,數(shù)據(jù)結(jié)構(gòu)（二）,算法和數(shù)據(jù)結(jié)構(gòu),7,幾個(gè)例子 圖書管理 對(duì)弈 道路交叉口 數(shù)據(jù)結(jié)構(gòu)的分類（例子） 集合

3、 線性 樹型 網(wǎng)狀,第一章：概論,數(shù)據(jù)結(jié)構(gòu)（三）,算法和數(shù)據(jù)結(jié)構(gòu),8,數(shù)據(jù)結(jié)構(gòu)物理結(jié)構(gòu) 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ) 抽象數(shù)據(jù)類型 數(shù)據(jù)類型（int,float） 抽象數(shù)據(jù)類型 原子類型 固定聚合類型 可變聚合類型 面向?qū)ο蠹夹g(shù)與數(shù)據(jù)結(jié)構(gòu),第一章：概論,數(shù)據(jù)結(jié)構(gòu)（四）,算法和數(shù)據(jù)結(jié)構(gòu),9,算法,定義 為了完成特定任務(wù)指令的有窮序列 好的算法的特性 正確性 可讀性 健壯性 效率和存儲(chǔ)要求,第一章：概論,算法和數(shù)據(jù)結(jié)構(gòu),10,算法的效率,時(shí)間復(fù)雜性 問(wèn)題規(guī)模 大O記法 空間復(fù)雜性,第一章：概論,算法和數(shù)據(jù)結(jié)構(gòu),11,線性表的定義,線性表的定義 唯一的第一個(gè)元素 唯一的最后一個(gè)元素 前驅(qū) 后繼,第二章：線性表

4、,1,2,3,n, ,算法和數(shù)據(jù)結(jié)構(gòu),12,相關(guān)概念和例子,數(shù)據(jù)項(xiàng) 紀(jì)錄 文件 例子 字母表 數(shù)據(jù)庫(kù)表,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),13,線性表操作（一）,初始化：Initiate 求長(zhǎng)度：Length 得到第I個(gè)元素：Get 求前驅(qū)：Prior 求后繼：Next 定位：Locate 插入：Insert,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),14,線性表操作（二）,刪除操作：Delete 判斷表是否為空：Empty 置空表操作：Clear,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),15,線性表的存儲(chǔ)結(jié)構(gòu),順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ),第二章：線性表,NULL,算法和數(shù)據(jù)結(jié)構(gòu),16,兩種存儲(chǔ)方式的比較,順序存儲(chǔ) 優(yōu)點(diǎn)

5、：元素訪問(wèn)方便 缺點(diǎn)：內(nèi)存使用；插入刪除不方便 鏈?zhǔn)酱鎯?chǔ) 優(yōu)點(diǎn)：內(nèi)存利用好，插入刪除方便 缺點(diǎn)：元素訪問(wèn)不方便,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),17,鏈?zhǔn)酱鎯?chǔ)的代碼（C）（一）,struct Node Data_Type Data; struct Node *pNext; ; 具體的兩種實(shí)現(xiàn) 1：pHeader指針指向的地址存放數(shù)據(jù) 這樣，鏈表為空時(shí)： pHeader = NULL;(未分配任何空間) 鏈表不為空時(shí)(一個(gè)元素)： 2：pHeader指針指向的地址不存放數(shù)據(jù) 鏈表為空時(shí)，分配了一個(gè)節(jié)點(diǎn)的空間。,第二章：線性表,pHeader,NULL,算法和數(shù)據(jù)結(jié)構(gòu),18,鏈?zhǔn)酱鎯?chǔ)的代碼（C）（

6、二）,/得到第nIndex個(gè)元素 /注意的問(wèn)題 /基0還是基1 /兩種實(shí)現(xiàn)方式的不同，以下的代碼是基1，第二種實(shí)現(xiàn)方式 Data_Type Get(struct Node *pHeader,int nIndex) struct Node *p = pHead; for(int i=0;ipNext; assert(p!=NULL); return p-Data; ,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),19,鏈?zhǔn)酱鎯?chǔ)的代碼（C）（三）,/向第nIndex個(gè)位置上插入數(shù)據(jù)元素dataInsert void Insert(struct Node *pHeader,int nIndex,Data_Type

7、 dataInsert) struct Node *p = pHead; struct Node *pInsert = new struct Node1; pInsert-Data = dataInsert;(注意賦值) for(int i=0;ipNext; assert(p!=NULL); struct Node *pTemp = p-pNext; p-pNext = pInsert; pInsert-pNext = pTemp; ,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),20,鏈?zhǔn)酱鎯?chǔ)的代碼（C）（四）,/刪除第nIndex個(gè)位置上的數(shù)據(jù)元素 void Insert(struct Node *p

8、Header,int nIndex) struct Node *p = pHead; for(int i=0;ipNext; assert(p!=NULL); struct Node *pTemp = p-pNext-Next; delete p-pNext; p-pNext = pTemp; ,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),21,其它形式的鏈表,循環(huán)鏈表 表尾元素的pNext指針不為NULL 判斷方式為是否等于pHeader 好處：從鏈表中任何一個(gè)節(jié)點(diǎn)都可以找到其它的節(jié)點(diǎn)。 雙向鏈表 兩個(gè)指針域 好處：可以進(jìn)行兩個(gè)方向的查找，但是插入和刪除時(shí)比較麻煩。,第二章：線性表,算法和數(shù)據(jù)結(jié)構(gòu),22

9、,棧,棧是限定于只在表尾進(jìn)行插入和刪除操作的線性表 后進(jìn)先出（Last in first out,LIFO） 相關(guān)概念 棧頂（表尾） 棧底（表頭）,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),23,棧的圖示,棧底,棧頂,出棧,壓棧,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),24,棧的操作,初始化：Inistack 判斷棧是否為空：Empty 壓棧：Push 彈棧：Pop 得到棧頂元素：GetTop 清空棧：Clear 得到棧的大?。篊urrent_Size,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),25,表達(dá)式求值,4+2*3-10/5 表達(dá)式：操作數(shù)，運(yùn)算符，界限符 操作數(shù)棧 算符棧 #算符，表示表達(dá)式的開始和結(jié)束,

10、第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),26,算符優(yōu)先級(jí),第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),27,表達(dá)式求值算法,1：操作數(shù)棧置空，操作符棧壓入算符“#” 2：依次讀入表達(dá)式的每個(gè)單詞 3：如果是操作數(shù)，壓入操作數(shù)棧 4：如果是操作符，將操作符棧頂元素1與讀入的操作符2進(jìn)行優(yōu)先級(jí)比較 4.1如果棧頂元素優(yōu)先級(jí)低，將2壓入操作符棧 4.2如果相等，彈操作符棧 4.3如果棧頂元素優(yōu)先級(jí)低，彈出兩個(gè)操作數(shù)，一個(gè)運(yùn)算符，進(jìn)行計(jì)算，并將計(jì)算結(jié)果壓入操作數(shù)棧，重復(fù)第4步的判斷 5:直至整個(gè)表達(dá)式處理完畢,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),28,表達(dá)式求值的例子,3*(7-2)#,步驟 操作符棧 操作數(shù)棧 輸入字

11、符 操作 1 # 3*(7-2)# 壓入“3” 2 # 3 *(7-2)# 壓入“*” 3 #* 3 (7-2)# 壓入“(” 4 #*( 3 7-2)# 壓入“7” 5 #*( 37 -2)# 壓入“-” 6 #*(- 37 2)# 壓入“2” 7 #*(- 372 )# 彈出“-”壓入7-2 8 #*( 35 )# 彈出“(” 9 #* 35 # 計(jì)算3*5 10 # 15 # 操作符?？?，結(jié)束,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),29,隊(duì)列,隊(duì)列的特點(diǎn) 先進(jìn)先出，F(xiàn)irst in first out(FIFO) 相關(guān)概念 隊(duì)頭 隊(duì)尾,A1 A2 A3 A4 A5 An,入隊(duì),出隊(duì),隊(duì)頭（f

12、ront）,隊(duì)尾（rear）,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),30,隊(duì)列的操作,初始化：InitQueue 判斷是否為空：Empty 入隊(duì)列：EnQueue 出隊(duì)列：DlQueue 取隊(duì)列頭：GetHead 清空隊(duì)列：Clear 得到隊(duì)列長(zhǎng)度：Current_size,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),31,隊(duì)列的應(yīng)用和實(shí)現(xiàn),任務(wù)調(diào)度 打印任務(wù) 消息隊(duì)列 排隊(duì)模擬 隊(duì)列的兩種實(shí)現(xiàn) 鏈?zhǔn)酱鎯?chǔ) 注意要有隊(duì)尾指針 循環(huán)隊(duì)列,第三章：棧和隊(duì)列,算法和數(shù)據(jù)結(jié)構(gòu),32,串,定義： 零個(gè)或多個(gè)字符組成的有限序列 例子 “China”, “Boy and Girl” 應(yīng)用 語(yǔ)言處理，如編譯器 文本檢索 專家

13、系統(tǒng) ,第四章：串,算法和數(shù)據(jù)結(jié)構(gòu),33,串的操作（一）,一個(gè)問(wèn)題 串和線性表 操作： 賦值和創(chuàng)建：Assign,Create 判斷是否相等：Equal 計(jì)算長(zhǎng)度：Length 聯(lián)結(jié)：Concat 求子串：SubStr,第四章：串,算法和數(shù)據(jù)結(jié)構(gòu),34,串的操作（二）,定位：Index 置換：Replace 插入：Insert 刪除：Delete,算法和數(shù)據(jù)結(jié)構(gòu),35,串的存儲(chǔ)實(shí)現(xiàn),靜態(tài)存儲(chǔ)結(jié)構(gòu) 數(shù)組 動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu) 鏈表 每個(gè)節(jié)點(diǎn)可以存儲(chǔ)一個(gè)或多個(gè)數(shù)組,算法和數(shù)據(jù)結(jié)構(gòu),36,串的匹配KMP算法,一種樸素的匹配算法 KMP匹配算法 出發(fā)點(diǎn)：利用前面匹配的結(jié)果，進(jìn)行無(wú)回溯匹配 一個(gè)示例匹配的講解 模式串：abcac 主串：ababcabcacbab,算法和數(shù)據(jù)結(jié)構(gòu),37,串的匹配KMP算法,思考的開始： 假定：主串為 S1S2Sn 模式串為 P1P2Pm 無(wú)回溯匹配問(wèn)題變?yōu)椋寒?dāng)主串中的第i個(gè)字符和模式串中的第j個(gè)字符出現(xiàn)不匹配，主串中的第i個(gè)字符應(yīng)該和模式串中的哪個(gè)字符匹配（無(wú)回溯）？,算法和數(shù)據(jù)結(jié)構(gòu),38,串的匹配KMP算法,進(jìn)一步思考 假定主串中第i個(gè)字符與模式串第k個(gè)字符相比較，則應(yīng)有 P1P2Pk =Si-k+1Si-k+2Si-1 問(wèn)題可能有多個(gè)k，取哪一個(gè)？ 而根據(jù)已有的匹配，有 Pj-k+1Pj-k