Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)

Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第1頁。第一章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)1.2有關(guān)概念和術(shù)語1.3算法和算法分析1.3.1算法1.3.2算法設(shè)計的要求1.3.3算法效率的度量1.3.4算法的存儲空間的需求Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第2頁。第一章緒論

計算機學(xué)科一直處于高速發(fā)展中,而且這種發(fā)展速度還會持續(xù)。計算機科學(xué)已經(jīng)難以完全覆蓋學(xué)科新的發(fā)展，因此擴展后的學(xué)科稱為計算學(xué)科。包括：計算機科學(xué)、計算機工程、軟件工程、信息系統(tǒng)Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第3頁。關(guān)鍵問題：利用計算機進(jìn)行信息表示和處理的涉及：信息的表示信息的處理而信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門課所要研究的問題。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第4頁。1.1什么是數(shù)據(jù)結(jié)構(gòu)眾所周知，計算機的程序是對信息進(jìn)行處理。在大多數(shù)情況下，這些信息并不是沒有組織的，信息（數(shù)據(jù)）之間往往具有重要的結(jié)構(gòu)關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)的內(nèi)容。什么是數(shù)據(jù)結(jié)構(gòu)呢？例子：例1、電話號碼查詢系統(tǒng)設(shè)有一個電話號碼薄，它記錄了N個人的名字和其相應(yīng)的電話號碼，假定按如下形式安排：(a1，b1)(a2，b2)…(an，bn)其中(ai，bi)(i=1，2…n)分別表示某人的名字和對應(yīng)的電話號碼。要求設(shè)計一個算法，當(dāng)給定任何一個人的名字時，該算法能夠打印出此人的電話號碼，如果該電話簿中根本就沒有這個人，則該算法也能夠報告沒有這個人的信息。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第5頁。數(shù)據(jù)結(jié)構(gòu)含義：就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對這種結(jié)構(gòu)定義相應(yīng)的運算，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第6頁。所有能被輸入到計算機中，且能被計算機處理的符號的集合。數(shù)據(jù):是計算機操作的對象的總稱。是計算機處理的信息的某種特定的符號表示形式。1.2有關(guān)概念和術(shù)語Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第7頁。是數(shù)據(jù)（集合）中的一個“個體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第8頁。數(shù)據(jù)結(jié)構(gòu)主要指邏輯結(jié)構(gòu)和物理結(jié)構(gòu)數(shù)據(jù)之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。通常分為四類基本結(jié)構(gòu)：一、集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一種類型外，別無其它關(guān)系。二、線性結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的關(guān)系。三、樹型結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對多的關(guān)系。四、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對多的關(guān)系。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第9頁。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)對象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個子集。數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第10頁。數(shù)據(jù)在計算機中的表示稱為數(shù)據(jù)的物理結(jié)構(gòu)，又稱為存儲結(jié)構(gòu)。數(shù)據(jù)對象可以是有限的，也可以是無限的。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類型，也不同于數(shù)據(jù)對象，它不僅要描述數(shù)據(jù)類型的數(shù)據(jù)對象，而且要描述數(shù)據(jù)對象各元素之間的相互關(guān)系。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第11頁。數(shù)據(jù)類型：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類。例1、在FORTRAN語言中，變量的數(shù)據(jù)類型有整型、實型、和復(fù)數(shù)型例2、在C++語言中數(shù)據(jù)類型：基本類型和構(gòu)造類型基本類型：整型、浮點型、字符型構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義數(shù)據(jù)對象：某種數(shù)據(jù)類型元素的集合。例3、整數(shù)的數(shù)據(jù)對象是{…-3，-2，-1，0，1，2，3，…}英文字符類型的數(shù)據(jù)對象是{A，B，C，D，E，F(xiàn)，…}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第12頁。1.3算法和算法分析1.3.1算法：是對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有以下五個特性：（1）有窮性一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。（2）確定性算法中每一條指令必須有確切的含義。不存在二義性。（3）可行性一個算法是可行的。即算法描述的操作都是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的。（4）輸入一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。（5）輸出一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第13頁。1.3.2算法設(shè)計的要求設(shè)計算法時，通常應(yīng)考慮達(dá)到以下目標(biāo)：1、正確性2、可讀性3、健壯性4、高效率與低存儲量需求Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第14頁。1．正確性

首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)格說明”方式給出的需求。

其次，對算法是否“正確”的理解可以有以下四個層次：a．程序中不含語法錯誤；b．程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第15頁。

c．程序?qū)τ诰倪x擇的、典型、苛刻且?guī)в械箅y性的幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果；通常以第c層意義的正確性作為衡量一個算法是否合格的標(biāo)準(zhǔn)。

d．程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果；Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第16頁。2.可讀性

算法主要是為了人的閱讀與交流，其次才是為計算機執(zhí)行，因此算法應(yīng)該易于人的理解；另一方面，晦澀難讀的程序易于隱藏較多錯誤而難以調(diào)試。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第17頁。3．健壯性

當(dāng)輸入的數(shù)據(jù)非法時，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個表示錯誤或錯誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第18頁。4．高效率與低存儲量需求

通常，效率指的是算法執(zhí)行時間；存儲量指的是算法執(zhí)行過程中所需的最大存儲空間，兩者都與問題的規(guī)模有關(guān)。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第19頁。1.3.3算法效率的度量通常有兩種衡量算法效率的方法:事后統(tǒng)計法事前分析估算法缺點：1．必須執(zhí)行程序2．其它因素掩蓋算法本質(zhì)Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第20頁。和算法執(zhí)行時間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機器代碼的質(zhì)量5．計算機執(zhí)行指令的速度Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第21頁。一個特定算法的“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第22頁。

假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)

的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時間復(fù)雜度。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第23頁。如何估算算法的時間復(fù)雜度？Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第24頁。算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時間

=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時間

算法的執(zhí)行時間

與

原操作執(zhí)行次數(shù)之和

成正比

Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第25頁。

從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運行時間的衡量準(zhǔn)則。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第26頁。voidmult(inta[],intb[],intc[]){

for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i][j]=0;

for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];

}//for}//mult基本操作:

乘法操作時間復(fù)雜度:

O(n3)例1Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第27頁。例２

{++x;s=0;}

將x自增看成是基本操作，則語句頻度為1

，即時間復(fù)雜度為Ｏ(1)如果將s=0也看成是基本操作，則語句頻度為1，其時間復(fù)雜度仍為Ｏ(1)，即常量階。例３

for(i=1;i<=n;++i){++x;s+=x;}

語句頻度為：n其時間復(fù)雜度為：O(n)

即時間復(fù)雜度為線性階。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第28頁。i=0:賦值１次i=1:賦值2次i=2:賦值3次i=n-1:賦值n次……………..+1+2+3+…+n=(1+n)n/2=n2/2+n/2例４

for(i=1;i<=n;++i)for(j=1;j<=n;++j){++x;s+=x;}

語句頻度為：n2

其時間復(fù)雜度為：O(n2)

即時間復(fù)雜度為平方階。例５

for(i=0;i<=n-1;++i)for(j=0;j<=i;++j)a[i][j]=0;Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第29頁。

定義：如果f(n)是正整數(shù)n的一個函數(shù)，若存在兩個正常數(shù)c和n0，對于所有的n≥n0，有︱f(n)︳≤c｜g(n)|，則記作f(n)=O(g(n))例：f(x)=anxn+an-1xn-1+…..+a1x+a0，其中an不等0，n為正整數(shù)，則f(x)=O(xn)證明：|f(x)|=|anxn+an-1xn-1+…..+a1x+a0|≦|anxn|+|an-1xn-1|+…+|a1x|+|a0|=|an|*|xn|+|an-1|*|xn-1|+…+|a1|*|x1|+|a0|*|x0|當(dāng)x>1=n0，n為正整數(shù)時，xn+1>xn，所以：|an|*|xn|+|an-1|*|xn-1|+…+|a1|*|x1|+|a0|*|x0|≤|an|*|xn|+|an-1|*|xn|+…+|a1|*|xn|+|a0|*|xn|=(|an|+|an-1|+…+|a1|+|a0|)|xn|=c|xn|其中：n0=1,c=|an|+|an-1|+…+|a1|+|a0|,g(n)=xnJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第30頁。一個算法時間為O(1)的算法，它的基本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)（即零次多項式）來限界。而一個時間為O(n2)的算法則由一個二次多項式來限界。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第31頁。以下六種計算算法時間的多項式是最常用的。其關(guān)系為：

O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)指數(shù)時間的關(guān)系為：

O(2n)<O(n!)<O(nn)

當(dāng)n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第32頁。1.3.4算法的存儲空間的需求算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第33頁。算法的存儲量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間3．輔助變量所占空間Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第34頁。若輸入數(shù)據(jù)所占空間只取決于問題本身，和算法無關(guān)，則只需要分析除輸入和程序之外的輔助變量所占額外空間。若所需額外空間相對于輸入數(shù)據(jù)量來說是常數(shù)，則稱此算法為原地工作。若所需存儲量依賴于特定的輸入，則通常按最壞情況考慮。注意：時間與空間往往是對矛盾，要綜合考慮。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第35頁。－最壞時間復(fù)雜性例6：有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。例如：voidbubble-sort(inta[]，intn)for(i=n-1;i>0;i--)for(j=0;j<i;++j)if(a[j]>a[j+1])a[j]←→a[j+1];}

時間：

最好情況：0次最壞情況：每次都換，Ｏ(n2)空間：一個數(shù)據(jù)交換的輔助空間--算法原地工作。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第36頁。例7：遞歸程序的分析intfact(intn){if(n==1)return1;elsereturnn*fact(n-1);}f(n)=c+f(n-1)=c+(c+f(n-2))=2c+f(n-2)………=(n-1)c+f(1)=(n-1)c+c0Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第37頁。課時安排與考核學(xué)分3:授課2.5(40課時)上機0.5(8+8課時)考核:平時成績20%作業(yè)(課后與課堂)、實驗課程考試80%

Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第38頁。作業(yè)：１.計算時間復(fù)雜度

sum=1;for(i=0;sum<n;i++)sum+=i;2.設(shè)給定若干n值，比較兩函數(shù)n2和50nlog2n的增長趨勢，并確定在什么范圍內(nèi)，函數(shù)n2的值大于50nlog2n的值。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第39頁。第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實現(xiàn)2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.3.1線性鏈表2.3.2循環(huán)鏈表2.3.3雙向鏈表2.4一元多項式的表示及相加Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第40頁。2.1線性表的邏輯結(jié)構(gòu)

線性表：由n(n≥0)個數(shù)據(jù)元素(結(jié)點)a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：(a1，a2，…an)

這里的數(shù)據(jù)元素ai(1≤i≤n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。（6，17，28，50，92，188）Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第41頁。…….…….…….……..……..神經(jīng)衰弱17男790634張立立健康21男790633劉建平一般20女790632陳紅健康18男790631王小林健康情況年齡性別學(xué)號姓名例3、學(xué)生健康情況登記表如下：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第42頁。

從以上例子可看出線性表的邏輯特征是：(1)對非空的線性表，有且僅有一個開始結(jié)點a1，它沒有直接前驅(qū)，而僅有一個直接后繼a2；(2)有且僅有一個終端結(jié)點an，它沒有直接后繼，而僅有一個直接前驅(qū)an-1；(3)其余的內(nèi)部結(jié)點ai(2≤i≤n-1)都有且僅有一個直接前驅(qū)ai-1和一個直接后繼ai+1。

線性表是一種典型的線性結(jié)構(gòu)。數(shù)據(jù)的運算是定義在邏輯結(jié)構(gòu)上的，而運算的具體實現(xiàn)則是在存儲結(jié)構(gòu)上進(jìn)行的。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第43頁。2.2線性表的順序存儲結(jié)構(gòu)2.2.1線性表把線性表的結(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。假設(shè)線性表的每個元素需占用m個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置作為參考點。則線性表中第i+1個數(shù)據(jù)元素的存儲位置Loc(ai+1)和第i個數(shù)據(jù)元素的存儲位置Loc(ai)之間滿足下列關(guān)系：

Loc(ai+1)=Loc(ai)+maiai+1Loc(ai+1)m個字節(jié)Loc(ai)Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第44頁。線性表的第i個數(shù)據(jù)元素ai的存儲位置為:a1a2aianLoc(a1)i-1個元素Loc(ai)=(i-1)*m+Loc(a1)=Loc(a1)-m+i*m由于Loc(a1)和m都是已知的所以：V0=Loc(a1)-mLoc(ai)=V0+i*mJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第45頁。

由于在高級語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，利用C++語言的結(jié)構(gòu)類型來定義順序表類型。

#defineListSize100//表容量

typedefintDataType;//以int為例

structSqlist{DataTypedata[ListSize];intlenth;//當(dāng)前表中元素數(shù)};lenth………..SqlistdataListSize個Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第46頁。2.2.2順序表上實現(xiàn)的基本操作在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。注意：C/C++語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素位置是L.data[i-1]。

線性表的插入和刪除兩種運算。1、插入線性表的插入運算是指在表的i(1≤i≤n+1)個位置上，插入一個新結(jié)點x，使長度為n的線性表(a1，…ai-1，ai，…，an)

變成長度為n+1的線性表(a1，…ai-1，x，ai，…，an)Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第47頁。注：可用memmove(L.data+i,L.dada+i-1,(L.lenth-i+1)*sizeof(DataType))代替for循環(huán)（包含文件：string.h,一般格式格式：memmove(目的地址，源地址，移動字節(jié)數(shù)))voidInsertList(L,x,i)//在線性表L中第i個位置插入元素x{if(i<1||i>L.length+1){cout<<“插入序號錯誤”<<endl;returnERROR;}if(L.length>=ListSize)溢出處理；else{for(j=L.length-1;j>=i-1;j--)//第i個元素（下標(biāo)為i-1)開始

L.data[j+1]=L.data[j];//順序后移

L.data[i-1]=x;L.length++;}}

Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第48頁。memcpy(目的地址,源地址，字節(jié)數(shù)）memset(目的地址,字符，字節(jié)數(shù)）inta[50][50],b[50][50];a清0for(i=0;i<50;i++)for(j=0;j<50;j++)a[i][j]=0;拷貝：for(i=0;i<50;i++)for(j=0;j<50;j++)b[i][j]=a[i][j];memset(a,’\0’,sizeof(a))memcpy(b,a,sizeof(a))memcpy與memmove的差異：后者允許地址重疊Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第49頁。算法分析設(shè)表的長度為n。該算法的時間主要化費在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動結(jié)點的次數(shù)）是n-i+1。由此，所需移動結(jié)點的次數(shù)依賴于(1)表的長度(2)插入位置。當(dāng)=n+1時，不移動->最好情況；當(dāng)=1時，需移動表中所有結(jié)點->最壞情況，a1，…ai-1，ai，…，anx移動數(shù)據(jù)：n-i+1Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第50頁。算法的平均移動

由于插入可能在表中任何位置上進(jìn)行，在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+1。Pi代表在第i個位置插入概率，則

Eis(n)=p1×n+p2×(n-1)+….+pn×

1+pn+1×

0

若表中任何位置(1≤i≤n+1)上插入結(jié)點的概率是均等的，則

p1=p2=p3=…=pn+1=1/(n+1)因此，在等概率插入的情況下：

Eis(n)=1/(n+1)[n+(n-1)+…+1+0]=n/2a1，…ai-1，ai，…，an可能的插入點有n+1處Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第51頁。結(jié)論：在順序表上做插入運算，平均要移動表上一半結(jié)點。當(dāng)表長n較大時，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。2、刪除線性表的刪除運算是指將表的第i(1≤i≤n)結(jié)點刪除，使長度為n的線性表：(a1，…ai-1，ai，ai+1…，an)變成長度為n-1的線性表(a1，…ai-1，ai+1，…，an)Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第52頁。voiddeleteList(L,i)//表L中刪除第i個元素{

if(i<1||i>L.length){cout<<“刪除序號錯”<<endl;returnERROR;}for(j=i;j<=L.length-1;j++)L.data[j-1]=L.data[j];L.length--;}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第53頁。算法分析與插入算法相似，結(jié)點的移動次數(shù)也是由表長n和位置i決定。若i=n，無需移動結(jié)點；若i=1，則前移元素n-1個令Edl表示所需移動結(jié)點的平均次數(shù)，刪除表中第i個結(jié)點的移動次數(shù)為n-i，pi是刪除i個元素的概率，則

Edl=p1×(n-1)+p2×(n-2)+….+pn-1×

1+pn×

0等概率的假設(shè)下：p1=p2=p3=…=pn=1/n

Edl=1/n[(n-1)+(n-2)+…+1+0]=(n-1)/2

即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是O(n)。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第54頁。表溢出問題的說明：指針elem長度lenthlistsize數(shù)據(jù)區(qū)listsize個空間Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第55頁。2.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)2.3.1線性鏈表鏈表是指用一組任意的存儲單元來依次存放線性表的結(jié)點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第56頁。其中：data域是數(shù)據(jù)域，用來存放結(jié)點的值。next是指針域（亦稱鏈域），用來存放結(jié)點的直接后繼的地址（或位置）。鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的。由于上述鏈表的每一個結(jié)只有一個鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。

顯然，單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。同時，由于最后一個結(jié)點無后繼，故結(jié)點的指針域為空，即NULL（圖示中常用^表示)。datanextJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第57頁。例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)示意圖如下：165head:110130160165170200205135......hat200......cat135eat170......matnullbat130fat110......jat205lat160......Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第58頁。

單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。用C++語言描述的單鏈表如下：typedefcharDataType;structLNode{DataTypedata;LNode*next;};eatmat…h(huán)eadbatcat^Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第59頁。一旦p所指的結(jié)點變量不再需要了，應(yīng)該通過deletep；(或用free(p))釋放所指的結(jié)點變量空間。pdatanextLNode*p,*head;

p為動態(tài)變量指針，它可以存放Lnode內(nèi)存塊的首地址，能利用標(biāo)準(zhǔn)函數(shù)使得p與一塊內(nèi)存空間關(guān)聯(lián)，即

p=newLNode;//C++p=(structLNode*)malloc(sizeof(structLNode));/*C*/

new分配了一個類型為LNode的結(jié)點變量的空間并將其首地址放入指針變量p中。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第60頁。一、建立單鏈表

問題：假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，逐個輸入這些字符型的數(shù)據(jù)，并以換行符‘$’為輸入結(jié)束標(biāo)記。動態(tài)地建立單鏈表的常用方法有如下兩種：

1、頭插法建表該方法從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志(比如$）為止。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第61頁。voidCreateList1(LNode*&h){charch;LNode*p; h=NULL;cin>>ch;while(ch!=$′){ p=newLNode; p–>data=ch;p–>next=h;h=p;cin>>ch;}}LNode*CreateList(){charch;LNode*h,*p;h=NULL;cin>>ch;while(ch!=‵$′){p=newLNode;p–>data=ch;p–>next=h;h=p;cin>>ch;}returnh;}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第62頁。#include<iostream.h>structLNode{chardata;LNode*next;};LNode*CreateList(){charch;LNode*h,*p;h=NULL;cin>>ch;while(ch!=‵$′){p=newLNode;p–>data=ch;p–>next=h;h=p;cin>>ch;}returnh;}voidCreateList1(LNode*&h){charch;LNode*p; h=NULL;

cin>>ch;while(ch!=$′){p=newLNode;p–>data=ch;p–>next=h;h=p;cin>>ch;}}voidprint(LNode*h){LNode*p=h;while(p!=NULL){cout<<p->data<<‘‘;p=p->next;}cout<<endl;}voidmain(){LNode*h1,*h2;h1=CreateList();CreateList1(h2);print(h1);print(h2);}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第63頁。2、尾插法建表頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上。為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。例：LNode*creat(){charch;LNode*p,*r,*head;head=r=NULL;cin>>ch;while(ch!=‘$’){p=newLNode;p–>data=ch;if(head==NULL)head=p;

elser->next=p;r=p;cin>>ch;}if(r!=NULL)r->next=NULL;returnhead;}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第64頁。頭結(jié)點（哨兵結(jié)點）引入：增加一個表頭結(jié)點，數(shù)據(jù)域可根據(jù)需要使用或不用。特點：a、表中第一個結(jié)點和在表的其它位置上的操作一致，無需進(jìn)行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結(jié)點。因此空表和非空表的處理統(tǒng)一。NULLhead有頭結(jié)點的空表head=無頭結(jié)點的空表LNode*creat(){LNode*r,*h;charch;h=newLNode;r=h;cin>>ch;while(ch!=‘$’){r->next=newLNode;r=r->next;r->data=ch;cin>>ch;}r->next=NULL;returnh;}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第65頁。

上述算法里動態(tài)申請新結(jié)點空間時未加錯誤處理，在實際使用時間，可作下列判定與處理：

p=newLNode;if(p==NULL)錯誤處理；

Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第66頁。二、查找運算1、按序號查找在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1≤i≤n時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0個結(jié)點，其算法如下：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第67頁。LNode*getnode(head，i)//i≥1//在鏈表head中取第i個數(shù)據(jù)，鏈表有頭結(jié)點{

p=head;j=0;//計數(shù)用

while(p–>next&&j<i){p=p–>next;j++;}if(i==j)returnp;

elsereturnNULL;}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第68頁。2、按值查找按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：LNode*locatenode(head，key){p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;

}

該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第69頁。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化xai-1aiJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第70頁。ai-1aix三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第71頁。ai-1aix三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第72頁。ai-1aixpqq->next=p->next;三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第73頁。ai-1aixpqq->next=p->next;p->next=q;三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第74頁。ai-1aixpqq->next=p->next;p->next=q;三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第75頁。ai-1aixpqq->next=p->next;p->next=q;定位ai-1并將指針p指向它；三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第76頁。ai-1aixpqq=newLNode;q->data=x;q->next=p->next;p->next=q;定位ai-1并將指針p指向它；三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第77頁。ai-1aixpqq=newLNode;q->data=x;q->next=p->next;p->next=q;p=getnode(head，i-1);功能：在頭指針為head的鏈表中定位第i-1個結(jié)點,并返回結(jié)點位置。三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令q指針指向該新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第78頁。三、插入運算

voidinsertnode(head，x，i){LNode*p，*q;p=getnode(head，i-1);if(p==NULL){cout<<“positionerror”<<endl; returnERROR;}q=newLNode;q–>data=x;q–>next=p–>next;p–>next=q;}LNode*getnode(head，i){p=head;j=0;//計數(shù)用

while(p–>next&&j<i){p=p–>next;j++;}if(i==j)returnp;elsereturnNULL;}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第79頁。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：ai-1aiai+1Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第80頁。ai-1aiai+1四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第81頁。ai-1aiai+1四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第82頁。ai-1aiai+1pp->next=p->next->next;四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第83頁。ai-1aiai+1pp->next=p->next->next;問題：鏈表的邏輯結(jié)構(gòu)已正確了，但結(jié)點ai空間丟了。四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第84頁。ai-1aiai+1pp->next=p->next->next;r=p->next;p->next=r->next;deleter;四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第85頁。ai-1aiai+1pp->next=p->next->next;r=p->next;p->next=r->next;deleter;r四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第86頁。ai-1aiai+1pp->next=p->next->next;r=p->next;p->next=r->next;deleter;r四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第87頁。ai-1aiai+1pp->next=p->next->next;p=getnode(head，i-1);r=p->next;p->next=r->next;deleter;r四、刪除運算

刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間。此過程為：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第88頁。四、刪除運算voiddeletelist(head，i){LNode*p，*r;p=getnode(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;deleter;}Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第89頁。從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。作業(yè)：（1）鏈表是有序的，現(xiàn)在插入數(shù)據(jù)x，要求插入后仍然有序（2）鏈表是有序的，現(xiàn)在刪除數(shù)據(jù)x，若x不存在，輸出一段提示信息。要求：按鏈表有頭結(jié)點和無頭結(jié)點兩種情況分別寫出并上機調(diào)試通過。（3）鏈表逆轉(zhuǎn)（沒有頭結(jié)點）Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第90頁。五、靜態(tài)鏈1、靜態(tài)鏈表的概念用一維數(shù)組來實現(xiàn)線性鏈表，這種用一維數(shù)組表示的線性鏈表，稱為靜態(tài)鏈表。靜態(tài)：體現(xiàn)在表的容量是一定的。（數(shù)組的大?。╂湵恚翰迦肱c刪除同前面所述的動態(tài)鏈表方法相同2、靜態(tài)鏈表的類型定義#defineMAXSIZE1000//鏈表的最大長度

structComponent{

ElemTypedata;

intcur;};ComponentVList[MAXSIZE];Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第91頁。SLinkList類型的數(shù)組變量是結(jié)構(gòu)數(shù)組，每一數(shù)組分量包括兩個域：data：用于存儲線性表元素；cur：用于存儲直接后繼元素在數(shù)組中的位置靜態(tài)鏈表圖示0h=5數(shù)組下標(biāo)靜態(tài)鏈表與線性鏈表的區(qū)別？？線性鏈表圖示地址a18a22a4-1a30123456789101010a11026a21014a40a310101012101410221024102610281030102010181016h=1020Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第92頁。例：靜態(tài)鏈表的操作設(shè)插入和刪除只在表的頭上進(jìn)行（棧）h=7（5，7，2，3）（8，5，7，2，3）h=0表中加入x01234793-15123567891001234793-1512356789102.(1)VList[i].data=x;1.在VList中找空位置i(比如0)(2)VList[i].cur=h;x7(3)h=i;Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第93頁?？瘴恢玫臉?biāo)識：將所有空位置構(gòu)成鏈表，用av表示鏈?zhǔn)?12342793-11058451-12365678910av=02.(1)Vlist[i].data=x;1.在VList中找空位置i(2)Vlist[i].cur=h;(3)h=i;if(av==-1)無空間處理else{i=av;av=VList[i].curVList[i].data=x;VList[i].cur=h;h=i;}刪除：if(h!=-1){x=VList[h].data; i=h; h=VList[i].cur;VList[i].cur=av;av=i;

}h=7空表初始化：開始，表是空的，所以：for(i=0;i<n-1;i++)a[i]=i+1;a[n-1]=-1;av=0;Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第94頁。2.3.2循環(huán)鏈表循環(huán)鏈表是一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點的或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示：Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第95頁。⑴非空表⑵空表在用頭指針表示的單鏈表中，找開始結(jié)點a1的時間是O(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n)

a1an…h(huán)eadJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第96頁。在很多實際問題中，表的操作常常是在表的尾位置上進(jìn)行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是rear–>next—>next和rear，顯然，查找時間都是O(1)。因此，實際中也常采用尾指針表示單循環(huán)鏈表.。

a1an…rearJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第97頁。

由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指針或尾指針等。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第98頁。2.3.3雙向鏈表

雙向鏈表(Doublelinkedlist):在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為：structDuLNode{datatypedata;DuLNode*prior，*next;};結(jié)點存儲前趨結(jié)點的地址存儲數(shù)據(jù)元素存儲后繼結(jié)點的地址指針域數(shù)據(jù)域指針域Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第99頁。雙鏈表一般由頭指針唯一確定的，將頭結(jié)點和尾結(jié)點鏈接起來構(gòu)成循環(huán)鏈表，并稱之為雙向鏈表。設(shè)指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述：

p—>prior—>next=p=p—>next—>prior

L（c）非空的雙向循環(huán)鏈表

(b)空的雙向循環(huán)鏈表LpabcJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第100頁。雙向鏈表結(jié)點p前的插如數(shù)據(jù)x的操作：pqxai-1aiq=newDuLNode;q->data=x;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第101頁。雙向鏈表結(jié)點p前的插如數(shù)據(jù)x的操作：pqxq=newDuLNode;q->data=x;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;ai-1aiJava版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第102頁。雙向鏈表結(jié)點p前的插如數(shù)據(jù)x的操作：pqxai-1aiq=newDuLNode;q->data=x;q->prior=p->prior;q->next=p;p->prior->next=q;p->prior=q;Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第103頁。ai+1aip–>prior–>next=p–>next;p–>next–>prior=p–>prior;deletep;p刪除p指針?biāo)傅慕Y(jié)點：ai-1Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第104頁。ai+1aip–>prior–>next=p–>next;p–>next–>prior=p–>prior;deletep;p刪除p指針?biāo)傅慕Y(jié)點：ai-1Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第105頁。ai+1aip–>prior–>next=p–>next;p–>next–>prior=p–>prior;deletep;p刪除p指針?biāo)傅慕Y(jié)點：ai-1

雙向鏈表的插入、刪除靈活；鏈表維護(hù)的工作量大，所需的存儲空間較大。Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第106頁。2．4一元多項式的表示及相加Pn(x)=pnxn+pn-1xn-1+…p1x+p0Qm(x)=qmxm+qm-1xm-1+…q1x+q0一、一元多項式的表示多項式的操作是表處理的典型用例。數(shù)學(xué)上,一元多項式可按降冪寫成：（指數(shù)為正整數(shù)的情況）其中：pn、qm不為0Java版數(shù)據(jù)結(jié)構(gòu)(程序員必須看)全文共1062頁，當(dāng)前為第107頁。

存儲結(jié)構(gòu)：用線性鏈表表示。增加頭結(jié)點，每個結(jié)點有coef:系數(shù)exp指數(shù)next：指針其中