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

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

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

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

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

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

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

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

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

9、,三種基本的元素框分支,P成立？,是,否,A,B,信息科學(xué)與工程學(xué)院,程序構(gòu)造的基本方法,25,2. 數(shù)據(jù)處理方法算法,三種基本的元素框循環(huán),C,當(dāng)P成立,C,當(dāng)P成立,信息科學(xué)與工程學(xué)院,程序構(gòu)造的基本方法,26,2. 數(shù)據(jù)處理方法算法,例3-2：判斷一個(gè)正整數(shù)是否是素?cái)?shù),輸入：正整數(shù)N,W0, I2,RN/I的余數(shù),R=0?,II+1,W=0?,直到IN-1或W=1,W1,N是素?cái)?shù),N不是素?cái)?shù),T,F,T,F,信息科學(xué)與工程學(xué)院,程序構(gòu)造的基本方法,27,2. 數(shù)據(jù)處理方法算法,常用算法 排序 查找 遞歸 回溯,信息科學(xué)與工程學(xué)院,程序構(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ù)集中選擇最大的，降序,信息科學(xué)與工程學(xué)院,程序構(gòu)造的基本方法,29,2. 數(shù)據(jù)處理方法算法,冒泡排序 每遍從最后一個(gè)數(shù)據(jù)開始進(jìn)行兩兩比較并將小的排在大的前面（交換兩數(shù)據(jù)），直到要冒出的位置 第一遍需要比較n - 1次冒出所有數(shù)據(jù)中的最小的，冒出位置是1 第二遍需要比較n - 2次冒出剩余數(shù)據(jù)

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

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