第2部分數(shù)據結構

目錄第1章緒論第3章結構化開發(fā)方法第4章面向對象的系統(tǒng)分析和設計第2章軟件工程概述第6章數(shù)據結構概述第5章并發(fā)程序開發(fā)技術第7章線性表第8章棧和隊列第10章樹第11章圖第9章數(shù)組第15章互聯(lián)網軟件開發(fā)實踐第12章排序第14章數(shù)據庫基本概念與應用程序設計第13章查找第1部分軟件技術基礎第2部分數(shù)據結構第3部分軟件技術實踐第六章數(shù)據結構概述6.1數(shù)據結構的引入

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

[例6.1]

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

[例6.2]

計算機和人對弈問題6.1數(shù)據結構的引入

[例6.3]

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