【文章內(nèi)容簡介】 數(shù)據(jù)對象及數(shù)據(jù)對象之間的關(guān)系 操作名稱及輸入輸出類型 數(shù)據(jù)結(jié)構(gòu) (表示 ) 操作 (算法 )的實現(xiàn) (函數(shù) ) ADT定義與實現(xiàn)的關(guān)系 預(yù)定義常量和類型： define TURE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2 typedef int Status。 ADT實現(xiàn)中幾個問題 引用 運算符： amp。 引用是個 別名 建立引用時 ,程序用另一個 已定義的變量 的名字 初始化它 ,從那時起 ,引用作為目標(biāo)的別名而使用 ,對引用的改動實際就是對目標(biāo)的改動。 例如： int a=4。 /*a為普通的整型變量 */ int amp。b=a。 /*b是 a的引用變量 */ b變量是變量 a的 引用 ,b也等于 4,這兩個變量 同步改變 注意： C語言 不支持引用 類型 ADT實現(xiàn)中幾個問題 關(guān)于 引用 ： 引用常用于 函數(shù)形參 中 ,采用引用型形參時 ,實現(xiàn)數(shù)據(jù)雙向傳遞 ,例如： ADT實現(xiàn)中幾個問題 關(guān)于 引用 ： void swap(int x, int y) { int temp。 temp=x。 x=y。 y=temp。 } 當(dāng)用執(zhí)行語句 swap(a,b)時： a 和 b的值 沒有 發(fā)生交換 值傳遞 引用常用于 函數(shù)形參 中 ,采用引用型形參時 ,實現(xiàn)數(shù)據(jù)雙向傳遞 ,例如： ADT實現(xiàn)中幾個問題 關(guān)于 引用 ： void swap(int *x, int *y) { int temp。 temp = *x。 *x= *y。 *y=temp。 } 當(dāng)用執(zhí)行語句 swap(amp。a,amp。b)時： a 和 b的值 發(fā)生 了 交換 地址傳遞 引用常用于 函數(shù)形參 中 ,采用引用型形參時 ,實現(xiàn)數(shù)據(jù)雙向傳遞 ,例如： ADT實現(xiàn)中幾個問題 關(guān)于 引用 ： void swap(int amp。x, int amp。y) { int temp。 temp=x。 x=y。 y=temp； } 當(dāng)用執(zhí)行語句 swap(a,b)時： a 和 b的值 發(fā)生了交換 引用傳遞 引用方式簡潔 教材中 很多算法都采用引用形式的形參 ? 書上算法采用 類 C語言 書寫 ? 類 C語言 與 C程序 之間的差別： (1) 算法中除形式參數(shù)外 ,變量不作定義 ，在 C程序中必須定義； (2) 算法中使用的 元素類型 (ElemType)沒有定義， C程序中必須定義； 常量 OK、 ERROR、OVERFLOW等在第一章統(tǒng)一定義； (3) 算法中的 比較運算符 (equal、 less)未作定義， C程序中必須定義； (4) 必要的 頭文件 (用作輸入輸出的 的 )，在 C程序中必須包含。 ADT實現(xiàn)中幾個問題 ?算法（ Algorithm） Pronunciation: algorithum Derives from the name of the Persian (Baghdad) mathematician: Abu Ja39。far Muhammad ibn Musa alKhwarizmi arithmetic 算法描述與算法分析簡介 Definitions of Algorithm: ?A putable set of steps to achieve a desired result ?A clearly specified set of simple instructions to be followed to solve a problem ?A finite set of instructions that, if followed, acplishes a particular task ?A finite set of rules which gives a sequence of operation for solving a specific type of problem. ?A stepbystep problemsolving procedure ?算法（ Algorithm） —解決某一特定問題的 具體步驟的描述 ，是指令的有限序列 算法定義 ?有窮性 (Finiteness)——算法必須在執(zhí)行有限步驟后結(jié)束 (The algorithm terminates after finite number of steps) ?確定性 (Definiteness)——算法每一步驟必須是確切定義的，不能產(chǎn)生二義性 (Each instruction is clear and unambiguous) ?可行性 (Effectiveness)——算法是能行的 (Every instruction must be basic enough to be carried out. It also must be feasible) ?輸入 (Input) ——算法有零個或多個輸入 (There are zero or more quantities that are externally supplied) ?輸出 (Output) ——算法有一個或多個輸出 (At least one quantity is produced) 算法特性 void exam1() { int n=2。 while(n%2==0) n=n+2。 printf(“%d\n”,n)。 } void exam2() { int y=0。 int x=3/y。 printf(“%d,%d\n”,x,y)。 } 違反了 有窮性 違反了 可行性 這兩段描述均不能滿足算法的特征 ,試問它們 違反了哪些特征 ？ 算法特性 In natural languages, like English or Chinese Flow charts Pseudocode Programming languages, like C or Java Recipe: CHOCOLATE CAKE 4 oz. chocolate 3 eggs 1 cup butter 1 tsp. vanilla 2 cups sugar 1 cup flour Melt chocolate and butter. Stir sugar into melted chocolate. Stir eggs and vanilla Mix in flour Spread mix in greased pan Baked at 350 for 40 minutes or until inserted fork es out almost clean Cool in pan before eating Program Code Declare variables Chocolate eggs mix butter vanilla sugar flour mix=melted ((4*chocolate) +butter) mix=stir(mix+(2*sugar)) mix=stir(mix+(3*eggs)+vanilla) mix=mix+flour spread(mix) while( not clean(fork)) bake(mix, 350) Mix Ingredients Spread In Pan Bake at 350 Remove from Oven Let Cool Eat Test with Fork Ready Not Ready 算法描述 Descriptions ?衡量算法優(yōu)劣的標(biāo)準(zhǔn) ?正確性 (Correctness) ?可讀性 (Readability) ?健壯性 (Robust