數(shù)據(jù)結(jié)構(gòu)課件

楊萬(wàn)扣自動(dòng)化學(xué)院中心樓217,wkyang@數(shù)據(jù)結(jié)構(gòu)東南大學(xué)教材：數(shù)據(jù)結(jié)構(gòu)（第二版）

嚴(yán)蔚敏吳偉民

（清華大學(xué)出版社）(考研指定書(shū)目)考試方式期末考試采用開(kāi)卷方式，占總評(píng)成績(jī)的50%。實(shí)驗(yàn)占總評(píng)成績(jī)50%?？荚囎⒅兀焊拍睢⒎椒?、技巧、思想、創(chuàng)新、關(guān)鍵步驟、程序設(shè)計(jì)風(fēng)格第一章緒論1.1學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的意義及要求1.2<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容1.3基本術(shù)語(yǔ)1.4算法描述及分析1.1學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的意義及要求2.數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的基礎(chǔ)

Program=Algorithms+DataStructure

數(shù)據(jù)結(jié)構(gòu)是設(shè)計(jì)OS、DBMS、編譯等系統(tǒng)程序和各種應(yīng)用程序的重要基礎(chǔ)1.1學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的意義及要求計(jì)算機(jī)軟件概念的發(fā)展軟件=程序軟件=程序+文檔

軟件=體系結(jié)構(gòu)+構(gòu)件+文檔ProblemsofLargesoftware1.1學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的意義及要求計(jì)算機(jī)軟件系統(tǒng)可看成是通過(guò)不同層次的數(shù)據(jù)結(jié)構(gòu)及其操作實(shí)現(xiàn)的。例如：

1.1學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的意義及要求軟件需求的發(fā)展數(shù)據(jù)處理階段（DPS）數(shù)據(jù)管理階段（MIS）數(shù)據(jù)應(yīng)用階段（DMDW）1.1學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的意義及要求二、要求掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型和相應(yīng)的存儲(chǔ)結(jié)構(gòu)提高閱讀和編寫(xiě)算法的能力能針對(duì)給定問(wèn)題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計(jì)和分析算法1.2學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例1：08010183202670210096510102780618748080101班號(hào)83202670自動(dòng)化學(xué)院辦公室電話號(hào)碼210096東南大學(xué)郵編510102780618748身份證號(hào)碼結(jié)論1.

雜亂的數(shù)據(jù)不能表達(dá)和交流信息1.2學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容結(jié)論３． 數(shù)據(jù)之間是有結(jié)構(gòu)的例３中數(shù)據(jù)之間呈分層結(jié)構(gòu)（樹(shù)狀結(jié)構(gòu)）《DS》就是要研究數(shù)據(jù)之間的各類結(jié)構(gòu)。例3：大學(xué)學(xué)生管理機(jī)構(gòu)

學(xué)校 一系．．．八系．．．

一年級(jí)二年級(jí)三年級(jí)四年級(jí)

１班．．．８班張三．．．李四1.2學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例４：圖書(shū)目錄管理設(shè)每個(gè)書(shū)目含：書(shū)名，作者，登錄號(hào)，分類，出版年月對(duì)圖書(shū)目錄常有如下操作：查找：某書(shū)在書(shū)庫(kù)中是否存在？插入：購(gòu)進(jìn)新書(shū)時(shí)的登錄；刪除：報(bào)廢或丟失的書(shū)，需從目錄中去掉；結(jié)論４． 在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運(yùn)算《DS》就是要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運(yùn)算。1.2學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容例5：交通網(wǎng)絡(luò)圖

從一個(gè)地方到另外一個(gè)地方可以有多條路徑。本問(wèn)題是一種典型的網(wǎng)狀結(jié)構(gòu)問(wèn)題，數(shù)據(jù)與數(shù)據(jù)成多對(duì)多的關(guān)系，是一種非線性關(guān)系結(jié)構(gòu)。佛山惠州廣州中山東莞深圳珠海1.2學(xué)習(xí)<數(shù)據(jù)結(jié)構(gòu)>的主要內(nèi)容綜上所述：《DS》主要研究?jī)?nèi)容：數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系并對(duì)每種結(jié)構(gòu)定義相適應(yīng)的各種運(yùn)算設(shè)計(jì)出相應(yīng)的算法分析算法的效率常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組、棧、隊(duì)列、表、串、樹(shù)、圖和文件等。1.3基本術(shù)語(yǔ)數(shù)據(jù)（Data)：所有能被計(jì)算機(jī)處理的符號(hào)的集合。數(shù)據(jù)元素（DataElement）：是數(shù)據(jù)這個(gè)集合中的一個(gè)個(gè)體。

設(shè)給定數(shù)據(jù)集合為：

D={d1，d2，．．．，dn}

則di屬于D，并稱di為數(shù)據(jù)元素。數(shù)據(jù)項(xiàng)（DataItem）：數(shù)據(jù)元素常常還可分為若干個(gè)數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)具有意義的最小單位。1.3基本術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)（DataStructure）：是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。

所謂結(jié)構(gòu)就是數(shù)據(jù)元素之間的關(guān)系，即描述數(shù)據(jù)元素之間的運(yùn)算及運(yùn)算規(guī)則。用集合的形式描述，數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：

DS=(D，R)

其中：D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。簡(jiǎn)言之，數(shù)據(jù)元素和其相互關(guān)系稱為數(shù)據(jù)結(jié)構(gòu)1.3基本術(shù)語(yǔ)邏輯結(jié)構(gòu)（LogicalStructure）：指數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。物理結(jié)構(gòu)（PhysicalStructure）：指數(shù)據(jù)結(jié)構(gòu)在機(jī)內(nèi)的表示。一點(diǎn)說(shuō)明：算法的設(shè)計(jì)取決于邏輯結(jié)構(gòu)；算法的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)。1.3基本術(shù)語(yǔ)1.3基本術(shù)語(yǔ)數(shù)據(jù)類型（DataType）：一個(gè)值的集合和定義在這個(gè)值集上的操作的總稱?；静僮鞯姆诸悾阂眯汀檎?；加工型——插入、刪除、更新、排序。1.４算法描述和算法分析④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。一個(gè)算法可以用多種方法描述，主要有：使用自然語(yǔ)言描述；使用形式語(yǔ)言描述；使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述。1.４算法描述和算法分析３．算法與程序的區(qū)別算法是解決問(wèn)題的一種方法或一個(gè)過(guò)程，考慮如何將輸入轉(zhuǎn)換成輸出，一個(gè)問(wèn)題可以有多種算法。程序是用某種程序設(shè)計(jì)語(yǔ)言對(duì)算法的具體實(shí)現(xiàn)。主要區(qū)別在：有窮性、正確性和描述方法

程序可以是無(wú)窮的，例如OS，算法是有窮的；程序可以是錯(cuò)誤的，算法必須是正確的；程序是用程序設(shè)計(jì)語(yǔ)言描述，在機(jī)器上可以執(zhí)行；算法還可以用框圖、自然語(yǔ)言等方式描述。1.４算法描述和算法分析三．算法分析

如何衡量一個(gè)正確算法的好壞？ 衡量的三個(gè)尺度：運(yùn)行所花費(fèi)的時(shí)間（算法的時(shí)間特性）；所占用存儲(chǔ)空間的大?。ㄋ惴ǖ目臻g特性）；其他（可讀性、易調(diào)性、健壯性等）。 時(shí)間和空間特性的巨大改進(jìn)源于更好的數(shù)據(jù)結(jié)構(gòu)或算法。1.４算法描述和算法分析與此相關(guān)的因素有：依據(jù)算法選用何種策略；問(wèn)題的規(guī)模；程序設(shè)計(jì)的語(yǔ)言；編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；機(jī)器執(zhí)行指令的速度；撇開(kāi)軟硬件等有關(guān)部門因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴于問(wèn)題的規(guī)模（通常用n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。1.４算法描述和算法分析算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，其時(shí)間量度記作T(n)=O(f(n))，稱作算法的漸近時(shí)間復(fù)雜度(AsymptoticTimecomplexity)，簡(jiǎn)稱時(shí)間復(fù)雜度。一般地，常用最深層循環(huán)內(nèi)的語(yǔ)句中的原操作的執(zhí)行頻度(重復(fù)執(zhí)行的次數(shù))來(lái)表示?！癘”的定義：若f(n)是正整數(shù)n的一個(gè)函數(shù)，則O(f(n))表示

M≥0，使得當(dāng)n≥n0時(shí)，|f(n)|≤M

|f(n0)|。表示時(shí)間復(fù)雜度的階有：

O(1)：常量時(shí)間階O(n)：線性時(shí)間階

O(㏒n)：對(duì)數(shù)時(shí)間階O(n㏒n)：線性對(duì)數(shù)時(shí)間階1.４算法描述和算法分析語(yǔ)句頻度（FrequencyCount）：

語(yǔ)句可能重復(fù)執(zhí)行的最大次數(shù)。時(shí)間復(fù)雜度（TimeComplexity）：

設(shè)算法中所有語(yǔ)句的語(yǔ)句頻度為t(n)，

f(n)是當(dāng)n趨向無(wú)窮大時(shí)與t(n)為同階無(wú)窮大， 則算法的時(shí)間復(fù)雜度T(n)=O(f(n))

其中：n為算法計(jì)算量或稱為規(guī)模（size）；

f(n)是運(yùn)算時(shí)間隨n增大時(shí)的增長(zhǎng)率；

O(f(n))是算法時(shí)間特性的量度。1.４算法描述和算法分析例：程序段語(yǔ)句頻度時(shí)間復(fù)雜度1.x=x+1;1O(1)常數(shù)階for(i=0;i<n;++i)n+1x=x+1nO(n)線性階3.for(i=1;i<n;++i)n

for(j=1;j<n;++j)n(n-1)x=x+1;(n-1)2O(n2)平方階1.４算法描述和算法分析

O(nk)：k≥2，k次方時(shí)間階例１兩個(gè)n階方陣的乘法

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];}由于是一個(gè)三重循環(huán)，每個(gè)循環(huán)從1到n，則總次數(shù)為：n×n×n=n3時(shí)間復(fù)雜度為T(n)=O(n3)例２{++x;s=0;}

將x自增看成是基本操作，則語(yǔ)句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)。1.４算法描述和算法分析如果將s=0也看成是基本操作，則語(yǔ)句頻度為２，其時(shí)間復(fù)雜度仍為Ｏ(1)，即常量階。例３for(i=1;i<=n;++i){++x;s+=x;}語(yǔ)句頻度為：2n，其時(shí)間復(fù)雜度為：O(n)，即為線性階。例４for(i=1;i<=n;++i)

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

語(yǔ)句頻度為：2n2，其時(shí)間復(fù)雜度為：O(n2)，即為平方階。1.４算法描述和算法分析定理：若A(n)=amnm

+am-1nm-1+…+a1n+a0是一個(gè)m次多項(xiàng)式，則A(n)=O(nm)例５

for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i,j]=x;}語(yǔ)句頻度為：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=(n2-3n+2)/2∴時(shí)間復(fù)雜度為O(n2)，即此算法的時(shí)間復(fù)雜度為平方階。一個(gè)算法時(shí)間為O(1)的算法，它的基本運(yùn)算執(zhí)行的次數(shù)是固定的。因此，總的時(shí)間由一個(gè)常數(shù)（即零次多項(xiàng)式）來(lái)限界。而一個(gè)時(shí)間為O(n2)的算法則由一個(gè)二次多項(xiàng)式來(lái)限界。1.４算法描述和算法分析設(shè)：A1，A2和A3是求解同一問(wèn)題的不同算法，其時(shí)間復(fù)雜度分別為：O(n)，O(nlogn)，O(N!)。C1和C2為計(jì)算機(jī)，且C2的計(jì)算速度是C1的10倍。(可解規(guī)模<-1/時(shí)間)復(fù)雜度C1可解規(guī)模C2可解規(guī)?？山庖?guī)模的關(guān)系O(n)N11N21N21=10N11O(nlogn)N12N22N22=10N12O(N!)N13N23N23=N13+小常數(shù)不必追求高效算法，低效算法可由高速計(jì)算機(jī)來(lái)彌補(bǔ)的看法是錯(cuò)誤的。小結(jié)數(shù)據(jù)結(jié)構(gòu)概念算法時(shí)間復(fù)雜度習(xí)題一1簡(jiǎn)要回答術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類型。2數(shù)據(jù)的邏輯結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)？邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的區(qū)別和聯(lián)系是什么？3數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括哪些？4算法分析的目的是什么？算法分析的主要方面是什么？5分析以下程序段的時(shí)間復(fù)雜度，請(qǐng)說(shuō)明分析的理由或原因。⑴Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}(2)遞歸函數(shù)fact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}習(xí)題一習(xí)題一(3)Sum2(intn){intsum=0,m,t;for(m=1;m<=n;m++){p=1;for(t=1;t<=m;t++)p*=t;sum+=p;}return(sum);}第二章線性表2.1 線性表及其基本運(yùn)算2.2 線性表的順序存儲(chǔ)結(jié)構(gòu)2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)，以及它們之間的相互關(guān)系；定義與之相適應(yīng)的運(yùn)算；設(shè)計(jì)相應(yīng)的算法；分析算法的效率。2.1線性表及其基本運(yùn)算

一、線性表（Linear_list）

線性表是n個(gè)數(shù)據(jù)元素的有限序列，記為：

L=（a1,a2,…,ai-1,ai,ai+1,…,an）數(shù)據(jù)元素之間的關(guān)系是：ai-1領(lǐng)先于ai，ai領(lǐng)先于ai+1。稱ai-1是ai的直接前驅(qū)元素；ai+1是ai的直接后繼元素。除a1外，每個(gè)元素有且僅有一個(gè)直接前驅(qū)元素，除an外，每個(gè)元素有且僅有一個(gè)直接后繼元素。線性表中數(shù)據(jù)元素的個(gè)數(shù)n(n>=0)稱為線性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱為空表。2.1線性表及其基本運(yùn)算線性表的基本操作：(1)初始化（Init置空表）——可由構(gòu)造函數(shù)實(shí)現(xiàn)(2)表長(zhǎng)（Length）(3)查找或定位（Find）(4)插入（Insert）

(5)刪除（Remove）(6)排序（Sort）(7)判空（IsEmpty）a2ana12.1線性表及其基本運(yùn)算

要實(shí)現(xiàn)在計(jì)算機(jī)內(nèi)表示一個(gè)數(shù)據(jù)結(jié)構(gòu)，要解決兩種信息的存貯問(wèn)題：數(shù)據(jù)元素本身的存貯 數(shù)據(jù)元素之間關(guān)系的存貯定義：利用內(nèi)存物理結(jié)構(gòu)上的鄰接特點(diǎn)，實(shí)現(xiàn)線性表的“一個(gè)跟著一個(gè)”這一序列關(guān)系的存貯方式，稱為線性表的順序存貯結(jié)構(gòu)，其上的線性表稱為順序表。利用數(shù)組作為順序表的存儲(chǔ)結(jié)構(gòu)，

2.1線性表及其基本運(yùn)算例2-1求兩個(gè)集合的并,即A=A∪B分析：設(shè)A、B分別由兩個(gè)線性表LA和LB表示，要求將LB中存在而LA中不存在的DE插入到表LA中。算法思想：①依次從LB中取出一個(gè)DE；②判在LA中是否存在；③若不存在，則插入到LA中。2.1線性表及其基本運(yùn)算voidunion(List&La，ListLb){La_len=Length(La);Lb_len=Length(Lb);for(i=0;i<=lb_len;++i){getelem(lb，i，e);if(!find(la,e)){Insert(la，e);++La_len;}}}2.1線性表及其基本運(yùn)算例2-2歸并兩個(gè)有序的線性表LA和LB,為一個(gè)新的有序線性表LC。算法思想：

①初始化：置LC為空表，設(shè)置變量i,j，初值為1，分別指向LA和LB的第一個(gè)DE，k表示LC的長(zhǎng)度，初值為0。②當(dāng)i<=Length(LA)ANDj<=Length(LB)時(shí)，判斷：若i所指的元素<=j所指的元素，則將i所指的元素插入在LC的k+1前，并且i,k的值分別加1；否則，將j所指的元素插入在LC的k+1前，并且j,k的值分別加1。

③重復(fù)②直到某個(gè)表的元素插入完畢。 ④將未插入完的表的余下的元素，依次插入在LC后。2.1線性表及其基本運(yùn)算voidmergelist(listla，listlb，list&lc){Init(lc);i=j=1;k=0;la_len=Length(la);lb_len=Length(lb);

while((i<=la_len)&&(j<=lb_len)){getelem(la，i，ai);getelem(lb，j，bj);if(ai<=bj){Insert(lc，++k，ai);++i;}else{Insert(lc，++k，bj);++j;}}2.1線性表及其基本運(yùn)算while(i<=la-len){getelem((la，i++，ai);Insert(lc，++k，ai);}while(j<=lb-len){getelem((lb，j++，bj);listinsert(lc，++k，bi);}}2.2線性表的順序存儲(chǔ)結(jié)構(gòu)一、順序存儲(chǔ)結(jié)構(gòu)用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素。設(shè)線性表的每個(gè)元素占用k個(gè)存儲(chǔ)單元，則第i個(gè)元素ai的存儲(chǔ)位置為：Loc(ai)=Loc(a1)+(i-1)*k其中，Loc(a1)為線性表的起址。a1a2aian

bb+kb+(i-1)kb+(n-1)k2.2線性表的順序存儲(chǔ)結(jié)構(gòu)在高級(jí)語(yǔ)言(如C語(yǔ)言)環(huán)境下：數(shù)組具有隨機(jī)存取的特性，因此，借助數(shù)組來(lái)描述順序表。除了用數(shù)組來(lái)存儲(chǔ)線性表的元素之外，順序表還應(yīng)該有表示線性表的長(zhǎng)度屬性，所以用結(jié)構(gòu)類型來(lái)定義順序表類型。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)#defineOK1#defineERROR-1#defineMAX_SIZE100typedefintStatus;typedefintElemType;structsqlist{ElemType*Elem_array;intlength;};2.2.2順序表上實(shí)現(xiàn)的基本操作二.操作的實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長(zhǎng)度等。以下將對(duì)幾種主要的操作進(jìn)行討論。1順序線性表初始化

StatusInit_SqList(SqList*L){L->elem_array=newElemType[MAX_SIZE];if(L->elem_array==NULL)returnERROR;else{L->length=0;returnOK;}}2.2.2順序表上實(shí)現(xiàn)的基本操作注意：C/C++語(yǔ)言中的數(shù)組下標(biāo)從“0”開(kāi)始，因此，若L是Sqlist類型的順序表，則表中第i個(gè)元素是l.data[i-1]。以下主要討論線性表的插入和刪除兩種運(yùn)算。2、插入線性表的插入運(yùn)算是指在表的第i(1≦i≦n+1)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，2.2.2順序表上實(shí)現(xiàn)的基本操作算法思想：

①進(jìn)行合法性檢查，1<=i<=n+1；②判斷線性表是否已滿；③將第n個(gè)至第i個(gè)元素逐一后移一個(gè)單元；④在第i個(gè)位置處插入新元素；⑤將表的長(zhǎng)度加1。2.插入運(yùn)算INSERT（L,i,b）插入前：L=（a1,...,ai-1,ai,...,an）插入后：L=（a1,...,ai-1,b,ai,...,an）2.2.2順序表上實(shí)現(xiàn)的基本操作b231先移動(dòng)后面元素0i-1ii+1last..................高質(zhì)量C++編程EffectiveC++深度探索C++對(duì)象模型2.2.2順序表上實(shí)現(xiàn)的基本操作算法描述StatusInsert_SqList(Sqlist*L，inti，ElemTypee)

{intj;if(i<1||i>L->length+1)returnERROR;if(L->length>=MAX_SIZE){printf(“線性表溢出!\n”);returnERROR;}for(j=L->length–1;j>=i-1;--j)L->Elem_array[j+1]=L->Elem_array[j];/*i-1位置以后的所有結(jié)點(diǎn)后移*/L->Elem_array[i-1]=e;/*在i-1位置插入結(jié)點(diǎn)*/L->length++;returnOK;}2.2.2順序表上實(shí)現(xiàn)的基本操作時(shí)間復(fù)雜度分析在線性表L中的第i個(gè)元素之前插入新結(jié)點(diǎn)，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。設(shè)在線性表L中的第i個(gè)元素之前插入結(jié)點(diǎn)的概率為Pi，不失一般性，設(shè)各個(gè)位置插入是等概率，則Pi=1/(n+1)，而插入時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i+1?？偟钠骄苿?dòng)次數(shù)：Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)汀Ｒ虼怂惴ǖ钠骄鶗r(shí)間復(fù)雜度為O(n)。2.2.2順序表上實(shí)現(xiàn)的基本操作3.刪除運(yùn)算DELETE（L,i）刪除前：L=（a1,...,ai-1,ai,ai+1,...,an）刪除后：L=（a1,...,ai-1,ai+1,...,an）算法思想：①判線性表是否已空，②進(jìn)行合法性檢查，i是否滿足1<=i<=n；③將第i+1至第n個(gè)元素逐一向前移一個(gè)位置；④將表的長(zhǎng)度減1。2.2.2順序表上實(shí)現(xiàn)的基本操作12...0i-1ii+1last-1last1...............2.2.2順序表上實(shí)現(xiàn)的基本操作ElemTypeDelete_SqList(Sqlist*L，inti){intk;ElemTypex;if(L->length==0){cout<<“線性表L為空!\n”;returnERROR;}elseif(i<1||i>L->length){cout“要?jiǎng)h除的數(shù)據(jù)元素不存在!\n”);returnERROR;}2.2.2順序表上實(shí)現(xiàn)的基本操作else{x=L->Elem_array[i-1];/*保存結(jié)點(diǎn)的值*/for(k=i;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];

/*i位置以后的所有結(jié)點(diǎn)前移*/L->length--;return(x);}}時(shí)間復(fù)雜度?2.2.2順序表上實(shí)現(xiàn)的基本操作算法思想：①?gòu)牡谝粋€(gè)DE開(kāi)始；②依次比較每個(gè)DE；③將從找到的位置返回。4順序線性表的查找定位在線性表L=(a1，a2，…，an)中值為x的第一個(gè)結(jié)點(diǎn)。2.2.2順序表上實(shí)現(xiàn)的基本操作算法描述intLocate_SqList(Sqlist*L，ElemTypex)/*線性表L中值為x的第一個(gè)結(jié)點(diǎn)*/{inti=0,k;2.2.2順序表上實(shí)現(xiàn)的基本操作while(i<L->length)/*查找值為x的第一個(gè)結(jié)點(diǎn)*/{if(L->Elem_array[i]!=x)i++;else{returni;}}if(i>L->length){printf(“要查找的數(shù)據(jù)元素不存在!\n”);return-1;}}2.2.2順序表上實(shí)現(xiàn)的基本操作時(shí)間復(fù)雜度分析

時(shí)間主要耗費(fèi)在數(shù)據(jù)元素的比較和移動(dòng)操作上。首先，在線性表L中查找值為x的結(jié)點(diǎn)是否存在;其次，若值為x的結(jié)點(diǎn)存在，且在線性表L中的位置為i，則在線性表L中刪除第i個(gè)元素。設(shè)在線性表L刪除數(shù)據(jù)元素概率為Pi，不失一般性，設(shè)各個(gè)位置是等概率，則Pi=1/n?！舯容^的平均次數(shù)：Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2?！魟h除時(shí)平均移動(dòng)次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。

平均時(shí)間復(fù)雜度：Ecompare+Edelete=n，即為O(n)2.3

線性表的鏈?zhǔn)酱鎯?chǔ)

2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)：用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱線性鏈表。存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。

鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)datanext圖2-1

鏈表結(jié)點(diǎn)結(jié)構(gòu)data

：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。next

：指針域，存放結(jié)點(diǎn)的直接后繼的地址。為操作方便，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)(頭指針)head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息(或鏈表長(zhǎng)度等信息)。2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)例1、線性表L=(bat，cat，eat，fat，hat)其帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲(chǔ)方式如圖2-2所示。

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfathat?head

圖2-2

帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1

結(jié)點(diǎn)的描述與實(shí)現(xiàn)用帶指針的結(jié)構(gòu)體類型來(lái)描述structLnode/*結(jié)點(diǎn)的類型*/{ElemTypedata;/*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/

Lnode*next;/*指針域*/}2結(jié)點(diǎn)的實(shí)現(xiàn)結(jié)點(diǎn)是通過(guò)動(dòng)態(tài)分配和釋放來(lái)的實(shí)現(xiàn)，即需要時(shí)分配，不需要時(shí)釋放。實(shí)現(xiàn)時(shí)是分別使用提供的標(biāo)準(zhǔn)函數(shù)：new，delete。2.3.1

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)動(dòng)態(tài)分配

p=newLNode;動(dòng)態(tài)釋放

deletep;3最常用的基本操作及其示意圖⑴

結(jié)點(diǎn)的賦值LNode*p;p=newLNode;p->data=20;p->next=NULL;p20NULL(2)常見(jiàn)的指針操作①

q=p;pa……操作前pa……q操作后②

q=p->next;bpa……操作前操作后qbpa……③

p=p->next;bpa……操作前操作后pba……④

q->next=p;c…pbqa……操作前操作后qb……ac…p(a)⑤

q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)2.3.2

單線性鏈?zhǔn)降幕静僮?

建立單鏈表假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類型是整型，以32767作為結(jié)束標(biāo)志。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：頭插入法，尾插入法。⑴頭插入法建表

從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。即每次插入的結(jié)點(diǎn)都作為鏈表的第一個(gè)結(jié)點(diǎn)。算法描述LNode*create_LinkList(void)/*頭插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值*/{intdata;LNode*head,*p;head=newLNode;head->next=NULL;/*創(chuàng)建鏈表的表頭結(jié)點(diǎn)head*/

while(1){scanf(“%d”,&data);if(data==32767)break;p=newLNode;p–>data=data;/*數(shù)據(jù)域賦值*/2.3.2

單線性鏈?zhǔn)降幕静僮?.3.2

單線性鏈?zhǔn)降幕静僮鱬–>next=head–>next;head–>next=p;

/*鉤鏈，新創(chuàng)建的結(jié)點(diǎn)總是作為第一個(gè)結(jié)點(diǎn)*/}return(head);}(2)尾插入法建表

頭插入法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾，使其成為當(dāng)前鏈表的尾結(jié)點(diǎn)。2.3.2

單線性鏈?zhǔn)降幕静僮魉惴枋鯨Node*create_LinkList(void)

/*尾插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值*/{intdata;LNode*head,*p,*q;head=p=newLNode;p->next=NULL;/*創(chuàng)建單鏈表的表頭結(jié)點(diǎn)head*/while(1){cin>>data;if(data==32767)break;q=newLNode;2.3.2

單線性鏈?zhǔn)降幕静僮鱭–>data=data;/*數(shù)據(jù)域賦值*/q–>next=p–>next;p–>next=q;p=q;

/*鉤鏈，新創(chuàng)建的結(jié)點(diǎn)總是作為最后一個(gè)結(jié)點(diǎn)*/}return(head);}

無(wú)論是哪種插入方法，如果要插入建立的單線性鏈表的結(jié)點(diǎn)是n個(gè)，算法的時(shí)間復(fù)雜度均為O(n)。對(duì)于單鏈表，無(wú)論是哪種操作，只要涉及到鉤鏈(或重新鉤鏈)，如果沒(méi)有明確給出直接后繼，鉤鏈(或重新鉤鏈)的次序必須是“先右后左”。2.3.2

單線性鏈?zhǔn)降幕静僮?

單鏈表的查找(1)

按序號(hào)查找

取單鏈表中的第i個(gè)元素。對(duì)于單鏈表，不能象順序表中那樣直接按序號(hào)i訪問(wèn)結(jié)點(diǎn)，而只能從鏈表的頭結(jié)點(diǎn)出發(fā)，沿鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直到搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。設(shè)單鏈表的長(zhǎng)度為n，要查找表中第i個(gè)結(jié)點(diǎn)，僅當(dāng)1≦i≦n時(shí)，i的值是合法的。2.3.2

單線性鏈?zhǔn)降幕静僮魉惴枋鯡lemTypeGet_Elem(LNode*L，inti){intj;LNode*p;p=L->next;j=1;/*使p指向第一個(gè)結(jié)點(diǎn)*/while(p!=NULL&&j<i){p=p–>next;j++;}/*移動(dòng)指針p,j計(jì)數(shù)*/If(j==i)return(p->data);elsereturn(-32768);

/*p為NULL表示i太大;j>i表示i為0*/}移動(dòng)指針p的頻度：i<1時(shí)：0次;i∈[1,n]：i-1次；i>n：n次?！鄷r(shí)間復(fù)雜度:O(n)。2.3.2

單線性鏈?zhǔn)降幕静僮?2)

按值查找按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)?若有，則返回首次找到的值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找時(shí)從開(kāi)始結(jié)點(diǎn)出發(fā)，沿鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。2.3.2

單線性鏈?zhǔn)降幕静僮魉惴枋鯨Node

*Locate_Node(Lnode*L，intkey)/*在以L為頭結(jié)點(diǎn)的單鏈表中查找值為key的第一個(gè)結(jié)點(diǎn)*/{Lnode*p=L–>next;while(p!=NULL&&p–>data!=key)p=p–>next;if(p–>data==key)returnp;else{printf(“所要查找的結(jié)點(diǎn)不存在!!\n”);retutn(NULL);}}算法的執(zhí)行與形參key有關(guān)，平均時(shí)間復(fù)雜度為O(n)。2.3.2

單線性鏈?zhǔn)降幕静僮?

單鏈表的插入

插入運(yùn)算是將值為e的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的結(jié)點(diǎn)p，然后生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)q，q結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn)。算法描述voidInsert_LNode(LNode*L，inti，ElemTypee)

/*在以L為頭結(jié)點(diǎn)的單鏈表的第i個(gè)位置插入值為e的結(jié)點(diǎn)*/{intj=0;LNode*p，*q;p=L–>next;while(p!=NULL&&j<i-1){p=p–>next;j++;}if(j!=i-1)cout<<“i太大或i為0!!\n”;else{q=newLNode;q–>data=e;q–>next=p–>next;p–>next=q;}}

設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1≦i≦n。算法的時(shí)間主要耗費(fèi)移動(dòng)指針p上，故時(shí)間復(fù)雜度亦為O(n)。2.3.2

單線性鏈?zhǔn)降幕静僮?.3.2

單線性鏈?zhǔn)降幕静僮?

單鏈表的刪除⑴按序號(hào)刪除刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。為了刪除第i個(gè)結(jié)點(diǎn)ai，必須找到結(jié)點(diǎn)的存儲(chǔ)地址。該存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)ai-1的next域中，因此，必須首先找到ai-1的存儲(chǔ)位置p，然后令p–>next指向ai的直接后繼結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下。最后釋放結(jié)點(diǎn)ai的空間，將其歸還給“存儲(chǔ)池”。設(shè)單鏈表長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≦i≦n時(shí)是合法的。則當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，是終端結(jié)點(diǎn)。故判斷條件之一是p–>next!=NULL。顯然此算法的時(shí)間復(fù)雜度也是O(n)。2.3.2

單線性鏈?zhǔn)降幕静僮魉惴枋鰒oidDelete_LinkList(LNode*L，inti)

/*刪除以L為頭結(jié)點(diǎn)的單鏈表中的第i個(gè)結(jié)點(diǎn)*/{intj=1;LNode*p，*q;p=L;q=L->next;while(p->next!=NULL&&j<I){p=q;q=q–>next;j++;}if(j!=i)printf(“i太大或i為0!!\n”);else{p–>next=q–>next;deleteq;}}2.3.2

單線性鏈?zhǔn)降幕静僮鳍瓢粗祫h除刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。與按值查找相類似，首先要查找值為key的結(jié)點(diǎn)是否存在?若存在，則刪除；否則返回NULL。2.3.2

單線性鏈?zhǔn)降幕静僮魉惴枋鰒oidDelete_LinkList(LNode*L，intkey)/*刪除以L為頭結(jié)點(diǎn)的單鏈表中值為key的第一個(gè)結(jié)點(diǎn)*/

{LNode*p=L,*q=L–>next;while(q!=NULL&&q–>data!=key){p=q;q=q–>next;}if(q–>data==key){p->next=q->next;deleteq;}elseprintf(“所要?jiǎng)h除的結(jié)點(diǎn)不存在!!\n”);}

2.3.2

單線性鏈?zhǔn)降幕静僮魉惴ǖ膱?zhí)行與形參key有關(guān)，平均時(shí)間復(fù)雜度為O(n)。從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)需移動(dòng)結(jié)點(diǎn)，僅需修改指針。解決了順序表的插入或刪除操作需要移動(dòng)大量元素的問(wèn)題。變形之一：刪除單鏈表中值為key的所有結(jié)點(diǎn)。與按值查找相類似，但比前面的算法更簡(jiǎn)單。基本思想：從單鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行檢查，若結(jié)點(diǎn)的值為key，則刪除之，然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。

2.3.2

單線性鏈?zhǔn)降幕静僮魉惴枋鰒oidDelete_LinkList_Node(LNode*L，intkey)/*刪除以L為頭結(jié)點(diǎn)的單鏈表中值為key的第一個(gè)結(jié)點(diǎn)*/

{LNode*p=L,*q=L–>next;while(q!=NULL){if(q–>data==key)

{p->next=q->next;deleteq;q=p->next;}else{p=q;q=q–>next;}}}

2.3.2

單線性鏈?zhǔn)降幕静僮髯冃沃簞h除單鏈表中所有值重復(fù)的結(jié)點(diǎn)，使得所有結(jié)點(diǎn)的值都不相同。與按值查找相類似，但比前面的算法更復(fù)雜?；舅枷耄簭膯捂湵淼牡谝粋€(gè)結(jié)點(diǎn)開(kāi)始，對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行檢查：檢查鏈表中該結(jié)點(diǎn)的所有后繼結(jié)點(diǎn)，只要有值和該結(jié)點(diǎn)的值相同，則刪除之；然后檢查下一個(gè)結(jié)點(diǎn)，直到所有的結(jié)點(diǎn)都檢查。技巧：兩層循環(huán)2.3.2

單線性鏈?zhǔn)降幕静僮鱲oidDelete_Node_value(LNode*L)/*刪除以L為頭結(jié)點(diǎn)的單鏈表中所有值相同的結(jié)點(diǎn)*/

{LNode*p=L->next,*q,*ptr;while(p!=NULL)/*檢查鏈表中所有結(jié)點(diǎn)*/{*q=p,*ptr=p–>next;/*檢查結(jié)點(diǎn)p的所有后繼結(jié)點(diǎn)ptr*/while(ptr!=NULL){if(ptr–>data==p->data)

{q->next=ptr->next;deleteptr;ptr=q->next;}else{q=ptr;ptr=ptr–>next;}}2.3.2

單線性鏈?zhǔn)降幕静僮鱬=p->next;}}

2.3.2

單線性鏈?zhǔn)降幕静僮?

單鏈表的合并

設(shè)有兩個(gè)有序的單鏈表，它們的頭指針?lè)謩e是La、Lb，將它們合并為以Lc為頭指針的有序鏈表。合并前的示意圖如圖2-4所示。15

?圖2-4

兩個(gè)有序的單鏈表La，Lb的初始狀態(tài)-249……

Lb

pb-7312……

23?La

Lcpapc2.3.2

單線性鏈?zhǔn)降幕静僮骱喜⒘酥禐?7，-2的結(jié)點(diǎn)后示意圖如圖2-5所示。圖2-5

合并了值為-7，-2的結(jié)點(diǎn)后的狀態(tài)-249……

15?Lb

pcpbLc-7312……

23?La

pa算法說(shuō)明算法中pa，pb分別是待考察的兩個(gè)鏈表的當(dāng)前結(jié)點(diǎn)，pc是合并過(guò)程中合并的鏈表的最后一個(gè)結(jié)點(diǎn)。算法描述LNode*Merge_LinkList(LNode*La，LNode*Lb)/*合并以La,Lb為頭結(jié)點(diǎn)的兩個(gè)有序單鏈表*/{LNode*Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}/*將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)*/if(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}/*將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)*/2.3.2

單線性鏈?zhǔn)降幕静僮鱥f(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;deleteptr;}/*將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除*/}if(pa!=NULL)pc->next=pa;elsepc->next=pb;/*將剩余的結(jié)點(diǎn)鏈上*/deleteLb;returnLc;}算法分析若La，Lb兩個(gè)鏈表的長(zhǎng)度分別是m，n，則鏈表合并的時(shí)間復(fù)雜度為O(m+n)。2.3.3

循環(huán)鏈表循環(huán)鏈表(CircularLinkedList)：是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)。從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。

圖2-6是帶頭結(jié)點(diǎn)的單循環(huán)鏈表的示意圖?？毡韴D2-6單循環(huán)鏈表示意圖非空表a1

a2

……anhead

head

2.3.3

循環(huán)鏈表循環(huán)鏈表的操作對(duì)于單循環(huán)鏈表，除鏈表的合并外，其它的操作和單線性鏈表基本上一致，僅僅需要在單線性鏈表操作算法基礎(chǔ)上作以下簡(jiǎn)單修改：⑴判斷是否是空鏈表：head->next==head;⑵判斷是否是表尾結(jié)點(diǎn)：p->next==head;2.4

雙向鏈表

雙向鏈表(DoubleLinkedList):指的是構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)中設(shè)立兩個(gè)指針域：一個(gè)指向其直接前趨的指針域prior，一個(gè)指向其直接后繼的指針域next。這樣形成的鏈表中有兩個(gè)方向不同的鏈，故稱為雙向鏈表。和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。2.4

雙向鏈表1雙向鏈表的結(jié)點(diǎn)及其類型定義雙向鏈表的結(jié)點(diǎn)的類型定義如下。其結(jié)點(diǎn)形式如圖2-7所示，帶頭結(jié)點(diǎn)的雙向鏈表的形式如圖2-8所示。structDulnode{ElemTypedata;structDulnode*prior,*next;};datanextprior圖2-7雙向鏈表結(jié)點(diǎn)形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??圖2-8帶頭結(jié)點(diǎn)的雙向鏈表形式2.4

雙向鏈表雙向鏈表結(jié)構(gòu)具有對(duì)稱性，設(shè)p指向雙向鏈表中的某一結(jié)點(diǎn)，則其對(duì)稱性可用下式描述：(p->prior)->next=p=(p->next)->prior;

結(jié)點(diǎn)p的存儲(chǔ)位置存放在其直接前趨結(jié)點(diǎn)p->prior的直接后繼指針域中，同時(shí)也存放在其直接后繼結(jié)點(diǎn)p->next的直接前趨指針域中。2雙向鏈表的基本操作(1)雙向鏈表的插入將值為e的結(jié)點(diǎn)插入雙向鏈表中。插入前后鏈表的變化如圖2-9所示。Sep…………aiai+1Sep…………aiai+1圖2-9雙向鏈表的插入2.4

雙向鏈表插入時(shí)僅僅指出直接前驅(qū)結(jié)點(diǎn)，鉤鏈時(shí)必須注意先后次序是：“先右后左”。部分語(yǔ)句組如下：S=newDulNode;S->data=e;S->next=p->next;p->next->prior=S;p->next=S;S->prior=p;/*鉤鏈次序非常重要

*/②

插入時(shí)同時(shí)指出直接前驅(qū)結(jié)點(diǎn)p和直接后繼結(jié)點(diǎn)q，鉤鏈時(shí)無(wú)須注意先后次序。部分語(yǔ)句組如下：S=newDulNode;S->data=e;p->next=S;S->next=q;S->prior=p;q->prior=S;

2.4

雙向鏈表

(2)

雙向鏈表的結(jié)點(diǎn)刪除

設(shè)要?jiǎng)h除的結(jié)點(diǎn)為p，刪除時(shí)可以不引入新的輔助指針變量，可以直接先斷鏈，再釋放結(jié)點(diǎn)。部分語(yǔ)句組如下：p->prior->next=p->next;p->next->prior=p->prior;free(p);注意：

與單鏈表的插入和刪除操作不同的是，在雙向鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向上的指針域的指向。2.5

一元多項(xiàng)式的表示和相加1一元多項(xiàng)式的表示

一元多項(xiàng)式p(x)=p0+p1x+p2x2+…

+pnxn，由n+1個(gè)系數(shù)唯一確定。則在計(jì)算機(jī)中可用線性表(p0

，p1

，p2

，…

，pn

)表示。既然是線性表，就可以用順序表和鏈表來(lái)實(shí)現(xiàn)。兩種不同實(shí)現(xiàn)方式的元素類型定義如下：(1)順序存儲(chǔ)表示的類型structElemType{floatcoef;/*系數(shù)部分*/

intexpn;/*指數(shù)部分*/};(2)鏈?zhǔn)酱鎯?chǔ)表示的類型structploy{floatcoef;/*系數(shù)部分*/

intexpn;/*指數(shù)部分*/

structploy*next;};2.5

一元多項(xiàng)式的表示和相加2一元多項(xiàng)式的相加不失一般性，設(shè)有兩個(gè)一元多項(xiàng)式：P(x)=p0+p1x+p2x2+…

+pnxn，Q(x)=q0+q1x+q2x2+…

+qmxm(m<n)R(x)=P(x)+Q(x)R(x)由線性表R((p0+q0)，(p1+q1)，(p2+q2)，…

，(pm+qm)，…

，

pn)唯一表示。2.5

一元多項(xiàng)式的表示和相加⑴順序存儲(chǔ)表示的相加線性表的定義structSqlist{ElemTypea[MAX_SIZE];intlength;};

用順序表示的相加非常簡(jiǎn)單。訪問(wèn)第5項(xiàng)可直接訪問(wèn)：L.a[4].coef，

L.a[4].expn(2)

鏈?zhǔn)酱鎯?chǔ)表示的相加當(dāng)采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，根據(jù)結(jié)點(diǎn)類型定義，凡是系數(shù)為0的項(xiàng)不在鏈表中出現(xiàn)，從而可以大大減少鏈表的長(zhǎng)度。2.5

一元多項(xiàng)式的表示和相加一元多項(xiàng)式相加的實(shí)質(zhì)是：

指數(shù)不同：是鏈表的合并。

指數(shù)相同：系數(shù)相加，和為0，去掉結(jié)點(diǎn)，和不為0，修改結(jié)點(diǎn)的系數(shù)域。算法之一：就在原來(lái)兩個(gè)多項(xiàng)式鏈表的基礎(chǔ)上進(jìn)行相加，相加后原來(lái)兩個(gè)多項(xiàng)式鏈表就不在存在。當(dāng)然再要對(duì)原來(lái)兩個(gè)多項(xiàng)式進(jìn)行其它操作就不允許了。算法描述Ploy*add_ploy(ploy*La，ploy*Lb)

/*將以La，Lb為頭指針表示的一元多項(xiàng)式相加*/{ploy*Lc,*pc,*pa,*pb,*ptr;floatx;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->expn<pb->expn){pc->next=pa;pc=pa;pa=pa->next;}

/*將pa所指的結(jié)點(diǎn)合并，pa指向下一個(gè)結(jié)點(diǎn)*/if(pa->expn>pb->expn){pc->next=pb;pc=pb;pb=pb->next;}

/*將pb所指的結(jié)點(diǎn)合并，pb指向下一個(gè)結(jié)點(diǎn)*/else{x=pa->coef+pb->coef;if(abs(x)<=1.0e-6)

/*如果系數(shù)和為0，刪除兩個(gè)結(jié)點(diǎn)*/{ptr=pa;pa=pa->next;deleteptr;ptr=pb;pb=pb->next;deleteptr;}else

/*如果系數(shù)和不為0，修改其中一個(gè)結(jié)點(diǎn)的系數(shù)域，刪除另一個(gè)結(jié)