【正文】 關(guān)系： O(1)O(log2n)O(n)O(n*log2n)O(n2) O(n3)O(2n)O(n!) 例 求階乘和： sum=1!+2!+3!+… …+n! 方法 1： float sum1(int n) {float s=0,p=1。 //(3) for (k=1。 2 Doubtlessness 對 于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定。 數(shù)據(jù)的邏輯結(jié)構(gòu)是從具體問題抽象出來的 數(shù)據(jù)模型 酒店管理問題中，客房之間的邏輯關(guān)系指的是什么？ 人機(jī)對弈問題中，格局之間的邏輯關(guān)系指的是什么？ 考試計劃編排問題中，課程之間的邏輯關(guān)系指的是什么？ 二、 Logical Structure 數(shù)據(jù)元素之間的 邏輯關(guān)系 ） (1) 數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類： Set——數(shù)據(jù)元素間除 “ 同屬于一個集合 ” 外，無其它關(guān)系 Linear list——onetoone ，如線性表、棧、隊列 Tree——onetomany graph——多 manytomany 基本概念 非線性結(jié)構(gòu) ? (2) 數(shù)據(jù) 邏輯 結(jié)構(gòu)的形式定義 ? 二元組表示法 ? Data_Structure=( D , S ) ? 其中： ? D 數(shù)據(jù)元素的有限集合。 對弈的過程就是從樹根沿樹杈到某個葉子的過程。 《 DS》 就是要研究數(shù)據(jù)之間的聯(lián)系。 ? 如果姓名和電話號碼的排列次序無規(guī)律， 則只能逐一比較姓名進(jìn)行查找 ? 如果姓名按字典順序組織，則查找就快捷多了 結(jié)論 2. 數(shù)據(jù)之間是有聯(lián)系的 這些聯(lián)系常常影響算法的選擇和效率。 } 2） nonnumerical problem play chess …….. …….. …... …... …... …... ◆ Build model ?問題涉及的對象 : 對弈過程中可能出現(xiàn)的棋盤格局； ?棋盤格局之間的關(guān)系：由比賽規(guī)則決定。 Data Structure—— the set of data elements with some special relationships. P31 data structure is divided into logical structure and storage structure ?Logical Structure：指數(shù)據(jù)元素之間 邏輯關(guān)系 的整體。 ? 形式如下： ? ADT 抽象數(shù)據(jù)類型名 ? Data ? 數(shù)據(jù)元素之間邏輯關(guān)系的定義 ? Operation ? 操作 1 ? 前置條件：執(zhí)行此操作前數(shù)據(jù)所必須的狀態(tài) ? 輸入：執(zhí)行此操作所需要的輸入 ? 功能：該操作將完成的功能 ? 輸出：執(zhí)行該操作后產(chǎn)生的輸出 ? 后置條件：執(zhí)行該操作后數(shù)據(jù)的狀態(tài) ? 操作 2 ? …… ? …… ? 操作 n ? …… Algorithm and Algorithm Analysis 一、 difinition of algorithm Algorithm is the operation sequence for solving a problem. For example： the algorithm is to find out the maximum number MAX of two positive integers m and n. ⑴ if m n then max=m ⑵ if m = n then max=n 求正整數(shù) m， n中的最大數(shù)的算法 Characteristic of algorithms： 1 Finiteness 對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個步驟都能在 有限時間 內(nèi)完成。j++){ //(2) x=0。 其余常用的還有平方階 O(n2)、立方階 O(n3)、對數(shù)階 O(log2n)、指數(shù)階 O(2n)等。 } time plexity：T(n) = O(n2) T(n) = = =n1 + n2 + n3 + ……+1= ??????11 11njjni????11)(njjn2)1( ?nn例 Bubble Sort algorithm void bubble_sort (int a[ ], int n ) { //用起泡排序方法，將 a[ ] 中 n個整數(shù)的序列排列成自小至大有序的整數(shù)序列 int i,j,t。 算法的度量 ： Time plexity Space Complexity ? 算法的時間復(fù)雜度、空間復(fù)雜度 ? T(n) = O(f(n)) ? O(n) = O(f(n)) ? 例 15 ++x。 ++i) ? for (j=1。 Count++。 j=i1。 了解抽象數(shù)據(jù)類型的定義、表示和實(shí)現(xiàn)方法。j=i。k=i+j。 for (i=1。存儲結(jié)構(gòu) ? 例如： 整數(shù)數(shù)據(jù)對象的集合： ? N={0,177。 drawback ：以數(shù)據(jù)為中心，不易應(yīng)對變化 History 3. Objectoriented stage ： (數(shù)據(jù)結(jié)構(gòu)＋算法 )=程序 Application Fields ： 更多地應(yīng)用于非數(shù)值處理； Processed data ： 更多地處理非數(shù)值型數(shù)據(jù) The relationship among data ：數(shù)據(jù)結(jié)構(gòu)發(fā)展到面向?qū)ο箅A段 類和數(shù)據(jù)結(jié)構(gòu)之間的對應(yīng)關(guān)系： History 類 ?屬性 ?方法 數(shù)據(jù)結(jié)構(gòu) ?數(shù)據(jù)之間的關(guān)系 ?基本操作 對應(yīng) ? 數(shù)據(jù)結(jié)構(gòu)的發(fā)展并未終結(jié) Research Objects of DS ? steps for solving problems with puter : A problem→ Abstract a problem model→ Find out the solution of this model ? Problem—— Numerical problem and nonnumerical problem Numerical problem → Mathematical Equation nonnumerical problem → DS Known length and wide of a swimming pool, then find out area of the pool. ◆ Build a model 問題涉及的 對象 ： length, wide and area. 對象之間的 關(guān)系 : area=len?wide ◆ Design the method of solving the problem ◆ programming example ?一、 Numerical Problems and nonnumerical problem Numerical problem include void main() { int len,wide,area。PASCAL之父，結(jié)構(gòu)化程序設(shè)計的首創(chuàng)者，獲得 1984年圖靈獎。 常見的數(shù)據(jù)結(jié)構(gòu)有：表 (linear list) 、 數(shù)組 (array)、串 (string)、棧 (stack)、 隊列