數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏本文是歷代傳誦的議論文名篇，應(yīng)引導(dǎo)學(xué)生熟讀課文，利用掌握的議論文知識(shí)來(lái)理解作者的觀點(diǎn)及現(xiàn)實(shí)的教育意義。全文層層推進(jìn)、步步深入的論證，使結(jié)構(gòu)非常清晰，富有說(shuō)服力，可作為教學(xué)難點(diǎn)。積累文言詞匯，理解重點(diǎn)詞句的含義，并了解一些文言實(shí)詞的使動(dòng)用法的作用，正確地翻譯課文。作為本文重點(diǎn)。學(xué)習(xí)本文宜以讀為主，以講為輔。教師引導(dǎo)學(xué)生利用搶記法，比賽法記憶文言詞匯，完成重點(diǎn)。在教師的適當(dāng)引導(dǎo)下學(xué)生的合作、體驗(yàn)、探究來(lái)突破難點(diǎn)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏本文是歷代傳誦的議論文名篇，應(yīng)引導(dǎo)學(xué)生熟讀課文，利用掌握的議論文知識(shí)來(lái)理解作者的觀點(diǎn)及現(xiàn)實(shí)的教育意義。全文層層推進(jìn)、步步深入的論證，使結(jié)構(gòu)非常清晰，富有說(shuō)服力，可作為教學(xué)難點(diǎn)。積累文言詞匯，理解重點(diǎn)詞句的含義，并了解一些文言實(shí)詞的使動(dòng)用法的作用，正確地翻譯課文。作為本文重點(diǎn)。學(xué)習(xí)本文宜以讀為主，以講為輔。教師引導(dǎo)學(xué)生利用搶記法，比賽法記憶文言詞匯，完成重點(diǎn)。在教師的適當(dāng)引導(dǎo)下學(xué)生的合作、體驗(yàn)、探究來(lái)突破難點(diǎn)。第1章緒論目前，計(jì)算機(jī)已深入到社會(huì)生活的各個(gè)領(lǐng)域，其應(yīng)用已不再僅僅局限于科學(xué)計(jì)算，而更多的是用于控制，管理及數(shù)據(jù)處理等非數(shù)值計(jì)算領(lǐng)域。計(jì)算機(jī)是一門(mén)研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。這里面涉及到兩個(gè)問(wèn)題：信息的表示，信息的處理。信息的表示和組織又直接關(guān)系到處理信息的程序的效率。隨著應(yīng)用問(wèn)題的不斷復(fù)雜，導(dǎo)致信息量劇增與信息范圍的拓寬，使許多系統(tǒng)程序和應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)又相當(dāng)復(fù)雜。因此，必須分析待處理問(wèn)題中的對(duì)象的特征及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門(mén)課所要研究的問(wèn)題。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第1頁(yè)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第2頁(yè)。編寫(xiě)解決實(shí)際問(wèn)題的程序的一般過(guò)程：

如何用數(shù)據(jù)形式描述問(wèn)題?—即由問(wèn)題抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型;

問(wèn)題所涉及的數(shù)據(jù)量大小及數(shù)據(jù)之間的關(guān)系;

如何在計(jì)算機(jī)中存儲(chǔ)數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系?

處理問(wèn)題時(shí)需要對(duì)數(shù)據(jù)作何種運(yùn)算?

所編寫(xiě)的程序的性能是否良好?上面所列舉的問(wèn)題基本上由數(shù)據(jù)結(jié)構(gòu)這門(mén)課程來(lái)回答。計(jì)算機(jī)求解問(wèn)題的一般步驟數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第3頁(yè)。1.1

數(shù)據(jù)結(jié)構(gòu)及其概念

《算法與數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)科學(xué)中的一門(mén)綜合性專(zhuān)業(yè)基礎(chǔ)課。是介于數(shù)學(xué)、計(jì)算機(jī)硬件、計(jì)算機(jī)軟件三者之間的一門(mén)核心課程，不僅是一般程序設(shè)計(jì)的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第4頁(yè)。1.1.1

數(shù)據(jù)結(jié)構(gòu)的例子姓名電話號(hào)碼陳四。。。。。例1：電話號(hào)碼查詢(xún)系統(tǒng)

設(shè)有一個(gè)電話號(hào)碼薄，它記錄了N個(gè)人的名字和其相應(yīng)的電話號(hào)碼，假定按如下形式安排：(a1,b1)，(a2,b2)，…(an,bn)，其中ai,bi(i=1，2…n)

分別表示某人的名字和電話號(hào)碼。本問(wèn)題是一種典型的表格問(wèn)題。如表1-1，數(shù)據(jù)與數(shù)據(jù)成簡(jiǎn)單的一對(duì)一的線性關(guān)系。表1-1

線性表結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第5頁(yè)。例2：磁盤(pán)目錄文件系統(tǒng)

磁盤(pán)根目錄下有很多子目錄及文件，每個(gè)子目錄里又可以包含多個(gè)子目錄及文件，但每個(gè)子目錄只有一個(gè)父目錄，依此類(lèi)推：本問(wèn)題是一種典型的樹(shù)型結(jié)構(gòu)問(wèn)題，如圖1-1

，數(shù)據(jù)與數(shù)據(jù)成一對(duì)多的關(guān)系，是一種典型的非線性關(guān)系結(jié)構(gòu)—樹(shù)形結(jié)構(gòu)。圖1-1

樹(shù)形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第6頁(yè)。例3：交通網(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

網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第7頁(yè)。

數(shù)據(jù)(Data)

：是客觀事物的符號(hào)表示。在計(jì)算機(jī)科學(xué)中指的是所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。

數(shù)據(jù)元素(DataElement)

：是數(shù)據(jù)的基本單位，在程序中通常作為一個(gè)整體來(lái)進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項(xiàng)是對(duì)客觀事物某一方面特性的數(shù)據(jù)描述。

數(shù)據(jù)對(duì)象(DataObject)：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如字符集合C={‘A’,’B’,’C,…}。1.1.2

基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第8頁(yè)。

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指相互之間具有(存在)一定聯(lián)系(關(guān)系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關(guān)系)稱(chēng)為邏輯結(jié)構(gòu)。數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)有四種基本類(lèi)型，如圖1-3所示。①集合：結(jié)構(gòu)中的數(shù)據(jù)元素除了“同屬于一個(gè)集合”外，沒(méi)有其它關(guān)系。②線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。③樹(shù)型結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。④圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第9頁(yè)。

數(shù)據(jù)結(jié)構(gòu)的形式定義是一個(gè)二元組：

Data-Structure=(D，S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。例2：設(shè)數(shù)據(jù)邏輯結(jié)構(gòu)B=（K，R）

K={k1,k2,…,k9}R={<k1,k3>，<k1,k8>，<k2,k3>，<k2,k4>，<k2,k5>，<k3,k9>，<k5,k6>，<k8,k9>，<k9,k7>，<k4,k7>，<k4,k6>}

畫(huà)出這邏輯結(jié)構(gòu)的圖示，并確定那些是起點(diǎn)，那些是終點(diǎn)1.1.3

數(shù)據(jù)結(jié)構(gòu)的形式定義圖1-3

四類(lèi)基本結(jié)構(gòu)圖數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第10頁(yè)。1.1.4

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式

數(shù)據(jù)元素之間的關(guān)系可以是元素之間代表某種含義的自然關(guān)系，也可以是為處理問(wèn)題方便而人為定義的關(guān)系，這種自然或人為定義的

“關(guān)系”稱(chēng)為數(shù)據(jù)元素之間的邏輯關(guān)系，相應(yīng)的結(jié)構(gòu)稱(chēng)為邏輯結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間的關(guān)系的表示。元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序表示和非順序表示。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

順序存儲(chǔ)結(jié)構(gòu)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第11頁(yè)。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：在每一個(gè)數(shù)據(jù)元素中增加一個(gè)存放另一個(gè)元素地址的指針(pointer)，用該指針來(lái)表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。例：設(shè)有數(shù)據(jù)集合A={3.0,2.3,5.0,-8.5,11.0}，兩種不同的存儲(chǔ)結(jié)構(gòu)。順序結(jié)構(gòu)：數(shù)據(jù)元素存放的地址是連續(xù)的；

鏈?zhǔn)浇Y(jié)構(gòu)：數(shù)據(jù)元素存放的地址是否連續(xù)沒(méi)有要求。

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個(gè)方面，一個(gè)算法的設(shè)計(jì)取決于所選定的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴(lài)于所采用的存儲(chǔ)結(jié)構(gòu)。在C語(yǔ)言中，用一維數(shù)組表示順序存儲(chǔ)結(jié)構(gòu)；用結(jié)構(gòu)體類(lèi)型表示鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第12頁(yè)。數(shù)據(jù)結(jié)構(gòu)的三個(gè)組成部分：邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間邏輯關(guān)系的描述

D_S=（D，S）存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)及其邏輯關(guān)系的表現(xiàn)稱(chēng)為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或物理結(jié)構(gòu)。數(shù)據(jù)操作：對(duì)數(shù)據(jù)要進(jìn)行的運(yùn)算。本課程中將要討論的三種邏輯結(jié)構(gòu)及其采用的存儲(chǔ)結(jié)構(gòu)如圖1-4所示。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第13頁(yè)。數(shù)據(jù)的邏輯結(jié)構(gòu)非線性結(jié)構(gòu)集合圖狀結(jié)構(gòu)有向圖無(wú)向圖樹(shù)形結(jié)構(gòu)一般樹(shù)二叉樹(shù)線性結(jié)構(gòu)一般線性表線性表推廣廣義表數(shù)組串受限線性表?xiàng)：完?duì)列圖1-5

數(shù)據(jù)邏輯結(jié)構(gòu)層次關(guān)系圖圖1-4

邏輯結(jié)構(gòu)與所采用的存儲(chǔ)結(jié)構(gòu)線性表樹(shù)圖順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)復(fù)合存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)物理結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第14頁(yè)。

數(shù)據(jù)類(lèi)型(DataType)：指的是一個(gè)值的集合和定義在該值集上的一組操作的總稱(chēng)。數(shù)據(jù)類(lèi)型是和數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的一個(gè)概念。在C語(yǔ)言中數(shù)據(jù)類(lèi)型有：基本類(lèi)型和構(gòu)造類(lèi)型。數(shù)據(jù)結(jié)構(gòu)不同于數(shù)據(jù)類(lèi)型，也不同于數(shù)據(jù)對(duì)象，它不僅要描述數(shù)據(jù)類(lèi)型的數(shù)據(jù)對(duì)象，而且要描述數(shù)據(jù)對(duì)象各元素之間的相互關(guān)系。1.1.5

數(shù)據(jù)類(lèi)型數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第15頁(yè)。

數(shù)據(jù)結(jié)構(gòu)的主要運(yùn)算包括：⑴建立(Create)一個(gè)數(shù)據(jù)結(jié)構(gòu)；⑵消除(Destroy)一個(gè)數(shù)據(jù)結(jié)構(gòu)；⑶從一個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除(Delete)一個(gè)數(shù)據(jù)元素；⑷把一個(gè)數(shù)據(jù)元素插入(Insert)到一個(gè)數(shù)據(jù)結(jié)構(gòu)中；⑸對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行訪問(wèn)(Access)；⑹對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)(中的數(shù)據(jù)元素)進(jìn)行修改(Modify)；⑺對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序(Sort)；⑻對(duì)一個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找(Search)。1.1.6

數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第16頁(yè)。

抽象數(shù)據(jù)類(lèi)型(AbstractDataType

，簡(jiǎn)稱(chēng)ADT)：是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。

ADT的定義僅是一組邏輯特性描述，與其在計(jì)算機(jī)內(nèi)的表示和實(shí)現(xiàn)無(wú)關(guān)。因此，不論ADT的內(nèi)部結(jié)構(gòu)如何變化，只要其數(shù)學(xué)特性不變，都不影響其外部使用。

ADT的形式化定義是三元組：ADT=(D，S，P)其中：D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。1.2

抽象數(shù)據(jù)類(lèi)型數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第17頁(yè)。ADT的一般定義形式是：ADT<抽象數(shù)據(jù)類(lèi)型名>{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT<抽象數(shù)據(jù)類(lèi)型名>

其中數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述。基本操作的定義是：<基本操作名>(<參數(shù)表>)初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第18頁(yè)。

初始條件：描述操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿(mǎn)足的條件;若不滿(mǎn)足，則操作失敗，返回相應(yīng)的出錯(cuò)信息。操作結(jié)果：描述操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第19頁(yè)。1.3.1

算法算法(Algorithm)：是對(duì)特定問(wèn)題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性①有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。②

確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個(gè)入口和一個(gè)出口。③可行性：一個(gè)算法是能行的。即算法描述的操作都可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。1.3

算法分析初步數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第20頁(yè)。④輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。⑤輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。一個(gè)算法可以用多種方法描述，主要有：使用自然語(yǔ)言描述；使用形式語(yǔ)言描述；使用計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言描述。

算法和程序是兩個(gè)不同的概念。一個(gè)計(jì)算機(jī)程序是對(duì)一個(gè)算法使用某種程序設(shè)計(jì)語(yǔ)言的具體實(shí)現(xiàn)。算法必須可終止意味著不是所有的計(jì)算機(jī)程序都是算法。在本門(mén)課程的學(xué)習(xí)、作業(yè)練習(xí)、上機(jī)實(shí)踐等環(huán)節(jié)，算法都用C語(yǔ)言來(lái)描述。在上機(jī)實(shí)踐時(shí)，為了檢查算法是否正確，應(yīng)編寫(xiě)成完整的C語(yǔ)言程序。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第21頁(yè)。評(píng)價(jià)一個(gè)好的算法有以下幾個(gè)標(biāo)準(zhǔn)①

正確性(Correctness

)：算法應(yīng)滿(mǎn)足具體問(wèn)題的需求。②

可讀性(Readability)：算法應(yīng)容易供人閱讀和交流?？勺x性好的算法有助于對(duì)算法的理解和修改。③

健壯性(Robustness)：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法或錯(cuò)誤數(shù)據(jù)時(shí)，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行處理，而不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果。④

通用性(Generality)：算法應(yīng)具有一般性，即算法的處理結(jié)果對(duì)于一般的數(shù)據(jù)集合都成立。1.3.2

算法設(shè)計(jì)的要求數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第22頁(yè)。

算法執(zhí)行時(shí)間需通過(guò)依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間來(lái)度量。其方法通常有兩種：事后統(tǒng)計(jì)：計(jì)算機(jī)內(nèi)部進(jìn)行執(zhí)行時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)。問(wèn)題：必須先運(yùn)行依據(jù)算法編制的程序；依賴(lài)軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒(méi)有實(shí)際價(jià)值。事前分析：求出該算法的一個(gè)時(shí)間界限函數(shù)。1.3.3

算法效率的度量⑤

效率與存儲(chǔ)量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過(guò)程中所需要的最大存儲(chǔ)空間。一般地，這兩者與問(wèn)題的規(guī)模有關(guān)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第23頁(yè)。與此相關(guān)的因素有：依據(jù)算法選用何種策略；問(wèn)題的規(guī)模；程序設(shè)計(jì)的語(yǔ)言；編譯程序所產(chǎn)生的機(jī)器代碼的質(zhì)量；機(jī)器執(zhí)行指令的速度；撇開(kāi)軟硬件等有關(guān)部門(mén)因素，可以認(rèn)為一個(gè)特定算法“運(yùn)行工作量”的大小，只依賴(lài)于問(wèn)題的規(guī)模（通常用n表示），或者說(shuō)，它是問(wèn)題規(guī)模的函數(shù)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第24頁(yè)。算法分析應(yīng)用舉例

算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，其時(shí)間量度記作T(n)=O(f(n))，稱(chēng)作算法的漸近時(shí)間復(fù)雜度(AsymptoticTimecomplexity)，簡(jiǎn)稱(chēng)時(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í)間階數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第25頁(yè)。

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(mén)(n)=O(n3)例２{++x;s=0;}

將x自增看成是基本操作，則語(yǔ)句頻度為１，即時(shí)間復(fù)雜度為Ｏ(1)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第26頁(yè)。如果將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)，即為平方階。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第27頁(yè)。定理：若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∴時(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)限界。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第28頁(yè)。

以下六種計(jì)算算法時(shí)間的多項(xiàng)式是最常用的。其關(guān)系為：

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)

指數(shù)時(shí)間的關(guān)系為：

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

當(dāng)n取得很大時(shí)，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時(shí)間算法中的任何一個(gè)算法化簡(jiǎn)為多項(xiàng)式時(shí)間算法，那就取得了一個(gè)偉大的成就。有的情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)還隨問(wèn)題的輸入數(shù)據(jù)集不同而不同。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第29頁(yè)。例1：素?cái)?shù)的判斷算法。Voidprime(intn)/*n是一個(gè)正整數(shù)*/{inti=2;while((n%i)!=0&&i*1.0<sqrt(n))i++;if(i*1.0>sqrt(n))printf(“&d是一個(gè)素?cái)?shù)\n”,n);elseprintf(“&d不是一個(gè)素?cái)?shù)\n”,n);}

嵌套的最深層語(yǔ)句是i++；其頻度由條件((n%i)!=0&&i*1.0<sqrt(n))決定，顯然i*1.0<sqrt(n)，時(shí)間復(fù)雜度O(n1/2)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第30頁(yè)。例2：冒泡排序法。Voidbubble_sort(inta[]，intn){change=false;for(i=n-1;change=TURE;i>1&&change;--i)for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE;}}

最好情況：0次最壞情況：1+2+3+?+n-1=n(n-1)/2

平均時(shí)間復(fù)雜度為：O(n2)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第31頁(yè)。1.3.4

算法的空間分析

空間復(fù)雜度(Spacecomplexity)：是指算法編寫(xiě)成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的度量。記作：S(n)=O(f(n))其中：n為問(wèn)題的規(guī)模(或大小)該存儲(chǔ)空間一般包括三個(gè)方面：指令常數(shù)變量所占用的存儲(chǔ)空間;

輸入數(shù)據(jù)所占用的存儲(chǔ)空間;

輔助(存儲(chǔ))空間。一般地，算法的空間復(fù)雜度指的是輔助空間。

一維數(shù)組a[n]：空間復(fù)雜度O(n)

二維數(shù)組a[n][m]：空間復(fù)雜度O(n*m)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第32頁(yè)。習(xí)題一1簡(jiǎn)要回答術(shù)語(yǔ)：數(shù)據(jù)，數(shù)據(jù)元素，數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)類(lèi)型。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ō)明分析的理由或原因。

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第33頁(yè)。⑴Sum1(intn){intp=1,sum=0,m;for(m=1;m<=n;m++){p*=m;sum+=p;}return(sum);}⑵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);}⑶遞歸函數(shù)fact(intn){if(n<=1)return(1);elsereturn(n*fact(n-1));}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第34頁(yè)。第2章

線性表

線性結(jié)構(gòu)是最常用、最簡(jiǎn)單的一種數(shù)據(jù)結(jié)構(gòu)。而線性表是一種典型的線性結(jié)構(gòu)。其基本特點(diǎn)是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：①

存在一個(gè)唯一的被稱(chēng)為“第一個(gè)”的數(shù)據(jù)元素；②存在一個(gè)唯一的被稱(chēng)為“最后一個(gè)”的數(shù)據(jù)元素；③

除第一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接前驅(qū)；④

除最后一個(gè)元素外，每個(gè)元素均有唯一一個(gè)直接后繼。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第35頁(yè)。2.1

線性表的邏輯結(jié)構(gòu)線性表(LinearList)：是由n(n≧0)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。該序列中的所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類(lèi)型。其中數(shù)據(jù)元素的個(gè)數(shù)n稱(chēng)為線性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱(chēng)為空表。當(dāng)n>0時(shí)，將非空的線性表記作：(a1，a2，…an)a1稱(chēng)為線性表的第一個(gè)(首)結(jié)點(diǎn)，an稱(chēng)為線性表的最后一個(gè)(尾)結(jié)點(diǎn)。2.1.1

線性表的定義數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第36頁(yè)。a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，其中ai+1是ai的直接后繼。2.1.2

線性表的邏輯結(jié)構(gòu)

線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應(yīng)用的不同而不同，在線性表的定義中，只不過(guò)是一個(gè)抽象的表示符號(hào)?！艟€性表中的結(jié)點(diǎn)可以是單值元素(每個(gè)元素只有一個(gè)數(shù)據(jù)項(xiàng))。例1:26個(gè)英文字母組成的字母表：(A，B，C、…、Z）數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第37頁(yè)。例2：某校從1978年到1983年各種型號(hào)的計(jì)算機(jī)擁有量的變化情況：(6，17，28，50，92，188）例3：一副撲克的點(diǎn)數(shù)(2，3，4，…，J，Q，K，A)

◆

線性表中的結(jié)點(diǎn)可以是記錄型元素，每個(gè)元素含有多個(gè)數(shù)據(jù)項(xiàng)，每個(gè)項(xiàng)稱(chēng)為結(jié)點(diǎn)的一個(gè)域。每個(gè)元素有一個(gè)可以唯一標(biāo)識(shí)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)項(xiàng)組，稱(chēng)為關(guān)鍵字。例4：某校2001級(jí)同學(xué)的基本情況：{(‘2001414101’，‘張里戶(hù)’，‘男’，06/24/1983)，(‘2001414102’，‘張化司’，‘男’，08/12/1984)…，(‘2001414102’，‘李利辣’，‘女’，08/12/1984)}

◆

若線性表中的結(jié)點(diǎn)是按值(或按關(guān)鍵字值)由小到大(或由大到小)排列的，稱(chēng)線性表是有序的。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第38頁(yè)。2.1.3

線性表的抽象數(shù)據(jù)類(lèi)型定義ADTList{數(shù)據(jù)對(duì)象：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}基本操作：InitList(&L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L；

◆

線性表是一種相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，其長(zhǎng)度可根據(jù)需要增長(zhǎng)或縮短。

◆

對(duì)線性表的數(shù)據(jù)元素可以訪問(wèn)、插入和刪除。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第39頁(yè)。ListLength(L)初始條件：線性表L已存在；操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE；….GetElem(L,i,&e)初始條件：線性表L已存在，1≦i≦ListLength(L)；操作結(jié)果：用e返回L中第i個(gè)數(shù)據(jù)元素的值；ListInsert(L,i,&e)初始條件：線性表L已存在，1≦i≦ListLength(L)；操作結(jié)果：在線性表L中的第i個(gè)位置插入元素e；…}ADTList數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第40頁(yè)。2.2

線性表的順序存儲(chǔ)

順序存儲(chǔ)：把線性表的結(jié)點(diǎn)按邏輯順序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。用這種方法存儲(chǔ)的線性表簡(jiǎn)稱(chēng)順序表。順序存儲(chǔ)的線性表的特點(diǎn)：

◆線性表的邏輯順序與物理順序一致;

◆數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來(lái)體現(xiàn)。設(shè)有非空的線性表：(a1，a2，…an)。順序存儲(chǔ)如圖2-1所示。2.2.1

線性表的順序存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第41頁(yè)。

在具體的機(jī)器環(huán)境下：設(shè)線性表的每個(gè)元素需占用l個(gè)存儲(chǔ)單元，以所占的第一個(gè)單元的存儲(chǔ)地址作為數(shù)據(jù)元素的存儲(chǔ)位置。則線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)之間滿(mǎn)足下列關(guān)系：

LOC(ai+1)=LOC(ai)+l

線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：

LOC(ai)=LOC(a1)+(i-1)*l

…a1a2…ai…an…Loc(a1)Loc(ai)+(i-1)*l

圖2-1

線性表的順序存儲(chǔ)表示數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第42頁(yè)。

在高級(jí)語(yǔ)言(如C語(yǔ)言)環(huán)境下：數(shù)組具有隨機(jī)存取的特性，因此，借助數(shù)組來(lái)描述順序表。除了用數(shù)組來(lái)存儲(chǔ)線性表的元素之外，順序表還應(yīng)該有表示線性表的長(zhǎng)度屬性，所以用結(jié)構(gòu)類(lèi)型來(lái)定義順序表類(lèi)型。#defineOK1#defineERROR-1#defineMAX_SIZE100typedefintStatus;typedefintElemType;typedefstructsqlist{ElemTypeElem_array[MAX_SIZE];intlength;}SqList;數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第43頁(yè)。2.2.2

順序表的基本操作

順序存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長(zhǎng)度等。以下將對(duì)幾種主要的操作進(jìn)行討論。1順序線性表初始化

StatusInit_SqList(SqList*L){L->elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L->elem_array)returnERROR;else{L->length=0;returnOK;}}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第44頁(yè)。2

順序線性表的插入

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)個(gè)位置上插入一個(gè)新結(jié)點(diǎn)e，使其成為線性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

實(shí)現(xiàn)步驟(1)

將線性表L中的第i個(gè)至第n個(gè)結(jié)點(diǎn)后移一個(gè)位置。(2)將結(jié)點(diǎn)e插入到結(jié)點(diǎn)ai-1之后。(3)線性表長(zhǎng)度加1。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第45頁(yè)。算法描述StatusInsert_SqList(Sqlist*L，inti，ElemTypee)

{intj;if(i<0||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;}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第46頁(yè)。

時(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ù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第47頁(yè)。3順序線性表的刪除

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中刪除結(jié)點(diǎn)ai(1≦i≦n)，使其成為線性表：

L=(a1，…ai-1，ai+1，…，an)

實(shí)現(xiàn)步驟(1)

將線性表L中的第i+1個(gè)至第n個(gè)結(jié)點(diǎn)依此向前移動(dòng)一個(gè)位置。(2)線性表長(zhǎng)度減1。算法描述ElemTypeDelete_SqList(Sqlist*L，inti){intk;ElemTypex;數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第48頁(yè)。if(L->length==0){printf(“線性表L為空!\n”);returnERROR;}elseif(i<1||i>L->length){printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!\n”);returnERROR;}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ù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第49頁(yè)。

時(shí)間復(fù)雜度分析

刪除線性表L中的第i個(gè)元素，其時(shí)間主要耗費(fèi)在表中結(jié)點(diǎn)的移動(dòng)操作上，因此，可用結(jié)點(diǎn)的移動(dòng)來(lái)估計(jì)算法的時(shí)間復(fù)雜度。設(shè)在線性表L中刪除第i個(gè)元素的概率為Pi，不失一般性，設(shè)刪除各個(gè)位置是等概率，則Pi=1/n，而刪除時(shí)移動(dòng)結(jié)點(diǎn)的次數(shù)為n-i。則總的平均移動(dòng)次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在順序表上做刪除運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。因此算法的平均時(shí)間復(fù)雜度為O(n)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第50頁(yè)。4順序線性表的查找定位刪除

在線性表L=(a1，a2，…，an)中刪除值為x的第一個(gè)結(jié)點(diǎn)。實(shí)現(xiàn)步驟(1)

在線性表L查找值為x的第一個(gè)數(shù)據(jù)元素。(2)將從找到的位置至最后一個(gè)結(jié)點(diǎn)依次向前移動(dòng)一個(gè)位置。

(3)線性表長(zhǎng)度減1。算法描述StatusLocate_Delete_SqList(Sqlist*L，ElemTypex)

/*刪除線性表L中值為x的第一個(gè)結(jié)點(diǎn)*/{inti=0,k;

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第51頁(yè)。while(i<L->length)/*查找值為x的第一個(gè)結(jié)點(diǎn)*/{if(L->Elem_array[i]!=x)i++;else{for(k=i+1;k<L->length;k++)L->Elem_array[k-1]=L->Elem_array[k];L->length--;break;}}if(i>L->length){printf(“要?jiǎng)h除的數(shù)據(jù)元素不存在!\n”);returnERROR;}returnOK;}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第52頁(yè)。

時(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。

◆刪除時(shí)平均移動(dòng)次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。平均時(shí)間復(fù)雜度：Ecompare+Edelete=n，即為O(n)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第53頁(yè)。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ēng)線性鏈表。存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第54頁(yè)。

為了正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其直接后繼結(jié)點(diǎn)的地址(或位置)，稱(chēng)為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)，如圖2-2所示。鏈表是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。每一個(gè)結(jié)只包含一個(gè)指針域的鏈表，稱(chēng)為單鏈表。為操作方便，總是在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)頭結(jié)點(diǎn)(頭指針)head指向第一個(gè)結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息(或鏈表長(zhǎng)度等信息)。datanext圖2-2

鏈表結(jié)點(diǎn)結(jié)構(gòu)data：數(shù)據(jù)域，存放結(jié)點(diǎn)的值。next：指針域，存放結(jié)點(diǎn)的直接后繼的地址。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第55頁(yè)。

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat?head

圖2-3

帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)、物理存儲(chǔ)方式單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。例1、線性表L=(bat，cat，eat，fat，hat)其帶頭結(jié)點(diǎn)的單鏈表的邏輯狀態(tài)和物理存儲(chǔ)方式如圖2-3所示。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第56頁(yè)。1

結(jié)點(diǎn)的描述與實(shí)現(xiàn)

C語(yǔ)言中用帶指針的結(jié)構(gòu)體類(lèi)型來(lái)描述typedefstructLnode{ElemTypedata;/*數(shù)據(jù)域，保存結(jié)點(diǎn)的值*/structLnode*next;/*指針域*/}LNode;/*結(jié)點(diǎn)的類(lèi)型*/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í)是分別使用C語(yǔ)言提供的標(biāo)準(zhǔn)函數(shù)：malloc()，realloc()，sizeof()，free()。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第57頁(yè)。動(dòng)態(tài)分配

p=(LNode*)malloc(sizeof(LNode));函數(shù)malloc分配了一個(gè)類(lèi)型為L(zhǎng)Node的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。動(dòng)態(tài)釋放

free(p);系統(tǒng)回收由指針變量p所指向的內(nèi)存區(qū)。P必須是最近一次調(diào)用malloc函數(shù)時(shí)的返回值。3最常用的基本操作及其示意圖⑴

結(jié)點(diǎn)的賦值

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第58頁(yè)。⑵

常見(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)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第59頁(yè)。⑤

q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第60頁(yè)。2.3.2

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

建立單鏈表

假設(shè)線性表中結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型是整型，以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)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第61頁(yè)。算法描述LNode*create_LinkList(void)/*頭插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值*/{intdata;LNode*head,*p;head=(LNode*)malloc(sizeof(LNode));head->next=NULL;/*創(chuàng)建鏈表的表頭結(jié)點(diǎn)head*/while(1){scanf(“%d”,&data);if(data==32767)break;p=(LNode*)malloc(sizeof(LNode));p–>data=data;/*數(shù)據(jù)域賦值*/數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第62頁(yè)。p–>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)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第63頁(yè)。算法描述LNode*create_LinkList(void)

/*尾插入法創(chuàng)建單鏈表,鏈表的頭結(jié)點(diǎn)head作為返回值*/{intdata;LNode*head,*p,*q;head=p=(LNode*)malloc(sizeof(LNode));p->next=NULL;/*創(chuàng)建單鏈表的表頭結(jié)點(diǎn)head*/while(1){scanf(“%d”,&data);if(data==32767)break;q=(LNode*)malloc(sizeof(LNode));q–>data=data;/*數(shù)據(jù)域賦值*/q–>next=p–>next;p–>next=q;p=q;數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第64頁(yè)。

/*鉤鏈，新創(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)有明確給出直接后繼，鉤鏈(或重新鉤鏈)的次序必須是“先右后左”。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第65頁(yè)。2

單鏈表的查找(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的值是合法的。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第66頁(yè)。算法描述ElemTypeGet_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(-32768);elsereturn(p->data);

/*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)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第67頁(yè)。(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作比較。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第68頁(yè)。算法描述LNode

*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)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第69頁(yè)。3

單鏈表的插入

插入運(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++;}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第70頁(yè)。if(j!=i-1)printf(“i太大或i為0!!\n”);else{q=(LNode*)malloc(sizeof(LNode));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)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第71頁(yè)。4

單鏈表的刪除⑴

按序號(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)。

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第72頁(yè)。算法描述voidDelete_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;free(q);}}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第73頁(yè)。⑵按值刪除

刪除單鏈表中值為key的第一個(gè)結(jié)點(diǎn)。與按值查找相類(lèi)似，首先要查找值為key的結(jié)點(diǎn)是否存在?若存在，則刪除；否則返回NULL。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第74頁(yè)。算法描述voidDelete_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;free(q);}elseprintf(“所要?jiǎng)h除的結(jié)點(diǎn)不存在!!\n”);}

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第75頁(yè)。算法的執(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)。與按值查找相類(lèi)似，但比前面的算法更簡(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)都檢查。

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第76頁(yè)。算法描述voidDelete_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;free(q);q=p->next;}else{p=q;q=q–>next;}}}

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第77頁(yè)。變形之二：刪除單鏈表中所有值重復(fù)的結(jié)點(diǎn)，使得所有結(jié)點(diǎn)的值都不相同。與按值查找相類(lèi)似，但比前面的算法更復(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)都檢查。

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第78頁(yè)。算法描述voidDelete_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;free(ptr);ptr=q->next;}else{q=ptr;ptr=ptr–>next;}}數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第79頁(yè)。p=p->next;}}

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第80頁(yè)。5

單鏈表的合并

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

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

Lb

pb-7312……

23?La

Lcpapc數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第81頁(yè)。合并了值為-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)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第82頁(yè)。算法描述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)*/數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第83頁(yè)。if(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;free(ptr);}/*將pa所指的結(jié)點(diǎn)合并，pb所指結(jié)點(diǎn)刪除*/}if(pa!=NULL)pc->next=pa;elsepc->next=pb;/*將剩余的結(jié)點(diǎn)鏈上*/free(Lb);return(Lc);}算法分析若La，Lb兩個(gè)鏈表的長(zhǎng)度分別是m，n，則鏈表合并的時(shí)間復(fù)雜度為O(m+n)。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第84頁(yè)。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

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第85頁(yè)。循環(huán)鏈表的操作對(duì)于單循環(huán)鏈表，除鏈表的合并外，其它的操作和單線性鏈表基本上一致，僅僅需要在單線性鏈表操作算法基礎(chǔ)上作以下簡(jiǎn)單修改：⑴判斷是否是空鏈表：head->next==head;⑵判斷是否是表尾結(jié)點(diǎn)：p->next==head;數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第86頁(yè)。2.4

雙向鏈表

雙向鏈表(DoubleLinkedList):指的是構(gòu)成鏈表的每個(gè)結(jié)點(diǎn)中設(shè)立兩個(gè)指針域：一個(gè)指向其直接前趨的指針域prior，一個(gè)指向其直接后繼的指針域next。這樣形成的鏈表中有兩個(gè)方向不同的鏈，故稱(chēng)為雙向鏈表。和單鏈表類(lèi)似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運(yùn)算變得方便。將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來(lái)也能構(gòu)成循環(huán)鏈表，并稱(chēng)之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第87頁(yè)。1雙向鏈表的結(jié)點(diǎn)及其類(lèi)型定義

雙向鏈表的結(jié)點(diǎn)的類(lèi)型定義如下。其結(jié)點(diǎn)形式如圖2-7所示，帶頭結(jié)點(diǎn)的雙向鏈表的形式如圖2-8所示。typedefstructDulnode{ElemTypedata;structDulnode*prior,*next;}DulNode;datanextprior圖2-7雙向鏈表結(jié)點(diǎn)形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??圖2-8帶頭結(jié)點(diǎn)的雙向鏈表形式數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第88頁(yè)。雙向鏈表結(jié)構(gòu)具有對(duì)稱(chēng)性，設(shè)p指向雙向鏈表中的某一結(jié)點(diǎn)，則其對(duì)稱(chēng)性可用下式描述：(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雙向鏈表的插入數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第89頁(yè)。①

插入時(shí)僅僅指出直接前驅(qū)結(jié)點(diǎn)，鉤鏈時(shí)必須注意先后次序是：“先右后左”

。部分語(yǔ)句組如下：S=(DulNode*)malloc(sizeof(DulNode));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=(DulNode*)malloc(sizeof(DulNode));S->data=e;p->next=S;S->next=q;S->prior=p;q->prior=S;

數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第90頁(yè)。

(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è)方向上的指針域的指向。數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏全文共815頁(yè)，當(dāng)前為第91頁(yè)。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)方式的元素類(lèi)型定義如下：(1)順序存儲(chǔ)表示的類(lèi)型typedefstruct{floatcoef;/*系數(shù)部分*/intexpn