數(shù)據(jù)結構 北航軟件技術基礎課程ppt

1、軟件技術基礎軟件技術基礎教材：教材：數(shù)據(jù)結構教程，遲樂軍等編著，北京航空航天大學出版社，數(shù)據(jù)結構教程，遲樂軍等編著，北京航空航天大學出版社，2003.4軟件技術基礎軟件技術基礎 王人驊王人驊 唐梓榮唐梓榮 北京航空航天大學出版社北京航空航天大學出版社參考資料：參考資料：數(shù)據(jù)結構與算法分析，數(shù)據(jù)結構與算法分析，美美Clifford A. Shaffer著，電著，電子工業(yè)出版社，子工業(yè)出版社，2001.2 權威著作：權威著作：The Art of Computer Programming(計算機程序設計技巧計算機程序設計技巧),其中其中的第一卷、第三卷的第一卷、第三卷軟件技術基礎軟件技術基礎要求的

2、基礎：要求的基礎：學習并掌握了一門高級語言，最好完成過一定數(shù)量的程學習并掌握了一門高級語言，最好完成過一定數(shù)量的程序序目標：目標：提高程序設計的分析能與實際動手能力，掌握一定的數(shù)提高程序設計的分析能與實際動手能力，掌握一定的數(shù)據(jù)處理方法據(jù)處理方法理解軟件設計與開發(fā)的基本概念理解軟件設計與開發(fā)的基本概念 聯(lián)系方法：聯(lián)系方法：姓名：高連生姓名：高連生 電話：電話：82317246Q：525573325eMail: liansheng_軟件技術基礎軟件技術基礎第零章第零章 編程的一些問題編程的一些問題第一章第一章 緒緒論論第二章第二章 線線 性性 表表第三章第三章 棧和隊列

3、棧和隊列第四章第四章 串和數(shù)組串和數(shù)組第五章第五章 二叉樹和樹二叉樹和樹第六章第六章 圖和廣義表圖和廣義表第七章第七章 排排序序第八章第八章 查查找找第九章第九章 文文件件適 合 于 軟 件 的 開 發(fā) 與 設 計 程 序包括：程序，軟件開發(fā)的步驟-軟件工程，程序設計的思維方法，結構化程序設計，O-O程序設計數(shù)據(jù)結構包括：線性表，鏈表，棧，隊列，樹，圖等軟件技術基礎軟件技術基礎學習方法學習方法講練結合講練結合作業(yè)：至少完成作業(yè)：至少完成6次作業(yè)次作業(yè)(每次每次布置作業(yè)后一周后上交，兩周布置作業(yè)后一周后上交，兩周截止日期，過期減少分數(shù)截止日期，過期減少分數(shù)-最最后一次除外后一次除外)結業(yè)方法結業(yè)

4、方法作業(yè)：作業(yè)：30%,考試考試70%1.考試占考試占100%數(shù)據(jù)結構在程序設計中是非常實用的一門技術，是前人程序設計的結晶，希望大家能掌握這門技術，為研究工作奠定基礎。第零章第零章 程序設計的一些問題程序設計的一些問題程序與軟件？程序程序是最終達到一定目的指令序列。例如課程表，會議程序，開學注冊程序計算機程序計算機程序：計算機指令的序列，實現(xiàn)預期的目的。軟件軟件狹義：軟件=程序，除了硬件都是軟件廣義：軟件程序軟件是一種抽象的、邏輯性的產品，它不僅是在計算機上運行的程序,還包括開發(fā)、使用和維護程序所需要的文檔。軟件可以減輕勞動，提高工作效率，是計算機工作的延伸。第零章第零章 程序設計的一些問題

5、程序設計的一些問題軟件和屬性計算機運行中不可缺少的預先編好，能為他人使用商品盤和軟件盤是軟件的載體軟件的分類應用軟件系統(tǒng)軟件第零章第零章 程序設計的一些問題程序設計的一些問題程序設計的幾個階段(軟件工程簡介)六、七十年代出現(xiàn)了軟件危機軟件開發(fā)周期長軟件開發(fā)費用大軟件的正確性差軟件的可靠性差工程化的方法-軟件工程據(jù)估計，將軟件生產由手工方式轉變?yōu)楣こ袒绞剑浖煽啃詫⑻岣?0%，測試和維護成本大大降低。速度：8行/天-20多行/天第零章第零章 程序設計的一些問題程序設計的一些問題需求分析-Requirement Analysis概要設計-Primary Design詳細設計-Detailed

6、Design編碼調試-Coding & Debug測試-Testing運行與維護-Maintenance評評審審（標準：國標，軍標，DOD標準）第零章第零章 程序設計的一些問題程序設計的一些問題需求分析-Requirement Analysis概要設計-Primary Design詳細設計-Detailed Design編碼調試-Coding & Debug測試-Testing運行與維護-Maintenance綜述：說明問題，明確軟件的功能，明確做什么，建立數(shù)據(jù)流圖，數(shù)據(jù)字典任務：確定軟件開發(fā)的主要任務功能：確定主要功能輸入/處理/輸出(IPO)性能：確定主要性能，速度，響應時

7、間，數(shù)據(jù)轉換/傳輸時間，數(shù)據(jù)刷新時間接口：與外設，與軟件，與人的界面產生：需求規(guī)格說明書，數(shù)據(jù)流程圖，數(shù)據(jù)字典（標準：國標，軍標，DOD標準）第零章第零章 程序設計的一些問題程序設計的一些問題需求分析-Requirement Analysis概要設計-Primary Design詳細設計-Detailed Design編碼調試-Coding & Debug測試-Testing運行與維護-Maintenance設計：如何解決問題，可能的解決方案，數(shù)據(jù)的處理方式，存貯方式，模塊的劃分、調用關系參考：與系統(tǒng)相關的資料，需求規(guī)格說明書，程序設計手冊，設備技術手冊，支持軟件文檔第零章第零章 程序

8、設計的一些問題程序設計的一些問題需求分析-Requirement Analysis概要設計-Primary Design詳細設計-Detailed Design編碼調試-Coding & Debug測試-Testing運行與維護-Maintenance綜述：設計程序的基本流程，組織結構，輸入輸出，接口設計及數(shù)據(jù)結構設計任務：1概要結構設計程序結構，給出程序的分層結構2功能劃分分程序與模塊的功能3程序的控制流程和數(shù)據(jù)流4系統(tǒng)間接口，與其他系統(tǒng)的接口5內部接口6算法上列舉可能的求解算法產生：概要設計說明，用戶手冊第零章第零章 程序設計的一些問題程序設計的一些問題需求分析-Requireme

9、nt Analysis概要設計-Primary Design詳細設計-Detailed Design編碼調試-Coding & Debug測試-Testing運行與維護-Maintenance綜述：對模塊進行過程描述，設計模塊內部細節(jié)。任務：1結構設計：模塊細化，形成程序單元2資源分析及余量大于20%的余量3參數(shù)化：設計參數(shù)，增加軟件的柔性4算法的具體化產生：詳細設計說明書第零章第零章 程序設計的一些問題程序設計的一些問題需求分析-Requirement Analysis概要設計-Primary Design詳細設計-Detailed Design編碼調試-Coding & D

10、ebug測試-Testing運行與維護-Maintenance綜述：根據(jù)詳細設計說明書，編程實現(xiàn)，并進行調試編程標準：語言結構化，編程格式縮進等，控制結構語言結構化，編程格式縮進等，控制結構三種控制結構，插入或復制程序時要完整從入三種控制結構，插入或復制程序時要完整從入口入，出口出，出口入，出口出，出/ /入口結構唯一，禁止自修改，入口結構唯一，禁止自修改，程序單元的規(guī)模程序單元的規(guī)模200200行，程序中平均單元行，程序中平均單元的長的長6060行，注意轉移，重定位能力，行，注意轉移，重定位能力，命名統(tǒng)一，數(shù)值約定一致，有效數(shù)字，命名統(tǒng)一，數(shù)值約定一致，有效數(shù)字，注釋行注釋行20%20%調試

11、后要進行單元測試，先逐步審查代碼，后測試，通過測試用例保證每條源代碼至少執(zhí)行一次第零章第零章 程序設計的一些問題程序設計的一些問題需求分析-Requirement Analysis概要設計-Primary Design詳細設計-Detailed Design編碼調試-Coding & Debug測試-Testing運行與維護-Maintenance綜述：由專門的測試人員對軟件進行測試結果：測試報告1 1測試計劃測試計劃2 2測試測試條件：編譯、鏈接成功，完成單元測試，walkthrough測試：模塊測試：單元問題聯(lián)合測試：接口問題系統(tǒng)測試：系統(tǒng)問題正確的依據(jù)：每條語句執(zhí)行一次，每個通道

12、執(zhí)行一次，每個功能正確第零章第零章 程序設計的一些問題程序設計的一些問題需求分析-Requirement Analysis概要設計-Primary Design詳細設計-Detailed Design編碼調試-Coding & Debug測試-Testing運行與維護-Maintenance綜述：記錄運行狀況，為下一版本升級奠定基礎第零章第零章 程序設計的一些問題程序設計的一些問題問題的解決周期：需求36%，設計5%，編碼與調試7%，測試15%，運行維護67%工作量費用：需求5%，設計10%，編碼調試8%，測試12%，運行維護65%費用可靠性與正確性：步步為營，測試統(tǒng)計數(shù)據(jù)錯誤：60%

13、發(fā)生在設計階段，36%發(fā)生在編碼階段糾正錯誤的費用：編制程序的費用為1，則說明階段的費用為0.5，測試階段的費用為25，運行階段的費用為10組織結構：七人小組軟件生命周期的概念第零章第零章 程序設計的一些問題程序設計的一些問題討論軟件工程強調開始定型，以后不變，這在實際工作中會有問題嗎？快速原型法Prototyping軟件工程還是快速原型？第零章第零章 程序設計的思維方法程序設計的思維方法程序設計的本質是實現(xiàn)算法，而算法是計算機解決問題精確描述，有如下特征：入口出口有窮次結束序列化后繼唯一抽象法：變量的應用，樹的處理枚舉法：歸納法：例如求自然數(shù)的和公式回朔法：走迷宮子問題法：Hanio塔問題，

14、二叉樹的遍歷反對教條化第零章第零章 如何評價程序如何評價程序正確性：讓它干等于程序干的嗎？，在不同的環(huán)境下的魯棒性。驗證方法：枚舉法，歸納法，抽象法，證明時空性：時間越少，空間越小越好時間和空間的定義時空的矛盾解決時間的關鍵是算法，解決空間的關鍵是數(shù)據(jù)結構發(fā)展趨勢易讀性-自己讀，別人讀，結構清晰，易讀易理解，人機界面好，注釋語句通用性好可靠性，可移植性-傳統(tǒng)的程序方法上：抽象思維，模塊化第零章第零章 程序設計方法程序設計方法結構化程序設計方法1968年Dijkstra提出結構化程序設計，主要思想：自上而下，逐步求精-功能結構分層結構與模塊結構的程序設計-系統(tǒng)結構，先全局后局部，保證塊間不構成圈

15、，塊獨立，塊的層次分明避免GOTO-控制結構采用三種結構主程序員-組織結構GOTO語句的討論1966年證明三種結構可以表達所需要的程序結構。使用GOTO出現(xiàn)的問題- 程序結構復雜化，閱讀時的靜態(tài)與運行中的動態(tài)不統(tǒng)一，無結構形式討論 *運算是不是一種GOTO？第零章第零章 程序設計方法程序設計方法自頂向下，逐步求精寫作文的方式在以后的學習中大量用到第一章第一章 緒緒論論1.1 什么是數(shù)據(jù)結構？煤氣管道鋪設問題煤氣管道鋪設問題ABCDE218163212405020數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中，計算機的操作對象以及它們之間的關系和操作的學科。第一章第一章 緒緒論論1.2 基本概念與

16、術語數(shù)據(jù)數(shù)據(jù)學號姓名語文數(shù)學C語言6201001張三8554926201002李四9284646201003王五8774736201004.例例1：學生成績：學生成績例例2：聲音、圖象：聲音、圖象數(shù)據(jù)是信息的載體，是對客觀事物的符號表示，它被計算機所識別、存儲和加工，構成計算機程序的加工原料。 數(shù)據(jù)元素數(shù)據(jù)元素 數(shù)據(jù)元素是數(shù)據(jù)的基本單位。數(shù)據(jù)元素是數(shù)據(jù)的基本單位。 它也可以再由不可分割的數(shù)據(jù)項組成它也可以再由不可分割的數(shù)據(jù)項組成 數(shù)據(jù)對象數(shù)據(jù)對象性質相同的數(shù)據(jù)元素的集合性質相同的數(shù)據(jù)元素的集合 。 例：一個班級的成績表可以看作一個數(shù)據(jù)對象。例：一個班級的成績表可以看作一個數(shù)據(jù)對象。 一個圖片、

17、聲音一個圖片、聲音.數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素集合。 數(shù)據(jù)元素集合（也可稱數(shù)據(jù)對象）數(shù)據(jù)元素集合（也可稱數(shù)據(jù)對象） 各元素之間的關系，即結構。各元素之間的關系，即結構。數(shù)據(jù)結構數(shù)據(jù)結構從三個方面研究數(shù)據(jù)結構：從三個方面研究數(shù)據(jù)結構：邏輯結構邏輯結構存儲結構存儲結構 算法算法數(shù)據(jù)結構 = 數(shù)據(jù) + 結構 數(shù)據(jù)元素之間具有的邏輯關系數(shù)據(jù)元素之間具有的邏輯關系(結構結構)。線性關系線性關系( (線性結構線性結構) )： 數(shù)據(jù)元素間為嚴格的一對一關系。 樹形結構樹形結構 ： 數(shù)據(jù)元素間為嚴格的一對多關系。邏輯結構邏輯結構圖狀結構（或網狀結構）圖狀結構（或網狀結構）： 數(shù)據(jù)元素間為多對多關系 非非 線

18、線 性性 結結 構構具有某種邏輯結構的數(shù)據(jù)在計算機存具有某種邏輯結構的數(shù)據(jù)在計算機存儲器中的存儲方式。儲器中的存儲方式。順序存儲：順序存儲：用一組地址任意的用一組地址任意的存儲單元依次存放數(shù)據(jù)元素，存儲單元依次存放數(shù)據(jù)元素，鏈式存儲：鏈式存儲：數(shù)據(jù)元素之間的邏數(shù)據(jù)元素之間的邏輯關系通過指針間接地反映。輯關系通過指針間接地反映。存儲結構存儲結構存儲結構是數(shù)據(jù)結構在計算機中的表示，也稱之為物理結構。計算機內存的模型030003010302030303040305邏輯結構：邏輯結構： 線性結構線性結構 (線性表線性表)a1a2a3 a30d1 d2 d3 d4 d30a2a1a3a4a30存儲結構存

19、儲結構:1. 順序存儲結構順序存儲結構:學號姓名語文數(shù)學C語言6201001張三8554926201002李四9284646201003王五8774736201004.例：例：2. 鏈式存儲結構鏈式存儲結構:d1 d2 d3 d4 a1a2a3a30lista2a1a4a3d4d1d5d3 算法算法數(shù)據(jù)的數(shù)據(jù)的處理方法（算法）處理方法（算法）查找：數(shù)學成績前三名的同學查找：數(shù)學成績前三名的同學學號姓名語文數(shù)學C語言6201001張三8554926201002李四9284646201003王五8774736201004.例例：添加：來了一個新同學添加：來了一個新同學 1. 研究數(shù)據(jù)元素之間的客觀

20、聯(lián)系研究數(shù)據(jù)元素之間的客觀聯(lián)系。 2. 研究具有某種邏輯關系的數(shù)據(jù)在計算機存儲研究具有某種邏輯關系的數(shù)據(jù)在計算機存儲 器內的存儲方式。器內的存儲方式。 3. 研究如何在數(shù)據(jù)的各種結構研究如何在數(shù)據(jù)的各種結構(邏輯的和物理的邏輯的和物理的) 的基礎上對數(shù)據(jù)實施一系列有效的基本操作。的基礎上對數(shù)據(jù)實施一系列有效的基本操作。 數(shù)據(jù)結構課程研究的主要內容數(shù)據(jù)結構課程研究的主要內容(算法算法)(邏輯結構邏輯結構)(存儲結構存儲結構)為什么研究數(shù)據(jù)結構 1.4 算法及其描述算法及其描述輸入輸入 一個完整的算法應該滿足下面五個基本標準：一個完整的算法應該滿足下面五個基本標準： 有效性有效性 確定性確定性有窮

21、性有窮性輸出輸出一一. 算法及其性質算法及其性質 (2). 算法算法是指令的有限序列，其中每一條指令表示一是指令的有限序列，其中每一條指令表示一 個或多個操作個或多個操作 。1. .算法的定義算法的定義2. .算法的性質算法的性質 (1). 算法算法是對特定問題求解步驟的一種描述。是對特定問題求解步驟的一種描述。二二. 算法的描述算法的描述 (1) M除以除以N，將余數(shù)送中間變量將余數(shù)送中間變量R； (2) 測試余數(shù)測試余數(shù)R是否等于零？是否等于零？ a) 若若R等于零，求得的最大公因子為當前等于零，求得的最大公因子為當前N 的值的值, 算法到此結束。算法到此結束。 b) 若若R不等于零，將不

22、等于零，將N送入送入M，將將R送送N，重重 復算法的復算法的(1)和和(2)。1. 采用自然語言來描述采用自然語言來描述問題：問題：求兩個正整數(shù)求兩個正整數(shù)M與與N的最大公因子。的最大公因子。2. 采用程序流程圖的形式來描述采用程序流程圖的形式來描述M除以N的余數(shù)送R余數(shù)R為0否？將N送M將R送N輸出輸出N的值的值結束開始yesnoCOMFACTOR( int M, int N ) int R; while( 1 ) R=M % N; if (R=0) return N; M=N; N=R; 3. 采用某種具體程序語言來描述采用某種具體程序語言來描述 4. 設計一種既脫離某種具體的程序設計語言

23、，設計一種既脫離某種具體的程序設計語言， 又具有各種程序設計語言的共同特點的形又具有各種程序設計語言的共同特點的形 式化語言來描述式化語言來描述類類 C C 語言語言 一一. 算法格式算法格式函數(shù)類型函數(shù)類型 函數(shù)名（形式參數(shù)及其說明）函數(shù)名（形式參數(shù)及其說明） 內部參數(shù)說明；內部參數(shù)說明； 語句序列；語句序列； 1.3 類類 C 語言簡介語言簡介二二. 語句語句1. 賦值語句：賦值語句： (1) if 條件表達式條件表達式 語句串；語句串； (2) if 條件表達式條件表達式 語句串語句串1； else 語句串語句串2； 變量名變量名 =表達式表達式 2. . 條件語句條件語句( (兩種兩種

24、) )3. 循環(huán)語句循環(huán)語句(三種三種) do 語句串；語句串； while(循環(huán)條件循環(huán)條件) for (賦初值表達式；條件表達式；修改表達式賦初值表達式；條件表達式；修改表達式) 語句串語句串; while (循環(huán)條件循環(huán)條件) 語句串；語句串； switch(表達式表達式) case 判定值判定值1：語句串：語句串1； break; case 判定值判定值2：語句串：語句串2； break; . . . . case 判定值判定值n：語句串語句串n； default ： 語句串語句串n+1; break; 4. 情況語句情況語句 1、 /* 注釋內容注釋內容 */ 2、/ 1、字符：函數(shù)

25、、字符：函數(shù)getchar()、 putchar()實現(xiàn)實現(xiàn) 2、其他數(shù)據(jù)：函數(shù)、其他數(shù)據(jù)：函數(shù)scanf() 、printf()實現(xiàn)表實現(xiàn)表) 5. 輸入輸入/輸出語句輸出語句 6. 注釋注釋求兩個求兩個n階矩陣的乘積：階矩陣的乘積：MATRIX( int A ,int B ,int C ,int n ) for (i=1 ; i=n; i+) for ( j=1; j=n; j+ ) Ci, j=0; for ( k=1; k=n; k+ ) Ci, j=Ci, j+Ai, k*Bk, j; 例例 1.5 算法分析算法分析 1、正確性、正確性2、可讀性、可讀性3、健壯性、健壯性4、效率與低

26、存儲量需求、效率與低存儲量需求 效率效率指的是算法執(zhí)行時間。指的是算法執(zhí)行時間。 存儲量存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。需求指算法執(zhí)行過程中所需要的最大存儲空間。 兩者都與問題的規(guī)模有關。兩者都與問題的規(guī)模有關。是指對算法質量優(yōu)劣的評價。是指對算法質量優(yōu)劣的評價。 3其他方面。如算法的可讀性、可移植性以其他方面。如算法的可讀性、可移植性以 及易測試性的好壞。及易測試性的好壞。 2依據(jù)算法編寫的程序在計算機中占存儲空依據(jù)算法編寫的程序在計算機中占存儲空 間多少的度量，稱之為間多少的度量，稱之為空間復雜度空間復雜度。 1依據(jù)算法編寫的程序在計算機中運行時間依據(jù)算法編寫的程序在計算機中運行時間 多少的度量，稱之為多少的度量，稱之為時間復雜度時間復雜度。 除正確性外，應從三個方面分析一個算法：除正確性外，應從三個方面分析一個算法：算法分析算法分析一一. 時間復