大學(xué)計算機基礎(chǔ)算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ).ppt

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