《畢業(yè)答辯ppt模板-安徽大學.ppt》由會員分享，可在線閱讀，更多相關《畢業(yè)答辯ppt模板-安徽大學.ppt（26頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、1,線性結構的定義：,若結構是非空有限集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼。可表示為：（a1,a2,,an）,簡言之，線性結構反映結點間的邏輯關系是的。,特點只有一個首結點和尾結點；特點除首尾結點外，其他結點只有一個直接前驅和一個直接后繼。,線性結構包括：線性表、堆棧、隊列、字符串、數(shù)組等，其中最典型、最常用的是------,線性表,一對一(1:1),2,第2章線性表,2.1線性表的基本概念2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈式表示和實現(xiàn)2.4應用舉例,3,2.1線性表的基本概念,、線性表它是一種最簡單的線性結構。是一種可以在任意位
2、置進行插入和刪除數(shù)據(jù)元素操作的，由n（n0)個相同類型數(shù)據(jù)元素a0,a1,,an-1組成的線性結構。,4,（a0,a1,ai-1，ai,ai1，,an-1）,,線性表的邏輯結構：,n=0時稱為,,數(shù)據(jù)元素,,線性起點,,ai的直接前趨,ai的直接后繼,,,下標，是元素的序號，表示元素在表中的位置,n為元素總個數(shù)，即表長。n0,空表,線性終點,,,,5,（A,B,C,D,,Z）,例2分析學生情況登記表是什么結構。,分析：數(shù)據(jù)元素都是同類型（記錄），元素間關系是線性的。,分析：數(shù)據(jù)元素都是同類型（字母），元素間關系是線性的。,注意：同一線性表中的元素必定具有相同特性！,例1分析26個英文字母組成的
3、英文表是什么結構。,6,、線性表抽象數(shù)據(jù)類型,它包括兩個方面：數(shù)據(jù)集合：a0,a1,,an-1ai的數(shù)據(jù)類型為DataType操作集合：(1)ListInitiate(L)初始化線性表(2)ListInsert(L,i,x)插入數(shù)據(jù)元素(3)ListLength(L)求當前數(shù)據(jù)元素個數(shù)(4)ListDelete(L,i,x)刪除數(shù)據(jù)元素(5)ListGet(L,i,x)取數(shù)據(jù)元素等,7,3、線性表的存儲結構,(1)順序存儲結構:它是使用一片地址連續(xù)的有限內(nèi)存單元空間存儲數(shù)據(jù)元素的一種計算機存儲數(shù)據(jù)方法。特點：(任意兩個在邏輯上相鄰的數(shù)據(jù)元素在物理位置上也必然相鄰)邏輯上相鄰的元素，物理上也相鄰
4、。(2)鏈式存儲結構:它是把數(shù)據(jù)元素和指針定義成一個存儲體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來的一種計算機存儲數(shù)據(jù)方法。特點：任意兩個在邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)元素的邏輯次序是通過鏈中的指針鏈接實現(xiàn)的。,8,2.2線性表的順序表示和實現(xiàn),一、順序表的存儲結構二、順序表的實現(xiàn)三、順序表的運算效率分析,9,一、順序表的存儲結構表示,1、順序表：用一組地址連續(xù)的存儲單元依次存儲線性表的各個數(shù)據(jù)元素。即采用順序存儲結構的線性表。它通常采用靜態(tài)數(shù)組實現(xiàn)數(shù)據(jù)元素的存儲。,可以利用數(shù)組Vn來實現(xiàn),注意：在C語言中數(shù)組的下標是從0開始，即：Vn的有效范圍是從V0Vn-1,10,(1)邏輯
5、上相鄰的數(shù)據(jù)元素，其物理上也相鄰；(2)若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數(shù)組Vn的下標）。,設首元素a0的存放地址為LOC(a0)（稱為首地址），設每個元素占用存儲空間（地址長度）為L字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a0)+L*i,對上述公式的解釋如圖所示,,2、線性表順序存儲特點：,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、線性表
6、的順序存儲結構示意圖,12,4、用C語言描述,typedefstructDateTypelistMaxSize;intsize;SeqList;/*MaxSize表示數(shù)組的最大元素個數(shù)，list表示順序表的數(shù)組名，size表示順序表中當前存儲的數(shù)據(jù)元素個數(shù)，它必須滿足sizeMaxSize，SeqList是該結構體的名字。*/,13,設有一維數(shù)組，下標的范圍是到，每個數(shù)組元素用相鄰的個字節(jié)存儲。存儲器按字節(jié)編址，設存儲數(shù)組元素的第一個字節(jié)的地址是，則的第一個字節(jié)的地址是多少？,113,LOC(M3)=98+53=113,解：已知地址計算通式為：,LOC(ai)=LOC(a0)+L*i,例1,1
7、4,charV30;voidbuild()/*字母線性表的生成，即建表操作*/inti;V0=a;for(i=1;i<=n-1;i++)Vi=Vi-1+1;,核心語句：方法1Vi=Vi-1+1;方法2Vi=a+i;方法3Vi=97+i;,,例2,,用數(shù)組V來存放26個英文字母組成的線性表（a，b，c，，z），寫出在順序結構上生成和顯示該表的C語言程序。,15,voidmain(void)/*主函數(shù)，字母線性表的生成和輸出*/n=26;/*n是表長，是數(shù)據(jù)元素的個數(shù)，而不是V的實際下標*/build();display();,voiddisplay()/*字母線性表的顯示，即讀表操作*/inti
8、;for(i=0;i<=n-1;i++)printf(%c,vi);printf(n);,執(zhí)行結果：abcdefghijklmnopqrstuvwxyz,16,二、順序表的實現(xiàn)（或操作）,數(shù)據(jù)結構的基本運算：修改、插入、刪除、查找、排序,1)修改通過數(shù)組的下標便可訪問某個特定元素并修改之。,核心語句:Vi=x;,顯然，順序表修改操作的時間效率是O(1),17,在線性表（n個元素）的第i個位置前插入一個元素,實現(xiàn)步驟：將第n至第i位的元素向后移動一個位置；將要插入的元素寫到第i個位置；表長加1。注意：事先應判斷:插入位置i是否合法?表是否已滿?,for(j=n-1;j=i;j--)aj+1=aj
9、;ai=x;n++;,//元素后移一個位置,//插入x,//表長加1,核心語句：,2)插入,18,在線性表的第i個位置前插入一個元素的示意圖如下：,插入25,,19,實現(xiàn)步驟：將第i+1至第n位的元素向前移動一個位置；表長減1。注意：事先需要判斷，刪除位置i是否合法?,刪除線性表的第i個位置上的元素,for(j=i+1;j<=n-1;j++)aj-1=aj;n--;,//元素前移一個位置,//表長減1,核心語句：,3)刪除,20,,刪除順序表中某個指定的元素的示意圖如下：,21,例：建立一個線性表，先依次輸入數(shù)據(jù)元素1，2，3，4，，10，然后刪除，最后依次顯示當前線性表中的數(shù)據(jù)元素。假設該線
10、性的數(shù)據(jù)元素個數(shù)最壞情況下不會超過100個。實現(xiàn)方法：1、采用直接編寫一個主函數(shù)實現(xiàn)。2、利用已設計實現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為SeqList.h中，通過#include“SeqList.h”）,22,三、順序表操作的效率分析,算法時間主要耗費在移動元素的操作上，因此計算時間復雜度的基本操作（最深層語句頻度）T(n)=O(移動元素次數(shù))而移動元素的個數(shù)取決于插入或刪除元素的位置.,思考：若插入在尾結點之后，則根本無需移動（特別快）；若插入在首結點之前，則表中元素全部要后移（特別慢）；應當考慮在各種位置插入（共n+1種可能）的平均移動次數(shù)才合理。,時間效率分析:,23,推導：假定在
11、每個元素位置上插入x的可能性都一樣（即概率P相同），則應當這樣來計算平均執(zhí)行時間：將所有位置的執(zhí)行時間相加，然后取平均。若在首結點前插入，需要移動的元素最多，后移n次；若在a1后面插入，要后移n-1個元素，后移次數(shù)為n-1;若在an-1后面插入，要后移1個元素；若在尾結點an之后插入，則后移0個元素；所有可能的元素移動次數(shù)合計：0+1++n=n(n+1)/2,故插入時的平均移動次數(shù)為：n(n+1)/2（n+1）n/2O(n),共有多少種插入形式?連頭帶尾有n+1種!,,24,同理可證：順序表刪除一元素的時間效率為:T（n)=(n-1)/2O(n),插入效率：,刪除效率：,教材P33有對執(zhí)行效率的推導：（與課本略有區(qū)別）,即插入、刪除算法的平均時間復雜度為O(n),25,鏈式存儲結構,本節(jié)小結,線性表順序存儲結構特點：邏輯關系上相鄰的兩個元素在物理存儲位置上也相鄰；優(yōu)點：可以隨機存取表中任一元素，方便快捷；缺點：在插入或刪除某一元素時，需要移動大量元素。解決問題的思路：改用另一種線性存儲方式：,26,作業(yè)：,P552-1,2-2,2-11,2-15,
畢業(yè)答辯ppt模板-安徽大學.ppt
