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

1引言數(shù)據(jù)結(jié)構(gòu)的概念及其研究的問(wèn)題，是本章中重要的概念，它們貫穿整本書(shū)。除了數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面，我們對(duì)每種數(shù)據(jù)結(jié)構(gòu)都會(huì)給出應(yīng)用的實(shí)例。要學(xué)會(huì)描述數(shù)據(jù)結(jié)構(gòu)和算法，分析算法的時(shí)、空復(fù)雜度。第1章基礎(chǔ)知識(shí)

數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE21.1算法和數(shù)據(jù)結(jié)構(gòu)瑞士的Wirth博士圖靈獎(jiǎng)獲得者提出：程序＝算法+數(shù)據(jù)結(jié)構(gòu)31.1算法和數(shù)據(jù)結(jié)構(gòu)課堂提要第1章基礎(chǔ)知識(shí)1.1算法和數(shù)據(jù)結(jié)構(gòu)1.2什么是數(shù)據(jù)結(jié)構(gòu)1.3數(shù)據(jù)抽象和抽象數(shù)據(jù)類型1.4描述數(shù)據(jù)結(jié)構(gòu)和算法1.5算法分析的基本方法

數(shù)據(jù)結(jié)構(gòu)和算法是計(jì)算機(jī)學(xué)科的基礎(chǔ)之一，更是軟件技術(shù)的基礎(chǔ)。

算法設(shè)計(jì)通常建立在所處理的數(shù)據(jù)之上的，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高效率的算法。程序＝算法+數(shù)據(jù)結(jié)構(gòu)4精心設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)真的可以帶來(lái)更高效率的算法嗎？5

圖一6，

圖二7

數(shù)據(jù)在計(jì)算機(jī)中的表示和存儲(chǔ)不能是無(wú)組織的，是有規(guī)律，有結(jié)構(gòu)的。

81.數(shù)據(jù)：計(jì)算機(jī)加工處理的對(duì)象

2.數(shù)據(jù)元素：是組成數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體來(lái)處理。數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成。3.數(shù)據(jù)項(xiàng)是不可再分割的。1.2什么是數(shù)據(jù)結(jié)構(gòu)

1.2.1基本概念9表1.1學(xué)生情況表學(xué)號(hào)姓名性別其他信息B02040101王小紅女…B02040102林悅女…B02040103陳菁女…B02040104張可可男……………數(shù)據(jù)項(xiàng)10數(shù)據(jù)結(jié)構(gòu)的由來(lái)

數(shù)據(jù)結(jié)構(gòu)主要是為研究和解決如何使用計(jì)算機(jī)組織和處理這些非數(shù)值問(wèn)題而產(chǎn)生的理論、技術(shù)和方法。它已成為計(jì)算機(jī)學(xué)科研究的基本課題之一。

11什么是數(shù)據(jù)結(jié)構(gòu)定義1----

數(shù)據(jù)元素之間的相互關(guān)系稱為結(jié)構(gòu)，帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合稱為數(shù)據(jù)結(jié)構(gòu)。定義2----按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計(jì)算機(jī)語(yǔ)言并按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在其上定義了一個(gè)運(yùn)算的集合。12

數(shù)據(jù)結(jié)構(gòu)包括三個(gè)方面邏輯結(jié)構(gòu)：數(shù)據(jù)元素間的邏輯關(guān)系；存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)內(nèi)的表示形式；運(yùn)算：在數(shù)據(jù)上執(zhí)行的操作。13數(shù)據(jù)結(jié)構(gòu)舉例表1.1學(xué)生情況表學(xué)號(hào)姓名性別其他信息B02040101王小紅女…B02040102林悅女…B02040103陳菁女…B02040104張可可男……………邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)，運(yùn)算141.2.2數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)可以用一個(gè)二元組表示。即DS=（D，R）其中，D是數(shù)據(jù)元素的有限集合，R是D中數(shù)據(jù)元素序偶的集合。例如DS={D,R},D={a,b,c,d},R={<a,b>,<b,c>,<c,d>},

其中，序偶<a,b>表示a和b之間的關(guān)系，我們稱為a是b的直接前驅(qū)，b是a的直接后繼。小圓圈代表數(shù)據(jù)元素，兩個(gè)不同元素的序偶稱為邊。abcd154種基本的邏輯結(jié)構(gòu)

(a)集合結(jié)構(gòu)(b)線性結(jié)構(gòu)(c)樹(shù)形結(jié)構(gòu)(d)圖結(jié)構(gòu)圖1-2四種基本的結(jié)構(gòu)關(guān)系對(duì)數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。根據(jù)數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間關(guān)系的不同特征，可以劃分為以下四種基本邏輯結(jié)構(gòu)：16

線性結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。一個(gè)前驅(qū)，一個(gè)后繼。樹(shù)形結(jié)構(gòu)：數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。圖結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的數(shù)目都不同。集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，沒(méi)有其它關(guān)系。四種邏輯結(jié)構(gòu)也可以分成兩類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。(a)集合結(jié)構(gòu)(b)線性結(jié)構(gòu)(c)樹(shù)形結(jié)構(gòu)(d)圖結(jié)構(gòu)圖1-2四種基本的結(jié)構(gòu)關(guān)系17

幾種存儲(chǔ)結(jié)構(gòu)

順序結(jié)構(gòu)鏈接結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu)

地址信息稱為鏈?！谋硎究真?。1.2.3數(shù)據(jù)的存儲(chǔ)表示存儲(chǔ)結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)形式，是數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的表示，即數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式。其中，順序和鏈接是兩種最基本的存儲(chǔ)表示方法。18

順序存儲(chǔ)順序（或稱連續(xù)）表示方法需要一塊連續(xù)的存儲(chǔ)空間，并把邏輯上相關(guān)的數(shù)據(jù)元素一次存儲(chǔ)在該連續(xù)的存儲(chǔ)區(qū)中。

例如，由4個(gè)元素組成的線性數(shù)據(jù)結(jié)構(gòu)（a0,a1,a2,a3），存儲(chǔ)在某個(gè)連續(xù)的存儲(chǔ)區(qū)內(nèi)，設(shè)存儲(chǔ)區(qū)的起始地址是102，假定每個(gè)元素占2個(gè)存儲(chǔ)單元。Loc(ak)=102+2×k19

鏈?zhǔn)酱鎯?chǔ)

例如，線性結(jié)構(gòu)（a0,a1,a2,a3

）的鏈接存儲(chǔ)表示。

結(jié)點(diǎn)存儲(chǔ)塊分成兩部分，元素本身和該元素后繼元素所在結(jié)點(diǎn)的存儲(chǔ)地址。

DataLink鏈接存儲(chǔ)表示下，為在機(jī)內(nèi)存儲(chǔ)一個(gè)元素，除了需要存放該元素本身的信息外，還需要存放于該元素相關(guān)的其它元素的地址信息。這兩部分信息組成一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。20邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)概念數(shù)據(jù)元素之間邏輯關(guān)系的描述數(shù)據(jù)及其關(guān)系在計(jì)算機(jī)內(nèi)的組織方式面向面向應(yīng)用問(wèn)題面向計(jì)算機(jī)關(guān)系存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的映像

小結(jié)211.2.4數(shù)據(jù)結(jié)構(gòu)的運(yùn)算數(shù)據(jù)結(jié)構(gòu)最常見(jiàn)的運(yùn)算創(chuàng)建運(yùn)算:創(chuàng)建一個(gè)數(shù)據(jù)結(jié)構(gòu)；

清除運(yùn)算:刪除數(shù)據(jù)結(jié)構(gòu)中的全部元素；插入運(yùn)算:在數(shù)據(jù)結(jié)構(gòu)的指定位置上插入一個(gè)新元素；刪除運(yùn)算:將數(shù)據(jù)結(jié)構(gòu)中的某個(gè)元素刪除；……22

靜態(tài)數(shù)據(jù)結(jié)構(gòu)和動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)

如果一個(gè)數(shù)據(jù)結(jié)構(gòu)一旦創(chuàng)建，其結(jié)構(gòu)不發(fā)生改變，則稱為靜態(tài)數(shù)據(jù)結(jié)構(gòu)，否則成為動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。23

小結(jié)

數(shù)據(jù)結(jié)構(gòu)是一門研究程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象（數(shù)據(jù)）以及它們之間的關(guān)系和運(yùn)算的學(xué)科。241.3數(shù)據(jù)抽象和抽象數(shù)據(jù)類型

抽象，封裝和信息隱蔽是控制軟件開(kāi)發(fā)復(fù)雜度，提高軟件可靠性的重要手段．

本書(shū)采用抽象數(shù)據(jù)類型的觀點(diǎn)討論數(shù)據(jù)結(jié)構(gòu)。課堂提要第1章基礎(chǔ)知識(shí)1.1算法和數(shù)據(jù)結(jié)構(gòu)1.2什么是數(shù)據(jù)結(jié)構(gòu)1.3數(shù)據(jù)抽象和抽象數(shù)據(jù)類型1.4描述數(shù)據(jù)結(jié)構(gòu)和算法1.5算法分析的基本方法251.C語(yǔ)言的數(shù)據(jù)類型(1)基本類型：字符、整型……

(2)構(gòu)造類型：數(shù)組、結(jié)構(gòu)和聯(lián)合(3)指針類型：指針例如，inta;變量a的取值范圍是：-32768

32767對(duì)變量a執(zhí)行的操作有：算術(shù)運(yùn)算+、-、*、/、%

關(guān)系運(yùn)算<、>、<=、>=、==、!=2.數(shù)據(jù)類型一個(gè)數(shù)據(jù)類型定義了一個(gè)值的集合以及作用于該值集的操作的集合。即一組值和一組操作。1.3.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型

26抽象數(shù)據(jù)類型（AbstractDataType,ADT）是一個(gè)數(shù)據(jù)類型，其主要特征是該類型的對(duì)象及其操作的規(guī)范,與該類型對(duì)象的表示和操作的實(shí)現(xiàn)分離，實(shí)行封裝和信息隱蔽，即使用和實(shí)現(xiàn)分離。使用和實(shí)現(xiàn)分離：使用者通過(guò)規(guī)范使用該類型的數(shù)據(jù)，而不必考慮其實(shí)現(xiàn)細(xì)節(jié)；改變實(shí)現(xiàn)將不影響使用。例如，C++中的整型int就是抽象數(shù)據(jù)類型。它的實(shí)現(xiàn)是隱蔽的，使用者只能通過(guò)整型上定義的一組運(yùn)算對(duì)整型變量執(zhí)行操作。3.抽象數(shù)據(jù)類型27規(guī)范指明“做什么”，實(shí)現(xiàn)解決“怎樣做”。規(guī)范是實(shí)現(xiàn)的準(zhǔn)則和依據(jù)28一個(gè)數(shù)據(jù)結(jié)構(gòu)包含兩個(gè)層次：(1)數(shù)據(jù)結(jié)構(gòu)的規(guī)范（抽象層）：邏輯結(jié)構(gòu)和運(yùn)算的定義組成了數(shù)據(jù)結(jié)構(gòu)的規(guī)范(2)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)（實(shí)現(xiàn)層）：

存儲(chǔ)結(jié)構(gòu)和運(yùn)算算法實(shí)現(xiàn)構(gòu)成了數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)1.3.4數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型

一種數(shù)據(jù)結(jié)構(gòu)被視為一個(gè)抽象數(shù)據(jù)類型。291.4描述數(shù)據(jù)結(jié)構(gòu)和算法30本書(shū)是怎樣描述每種數(shù)據(jù)結(jié)構(gòu)？1.4描述數(shù)據(jù)結(jié)構(gòu)和算法

首先描述數(shù)據(jù)結(jié)構(gòu)的規(guī)范（邏輯結(jié)構(gòu)和運(yùn)算的定義）然后介紹數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)（存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體程序?qū)崿F(xiàn)），31

（1）用格式化的自然語(yǔ)言來(lái)描述數(shù)據(jù)結(jié)構(gòu)的規(guī)范。（2）用一個(gè)C++的抽象模板類描述數(shù)據(jù)結(jié)構(gòu)的規(guī)范。1.4.1數(shù)據(jù)結(jié)構(gòu)的規(guī)范1.4描述數(shù)據(jù)結(jié)構(gòu)和算法對(duì)數(shù)據(jù)結(jié)構(gòu)的規(guī)范的描述：32數(shù)據(jù)結(jié)構(gòu)描述舉例---堆棧1.4.1數(shù)據(jù)結(jié)構(gòu)的規(guī)范33ADT1.1棧抽象數(shù)據(jù)類型ADTStack{Data:

(描述邏輯結(jié)構(gòu))0個(gè)或多個(gè)元素的線性序列（a0，a1，

，an-1)，遵循LIFO原則。

Operations:

(描述運(yùn)算的定義)Create()：創(chuàng)建一個(gè)空棧。

Destroy():撤消一個(gè)棧。

Push(x)：元素x插入棧頂。

Pop()：刪除棧頂元素。

Top(x)：在x中返回棧頂元素。}

（1）用ADT描述數(shù)據(jù)結(jié)構(gòu)——堆棧的例子對(duì)堆棧的規(guī)范的描述：34程序1.1棧的C++模板抽象類template<classT>classStack{public:

virtualvoidPush(Tx)=0;

virtualvoidPop()=0;virtualTTop(T&x)const=0;

…};

除了構(gòu)造函數(shù)，其余成員函數(shù)都是純虛函數(shù)。順序棧類SeqStack是類Stack在順序存儲(chǔ)表示下的一種實(shí)現(xiàn)，它是從抽象類Stack派生出來(lái)的，它可以實(shí)例化。（2）用C++模板抽象類描述數(shù)據(jù)結(jié)構(gòu)35template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}1.4.２實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)堆棧的實(shí)現(xiàn)：361.5算法分析的基本方法內(nèi)容提要

算法及其性能分析算法的空間復(fù)雜度算法的時(shí)間復(fù)雜度漸近時(shí)間復(fù)雜度課堂提要第1章基礎(chǔ)知識(shí)1.1算法和數(shù)據(jù)結(jié)構(gòu)1.2什么是數(shù)據(jù)結(jié)構(gòu)1.3數(shù)據(jù)抽象和抽象數(shù)據(jù)類型

1.4描述數(shù)據(jù)結(jié)構(gòu)和算法1.5算法分析的基本方法371.什么是算法

一個(gè)算法(algorithm)是對(duì)特定問(wèn)題的求解步驟的一種描述，它是指令的有限序列；此外，算法具有下列五個(gè)特征：

(1)輸入算法有零個(gè)或多個(gè)輸入。

(2)輸出算法至少產(chǎn)生一個(gè)輸出

(3)確定性算法的每一條指令都有確切的定義，沒(méi)有二義性。

(4)能行性算法的每一條指令都足夠基本，它們可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。

(5)有窮性算法必須總能在執(zhí)行有限步之后終止。

1.5.1算法及其性能分析

382.算法描述方法算法可以自然語(yǔ)言、流程圖或程序設(shè)計(jì)語(yǔ)言描述。當(dāng)一個(gè)算法用程序設(shè)計(jì)語(yǔ)言描述時(shí)，便成為程序。本書(shū)中，主要使用C++語(yǔ)言描述。3.算法的性能標(biāo)準(zhǔn)正確性：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足預(yù)先規(guī)定的功能和性能要求。(2)簡(jiǎn)明性：一個(gè)算法應(yīng)當(dāng)思路清晰、層次分明、易讀易懂。(3)健壯性：當(dāng)輸入不合法數(shù)據(jù)時(shí)，應(yīng)能做適當(dāng)處理，不至于引起嚴(yán)重后果。(4)效率：有效使用存儲(chǔ)空間和有高的時(shí)間效率。(5)最優(yōu)性：解決同一個(gè)問(wèn)題可能有多種算法，應(yīng)進(jìn)行比較，選擇最佳算法。391.5.2算法的時(shí)間復(fù)雜度

程序步一個(gè)程序步是指在語(yǔ)法上或語(yǔ)義上有意義的程序段，該程序段的執(zhí)行時(shí)間與問(wèn)題實(shí)例的特征無(wú)關(guān)。算法的時(shí)間復(fù)雜度是程序運(yùn)行從開(kāi)始到結(jié)束所需的時(shí)間。40程序1.3求一個(gè)數(shù)組元素的累加之和floatsum(floatlist[],constintn){floattempsum=0.0;for(inti=0;i<n;i++)tempsum+=list[i];returntempsum;}程序步數(shù)為2n+3。411.5.3漸近時(shí)間復(fù)雜度

大O記號(hào)如果存在兩個(gè)正常數(shù)c和n0，使得對(duì)所有的n，n

n0

，有f(n)

cg(n)則有f(n)=O(g(n))。漸近時(shí)間復(fù)雜度使用大O記號(hào)表示的算法的時(shí)間復(fù)雜性，稱為算法的漸近時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度。42漸近時(shí)間復(fù)雜度使用大O記號(hào)表示的算法的時(shí)間復(fù)雜性，稱為算法的漸近時(shí)間復(fù)雜度,簡(jiǎn)稱時(shí)間復(fù)雜度。

大O記號(hào)用以表達(dá)一個(gè)算法運(yùn)行時(shí)間的上界，可用程序步在數(shù)量級(jí)上估計(jì)算法的執(zhí)行時(shí)間。例如，設(shè)

T(n)=3.6n3+2.5n2+2.88.9n3則根據(jù)大O記號(hào)的定義容易證明

T(n)=O(n3)43例如，程序1.2為求一個(gè)數(shù)組元素的累加之和的算法。floatsum(floatlist[],constintn){floattempsum=0.0;//1for(inti=0;i<n;i++)//n+1

tempsum+=list[i];//nreturntempsum;//1}（1）總的程序步數(shù)為2n+3，則漸近時(shí)間復(fù)雜性為O(n)。44floatsum(floatlist[],constintn){floattempsum=0.0;//1for(inti=0;i<n;i++)//n+1

tempsum+=list[i];//nreturntempsum;//1}（2）語(yǔ)句tempsum+=list[i]可認(rèn)為是關(guān)鍵操作，它的執(zhí)行次數(shù)為n次，則漸近時(shí)間復(fù)雜性為O(n)。很多情況下，可以通過(guò)考察一個(gè)算法中的關(guān)鍵操作（關(guān)鍵操作被認(rèn)為是一個(gè)執(zhí)行次數(shù)最多的程序步）的執(zhí)行次數(shù)來(lái)計(jì)算算法的漸近時(shí)間復(fù)雜性。45常見(jiàn)的漸近時(shí)間復(fù)雜性從小到大排列有：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)

例如：若某算法程序的總程序步為4,則其漸近時(shí)間復(fù)雜性為多少？

O(4)是錯(cuò)誤寫(xiě)法。應(yīng)為O(1)46voidMult(inta[n][n],b[n][n],c[n][n],intn){//n

n矩陣a與b相乘得到c。

for(inti=0;i<n;i++)//n+1for(intj=0;j<n;j++)//n(n+1){c[i][j]=0;//n2 for(intk=0;k<n;k++)//n2（n+1)

c[i][j]+=a[i][k]*b[k][j];//n3}}

程序步為：2n3+3n2+2n+1

漸近時(shí)間復(fù)雜度為：T(n)=O(n3)再看一例：471.5.4最好、最壞和平均情況時(shí)間復(fù)雜度

對(duì)于某些算法，即使問(wèn)題實(shí)例的規(guī)模相同，如果輸入的數(shù)據(jù)不同，算法所需的時(shí)間開(kāi)銷也會(huì)不同。比如在有n個(gè)元素的一維數(shù)組上查找一個(gè)給定元素。48算法的空間復(fù)雜度是程序運(yùn)行從開(kāi)始到結(jié)束所需的存儲(chǔ)量。1.5.5算法的空間復(fù)雜度

49程序運(yùn)行所需的存儲(chǔ)空間包括兩部分：（1）固定部分

這部分空間與所處理數(shù)據(jù)的大小和個(gè)數(shù)無(wú)關(guān)，或者稱與問(wèn)題的實(shí)例的特征無(wú)關(guān)。主要包括程序代碼、常量、簡(jiǎn)單變量、定長(zhǎng)成分的結(jié)構(gòu)變量所占的空間。（2）可變部分

這部分空間大小與算法在某次執(zhí)行中處理的特定數(shù)據(jù)的大小和規(guī)模有關(guān)。例如，分別為100個(gè)元素的兩個(gè)數(shù)組相加，與分別為10個(gè)元素的兩個(gè)數(shù)組相加，所需的存儲(chǔ)空間顯然是不同的。內(nèi)容提要1、定義線性表抽象數(shù)據(jù)類型；2、討論線性表的順序存儲(chǔ)表示方法；3、討論單鏈表、循環(huán)鏈表等鏈接存儲(chǔ)表示方法；4、線性表的應(yīng)用實(shí)例——多項(xiàng)式的算術(shù)運(yùn)算。

學(xué)號(hào) 姓名性別

964501 王小紅 女

964502 林悅 女

964503 陳菁菁 女

964504 張可可 男

…

…

…表1-1學(xué)生情況表1.線性表舉例2.1線性表抽象數(shù)據(jù)類型課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項(xiàng)式的算術(shù)運(yùn)算(a)集合結(jié)構(gòu)(b)線性結(jié)構(gòu)(c)樹(shù)形結(jié)構(gòu)(d)圖結(jié)構(gòu)圖1-2四種基本的結(jié)構(gòu)關(guān)系

線性表是n(

0)個(gè)元素a0，a1，…，an-1的有序集合，記為（a0，a1，…，an-1）其中，n是線性表中元素的個(gè)數(shù)，稱為線性表的長(zhǎng)度，n=0時(shí)稱為空表。

設(shè)ai是線性表（a0，a1，…

ai,ai+1，…

an-1）中下標(biāo)為i的元素，i=0,1,…,n-1，則稱ai

是ai+1的直接前驅(qū)元素，ai+1是ai的直接后繼元素。

線性表是動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，它的表長(zhǎng)可以改變。

2.線性表的定義ADT2.1線性表抽象數(shù)據(jù)類型ADTLinearList{Data:零個(gè)或多個(gè)元素的有序集合。(邏輯結(jié)構(gòu))Operations:（運(yùn)算的定義）

Create()：創(chuàng)建一個(gè)空線性表。

Destroy()：撤消一個(gè)線性表。

IsEmpty()：若線性表空，則返回true；否則返回false。

Length()：返回表中元素個(gè)數(shù)。

Find(i,x)：在x中返回表中下標(biāo)為i的元素ai(即表中第i+1個(gè)元素)。如果不存在，則返回false，否則返回true。

Search(x)：返回x在表中的下標(biāo)；若x不在表中，則返回-1。

Insert(i,x)：在元素ai之后插入x。若i=-1，則x插在第一個(gè)元素a0前。插入成功返回true，否則返回false。

Delete(i)：刪除元素ai。刪除成功返回true，否則返回false。

Update(i,x)：將元素ai的值修改為x。修改成功返回true，否則返回

false。

Output(out)：把表送至輸出流。}

3.線性表抽象數(shù)據(jù)類型（描述規(guī)范）4.線性表的C++模板抽象類（描述規(guī)范）程序2.1線性表的C++類template<classT>//使用模板的目的是為了提高通用性classLinearList{public:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;proteced:intn;//線性表的長(zhǎng)度};2.2線性表的順序表示

1.線性表的兩種存儲(chǔ)表示法

(1)

順序表示法

(2)鏈接表示法2.線性表的順序表示法是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中元素。順序表示的線性表程為順序表。存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在機(jī)內(nèi)的映象，包括：元素和關(guān)系。課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項(xiàng)式的算術(shù)運(yùn)算（1）線性表的順序表示法

若已知順序表示的線性表中每個(gè)元素占k個(gè)存儲(chǔ)單元，第一個(gè)元素a0在計(jì)算機(jī)內(nèi)存中的地址是loc(a0)

，則表中任意一個(gè)元素ai在內(nèi)存中的存儲(chǔ)地址loc(ai)為loc(ai)=loc(a0)+i*k

只要給定loc(a0)和k，就可以確定線性表中任意一個(gè)元素的存儲(chǔ)地址，換句話說(shuō)，順序表是一種隨機(jī)存取結(jié)構(gòu)。a0a1…ai

…

an-1

…（2）地址計(jì)算公式：

順序表類SeqList、單鏈表類SingleList和作為基類的線性表類LinearList三者的結(jié)構(gòu)圖2.6SeqList、SingleList和LinearList三者的結(jié)構(gòu)關(guān)系SingleListLinearListSeqListNodefriend繼承3.順序表類程序2.1線性表的C++模板抽象類(規(guī)范)template<classT>classLinearList{public:virtualboolIsEmpty()const=0;virtualintLength()const=0;virtualboolFind(inti,T&x)const=0;virtualintSearch(Tx)const=0;virtualboolInsert(inti,Tx)=0;virtualboolDelete(inti)=0;virtualboolUpdate(inti,Tx)=0;virtualvoidOutput(ostream&out)const=0;proteced:intn;//線性表的長(zhǎng)度，即元素個(gè)數(shù)};template<classT>classSeqList:publicLinearList<T>//SeqList繼承LinearList{public:

SeqList(intmSize);~SeqList(){Delete[]elements;};boolIsEmpty()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;private:intmaxLength;//順序表的最大長(zhǎng)度

T*elements;//動(dòng)態(tài)一維數(shù)組的指針};定義順序表對(duì)象的實(shí)例：SeqList<int>L(5);//定義了一個(gè)長(zhǎng)度為5的順序表對(duì)象Ｌ程序2.2線性表的順序?qū)崿F(xiàn)classSeqList:publicLinearList<T>{public:SeqList(intmSize);……private:intmaxLength;T*elements;

//動(dòng)態(tài)一維數(shù)組的指針}4.動(dòng)態(tài)一維數(shù)組描述順序表a0a1…ai

…

an-1

…01…i…n-1…maxLength-1順序表在一維數(shù)組中的存儲(chǔ)運(yùn)算的實(shí)現(xiàn)(1)構(gòu)造函數(shù)//創(chuàng)建一個(gè)順序表template<classT>SeqList<T>::SeqList(intmSize){maxLength=mSize;elements=newT[maxLength];n=0;}

012…

…

…maxLength-1elements(2)析構(gòu)函數(shù)//撤消一個(gè)順序表template<classT>SeqList<T>::~SeqList(){

delete[]elements;}（1）查找下標(biāo)為i的元素ai

Find(i,x):

在x中返回表中下標(biāo)為i的元素ai(即表中

第i+1個(gè)元素)。如果不存在，則返回

false，否則返回true。x=elements[i];5.在順序存儲(chǔ)表示下實(shí)現(xiàn)線性表上定義的操作a0a1…ai

…

an-1

…01…i…n-1…maxLength-1template<classT>boolSeqList<T>::Find(inti,T&x)const{if(i<0||i>n-1){cout<<"OutofBounds"<<endl;returnfalse;}x=elements[i];returntrue;}

漸近時(shí)間復(fù)雜度：O(1)

…（2）插入操作

Insert(i,x)：在表中下標(biāo)為i的元素ai后插入x。若i=-1，則將新元素x插在最前面。若插入成功，返回true；

后移n-i-1個(gè)元素01…ii+1i+2…n-1…

maxLength-1a0a1…ai

…插入操作an-1x…ai+1…插入操作算法：在表中下標(biāo)為i的元素ai后插入xtemplate<classT>boolSeqList<T>::Insert(inti,Tx){if(i<-1||i>n-1)//{cout<<"OutOfBounds"<<endl;returnfalse;}if(n==maxLength)

{cout<<"OverFlow"<<endl;returnfalse;}for(intj=n-1;j>i;j--)//后移元素

elements[j+1]=elements[j];elements[i+1]=x;n++;returntrue;}…a0a1…ai

…an-1…ai+1…后移n-i-1個(gè)元素分析：設(shè)順序表長(zhǎng)度為n，則在位置i（i=-1,0,…,n-1）后插入一個(gè)元素要移動(dòng)n-i-1個(gè)元素。設(shè)共有n+1個(gè)可插入元素的位置，并設(shè)在各位置處插入元素的概率是相等的，即Pi=1/(n+1)，則平均情況下在表中插入元素需要移動(dòng)元素的個(gè)數(shù)為：漸近時(shí)間復(fù)雜度：O(n)…a0a1…ai

…an-1…ai+1…后移n-i-1個(gè)元素aia0…

ai-1…（3）刪除操作

Delete(i)：刪除下標(biāo)為i元素ai?！耙苙-i-1個(gè)元素

0…i-1ii+1i+2

…n-1

…

maxLength-1刪除操作an-1……刪除它ai+1刪除操作算法：template<classT>boolSeqList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){ cout<<"OutOfBounds"<<endl;returnfalse;}for(intj=i+1;j<n;j++)//前移n-i-1個(gè)元素

elements[j-1]=elements[j];n--;returntrue;}分析:

設(shè)順序表長(zhǎng)度為n,則刪除元素ai（i=0,…,n-1）,要移動(dòng)n-i-1元素。若刪除表中每個(gè)元素的概率是相等的，即Qi=1/n，則平均情況下從表中刪除一個(gè)元素需要移動(dòng)元素的個(gè)數(shù)為：漸近時(shí)間復(fù)雜度：O(n)（4）順序表的應(yīng)用——集合求“并”求集合A和B的并兩集合求并的算法思想是：⑴置i=0；⑵若i小于集合LB的元素個(gè)數(shù)，則做⑶，否則轉(zhuǎn)⑺；⑶取出集合LB中i位置的元素x；⑷若x不在集合LA中，則將其插入集合LA的最后位置；⑸i++；⑹轉(zhuǎn)⑵繼續(xù)⑺結(jié)束。

求集合A和B的并求集合A和B的并例2.1求集合A和B的并A'＝Ａ∪Ｂ分析：集合可以看成是線性表，用順序表LA和LB分別表示集合A和B，“并”的結(jié)果放在LA中。

用順序表類SeqList實(shí)現(xiàn)集合“并”算法的程序，存入頭文件seqlistu.h中。#include"seqlist.h"template<classT>voidUnion(SeqList<T>&LA,SeqList<T>LB){Tx;for(inti=0;i<LB.Length();i++){LB.Find(i,x);//取出集合LB中下標(biāo)為i的元素放入x中

if(LA.Search(x)==-1)//如果集合LA中不存在x,則將

LA.Insert(LA.Length()-1,x);//其插入集合LA中

}}#include"seqlistu.h"constintSIZE=20;voidmain(){SeqList<int>LA(SIZE);//定義順序表對(duì)象LA，表示集合A

SeqList<int>LB(SIZE);//定義順序表對(duì)象LB，表示集合B

for(inti=0;i<5;i++)//插入元素0~4，構(gòu)造集合LA={0,1,2,3,4}

LA.Insert(i-1,i);

for(i=5;i<10;i++)//插入5~9，構(gòu)造集合B={5,6,7,8,9}

LB.Insert(i-6,i);

LB.Insert(-1,0);//LB中插入0，LB={0,5,6,7,8,9}

LB.Insert(3,2);//LB中插入2，LB={0,5,6,7,2,8,9}

LB.Insert(LB.Length()-1,4);//LB中插入4，LB={0,5,6,7,2,8,9,4}

Union(LA,LB);//兩集合并，結(jié)果放入LA中

LA.Output(cout);//輸出最終結(jié)果LA={0,1,2,3,4,5,6,7,8,9}}6.線性表的順序存儲(chǔ)表示的優(yōu)缺點(diǎn)：（1）優(yōu)點(diǎn)：隨機(jī)存??；存儲(chǔ)空間利用率高。（2）缺點(diǎn)：插入、刪除效率低；必須按事先估計(jì)的最大元素個(gè)數(shù)分配連續(xù)的存儲(chǔ)空間，難以臨時(shí)擴(kuò)大。2.3線性表的鏈接表示

1.線性表的鏈接存儲(chǔ)表示法

(1)

單鏈表

(2)帶表頭結(jié)點(diǎn)的鏈表

(3)循環(huán)鏈表

(4)雙向鏈表課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示

2.3.1單鏈表

2.3.2帶表頭結(jié)點(diǎn)的單鏈表

2.3.3循環(huán)鏈表

2.3.4雙向鏈表2.4多項(xiàng)式的算術(shù)運(yùn)算2.3.1單鏈表

單鏈表存儲(chǔ)表示法每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，稱為單鏈表(1)

單鏈表的結(jié)點(diǎn)結(jié)構(gòu)elementlinka0a1a2an-1…first∧課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示

2.3.1單鏈表

2.3.2帶表頭結(jié)點(diǎn)的單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向鏈表2.4多項(xiàng)式的算術(shù)運(yùn)算數(shù)據(jù)地址a0a1a3a4a2單鏈表在內(nèi)存中的示意圖(2)單鏈表結(jié)構(gòu)a0a1a2an-1…first∧非空單鏈表first

空單鏈表注意：●頭結(jié)點(diǎn)：第一個(gè)結(jié)點(diǎn)●單鏈表頭指針first不能少,指向頭結(jié)點(diǎn)（第一個(gè)結(jié)點(diǎn)）●最后一個(gè)結(jié)點(diǎn)的指針域?yàn)?/p>

●邏輯上相鄰的元素在物理上不一定相鄰

●不能出現(xiàn)“斷鏈”現(xiàn)象

NULLfirst頭指針綠色為結(jié)點(diǎn)的指針域first∧（a0，a1，a2，a3,a4）2.單鏈表結(jié)點(diǎn)類程序2.3線性表的單鏈表實(shí)現(xiàn)#include“l(fā)inearlist.h”template<classT>classSingleList;template<classT>classNode{private:Telement;

Node<T>*link;

friendclassSingleList<T>;};elementlink數(shù)據(jù)地址3.單鏈表類程序2.3線性表的單鏈表實(shí)現(xiàn)template<classT>classSingleList:publicLinearList<T>{public:

SingleList(){first=NULL;n=0;}//構(gòu)造函數(shù)

~SingleList();boolIsEmpty()const;intLength()const;boolFind(inti,T&x)const;intSearch(Tx)const;boolInsert(inti,Tx);boolDelete(inti);boolUpdate(inti,Tx);voidOutput(ostream&out)const;private:

Node<T>*first;};SingleListLinearListNodefriend繼承析構(gòu)函數(shù)template<classT>SingleList<T>::~SingleList(){Node<T>*p;while(first){p=first->link;deletefirst;first=p;}}a0a1firsta2∧單鏈表pp=∧first=∧如何閱讀4.在單鏈表上實(shí)現(xiàn)線性表規(guī)范中所定義的操作（1）查找元素ai（2）插入操作（3）刪除操作（1）查找元素aia0a1a2an-1…first∧單鏈表

由于鏈表失去了隨機(jī)查找元素的特性,所以必須從頭指針開(kāi)始沿鏈逐個(gè)計(jì)數(shù)查找。查找元素ai的算法

template<classT>boolSingleList<T>::Find(inti,T&x)const{if(i<0||i>n-1){cout<<"OutOfBounds";returnfalse;}Node<T>*p=first;for(intj=0;j<i;j++)p=p->link;x=p->element;returntrue;}漸近時(shí)間復(fù)雜度：O(n)a0a1a2an-1…first∧單鏈表p（2）插入操作在給定元素ai之后插入值為x的元素。(a0,a1,...,ai,ai+1,...,an-1)即在此處插入x插入算法步驟為：①生成數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，q指向新結(jié)點(diǎn);②從first開(kāi)始找元素ai，即第i+1個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)；③將q插入p之后。④表長(zhǎng)加1。q插入時(shí)只要修改二個(gè)指針：

q->link=p->linkp->link=q能否對(duì)調(diào)上述2語(yǔ)句的執(zhí)行順序？

不能，會(huì)“斷鏈”現(xiàn)象aiai+1xpaiai+1xqp“斷鏈”現(xiàn)象i>-1時(shí)，將q插入p之后:a0a1a2an-1…first∧單鏈表插入的一般情況firsta0a1a2an-1…∧qx插入時(shí)只要修改二個(gè)指針：

q->link=first；

first=q;插入在頭結(jié)點(diǎn)之前的特殊情況i==1時(shí)，插入在頭結(jié)點(diǎn)之前template<classT>boolSingleList<T>::Insert(inti,Tx){if(i<-1||i>n-1){cout<<"OutOfBounds";returnfalse;}Node<T>*q=newNode<T>;q->element=x;//生成新結(jié)點(diǎn)qNode<T>*p=first;for(intj=0;j<i;j++)p=p->link;//找元素aiif(i>-1)

{

q->link=p->link；p->link=q;

//在p之后插入q}else{q->link=first；first=q;

//插在第一個(gè)元素之前

}n++;

//表長(zhǎng)加１

returntrue;}漸近時(shí)間復(fù)雜度：O(n)a0a1a2an-1…first∧（3）刪除操作刪除元素ai。(a0,a1,...,ai...,an-1)即刪除該元素刪除算法步驟為：①?gòu)膄irst開(kāi)始找第i+1個(gè)結(jié)點(diǎn)，p指向該結(jié)點(diǎn)，q指向p之前驅(qū)結(jié)點(diǎn);②從單鏈表中刪除p；③釋放p之空間；④表長(zhǎng)減1。aiai+1ai-1qp刪除時(shí)只要修改一個(gè)指針：

q->link=p->link刪除p:刪除結(jié)點(diǎn)的一般情況(i>0)firsta0a1a2an-1…∧刪除時(shí)只要修改一個(gè)指針：

first=first->link刪除頭結(jié)點(diǎn)的特殊情況(i==0)template<classT>boolSingleList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){cout<<"OutOfBounds"<<endl;returnfalse；}Node<T>*p=first,*q=first;for(intj=0;j<i-1;j++)q=q->link;//q指向要?jiǎng)h除結(jié)點(diǎn)的前一結(jié)點(diǎn)

if(i==0)first=first->link;

//刪除的是頭結(jié)點(diǎn)

else{p=q->link;

//從單鏈表中刪除pq->link=p->link;}deletep;n--;

//表長(zhǎng)減一

returntrue;}漸近時(shí)間復(fù)雜度：O(n)

aiai+1ai-1qp5.單鏈表的應(yīng)用——集合求“交”求集合A和B的并兩集合求交的算法思想是：⑴置i=0；⑵若i小于集合LA中當(dāng)前元素的個(gè)數(shù)，則做⑶，否則轉(zhuǎn)⑹；⑶取出集合LA中i位置的元素x；⑷若x不在集合LB中，則將其從集合LA中刪除，否則i++；⑸轉(zhuǎn)⑵繼續(xù);⑹結(jié)束。

求集合A和B的并例2.2求集合A和B的交A'＝Ａ∩Ｂ分析：集合可以看成是線性表，用單鏈表LA和LB分別表示集合A和B，“交”的結(jié)果放在LA中。#include"singlelist.h"template<classT>voidIntersection(SingleList<T>&LA,SingleList<T>&LB){Tx;inti=0;while(i<LA.Length()){LA.Find(i,x);//取出集合LA中i位置的元素xif(LB.Search(x)==-1)LA.Delete(i);//若x不在集合LB中，則將其從集合LA中刪除

elsei++;//否則i++}}2.3.2帶表頭結(jié)點(diǎn)的單鏈表

上一節(jié)介紹的單鏈表在做插入和刪除運(yùn)算時(shí)，要考慮一般情況和特殊情況，用帶表頭結(jié)點(diǎn)的單鏈表可以簡(jiǎn)化上述兩種算法。課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示

2.3.1單鏈表

2.3.2帶表頭結(jié)點(diǎn)的單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向鏈表2.4多項(xiàng)式的算術(shù)運(yùn)算1.帶表頭結(jié)點(diǎn)的單鏈表(a0,a1,...,ai...,an-1)

在原單鏈表中增加一個(gè)結(jié)點(diǎn)，但它的element域中不存放線性表中的任何元素，稱該結(jié)點(diǎn)為表頭結(jié)點(diǎn)。firsta0a1a2an-1…∧非空表first∧空表2.帶表頭結(jié)點(diǎn)單鏈表HeaderList的構(gòu)造、插入和刪除（1）構(gòu)造函數(shù)SingleList<T>::SingleList()//單鏈表構(gòu)造函數(shù){first=NULL;n=0;}HeaderList<T>::HeaderList()//帶表頭結(jié)點(diǎn)單鏈表構(gòu)造函數(shù){Node<T>*first=newNode<T>;first->link=NULL;n=0;}first∧空表first

空單鏈表（2）插入操作template<classT>boolHeaderList<T>::Insert(inti,Tx){if(i<-1||i>n-1){cout<<"OutOfBounds“<<endl;returnfalse;}Node<T>*p=first;for(intj=0;j<=i;j++)p=p->link;Node<T>*q=newNode<T>;q->element=x;

q->link=p->link;p->link=q;n++;returntrue;}a0a1a2an-1…first∧p

（3）刪除操作template<classT>boolHeaderList<T>::Delete(inti){if(!n){cout<<"UnderFlow"<<endl;returnfalse;}if(i<0||i>n-1){cout<<"OutOfBounds"<<endl;returnfalse;}Node<T>*q=first,*p;for(intj=0;j<i;j++)q=q->link;p=q->link;q->link=p->link;deletep;n--;returntrue;}q

a0a1a2an-1…first∧p

例如刪除a22.3.3單循環(huán)鏈表

1.單循環(huán)鏈表

單循環(huán)鏈表可以從表中任一結(jié)點(diǎn)出發(fā)訪問(wèn)表中所有結(jié)點(diǎn)。課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示

2.3.1單鏈表

2.3.2帶表頭結(jié)點(diǎn)的單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向鏈表2.4多項(xiàng)式的算術(shù)運(yùn)算帶表頭結(jié)點(diǎn)的單循環(huán)鏈表不帶表頭結(jié)點(diǎn)的單循環(huán)鏈表a0a1a2an-1…first空表first非空表a0a1a2an-1…first非空表空表first∧2.3.4雙向鏈表

1.雙向鏈表(1)

雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)lLinkelementrLink課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示

2.3.1單鏈表

2.3.2帶表頭結(jié)點(diǎn)的單鏈表

2.3.3單循環(huán)鏈表

2.3.4雙向鏈表2.4多項(xiàng)式的算術(shù)運(yùn)算(2)帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表2.3線性表的鏈接表示2.3.3雙向鏈表3.雙向鏈表的插入插入操作的核心步驟：

(1)DNode<T>*q=newDNode<T>;q->element=x;(2)①q->llink=p->llink;

②q->rlink=p;

③p->llink->rlink=q;④p->llink=q;

能否顛倒順序？③p->llink->rlink=q;①q->llink=p->llink;②q->rlink=p;④p->llink=q;xqp

插入操作：在p所指示的結(jié)點(diǎn)前插入值為x新結(jié)點(diǎn)2.3線性表的鏈接表示4.雙向鏈表的刪除刪除操作的核心步驟是：(1)①p->llink->rlink=p->rlink;

②p->rlink->llink=p->llink;(2)deletep;能否顛倒順序？p

刪除操作:刪除p所指示的結(jié)點(diǎn)2.4多項(xiàng)式的算術(shù)運(yùn)算

線性表是一種最簡(jiǎn)單、最基本，也是最常用的數(shù)據(jù)結(jié)構(gòu)，其用途十分廣泛。作為線性表應(yīng)用的一個(gè)例子，下面討論一元整系數(shù)多項(xiàng)式的算術(shù)運(yùn)算。從該例中，要學(xué)會(huì)如何分析元素間的關(guān)系、結(jié)構(gòu)的描述、存儲(chǔ)方式的選擇，如何描述和實(shí)現(xiàn)算法。課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項(xiàng)式的算術(shù)運(yùn)算一元整系數(shù)多項(xiàng)式

p(x)=3x14-8x8+6x2+2

要求:(1)按降冪排列

(2)做q(x)

q(x)+p(x)1.數(shù)據(jù)元素該多項(xiàng)式是由一項(xiàng)一項(xiàng)組成的。我們忽略掉各項(xiàng)具體數(shù)字的細(xì)節(jié)，即每一項(xiàng)就是由系數(shù)(coef)和指數(shù)(exp)組成的：coef·xexp。每一項(xiàng)就是一個(gè)要處理的數(shù)據(jù)元素，即

(coef,exp)

。分析:2.元素間的邏輯關(guān)系由于多項(xiàng)式按降冪排列，因此每一項(xiàng)都有一個(gè)指數(shù)比它高的項(xiàng)，有一個(gè)比它低的項(xiàng)，除了最高項(xiàng)沒(méi)有比它高的項(xiàng)，最后一項(xiàng)沒(méi)有比踏低的項(xiàng)外。這樣，多項(xiàng)式的每一項(xiàng)就組成了一個(gè)線性表，線性表中的每個(gè)數(shù)據(jù)元素是多項(xiàng)式的一項(xiàng)(coef,exp)。因此，一元整系數(shù)多項(xiàng)式可以視為線性表。3.存儲(chǔ)表示(2,10)(4,8)(-6,2)１.用順序存儲(chǔ)：q(x)線性表有順序和鏈接存儲(chǔ)：q(x)=2x10+4x8-6x2，p(x)=3x14-8x8+6x2+2做q(x)+p(x)q(x)，結(jié)果為：q(x)=3x14+2x10-4x8+2(3,14)

(-8,8)(6,2)(2,0)p(x)(3,14)

(2,10)(-4,8)(2,0)結(jié)果q(x)

從結(jié)果中可以發(fā)現(xiàn)，在q(x)上做了插入和刪除運(yùn)算，因此不宜采用順序存儲(chǔ)。p(x)=3x14-8x8+6x2+2

２.用帶表頭結(jié)點(diǎn)的單循環(huán)鏈表表示一元多項(xiàng)式多項(xiàng)式的項(xiàng)coef

xexp結(jié)點(diǎn)結(jié)構(gòu)：coefexplink314px-8820620-12.4.1項(xiàng)結(jié)點(diǎn)的C++類

(1)項(xiàng)結(jié)點(diǎn)的C++類：

classTerm(2)多項(xiàng)式的C++類：

classPolynominal(3)類Polynominal是類Term的友元類。課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項(xiàng)式的算術(shù)運(yùn)算

2.4.1項(xiàng)結(jié)點(diǎn)的C++類

2.4.2多項(xiàng)式的C++類

2.4.3多項(xiàng)式的實(shí)現(xiàn)程序2.6多項(xiàng)式項(xiàng)結(jié)點(diǎn)的C++類classPolynominal；classTerm{public:Term(intc,inte);Term(intc,inte,Term*nxt);Term*InsertAfter(intc,inte);//在this指

//針指示的項(xiàng)后插入新項(xiàng)

private:intcoef;intexp;Term*link;friendostream&operator<<(ostream&,constTerm&);//輸出項(xiàng)friendclassPolynominal;};項(xiàng)結(jié)點(diǎn)類的兩種構(gòu)造函數(shù)Term::Term(intc,inte):coef(c),exp(e){link=0;}Term::Term(intc,inte,Term*nxt):coef(c),exp(e){link=nxt;}項(xiàng)結(jié)點(diǎn)類的InsertAfter函數(shù)Term*Term::InsertAfter(intc,inte){//函數(shù)功能：在調(diào)用該函數(shù)的項(xiàng)結(jié)點(diǎn)對(duì)象后插入新的結(jié)點(diǎn)

link=newTerm(c,e,link);returnlink;}關(guān)于項(xiàng)結(jié)點(diǎn)類的InsertAfter函數(shù)的執(zhí)行過(guò)程q210-1q1qx申請(qǐng)新項(xiàng)結(jié)點(diǎn)存儲(chǔ)單元新項(xiàng)結(jié)點(diǎn)例如：執(zhí)行q1->InsertAfter(3,14)//結(jié)點(diǎn)q1后面插入新結(jié)點(diǎn)Term*Term::InsertAfter(intc,inte){link=;returnlink;}3

14newTerm(c,e,link)先做new

這里要搞清楚一個(gè)問(wèn)題：上述函數(shù)中，link是指哪個(gè)結(jié)點(diǎn)的指針域？

q1的指針域！存放的是指向q1后繼的q的地址!關(guān)于項(xiàng)結(jié)點(diǎn)類的InsertAfter函數(shù)的執(zhí)行過(guò)程q210-1q1qx新項(xiàng)結(jié)點(diǎn)例如：執(zhí)行q1->InsertAfter(3,14)Term*Term::InsertAfter(intc,inte){link=;returnlink;}3

14newTerm(c,e,link)再做Term(3,14,q)314q最后執(zhí)行賦值運(yùn)算=新項(xiàng)結(jié)點(diǎn)的地址賦值給q1的指針域重載輸出操作符<<ostream&operator<<(ostream&out,constTerm&val){//函數(shù)功能：輸出項(xiàng)結(jié)點(diǎn)

if(val.coef==0)returnout;out<<val.coef;switch(val.exp){case0:break;case1:out<<"X";break;default:out<<"X^"<<val.exp;}returnout;}

例如：-4x2

將以-4x^2的形式輸出2.4.2多項(xiàng)式的C++類

1.多項(xiàng)式類Polynominal的成員函數(shù)(1)AddTerms

函數(shù):

通過(guò)輸入流in，輸入多項(xiàng)式的各項(xiàng)(c,e)構(gòu)造一個(gè)多項(xiàng)式。(2)Output

函數(shù):

將多項(xiàng)式的每一項(xiàng)按降冪方式送輸出流。(3)PolyAdd

函數(shù):

實(shí)現(xiàn)將多項(xiàng)式r加到指針this指示的多項(xiàng)式上。課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項(xiàng)式的算術(shù)運(yùn)算

2.4.1項(xiàng)結(jié)點(diǎn)的C++類

2.4.2多項(xiàng)式的C++類

2.4.3多項(xiàng)式的實(shí)現(xiàn)程序2.7多項(xiàng)式的C++類classPolynominal{public:Polynominal();~Polynominal();voidAddTerms(istream&in）；

voidOutput(ostream&out)const；

voidPolyAdd(Polynominal&r）；

private:Term*theList;//頭指針

friendostream&operator<<(ostream&,constPolynominal&);friendistream&operator>>(istream&,Polynominal&);friendPolynominaloperator+(

Polynominal&,Polynominal&);}2.4.3多項(xiàng)式類的實(shí)現(xiàn)

構(gòu)造函數(shù)Polynominal::Polynominal(){theList=newTerm(0,-1); theList->link=theList;}theList0-1課堂提要第2章線性表2.1線性表ADT2.2線性表的順序表示2.3線性表的鏈接表示2.4多項(xiàng)式的算術(shù)運(yùn)算

2.4.1項(xiàng)結(jié)點(diǎn)的C++類

2.4.2多項(xiàng)式的C++類

2.4.3多項(xiàng)式的實(shí)現(xiàn)2.多項(xiàng)式輸入、輸出程序2.9多項(xiàng)式類的輸入和輸出函數(shù)AddTerms函數(shù)從輸入流in通過(guò)輸入各項(xiàng)來(lái)構(gòu)造多項(xiàng)式。voidPolynominal::AddTerms(istream&in){Term*q=theList;intc,e;for(;;){cout<<"Inputaterm(coef,exp):\n"<<endl;in>>c>>e;if(e<0)break;

q=q->InsertAfter(c,e);}}-88theList0-1q-88theList3140-1qp(x)=3x14-8x8+6x2+2

輸入多項(xiàng)式的項(xiàng)，建立多項(xiàng)式:

62(3,14)

20(-8,8)(6,2)(2,0)Output函數(shù)將多項(xiàng)式按降冪方式送輸出流。voidPolynominal::Output(ostream&out)const{//依次輸出多項(xiàng)式的每一項(xiàng)

intfirst=1;Term*p=theList->link;cout<<"Thepolynominalis:\n"<<endl;for(;p!=theList;p=p->link){if(!first&&(p->coef>0))out<<"+";first=0;out<<*p;//調(diào)用Term類上重載的“<<”操作。

}cout<<"\n"<<endl;}314px-8820620-1pq1314px-8820620-1q210qx48-620-1314qx21020-480-1一元整系數(shù)多項(xiàng)式相加3.多項(xiàng)式相加——實(shí)現(xiàn)q(x)

q(x)+p(x)3.多項(xiàng)式相加——實(shí)現(xiàn)q(x)

q(x)+p(x)

設(shè)p和q分別指向多項(xiàng)式p(x)和q(x)的當(dāng)前正進(jìn)行比較的項(xiàng)，初始時(shí)分別指向兩多項(xiàng)式中最高冪次的項(xiàng)。q1指向q的前驅(qū)結(jié)點(diǎn)。對(duì)p(x)進(jìn)行遍歷，根據(jù)指針p、q的exp域的大小情