算法與數(shù)據(jù)結(jié)構(gòu)講稿

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

2：pHeader指針指向的地址不存放數(shù)據(jù) 鏈表為空時(shí)，分配了一個(gè)節(jié)點(diǎn)的空間。第二章：線性表pHeaderNULL17*第十七頁，共四十頁。鏈?zhǔn)酱鎯?chǔ)的代碼（C）（二）//得到第nIndex個(gè)元素//注意的問題//基0還是基1//兩種實(shí)現(xiàn)方式的不同，以下的代碼是基1，第二種實(shí)現(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*第十八頁，共四十頁。鏈?zhǔn)酱鎯?chǔ)的代碼（C）（三）//向第nIndex個(gè)位置上插入數(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*第十九頁，共四十頁。鏈?zhǔn)酱鎯?chǔ)的代碼（C）（四）//刪除第nIndex個(gè)位置上的數(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好處：從鏈表中任何一個(gè)節(jié)點(diǎn)都可以找到其它的節(jié)點(diǎn)。雙向鏈表兩個(gè)指針域好處：可以進(jìn)行兩個(gè)方向的查找，但是插入和刪除時(shí)比較麻煩。第二章：線性表21*第二十一頁，共四十頁。棧棧是限定于只在表尾進(jìn)行插入和刪除操作的線性表后進(jìn)先出（Lastinfirstout,LIFO）相關(guān)概念棧頂（表尾）棧底（表頭）第三章：棧和隊(duì)列22*第二十二頁，共四十頁。棧的圖示棧底棧頂出棧壓棧第三章：棧和隊(duì)列23*第二十三頁，共四十頁。棧的操作初始化：Inistack判斷棧是否為空：Empty壓棧：Push彈棧：Pop得到棧頂元素：GetTop清空棧：Clear得到棧的大小：Current_Size第三章：棧和隊(duì)列24*第二十四頁，共四十頁。表達(dá)式求值4+2*3-10/5表達(dá)式：操作數(shù)，運(yùn)算符，界限符操作數(shù)棧算符棧#算符，表示表達(dá)式的開始和結(jié)束第三章：棧和隊(duì)列25*第二十五頁，共四十頁。算符優(yōu)先級(jí)+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=第三章：棧和隊(duì)列26*第二十六頁，共四十頁。表達(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ì)列27*第二十七頁，共四十頁。表達(dá)式求值的例子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#計(jì)算3*510#15#操作符?？眨Y(jié)束第三章：棧和隊(duì)列28*第二十八頁，共四十頁。隊(duì)列隊(duì)列的特點(diǎn)先進(jìn)先出，F(xiàn)irstinfirstout(FIFO)相關(guān)概念隊(duì)頭隊(duì)尾A1A2A3A4A5……An入隊(duì)出隊(duì)隊(duì)頭（front）隊(duì)尾（rear）第三章：棧和隊(duì)列29*第二十九頁，共四十頁。隊(duì)列的操作初始化：InitQueue判斷是否為空：Empty入隊(duì)列：EnQueue出隊(duì)列：DlQueue取隊(duì)列頭：GetHead清空隊(duì)列：Clear得到隊(duì)列長度：Current_size第三章：棧和隊(duì)列30*第三十頁，共四十頁。隊(duì)列的應(yīng)用和實(shí)現(xiàn)任務(wù)調(diào)度打印任務(wù)消息隊(duì)列排隊(duì)模擬隊(duì)列的兩種實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)注意要有隊(duì)尾指針循環(huán)隊(duì)列第三章：棧和隊(duì)列31*第三十一頁，共四十頁。串定義：零個(gè)或多個(gè)字符組成的有限序列例子“China”,“BoyandGirl”應(yīng)用語言處理，如編譯器文本檢索專家系統(tǒng)…第四章：串32*第三十二頁，共四十頁。串的操作（一）一個(gè)問題串和線性表操作：賦值和創(chuàng)建：Assign,Create判斷是否相等：Equal計(jì)算長度：Length聯(lián)結(jié)：Concat求子串：SubStr第四章：串33*第三十三頁，共四十頁。串的操作（二）定位：Index置換：Replace插入：Insert刪除：Delete34*第三十四頁，共四十頁。串的存儲(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ù)組35*第三十五頁，共四十頁。串的匹配——KMP算法一種樸素的匹配算法KMP匹配算法出發(fā)點(diǎn)：利用前面匹配的結(jié)果，進(jìn)行無回溯匹配一個(gè)示例匹配的講解模式串：abcac主串：ababcabcacbab36*第三十六頁，共四十頁。串的匹配——KMP算法思考的開始：假定：主串為S1S2…Sn

模式串為

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