數(shù)據(jù)結(jié)構(gòu)（Java語言實(shí)現(xiàn)） 課件全套 陳銳 第1-8章 數(shù)據(jù)結(jié)構(gòu)概述、線性表 -排序

數(shù)據(jù)結(jié)構(gòu)（Java語言實(shí)現(xiàn)）結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)學(xué)習(xí)目標(biāo)LearningObjectives1數(shù)據(jù)結(jié)構(gòu)能做什么2數(shù)據(jù)結(jié)構(gòu)與算法的相關(guān)概念3能利用數(shù)據(jù)結(jié)構(gòu)知識對問題建模6提高Java語言開發(fā)水平和調(diào)試技巧4能編寫出算法解決實(shí)際問題5會分析算法的時間復(fù)雜度和空間復(fù)雜度7提高算法設(shè)計(jì)能力內(nèi)容與特點(diǎn)ContentandCharacteristics1突出體現(xiàn)數(shù)據(jù)結(jié)構(gòu)的算法實(shí)踐2案例豐富，精選自考研、軟考試題3圖文并茂，內(nèi)容講解細(xì)致4配套PPT、源代碼、視頻等，資源豐富5內(nèi)容講解理論與實(shí)踐并重，實(shí)用性強(qiáng)第1章緒論結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS1.1數(shù)據(jù)結(jié)構(gòu)相關(guān)概念1.2抽象數(shù)據(jù)類型1.5算法分析1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)1.4算法的特性與算法的描述1.6關(guān)于數(shù)據(jù)結(jié)構(gòu)的地位及學(xué)習(xí)方法1.1數(shù)據(jù)結(jié)構(gòu)相關(guān)概念學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力數(shù)據(jù)元素（dataelement）是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個整體來考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(xiàng)（dataitem）組成，數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位。0102數(shù)據(jù)（data）是描述客觀事物的符號，能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號集合。工

號姓

名性

別籍

貫所在院系出生年月職

稱2006002孫冬平男河南計(jì)算機(jī)學(xué)院1970.10教

授2019056朱

琳女北京文學(xué)院1985.08講師2015028劉曉光男陜西軟件學(xué)院1981.11副教授表1-1教職工基本情況1.1數(shù)據(jù)結(jié)構(gòu)相關(guān)概念學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力數(shù)據(jù)結(jié)構(gòu)（datastructure）即數(shù)據(jù)的組織形式，它是數(shù)據(jù)元素之間存在的一種或多種特定關(guān)系的數(shù)據(jù)元素集合。0304數(shù)據(jù)對象（dataobject）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。1.1數(shù)據(jù)結(jié)構(gòu)相關(guān)概念學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力在Java語言中，按照數(shù)據(jù)的構(gòu)造，數(shù)據(jù)類型可分為兩類：基本數(shù)據(jù)類型和引用數(shù)據(jù)類型，其中，基本數(shù)據(jù)類型有char、byte、short、int、long、float、double、boolean等8種，引用數(shù)據(jù)類型有數(shù)組、class（類）、接口。05數(shù)據(jù)類型（datatype）用來刻畫一組性質(zhì)相同的數(shù)據(jù)及其上的操作。1.2抽象數(shù)據(jù)類型及其描述1.2.1抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型（AbstractDataType，ADT）是對具有某種邏輯關(guān)系的數(shù)據(jù)類型進(jìn)行描述，并在該類型上進(jìn)行的一組操作。抽象數(shù)據(jù)類型描述的是一組邏輯上的特性，與在計(jì)算機(jī)內(nèi)部表示無關(guān)。計(jì)算機(jī)中的整數(shù)數(shù)據(jù)類型是一個抽象數(shù)據(jù)類型，不同的處理器可能實(shí)現(xiàn)方法不同，但其邏輯特性相同，即加、減、乘、除等運(yùn)算是一致的。抽象數(shù)據(jù)類型，就是對象的數(shù)據(jù)模型，它定義了數(shù)據(jù)對象、數(shù)據(jù)對象之間的關(guān)系及對數(shù)據(jù)對象的操作。抽象數(shù)據(jù)類型通常是指用戶定義的解決應(yīng)用問題的數(shù)據(jù)模型，包括數(shù)據(jù)的定義和操作。例如，Java、C++、Python中的類就是一個抽象數(shù)據(jù)類型，它包括用戶類型的定義和在用戶類型上的一組操作。1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型的描述抽象數(shù)據(jù)類型包括3個方面的內(nèi)容：數(shù)據(jù)對象、數(shù)據(jù)關(guān)系和基本運(yùn)算，通常采用三元組(D,SP)來表示。其基本格式如下：ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：數(shù)據(jù)對象的描述數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系的描述基本運(yùn)算：基本運(yùn)算的聲明}ADT抽象數(shù)據(jù)類型名1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型描述ADTMySet{數(shù)據(jù)對象：{ai|0≤ai≤n-1,ai∈R}。數(shù)據(jù)關(guān)系：無。基本操作：（1）InitSet(&S)：初始化操作，建立一個空的集合S。（2）SetEmpty(S)：若集合S為空，返回True，否則返回False。（3）GetSetElem(S,i,&e)：返回集合S的第i個位置元素值給e。（4）LocateElem(S,e)：在集合S中查找與給定值e相等的元素，如果查找成功返回該元素在表中的序號，否則返回0。（5）InsertSet(&S,e)：在集合S中插入一個新元素e。（6）DelSet(&S,i,&e)：刪除集合S中的第i個位置元素，并用e返回其值。（7）SetLength(S)：返回集合S中的元素個數(shù)。（8）ClearSet(&L)：將集合S清空。（9）UnionSet(&S,T)：合并集合S和T，即將T中的元素插入到S中，相同的元素只保留一個。（10）DiffSet(&S,T)：求兩個集合的差集，即S-T，即刪除S中與T中相同的元素。（11）DispSet(S)：輸出集合S中的元素。}ADTMySet1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型描述publicclassMySet<T>//集合的類型定義{

Tlist[];

intlength;

finalintMAXSIZE=100;

MySet()//集合的初始化

{

list=(T[])newObject[MAXSIZE];

length=0;

}

publicbooleanSetEmpty()

//判斷集合是否為空，若為空，則返回true；否則，返回false

{

if(length<=0)

returntrue;

else

returnfalse;

}

1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型描述publicintSetLength()//返回集合中元素個數(shù)

{

returnlength;

}

publicvoidClearSet()//清空集合

{

length=0;

}

publicbooleanInsertSet(Te)//在集合中插入一個元素e

{

if(length>=MAXSIZE-1){

System.out.println("下標(biāo)越界，不能插入!");

returnfalse;

}

else{

list[length++]=e;

returntrue;

}

}

1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型描述publicbooleanDelSet(intpos)

//刪除集合中的第pos個元素

{

if(length<=0)

{

System.out.println("集合為空，不能進(jìn)行刪除操作!");

returnfalse;

}

else{

for(inti=pos-1;i<length-1;i++)

{

list[i]=list[i+1];

length--;

}

returntrue;

}

}

1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型描述publicTGetSetElem(inti)throwsException//獲取集合中第i個元素賦給e

{

if(length<=0){System.out.println("集合為空，不能獲取任何元素!");}

elseif(i<1&&i>length){

thrownewException("下標(biāo)錯誤!");

}else{

Te=list[i-1];

returne;}

}

publicintLocateElem(Te)//查找集合中元素值為e的元素，返回其序號

{

for(inti=1;i<length+1;i++)

{

if(list[i-1]==e)

returni;

}

return0;

}

1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型描述publicintUnionSet(MySetS,MySetT)throwsException

//合并集合S和T

{

if(S.length+T.length>=S.MAXSIZE)

return-1;

else{

for(inti=1;i<T.length+1;i++){

Te=(T)T.GetSetElem(i);

if(S.LocateElem(e)==0)

S.InsertSet(e);

}

}

}

1.2抽象數(shù)據(jù)類型及其描述1.2.2抽象數(shù)據(jù)類型描述publicintDiffSet(MySetS,MySetT)throwsException//求集合S和T的差集

{

if(S.length<=0)

return-1;

else{

for(inti=1;i<T.length+1;i++){

Te=(T)T.GetSetElem(i);

intpos=S.LocateElem(e);

if(pos!=0)

S.DelSet(pos);

}

return1;

}

}

1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)1.3.1邏輯結(jié)構(gòu)（1）集合。數(shù)據(jù)元素除了同屬于一個集合外，數(shù)據(jù)元素之間沒有其他關(guān)系。（2）線性結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系。（3）樹形結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系。（4）圖結(jié)構(gòu)。結(jié)構(gòu)中的數(shù)據(jù)元素是多對多的關(guān)系。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)1.3.2存儲結(jié)構(gòu)存儲結(jié)構(gòu)也稱為物理結(jié)構(gòu)，數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中存儲形式。通常有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。采用順序存儲的字符串“abcdef”地址連續(xù)的存儲的存儲結(jié)構(gòu)如圖1-9所示。鏈?zhǔn)酱鎯κ前褦?shù)據(jù)元素存放在任意的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的1.4算法的特性與算法的描述算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切。兩者既有聯(lián)系又有區(qū)別。數(shù)據(jù)結(jié)構(gòu)與算法的聯(lián)系可用一個公式描述：程序=算法+數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是算法實(shí)現(xiàn)的基礎(chǔ)，算法依賴于某種數(shù)據(jù)結(jié)構(gòu)才能實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)與算法相輔相成，不是相互孤立存在的。數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及基本操作，而算法更多的是關(guān)注如何在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上怎樣設(shè)計(jì)解決實(shí)際問題的方法。算法是編程思想，數(shù)據(jù)結(jié)構(gòu)則是為了算法實(shí)現(xiàn)方便而提供的存儲結(jié)構(gòu)及基本操作，是算法設(shè)計(jì)的基礎(chǔ)。：1.4算法的特性與算法的描述1.4.1算法的定義算法（algorithm）是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為有限的操作序列。求n個數(shù)中最大者的問題for(i=0;i<a.length;i++)//for循環(huán)處理if(max<a[i])

//判斷是否滿足max小于a[i]的條件

max=a[i];

//如果滿足條件，將a[i]賦值給maxSystem.out.println("max=:"+max);1.4算法的特征與算法的描述1.4.2算法的五大特性（1）有窮性（finiteness）。有窮性指的是算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。（2）確定性（definiteness）。算法的每一步驟都具有確定的含義，不會出現(xiàn)二義性。算法在一定條件下只有一條執(zhí)行路徑，也就是相同的輸入只能有一個唯一的輸出結(jié)果。（3）可行性（feasibility）。算法的每個操作都能夠通過執(zhí)行有限次基本運(yùn)算完成。（4）輸入（input）。算法具有零個或多個輸入。（5）輸出（output）。算法至少有一個或多個輸出。輸出的形式可以是打印輸出，也可以是返回一個或多個值。1.4算法的特征與算法的描述算法的描述方式有多種，如自然語言、偽代碼（或稱為類語言）、程序流程圖及程序設(shè)計(jì)語言（如Java、Python、C、C++）等。1.4.3算法的描述1.4算法的特征與算法的描述2.程序流程圖法判斷m是否為質(zhì)數(shù)的程序流程圖如圖1-9所示。

采用自然語言描述算法直觀性和可讀性不強(qiáng)；

采用程序流程圖描述算法比較直觀，可讀性好，缺點(diǎn)是不能直接轉(zhuǎn)化為計(jì)算機(jī)程序，移植性不好。1.4.3算法的描述1.4算法的特征與算法的描述3.類語言法voiddcf()//求最大公約數(shù){ input(m,n); //輸入兩個正整數(shù)

r=m; do{ m=n; n=r; r=m%n; //r表示兩個數(shù)的余數(shù)

}while(r); print(n); //輸出最大公約數(shù)}1.4.3算法的描述1.4算法的特性與算法的描述4.程序設(shè)計(jì)語言法voiddcf()//求最大公約數(shù){intm,n,r;System.out.println("請輸入兩個正整數(shù)m和n：");Scannersc=newScanner(System.in);Stringa[]=sc.nextLine().split("");m=Integer.parseInt(a[0]);n=Integer.parseInt(a[1]);System.out.print(String.format("dcf（%d，%d）=",m,n));r=m;1.4.3算法的描述do{

//使用輾轉(zhuǎn)相除法法求解最大公約數(shù)

m=n;n=r;r=m%n;//r存放兩個數(shù)的余數(shù)

}while(r!=0);System.out.println(n);//輸出最大公約數(shù)}1.5算法分析1.算法的正確性（correctness）算法至少應(yīng)該包括對于輸入、輸出和處理無歧義性的描述，能正確反映問題的需求，且能夠得到問題的正確答案。通常算法的正確性應(yīng)包括以下4個層次。（1）算法對應(yīng)的程序沒有語法錯誤。（2）對于幾組輸入數(shù)據(jù)能得到滿足規(guī)格要求的結(jié)果。（3）對于典型的、苛刻的帶有刁難性的輸入數(shù)據(jù)，能得到滿足規(guī)格要求的結(jié)果。（4）對于一切合法的輸入都能得到滿足要求的結(jié)果。1.5.1算法設(shè)計(jì)的四個目標(biāo)1.5算法分析2.可讀性（readability）算法主要是為了人們方便閱讀和交流，其次才是計(jì)算機(jī)執(zhí)行。可讀性好有助于人們對算法的理解，晦澀難懂的程序往往隱含著不易被發(fā)現(xiàn)的錯誤，難以調(diào)試和修改。3.健壯性（robustness）當(dāng)輸入數(shù)據(jù)不合法時，算法也應(yīng)該能做出反應(yīng)或進(jìn)行處理，而不會產(chǎn)生異常或莫名其妙的輸出結(jié)果。4.高效率和低存儲量（Highefficiencyandlowstorage）效率指的是算法的執(zhí)行時間。對于同一個問題，如果有多個算法能夠解決，執(zhí)行時間短的算法效率高，執(zhí)行時間長的效率低。1.5.1算法設(shè)計(jì)的四個目標(biāo)1.5算法分析1.事后統(tǒng)計(jì)方法目前計(jì)算機(jī)內(nèi)部大都有計(jì)時功能，有的甚至可精確到毫秒級，不同算法的程序可通過一組或若干組相同的測試程序和數(shù)據(jù)以分辨算法的優(yōu)劣。缺點(diǎn)：一是必須依據(jù)算法事先編制好程序，這通常需要花費(fèi)大量的時間與精力；

二是時間的長短依賴計(jì)算機(jī)硬件和軟件等環(huán)境因素，有時會掩蓋算法本身的優(yōu)劣。1.5.2算法效率評價1.5算法分析2.事前分析估算方法在計(jì)算機(jī)程序編制前，對算法依據(jù)數(shù)學(xué)中的統(tǒng)計(jì)方法進(jìn)行估算。這個方法可行，主要是因?yàn)樗惴ǖ某绦蛟谟?jì)算機(jī)上的運(yùn)行時間取決于以下因素： 算法采用的策略、方法。 編譯產(chǎn)生的代碼質(zhì)量。 問題的規(guī)模。 書寫的程序語言，對于同一個算法，語言級別越高，執(zhí)行效率越低。 機(jī)器執(zhí)行指令的速度。1.5.2算法效率評價1.5算法分析例如，兩個n×n矩陣相乘的算法和語句的的頻度如下。

每條語句的頻度for(i=0;i<n;i++)n

for(j=0;j<n;j++)n2{

a[i][j]=0;

n2

for(k=0;k<n;k++)n3

a[i][j]=a[i][j]+a[i][k]*a[k][j];n3}總的執(zhí)行次數(shù)為1.5.2算法效率評價f(n)=n+n2+n2+n3+n3=2n3+2n2+n1.5算法分析1.什么是算法時間復(fù)雜度在進(jìn)行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復(fù)雜度，也就是算法的時間量度，記作T(n)=O(f(n))。它表示隨問題規(guī)模n的增大，算法的執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸進(jìn)時間復(fù)雜度，簡稱為時間復(fù)雜度。1.5.3算法時間復(fù)雜度1.5算法分析（1）x=x+1;（2）for(i=1;i<n+1;i++)x=x+1;（3）for(i=1;i<n+1;i++)for(j=1;j<n+1;j++)

x=x+1;程序段（1）的時間復(fù)雜度為O(1)，稱為常量階；程序段（2）的時間復(fù)雜度為O(n)，稱為線性階；程序段（3）的時間復(fù)雜度為O(n2)，稱為平方階。此外算法的時間復(fù)雜度還有對數(shù)階O(log2n)、指數(shù)階O(2n)等1.5.3算法時間復(fù)雜度1.5算法分析常用的時間復(fù)雜度所耗費(fèi)的時間從小到大依次是O(1)<O(log2n)<O(n)<O(n2)<O(n3)<O(2n)<O(n!)1.5.3算法時間復(fù)雜度1.5算法分析2.算法時間復(fù)雜度分析舉例例1.1分析以下程序段的時間復(fù)雜度。for(i=1;i<n;i++)

for(j=1;j<I;j++){

x=x+1;//基本操作

a[i][j]=x;//基本操作}該程序段中的基本操作是第二層for循環(huán)中的語句，即x=x+1和a[i][j]=x，其語句頻度為(n-1)(n-2)/2。因此，其時間復(fù)雜度為O(n2)。1.5算法分析2.算法時間復(fù)雜度分析舉例例1.2分析以下算法的時間復(fù)雜度。voidFun(){

inti=1;

while(i<=n)

i=i*2;//基本操作}該函數(shù)fun()的基本運(yùn)算是i=i*2，設(shè)執(zhí)行時間次數(shù)為f(n)，則2f(n)≤n，則有f(n)≤log2n。因此，時間復(fù)雜度為O(log2n)。1.5算法分析2.算法時間復(fù)雜度分析舉例例1.3分析以下算法的時間復(fù)雜度。

voidFunc(){

inti=0;

ints=0;

while(s<n){

i=i+1;//基本操作

s+=i;//基本操作}}該算法中的基本操作是while循環(huán)中的語句，設(shè)while循環(huán)次數(shù)為f(n)，則變量i從0到f(n)，因此循環(huán)次數(shù)為f(n)*(f(n)+1)/2≤n，則f(n)≤

，故時間復(fù)雜度為O()。1.5算法分析例1.4一個算法所需時間由以下遞歸方程表示，分析算法的時間復(fù)雜度。

根據(jù)以上遞歸方程，可得T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=2*2T(n-2)+2+1=2*2*(2T(n-3)+1)+2+1=……=2k-1(2T(n-k)+1)+2k-2+…+2+1=…=2n-2(2T(1)+1)+2n-2+…+2+1=2n-1+…+2+1=2n-1因此，該算法的時間復(fù)雜度為O(2n)。1.5算法分析1.5.4算法空間復(fù)雜度空間復(fù)雜度（spacecomplexity）作為算法所需存儲空間的量度，記作S(n)=O(f(n))。n為問題的規(guī)模，f(n)為語句關(guān)于n的所占存儲空間的函數(shù)。例1.5以下是一個簡單插入排序算法，分析算法的空間復(fù)雜度。for(i=0;i<n-1;i++){

t=a[i+1];

j=i;

while(j>=0&&t<a[j]){

a[j+1]=a[j];

j=j-1;}

a[j+1]=t;}該算法借助了變量t，與問題規(guī)模n的大小無關(guān)，空間復(fù)雜度為O(1)。1.5算法分析1.5.4算法空間復(fù)雜度例1.6以下算法是求n個數(shù)中的最大者，分析算法的空間復(fù)雜度。intFindMax(inta[],intn){

if(n<=1)

returna[0];

else:

intm=FindMax(a,n-1);

returna[n-1]>=m?a[n-1]:m;}設(shè)FindMax(a,n)占用的臨時空間為S(n)，由以上算法可得到以下占用臨時空間的遞推式。因此，該算法的空間復(fù)雜度為O(n)。1.6關(guān)于數(shù)據(jù)結(jié)構(gòu)課程的地位及學(xué)習(xí)方法明確數(shù)據(jù)結(jié)構(gòu)的重要性，樹立學(xué)好數(shù)據(jù)結(jié)構(gòu)的信心熟練掌握程序設(shè)計(jì)語言，變腐朽為神奇結(jié)合生活實(shí)際，變抽象為具體多思考，多上機(jī)實(shí)踐1.6關(guān)于數(shù)據(jù)結(jié)構(gòu)課程的地位及學(xué)習(xí)方法1.數(shù)據(jù)結(jié)構(gòu)的前世今生唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程是從1968年開始在美國設(shè)立的。Donald的經(jīng)典巨著《計(jì)算機(jī)程序設(shè)計(jì)的藝術(shù)》（TheArtofComputerProgramming），與愛因斯坦《相對論》、狄拉克《量子力學(xué)》、理查?費(fèi)曼《量子電動力學(xué)》等經(jīng)典比肩。高德納在36歲時就榮獲1974年度的圖靈獎。DonaldErvinKnuth教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。1.6關(guān)于數(shù)據(jù)結(jié)構(gòu)課程的地位及學(xué)習(xí)方法2.數(shù)據(jù)結(jié)構(gòu)的地位與作用數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)已經(jīng)不僅僅是計(jì)算機(jī)相關(guān)專業(yè)的核心課程，還是其他非計(jì)算機(jī)專業(yè)的主要選修課程之一。算術(shù)表達(dá)式求值問題、迷宮求解、機(jī)器學(xué)習(xí)中的決策樹分類等分別利用了數(shù)據(jù)結(jié)構(gòu)中的棧、樹進(jìn)行解決。數(shù)據(jù)結(jié)構(gòu)也是學(xué)習(xí)操作系統(tǒng)、軟件工程、人工智能、算法設(shè)計(jì)與分析、機(jī)器學(xué)習(xí)、大數(shù)據(jù)等眾多后繼課程的重要基礎(chǔ)。參考書目：1、李春葆，《數(shù)據(jù)結(jié)構(gòu)（第5版）》，清華大學(xué)出版社。2、耿國華，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，高等教育出版社。3、陳銳，馬軍霞，張建偉等，《數(shù)據(jù)結(jié)構(gòu)（C語言實(shí)現(xiàn)）》，機(jī)械工業(yè)出版社4、陳銳、張志鋒、馬軍霞等，《數(shù)據(jù)結(jié)構(gòu)與算法詳解》，人民郵電出版社。5、嚴(yán)蔚敏，吳偉民，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版社。6、潘金貴譯，《算法導(dǎo)論》，機(jī)械工業(yè)出版社。7、《算法（第4版）》，人民郵電出版社。8、陳銳、張建偉、馬軍霞等，《數(shù)據(jù)結(jié)構(gòu)習(xí)題精解》，清華大學(xué)出版社。感謝聆聽主講：結(jié)構(gòu)實(shí)據(jù)現(xiàn)數(shù)Java第2章線性表結(jié)構(gòu)Java實(shí)據(jù)現(xiàn)數(shù)目錄CONTENTS2.1

線性表的定義及抽象數(shù)據(jù)類型2.2線性表的順序表示與實(shí)現(xiàn)2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)2.7小結(jié)2.6一元多項(xiàng)式的表示與相乘2.4循環(huán)單鏈表2.5雙向鏈表2.1線性表的定義及抽象數(shù)據(jù)類型1.線性表的定義唐·歐·克努特（DonaldErvinKnuth）教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。英文單詞“China”“Science”“Structure”等就屬于線性結(jié)構(gòu)，其中的每一個英文字母就是一個數(shù)據(jù)元素，數(shù)據(jù)元素之間存在著一對一的順序關(guān)系。如“China”中字母“C”的直接后繼是字母“h”，字母“h”的直接后繼是字母“i”。線性表是由n個類型相同的數(shù)據(jù)元素組成的有限序列，記(a1,a2,…,ai-1,ai,ai+1,…,an)。數(shù)據(jù)元素可以是原子類型，也可以是結(jié)構(gòu)類型。在線性表中，數(shù)據(jù)元素ai-1稱為ai的直接前驅(qū)元素，ai稱為ai-1的直接后繼元素。2.1線性表的定義及抽象數(shù)據(jù)類型一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(xiàng)組成，如圖2.2所示的一個學(xué)校的教職工情況表，一個數(shù)據(jù)元素由姓名、性別、出生年月、籍貫、學(xué)歷、職稱及任職時間七個數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)元素也稱為記錄。2.1線性表的定義及抽象數(shù)據(jù)類型學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力ADTList{

數(shù)據(jù)對象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}

基本操作：（1）InitList(&L)

初始條件：表L不存在。操作結(jié)果：建立一個空的線性表L。這就像日常生活中，新生入學(xué)剛建立一個學(xué)生情況表，準(zhǔn)備登記學(xué)生信息。（2）ListEmpty(L)

初始條件：表L存在。操作結(jié)果：若表L為空，返回1，否則返回0。這就像日常生活中，剛剛建立了學(xué)生情況表，還沒有學(xué)生來登記。2.1線性表的定義及抽象數(shù)據(jù)類型學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（3）GetElem(L,i,&e)

初始條件：表L存在，且i值合法，即1≤i≤ListLength(L)。操作結(jié)果：返回表L的第i個位置元素值給e。這就像在學(xué)生情況表查找一個學(xué)生，將查到的學(xué)生情況報(bào)告給老師。（4）LocateElem(L,e)

初始條件：表L存在，且e為合法元素值。操作結(jié)果：在表L中查找與給定值e相等的元素。如果查找成功，則返回該元素在表中的序號；如果這樣的元素不存在，則返回0。這就像在學(xué)生情況表查找一個學(xué)生，只報(bào)告是否找到這個學(xué)生，并不報(bào)告這個學(xué)生的基本情況。（5）InsertList(&L,i,e)

初始條件：表L存在，e為合法元素且1≤i≤ListLength(L)。操作結(jié)果：在表L中的第i個位置插入新元素e。這就像新來了一個學(xué)生報(bào)到，被登記到學(xué)生情況表中。2.1線性表的定義及抽象數(shù)據(jù)類型學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力（6）DeleteList(&L,i,&e)

初始條件：表L存在且1≤i≤ListLength(L)。操作結(jié)果：刪除表L中的第i個位置元素，并用e返回其值。這就像一個學(xué)生違反了校規(guī)，被學(xué)校開除，需要把該學(xué)生從學(xué)生情況表中刪除。（7）ListLength(L)

初始條件：表L存在。操作結(jié)果：返回表L的元素個數(shù)。這就像學(xué)校招了新生之后，需要統(tǒng)計(jì)下學(xué)生的總?cè)藬?shù)，查找下學(xué)生情況表，看有多少個學(xué)生。（8）ClearList(&L)

初始條件：表L存在。操作結(jié)果：將表L清空。這就像學(xué)生已經(jīng)畢業(yè)，不再需要保留這些學(xué)生信息，將這些學(xué)生信息全部清空。}ADTList2.2線性表的順序表示與實(shí)現(xiàn)2.2.1線性表的順序存儲線性表的順序存儲指的是將線性表中的各個元素依次存放在一組地址連續(xù)的存儲單元中。用這種方法存儲的線性表稱為順序表。順序表具有以下特征：邏輯上相鄰的元素，在物理上也是相鄰的。

假設(shè)線性表有n個元素，每個元素占用m個存儲單元，如果第一個元素的存儲位置為LOC(a1)，第i個元素的存儲位置為LOC(ai)，第i+1個元素的存儲位置為LOC(ai+1)。則線性表的第i+1個元素的存儲位置與第i個元素的存儲位置滿足以下關(guān)系：LOC(ai+1)=LOC(ai)+m2.2線性表的順序表示與實(shí)現(xiàn)2.2.1線性表的順序存儲線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存取的存儲結(jié)構(gòu)。只要知道其中一個元素的存儲地址，就可以得到線性表中任何一個元素的存儲地址。線性表的順序存儲結(jié)構(gòu)如圖2.3所示。2.2線性表的順序表示與實(shí)現(xiàn)2.2.1線性表的順序存儲由于在Java語言中，數(shù)組具有隨機(jī)存取、且存儲地址連續(xù)的特點(diǎn)，因此，可采用數(shù)組來存儲順序表中的元素。publicclassSeqList<T>{staticfinalintLISTSIZE=100;privateintlength;Tlist[];}LISTSIZE表示數(shù)組能容納的元素個數(shù)，length表示當(dāng)前數(shù)組中存儲的元素個數(shù)，list[]用于存儲線性表中的元素。2.2線性表的順序表示與實(shí)現(xiàn)2.2.2順序表的基本運(yùn)算①順序表的構(gòu)造方法。SeqList(){list=(T[])newInteger[LISTSIZE];length=0;}②判斷線性表是否為空。publicbooleanListEmpty()//判斷線性表是否為空{(diào)if(length==0)returntrue;elsereturnfalse;

}2.2線性表的順序表示與實(shí)現(xiàn)2.2.2順序表的基本運(yùn)算③按序號查找。publicTGetElem(inti)//取線性表中某一位置上的元素值{if(i>=1&&i<=length)returnlist[i-1];elsethrownewIllegalArgumentException("i超出了線性表的有效范圍！");}2.2線性表的順序表示與實(shí)現(xiàn)2.2.2順序表的基本運(yùn)算④按內(nèi)容查找。從線性表中的第一個元素開始，依次與e比較，如果相等，返回該序號表示成功；否則返回0表示查找失敗。publicintLocateElem(Tx){inti;for(i=0;i<length;i++){if(list[i]==x)returni+1;}return-1;}2.2線性表的順序表示與實(shí)現(xiàn)2.2.2順序表的基本運(yùn)算⑤插入操作。插入操作就是在線性表L中的第i個位置插入新元素e，使線性表{a1,a2,…,ai-1,ai,…,an}變?yōu)閧a1,a2,…,ai-1,e,ai,…,an}，線性表的長度也由n變成n+1。例如，在線性表{9,12,6,15,20,10,4,22}中，要在第5個元素之前插入1個元素28，需要將序號為8、7、6、5的元素依次向后移動1個位置，然后在第5號位置插入元素28，這樣，線性表就變成了{(lán)9,12,6,15,28,20,10,4,22}，如圖2-3所示。2.2線性表的順序表示與實(shí)現(xiàn)2.2.2順序表的基本運(yùn)算publicbooleanInsertList(inti,Te){if(length>=LISTSIZE){System.out.println("順序表空間已滿!");returnfalse;}if(i<1||i>length+1){System.out.println("插入位置不合法");returnfalse;}else{for(intj=length;j>i-1;j=j-1)list[j]=list[j-1];list[i-1]=e;length+=1;returntrue;}}2.2線性表的順序表示與實(shí)現(xiàn)2.2.2順序表的基本運(yùn)算⑥刪除第i個元素。刪除第i個元素之后，線性表{a1,a2,…,ai-1,ai,ai+1,…,an}變?yōu)閧a1,a2,…,ai-1,ai+1,…,an}，線性表的長度由n變成n-1。例如要刪除線性表{9,12,6,15,28,20,10,4,22}的第4個元素，需要依次將序號為5、6、7、8、9的元素向前移動一個位置，并將表長減1，如圖2-4所示。2.2線性表的順序表示與實(shí)現(xiàn)2.2.2順序表的基本運(yùn)算publicbooleanDeleteList(inti)

{

if(i>=1&&i<length){

for(intj=i;j<length;j++)

list[j-1]=list[j];

length-=1;

returntrue;

}

else

returnfalse;

}2.2線性表的順序表示與實(shí)現(xiàn)⑦求線性表的長度。publicintListlength(){returnlength;}⑧清空順序表。publicvoidClearList(){length=0;}2.2.2順序表的基本運(yùn)算2.2線性表的順序表示與實(shí)現(xiàn)在順序表的實(shí)現(xiàn)算法中，除了按內(nèi)容查找運(yùn)算、插入和刪除操作外，算法的時間復(fù)雜度均為O（1）。在按內(nèi)容查找的算法中，若要查找的是第一個元素，則僅需要進(jìn)行一次比較；若要查找的是最后一個元素，則需要比較n次才能找到該元素（設(shè)線性表的長度為n）。設(shè)Pi表示在第i個位置上找到與e相等的元素的概率，若在任何位置上找到元素的概率相等，即Pi=1/n，則查找元素需要的平均比較次數(shù)為

==，因此，按內(nèi)容查找的平均時間復(fù)雜度為O（n）。2.2.3基本操作性能分析=2.2線性表的順序表示與實(shí)現(xiàn)在順序表的插入算法中，時間的耗費(fèi)主要集中在移動元素上。設(shè)pi為在第i個位置上插入元素的概率，假設(shè)在任何位置上找到元素的概率相等，即pi=1/(n+1)，則順序表的插入操作需要移動元素的平均次數(shù)為：2.2.3基本算法性能分析插入操作的平均時間復(fù)雜度為O(n)。2.2線性表的順序表示與實(shí)現(xiàn)在順序表的刪除算法中，時間的耗費(fèi)同樣在移動元素上。設(shè)pi表示刪除第i個位置上的元素的概率，假設(shè)在任何位置上找到元素的概率相等，即pi=1/n，則順序表的刪除操作需要移動元素的平均次數(shù)為：2.2.3基本操作的性能分析刪除操作的平均時間復(fù)雜度為O(n)。2.2線性表的順序表示與實(shí)現(xiàn)staticvoidUnionAB(SeqList<Integer>LA,SeqList<Integer>LB)//合并順序表LA和LB的元素，并保持非遞減排列{inti=1,pos;Integere;while(i<=LB.Listlength()){e=LB.GetElem(i);//取出順序表LA中第i個元素

pos=LA.LocateElem(e);if(pos==-1)//若LA中的元素小于LB中的元素

{LA.InsertList(LA.Listlength()+1,e);//則將當(dāng)前元素插入到LA中

}i+=1;}

}【例2.1】假設(shè)線性表LA和LB分別表示兩個集合A和B，利用線性表的基本運(yùn)算實(shí)現(xiàn)新的集合A=AB，即擴(kuò)大線性表ListA，將存在于線性表LB中且不存在于LA中的順序表LA中有10個元素:11121314151617181920順序表LB中有6個元素:4812162024將LB中不存在LA的元素合并到LA中，LA中有13個元素:1112131415161718192048242.2線性表的順序表示與實(shí)現(xiàn)【例2-2】編寫一個算法，把一個順序表分拆成兩個部分，使順序表中小于等于0的元素位于左端，大于0的元素位于右端。要求不占用額外的存儲空間。例如順序表（-12,3,-6,-10,20,-7,9,-20）經(jīng)過分拆調(diào)整后變?yōu)椋?12,-20,-6,-10,-7,20,9,3）。staticvoidSplitSeqList(SeqList<Integer>L){inti=0,j=L.Listlength()-1;//指示器i和j分別指示順序表的左端和右端元素

Integere;Integerzero=newInteger(0);while(i<j)//若未掃描完畢所有元素

{while(L.list[i].compareTo(zero)<=-1)//i遇到小于等于0的元素

i++;//略過

while(L.list[j].compareTo(Integer.valueOf(0))>0)//j遇到大于0的元素

j--;//略過

if(i<j){e=L.list[i];L.list[i]=L.list[j];L.list[j]=e;}}

}順序表L中有8個元素:-123-6-1020-79-20調(diào)整后的順序表L的元素依次為：

-12-20-6-10-72093【考研真題】設(shè)將n（n>1）個整數(shù)存放到一維數(shù)組R中，試設(shè)計(jì)一個在時間和空間兩方面都盡可能高效的算法，將R中保存的序列循環(huán)左移p（0<p<n）個位置，即把R中的數(shù)據(jù)序列由(x0,x1,…,xn-1)變換為(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。要求如下。（1）給出算法的基本設(shè)計(jì)思想。（2）根據(jù)設(shè)計(jì)思想，采用Java語言描述算法。（3）說明所設(shè)計(jì)算法的時間復(fù)雜度和空間復(fù)雜度。【分析】該題目主要考查對順序表的掌握情況，具有一定的靈活性。（1）先將這n個元素序列(x0,x1,…,xp,xp+1,…,xn-1)就地逆置，得到(xn-1,xn-2,…,xp,xp-1,…,x0)，然后再將前n-p個元素(xn-1,xn-2,…,xp)和后p個元素(xp-1,xp-2,…,x0)分別就地逆置，得到最終結(jié)果(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。publicstaticvoidReverse(SeqListR,intleft,intright)

//將n個元素序列逆置{intk=left;intj=right;while(k<j)//若未完成逆置{//將這n個元素序列逆置處理過程

t=R.mylist[k];R.mylist[k]=R.mylist[j];R.mylist[j]=t;k++;j--;}}publicstaticvoidLeftShift(SeqListR,intn,intp)

//將R中保存的序列循環(huán)左移p（0<p<n）個位置{

if(p>0&&p<n)//若循環(huán)左移的位置合法{

Reverse(R,0,n-1);//將全部元素逆置

Reverse(R,0,n-p-1);//逆置前n-p個元素

Reverse(R,n-p,n-1);//逆置后n個元素}}2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)為了表示這些元素之間的邏輯關(guān)系，除了需要存儲元素本身的信息外，還需要存儲指示其后繼元素的地址信息。這兩部分組成的存儲結(jié)構(gòu)，稱為結(jié)點(diǎn)。結(jié)點(diǎn)包括兩個域：數(shù)據(jù)域和指針域。一個采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表(Hou,Geng,Zhou,Hao,Chen,Liu,Yang)的存儲結(jié)構(gòu)如圖2.9所示。2.3.1單鏈表的存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)一般情況下，我們只關(guān)心鏈表的邏輯順序，而不關(guān)心鏈表的實(shí)際存儲位置。通常用箭頭代替指針來連接結(jié)點(diǎn)序列。因此，圖2.9所示的線性表可以形象化為圖2.10所示的序列。

2.3.1單鏈表的存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)在單鏈表的第一個結(jié)點(diǎn)之前增加一個結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以存放線性表的附加信息，如線性表的長度。若帶頭結(jié)點(diǎn)的鏈表為空鏈表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡保鐖D2.12所示。2.3.1單鏈表的存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)classListNode//單鏈表中結(jié)點(diǎn)的存儲結(jié)構(gòu){intdata;ListNodenext;ListNode(intdata,ListNodenext){this.data=data;this.next=next;}ListNode(intdata){this.data=data;}}2.3.1單鏈表的存儲結(jié)構(gòu)2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)①判斷單鏈表是否為空。若單鏈表為空，返回true；否則返回false。publicbooleanListEmpty(){if(head.next==null)returntrue;elsereturnfalse;}2.3.2單鏈表上的基本運(yùn)算2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)②按序號查找操作。從單鏈表的頭指針head出發(fā)，利用結(jié)點(diǎn)的指針域依次掃描鏈表的結(jié)點(diǎn)，并進(jìn)行計(jì)數(shù)，直到計(jì)數(shù)為i，就找到了第i個結(jié)點(diǎn)。如果查找成功，返回該結(jié)點(diǎn)的指針，否則返回null表示查找失敗。publicListNodeGetNode(inti){ListNodecur=head;//標(biāo)記當(dāng)前結(jié)點(diǎn)

intj=1;while(cur!=null&&j<i){cur=cur.next;j++;}if(j==i)returncur;elsereturnnull;}2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)③按內(nèi)容查找，查找元素值為e的結(jié)點(diǎn)。從單鏈表中的頭指針開始，依次與e比較，如果找到返回該元素結(jié)點(diǎn)的指針；否則返回null。publicListNodeLocateElem(inte)

{ListNodep=head.next;//p指向第一個結(jié)點(diǎn)

while(p!=null){if(p.data!=e)//沒有找到與e相等的元素

p=p.next;//繼續(xù)找下一個元素

else//找到與e相等的元素

break;//退出循環(huán)

}returnp;//返回元素值為e的結(jié)點(diǎn)引用

}2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)④定位操作。定位操作與按內(nèi)容查找類似，只是返回的是該結(jié)點(diǎn)的序號。publicintLocatePos(inte){inti;ListNodep;if(ListEmpty())//查找第i個元素之前，判斷鏈表是否為空

return0;p=head.next;i=1;//從第一個結(jié)點(diǎn)開始查找while(p!=null){if(p.data==e)//找到與e相等的元素

returni;//返回該序號

else

//否則繼續(xù)查找

{p=p.next;i=i+1;}}if(p==null)//如果沒有找到與e相等的元素，返回0，表示失敗

return0;}2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)⑤在第i個位置插入元素e。插入成功返回1，否則返回0；如果沒有與e值相等的元素，返回0表示失敗。假設(shè)p指向存儲元素e的結(jié)點(diǎn)，要將p指向的結(jié)點(diǎn)插入pre和pre.next之間，無需移動其他結(jié)點(diǎn)，只需要修改p指向結(jié)點(diǎn)的指針域和pre指向結(jié)點(diǎn)的指針域即可。即先把pre指向結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)變成p的直接后繼結(jié)點(diǎn)，然后把p變成pre的直接后繼結(jié)點(diǎn)，如圖2-14所示booleanInsertList(inti,inte){intj=1;ListNodepre;if(i<1)returnfalse;if(i==1){ListNodenewNode=newListNode(e);head=newNode;returntrue;}

else{pre=head;while(pre.next!=null&&j<i-1){pre=pre.next;j++;}if(j!=i-1){System.out.println("插入位置錯誤!");returnfalse;}ListNodenewNode=newListNode(e);newNode.next=pre.next;pre.next=newNode;returntrue;}}2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)⑥刪除第i個結(jié)點(diǎn)。假設(shè)p指向第i個結(jié)點(diǎn)，要將該結(jié)點(diǎn)刪除，只需要使它的直接前驅(qū)結(jié)點(diǎn)的指針指向它的直接后繼結(jié)點(diǎn)，即可刪除鏈表的第i個結(jié)點(diǎn)。將單鏈表中第i個結(jié)點(diǎn)刪除可分為3步：

第1步找到第i個結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，即第i-1個結(jié)點(diǎn)，并用pre指向該結(jié)點(diǎn)，p指向其直接后繼結(jié)點(diǎn)，即第i個結(jié)點(diǎn)，如圖2-19所示；

第2步將p指向結(jié)點(diǎn)的數(shù)據(jù)域賦值給e；

第3步刪除第i個結(jié)點(diǎn)，即pre.next=p.next，并釋放p指向結(jié)點(diǎn)的內(nèi)存空間。刪除過程如圖2-20所示。2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)publicintDeleteList(inti)//刪除單鏈表中的第i個位置的結(jié)點(diǎn)。刪除成功返回1，失敗返回0{ListNodepre,p;intj,e;pre=head;j=0;while(pre.next!=null&&j<i-1)//在尋找的過程中確保被刪除結(jié)點(diǎn)存在

pre=pre.next;j++;if(pre.next==null||j!=i-1)//如果沒找到要刪除的結(jié)點(diǎn)位置，說明刪除位置錯誤

{System.out.println("刪除位置錯誤");return0;}

p=pre.next;pre.next=p.next;//將前驅(qū)結(jié)點(diǎn)的指針域指向要刪除結(jié)點(diǎn)的下一個結(jié)點(diǎn)

e=p.data;returne;}2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)⑦求表長操作。求表長操作即返回單鏈表的元素個數(shù)。publicintListLength(){intlength=0;ListNodecur=head;while(cur!=null){cur=cur.next;length++;}returnlength;}2.3.3單鏈表存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)的優(yōu)缺點(diǎn)1．存儲分配方式順序存儲結(jié)構(gòu)用一組連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。單鏈表采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，用一組任意的存儲單元存放線性表的數(shù)據(jù)元素。2．時間性能采用順序存儲結(jié)構(gòu)時，查找操作時間復(fù)雜度為O（1），插入和刪除操作時間復(fù)雜度為O（n）。采用單鏈表存儲結(jié)構(gòu)時，查找操作時間復(fù)雜度為O（n），插入和刪除操作時間復(fù)雜度僅為O(1)。3．空間性能采用順序存儲結(jié)構(gòu)時，需要預(yù)先分配存儲空間。采用單鏈表存儲結(jié)構(gòu)時，可根據(jù)需要臨時分配，不需要估計(jì)問題的規(guī)模大小。2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)【例2-3】已知兩個單鏈表A和B，其中的元素都是非遞減排列，編寫算法將單鏈表A和B合并得到一個遞減有序的單鏈表C（值相同的元素只保留一個），并要求利用原鏈表結(jié)點(diǎn)空間。staticLinkListMergeList(LinkListA,LinkListB)//將非遞減排列的單鏈表A和B中的元素合并到C中，使C中的元素按遞減排列，相同值的元素只保留一個

{ListNodepa,pb,qa,qb;LinkListC=newLinkList();pa=A.head;pb=B.head;

//利用頭插法將鏈表A和B中的結(jié)點(diǎn)插入到鏈表C中（先插入元素值較小的結(jié)點(diǎn)）

while(pa!=null&&pb!=null)//單鏈表A和B均不空時

{if(pa.data<pb.data)//pa指向結(jié)點(diǎn)元素值較小時，將pa指向的結(jié)點(diǎn)插入到C中

{qa=pa;pa=pa.next;

//qa指向待插入結(jié)點(diǎn)，pa指向下一個結(jié)點(diǎn)

if(C.head==null)//單鏈表C為空時，直接將結(jié)點(diǎn)插入到C中

{qa.next=C.head;C.head=qa;}

elseif(C.head.data<qa.data)//pa指向的結(jié)點(diǎn)元素值不同于已有結(jié)點(diǎn)元素值

{qa.next=C.head;C.head=qa;}}2.3線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)else//pb指向結(jié)點(diǎn)元素值較小，將pb指向的結(jié)點(diǎn)插入到C中

{qb=pb;pb=pb.next;//qb指向待插入結(jié)點(diǎn)，pb指向下一個結(jié)點(diǎn)

if(C.head==null)//單鏈表C為空時，直接將結(jié)點(diǎn)插入到C中

{qb.next=C.head;C.head=qb;}

elseif(C.head.data<qb.data)//pb指向的結(jié)點(diǎn)元素值不同于已有結(jié)點(diǎn)元素時

{qb.next=C.head;C.head=qb;}}}while(pa!=null)//如果pb為空、pa不為空，則將pa指向的后繼結(jié)點(diǎn)插入到C中

{qa=pa;pa=pa.next;//qa指向待插入結(jié)點(diǎn)，pa指向下一個結(jié)點(diǎn)

if(C.head!=null&&C.head.data<qa.data){//pa指向的結(jié)點(diǎn)元素值不同于已有結(jié)點(diǎn)元素時，才將結(jié)點(diǎn)插入

qa.next=C.head;C.head=qa;}}

while(pb!=null)//將pb指向的后繼結(jié)點(diǎn)插入C中

{qb=pb;

//qb指向待插入結(jié)點(diǎn)

pb=pb.next;//pb指向下一個結(jié)點(diǎn)

if(C.head!=null&&C.head.data<qb.data)//pb指向的結(jié)點(diǎn)元素值不同于已有結(jié)點(diǎn)元素

{qb.next=C.head;C.head=qb;}}returnC;}}程序的運(yùn)行結(jié)果如下所示。表A中的元素有6個：81015