數(shù)據(jù)結構基礎概論.ppt

第1章 數(shù)據(jù)結構基礎概論,本章主要介紹以下內容 數(shù)據(jù)結構研究的主要內容 數(shù)據(jù)結構中涉及的基本概念 算法的概念、描述方法以及評價標準,1.1 數(shù)據(jù)結構研究的主要內容 1.2 基本概念和術語 1.3 算法,1.1 數(shù)據(jù)結構研究的主要內容,當今計算機應用的特點： l 所處理的數(shù)據(jù)量大且具有一定的關系； l 對其操作不再是單純的數(shù)值計算，而更多 的是需要對其進行組織、管理和檢索。 應用舉例1學籍檔案管理 假設一個學籍檔案管理系統(tǒng)應包含如下表1-1所示的學生信息。,表1-1,特點： l 每個學生的信息占據(jù)一行，所有學生的信息按學號順序依次排列構成一張表格； l 表中每個學生的信息依據(jù)學號的大小存在著一種前后關系，這就是我們所說的線性結構； l 對它的操作通常是插入某個學生的信息，刪除某個學生的信息，更新某個學生的信息，按條件檢索某個學生的信息等等。 應用舉例2輸出n個對象的全排列 輸出n個對象的全排列可以使用下圖1-1所示的形式描述。,圖 1-1 3個對象的全排列過程,特點： l 在求解過程中，所處理的數(shù)據(jù)之間具有層次關系，這是我們所說的樹形結構； l 對它的操作有：建立樹形結構，輸出最低層結點內容等等。 應用舉例3制定教學計劃 在制定教學計劃時，需要考慮各門課程的開設順序。有些課程需要先導課程，有些課程則不需要，而有些課程又是其他課程的先導課程。比如，計算機專業(yè)課程的開設情況如下表1-2所示：,表1-2,課程先后關系的圖形描形式：,圖 1-2 計算機專業(yè)必修課程開設先后關系,特點 l 課程之間的先后關系用圖結構描述； l 通過實施創(chuàng)建圖結構，按要求將圖結構中的頂點進行線性排序。 結論 計算機的操作對象的關系更加復雜，操作形式不再是單純的數(shù)值計算，而更多地是對這些具有一定關系的數(shù)據(jù)進行組織管理，我們將此稱為非數(shù)值性處理。要使計算機能夠更有效地進行這些非數(shù)值性處理，就必須弄清楚這些操作對象的特點，在計算機中的表示方式以及各個操作的具體實現(xiàn)手段。這些就是數(shù)據(jù)結構這門課程研究的主要內容。,1.2 基本概念和術語,數(shù)據(jù) 是對客觀事物的符號表示。在計算機科學中其含義是指所有能夠輸入到計算機中并被計算機程序處理的符號集合。 數(shù)據(jù)元素 是數(shù)據(jù)集合中的一個實體，是計算機程序中加工處理的基本單位。,數(shù)據(jù)元素按其組成可分為簡單型數(shù)據(jù)元素和復雜型數(shù)據(jù)元素。簡單型數(shù)據(jù)元素由一個數(shù)據(jù)項組成，所謂數(shù)據(jù)項就是數(shù)據(jù)中不可再分割的最小單位；復雜型數(shù)據(jù)元素由多個數(shù)據(jù)項組成，它通常攜帶著一個概念的多方面信息。 數(shù)據(jù)結構 簡單地說，就是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。常見的數(shù)據(jù)結構有：線性結構、樹形結構和圖形結構。 邏輯結構 數(shù)據(jù)結構中所說的“關系”實際上是指數(shù)據(jù)元素之間的邏輯關系，又稱此為邏輯結構。,存儲結構（物理結構） 是指數(shù)據(jù)結構在計算機存儲器中的具體實現(xiàn)。與孤立的數(shù)據(jù)元素表示形式不同，數(shù)據(jù)結構中的數(shù)據(jù)元素不但要表示其本身的實際內容，還要表示清楚數(shù)據(jù)元素之間的邏輯結構。 常見的存儲結構 順序存儲結構：特點是借助于數(shù)據(jù)元素的相對存儲位置來表示數(shù)據(jù)元素之間的邏輯結構； 鏈式存儲結構：特點是借助于指示數(shù)據(jù)元素地址的指針表示數(shù)據(jù)元素之間的邏輯結構。,1.3 算法,1.3.1 算法的概念 算法是解決某個特定問題的一種方法或一個過程。 計算機對數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進行的是算術運算；而在非數(shù)值性操作中主要進行的是檢索、排序、插入、刪除等等。,設計算法的基本過程 l 通過對問題進行詳細地分析，抽象出相應的數(shù)學模型； l 確定使用的數(shù)據(jù)結構，并在此基礎上設計對此數(shù)據(jù)結構實施各種操作的算法； l 選用某種語言將算法轉換成程序； l 調試并運行這些程序。,算法應該具有下列五個特性 （1）有窮性：一個算法必須在執(zhí)行有窮步之后結束。 （2）確定性：算法中的每一步，必須有確切的含義，在他人理解時不會產生二義性。 （3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實現(xiàn)。 （4）輸入：一個算法應該有零個或多個輸入。 （5）輸出：一個算法應該有一個或多個輸出。這里所說的輸出是指與輸入有某種特定關系的量。,舉例 問題：按從小到大的順序重新排列x，y，z三個數(shù)值的內容。 算法： （1）輸入x，y，z三個數(shù)值； （2）從三個數(shù)值中挑選出最小者并換到x中； （3）從y，z中挑選出較小者并換到y(tǒng)中； （4）輸出排序后的結果。,1.3.2 算法的描述 選擇算法描述語言的準則 （1）該語言應該具有描述數(shù)據(jù)結構和算法的基本功能； （2）該語言應該盡可能地簡捷，以便于掌握、理解； （3）使用該語言描述的算法應該能夠比較容易地轉換成任何一種程序設計語言。 “類C”描述語言是通過對C語言進行精心篩選保留的一個核心子集，并為了便于描述，又做了若干擴展修改，從而，增強了語言的描述功能。,1. 預定義常量及類型 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW -1 數(shù)據(jù)元素被約定為EntryType 類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。,2. 算法描述為以下的函數(shù)形式： 函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） 語句序列； 為了簡化函數(shù)的書寫，提高算法描述的清晰度，我們規(guī)定除函數(shù)參數(shù)表中的參數(shù)需要說明數(shù)據(jù)類型外，函數(shù)中使用的局部變量可以不做變量說明，必要時給出相應的注釋即可。另外，在書寫算法時，應該養(yǎng)成對重點語句段落添加注解的良好習慣。,3. 在算法描述中可以使用的賦值語句形式有： 簡單賦值 變量名 = 表達式； 串聯(lián)賦值 變量名1 = 變量名2 = . = 變量名n = 表達式； 成組賦值 （變量名1，.，變量名n）=（表達式1，.，表達式n）； 結構賦值 結構名1 = 結構名2； 結構名 =（值1，值2，.，值n）； 條件賦值 變量名 = 條件表達式 ? 表達式1：表達式2； 交換賦值 變量名1 變量名2；,4. 在算法描述中可以使用的選擇結構語句形式有： 條件語句1 if （表達式） 語句； 條件語句2 if （表達式） 語句； else 語句； 開關語句1 switch （表達式） case 值1：語句序列1；break； case 值2：語句序列2；break； . case 值n：語句序列n；break； default：語句序列n+1； ,開關語句2 switch case 條件1：語句序列1；break； case 條件2：語句序列2；break； . case 條件n：語句序列n；break； default：語句序列n+1； ,5. 在算法描述中可以使用的循環(huán)結構語句形式有： for循環(huán)語句 for （表達式1；循環(huán)條件表達式；表達式2） 語句； while循環(huán)語句 while （循環(huán)條件表達式） 語句； do-while循環(huán)語句 do 語句序列； while （循環(huán)條件表達式）； 6. 在描述算法中可以使用的結束語句形式有： 函數(shù)結束語句 return 表達式； return; case或循環(huán)結束語句 break; 異常結束語句 exit（異常代碼）；,7. 在算法描述中可以使用的輸入輸出語句形式有： 輸入語句 scanf( 格式串，變量名1，.，變量名n)； 輸出語句 printf( 格式串，表達式1，.，表達式n); 方括號（ ）中的內容是可以省略的部分。 8. 在算法描述中使用的注釋格式為： 單行注釋 /文字序列 9. 在算法描述中可以使用的擴展函數(shù)有： 求最大值 max（表達式1，.，表達式n）；這個函數(shù)返回參數(shù)表中n個表達式計算結果中的最大值。 求最小值 min（表達式1，.，表達式n）；這個函數(shù)返回參數(shù)表中n個表達式計算結果中的最小值。,【算法1-1】用類C描述將三個數(shù)值排序的算法。 viod Three_Sort( int *x,int *y,int *z) /將x,y,z三個指針所指示的內容按從小到大的順序重新排列 if (*y*x /在y和z所指示的存儲單元中挑選出較小者換到y(tǒng)中 ,1.3.3 算法的評價 算法的評價標準 (1) 正確性：要求算法能夠正確地執(zhí)行預先規(guī)定的功能，并達到所期望的性能要求。 (2) 可讀性：為了便于理解、測試和修改算法，算法應該具有良好的可讀性。 (3) 健壯性：算法中擁有對輸入數(shù)據(jù)、打開文件、讀取文件記錄、分配內存空間等操作的結果檢測，并通過與用戶對話的形式做出相應的處理選擇。 (4) 時間與空間效率：算法的時間與空間效率是指將算法變換為程序后，該程序在計算機上運行時所花費的時間及所占據(jù)空間的度量。,算法的時間效率 算法的時間效率主要由兩個因素決定： l 所需處理問題的數(shù)據(jù)量大小，數(shù)據(jù)量大，所花費的時間就多； l 在解決問題的過程中，基本操作的執(zhí)行次數(shù)。 時間特性的分析 如果我們將一個算法所花費的時間設計成一個以數(shù)據(jù)量n為自變量的函數(shù)T(n)，這個函數(shù)在正整數(shù)