【正文】 1 數(shù) 據(jù) 結(jié) 構(gòu) （ C語言版） 作者：黎劍兵 2 第 一 章 緒 論 [學(xué)習(xí)內(nèi)容 ] ? 常用術(shù)語 ? 算法評價 ? 時間復(fù)雜度與空間復(fù)雜度的分析 [重點(diǎn) ]了解邏輯結(jié)構(gòu) 物理結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三方面相關(guān)概念及相互關(guān)系 [難點(diǎn) ] 時間復(fù)雜度的分析方法 [掌握 ] 用類 C語言的表示方法會用類 C編寫程序 3 第 一 章 緒 論 計(jì)算機(jī)科技 是 一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。 ?主要涉及兩方面的問題： 信息的表示 和 信息的處理 信息的表示和組織直接關(guān)系到處理信息的程序 的效率，隨著計(jì)算機(jī)的應(yīng)用領(lǐng)域的擴(kuò)大。信息量的增加，信息范圍的拓寬，使系統(tǒng)程序和應(yīng)用程序的規(guī)模的日趨增大，結(jié)構(gòu)也日趨增大。因此，為了編寫出一個“好”的程序，必須分析 處理的對象的特征及個對象之間的存在的關(guān)系。這就是本課程所要研究的問題 。 4 第 一 章 緒 論 計(jì)算機(jī)程序 是 對信息進(jìn)行加工處理。這些信息之間大多數(shù)情況下往往具有重要的結(jié)構(gòu)關(guān)系。這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。那么，什么是數(shù)據(jù)結(jié)構(gòu)呢？ 5 數(shù)學(xué) 軟件 硬件 DS 第 一 章 緒 論 6 數(shù)學(xué) 軟件 硬件 DS 第 一 章 緒 論 數(shù)據(jù)結(jié)構(gòu) Data Structure 7 機(jī)外表示 處理要求 邏輯機(jī)構(gòu) 基本運(yùn)算 存儲機(jī)構(gòu) 算法 數(shù)據(jù)模型 問題 實(shí)現(xiàn) 第 一 章 緒 論 8 機(jī)外表示 處理要求 邏輯機(jī)構(gòu) 基本運(yùn)算 存儲機(jī)構(gòu) 算法 數(shù)據(jù)模型 問題 實(shí)現(xiàn) 第 一 章 緒 論 (1)要對所加工的對象進(jìn)行邏輯組織 (2)如何把加工對象存儲到計(jì)算機(jī)中去？ (3)數(shù)據(jù)運(yùn)算 9 3. 學(xué)科定義 11 什么是數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu) 是一門研究非數(shù)值 計(jì)算的程序設(shè) 計(jì)問題中計(jì)算機(jī)的 操作對象以及它們之間的關(guān)系和 操作等等的科 。 10 12 基本概念和術(shù)語 (1) 數(shù)據(jù)元素 (data element) 數(shù)據(jù)基本單位，也稱節(jié)或孩子，可由若干個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng) 是數(shù)據(jù)最小單位 (2) 數(shù)據(jù) (data) 是對客觀事物的 表示，指所有能輸入到計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號的總稱。 (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é)模型。體現(xiàn)邏輯關(guān)系。 （ 6）物理結(jié)構(gòu) (存儲結(jié)構(gòu) )： DE及關(guān)于在計(jì)算機(jī)中的表示。 ? DE存儲稱為 節(jié)點(diǎn) ?關(guān)系存儲： a. 順序存儲 b. 鏈?zhǔn)酱鎯? 17 12 基本概念和術(shù)語 （ 7） DS廣義定義： ? DE 的邏 輯 結(jié) 構(gòu) ? DE 的物 理 結(jié) 構(gòu) ? DE 的 抽 象 運(yùn) 算 （ 8）基本操作 ? 加工型：查找 刪除 更新 排序 ? 引用型：查找 18 1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A．線性結(jié)構(gòu) B． 非線性結(jié)構(gòu) A 順序存儲 B 鏈?zhǔn)酱鎯? 線性表 棧 隊(duì) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的三個方面 12 基本概念和術(shù)語 19 13 算法和算法分析 一、算法定義 算法 是對特定問題求解步驟的一種描述，是指令的有限序列。 ? 特性： 有窮性 確定性 可行性 輸入 輸出 20 13 算法和算法分析 二、算法的描述與分析 ?描述：類 C語言 ?要求 ? 正確性： a. 語法 b. n個輸入 c. 一組典型的苛刻的輸入 d. 所有輸入 ? 可讀性 ? 健壯性 ? 效率與存貯量 21 13 算法和算法分析 ?分析標(biāo)準(zhǔn) a 、時間復(fù)雜度 ： 算法中基本操作重復(fù)執(zhí)行的次數(shù) (頻度 )。 T(o)=O(f(n)) 時間復(fù)雜度分為平均時間復(fù)雜度和最壞時間復(fù)雜度 復(fù)雜度的值取規(guī)模函數(shù)最高階 22 ?分析標(biāo)準(zhǔn) a 、時間復(fù)雜度 ： 算法中基本操作重復(fù)執(zhí)行的次數(shù)。 T(o)=O(f(n)) 時間復(fù)雜度分為平均時間復(fù)雜度和最壞時間復(fù)雜度 復(fù)雜度的值取規(guī)模函數(shù)最高階 13 算法和算法分析 b 、空間復(fù)雜度： 算法所需存貯空間 S(n)=O(f(n)) 23 13 算法和算法分析 例：分析下列語句段的時間復(fù)雜度 m = 0。 1 for( k=0。kn。k++) n+1 for(j=0。jk。j++) n(n+1)/2 m +=2。 O(n2) 24 習(xí)題與練習(xí) 一 ： a. 數(shù)據(jù)與數(shù)據(jù)元素有何區(qū)別？ b. 邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是什么？它們 是什么關(guān)系？ c. 什么是算法？它有什么特點(diǎn)？ 25 習(xí)題與練習(xí) 一 2. 試寫一個算法，統(tǒng)計(jì)輸入的 100個整數(shù)中奇數(shù)和偶數(shù)的個數(shù)。 3. 設(shè)計(jì)下面問題算法，并分析最壞情況時間復(fù)雜性 : 在數(shù)組 A[1..n]中查找值為 K的元素，若找到輸出其位置 i ( 0 i n+1),否則輸出 0。 26 習(xí)題與練習(xí) 一 4. 設(shè) n 為正整數(shù)，寫出下列程序段的時間復(fù)雜度： （ 1） for(I=1。In。I++){ m=m+I。 for(j=0。jn。j++) count +=m+j。 } 27 習(xí)題與練習(xí) 一 （ 2） for(I=0。In。I++){ m=m+I。 for(j=0。j10。) { count +=m+j。 j++。 } } 28 習(xí)題與練習(xí) 一 （ 3） k=1。s=0。 while(s=n1){ k=k+s*6。 s++。 } printf(“ %d,%d” ,s,k)。 29 第 二 章 線 性 表 [學(xué)習(xí)內(nèi)容 ] ? 線性表定義 ? 線性表的抽象數(shù)據(jù)結(jié)構(gòu) ? 線性表的順序存儲和操作實(shí)現(xiàn) ? 線性表的鏈接存儲 ? 線性表在鏈表上的操作實(shí)現(xiàn) ? 線性表在雙向鏈表操作實(shí)現(xiàn) 30 第二章 線性表 線性結(jié)構(gòu)特點(diǎn) ： 在數(shù)據(jù)元素的非空有限集合中 1）“第一個 ”唯一 2）“最后一個”唯一 3）除第一個外，每一個有且僅有一個直接前驅(qū) 4）除最后一個外，每一個均有且僅有一個直接后繼 31 一 、 線性表的定義 第二章 線性表 線性表的邏輯結(jié)構(gòu)示意圖 a … ai a2 … ai+1 an 表頭元素 表尾元素 167。 線性表的類型定義32 167。 線性表的類型定義 一、線性表的定義 ?一個線性表可以用一個標(biāo)識符來命名： A=(a1 , a2 , … , ai , ai+1 , … , an) ai可以是基本數(shù)據(jù)類型也可以是 struct 類型 33 167。 線性表的類型定義 二、線性結(jié)構(gòu)特點(diǎn) ?在數(shù)據(jù)元素的非空有限集中 ? 元素個數(shù) n—表長度， n=0空表 ? 存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素 ? 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素 ? 除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前趨 ? 除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼 ? 元素同構(gòu)，且不能出現(xiàn)缺項(xiàng) 34 學(xué)號 姓名 年齡 001 張三 18 002 李四 19 …… …… …… 數(shù)據(jù)元素 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。 線性表的類型定義 基本運(yùn)算 ( 1 ) 初始化 initList(sq)。其作用是建立一個空表 sq(即建立線性表的構(gòu)架，但不含任何數(shù)據(jù)元素 )。 ( 2 ) 求表長 ListLen(sq)。 其作用是返回線性表 sq的長度 。 ( 3 ) 讀表 元 素 G e t E l e m ( s q ， i)。 若1≤i≤ListLen(sq)， 則其作用是返回線性表 sq的第 i個數(shù)據(jù)元素 。否則 ， 返回 NULL。 36 167。 線性表的類型定義 基本運(yùn)算 (4)定位 (按值查找 )LocateElem(sq， x)。 若 sq中存在一個或多個值與 x相等的元素 ， 則其作用是返回這些元素的序號的最小值；否則 ， 返回 0。 37 基本運(yùn)算 (5)插入 ListInsert(sq， x， i)。 其作用是在線性表 sq的第 i個位置上增加一個以 x為值的新元素 ， 使 sq由 (a1， … ， ai1， ai， … ， an)變?yōu)?(a1， … ， ai1， x， ai， … ， an)。 參數(shù) i的合法取值范圍是： 1≤i≤n+ 1 167。 線性表的類型定義 38 167。 線性表的類型定義 基本運(yùn)算 (6)刪除 ListDelete(sq， i)。其作用是刪除線性表 sq的第 i個元素 ai,使 sq由 (a1， … ， ai1，ai， ai+l， … ， an)變?yōu)?(a1， … ， ai1，ai+1， … ， an)。參數(shù) i的合法取值范圍是：1≤i≤n。 39 167。 線性表的類型定義 基本運(yùn)算 (7)求前趨 PriorElem(sq,e) 若線性表中存在元素 e且不是第一個 ,其作用是返回 e的前趨元素 。否則，返回 NULL。 (8)求后繼 NextElem(sq,e) 若線性表中存在元素 e且不是最后一個 ,其作用是返回 e的后繼元素 。否則，返回 NULL 40 167。 線性表的類型定義 基本運(yùn)算 ?應(yīng)用基本運(yùn)算可以實(shí)現(xiàn)線性表的其他運(yùn)算，如求任一給定數(shù)據(jù)元素的直接后繼或直接前趨，將兩個線性表合并成一個線性表或?qū)⒁粋€線性表拆分成兩個線性表等等。另一方面，在實(shí)際應(yīng)用中，可以根據(jù)具體需要選擇適當(dāng)?shù)幕具\(yùn)算 41 167。 線性表的類型定義 [解 ]本題的算法思路是：依次檢查線性表 B中的每個元素，看它是否在線性表 A中。若在表A中，則將其從 A中刪除 。 基本運(yùn)算 [例 ] 利用線性表的基本運(yùn)算，編寫在線性表 A中刪除線性表 B中出現(xiàn)的元素的算法。 42 167。 線性表的類型定義