軟件工程第四章 軟件設計.ppt

1、軟件工程,第4講 軟件設計,第4講 軟件設計,4.1 軟件設計的任務、過程和原則 4.2 軟件設計的基本概念和原理 4.3 面向數(shù)據(jù)流的結(jié)構(gòu)化設計方法 4.4 數(shù)據(jù)設計 4.5 用戶界面設計 4.6 軟件過程設計 4.7 軟件設計文檔的內(nèi)容及其復審的方法,4.1 軟件設計的任務、過程和原則,軟件設計的任務 分析、理解軟件需求規(guī)格說明書（SRS），并將其轉(zhuǎn)化為實際軟件系統(tǒng)的一個模型或軟件表示，即用于構(gòu)造軟件的“藍圖”。 形成必要的設計文檔，包括：軟件概要設計說明書，軟件詳細設計說明書，數(shù)據(jù)庫設計說明書 軟件設計的主要內(nèi)容 主要包括：數(shù)據(jù)設計、體系結(jié)構(gòu)設計、接口設計、過程設計等4個部分。,數(shù)據(jù)設計

2、 將實體關系圖中描述的對象和關系，以及數(shù)據(jù)詞典中描述的詳細數(shù)據(jù)內(nèi)容轉(zhuǎn)化為數(shù)據(jù)結(jié)構(gòu)的定義。 體系結(jié)構(gòu)設計 定義軟件系統(tǒng)各主要模塊的功能及其之間的關系。 接口設計 根據(jù)數(shù)據(jù)流圖定義軟件內(nèi)部各成份之間、軟件與其它協(xié)同系統(tǒng)之間及軟件與用戶之間的交互機制。 過程設計 把結(jié)構(gòu)成分轉(zhuǎn)換成軟件的過程性描述。在編碼時，根據(jù)這種過程性描述，生成源程序代碼，然后通過測試最終得到完整有效的軟件。,軟件設計與軟件需求之間的關系：,軟件設計可細分為兩個階段,概要設計：確定程序各主要部件之間的關系，給出能反映系統(tǒng)功能、數(shù)據(jù)、行為需求的軟件的總的框架。 詳細設計：對此框架中每一部件進行過程化描述，把它刻畫為在細節(jié)上非常接近于

3、源程序的軟件表示。,例如：機器人控制系統(tǒng),為何要重視軟件設計, 因為它與軟件質(zhì)量和用戶需求息息相關，用戶所有的需求都必須通過精心的設計來滿足。 比如，如果信息安全是對用戶的關鍵需求，那么體系結(jié)構(gòu)設計時就應該采用分層結(jié)構(gòu)，將重要資源放在內(nèi)層，并在每層采用嚴格的安全性驗證。 如果可用性是一個關鍵需求，則需要考慮冗余的體系結(jié)構(gòu)設計，以便在無須系統(tǒng)停止的情況下更新或替換組件。 設計是所有后續(xù)工作的指南，編碼實現(xiàn)必須以設計為前提和基礎。,4.2 軟件設計的基本概念和原理,1）模塊化 模塊化就是將大型軟件按照規(guī)定的原則劃分解成一個個較小的、相對獨立的但又相互關聯(lián)的模塊的設計方法。 將系統(tǒng)分解成模塊、對象和

4、構(gòu)件等組成部分。在傳統(tǒng)的軟件工程中用分解來實現(xiàn)模塊化設計；在OO軟件工程中，靠分解來劃分類和對象。,C(P1+P2) C(P1)+C(P2) E(P1+P2) E(P1)+E(P2),模塊分解的程度 模塊的分解不能太多也不能太少。,2）抽象 解決問題時只考慮與問題有關的方面，不考慮與問題無關的方面。即抽出事物的本質(zhì)特性而不考慮細節(jié)。,3）信息隱藏 模塊內(nèi)部的數(shù)據(jù)與過程(操作)，應該對不需要了解這些數(shù)據(jù)和過程（操作）的模塊隱藏起來。 信息隱藏的目的 提高模塊的獨立性，減少把一個模塊的錯誤擴散到其他模塊中去的機會。 信息隱藏的例子 全局變量：任何函數(shù)都可以訪問。 堆棧： 通過函數(shù)Push（）、Po

5、p（）、Clear() 操作棧 其他函數(shù)并需要、也不知道棧的具體情況。,4）軟件復用 軟件復用是指在兩次或多次不同的軟件開發(fā)過程中重復使用相同或相似軟件元素的過程。 構(gòu)件(component)可以復用的軟件成分，可被用來構(gòu)造其他軟件。它可以是： 被封裝的對象類 功能模塊 軟件架構(gòu)（或體系結(jié)構(gòu)Architecture） 設計模式等,5）模塊獨立性 模塊獨立性的度量：內(nèi)聚度和耦合度 內(nèi)聚：指模塊內(nèi)部各個成分之間的聯(lián)系。也稱：塊內(nèi)聯(lián)系、模塊強度。 耦合：指一個模塊與其它模塊之間的聯(lián)系。也稱塊間聯(lián)系。 模塊獨立性的度量準則： 塊內(nèi)聯(lián)系程度越強、塊間聯(lián)系程度越弱，則模塊的獨立性越高。 模塊獨立性強的模塊

6、的優(yōu)點 降低復雜性，便于并行開發(fā)和實現(xiàn) 容易測試和維護,（1）內(nèi)聚的分類,從功能的角度來看模塊內(nèi)部的聚合程度，可以按照由弱到強的順序，把內(nèi)聚分為7類。,低內(nèi)聚,中內(nèi)聚,高內(nèi)聚,偶然 邏輯 時間 過程 通信 順序 功能,偶然性內(nèi)聚模塊：即無任何聯(lián)系。 塊內(nèi)各組成成分在功能上是互不相關的。 例如，“記錄人員信息”和“產(chǎn)生公司財務報表”構(gòu)成了一個模塊。 邏輯性內(nèi)聚模塊：即有某種類型聯(lián)系。 通常由若干邏輯功能相似的成分組成,每次調(diào)用由傳給模塊的參數(shù)確定執(zhí)行哪種功能。 時間性內(nèi)聚模塊：即從時間方面看有聯(lián)系。 這類模塊所包含的成分在一個固定的時間點執(zhí)行。 例如，一個初始化模塊中的“為變量賦初值”、“打開文

7、件”等。,過程化內(nèi)聚模塊：即一組任務有次序的聯(lián)系。 一個模塊中包含的一組任務必須按照某一特定的次序執(zhí)行。 例如， “讀入爐溫”-“記錄爐溫”-“比較溫度”-“計算閥門開度”-“驅(qū)動閥門”等。 通信性內(nèi)聚模塊：即數(shù)據(jù)結(jié)構(gòu)的區(qū)域聯(lián)系。 模塊內(nèi)部的各個組成部分都引用一組相同的數(shù)據(jù)。 如下圖的例子：,順序性內(nèi)聚模塊：即有輸入/輸出的緊密聯(lián)系。 模塊中各組成部分密切相關且必須順序執(zhí)行，前一處理部分的輸出就是下一處理部分的輸入。 例如，排序程序：“讀如一組整型數(shù)”-“對這組數(shù)從小到大排序”-“將排序后的這組數(shù)輸出”。 功能性內(nèi)聚模塊：內(nèi)聚性最強。即有功能的緊密聯(lián)系。 一個模塊中各個部分都是為完成一項具體功

8、能而協(xié)同工作，緊密聯(lián)系，不可分割的. 例如，求一元二次方程ax2+bx+c=0的實根。 Root( a,b,c,X1,X2)： 計算b2-4ac；sqrt(b2-4ac)； X1=(-b+sqrt(b2-4ac)/2a；X2=(-b-sqrt(b2-4ac)/2a,設計時對模塊內(nèi)聚性的選擇,“一個模塊，一個功能”是模塊化設計的一條準則，也是設計人員爭取的目標。 功能性內(nèi)聚模塊是最理想的。 中、高內(nèi)聚的模塊也可使用。 低內(nèi)聚模塊的可維護性和可復用性差，設計時應盡量避免使用。,（2）耦合的分類,模塊間的引用方式，數(shù)據(jù)量，數(shù)據(jù)格式，數(shù)據(jù)類型都對耦合的強度產(chǎn)生影響 按照影響程度耦合可分為7類，如下圖所

9、示。,非直接 數(shù)據(jù) 特征 控制 外部 公共 內(nèi)容,數(shù)據(jù)耦合 模塊間通過參數(shù)表交換數(shù)據(jù)，且交換的都是數(shù)據(jù)項參數(shù)（而不是控制參數(shù)、公共數(shù)據(jù)結(jié)構(gòu)或外部變量）。 數(shù)據(jù)耦合是松散的耦合，模塊之間的獨立性比較強。,非直接耦合 兩個模塊之間沒有直接關系，相互之間沒有信息傳遞，它們之間的聯(lián)系完全是通過主模塊的控制和調(diào)用來實現(xiàn)的。 這種耦合的耦合度最低，模塊獨立性最強。,特征耦合(也稱標記耦合)： 如果2個以上的模塊都需要共享某一數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)時，不能用全局變量的共享方式，而是采用記錄傳遞方式。 例如，A調(diào)用B，向B傳遞某個人的記錄（而B可能只需要記錄中的幾個數(shù)據(jù)項）。,控制耦合： 模塊間傳遞的是用作控制信號

10、的開關值或標志。 這種耦合的實質(zhì)是在單一接口上選擇多功能模塊中的某項功能。因此，對被控制模塊的任何修改，都會影響控制模塊。這也意味著控制模塊必須知道被控制模塊內(nèi)部的一些邏輯關系，這些都會降低模塊的獨立性。,外部耦合： 允許一組模塊訪問同一個全局變量（單域變量）。 例如，C中的extern。 問題：當max的值發(fā)生錯誤時，是哪個函數(shù)造成的？,#define MAXLINE 1000 char line MAXLINE; char save MAXLINE; int max; main() int len; extern int max,line; extern int save; ,getlin

11、e() int c,j; extern char line; Copy() int j; extern char line,save; ,公共耦合 一組模塊都訪問同一個公共數(shù)據(jù)結(jié)構(gòu)。 公共的數(shù)據(jù)結(jié)構(gòu)可以是全局數(shù)據(jù)結(jié)構(gòu)、共享的通信區(qū)、內(nèi)存的公共覆蓋區(qū)等。 公共耦合的復雜程度隨耦合模塊的個數(shù)增加而顯著增加。只有在模塊之間共享的數(shù)據(jù)很多，且通過參數(shù)表傳遞不方便時，才使用公共耦合。, 內(nèi)容耦合 (1)一模塊直接訪問另一模塊的內(nèi)部數(shù)據(jù) (2)一模塊不通過正常入口轉(zhuǎn)到另一模塊內(nèi) (3)兩模塊有一部分代碼重疊 (4)一模塊有多個入口,一模塊直接訪問 另一模塊的內(nèi)部 信息 (程序代碼 或數(shù)據(jù)）,A,B,A,B

12、,模塊代碼重疊,Entry1 Entry1 ,多入口模塊,設計時對模塊耦合度的選擇,耦合越弱，則模塊的獨立性越強，因此應盡量使用耦合度低的設計。 但實際開發(fā)軟件系統(tǒng)時，中等或較強耦合是不可避免的，也不需要禁止使用。 最強耦合度的內(nèi)容耦合，會給維護工作帶來很大的困難，應該不用。,4.3 概要設計方法結(jié)構(gòu)化設計方法,4.3.1 概要設計 概要設計應該包括兩方面內(nèi)容： （）產(chǎn)生一個模塊化的程序結(jié)構(gòu)，并明確各模塊之間的控制關系, 亦稱為系統(tǒng)結(jié)構(gòu); （）說明每個程序模塊的輸入輸出數(shù)據(jù)結(jié)構(gòu)。,軟件設計從需求定義開始,逐步分層導出系統(tǒng)結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu),當需求定義中所述的每個部分最終都能由一個或幾個軟件元素實現(xiàn)

13、時,整個求解過程即告結(jié)束。,例如：機器人控制系統(tǒng),依據(jù)不同軟件設計方法總能推導出一個軟件結(jié)構(gòu),對于同一問題的各種軟件結(jié)構(gòu),4.3.2 面向數(shù)據(jù)流的結(jié)構(gòu)化設計方法,結(jié)構(gòu)化設計方法(SD)是以數(shù)據(jù)流圖為基礎的，它定義了把數(shù)據(jù)流圖變換成軟件系統(tǒng)結(jié)構(gòu)的映射方法，所以這種方法也稱為面向數(shù)據(jù)流的設計方法。 (1)主要任務,映射 DFD 軟件系統(tǒng)的結(jié)構(gòu) (軟件系統(tǒng) (軟件的 邏輯模型) 初始結(jié)構(gòu)描述),(2) SD方法的設計過程,步1：鑒別DFD圖所表示的軟件系統(tǒng)的結(jié)構(gòu)特征，確定它所代表的軟件結(jié)構(gòu)是屬于變換型還是事務型； 步2：劃分流界，按照SD方法規(guī)定的規(guī)則，把DFD圖轉(zhuǎn)換為初始的SC圖；,步3. 根據(jù)設

14、計優(yōu)化的指導原則改進初始SC圖，生成最終的SC圖。,(3) 數(shù)據(jù)流圖的兩種類型,變換型數(shù)據(jù)流圖,變換 中心,輸入 路徑,輸出 路徑,(3) 數(shù)據(jù)流圖的兩種類型,事務型數(shù)據(jù)流圖,輸入邊界,輸出邊界,(4)軟件結(jié)構(gòu)表示,4.1）層次圖（HC）,模塊：用矩形表示 模塊間的調(diào)用關系：用帶箭頭的連線表示 數(shù)據(jù)流：在調(diào)用關系線的旁邊用命名的箭頭表示 選擇調(diào)用： 循環(huán)調(diào)用：,4.2）軟件結(jié)構(gòu)圖（SC),(5)變換分析方法,5.1）劃分邊界,5.2）第一級分解(建立初始SC框架),5.3）第二級分解(建立每個分支的下級模型),傳入分支的分解,傳出分支的分解,加工中心的分解,(6)事務分析方法,6.1)在DFD

15、上確定事務中心、接收部分和發(fā)送部分。 6.2)畫出SC框架，把DFD上的三部分分別映射為事務控制模塊、接收模塊和動作發(fā)送模塊。 6.3)分解細化接收分支和發(fā)送分支，完成初始SC。,(7)結(jié)構(gòu)設計案例：用戶命令交互子系統(tǒng),事務型設計,變換型設計(1),變換型設計(2),(8) 軟件結(jié)構(gòu)設計優(yōu)化,保持高扇入/低扇出； 模塊的作用范圍應在其控制范圍之內(nèi)； 模塊的控制范圍(Scope of Effect) ：由它本身及其所有的從屬模塊。 模塊的作用范圍(Scope of Control)：由此模塊的某些決定而影響的所有模塊所組成。 可預測性：一個模塊應該是可預測的； 輸入恒定，輸出則恒定，即“黑箱”概

16、念。 有必要的錯誤處理,高扇入/低扇出：上層高扇出，下層高扇入,模塊的控制范圍與其作用范圍,模塊F的控制范圍: F、G、H、I,模塊F的作用范圍: B,錯誤處理示例,一種語言機制 模塊： 正常處理部分; ; 當錯誤條件發(fā)生 啟動例外處理過程; 例外處理過程 ; 例如，S ybase T-SQL Trigger Code,/* Insert trigger ti_store_account_history for table STORE_ACCOUNT_HISTORY */create trigger ti_store_account_history on STORE_ACCOUNT_HISTO

17、RY for insert asbegin declare numrows int,numnull int, errno int,errmsg varchar(255) select numrows = rowcount if numrows = 0 return /* Parent STORE_ACCOUNT must exist when inserting a child in STORE_ACCOUNT_HISTORY */ if update(GOODSID) begin if (select count(*) from STORE_ACCOUNT t1, inserted t2 w

18、here t1.GOODSID = t2.GOODSID) != numrows begin select errno = 30002, errmsg = Parent does not exist in STORE_ACCOUNT. Cannot create child in STORE_ACCOUNT_HISTORY. goto error end end return/* Errors handling */error: raiserror errno errmsg rollback transactionend,又例，MRP/ERP軟件中入/出庫處理 入庫模塊的一種處理方式： 錄入產(chǎn)

19、品項目編號; 在產(chǎn)品清單中查找該產(chǎn)品項目編號； 如果存在 則 記入入庫明細帳中； 更新庫存總帳； 否則 按照該錯誤條件（編號） 查找錯誤信息表并獲取信息； 啟動例外處理過程; 例外處理過程 給用戶顯示錯誤信息； 返回錄入界面; ,錯誤信息表,窗口的形狀、位置、大小 文字的字體、大小、顏色,（1）數(shù)據(jù)庫設計 概念設計 ER模型/EER模型 邏輯設計設計階段的任務 把ER模型/EER模型轉(zhuǎn)換成關系模型，用SQL表示 物理設計 借助于RDBMS的有關功能進行。 （2）數(shù)據(jù)結(jié)構(gòu)設計,4.4 數(shù)據(jù)設計,數(shù)據(jù)庫設計科借助于工具來完成 把ER模型/EER模型轉(zhuǎn)換成關系模型，用SQL表示,/*= */ /*

20、Database name: SMSTORE_1 */ /* DBMS name: Sybase System 11 */ /* Created on: 2/25/2005 12:41 AM */ /* = */ /* Table: SUPPLIER */ create table SUPPLIER ( SUPPLIERID char(10) not null, SUPPLIERNAME varchar(40) null , JURISTICPERSON char(10) null , JURISTICPERSONRP char(10) null , IFSIGN bit null , SIG

21、NDATE datetime null , TEL varchar(30) null , ADDR varchar(60) null , TAXNO varchar(20) null , BANKNAME varchar(40) null , ACCOUNTS char(1) null constraint CKC_ACCOUNTS_SUPPLIER check (ACCOUNTS in (1,0), FAX varchar(20) null , constraint PK_SUPPLIER primary key (SUPPLIERID),數(shù)據(jù)結(jié)構(gòu)設計示例： 設計一種好的數(shù)據(jù)結(jié)構(gòu)，便于根據(jù)該

22、結(jié)構(gòu)能快速查找中文的任意“詞語”,4.5 接口設計,（1）用戶界面設計的指導原則 分析用戶類型 應用程序和界面分離 一致性 盡量減少用戶記憶和工作量 可恢復性 出錯處理和幫助功能 增加可視化圖形表示,4.5.1 用戶界面設計,系統(tǒng)內(nèi)部模塊接口、系統(tǒng)外部接口、人機界面,用戶界面設計范例,（2）用戶界面設計過程,用戶、任務和環(huán)境分析及建模 用戶類型通常分為：外行型、初學型、熟練型、專家型。 用戶特性度量與用戶使用模式和用戶群體能力有關。包括：用戶使用頻度、用戶用機能力、用戶的知識、思維能力等。 界面設計 界面構(gòu)造 界面確認,界面設計層次化任務分析HTA,層次任務分析HTA是用一種結(jié)構(gòu)化的方法來分析

23、并描述用戶如何為達到目標所進行的一系列任務，以及用戶與軟件系統(tǒng)是如何交互的。 通過層級分析將任務不斷拆解，逐級細化用戶的任務，直至用戶實際的具體操作。隨著任務的細化，我們對用戶和產(chǎn)品的理解會越來越清晰。 例如：通過用戶的任務分析，來設計一個網(wǎng)上書店,對“挑選圖書”任務進行分解,繼續(xù)對“搜索圖書”細化,界面構(gòu)造基于visio實現(xiàn),1）過程設計的主要任務 過程設計就是在概要設計階段的基礎上，對各個模塊給出確定采用的算法和模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)，用某種表達工具給出清晰的過程描述。具體的任務有： 確定各個模塊的算法；確定各個模塊使用的數(shù)據(jù)結(jié)構(gòu)；確定各個模塊接口的細節(jié)； 編寫詳細設計說明書； 2）過程設計的目

24、的 為編碼階段的工作提供足夠的依據(jù)，使其能夠根據(jù)過程描述，快速地、幾乎是機械地完成編碼任務，同時也為測試工作打下基礎。,4.6 軟件過程設計,3）過程設計的基本原則 （1）運用結(jié)構(gòu)化程序設計的思想 （2）遵循一些規(guī)則 使用三種基本結(jié)構(gòu) 單入口/單出口 限制GOTO 使用統(tǒng)一的描述工具，如 FC 程序流程圖 NS 盒圖 PAD 問題分析圖 PDL 程序設計語言,3）描述工具 FC程序流程圖,NS 盒圖 由Nassi和Shneiderman提出，因此而得名。,PAD 問題分析圖 由Nassi和Shneiderman提出。,PDL 程序設計語言 PDL是一種用于描述功能模塊的算法設計和加工細節(jié)的語言

25、，也稱偽碼(pseudo code)。 外層語法：符合一般程序設計語言常用語句的較嚴格的關鍵字語法規(guī)則，用于定義控制結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)。 內(nèi)層語法：可以用英語中一些簡單的句子、短語和通用的數(shù)學符號，來描述程序應執(zhí)行的功能。,IF- THEN- ELSE- ENDIF DO-WHILE- ENDDO REPEAT-UNTIL- ENDREP CASE-OF- WHEN-CONDITION-SELECT- ENDCASE DECLARE AS STRING ARG AS ARRAY ARG,例 某系統(tǒng)主控模塊的處理流程用PDL描述如下： PROCEDURE MAIN( ) 清屏； 顯示xx系統(tǒng)用戶界面

26、； 接收用戶輸入口令； IF 輸入口令系統(tǒng)保存的口令 提示警告信息； 退出系統(tǒng)； ENDIF WHILE (.T.) 顯示系統(tǒng)主菜單； ABC=接收用戶選擇； IF ABC = 退出 退出本循環(huán); ENDIF 調(diào)用相應的下層模塊完成用戶選擇的功能; ENDWHILE 清屏； RETURN END,例 某系統(tǒng)主控模塊的處理流程用FC描述如下：,例 模塊binary(x,v,n,p)完成判斷一個特定值x是否出現(xiàn)在已經(jīng)按遞增順序排好序的數(shù)組v中。如果存在則返回相應下標mid ，否則返回值-1。,Y,例 逐步求精方法示例：騎士周游問題。給出一塊有n2個格子的棋盤。一位騎士放在初始坐標為（x0,y0）的

27、格子里，然后按照國際象棋的規(guī)則移動。問題是找到一種可以走遍整個棋盤的方案（如果這種方案存在），即計算一個n2-1次移動的周游，使得棋盤上每一個格子恰好被走過（訪問過）一次。 (1)數(shù)據(jù)結(jié)構(gòu)設計： 棋盤：用一個二維整型數(shù)組hi,j,I=1.n,j=1.n 馬的移動位置：有8個可走位置。馬的初始位置為(x,y),下一個移動位置(x+ak,y+bk)，其中k=1.8。,X,0,棋盤格子h x,y是否被訪問過，可以用下面的方式記錄：,0表示格子 x,y未被訪問過 i 表示格子 x,y在第i次移動中被訪問過,1=i=n2,h x,y =,(2)算法設計：試探+回溯 步1：初始化； 步2：對給定的馬的當前

28、位置 調(diào)用“試探下步移動”； 步3：if 下步移動成功 then 步3.1： 打印移動結(jié)果； else 步3.2： 打印無解 endif,步1的“初始化”工作可以細化為： 1.1馬的8個可移動位置的差值分別按照前面表格中的值預先放在a、b數(shù)組中； 1.2 棋盤在馬未訪問過時應該都預先放入0； 1.3 馬的最初位置可以是（1 ,1）；此時該位置所確定的棋盤格子認為被訪問過,因此應有h 1,1 =1。,(2)算法設計：試探+回溯 步1：初始化； 步2：對給定的馬的當前位置 調(diào)用“試探下步移動”； 步3：if 下步移動成功 then 步3.1： 打印移動結(jié)果； else 步3.2： 打印無解。 en

29、dif,對于馬的當前位置的下步移動應該有8個候選位置用K計數(shù)，候選次序是前面圖示中的逆時針方向進行。一旦進入下一步即一個新的位置，同樣又要“試探下步移動”。如果本步移動成功，那么返回“真”，否則返回“假”。因此是一個遞歸過程try(i,x,y,q) 。,“試探下步移動”可設為try(i,x,y,q) ： 2.0 做候選準備； 2.1 repeat 2.1.1 從下一步移動表中挑選出下一步候選者; 2.1.2 if 候選者可接受 then 進行移動； endif 2.2 until 移動成功或再無候選者； 2.3 返回移動成功與否的標志.,馬在當前位置而且在下步移動前，一個位置都沒有試探過，因此

30、k值應為0。8個候選位置試探完畢時k值應為8。,“試探下步移動”還需要細化： 2.0 做候選準備； 2.1 repeat 2.1.1 從下一步移動表中挑選出下一步候選者 2.1.2 如果候選者可接受，則 2.1.2.1 進行移動； 2.2 until 移動成功或再無候選者; 2.3 返回移動成功與否的標志.,如果候選者的當前步為k，則候選者的下一步變?yōu)閗+1。,那么，下一步的候選者“可接受”的條件應該是：u,v不能越界而且該步所處位置未被訪問過，可表示為(1=u=n） and （1=v=n） and （hu,v=0）,2.1.2.1“進行移動”可以進一步細化為： 記錄移動; if 盤未走遍 t

31、hen “試探下步移動”即為遞歸調(diào)用步2； if “試探下步移動”不成功 then刪去這一記錄即回溯； else 用局部變量q1表示并賦true; endif endif,設挑出的下一步候選者為（u,v),則 u可用x+ak,v可用y+bk表示。,“移動成功”可把ture賦予局部變量q1; “再無候選者”意味著當前馬的位置的下一步已經(jīng)對可能的8個位置都試完了,因此可表示為k=8。,移動成功與否可把變量q1的值賦予變量q,2.1.2.1“進行移動”還需要細化： 記錄移動; if 盤未走遍 then “試探下步移動”即為遞歸調(diào)用步2； if “試探下步移動”不成功 then刪去這一記錄； else

32、 給q1賦值true; endif endif,“記錄移動”可以表示為： hu,v被賦予當前所試探的次數(shù)i。i是一個全局變量,“盤未走遍”可以表示為： in2,“試探下步移動”應該是一個遞歸調(diào)用，可以表示為： try(i+1,x,y,q1),“試探下步移動不成功”可以表示為：NOT q1,“刪去這一記錄”可以表示為： hu,v被賦予0,(2)算法設計：試探+回溯 步1：初始化； 步2：對給定的馬的當前位置 調(diào)用“試探下步移動”； 步3：if 下步移動成功 then 步3.1： 打印移動結(jié)果； else 步3.2： 打印無解。 endif,步3中對“下步移動成功”的判斷可以對步2中“試探下步移動

33、”即過程try(i,x,y,q)調(diào)用結(jié)果的返回值q作判斷即可： q為true即為移動成功， q為false即為移動失敗。,步3.1“打印移動結(jié)果”即輸出數(shù)組hi,j 的各元素之值。其中i,j 的取值為1到n；,步3.2“打印無解”即是輸出一個提示信息。,(2)算法設計的最后描述 步1：定義全局變量并初始化 PRAGRAM KNIGHTSTOUR DECLARE n:as integer; q:as boolean; GET(n); DO-WHILE i=n DO-WHILE j=n hi,j=0; j=j+1; ENDDO i=i+1; ENDDO; a1=2; b1=1; a2=1; b2=

34、2; a3=-1;b3=2; a4=-2;b4=1; a5=-2;b5=-1;a6=-1;b6=-2; a7=1; b7=-2;a8=2; b8=-1;,步2和步3 ： h1,1=1; try(2,1,1,q) ;/調(diào)用過程try( i,x,y,q) 見后 IF q THEN DO-WHILE i=n DO-WHILE j=n PUT(hi,j); j=j+1; ENDDO 換行； i=i+1; ENDDO ELSE PUT（ “打印無解”）； ENDIF END PROG,PROCEDURE try(i,x,y,q) DECLARE i,x,y:as integer ARG; q:as bo

35、olean ARG;,k=0; REPEAT UNTIL k=8 or q1 k=k+1;q1= FALSE; u=x+ak;v=y+bk; IF (1un)and (1vn) and (hu,v=0) THEN try(i+1,u,v,q1) ； IF NOTq1 THEN hu,v=0 ELSE q1= TRUE; ENDIF ENDIF ENDREP q= q1; ENDPROC,處理編號：3（簡單庫存管理系統(tǒng)SMSTORE的一個處理描述） 處理名稱：辦理出庫 接受的輸入：出庫單 產(chǎn)生的輸出：倉庫中無此貨物，庫存不夠 讀取的文件：貨物清單 寫或修改的文件：出庫明細帳，庫存帳 處理過程：

36、1）接受出庫單； 2）根據(jù)出庫單的基本信息，檢查該出庫單所列貨物是否在倉庫貨物清單中存在 如果不存在，則 對出庫員給出倉庫中無此貨物信息，結(jié)束處理。 3）根據(jù)出庫單的基本信息，檢查該出庫單所列貨物的數(shù)量在庫存帳中是否夠 如果不夠，則 對出庫員給出庫存不夠信息，結(jié)束處理。 否則 把出庫單的基本信息寫入出庫明細帳； 根據(jù)出庫單的基本信息修改庫存帳中的庫存量。 結(jié)束處理。 激發(fā)條件：當出庫員收到出庫單并進行登記時。,例 信息處理流程圖示例,開始,結(jié)束,根據(jù)設定的出庫單界面錄入各項數(shù)據(jù)： OUTSTOREID、GOODSID、 SUPPLIERID、OUTDATE、 OUTPERSON、MANAGER、 QUANTITY、CLIENTNAME,根據(jù)錄入的出庫單中各貨物的 GOODSID 檢查“貨物清單” GOODSLIST中是否存在,GOODSLIST,存在？,“倉庫中 無此貨物,根據(jù)出庫單中各GOODSID的數(shù)量檢查“庫存帳” STORE_ACCOUNT中的庫存量QUANTITY是否夠. QUANTITY= STORE_ACCOUNT.EARLY_QUANTITY+ STORE_ACCOUNT.CURRENT_IN_QUANTITY- STORE_ACCOUNT.CURRENT_OUT_QUANTITY,S