數(shù)據(jù)結(jié)構(gòu)與算法講義數(shù)據(jù)結(jié)構(gòu)與算法講義數(shù)據(jù)結(jié)構(gòu)與算法講義學(xué)習(xí)目標(biāo)objective1了解《公共基礎(chǔ)知識》的內(nèi)容2掌握算法的基本概念

《公共基礎(chǔ)知識》的內(nèi)容01數(shù)據(jù)結(jié)構(gòu)與算法程序設(shè)計基礎(chǔ)軟件工程基礎(chǔ)數(shù)據(jù)庫設(shè)計基礎(chǔ)四個部分1234第一章數(shù)據(jù)結(jié)構(gòu)及算法1算法的概念、時間復(fù)雜度與空間復(fù)雜度2數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的定義3棧的定義及其運(yùn)算、線性鏈表的存儲方式4樹與二叉樹的相關(guān)概念5查找與排序方法重要知識點(diǎn)：第二章程序設(shè)計基礎(chǔ)重要知識點(diǎn)：結(jié)構(gòu)化程序設(shè)計方法的四個原則01對象、類、消息、繼承的概念類與實(shí)例的區(qū)別02經(jīng)?？疾榻Y(jié)構(gòu)化程序設(shè)計的原則、面向?qū)ο蠓椒ǖ幕靖拍钴浖母拍?、軟件生命周期及各階段所包含的活動1概要設(shè)計與詳細(xì)設(shè)計的概念、模塊獨(dú)立性及其度量的標(biāo)準(zhǔn)、詳細(xì)設(shè)計常用的工具2軟件測試的目的和4個步驟3軟件調(diào)試的任務(wù)4第三章軟件工程基礎(chǔ)重要知識點(diǎn)：01請02請02數(shù)據(jù)模型3個描述內(nèi)容、E-R模型的概念及其E-R圖表示法、關(guān)系操縱、關(guān)系模型三類數(shù)據(jù)約束第四章數(shù)據(jù)庫設(shè)計基礎(chǔ)01數(shù)據(jù)庫及其相關(guān)的概念03關(guān)系模型的基本操作、關(guān)系代數(shù)中的擴(kuò)充運(yùn)算04數(shù)據(jù)庫設(shè)計的4個階段重要知識點(diǎn)：算法的概念029算法復(fù)雜度算法的基本概念0102兩個考點(diǎn)考核幾率30%，分值為2分，此考點(diǎn)為識記內(nèi)容，了解算法中對數(shù)據(jù)的基本運(yùn)算?？荚嚽闆r算法的基本概念1.算法的定義對解題方案準(zhǔn)確而完整的描述稱為算法算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則,是計算機(jī)解題的過程(計算的方法)。在這個過程中，無論是形成解題思路(推理實(shí)現(xiàn)的算法),還是編寫程序(操作實(shí)現(xiàn)的算法)，都是在實(shí)施某種算法。2.算法的基本特征一個算法應(yīng)該具有以下五個重要的特征。一個算法必須保證執(zhí)行有限步之后結(jié)束有窮性確定性輸入輸出可行性算法的每一步驟必須有確切的定義0個或多個輸入，運(yùn)算對象的初始情況有一個或多個輸出，沒有輸出的算法是毫無意義的算法原則上能夠精確地運(yùn)行，用筆和紙做有限次運(yùn)算后即可完成圖形法偽碼描述法3.算法的表示方法1.流程圖2.N-S圖輸入園的半徑，計算園的面積問題計算園面積輸入半徑的值給rS=3.14*r*r輸出S的值N-S圖：

已知半徑，求園的面積INPUTrS=3.14*r*rPTINTS求園面積對數(shù)據(jù)對象的運(yùn)算和操作01算法的控制結(jié)構(gòu)024.算法的兩個基本要素算術(shù)運(yùn)算邏輯運(yùn)算關(guān)系運(yùn)算數(shù)據(jù)傳輸基本的運(yùn)算和操作順序結(jié)構(gòu)選擇結(jié)構(gòu)循環(huán)結(jié)構(gòu)控制結(jié)構(gòu)考點(diǎn)2：算法的復(fù)雜度考試幾率70%，分值為2分，此考點(diǎn)為重點(diǎn)識記內(nèi)容，掌握算法時間復(fù)雜度、空間復(fù)雜度的概念。考試情況執(zhí)行這個算法所需要的計算工作量時間復(fù)雜度空間復(fù)雜度執(zhí)行這個算法所需要的內(nèi)存算法在執(zhí)行過程中臨時占用的存儲空間算法優(yōu)劣的主要標(biāo)準(zhǔn)大致等于計算機(jī)執(zhí)行一種簡單操作所需的平均時間與算法中進(jìn)行簡單操作的次數(shù)的乘積。時間復(fù)雜度存儲算法本身所占用的存儲空間、算法中的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運(yùn)行過程中臨時占用的存儲空間這三個部