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

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

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

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

4、法，對應(yīng)二種不同的存儲結(jié)構(gòu) 順序映象順序映象 順序存儲結(jié)構(gòu) 非順序映象非順序映象 鏈?zhǔn)酱鎯Y(jié)構(gòu) 復(fù)數(shù)復(fù)數(shù)的兩種存儲方式：的兩種存儲方式： 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ù)對象數(shù)據(jù)對象 D D上的關(guān)系集上的關(guān)系集 D D上的操作集上的操作集 ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名 數(shù)據(jù)數(shù)據(jù)對象對象： 數(shù)據(jù)數(shù)據(jù)關(guān)系關(guān)系： 基本操作基本操作 ： ADTADT抽象數(shù)據(jù)類型名抽象數(shù)據(jù)類型名

5、第二章：線性表9 Recap:抽象數(shù)據(jù)類型定義 定義并實現(xiàn)定義并實現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型復(fù)數(shù)抽象數(shù)據(jù)類型（定義定義） ADT ComplexADT Complex 數(shù)據(jù)對象：數(shù)據(jù)對象：D = c1, c2 | c1, c2 D = c1, c2 | c1, c2 R(R R(R為實數(shù)集）為實數(shù)集） 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：S = S = （ c1 c1為實部，為實部，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 定義并實現(xiàn)定義并實現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型復(fù)數(shù)抽象數(shù)據(jù)類型（實現(xiàn)實現(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 正確性正確性 時間代價時間代價(時間復(fù)雜度時間復(fù)雜度) 空間代價空間代價 (空間復(fù)雜度

9、空間復(fù)雜度) 最優(yōu)性最優(yōu)性 Recap: 算法效率度量 第二章：線性表12 O： 當(dāng)且僅當(dāng)存在一個正的常數(shù)當(dāng)且僅當(dāng)存在一個正的常數(shù) C，使得對所有使得對所有 的的 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 */ 面試: 順序存儲還是鏈?zhǔn)酱鎯Γ?第二章：線性表13 學(xué)號學(xué)號姓名姓名性別性別出生日期出生日期二外二外 10001王

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

11、只有一個直接前趨和一個直終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個直 接后繼。接后繼。 可表示為：（可表示為：（a a1 1 , a , a2 2 , , , a, an n） 簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 的。的。 特點特點 只有一個首結(jié)點和尾結(jié)點；只有一個首結(jié)點和尾結(jié)點； 特點特點 除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個除首尾結(jié)點外，其他結(jié)點只有一個直接前驅(qū)和一個 直接后繼。直接后繼。 線性結(jié)構(gòu)包括：線性結(jié)構(gòu)包括：線性表、堆棧、隊列、字符串、數(shù)組線性表、堆棧、隊列、字符串、數(shù)組 等，其中最典型、最常用的是等，其中最典型、最常用的

12、是- 一對一一對一 (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ù)據(jù)元素數(shù)據(jù)元素 線性起點線性起點ai的直接前趨的直接前趨ai的直接后繼的直接后繼 下標(biāo)，下標(biāo)，是元素的是元素的 序號，表示元素序號，表示元素 在表中的位置在表中的位置 n為元素總為元素總 個數(shù)，即表個數(shù)，即表 長。長。 空表空表 線性終點線性終點 2.1 線性表的邏輯結(jié)構(gòu) 19 （ A, B, C, D, , Z） 學(xué)號學(xué)號姓名姓名性別性別年齡

13、年齡班級班級 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 個英文字母組成的英文表是什么結(jié)構(gòu)。個英文

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ù)項的個數(shù)都相等。是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)都相等。 試判斷下列敘述的正誤：試判斷下列敘述的正誤： 2.1 線性表的邏輯結(jié)構(gòu) 21 2.2.1 順序表的表示順序表的表示 用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次的存儲單元依次 存儲線性表的元素。存儲線性表的元素。 把邏輯上相鄰的數(shù)據(jù)元素存儲在物把邏輯上相鄰的數(shù)據(jù)元素存儲在物 理上相鄰的存儲單元中的存儲結(jié)構(gòu)。理上相鄰的存儲單元中的存儲結(jié)構(gòu)。 線性表的順序表

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

16、素在存儲器中的位置，則其他元 素存放位置亦可求出素存放位置亦可求出（利用數(shù)組利用數(shù)組VnVn的的下標(biāo)下標(biāo)）。）。 設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為LOC(a1)（稱為稱為首地址首地址），）， 設(shè)每個元素占用存儲空間（地址長度）為設(shè)每個元素占用存儲空間（地址長度）為L字節(jié)，字節(jié)， 則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC ( ai+1 ) = LOC( ai ) + L 對上述公式的解釋如圖所示對上述公式的解釋如圖所示 線性表順序存儲特點：線性表順序存儲特點： 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 線性表的順序存儲結(jié)構(gòu)示意圖線性表的順序存儲結(jié)構(gòu)示意圖 下標(biāo)起下標(biāo)起 點是點是1 1 2.2.1 順序表的表示 24 設(shè)有一維數(shù)組設(shè)有一維數(shù)組，下標(biāo)的范圍是，下標(biāo)的范圍是到到，每個數(shù)，每個數(shù) 組元素用相鄰的組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器按字節(jié)編址，存儲。存儲器按字節(jié)編址， 設(shè)存儲數(shù)組元素設(shè)存儲數(shù)組元素

18、 的第一個字節(jié)的地址是的第一個字節(jié)的地址是9898，則，則 的第一個字節(jié)的地址是多少？的第一個字節(jié)的地址是多少？ 答案：答案：113 但此題要注意下標(biāo)起點是從但此題要注意下標(biāo)起點是從0 0開始：開始： LOC( M3 ) = 98 + 5 (4-1) =113 解：解：已知地址計算通式為：已知地址計算通式為： 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; 核心語句：核心語句： 例例2用數(shù)組用數(shù)組V來存放來存放26個英文字母組成的線性表（個英文字母組成的線性表（a，b， c，z），寫出在順序結(jié)構(gòu)上），寫出在順序結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C語言語言 程序。程序。 省略了省略了includeinclude語句語句 2.2.1 順序表的表示 26 void main(void) /主函數(shù)，字母線性表的主函數(shù)，字母線性表的生成和輸出生成和輸出 n=26; / n n是表長，是數(shù)據(jù)元素的個數(shù)，而不是是表長，是數(shù)據(jù)元素的個數(shù)，而不是V V的實際下標(biāo)的實際下標(biāo) build( ); display( ); void

20、display( ) /字母線性表的字母線性表的顯示顯示，即讀表操作，即讀表操作 int i; for( i=0; i=i; j ) aj+1=a j ; a i =x; n+; / / 元素后移一個位置元素后移一個位置 / / 插入插入x x / / 表長加表長加1 1 核核 心心 語語 句：句： 2)2)插入插入 2.2.2 順序表的操作 29 在線性表的第在線性表的第i i個位置前插入一個元素的示意圖如下：個位置前插入一個元素的示意圖如下： 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 實現(xiàn)步驟：實現(xiàn)步驟： 將第將第i+1 至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置； 表長減表長減1。 注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法? 應(yīng)當(dāng)符合條件：應(yīng)當(dāng)符合條件：1in 或或 i=1, n 刪除線性表的第刪除線性表的第i i個位置上的元素個位置上的元素 for ( j=i+1; j=n; j+ ) aj-1=aj; n-; / / 元素前移一個位置元素前移一個位置 / / 表長減表長減1 1 核心語句：核心語句： 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 刪除順序表中某個指定的元素的示意圖如下：刪除順序表中某個指定的元素的示意圖如下： 順序表插入和刪除的完整程序請同學(xué)們自編，順序表插入和刪除的完整程序請同學(xué)們自編， 并務(wù)必上機驗證！并務(wù)必上機驗證！ 2.2.2 順序表的操作 32 2.2.3 順序表的運算效率分析順序表的運算效率分析 算法時間主要耗費在算法時間主要耗費在移動元素移動元素的操作上，因此的操作上，因此 計算時間復(fù)雜度的基本操作（最深層語句頻度）計算時間復(fù)雜度的基本操

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

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

25、后面插入，后移次數(shù)為后面插入，后移次數(shù)為1 1； 若在尾結(jié)點若在尾結(jié)點a an n之后插入，則后移次數(shù)為之后插入，則后移次數(shù)為0 0； 故插入時的故插入時的平均平均移動次數(shù)為：移動次數(shù)為：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少種插入形式共有多少種插入形式? ?連頭帶尾有連頭帶尾有n+1n+1種種! ! 所有所有可能的元素移動次數(shù)合計可能的元素移動次數(shù)合計： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/2 2.2.3 順序表的運算效率分析 34 同理可證：同理可證：順序表刪除一元素的時間效率為順序表刪除一元素的時間效率為: : 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也是對執(zhí)行效率的推導(dǎo)：也是對執(zhí)行效率的推導(dǎo)： 因為沒有占用輔助空間！因為沒有占用輔助空間！ 含義：對于順序表，插入、刪除操含義：對于順序表，插入、刪除操 作平均需要移動一半元素作平均需要移動一半元素( n / 2 ) O(1)O(1) 即插入、刪除算法

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

28、章：線性表 Recap 37 用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次的存儲單元依次 存儲線性表的元素。存儲線性表的元素。 把邏輯上相鄰的數(shù)據(jù)元素存儲在物把邏輯上相鄰的數(shù)據(jù)元素存儲在物 理上相鄰的存儲單元中的存儲結(jié)構(gòu)。理上相鄰的存儲單元中的存儲結(jié)構(gòu)。 線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)或順序映像?；蝽樞蛴诚?。 順序存儲定義：順序存儲定義： 順序存儲方法：順序存儲方法： 特點：特點：邏輯上相鄰的元素，物理上也相鄰邏輯上相鄰的元素，物理上也相鄰 可以利用可以利用數(shù)組數(shù)組VnVn來實現(xiàn)來實現(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 因為沒有占用輔助空間！因為沒有占用輔助空間！ 含義：對于順序表，插入、刪除操含義：對于順序表，插入、刪除操 作平均需要移動一半元素作平均需要移動一半元素( n / 2 ) O(1)O(1) 即插入、刪除算法的平均即插入、刪除算法的平均 時間復(fù)雜度為時間復(fù)雜度為 O(n) Recap: 39 線性表的基本操作如何表示？線性表的基本操作如何表示

30、？ （見教材（見教材P19） InitList( /建空表，初始化建空表，初始化 DestoryList( /撤銷表，釋放內(nèi)存撤銷表，釋放內(nèi)存 int LengthList( L ); /求表中元素個數(shù)，即表長求表中元素個數(shù)，即表長 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個元素之前個元素之前 ListDelet

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

32、或構(gòu)造型 struct是關(guān)鍵字, 不能省略 合法標(biāo)識符 可省:無名結(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)識符 成員名； 類型標(biāo)識符 成員名； . ； 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)體類型的同時定義結(jié)構(gòu)體變量 一般形式： struct 結(jié)構(gòu)體名 類

34、型標(biāo)識符 成員名； 類型標(biāo)識符 成員名； . 變量名表列； 例 struct student int num; char name20; char sex; int age; float score; char addr30; stu1,stu2; 44 說明 結(jié)構(gòu)體類型與結(jié)構(gòu)體變量概念不同 類型:不分配內(nèi)存； 變量:分配內(nèi)存 類型:不能賦值、存取、運算; 變量:可以 結(jié)構(gòu)體可嵌套 結(jié)構(gòu)體成員名與程序中變量名可相同，不會混淆 結(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)體變量不能整體引用,只能引用變量成員 可以將一個結(jié)構(gòu)體變量賦值給另一個結(jié)構(gòu)體變量 結(jié)構(gòu)體嵌套時逐級引用 成員(分量)運算符 優(yōu)先級: 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語言描述 (p22) #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct ElemType *elem; int length; int listsize; SqList; SqList L; 說明：elem數(shù)組指針指向線性表的基地址；length 指示線性表的當(dāng)前長度；listsize指示順序表當(dāng)前分 配的存儲空間大小。當(dāng)空間不足時，再分配的存儲 空間增量為 LISTINCREMENT*sizeof(ElemType) 48 malloc函數(shù)函數(shù) 格式：格式：void * malloc ( unsigned int size); 功能：功能：在內(nèi)存的動態(tài)存儲區(qū)分配一個長度為size的 連續(xù)空間，返回一個指向該區(qū)域起始地址的指針（ void類型） free函數(shù)函數(shù) 格式：格式：void free(void *p) 功能：功能：釋放由p指向的內(nèi)存區(qū) realloc的格式及功能的格式及功