畢業(yè)答辯ppt模板-安徽大學(xué).ppt

《畢業(yè)答辯ppt模板-安徽大學(xué).ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《畢業(yè)答辯ppt模板-安徽大學(xué).ppt（26頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1,線(xiàn)性結(jié)構(gòu)的定義：,若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼?？杀硎緸椋海╝1,a2,,an）,簡(jiǎn)言之，線(xiàn)性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是的。,特點(diǎn)只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；特點(diǎn)除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。,線(xiàn)性結(jié)構(gòu)包括：線(xiàn)性表、堆棧、隊(duì)列、字符串、數(shù)組等，其中最典型、最常用的是------,線(xiàn)性表,一對(duì)一(1:1),2,第2章線(xiàn)性表,2.1線(xiàn)性表的基本概念2.2線(xiàn)性表的順序表示和實(shí)現(xiàn)2.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4應(yīng)用舉例,3,2.1線(xiàn)性表的基本概念,、線(xiàn)性表它是一種最簡(jiǎn)單的線(xiàn)性結(jié)構(gòu)。是一種可以在任意位

2、置進(jìn)行插入和刪除數(shù)據(jù)元素操作的，由n（n0)個(gè)相同類(lèi)型數(shù)據(jù)元素a0,a1,,an-1組成的線(xiàn)性結(jié)構(gòu)。,4,（a0,a1,ai-1，ai,ai1，,an-1）,,線(xiàn)性表的邏輯結(jié)構(gòu)：,n=0時(shí)稱(chēng)為,,數(shù)據(jù)元素,,線(xiàn)性起點(diǎn),,ai的直接前趨,ai的直接后繼,,,下標(biāo)，是元素的序號(hào)，表示元素在表中的位置,n為元素總個(gè)數(shù)，即表長(zhǎng)。n0,空表,線(xiàn)性終點(diǎn),,,,5,（A,B,C,D,,Z）,例2分析學(xué)生情況登記表是什么結(jié)構(gòu)。,分析：數(shù)據(jù)元素都是同類(lèi)型（記錄），元素間關(guān)系是線(xiàn)性的。,分析：數(shù)據(jù)元素都是同類(lèi)型（字母），元素間關(guān)系是線(xiàn)性的。,注意：同一線(xiàn)性表中的元素必定具有相同特性！,例1分析26個(gè)英文字母組成的

3、英文表是什么結(jié)構(gòu)。,6,、線(xiàn)性表抽象數(shù)據(jù)類(lèi)型,它包括兩個(gè)方面：數(shù)據(jù)集合：a0,a1,,an-1ai的數(shù)據(jù)類(lèi)型為DataType操作集合：(1)ListInitiate(L)初始化線(xiàn)性表(2)ListInsert(L,i,x)插入數(shù)據(jù)元素(3)ListLength(L)求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)(4)ListDelete(L,i,x)刪除數(shù)據(jù)元素(5)ListGet(L,i,x)取數(shù)據(jù)元素等,7,3、線(xiàn)性表的存儲(chǔ)結(jié)構(gòu),(1)順序存儲(chǔ)結(jié)構(gòu):它是使用一片地址連續(xù)的有限內(nèi)存單元空間存儲(chǔ)數(shù)據(jù)元素的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。特點(diǎn)：(任意兩個(gè)在邏輯上相鄰的數(shù)據(jù)元素在物理位置上也必然相鄰)邏輯上相鄰的元素，物理上也相鄰

4、。(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):它是把數(shù)據(jù)元素和指針定義成一個(gè)存儲(chǔ)體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來(lái)的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。特點(diǎn)：任意兩個(gè)在邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)元素的邏輯次序是通過(guò)鏈中的指針鏈接實(shí)現(xiàn)的。,8,2.2線(xiàn)性表的順序表示和實(shí)現(xiàn),一、順序表的存儲(chǔ)結(jié)構(gòu)二、順序表的實(shí)現(xiàn)三、順序表的運(yùn)算效率分析,9,一、順序表的存儲(chǔ)結(jié)構(gòu)表示,1、順序表：用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的各個(gè)數(shù)據(jù)元素。即采用順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表。它通常采用靜態(tài)數(shù)組實(shí)現(xiàn)數(shù)據(jù)元素的存儲(chǔ)。,可以利用數(shù)組Vn來(lái)實(shí)現(xiàn),注意：在C語(yǔ)言中數(shù)組的下標(biāo)是從0開(kāi)始，即：Vn的有效范圍是從V0Vn-1,10,(1)邏輯

5、上相鄰的數(shù)據(jù)元素，其物理上也相鄰；(2)若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利用數(shù)組Vn的下標(biāo)）。,設(shè)首元素a0的存放地址為L(zhǎng)OC(a0)（稱(chēng)為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a0)+L*i,對(duì)上述公式的解釋如圖所示,,2、線(xiàn)性表順序存儲(chǔ)特點(diǎn)：,11,地址內(nèi)容元素在表中的位序,0,i,1,n-1,,空閑區(qū),i+1,,L,b=LOC(a0),b+L,b+iL,b+(n-1)L,b+(MaxSize-1)L,LOC(ai)=LOC(a0)+L*i,3、線(xiàn)性表

6、的順序存儲(chǔ)結(jié)構(gòu)示意圖,12,4、用C語(yǔ)言描述,typedefstructDateTypelistMaxSize;intsize;SeqList;/*MaxSize表示數(shù)組的最大元素個(gè)數(shù)，list表示順序表的數(shù)組名，size表示順序表中當(dāng)前存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)，它必須滿(mǎn)足sizeMaxSize，SeqList是該結(jié)構(gòu)體的名字。*/,13,設(shè)有一維數(shù)組，下標(biāo)的范圍是到，每個(gè)數(shù)組元素用相鄰的個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素的第一個(gè)字節(jié)的地址是，則的第一個(gè)字節(jié)的地址是多少？,113,LOC(M3)=98+53=113,解：已知地址計(jì)算通式為：,LOC(ai)=LOC(a0)+L*i,例1,1

7、4,charV30;voidbuild()/*字母線(xiàn)性表的生成，即建表操作*/inti;V0=a;for(i=1;i<=n-1;i++)Vi=Vi-1+1;,核心語(yǔ)句：方法1Vi=Vi-1+1;方法2Vi=a+i;方法3Vi=97+i;,,例2,,用數(shù)組V來(lái)存放26個(gè)英文字母組成的線(xiàn)性表（a，b，c，，z），寫(xiě)出在順序結(jié)構(gòu)上生成和顯示該表的C語(yǔ)言程序。,15,voidmain(void)/*主函數(shù)，字母線(xiàn)性表的生成和輸出*/n=26;/*n是表長(zhǎng)，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V的實(shí)際下標(biāo)*/build();display();,voiddisplay()/*字母線(xiàn)性表的顯示，即讀表操作*/inti

8、;for(i=0;i<=n-1;i++)printf(%c,vi);printf(n);,執(zhí)行結(jié)果：abcdefghijklmnopqrstuvwxyz,16,二、順序表的實(shí)現(xiàn)（或操作）,數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算：修改、插入、刪除、查找、排序,1)修改通過(guò)數(shù)組的下標(biāo)便可訪(fǎng)問(wèn)某個(gè)特定元素并修改之。,核心語(yǔ)句:Vi=x;,顯然，順序表修改操作的時(shí)間效率是O(1),17,在線(xiàn)性表（n個(gè)元素）的第i個(gè)位置前插入一個(gè)元素,實(shí)現(xiàn)步驟：將第n至第i位的元素向后移動(dòng)一個(gè)位置；將要插入的元素寫(xiě)到第i個(gè)位置；表長(zhǎng)加1。注意：事先應(yīng)判斷:插入位置i是否合法?表是否已滿(mǎn)?,for(j=n-1;j=i;j--)aj+1=aj

9、;ai=x;n++;,//元素后移一個(gè)位置,//插入x,//表長(zhǎng)加1,核心語(yǔ)句：,2)插入,18,在線(xiàn)性表的第i個(gè)位置前插入一個(gè)元素的示意圖如下：,插入25,,19,實(shí)現(xiàn)步驟：將第i+1至第n位的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減1。注意：事先需要判斷，刪除位置i是否合法?,刪除線(xiàn)性表的第i個(gè)位置上的元素,for(j=i+1;j<=n-1;j++)aj-1=aj;n--;,//元素前移一個(gè)位置,//表長(zhǎng)減1,核心語(yǔ)句：,3)刪除,20,,刪除順序表中某個(gè)指定的元素的示意圖如下：,21,例：建立一個(gè)線(xiàn)性表，先依次輸入數(shù)據(jù)元素1，2，3，4，，10，然后刪除，最后依次顯示當(dāng)前線(xiàn)性表中的數(shù)據(jù)元素。假設(shè)該線(xiàn)

10、性的數(shù)據(jù)元素個(gè)數(shù)最壞情況下不會(huì)超過(guò)100個(gè)。實(shí)現(xiàn)方法：1、采用直接編寫(xiě)一個(gè)主函數(shù)實(shí)現(xiàn)。2、利用已設(shè)計(jì)實(shí)現(xiàn)的抽象數(shù)據(jù)類(lèi)型模塊。（存放在頭文件名為SeqList.h中，通過(guò)#include“SeqList.h”）,22,三、順序表操作的效率分析,算法時(shí)間主要耗費(fèi)在移動(dòng)元素的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語(yǔ)句頻度）T(n)=O(移動(dòng)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.,思考：若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的平均移動(dòng)次數(shù)才合理。,時(shí)間效率分析:,23,推導(dǎo)：假定在

11、每個(gè)元素位置上插入x的可能性都一樣（即概率P相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間：將所有位置的執(zhí)行時(shí)間相加，然后取平均。若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移n次；若在a1后面插入，要后移n-1個(gè)元素，后移次數(shù)為n-1;若在an-1后面插入，要后移1個(gè)元素；若在尾結(jié)點(diǎn)an之后插入，則后移0個(gè)元素；所有可能的元素移動(dòng)次數(shù)合計(jì)：0+1++n=n(n+1)/2,故插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2（n+1）n/2O(n),共有多少種插入形式?連頭帶尾有n+1種!,,24,同理可證：順序表刪除一元素的時(shí)間效率為:T（n)=(n-1)/2O(n),插入效率：,刪除效率：,教材P33有對(duì)執(zhí)行效率的推導(dǎo)：（與課本略有區(qū)別）,即插入、刪除算法的平均時(shí)間復(fù)雜度為O(n),25,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),本節(jié)小結(jié),線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素，方便快捷；缺點(diǎn)：在插入或刪除某一元素時(shí)，需要移動(dòng)大量元素。解決問(wèn)題的思路：改用另一種線(xiàn)性存儲(chǔ)方式：,26,作業(yè)：,P552-1,2-2,2-11,2-15,