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

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