uml與面向?qū)ο笙到y(tǒng)分析與設計與java9

1、第六講 算法與數(shù)據(jù)結構 （數(shù)組、向量及字符處理）1、數(shù)組（Array）2、向量（Vector）3、字符處理（String）4、算法：遞歸、排序、查找5、復雜數(shù)據(jù)結構程序 算法 數(shù)據(jù)結構 軟件：刻畫現(xiàn)實世界，解決現(xiàn)實世界中的問題 語言：實現(xiàn)的工具 算法：問題的解的描述 數(shù)據(jù)結構：現(xiàn)實世界的數(shù)據(jù)模型 程序就是在數(shù)據(jù)的某些特定的表示方式和結構的基礎上對抽象算法的具體表述。瑞士科學家沃思（Niklaus Wirth，1984年圖靈獎得主）在1976年出版了著名的程序算法數(shù)據(jù)結構一書。不了解施加于數(shù)據(jù)上的算法就無法決定如何構造數(shù)據(jù)，反之，算法的結構和選擇卻常常在很大程度上依賴于作為基礎的數(shù)據(jù)結構。簡而言

2、之，程序的構成（算法）與數(shù)據(jù)結構是兩個不可分割地聯(lián)系在一起的問題。1、數(shù)組一維數(shù)組：定義一維數(shù)組的定義方式為： type arrayName ； 其中類型(type)可以為Java中任意的數(shù)據(jù)類型，包 括簡單類型和組合類型，數(shù)組名arrayName為一個 合法的標識符， 指明該變量是一個數(shù)組類型變量。 例如： int intArray ； 聲明了一個整型數(shù)組，數(shù)組中的每個元素為整型數(shù)據(jù)。 我們還可以定義一個復合類型的數(shù)組，例如： Date dateArray ；聲明了一個容納復合數(shù)據(jù)類型Date的數(shù)組。 與C、C+不同，Java在數(shù)組的定義中并不為數(shù)組元素分配內(nèi)存，因此 中不用指出數(shù)組中元素的

3、個數(shù)，即數(shù)組長度，而且對于如上定義的一個數(shù)組是不能訪問它的任何元素的。必須經(jīng)過初始化后，才能應用數(shù)組的元素。1、數(shù)組一維數(shù)組：定義 除了這種定義數(shù)組的方式之外，java語言還提供了其他的定義形式，如下所示：type arrayName； 對于以上舉出的例子，我們也可以這樣定義：int intArray； Date dateArray;1、數(shù)組一維數(shù)組：定義一維數(shù)組定義之后，必須經(jīng)過初始化才可以引用。數(shù)組的初始化分為靜態(tài)初始化和動態(tài)初始化兩種： 靜態(tài)初始化：在定義數(shù)組的同時對數(shù)組元素進行初始化，例如： int intArray =1,2,3,4;/定義了一個含有4個 / 元素的int型數(shù)組。1、

4、數(shù)組一維數(shù)組：初始化 動態(tài)初始化：使用運算符new為數(shù)組分配空間，對于簡單類型的數(shù)組，其格式如下： type arrayName =new typearraySize; type arrayName=new typearraySize;對于復合類型的數(shù)組，需要經(jīng)過兩步空間分配。 首先： type arrayName =new typearraySize; 然后：arrayName0=new type(paramList); arrayNamearraySize-1=new type(paramList);1、數(shù)組一維數(shù)組：初始化例如：String stringArrar; /定義一個Strin

5、g類型的數(shù)組stringArray = new String3; /給數(shù)組stringArray分配3個應用 /空間，初始化每個引用值為nullstringArray0=new String(“how”);stringArray1=new String(“are”);stringArray2=new String(“you”);初始化各數(shù)組元素1、數(shù)組一維數(shù)組：初始化當定義了一個數(shù)組，并用運算符new為它分配了內(nèi)存空間后，就可以引用數(shù)組中的每一個元素了。元素的引用方式為： arrayNameindex index為數(shù)組下標，可以是整型常數(shù)或表達式，如：arrayName1, arrayName

6、i, arrayName6*i等。下標是0序的，即從0開始，一直到數(shù)組長度減1。1、數(shù)組一維數(shù)組：引用 另外，與C、C+中不同，Java對數(shù)組元素要進行越界檢查以保證安全性。同時，對于每個數(shù)組都有一個屬性length指明它的長度，例如： intArray.length指明數(shù)組intArray的長度。 1、數(shù)組一維數(shù)組：邊界檢查 public class ArrayTest public static void main( String args ) int i; int a = new int5; for( i=0; i=0; i- ) System.out.println(a+i+ = +a

7、i); 該程序?qū)?shù)組中的每個元素賦值，然后按逆序輸出。 1、數(shù)組一維數(shù)組：示例運行結果為：C:java ArrayTest a4 = 4a3 = 3 a2 = 2 a1 = 1a0 = 01、數(shù)組一維數(shù)組：示例數(shù)組作為參數(shù)/ Passing arrays and individual array elements to methods/ Java core packagesimport java.awt.Container;/ Java extension packagesimport javax.swing.*;public class PassArray extends JApplet /

8、 initialize applet public void init() JTextArea outputArea = new JTextArea(); Container container = getContentPane(); container.add( outputArea ); int array = 1, 2, 3, 4, 5 ; String output = Effects of passing entire array by reference:n + The values of the original array are:n; / append original ar

9、ray elements to String output for ( int counter = 0; counter array.length; counter+ ) output += + array counter ; modifyArray( array ); / array passed by reference output += nnThe values of the modified array are:n; / append modified array elements to String output for ( int counter = 0; counter arr

10、ay.length; counter+ ) output += + array counter ; output += nnEffects of passing array + element by value:n + a3 before modifyElement: + array 3 ; / attempt to modify array 3 modifyElement( array 3 ); output += na3 after modifyElement: + array 3 ; outputArea.setText( output ); / end method init / mu

11、ltiply each element of an array by 2 public void modifyArray( int array2 ) for ( int counter = 0; counter array2.length; counter+ ) array2 counter *= 2; / multiply argument by 2 public void modifyElement( int element ) element *= 2; / end class PassArray1、數(shù)組一維數(shù)組：示例在任何語言中，多維數(shù)組都被看作數(shù)組的數(shù)組。比如二維數(shù)組是一個特殊的一維

12、數(shù)組，其每一個元素又是一個一維數(shù)組。我們主要以二維數(shù)組為例來說明，高維數(shù)組與此類似。1、數(shù)組多維數(shù)組二維數(shù)組的定義方式 type arrayName ； 例如： int intArray ； 也可以采用另一種定義方式： type arrayName;與一維數(shù)組一樣，這時對數(shù)組元素也沒有分配內(nèi)存空間，同樣要使用運算符new來分配內(nèi)存，然后才可以訪問每個元素。1、數(shù)組二維數(shù)組：定義二維數(shù)組的初始化也分為靜態(tài)和動態(tài)兩種。 靜態(tài)初始化：在定義數(shù)組的同時為數(shù)組分配空間。 int intArray =1,2,2,3,3,4;不必指出數(shù)組每一維的大小，系統(tǒng)會根據(jù)初始化時給出的初始值的個數(shù)自動算出數(shù)組每一維的

13、大小。1、數(shù)組二維數(shù)組：初始化動態(tài)初始化：對高維數(shù)組來說，分配內(nèi)存空間有下面兩種方法：1.直接為每一維分配空間，如： type arrayName =new typearraylength1arraylength2例如： int a =new int23；1、數(shù)組二維數(shù)組：初始化2.從最高維開始（而且必須從最高維開始），分別為每一維分配空間，如： String s =new String2 ; s0=new String2; s1=new String3; s00=new String(“Good”); s01=new String(“Luck”); s10=new String(“to”);

14、 s11=new String(“you”); s12=new String(“!”);1、數(shù)組二維數(shù)組：初始化二維數(shù)組的引用 對二維數(shù)組中每個元素，引用方式為： arrayNameindex1index2 其中index1和index2為數(shù)組下標，為整型常數(shù)和表達式，都是0序的。二維數(shù)組舉例 兩個矩陣相乘，參照參考書在課余時間上機練習。1、數(shù)組二維數(shù)組：引用及示例數(shù)組是用來表達一組同類型數(shù)據(jù)的數(shù)據(jù)結構在Java中數(shù)組是定長的，數(shù)組的大小不會動態(tài)變化數(shù)組變量的值是數(shù)組對象實例的引用在java.util包中的Arrays類提供了一些操作數(shù)組的方法在java.util包中的Vector提供了動態(tài)變

15、長數(shù)組的功能，Vector的容量可以隨著需要變化1、數(shù)組java.util.Arraysint binarySearch(type a, type key)數(shù)組a必須已經(jīng)排序，否則返回值無意義當數(shù)組a中有重復的值時，該方法返回的值不確定如果key存在，則返回它在數(shù)組a中的位置如果不存在，則返回它的“-(插入位置-1)”void fill(type a, type val)void fill(type a, int fromIndx, int toIndex, type val)包括afromIndx，但不包括atoIndexfromIndx= toIndex時，范圍是一個空的范圍1、數(shù)組jav

16、a.util.Arraysboolean equals(type a, type a2)兩個數(shù)組大小相同，并且每一個元素相等兩個null數(shù)組是相等的1、數(shù)組java.util.Arraysvoid sort(type a)void sort(type a, int fromIndx, int toIndex)void sort(type a, Comparatorc)void sort(type a, int fromIndx, int toIndex, Comparatorc)包括afromIndx，但不包括atoIndexfromIndx= toIndex時，范圍是一個空的范圍排序算法都具

17、有n*log(n)的計算復雜性，效率高排序算法都保證穩(wěn)定，即排序算法不會改變相等元素的順序?qū)Σ煌愋偷臄?shù)組，算法的實現(xiàn)并不完全相同可以用自己的Comparator對象聲明自定義的順序1、數(shù)組java.util.Arraysjava.lang.Systemvoid arraycopy(Objectsrc, intsrc_position, Objectdst, intdst_position, intlength)范圍不能越界可對任何同類型的數(shù)組進行復制數(shù)組復制過程中做嚴格的類型檢查更詳細的內(nèi)容參見JDK文檔1、數(shù)組數(shù)組的復制 向量(Vector)是java.util類包提供的一個工具類。它對應

18、于類似數(shù)組的順序存儲的數(shù)據(jù)結構，但是具有比數(shù)組更強大的功能。它是允許不同類型元素共存的變長數(shù)組。每個Vector類的對象可以表達一個完整的數(shù)據(jù)序列。Vector類的對象不但可以保存順序的一列數(shù)據(jù)，而且還提供了許多有用的方法來操作和處理這些數(shù)據(jù)。 另外，Vector類對象所表達的序列中元素的個數(shù)是可變的，即Vector實現(xiàn)了變長數(shù)組。2、向量 Java中的數(shù)組只能保存固定數(shù)目的元素，且必須把所有需要的內(nèi)存單元一次性的申請出來，而不能先創(chuàng)建數(shù)組再追加數(shù)組元素數(shù)量，為了解決這個問題Java中引入了向量類Vector。Vector也是一組對象的集合，但相對于數(shù)組，Vector可以追加對象元素數(shù)量，可以

19、方便的修改和維護序列中的對象。2、向量向量比較適合在如下情況下使用： 1. 需要處理的對象數(shù)目不定，序列中的元素都是對象或可以表示為對象。 2. 需要將不同類的對象組合成一個數(shù)據(jù)序列。 3. 需要做頻繁的對象序列中元素的插入和刪除。 4. 經(jīng)常需要定位序列中的對象和其他查找操作。 5. 在不同的類之間傳遞大量的數(shù)據(jù)。 Vector類的方法相對于數(shù)組要多一些，但是使用這個類也有一定的局限性，例如其中的對象不能是簡單數(shù)據(jù)類型等。2、向量Vector類有三個構造函數(shù)： Vector()：構造一個空的向量 Vector(int capacity)：以指定的存儲容量構造一個空的向量 Vector(int

20、 capacity, int capacityIncrement)：以指定的存儲容量和容量增量構造一個空的Vector。例如： Vector MyVector=new Vector(100,50)； 這個語句創(chuàng)建的MyVector向量序列初始有100個元素的空間，以后一旦使用殆盡則以50為單位遞增，使序列中元素的個數(shù)變化成150，200，。在創(chuàng)建Vector序列時，不需要指明序列中元素的類型，可以在使用時確定。2、向量 創(chuàng)建向量類的對象有兩種添加元素的方法： addElement( Object obj)：將新元素添加到序列尾部。 insertElementAt(Object obj, int

21、 index)：將新元素插 入到指定位置。2、向量向向量序列中添加元素下面是使用這兩種方法的例子：Vector MyVector=new Vector()；for (int i=1;i=10;i+) MyVector.addElement(new Random();MyVector.insertElementAt(middle,5);2、向量向向量序列中添加元素使用以下方法修改或刪除向量序列中的元素： 1. setElementAt(Object obj,int index) 將向量序列index位置處的對象元素設置成為obj，如果這個位置原來有元素則被覆蓋。 2. removeElement

22、(Object obj) 刪除向量序列中第一個與指定的obj對象相同的元素，同時將后面的元素前提，補上空位。這個方法返回的是布爾值。 3. removeElementAt(int index) 刪除index指定位置處的元素，同時將后面的元素前提。2、向量修改或刪除向量序列中的元素4. removeAllElements() 清除向量序列中的所有元素。下例中先創(chuàng)建了一個Vector，再刪除掉其中的所有字符串對象“to”。Vector MyVector=new Vector(100);for (int i=0;ijava demoOfStringBuffer buffer=abclength=3

23、capacity=192. append public synchronized StringBuffer append(對象類型 對象名) append方法將指定的參數(shù)對象轉化成字符串，附加在原來的字符串對象之后。3. insert public synchronized StringBuffer insert(int 插入位置，對象類型 對象名) 在指定的位置插入給出的參數(shù)對象所轉化而得的字符串。3、字符串StringBuffer：基本方法4. setChatAt() public synchronized void setCharAt(int index,char ch) 用來設置指定索

24、引index位置的字符值。5. setLength public synchronized void setLength(int newLength) 如果希望明確地定義字符緩沖區(qū)的長度，則可以用此方法。如果newlength大于現(xiàn)在的長度，串尾將補0，如果小于，那么newlength后的字符將丟失。3、字符串StringBuffer：基本方法 1. C/C+的字符串只是簡單的以零字符結尾的字符數(shù)組，而Java中，字符串是一個封裝的對象，這種處理對于編程者提供了許多有利之處。 2. C/C+中可以通過指針直接對字符串所在的內(nèi)存地址進行操作，并且不對越界情況進行檢查，Java中只能通過類Stri

25、ng或StringBuffer所提供的接口對字符串進行操作，并且要對越界情況進行檢查并報告，這樣大大增加了安全性。 3. 由于類String和StringBuffer的接口都經(jīng)明確說明，所以我們可以預知Java中字符串處理的功能；而在C/C+中，只有通過庫函數(shù)或者自定義函數(shù)對字符串進行處理。 3、字符串Java與C/C+處理字符串的差別字符類，支持字符的相關操作作為基本數(shù)據(jù)類型char的包裝類提供了一些關于char常量的定義提供了變換大小寫的方法參見JDK文檔3、字符串Charactor從一個字符串析取子字符串構造方法StringTokenizer(Stringstr) /缺省分隔符，為空格S

26、tringTokenizer(Stringstr, Stringdelim) /指定分隔符StringTokenizer(Stringstr,Stringdelim, booleanreturnDelims)int countTokens()：返回Token的數(shù)目boolean hasMoreTokens()：是否還有下一個TokenString nextToken()：返回下一個TokenString nextToken(Stringdelim) ：改變分隔符，從當前位置處，繼續(xù)返回下一個Token。3、字符串StringTokenizerStringTokenizer st = new S

27、tringTokenizer(this is a test);while (st.hasMoreTokens() println(st.nextToken();輸出結果為：thisisatest 3、字符串StringTokenizer算法指的是一種計算過程，具有以下性質(zhì)： 通用性：即適用于某一類問題中的所有個體，而不只是用來解決一個具體的問題。 能行性：即應有明確的步驟一步一步地引導計算的進行。 機械性：即每個步驟都是機械的、定死的，不需要計算者臨時動腦筋。 有限性：至少對某些輸入數(shù)據(jù)，算法應在有限多步內(nèi)結束，并給出計算結果。 離散性：算法的輸入數(shù)據(jù)及輸出數(shù)據(jù)都應是離散的符號。4、算法：遞歸

28、、排序、查找算法的基本要求： 正確 易維護（可讀，易修改） 方便使用 高效 速度快 運行時間少，時間復雜度低 占用內(nèi)存少 空間復雜度低 算法的效率可以測試，用大量輸入數(shù)據(jù)測量運行的時間和占用的內(nèi)存，通過比較判別和選擇效率高的算法 更重要的是編程前的分析和估計，即理論的計算，給出事前的判斷4、算法：遞歸、排序、查找遞歸一個關于遞歸的故事 一個沒有去過北京的人問：天安門是什么樣子？去過北京的人答道：天安門有個城樓，城樓上有個國徽，國徽里有個天安門，天安門有個城樓，城樓上有個國徽，國徽里有個天安門， 4、算法：遞歸、排序、查找遞歸4、算法：遞歸、排序、查找遞歸 遞歸是常用的編程技術，其基本思想是“自

29、己調(diào)用自己”。 數(shù)學上最常見、最簡單的遞歸問題就是自然數(shù)的階乘。 n=1 n! = 1; n1 n! = n * (n-1)!;適合用遞歸方法求解的問題 有一個初始狀態(tài) 后續(xù)的情況可由前面的狀態(tài)推出 如Fibonacci數(shù)列F1 = F2 = 1; Fn = Fn-1 + Fn-2 (n=3)遞歸與循環(huán)long Fibonacci(int n) if( n=1| n=2 ) return 1; else return Factorial(n-1) + Factorial(n-2) ;long Fibonacci(int n) int i; long f1,f2,fn; if( n=1| n=2

30、 ) return 1; f1 = 1; f2 = 1; for( i=3; i=n; i+) fn = f1 + f2; f1 = f2; f2 = fn; return fn;4、算法：遞歸、排序、查找遞歸遞歸問題欣賞河內(nèi)塔（ Hanoi Tower）問題：這是一個流傳很久的游戲。1. 有三根桿子A,B,C。A桿上有n只碟子 2. 每次移動一塊碟子,小的只能疊在大的上面 3. 把所有碟子從A桿經(jīng)C桿全部移到B桿上. 遞歸求解：1. 若只有一只碟子，直接將它從A桿移到B桿；2. 把n-1只碟子從A桿經(jīng)B桿移動到C桿，將A桿上第n只碟子移到B桿；然后再將n-1只碟子從C桿經(jīng)A桿移到B桿。 4、

31、算法：遞歸、排序、查找遞歸 此外，遞歸是人工智能語言Lisp/Prolog等進行問題求解的基本手段。遞歸問題欣賞8皇后問題：把8個皇后放在8 x 8的棋盤上，使得任何一個都不將其他7個的軍。騎士巡游問題：給出一個n x n的棋盤，一位騎士按國際象棋的規(guī)則移動放在第（0,0）格里，找出一種可以走遍整個棋盤的方案（如果存在的話）。即做n2-1次移動，使得棋盤上每個格子都恰好只被訪問一次。4、算法：遞歸、排序、查找遞歸4、算法：遞歸、排序、查找排序 排序是指對一些數(shù)據(jù)信息的重新組織，通常是對一個數(shù)組進行重新操作，使得信息由大到?。ń敌颍┗蛘哂尚〉酱螅ㄉ颍┐鎯ΑＲ笈判蚴呛芤环N基本的需要。我們所感興

32、趣的是如何尋找到一個好的辦法來進行排序。 就地排序算法：不增加新的存儲空間1、插入排序法（Insert Sort）將一個數(shù)插入到序列中的合適位置。2、選擇排序法（Selection Sort）每次把最?。ù螅┑脑亟粨Q到最前面。3、冒泡排序法（Bubble Sort）比較并交換相鄰的元素，直到所有元素都被放到合適的位置。4、算法：遞歸、排序、查找排序4、算法：遞歸、排序、查找排序：插入排序（思想）4、算法：遞歸、排序、查找排序：插入排序（算法）int a = 19, 2, 35, -6, -12, 5, 23, 16, 9, 0;int i,j,k;int x;for(i=1; i= 0 &

33、x aj ) aj+1 = aj; j-; aj+1 = x;Worst case遞增/遞減Comparison = n(n-1)/2Average= n(n-1)/4SpaceNone4、算法：遞歸、排序、查找排序：插入排序（分析）4、算法：遞歸、排序、查找排序：選擇排序（算法）int num = 19, 2, 35, -6, -12, 5, 23, 16, 9, 0;int i,j,k;int x;for(i=0; inum.length-1; i+) /最后一個元素無需比較 k = i; x = numi; for(j=i+1; jnum.length; j+) if(numj n2Av

34、erage case=n2/4 - n2SpaceNone4、算法：遞歸、排序、查找排序：選擇排序（分析）4、算法：遞歸、排序、查找排序：冒泡排序（算法）int a = 19, 2, 35, -6, -12, 5, 23, 16, 9, 0;int i,j,k;int x;for(i=1; i=i; j-) if( aj-1aj) x = aj-1; aj-1 = aj; aj = x; Worst case遞增/遞減Comparison = n(n-1)/2 - n2Average case=n2/4 - n2SpaceNone4、算法：遞歸、排序、查找排序：冒泡排序（分析）其他就地排序算法

35、： 前面三種算法的變種 快速排序算法（Quick Sort） 4、算法：遞歸、排序、查找排序：其他就地排序算法待排序的數(shù)據(jù)（N個）放在一個一維數(shù)組中，另設一個10*N的二維數(shù)組，設待排序數(shù)據(jù)中最大的數(shù)是4位，則排序需要4輪掃描，每輪包括分散掃描和集中掃描：分散掃描將數(shù)據(jù)分散到二維數(shù)組中。求出個待排序數(shù)據(jù)的個位數(shù)，以此個位數(shù)位行下標，保存到二維數(shù)組相應的行中。如104，24將保存到第三行中（0序），90則被保存到第一行中。如果兩個數(shù)的個位數(shù)相同，則保存到同一行中，但它們列下標的先后順序則由它們在一維數(shù)組中的先后順序決定。集中掃描將二維數(shù)組中的數(shù)據(jù)按照行優(yōu)先順序返回到一維數(shù)組中。如上面的三個數(shù)據(jù)返

36、回到一維數(shù)組中后成為：90，104，24。第二輪掃描針對十位數(shù)做分散掃描和集中掃描，掃描后一維數(shù)組中的數(shù)據(jù)為：104，24，90。第三輪針對百位數(shù)，掃描后得到最終排序：24，90，104。4、算法：遞歸、排序、查找排序：桶排序（思想）009012310402445678911040240902901040243104024090402409010401041024234567890900024090110423456789用空間換時間，效率高4、算法：遞歸、排序、查找排序：桶排序（分析）4、算法：遞歸、排序、查找查找 查找是利用給出的匹配關鍵值，在一個數(shù)據(jù)集合或數(shù)據(jù)序列中找出符合匹配關鍵值的一

37、個或一組數(shù)據(jù)的過程。 順序查找：最簡單的查找算法，程序從數(shù)據(jù)序列的第一個數(shù)據(jù)開始，逐個與匹配關鍵值比較，直到找到一個或所有的匹配數(shù)據(jù)為止（也可能找不到）。順序查找不要求待查找的數(shù)據(jù)序列是否已經(jīng)排好序。 二分查找：當待查找數(shù)據(jù)序列中數(shù)據(jù)比較多時，順序查找的效率將十分低。二分查找可以提高查找效率，但要求待查找的數(shù)據(jù)序列已經(jīng)排好序。以序列中間數(shù)據(jù)為界將待查找的數(shù)據(jù)序列分成兩個子序列，比較匹配關鍵值與中間數(shù)據(jù)的大小，再確定去哪個子序列中繼續(xù)查找。這樣逐步縮小范圍，直到找到所需數(shù)據(jù)。 線性表堆棧（Stack）隊列（Queue）列表（List）鏈表（Linked List）集合（Set） 樹（Tree）

38、圖（Graph）5、復雜數(shù)據(jù)結構線性表 數(shù)據(jù)元素（節(jié)點）的有限序列 叫線性表，數(shù)組其實也是一種線性表, 也叫順序表。 （a1, a2, ,an-1, an） a1為首元，an為末元， n叫線性表的長度 ai的后繼是ai+1, i=1, ,n-1. an沒有后繼。 ai的前驅(qū)是ai-1, i=2, ,n. a1沒有前驅(qū)。 ai可以是基本數(shù)據(jù)類型也可以是引用數(shù)據(jù)類型。 沒有數(shù)據(jù)的線性表叫空表。空表的長度n=0。 線性表是最簡單的也是最基本的數(shù)據(jù)結構。不同的線性表具有不同的約束和不同的行為。5、復雜數(shù)據(jù)結構線性表堆棧（Stack）的概念 LIFO（Last In First Out，后進先出）的線性

39、表，元素的插入和刪除必須在棧頂進行，不能在棧底進行。對堆棧的操作 push(x)：在棧的頂部插入元素，簡稱入棧； pop()：刪除棧頂?shù)脑?，簡稱出棧。5、復雜數(shù)據(jù)結構線性表：堆棧（Stack）5、復雜數(shù)據(jù)結構線性表：堆棧（Stack）5、復雜數(shù)據(jù)結構線性表：堆棧（Stack）堆棧的應用求表達式的值 表達式的中綴表示法： 31+2*(5-3) 表達式的后綴表示法： 31 2 5 3 - * + 利用后綴表示法求表達式的值：順序掃描表達式的后綴表示，遇到操作數(shù)則將操作數(shù)入棧，遇到運算符則將棧頂?shù)膬蓚€操作數(shù)取出進行計算，并將計算結果入棧。 遞歸、例外處理等也都是利用堆棧機制來實現(xiàn)。5、復雜數(shù)據(jù)結構

40、線性表：堆棧（Stack） 隊列（Queue）是與堆棧不同的另一類數(shù)據(jù)結構。在一個隊列中，最先入列的數(shù)據(jù)最先出列（先進先出），這與先入后出的堆棧形成了對比。 在應用軟件開發(fā)實踐中，經(jīng)常涉及到“先進先處理”的案例。比如，紅綠燈下的車輛調(diào)度，飛機等候著陸時的機場跑道的指揮控制等。服務行業(yè)也有許多相同的情況，比如在一家銀行或超市，顧客在服務員（出納、收銀員等）的前面排隊的情況。 5、復雜數(shù)據(jù)結構線性表：隊列（Queue）5、復雜數(shù)據(jù)結構線性表：鏈表（Linked List） 單鏈表 循環(huán)鏈表 雙向鏈表 雙向循環(huán)鏈表5、復雜數(shù)據(jù)結構線性表：鏈表 單鏈表單鏈表插入刪除AH:1-10 x6+2x8+7x1

41、4BH:-x4+10 x6-3x10+8x14+4x18單鏈表的應用：多項式加法5、復雜數(shù)據(jù)結構線性表：鏈表 單鏈表5、復雜數(shù)據(jù)結構線性表：鏈表 雙向鏈表雙向鏈表插入刪除雙向鏈表的應用：稀疏矩陣5、復雜數(shù)據(jù)結構線性表：鏈表 雙向鏈表5、復雜數(shù)據(jù)結構樹（Tree）與線性表不同，每個節(jié)點的后續(xù)可能大于1個。樹(Tree)的定義樹是n（n=0）個節(jié)點的有限集合，有且僅有一個稱為根的節(jié)點；當n1時，其余節(jié)點可以分為m個互不相交的集合，其中每個集合又是一棵樹，稱為樹的子樹遞歸的定義現(xiàn)實世界中的樹家譜目錄5、復雜數(shù)據(jù)結構樹（Tree）樹的示例ABCDE節(jié)點(Node)節(jié)點的度(Degree)葉子（終端節(jié)點

42、）非終端節(jié)點樹的深度孩子(Child)雙親(Parent)兄弟(Sibling)5、復雜數(shù)據(jù)結構樹（Tree）：樹的相關概念InitiateRootParentChildRight_SiblingLeft_SiblingCreateTreeInsertChildDeleteChildTraverseClear5、復雜數(shù)據(jù)結構樹（Tree）：樹的操作二叉樹(Binary Tree)每個節(jié)點最多只有兩棵子樹，并且子樹有左右之分，不能任意互換二叉樹的五種形態(tài)空只有根只有左子樹只有右子樹左右子樹均不空5、復雜數(shù)據(jù)結構樹（Tree）：二叉樹第I層上最多有2I-1個節(jié)點深度為K的二叉樹最多有2k - 1個

43、節(jié)點對于任意一個二叉樹，如果其葉子（終端節(jié)點）數(shù)目為n0，度為2的節(jié)點數(shù)目為n2，有n0 = n2 + 1完全二叉樹與滿二叉樹5、復雜數(shù)據(jù)結構樹（Tree）：二叉樹的性質(zhì)完全二叉樹滿二叉樹具有n個節(jié)點的完全二叉樹的深度為log2n+1N個節(jié)點的完全二叉樹，按照從頂?shù)降?，從左到右的順序編號?-N)如果I=1，根節(jié)點如果I1，則雙親為I/2如果2*IN，則節(jié)點I無左孩子，否則左孩子為2*I如果2*I+1N，則節(jié)點I無右孩子，否則右孩子為2*I+15、復雜數(shù)據(jù)結構樹（Tree）：二叉樹的性質(zhì)A+B*(C-D)-E/F-/+*A-BDCFE5、復雜數(shù)據(jù)結構樹（Tree）：二叉樹的應用（表達式）與樹和

44、線性表不同，每個元素都可能與其它元素有關系。形式化定義Graph = (V, R)頂點，V是頂點的集合R是兩個頂點之間關系的集合如果屬于R，則表示一條弧5、復雜數(shù)據(jù)結構圖（Graph）弧頭，弧尾無向圖、邊頂點數(shù)目、邊的數(shù)目完全圖、有向完全圖權網(wǎng)絡子圖5、復雜數(shù)據(jù)結構圖（Graph）：相關概念1243V = V1, V2, V3, V4A = , , , 5、復雜數(shù)據(jù)結構圖（Graph）：例子鄰接點依附相關聯(lián)頂點的度出度入度5、復雜數(shù)據(jù)結構圖（Graph）：其他概念路徑，回路和環(huán)連通連通圖 連通分量生成樹生成森林頂點定位取頂點求第一個鄰接點求下一個鄰接點插入頂點插入弧刪除頂點刪除弧5、復雜數(shù)據(jù)結構圖（Graph）：圖的操作數(shù)據(jù)類型（數(shù)據(jù)）DataType節(jié)點（關系、自身行為）Node容器（行為）數(shù)據(jù)結構（Queue）5、復雜數(shù)據(jù)結構設計與實現(xiàn)5、復雜數(shù)據(jù)結構設計與實現(xiàn)class DataType class Node DataType data; /結點之間的關系 /Node preNode; /Node nextNode; /Node leftNode; /Node rightNode; /結點自身的行為 void setData(DataType d) DataType getData()