算法與數(shù)據(jù)結構講稿

算法數(shù)據(jù)和數(shù)據(jù)結構劉宇2001年1*第一頁，共四十頁。程序=算法+數(shù)據(jù)結構軟件：刻畫現(xiàn)實世界，解決現(xiàn)實世界中的問題語言：實現(xiàn)的工具算法：解的描述（日常的：如魔方）數(shù)據(jù)結構：現(xiàn)實世界的數(shù)據(jù)模型程序=算法+數(shù)據(jù)結構第一章：概論2*第二頁，共四十頁。幾個例子（問題）表達式解釋6+5*4=？字符串匹配串“ABCAC”出現(xiàn)在另一個串“ABCABCACAC”的第幾個位置上排序一個序列，如何最快地對其進行排序壓縮編碼AAAABBBCDDE?圖的最短路徑地理研究中的交通網(wǎng)絡第一章：概論3*第三頁，共四十頁。課程講述的內容上述問題的答案，包括一些常用的數(shù)據(jù)結構類型以及其應用與這些數(shù)據(jù)結構的有關算法空間數(shù)據(jù)結構第一章：概論4*第四頁，共四十頁。數(shù)據(jù)結構（一）作為學科的數(shù)據(jù)結構數(shù)據(jù)結構是研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間關系和操作等等的學科。非數(shù)值計算操作對象（數(shù)組）第一章：概論5*第五頁，共四十頁。作為研究對象的數(shù)據(jù)結構數(shù)據(jù)數(shù)據(jù)項目數(shù)據(jù)對象數(shù)據(jù)結構存在一種或多種特定關系的數(shù)據(jù)元素的集合集合關系Data_Structure=(D,S)D:數(shù)據(jù)元素的有限集合S:關系第一章：概論數(shù)據(jù)結構（二）6*第六頁，共四十頁。幾個例子圖書管理對弈道路交叉口數(shù)據(jù)結構的分類（例子）集合線性樹型網(wǎng)狀第一章：概論數(shù)據(jù)結構（三）7*第七頁，共四十頁。數(shù)據(jù)結構物理結構順序存儲鏈式存儲抽象數(shù)據(jù)類型數(shù)據(jù)類型（int,float）抽象數(shù)據(jù)類型原子類型固定聚合類型可變聚合類型面向對象技術與數(shù)據(jù)結構第一章：概論數(shù)據(jù)結構（四）8*第八頁，共四十頁。算法定義為了完成特定任務指令的有窮序列好的算法的特性正確性可讀性健壯性效率和存儲要求第一章：概論9*第九頁，共四十頁。算法的效率時間復雜性問題規(guī)模大O記法空間復雜性第一章：概論10*第十頁，共四十頁。線性表的定義線性表的定義唯一的第一個元素唯一的最后一個元素前驅后繼第二章：線性表123n……11*第十一頁，共四十頁。相關概念和例子數(shù)據(jù)項紀錄文件例子字母表數(shù)據(jù)庫表第二章：線性表12*第十二頁，共四十頁。線性表操作（一）初始化：Initiate求長度：Length得到第I個元素：Get求前驅：Prior求后繼：Next定位：Locate插入：Insert第二章：線性表13*第十三頁，共四十頁。線性表操作（二）刪除操作：Delete判斷表是否為空：Empty置空表操作：Clear第二章：線性表14*第十四頁，共四十頁。線性表的存儲結構順序存儲鏈式存儲第二章：線性表NULL……15*第十五頁，共四十頁。兩種存儲方式的比較順序存儲優(yōu)點：元素訪問方便缺點：內存使用；插入刪除不方便鏈式存儲優(yōu)點：內存利用好，插入刪除方便缺點：元素訪問不方便第二章：線性表16*第十六頁，共四十頁。鏈式存儲的代碼（C）（一）structNode{ Data_TypeData; structNode*pNext;};具體的兩種實現(xiàn)1：pHeader指針指向的地址存放數(shù)據(jù) 這樣，鏈表為空時： pHeader=NULL;(未分配任何空間) 鏈表不為空時(一個元素)：

2：pHeader指針指向的地址不存放數(shù)據(jù) 鏈表為空時，分配了一個節(jié)點的空間。第二章：線性表pHeaderNULL17*第十七頁，共四十頁。鏈式存儲的代碼（C）（二）//得到第nIndex個元素//注意的問題//基0還是基1//兩種實現(xiàn)方式的不同，以下的代碼是基1，第二種實現(xiàn)方式Data_TypeGet(structNode*pHeader,intnIndex){ structNode*p=pHead; for(inti=0;i<nIndex;i++) { p=p->pNext; assert(p!=NULL); } returnp->Data;}第二章：線性表18*第十八頁，共四十頁。鏈式存儲的代碼（C）（三）//向第nIndex個位置上插入數(shù)據(jù)元素dataInsertvoidInsert(structNode*pHeader,intnIndex,Data_TypedataInsert){ structNode*p=pHead; structNode*pInsert=newstructNode[1]; pInsert->Data=dataInsert;(注意賦值) for(inti=0;i<nIndex-1;i++) { p=p->pNext; assert(p!=NULL); } structNode*pTemp=p->pNext; p->pNext=pInsert; pInsert->pNext=pTemp;}第二章：線性表19*第十九頁，共四十頁。鏈式存儲的代碼（C）（四）//刪除第nIndex個位置上的數(shù)據(jù)元素voidInsert(structNode*pHeader,intnIndex){ structNode*p=pHead; for(inti=0;i<nIndex-1;i++) { p=p->pNext; assert(p!=NULL); } structNode*pTemp=p->pNext->Next; delete[]p->pNext; p->pNext=pTemp;}第二章：線性表20*第二十頁，共四十頁。其它形式的鏈表循環(huán)鏈表表尾元素的pNext指針不為NULL判斷方式為是否等于pHeader好處：從鏈表中任何一個節(jié)點都可以找到其它的節(jié)點。雙向鏈表兩個指針域好處：可以進行兩個方向的查找，但是插入和刪除時比較麻煩。第二章：線性表21*第二十一頁，共四十頁。棧棧是限定于只在表尾進行插入和刪除操作的線性表后進先出（Lastinfirstout,LIFO）相關概念棧頂（表尾）棧底（表頭）第三章：棧和隊列22*第二十二頁，共四十頁。棧的圖示棧底棧頂出棧壓棧第三章：棧和隊列23*第二十三頁，共四十頁。棧的操作初始化：Inistack判斷棧是否為空：Empty壓棧：Push彈棧：Pop得到棧頂元素：GetTop清空棧：Clear得到棧的大小：Current_Size第三章：棧和隊列24*第二十四頁，共四十頁。表達式求值4+2*3-10/5表達式：操作數(shù)，運算符，界限符操作數(shù)棧算符棧#算符，表示表達式的開始和結束第三章：棧和隊列25*第二十五頁，共四十頁。算符優(yōu)先級+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=第三章：棧和隊列26*第二十六頁，共四十頁。表達式求值算法1：操作數(shù)棧置空，操作符棧壓入算符“#”2：依次讀入表達式的每個單詞3：如果是操作數(shù)，壓入操作數(shù)棧4：如果是操作符，將操作符棧頂元素θ1與讀入的操作符θ2進行優(yōu)先級比較4.1如果棧頂元素優(yōu)先級低，將θ2壓入操作符棧4.2如果相等，彈操作符棧4.3如果棧頂元素優(yōu)先級低，彈出兩個操作數(shù)，一個運算符，進行計算，并將計算結果壓入操作數(shù)棧，重復第4步的判斷5:直至整個表達式處理完畢第三章：棧和隊列27*第二十七頁，共四十頁。表達式求值的例子3*(7-2)#步驟操作符棧操作數(shù)棧輸入字符操作1#3*(7-2)#壓入“3”2#3*(7-2)#壓入“*”3#*3(7-2)#壓入“(”4#*(37-2)#壓入“7”5#*(37-2)#壓入“-”6#*(-372)#壓入“2”7#*(-372)#彈出“-”壓入7-28#*(35)#彈出“(”9#*35#計算3*510#15#操作符?？?，結束第三章：棧和隊列28*第二十八頁，共四十頁。隊列隊列的特點先進先出，F(xiàn)irstinfirstout(FIFO)相關概念隊頭隊尾A1A2A3A4A5……An入隊出隊隊頭（front）隊尾（rear）第三章：棧和隊列29*第二十九頁，共四十頁。隊列的操作初始化：InitQueue判斷是否為空：Empty入隊列：EnQueue出隊列：DlQueue取隊列頭：GetHead清空隊列：Clear得到隊列長度：Current_size第三章：棧和隊列30*第三十頁，共四十頁。隊列的應用和實現(xiàn)任務調度打印任務消息隊列排隊模擬隊列的兩種實現(xiàn)鏈式存儲注意要有隊尾指針循環(huán)隊列第三章：棧和隊列31*第三十一頁，共四十頁。串定義：零個或多個字符組成的有限序列例子“China”,“BoyandGirl”應用語言處理，如編譯器文本檢索專家系統(tǒng)…第四章：串32*第三十二頁，共四十頁。串的操作（一）一個問題串和線性表操作：賦值和創(chuàng)建：Assign,Create判斷是否相等：Equal計算長度：Length聯(lián)結：Concat求子串：SubStr第四章：串33*第三十三頁，共四十頁。串的操作（二）定位：Index置換：Replace插入：Insert刪除：Delete34*第三十四頁，共四十頁。串的存儲實現(xiàn)靜態(tài)存儲結構數(shù)組動態(tài)存儲結構鏈表每個節(jié)點可以存儲一個或多個數(shù)組35*第三十五頁，共四十頁。串的匹配——KMP算法一種樸素的匹配算法KMP匹配算法出發(fā)點：利用前面匹配的結果，進行無回溯匹配一個示例匹配的講解模式串：abcac主串：ababcabcacbab36*第三十六頁，共四十頁。串的匹配——KMP算法思考的開始：假定：主串為S1S2…Sn

模式串為

P1P2…Pm無回溯匹配問題變?yōu)椋寒斨鞔械牡趇個字符和模式串中的第j個字符出現(xiàn)不匹配，主串中的第i個字符應該和模式串中的哪個字符匹配（無回溯）？37*第三十七頁，共四十頁。串的匹配——KMP算法進一步思考假定主串中第i個字符與模式串第k個字符相比較，則應有P1P2…Pk=Si-k+1Si-k+2…Si-1問題可能有多個k，取哪一個？而根據(jù)已有的匹配，有Pj-k+1Pj-k+2…Pj-1=Si-k+1Si-k+2…Si-1因此Pj-k+1Pj-k+2…Pj-1=P1P2…Pk-1因此k值只和P以及j有關，定義為Next[j]38*第三十八頁，共四十頁。串的匹配——KMP算法Next[j]的定義Next[j]=0,j=1時Max{k|1<k<jandp1p2…pk-1=pj-k+1…pj-1}1,其它情況j12345678abaabcac01122312Next[j]39*第三十九頁，共四十頁。內容總結算法數(shù)據(jù)和數(shù)據(jù)結構。算法和數(shù)據(jù)結構。軟件：刻畫現(xiàn)實世界