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

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

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

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

[例6.1]

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

[例6.2]

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

[例6.3]

多叉路口交通燈管理問題6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.1引論什么是數(shù)據(jù)計(jì)算機(jī)處理的對(duì)象是數(shù)據(jù)，那么什么是數(shù)據(jù)呢？數(shù)據(jù)是客觀事物在計(jì)算機(jī)中的表示，是信息的載體，具有可識(shí)別性、可加工處理性和可存儲(chǔ)性等特征，是計(jì)算機(jī)程序加工處理的對(duì)象?？勺R(shí)別性是指計(jì)算機(jī)能夠識(shí)別數(shù)據(jù)，為此必須對(duì)客觀事物進(jìn)行編碼；可存儲(chǔ)性是指數(shù)據(jù)能夠存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)設(shè)備上；可加工處理性是指計(jì)算機(jī)能夠以程序設(shè)計(jì)人員設(shè)計(jì)的算法，對(duì)數(shù)據(jù)進(jìn)行加工處理，以得到預(yù)期的結(jié)果。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.2名詞定義數(shù)據(jù)(Data)是描述客觀事物的數(shù)、字符以及所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的集合。數(shù)據(jù)元素(DataElement)是數(shù)據(jù)的基本單位，即數(shù)據(jù)這個(gè)集合中的一個(gè)個(gè)體（客體）。數(shù)據(jù)對(duì)象(DataObject)具有相同特性的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(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ù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)方法，即為數(shù)據(jù)的存儲(chǔ)結(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)容直接前趨與直接后繼學(xué)號(hào)姓名性別課名成績95001王麗女物理8195002劉建東男物理76···············95031陳立平男物理92學(xué)生成績表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ù)，應(yīng)用計(jì)算機(jī)語言，可按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在該數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合。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)的邏輯特征是有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。線性表就是一種典型的線性結(jié)構(gòu)。本書第7章到第8章介紹的都是線性結(jié)構(gòu)。2)非線性結(jié)構(gòu)非線性結(jié)構(gòu)的邏輯特征是一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。第9章到第11章介紹的都是非線性結(jié)構(gòu)。6.2數(shù)據(jù)結(jié)構(gòu)的基本概念6.2.5存儲(chǔ)方法1.順序存儲(chǔ)方法2.鏈接存儲(chǔ)方法3.索引存儲(chǔ)方法4.散列存儲(chǔ)方法6.3關(guān)于算法的描述及算法分析6.3.1算法的概念算法是由若干條指令組成的有限序列，它必須滿足以下性質(zhì)：1.輸入性2.輸出性3.有窮性4.確定性5.可行性6.3關(guān)于算法的描述及算法分析6.3.2算法分析衡量一個(gè)算法的好壞，除其“正確性”外，還應(yīng)考慮：(1)執(zhí)行算法所消耗的時(shí)間；(2)執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間，其中主要應(yīng)考慮輔存量的大??；(3)其他諸如：算法是否易讀，是否易于調(diào)試、測(cè)試等。6.3關(guān)于算法的描述及算法分析6.3.2算法分析求兩個(gè)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)于算法的描述及算法