數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料,java數(shù)據(jù)結(jié)構(gòu)期末考試

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)資料,java數(shù)據(jù)結(jié)構(gòu)期末考試其次章算法分析

1.算法分析是計(jì)算機(jī)科學(xué)的基礎(chǔ)

2.增長函數(shù)表示問題（n）大小與我們希翼最優(yōu)化的值之間的關(guān)系。該函數(shù)表示了該算法的時(shí)光復(fù)雜度或空間復(fù)雜度。增長函數(shù)表示與該問題大小相對(duì)應(yīng)的時(shí)光或空間的使用

3.漸進(jìn)復(fù)雜度：隨著n的增強(qiáng)時(shí)增長函數(shù)的普通性質(zhì)，這一特性基于該表達(dá)式的主項(xiàng)，即n增強(qiáng)時(shí)表達(dá)式中增長最快的那一項(xiàng)。

4.漸進(jìn)復(fù)雜度稱為算法的階次，算法的階次是忽視該算法的增長函數(shù)中的常量和其他次要項(xiàng)，只保留主項(xiàng)而得出來的。算法的階次為增長函數(shù)提供了一個(gè)上界。

5.漸進(jìn)復(fù)雜度：增長函數(shù)的界限，由增長函數(shù)的主項(xiàng)確定的。漸進(jìn)復(fù)雜度類似的函數(shù)，歸為相同類型的函數(shù)。

6.惟獨(dú)可運(yùn)行的語句才會(huì)增強(qiáng)時(shí)光復(fù)雜度。

7.O()或者大O記法：與問題大小無關(guān)、執(zhí)行時(shí)光恒定的增長函數(shù)稱為具有O（1）的復(fù)雜度。

增長函數(shù)階次

t(n)=17O(1)

t(n)=3lognO(logn)

t(n)=20n-4O(n)

t(n)=12nlogn+100nO(nlogn)

t(n)=3n2+5n-2O(n2)

t(n)=8n3+3n2O(n3)

t(n)=2n+18n2+3nO(2n)

8.全部具有相同階次的算法，從運(yùn)行效率的角度來說都是等價(jià)的。

9.假如算法的運(yùn)行效率低，從長遠(yuǎn)來說，使用更快的處理器也無濟(jì)于事。

10.要分析循環(huán)運(yùn)行，首先要確定該循環(huán)體的階次n，然后用該循環(huán)要運(yùn)行的次數(shù)乘以它。（n表示的是問題的大?。?/p>

11.分析嵌套循環(huán)的復(fù)雜度時(shí)，必需將內(nèi)層和外層循環(huán)都考慮進(jìn)來。

12.辦法調(diào)用的復(fù)雜度分析：

如：publicvoidprintsum(intcount){

intsum=0;

for(intI=1;I冪函數(shù)增長>對(duì)數(shù)函數(shù)增長

第三章集合概述——棧

1.集合是一種聚攏、組織了其他對(duì)象的對(duì)象。它定義了一種特定的方式，可以拜訪、管理所包含的對(duì)象（稱為該集合的元素）。集合的使用者——通常是軟件系統(tǒng)中的另一個(gè)類或?qū)ο蟆荒芡ㄟ^這些預(yù)定的方式與該集合舉行交互。

2.集合可分為線性集合和非線性集合。線性集合是一種元素按直線方式組織的集合。非線性集合是一種元素按某種非直線方式組織的集合，例如按層次組織或按網(wǎng)狀組織。從這種意義上來說，非線性集合大概根本就沒有任何組織形式。

3.集合中的元素通常是根據(jù)它們添加到集合的挨次，或者是按元素之間的某種內(nèi)在關(guān)系來組織的。

4.抽象能躲藏某些細(xì)節(jié)。

5.集合是一種躲藏了實(shí)現(xiàn)細(xì)節(jié)的抽象。

6.對(duì)象是用于創(chuàng)建集合一種完善機(jī)制，由于只要設(shè)計(jì)正確，對(duì)象的內(nèi)部工作對(duì)系統(tǒng)其他部分而言是被封裝的。幾乎在全部狀況下，在類中定義的實(shí)例變量的可見性都應(yīng)聲明為私有的（private）。因此，惟獨(dú)該類的辦法才可以拜訪和修改這些變量。用戶與對(duì)象的唯一交互只能通過其公用辦法。公用辦法表示了對(duì)象所能提供的服務(wù)。

7.數(shù)據(jù)類型是一組值及作用于這些數(shù)值上的各種操作。

8.抽象數(shù)據(jù)類型（ADT）是一種在程序設(shè)計(jì)語言中尚未定義其值和操作的數(shù)據(jù)類型。ADT的抽象性體現(xiàn)在，ADT必需對(duì)其實(shí)現(xiàn)細(xì)節(jié)舉行定義，且對(duì)這些用戶是不行見的。因此，集合是一種抽象數(shù)據(jù)類型。

9.數(shù)據(jù)結(jié)構(gòu)是一種用于實(shí)現(xiàn)集合的基本編程結(jié)構(gòu)。

10.Java集合API（應(yīng)用程序編程接口）是一個(gè)類集，表示了一些特定類型的集合，這些類的實(shí)現(xiàn)方式各不相同。

11.棧的元素是根據(jù)后進(jìn)先出（LIFO）的方式舉行處理的，最后進(jìn)入棧中的元素最先被移出。棧是一種線性集合，元素的添加和刪除都在同一端舉行。在科學(xué)計(jì)算中，棧的基本使用就是用于顛倒挨次（如一個(gè)取消操作）。

12.通常垂直的繪制棧，棧的末端稱為棧的頂部，元素的添加和刪除在頂部舉行。

13.假如pop或者peek可作用于空棧，那么棧的任何實(shí)現(xiàn)都要拋出一個(gè)異樣。集合的作用不是去確定如何處理這個(gè)異樣，而是把它報(bào)告給使用該棧的應(yīng)用程序。在棧中沒有滿棧的概念，應(yīng)由棧來管理它自己的存儲(chǔ)空間。

14.棧的toString（）操作可以在不修改棧的狀況下遍歷和現(xiàn)實(shí)棧的內(nèi)容，對(duì)調(diào)試十分實(shí)用。

15.類型兼容性是指把一個(gè)對(duì)象賦給引用的特定賦值是否合法。

16.繼承就是通過某個(gè)現(xiàn)有類派生出一個(gè)新類的過程。多態(tài)：使得一個(gè)引用可以多次指向相關(guān)但不同的對(duì)象類型，且其中調(diào)用的辦法是在運(yùn)行時(shí)與代碼。多態(tài)引用是一個(gè)引用變量，它可以在不同地點(diǎn)引用不同類型的對(duì)象。繼承可用于創(chuàng)建一個(gè)類層次，其中，一個(gè)引用變量可用于只想與之相關(guān)的隨意對(duì)象。類層次：通過繼承創(chuàng)建的類之間的關(guān)系，某個(gè)類的子類可以成為其他類的父類

17.一個(gè)Object引用可用于引用隨意對(duì)象，由于全部類終于都是從Object類派生而來的。

18.泛型，用泛型定義類：使這個(gè)類能存儲(chǔ)、操作和管理在實(shí)例化之前沒有指定是何種類型的對(duì)象。

19.泛型不能被實(shí)例化。它只是一個(gè)占位符，允許我們?nèi)ザx管理特定類型的對(duì)象的類，且惟獨(dú)當(dāng)該類被實(shí)例化時(shí)，才創(chuàng)建該類的對(duì)象。

20.計(jì)算后綴表達(dá)式：從左到右掃描，把每個(gè)操作符應(yīng)用到其之前的兩個(gè)緊鄰操作數(shù)，并用該計(jì)算結(jié)果代替該操作符。

21.棧是用于計(jì)算后綴表達(dá)式的抱負(fù)數(shù)據(jù)結(jié)構(gòu)。

22.用棧計(jì)算后綴表達(dá)式時(shí)，操作數(shù)是作為一個(gè)Integer對(duì)象而不是作為一個(gè)int基本數(shù)值被壓入棧中的，這是由于棧被設(shè)計(jì)為存儲(chǔ)對(duì)象的。注重：第一個(gè)彈出的操作數(shù)是表達(dá)式的其次個(gè)操作數(shù)，其次個(gè)彈出的操作數(shù)是表達(dá)式的第一個(gè)操作數(shù)。

23.Javadoc解釋以/**開頭，以*/結(jié)束。Javadoc標(biāo)簽用于標(biāo)識(shí)特定類型的信息。@auther標(biāo)簽用于標(biāo)識(shí)編寫代碼的程序員。@version標(biāo)簽用于制定代碼的版本號(hào)。@return標(biāo)簽用于表明該辦法的返回值。@param標(biāo)簽用于標(biāo)識(shí)傳遞給該辦法的每個(gè)參數(shù)。

24.異樣就是一個(gè)對(duì)象，它被定義了一種非正?；蝈e(cuò)誤的狀況。異樣由程序或運(yùn)行時(shí)環(huán)境拋出，可以按預(yù)期的被捕捉或被正確處理。錯(cuò)誤與一場(chǎng)異樣類似，只不過錯(cuò)誤往往表示一種無法恢復(fù)的狀況，且不必去捕捉它。

25.接口的命名：用集合名+ADT來為集合接口命名。

26.取消操作通常是使用一種名為drop-out的棧來實(shí)現(xiàn)。它與棧唯一的不同是，它對(duì)存儲(chǔ)元素的數(shù)量有限制，一旦達(dá)到限制，假如有新元素要壓入，那么棧底的元素將從棧中被丟棄。

27.數(shù)組一旦創(chuàng)建好，其容量是不能轉(zhuǎn)變的。

28.處于運(yùn)行效率的考慮，賦予數(shù)組的棧實(shí)現(xiàn)總是使棧底位于數(shù)組的索引0處。

29.ArrayStack類有兩個(gè)構(gòu)造函數(shù)，一個(gè)使用的是默認(rèn)容量，一個(gè)使用的是制定容量。

30.構(gòu)造函數(shù)與成員辦法的區(qū)分：

a)構(gòu)造函數(shù)是初始化一個(gè)類的對(duì)象時(shí)調(diào)用，無返回值。名字與類名相同

b)成員函數(shù)由類對(duì)象主動(dòng)調(diào)用，使用點(diǎn)操作符（“.”），又返回值。

31.privateT[]stack;

Stack=(T[])(newObject[DEFAULT_CAPACITY]);

因?yàn)椴荒軐?shí)例化一個(gè)泛型對(duì)象，這里實(shí)例化了一個(gè)Object數(shù)組，然后將它轉(zhuǎn)換為一個(gè)泛型數(shù)組。

32.push（）

publicvoidpush(Telement){

if(size()==stack.length)

expandCapacity();

stack[top]=element;

top++;

}

33.pop（）

publicTpop()throwsEmptyCollectionException

{

if(isEmpty())

thrownewEmptyCollectionException("Stack");

top--;

Tresult=stack[top];

stack[top]=null;

returnresult;

}

34.peek（）

publicTpeek()throwsEmptyCollectionException{

if(isEmpty())

thrownewEmptyCollectionException("Stack");

returnstack[top-1];}

35.privatevoidexpandCapacity(){

T[]larger=(T[])(newObject[stack.length*2]);

for(intindex=0;indextemp=newLinearNode(element);

temp.setNext(top);

top=temp;

count++;

}

b)Pop：

publicTpop()throwsEmptyCollectionException{

if(isEmpty())

thrownewEmptyCollectionException("stack");

Tresult=top.getElement();

top=top.getNext();

count--;

returnresult;

}

第五章隊(duì)列

1.隊(duì)列是一種線性集合，其元素從一端加入，另一端刪除。因此，隊(duì)列元素是按先進(jìn)先出（FIFO）方式處理的。從隊(duì)列中刪除元素的次序，與往隊(duì)列中放置元素的次序是一樣的。元素都是從隊(duì)列末端（rear）進(jìn)入，從隊(duì)列前端（front）退出。

2.用鏈表實(shí)現(xiàn)棧：

a)隊(duì)列和棧的主要區(qū)分在于，隊(duì)列中我們必需要操作鏈表的兩端。因此需要兩個(gè)引用

分離指向鏈表的首、末元素。

b)對(duì)于單向鏈表，可挑選從末端入列，先前端出列。

c)雙向鏈表可以解決需要遍歷鏈表的問題，因此在雙向鏈表實(shí)現(xiàn)中，無所謂在哪端入

列和出列。

d)對(duì)于一個(gè)空隊(duì)列，head和tail引用都為null，count為0。隊(duì)列中惟獨(dú)一個(gè)元素時(shí)，

head和tail引用都會(huì)指向這個(gè)對(duì)象。

e)Enqueue：將新元素放到鏈表末端

publicvoidenqueue(Telement){

LinearNodenode=newLinearNode(element);

if(isEmpty())

head=node;

else

tail.setNext(node);

tail=node;

count++;

}

f)Dequeue

publicTdequeue()throwsEmptyCollectionException{if(isEmpty())

thrownewEmptyCollectionException("queue");Tresult=head.getElement();head=head.getNext();count--;

if(isEmpty())tail=null;

returnresult;}

3.用數(shù)組實(shí)現(xiàn)隊(duì)列：

a)因?yàn)殛?duì)列操作會(huì)修改集合的兩端，因此將一端固定于索引0出要求移動(dòng)元素。b)非環(huán)形數(shù)組實(shí)現(xiàn)的元素位移，將產(chǎn)生O（n）的復(fù)雜度。

c)把數(shù)組看作是環(huán)形的，可以除去在隊(duì)列的數(shù)組實(shí)現(xiàn)中元素的移位需要。d)環(huán)形數(shù)組：假如數(shù)組的最后一個(gè)索引后面跟的是第一個(gè)索引，那么該數(shù)組就可用作

環(huán)形數(shù)組。

e)用兩個(gè)整數(shù)值表示隊(duì)列的前端和末端。front的值表示的是隊(duì)列的首元素存儲(chǔ)的位

置，rear的值表示的是數(shù)組下一個(gè)可用單元（不是最后一個(gè)元素儲(chǔ)存的位置），此時(shí)rear的值不在表示隊(duì)列元素的數(shù)目了。f)Enqueue：

publicvoidenqueue(Telement){if(size()==queue.length)expendCapacity();queue[rear]=element;

rear=(rear+1)%queue.length;count++;}

注重：環(huán)形增強(qiáng)

rear=(rear+1)%queue.length;

e)Dequeue:

publicTdequeue()throwsEmptyCollectionException{if(isEmpty())

thrownewEmptyCollectionException("queue");Tresult=queue[front];queue[rear]=null;

front=(front+1)%queue.length;count--;

returnresult;}

4.隊(duì)列是一種可存儲(chǔ)重復(fù)編碼密鑰的方便集合。

正常增強(qiáng)

適當(dāng)?shù)臅r(shí)候，繞回到0

5.隊(duì)列的鏈表實(shí)現(xiàn)中，head和tail引用相等的狀況：

a)隊(duì)列為空：head和tail都為null

b)隊(duì)列中惟獨(dú)一個(gè)元素

6.隊(duì)列的環(huán)形數(shù)組實(shí)現(xiàn)中，front和rear引用相等的狀況：

a)隊(duì)列為空

b)隊(duì)列為滿

7.dequeue操作復(fù)雜度為O(n)的非環(huán)形數(shù)組實(shí)現(xiàn)的時(shí)光復(fù)雜度最差

8.環(huán)形數(shù)組和非環(huán)形數(shù)組都會(huì)因未填充元素而鋪張空間。鏈表實(shí)現(xiàn)中的每個(gè)存儲(chǔ)元素都會(huì)占用更多的空間。

第六章列表

1.鏈表和列表集合之間的差別：

a)鏈表是一種實(shí)現(xiàn)策略，使用引用來在對(duì)象之間創(chuàng)建鏈接，如前面用鏈表來實(shí)現(xiàn)了棧

和隊(duì)列集合。

b)列表集合是一種概念性表示法，其思想是使事物以線性列表的方式舉行組織。就像

棧和隊(duì)列一樣，列表也可以使用鏈表或數(shù)組來實(shí)現(xiàn)。

2.列表集合沒有內(nèi)在的容量大小，它可以隨著需要增大。

3.棧和隊(duì)列都是線性結(jié)構(gòu)，可以像列表那樣舉行思量，但元素只能在末端添加和刪除。列表集合更普通化，可以在列表的中間和末端添加和刪除元素。Inotherwords,棧和隊(duì)列都屬于列表，列表可隨意操作。

4.列表可分為：

a)有序列表：其元素根據(jù)元素的某種內(nèi)在特性舉行排序；

b)無序列表：其元素間不具有內(nèi)在挨次，元素根據(jù)它們?cè)诹斜碇械奈恢门e行排序。

c)索引列表：其元素可以用數(shù)字索引來引用。

5.有序列表是基于列表中元素的某種內(nèi)在特征的。列表基于某個(gè)關(guān)鍵值排序。對(duì)于任何已添加到有序列表中的元素，只要給定了元素的關(guān)鍵值，同時(shí)已經(jīng)定義了元素的全部關(guān)鍵值，那么它在列表中就會(huì)有一個(gè)固定的位置。

6.無序列表中各元素的位置并不基于元素的任何內(nèi)在特性。但列表中的元素是根據(jù)特別挨次放置著，只不過這種挨次與元素本身無關(guān)。列表的使用者會(huì)打算元素的挨次。無序列表的新元素可以加到列表的前端、后端，或者插到某個(gè)特定元素之后。

7.索引列表與無序列表類似，各元素間也不存在能夠打算它們?cè)诹斜碇械陌ご蔚膬?nèi)在關(guān)系。列表的使用者打算了元素的挨次。除此之外，索引列表的每個(gè)元素都能夠從一個(gè)數(shù)字索引值得到引用，該索引值從列表頭開頭從0延續(xù)增強(qiáng)直到列表末端。索引列表的新元素可以加到列表的任一位置，包括列表的前端和后端。每當(dāng)列表發(fā)生轉(zhuǎn)變，索引值就相應(yīng)調(diào)節(jié)以保持挨次和延續(xù)性。索引列表為它的元素維護(hù)一段延續(xù)的數(shù)字索引值。

8.索引列表和數(shù)組的根本區(qū)分在于：索引列表的索引值總是延續(xù)的。假如刪除了一個(gè)元素，其他元素的位置會(huì)像“坍塌”了一樣消退產(chǎn)生的空隙。當(dāng)插入一個(gè)元素時(shí)，其他元素的索引將舉行位移以騰出位置。

9.列表有可能既是有序列表，又是索引列表，但這種設(shè)計(jì)沒有什么意義。

10.Java集合API中的列表：

a)Java集合API提供的列表類只要是支持索引列表。在一定程度上，這些類與無序

列表是重疊的。

i.注重：javaAPI并沒有任何類能直接實(shí)現(xiàn)以上描述的有序列表。

b)List接口：

add(Eelement)往列表的末端添加一個(gè)元素

add（intindex,Eelement）在指定索引處插入一個(gè)元素

get（intindex）返回指定索引處的元素

remove(intindex)刪除指定索引處的元素

remove（EObject）刪除制定對(duì)象的第一個(gè)浮現(xiàn)

set（intindex，Eelement）替代指定索引處的元素

size（）返回列表中的元素?cái)?shù)目

11.數(shù)組實(shí)現(xiàn)列表：使用環(huán)形數(shù)組辦法，但當(dāng)從列表中間插入或者刪除元素時(shí)，仍需移動(dòng)元素。

a)Remove操作：

publicTremove(Telement)throwsElementNotFoundException{Tresult;

intindex=find(element);

if(index==NOT_FOUND)

thrownewElementNotFoundException("ArrayList");

result=list[index];

rear--;

for(intscan=index;scantemp=(Comparable)element;

intscan=0;

while(scanscan;scan2--)

list[scan2]=list[scan2-1];

list[scan]=element;

rear++;

}

注重：

復(fù)雜度為O（n）。

惟獨(dú)Comparable對(duì)象才干存儲(chǔ)在有序列表中。

e）Comparable接口定義了compareTo辦法，當(dāng)執(zhí)行對(duì)象為小于、等于或者大于傳入?yún)?shù)時(shí)，該辦法將分離返回一個(gè)負(fù)整數(shù)、0或者一個(gè)正整數(shù)。

無序列表和索引列表不要求它們所存儲(chǔ)的元素是Comparable的。

f）無序列表的操作

publicvoidaddAfter(Telement,Ttarget){

if(size()==list.length)

expandCapacity();

intscan=0;

while(scanscan+1;i--)

list[i]=list[i-1];

list[scan+1]=element;

rear++;

}

publicvoidaddToFront(Telement){

if(size()==list.length)

expandCapacity();

for(inti=rear;iprevious=null;

LinearNodecurrent=head;

while(current!=null

else

{previous=current;

current=current.getNext();

}

if(!found)

thrownewElementNotFoundException("List");

if(size()==1)

head=tail=null;

elseif(current.equals(head))

head=current.getNext();

elseif(current.equals(tail))

{tail=previous;

tail.setNext(null);

}

else

previous.setNext(current.getNext());

count--;

returncurrent.getElement();

}

b)有序列表的add操作（僅供參考）

publicclassLinkedOrderedList42>extendsLinkedList42implements

OrderedListADT{

@Override

publicvoidadd(Telement){

LinearNodenode=newLinearNode(element);

LinearNodetemp=head;

LinearNodetemp0=temp;

if(isEmpty()){

head=tail=node;

count++;

}

else{

if(size()==1){

if(head.getElement().compareTo(element)>0){

node.setNext(head);

head=node;

count++;

}else{

head.setNext(node);

tail=node;

count++;

}

}elseif(head.getElement().compareTo(element)>=0){node.setNext(head);

head=node;

count++;

}

else{

while(temp!=tail&&

temp.getElement().compareTo(element)extendsLinkedList42implementsUnorderedListADT{

@Override

publicvoidaddToFront(Telement){

LinearNodeNew=newLinearNode(element);

if(count==0){

tail=New;

head=New;

count++;

}

else{

New.setNext(head);

head=New;

count++;

}

}

@Override

publicvoidaddToRear(Telement){

LinearNodeNew=newLinearNode(element);

if(count==0){

tail=New;

}else{

tail.setNext(New);

tail=New;

}

count++;

}

@Override

publicvoidaddAfter(Telement,Ttarget){

LinearNodeNew=newLinearNode(element);

LinearNodecurrent=head;

if(contains(targ