【正文】 序存儲和實現(xiàn) ?刪 除 一 個 元 素圖示 2 63 ? ? ? ?nOnTninnEnQnidei????????? 1 21)(11則若認(rèn)為 故在順序表中插入或刪除一個元平均移動表的一半元素，當(dāng) n很大時，效率很低 167。 *p=n。 if((i1) || (in)) return (0)。 } 59 ? ?nii aaaaa ???? , 1,21 ?變成長度為 n1的線性表 ? ?nii aaaaa ???? , 11,21 ??需將第 i+1至第 n共（ ni）個元素前移 167。 item){ if( = = MaxSize){ printf( “ List overflow!” )。 ++ 。 for(int j = –1。 return。 } 57 167。 i = 0。 L,const ElemTypeamp。 線性表的順序存儲和實現(xiàn) ?插入一個元素圖示 1 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標(biāo) n1 i n 1 2 i 元素序號 i+1 n n+1 54 內(nèi)存 a1 a2 ai ai+1 an 0 1 i1 V數(shù)組下標(biāo) n1 i n 1 2 i 元素序號 i+1 n n+1 an1 167。 v[j]=x。 if((i1) || (in+1)) return (0)。 線性表的順序存儲和實現(xiàn) ?線性表的順序存儲示例 （圖書資料） 51 167。 }DATATYPE。 char name[20]。 線性表的順序存儲和實現(xiàn) ?ElemType類型的數(shù)組 list[MaxSize]存儲線性表 A= (a1 , a2 , … , ai , ai+1 , … , an) ?元素地址計算方法 第 i個元素的存儲位置為： list+(i1)*sizeof(ElemType) ?線性表的順序存儲結(jié)構(gòu)示意圖 47 167。j++。 線性表的類型定義 void celem(sqlist A， sqlist B， sqlist amp。 //依次獲取線性表 B中的元素 ， //存放在 x中 k=locate(A， x)。 ElemType x。 基本運算 [例 ] 利用線性表的基本運算，編寫在線性表 A中刪除線性表 B中出現(xiàn)的元素的算法。 線性表的類型定義 基本運算 ?應(yīng)用基本運算可以實現(xiàn)線性表的其他運算，如求任一給定數(shù)據(jù)元素的直接后繼或直接前趨，將兩個線性表合并成一個線性表或?qū)⒁粋€線性表拆分成兩個線性表等等。 線性表的類型定義 基本運算 (7)求前趨 PriorElem(sq,e) 若線性表中存在元素 e且不是第一個 ,其作用是返回 e的前趨元素 。 線性表的類型定義 基本運算 (6)刪除 ListDelete(sq， i)。 37 基本運算 (5)插入 ListInsert(sq， x， i)。否則 ， 返回 NULL。 ( 2 ) 求表長 ListLen(sq)。 線性表的類型定義 二、線性結(jié)構(gòu)特點 ?在數(shù)據(jù)元素的非空有限集中 ? 元素個數(shù) n—表長度， n=0空表 ? 存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素 ? 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素 ? 除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前趨 ? 除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼 ? 元素同構(gòu)，且不能出現(xiàn)缺項 34 學(xué)號 姓名 年齡 001 張三 18 002 李四 19 …… …… …… 數(shù)據(jù)元素 167。 } printf(“ %d,%d” ,s,k)。 } } 28 習(xí)題與練習(xí) 一 （ 3） k=1。 for(j=0。j++) count +=m+j。In。j++) n(n+1)/2 m +=2。 1 for( k=0。 A．線性結(jié)構(gòu) B． 非線性結(jié)構(gòu) A 順序存儲 B 鏈?zhǔn)酱鎯? 線性表 棧 隊 樹形結(jié)構(gòu) 圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的三個方面 12 基本概念和術(shù)語 19 13 算法和算法分析 一、算法定義 算法 是對特定問題求解步驟的一種描述，是指令的有限序列。 (3) 數(shù)據(jù)對象 ( data object)性質(zhì)相同的數(shù)據(jù)元素的集合 (4) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)元素之間的相互關(guān)系 11 1) 集合 12 基本概念和術(shù)語 數(shù)據(jù)間的四種典型結(jié)構(gòu)： 2）線形 3）樹形 4）圖或網(wǎng)絡(luò)： 12 12 基本概念和術(shù)語 四種典型結(jié)構(gòu)： 1) 集合 13 四種典型結(jié)構(gòu) 12 基本概念和術(shù)語 2）線形 ： 14 四種典型結(jié)構(gòu)： 12 基本概念和術(shù)語 3）樹形 ： 15 四種典型結(jié)構(gòu)： 12 基本概念和術(shù)語 4）圖或網(wǎng)絡(luò)： 16 12 基本概念和術(shù)語 （ 5）邏輯結(jié)構(gòu)： 從具體問題抽象出的數(shù)學(xué)模型。這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。因此，為了編寫出一個“好”的程序，必須分析 處理的對象的特征及個對象之間的存在的關(guān)系。1 數(shù) 據(jù) 結(jié) 構(gòu) （ C語言版） 作者：黎劍兵 2 第 一 章 緒 論 [學(xué)習(xí)內(nèi)容 ] ? 常用術(shù)語 ? 算法評價 ? 時間復(fù)雜度與空間復(fù)雜度的分析 [重點 ]了解邏輯結(jié)構(gòu) 物理結(jié)構(gòu)和數(shù)據(jù)的運算三方面相關(guān)概念及相互關(guān)系 [難點 ] 時間復(fù)雜度的分析方法 [掌握 ] 用類 C語言的表示方法會用類 C編寫程序 3 第 一 章 緒 論 計算機科技 是 一門研究用計算機進(jìn)行信息表示和處理的科學(xué)。這就是本課程所要研究的問題 。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？ 5 數(shù)學(xué) 軟件 硬件 DS 第 一 章 緒 論 6 數(shù)學(xué) 軟件 硬件 DS 第 一 章 緒 論 數(shù)據(jù)結(jié)構(gòu) Data Structure 7 機外表示 處理要求 邏輯機構(gòu) 基本運算 存儲機構(gòu) 算法 數(shù)據(jù)模型 問題 實現(xiàn) 第 一 章 緒 論 8 機外表示 處理要求 邏輯機構(gòu) 基本運算 存儲機構(gòu) 算法 數(shù)據(jù)模型 問題 實現(xiàn) 第 一 章 緒 論 (1)要對所加工的對象進(jìn)行邏輯組織 (2)如何把加工對象存儲到計算機中去？ (3)數(shù)據(jù)運算 9 3. 學(xué)科定義 11 什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 是一門研究非數(shù)值 計算的程序設(shè) 計問題中計算機的 操作對象以及它們之間的關(guān)系和 操作等等的科 。體現(xiàn)邏輯關(guān)系。 ? 特性： 有窮性 確定性 可行性 輸入 輸出 20 13 算法和算法分析 二、算法的描述與分析 ?描述：類 C語言 ?要求 ? 正確性： a. 語法 b. n個輸入 c. 一組典型的苛刻的輸入 d. 所有輸入 ? 可讀性 ? 健壯性 ? 效率與存貯量 21 13 算法和算法分析 ?分析標(biāo)準(zhǔn) a 、時間復(fù)雜度 ： 算法中基本操作重復(fù)執(zhí)行的次數(shù) (頻度 )。kn。 O(n2) 24 習(xí)題與練習(xí) 一 ： a. 數(shù)據(jù)與數(shù)據(jù)元素有何區(qū)別？ b. 邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么？它們 是什么關(guān)系？ c. 什么是算法？它有什么特點？ 25 習(xí)題與練習(xí) 一 2. 試寫一個算法，統(tǒng)計輸入的 100個整數(shù)中奇數(shù)和偶數(shù)的個數(shù)。I++){ m=m+I。 } 27 習(xí)題與練習(xí) 一 （ 2） for(I=0。j10。s=0。 29 第 二 章 線 性 表 [學(xué)習(xí)內(nèi)容 ] ? 線性表定義 ? 線性表的抽象數(shù)據(jù)結(jié)構(gòu) ? 線性表的順序存儲和操作實現(xiàn) ? 線性表的鏈接存儲 ? 線性表在鏈表上的操作實現(xiàn) ? 線性表在雙向鏈表操作實現(xiàn) 30 第二章 線性表 線性結(jié)構(gòu)特點 ： 在數(shù)據(jù)元素的非空有限集合中 1）“第一個 ”唯一 2）“最后一個”唯一 3）除第一個外，每一個有且僅有一個直接前驅(qū) 4）除最后一個外，每一個均有且僅有一個直接后繼 31 一 、 線性表的定義 第二章 線性表 線性表的邏輯結(jié)構(gòu)示意圖 a … ai a2 … ai+1 an 表頭元素 表尾元素 167。 線性表的類型定義 線性表幾個具體例子 L1=（’ a’ ,’ b’ ,’ c’ ,’ 4’ ,’ 7’ ,’ +’ ,’’ ,’ *’ ,’ /’ ） L2=（ 25,35,28,49,51,87,46,32,88） L 3 =（ “ BASIC” ,“ PASCAL” ,“ JAVA” ,“OK” ） L4=（ a,b,c,d,e,f,g,h,i,j,k,x,y,z） 35 167。 其作用是返回線性表 sq的長度 。 36 167。 其作用是在線性表 sq的第 i個位置上增加一個以 x為值的新元素 ， 使 sq由 (a1， … ， ai1， ai， … ， an)變?yōu)?(a1， … ， ai1， x， ai， … ， an)。其作用是刪除線性表 sq的第 i個元素 ai,使 sq由 (a1， … ， ai1，ai， ai+l， … ， an)變?yōu)?(a1， … ， ai1，ai+1， … ， an)。否則，返回 NULL。另一方面，在實際應(yīng)用中，可以根據(jù)具體需要選擇適當(dāng)?shù)幕具\算 41 167。 42 167。 for(i=l。 //在線性表 A中查找 x if (k0) ListDelete (A， k)。C){ int i， k， j=1； ElemType x； InitList(C)； for (i=1； i=Getlen(A)； i++) { x=GetElem(A,i)。 } //若在線性表 B中 }} //找到 ， 將其插入 C 45 167。 線性表的順序存儲和實現(xiàn) 元素地址計算方法 ： lLOC(ai)=LOC(a1)+(i1)*L lLOC(ai+1)=LOC(ai)+L 其中： uL一個元素占用的存儲單元個數(shù) uLOC(ai)—線性表第 i個元素的地址 48 a1 an 0 1 n1 1 2 n 內(nèi)存 V數(shù)組下標(biāo) 元素序號 M1 a2 備用空間 167。 char author[10]。 50 可以定義為靜態(tài)數(shù)組或變量 DATATYPE library[M]。 線性表的順序存儲和實現(xiàn) )11( ??? ni?插入一個元素 定義： 線性表的插入是指在第 i 個元素之前插入一個新的數(shù)據(jù)元素 x，使長度為 n的線性表 ( a1,