【正文】 (a1, a2, …, a i1, x, ai, … a n ) 52 167。 free(pData )； 167。 50 可以定義為靜態(tài)數(shù)組或變量 DATATYPE library[M]。 float price。 char author[10]。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) ?線性表的順序存儲(chǔ)示例 （圖書資料） typedef struct card{ int num。 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 元素地址計(jì)算方法 ： lLOC(ai)=LOC(a1)+(i1)*L lLOC(ai+1)=LOC(ai)+L 其中： uL一個(gè)元素占用的存儲(chǔ)單元個(gè)數(shù) uLOC(ai)—線性表第 i個(gè)元素的地址 48 a1 an 0 1 n1 1 2 n 內(nèi)存 V數(shù)組下標(biāo) 元素序號(hào) M1 a2 備用空間 167。即用一組地址連續(xù)的存儲(chǔ)單元存放一個(gè)線性表 ?特點(diǎn)： ? 實(shí)現(xiàn)邏輯上相鄰 —物理地址相鄰 ? 實(shí)現(xiàn)隨機(jī)存取 ?實(shí)現(xiàn)： （ 一維 ） 數(shù)組 46 下標(biāo)位置 0 1 … i1 i … n1 … MaxSize1 數(shù)組存貯空間 a1 a2 … ai ai+1 … an … 167。 } //若在線性表 B中 }} //找到 ， 將其插入 C 45 167。 //在線性表 B中查 x if (k0) {Insert(C,x,j)。C){ int i， k， j=1； ElemType x； InitList(C)； for (i=1； i=Getlen(A)； i++) { x=GetElem(A,i)。 線性表的類型定義 [解 ] 先始化線性表 C，然后依次檢查線性表 A中的每個(gè)元素，看它是否在線性表 B中；若在線性表 B中，則將其插入到線性表 C中 . 基本運(yùn)算 [例 ] 利用線性表的基本運(yùn)算，編寫將線性表 A和 B中公共元素生成線性表 C的算法 44 167。 //在線性表 A中查找 x if (k0) ListDelete (A， k)。i++){ x=GetElem(B,i)。 for(i=l。A， sqlist B) { //A為引用型參數(shù) int i, k。 42 167。若在表A中，則將其從 A中刪除 。另一方面，在實(shí)際應(yīng)用中，可以根據(jù)具體需要選擇適當(dāng)?shù)幕具\(yùn)算 41 167。否則，返回 NULL 40 167。否則，返回 NULL。 39 167。其作用是刪除線性表 sq的第 i個(gè)元素 ai,使 sq由 (a1， … ， ai1，ai， ai+l， … ， an)變?yōu)?(a1， … ， ai1，ai+1， … ， an)。 線性表的類型定義 38 167。 其作用是在線性表 sq的第 i個(gè)位置上增加一個(gè)以 x為值的新元素 ， 使 sq由 (a1， … ， ai1， ai， … ， an)變?yōu)?(a1， … ， ai1， x， ai， … ， an)。 若 sq中存在一個(gè)或多個(gè)值與 x相等的元素 ， 則其作用是返回這些元素的序號(hào)的最小值；否則 ， 返回 0。 36 167。 若1≤i≤ListLen(sq)， 則其作用是返回線性表 sq的第 i個(gè)數(shù)據(jù)元素 。 其作用是返回線性表 sq的長(zhǎng)度 。其作用是建立一個(gè)空表 sq(即建立線性表的構(gòu)架，但不含任何數(shù)據(jù)元素 )。 線性表的類型定義 線性表幾個(gè)具體例子 L1=（’ a‘,‘b‘,‘c‘,‘4‘,‘7‘,‘+‘,‘‘,‘*‘,‘/‘） L2=（ 25,35,28,49,51,87,46,32,88） L3=（ “ BASIC‖,―PASCAL‖,―JAVA‖,―OK‖） L4=（ a,b,c,d,e,f,g,h,i,j,k,x,y,z） 35 167。 線性表的類型定義 一、線性表的定義 ?一個(gè)線性表可以用一個(gè)標(biāo)識(shí)符來命名： A=(a1 , a2 , … , ai , ai+1 , … , an) ai可以是基本數(shù)據(jù)類型也可以是 struct 類型 33 167。 29 第 二 章 線 性 表 [學(xué)習(xí)內(nèi)容 ] ? 線性表定義 ? 線性表的抽象數(shù)據(jù)結(jié)構(gòu) ? 線性表的順序存儲(chǔ)和操作實(shí)現(xiàn) ? 線性表的鏈接存儲(chǔ)和在鏈表上的操作實(shí)現(xiàn) ? 線性表在雙向鏈表操作實(shí)現(xiàn) 30 第二章 線性表 線性結(jié)構(gòu)特點(diǎn) ： 在數(shù)據(jù)元素的非空有限集合中 1）“第一個(gè) ”唯一 2）“最后一個(gè)”唯一 3）除第一個(gè)外，每一個(gè)有且僅有一個(gè)直接前驅(qū) 4）除最后一個(gè)外，每一個(gè)均有且僅有一個(gè)直接后繼 31 一 、 線性表的定義 第二章 線性表 線性表的邏輯結(jié)構(gòu)示意圖 a … ai a2 … ai+1 an 表頭元素 表尾元素 167。 s++。s=0。 j++。j10。I++){ m=m+I。 } 27 習(xí)題與練習(xí) 一 （ 2） for(I=0。jn。I++){ m=m+I。 26 習(xí)題與練習(xí) 一 4. 設(shè) n 為正整數(shù)，寫出下列程序段的時(shí)間復(fù)雜度： （ 1） for(I=1。 O(n2) 24 習(xí)題與練習(xí) 一 ： a. 數(shù)據(jù)與數(shù)據(jù)元素有何區(qū)別？ b. 邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是什么？它們 是什么關(guān)系？ c. 什么是算法？它有什么特點(diǎn)？ 25 習(xí)題與練習(xí) 一 2. 試寫一個(gè)算法，統(tǒng)計(jì)輸入的 100個(gè)整數(shù)中奇數(shù)和偶數(shù)的個(gè)數(shù)。jk。kn。 T(o)=O(f(n)) 時(shí)間復(fù)雜度分為平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度 復(fù)雜度的值取規(guī)模函數(shù)最高階 13 算法和算法分析 b 、空間復(fù)雜度： 算法所需存貯空間 S(n)=O(f(n)) 23 13 算法和算法分析 例：分析下列語(yǔ)句段的時(shí)間復(fù)雜度 m = 0。 ? 特性： 有窮性 確定性 可行性 輸入 輸出 20 13 算法和算法分析 二、算法的描述與分析 ?描述：類 C語(yǔ)言 ?要求 ? 正確性： a. 語(yǔ)法 b. n個(gè)輸入 c. 一組典型的苛刻的輸入 d. 所有輸入 ? 可讀性 ? 健壯性 ? 效率與存貯量 21 13 算法和算法分析 ?分析標(biāo)準(zhǔn) a 、時(shí)間復(fù)雜度 ： 算法中基本操作重復(fù)執(zhí)行的次數(shù) (頻度 )。 ? DE存儲(chǔ)稱為 節(jié)點(diǎn) ?關(guān)系存儲(chǔ)： a. 順序存儲(chǔ) b. 鏈?zhǔn)酱鎯?chǔ) 17 12 基本概念和術(shù)語(yǔ) （ 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ù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。體現(xiàn)邏輯關(guān)系。數(shù)據(jù)項(xiàng) 是數(shù)據(jù)最小單位 (2) 數(shù)據(jù) (data) 是對(duì)客觀事物的 表示，指所有能輸入到計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號(hào)的總稱。那么，什么是數(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)算 存儲(chǔ)機(jī)構(gòu) 算法 數(shù)據(jù)模型 問題 實(shí)現(xiàn) 第 一 章 緒 論 8 機(jī)外表示 處理要求 邏輯機(jī)構(gòu) 基本運(yùn)算 存儲(chǔ)機(jī)構(gòu) 算法 數(shù)據(jù)模型 問題 實(shí)現(xiàn) 第 一 章 緒 論 (1)要對(duì)所加工的對(duì)象進(jìn)行邏輯組織 (2)如何把加工對(duì)象存儲(chǔ)到計(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ī)的 操作對(duì)象以及它們之間的關(guān)系和 操作等等的學(xué)科 。這些信息之間大多數(shù)情況下往往具有重要的結(jié)構(gòu)關(guān)系。這就是本課程所要研究的問題 。信息量的增加，信息范圍的拓寬，使系統(tǒng)程序和應(yīng)用程序的規(guī)模的日趨增大，結(jié)構(gòu)也日趨增大。1 數(shù) 據(jù) 結(jié) 構(gòu) （ C語(yǔ)言版） 作者：黎劍兵 2 第 一 章 緒 論 [學(xué)習(xí)內(nèi)容 ] ? 常用術(shù)語(yǔ) ? 算法評(píng)價(jià) ? 時(shí)間復(fù)雜度與空間復(fù)雜度的分析 [重點(diǎn) ]了解邏輯結(jié)構(gòu) 物理結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算三方面相關(guān)概念及相互關(guān)系 [難點(diǎn) ] 時(shí)間復(fù)雜度的分析方法 [掌握 ] 用類 C語(yǔ)言的表示方法會(huì)用類 C編寫程序 3 第 一 章 緒 論 計(jì)算機(jī)科技 是 一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。 ?主要涉及兩方面的問題： 信息的表示 和 信息的處理 信息的表示和組織直接關(guān)系到處理信息的程序 的效率，隨著計(jì)算機(jī)的應(yīng)用領(lǐng)域的擴(kuò)大。因此，為了編寫出一個(gè)“好”的程序，必須分析 處理的對(duì)象的特征及個(gè)對(duì)象之間的存在的關(guān)系。 4 第 一 章 緒 論 計(jì)算機(jī)程序 是 對(duì)信息進(jìn)行加工處理。這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。 10 12 基本概念和術(shù)語(yǔ) (1) 數(shù)據(jù)元素 (data element) 數(shù)據(jù)基本單位，也稱節(jié)或孩子，可由若干個(gè)數(shù)據(jù)項(xiàng)組成。 (3) 數(shù)據(jù)對(duì)象 ( data object)性質(zhì)相同的數(shù)據(jù)元素的集合 (4) 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)元素之間的相互關(guān)系 11 1) 集合 12 基本概念和術(shù)語(yǔ) 數(shù)據(jù)間的四種典型結(jié)構(gòu)： 2）線形 3）樹形 4）圖或網(wǎng)絡(luò)： 12 12 基本概念和術(shù)語(yǔ) 四種典型結(jié)構(gòu)： 1) 集合 13 四種典型結(jié)構(gòu) 12 基本概念和術(shù)語(yǔ) 2）線形 ： 14 四種典型結(jié)構(gòu)： 12 基本概念和術(shù)語(yǔ) 3）樹形 ： 15 四種典型結(jié)構(gòu)： 12 基本概念和術(shù)語(yǔ) 4）圖或網(wǎng)絡(luò)： 16 12 基本概念和術(shù)語(yǔ) （ 5）邏輯結(jié)構(gòu)： 從具體問題抽象出的數(shù)學(xué)模型。 （ 6）物理結(jié)構(gòu) (存儲(chǔ)結(jié)構(gòu) )： DE及關(guān)系在計(jì)算機(jī)中的表示。 A．線性結(jié)構(gòu) B． 非線性結(jié)構(gòu) A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表 棧 隊(duì) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 12 基本概念和術(shù)語(yǔ) 19 13 算法和算法分析 一、算法定義 算法 是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。 T(o)=O(f(n)) 時(shí)間復(fù)雜度分為平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度 復(fù)雜度的值取規(guī)模函數(shù)最高階 22 ?分析標(biāo)準(zhǔn) a 、時(shí)間復(fù)雜度 ： 算法中基本操作重復(fù)執(zhí)行的次數(shù)。 1 for( k=0。k++) n+1 for(j=0。j++)