數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)課件

1、數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)1線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義：若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。接后繼。 可表示為：（可表示為：（a a1 1 , a, a2 2 , , a, , an n） 簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是簡言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 的。的。特點(diǎn)特點(diǎn) 只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；只有一個(gè)首結(jié)點(diǎn)和尾結(jié)點(diǎn)；特點(diǎn)特點(diǎn) 除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和一個(gè)除首尾結(jié)點(diǎn)外，其他結(jié)點(diǎn)只有一個(gè)直接前驅(qū)和

2、一個(gè)直接后繼。直接后繼。線性結(jié)構(gòu)包括：線性結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、字符串、數(shù)組線性表、堆棧、隊(duì)列、字符串、數(shù)組等，其中最典型、最常用的是等，其中最典型、最常用的是-一對一一對一 (1:1)數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)2數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)32.1 線性表的基本概念線性表的基本概念、線性表、線性表它是一種最簡單的線性結(jié)構(gòu)。是一種可以在任它是一種最簡單的線性結(jié)構(gòu)。是一種可以在任意位置進(jìn)行插入和刪除數(shù)據(jù)元素操作的，由意位置進(jìn)行插入和刪除數(shù)據(jù)元素操作的，由n（n0)個(gè)相同類型數(shù)據(jù)元素個(gè)相同類型數(shù)據(jù)元素a0, a1, , an-1組成的線性結(jié)組成的線性結(jié)構(gòu)。構(gòu)。數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)4（a0, a1,

3、 ai-1，ai, ai1 ，, an-1）n=0時(shí)稱為時(shí)稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素線性起點(diǎn)線性起點(diǎn)ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號(hào)，表示元素序號(hào)，表示元素在表中的位置在表中的位置n為元素總為元素總個(gè)數(shù)，即表個(gè)數(shù)，即表長。長?？毡砜毡砭€性終點(diǎn)線性終點(diǎn)數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)5 （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別成績成績年齡年齡001張東張東女女7023002趙玉鳳趙玉鳳女女 8020003王王 澤澤男男 9019004薛薛 荃荃男男 8121005王 春男 88 8822： ：例例2 分析學(xué)生檔案表是什么結(jié)構(gòu)。分析學(xué)生檔案表是什

4、么結(jié)構(gòu)。分析：分析：數(shù)據(jù)元素都是同類型（數(shù)據(jù)元素都是同類型（記錄記錄），元素間關(guān)系是線性的。），元素間關(guān)系是線性的。分析：分析： 數(shù)據(jù)元素都是同類型（數(shù)據(jù)元素都是同類型（字母字母），）， 元素間關(guān)系是線性的。元素間關(guān)系是線性的。例例1 分析分析26 個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。個(gè)英文字母組成的英文表是什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)6、線性表抽象數(shù)據(jù)類型、線性表抽象數(shù)據(jù)類型 它包括兩個(gè)方面：它包括兩個(gè)方面： 數(shù)據(jù)集合：數(shù)據(jù)集合： a0, a1, , an-1 ai的數(shù)據(jù)類型為的數(shù)據(jù)類型為DataType 操作集合操作集合： (1) InitList(List) 初始化線性表初始化線性表,

5、建一空線性表建一空線性表List (2) ListLength(L) 求當(dāng)前數(shù)據(jù)元素個(gè)數(shù)求當(dāng)前數(shù)據(jù)元素個(gè)數(shù) (3) GetElement(List,i) 取線性表中第取線性表中第 i個(gè)元素（個(gè)元素（1，n） (4) ListInsert(L,i,x) 插入數(shù)據(jù)元素插入數(shù)據(jù)元素 (5)ListDelete(L,i,x) 刪除數(shù)據(jù)元素刪除數(shù)據(jù)元素 (6)ListGet(L,i,x) 取數(shù)據(jù)元素等取數(shù)據(jù)元素等數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)73 3、線性表的存儲(chǔ)結(jié)構(gòu)、線性表的存儲(chǔ)結(jié)構(gòu)(1)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu): :它是使用一片它是使用一片地址連續(xù)地址連續(xù)的有限內(nèi)存單的有限內(nèi)存單元空間存儲(chǔ)數(shù)據(jù)元素的一種計(jì)算

6、機(jī)存儲(chǔ)數(shù)據(jù)方法。元空間存儲(chǔ)數(shù)據(jù)元素的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。特點(diǎn)：特點(diǎn)：( (任意兩個(gè)在邏輯上相鄰的數(shù)據(jù)元素在物理位置任意兩個(gè)在邏輯上相鄰的數(shù)據(jù)元素在物理位置上也必然相鄰上也必然相鄰) )邏輯上相鄰的元素，物理上也相鄰。邏輯上相鄰的元素，物理上也相鄰。(2)(2)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu): :它是把數(shù)據(jù)元素和指針定義成一個(gè)它是把數(shù)據(jù)元素和指針定義成一個(gè)存儲(chǔ)體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來存儲(chǔ)體，使用指針把發(fā)生聯(lián)系的數(shù)據(jù)元素鏈接起來的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。的一種計(jì)算機(jī)存儲(chǔ)數(shù)據(jù)方法。特點(diǎn)：特點(diǎn)：任意兩個(gè)在任意兩個(gè)在邏輯上相鄰邏輯上相鄰的數(shù)據(jù)元素在的數(shù)據(jù)元素在物理上不物理上不一定相鄰一定相

7、鄰，數(shù)據(jù)元素的邏輯次序是通過鏈中的指針，數(shù)據(jù)元素的邏輯次序是通過鏈中的指針鏈接實(shí)現(xiàn)的。鏈接實(shí)現(xiàn)的。數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)82.2 線性表的順序存儲(chǔ)結(jié)構(gòu)及其算法線性表的順序存儲(chǔ)結(jié)構(gòu)及其算法一一 、順序表的存儲(chǔ)結(jié)構(gòu)順序表的存儲(chǔ)結(jié)構(gòu)二、二、 順序表的實(shí)現(xiàn)順序表的實(shí)現(xiàn)三、三、 順序表的運(yùn)算效率分析順序表的運(yùn)算效率分析數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)9一、一、 順序表的存儲(chǔ)結(jié)構(gòu)表示順序表的存儲(chǔ)結(jié)構(gòu)表示 1、順序表順序表：用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。即采用順序存儲(chǔ)結(jié)構(gòu)的線性性表的各個(gè)數(shù)據(jù)元素。即采用順序存儲(chǔ)結(jié)構(gòu)的線性表。它通常采用靜態(tài)數(shù)組實(shí)現(xiàn)數(shù)據(jù)元素的存儲(chǔ)

8、。表。它通常采用靜態(tài)數(shù)組實(shí)現(xiàn)數(shù)據(jù)元素的存儲(chǔ)?？梢岳每梢岳脭?shù)組數(shù)組VnVn來實(shí)現(xiàn)來實(shí)現(xiàn)注意：在注意：在C C語言中數(shù)組的下標(biāo)是從語言中數(shù)組的下標(biāo)是從0 0開始，即：開始，即： VnVn的有效范圍是從的有效范圍是從 V0V0Vn-1Vn-1數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)10(1) 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；(2) 若已知表中首元素在存儲(chǔ)器中的位置，則其他元若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出素存放位置亦可求出（利用數(shù)組利用數(shù)組VnVn的的下標(biāo)下標(biāo)）。）。設(shè)首元素設(shè)首元素a0的存放地址為的存放地址為LOC(a0)（稱為稱為首地址首

9、地址），），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長度）為設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長度）為L字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對上述公式的解釋如圖所示對上述公式的解釋如圖所示2 2、線性表順序存儲(chǔ)特點(diǎn)：、線性表順序存儲(chǔ)特點(diǎn)：數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)11a a0 0a a1 1a ai ia ai+1i+1a an-1n-1 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序0 0i i1 1n-1n-1空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a0)b + + L Lb +i+iL Lb +(n-1)+

10、(n-1)L Lb +(MaxSize-1)+(MaxSize-1)L L3、線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖、線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)124 4、用、用C C語言描述語言描述 typedef struct DateType listMaxSize; int size; SeqList; /* MaxSize表示數(shù)組的最大元素個(gè)數(shù)，list表示順序表的數(shù)組名，size表示順序表中當(dāng)前存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)，它必須滿足size MaxSize，SeqList是該結(jié)構(gòu)體的名字。*/數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)13設(shè)有一維數(shù)組設(shè)有一維數(shù)組，下標(biāo)的范圍是，下標(biāo)的范圍是到到，每個(gè)數(shù)組元素用相鄰的

11、每個(gè)數(shù)組元素用相鄰的個(gè)字節(jié)個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素 的第一個(gè)的第一個(gè)字節(jié)的地址是字節(jié)的地址是，則，則 的第一個(gè)字節(jié)的的第一個(gè)字節(jié)的地址是多少？地址是多少？113LOC( M3 ) = 98 + 5 3 =113解：解：已知地址計(jì)算通式為：已知地址計(jì)算通式為：LOC(ai) = LOC(a0) + L *i例例1 1數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)14 char V30;void build() /*字母線性表的生成，即字母線性表的生成，即建表操作建表操作*/ int i;V0=a;for( i=1; i=n-1; i+ ) Vi=Vi-1+1;

12、核心語句：核心語句：例例2用數(shù)組用數(shù)組V來存放來存放26個(gè)英文字母組成的線性表個(gè)英文字母組成的線性表（a，b，c，z），寫出在順序結(jié)構(gòu)上），寫出在順序結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C語言程序。語言程序。數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)15void main(void) /*主函數(shù)主函數(shù)，字母線性表的，字母線性表的生成和輸出生成和輸出*/ n=26; /* n n是表長，是數(shù)據(jù)元素的個(gè)數(shù)，而不是是表長，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V V的的 實(shí)際下標(biāo)實(shí)際下標(biāo)*/build( );display( );void display( ) /*字母線性表的顯示，即字母線性表的顯示，即讀表操作讀表操作*/ in

13、t i;for( i=0; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一個(gè)位置元素后移一個(gè)位置/ / 插入插入x x / / 表長加表長加1 1 核核心心語語句：句：2)2)插入插入數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)18在線性表的第在線性表的第i i個(gè)位置前插入一個(gè)元素的示意圖如下：個(gè)位置前插入一個(gè)元素的示意圖如下：1213212428304277121321242830427712345678123456789插入插入數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)19實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： 將第將第i+1 至第至第n 位的元素向前移動(dòng)一個(gè)位置；位的元素向前移動(dòng)一個(gè)位置； 表長減表長減1。注意：事

14、先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?刪除線性表的第刪除線性表的第i i個(gè)位置上的元素個(gè)位置上的元素for ( j=i+1; j=n-1; j+ )aj-1=aj; n-;/ / 元素前移一個(gè)位置元素前移一個(gè)位置/ / 表長減表長減1 1 核心語句：核心語句：3)3)刪除刪除數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)20123456789121321242528304277123456781213212428304277刪除順序表中某個(gè)指定的元素的示意圖如下：刪除順序表中某個(gè)指定的元素的示意圖如下：數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)21例：建立一個(gè)線性表，先依次輸入數(shù)據(jù)元素1，2，3，4，10

15、，然后刪除，最后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。假設(shè)該線性的數(shù)據(jù)元素個(gè)數(shù)最壞情況下不會(huì)超過100個(gè)。實(shí)現(xiàn)方法：1、采用直接編寫一個(gè)主函數(shù)實(shí)現(xiàn)。2、利用已設(shè)計(jì)實(shí)現(xiàn)的抽象數(shù)據(jù)類型模塊。（存放在頭文件名為SeqList.h中，通過 #include “SeqList.h” ）數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)22三、三、 順序表操作的效率分析順序表操作的效率分析 算法時(shí)間主要耗費(fèi)在算法時(shí)間主要耗費(fèi)在移動(dòng)元素移動(dòng)元素的操作上，因此的操作上，因此計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語句頻度）計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語句頻度） T(n)= O (移動(dòng)移動(dòng)元素次數(shù)元素次數(shù))而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置

16、而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置.思考：思考：若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；若插入在尾結(jié)點(diǎn)之后，則根本無需移動(dòng)（特別快）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；應(yīng)當(dāng)考慮在各種位置插入（共應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的種可能）的平均平均移動(dòng)次數(shù)才合理。移動(dòng)次數(shù)才合理。時(shí)間效率分析時(shí)間效率分析:數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)23推導(dǎo)：推導(dǎo)：假定在每個(gè)元素位置上插入假定在每個(gè)元素位置上插入x x的可能性都一樣（即的可能性都一樣（即概率概率P P相同），則應(yīng)當(dāng)這樣來計(jì)算平均執(zhí)行時(shí)間：相同），則應(yīng)當(dāng)這樣來計(jì)算

17、平均執(zhí)行時(shí)間：若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1個(gè)元素，后移次數(shù)為個(gè)元素，后移次數(shù)為n-1n-1; ;若在若在a an-1n-1后面插入，要后移后面插入，要后移1 1個(gè)元素；個(gè)元素；若在尾結(jié)點(diǎn)若在尾結(jié)點(diǎn)a an n之后插入，則后移之后插入，則后移0 0個(gè)元素；個(gè)元素；所有可能的元素移動(dòng)次數(shù)合計(jì)所有可能的元素移動(dòng)次數(shù)合計(jì)： 0+1+n0+1+n = n(n+1)/2 = n(n+1)/2故插入時(shí)的平均移動(dòng)次數(shù)為：故插入時(shí)的平均移動(dòng)次數(shù)為：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少種插入形式共有多少種插入形式?連頭帶尾有連頭帶尾有n+1n+1種種! !數(shù)據(jù)結(jié)構(gòu)第2章數(shù)據(jù)結(jié)構(gòu)24同理可證：同理可證：順序表刪除一元素的時(shí)間效率為順序表刪除一元素的時(shí)間效率為: :T T（n)=(n-1)/2 n)=(n-1)/2 插入插入效率：效率：刪除刪除效率：效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin即插入、刪除算法的平