數(shù)據(jù)結(jié)構(gòu)線性表A

1、Recap: 數(shù)據(jù)結(jié)構(gòu)的定位 第二章：線性表1 介于數(shù)學(xué)、計(jì)算 機(jī)硬件和計(jì)算機(jī) 軟件三者之間的 一門(mén)核心課程 大數(shù)據(jù)時(shí)代的核 心問(wèn)題 Recap: 什么是數(shù)據(jù)結(jié)構(gòu)？ 第二章：線性表2 問(wèn)題分類：數(shù)值問(wèn)題、非數(shù)值問(wèn)題問(wèn)題分類：數(shù)值問(wèn)題、非數(shù)值問(wèn)題 數(shù) 值 問(wèn) 題數(shù)學(xué)方程 非數(shù)值問(wèn)題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別出生日期出生日期二外二外 10001王王 軍軍男男1993/09/02法語(yǔ) 20003李李 明明男男1992/12/25西語(yǔ) Recap: 什么是數(shù)據(jù)結(jié)構(gòu)？ 第二章：線性表3 Data_Structure=（D, S） 元素有限集 關(guān)系有限集 相互之間存在一種或多種特定相互之間

2、存在一種或多種特定關(guān)系關(guān)系的的數(shù)據(jù)元素?cái)?shù)據(jù)元素 的集合，表示為：的集合，表示為： 程序設(shè)計(jì)好算法好結(jié)構(gòu)程序設(shè)計(jì)好算法好結(jié)構(gòu) Recap: 基本概念 第二章：線性表4 數(shù)據(jù)數(shù)據(jù) (data)：所有能所有能輸入輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序到計(jì)算機(jī)中并能被計(jì)算機(jī)程序識(shí)別和識(shí)別和 處理處理的符號(hào)集合。的符號(hào)集合。 數(shù)據(jù)元素?cái)?shù)據(jù)元素 (data element)：數(shù)據(jù)的數(shù)據(jù)的基本基本單位，在計(jì)算機(jī)程單位，在計(jì)算機(jī)程 序中通常作為一個(gè)序中通常作為一個(gè)整體整體進(jìn)行考慮和處理。進(jìn)行考慮和處理。 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) (data item)：構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。 三者之

3、間的關(guān)系：三者之間的關(guān)系：數(shù)據(jù)數(shù)據(jù) 數(shù)據(jù)元素?cái)?shù)據(jù)元素 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng) Recap: 數(shù)據(jù)結(jié)構(gòu)主要內(nèi)容 第二章：線性表5 Recap: 邏輯結(jié)構(gòu) 第二章：線性表6 集合結(jié)構(gòu)集合結(jié)構(gòu)： 僅同屬一個(gè)集合 線性結(jié)構(gòu)線性結(jié)構(gòu): 一對(duì)一 (1:1) 樹(shù)結(jié)構(gòu)樹(shù)結(jié)構(gòu): 一對(duì)多 (1:n) 圖結(jié)構(gòu)圖結(jié)構(gòu): 多對(duì)多 (m:n) 非線性 線 性 指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它 與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是，是獨(dú)立于計(jì)算機(jī)獨(dú)立于計(jì)算機(jī)的。的。 Recap: 存儲(chǔ)結(jié)構(gòu) 第二章：線性表7 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中通常有以二種 不同的表示方

4、法，對(duì)應(yīng)二種不同的存儲(chǔ)結(jié)構(gòu) 順序映象順序映象 順序存儲(chǔ)結(jié)構(gòu) 非順序映象非順序映象 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 復(fù)數(shù)復(fù)數(shù)的兩種存儲(chǔ)方式：的兩種存儲(chǔ)方式： 2.30302 3.00300 0302 3.00300 0415 2.3 地址地址 內(nèi)容內(nèi)容 地址地址 內(nèi)容內(nèi)容 2字節(jié)字節(jié) 2字節(jié)字節(jié) Recap:抽象數(shù)據(jù)類型的定義 第二章：線性表8 ADT = ADT = （D D，S S，P P） 數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象 D D上的關(guān)系集上的關(guān)系集 D D上的操作集上的操作集 ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)數(shù)據(jù)對(duì)象對(duì)象： 數(shù)據(jù)數(shù)據(jù)關(guān)系關(guān)系： 基本操作基本操作 ： ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名

5、第二章：線性表9 Recap:抽象數(shù)據(jù)類型定義 定義并實(shí)現(xiàn)定義并實(shí)現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型復(fù)數(shù)抽象數(shù)據(jù)類型（定義定義） ADT ComplexADT Complex 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象：D = c1, c2 | c1, c2 D = c1, c2 | c1, c2 R(R R(R為實(shí)數(shù)集）為實(shí)數(shù)集） 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：S = S = （ c1 c1為實(shí)部，為實(shí)部，c2c2為虛部）為虛部） 基本操作：基本操作： void Assign(void Assign(* *A, c1, c2A, c1, c2） void Add( void Add(* *A, B)A, B) void Minus( voi

6、d Minus(* *A, B)A, B) void Multiply( void Multiply(* *A, B)A, B) void Divide( void Divide(* *A, B)A, B) . ADT ComplexADT Complex Recap:抽象數(shù)據(jù)類型定義 第二章：線性表10 定義并實(shí)現(xiàn)定義并實(shí)現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型復(fù)數(shù)抽象數(shù)據(jù)類型（實(shí)現(xiàn)實(shí)現(xiàn)/ /類類C C描述描述） typedef ItemTypetypedef ItemTypedouble;double; typedef structtypedef struct ItemTypeItemTyper ;r ; It

7、emTypeItemTypev;v; Complex;Complex;/ /* * 復(fù)數(shù)抽象數(shù)據(jù)類型復(fù)數(shù)抽象數(shù)據(jù)類型 * */ / void Assign(Complex void Assign(Complex * *A, ItemType r, ItemType v); A, ItemType r, ItemType v); void Add(Complex void Add(Complex * *A, Complex B);A, Complex B);/ /* * A+B A+B * */ / void Minus(Complex void Minus(Complex * *A, Comp

8、lex B);A, Complex B);/ /* * A-B A-B * */ / void Multiply(Compex void Multiply(Compex * *A, Complex B); /A, Complex B); /* * A A* *B B * */ / void Divide(Complex void Divide(Complex * *A, Complex B);A, Complex B);/ /* * A/B A/B * */ / . Recap:算法分析 第二章：線性表11 正確性正確性 時(shí)間代價(jià)時(shí)間代價(jià)(時(shí)間復(fù)雜度時(shí)間復(fù)雜度) 空間代價(jià)空間代價(jià) (空間復(fù)雜度

9、空間復(fù)雜度) 最優(yōu)性最優(yōu)性 Recap: 算法效率度量 第二章：線性表12 O： 當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù) C，使得對(duì)所有使得對(duì)所有 的的 n n0 ，有有 f(n) Cg(n)，則則 f(n) = O(g(n) 100n+6=O(n) /* 100n+6 101n for n 6 */ 10n2+4n+2=O(n2) /* 10n2+4n+2 11n2 for n 5 */ 6*2n+n2=O(2n) /* 6*2n+n2 7*2n for n 4 */ 面試: 順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)？ 第二章：線性表13 學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別出生日期出生日期二外二外 10001王

10、王 軍軍男男1993/09/02法語(yǔ) 20003李李 明明男男1992/12/25西語(yǔ) 反問(wèn)：操作是什么？ 14 第第1章章 緒論緒論 第第2章章 線性表線性表 第第3章章 棧和隊(duì)列棧和隊(duì)列 第第4章章 串串 第第5章章 數(shù)組和廣義表數(shù)組和廣義表 第第6 6章章 樹(shù)和二叉樹(shù)樹(shù)和二叉樹(shù) 第第7章章 圖圖 第第9章章 查找查找 第第10章章 排序排序 目目 錄錄 第二章：線性表 什么是什么是 線性結(jié)構(gòu)？線性結(jié)構(gòu)？ 15第二章：線性表 16 線性結(jié)構(gòu)的定義：線性結(jié)構(gòu)的定義： 若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)若結(jié)構(gòu)是非空有限集，則有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè) 終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多

11、只有一個(gè)直接前趨和一個(gè)直終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直 接后繼。接后繼。 可表示為：（可表示為：（a a1 1 , a , a2 2 , , , a, an n） 簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是簡(jiǎ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ū)和一個(gè) 直接后繼。直接后繼。 線性結(jié)構(gòu)包括：線性結(jié)構(gòu)包括：線性表、堆棧、隊(duì)列、字符串、數(shù)組線性表、堆棧、隊(duì)列、字符串、數(shù)組 等，其中最典型、最常用的是等，其中最典型、最常用的

12、是- 一對(duì)一一對(duì)一 (1:1) 第二章：線性表 17第二章：線性表 18 （a1, a2, ai-1， ，ai, ai1 ， ，, an） 2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 用數(shù)據(jù)元素的有限序列表示用數(shù)據(jù)元素的有限序列表示 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ù)，即表 長(zhǎng)。長(zhǎng)。 空表空表 線性終點(diǎn)線性終點(diǎn) 2.1 線性表的邏輯結(jié)構(gòu) 19 （ A, B, C, D, , Z） 學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡

13、年齡班級(jí)班級(jí) U200713569李春元李春元男男19通信工程通信工程200701班班 U200713611李煜墉李煜墉男男19通信工程通信工程200701班班 U200713537張祺軒張祺軒男男19通信工程通信工程200702班班 ： ： 例例2 分析學(xué)生情況登記表是什么結(jié)構(gòu)。分析學(xué)生情況登記表是什么結(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è)英文

14、字母組成的英文表是什么結(jié)構(gòu)。 2.1 線性表的邏輯結(jié)構(gòu) 20 “同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性” 是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。 試判斷下列敘述的正誤：試判斷下列敘述的正誤： 2.1 線性表的邏輯結(jié)構(gòu) 21 2.2.1 順序表的表示順序表的表示 用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次的存儲(chǔ)單元依次 存儲(chǔ)線性表的元素。存儲(chǔ)線性表的元素。 把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物 理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。 線性表的順序表

15、示又稱為線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或順序映像?；蝽樞蛴诚?。 順序存儲(chǔ)定義：順序存儲(chǔ)定義： 順序存儲(chǔ)方法：順序存儲(chǔ)方法： 特點(diǎn)：特點(diǎn)：邏輯上相鄰的元素，物理上也相鄰邏輯上相鄰的元素，物理上也相鄰 可以利用可以利用數(shù)組數(shù)組VnVn來(lái)實(shí)現(xiàn)來(lái)實(shí)現(xiàn) 注意：在注意：在C C語(yǔ)言中數(shù)組的下標(biāo)是從語(yǔ)言中數(shù)組的下標(biāo)是從0 0開(kāi)始，即：開(kāi)始，即： VVn n 的有效范圍是從的有效范圍是從 VV0 0 VVn-1n-1 2.2.1 順序表的表示 22 1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰； 2. 若已知表中首元素在存儲(chǔ)器中的位置，則其他元若已知表中首元

16、素在存儲(chǔ)器中的位置，則其他元 素存放位置亦可求出素存放位置亦可求出（利用數(shù)組利用數(shù)組VnVn的的下標(biāo)下標(biāo)）。）。 設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為L(zhǎng)OC(a1)（稱為稱為首地址首地址），）， 設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，字節(jié)， 則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對(duì)上述公式的解釋如圖所示對(duì)上述公式的解釋如圖所示 線性表順序存儲(chǔ)特點(diǎn)：線性表順序存儲(chǔ)特點(diǎn)： 2.2.1 順序表的表示 23 a a1 1 a a2 2 a ai i a ai+1 i+

17、1 a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序 1 1 i i 2 2 n n 空閑區(qū)空閑區(qū) i+1i+1 L b=LOC(a1) b + + L L b +(i-1)+(i-1)L L b +(n-1)+(n-1)L L b +(max-1)+(max-1)L L 線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖 下標(biāo)起下標(biāo)起 點(diǎn)是點(diǎn)是1 1 2.2.1 順序表的表示 24 設(shè)有一維數(shù)組設(shè)有一維數(shù)組，下標(biāo)的范圍是，下標(biāo)的范圍是到到，每個(gè)數(shù)，每個(gè)數(shù) 組元素用相鄰的組元素用相鄰的個(gè)字節(jié)個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，存儲(chǔ)。存儲(chǔ)器按字節(jié)編址， 設(shè)存儲(chǔ)數(shù)組元素設(shè)存儲(chǔ)數(shù)組元素

18、 的第一個(gè)字節(jié)的地址是的第一個(gè)字節(jié)的地址是9898，則，則 的第一個(gè)字節(jié)的地址是多少？的第一個(gè)字節(jié)的地址是多少？ 答案：答案：113 但此題要注意下標(biāo)起點(diǎn)是從但此題要注意下標(biāo)起點(diǎn)是從0 0開(kāi)始：開(kāi)始： LOC( M3 ) = 98 + 5 (4-1) =113 解：解：已知地址計(jì)算通式為：已知地址計(jì)算通式為： LOC(ai) = LOC(a1) + L *（i-1） 例例1 1 或用（或用（3-0） 2.2.1 順序表的表示 25 char V30; void build() /字母線性表的字母線性表的生成生成，即建表操作，即建表操作 int i; V0=a; for( i=1; i=n-1;

19、 i+ ) Vi=Vi-1+1; 核心語(yǔ)句：核心語(yǔ)句： 例例2用數(shù)組用數(shù)組V來(lái)存放來(lái)存放26個(gè)英文字母組成的線性表（個(gè)英文字母組成的線性表（a，b， c，z），寫(xiě)出在順序結(jié)構(gòu)上），寫(xiě)出在順序結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C語(yǔ)言語(yǔ)言 程序。程序。 省略了省略了includeinclude語(yǔ)句語(yǔ)句 2.2.1 順序表的表示 26 void main(void) /主函數(shù)，字母線性表的主函數(shù)，字母線性表的生成和輸出生成和輸出 n=26; / n n是表長(zhǎng)，是數(shù)據(jù)元素的個(gè)數(shù)，而不是是表長(zhǎng)，是數(shù)據(jù)元素的個(gè)數(shù)，而不是V V的實(shí)際下標(biāo)的實(shí)際下標(biāo) build( ); display( ); void

20、display( ) /字母線性表的字母線性表的顯示顯示，即讀表操作，即讀表操作 int i; for( i=0; i=i; j ) aj+1=a j ; a i =x; n+; / / 元素后移一個(gè)位置元素后移一個(gè)位置 / / 插入插入x x / / 表長(zhǎng)加表長(zhǎng)加1 1 核核 心心 語(yǔ)語(yǔ) 句：句： 2)2)插入插入 2.2.2 順序表的操作 29 在線性表的第在線性表的第i i個(gè)位置前插入一個(gè)元素的示意圖如下：個(gè)位置前插入一個(gè)元素的示意圖如下： 12 13 21 24 28 30 42 77 12 13 21 24 25 28 30 42 77 1 2 3 4 5 6 7 8 1 2 3 4

21、 5 6 7 8 9 插入插入 2.2.2 順序表的操作 30 實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： 將第將第i+1 至第至第n 位的元素向前移動(dòng)一個(gè)位置；位的元素向前移動(dòng)一個(gè)位置； 表長(zhǎng)減表長(zhǎng)減1。 注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法? 應(yīng)當(dāng)符合條件：應(yīng)當(dāng)符合條件：1in 或或 i=1, n 刪除線性表的第刪除線性表的第i i個(gè)位置上的元素個(gè)位置上的元素 for ( j=i+1; j=n; j+ ) aj-1=aj; n-; / / 元素前移一個(gè)位置元素前移一個(gè)位置 / / 表長(zhǎng)減表長(zhǎng)減1 1 核心語(yǔ)句：核心語(yǔ)句： 3)3)刪除刪除 2.2.2 順序表的操作 31

22、1 2 3 4 5 6 7 8 9 12 13 21 24 25 28 30 42 77 1 2 3 4 5 6 7 8 12 13 21 24 28 30 42 77 刪除順序表中某個(gè)指定的元素的示意圖如下：刪除順序表中某個(gè)指定的元素的示意圖如下： 順序表插入和刪除的完整程序請(qǐng)同學(xué)們自編，順序表插入和刪除的完整程序請(qǐng)同學(xué)們自編， 并務(wù)必上機(jī)驗(yàn)證！并務(wù)必上機(jī)驗(yàn)證！ 2.2.2 順序表的操作 32 2.2.3 順序表的運(yùn)算效率分析順序表的運(yùn)算效率分析 算法時(shí)間主要耗費(fèi)在算法時(shí)間主要耗費(fèi)在移動(dòng)元素移動(dòng)元素的操作上，因此的操作上，因此 計(jì)算時(shí)間復(fù)雜度的基本操作（最深層語(yǔ)句頻度）計(jì)算時(shí)間復(fù)雜度的基本操

23、作（最深層語(yǔ)句頻度） T(n)= O (移動(dòng)元素次數(shù)移動(dòng)元素次數(shù)) 而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。 思考：思考：若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）；若插入在尾結(jié)點(diǎn)之后，則根本無(wú)需移動(dòng)（特別快）； 若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）；若插入在首結(jié)點(diǎn)之前，則表中元素全部要后移（特別慢）； 應(yīng)當(dāng)考慮在各種位置插入（共應(yīng)當(dāng)考慮在各種位置插入（共n+1種可能）的種可能）的平均平均移動(dòng)次數(shù)才合理。移動(dòng)次數(shù)才合理。 討論討論1：若在長(zhǎng)度為若在長(zhǎng)度為 n 的線性表的第的線性表的第 i 位前位前 插入插入一個(gè)元素，一個(gè)元素， 則

24、向后移動(dòng)元素的次數(shù)則向后移動(dòng)元素的次數(shù)f(n)為為: f(n) = n i + 1 時(shí)間效率分析時(shí)間效率分析: 2.2.3 順序表的運(yùn)算效率分析 33 推導(dǎo)：推導(dǎo)：假定在每個(gè)元素位置上插入假定在每個(gè)元素位置上插入x x的可能性都一樣（即的可能性都一樣（即 概率概率P P相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間：相同），則應(yīng)當(dāng)這樣來(lái)計(jì)算平均執(zhí)行時(shí)間： 若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移次數(shù)為若在首結(jié)點(diǎn)前插入，需要移動(dòng)的元素最多，后移次數(shù)為n n； 若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1個(gè)元素，后移次數(shù)為個(gè)元素，后移次數(shù)為n-1n-1; ; 若在若在a an-1n-1

25、后面插入，后移次數(shù)為后面插入，后移次數(shù)為1 1； 若在尾結(jié)點(diǎn)若在尾結(jié)點(diǎn)a an n之后插入，則后移次數(shù)為之后插入，則后移次數(shù)為0 0； 故插入時(shí)的故插入時(shí)的平均平均移動(dòng)次數(shù)為：移動(dòng)次數(shù)為：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少種插入形式共有多少種插入形式? ?連頭帶尾有連頭帶尾有n+1n+1種種! ! 所有所有可能的元素移動(dòng)次數(shù)合計(jì)可能的元素移動(dòng)次數(shù)合計(jì)： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/2 2.2.3 順序表的運(yùn)算效率分析 34 同理可證：同理可證：順序表刪除一元素的時(shí)間效率為順序表刪除一元素的時(shí)間效率為: : T T（n)=(

26、n-1)/2 n)=(n-1)/2 順序表插入、刪除算法的順序表插入、刪除算法的平均平均空間空間復(fù)雜度復(fù)雜度為多少？為多少？ 插入效率：插入效率： 刪除效率：刪除效率： 11 11 1 (1)(1) 12 nn isi ii n Ep nini n 11 11 ()() 2 nn dli ii n Eq nini n 教材教材P25算法算法2.5也是對(duì)執(zhí)行效率的推導(dǎo)：也是對(duì)執(zhí)行效率的推導(dǎo)： 因?yàn)闆](méi)有占用輔助空間！因?yàn)闆](méi)有占用輔助空間！ 含義：對(duì)于順序表，插入、刪除操含義：對(duì)于順序表，插入、刪除操 作平均需要移動(dòng)一半元素作平均需要移動(dòng)一半元素( n / 2 ) O(1)O(1) 即插入、刪除算法

27、的平均即插入、刪除算法的平均 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n) 35 線性表的抽象數(shù)據(jù)類型定義線性表的抽象數(shù)據(jù)類型定義（見(jiàn)教材見(jiàn)教材P19） ADT List 數(shù)據(jù)數(shù)據(jù)對(duì)象對(duì)象：D=ai | aiElemSet, i=1, 2, , n, n0 數(shù)據(jù)數(shù)據(jù)關(guān)系關(guān)系：R= | ai 1, ai D, i=2, n 基本基本操作操作： 初始化、撤銷、清空、判空；初始化、撤銷、清空、判空； 求表長(zhǎng)、表頭、表尾、前趨、后繼；求表長(zhǎng)、表頭、表尾、前趨、后繼； 讀元素、查找（含定位）、遍歷；讀元素、查找（含定位）、遍歷； 插入、刪除插入、刪除 ADT List 什么是什么是 線性結(jié)構(gòu)？線性結(jié)構(gòu)？ 36第二

28、章：線性表 Recap 37 用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次的存儲(chǔ)單元依次 存儲(chǔ)線性表的元素。存儲(chǔ)線性表的元素。 把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物 理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。 線性表的順序表示又稱為線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或順序映像。或順序映像。 順序存儲(chǔ)定義：順序存儲(chǔ)定義： 順序存儲(chǔ)方法：順序存儲(chǔ)方法： 特點(diǎn)：特點(diǎn)：邏輯上相鄰的元素，物理上也相鄰邏輯上相鄰的元素，物理上也相鄰 可以利用可以利用數(shù)組數(shù)組VnVn來(lái)實(shí)現(xiàn)來(lái)實(shí)現(xiàn) 2.2.1 順序表的表示 Recap: 38 順序表插入、刪除算法的順序

29、表插入、刪除算法的平均平均空間空間復(fù)雜度復(fù)雜度為多少？為多少？ 插入效率：插入效率： 刪除效率：刪除效率： 11 11 1 (1)(1) 12 nn isi ii n Ep nini n 11 11 ()() 2 nn dli ii n Eq nini n 因?yàn)闆](méi)有占用輔助空間！因?yàn)闆](méi)有占用輔助空間！ 含義：對(duì)于順序表，插入、刪除操含義：對(duì)于順序表，插入、刪除操 作平均需要移動(dòng)一半元素作平均需要移動(dòng)一半元素( n / 2 ) O(1)O(1) 即插入、刪除算法的平均即插入、刪除算法的平均 時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為 O(n) Recap: 39 線性表的基本操作如何表示？線性表的基本操作如何表示

30、？ （見(jiàn)教材（見(jiàn)教材P19） InitList( /建空表，初始化建空表，初始化 DestoryList( /撤銷表，釋放內(nèi)存撤銷表，釋放內(nèi)存 int LengthList( L ); /求表中元素個(gè)數(shù)，即表長(zhǎng)求表中元素個(gè)數(shù)，即表長(zhǎng) POSITION LocateElem (L,ElemType e，compare() ) /查找查找e PriorElem( L, cur_e, /求當(dāng)前元素求當(dāng)前元素e的前驅(qū)的前驅(qū) NextElem( L, cur_e, /求當(dāng)前元素求當(dāng)前元素e的后繼的后繼 ListInsertBefore( /把把e插入到第插入到第i個(gè)元素之前個(gè)元素之前 ListDelet

31、e( /刪除第刪除第i個(gè)元素并個(gè)元素并“看看”此元素此元素 ListTraverse( L, Visit() ); / “看看”表中全部元素（遍歷）表中全部元素（遍歷） l初始化、撤銷、清空、判空；初始化、撤銷、清空、判空； l求表長(zhǎng)、表頭、表尾、前趨、后繼；求表長(zhǎng)、表頭、表尾、前趨、后繼； l讀元素、查找（含定位）、遍歷；讀元素、查找（含定位）、遍歷； l插入、刪除插入、刪除 40 結(jié)構(gòu)體 結(jié)構(gòu)體 結(jié)構(gòu)體是一種構(gòu)造數(shù)據(jù)類型 用途：把不同類型的數(shù)據(jù)組合成一個(gè)整體-自定 義數(shù)據(jù)類型 結(jié)構(gòu)體類型定義 struct 結(jié)構(gòu)體名 類型標(biāo)識(shí)符 成員名； 類型標(biāo)識(shí)符 成員名； . ； 成員類型可以是 基本型

32、或構(gòu)造型 struct是關(guān)鍵字, 不能省略 合法標(biāo)識(shí)符 可省:無(wú)名結(jié)構(gòu)體 41 例 struct student int num; char name20; char sex; int age; float score; char addr30; ; name num sex age score addr 2字節(jié) 2字節(jié) 20字節(jié) 1字節(jié) 4字節(jié) 30字節(jié) . 結(jié)構(gòu)體類型定義描述結(jié)構(gòu) 的組織形式,不分配內(nèi)存 結(jié)構(gòu)體類型定義的作用域 42 例 struct student int num; char name20; char sex; int age; float score; char add

33、r30; ; struct student stu1,stu2; 結(jié)構(gòu)體變量的定義結(jié)構(gòu)體變量的定義 先定義結(jié)構(gòu)體類型，再定義結(jié)構(gòu)體變量 一般形式： struct 結(jié)構(gòu)體名 類型標(biāo)識(shí)符 成員名； 類型標(biāo)識(shí)符 成員名； . ； struct 結(jié)構(gòu)體名 變量名表列； 例 #define STUDENT struct student STUDENT int num; char name20; char sex; int age; float score; char addr30; ; STUDENT stu1,stu2; 43 定義結(jié)構(gòu)體類型的同時(shí)定義結(jié)構(gòu)體變量 一般形式： struct 結(jié)構(gòu)體名 類

34、型標(biāo)識(shí)符 成員名； 類型標(biāo)識(shí)符 成員名； . 變量名表列； 例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; 44 說(shuō)明 結(jié)構(gòu)體類型與結(jié)構(gòu)體變量概念不同 類型:不分配內(nèi)存； 變量:分配內(nèi)存 類型:不能賦值、存取、運(yùn)算; 變量:可以 結(jié)構(gòu)體可嵌套 結(jié)構(gòu)體成員名與程序中變量名可相同，不會(huì)混淆 結(jié)構(gòu)體類型及變量的作用域與生存期 例 struct date int month; int day; int year; ; struct student int num

35、; char name20; struct date birthday; stu; numname birthday monthdayyear 例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu; numname birthday monthdayyear 45 結(jié)構(gòu)體變量的引用結(jié)構(gòu)體變量的引用 引用規(guī)則 結(jié)構(gòu)體變量不能整體引用,只能引用變量成員 可以將一個(gè)結(jié)構(gòu)體變量賦值給另一個(gè)結(jié)構(gòu)體變量 結(jié)構(gòu)體嵌套時(shí)逐級(jí)引用 成員(分量)運(yùn)算符 優(yōu)先級(jí): 1 結(jié)合性:從左

36、向右 引用方式： 結(jié)構(gòu)體變量名.成員名 例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; stu1.num=10; stu1.score=85.5; stu1.score+=stu2.score; stu1.age+; 例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; printf(“%d,%s,%c,%d,%f,%s

37、n”,stu1); () stu1=101,“Wan Lin”,M,19,87.5,“DaLian”; () 例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; stu2=stu1; ( ) 例 struct student int num; char name20; struct date int month; int day; int year; birthday; stu1,stu2; numname birthday monthdayyear stu

38、1.birthday.month=12; 例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; if(stu1=stu2) . () 46 結(jié)構(gòu)體數(shù)組結(jié)構(gòu)體數(shù)組 結(jié)構(gòu)體數(shù)組的定義 三種形式： 形式一: struct student int num; char name20; char sex; int age; ; struct student stu2; 形式二: struct student int num; char name20; char sex;

39、int age; stu2; 形式三: struct int num; char name20; char sex; int age; stu2; num name sex age num name sex age stu0 stu1 25B 47 順序表的C語(yǔ)言描述 (p22) #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; SqList; SqList L; 說(shuō)明：elem數(shù)組指針指向線性表的基地址；length 指示線性表的當(dāng)前長(zhǎng)度；listsize指示順序表當(dāng)前分 配的存儲(chǔ)空間大小。當(dāng)空間不足時(shí)，再分配的存儲(chǔ) 空間增量為 LISTINCREMENT*sizeof(ElemType) 48 malloc函數(shù)函數(shù) 格式：格式：void * malloc ( unsigned int size); 功能：功能：在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)分配一個(gè)長(zhǎng)度為size的 連續(xù)空間，返回一個(gè)指向該區(qū)域起始地址的指針（ void類型） free函數(shù)函數(shù) 格式：格式：void free(void *p) 功能：功能：釋放由p指向的內(nèi)存區(qū) realloc的格式及功能的格式及功