數據結構一章緒論ppt課件

1、第一章第一章 緒論緒論11 根本術語根本術語12 數據構造的定義及研討的內容數據構造的定義及研討的內容121 數據的邏輯構造數據的邏輯構造122 數據的存儲構造數據的存儲構造123 數據的運算數據的運算13 算法算法131 算法的概念及特性算法的概念及特性132 算法的描畫算法的描畫133 算法的評價算法的評價14 學習數據構造的意義和目的學習數據構造的意義和目的 11 根本術語 數據Data是人們商定的符號，用它來表示客觀事物及其活動，是信息的載體。數據是計算機程序加工處置的對象。 數據元素Data Element是數據的根本單位，在計算機程序中通常作為一個整體進展思索和處置，在不同的情況下

2、，又可以稱為元素、結點、頂點或記錄。數據是由數據元素構成的。 數據項Data Item是構成數據元素不可分割的具有獨立含義的最小標識單位。假設數據元素可再分，那么數據元素是由假設干個數據項組成；如數據元素不可再分，數據元素和數據項是同一概念，如整型數據就是不可再分的。 數據類型Data Type是一個值的集合和定義在這個值集上一組操作的總稱。按值的不同特性，高級程序設計言語中的數據類型可分為原子類型和構造類型兩類。 第一章第一章 緒論緒論12 數據構造的定義及研討的內容數據構造的定義及研討的內容數據構造Data Structure：按照某種邏輯關系組織起來的一批數據，用一定的存儲方式存儲在計算

3、機的存儲器中，并在這些數據上定義一個運算的集合，就稱為一個數據構造Data Structure。數據構造重點研討的內容：1數據的邏輯構造：即數據之間的邏輯關系。2數據的存儲構造：即數據及數據之間的關系在計算機存儲器中的表示。3數據的運算：即對數據施加的各種操作。 數據的邏輯構造 數據的邏輯構造Logical Structure：的是數據元素之間的邏輯關系。它是人們根據實踐問題的需求和問題本身所含數據之間的內在聯(lián)絡而籠統(tǒng)出來的數學模型，與如何利用計算機存儲和處置無關，所以被稱為數據的邏輯構造。由于數據的邏輯構造是數學模型，可以借助數學方法來表示，詳細的可以用離散數學中關系代數的二元組表示：Dat

4、a_Structure =D，S通常取S中的一個關系rj來進展討論，rj可以表示為數據元素的序偶的集合。假設集合中有序偶，表示數據元素di和dj之間有rj這種關系。用二元組表示的數據的邏輯構造，有如下的常用術語1前趨結點、后繼結點、相鄰結點2開場結點、終端結點、內部結點數據的邏輯構造還可以利用更籠統(tǒng)的圖形表示 v數據的邏輯構造有兩大類：數據的邏輯構造有兩大類：v1線性構造：經典的線性構造是線性表。線性構造：經典的線性構造是線性表。v 線性構造的邏輯特征是：有且僅有一個開場結點和一個終端結點線性構造的邏輯特征是：有且僅有一個開場結點和一個終端結點，其他的內部結點都有且僅有一個前趨結點和一個后繼結

5、點，也就是，其他的內部結點都有且僅有一個前趨結點和一個后繼結點，也就是說構造中的數據元素間存在著一對一的相互關系。說構造中的數據元素間存在著一對一的相互關系。v2非線性構造：經典的非線性構造有樹形構造和圖形構造。非線性構造：經典的非線性構造有樹形構造和圖形構造。v 樹形構造的邏輯特征是：有且僅有一個開場結點，可有假設干樹形構造的邏輯特征是：有且僅有一個開場結點，可有假設干個終端結點，其他的內部結點都有且僅有一個前趨結點，可以有假設個終端結點，其他的內部結點都有且僅有一個前趨結點，可以有假設干個后繼結點，也就是說構造中的數據元素間存在著一對多的層次關干個后繼結點，也就是說構造中的數據元素間存在著

6、一對多的層次關系。系。v 圖形構造的邏輯特征是：可有假設干個開場結點和終端結點，圖形構造的邏輯特征是：可有假設干個開場結點和終端結點，其他的內部結點可以有假設干個前趨結點和假設干個后繼結點，也就其他的內部結點可以有假設干個前趨結點和假設干個后繼結點，也就是說構造中的數據元素間存在著多對多的網狀關系。是說構造中的數據元素間存在著多對多的網狀關系。表1.1 某校圍棋社團學生簡表學號姓名性別出生日期職務01黃家正男1982-08-05團長02趙 芳女1981-08-15組長03王 明女1983-04-01組長04王 紅女1982-06-28組員05張小才男1984-03-17組員06馬立偉男1983

7、-10-12組員07孫 剛男1982-07-05組員08劉 永男1982-12-09組員 例例1.1 在表在表1.1中，八名學生按學號從小到大陳中，八名學生按學號從小到大陳列，構成一個線性構造。假設表示這種邏輯構列，構成一個線性構造。假設表示這種邏輯構造的關系為造的關系為r1，那么，那么r1可以定義為學生按學號可以定義為學生按學號順序遞增陳列的關系，該線性構造的邏輯構造順序遞增陳列的關系，該線性構造的邏輯構造可用二元組表示為：可用二元組表示為：L =D，S，r1SD =01，02，03，04，05，06，07，08 r 1 =， ，圖1.1 線性構造的圖示 例例1.2 在表在表1.1中，學生之

8、間還存在著指點與被指中，學生之間還存在著指點與被指點關系，其中點關系，其中01號學生為團長，直接指點號學生為團長，直接指點02和和03號學生，他們分別是組長，號學生，他們分別是組長，02號學生直接指點號學生直接指點04和和05號學生，號學生，03號學生直接指點號學生直接指點06、07和和08號學生號學生，假設表示這種邏輯構造的關系為，假設表示這種邏輯構造的關系為r2，那么，那么r2可以可以定義為學生之間的指點與被指點關系，該數據構造定義為學生之間的指點與被指點關系，該數據構造的邏輯構造可用二元組表示為：的邏輯構造可用二元組表示為：T =D，S，r2SD =01，02，03，04，05，06，0

9、7，08r2 =， ， 0 10 20 30 40 50 60 70 8圖1.2 樹形構造的圖示例例1.3 在表在表1.1中，學生之間還有好友關系，如中，學生之間還有好友關系，如01和和02、03、05號是好友，號是好友，02和和04號是好友，號是好友，03和和05號是好友，號是好友，04和和05、06號是好友，號是好友，06和和07之間是好友，之間是好友，08無好友，假設表示無好友，假設表示這種邏輯構造的關系為這種邏輯構造的關系為r3，那么，那么r3可以定義為學生之間的好可以定義為學生之間的好友關系，該數據構造的邏輯構造可用二元組表示為：友關系，該數據構造的邏輯構造可用二元組表示為：G =D

10、，S，r3SD =01，02，03，04，05，06，07，08r3 =，數據的存儲構造 數據的存儲構造Storage Structure，是指數據的邏輯構造到計算機存儲器的映射。對于數據的邏輯構造G =D，S，在映射中，一方面要將數據集D中的數據元素存放到存儲器中，另一方面還要表達關系集S，常見的表達關系S的方式有顯示和隱含兩種。常用的實現數據存儲構造的方法有如下四種：1順序存儲2鏈接存儲3索引存儲4散列存儲四種存儲方法，可以單獨運用，也可以組合起來對數據構造進展存儲映象。同一種邏輯構造采用不同的存儲方法，可以得到不同的存儲構造。針對詳細的運用，某種數據構造選擇何種存儲構造主要思索運算的方便

11、及效率。存儲構造的描畫：數據的存儲構造是數據的邏輯構造用計算機言語的實現，它是依賴于計算機言語的，因此可以借用高級言語中提供的數據類型如數組、指針等來描畫它。l1順序存儲順序存儲l根本思想是：把邏輯上相鄰的數據元素存儲在物理位置上相鄰的根本思想是：把邏輯上相鄰的數據元素存儲在物理位置上相鄰的存儲單元里。存儲單元里。l數據元素間的邏輯關系由存儲單元的鄰接關系來表達，也就是說數據元素間的邏輯關系由存儲單元的鄰接關系來表達，也就是說邏輯關系上相鄰物理位置上也相鄰，數據元素的邏輯次序與物理邏輯關系上相鄰物理位置上也相鄰，數據元素的邏輯次序與物理次序一致。這是一種隱含表達關系的存儲方法，關系隱含在存儲次

12、序一致。這是一種隱含表達關系的存儲方法，關系隱含在存儲位置上。位置上。 l數據元素在存儲區(qū)域中是延續(xù)存放的，這種存儲方法稱為順序存數據元素在存儲區(qū)域中是延續(xù)存放的，這種存儲方法稱為順序存儲構造儲構造Sequential Storage Structure，通常用計算機高級，通常用計算機高級言語中的數組來描畫。言語中的數組來描畫。 l2鏈接存儲鏈接存儲l根本思想是：經過附加指針域表示數據元素之間的關系。根本思想是：經過附加指針域表示數據元素之間的關系。l這種存儲方法不要求邏輯上相鄰的數據元素存儲位置上也相鄰，這種存儲方法不要求邏輯上相鄰的數據元素存儲位置上也相鄰，數據元素間的邏輯關系是經過附加指

13、示其他數據元素位置的地址數據元素間的邏輯關系是經過附加指示其他數據元素位置的地址信息指針而得到的，這是一種顯示表達關系的存儲方法。信息指針而得到的，這是一種顯示表達關系的存儲方法。l數據元素在存儲區(qū)域中可以是延續(xù)的，也可以是不延續(xù)的，通常數據元素在存儲區(qū)域中可以是延續(xù)的，也可以是不延續(xù)的，通常用計算機高級言語中的指針來描畫，稱為鏈接存儲構造用計算機高級言語中的指針來描畫，稱為鏈接存儲構造Linked Storage Structure。 l由于不要求存儲空間的延續(xù)性，很適宜動態(tài)存儲管理由于不要求存儲空間的延續(xù)性，很適宜動態(tài)存儲管理 例例1.4 用上述兩種方法存儲有序序列用上述兩種方法存儲有序序

14、列A=99， 123，134，假設每個數據元素占，假設每個數據元素占2個字個字 節(jié)，即一個存儲單元為兩個字節(jié)。節(jié)，即一個存儲單元為兩個字節(jié)。圖1.4 關系的映像方法l 3索引存儲索引存儲l 根本思想是：除了存儲數據元素，還要建立一個或假設干個附加的根本思想是：除了存儲數據元素，還要建立一個或假設干個附加的索引表來標識數據元素的地址。索引表來標識數據元素的地址。l 索引表中的每一項稱為索引項，是用來標識一個或一組數據元素的索引表中的每一項稱為索引項，是用來標識一個或一組數據元素的存儲位置。索引項普通方式為關鍵字，地址，其中的關鍵字是存儲位置。索引項普通方式為關鍵字，地址，其中的關鍵字是用來標識數

15、據元素的數據項。用來標識數據元素的數據項。l 假設每個數據元素對應一個索引項，那么該索引表為稠密索引假設每個數據元素對應一個索引項，那么該索引表為稠密索引Dense Index。假設一組數據元素對應一個索引項，那么該索引。假設一組數據元素對應一個索引項，那么該索引表稱為稀疏索引表稱為稀疏索引Sparse Index。l 索引存儲方法主要是用于實現快速查找而設計的一種存儲方式。索引存儲方法主要是用于實現快速查找而設計的一種存儲方式。l 4散列存儲散列存儲l 根本思想是：根據數據元素的關鍵字直接計算出該結點的存儲地址根本思想是：根據數據元素的關鍵字直接計算出該結點的存儲地址，通常稱為關鍵字地址轉換

16、法。在此方法中需求設計一個散列函，通常稱為關鍵字地址轉換法。在此方法中需求設計一個散列函數，以關鍵字為自變量，散列函數值即為地址。數，以關鍵字為自變量，散列函數值即為地址。l 用這種存儲方法設計的存儲構造最適宜按關鍵字進展查找，但數據用這種存儲方法設計的存儲構造最適宜按關鍵字進展查找，但數據元素之間的關系曾經無法在存儲構造上表達。元素之間的關系曾經無法在存儲構造上表達。 數據的運算數據的運算也稱操作是指對數據元素進展加工和處置。運算的種類很多，詳細視運用的要求而設置運算的種類。對每種數據構造設置一些根本運算操作，使得不同運用都能經過這些操作實現對數據構造的各種訪問，是數據構造中研討的一個重要方

17、面。數據構造的根本操作普通包括查找、插入、刪除、更新、排序等。這些根本運算實踐是在籠統(tǒng)的數據上所施加的一系列籠統(tǒng)的操作，所謂籠統(tǒng)的操作，就是不涉及詳細的運用，只知道這些操作應該完成的功能，但無須思索“如何完成。這些運算的粒度很小，是構造復雜運算的根底。數據根本運算的定義是基于數據的邏輯構造，每種經典的邏輯構造都有一個運算的集合。數據的運算是定義在數據的邏輯構造上而實如今數據的存儲構造上的 。 數據的運算是經過算法來描畫的 。在討論任何一種數據構造時，都應該將數據的邏輯構造、數據的存儲構造和數據的運算這三方面看成一個整體，不要孤立地了解一個方面，而要留意它們之間的聯(lián)絡 13 算法算法的概念及特性

18、算法Algorithm是處理特定問題的方法和步驟，是由假設干條指令組成的有限序列。一個算法必需具有以下五個特性：1有窮性：對于恣意一組合法輸入值，一個算法必需總是在執(zhí)行有窮步驟后終了，有限時間內完成。2確定性：算法中每條指令都確切地規(guī)定了所應執(zhí)行的操作，使算法的執(zhí)行者或閱讀者能明確其含義及如何執(zhí)行，不致產生二義性或多義性；另外，在同一條件下，一個算法只能有一條執(zhí)行途徑。3可行性：算法中的每一步都是可行的，都可以經過手工或機器可以接受的有限次操作在有限時間內完成。4輸入：一個算法有0個或多個輸入，這些輸入是算法所需的初始量或待處置的對象，來自某個特定的對象集合。 5輸出：一個算法有1個或多個輸出

19、，這些輸出與輸入有著某種特定的關系。算法的描畫算法的描畫 算法普通可以采用自然言語、程序流程圖、偽碼、算法普通可以采用自然言語、程序流程圖、偽碼、高級程序設計言語等描畫。高級程序設計言語等描畫。算法的評價算法的評價 通常從定性和定量兩方面來評價一個算法通常從定性和定量兩方面來評價一個算法 算法的定性評價，是從算法的設計者和運用者角度算法的定性評價，是從算法的設計者和運用者角度來衡量優(yōu)劣的來衡量優(yōu)劣的 1正確性正確性Correctness是指算法該當滿足是指算法該當滿足詳細問題的需求，即對合理的輸入，算法都會得出詳細問題的需求，即對合理的輸入，算法都會得出正確的結果，這是設計和評價一個算法的首要

20、條件正確的結果，這是設計和評價一個算法的首要條件，否那么其他的評價規(guī)范也就無從談起。，否那么其他的評價規(guī)范也就無從談起。2可讀性可讀性Readablity是指算法被了解的難是指算法被了解的難易程度。易程度。3強壯性強壯性Robustness是指算法對輸入的非是指算法對輸入的非法數據恰當地作出反映或進展相應處置的才干。法數據恰當地作出反映或進展相應處置的才干。4簡單性簡單性Simplicity是指一個算法所采用的是指一個算法所采用的邏輯構造、存儲構造以及處置過程的簡單程度。邏輯構造、存儲構造以及處置過程的簡單程度。 l 算法的定量評價l1時間復雜度Time Complexity是一個算法運轉時所

21、耗費的系統(tǒng)時間，也就是算法的時間效率。 l每條語句反復執(zhí)行的次數稱為語句的頻度Frenquency countl當不思索算法運轉的軟硬件環(huán)境時，算法所耗費的時間就是該算法中一切簡單語句的頻度之和。 l普通情況，在討論算法的時間效率時，主要思索當問題規(guī)模n趨向無窮大時，時間復雜度T(n)的數量級，亦稱為算法的漸近時間復雜度，那么T(n)= O(f(n) 。l 記號“O是一個數學符號，其數學定義是： l 設T(n)和f(n)均為正整數n的函數，假設存在兩個正整數M和n0，使得當nn0時，都有 | T(n)| M | f(n)| 存在，那么T(n)= O(f(n)。lim T(n) / f(n) =

22、 Mnu在多數情況下，當一個算法中有假設干個循環(huán)語句時，算法的時間復雜度是由嵌套循環(huán)中最內層循環(huán)語句的頻度決議的。需求留意的是，假設算法中包括對其他函數或算法的調用，計算算法的時間復雜度時還要分析被調用算法或函數的時間復雜度。例例1.5 求一維數組元素中的最大值求一維數組元素中的最大值 int sum(int a,int n) int i,s; 1 s= a0; /*1次次*/2 for(i=1;in; i+; ) /*n次次*/3 if (s ai) s= ai; /*n-1次次*/4 return s; /*1次次*/ T1(n)= 1+n+n-1+1=2n+1 T1(n)=O(n) ，即

23、，即f(n)=n例例1.6 兩個兩個n階方陣相加階方陣相加void Matrixadd(int a ,int b ,int c ,int n) int i,j;1 for (i=0;in;i+) /*n+1次次*/2 for (j=0;jn;j+) /* n(n+1)次次*/3 cij=aij+bij; /* n2次次*/T2(n)= n+1+ n(n+1)+ n2=2n2+2n+1T2(n)=O(n2)，即，即f(n)=n2 例例1.7 求兩個求兩個n階方陣的乘積階方陣的乘積void Matrixmlt(int a ,int b ,int c ,int n) int i,j,k;1 for

24、(i=0;in;i+) /*n+1次次*/2 for (j=0;jn;j+) /* n(n+1)次次*/3 cij=0; /* n2次次*/4 for (k=0;kn;k+) /* n2(n+1)次次*/5 cij= cij+aik*bkj; /* n3次次*/ T3(n)= n+1+ n(n+1)+ n2+ n2(n+1)+ n3=2n3+3n2+2n+1T3(n)= O(n3) ，即，即f(n)=n3 l最好時間復雜度、最壞時間復雜度和平均時間復雜度最好時間復雜度、最壞時間復雜度和平均時間復雜度 l例例1.8 在一維數組中查找指定的元素在一維數組中查找指定的元素l int search(int a,int x,int n)l int i;l1 for(i=0;in; i+; ) l2 if (ai=x) ruturn i+1; l3 return 0; l l最好時間復雜度為最好時間復雜度為O(1)l最壞時間復雜度為最壞時間復雜度為O(n)l平均