《數(shù)據(jù)結(jié)構(gòu)與算法項(xiàng)目化教程》課件第2章

學(xué)習(xí)情境２線性表2.1任務(wù)一認(rèn)識線性表2.2任務(wù)二程序?qū)崿F(xiàn)線性表的順序存儲結(jié)構(gòu)及操作2.3任務(wù)三程序?qū)崿F(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及操作2.4任務(wù)四線性表的應(yīng)用——解決約瑟夫環(huán)問題線性表是組成數(shù)據(jù)間具有線性關(guān)系的一種數(shù)據(jù)結(jié)構(gòu)。對線性表的基本操作主要有初始化、插入、刪除、查找、替換、顯示等，這些操作可以在線性表中的任何位置進(jìn)行。線性表可以采用順序存儲結(jié)構(gòu)表示。本學(xué)習(xí)情境的任務(wù)是學(xué)習(xí)線性表抽象數(shù)據(jù)類型，線性表的兩種存儲結(jié)構(gòu)的操作算法及程序?qū)崿F(xiàn)，比較這兩種程序?qū)崿F(xiàn)的特點(diǎn)，以及各種基本操作算法的效率。2.1任務(wù)一認(rèn)識線性表2.1.1子任務(wù)1初識線性表

1．定義線性表(linearlist)線性表是許多實(shí)際應(yīng)用領(lǐng)域中表結(jié)構(gòu)的抽象形式，因此，線性表中數(shù)據(jù)在不同的場合可以有不同的含義。例如，在字母表(A，B，C，…，Z)中，每個數(shù)據(jù)是一個字母；在一個學(xué)生成績中，每個數(shù)據(jù)是一個學(xué)生的成績信息，其中可能包含學(xué)號、姓名、成績等字段。但要注意，在同一個表中各數(shù)據(jù)的類型或數(shù)據(jù)結(jié)構(gòu)是一致的。線性表定義：由n(n≥0)個類型相同的數(shù)據(jù)a0，a1，…，an-1組成的有限序列，記作：

LinearList=(a0，a1，…，an-1)本教程約定線性表中數(shù)據(jù)序號從0開始計數(shù)。其中，數(shù)據(jù)ai可以是數(shù)字、字符、也可以是其他對象。n是線性表的數(shù)據(jù)個數(shù)，稱為線性表長度。若n=0，則LinearList為空表。若n>0，則a0沒有前驅(qū)數(shù)據(jù)，an-1沒有后繼數(shù)據(jù)，ai(0<i<n-1)有且僅有一個直接前驅(qū)數(shù)據(jù)ai-1和一個直接后繼數(shù)據(jù)ai+1。線性表的圖形如圖2-1所示。圖2-1線性表

2．操作線性表線性表結(jié)構(gòu)是許多實(shí)際應(yīng)用中所用到的表結(jié)構(gòu)的抽象，因而對線性表的實(shí)際操作可以有很多種，例如，對我們所熟知的成績表就有很多操作的要求。為便于教學(xué)和學(xué)習(xí)領(lǐng)會，只討論常用基本操作。在此基礎(chǔ)上，學(xué)習(xí)者可以舉一反三地實(shí)現(xiàn)需要的操作。線性表常用的基本操作有如下8個：

(1)初始化線性表initiate()：建立線性表的初始結(jié)構(gòu)，即建空表。這也是各種數(shù)據(jù)結(jié)構(gòu)都經(jīng)常用到的操作。

(2)顯示線性表中數(shù)據(jù)displayData()：顯示線性表中全部數(shù)據(jù)，可以直接驗(yàn)證程序是否正確實(shí)現(xiàn)，是非常必要的操作。

(3)求線性表數(shù)據(jù)個數(shù)getSize()：得到線性表中的數(shù)據(jù)個數(shù)。

(4)追加數(shù)據(jù)add()：在線性表最后增加數(shù)據(jù)。

(5)插入數(shù)據(jù)insert()：在線性表的第i個數(shù)據(jù)位置上插入值為x的數(shù)據(jù)。顯然，若表中的數(shù)據(jù)個數(shù)為n，則插入序號i應(yīng)滿足0≤i≤n-1。

(6)刪除數(shù)據(jù)delete(inti)：刪除線性表中序號為i的數(shù)據(jù)。顯然，待刪除數(shù)據(jù)的序號應(yīng)滿足0≤i≤n-1。

(7)查找數(shù)據(jù)getData()：得到表中序號為i的數(shù)據(jù)并顯示。

(8)修改數(shù)據(jù)updateData()：修改表中序號為i的數(shù)據(jù)。雖然只給出了8個基本操作，但借助這些基本操作可以構(gòu)造出其他更為復(fù)雜的操作。例如，如果要求刪除線性表中值為x的數(shù)據(jù)，則可用上述操作中的兩個操作來實(shí)現(xiàn)：先引用list_locate求出數(shù)據(jù)x的位置，再用list_delete來實(shí)現(xiàn)刪除。盡管這一實(shí)現(xiàn)的時間性能不太好，但在討論基本操作時，主要還是側(cè)重于其邏輯上的實(shí)現(xiàn)，而不是具體程序上的實(shí)現(xiàn)。2.1.2子任務(wù)2認(rèn)識線性表的存儲結(jié)構(gòu)線性表的存儲結(jié)構(gòu)主要有兩種，常用的有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。

1．順序存儲結(jié)構(gòu)線性表中的元素按照其邏輯次序依次存儲到這一存儲區(qū)中，方法是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存的物理存儲次序與它們在線性表的邏輯次序相同，如圖2-2所示。圖2-2線性表順序存儲結(jié)構(gòu)

2．鏈?zhǔn)酱鎯Y(jié)構(gòu)用若干地址分散的存儲單元存儲數(shù)據(jù)元素，邏輯上相鄰的數(shù)據(jù)元素在物理位置上不一定相鄰，必須采用附加信息，如圖2-3中的箭頭表示元素之間的前后順序關(guān)系。因此，對每個表元素，除了存儲元素本身的值外，還帶有一個指向其后繼元素的地址(指針)，鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖2-3所示。圖2-3線性表鏈?zhǔn)酱鎯?.2任務(wù)二程序?qū)崿F(xiàn)線性表的順序存儲結(jié)構(gòu)及操作2.2.1子任務(wù)1認(rèn)識線性表的順序存儲結(jié)構(gòu)

1．順序存儲結(jié)構(gòu)特點(diǎn)線性表的數(shù)據(jù)元素順序存放在數(shù)組中，數(shù)據(jù)元素在數(shù)組中的物理順序與線性表中元素的順序關(guān)系完全相同。

2．順序存儲結(jié)構(gòu)的數(shù)據(jù)存儲地址如圖2-2所示，線性表的順序存儲是用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素，元素在內(nèi)存中的物理存儲次序與它們在線性表中的邏輯次序相同，即元素ai與其連接前驅(qū)ai-1及直接后續(xù)ai+1的存儲位置相鄰。順序存儲的線性表也稱為順序表(sequentiallist)。線性表的元素屬于同一種數(shù)據(jù)類型，設(shè)每個元素占用c字節(jié)，a0的存儲地址為address(a0),則ai的存儲地址為address(a0)+i*c。

3．順序存儲結(jié)構(gòu)的時間復(fù)雜度順序表元素ai的存儲地址是它在線性表中位置i的線性函數(shù)，如圖2.2所示，與線性表長度n無關(guān)，而計算一個元素地址所需時間是一個常量，與元素位置i無關(guān)。因此，存取任何一個元素的時間復(fù)雜度是O(l)。換言之，順序表是一種隨機(jī)存取結(jié)構(gòu)。

4．?dāng)?shù)組數(shù)組是順序存儲的隨機(jī)存取結(jié)構(gòu)，它占用一組連續(xù)的存儲單元，通過下標(biāo)i識別元素，元素地址是下標(biāo)的線性函數(shù)。一個下標(biāo)能夠唯一確定一個元素，存取任何一個元素所花費(fèi)的時間是O(l)。所以線性表的存儲結(jié)構(gòu)通常采用數(shù)組存儲數(shù)據(jù)元素。

5．定義線性表順序存儲結(jié)構(gòu)的類

publicclassSeqList{

privateintmaxn=100;//線性表存儲空間為100或根據(jù)需要而定

privateintn=-1; //線性表個數(shù)，-1表示未初始化

privateObject[]data; //聲明線性表數(shù)據(jù)類型，Object可以存儲任何類型

}2.2.2子任務(wù)2線性表順序存儲結(jié)構(gòu)的操作算法下面分析線性表順序存儲結(jié)構(gòu)的操作算法。

1．初始化線性表initiate()算法在進(jìn)行線性表的各種操作前必須先建立線性表的初始結(jié)構(gòu)，對順序存儲結(jié)構(gòu)而言，即建立一個具有一定大小的空表。用中文描述算法：創(chuàng)建一個大小為maxn的數(shù)組；線性表沒有數(shù)據(jù)，即n為0；用程序設(shè)計語言描述算法：

data=newObject[maxn];

n=0;

2．顯示線性表中所有數(shù)據(jù)displayData()算法顯示線性表中的全部數(shù)據(jù)，可用中文描述如下： 如果沒有數(shù)據(jù) 提示“線性表中沒有數(shù)據(jù)”； 否則 按順序?qū)⑺袛?shù)據(jù)輸出；前面約定用n表示線性表的個數(shù)，所以“沒有數(shù)據(jù)”的條件就是n<1；“按順序?qū)⑺袛?shù)據(jù)輸出”，可以很容易想到用循環(huán)控制結(jié)構(gòu)來實(shí)現(xiàn)。用程序設(shè)計語言描述算法：

if(n<1){

System.out.println("線性表中沒有數(shù)據(jù)");

}else{

for(inti=1;i<=n;i++){ //按順序?qū)⑺袛?shù)據(jù)輸出

System.out.print(data[i]+"");

}

}

3．求線性表數(shù)據(jù)個數(shù)getSize()算法線性表中的數(shù)據(jù)個數(shù)實(shí)際就是線性表的參數(shù)n，可以直接得到，用中文描述算法： 返回線性表個數(shù)n用程序設(shè)計語言描述算法：

returnn;

4．追加數(shù)據(jù)add(Objectobj)算法在線性表后面增加數(shù)據(jù)，在2.2.1子任務(wù)1中定義線性表順序存儲結(jié)構(gòu)的類時，n=-1表示線性表未初始化，如果直接追回數(shù)據(jù)會造成異常，所以追加數(shù)據(jù)前先要判斷線性表是否已經(jīng)初始化。如果不斷增加數(shù)據(jù)，達(dá)到線性表定義空間，這時就要擴(kuò)展線性表空間，或者進(jìn)行簡單處理不讓數(shù)據(jù)繼續(xù)增加。用中文描述算法： 如果線性表未初始化 拋出未初始化異常信息 如果達(dá)到線性表定義大小 拋出線性表已滿異常信息 讀入數(shù)據(jù) 在線性表最后位置存入該數(shù)據(jù) 線性表個數(shù)加1用程序設(shè)計語言描述算法：

if(n==-1){

thrownewException("尚未初始化，請選擇0進(jìn)行初始化！"); }

if(n==maxn){

thrownewException("線性表已滿，無法再插入"); } System.out.print("請輸入要加進(jìn)的數(shù)據(jù)："); Objectobj=scan.next();

data[n+1]=obj; //在線性表最后位置存入讀入的數(shù)據(jù)

n++; //每次執(zhí)行完add()之后記得將線性表長度加1

5．插入數(shù)據(jù)insert()算法在線性表的第i個數(shù)據(jù)位置上插入值為x的數(shù)據(jù)。顯然，若表中的數(shù)據(jù)個數(shù)為n，則插入序號i應(yīng)滿足0≤i≤n-1，還要判斷線性表是否已滿；插入操作時，插入位置后面的所有數(shù)據(jù)要從后往前依次將數(shù)據(jù)后移一位，空出位置i，將讀入數(shù)據(jù)存入此位置，最后n加1，如圖2-4所示。圖2-4線性表順序存儲結(jié)構(gòu)插入操作用中文描述算法： 輸入插入位置i的值 如果i不滿足0≤i≤n-1

拋出位置錯誤信息 如果達(dá)到線性表定義大小 拋出線性表已滿異常信息 讀入數(shù)據(jù) 從ai開始全部數(shù)據(jù)從后向前后移一位用程序設(shè)計語言描述算法：

System.out.println("請輸入要插入第幾個數(shù)據(jù)的后面");

inti=scan.nextInt();

if(i<0||i>n){

thrownewException("位置錯誤，請選擇1查看數(shù)據(jù)以確定插入位置");

}

if(n==maxn){

thrownewException("線性表已滿，無法再插入");

}

System.out.println("請輸入你要輸入的數(shù)據(jù)");

Objectobj=scan.next();

//插入位置開始的所有數(shù)據(jù)要從后往前依次將數(shù)據(jù)后移一位

for(intj=n;j>i;j--){

data[j+1]=data[j];

}

data[i+1]=obj;

n++;

6．刪除數(shù)據(jù)delete(inti)算法刪除線性表中序號為i的數(shù)據(jù)，顯然，待刪除數(shù)據(jù)的序號應(yīng)滿足0≤i≤n-1，順序存儲結(jié)構(gòu)的線性表刪除數(shù)據(jù)時，只要將此位置后面的數(shù)據(jù)依次向前移一位，覆蓋前一位數(shù)據(jù)，最后將線性表的個數(shù)減1即可，如圖2-5所示。圖2-5線性表順序存儲結(jié)構(gòu)刪除操作用中文描述算法： 如果i不滿足0≤i≤n-1

拋出位置錯誤信息暫存要刪除的數(shù)據(jù)

i位置后面的數(shù)據(jù)依次往前移一位 線性表個數(shù)減1

返回刪除的數(shù)據(jù)用程序設(shè)計語言描述算法：

if(i<0||i>n){

thrownewException("位置錯誤，請選擇1查看數(shù)據(jù)以確定刪除位置"); } Objectit=data[i]; //暫存要刪除的數(shù)據(jù)

//i位置后面的數(shù)據(jù)依次向前移一位

for(intj=i;j<n;j++){

data[j]=data[j+1];

}

n--;

returnit; //返回已刪除的數(shù)據(jù)

7．查找數(shù)據(jù)getData()算法得到表中序號為i的數(shù)據(jù)并顯示，先判斷序號i是否在線性表的有效范圍內(nèi)，如果是就直接獲得該位置的數(shù)據(jù)并返回。用中文描述算法： 如果i不滿足0≤i≤n-1

拋出位置錯誤信息 返回序號i位置的數(shù)據(jù)用程序設(shè)計語言描述算法：

if(i<0||i>n){

thrownewException("該位置無數(shù)據(jù)");

}

System.out.println("你要查找的數(shù)為："+data[i]);

returndata[i];

8．修改數(shù)據(jù)updateData()算法修改表中序號為i的數(shù)據(jù)，先判斷序號i是否在線性表的有效范圍內(nèi)，如果是就將數(shù)組下標(biāo)為i的數(shù)據(jù)置為輸入數(shù)據(jù)。用中文描述算法： 讀入修改序號i如果i不滿足0≤i≤n-1

拋出位置錯誤信息 讀入新的數(shù)據(jù)將數(shù)組下標(biāo)為i的數(shù)據(jù)置為輸入數(shù)據(jù)用程序設(shè)計語言描述算法：

System.out.println("請輸入你要修改的第幾個數(shù)"); inti=scan.nextInt(); if(i<=0||i>n){ return; } System.out.println("請輸入修改的數(shù)據(jù)為："); Objectobj=scan.next(); data[i]=obj; //將數(shù)組下標(biāo)為i的數(shù)據(jù)置為輸入數(shù)據(jù)2.2.3子任務(wù)3程序?qū)崿F(xiàn)線性表順序存儲結(jié)構(gòu)的操作考慮到不少程序初學(xué)者在學(xué)完《數(shù)據(jù)結(jié)構(gòu)和算法》教程后卻從未完成一個能夠運(yùn)行的程序，本學(xué)習(xí)任務(wù)將詳細(xì)介紹該程序?qū)崿F(xiàn)的全過程。對于初學(xué)者，務(wù)必按照本任務(wù)一步一步認(rèn)真學(xué)習(xí)和操作，在進(jìn)行任何一步時，有錯誤一定要查出來并改正，必須做到無錯誤才能進(jìn)入下一步，只要掌握了本任務(wù)，后面的程序就可以輕松上手。

1．構(gòu)建主程序SeqListMain.java

(1)新建包c(diǎn)h2List，在此包中新建主程序文件，文件名為SeqListMain.java，開始創(chuàng)建線性表操作菜單，程序如下(調(diào)試通過后再進(jìn)入下一步)：packagech2List;importjava.util.Scanner;publicclassSeqListMain{publicstaticvoidmain(String[]args){ Scannerscan=newScanner(System.in);intselect;do{System.out.println("\n\n\t==========線性表操作菜單==========");System.out.print("1.初始化");System.out.print("2.顯示線性表中數(shù)據(jù)");System.out.print("3.求線性表數(shù)據(jù)個數(shù)");System.out.print("4.追加數(shù)據(jù)");System.out.print("5.插入數(shù)據(jù)");

System.out.print("6.刪除數(shù)據(jù)");

System.out.print("7.查找數(shù)據(jù)");

System.out.print("8.修改數(shù)據(jù)");

System.out.print("9.退出\n");

System.out.print("請輸入您的選擇項(xiàng)：");

select=scan.nextInt();

}while(true);

}

}運(yùn)行程序，結(jié)果如下：

==========線性表操作菜單==========

1.初始化2.顯示線性表中數(shù)據(jù)3.求線性表數(shù)據(jù)個數(shù)4.追加數(shù)據(jù)

5.插入數(shù)據(jù)6.刪除數(shù)據(jù)7.查找數(shù)據(jù)8.修改數(shù)據(jù)9.退出請輸入您的選擇項(xiàng)：

(2)對菜單選擇進(jìn)行處理，根據(jù)用戶鍵盤輸入的選擇值，即select值使用switch結(jié)構(gòu)來構(gòu)造響應(yīng)用戶選擇的處理框架，程序如下：

switch(select){

case1:

break;

case2:

break;

case3:

break;

case4:

break;

case5:

break;

case6:

break;

case7:

break;

case8:

break;

case9:

System.out.print("正在退出菜單.....");

System.exit(0);

break;運(yùn)行程序，鍵盤輸入9，回車后，就可以退出系統(tǒng)。接下來只有先構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java，才能繼續(xù)響應(yīng)其他選擇。

注意：請轉(zhuǎn)而閱讀“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第三步，然后再返回此處進(jìn)行第三步操作。

(3)調(diào)用initiate()方法，先在

publicstaticvoidmain(String[]args){后面插入一行代碼——創(chuàng)建SeqList類的對象seqlist，代碼如下，

SeqListseqlist=newSeqList();接著在case1：調(diào)用initiate()方法，程序如下：

case1：

seqlist.initiate();

break;運(yùn)行程序，通過鍵盤輸入1，得到如下結(jié)果，表示初始化方法編寫成功：

==========線性表操作菜單==========

1.初始化2.顯示線性表中數(shù)據(jù)3.求線性表數(shù)據(jù)個數(shù)

4.追加數(shù)據(jù)5.插入數(shù)據(jù)6.刪除數(shù)據(jù)7.查找數(shù)據(jù)8.修改數(shù)據(jù)

9.退出請輸入您的選擇項(xiàng)：1初始化成功。注意：先轉(zhuǎn)入“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第四步，然后再返回此處進(jìn)行下面的操作。

(4)在case2：中調(diào)用displayData()方法，程序如下：

case2:

seqlist.displayData();

break;注意：調(diào)試通過后，轉(zhuǎn)入“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第五步，然后再返回此處進(jìn)行下面的步驟。

(5)在case3：中調(diào)用getSize()方法，得到線性表的個數(shù)n，如果n為0則表明線性表沒有數(shù)據(jù)，否則輸出個數(shù)，程序如下：

case3:

if(seqlist.getSize()==0){

System.out.println("線性表為空");

}else{

System.out.print("元素的個數(shù)為");

System.out.print(seqlist.getSize());

}

break;注意：調(diào)試通過后，轉(zhuǎn)入“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第六步，然后再返回此處進(jìn)行下面的步驟。

(6)在case4：中調(diào)用add()方法，因?yàn)閍dd()方法有拋出異常信息，所以在調(diào)用時要捕獲異常并處理。因?yàn)閍dd()方法是拋出線性表未初始化或已滿的信息，所以處理異常就會輸出add()方法異常拋出的信息(e.toString())，程序如下：

case4:

System.out.print("請輸入要加進(jìn)的數(shù)據(jù)：");

Objectobj=scan.next();

try{

seqlist.add(obj);

}catch(Exceptione){

System.out.print(e.toString());

}

break;注意：調(diào)試通過后，轉(zhuǎn)入“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第七步，然后再返回此處進(jìn)行下面的步驟。

(7)在case5：中調(diào)用方法并進(jìn)行異常捕獲和處理，程序如下：

case5:

try{

seqlist.insert();

}catch(Exceptione){

System.out.print(e.toString());

}

break;注意：調(diào)試通過后，轉(zhuǎn)入“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第八步，然后再返回此處進(jìn)行下面的步驟。

(8)在case6：中調(diào)用delete(i)方法，delete(i)方法以刪除序號i作為參數(shù)傳遞來進(jìn)行刪除調(diào)用，事先需要使用者從鍵盤輸入刪除位置，程序如下：

case6:

//刪除i位置的數(shù)據(jù)

System.out.println("請輸入你要刪除第幾個數(shù)：");

inti=scan.nextInt();

if(seqlist.getSize()==0){

System.out.print("順序表已空無法刪除！");

}

if(i<0||i>seqlist.getSize()){

System.out.print("位置錯誤，請選擇1察看數(shù)據(jù)以確定刪除位置");

}

try{

seqlist.delete(i);

}catch(Exceptione){

System.out.print(e.toString());

}

break;注意：調(diào)試通過后，轉(zhuǎn)入“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第九步，然后再返回此處進(jìn)行下面的步驟。

(9)在case7：中調(diào)用getData()方法，程序如下：

case7:

try{

seqlist.getData();

}catch(Exceptione){

System.out.print(e.toString());

}

break;注意：調(diào)試通過后，轉(zhuǎn)入“2.構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java”的第十步，然后再返回此處進(jìn)行下面的步驟。

(10)在case8：中調(diào)用updateData()方法，程序如下：

case8:

intnumber=0;

intindex=0;

seqlist.updateData();

break;至此，全部程序調(diào)試通過。

2．構(gòu)建線性表順序存儲結(jié)構(gòu)和算法程序SeqList.java

(1)在包c(diǎn)h2List中新建算法程序，文件名為SeqList.java。

(2)構(gòu)建線性表順序存儲結(jié)構(gòu)，程序代碼如下：

packagech2List;

importjava.util.Scanner;

publicclassSeqList{

Scannerscan=newScanner(System.in);

privateintmaxn=100; //線性表存儲空間為100或根據(jù)需要而定

privateintn=-1; //線性表個數(shù)，-1表示未初始化

privateObject[]data; //聲明線性表數(shù)據(jù)類型，Object可以存儲任何類型

}

(3)創(chuàng)建初始化initiate()方法，程序如下：

publicvoidinitiate(){//初始化

data=newObject[maxn];

n=0;

System.out.println("初始化成功.");

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第三步，調(diào)用該方法。

(4)創(chuàng)建顯示所有數(shù)據(jù)displayData()方法，程序如下：

publicvoiddisplayData(){

if(n<1){

System.out.println("線性表中沒有數(shù)據(jù)");

}else{

for(inti=1;i<=n;i++){//按順序?qū)⑺袛?shù)據(jù)輸出

System.out.print(data[i]+"");

}

}

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第四步，調(diào)用該方法。

(5)獲得線性表數(shù)據(jù)個數(shù)getSize()方法，程序如下：

publicintgetSize(){

returnn;

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第五步，調(diào)用該方法。

(6)追加數(shù)據(jù)add()方法，要算法分析時，需要拋出異常信息，如線性表未初始化或已滿等信息，所以在創(chuàng)建add()方法時要用throwsException拋出異常，從而讓調(diào)用者捕獲和處理。程序如下：

publicvoidadd(Objectobj)throwsException{

if(n==-1){//未初始化，拋出異常信息

thrownewException("尚未初始化，請選擇0進(jìn)行初始化！");

}

if(n==maxn){//已滿，拋出異常信息

thrownewException("線性表已滿，無法再插入");

}

data[n+1]=obj;//在線性表最后位置存入讀入的數(shù)據(jù)

n++;//每次執(zhí)行完add()之后記得將線性表長度加1

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第六步，調(diào)用該方法。

(7)插入數(shù)據(jù)insert()方法，與add()方法相同，要用throwsException拋出異常，從而讓調(diào)用者捕獲和處理。程序如下：

publicvoidinsert()throwsException{

System.out.println("請輸入要插入第幾個數(shù)據(jù)的后面");

inti=scan.nextInt();

if(i<0||i>n){

thrownewException("位置錯誤，請選擇1查看數(shù)據(jù)以確定插入位置");

}

if(n==maxn){

thrownewException(“線性表已滿，無法再插入”);

}

System.out.println("請輸入你要輸入的數(shù)據(jù)");

Objectobj=scan.next();

//插入位置開始的所有數(shù)據(jù)要從后往前依次將數(shù)據(jù)后移一位

for(intj=n;j>i;j--){

data[j+1]=data[j];

}

data[i+1]=obj;

n++;

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第七步，調(diào)用該方法。

(8)刪除數(shù)據(jù)delete(inti)方法，用throwsException拋出異常，從而讓調(diào)用者捕獲和處理。程序如下：

publicObjectdelete(inti)throwsException{

Objectit=data[i];//獲得要刪除的數(shù)據(jù)

if(i<0||i>n){

thrownewException("位置錯誤，請選擇1查看數(shù)據(jù)以確定刪除位置");

}

//i位置后面的數(shù)據(jù)依次往前移一位

for(intj=i;j<n;j++){

data[j]=data[j+1];

}

n--;

returnit;//返回已刪除的數(shù)據(jù)

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第八步，調(diào)用該方法。

(9)查找數(shù)據(jù)getData()方法，用throwsException拋出異常，從而讓調(diào)用者捕獲和處理。程序如下：

publicObjectgetData()throwsException{

//獲取i位置的數(shù)據(jù)并返回

System.out.println("請輸入你要查找的第幾個數(shù)");

inti=scan.nextInt();

if(i<0||i>n){

thrownewException("該位置無數(shù)據(jù)");

}

System.out.println("你要查找的數(shù)為："+data[i]);

returndata[i];

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第九步，調(diào)用該方法。

(10)修改數(shù)據(jù)updateData()方法，程序如下：

publicvoidupdateData(){

System.out.println("請輸入你要修改的第幾個數(shù)");

inti=scan.nextInt();

if(i<=0||i>n){

return;

}

System.out.println("請輸入修改的數(shù)據(jù)為：");

Objectobj=scan.next();

data[i]=obj;//將數(shù)組的下標(biāo)為i的數(shù)據(jù)設(shè)置為輸入數(shù)據(jù)

}轉(zhuǎn)回“1.構(gòu)建主程序SeqListMain.java”的第十步，調(diào)用該方法。

3．完整源程序

(1)?SeqListMain.java程序。

packagech2List;

importjava.util.Scanner;

publicclassSeqListMain{

publicstaticvoidmain(String[]args){

SeqListseqlist=newSeqList();

Scannerscan=newScanner(System.in);

intselect;

do{System.out.println("\n\n\t==========線性表操作菜單==========");System.out.print("1.初始化");System.out.print("2.顯示線性表中數(shù)據(jù)");System.out.print("3.求線性表數(shù)據(jù)個數(shù)");System.out.print("4.追加數(shù)據(jù)");System.out.print("5.插入數(shù)據(jù)");System.out.print("6.刪除數(shù)據(jù)");System.out.print("7.查找數(shù)據(jù)");System.out.print("8.修改數(shù)據(jù)");System.out.print("9.退出\n");System.out.print("請輸入您的選擇項(xiàng)：");select=scan.nextInt();

switch(select){case1:seqlist.initiate();break;case2:seqlist.displayData();break;case3:if(seqlist.getSize()==0){System.out.println("線性表為空");}else{System.out.print("數(shù)據(jù)的個數(shù)為");System.out.print(seqlist.getSize());}break;

case4:System.out.print("請輸入要加進(jìn)的數(shù)據(jù)：");Objectobj=scan.next();try{seqlist.add(obj);}catch(Exceptione){System.out.print(e.toString());}break;case5:try{seqlist.insert();}catch(Exceptione){System.out.print(e.toString());}break;case6://刪除i位置的數(shù)據(jù)

System.out.println("請輸入你要刪除第幾個數(shù)：");inti=scan.nextInt();if(seqlist.getSize()==0){System.out.print("順序表已空無法刪除！");}if(i<0||i>seqlist.getSize()){System.out.print("位置錯誤，請選擇1查看數(shù)據(jù)以確定刪除位置");}try{seqlist.delete(i);}catch(Exceptione){System.out.print(e.toString());}break;case7:try{seqlist.getData();}catch(Exceptione){System.out.print(e.toString());}break;case8:intnumber=0;intindex=0;seqlist.updateData();break;

case9:

System.out.print("正在退出菜單.....");

System.exit(0);

break;}}while(true);}}

(2)?SeqList.java程序。

packagech2List;

importjava.util.Scanner;

publicclassSeqList{

Scannerscan=newScanner(System.in);

privateintmaxn=100; //線性表存儲空間為100或根據(jù)需要而定

privateintn=-1; //線性表個數(shù)，-1表示未初始化

privateObject[]data; //聲明線性表數(shù)據(jù)類型，Object可以存儲任何類型publicvoidinitiate(){ //初始化

data=newObject[maxn];n=0;System.out.println("初始化成功.");}publicvoiddisplayData(){if(n<1){System.out.println("線性表中沒有數(shù)據(jù)");}else{for(inti=1;i<=n;i++){ //按順序?qū)⑺袛?shù)據(jù)輸出

System.out.print(data[i]+"");}}}publicintgetSize(){returnn;}publicvoidadd(Objectobj)throwsException{if(n==-1){ //未初始化，拋出異常信息

thrownewException("尚未初始化，請選擇0進(jìn)行初始化！");}if(n==maxn){ //已滿，拋出異常信息

thrownewException("線性表已滿，無法再插入");}data[n+1]=obj; //在線性表最后位置存入讀入的數(shù)據(jù)

n++;//每次執(zhí)行完add()之后記得將線性表長度加1}publicvoidinsert()throwsException{System.out.println("請輸入要插入第幾個數(shù)據(jù)的后面");inti=scan.nextInt();if(i<0||i>n){thrownewException("位置錯誤，請選擇1查看數(shù)據(jù)以確定插入位置");}if(n==maxn){thrownewException("線性表已滿，無法再插入");}System.out.println("請輸入你要輸入的數(shù)據(jù)");Objectobj=scan.next();//插入位置開始的所有數(shù)據(jù)要從后往前依次將數(shù)據(jù)后移一位

for(intj=n;j>i;j--){data[j+1]=data[j];

}data[i+1]=obj;n++;}publicObjectdelete(inti)throwsException{if(i<0||i>n){thrownewException("位置錯誤，請選擇1查看數(shù)據(jù)以確定刪除位置");}Objectit=data[i]; //暫存要刪除的數(shù)據(jù)

//i位置后面的數(shù)據(jù)依次往前移一位

for(intj=i;j<n;j++){data[j]=data[j+1];}n--;returnit; //返回已刪除的數(shù)據(jù)

}

publicObjectgetData()throwsException{//獲取i位置的數(shù)據(jù)并返回

System.out.println("請輸入你要查找的第幾個數(shù)");inti=scan.nextInt();if(i<0||i>n){thrownewException("該位置無數(shù)據(jù)");}System.out.println("你要查找的數(shù)為："+data[i]);

returndata[i];}publicvoidupdateData(){System.out.println("請輸入你要修改的第幾個數(shù)");inti=scan.nextInt();if(i<=0||i>n){return;}System.out.println("請輸入修改的數(shù)據(jù)為：");Objectobj=scan.next();data[i]=obj; //將數(shù)組下標(biāo)為i的數(shù)據(jù)設(shè)置為輸入數(shù)據(jù)

}}2.3任務(wù)三程序?qū)崿F(xiàn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及操作2.3.1子任務(wù)1認(rèn)識線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)

1．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表的鏈?zhǔn)酱鎯τ袆e于順序存儲，邏輯上相鄰的數(shù)據(jù)在物理位置上不一定相鄰，用地址分散的存儲單元存儲線性表的數(shù)據(jù)時，各存儲單元之間必須采用附加信息表示數(shù)據(jù)之間的順序關(guān)系。所以，對每個線性表數(shù)據(jù)，除了存儲數(shù)據(jù)本身的值外，還帶有一個指向其后繼數(shù)據(jù)的地址，即每個數(shù)據(jù)采用圖2-6所示的結(jié)構(gòu)表示。圖2-6線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表數(shù)據(jù)具有兩個域，一個數(shù)據(jù)域，一個指針域。其中，數(shù)據(jù)域用data表示存儲數(shù)據(jù)的值；指針域一般用Next或Link存儲后繼數(shù)據(jù)的地址，也稱為地址域或鏈。上述結(jié)構(gòu)通常稱為節(jié)點(diǎn)。圖2-6所示的節(jié)點(diǎn)只有一個指針，由一個指針的節(jié)點(diǎn)構(gòu)成的線性表稱單鏈表；還可以有兩個或更多的指針，比如兩個指針(一般稱為左指針和右指針)的節(jié)點(diǎn)構(gòu)成的線性表稱為雙鏈表，兩個指針分別為前繼節(jié)點(diǎn)和后繼節(jié)點(diǎn)，如圖2-7所示。雙指針節(jié)點(diǎn)結(jié)構(gòu)的線性表操作與單指針的鏈表操作相似，只要真正理解單鏈表的操作，雙鏈表的操作就可以類似解決，所以本教程重點(diǎn)講解單鏈表的操作。圖2-7線性表鏈?zhǔn)酱鎯Φ碾p指針節(jié)點(diǎn)

2．定義線性表鏈?zhǔn)酱鎯Φ墓?jié)點(diǎn)在C語言中，可以使用結(jié)構(gòu)體和指針來定義鏈?zhǔn)酱鎯Y(jié)構(gòu)的節(jié)點(diǎn)數(shù)據(jù)和指針；在C++語言中，采用指針類型存儲地址來實(shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)。

Java語言不支持指針類型，提供引用方式保存地址在內(nèi)的結(jié)構(gòu)化信息。引用是比指針更健壯、更安全的鏈接方式，它不僅實(shí)現(xiàn)了指針類型的所有功能，而且避免了因指針使用不當(dāng)而產(chǎn)生的不安全性。因此，采用Java語言的引用類型可以更好地實(shí)現(xiàn)鏈?zhǔn)酱鎯Y(jié)構(gòu)。定義的程序?qū)崿F(xiàn)如下：

publicclassSingleLinkList{

privateObjectdata; //聲明線性表數(shù)據(jù)類型，Object可以存儲任何類型

privateSingleLinkListnext; //聲明鏈表引用(指針)

privateSingleLinkListfront; //定義線性表的頭節(jié)點(diǎn)

}

2.3.2子任務(wù)2線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的操作算法在分析線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的操作算法之前，需要構(gòu)造鏈表的節(jié)點(diǎn)，可以使用Java語言的構(gòu)造方法來實(shí)現(xiàn)。為了方便起見，可以采用無數(shù)據(jù)參數(shù)構(gòu)造方法和帶數(shù)據(jù)參數(shù)構(gòu)造方法，分別構(gòu)造無數(shù)據(jù)節(jié)點(diǎn)和數(shù)據(jù)節(jié)點(diǎn)，程序?qū)崿F(xiàn)如下：

publicSingleLinkList(){//無參構(gòu)造方法，構(gòu)造無數(shù)據(jù)節(jié)點(diǎn)

this.next=null;

}

publicSingleLinkList(Objectdata){//帶數(shù)據(jù)參數(shù)構(gòu)造方法，構(gòu)造數(shù)據(jù)節(jié)點(diǎn)

this.data=data;

this.next=null;

}

與順序存儲類似，下面分析線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的操作算法。

1．初始化線性表initiate()算法在進(jìn)行線性各種操作前必須先建立線性表的初始結(jié)構(gòu)，對鏈?zhǔn)酱鎯Φ逆湵矶?，將頭節(jié)點(diǎn)的引用置為空(null)。用中文描述算法：將頭節(jié)點(diǎn)置空用程序設(shè)計語言描述算法：

this.front=null; //將頭節(jié)點(diǎn)置空

2．顯示線性表中所有數(shù)據(jù)displayData()算法顯示線性表中全部數(shù)據(jù)，用中文描述： 如果沒有數(shù)據(jù) 提示“線性表中沒有數(shù)據(jù)”； 否則 按順序?qū)⑺袛?shù)據(jù)輸出；鏈表的“沒有數(shù)據(jù)”的條件就是頭節(jié)點(diǎn)引用為空(null)；“按順序?qū)⑺袛?shù)據(jù)輸出”，可以利用節(jié)點(diǎn)的引用“順藤摸瓜”，直到最后數(shù)據(jù)，用循環(huán)控制結(jié)構(gòu)來實(shí)現(xiàn)。用程序設(shè)計語言描述算法：

if(front==null){

System.out.println("線性表中沒有數(shù)據(jù)");

return;

}

SingleLinkListcurrent=front; //當(dāng)前節(jié)點(diǎn)，從頭節(jié)點(diǎn)開始

while(current!=null){ //當(dāng)前節(jié)點(diǎn)非空，就輸出數(shù)據(jù)

System.out.print(current.data+"");

current=current.next; //當(dāng)前節(jié)點(diǎn)向后移，“順藤摸瓜”

}

3．求線性表數(shù)據(jù)個數(shù)getLength()算法鏈?zhǔn)酱鎯€性表中的數(shù)據(jù)個數(shù)，也需采用“順藤摸瓜”方式，節(jié)點(diǎn)不斷向后移，每移一次進(jìn)行一次計數(shù)，用中文描述算法： 頭節(jié)點(diǎn)的引用是空 返回0

從頭節(jié)點(diǎn)開始，直到節(jié)點(diǎn)引用為空 按節(jié)點(diǎn)引用往后移動節(jié)點(diǎn)，每移一次個數(shù)加1用程序設(shè)計語言描述算法：

if(front==null){

return0;//表為空，則返回0

}else{

SingleLinkListcurrent=front; //從頭節(jié)點(diǎn)開始

intlength=1; //從頭節(jié)點(diǎn)開始，length的初值為1

while(current.next!=null){ //一直到找到最后一個數(shù)據(jù)為止

current=current.next; //逐個向后遍歷

length++; //每移動一次，將length的值遞加一次

}

returnlength;

//返回length的值，length就是表中數(shù)據(jù)的個數(shù)

}

}

4．追加數(shù)據(jù)add(Objectdata)算法增加數(shù)據(jù)首先要創(chuàng)建數(shù)據(jù)節(jié)點(diǎn)(由構(gòu)造方法完成，將新增數(shù)據(jù)存入新創(chuàng)建的節(jié)點(diǎn)數(shù)據(jù)域、引用置為空)，接著將鏈表的最后一個節(jié)點(diǎn)的引用指向新節(jié)點(diǎn)即可。用中文描述算法： 創(chuàng)建新數(shù)據(jù)節(jié)點(diǎn)如果鏈表為空 新數(shù)據(jù)節(jié)點(diǎn)作為頭節(jié)點(diǎn) 否則 從頭節(jié)點(diǎn)開始移到鏈表最后 最后節(jié)點(diǎn)的引用指向新節(jié)點(diǎn)用程序設(shè)計語言描述算法：

SingleLinkListnewNode=newSingleLinkList(data); //創(chuàng)建新數(shù)據(jù)節(jié)點(diǎn)

if(front==null){ //表為空，新數(shù)據(jù)節(jié)點(diǎn)作為頭節(jié)點(diǎn)

front=newNode;

newNode.next=null;

return;

}else{

SingleLinkListcurrent=front; //移動節(jié)點(diǎn)指向頭節(jié)點(diǎn)

while(current.next!=null){

//節(jié)點(diǎn)引用非空，即還不到表最后

current=current.next; //向后移動節(jié)點(diǎn)

}

current.next=newNode; //最后節(jié)點(diǎn)的引用指向新節(jié)點(diǎn)

}

5．插入數(shù)據(jù)insert()算法在鏈表的第i個數(shù)據(jù)位置上插入數(shù)據(jù)，首先找到插入點(diǎn)，可以從頭節(jié)點(diǎn)開始，移動i次節(jié)點(diǎn)引用即可。在插入操作時，先將新節(jié)點(diǎn)的引用指向插入點(diǎn)后面的節(jié)點(diǎn)，再將插入點(diǎn)前的節(jié)點(diǎn)引用指向新節(jié)點(diǎn)。需要注意的是，這兩個操作不能顛倒，否則會丟掉插入點(diǎn)的引用，使得新節(jié)點(diǎn)無法正確指向插入后的節(jié)點(diǎn)，如圖2-8所示。圖2-8鏈?zhǔn)酱鎯€性表的插入操作用中文描述算法： 輸入插入位置i的值 如果i超過表的長度 拋出位置錯誤信息 否則 移動節(jié)點(diǎn)到插入位置 讀入數(shù)據(jù)，構(gòu)造新節(jié)點(diǎn) 如果表為空 新節(jié)點(diǎn)作為頭節(jié)點(diǎn) 否則 先將新節(jié)點(diǎn)的引用指向插入點(diǎn)后面的節(jié)點(diǎn) 再將插入點(diǎn)前的節(jié)點(diǎn)引用指向新插入的節(jié)點(diǎn)用程序設(shè)計語言描述算法：

System.out.print("請輸入要插入第幾個數(shù)據(jù)的后面：");

intindex=scan.nextInt();

if(index>getLength()){

System.out.println("輸入的位置超過鏈表的長度！");

}else{ //prev用于指向插入點(diǎn)之前的節(jié)點(diǎn)

SingleLinkListprev=newSingleLinkList();

//開始遍歷時，當(dāng)前節(jié)點(diǎn)current指向頭節(jié)點(diǎn)

SingleLinkListcurrent=front;

for(inti=1;i<=index;i++){

//從第一個節(jié)點(diǎn)開始，向后移動index個位置

prev=current; //當(dāng)前節(jié)點(diǎn)向后移動之前記為前一節(jié)點(diǎn)

current=current.next; //當(dāng)前節(jié)點(diǎn)向后移

}

System.out.print("請輸入要插入的數(shù)據(jù)：");data=scan.next();SingleLinkListnewNode=newSingleLinkList(data); //構(gòu)造新節(jié)點(diǎn)

if(front==null){ //表為空，新數(shù)據(jù)節(jié)點(diǎn)作為頭節(jié)點(diǎn)

front=newNode;newNode.next=null;return;}newNode.next=current; //先將新節(jié)點(diǎn)的引用指向插入點(diǎn)后面的節(jié)點(diǎn)，即currentprev.next=newNode; //再將插入點(diǎn)前的節(jié)點(diǎn)引用指向新插入的節(jié)點(diǎn)

}

6．刪除數(shù)據(jù)delete(intindex)算法刪除鏈表中第index位置的數(shù)據(jù)，只需將第index位置上一個節(jié)點(diǎn)的引用指向第index位置的下一個節(jié)點(diǎn)即可。Java有自動垃圾回收機(jī)制，可以不必編寫釋放已刪除節(jié)點(diǎn)的代碼。如果需要顯示被刪除的數(shù)據(jù)值，只要取出該數(shù)據(jù)域的值即可。刪除操作如圖2-9所示。用中文描述算法： 如果刪除頭節(jié)點(diǎn) 將頭節(jié)點(diǎn)的引用指向頭節(jié)點(diǎn)下一節(jié)點(diǎn) 否則 移動節(jié)點(diǎn)到刪除位置 輸出刪除節(jié)點(diǎn)的數(shù)據(jù)值 將第i位置上一個節(jié)點(diǎn)的引用指向第i位置的下一個節(jié)點(diǎn)圖2-9鏈?zhǔn)酱鎯€性表的刪除操作用程序設(shè)計語言描述算法：

SingleLinkListprev=newSingleLinkList(); //前一節(jié)點(diǎn)

SingleLinkListcurrent=front;//當(dāng)前節(jié)點(diǎn)

Objectit=null;

try{//防止移動過程出現(xiàn)空指針的異常

if(index==1){ //如果是刪除第一個，將頭節(jié)點(diǎn)指向頭節(jié)點(diǎn)的下一個

front=front.next;

}

for(inti=1;i<index;i++){ //從第一個節(jié)點(diǎn)開始，向后移動index個位置

prev=current;

current=current.next;

}