大學計算機基礎算法與數據結構基礎.ppt

算法與數據結構基礎,算法,算法是解題方案的準確而完整的描述。具有可行性，確定性，有窮性，有足夠的情報輸入與輸出。 算法要素：數據的運算和操作+控制結構； 運算與操作：算術，邏輯，關系，數據傳輸（賦值，輸入，輸出等）； 控制結構：順序，選擇，循環(huán)；,算法的常見描述方法: 自然語言方式 偽代碼方式 程序流程圖方式 N/S盒圖方式,算法描述-偽代碼,介于自然語言和程序語言之間的一種描述方法，與具體編程語言無關。 Keep track of current number of resources in use If another resource is available Allocate a dialog box structure If a dialog box structure could be allocated Note that one more resource is in use Initialize the resource Store the resource number at the location provided by the caller Endif Endif Return TRUE if a new resource was created; else return FALSE,算法描述-程序流程圖,算法由若干張流程圖描述，每張流程圖由結點和有向邊構成，該圖描述了算法中所進行的操作以及這些操作執(zhí)行的邏輯順序。 流程圖的常用結點及控制結構描述如下 ：,算法描述- N/S盒圖方式,算法設計基本方法,列舉法 歸納法 遞推法 遞歸法 回溯法,列舉法,設每只母雞值3元，每只公雞值2元，每只小雞值0.5元。現要用100元錢買100只雞，設計買雞方案。,遞推法,假定一對剛出生的小兔子，一個月后就能長成大兔子，再過一個月后就開始生小兔子，并且也正好生一對兔子。問在沒有兔子死亡的情況下，一對初生的兔子一年后可繁殖成多少對兔子。,算法的復雜度,空間復雜度：占用的存儲空間大小 時間復雜度：編譯時間+運行時間 (1) a=b; /O(1)-時間復雜度為常數值 (2) for(int i=0;in;i+) a=b; /O(n)-時間復雜度為一階值 (3) for(int i=0;in;i+) for(int j=0;jn;j+) a=b; /O(n2)-時間復雜度為二階值,數據結構的基本概念,數據：數據是信息的載體，是能夠輸入到計算機中，并被計算機識別、存儲和處理的符號的集合。 數據元素：數據處理中具有獨立意義的個體。元素可能是數也有可能是記錄。 數據結構：數據結構是指組成數據的元素之間的結構關系（線性結構，樹形結構）。 邏輯結構：數據的邏輯結構（如線性結構和非線性，如樹形結構）。 物理結構：數據的存儲結構（線性存貯，鏈式存貯）。,邏輯結構線性結構（線性表）,一個線性表是n個數據元素的有限序列。 其存儲空間是連續(xù)的，各個數據元素在存儲空間是按邏輯順序依次存放的。只有一個跟結點，每個結點只有一個前后件。 限定性的線性表結構： 棧：后進先出（進入和刪除都在一端） 隊列：先進先出（進入在尾部和刪除在頭部）,線性和鏈式存貯結構,線性存儲結構具有簡單、操作方便、占用空間少的優(yōu)點，但做插入和刪除時需要移動大量的元素，并且需要足夠大的成塊的內存。 鏈式存儲結構：每個存儲節(jié)點由兩部分構成，一部分用于存放數據，一部分用于存放指針（記錄前一個或后一個節(jié)點的地址）。用一個專門的指針（稱為頭指針）指向第一個數據節(jié)點。,1) 單向鏈結構 2) 雙向鏈結構 3) 多向鏈結構,非線性結構樹與二叉樹,數據元素具有層次關系，并以分支關系定義了層次結構。 父結點（結點的前驅結點），子結點（結點的后繼結點），根結點（無前驅結點的結點），葉子結點（無后繼結點的結點）。 結點所擁有的子樹的棵樹被稱為度。,二叉樹基本性質,二叉樹：只有一個跟結點，每個結點度最大為2 性質1 二叉樹第i層上的結點數目最多為2i-1(i1)。 性質2 深度為m的二叉樹至多有2m-1個結點(k1)。 證明：在具有相同深度的二叉樹中，僅當每一層都含有最大結點數時，其樹中結點數最多。因此利用性質1可得，深度為k的二叉樹的結點數至多為： 20+21+2k-1=2k-1 故命題正確。,性質3 在任意-棵二叉樹中，若度為零的結點為n0，度為2的結點數為n2，則no=n2+1。,特殊形態(tài)二叉樹,滿二叉樹：深度為m且有2m-1個結點的二叉樹。即每一層的所有結點數都達到最大值。 完全二叉樹：除最后一層外，每一層結點數都達到最大值；在最后一層只缺少右邊的若干結點。,二叉樹的遍歷,首先訪問根結點為前序，先左再根再右為中序，先左再右再根為后序 前序：A B D C E F 中序：D B A E C F 后序：D B E F C A,查找技術,順序查找：無序表，采用鏈式存儲結構的有序線性表。 折半查找：有序表（需要排序）。 最壞情況下順序查找需要比較m次，折半查找需要log2m次。,1.5 程序設計基礎,程序設計的重要性,程序是計算機的一組指令，是程序設計的最終結果。 程序經過編譯和執(zhí)行才能最終完成程序的功能。 高級程序設計語言的出現使得程序設計不僅是計算機專業(yè)人員必備知識，也是各行各業(yè)專業(yè)技術人員必須掌握的技術。,程序設計方法與風格,程序設計應該簡單清晰，為了測試和維護應該遵循“清晰第一，效率第二”的風格。 注意以下因素： 源程序文檔化（符號命名規(guī)律，程序注釋，視覺組織） 數據說明便于理解和維護（次序規(guī)范便于查找） 語句結構簡單直接（一行一句，避免使用零時變量，模塊功能應單一，不用無條件轉移，不良程序應重新編寫） 輸入輸出方便并能進行合理性檢查（輸入輸出數據合法性，合理檢查，輸入數據應盡可能少，人機會話界面）,兩種程序設計方法,結構化程序設計 程序=數據結構+算法 面向對象程序設計 程序 = 對象 + 消息,1、結構化程序設計,結構化程序設計：Structured Programming 基本原則： 采用自頂向下，逐步求精的方法：先考慮總體，后考慮細節(jié)；先考慮全局目標，后考慮局部目標，逐步使得問題具體化。 模塊化：每一個小問題構成一個模塊，模塊只有一個入口和出口，一個功能。 禁用無條件轉移（GOTO）,好結構的程序具有結構清晰，容易閱讀，容易理解，容易驗證，容易維護的特點。 可以證明采用三種結構可以表達出各種其它復雜形式的程序結構。 三種結構：順序，選擇，循環(huán),2、面向對象的程序設計,面向對象：Object Oriented 對象即客觀世界中的實體，客觀世界中的實體都具有靜態(tài)的屬性和動態(tài)的行為。 程序設計中的對象：在編程中將實體表示成一組表示其靜態(tài)特征的“屬性”（property）和它可執(zhí)行的一組操作組成即“方法”（method）。 屬性即對象所包含的信息，用來描述對象的狀態(tài)。 操作（方法）描述了對象的行為，操作的過程對外界來說是不可見的，是封裝到對象中的，用戶只能看到結果，或者調用這個操作。,對象實際是對數據和專屬操作的封裝，是更高級的封裝形式。 對象的基本特點：標識唯一性，分類性（抽象成類），多態(tài)性，封裝性。 類是對象的抽象，是具有共同屬性、共同方法的對象的集合。描述了對象類中所有對象的性質和行為。對象則是對應類中的實例。,類（class）和實例（Instance）,類和實例（Class，Instance）,二維圖形,直線,圓形,方形,三角形,R= 3cm 4cm 5cm Color= red blue green,實例,消息（Message）,消息是一個實例與另一個實例之間傳遞的信息。 封裝的對象通過“消息”完成合作與信息傳遞。 “消息”是面向對象世界的協(xié)作機制。 消息的傳遞：“消息”包括接收消息的實例，操作名和參數表（數據流和控制流），接收“消息”的實例會因此產生一系列的操作。 特點：發(fā)送者只提要求，接收者完全獨立的處理。傳輸消息可以1對多也可以多對1。,繼承（Inheritance）,繼承是使用已定義的類作為基礎建立新類（派生類）的定義技術。 面向對象軟件技術的優(yōu)點在于可以把類組成一個層次結構系統(tǒng)，子類繼承了父類的數據和操作。 采用繼承可以節(jié)省大量的重復工作，提高軟件可重用性，便于維護和管理。,二維圖形 CGdiObject,CPen,CCircle,CRect,CTri,r= 3cm 4cm 5cm,實例,CPen筆，畫線 CBrush刷子，填充 CFont字體，控制文字輸出的字體 CBitmap位圖 CPalette調色板 CRgn區(qū)域，指定一塊區(qū)域可以用于做特殊處理。 CFile文件。最重要的不外是Open（打開）,Read（讀入）,Write（寫） CString字符串。封裝了C中的字符數組，非常實用。 CPoint點，就是（x,y）對 CRect矩形，就是（left,top,right,bottom）,多態(tài)性（Polymorphism）,多態(tài)性是指用一個名字定義不同的函數，這函數執(zhí)行不同但又類似的操作，從而實現“一個接口，多種方法”。 通過在基類中定義虛方法(virtual)，在子類中，可以通過override進行派生重寫。 這樣增加了面向對象編程的靈活性（有繼承有變革）。,面向對象方法的特點,與人類思維方法一致 穩(wěn)定性好 可重用性好 易于開發(fā)大型軟件 可維護性好,MFC(Microsoft Foundation Classes),MFC是對WindowsAPI的封裝，大大簡化了我們的工作；學VC主要就是要學MFC. MFC大約有100多個類，但常用的也就二三十個。 CWnd：窗口，它是大多數“看得見的東西”的父類 CDocument文檔，負責內存數據與磁盤的交互 CView視圖，負責內存數據與用戶的交互。包括數據的顯示、用戶操作的響應（如菜單的選取、鼠標的響應） CWinApp應用程序類。似于C中的main函數，是程序執(zhí)行的入口和管理者，負責程序建立、消滅，主窗口和文檔模板的建立,軟件工程基礎,軟件開發(fā)的演化過程,個人編程時代（46年50年代末） 軟件開發(fā)是科學家們根據各自的應用需要寫出的能夠解決預定問題的運行程序。程序生產的效率極低，可靠性難以保證，且僅限于處理比較簡單的數值計算問題 軟件作坊時代(60年代初一60年代未) 軟件作坊的開發(fā)方法是個體的或小組的思維行為，使得軟件任務延誤、質量不可靠、甚至無法維護，極大地制約了計算機以后)的功能發(fā)揮和實際應用。 軟件工程時代(70年代-) 在世界范圍內出現了許多組織嚴密、管理科學、手段先進、工具齊全的軟件開發(fā)公司，為計算機軟件市場提供了大量成功的軟件產品。80年代，明確提出了“軟件工程支撐環(huán)境”的思想，使程序設計可以直接從支撐環(huán)境中調用所需的各個“組件”。,軟件工程基本概念,計算機軟件的數量迅速增加，軟件規(guī)模不斷增加，投入的人力資金十分巨大，成本不斷上升。如何保證軟件開發(fā)的速度和質量成為一個十分嚴重的問題，必須采用軟件工程的思想和方法解決。 對軟件開發(fā)成本和進度的估算很不準確 質量很不可靠 沒有適當的文檔 軟件成本比重上升 速度慢：軟件開發(fā)生產率跟不上計算機應用迅速深入的趨勢,100%,0%,1955,1970,1985,硬件/軟件成本變化趨勢,原因 客觀：軟件本身特點 邏輯部件 規(guī)模龐大 主觀：不正確的開發(fā)方法 忽視需求分析 錯誤認為：軟件開發(fā)=程序編寫 輕視軟件維護,軟件定義： 軟件=程序+數據+文檔 程序：按事先設計的功能和性能需求執(zhí)行的指令序列 數據：是程序能正常操縱信息的數據結構 文檔：與程序開發(fā)、維護和使用有關的圖文材料,軟件工程,軟件工程: 借鑒從事工程項目所積累的原理、概念、技術和方法來開發(fā)和維護軟件，把正確的管理和科學的技術結合起來，這就是軟件工程。 軟件工程=開發(fā)技術+工程管理 軟件開發(fā)技術 軟件開發(fā)方法學，軟件開發(fā)工具，軟件開發(fā)環(huán)境 軟件工程管理 軟件管理學 軟件經濟學 軟件心理學,軟件生存周期模型,軟件產品從形成概念開始，經過開發(fā)、使用和不斷增補修正，直到最后被淘汰的整個過程。按照軟件工程的思想，這個過程又可劃分成若干個互相區(qū)別而又有聯系的階段。,軟件生命周期,瀑布式生存周期模型,（1）可行性研究與計劃階段 明確“要做什么”及“是否能做” （2）需求分析階段 弄清“必須做什么” （3）設計階段 “如何做”和“如何具體做” （4）實現階段 源程序的編碼、編譯及程序單元測試。 （5）測試階段 總裝測試和確認測試 （6）運行與維護階段 根據新提出需求，擴充和修改軟件,兩類軟件工程方法,傳統(tǒng)軟件工程： 軟件分析 總體設計 詳細設計 面向過程的編碼 測試 面向對象軟件工程 軟件分析對象抽取 對象詳細設計 面向對象的編碼 測試,軟件測試,軟件測試是在軟件投入生產性運行之前，對軟件需求分析、設計規(guī)格說明和編碼的最終復審，是軟件質量保證的關鍵步驟。 軟件測試是為了發(fā)現錯誤而執(zhí)行程序的過程。,測試方法,一、靜態(tài)測試與動態(tài)測試 （一） 靜態(tài)測試方法 靜態(tài)測試一般指人工評審軟件文檔或程序，以便發(fā)現錯誤。靜態(tài)測試包括：代碼檢查、靜態(tài)結構分析、代碼質量度量等。 （二）動態(tài)測試方法 動態(tài)測試是在樣板測試數據上執(zhí)行程序并分析輸出以發(fā)現錯誤的過程。所以動態(tài)測試包括三部分：生成測試數據、執(zhí)行程序與驗證的輸出結果。,二、白盒測試與