數(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)唯一存儲(chǔ)結(jié)構(gòu)不唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴(lài)運(yùn)算的實(shí)現(xiàn)依賴(lài)于存儲(chǔ)結(jié)構(gòu)于存儲(chǔ)結(jié)構(gòu)線性表線性表邏 輯 結(jié)邏 輯 結(jié)構(gòu)構(gòu)存 儲(chǔ) 結(jié)存 儲(chǔ) 結(jié)構(gòu)構(gòu)基基本本概概念念抽象抽象數(shù)據(jù)數(shù)據(jù)類(lèi)型類(lèi)型定義定義線性表定義線性表定義邏輯特征邏輯特征ADTADT定義定義基本操作基本操作順順序序存存儲(chǔ)儲(chǔ)鏈鏈接接存存儲(chǔ)儲(chǔ)其其他他存存儲(chǔ)儲(chǔ)順序表的特點(diǎn)順序表的特點(diǎn)順序表類(lèi)定義順序表類(lèi)定義基本操作的實(shí)基本操作的實(shí)現(xiàn)及時(shí)間性能現(xiàn)及時(shí)間性能單鏈表的特點(diǎn)單鏈表的特點(diǎn)單鏈表類(lèi)定義單鏈表類(lèi)定義基本操作的實(shí)基本操作的實(shí)現(xiàn)及時(shí)間性能現(xiàn)及時(shí)間性能 比比 較較循環(huán)鏈表循環(huán)鏈表雙鏈表雙鏈表靜態(tài)

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

3、在表中的位置在表中的位置n n為元素總個(gè)為元素總個(gè)數(shù)，即數(shù)，即表長(zhǎng)表長(zhǎng)空表空表線性終點(diǎn)線性終點(diǎn)2.1 2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 例例1 分析分析26 個(gè)英文字母組成的英文表個(gè)英文字母組成的英文表 （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)2005011810205于春梅于春梅女女 182005級(jí)計(jì)信級(jí)計(jì)信016班班2005011810260何仕鵬何仕鵬男男 182005級(jí)計(jì)信級(jí)計(jì)信017班班2005011810284王王 爽爽女女 182005級(jí)通信級(jí)通信011班班2005011810360王亞武王亞武男男 182005級(jí)通信級(jí)通信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ù)元素的個(gè)數(shù)是有窮的。線性表中數(shù)據(jù)元素的個(gè)數(shù)是有窮的。2 2）. .相同性：相同性：線性表中數(shù)據(jù)元素的類(lèi)型是同一的。線性表中數(shù)據(jù)元素的類(lèi)型是同一的。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 無(wú)前驅(qū)，無(wú)前驅(qū)，a an n無(wú)后繼，其它每個(gè)元素有且無(wú)后繼，其它每個(gè)元素有且僅有一個(gè)前驅(qū)和一個(gè)后繼。僅有一個(gè)前驅(qū)和一個(gè)后繼。 練：判斷下列敘述的正誤：練：判斷下列敘述的正誤：1. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶(hù)按使用需要建立的。是用戶(hù)按使用需要建立的。2. 線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴(lài)于計(jì)線性表的邏輯結(jié)構(gòu)定義是唯一的，不依賴(lài)于計(jì)算機(jī)。算機(jī)。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é)點(diǎn)間的邏輯關(guān)系是一對(duì)一的。線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是一對(duì)一的。一維向量是線性表，但二維或一維向量是線性表，但二維或N維數(shù)組不是。維數(shù)組不是。5.“同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有同一數(shù)據(jù)邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素都具有相同的特性相同的特性”是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的是指數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)都相等。個(gè)數(shù)都相等。3、線性表的操作、線性表的操作線性表接口線性表接口LList聲明如下，描述線性表的取值、置聲明如下，描述線性表的取值、置值、插入、刪除等基本操作。值、插入、刪除等基本操作。package dataStructure.l

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

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

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

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

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

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

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

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

15、 index, E element); /在第在第index個(gè)位置個(gè)位置插入對(duì)象插入對(duì)象element public void clear(); /清空順序表清空順序表2 2）順序表的操作實(shí)現(xiàn)）順序表的操作實(shí)現(xiàn)( (即順序表類(lèi)的定義實(shí)現(xiàn)即順序表類(lèi)的定義實(shí)現(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、求順序表的長(zhǎng)度求順序表的長(zhǎng)度 public E get(int index) /返回返回index位置的對(duì)象位置的對(duì)象 public E set(int index, E element) /設(shè)置設(shè)置index位位置的對(duì)象為置的對(duì)象為element,若成功返回原對(duì)象，否則返回若成功返回原對(duì)象，否則返回null操作接口操作接口public boolean add(int index, E element); /在第在第index個(gè)位置插入對(duì)象個(gè)位置插入對(duì)象element插入前：插入前：(a0, , ai-1, ai, , an-1)插入后：插入后：(a0, , ai-1, item , ai,

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

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

19、ength) /若數(shù)組滿(mǎn)，則需要擴(kuò)充順序表容量若數(shù)組滿(mǎn)，則需要擴(kuò)充順序表容量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ā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化存儲(chǔ)位置要反映這個(gè)變化刪除操作實(shí)現(xiàn)刪除操作實(shí)現(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什么時(shí)候不能刪除什么時(shí)候不能刪除？實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： 獲得獲得index位置上要?jiǎng)h除的元素值位置上要?jiǎng)h除的元素值; 將位置為將位置為index 至至this.n-1的元素向前移動(dòng)一的元素向前移動(dòng)一個(gè)位置；個(gè)位置； 表長(zhǎng)減表長(zhǎng)減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;時(shí)間復(fù)雜度時(shí)間復(fù)雜度？O(1)2.2.3順序表的算法效率分析順序表的算法效率分析 插入、刪除算法時(shí)間主要耗費(fèi)在插入、刪除算法時(shí)間主要耗費(fèi)在移動(dòng)元素移動(dòng)元素的操作的操作 T(n)= O (移動(dòng)元素次數(shù)移動(dòng)元素次數(shù)) 移動(dòng)元素的次數(shù)取決于插入或刪除元素的位置。移動(dòng)元素的次數(shù)取決于插入或刪除元素的位置。討論討論1：若在長(zhǎng)度為若在長(zhǎng)度為 n 的線性表的第的線性表的第 i 位前位前 插入一元素，插入一元素，則向后移動(dòng)元素的次數(shù)則向后移動(dòng)元素的次數(shù)f(n)為為:f(n) =n i + 1時(shí)間效率分析時(shí)間效率分析:最好最好情況（情況（ i =n+1）：移動(dòng)元素

23、次數(shù)）：移動(dòng)元素次數(shù)0次，時(shí)間復(fù)雜度次，時(shí)間復(fù)雜度為為O(1)。最壞最壞情況（情況（ i =1）：移動(dòng)元素次數(shù)）：移動(dòng)元素次數(shù)n次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(n)。平均平均情況（情況（1in+1）：時(shí)間復(fù)雜度為）：時(shí)間復(fù)雜度為O(n)。 - - 11)=1(niiinp - - 11)=1(11niinn2nO(n) 討論討論2：若在長(zhǎng)度為若在長(zhǎng)度為n n的線性表上刪除第的線性表上刪除第i i位元素，向位元素，向前移動(dòng)元素的次數(shù)前移動(dòng)元素的次數(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）：移動(dòng)元素次數(shù)）：移動(dòng)元素次數(shù)0次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(1)。最壞最壞情況（情況（ i =1）：移動(dòng)元素次數(shù)）：移動(dòng)元素次數(shù)n-1次，時(shí)間復(fù)雜度次，時(shí)間復(fù)雜度為為O(n)。平均平均情況（情況（1in）：時(shí)間復(fù)雜度為）：時(shí)間復(fù)雜度為O(n)。 - - 1)=(niiinp - - 1)=(1niinn2n-1O(n) 數(shù)據(jù)結(jié)構(gòu)（Java版）（第2版）【例2.1】 使用順序表類(lèi)求解約瑟夫環(huán)問(wè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()