計算機軟件技術(shù)基礎(chǔ)教程課件-6第六章-數(shù)據(jù)結(jié)構(gòu)概述

第2部分數(shù)據(jù)結(jié)構(gòu)

目錄第1章緒論第3章結(jié)構(gòu)化開發(fā)方法第4章面向?qū)ο蟮南到y(tǒng)分析和設(shè)計第2章軟件工程概述第6章數(shù)據(jù)結(jié)構(gòu)概述第5章并發(fā)程序開發(fā)技術(shù)第7章線性表第8章棧和隊列第10章樹第11章圖第9章數(shù)組第15章互聯(lián)網(wǎng)軟件開發(fā)實踐第12章排序第14章數(shù)據(jù)庫基本概念與應用程序設(shè)計第13章查找第1部分軟件技術(shù)基礎(chǔ)第2部分數(shù)據(jù)結(jié)構(gòu)第3部分軟件技術(shù)實踐第六章數(shù)據(jù)結(jié)構(gòu)概述6.1數(shù)據(jù)結(jié)構(gòu)的引入

從提出一個實際問題到計算機解出答案，需要經(jīng)歷下列步驟：分析階段、設(shè)計階段、編碼階段和測試維護階段等。其中分析階段就是從實際問題中提取操作對象以及操作對象之間的關(guān)系。下面我們來看幾個例子。6.1數(shù)據(jù)結(jié)構(gòu)的引入

[例6.1]

計算機管理圖書目錄問題書名作者登錄號分類號出版日期定價Java語言李曉等9700001873.8792-991977/3/2643.5UNIX系統(tǒng)張昊9600012973.874-1261996/9/1923.5··················6.1數(shù)據(jù)結(jié)構(gòu)的引入

[例6.2]

計算機和人對弈問題6.1數(shù)據(jù)結(jié)構(gòu)的引入

[例6.3]

多叉路口交通燈管理問題6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.1引論什么是數(shù)據(jù)計算機處理的對象是數(shù)據(jù)，那么什么是數(shù)據(jù)呢？數(shù)據(jù)是客觀事物在計算機中的表示，是信息的載體，具有可識別性、可加工處理性和可存儲性等特征，是計算機程序加工處理的對象?？勺R別性是指計算機能夠識別數(shù)據(jù)，為此必須對客觀事物進行編碼；可存儲性是指數(shù)據(jù)能夠存儲在計算機的存儲設(shè)備上；可加工處理性是指計算機能夠以程序設(shè)計人員設(shè)計的算法，對數(shù)據(jù)進行加工處理，以得到預期的結(jié)果。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.2名詞定義數(shù)據(jù)(Data)是描述客觀事物的數(shù)、字符以及所有能輸入到計算機中并被計算機程序處理的符號的集合。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，即數(shù)據(jù)這個集合中的一個個體（客體）。數(shù)據(jù)對象(DataObject)具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)是指數(shù)據(jù)之間的相互關(guān)系，即數(shù)據(jù)的組織形式。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.3數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容(1)研究數(shù)據(jù)元素之間固有的客觀聯(lián)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)（LogicalStructure）。(2)研究數(shù)據(jù)在計算機內(nèi)部的存儲方法，即為數(shù)據(jù)的存儲結(jié)構(gòu)（StorageStructure），又稱物理結(jié)構(gòu)。(3)研究如何在數(shù)據(jù)的各種結(jié)構(gòu)（邏輯的和物理的）上施加有效的操作或處理（算法）。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.3數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容直接前趨與直接后繼學號姓名性別課名成績95001王麗女物理8195002劉建東男物理76···············95031陳立平男物理92學生成績表6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.3數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容綜上所述，我們可以將數(shù)據(jù)結(jié)構(gòu)定義為：按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)，應用計算機語言，可按一定的存儲表示方式把它們存儲在計算機的存儲器中，并在該數(shù)據(jù)上定義了一個運算的集合。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.4數(shù)據(jù)的邏輯結(jié)構(gòu)分類通常我們將數(shù)據(jù)的邏輯結(jié)構(gòu)簡稱為數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有以下兩大類：1)線性結(jié)構(gòu)線性結(jié)構(gòu)的邏輯特征是有且僅有一個開始結(jié)點和一個終端結(jié)點，且所有結(jié)點都最多只有一個直接前趨和一個直接后繼。線性表就是一種典型的線性結(jié)構(gòu)。本書第7章到第8章介紹的都是線性結(jié)構(gòu)。2)非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是一個結(jié)點可能有多個直接前趨和直接后繼。第9章到第11章介紹的都是非線性結(jié)構(gòu)。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.5存儲方法1.順序存儲方法2.鏈接存儲方法3.索引存儲方法4.散列存儲方法6.3關(guān)于算法的描述及算法分析6.3.1算法的概念算法是由若干條指令組成的有限序列，它必須滿足以下性質(zhì)：1.輸入性2.輸出性3.有窮性4.確定性5.可行性6.3關(guān)于算法的描述及算法分析6.3.2算法分析衡量一個算法的好壞，除其“正確性”外，還應考慮：(1)執(zhí)行算法所消耗的時間；(2)執(zhí)行算法所耗費的存儲空間，其中主要應考慮輔存量的大??；(3)其他諸如：算法是否易讀，是否易于調(diào)試、測試等。6.3關(guān)于算法的描述及算法分析6.3.2算法分析求兩個n階方陣的乘積C=A×B，下面是算法描述：＃definen自然數(shù)MATRIXMLT(A,B,C)FloatA[][n],B[][n],C[][n];{inti,j,k;(1) for(i=0;i<n;i++)n+1(2) for(j=0；j<n;j++)n(n+1)(3) {C[i][j]=0;n2(4) for(k=0;k<n;k++)n2(n+1)(5) C[i][j]=C[i][j]+A[i][k]*B[k][j];}}n36.3關(guān)于算法的描述及算法