教學(xué)課件：《數(shù)據(jù)結(jié)構(gòu)》陳越

第1章概論【定義】“數(shù)據(jù)結(jié)構(gòu)是計算機(jī)中存儲、組織數(shù)據(jù)的方式。精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來最優(yōu)效率的算法?！?/25§1引子[例1.1]該如何擺放書，才能讓讀者很方便地找到你手里這本《數(shù)據(jù)結(jié)構(gòu)》？第1章概論【分析】2/25§1引子[方法1]隨便放——任何時候有新書進(jìn)來，哪里有空就把書插到哪里。[方法2]按照書名的拼音字母順序排放。[方法3]把書架劃分成幾塊區(qū)域，每塊區(qū)域指定擺放某種類別的圖書；在每種類別內(nèi)，按照書名的拼音字母順序排放。

查找效率極低！

有時插入新書很困難！

可能造成空間的浪費！第1章概論§1引子[例1.2]寫程序?qū)崿F(xiàn)一個函數(shù)PrintN，使得傳入一個正整數(shù)為N的參數(shù)后，能順序打印從1到N的全部正整數(shù)。

voidPrintN(intN){inti;

for(i=1;i<=N;i++)printf(“%d\n”,i);

return;}voidPrintN(intN){if(!N)return;PrintN(N–1);printf(“%d\n”,N);

return;}3/25第1章概論§1引子[例1.3]多項式的標(biāo)準(zhǔn)表達(dá)式可以寫為：

f(x)=a0+a1x+a2x2+…+anxn現(xiàn)給定一個多項式的階數(shù)

n，并將全體系數(shù)存放在數(shù)組a[]里。請寫程序計算這個多項式在給定點x

處的值。[方法1]計算多項式函數(shù)值的直接法

doublef(intn,doublea[],doublex){/*計算階數(shù)為n，系數(shù)為a[0]...a[n]的多項式在x點的值*/

inti;

doublep=a[0];

for(i=1;i<=n;i++) p+=a[i]*pow(x,i);

returnp;}[方法2]秦九韶法

f(x)=a0+x(a1+x(a2+…+x(an)…)doublef(intn,doublea[],doublex){/*計算階數(shù)為n，系數(shù)為a[0]...a[n]的多項式在x點的值*/

inti;

doublep=a[n];

for(i=n;i>0;i--) p=a[i-1]+x*p;

returnp;}4/25秦九韶算法的計算速度明顯比直接法快了一個數(shù)量級！為什么會這樣？第1章概論§1引子5/25#include<stdio.h>#include<time.h>clock_tstart,stop;/*clock_t是clock()函數(shù)返回的變量類型*/doubleduration;/*記錄被測函數(shù)運行時間，以秒為單位*/intmain(){/*不在測試范圍內(nèi)的準(zhǔn)備工作寫在clock()調(diào)用之前*/start=clock();/*開始計時*/function();/*把被測函數(shù)加在這里*/stop=clock(); /*停止計時*/duration=((double)(stop-start))/CLK_TCK;/*計算運行時間*/

/*其他不在測試范圍的處理寫在后面，例如輸出duration的值*/

return0;}代碼1.6測試函數(shù)function()的運行時間即使解決一個非常簡單的問題，往往也有多種方法，且不同方法之間的效率可能相差甚遠(yuǎn)解決問題方法的效率跟數(shù)據(jù)的組織方式有關(guān)（如例1.1）跟空間的利用效率有關(guān)（如例1.2）跟算法的巧妙程度有關(guān)（如例1.3）第1章概論§1引子6/25第1章概論

數(shù)據(jù)對象：

計算機(jī)要處理的事物，如例1.1中“圖書”

。§2.1術(shù)語定義

操作：處理事物的動作集合，如例1.1中的“查找”和“插入”，例1.2的函數(shù)“求值”等。

算法：

操作的實現(xiàn)方法，如例1.1的按字母序排放的“查找”和“插入”、例1.2的“直接法”和例1.3的“秦九韶法”等。

通常一個算法用一個函數(shù)來實現(xiàn)。

邏輯結(jié)構(gòu)：數(shù)據(jù)對象的邏輯組織關(guān)系。分為“線性”、“樹”和“圖”。例1.1中按方法1來處理，就是把圖書集看成是線性的結(jié)構(gòu)；按方法3來處理，就是把圖書集看成是樹形的結(jié)構(gòu)。

物理結(jié)構(gòu)：數(shù)據(jù)對象信息在計算機(jī)內(nèi)存中的存儲組織關(guān)系。一般分為“順序存儲”和“鏈?zhǔn)酱鎯Α薄?/25第1章概論

數(shù)據(jù)類型：

數(shù)據(jù)對象的類型確定了其“操作集”和“數(shù)據(jù)定義域”?！?.2抽象數(shù)據(jù)類型

抽象數(shù)據(jù)類型：

“抽象”的意思，是指我們描述數(shù)據(jù)類型的方法是不依賴于具體實現(xiàn)的，即數(shù)據(jù)對象集和操作集的描述與存放數(shù)據(jù)的機(jī)器無關(guān)、與數(shù)據(jù)存儲的物理結(jié)構(gòu)無關(guān)、與實現(xiàn)操作的算法和編程語言均無關(guān)。簡而言之，抽象數(shù)據(jù)類型只描述數(shù)據(jù)對象集和相關(guān)操作集“是什么”，并不涉及“如何做到”的問題。8/25第1章概論[例1.4]“矩陣”的抽象數(shù)據(jù)類型定義§2.2抽象數(shù)據(jù)類型類型名稱：Matrix數(shù)據(jù)對象集：一個M

N的矩陣A。操作集：對于任意矩陣A、B、C

Matrix，以及正整數(shù)i、j、M、N，以下僅列出幾項有代表性的操作。1）MatrixCreate(intM,intN)：返回一個M

N的空矩陣；2）

intGetMaxRow(MatrixA)：返回矩陣A的總行數(shù)；3）intGetMaxCol(MatrixA)：返回矩陣A的總列數(shù)；4）ElementTypeGetEntry(MatrixA,inti,intj)：返回矩陣A的第i行、第j列的元素；5）MatrixAdd(MatrixA,MatrixB)：如果A和B的行、列數(shù)一致，則返回矩陣C=A+B，否則返回錯誤標(biāo)志；6）MatrixMultiply(MatrixA,MatrixB)：如果A的列數(shù)等于B的行數(shù)，則返回矩陣C=AB，否則返回錯誤標(biāo)志；7）……9/25【定義】一個算法是解決某一類問題的步驟的描述。一般而言，算法應(yīng)該符合以下五項要求：(1)輸入：它接受一些輸入（有些情況下不需要輸入）；(2)輸出：至少產(chǎn)生一個輸出；(3)確定性：算法的每一步必須有充分明確的含義，不可以有歧義；(4)有限性：算法是一個有限指令集，并一定在有限步驟之后終止；(5)

可行性：算法的每一步必須在計算機(jī)能處理的范圍之內(nèi)。第1章概論§3.1算法定義

另外，算法的描述可以不依賴于任何一種計算機(jī)語言以及具體的實現(xiàn)手段?？梢杂米匀徽Z言、流程圖等方法來描述。

但是，用某一種計算機(jī)語言進(jìn)行偽碼描述往往使算法容易被理解，本書即采用C語言的部分語法作為描述算法的工具。10/25〖例〗選擇法排序：把n個整數(shù)從小到大排序。思想：從余下的未排序的部分整數(shù)中，挑選最小整數(shù)放在前面已排序部分的后面.如何進(jìn)行排序?

哪里?voidSelectionSort(intList[],intN){/*將N個整數(shù)List[0]...List[N-1]進(jìn)行非遞減排序*/

for(i=0;i<N;i++){MinPosition=ScanForMin(List,i,N–1);

/*從List[i]到List[N–1]中找最小元，并將其位置賦給MinPosition*/Swap(List[i],List[MinPosition]);

/*將未排序部分的最小元換到有序部分的最后位置*/}}選擇排序=找最小整數(shù)+交換至合適位置.第1章概論§3.1算法例子11/25

具體衡量、比較算法優(yōu)劣的指標(biāo)主要有兩個：

空間復(fù)雜度S(n)——根據(jù)算法寫成的程序在執(zhí)行時占用存儲單元的長度。這個長度往往與輸入數(shù)據(jù)的規(guī)模有關(guān)。空間復(fù)雜度過高的算法可能導(dǎo)致使用的內(nèi)存超限，造成程序非正常中斷。第1章概論§3.2算法復(fù)雜度

時間復(fù)雜度T(n)——根據(jù)算法寫成的程序在執(zhí)行時耗費時間的長度。這個長度往往也與輸入數(shù)據(jù)的規(guī)模有關(guān)。時間復(fù)雜度過高的低效算法可能導(dǎo)致我們在有生之年都等不到運行結(jié)果。

什么是“好”的算法？○例1.2的實現(xiàn)函數(shù)PrintN的遞歸算法S(n)太大?！鹄?.3的秦九韶算法的T(n)比較小。12/25第1章概論§3.2算法復(fù)雜度

例1.2的實現(xiàn)函數(shù)PrintN的遞歸算法的S(n)太大：

S(n)=c·n其中：n是需要打印的整數(shù)的個數(shù)，是變量；c是1個單位的內(nèi)存空間占用存儲單元的長度，為固定常數(shù)。

例1.3的秦九韶算法的T(n)比較?。篢1(n)=c

·n其中：n是多項式的階數(shù)，是變量；c是執(zhí)行1次加法和乘法需要的時間，為固定常數(shù)。

而簡單直接算法的T(n)比較大：T2(n)=c1n2+c2n，其中：n是多項式的階數(shù)，是變量；c1是執(zhí)行1/2次乘法需要的時間；c2是執(zhí)行1次加法和1/2次乘法需要的時間，都是固定常數(shù)。13/25第1章概論§3.2算法復(fù)雜度

我們經(jīng)常關(guān)注下面兩種復(fù)雜度：

最壞情況復(fù)雜度：

Tworst(n)

平均復(fù)雜度：

Tavg(n)

顯然:Tavg(n)≤Tworst(n)。對Tworst(n)

的分析往往比對

Tavg(n)的分析容易。14/25

如果:程序A執(zhí)行了(3n+4)步，程序B執(zhí)行了(2n+2)步，A一定比B慢嗎？

No！

Why?第1章概論§3.3復(fù)雜度的漸進(jìn)表示法

如何來“度量”一個算法的時間復(fù)雜度呢？

首先，它應(yīng)該與運行該算法的機(jī)器和編譯器無關(guān)；

其次，它應(yīng)該與要解決的問題的規(guī)模n有關(guān)；（有時，描述一個問題的規(guī)模需要多個參數(shù)）

再次，它應(yīng)該與算法的“1步”執(zhí)行需要的工作量無關(guān)！

所以，在描述算法的時間性能時，人們只考慮宏觀漸近性質(zhì)，即當(dāng)輸入問題規(guī)模n“充分大”時，觀察算法復(fù)雜度隨著n的“增長趨勢”：當(dāng)變量n不斷增加時，解決問題所需要的時間的增長關(guān)系。

比如：線性增長T(n)=c·n即問題規(guī)模n增長到2倍、3倍……時，解決問題所需要的時間T(n)也是增長到2倍、3倍……（

與c無關(guān)

）

平方增長：T(n)=c·n2即問題規(guī)模n增長到2倍、3倍……時，解決問題所需要的時間T(n)增長到4倍、9倍……（

與c無關(guān)

）15/25第1章概論

引入下面幾種數(shù)學(xué)符號：[定義1.1]T(n)=O(f(n))表示存在常數(shù)c>0,n0>0，使得當(dāng)n≥n0

時有

T(n)≤cf(n)

例1.3中秦九韶算法的時間復(fù)雜度是O(n)

，

而簡單直接法的時間復(fù)雜度是O(n2)

。[定義1.2]T(n)=Ω(g(n))表示存在常數(shù)c>0,n0>0，使得當(dāng)n≥n0

時有

T(n)≥cg(n)§3.3復(fù)雜度的漸進(jìn)表示法[定義1.3]T(n)=Θ(h(n))表示T(n)=O(h(n))

同時T(n)=Ω(h(n))16/25第1章概論

常用函數(shù)增長表§3.3復(fù)雜度的漸進(jìn)表示法輸入規(guī)模n函數(shù)124816321111111log2

n012345n12481632nlog2

n0282464160n21416642561024n318645124096327682n2416256655364294967296n!122440326209227898800026313

103317/252nn2nlognnlognfn第1章概論§3.3復(fù)雜度的漸進(jìn)表示法18/25s=微秒=10-6

秒ms=毫秒=10-3

秒sec=秒min=分yr=年hr=小時d=天n第1章概論§3.3復(fù)雜度的漸進(jìn)表示法19/25第1章概論

對給定的算法做漸進(jìn)分析時，有幾個小竅門：(1)若兩段算法分別有復(fù)雜度T1(n)=O(f1(n))

和

T2(n)=O(f2(n))，▲那么兩段算法串聯(lián)在一起的復(fù)雜度:

T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))

▲那么兩段算法嵌套在一起的復(fù)雜度:

T1(n)×T2(n)=O(f1(n)×f2(n))§3.3復(fù)雜度的漸進(jìn)表示法(2)若

T(n)是關(guān)于n的k階多項式，那么T(n)=Θ(nk)

(3)一個循環(huán)的時間復(fù)雜度等于循環(huán)次數(shù)乘以循環(huán)體代碼的復(fù)雜度。例如下面循環(huán)的復(fù)雜度是O(N)：for(i=0;i<N;i++){x=y*x+z;k++;}(1)若干層嵌套循環(huán)的時間復(fù)雜度等于各層循環(huán)次數(shù)的乘積再乘以循環(huán)體代碼的復(fù)雜度。例如下列2層嵌套循環(huán)的復(fù)雜度是O(N2)：for(i=0;i<N;i++)

for(j=0;j<N;j++){x=y*x+z;k++;}(2)if-else

結(jié)構(gòu)的復(fù)雜度取決于if的條件判斷復(fù)雜度和兩個分枝部分的復(fù)雜度，總體復(fù)雜度取三者中最大。即對結(jié)構(gòu)：if(P1)/*P1的復(fù)雜度為

O(f1)*/P2;/*P2的復(fù)雜度為

O(f2)*/

elseP3;/*P3的復(fù)雜度為

O(f3)*/總復(fù)雜度為max(O(f1),O(f2),O(f3))。20/25〖問題〗給定n個整數(shù)(可以是負(fù)數(shù))的序列{a1,a2,…,an},求函數(shù)f(i,j)=max(0,)的最大值。

若全部整數(shù)都是負(fù)數(shù)，則最大子列和為0.算法1intMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,i,j,k;/*1*/ MaxSum=0;/*初始化最大子列和*//*2*/

for(i=0;i<N;i++)/*i是子列左端位置*//*3*/

for(j=i;j<N;j++){/*j是子列右端位置*//*4*/ ThisSum=0;/*ThisSum是從A[i]到A[j]的子列和*//*5*/

for(k=i;k<=j;k++)/*6*/ ThisSum+=A[k];/*7*/

if(ThisSum>MaxSum)/*如果剛得到的這個子列和更大*//*8*/ MaxSum=ThisSum;/*則更新結(jié)果*/ }/*i，j循環(huán)結(jié)束*//*9*/

returnMaxSum;}T(N)=O(N3)教材p.15有分析.第1章概論§4應(yīng)用實例：最大子列和問題21/25算法2intMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,i,j;/*1*/ MaxSum=0;/*初始化最大子列和*//*2*/

for(i=0;i<N;i++){/*i是子列左端位置

*//*3*/ ThisSum=0;/*ThisSum是從A[i]到A[j]的子列和

*//*4*/

for(j=i;j<N;j++){/*j是子列右端位置*//*5*/ ThisSum+=A[j];/*對于相同的i，不同的j，只要在j-1次循環(huán)的基礎(chǔ)上累加1項即可*//*6*/

if(ThisSum>MaxSum)/*如果剛得到的這個子列和更大*//*7*/ MaxSum=ThisSum;/*則更新結(jié)果*/

}/*j循環(huán)結(jié)束*/ }/*i循環(huán)結(jié)束*//*8*/

returnMaxSum;}T(N)=O(N2)第1章概論§4應(yīng)用實例：最大子列和問題22/25算法3分治法4

35

2

126

2治分45626811T(N/2)T(N/2)O(N)T(N)=2T(N/2)+cN,T(1)=O(1)=2[2T(N/22)+cN/2]+cN=2kO(1)+ckN此處

N/2k=1=O(NlogN)結(jié)論對N

2k同樣正確程序在教材p.16-17第1章概論§4應(yīng)用實例：最大子列和問題23/25該算法的核心思想是基于下面的事實：如果整數(shù)序列

{a1,a2,…,an}的最大和子列是

{ai,ai+1,…,aj}，那么必定有

對任意i≤l≤j

都成立。因此，一旦發(fā)現(xiàn)當(dāng)前子列和為負(fù)，則可以重新開始考察一個新的子列。算法4“在線”算法intMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,j;/*1*/ ThisSum=MaxSum=0;/*2*/

for(j=0;j<N;j++){/*3*/ ThisSum+=A[j];/*4*/

if(ThisSum>MaxSum)/*5*/ MaxSum=ThisSum;/*6*/

else

if(ThisSum<0)/*7*/ ThisSum=0; }/*endfor-j*//*8*/

returnMaxSum;}T(N)=O(N

)序列A[]僅需掃描一遍！

13

24

616

1

1324

6任何時刻,“在線”算法都可以對已經(jīng)讀入的數(shù)據(jù)序列給出正確的最大子列和答案第1章概論§4應(yīng)用實例：最大子列和問題24/25-241-63-150.000340.000630.003330.030420.298320.000660.004860.058430.686318.01130.000450.011121.1233111.13NA0.001030.47015448.77NANAO(N)O(N

logN)O(N2)O(N3)時間復(fù)雜性4321算法N=10N=100N=1,000N=10,000N=100,000子列大小

上述4種算法用于求最大子列和所需的運行時間的比較(單位：秒)注:不包括輸入子列的時間.NA–NotAcceptable,不可接受的時間第1章概論§4應(yīng)用實例：最大子列和問題25/25第2章實現(xiàn)基礎(chǔ)§2.1引子

還是為每個具體應(yīng)用都編一個程序?

類型名稱：數(shù)據(jù)集合的基本統(tǒng)計

數(shù)據(jù)對象集：集合S={，

，…，}

操作集：ElementTypeAverage(S)：求S中元素的平均值；ElementTypeMax(S)：求S中元素的最大值；ElementTypeMin(S)：求S中元素的最小值；ElementTypeMedian(S)：求S中元素的中位數(shù)。

從不同的應(yīng)用中抽象出共性的數(shù)據(jù)組織與操作方法？[例2.1]在日常數(shù)據(jù)處理中經(jīng)常碰到的問題是需要對一組數(shù)據(jù)進(jìn)行基本的統(tǒng)計分析。比如，分析一個課程班學(xué)生的平均成績、最高成績、最低成績、中位數(shù)、標(biāo)準(zhǔn)差等。同樣的統(tǒng)計要求也可能發(fā)生在其他領(lǐng)域。1/25

如何利用程序設(shè)計語言實現(xiàn)上述抽象類型？第2章實現(xiàn)基礎(chǔ)§2.1引子1.數(shù)據(jù)存儲

C語言（包括其他高級語言）提供了數(shù)組、結(jié)構(gòu)、鏈表等。

數(shù)據(jù)結(jié)構(gòu)的存儲實現(xiàn)跟所需要的操作密切相關(guān)。

在數(shù)據(jù)結(jié)構(gòu)里，是利用數(shù)組和鏈表方式來實現(xiàn)的，包括很復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，如圖、樹等。2.操作實現(xiàn)流程控制語句，即分支控制語句（如if-else、switch語句）、循環(huán)控制語句（如for、while、do-while語句）。

此外，還有模塊化的程序設(shè)計方法——函數(shù)ElementTypeAverage(ElementTypeS[],intN){/*求集合元素的平均值。集合元素存放在數(shù)組S中，數(shù)組大小為N*/

int

i;ElementTypeSum=0;

for(i=0;i<N;i++)Sum+=S[i];/*將數(shù)組元素累加到Sum中*/

returnSum/N;}2/25[方法2]基于問題分解

相近的另一個問題是：求集合中的第K大整數(shù)。

當(dāng)K=

N/2

時，集合的第K大整數(shù)就是中位數(shù)。

第2章實現(xiàn)基礎(chǔ)§2.1引子

求中位數(shù)Median(S)[方法1]

基于排序。首先將集合S從大到小排序，第

N/2

（大于等于N/2的最小整數(shù)）個元素就是中位數(shù)。

求解集合第K大整數(shù)問題的一種遞歸思路是：SN個元素S1N1個元素S2N2個元素元素>=e元素<e

當(dāng)K=N1時，

第K大整數(shù)就是e。

當(dāng)K<N1時，第K大整數(shù)是在S1中的第K大整數(shù)。

當(dāng)K>N1時，第K大整數(shù)是在S2中的第(K-N1)大整數(shù)。

比較慢！3/25ElementTypeKthLargest(ElementTypeS[],intK){選取S中的第一個元素e;根據(jù)e將集合S分解為大于等于e的元素集合S1和小于e的元素集合S2;while(|S2|==0)另選一個

e;if(|S1|>K)returnKthLargest(S1，K);elseif(|S1|<K)returnKthLargest(S2，K-|S1|);else

returne;}[例2.2]求集合{659821734}的中位數(shù)?！痉治觥坑捎谠摷嫌?個元素，所以中位數(shù)應(yīng)該是集合從大到小排序后的第

9/2

=5個元素。

首先，選取集合的第一個元素6，根據(jù)這個元素從集合中分解出S1={6，9，8，7}，S2={5，2，1，3，4}。由于|S1|=4<5，所以該中位數(shù)應(yīng)該在集合S2中，且是S2中第(5–4=1)大整數(shù)。

繼續(xù)選取S2中的第一個整數(shù)5，將S2分解出兩個集合S1’={5}，S2’={2,1,3,4}。由于|S1’|=1，所以5就是S2集合的第1大整數(shù)，也就是集合{659821734}的中位數(shù)。第2章實現(xiàn)基礎(chǔ)§1引子4/25第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)

變量是數(shù)據(jù)存儲的基本單位。變量的類型決定了存儲和操作。

幾種基本的數(shù)據(jù)類型：整型、實型（浮點型）、字符型等。

提供了構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)、指針等。數(shù)組數(shù)組是最基本的構(gòu)造類型，它是一組相同類型數(shù)據(jù)的有序集合。數(shù)組中的元素在內(nèi)存中連續(xù)存放，用數(shù)組名和下標(biāo)可以唯一地確定數(shù)組元素。[例2.3]求集合元素的最大值。集合元素存放在數(shù)組A中，數(shù)組大小為N。floatMax(floatA[],intN){/*求N個元素數(shù)組中的最大值*/

floatCurMax=A[0];

inti;

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

if(A[i]>CurMax)CurMax=A[i];

returnCurMax;}5/25指針第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)

指針是C語言中一個非常重要的概念。使用指針可以對復(fù)雜數(shù)據(jù)進(jìn)行處理，能對計算機(jī)的內(nèi)存進(jìn)行分配控制，在函數(shù)調(diào)用中使用指針還可以返回多個值。⑴指針與數(shù)組

數(shù)組名是數(shù)組中第1個元素（下標(biāo)為0）的地址，可以看作是常量指針，不能改變指針常量（數(shù)組名）的值。⑵用指針實現(xiàn)內(nèi)存動態(tài)分配①分配函數(shù)void*malloc(unsignedsize)。②釋放函數(shù)voidfree(void*ptr)。6/25結(jié)構(gòu)結(jié)構(gòu)類型定義的一般形式為：struct

結(jié)構(gòu)名{

類型名結(jié)構(gòu)成員名1;

類型名結(jié)構(gòu)成員名2;

……

類型名結(jié)構(gòu)成員名n;};第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)【定義】結(jié)構(gòu)類型把一些可以是不同類型的數(shù)據(jù)分量聚合成一個整體。同時，結(jié)構(gòu)又是一個變量的集合，可以單獨使用其變量成員。結(jié)構(gòu)變量的使用使用結(jié)構(gòu)變量就是對其成員進(jìn)行操作。格式為：結(jié)構(gòu)變量名.結(jié)構(gòu)成員名。此外，結(jié)構(gòu)變量不僅可以作為函數(shù)參數(shù)，也可以作為函數(shù)的返回值。結(jié)構(gòu)數(shù)組：結(jié)構(gòu)與數(shù)組的結(jié)合結(jié)構(gòu)指針：指向結(jié)構(gòu)的指針（1）用*方式訪問，形式：（*結(jié)構(gòu)指針變量名）.結(jié)構(gòu)成員名（2）用指向運算符“->”訪問指針指向的結(jié)構(gòu)成員，形式：結(jié)構(gòu)指針變量名->結(jié)構(gòu)成員名對結(jié)構(gòu)數(shù)組元素成員的引用是通過使用數(shù)組下標(biāo)與結(jié)構(gòu)成員操作符“.”相結(jié)合的方式來完成的，其一般格式為：結(jié)構(gòu)數(shù)組名[下標(biāo)].結(jié)構(gòu)成員名7/25共用體【定義】共用體類型是指將不同的數(shù)據(jù)項組織成一個整體，它們在內(nèi)存中占用同一段存儲單元。第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)共用體類型定義的一般形式為：union共用體名{

類型名成員名1;

類型名成員名2;

……

類型名成員名n;};

各個成員變量在內(nèi)存中都使用同一段存儲空間，因此共用體變量的長度等于最長的成員的長度。

共用體的訪問方式同結(jié)構(gòu)體類似。intmain(){

unionkey{

intk;

charch[2];}u;u.k=258；printf(“%d%d\n”,u.ch[0],u.ch[1]);return0;}0000001000000001

u.k=258的二進(jìn)制表示：u.ch[0]=2u.ch[1]=18/25鏈表

鏈表是一種重要的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，也是實現(xiàn)復(fù)雜數(shù)據(jù)結(jié)構(gòu)的重要手段。它不按照線性的順序存儲數(shù)據(jù)，而是由若干個同一結(jié)構(gòu)類型的“結(jié)點”依次串接而成的，即每一個結(jié)點里保存著下一個結(jié)點的地址（指針）。

鏈表又分單向鏈表，雙向鏈表以及循環(huán)鏈表等。單向鏈表的結(jié)構(gòu)使用結(jié)構(gòu)的嵌套來定義單向鏈表結(jié)點的數(shù)據(jù)類型。如：structNode{ElementTypeData;

structNode*Next;};第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)structNode*p;p=(structNode*)malloc(sizeof(structNode));9/25head……（1） 插入結(jié)點(p之后插入新結(jié)點t)單向鏈表的常見操作（2） 刪除結(jié)點第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)ptt->Next=p->Next;p->Next=t;

head……pt=p->Next;p->Next=t->next;

10/25（3）單向鏈表的遍歷p=head;while(p!=NULL){……處理p所指的結(jié)點信息；

……p=p->Next;}（4） 鏈表的建立

有兩種常見的插入結(jié)點方式：（1）在鏈表的頭上不斷插入新結(jié)點；（2）在鏈表的尾部不斷插入新結(jié)點。如果是后者，一般需要有一個臨時的結(jié)點指針一直指向當(dāng)前鏈表的最后一個結(jié)點，以方便新結(jié)點的插入。第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)11/25雙向鏈表如果將雙向鏈表最后一個單元的Next指針指向鏈表的第一個單元，而第一個單元的Previous指針指向鏈表的最后一個單元，這樣構(gòu)成的鏈表稱為雙向循環(huán)鏈表。第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)structNode{ElementTypeData;

structNode*Next;

structNode*

Previous;};12/25

雙向鏈表的插入、刪除和遍歷基本思路與單向鏈表相同，但需要同時考慮前后兩個指針。A1A2A3AN…h(huán)eadpt第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)structDNode{ ElementTypeData;

structDNode*Next;

structDNode*Previous;}*p,*t;指針操作順序：①t->Previous=p;②t->Next=p->Next;③p->Next->Previous=t;④p->Next=t;①②③④13/25[例2.4]給定一個單鏈表L，請設(shè)計函數(shù)Reverse將鏈表L就地逆轉(zhuǎn)，即不需要申請新的結(jié)點，將鏈表的第一個元素轉(zhuǎn)為最后一個元素，第二個元素轉(zhuǎn)為倒數(shù)第二個元素……【分析】基本思路是：

利用循環(huán)，從鏈表頭開始逐個處理。

如何把握住循環(huán)不變式。（循環(huán)不變式表示一種在循環(huán)過程進(jìn)行時不變的性質(zhì)，不依賴于前面所執(zhí)行過程的重復(fù)次數(shù)的斷言。）

在每輪循環(huán)開始前我們都面臨兩個序列，其中p是一個待逆轉(zhuǎn)的序列，而q是一個已經(jīng)逆轉(zhuǎn)好的序列，如下圖。

每輪循環(huán)的目的是把p中的第一個元素插入到q的頭上，使這輪循環(huán)執(zhí)行好后，p和q還是分別指向新的待逆轉(zhuǎn)序列和已經(jīng)逆轉(zhuǎn)好的序列。第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)p->Next=q;q=p;t……qpt=p->Next;p->Next=q;q=p;p=t;

structNode*Reverse(structNode*L){structNode*p,*q,*t;

p=L，q=NULL;

while(p!=NULL){

t=p->Next;p->Next=q;q=p;

p=t;

}

returnq;}14/25類型定義typedef第2章實現(xiàn)基礎(chǔ)§2數(shù)據(jù)存儲基礎(chǔ)除了使用C語言提供的標(biāo)準(zhǔn)類型和自己定義的一些結(jié)構(gòu)體、枚舉等類型外，還可以用typedef語句來建立已經(jīng)定義好的數(shù)據(jù)類型的別名。typedef

原有類型名

新類型名typedef

structNode*NodePtr;這樣，Reverse函數(shù)頭就可以寫成：NodePtrReverse(NodePtrL)NodePtrReverse(NodePtrL)/*structNode*Reverse(structNode*L)*/{structNode*p,*q,*t;

p=L，q=NULL;

while(p!=NULL){

t=p->Next;p->Next=q;q=p;

p=t;

}returnq;}15/25第2章實現(xiàn)基礎(chǔ)§3流程控制基礎(chǔ)順序結(jié)構(gòu)是一種自然的控制結(jié)構(gòu)，通過安排語句或模塊的順序就能實現(xiàn)。C語言為分支控制提供了if-else和switch兩類語句，為循環(huán)控制提供了for、while和do-while三類語句。

三種基本的控制結(jié)構(gòu)是順序、分支和循環(huán)。函數(shù)定義函數(shù)調(diào)用函數(shù)遞歸語句級控制單位級控制16/25[例2.5]求100到200之間的所有素數(shù)。[分析]可以設(shè)定兩重循環(huán)：大循環(huán)（外層循環(huán)）控制整數(shù)i在100到200之間變化（用for語句），而小循環(huán)（內(nèi)層循環(huán)）則用來判別i是否是素數(shù)（用while語句）。第2章實現(xiàn)基礎(chǔ)§3流程控制基礎(chǔ)intmain(){

inti,j;

for(i=100;i<=200;i++){/*外層循環(huán)*/

j=2;

while

(j<i&&i%j!=0)j++;

/*內(nèi)層循環(huán),判別i是否是素數(shù)*/

if(j==i)printf(“%d”,i);

/*j==i說明在上面的while循環(huán)中i都不能被j整除，因此i是素數(shù)*/}return

0;}17/25函數(shù)與遞歸比如：C語言提供了實數(shù)和整數(shù)的加法運算符號“+”來完成運算；但是“+”不能對復(fù)數(shù)做加法運算；可以寫一個函數(shù)來實現(xiàn)這個功能。第2章實現(xiàn)基礎(chǔ)§3流程控制基礎(chǔ)【定義】函數(shù)是一個完成特定工作的獨立程序模塊。

只需定義一次，就可以多次調(diào)用。

函數(shù)包括庫函數(shù)和自定義函數(shù)兩種。例如，scanf、printf等庫函數(shù)由C語言系統(tǒng)提供定義，編程時只要直接調(diào)用即可。

在程序設(shè)計中，往往根據(jù)模塊化程序設(shè)計的需要，用戶可以自己定義函數(shù)，屬于自定義函數(shù)。先定義復(fù)數(shù)類型ImgType，以約定何為復(fù)數(shù)：structImage{doubler;doublei;};typedefstructImageImgType;再定義復(fù)數(shù)的加法函數(shù)：ImgTypeImgAdd(ImgTypea,ImgTypeb){ImgTypec;c.r=a.r+b.r;c.i=a.i+b.i;/*實部和虛部分別相加*/

returnc;}有了這個函數(shù)，以后可以在任何需要計算復(fù)數(shù)加法的地方調(diào)用它！18/25

在設(shè)計函數(shù)時，注意掌握以下原則：第2章實現(xiàn)基礎(chǔ)§3流程控制基礎(chǔ)（1）函數(shù)功能的設(shè)計原則：結(jié)合模塊的獨立性原則，函數(shù)的功能要單一，不要設(shè)計多用途的函數(shù)，否則會降低模塊的聚合度；（2）函數(shù)規(guī)模的設(shè)計原則：函數(shù)的規(guī)模要小，盡量控制在50行代碼以內(nèi)，這樣可以使得函數(shù)更易于維護(hù)；（3）函數(shù)接口的設(shè)計原則：結(jié)合模塊的獨立性原則，函數(shù)的接口包括函數(shù)的參數(shù)（入口）和返回值（出口），不要設(shè)計過于復(fù)雜的接口，合理選擇、設(shè)置并控制參數(shù)的數(shù)量，盡量不要使用全局變量，否則會增加模塊的耦合度。19/25

遞歸函數(shù)【定義】一個函數(shù)除了可以調(diào)用其他函數(shù)外，C語言還支持函數(shù)直接或間接調(diào)用自己。這種函數(shù)自己調(diào)用自己的形式稱為函數(shù)的遞歸調(diào)用，帶有遞歸調(diào)用的函數(shù)也稱為遞歸函數(shù)。

兩個關(guān)鍵點：（1） 遞歸出口：即遞歸的結(jié)束條件，到何時不再遞歸調(diào)用下去;第2章實現(xiàn)基礎(chǔ)§2.3流程控制基礎(chǔ)（2） 遞歸式子：當(dāng)前函數(shù)結(jié)果與準(zhǔn)備調(diào)用的函數(shù)結(jié)果之間的關(guān)系，如求階乘函數(shù)的遞歸式子

Factorial(n)=n*Factorial(n-1)longint

Factorial(intn){if(n==0)return1;else

returnn*Factorial(n-1);}注意：程序代碼不能寫成上述式子?。∵f歸調(diào)用20/25[例2.8]設(shè)計函數(shù)求n!圖2.7遞歸求解4!的過程第2章實現(xiàn)基礎(chǔ)§2.3流程控制基礎(chǔ)longint

Factorial(intn){if(n==0)return1;else

returnn*Factorial(n-1);}遞歸出口遞歸式子Factorial(4)4

Factorial(3)3

Factorial(2)2

Factorial(1)1

Factorial(0)11262421/25[例2.9]漢諾塔（TowerofHanoi）問題132132（a）初始狀態(tài)（b）中間狀態(tài)§3流程控制基礎(chǔ)第2章實現(xiàn)基礎(chǔ)【分析】可以用遞歸方法來求解漢諾塔問題，也就是將n個金片的移動問題轉(zhuǎn)換為2個n-1個金片的移動問題。當(dāng)n=1時，就不需要再遞歸了。voidMove(intn,intstart,intgoal,inttemp){

if(n==0)return;Move(n-1,start,temp,goal);printf(“Movedisk%dfrom%dto%d.\n”,n,start,goal);Move(n-1,temp,goal,start);}遞歸調(diào)用22/25§3流程控制基礎(chǔ)第2章實現(xiàn)基礎(chǔ)①Move(3,1,3,2)Move(2,1,2,3)Move(1,1,3,2)Move(0,1,2,3)Move(0,2,3,1)Movedisk2from1to2Move(1,3,2,1)Move(0,3,1,2)Movedisk3from1to3Move(1,2,1,3)Move(0,1,2,3)Movedisk1from3to2Move(0,3,1,2)Move(1,1,3,2)Move(0,1,2,3)Move(0,2,3,1)Move(0,2,3,1)Move(2,2,3,1)Movedisk1from2to1Movedisk1from1to3Movedisk1from1to3②③④⑤⑥⑦M(jìn)ovedisk2from2to323/25[例2.10]用遞歸方法求集合的中位數(shù)。第2章實現(xiàn)基礎(chǔ)§2.3流程控制基礎(chǔ)

根據(jù)前面求解集合第K大整數(shù)問題的遞歸算法思路，還需要解決以下兩個關(guān)鍵問題：（1）如何根據(jù)元素e將集合S分解為S1和S2兩個集合？可以采用臨時申請空間的方法建立一個臨時數(shù)組。（2）如何設(shè)計遞歸函數(shù)的參數(shù)？

將臨時數(shù)組作為參數(shù)傳遞。#include<malloc.h>ElementTypeMedian(ElementTypeS[],intN){ElementType*p,m;/*申請臨時數(shù)組大小所需要的空間*/p=(ElementType*)malloc(sizeof(ElementType)*N);m=FindKthLargest(S,(N+1)/2,0,N-1,p);free(p);/*釋放臨時數(shù)組空間*/returnm;}24/25ElementTypeFindKthLargest(ElementTypeS[],intK，intleft,intright,ElementTypet[]){/*在S[left]..S[right]中找第K大整數(shù)，t是臨時數(shù)組*/inti,Large=left,Small=right;/*Large和Small分別指向S1和S2在臨時數(shù)組中的下一個存放位置*/ElementTypee;/*分解集合的基準(zhǔn)e*/e=S[left];/*將第一個元素作為基準(zhǔn)*/for(i=left;i<=right;i++)if(S[i]>=e)/*將比e大的元素放臨時數(shù)組t左邊，小的元素放右邊*/t[Large++]=S[i];

elset[Small--]=S[i];for(i=left;i<=right;i++)/*將臨時數(shù)組中的元素拷貝回原數(shù)組*/S[i]=t[i];if(K<Large-left)/*Large-left代表了集合S1的大小*//*在集合S1中繼續(xù)找*/returnFindKthLargest(S,K,left,Large-1,t);if(k==Large-left)/*找到，返回*/returne;else/*在集合S2中找*/returnFindKthLargest(S,K-Large+left,Large,right,t);}25/25若Small==right，即沒有比e小的元素，要另選一個基準(zhǔn)第3章線性結(jié)構(gòu)1/25§3.1引子【分析】多項式的關(guān)鍵數(shù)據(jù)是：多項式項數(shù)n、每一項的系數(shù)ai

（及相應(yīng)指數(shù)i）。有3種不同的方法。一元多項式：

主要運算：多項式相加、相減、相乘等方法1：采用順序存儲結(jié)構(gòu)直接表示[例3.1]一元多項式及其運算。例如：下標(biāo)i012345……a[i]10–3004……表示成：方法2：采用順序存儲結(jié)構(gòu)表示多項式的非零項。第3章線性結(jié)構(gòu)§3.1引子每個非零項涉及兩個信息：指數(shù)和系數(shù)，可以將一個多項式看成是一個(，)二元組的集合。例如：和表示成：數(shù)組下標(biāo)i012……數(shù)組下標(biāo)i0123……系數(shù)9153–系數(shù)26–4–1382–指數(shù)1282–指數(shù)19860–P1(x)(b)P2(x)

相加過程：

比較（9,12）和（26，19），將（26,19）移到結(jié)果多項式；

繼續(xù)比較（9,12）和（–4，8），將（9,12）移到結(jié)果多項式；

比較（15,8）和（–4，8），15+（–4）=11，不為0，將新的一項（11,8）增加到結(jié)果多項式；

比較（3,2）和（–13,6）,將（–13,6）移到結(jié)果多項式；

比較（3,2）和（82,0）,將（3,2）移到結(jié)果多項式；

將（82,0）直接移到結(jié)果多項式。最后得到的結(jié)果多項式是：((26,19),(9,12),(11,8),(–13,6),(3,2),(82,0))

2/25方法3：采用鏈表結(jié)構(gòu)來存儲多項式的非零項。每個鏈表結(jié)點存儲多項式中的一個非零項，包括系數(shù)和指數(shù)兩個數(shù)據(jù)域以及一個指針域，表示為：coefexponlinktypedef

structPolyNode*Polynomial;typedef

structPolyNode{

intcoef;

intexpon; Polynomiallink;}例如:鏈表存儲形式為：第3章線性結(jié)構(gòu)§3.1引子912P1P215832NULL2619–48–136820NULL3/25[例3.2]二元多項式又該如何表示？比如，給定二元多項式：

【分析】可以將上述二元多項式看成關(guān)于x的一元多項式

所以，上述二元多項式可以用“復(fù)雜”鏈表表示為：第3章線性結(jié)構(gòu)§3.1引子圖3.4二元多項式非零項的鏈表表示12P832NULL9240NULL153–11NULL4/25第3章線性結(jié)構(gòu)5/25§3.2線性表的定義與實現(xiàn)【定義】“線性表(LinearList)”是由同一類型的數(shù)據(jù)元素構(gòu)成的有序序列的線性結(jié)構(gòu)。

線性表中元素的個數(shù)稱為線性表的長度；

當(dāng)一個線性表中沒有元素（長度為0）時，稱為空表；

表的起始位置稱表頭，表的結(jié)束位置稱表尾。,類型名稱：線性表（List）數(shù)據(jù)對象集：線性表是

n(≥0)個元素構(gòu)成的有序序列(a1,a2,

,an)；

ai+1稱為

ai的直接后繼，

ai-1為

ai的直接前驅(qū)；直接前驅(qū)和直接后繼反映了元素之間一對一的鄰接邏輯關(guān)系。操作集：對于一個具體的線性表L

List，一個表示位置的整數(shù)i，一個元素X

ElementType，線性表的基本操作主要有：1、ListMakeEmpty()：初始化一個新的空線性表L；2、ElementType

FindKth(intK,ListL)：根據(jù)指定的位序K，返回相應(yīng)元素

；3、intFind(ElementTypeX,ListL)：已知X，返回線性表L中與X相同的第一個元素的相應(yīng)位序i；若不存在則返回空；4、voidInsert(ElementTypeX,inti,ListL)：指定位序i前插入一個新元素X；5、voidDelete(inti,ListL)：刪除指定位序i的元素；6、intLength(ListL)：返回線性表L的長度n。

線性表的順序存儲實現(xiàn)第3章線性結(jié)構(gòu)§3.2.1線性表的順序存儲實現(xiàn)在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素。一維數(shù)組在內(nèi)存中占用的存儲空間就是一組連續(xù)的存儲區(qū)域。typedef

struct{ ElementTypeData[MAXSIZE];

intLast;}List;ListL,*PtrL;下標(biāo)i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last訪問下標(biāo)為i的元素：L.Data[i]或PtrL->Data[i]線性表的長度：L.Last+1或PtrL->Last+16/251.初始化（建立空的順序表）第3章線性結(jié)構(gòu)

主要操作的實現(xiàn)List*MakeEmpty(){List*PtrL;PtrL=(List*)malloc(sizeof(List));PtrL->Last=-1;

returnPtrL;}2.查找intFind(ElementTypeX,List*PtrL){int

i=0;

while(i<=PtrL->Last&&PtrL->Data[i]!=X)

i++;

if(i>PtrL->Last)return-1;/*如果沒找到，返回-1*/

else

returni;/*找到后返回的是存儲位置*/}查找成功的平均比較次數(shù)為(n+1)/2，平均時間性能為

O(n)?！?.2.1線性表的順序存儲實現(xiàn)7/25第3章線性結(jié)構(gòu)下標(biāo)i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下標(biāo)i01…i-1ii+1…n…SIZE-1Dataa1a2…aiai+1…an…-Last3.插入（第

i(1≤i≤n+1)個位置上插入一個值為X的新元素)先移動，再插入X§3.2.1線性表的順序存儲實現(xiàn)8/25

插入算法第3章線性結(jié)構(gòu)voidInsert(ElementTypeX,inti,List*PtrL){intj;

if(PtrL->Last==MAXSIZE-1){/*表空間已滿，不能插入*/printf(＂表滿＂);return;}

if(i<1||i>PtrL->Last+2){/*檢查插入位置的合法性*/printf(＂位置不合法＂);return;}

for(j=PtrL->Last;j>=i-1;j--)PtrL->Data[j+1]=PtrL->Data[j];/*將

ai～

an倒序向后移動*/PtrL->Data[i-1]=X;/*新元素插入*/PtrL->Last++;/*Last仍指向最后元素*/

return;}平均移動次數(shù)為n/2，平均時間性能為

O(n)?！?.2.1線性表的順序存儲實現(xiàn)9/25第3章線性結(jié)構(gòu)下標(biāo)i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下標(biāo)i01…i-1…n-2n-1…MAXSIZE-1Dataa1a2…ai+1…anan…-Last4.

刪除（刪除表的第

i(1≤i≤n)個位置上的元素)后面的元素依次前移§3.2.1線性表的順序存儲實現(xiàn)10/25

刪除算法第3章線性結(jié)構(gòu)voidDelete(inti,List*PtrL){intj;

if(i<1||i>PtrL->Last+1){/*檢查空表及刪除位置的合法性*/printf(“不存在第%d個元素”,i);

return;}

for(j=i;j<=PtrL->Last;j++)PtrL->Data[j-1]=PtrL->Data[j];/*將

ai+1～

an順序向前移動*/PtrL->Last--;/*Last仍指向最后元素*/

return;}平均移動次數(shù)為(n-1)/2，平均時間性能為

O(n)?！?.2.1線性表的順序存儲實現(xiàn)11/25

線性表的鏈?zhǔn)酱鎯崿F(xiàn)第3章線性結(jié)構(gòu)不要求邏輯上相鄰的兩個數(shù)據(jù)元素物理上也相鄰，它是通過“鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系。因此對線性表的插入、刪除不需要移動數(shù)據(jù)元素，只需要修改“鏈”。typedef

structNode{ElementTypeData;

structNode*Next;}List;ListL,*PtrL;訪問序號為i的元素？求線性表的長度？§3.2.3線性表的鏈?zhǔn)酱鎯崿F(xiàn)12/251.求表長第3章線性結(jié)構(gòu)

主要操作的實現(xiàn)intLength(List*PtrL){List*p=PtrL;/*p指向表的第一個結(jié)點*/intj=0;while(p){p=p->Next;j++;/*當(dāng)前p指向的是第

j個結(jié)點*/}returnj;}時間性能為

O(n)?！?.2.3線性表的鏈?zhǔn)酱鎯崿F(xiàn)13/25第3章線性結(jié)構(gòu)2.查找List*FindKth(intK,List*PtrL){List*p=PtrL;

inti=1;

while(p!=NULL&&i<K){p=p->Next;i++;}

if(i==K)returnp;/*找到第K個，返回指針*/

else

returnNULL;

/*否則返回空*/}List*Find(ElementTypeX,List*PtrL){List*p=PtrL;

while(p!=NULL&&p->Data!=X)p=p->Next;

returnp;}（1）按序號查找:

FindKth;（2）按值查找:Find平均時間性能為

O(n)。§3.2.3線性表的鏈?zhǔn)酱鎯崿F(xiàn)14/25第3章線性結(jié)構(gòu)3.插入（在鏈表的第

i-1(1≤i≤n+1)個結(jié)點后插入一個值為X的新結(jié)點)（1）先構(gòu)造一個新結(jié)點，用s指向；（2）再找到鏈表的第

i-1個結(jié)點，用p指向；（3）然后修改指針，插入結(jié)點(p之后插入新結(jié)點是s)head……pss->Next=p->Next;p->Next=s;

§3.2.3線性表的鏈?zhǔn)酱鎯崿F(xiàn)思考:修改指針的兩個步驟如果交換一下，將會發(fā)生什么?15/25

插入算法第3章線性結(jié)構(gòu)List*Insert(ElementTypeX,inti,List*PtrL){List*p,*s;

if(i==1){/*新結(jié)點插入在表頭