課程內(nèi)容計算機軟件的基礎知識.ppt

1、數(shù)據(jù)結構,課程內(nèi)容： 計算機軟件的基礎知識數(shù)據(jù)結構 課時安排： 數(shù)據(jù)結構54學時 上機18學時 周二（56）周四（12） 逸夫教學樓306 逸夫教學樓7樓2號機房,教材： 數(shù)據(jù)結構 劉振鵬 張曉莉 郝杰編 參考書： 數(shù)據(jù)結構 嚴蔚敏 清華,第一章 緒言,1.1 什么是數(shù)據(jù)結構 程序=數(shù)據(jù)結構+算法 例1 書目自動檢索系統(tǒng),書目文件,例2 人機對奕問題,多叉路口交通燈管理問題,數(shù)據(jù)結構定義: 是一門研究非數(shù)值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科,1.2 基本概念和術語 數(shù)據(jù)（data)所有能輸入到計算機中去的描述客觀事物的符號 數(shù)據(jù)元素（data element

2、）數(shù)據(jù)的基本單位，也稱節(jié)點（node）或記錄（record） 數(shù)據(jù)項（data item）有獨立含義的數(shù)據(jù)最小單位，也稱域(field) 數(shù)據(jù)結構（data structure)數(shù)據(jù)元素和數(shù)據(jù)元素關系的集合,數(shù)據(jù)的邏輯結構只抽象反映數(shù)據(jù)元素的邏輯關系 數(shù)據(jù)的存儲（物理）結構數(shù)據(jù)的邏輯結構在計算機存儲器中的實現(xiàn),1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,鏈式存儲,h,數(shù)據(jù)類型高級語言中指數(shù)據(jù)的取值范圍及其上可進行的操作的總稱,例 C語言中，提供int, char, float, double等基本 數(shù)據(jù)類型，數(shù)組、結構體、共用體、枚舉 等構造數(shù)據(jù)類型，還有指針、

3、空(void)類 型等。用戶也可用typedef 自己定義數(shù)據(jù)類型,typedef struct int num; char name20; float score; STUDENT; STUDENT stu1,stu2, *p;,1.3 算法的描述和算法分析簡介 算法（algorithm）解決某一特定問題的具體步驟的描述，是指令的有限序列 算法特性,算法的描述采用C語言 算法的評價衡量算法優(yōu)劣的標準 正確性(correctness) 可讀性(readability) 健壯性(robustness) 效率與低存儲量,算法效率用依據(jù)該算法編制的程序在計算機上執(zhí)行所消耗的時間來度量 1.事后統(tǒng)計利用計算機內(nèi)記時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分 缺點：必須先運行依據(jù)算法編制的程序 所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本 身的優(yōu)劣 2.事前分析估計一個高級語言程序在計算機上運行所消耗的時間取決于： 依據(jù)的算法選用何種策略 問題的規(guī)模 程序語言 編譯程序產(chǎn)生機器代碼質(zhì)量 機器執(zhí)行指令速度 同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，所以使用絕對時間單位衡量算法效率不合適,時間復雜度：基本操作重復執(zhí)行的次數(shù)的階數(shù) T(n)=o(f(n) 空間復雜度：s(n)=o(f(n),例1：NXN矩陣相乘 for(i=1;i=n