《數(shù)據(jù)結構》課件-第一章 緒論

數(shù)據(jù)結構（Java語言描述）第1章緒論1.2數(shù)據(jù)結構概述1.1 java簡介1.3算法的描述和算法分析1.1Java簡介1.1.1Java語言Java語言是一種高級語言，它具有以下性質：面向對象、多線程、與體系結構無關、可解釋以及可移植。大多數(shù)語言要么用于編譯程序，要么用于解釋程序，這些程序經翻譯后才能在計算機上運行。Java語言的特殊之處在于用Java語言編寫的程序既能被編譯又能被解釋。首先，使用編譯器將程序翻譯為一種被稱為Java字節(jié)碼的中間代碼，這是由Java平臺上的解釋器解釋的與平臺無關的代碼。然后，解釋器在計算機上分析并運行每條Java字節(jié)碼。編譯只發(fā)生一次，而解釋在每次執(zhí)行程序時都發(fā)生。Java字節(jié)碼有助于使“一次編寫，處處運行”成為可能。1.1Java簡介1.1.2Java虛擬機JVM（Javavirtualmachine）就是我們常說的Java虛擬機，它是整個Java實現(xiàn)跨平臺的最核心的部分，所有的Java程序編譯后的類文件可以在虛擬機上執(zhí)行，并不直接與計算機的操作系統(tǒng)相對應，而是經過虛擬機間接與操作系統(tǒng)交互，由虛擬機將程序解釋給操作系統(tǒng)執(zhí)行。

JVM是Java平臺的基礎，和實際的計算機一樣，它也有自己的指令集，并且在運行時操作不同的主存儲器（簡稱內存）區(qū)域。

JVM的主要工作是解釋自己的指令集到CPU的指令集或系統(tǒng)調用，保護用戶免被惡意程序騷擾。1.2數(shù)據(jù)結構概述1.2.1學習數(shù)據(jù)結構的必要性數(shù)據(jù)結構是計算機專業(yè)中的一門專業(yè)基礎必修課，凡是設置計算機專業(yè)的院校都開設了此課程。此外，一些常見的數(shù)據(jù)結構已經滲透到計算機專業(yè)的各門課程中，例如《操作系統(tǒng)》課程中涉及到“隊列”和“樹”數(shù)據(jù)結構的使用，即進程調度的原則就是從就緒隊列中按照某種原則選取一個進程執(zhí)行；在文件管理中，文件的一般都按照“樹”型結構進行存儲和處理。1.2數(shù)據(jù)結構概述瑞士著名計算機科學家N.Wirth提出了著名公式“程序=算法+數(shù)據(jù)結構”，表明了數(shù)據(jù)結構在程序設計中的重要地位。在計算機發(fā)展的初期，人們使用計算機的目的主要是處理數(shù)值計算問題。由于當時所涉及的運算對象時簡單的整型、實型或布爾類型數(shù)據(jù)，所以程序設計者的主要精力都集中在程序設計技巧上，而無需重視數(shù)據(jù)結構。隨著計算機應用領域的擴大以及軟硬件的發(fā)展，非數(shù)值計算問題越來越顯得重要。這類問題涉及到的數(shù)據(jù)結構更為復雜，數(shù)據(jù)元素之間的相互關系一般無法用數(shù)學方程式直接描述。數(shù)學分析和計算方法在解決此類問題時顯得力不從心，而設計出合適的數(shù)據(jù)結構，才能有效地解決問題。1.2數(shù)據(jù)結構概述因此，掌握好數(shù)據(jù)結構課程的知識，對于提高解決實際問題的能力將會有很大的幫助。實際上，一個“好”的程序無非是選擇一個合理的數(shù)據(jù)結構和好的算法，而好的算法的選擇很大程度上取決于描述實際問題所采用的數(shù)據(jù)結構。所以，要想編寫出好的程序，僅僅學習計算機語言是不夠的，必須扎實的掌握數(shù)據(jù)結構的基本知識和基本技能。1.2數(shù)據(jù)結構概述1.2.2什么是數(shù)據(jù)結構一般而言，利用計算機解決一個具體問題時，大致需要經過如下幾個步驟：（1）從具體問題抽象出一個合適的數(shù)學模型；（2）設計一個解此數(shù)學模型的算法；（3）編寫出程序，進行測試、調整直到最終解答。尋求數(shù)學模型的實質是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關系，然后用數(shù)學的語言加以描述。1.2數(shù)據(jù)結構概述例1-1在八皇后問題中，處理過程不是根據(jù)某種確定的計算法則，而是利用試探和回溯的探索技術求解。為了求得合理布局，在計算機中要存儲布局的當前狀態(tài)。從最初的布局狀態(tài)開始，一步步地進行試探，每試探一步形成一個新的狀態(tài)，整個試探過程形成了一棵隱含的狀態(tài)樹。如圖1-1所示（為了描述方便，將八皇后問題簡化為四皇后問題）?；厮莘ㄇ蠼膺^程實質上就是一個遍歷狀態(tài)樹的過程。在這個問題中所出現(xiàn)的樹也是一種數(shù)據(jù)結構，它可以應用在許多非數(shù)值計算的問題。1.2數(shù)據(jù)結構概述1.2數(shù)據(jù)結構概述由以上例子可以看出，描述這類非數(shù)值計算問題的數(shù)學模型不再是數(shù)學方程，而主要是線性表、樹、圖這類的數(shù)據(jù)結構。因此，可以說數(shù)據(jù)結構課程主要是研究非數(shù)值計算的程序設計問題中所出現(xiàn)的計算機操作對象以及他們之間關系和操作的學科。1.2數(shù)據(jù)結構概述1.2.3基本概念和術語數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的描述。在計算機中，它泛指所有能輸入計算機中并被計算機程序處理的符號。它是計算機程序加工的原料，文字、表格、聲音、圖像等都稱為數(shù)據(jù)。數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在程序中通常把數(shù)據(jù)元素作為一個整體進行考慮和處理。例如，表1-1所示的學生表中，如果把每行當作一個數(shù)據(jù)元素來處理，此表共包含7個數(shù)據(jù)元素。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成，例如表1-1中每一個學生的信息作為數(shù)據(jù)元素，而學生信息的每一項（如學號、姓名等）都是數(shù)據(jù)項。數(shù)據(jù)的最小單位即數(shù)據(jù)項。1.2數(shù)據(jù)結構概述1.2數(shù)據(jù)結構概述數(shù)據(jù)結構是指數(shù)據(jù)及其之間的相互關系，可以看成相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。因此，可以把數(shù)據(jù)結構看成是帶結構的數(shù)據(jù)元素的集合。數(shù)據(jù)結構包括以下幾個方面。①數(shù)據(jù)元素之間的邏輯關系，即數(shù)據(jù)的邏輯結構。②數(shù)據(jù)元素及其關系在計算機存儲系統(tǒng)中的存儲方式，即數(shù)據(jù)的存儲結構，也稱為數(shù)據(jù)的物理結構。③施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運算。1.2數(shù)據(jù)結構概述

1.2數(shù)據(jù)結構概述數(shù)據(jù)類型是一個值的集合和定義在這個集合上的一組操作的總稱。例如，Java語言中的整型變量，其值集為某個區(qū)間上的整數(shù)，定義在其上的操作即為加、減、乘、除和模運算等算術運算。按“值”的不同特性，高級程序設計語言中的數(shù)據(jù)類型可分為兩類：原子類型和結構類型。原子類型的值是不可分解的，例如Java語言中的基本類型（整型、布爾型等）。結構類型的值是若干成分按照某種結構組成的，因此是可以分解的，其組成成分既可以是結構的，也可以是非結構的。1.2數(shù)據(jù)結構概述抽象數(shù)據(jù)類型是指一個數(shù)學模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型的定義僅取決于它的一組邏輯特性，而與其在計算機內的存儲形式無關，即不論其內部結構如何變化，只要它的數(shù)學特性不變，都不影響外部的使用。抽象數(shù)據(jù)類型定義格式如下：

ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：（數(shù)據(jù)對象定義） 數(shù)據(jù)關系：（數(shù)據(jù)關系定義） 數(shù)據(jù)操作：（數(shù)據(jù)操作定義）

}ADT抽象數(shù)據(jù)類型名1.2數(shù)據(jù)結構概述1.2.4數(shù)據(jù)的邏輯結構（1）集合集合是指數(shù)據(jù)元素之間除了“同屬于一個集合”的關系外，別無其他關系。1.2數(shù)據(jù)結構概述（2）線性結構線性結構是指該結構中的結點之間存在一對一的關系。其特點是開始結點和終端結點都是唯一的，除了開始結點和終端結點以外，其余結點都有且僅有一個直接前驅，有且僅有一個直接后繼。順序表就是一種典型的線性結構。1.2數(shù)據(jù)結構概述（3）樹形結構樹形結構是指該結構中結點之間存在一對多的關系。其特點是每個結點最多只有一個直接前驅，但可以有多個直接后繼或終端結點。二叉樹就是一種典型的樹形結構。1.2數(shù)據(jù)結構概述（4）圖形結構圖形結構或稱為網狀結構，是指該結構中的結點之間存在多對多的關系。其特點是每個結點的直接前驅和直接后繼的個數(shù)都可以是任意的。因此，圖形結構可能沒有開始結點和終端結點，也可能有多個開始結點和多個終端結點。1.2數(shù)據(jù)結構概述樹形結構和圖形結構統(tǒng)稱為非線性結構，該結構中的結點之間存在一對多或多對多的關系。由圖形結構、樹形結構和線性結構的定義可知，線性結構是樹形結構的特殊情況，而樹形結構又是圖形結構的特殊情況。1.2數(shù)據(jù)結構概述

1.2數(shù)據(jù)結構概述

1.2數(shù)據(jù)結構概述1.2.5數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構是邏輯結構用計算機語言的實現(xiàn)或在計算機中的表示（亦稱為映像），也就是邏輯結構在計算機中的存儲方式，它是依賴于計算機語言的。數(shù)據(jù)元素之間的關系在計算機中有兩種不同的表示方式：順序映像和非順序映像。歸納起來，數(shù)據(jù)結構在計算機中有以下4種存儲結構類型。1.2數(shù)據(jù)結構概述（1）順序存儲結構順序存儲結構是把邏輯上相鄰的結點存儲在物理位置上相鄰的存儲單元里，結點之間的邏輯關系由存儲單元的鄰接關系來體現(xiàn)。由此得到的存儲表示稱為順序存儲結構，通常順序存儲結構是借助于計算機程序設計語言的數(shù)組來描述的。順序存儲方法的主要優(yōu)點是節(jié)省存儲空間，因為分配給數(shù)據(jù)的存儲單元全用戶存放結點的數(shù)據(jù)，結點之間的邏輯關系沒有占用額外的存儲空間。采用這種方法時，可實現(xiàn)對結點的隨機存取。然而順序存儲方法的主要缺點是不便于修改，對結點的插入、刪除運算時，可能要移動一系列的結點。1.2數(shù)據(jù)結構概述（2）鏈式存儲結構鏈式存儲結構不要求邏輯上相鄰的結點在物理位置上也相鄰，結點間的邏輯關系是由附加的“指針”字段表示的。由此得到的存儲表示稱為鏈式存儲結構。鏈式存儲方法的優(yōu)點是便于修改，在進行插入、刪除操作時，僅需要修改相應結點的“指針域”，不必移動結點。但與順序存儲方法相比，鏈式存儲方法的存儲空間利用率較低，因為分配給數(shù)據(jù)的存儲單元有一部分被用來存儲結點間的邏輯關系了。另外，由于邏輯上相鄰的結點在物理位置上并不一定相鄰，所以不能對結點進行隨機方法操作。1.2數(shù)據(jù)結構概述（3）索引存儲結構索引存儲結構通常在存儲結點信息的同時還建立附加的索引表。索引表的每一項稱為索引項，索引項的一般形式是:（關鍵字，地址），關鍵字唯一標識一個結點，地址作為指向結點的指針。這種帶有索引表的存儲結構可以大大提高數(shù)據(jù)查找的速度。線性結構采用索引存儲方法后，可以對結點進行隨機訪問。在進行插入、刪除運算時，只需移動存儲在索引表中對應結點的存儲地址，而不必移動存放在結點表中結點的數(shù)據(jù)，所以仍保持較高的數(shù)據(jù)修改效率。索引存儲方法的缺點是增加了索引表，增加了存儲空間開銷。1.2數(shù)據(jù)結構概述（4）哈希存儲結構哈希存儲結構的基本思想是根據(jù)結點的關鍵字通過哈希函數(shù)直接計算出一個值，并將這個值作為該結點的存儲地址。哈希存儲結構的優(yōu)點是查找速度快，只要給出待查找結點的關鍵字，就可以計算出該結點的存儲地址。與前3種存儲結構不同的是，哈希存儲結構只存儲結點的數(shù)據(jù)，不存儲結點之間的邏輯關系。哈希存儲結構一般適用于要求對數(shù)據(jù)能夠進行查找和插入的場合。1.3算法的描述和算法分析1.3.1算法的描述算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每條指令表示一個或多個操作；一個算法具有以下5個重要的特性：（1）有窮性（2）確定性（3）可行性（4）輸入（5）輸出1.3算法的描述和算法分析當我們設計一個算法時，它應該滿足以下幾條目標：（1）正確性要求算法能夠正確地執(zhí)行預先規(guī)定的功能和性能要求。這是最重要也是最基本的標準。（2）可讀性算法應當易于理解，也就是可讀性好。（3）健壯性算法要求具有良好的容錯性，提供異常處理，能夠對如何的輸入進行檢查。不經常出現(xiàn)異常中斷或死機現(xiàn)象。（4）效率與低存儲量需求通常算法的效率主要指算法的執(zhí)行時間。對于同一個問題，如果能有多種算法進行求解，執(zhí)行時間短的算法效率高。算法存儲量指的是算法執(zhí)行過程中所需的大量存儲空間。1.3算法的描述和算法分析1.3.2影響算法效率的因素一個算法用高級語言實現(xiàn)以后，在計算機上運行時所消耗的時間與很多因素有關，主要因素列舉如下。①依據(jù)算法所選擇的具體策略；②問題的規(guī)模，如求100以內還是1000以內的素數(shù)；③編寫程序的語言，對于同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率往往越低；④編譯程序所產生的計算機代碼的質量；⑤計算機執(zhí)行指令的速度。1.3算法的描述和算法分析1.3.3算法效率的評價一個算法是由控制結構（順序、分支和循環(huán)）和原操作（指固有數(shù)據(jù)類型的操作）構成的，算法的執(zhí)行時間取決于二者的綜合結果。為了便于比較同一問題的不同算法，通常從算法中選取一種對于所研究的問題來說是基本運算的原操作，算法執(zhí)行的時間大致為基本運算所需的時間與其運行次數(shù)（一條語句的運行次數(shù)稱為語句頻度）的乘積。顯然，在一個算法中，執(zhí)行的基本運算次數(shù)越少，其執(zhí)行時間就相對越少；執(zhí)行基本運算的次數(shù)越多，其運行時間也相對越多。也就是說，一個算法的執(zhí)行時間可以看成基本運算執(zhí)行的次數(shù)。1.3算法的描述和算法分析算法基本運算次數(shù)T(n)是問題規(guī)模n的某個函數(shù)f(n)，記作：T(n)=O(f(n))記號“O”表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長和f(n)的增長率相同，稱為算法的時間復雜度?！癘”的形式定義為：若f(n)是正整數(shù)n的一個函數(shù)，則T(n)=O(f(n))表示存在一個正的常數(shù)M，使得當n≥n0時都滿足|T(n)|≤M|f(n)|，也就是只求出T(n)的最高階，忽略其低階項和常數(shù)，這樣既可以簡化計算，又可以較為客觀地反映當n很大時算法的效率。一個沒有循環(huán)的算法中基本運算次數(shù)與問題規(guī)模n無關，記為O(1)，也稱作常數(shù)階。一個只有一重循環(huán)的算法中基本次數(shù)與問題規(guī)模n的增長呈線性增大關系，記為O(n)，也稱線性階。1.3算法的描述和算法分析例如，以下3個程序段：

（a）{++x;s=0;}

（b）for(i=1;i<=n;i++){++x;s+=x;}

（c）for(j=1;j<=n;j++)

for(k=1;k<=n;k++){++x;s+=x;}

含基本操作“++x”的語句頻度分別為1、n和n2，則這3個程序段的時間復雜度分別為O(1)、O(n)和O(n2)，分別稱為常數(shù)階、線性階和平方階。各種不同數(shù)量級對應的值存在如下關系：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)

1.3算法的描述和算法分析例1-4分析以下算法的時間復雜度。voidfun(inta[],intn,intk){inti;i=0; //語句（1）while(i<n&&a[i]!=k) //語句（2） i++; //語句（3）return(i); //語句（4）}1.3算法的描述和算法分析

1.3算法的描述和算法分析例1-5分析以下算法的時間復雜度。floatRSum(floatlist[],intn)

{

count++;

if(n){

count++;

returnRSum(list,n-1)+list[n-1];

}

count++;

return0;

}

1.3算法的描述和算法分析

1.3算法的描述和算法分析這是一個遞推關系式，它可以通過轉換成如下公式來計算：根據(jù)上述結果可知，該程序的時間復雜度為線性階，即O(n)。

1.3算法的描述和算法分析1.3.4算法的存儲空間需求一個算法的空間復雜度是指算法運行所需的存儲空間。算法運行所需的存儲空間包括如下兩個部分。（1）固定空間需求這部分空間域所處理數(shù)據(jù)的規(guī)模大小和個數(shù)無關，也就是說，與問題實例的特征無關，主要包括程序代碼、常量、簡單變量、定長成分的結構變量所占的空間。（2）可變空間需求這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的規(guī)模有關。例如，分別包含100個元素的兩個數(shù)組相加，與分別包含10個元素的兩個數(shù)組相加，所需的存儲空間顯然是不同的。這部分存儲空間包括數(shù)據(jù)元素所占的空間，以及算法執(zhí)行所需的額外空間，例如，運行遞歸算法所需的系統(tǒng)?？臻g。1.3算法的描述和算法分析

1.3算法的描述和算