1、數(shù)據(jù)結(jié)構(gòu),第一章緒論 第二章線性表 第三章數(shù)組和廣義表 第四章棧和隊(duì)列 第五章串 第六章樹 第七章圖 第八章查找 第九章排序,第一章 緒論,本章學(xué)習(xí)要求： 了解數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容。 理解掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語。 了解數(shù)據(jù)元素間的結(jié)構(gòu)關(guān)系。 理解掌握算法及算法的描述,1.1 數(shù)據(jù)結(jié)構(gòu)的發(fā)展,1.1.1數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史 最早對(duì)這一發(fā)展作出杰出貢獻(xiàn)的是D.E.Kunth教授和C.A.R.Hoare(霍爾)。D.E.Kunth的計(jì)算機(jī)程序設(shè)計(jì)技巧和霍爾的數(shù)據(jù)結(jié)構(gòu)札記對(duì)數(shù)據(jù)結(jié)構(gòu)這門學(xué)科的發(fā)展作出了重要貢獻(xiàn)。隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，到20世紀(jì)80年代初期，數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)研究日臻成熟，已經(jīng)成為一門

2、完整的學(xué)科。,1.1.2數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容,用計(jì)算機(jī)解決一個(gè)具體的問題時(shí)，大致需要經(jīng)過以下幾個(gè)步聚： （1）分析問題，確定數(shù)據(jù)模型。 （2）設(shè)計(jì)相應(yīng)的算法。 （3）編寫程序，運(yùn)行并調(diào)試程序直至得到正確的結(jié)果。,例1.1 學(xué)生成績(jī)表,一個(gè)數(shù)據(jù)元素,數(shù)據(jù)項(xiàng),例1.2組織示意圖,例1.3七橋問題,Euler在1736年訪問俄羅斯的哥尼斯堡時(shí)，他發(fā)現(xiàn)當(dāng)?shù)氐木用裾龔氖乱豁?xiàng)非常有趣的消遣活動(dòng)。哥尼斯堡城中有一條名叫勒格爾的河流橫經(jīng)其中，在河上建有七座橋如圖所示：,這項(xiàng)有趣的消遣活動(dòng)是在星期六作一次走過所有七座橋的散步，每座橋只能經(jīng)過一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn)。,設(shè)四塊陸地分別為A、B、C、D，Eul

3、er把每一塊陸地考慮成一個(gè)點(diǎn)，連接兩塊陸地的橋以線表示，便得到如下的圖形：,后來推論出此種走法是不可能的。 他的論點(diǎn)是這樣的，除了起點(diǎn)以外，每一次當(dāng)一個(gè)人由一座橋進(jìn)入一塊陸地（或點(diǎn)）時(shí)，他（或她）同時(shí)也由另一座橋離開此點(diǎn)。即每個(gè)點(diǎn)如果有進(jìn)去的邊就必須有出來的邊，因此每一個(gè)陸地與其他陸地連接的橋數(shù)必為偶數(shù)。七橋所成的圖形中，沒有一點(diǎn)含有偶數(shù)條數(shù)，因此上述的任務(wù)是不可能實(shí)現(xiàn)的。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語,數(shù)據(jù)（data）：是指在計(jì)算機(jī)科學(xué)中能夠被計(jì)算機(jī)輸入、存儲(chǔ)、處理和輸出的一切信息，是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。包括數(shù)字、英文、漢字、以及表示圖形、聲音、光和電的符號(hào)等。 數(shù)

4、據(jù)項(xiàng)(Data Item)：是數(shù)據(jù)的最小單位，有時(shí)也稱為域（field），即數(shù)據(jù)表中的字段。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的不可分割的最小標(biāo)識(shí)單位。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語,數(shù)據(jù)元素(Data Element)：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)信息處理中通常作為一個(gè)整體來考慮。一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄。 數(shù)據(jù)對(duì)象(Data Object)：具有性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。如整數(shù)數(shù)據(jù)對(duì)象是集合N= 0, 1, 2, 。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語,數(shù)據(jù)類型：是一個(gè)值的集合和定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合

5、：值的集合和操作集合。其中值的集合定義了該類型數(shù)據(jù)元素的取值，操作集合定義了該類型數(shù)據(jù)允許參加的運(yùn)算，例如C語言中的int類型，取值范圍是-3276832767，主要的運(yùn)算為加、減、乘、除、取模、乘方等。 數(shù)據(jù)結(jié)構(gòu)(Data Structure)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，描述了一組數(shù)據(jù)元素及元素間的相互關(guān)系。數(shù)據(jù)元素間的關(guān)系包括三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作集合。,1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語,數(shù)據(jù)類型：是一個(gè)值的集合和定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合：值的集合和操作集合。其中值的集合定義了該類型數(shù)據(jù)元素的取值，操作集合定義了該類型數(shù)據(jù)允許參加的運(yùn)算，

6、例如C語言中的int類型，取值范圍是-3276832767，主要的運(yùn)算為加、減、乘、除、取模、乘方等。 數(shù)據(jù)結(jié)構(gòu)(Data Structure)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，描述了一組數(shù)據(jù)元素及元素間的相互關(guān)系。數(shù)據(jù)元素間的關(guān)系包括三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作集合。,1.3 數(shù)據(jù)的邏輯結(jié)構(gòu),邏輯結(jié)構(gòu)（logical structure）：是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶使用需要建立起來的數(shù)據(jù)組織形式，是獨(dú)立于計(jì)算機(jī)的。 根據(jù)數(shù)據(jù)元素之間的不同關(guān)系，有以下四種基本邏輯結(jié)構(gòu)： （1）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對(duì)一的關(guān)系。在線性結(jié)構(gòu)中，有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，除了開始結(jié)

7、點(diǎn)和終端結(jié)點(diǎn)，其余結(jié)點(diǎn)都有且僅有一個(gè)直接前趨和一個(gè)直接后繼。,1.3 數(shù)據(jù)的邏輯結(jié)構(gòu),（2）樹狀結(jié)構(gòu)或?qū)哟谓Y(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。比如部門之間的隸屬關(guān)系、人類社會(huì)的父子關(guān)系、上下級(jí)關(guān)系等。在樹形結(jié)構(gòu)中，除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有唯一直接前趨，所有的結(jié)點(diǎn)都可以有0個(gè)或多個(gè)直接后繼。,1.3 數(shù)據(jù)的邏輯結(jié)構(gòu),（3）圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系。在圖狀結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都可以有多個(gè)直接前趨和多個(gè)直接后繼。,（4）集合結(jié)構(gòu)：數(shù)據(jù)元素間除了同屬于一個(gè)集合的關(guān)系外，無任何其他關(guān)系。,1.3 數(shù)據(jù)的邏輯結(jié)構(gòu),一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)G可以用二元組來表示： G=（D，R

8、） 其中： D是數(shù)據(jù)元素的集合； R是D上所有數(shù)據(jù)元素之間關(guān)系的集合（表示各元素的前趨、后繼關(guān)系）。R中的關(guān)系圓括號(hào)表示是雙向的，尖括號(hào)表示是單向的。,例1-4一種數(shù)據(jù)結(jié)構(gòu)Graph=（D，R） 其中： D=A，B，C，D，E R=r r=(A,B),(A,C),(B,C),(B,D), (B,E),(C,E) r中的(A,B)表示頂點(diǎn)A到頂點(diǎn)B之間的邊是雙向的，上述的結(jié)構(gòu)關(guān)系如圖1-5所示。,1.4數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(storage structure)又稱物理結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)形式（或稱映象）。 （1）順序存儲(chǔ)結(jié)構(gòu)：借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)

9、據(jù)元素之間的邏輯關(guān)系，可用一維數(shù)組描述。 （2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系?？捎弥羔樏枋觯瑪?shù)據(jù)元素不一定存在地址的存儲(chǔ)單元，存儲(chǔ)處理的靈活性較大。 （3）索引存儲(chǔ)：是在原有存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上，附加建立一個(gè)索引表，索引表中的每一項(xiàng)都由關(guān)鍵字和地址組成。采取索引存儲(chǔ)的主要作用是為了提高數(shù)據(jù)的檢索速度。 （4）散列存儲(chǔ)：是通過構(gòu)造散列函數(shù)來確定數(shù)據(jù)存儲(chǔ)地址或查找地址的。,1.5算法和算法的描述,1.5.1 什么是算法 1算法的的概念 算法是為了解決某類問題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列，是對(duì)解題過程的準(zhǔn)確而完整的描述。 2算法的特性 一個(gè)算法一般具有以下特性

10、： （1）輸入：一個(gè)算法必須有0個(gè)或多個(gè)輸入。這些輸入取自于特定的對(duì)象的集合。它們可以使用輸入語句由外部提供，也可以使用賦值語句在算法內(nèi)給定。 （2）確定性：算法的每一步都應(yīng)確切地、無歧義地定義。對(duì)于每一種情況，需要執(zhí)行的動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。 （3）有窮性：一個(gè)算法無論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。,1.5算法和算法的描述,（4）可行性：一個(gè)算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。 （5）輸出：一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。 3.算法與程序的區(qū)別 （1）算法代表了對(duì)問題的求解過程，而程序則是算法在計(jì)算機(jī)上的實(shí)現(xiàn)。算

11、法用特寫的程序設(shè)計(jì)語言來描述，就成了程序。 （2）程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。 （3）一個(gè)算法必須在有窮步之后結(jié)束，一個(gè)程序不一定滿足有窮性。,（4）可行性：一個(gè)算法是能行的，即算法中描述的操作都是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。 （5）輸出：一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。 3.算法與程序的區(qū)別 （1）算法代表了對(duì)問題的求解過程，而程序則是算法在計(jì)算機(jī)上的實(shí)現(xiàn)。算法用特寫的程序設(shè)計(jì)語言來描述，就成了程序。 （2）程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制。 （3）一個(gè)算法必須在有窮步之后結(jié)束，一個(gè)程序不一定滿足有

12、窮性。,1.5.2 算法設(shè)計(jì)的要求,通常設(shè)計(jì)一個(gè)“好”的算法應(yīng)考慮達(dá)到如下目標(biāo)： （1）正確性：在合理的數(shù)據(jù)輸入下，能在有限的運(yùn)行時(shí)間內(nèi)得到正確的結(jié)果。 （2）可讀性：程序可讀性好，有助于人對(duì)算法的理解。 （3）健壯性：當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)恰當(dāng)?shù)刈鞒龇从郴蜻M(jìn)行相應(yīng)處理，而不是產(chǎn)生莫名奇妙的輸出結(jié)果。并且，處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更高的抽象層次上進(jìn)行處理。 （4）高效性：對(duì)同一個(gè)問題，執(zhí)行時(shí)間越短，算法的效率越高。 （5）低存儲(chǔ)量：完成相同的功能，執(zhí)行算法所占用的存儲(chǔ)空間應(yīng)盡可能的少。,1.5.4 算法的描述,算法可以用流程圖、自然

13、語言、計(jì)算機(jī)程序語言或其他語言來描述，但描述必須精確地說明計(jì)算過程。 在本書中算法是以函數(shù)形式描述，描述如下： 類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說明 語句序列,1.5.4 算法效率的評(píng)價(jià),算法可以用流程圖、自然語言、計(jì)算機(jī)程序語言或其他語言來描述，但描述必須精確地說明計(jì)算過程。 在本書中算法是以函數(shù)形式描述，描述如下： 類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說明 語句序列 1時(shí)間復(fù)雜度（Time Complexity） 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)(n)，算法的時(shí)間量度記作： T（n）=O(n) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和(n)

14、的增長(zhǎng)率相同，稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。,1.5.4 算法效率的評(píng)價(jià),算法可以用流程圖、自然語言、計(jì)算機(jī)程序語言或其他語言來描述，但描述必須精確地說明計(jì)算過程。 在本書中算法是以函數(shù)形式描述，描述如下： 類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說明 語句序列 1時(shí)間復(fù)雜度（Time Complexity） 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)(n)，算法的時(shí)間量度記作： T（n）=O(n) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和(n)的增長(zhǎng)率相同，稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。,1.5.4 算法效率的評(píng)價(jià),算法可以用流程圖、自然語

15、言、計(jì)算機(jī)程序語言或其他語言來描述，但描述必須精確地說明計(jì)算過程。 在本書中算法是以函數(shù)形式描述，描述如下： 類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說明 語句序列 1時(shí)間復(fù)雜度（Time Complexity） 一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)(n)，算法的時(shí)間量度記作： T（n）=O(n) 它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和(n)的增長(zhǎng)率相同，稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。,1.5.4 算法效率的評(píng)價(jià),例1-5在下列的三個(gè)程序中 (a) x=0 (b) for (i=1;i=n;i+) x=x+1 (c) for (i=1;i=n;i

16、+) for(j=1;j=n;j+) X=X+i*j 上述三個(gè)語句的頻度分別為1，n,n2 2.空間復(fù)雜度（Space ComPlexity） 一個(gè)程序的空間復(fù)雜度是指程序運(yùn)行從開始到結(jié)束所需要的存儲(chǔ)空間。包括算法本身所占用的存儲(chǔ)空間、輸入數(shù)據(jù)占用的存儲(chǔ)空間以及算法在運(yùn)行過程中的工作單元和實(shí)現(xiàn)算法所需輔助空間。,第二章 線性表,本章學(xué)習(xí)要求： 系統(tǒng)學(xué)習(xí)線性表的存儲(chǔ)結(jié)構(gòu)及其基本操作。 理解線性表的邏輯結(jié)構(gòu) 理解掌握線性表的順序存儲(chǔ)結(jié)構(gòu)及操作 理解掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作,2.1線性表邏輯結(jié)構(gòu),2.1.1 線性表的定義 1線性表的定義 線性表（Linear List）是具有相同數(shù)據(jù)類型的數(shù)據(jù)

17、元素的一個(gè)有限序列。通常表示為： （a1，a2， ai，ai+1 an） 其中n為線性表的長(zhǎng)度，n0；當(dāng)n=0時(shí)表示一個(gè)空表。線性表相鄰元素之間存在著順序關(guān)系。a1叫表頭元素，an叫表尾元素。除第一個(gè)和最后一個(gè)元素外，每個(gè)元素都只有一個(gè)前趨和一個(gè)直接后繼。ai-1稱為ai的直接前趨結(jié)點(diǎn)，ai+1稱為ai的直接后繼結(jié)點(diǎn)。 表中的元素可以是一個(gè)數(shù)，也可以是由多個(gè)數(shù)據(jù)項(xiàng)組成的復(fù)雜信息，但線性表中的元素必須屬于同一數(shù)據(jù)對(duì)象。例如英文字母（A，B，.Y，Z）和在緒論中引入的學(xué)生成績(jī)表表11。,2線性表的二元組表示,線性表用二元組表示為：linear_list=(D，R) 其中數(shù)據(jù)對(duì)象：D=ai|1in,

18、n 0, aiElemType 數(shù)據(jù)關(guān)系：R=r，r= |1in-1，對(duì)應(yīng)的邏輯結(jié)構(gòu)圖如圖2-1所示： 圖2-1線性表的邏輯結(jié)構(gòu)圖,2.1.2 線性表的基本操作,線性表是一種簡(jiǎn)單靈活的數(shù)據(jù)結(jié)構(gòu)，我們根據(jù)需要可以對(duì)線性表中的元素進(jìn)行訪問、插入和刪除等操作，常用操作有以下幾種： (1)創(chuàng)建線性表：InitList( L ) 初始條件：表不存在 操作結(jié)果：構(gòu)造一個(gè)空的線性表L。 (2)求線性表的長(zhǎng)度：ListLength( L ) 初始條件：線性表L已存在。 操作結(jié)果：返回L中元素個(gè)數(shù)。 (3)查找線性表中的元素：GetElem( L, i) 初始條件：線性表L已存在， 1iLengthList(L

19、) 操作結(jié)果：用來返回L中第i個(gè)元素的值。,2.1.2 線性表的基本操作,(4)查找線性表中元素的位置：LocateElem( L, x ) 初始條件：線性表L已存在 操作結(jié)果：返回L中查找值為x的數(shù)據(jù)元素，若查找成功，則返回值為x的那個(gè)元素在L中首次出現(xiàn)的的序號(hào)或地址，否則，在L中未找到值為X的數(shù)據(jù)元素，則返回值為特定值，表示查找失敗。 (5)插入操作：ListInsert( /*存儲(chǔ)線性表中的元素*/ int len; /*線性表的當(dāng)前表長(zhǎng)*/ SqList;,2.2.2 基本操作的實(shí)現(xiàn),在線性表的順序存儲(chǔ)結(jié)構(gòu)中，ListLength(L)等操作比較簡(jiǎn)單，在這里我們主要介紹以下幾種操作。

20、1插入 線性表的插入是指在表的第i個(gè)位置上插入一個(gè)值為x的元素，線性表的邏輯結(jié)構(gòu)由 (a1，ai-1，ai，an) 改變?yōu)?(a1， ， ai-1，x，ai，an)，表長(zhǎng)變?yōu)閚+1。算法思想如下： （1）檢查i值是否超出所允許的范圍（1in+1），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理； （2）否則，將線性表的第i個(gè)元素和它后面的所有元素均向后移動(dòng)一個(gè)位置； （3）將新元素寫入到空出的第i個(gè)位置上； （4）使線性表的長(zhǎng)度增加1。,2.2.2 基本操作的實(shí)現(xiàn),具體算法： 【算法2.1】 int Insert_Sq (SqList *L, int i, ElemType x) /* 在順序線性表L的第

21、i個(gè)元素之前插入新的元素x */ Int i,j; if (i L-len+1) return 0; /*不合理的插入位置*/ if (L-len = = L-MaxSize-1) return 1;/* 表已滿 */ for (j= L-len;j=i;-j) L-elemj+1=L-elemj; L-elemi=x; +L-len; return 1 Insert_Sq,2.2.2 基本操作的實(shí)現(xiàn),插入算法的時(shí)間性能分析： 順序表上的插入運(yùn)算，時(shí)間主要消耗在數(shù)據(jù)的移動(dòng)上，在第i個(gè)位置上插入x，從an到ai都要向下移動(dòng)一個(gè)位置，共需要移動(dòng)n-il個(gè)元素，而i的取值范圍為：1in+1，即n+1

22、個(gè)位置可以插入。設(shè)在第i個(gè)位置上作插入的概率為pi，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)： Ein=,2.2.2 基本操作的實(shí)現(xiàn),如果在表的任何位置插入元素的概率相等，即：pi=，則： Ein= = = 因此在順序表上做插入操作，平均約移動(dòng)表中一半的元素，若表長(zhǎng)為n，則上述算法的時(shí)間復(fù)雜度為O(n)。,2.2.2 基本操作的實(shí)現(xiàn),2 刪除操作 刪除操作是指刪除線性表中的第i個(gè)數(shù)據(jù)元素，線性表的邏輯結(jié)構(gòu)由(a1，ai-1，ai，ai+1，an)變成長(zhǎng)度為n-1的(a1，,ai-1，ai+1，an)。算法思想如下： （1）檢查i值是否超出所允許的范圍（1in），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理； （2）否則

23、，將線性表的第i個(gè)元素后面的所有元素均向前移動(dòng)一個(gè)位置； （3）使線性表的長(zhǎng)度減1。具體算法如下：,2.2.2 基本操作的實(shí)現(xiàn),【算法2.2】 int Delete_Sq(SqList *L,int i) /*刪除線性表中第i個(gè)元素*/ if (i L-len) return 0; /*不合理的刪除位置*/ if (L-len=0) return 1; /*空表*/ for (j=i;jlen-1;j+) /*被刪除元素的后面元素向前移*/ L-elemj=L-elemj+1; - -L-len; return 1; /*Delete_Sq*/,2.2.2 基本操作的實(shí)現(xiàn),刪除算法的時(shí)間性能分

24、析： 與插入運(yùn)算相同，其時(shí)間主要消耗在數(shù)據(jù)的移動(dòng)上，刪除第i個(gè)元素時(shí)，其后面的元素ai1到an都要向前移動(dòng)一個(gè)位置，共需要移動(dòng)n-i個(gè)元素，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)： Edel=,2.2.2 基本操作的實(shí)現(xiàn),3.按值查找 線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。算法思想如下： （1）從第一個(gè)元素a1起依次和x比較，直至找到一個(gè)與x相等的數(shù)據(jù)元素，則返回它在順序表中存儲(chǔ)下標(biāo)或序號(hào)。 （2）如果沒有找到，則返回1。,2.2.2 基本操作的實(shí)現(xiàn),具體算法如下： 【算法2.3】 int LocateElem(SqList *L, ElemType x) int i; for (i

25、=0;ilen;i+) if (L-datai=x) return i; return(0) ,2.2.2 基本操作的實(shí)現(xiàn),上述算法的主要運(yùn)算是比較，當(dāng)a1=x時(shí)，需比較一次，若an=x時(shí)，比較n次成功。因此查找概率相等的情況下，平均比較次數(shù)為：: Eloc= = 所以上述算法的時(shí)間復(fù)雜度也為O(n)。,2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),采用順序存儲(chǔ)方式的線性表，內(nèi)存的存儲(chǔ)密度高，可以節(jié)約存儲(chǔ)空間，并可以隨機(jī)地存取結(jié)點(diǎn)，但是插入和刪除操作時(shí)往往需要移動(dòng)大量的數(shù)據(jù)元素，并且要預(yù)先分配空間，并要按最大空間分配，因此存儲(chǔ)空間得不到充分的利用，從而影響了運(yùn)行效率。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它能有效地克服順序存儲(chǔ)

26、方式的不足，同時(shí)也能有效地實(shí)現(xiàn)線性表的擴(kuò)充。,2.3.1 單鏈表,線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的值之外，還必須有一個(gè)指示該元素直接后繼存儲(chǔ)位置的信息，即指出后繼元素的存儲(chǔ)位置。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)（node）。每個(gè)結(jié)點(diǎn)包括兩個(gè)域：一個(gè)域存儲(chǔ)數(shù)據(jù)元素信息，稱為數(shù)據(jù)域；另一個(gè)存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域。指針域中存儲(chǔ)的信息稱做指針或鏈。N個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表，由于此鏈表的每一個(gè)結(jié)點(diǎn)中包含一個(gè)指針域，故又稱線性鏈表或單鏈表。

27、,2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),單鏈表中結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)描述如下： typedefstructLnode ElemTypedata； Struct Lnode *next; Lnode;,2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),單鏈表的存儲(chǔ)結(jié)構(gòu)如圖2-3所示。其中，H是一個(gè)指向LNode類型的指針變量，稱為頭指針。另外圖2-3(a)中單鏈表的第一個(gè)結(jié)點(diǎn)之前還附設(shè)一個(gè)結(jié)點(diǎn)，稱之為頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可存儲(chǔ)如線性表的長(zhǎng)度等附加信息，單鏈表的頭指針指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的指針域指向第一個(gè)結(jié)點(diǎn)的指針，由于最后一個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)，它的指針域?yàn)榭?，用“”表示。若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?/p>

28、，如圖2-3(b)所示。,2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),(a)非空表 (b)空表 圖2-3 線性表的單鏈表存儲(chǔ)結(jié)構(gòu),2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),在建立鏈表或向鏈表中插入結(jié)點(diǎn)時(shí)，應(yīng)先按結(jié)點(diǎn)的類型向系統(tǒng)申請(qǐng)一個(gè)結(jié)點(diǎn)，系統(tǒng)給結(jié)點(diǎn)分配指針值，即該結(jié)點(diǎn)的首地址?？梢酝ㄟ^調(diào)用C的動(dòng)態(tài)分配庫函數(shù)malloc，向系統(tǒng)申請(qǐng)結(jié)點(diǎn)。如有說明語句： LNode *p； 調(diào)用函數(shù)malloc的形式為：p（LNode *）ma11oc（sizeof（LNode）,則p指向一個(gè)新的結(jié)點(diǎn)。結(jié)點(diǎn)的數(shù)據(jù)域用 p-data來表示，指針域用 p-next來表示。使用時(shí)要注意區(qū)分結(jié)點(diǎn)和指向結(jié)點(diǎn)指針這兩個(gè)不同的概念,2.3.2 基本操作的

29、實(shí)現(xiàn),1.初始化鏈表操作 算法思想：初始化單鏈表，其結(jié)構(gòu)形式如圖2-3(b)所示。在初始狀態(tài)，鏈表中沒有元素結(jié)點(diǎn)，只有一個(gè)頭結(jié)點(diǎn)，因此需要?jiǎng)討B(tài)產(chǎn)生頭結(jié)點(diǎn)，并將其后繼指針置為空。算法如下： 【算法2.4】 Lnode Init_L() Lnode H; if (H=(LNnode*)malloc(sizeof(LNode) /*頭結(jié)點(diǎn)*/ H-next=NULL;return 1; /*設(shè)置后繼指針為空*/ else return 0; ,2.3.2 基本操作的實(shí)現(xiàn),2.取某序號(hào)元素的操作 算法思想:在單鏈表中查找某結(jié)點(diǎn)時(shí)，需要設(shè)置一個(gè)指針變量從頭結(jié)點(diǎn)開始依次數(shù)過去，并設(shè)置一個(gè)變量j，記錄所指結(jié)

30、點(diǎn)的序號(hào)。查找到則返回該指針值,否則返回空指針.具體算法如下: 【算法2.5】 Status GetElem_L(LNode *H ,int i) p=H-next,j=1; while(p /*GetElem_L*/,2.3.2 基本操作的實(shí)現(xiàn),3.插入操作 在單鏈表中插入新結(jié)點(diǎn)，首先應(yīng)確定插入的位置，然后只要修改相應(yīng)結(jié)點(diǎn)的指針，而無須移動(dòng)表中的其他結(jié)點(diǎn)。 （1）在第i個(gè)位置插入一個(gè)新結(jié)點(diǎn)。 算法思想如下： 1）從頭結(jié)點(diǎn)開始向后查找，找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)2，否則結(jié)束。 2）動(dòng)態(tài)的申請(qǐng)一個(gè)新結(jié)點(diǎn),賦給s結(jié)點(diǎn)的數(shù)據(jù)域值。 3）將新結(jié)點(diǎn)插入。 如在第三位置插入一個(gè)新結(jié)點(diǎn)操作示意圖如圖所示

31、，具體算法如下：,2.3.2 基本操作的實(shí)現(xiàn),【算法2.6】 Status ListInsert_L1(LNode *H,int i,ElemType x) p=H,j=0; while(p /*ListInsert_L*/,2.3.2 基本操作的實(shí)現(xiàn),圖2-4插入結(jié)點(diǎn),2.3.2 基本操作的實(shí)現(xiàn),（2）在鏈表中值為x的結(jié)點(diǎn)前插入一個(gè)值為y的新結(jié)點(diǎn)。如果x值不存在，則把新結(jié)點(diǎn)插入在表尾。 算法思想：設(shè)置一個(gè)指針p從第一個(gè)元素結(jié)點(diǎn)開始向后查找，再設(shè)一個(gè)指針q指向p的前趨結(jié)點(diǎn)。當(dāng)指針指向x結(jié)點(diǎn)，便在q結(jié)點(diǎn)后插入；如果值為x的結(jié)點(diǎn)不在鏈表，此時(shí)指針正好指向尾結(jié)點(diǎn)，即可完成插入。,2.3.2 基本操作

32、的實(shí)現(xiàn),【算法2.7】 void Insert_L2(LNode *H, ElemType x, ElemType y) q=H,p=H-next; while(p/*插入*/ /*Insert_L*/,2.3.2 基本操作的實(shí)現(xiàn),4刪除操作 從鏈表中刪除一個(gè)結(jié)點(diǎn)，首先應(yīng)找到被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后修改該結(jié)點(diǎn)的指針域，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間。從鏈表中刪除一個(gè)不需要的結(jié)點(diǎn)時(shí)，要把結(jié)點(diǎn)歸還給系統(tǒng)，用庫函數(shù)free(p)實(shí)現(xiàn)。 （1）刪除單鏈表中的第i（i0）個(gè)元素。 算法思想：設(shè)置一個(gè)指針p從第一個(gè)元素結(jié)點(diǎn)開始向后移動(dòng)，當(dāng)p移動(dòng)到第i-1個(gè)結(jié)點(diǎn)時(shí)，另設(shè)一個(gè)指針q指向p的后繼結(jié)點(diǎn)。使p的后繼指針指

33、向q的后繼指針，即可完成刪除操作。如刪除第二個(gè)結(jié)點(diǎn)元素，操作如圖2-5所示,具體算法如下,2.3.2 基本操作的實(shí)現(xiàn),【算法2.8】 Status ListDelete_L(LNode *H,int i,ElemType /*ListDelete_L,2.3.2 基本操作的實(shí)現(xiàn),圖2-5刪除結(jié)點(diǎn),2.3.2 基本操作的實(shí)現(xiàn),(2)刪除鏈表中所有值為x的結(jié)點(diǎn)，并返回值為x的結(jié)點(diǎn)的個(gè)數(shù)。 算法思想：操作時(shí)設(shè)指針p從第一個(gè)元素結(jié)點(diǎn)起逐一查找值為x的結(jié)點(diǎn)，并設(shè)一個(gè)輔助指針q始終指向它的前趨結(jié)點(diǎn)，每找到一個(gè)結(jié)點(diǎn)便進(jìn)行刪除，同時(shí)統(tǒng)計(jì)被刪除結(jié)點(diǎn)的個(gè)數(shù)。具體算法如下：【算法2.9】 int Delete_Li

34、nkst(LNode *H,ELEMTP X) q=H;count=0; while (q-next) /*遍歷整個(gè)鏈表*/ p=q-next; if (p-data=x) q-next=p-next; free(p); +count; else q=p; return count; /* delete_Linkst */,2.3.2 基本操作的實(shí)現(xiàn),從以上的查找、插入、刪除算法可知，這些操作都是從鏈表的頭結(jié)點(diǎn)開始，向后查找插入、刪除的位置，然后進(jìn)行插入、刪除。所以，如果表長(zhǎng)是n，則上述算法的時(shí)間復(fù)雜度為O(n)。,2.3.3 循環(huán)鏈表,循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在線性表中，每個(gè)結(jié)點(diǎn)

35、的指針都指向其下一個(gè)結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的指針為“空”，不指向任何地方，只表示鏈表的結(jié)束。若把這種結(jié)構(gòu)修改一下，使其最后一個(gè)結(jié)點(diǎn)的指針回指向第一個(gè)結(jié)點(diǎn)，這樣就形成了一個(gè)環(huán)，這種形式的鏈表就叫做循環(huán)鏈表。如圖2-6所示。 (a)非空表 (b)空表 圖2-6單向循環(huán)鏈表,2.3.3 循環(huán)鏈表,循環(huán)單鏈表的操作與線性表類似，只是有關(guān)表尾、表空的判定條件不同。在采用頭指針描述的循環(huán)鏈表中，空表的條件是head-next=head，指針p到達(dá)表尾的條件是 p-next=head。因此循環(huán)鏈表的插入、刪除、建立、查找等操作只需在線性鏈表的算法上稍加修改即可。 在循環(huán)鏈表結(jié)構(gòu)中從表中任一結(jié)點(diǎn)出發(fā)均可找到表中的

36、其他結(jié)點(diǎn)。如果從表頭指針出發(fā)，訪問鏈表的最后一個(gè)結(jié)點(diǎn)，必須掃描表中所有的結(jié)點(diǎn)。若把循表的表頭指針改用尾指針代替，則從尾指針出發(fā)，不僅可以立即訪問最后一個(gè)結(jié)點(diǎn)，而且也可十分方便地找到第一個(gè)結(jié)點(diǎn)，如圖27所示。設(shè)rear為循環(huán)鏈表的尾指針，則開始結(jié)點(diǎn)a1的存儲(chǔ)位置可用 rear-next-next表示,2.3.3 循環(huán)鏈表,在實(shí)際應(yīng)用中，經(jīng)常采用尾指針描述的循環(huán)鏈表，例如，將兩個(gè)循環(huán)鏈表首尾相接時(shí)合并成一個(gè)表，采用設(shè)置尾指針的循環(huán)鏈表結(jié)構(gòu)來實(shí)現(xiàn)，將十分簡(jiǎn)單、有效。操作過程如圖2-8所示，有關(guān)的操作語句如下 p=rb-next; rb-next=ra-next; ra-next=p-next; fr

37、ee(p); ra=rb; ,圖2-7 設(shè)尾指針的循環(huán)鏈表,2.3.3 循環(huán)鏈表,圖2-8循環(huán)鏈表合并示意圖,2.3.4 雙向鏈表,在單鏈表中，從任何一個(gè)結(jié)點(diǎn)通過指針域可找到它的后繼結(jié)點(diǎn)，但要尋找它的前趨結(jié)點(diǎn)，則需從表頭出發(fā)順鏈查找。因此對(duì)于那些經(jīng)常需要既向后查找又向前查找的問題，采用雙向鏈表結(jié)構(gòu)，將會(huì)更方便。 在雙向鏈表結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)除了數(shù)據(jù)域外，還包括兩個(gè)指針域，一個(gè)指針指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，另一個(gè)指針指向它的前趨結(jié)點(diǎn)。結(jié)點(diǎn)結(jié)構(gòu)如圖2-9(a)所示，雙向鏈表也可以是循環(huán)表，其結(jié)構(gòu)如圖2-10(b) 所示。,2.3.4 雙向鏈表,(a)結(jié)點(diǎn)結(jié)構(gòu) （b)非空的雙向鏈表,圖2-9雙向循環(huán)鏈表

38、示意圖,2.3.4 雙向鏈表,雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)可描述如下： typedef struct dunode ElemType data; struct dunode *prior,*next; Dunode; 雙向鏈表由于可以從兩個(gè)方向搜索某個(gè)結(jié)點(diǎn)，這使得鏈表的某些操作變得比較簡(jiǎn)單，本節(jié)主要介紹以下幾種操作： 1插入 在雙向鏈表的指定結(jié)點(diǎn)p之前插入一個(gè)新的結(jié)點(diǎn)。如圖2-10所示，算法思想： （1）生成一個(gè)新結(jié)點(diǎn)s，將值x賦給s的數(shù)據(jù)域。 （2）將p的前驅(qū)結(jié)點(diǎn)指針作為s的前驅(qū)結(jié)點(diǎn)指針。 （3）p作為新結(jié)點(diǎn)的直接后繼。 （4）s作為結(jié)點(diǎn)的直接前驅(qū)的后繼。 （5）s作為p結(jié)點(diǎn)新的直接前驅(qū)。,2.3.4

39、 雙向鏈表,圖2-10在雙向鏈表中插入一個(gè)結(jié)點(diǎn),具體算法如下： 【算法2.10】 void ListInsert_Dul(Dunode *p,ElemType x) Dunode *s; s=( Dunode *) malloc (sizeof(Dunode); s -data=x; s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s; ,2.3.4 雙向鏈表,2刪除：在雙向鏈表中刪除p結(jié)點(diǎn)，如圖2-11所示，主要操作步驟如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 圖2-1

40、1在雙向鏈表中刪除一個(gè)結(jié)點(diǎn),2.4 線性表的應(yīng)用-多項(xiàng)式相加問題,多項(xiàng)式的相加操作是線性表處理的典型例子。在數(shù)學(xué)上，一個(gè)多項(xiàng)式可寫成下列形式： P（x）a0 x0a1x1+anxn 其中ai為xi的非零系數(shù)。在多項(xiàng)式相加時(shí)，至少有兩個(gè)或兩個(gè)以上的多項(xiàng)式同時(shí)并存，而且在實(shí)現(xiàn)運(yùn)算的過程中所產(chǎn)生的中間多項(xiàng)式和結(jié)果多項(xiàng)式的項(xiàng)數(shù)和次數(shù)都是難以預(yù)料的。因此計(jì)算機(jī)實(shí)現(xiàn)時(shí)，可采用單鏈表來表示。多項(xiàng)式中的每一項(xiàng)為單鏈表中的一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)包含三個(gè)域：系數(shù)域、指數(shù)域和指針域，其形式如下： coefexpnext結(jié)點(diǎn)結(jié)構(gòu)描述為： type struct pnode int coef;/*系數(shù)域*/ int exp

41、; /*指數(shù)域*/ struct pnode *next/*指針域*/ ,2.4 線性表的應(yīng)用-多項(xiàng)式相加問題,多項(xiàng)式相加的運(yùn)算規(guī)則為：兩個(gè)多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相加，若和不為零，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)，否則，“和多項(xiàng)式”中就去掉這一指數(shù)項(xiàng)，所有指數(shù)不同的項(xiàng)均復(fù)制到“和多項(xiàng)式”中。如對(duì)于多項(xiàng)式A(x)=5x5+8x4+4x2-8，B(x)=6x10+4x5-4x2。 實(shí)現(xiàn)時(shí)，可采用另建多項(xiàng)式的方法，也可以把一個(gè)多項(xiàng)式歸并到另一個(gè)多項(xiàng)式中去的方法。這里介紹后一種方法。 算法思想：首先設(shè)兩個(gè)指針qa和qb分別從多項(xiàng)式的首項(xiàng)開始掃描。比較qa和qb所指結(jié)點(diǎn)指數(shù)域的值， 可能出現(xiàn)下列三

42、種情況之一：,（1）qa-exp大于qb-exp，則qa繼續(xù)向后掃描。 (2)qa-exp等于qb-exp ，則將其系數(shù)相加。若相加結(jié)果不為零，將結(jié)果放入qacoef中，否則同時(shí)刪除qa和qb所指結(jié)點(diǎn)。然后qa、qb繼續(xù)向后掃描。 （3）qa-exp小于qb-exp，則將qb所指結(jié)點(diǎn)插入qa所指結(jié)點(diǎn)之前，然后qa、qb繼續(xù)向后掃描。 掃描過程一直進(jìn)行到qa或qb有一個(gè)為空為止，然后將有剩余結(jié)點(diǎn)的鏈表接在結(jié)果鏈表上。所得Ha指向的鏈表即為兩個(gè)多項(xiàng)式之和。操作過程見圖2-13所示。,圖2-13多項(xiàng)式相加示意圖,下面是多項(xiàng)式相加算法： 【算法2.11】 void polyadd(pnode *Ha,

43、pnode *Hb) /* 以Ha和Hb為頭指針的單鏈表分別表示兩個(gè)多項(xiàng)式，實(shí)現(xiàn)Ha=Ha+Hb*/ pnode *pre,*qa,*qb,*q;int sum; pre=Ha; /*pre始終指向當(dāng)肖和多項(xiàng)式的最后一個(gè)結(jié)點(diǎn)*/ qa=Ha-next; qb=Hb-next; while(qa else /*系數(shù)和為零*/,pre-next=qa-next; free(qa); qa=pre-next; q=qb; qb=qb-next;free(q); else/*指數(shù)不相同*/ if(qa-expqb-exp) pre=qa;qa=qa-next; else pre-next=qb;pre

44、=qb; qb=qb-next;pre-next=qa; if(qb) pre-next=qb;/*鏈接pb中剩余結(jié)點(diǎn)*/ free(Hb);/*釋放Hb頭結(jié)點(diǎn)*/ ,本章小結(jié),線性表是一種最基本、最常用的數(shù)據(jù)結(jié)構(gòu)。本章主要介紹了線性表的定義、運(yùn)算和線性表的兩種存儲(chǔ)結(jié)構(gòu)順序表和鏈表，以及在這兩種存化結(jié)構(gòu)上實(shí)現(xiàn)的基本運(yùn)算。 順序表是用數(shù)組實(shí)現(xiàn)的，鏈表是用指針實(shí)現(xiàn)的。用指針來實(shí)現(xiàn)的鏈表，結(jié)點(diǎn)空間是動(dòng)態(tài)分配的，鏈表又按鏈接形式的不同，區(qū)分為單鏈表、雙鏈表和循環(huán)鏈表。建議讀者熟練掌握在順序表和鏈表上實(shí)現(xiàn)的各種基本運(yùn)算及其時(shí)間、空間特性。,習(xí)題2,一 選擇題 1.一個(gè)線性表第一個(gè)元素的存儲(chǔ)地址是100,

45、每個(gè)元素的長(zhǎng)度為4,則第5個(gè)元素的地址是( ) A.110 B.116 C.100 D.120 2. 向一個(gè)有128個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（ ）個(gè)元素。 A.64 B.63 C.63.5D.7 3在循環(huán)雙鏈表的p所指接點(diǎn)之前插入s所指接點(diǎn)的操作是 A.p- prior =s;s- next t=p;p- prior t-left=s;s- prior =p- prior; B. p- prior =s;p- prior - next =s;s- next =p;s- prior =p- prior; C.s- next =p;s- prior =p- pr

46、ior;p- prior =s;p- prior - next =s; D.s- next =p;s- prior =p- prior;p- prior - next =s;p- prior =s; 4從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較（ ）個(gè)結(jié)點(diǎn)。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 5線性表是具有n個(gè)（ ）的有限序列（n0） A.表元素 B.字符 C.數(shù)據(jù)元素 D.數(shù)據(jù)項(xiàng) 6非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由P指向）滿足 A. p-next=NULL B. p=NULL C. p-next=head D.p=head

47、7在一個(gè)單鏈表中已知q所指的結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(zhí)行( ) A. s-next=p-next;p-next=s; B.p-next=s-next;s-next=p; C. q-next=s;s-next=p; D.p-next=s;s-next=q;,習(xí)題2,8已知一個(gè)順序存儲(chǔ)線性表，若第1個(gè)結(jié)點(diǎn)的地址d，第3個(gè)的地址是5d，則第n個(gè)結(jié)點(diǎn)的地址為( ) A2*(n-1)+1*d B.2*(n-1)*d C.2*(n-1)-1*d D.(n+1)*d 9在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是( ) A.O(1) B.O(n) C

48、.O(n2) D.O(nlog2n) 10如果最常用的操作是提取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用( )存儲(chǔ)方式最節(jié)省時(shí)間。 A單鏈表B.順序表C.循環(huán)鏈表D.雙鏈表 11在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1in)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移( )個(gè)元素。 A.n-i B.n-i+1 C.n-i-1 D.i 12在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(0in-1)時(shí)，需要從后向前依次前移( )個(gè)元素。 A.n-i B.n-i+1 C. n-i-1 D.i 13在單鏈表中刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為( ) A.O(1) B.O(n2 ) C.O(n) D(logn) 14

49、 鏈表不具有的特點(diǎn)是( )。 A.可隨機(jī)訪問任一元素 B.插入刪除不需要移動(dòng)元素 C.不必事先估計(jì)存儲(chǔ)空間 D.所需空間與線性表長(zhǎng)度成正比 15線性表L=(a1,a2,an)，下列說法正確的是( )。 A.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B.線性表中至少要有一個(gè)元素 C.表中諸元素的排列順序必須是有小到大或者由大到小 D.除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。,習(xí)題2,二填空題 1寫出循環(huán)鏈表L中某個(gè)結(jié)點(diǎn)*p為尾指針的條件_。 2在一個(gè)帶頭節(jié)點(diǎn)的單向循環(huán)鏈表中，p指向尾節(jié)點(diǎn)的直接前驅(qū)，則指向頭節(jié)點(diǎn)的指針head可用p表示為_。 3帶頭結(jié)點(diǎn)的單鏈表h

50、ead為空的判定條件是_。 4長(zhǎng)度為0的線性表稱為_。 5在雙鏈表中，刪除p結(jié)點(diǎn)語句序列是_。 6在單鏈表中，刪除指針p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是_。 7已知P為單鏈表中的非首尾結(jié)點(diǎn)，在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句為：_ 。 8順序表中邏輯上相鄰的元素物理位置_相鄰， 單鏈表中邏輯上相鄰的元素物理位置_相鄰。 9線性表L（a1，a2，.，an）采用順序存儲(chǔ)，假定在不同的n1個(gè)位置上插入的概率相同，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)是_。 10在一個(gè)長(zhǎng)度為n的線性表中順序查找值為x的元素時(shí)，查找時(shí)的平均查找長(zhǎng)度（即x同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 C。 11單鏈表是的鏈接

51、存儲(chǔ)表示。 12在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向，另一個(gè)指向。,習(xí)題2,三判斷題 1.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，其地址必須是連續(xù)的。（） 2.線性表中至少有一個(gè)元素（） 3.線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨（） 4線性表的長(zhǎng)度是線性表所占用的存儲(chǔ)空間的大小。（） 5雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。（） 6線性表的唯一存儲(chǔ)形式是鏈表。 7線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。（） 8鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。（） 9在線性表的順序存儲(chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置一定緊鄰。（） 10在線性表的順序結(jié)構(gòu)中，插入和刪除元素時(shí)，移動(dòng)元素的個(gè)數(shù)與該元素

52、的位置有關(guān)。（） 四算法設(shè)計(jì)題部分 1設(shè)計(jì)算法，刪除順序表中值為x的所有結(jié)點(diǎn)。 2試編寫一個(gè)求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)（數(shù)據(jù)域數(shù)據(jù)類型為整 型）。 3有一個(gè)單鏈表（不同結(jié)點(diǎn)的數(shù)據(jù)域值可能相同），其頭指針為head，編寫一個(gè)函數(shù)計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。 4已知帶有頭結(jié)點(diǎn)的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數(shù)據(jù)域值 為x的所有結(jié)點(diǎn)的c函數(shù)。 5對(duì)給定的單鏈表，編寫一個(gè)刪除單鏈表中值為x的結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)算法。 6試編寫算法,刪除雙向循環(huán)鏈表中第k個(gè)結(jié)點(diǎn)。,第3章 數(shù)組和廣義表,本章學(xué)習(xí)要求： 數(shù)組和廣義表是線性結(jié)構(gòu)的一種擴(kuò)展，通過本章的學(xué)習(xí)認(rèn)識(shí)數(shù)組和廣義表這兩種數(shù)據(jù)結(jié)構(gòu)。 理

53、解掌握數(shù)組的兩種存儲(chǔ)表示方法與實(shí)現(xiàn) 掌握對(duì)特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式。 掌握稀疏矩陣的存儲(chǔ)方法 掌握廣義表的結(jié)構(gòu)特點(diǎn)及其存儲(chǔ)表示方法,3.1 數(shù)組,3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu) 1.數(shù)組的概念 數(shù)組是幾乎所有的高級(jí)語言都提供的一種常用的數(shù)據(jù)結(jié)構(gòu)。數(shù)組（array）是由下標(biāo)（index）和值（value）組成的序?qū)Γ╥ndexvalue pairs）的集合。在一般程序設(shè)計(jì)語言中，數(shù)組必須先進(jìn)行定義（或聲明）后，才能使用，數(shù)組的定義由以下三部分組成： (1)數(shù)組的名稱； (2) 數(shù)組的維數(shù)及各維長(zhǎng)度； (3) 數(shù)組元素的數(shù)據(jù)類型； 如在c語言中，二維數(shù)組的定義為： ElemType a

54、rraynamerowcol; 由此可以看出，數(shù)組中所有的元素屬于同一數(shù)據(jù)類型，數(shù)組一旦定后，它的元素個(gè)數(shù)確定，所需的存儲(chǔ)空間也就確定了。因此，數(shù)組不存在線性表中的插入和刪除操作，除了初始化操作外，對(duì)于數(shù)組的操作一般只限于兩類：取得特定位置的元素值及對(duì)特定位置的元素進(jìn)行賦值。,3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu),2.數(shù)組的順序存儲(chǔ) 高級(jí)語言中數(shù)組在計(jì)算機(jī)內(nèi)是用一批連續(xù)的存儲(chǔ)單元來表示的，稱為數(shù)組的順序存儲(chǔ)結(jié)構(gòu)。在二維數(shù)組中，每個(gè)元素都受行關(guān)系和列關(guān)系的約束，例如在一個(gè)二維數(shù)組Amn中，對(duì)于第i行第j列的元素Aij，Aij+1是該元素在行關(guān)系中的直接后繼元素；而Ai+1j是該元素在列關(guān)系中的直接后繼

55、元素。大部分高級(jí)語言采用行序?yàn)橹鞯拇鎯?chǔ)方式（如c,Pascal），如圖3-1(a)所示，有的語言（如Fortran）中采用的是以列序?yàn)橹鞯拇鎯?chǔ)方式。如圖3-1(b)所示。,3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu),圖3-1二維數(shù)組的存儲(chǔ)結(jié)構(gòu),3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu),(1)按行存儲(chǔ)方式 首先看一維數(shù)組an，數(shù)組的長(zhǎng)度為n，每個(gè)元素所需的存儲(chǔ)空間L是由數(shù)組元素的數(shù)據(jù)類型決定的，即L=sizeof(ElemType)；數(shù)組的首地址為L(zhǎng)OCA(元素A0)的地址），則數(shù)組A中任何一個(gè)元素Ai的地址LOCi可由下式進(jìn)行計(jì)算： LOCi=LOCA+I*L 對(duì)于二維數(shù)組anm來說，先依次存放第一行的元素a00,

56、a01.,a0m-1；然后存放第二行元素a10,a11.,a1m-1，.最后存放第n行元素an-10,an-11.,an-1m-1；若每行的元素個(gè)數(shù)為m，每個(gè)元素所需存儲(chǔ)單元為L(zhǎng)，則二維數(shù)組按行存儲(chǔ)的地址映像公式為： LOCi,j=LOC0,0+(m*i+j)*L 同理可知三維數(shù)組Ac1c2c3按行存儲(chǔ)方式下地址映像公式為： LOCi,j,k=LOC0,0,0+(c2*c3*i+c3*j+k)*L,3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu),分析上面的公式，c2*c3為最未兩維所對(duì)應(yīng)的二維數(shù)組的元素個(gè)數(shù)，c3則是最未一維所規(guī)定的一維數(shù)組的元素個(gè)數(shù)，以上規(guī)則可以推廣到多維數(shù)組的情況。設(shè)n維數(shù)組的各維長(zhǎng)度為c

57、1，c2.，.，每個(gè)元素所需存儲(chǔ)單元為L(zhǎng)個(gè)，各維數(shù)組元素的下標(biāo)由0開始，則n維數(shù)組按行存儲(chǔ)的地址映像公式為： LOCJ1,J2,.Jn =LOC0,0,0+( c2*c3*. cn)* J1+( c3*c4*)* J2+.+cn*Jn-1+Jn)*L = LOC0,0,0+ （公式2-1）,3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu),例3-1有如下數(shù)組定義： int a89; float b1064; 若數(shù)組a的首地址為500，b的首地址為1000，且按行存儲(chǔ)。求數(shù)組元素a5,6,b345的地址。 解：（1）數(shù)組元素a56的地址 將j1=5，j2=6,c1=8，c2=9帶入公式2-1得： LOC5,6=5

58、00+(9*5+6)*sizeof(int)=500+51*2=602 (2) 數(shù)組元素b345的地址 將j1=3，j2=4，j3=5，c1=10，c2=6，c3=4帶入公式得： LOC3,4,5=1000+(3*6*4+4*4+5)*sizeof(float) =1000+93*4=1372,3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu),（2）按列存儲(chǔ)方式 所謂按列存儲(chǔ)，是首先存儲(chǔ)第一列的元素，然后存儲(chǔ)第二列的元素，.最后存儲(chǔ)第n-1列的元素。 推廣到一般情況，設(shè)n維數(shù)組的各維長(zhǎng)度為c1，c2.，.，每個(gè)元素所需存儲(chǔ)單元為L(zhǎng)個(gè)，各維數(shù)組元素的下標(biāo)由0開始，則n維數(shù)組按列存儲(chǔ)的地址映像公式為： LOCj1,j2,.jn =LOC0,0,0+( c1*c2*. cn1)* jn+( c1*c2*. cn2)* jn-1+.+c1*j2+j1)*L = LOC0,0,0+ （公式2-2）,3.1.1數(shù)組概念及其存儲(chǔ)結(jié)構(gòu),例3-2有如下數(shù)組定義： int a99; float b1064; 若數(shù)組a的首地址為500，b的首地址為1000，且按列存儲(chǔ)。求數(shù)組元素a5,6,b345的地址。 解：（1）數(shù)組元素a5