1、1/53,第一章回顧,1、程序設計和算法、數據結構的關系 2、數據結構討論的內容 3、數據結構的定義 4、抽象數據類型的概念 5、算法及其度量,2/53,練習,設 n 為正整數。試確定下列各程序段中前置以記號 的語句的頻度 i=1; k=0;while ( i=n-1) k += 10 * i; i+;,n-1,3/53,i=1; k=0;do k +=10 * i; i+; while(i=n-1);,n-1,但n=1時特殊,是1次,4/53,x=n; y=0; / n 是不小于1的常數while (x=(y+1)*(y+1) y+;,5/53,x=91; y=100;while (y0 )

2、 if (x100 ) x -= 10; y- -; else x+;,1100,6/53,數據結構部分的起點：,什么是 線性結構？,7/53,第1章 緒論 第2章 線性表 第3章 棧和隊列 第4章 串 第5章 數組和廣義表 第6章 樹和二叉樹 第7章 圖 第9章 查找 第10、11章 排序 數據庫部分,目 錄,8/53,線性結構的定義：,若結構是非空有限集，則有且僅有一個開始結點和一個終端結點，并且所有結點都最多只有一個直接前趨和一個直接后繼。 可表示為：（a1 , a2 , , an）,簡言之，線性結構反映結點間的邏輯關系是 的。,特點 只有一個首結點和尾結點； 特點 除首尾結點外，其他結

3、點只有一個直接前驅和一個直接后繼。,線性結構包括：線性表、堆棧、隊列、字符串、數組等，其中最典型、最常用的是-,線性表,一對一 (1:1),9/53,第2章 線性表,2.1 線性表的類型定義 2.2 線性表的順序表示和實現 2.3 線性表的鏈式表示和實現 2.4 應用舉例,10/53,（a1, a2, ai-1，ai, ai1 ，, an）,2.1 線性表的定義：用數據元素的有限序列表示,n=0時稱為,數據元素,線性起點,ai的直接前趨,ai的直接后繼,下標，是元素的序號，表示元素在表中的位置,n為元素總個數，即表長。n0,空表,線性終點,11/53,（ A, B, C, D, , Z）,例2

4、 分析學生情況登記表是什么結構。,分析：數據元素都是同類型（記錄），元素間關系是線性的。,分析： 數據元素都是同類型（字母）， 元素間關系是線性的。,注意：同一線性表中的元素必定具有相同特性 ！,例1 分析26 個英文字母組成的英文表是什么結構。,12/53,“同一數據邏輯結構中的所有數據元素都具有相同的特性”是指數據元素所包含的數據項的個數都相等。,是指各元素具有相同的數據類型,試判斷下列敘述的正誤：,13/53,線性表的抽象數據類型的定義,ADT List 數據對象：Dai | ai ElemSet, i=1,2,.,n, n0 數據關系：R1 | ai-1,aiD, i=2,.,n 基本

5、操作： 結構初始化 銷毀結構 引用型操作 加工型操作 ADT List,14/53,線性表的抽象數據類型的定義,ADT List 數據對象：Dai | ai ElemSet, i=1,2,.,n, n0 數據關系：R1 | ai-1,aiD, i=2,.,n 基本操作：結構初始化InitList( 2依值在線性表 LA 中進行查詢； LocateElem(LA,e,equal( ) 3若不存在，則將它插入到 LA 中。 ListInsert( LA, n+1,e ) 重復上述三步直至 LB 遍歷止。,20/53,對應的線性表基本操作： 1. GetElem(Lb,i,e); 2. Locate

6、Elem( LA, e, equal() ); 3. ListInsert( LA, n+1,e ) void union(List / 銷毀線性表 LB / union,21/53,例2有順序表A和B，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表C，要求C的元素也按從小到大的升序排列。,基本思路： 依次掃描A和B的元素，比較當前元素ai和bj： if(aibj) ai賦給Ck; i+;k+； else bj賦給Ck; j+;k+； 將未完的那個順序表中余下部分賦給C;,22/53,void MergeList(SqList La,SqList Lb,SqList *Lc)

7、 /* 算法2.2 */ /* 已知線性表La和Lb中的數據元素按值非遞減排列。 */ /* 歸并La和Lb得到新的線性表Lc，Lc的數據元素也按值非遞減排列 */ int i=1,j=1,k=0; InitList(Lc); /* 創(chuàng)建空表Lc */ La_len=ListLength(La); Lb_len=ListLength(Lb); /依次掃描A和B的元素，比較當前元素ai和bj： while(i=La_len ,23/53,教材例2-1：求兩個線性表的“并”，即： LA U LB = ?,算法至少有兩種： LA和LB都是無序表，則從LB中取元素逐一與LA中所有元素比較，相同則不插入

8、LA中；O(ListLength(LA)* ListLength(LB) 若LA和LB已經是有序表，則“歸并”的時間效率可以大大提高。 O(ListLength(LA)+ ListLength(LB)。,24/53,2.2.1 順序表的表示,用一組地址連續(xù)的存儲單元依次存儲線性表的元素。,把邏輯上相鄰的數據元素存儲在物理上相鄰的存儲單元中的存儲結構。,線性表的順序表示又稱為順序存儲結構或順序映像。,順序存儲定義：,順序存儲方法：,特點：,邏輯上相鄰的元素，物理上也相鄰,可以利用數組Vn來實現,注意：在C語言中數組的下標是從0開始，即： Vn的有效范圍是從 V0Vn-1,25/53,1. 邏輯上

9、相鄰的數據元素，其物理上也相鄰； 2. 若已知表中首元素在存儲器中的位置，則其他元素存放位置亦可求出（利用數組Vn的下標）。,設首元素a1的存放地址為LOC(a1)（稱為首地址）， 設每個元素占用存儲空間（地址長度）為L字節(jié)， 則表中任一數據元素的存放地址為： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1）,對上述公式的解釋如圖所示,線性表順序存儲特點：,26/53,地址 內容 元素在表中的位序,1,i,2,n,空閑區(qū),i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(ma

10、x-1)L,LOC ( ai ) = LOC( a1 ) + L *（i -1）,線性表的順序存儲結構示意圖,下標起點是1,27/53,設有一維數組，下標的范圍是到，每個數組元素用相鄰的個字節(jié)存儲。存儲器按字節(jié)編址，設存儲數組元素的第一個字節(jié)的地址是98，則的第一個字節(jié)的地址是多少？,答案：113,但此題要注意下標起點是從0開始： LOC( M3 ) = 98 + 5 (4-1) =113,解：已知地址計算通式為：,LOC(ai) = LOC(a1) + L *（i-1）,例1,或用（3-0）,28/53,char V30; void build() /字母線性表的生成，即建表操作 int i

11、; V0=a; for( i=1; i=n-1; i+ ) Vi=Vi-1+1; ,核心語句： 法1 Vi= Vi-1+1; 法2 Vi=a+i; 法3 Vi=97+i;,例2,用數組V來存放26個英文字母組成的線性表（a，b，c，z），寫出在順序結構上生成和顯示該表的C語言程序。,省略了include語句,29/53,void main(void) /主函數，字母線性表的生成和輸出 n=26; / n是表長，是數據元素的個數，而不是V的實際下標 build( ); display( ); ,void display( ) /字母線性表的顯示，即讀表操作 int i; for( i=0; i=

12、n-1; i+ ) printf( %c, vi ); printf( n ); ,執(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,30/53,2.2.2 順序表的實現（或操作）,數據結構的基本運算： 修改、插入、刪除、查找、排序,1) 修改 通過數組的下標便可訪問某個特定元素并修改之。,核心語句: Vi=x;,顯然，順序表修改操作的時間效率是 O(1),31/53,在線性表的第i個位置前插入一個元素,實現步驟： 將第n至第i 位的元素向后移動一個位置； 將要插入的元素寫到第i個位置； 表長加1。,for (j=n; j=i;

13、 j-) aj+1=a j ; a i =x; n+;,/ 元素后移一個位置,/ 插入x,/ 表長加1,核心語句：,2)插入,注意：事先應判斷: 插入位置i 是否合法?表是否已滿? 應當符合條件： 1in+1 或 i=1, n+1,32/53,在線性表的第i個位置前插入一個元素的示意圖如下：,插入25,33/53,實現步驟： 將第i+1 至第n 位的元素向前移動一個位置； 表長減1。,刪除線性表的第i個位置上的元素,for ( j=i+1; j=n; j+ ) aj-1=aj; n-;,/ 元素前移一個位置,/ 表長減1,核心語句：,3)刪除,注意：事先需要判斷，刪除位置i 是否合法? 應當符

14、合條件：1in 或 i=1, n,34/53,刪除順序表中某個指定的元素的示意圖如下：,35/53,順序表的運算效率分析,算法時間主要耗費在移動元素的操作上，因此 計算時間復雜度的基本操作（最深層語句頻度） T(n)= O (移動元素次數) 而移動元素的個數取決于插入或刪除元素的位置。,思考：若插入在尾結點之后，則根本無需移動（特別快）； 若插入在首結點之前，則表中元素全部要后移（特別慢）； 應當考慮在各種位置插入（共n+1種可能）的平均移動次數才合理。,討論1：若在長度為 n 的線性表的第 i 位前 插入一個元素，則向后移動元素的次數f(n)為: f(n) =,n i + 1,時間效率分析:

15、,36/53,推導：假定在每個元素位置上插入x的可能性都一樣（即概率P相同），則應當這樣來計算平均執(zhí)行時間： 將所有位置的執(zhí)行時間相加，然后取平均。 若在首結點前插入，需要移動的元素最多，后移次數為n； 若在a1后面插入，要后移n-1個元素，后移次數為n-1; 若在an-1后面插入，后移次數為1； 若在尾結點an之后插入，則后移次數為0；,故插入時的平均移動次數為：n(n+1)/2（n+1）n/2O(n),共有多少種插入形式?連頭帶尾有n+1種!,所有可能的元素移動次數合計： 0+1+n = n(n+1)/2,37/53,同理可證：順序表刪除一元素的時間效率為: T（n)=(n-1)/2 O(

16、n),想一想： 順序表插入、刪除算法的平均空間復雜度為多少？,插入效率：,刪除效率：,教材P25算法2.5也是對執(zhí)行效率的推導：,因為沒有占用輔助空間！,含義：對于順序表，插入、刪除操作平均需要移動一半元素( n / 2 ),O(1),即插入、刪除算法的平均時間復雜度為 O(n),38/53,#define LIST_MAX_LENGTH 100 /線性表的最大長度 typedef int ElemType; typedef struct ElemType *elem; /指向存放線性表中數據元素的基地址 int length; /線性表的當前長度 SQ_LIST；,39/53,典型操作的算法

17、實現,1. 初始化線性表L int InitList(SQ_LIST /成功返回OK / sizeof(x)算符的意思是：計算變量x的長度(字節(jié)數) malloc(m)函數的意思是：新開一片大小為m字節(jié)的連續(xù)空間，并把該區(qū)首址作為函數值。,40/53,2. 銷毀線性表L void DestroyList(SQ_LIST /釋放線性表占據的所有存儲空間 ,41/53,3. 清空線性表L void ClearList(SQ_LIST /將線性表的長度置為0 ,42/53,4. 求線性表L的長度 int GetLength(SQ_LIST L) return (L.length); ,43/53,5

18、. 判斷線性表L是否為空 int IsEmpty(SQ_LIST L) if (L.length=0) return TRUE; else return FALSE; ,44/53,6. 獲取線性表L中的某個數據元素的內容 int GetElem(SQ_LIST L,int i, ElemType ,45/53,7. 在線性表L中檢索值為e的數據元素 int LocateELem(SQ_LIST L, int(*compare)(ElemType,ElemType) /* 操作結果：返回L中第1個與e滿足關系compare()的數據元素的位序。若這樣的數據元素不存在，則返回值為0。 */ El

19、emType *p; int i=1; /* i的初值為第1個元素的位序 */ p=L.elem; /* p的初值為第1個元素的存儲位置 */ while(i=L.length ,int equal (ElemType a,ElemType b) /* 根據a 或= b，分別返回0或1 */ if(a=b) return 1; else return 0; ,LocateElem(L,j,equal);,46/53,8. 將線性表L中第i個數據元素刪除 int ListDelete(SQ_LIST ,47/53,9. 在線性表L中第i個數據元素之前插入數據元素e int ListInsert(

20、SQ_LIST ,48/53,進一步討論：,順序表的存儲結構是一維數組，如果插入的元素個數超過數組定義的長度怎么辦？ 采用動態(tài)分配的一維數組,49/53,動態(tài)數組簡介,先為順序表空間設定一個初始分配量，一旦因插入元素而空間不足時，可為順序表增加一個約定長度的空間增量。,#define LIST_INIT_SIZE 100 /存儲空間的初始分配量 #define LISTINCREMENT 10/存儲空間的分配增量 Typedef struct ElemType *elem; /表基址(用指針*elem表示） int length; /表長度（表中有多少個元素） int listsize; /當

21、前分配的表尺寸（字節(jié)單位） SqList;,注：三個分量可簡寫為：L.elem L.length L.listsize,存儲結構描述如下（見教材P22）：,50/53,Status InitList_Sq( SqList /InitList_Sq,動態(tài)創(chuàng)建一個空順序表的算法：,51/53,動態(tài)順序表的插入算法 Status ListInsert_Sq(SqList / 檢驗i 值的合法性,if ( L.length L.listsize ) /若表長超過表尺寸則要增加尺寸 newbase = ( ElemType* ) realloc ( L.elem , (L.listsize + LISTINCREMENT )* sizeof ( Ele