程序構(gòu)造的基本方法.ppt

1、程序設計與算法語言大學計算機知識基礎(chǔ),程序構(gòu)造的基本方法,信息科學與工程學院,程序構(gòu)造的基本方法,2,上講回顧,計算機中數(shù)據(jù)的表示 進位計數(shù)制 基數(shù) 位權(quán) 機器數(shù)怎樣用二進制表示負數(shù)并正確運算 原碼、補碼、反碼、移碼 小數(shù)點的表示 定點 浮點 非數(shù)值數(shù)據(jù)的編碼 漢字編碼 布爾代數(shù),信息科學與工程學院,程序構(gòu)造的基本方法,3,程序構(gòu)造的基本方法,1. 數(shù)據(jù)組織 2. 數(shù)據(jù)處理 數(shù)據(jù)的組織與數(shù)據(jù)的處理相互影響,信息科學與工程學院,程序構(gòu)造的基本方法,4,1. 數(shù)據(jù)組織,兩大類型 內(nèi)存數(shù)據(jù)組織：存放于內(nèi)部存儲器中的數(shù)據(jù)，數(shù)量相對較小 外存數(shù)據(jù)組織：存放于內(nèi)部（一小部分）和外部（絕大部分）存儲器中的數(shù)

2、據(jù)，數(shù)量相對較大，需要專用數(shù)據(jù)管理系統(tǒng)來協(xié)調(diào)數(shù)據(jù)的交換 文件系統(tǒng) 數(shù)據(jù)庫系統(tǒng),信息科學與工程學院,程序構(gòu)造的基本方法,5,1. 數(shù)據(jù)組織,邏輯組織：一種抽象的描述，只涉及數(shù)據(jù)之間的組織關(guān)系。其組織方法 1. 簡單 2. 線性 3. 層次 4. 網(wǎng)狀 5. 外存 物理組織：一種具體的組織形態(tài),信息科學與工程學院,程序構(gòu)造的基本方法,6,1. 數(shù)據(jù)組織,簡單數(shù)據(jù)組織方法 用于相互之間沒有太強關(guān)系的少量數(shù)據(jù) 對每一個數(shù)據(jù)都取一個名稱，代表存放數(shù)據(jù)的空間,x,y,k,l,z,信息科學與工程學院,程序構(gòu)造的基本方法,7,1. 數(shù)據(jù)組織,線性數(shù)據(jù)組織方法 用于同類的批量數(shù)據(jù)，即“向量”，例如 一時間段對內(nèi)

3、某一事物的觀測數(shù)據(jù)x1, x2, , xn-1, xn 一個班級全體學生學號 整批數(shù)據(jù)共享一個名稱，而其中每一個具體數(shù)據(jù)通過賦予各自的一個序號給出,x1,x2,x3,x4,x5,x6,x7,x8,x9,信息科學與工程學院,程序構(gòu)造的基本方法,8,1. 數(shù)據(jù)組織,線性數(shù)據(jù)組織方法 具體實現(xiàn)（物理組織）方式 連續(xù)： 將這組數(shù)據(jù)存放在計算機內(nèi)存中某個連續(xù)區(qū)域，因此可根據(jù)其對應的序號直接計算出每一個數(shù)據(jù)存儲的具體區(qū)域，例如：數(shù)組 非連續(xù)：將這組數(shù)據(jù)分散存放在計算機內(nèi)存中，需一個聯(lián)系每一個數(shù)據(jù)存儲位置的附加區(qū)域，將后面一個數(shù)據(jù)存儲位置登記到前面一個數(shù)據(jù)的附加區(qū)域，例如：單向鏈表,信息科學與工程學院,程序

4、構(gòu)造的基本方法,9,1. 數(shù)據(jù)組織,線性數(shù)據(jù)組織鏈表（linked table，空間換時間）,信息科學與工程學院,程序構(gòu)造的基本方法,10,1. 數(shù)據(jù)組織,線性數(shù)據(jù)組織在鏈表中插入元素,2060,2030,X,信息科學與工程學院,程序構(gòu)造的基本方法,11,1. 數(shù)據(jù)組織,線性數(shù)據(jù)組織在鏈表中刪除元素,X,X,2030,信息科學與工程學院,程序構(gòu)造的基本方法,12,1. 數(shù)據(jù)組織,線性數(shù)據(jù)組織棧（stack，先進后出） First In Last Out（FILO） 壓棧（push） 出棧（pop） 數(shù)據(jù)操作特點 只能在同一端（棧頂）進行 每次涉及一個數(shù)據(jù),棧底,棧頂,入棧,出棧,信息科學與工程

5、學院,程序構(gòu)造的基本方法,13,1. 數(shù)據(jù)組織,線性數(shù)據(jù)組織隊列（queue，先進先出） First In First Out（FIFO） 進隊（push） 出隊（pop） 數(shù)據(jù)操作特點 在不同端進行插入和刪除操作 每次涉及一個數(shù)據(jù),隊尾,隊頭,進隊,出隊,信息科學與工程學院,程序構(gòu)造的基本方法,14,1. 數(shù)據(jù)組織,層次數(shù)據(jù)組織方法樹（tree） 節(jié)點 根 枝 葉子 從根到葉子的一條路經(jīng)上的所有節(jié)點構(gòu)成一個線性關(guān)系 整個數(shù)型結(jié)構(gòu)由多個線性關(guān)系疊加構(gòu)成,Root,L,R,LL,RL,RLL,RR,LRR,信息科學與工程學院,程序構(gòu)造的基本方法,15,1. 數(shù)據(jù)組織,網(wǎng)狀數(shù)據(jù)組織方法圖（grap

6、h） 允許任意兩個數(shù)據(jù)之間都可存在關(guān)系 使用一個矩陣定義數(shù)據(jù)之間的關(guān)系 使用線性復合的方式表達網(wǎng)狀數(shù)據(jù)組織 可定義數(shù)據(jù)之間的順序關(guān)系 可定義數(shù)據(jù)之間的關(guān)系代價,A,B,D,E,C,信息科學與工程學院,程序構(gòu)造的基本方法,16,1. 數(shù)據(jù)組織,外存數(shù)據(jù)組織方法（大容量數(shù)據(jù)組織）文件（file） 建立（create） 使用 打開（open） 讀/寫（read/write） 關(guān)閉（close） 刪除（delete） 移動（move）,信息科學與工程學院,程序構(gòu)造的基本方法,17,2. 數(shù)據(jù)處理方法算法,定義：一個有窮的指令集，規(guī)定一個運算序列 特點 有零或多個輸入（事先得到的） 有一或多個輸出 確定

7、性：每一步都應確切和無歧義定義 有窮性 有效性 算法與數(shù)據(jù)組織密切相關(guān)，是在某種數(shù)據(jù)組織結(jié)構(gòu)上的一種解決問題的計算方法,信息科學與工程學院,程序構(gòu)造的基本方法,18,2. 數(shù)據(jù)處理方法算法,衡量算法的標準用相對量級表示 時間 空間,信息科學與工程學院,程序構(gòu)造的基本方法,19,2. 數(shù)據(jù)處理方法算法,1. 算法描述 算法是抽象的，但必須通過具象的方式來展示。形式 語言：自然語言、類計算機語言、計算機語言 圖形： 流程圖、N-S圖、PAD 圖 表格 2. 常用算法,信息科學與工程學院,程序構(gòu)造的基本方法,20,2. 數(shù)據(jù)處理方法算法,用流程圖表示基本邏輯控制規(guī)則,處理,順序,單分支,雙分支,信息

8、科學與工程學院,程序構(gòu)造的基本方法,21,2. 數(shù)據(jù)處理方法算法,用流程圖表示基本邏輯控制規(guī)則,循環(huán)（先判斷）,循環(huán)（后判斷）,信息科學與工程學院,程序構(gòu)造的基本方法,22,2. 數(shù)據(jù)處理方法算法,算法描述的圖形方式N-S圖 由Ike Nassi和Ben Shneiderman提出 一種結(jié)構(gòu)化的流程圖 通過一個矩形框表達一個對數(shù)據(jù)的基本處理 三種基本的元素框：順序、分支、循環(huán) 通過三種元素框的任意邏輯組合（框的嵌套）來表達算法,信息科學與工程學院,程序構(gòu)造的基本方法,23,2. 數(shù)據(jù)處理方法算法,三種基本的元素框順序,A,B,信息科學與工程學院,程序構(gòu)造的基本方法,24,2. 數(shù)據(jù)處理方法算法

9、,三種基本的元素框分支,P成立？,是,否,A,B,信息科學與工程學院,程序構(gòu)造的基本方法,25,2. 數(shù)據(jù)處理方法算法,三種基本的元素框循環(huán),C,當P成立,C,當P成立,信息科學與工程學院,程序構(gòu)造的基本方法,26,2. 數(shù)據(jù)處理方法算法,例3-2：判斷一個正整數(shù)是否是素數(shù),輸入：正整數(shù)N,W0, I2,RN/I的余數(shù),R=0?,II+1,W=0?,直到IN-1或W=1,W1,N是素數(shù),N不是素數(shù),T,F,T,F,信息科學與工程學院,程序構(gòu)造的基本方法,27,2. 數(shù)據(jù)處理方法算法,常用算法 排序 查找 遞歸 回溯,信息科學與工程學院,程序構(gòu)造的基本方法,28,2. 數(shù)據(jù)處理方法算法,排序（s

10、orting）：一組數(shù)據(jù)有序化的過程 由小到大排列稱為升序（ascent sorting） 由大到小排列稱為降序（descent sorting） 類型（用于線性數(shù)據(jù)組織） 冒泡：將比較小的數(shù)據(jù)（泡泡）向前擠，升序；將比較大的數(shù)據(jù)（泡泡）向前擠，降序 選擇：從未排序的數(shù)據(jù)集中選擇最小的，升序；從未排序的數(shù)據(jù)集中選擇最大的，降序,信息科學與工程學院,程序構(gòu)造的基本方法,29,2. 數(shù)據(jù)處理方法算法,冒泡排序 每遍從最后一個數(shù)據(jù)開始進行兩兩比較并將小的排在大的前面（交換兩數(shù)據(jù)），直到要冒出的位置 第一遍需要比較n - 1次冒出所有數(shù)據(jù)中的最小的，冒出位置是1 第二遍需要比較n - 2次冒出剩余數(shù)據(jù)

11、中的最小的（第二小的） ，冒出位置是2 以此類推，共進行n - 1遍（最后第n遍不需要進行）,信息科學與工程學院,程序構(gòu)造的基本方法,30,信息科學與工程學院,程序構(gòu)造的基本方法,31,信息科學與工程學院,程序構(gòu)造的基本方法,32,2. 數(shù)據(jù)處理方法算法,選擇排序 每遍首先確定要選擇的位置，再從未排序數(shù)據(jù)中找出最小的并與選擇位置處的數(shù)據(jù)交換 第一遍需要比較n - 1次得到所有數(shù)據(jù)中的最小的，選擇位置是1 第二遍需要比較n - 2次得到剩余數(shù)據(jù)中的最小的（第二小的），選擇位置是2 以此類推，共進行n - 1遍（最后第n遍不需要進行）,信息科學與工程學院,程序構(gòu)造的基本方法,33,信息科學與工程學

12、院,程序構(gòu)造的基本方法,34,2. 數(shù)據(jù)處理方法算法,查找（search）：從一組數(shù)據(jù)中找出所需數(shù)據(jù)的過程 直接（用于線性數(shù)據(jù)組織） ：逐一地與需查找的數(shù)據(jù)比較 二叉樹（用于樹型數(shù)據(jù)組織） 二叉搜索（排序）樹：任意一結(jié)點的左子樹的所有結(jié)點的數(shù)據(jù)都小于該結(jié)點數(shù)據(jù)，反之則大于 從樹根開始與需查找的數(shù)據(jù)比較，大則向左，小則向右，直到樹葉 動態(tài)查找需在查不到時將需查找數(shù)據(jù)插入,信息科學與工程學院,程序構(gòu)造的基本方法,35,2. 數(shù)據(jù)處理方法算法,遞歸（recursion）：通過概念定義概念本身 一種特殊的循環(huán)，在循環(huán)體內(nèi)重復循環(huán) 特征 “自引用”規(guī)則 終止條件 本質(zhì) 分解：向終止條件逼近 綜合：從終止條件返回 分解與綜合互為逆過程 形式：單遞歸、多遞歸、嵌套遞歸,信息科學與工