數(shù)據(jù)結(jié)構(gòu)java課件

1、數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容邏輯結(jié)構(gòu)唯一邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴運算的實現(xiàn)依賴于存儲結(jié)構(gòu)于存儲結(jié)構(gòu)線性表線性表邏 輯 結(jié)邏 輯 結(jié)構(gòu)構(gòu)存 儲 結(jié)存 儲 結(jié)構(gòu)構(gòu)基基本本概概念念抽象抽象數(shù)據(jù)數(shù)據(jù)類型類型定義定義線性表定義線性表定義邏輯特征邏輯特征ADTADT定義定義基本操作基本操作順順序序存存儲儲鏈鏈接接存存儲儲其其他他存存儲儲順序表的特點順序表的特點順序表類定義順序表類定義基本操作的實基本操作的實現(xiàn)及時間性能現(xiàn)及時間性能單鏈表的特點單鏈表的特點單鏈表類定義單鏈表類定義基本操作的實基本操作的實現(xiàn)及時間性能現(xiàn)及時間性能 比比 較較循環(huán)鏈表循環(huán)鏈表雙鏈表雙鏈表靜態(tài)

2、鏈表靜態(tài)鏈表線性表的應(yīng)用線性表的應(yīng)用 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 線性表的順序存儲及實現(xiàn)線性表的順序存儲及實現(xiàn) 線性表的鏈接存儲及實現(xiàn)線性表的鏈接存儲及實現(xiàn) 順序表和單鏈表的比較順序表和單鏈表的比較 線性表的其他存儲及實現(xiàn)線性表的其他存儲及實現(xiàn)本章的基本內(nèi)容是：本章的基本內(nèi)容是：（a1, a2, ai-1，ai, ai1 ，, an）1. 線性表的定義：線性表的定義：n(n0)個個相同類型數(shù)據(jù)元相同類型數(shù)據(jù)元素素的有限序列。的有限序列。n=0時稱為時稱為數(shù)據(jù)元素數(shù)據(jù)元素線性起點線性起點ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號，表示元素序號，表示元素

3、在表中的位置在表中的位置n n為元素總個為元素總個數(shù)，即數(shù)，即表長表長空表空表線性終點線性終點2.1 2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 例例1 分析分析26 個英文字母組成的英文表個英文字母組成的英文表 （ A, B, C, D, , Z）學(xué)號學(xué)號姓名姓名性別性別年齡年齡班級班級2005011810205于春梅于春梅女女 182005級計信級計信016班班2005011810260何仕鵬何仕鵬男男 182005級計信級計信017班班2005011810284王王 爽爽女女 182005級通信級通信011班班2005011810360王亞武王亞武男男 182005級通信級通信012班班：

4、 ：例例2 分析學(xué)生情況登記表分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性元素間關(guān)系是線性數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母; 元素間關(guān)系是線性的。元素間關(guān)系是線性的。a1a3a4ana22、線性表的、線性表的特性特性1 1）. .有限性：有限性：線性表中數(shù)據(jù)元素的個數(shù)是有窮的。線性表中數(shù)據(jù)元素的個數(shù)是有窮的。2 2）. .相同性：相同性：線性表中數(shù)據(jù)元素的類型是同一的。線性表中數(shù)據(jù)元素的類型是同一的。3 3）. .順序性：順序性：線性表中相鄰的數(shù)據(jù)元素線性表中相鄰的數(shù)據(jù)元素a ai i-1-1和和a ai i之間之間存在序偶關(guān)系存在序偶關(guān)系 ，即，即a ai i-1-

5、1是是a ai i的前驅(qū)，的前驅(qū)， a ai i是是a ai i- -1 1的后繼；的后繼；a a1 1 無前驅(qū)，無前驅(qū)，a an n無后繼，其它每個元素有且無后繼，其它每個元素有且僅有一個前驅(qū)和一個后繼。僅有一個前驅(qū)和一個后繼。 練：判斷下列敘述的正誤：練：判斷下列敘述的正誤：1. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立的。是用戶按使用需要建立的。2. 線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴于計線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴于計算機。算機。3. 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系的數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種關(guān)系

6、的數(shù)據(jù)元素的全體。數(shù)據(jù)元素的全體。4. 線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的。線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是一對一的。一維向量是線性表，但二維或一維向量是線性表，但二維或N維數(shù)組不是。維數(shù)組不是。5.“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的是指數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)都相等。個數(shù)都相等。3、線性表的操作、線性表的操作線性表接口線性表接口LList聲明如下，描述線性表的取值、置聲明如下，描述線性表的取值、置值、插入、刪除等基本操作。值、插入、刪除等基本操作。package dataStructure.l

7、inearList;/聲明屬于的包聲明屬于的包public interface LList/純性表接口純性表接口boolean isEmpty();/判斷線性表是否為空，若空返回判斷線性表是否為空，若空返回trueint length(); /返回線性表長度；返回線性表長度；E get(int index);/返回序號為返回序號為index的對象，的對象，index初值為初值為0BACKBACKE set(int index, E element);/設(shè)置序號為設(shè)置序號為indexindex對象為對象為elementelement，返回原對象，返回原對象boolean add(int inde

8、x, E element);/插入插入elementelement對象，插入后對象序號為對象，插入后對象序號為indexindexboolean add(E element);/插入插入elementelement對象，插入位置沒有約定對象，插入位置沒有約定E remove(int index);/移去序號為移去序號為index的對象，返回被移動對象的對象，返回被移動對象void clear();/清空線性表；清空線性表；進一步說明進一步說明: :（1 1）線性表的基本操作根據(jù)實際應(yīng)用是而定；）線性表的基本操作根據(jù)實際應(yīng)用是而定；（2 2）復(fù)雜的操作可以通過基本操作的組合來實現(xiàn)；）復(fù)雜的操作可

9、以通過基本操作的組合來實現(xiàn)；（3 3）對不同的應(yīng)用，操作的接口可能不同。）對不同的應(yīng)用，操作的接口可能不同。BACK2.2 2.2 線性表的順序存儲和實現(xiàn)線性表的順序存儲和實現(xiàn)2.2.1 順序表的順序存儲表示順序表的順序存儲表示2.2.2 順序表的實現(xiàn)順序表的實現(xiàn)2.2.3 順序表的算法效率分析順序表的算法效率分析本節(jié)小結(jié)本節(jié)小結(jié)2.2.1順序表的順序存儲表示順序表的順序存儲表示用一組用一組地址連續(xù)地址連續(xù)的存儲單元依的存儲單元依次存儲線性表的元素，可通過靜態(tài)次存儲線性表的元素，可通過靜態(tài)數(shù)組數(shù)組VnVn或動態(tài)數(shù)組或動態(tài)數(shù)組來實現(xiàn)。來實現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲把邏輯上相鄰的數(shù)據(jù)元素存儲在

10、物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。在物理上相鄰的存儲單元中的存儲結(jié)構(gòu)。線性表的順序表示又稱為線性表的順序表示又稱為順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)或或順序映像順序映像。順序存儲定義：順序存儲定義：順序存儲方法順序存儲方法：簡言之，邏輯上相鄰，物理上也相鄰簡言之，邏輯上相鄰，物理上也相鄰“順序表順序表是一種是一種隨機存取隨機存取的的存儲存儲結(jié)構(gòu)結(jié)構(gòu)”的含義為：查的含義為：查找操作，其時間性能為找操作，其時間性能為O(1)。線性表順序存儲特點：線性表順序存儲特點：1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2. 若已知表中首元素在存儲器中的位置，則其他若已知表中首元素

11、在存儲器中的位置，則其他元素存放位置亦可求出（元素存放位置亦可求出（利用數(shù)組下標(biāo)利用數(shù)組下標(biāo)）。計算方）。計算方法是（法是（參見存儲結(jié)構(gòu)示意圖參見存儲結(jié)構(gòu)示意圖）：）：設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為LOC(a0)（稱為稱為首地址首地址），），設(shè)每個元素占用存儲空間（地址長度）為設(shè)每個元素占用存儲空間（地址長度）為c字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存放地址存放地址為：為： LOC(ai) = LOC(a0) + i*c LOC(ai+1) = LOC(a0)+ (i+1)*c 注意：注意：JAVAJAVA語言中的數(shù)組的下標(biāo)從語言中的數(shù)組的下標(biāo)從0 0開始，開始，

12、 即：即：VnVn的有效范圍是的有效范圍是V0V0Vn-1Vn-1線性表的順序存儲結(jié)構(gòu)示意圖線性表的順序存儲結(jié)構(gòu)示意圖ciaLocaLoci)()(0一個一維數(shù)組，下標(biāo)的范圍是到，一個一維數(shù)組，下標(biāo)的范圍是到，每個數(shù)組元素用相鄰的每個數(shù)組元素用相鄰的個字節(jié)個字節(jié)存儲。存儲存儲。存儲器按字節(jié)編址，設(shè)存儲數(shù)組元素器按字節(jié)編址，設(shè)存儲數(shù)組元素 的第的第一個字節(jié)的地址是一個字節(jié)的地址是，則，則 的第一個的第一個字節(jié)的地址是字節(jié)的地址是 113例例3、因此：因此：LOC( M3 ) = 98 + 35=113解：解：地址計算通式為：地址計算通式為：ciaLocaLoci)()(02.2.2 順序表的實現(xiàn)

13、順序表的實現(xiàn)1 1）順序表的存儲結(jié)構(gòu)定義）順序表的存儲結(jié)構(gòu)定義( (即順序表類的聲明即順序表類的聲明) )：package dataStructure.linearlist;import dataStructure.linearlist.Llist;public class SeqList implements Llist/順序表類順序表類SeqList，實現(xiàn)線性表接口，實現(xiàn)線性表接口 private Object table; /對象數(shù)據(jù)，私有成員對象數(shù)據(jù)，私有成員 private int n; /順序表的長度順序表的長度 public SeqList( ); /指定空表的默認(rèn)容量指定空表的

14、默認(rèn)容量 public SeqList(int capacity); /創(chuàng)建指定容量的空表創(chuàng)建指定容量的空表 public boolean isEmpty()；/判斷順序表是否為空判斷順序表是否為空 public int length(); /求順序表的長度求順序表的長度 public E get(int index) /返回返回index位置的對象位置的對象 public E set(int index, E element) /設(shè)置設(shè)置index位置的對象為位置的對象為element,若成功返回原對象，否則返回若成功返回原對象，否則返回null public boolean add(int

15、 index, E element); /在第在第index個位置個位置插入對象插入對象element public void clear(); /清空順序表清空順序表2 2）順序表的操作實現(xiàn)）順序表的操作實現(xiàn)( (即順序表類的定義實現(xiàn)即順序表類的定義實現(xiàn)P51-53)P51-53)： public SeqList( ); /指定空表的默認(rèn)容量指定空表的默認(rèn)容量 public SeqList(int capacity); /創(chuàng)建指定容量創(chuàng)建指定容量的空表的空表 public boolean isEmpty()；/判斷順序表是否判斷順序表是否為空為空 public int length(); /

16、求順序表的長度求順序表的長度 public E get(int index) /返回返回index位置的對象位置的對象 public E set(int index, E element) /設(shè)置設(shè)置index位位置的對象為置的對象為element,若成功返回原對象，否則返回若成功返回原對象，否則返回null操作接口操作接口public boolean add(int index, E element); /在第在第index個位置插入對象個位置插入對象element插入前：插入前：(a0, , ai-1, ai, , an-1)插入后：插入后：(a0, , ai-1, item , ai,

17、, an-1)插入操作實現(xiàn)插入操作實現(xiàn)ai-1和和ai之間的邏輯關(guān)系發(fā)生了變化之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化存儲位置要反映這個變化插入操作圖示33例如：（例如：（35，12，24，42），在），在index=2的位置上的位置上插入插入33。表滿：表滿：this.n=table.length合理的插入位置：合理的插入位置：0indextable.length-1 435122442a0a1a2a30 1 2 3 4422412335什么時候不能插入什么時候不能插入？注意邊界條件注意邊界條件插入：插入：在順序表的第在順

18、序表的第indexindex個位置個位置插入插入一個元素一個元素實現(xiàn)步驟：實現(xiàn)步驟： 將第將第n-1至第至第index位的元素向后移動一個位置；位的元素向后移動一個位置； 將要插入的元素寫到第將要插入的元素寫到第index個位置；個位置； 表長加表長加1。注意：注意：事先應(yīng)判斷事先應(yīng)判斷: 插入位置插入位置index是否合法是否合法? 表是否已滿表是否已滿? JAVA具體實現(xiàn)：具體實現(xiàn)：public boolean add(int index, E element) if (element=null) return false; /不能插入不能插入null if (this.n=table.l

19、ength) /若數(shù)組滿，則需要擴充順序表容量若數(shù)組滿，則需要擴充順序表容量Object temp=this.table; this.table=new Objecttemp.length*2; for (int i=0;itemp.length;i+)/復(fù)制數(shù)組元素復(fù)制數(shù)組元素this.tablei=tempi; if (indexthis.n) index=this.n; for (int j=this.n-1;j=index;j-)/元素后移元素后移this.tablej+1=this.tablej; this.tableindex=element; this.n+; return tr

20、ue;操作接口操作接口public E remove(int index x)刪除前：刪除前：(a1, , ai-1,ai,ai+1,an)刪除后：刪除后：(a1,ai-1,ai+1, ,an) ai-1和和ai之間的邏輯關(guān)系發(fā)生了變化之間的邏輯關(guān)系發(fā)生了變化順序存儲要求存儲位置反映邏輯關(guān)系順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化存儲位置要反映這個變化刪除操作實現(xiàn)刪除操作實現(xiàn)刪除操作圖示例：（例：（35, 33, 12, 24, 42），刪除），刪除index=2的數(shù)據(jù)元的數(shù)據(jù)元素。素。 535a1a2a3a40 1 2 3 4422412334a5122442表空：表空： th

21、is.n=0合理的刪除位置：合理的刪除位置：0indexthis.n什么時候不能刪除什么時候不能刪除？實現(xiàn)步驟：實現(xiàn)步驟： 獲得獲得index位置上要刪除的元素值位置上要刪除的元素值; 將位置為將位置為index 至至this.n-1的元素向前移動一的元素向前移動一個位置；個位置； 表長減表長減1。注意：注意：事先需要判斷，事先需要判斷，刪除位置刪除位置index是否合法是否合法?應(yīng)當(dāng)有應(yīng)當(dāng)有0index=0 & indexthis.n) E old=(E) this.tableindex; for (int j=index;j=0 & indexthis.n) return (E)this.

22、tableindex; return null;時間復(fù)雜度時間復(fù)雜度？O(1)2.2.3順序表的算法效率分析順序表的算法效率分析 插入、刪除算法時間主要耗費在插入、刪除算法時間主要耗費在移動元素移動元素的操作的操作 T(n)= O (移動元素次數(shù)移動元素次數(shù)) 移動元素的次數(shù)取決于插入或刪除元素的位置。移動元素的次數(shù)取決于插入或刪除元素的位置。討論討論1：若在長度為若在長度為 n 的線性表的第的線性表的第 i 位前位前 插入一元素，插入一元素，則向后移動元素的次數(shù)則向后移動元素的次數(shù)f(n)為為:f(n) =n i + 1時間效率分析時間效率分析:最好最好情況（情況（ i =n+1）：移動元素

23、次數(shù)）：移動元素次數(shù)0次，時間復(fù)雜度次，時間復(fù)雜度為為O(1)。最壞最壞情況（情況（ i =1）：移動元素次數(shù)）：移動元素次數(shù)n次，時間復(fù)雜度為次，時間復(fù)雜度為O(n)。平均平均情況（情況（1in+1）：時間復(fù)雜度為）：時間復(fù)雜度為O(n)。 - - 11)=1(niiinp - - 11)=1(11niinn2nO(n) 討論討論2：若在長度為若在長度為n n的線性表上刪除第的線性表上刪除第i i位元素，向位元素，向前移動元素的次數(shù)前移動元素的次數(shù)f(n)f(n)為：為： f(n) =f(n) = n i討論討論3 3：順序表的插入、刪除操作算法順序表的插入、刪除操作算法空間空間復(fù)雜度復(fù)雜度

24、S(n)=O(1)S(n)=O(1)最好最好情況（情況（ i =n）：移動元素次數(shù)）：移動元素次數(shù)0次，時間復(fù)雜度為次，時間復(fù)雜度為O(1)。最壞最壞情況（情況（ i =1）：移動元素次數(shù)）：移動元素次數(shù)n-1次，時間復(fù)雜度次，時間復(fù)雜度為為O(n)。平均平均情況（情況（1in）：時間復(fù)雜度為）：時間復(fù)雜度為O(n)。 - - 1)=(niiinp - - 1)=(1niinn2n-1O(n) 數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）【例2.1】 使用順序表類求解約瑟夫環(huán)問題。public class Josephusprivate LListlist; public Josephus (int number, int start, int distance) this.list=new SeqlList(number); for (int i=0;i1) index=(index+distance-1)%this.list.length(); System.out.print(“刪除“+this.list.remove(index).toString()+”); System.out.println(this.list.toString()