數據結構：第2章線性表A

1、1課堂練習：課堂練習：1. 1. 分析以下程序段的時間復雜度。分析以下程序段的時間復雜度。i=1; while(i=n) i=i*3; 2將下列函數，按它們在將下列函數，按它們在n時的無窮大階數，從小到大排序。時的無窮大階數，從小到大排序。n, n-n3+0.7n5, nlogn, 2n/2, n3, 100logn, n1/2+logn, n!答：答：100logn, n1/2+logn, n, nlogn, n3, n-n3+0.7n5, 2n/2, n!答：答：O(log3n)2 習題集習題集1.6 1.7 1.8 1.10 1.17 1.20習題集習題集 2.8 2.10 2.21 2

2、.22 2.34 2.35助教助教蔡科超蔡科超4302066563第第1章回顧章回顧數據結構課程數據結構課程 數據結構算法程序，涉及數學、數據結構算法程序，涉及數學、計算機硬件和軟件。計算機硬件和軟件。數據結構定義數據結構定義指互相有關聯的數據元素的集合，指互相有關聯的數據元素的集合，可用可用data_Structure=(D,R)data_Structure=(D,R)表示。表示。數據結構內容數據結構內容數據的邏輯結構、存儲結構和基本數據的邏輯結構、存儲結構和基本運算運算(計算機處理非數值對象計算機處理非數值對象) 數據結構學習工具數據結構學習工具抽象數據類型和偽碼

3、抽象數據類型和偽碼（類（類C）算法效率指標算法效率指標時間效率和空間效率時間效率和空間效率 4第第1章章 緒論緒論第第2章章 線性表線性表第第3章章 棧和隊列棧和隊列 第第4章章 串串第第5章章 數組和廣義表數組和廣義表第第6 6章章 樹和二叉樹樹和二叉樹 第第7章章 圖圖第第9章章 查找查找第第10章章 排序排序目目 錄錄什么是什么是線性結構？線性結構？6線性結構的定義：線性結構的定義：若結構是非空有限集，則有且僅有一個開始結點和一個若結構是非空有限集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼。

4、接后繼。 可表示為：（可表示為：（a a1 1 , a, a2 2 , , , a, an n） 簡言之，線性結構反映結點間的邏輯關系是簡言之，線性結構反映結點間的邏輯關系是 的。的。特點特點 只有一個首結點和尾結點；只有一個首結點和尾結點；特點特點 除首尾結點外，其他結點只有一個直接前驅和一個除首尾結點外，其他結點只有一個直接前驅和一個直接后繼。直接后繼。線性結構包括：線性結構包括：線性表、堆棧、隊列、字符串、數組線性表、堆棧、隊列、字符串、數組等，其中最典型、最常用的是等，其中最典型、最常用的是-一對一一對一 (1:1)78（a1, a2, ai-1，ai, ai1 ，, an）2.1 線

5、性表的邏輯結構線性表的邏輯結構 用數據元素的有限序列表示用數據元素的有限序列表示n=0時稱為時稱為數據元素數據元素線性起點線性起點ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標，下標，是元素的是元素的序號，表示元素序號，表示元素在表中的位置在表中的位置n為元素總為元素總個數，即表個數，即表長。長?？毡砜毡砭€性終點線性終點9 （ A, B, C, D, , Z）學號學號姓名姓名性別性別年齡年齡班級班級U200913798章達航章達航男男19通信工程通信工程200901班班U200913818張巖張巖男男19通信工程通信工程200902班班U200913955周凱周凱男男19通信工程通信工程

6、200903班班U200913887吳益陽吳益陽男男1919通信工程通信工程200904班班： ： ：例例2 分析學生情況登記表是什么結構。分析學生情況登記表是什么結構。分析：分析：數據元素都是同類型（數據元素都是同類型（記錄記錄），元素間關系是線性的。），元素間關系是線性的。分析：分析： 數據元素都是同類型（數據元素都是同類型（字母字母），）， 元素間關系是線性的。元素間關系是線性的。例例1 分析分析26 個英文字母組成的英文表是什么結構。個英文字母組成的英文表是什么結構。10“同一數據邏輯結構中的所有數據元素都具有相同的特性同一數據邏輯結構中的所有數據元素都具有相同的特性”是指數據元素所包

7、含的數據項的個數都相等。是指數據元素所包含的數據項的個數都相等。試判斷下列敘述的正誤：試判斷下列敘述的正誤：112.2 線性表的順序表示和實現線性表的順序表示和實現2.2.1 順序表的表示順序表的表示2.2.2 順序表的實現順序表的實現2.2.3 順序表的運算效率分析順序表的運算效率分析122.2.1 順序表的表示順序表的表示用一組用一組地址連續(xù)地址連續(xù)的存儲單元依次的存儲單元依次存儲線性表的元素存儲線性表的元素。把邏輯上相鄰的數據元素存儲在物把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元中的存儲結構。理上相鄰的存儲單元中的存儲結構。線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結構順

8、序存儲結構或順序映像?；蝽樞蛴诚瘛ｍ樞虼鎯Χx：順序存儲定義：順序存儲方法：順序存儲方法：特點：特點：邏輯上相鄰的元素，物理上也相鄰邏輯上相鄰的元素，物理上也相鄰可以利用可以利用數組數組VnVn來實現來實現注意：在注意：在C C語言中數組的下標是從語言中數組的下標是從0 0開始，即：開始，即： VVn n 的有效范圍是從的有效范圍是從 VV0 0 VVn-1n-1 131. 邏輯上相鄰的數據元素，其物理上也相鄰；邏輯上相鄰的數據元素，其物理上也相鄰；2. 若已知表中首元素在存儲器中的位置，則其他元若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出素存放位置亦可求出（利用數組利用數組V

9、nVn的的下標下標）。設首元素設首元素a1的存放地址為的存放地址為LOC(a1)（稱為稱為首地址首地址），），設每個元素占用存儲空間（地址長度）為設每個元素占用存儲空間（地址長度）為L字節(jié)，字節(jié)，則表中任一數據元素的則表中任一數據元素的存放地址存放地址為為？ 先畫圖先畫圖線性表順序存儲特點：線性表順序存儲特點：14a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內容內容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(m

10、ax-1)+(max-1)L L線性表的順序存儲結構示意圖線性表的順序存儲結構示意圖 LOC ( a ) = LOC( a ) + L 表中任一數據表中任一數據元素的元素的存放地存放地址址為為:下標起下標起點是點是1 115設有一維數組設有一維數組，下標的范圍是，下標的范圍是到到，每個數，每個數組元素用相鄰的組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲器按字節(jié)編址，存儲。存儲器按字節(jié)編址，設存儲數組元素設存儲數組元素 的第一個字節(jié)的地址是的第一個字節(jié)的地址是9898，則，則 的第一個字節(jié)的地址是多少？的第一個字節(jié)的地址是多少？答案：答案：113但此題要注意下標起點是從但此題要注意下標起點是從0 0開始

11、：開始： LOC( M3 ) = 98 + 5 (3-0) =113或或: : LOC( M3 ) = 98 + 5 (4-1) =113解：解：已知地址計算通式為：已知地址計算通式為：LOC(ai) = LOC(a1) + L *（i-1）例例1 116 char V30;void build() /字母線性表的字母線性表的生成生成，即建表操作，即建表操作 例例2用數組用數組V來存放來存放26個英文字母組成的線性表（個英文字母組成的線性表（a，b，c，z），寫出在順序結構上），寫出在順序結構上生成生成和和顯示顯示該表的該表的C語言語言程序。程序。省略了省略了includeinclude語句語

12、句 int i; V0=a; for( i=1; i=n-1; i+ ) Vi=Vi-1+1; 17void main(void) /主函數，字母線性表的主函數，字母線性表的生成和輸出生成和輸出 n=26; / n n是表長，是數據元素的個數，而不是是表長，是數據元素的個數，而不是V V的實際下標的實際下標 build( ); display( );void display( ) /字母線性表的字母線性表的顯示顯示，即讀表操作，即讀表操作 執(zhí)行結果：執(zhí)行結果： a b c d e f g h i j k l m n o p q r s t u v w x y z int i; for( i=0

13、; i=i; j )aj+1=a j ; a i =x; n+;/ / 元素后移一個位置元素后移一個位置/ / 插入插入x x / / 表長加表長加1 1 事先應判斷事先應判斷: 插入位置插入位置i 是否合法是否合法? 表是否已滿表是否已滿? 應當符合條件：應當符合條件： 1in+1 或或 i=1, n+1 將第將第n至第至第i 位的元素向后移動一個位置；位的元素向后移動一個位置； 將要插入的元素寫到第將要插入的元素寫到第i個位置；個位置； 表長加表長加1。核核心心語語句句if ( iL.length+1) return ERROR2112345678912132124252830427712

14、3456781213212428304277刪除順序表中某個指定的元素的示意圖如下：刪除順序表中某個指定的元素的示意圖如下：刪除線性表的第刪除線性表的第i i個位置上的元素個位置上的元素3)3)刪除刪除22實現步驟：實現步驟： 將第將第i+1 至第至第n 位的元素向前移動一個位置；位的元素向前移動一個位置； 表長減表長減1。for ( j=i+1; j=n; j+ )aj-1=aj; n-;/ / 元素前移一個位置元素前移一個位置/ / 表長減表長減1 1 核心語句：核心語句：順序表插入和刪除的完整程序請同學們自編，順序表插入和刪除的完整程序請同學們自編，并務必上機驗證！并務必上機驗證！if

15、( iL.length) return ERROR 注意：事先需要判斷，注意：事先需要判斷，刪除位置刪除位置i 是否合法是否合法?應當符合條件：應當符合條件：1in 或或 i=1, n232.2.3 順序表的運算效率分析順序表的運算效率分析 算法時間主要耗費在算法時間主要耗費在移動元素移動元素的操作上，因此的操作上，因此計算時間復雜度的基本操作（最深層語句頻度）計算時間復雜度的基本操作（最深層語句頻度） T(n)= O (移動元素次數移動元素次數)而移動元素的個數取決于插入或刪除元素的位置。而移動元素的個數取決于插入或刪除元素的位置。思考：思考：若插入在尾結點之后，則根本無需移動（特別快）；若

16、插入在尾結點之后，則根本無需移動（特別快）；若插入在首結點之前，則表中元素全部要后移（特別慢）；若插入在首結點之前，則表中元素全部要后移（特別慢）；應當考慮在各種位置插入（共應當考慮在各種位置插入（共n+1種可能）的種可能）的平均平均移動次數才合理。移動次數才合理。討論討論1：若在長度為若在長度為 n 的線性表的第的線性表的第 i 位前位前 插入插入一個元素，一個元素，則向后移動元素的次數則向后移動元素的次數f(n)為為:f(n) = n i + 1時間效率分析時間效率分析:24推導：推導：假定在每個元素位置上插入假定在每個元素位置上插入x x的可能性都一樣（即的可能性都一樣（即概率概率P P

17、相同），則應當這樣來計算平均執(zhí)行時間：相同），則應當這樣來計算平均執(zhí)行時間：若在首結點前插入，需要移動的元素最多，后移次數為若在首結點前插入，需要移動的元素最多，后移次數為n n；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1個元素，后移次數為個元素，后移次數為n-1n-1; ;若在若在a an-1n-1后面插入，后移次數為后面插入，后移次數為1 1；若在尾結點若在尾結點a an n之后插入，則后移次數為之后插入，則后移次數為0 0；故插入時的故插入時的平均平均移動次數為：移動次數為：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2 共有多少種插入形式共有多少種插

18、入形式? ?連頭帶尾有連頭帶尾有n+1n+1種種! !所有所有可能的元素移動次數合計可能的元素移動次數合計： 0+1+0+1+n+n = n(n+1)/2 = n(n+1)/225同理可證：同理可證：順序表刪除一元素的時間效率為順序表刪除一元素的時間效率為: :T T（n)=(n-1)/2 n)=(n-1)/2 順序表插入、刪除算法的順序表插入、刪除算法的平均平均空間空間復雜度復雜度為多少？為多少？插入效率：插入效率：刪除效率：刪除效率：11111(1)(1)12nnisiiinEp ninin 1111()()2nndliiinEq ninin教材教材P25算法算法2.5也是對執(zhí)行效率的推導：也是對執(zhí)行效率的推導：因為沒有占用輔助空間！因為沒有占用輔助空間！含義：對于順序表，插入、刪除操含義：對于順序表，插入、刪除操作平均需要移動一半元素作平均需要移動一半元素( n / 2 )O(1)O(1)即插入、刪除算法的平均即插入、刪除算法的平均時間復雜度為時間復雜度為 O(n)26例例1(1(華為招聘試題華為招聘試題) )：試用試用C C或類或類C C語言編寫一語言編寫一高效高效算法，將一順序存儲的線性表（設元素均為整型算法，將一順序存儲的線性表（設元素均為整型量）中所