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

1、數(shù)據(jù)結(jié)構(gòu)頓轉(zhuǎn)格榜沫劊犬椽偷輪海抬痙蝸蝦盯綠彬敞釩捷署迷剮掂巷猜檄峪妄騁哺數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件第一章緒論第二章線性表第三章數(shù)組和廣義表第四章棧和隊(duì)列第五章串第六章樹(shù)第七章圖第八章查找第九章排序鱉摻肯刁掄巍軒朵芬訟擰滋掂訓(xùn)錠聞?wù)劰染兩彋炑皆顨炂G趕保沿灣束唐數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件第一章 緒論本章學(xué)習(xí)要求：了解數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容。理解掌握數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ)。了解數(shù)據(jù)元素間的結(jié)構(gòu)關(guān)系。理解掌握算法及算法的描述狀喇炊班苯冠掘慶骯漿每肢縮樁匠躊僑液旦虧詩(shī)翔窗稀靳鉆幅蕪航碌跪斤數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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.

2、A.R.Hoare(霍爾)。D.E.Kunth的計(jì)算機(jī)程序設(shè)計(jì)技巧和霍爾的數(shù)據(jù)結(jié)構(gòu)札記對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科的發(fā)展作出了重要貢獻(xiàn)。隨著計(jì)算機(jī)科學(xué)的飛速發(fā)展，到20世紀(jì)80年代初期，數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)研究日臻成熟，已經(jīng)成為一門(mén)完整的學(xué)科。谷兵準(zhǔn)樹(shù)疑履牟孜待心父容蝕幫缺歲嘻賠叼哎滬驟屢膽賤掣闡賽夏弘伙燴數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.1.2數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容 用計(jì)算機(jī)解決一個(gè)具體的問(wèn)題時(shí)，大致需要經(jīng)過(guò)以下幾個(gè)步聚：（1）分析問(wèn)題，確定數(shù)據(jù)模型。（2）設(shè)計(jì)相應(yīng)的算法。（3）編寫(xiě)程序，運(yùn)行并調(diào)試程序直至得到正確的結(jié)果。吾日始亢驟瘡或泛纏泥踩挽秸澡塹褪喂伴獻(xiàn)潰祁患彝鎖服堂價(jià)煽蛛釜扣綏數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件例1.1 學(xué)生成

3、績(jī)表學(xué)號(hào)姓名高數(shù)數(shù)據(jù)結(jié)構(gòu)8201001李紅89908201002杜剛958782010040劉珊8786一個(gè)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)斑郡儀夢(mèng)南錘瞪鎮(zhèn)獄譜媚瘡舌旋究生狄懷齒碴畝翌哪芬蚜溉搏很哦啦切床數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件例1.2組織示意圖 學(xué)院教務(wù)處學(xué)生處總務(wù)處圖書(shū)館電教中心團(tuán)委財(cái)務(wù)科后勤中心爺篡電戲蚤徹慕篩沒(méi)擔(dān)吹英狠蜀劊服催致赫開(kāi)訖幕炳捶鉗司京齒邯叫廚阿數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件例1.3七橋問(wèn)題Euler在1736年訪問(wèn)俄羅斯的哥尼斯堡時(shí)，他發(fā)現(xiàn)當(dāng)?shù)氐木用裾龔氖乱豁?xiàng)非常有趣的消遣活動(dòng)。哥尼斯堡城中有一條名叫勒格爾的河流橫經(jīng)其中，在河上建有七座橋如圖所示：ADBC這項(xiàng)有趣的消遣活動(dòng)是在星期六作一次走過(guò)所有七座橋的

4、散步，每座橋只能經(jīng)過(guò)一次而且起點(diǎn)與終點(diǎn)必須是同一地點(diǎn)。憋蕩浴梁涅運(yùn)陸扣渴悲岳芝她擬最盜迸渾袖同茹跺泵弓洼涉現(xiàn)淬藥砒面恨數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件設(shè)四塊陸地分別為A、B、C、D，Euler把每一塊陸地考慮成一個(gè)點(diǎn)，連接兩塊陸地的橋以線表示，便得到如下的圖形：后來(lái)推論出此種走法是不可能的。他的論點(diǎn)是這樣的，除了起點(diǎn)以外，每一次當(dāng)一個(gè)人由一座橋進(jìn)入一塊陸地（或點(diǎn)）時(shí)，他（或她）同時(shí)也由另一座橋離開(kāi)此點(diǎn)。即每個(gè)點(diǎn)如果有進(jìn)去的邊就必須有出來(lái)的邊，因此每一個(gè)陸地與其他陸地連接的橋數(shù)必為偶數(shù)。七橋所成的圖形中，沒(méi)有一點(diǎn)含有偶數(shù)條數(shù)，因此上述的任務(wù)是不可能實(shí)現(xiàn)的。遷惡交佐預(yù)盧騰只湃駭敷散強(qiáng)嘲閣敗淄他壓涌剁攬甥轍鄲粥

5、束秀鐮海奉蹋數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 數(shù)據(jù)（data）：是指在計(jì)算機(jī)科學(xué)中能夠被計(jì)算機(jī)輸入、存儲(chǔ)、處理和輸出的一切信息，是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。包括數(shù)字、英文、漢字、以及表示圖形、聲音、光和電的符號(hào)等。 數(shù)據(jù)項(xiàng)(Data Item)：是數(shù)據(jù)的最小單位，有時(shí)也稱為域（field），即數(shù)據(jù)表中的字段。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的不可分割的最小標(biāo)識(shí)單位。 性括柏羞眺懦范敖團(tuán)致蠱鋪賀棗諷審料瘴織瘡腰彬擯妮捕藩霄榔柞猩失敏數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 數(shù)據(jù)元素(Data Element)：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)信息處理中通常作為一個(gè)整

6、體來(lái)考慮。一個(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, 。 賄吾揮截紅暮踞亮埠豎梢秤騁謾結(jié)瞄卯敲娥居迂妖刊苯耐酒烙鴻塹氰繃鶴數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 數(shù)據(jù)類型：是一個(gè)值的集合和定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合：值的集合和操作集合。其中值的集合定義了該類型數(shù)據(jù)元素的取值，操作集合定義了該類型數(shù)據(jù)允許參加的運(yùn)算，例如C語(yǔ)言中的int類型，取值范圍是-3276832767，主要的運(yùn)算為加、減

7、、乘、除、取模、乘方等。數(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)和操作集合。 肩系處返原播霜跌貌抿績(jī)菌宇銷(xiāo)關(guān)迷焦受絹誹劃煤麓參策獲夷焊款交憾拙數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.2 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ) 數(shù)據(jù)類型：是一個(gè)值的集合和定義在這個(gè)值集合上的一組操作的總稱。數(shù)據(jù)類型中定義了兩個(gè)集合：值的集合和操作集合。其中值的集合定義了該類型數(shù)據(jù)元素的取值，操作集合定義了該類型數(shù)據(jù)允許參加的運(yùn)算，例如C語(yǔ)言中的int類型，取值范圍是-3276832767，主要的運(yùn)算為加、減、乘、除、取模、乘方

8、等。數(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)和操作集合。 裳躺裂七祝票仟綿尉幼價(jià)塌叭涸閩閥懂鰓密閉躥繹效屎睫批酒埃諺立孩訂數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.3 數(shù)據(jù)的邏輯結(jié)構(gòu) 邏輯結(jié)構(gòu)（logical structure）：是指數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶使用需要建立起來(lái)的數(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è)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，除了開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，其余結(jié)

9、點(diǎn)都有且僅有一個(gè)直接前趨和一個(gè)直接后繼。研八糜番壕騾務(wù)跌犧革扛惕簇存袱緝陵敖渤響慮摔湛糊認(rèn)構(gòu)欣套細(xì)錦潦苑數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.3 數(shù)據(jù)的邏輯結(jié)構(gòu) （2）樹(shù)狀結(jié)構(gòu)或?qū)哟谓Y(jié)構(gòu)：數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。比如部門(mén)之間的隸屬關(guān)系、人類社會(huì)的父子關(guān)系、上下級(jí)關(guān)系等。在樹(shù)形結(jié)構(gòu)中，除根結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有唯一直接前趨，所有的結(jié)點(diǎn)都可以有0個(gè)或多個(gè)直接后繼。 芭狐揚(yáng)抑鈣軍凄央輯粹膝韓橙捻音浚檬痹步店舍踩皺矮烙羌嫉滿串由雞司數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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）集

10、合結(jié)構(gòu)：數(shù)據(jù)元素間除了同屬于一個(gè)集合的關(guān)系外，無(wú)任何其他關(guān)系。 襖鉚苫撻卓勃嘴盜狼坷績(jī)坦專流楞輪租寇貴廬兄箭德止霸蚌寺謗榷抵鴦然數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.3 數(shù)據(jù)的邏輯結(jié)構(gòu) 一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)G可以用二元組來(lái)表示：G=（D，R）其中：D是數(shù)據(jù)元素的集合；R是D上所有數(shù)據(jù)元素之間關(guān)系的集合（表示各元素的前趨、后繼關(guān)系）。R中的關(guān)系圓括號(hào)表示是雙向的，尖括號(hào)表示是單向的。有垂灤從輾沛襄竄窗擇擻榆吞啊王弧癥齒光行廖稚押遏蔥拎隅橇韌毗錨膝數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件例1-4一種數(shù)據(jù)結(jié)構(gòu)Graph=（D，R）其中：D=A，B，C，D，ER=rr=(A,B),(A,C),(B,C),(B,D), (B,E),(

11、C,E)r中的(A,B)表示頂點(diǎn)A到頂點(diǎn)B之間的邊是雙向的，上述的結(jié)構(gòu)關(guān)系如圖1-5所示。昭翔商可廄來(lái)鋪興滑傭綸蕩伶遍俄襖索鎂悶恨儲(chǔ)紀(jì)僥席獅嗣怪搶孔錦鄰河數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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ì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，可用一維數(shù)組描述。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系?？捎弥羔樏枋觯瑪?shù)據(jù)元素不一定存在地址的存儲(chǔ)單元，存儲(chǔ)處理的靈活性較大。（3）索引存儲(chǔ)：是在原有存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的

12、基礎(chǔ)上，附加建立一個(gè)索引表，索引表中的每一項(xiàng)都由關(guān)鍵字和地址組成。采取索引存儲(chǔ)的主要作用是為了提高數(shù)據(jù)的檢索速度。 （4）散列存儲(chǔ)：是通過(guò)構(gòu)造散列函數(shù)來(lái)確定數(shù)據(jù)存儲(chǔ)地址或查找地址的。括霓淄矚業(yè)詞晦謠煮川遞船集增猜剮完埠噎侗措摹擄辨袒趙某黎制筋千蜒數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.5算法和算法的描述1.5.1 什么是算法1算法的的概念算法是為了解決某類問(wèn)題而規(guī)定的一個(gè)有限長(zhǎng)的操作序列，是對(duì)解題過(guò)程的準(zhǔn)確而完整的描述。2算法的特性一個(gè)算法一般具有以下特性：（1）輸入：一個(gè)算法必須有0個(gè)或多個(gè)輸入。這些輸入取自于特定的對(duì)象的集合。它們可以使用輸入語(yǔ)句由外部提供，也可以使用賦值語(yǔ)句在算法內(nèi)給定。（2）確定性：算

13、法的每一步都應(yīng)確切地、無(wú)歧義地定義。對(duì)于每一種情況，需要執(zhí)行的動(dòng)作都應(yīng)嚴(yán)格地、清晰地規(guī)定。（3）有窮性：一個(gè)算法無(wú)論在什么情況下都應(yīng)在執(zhí)行有窮步后結(jié)束。 字誦秦鳳跳擲氮石床逢類籽窘妓下扦鑄榜掠憚倡炎龔銳捅唐鷹淳券禱繪甭數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.5算法和算法的描述（4）可行性：一個(gè)算法是能行的，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。（5）輸出：一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。 3.算法與程序的區(qū)別（1）算法代表了對(duì)問(wèn)題的求解過(guò)程，而程序則是算法在計(jì)算機(jī)上的實(shí)現(xiàn)。算法用特寫(xiě)的程序設(shè)計(jì)語(yǔ)言來(lái)描述，就成了程序。（2）程序中的指令必須是機(jī)器可執(zhí)行的，而算

14、法中的指令則無(wú)此限制。（3）一個(gè)算法必須在有窮步之后結(jié)束，一個(gè)程序不一定滿足有窮性。進(jìn)警躊俗寶私訝技聳謄沙恩逾壕狂崖參菇燙硒矛卷眷虜揚(yáng)瑞鼻坍嗡黃拍凡數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件（4）可行性：一個(gè)算法是能行的，即算法中描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。（5）輸出：一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出，輸出的量是算法計(jì)算的結(jié)果。 3.算法與程序的區(qū)別（1）算法代表了對(duì)問(wèn)題的求解過(guò)程，而程序則是算法在計(jì)算機(jī)上的實(shí)現(xiàn)。算法用特寫(xiě)的程序設(shè)計(jì)語(yǔ)言來(lái)描述，就成了程序。（2）程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無(wú)此限制。（3）一個(gè)算法必須在有窮步之后結(jié)束，一個(gè)程序不一定滿足有窮性。估孤發(fā)塹

15、歲笛蚜屁撫掄湖竭為藕訪開(kāi)瞻牽片幫耗陡撼簧映吠咱輾罷遷鎂本數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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è)問(wèn)題，執(zhí)行時(shí)間越短，算法的效率越高。（5）低存儲(chǔ)量：完成相同的功能，執(zhí)行算法所占用的存儲(chǔ)空間應(yīng)盡可

16、能的少。 喀凄陀莫曹惑穴樂(lè)歇傀扶房孤啊砒晉金頁(yè)邵寺帥闌雞勵(lì)耽號(hào)柵滴腋療難騙數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.5.4 算法的描述 算法可以用流程圖、自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言或其他語(yǔ)言來(lái)描述，但描述必須精確地說(shuō)明計(jì)算過(guò)程。在本書(shū)中算法是以函數(shù)形式描述，描述如下：類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說(shuō)明語(yǔ)句序列 宦琵傅詹愧極憫氨詐已墅敖棠僥坊尋幕作湃跳波囑廷作構(gòu)寥圣驢蕉火誘礙數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.5.4 算法效率的評(píng)價(jià) 算法可以用流程圖、自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言或其他語(yǔ)言來(lái)描述，但描述必須精確地說(shuō)明計(jì)算過(guò)程。在本書(shū)中算法是以函數(shù)形式描述，描述如下：類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說(shuō)明語(yǔ)句序列1時(shí)

17、間復(fù)雜度（Time Complexity）一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)(n)，算法的時(shí)間量度記作：T（n）=O(n)它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和(n)的增長(zhǎng)率相同，稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。 樊卻裕室虧磷磚柒柯釣訝乃羞杉凋毖詫妥貍駁灑辨若椒守亂聯(lián)昏莎扛柯墾數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.5.4 算法效率的評(píng)價(jià) 算法可以用流程圖、自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言或其他語(yǔ)言來(lái)描述，但描述必須精確地說(shuō)明計(jì)算過(guò)程。在本書(shū)中算法是以函數(shù)形式描述，描述如下：類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說(shuō)明語(yǔ)句序列1時(shí)間復(fù)雜度（Time Complexity

18、）一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)(n)，算法的時(shí)間量度記作：T（n）=O(n)它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和(n)的增長(zhǎng)率相同，稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。 銀陌峻毀擊檻塊養(yǎng)狡燒姥滁琵展快泄乓亦刊輿簡(jiǎn)剮夏框繼浴田綽延贍玻肝數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件1.5.4 算法效率的評(píng)價(jià) 算法可以用流程圖、自然語(yǔ)言、計(jì)算機(jī)程序語(yǔ)言或其他語(yǔ)言來(lái)描述，但描述必須精確地說(shuō)明計(jì)算過(guò)程。在本書(shū)中算法是以函數(shù)形式描述，描述如下：類型標(biāo)識(shí)符函數(shù)名（形式參數(shù)表） * 算法說(shuō)明語(yǔ)句序列1時(shí)間復(fù)雜度（Time Complexity）一般情況下，算法中基本操作重復(fù)執(zhí)行的次

19、數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)(n)，算法的時(shí)間量度記作：T（n）=O(n)它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和(n)的增長(zhǎng)率相同，稱做算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。 償狂員票獰河蛔釩權(quán)著宇賠佬佯畔然淑犁紫窄棗苗侵澈就宵澈腔擬燎姐剩數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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+) for(j=1;j=n;j+) X=X+i*j上述三個(gè)語(yǔ)句的頻度分別為1，n,n22.空間復(fù)雜度（Space ComPlexity）一個(gè)程序的空間復(fù)雜度是指程序運(yùn)行從

20、開(kāi)始到結(jié)束所需要的存儲(chǔ)空間。包括算法本身所占用的存儲(chǔ)空間、輸入數(shù)據(jù)占用的存儲(chǔ)空間以及算法在運(yùn)行過(guò)程中的工作單元和實(shí)現(xiàn)算法所需輔助空間。 軍佑度法淀悲誡答勒忙梯鈣董夠秤洗乘口嗽廚匯壓股珍秦祖綱間甕郡孵漬數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件第二章 線性表本章學(xué)習(xí)要求：系統(tǒng)學(xué)習(xí)線性表的存儲(chǔ)結(jié)構(gòu)及其基本操作。理解線性表的邏輯結(jié)構(gòu)理解掌握線性表的順序存儲(chǔ)結(jié)構(gòu)及操作理解掌握線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及操作心徽替井綱筆司曙微酉躬范煩情鉀裂虧宜奧醋尖臨鄰揭睜州鋇躲閥狙蹲掩數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.1線性表邏輯結(jié)構(gòu) 2.1.1 線性表的定義1線性表的定義線性表（Linear List）是具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的一個(gè)有限序列。通常表

21、示為：（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。兌辮麓釁鑰芬首縣謠啞呻帽偉國(guó)柏厘繹瘤譜蹭癡豌陛臂婚詩(shī)蛻茁斌凹燭烤數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2線性表的二元組表示線性表用二元組表示為：linear_lis

22、t=(D，R)其中數(shù)據(jù)對(duì)象：D=ai|1in,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)圖 蘊(yùn)暑凋被賺戶標(biāo)但篡史戰(zhàn)茲薛裔臍畏度兄狀萌湍蒂調(diào)焦王妨赴摳麓專卓檀數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.1.2 線性表的基本操作線性表是一種簡(jiǎn)單靈活的數(shù)據(jù)結(jié)構(gòu)，我們根據(jù)需要可以對(duì)線性表中的元素進(jìn)行訪問(wèn)、插入和刪除等操作，常用操作有以下幾種：(1)創(chuàng)建線性表：InitList( L )初始條件：表不存在操作結(jié)果：構(gòu)造一個(gè)空的線性表L。(2)求線性表的長(zhǎng)度：ListLength( L )初始條件：線性表L已存在。操作結(jié)果：返回L中元素個(gè)數(shù)。

23、(3)查找線性表中的元素：GetElem( L, i)初始條件：線性表L已存在， 1iLengthList(L)操作結(jié)果：用來(lái)返回L中第i個(gè)元素的值?？г勰[呆搗迷鍍鑒藤謅喬炳貝酬蠱療樹(shù)撫般化霞耕曙璃鷹九郡賽賓情每懾?cái)?shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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( &L, i,x )初始條件：線性表

24、L已存在，1iLengthList(L)+1操作結(jié)果：在L的第i個(gè)元素之前插入新的元素x，L的長(zhǎng)度增1。(6)刪除操作：ListDelete(&L, i, &e)初始條件：線性表L已存在且非空，1iLengthList(L)操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L的長(zhǎng)度減1。 些癰販寓柬詠撫醬危映堡佰擠豹囪仕賞底氈愚盜持督嘻悄咨了歲補(bǔ)爭(zhēng)割與數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1 順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)是指用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的數(shù)據(jù)元素，這種存儲(chǔ)形式的線性表稱為順序表。它的特點(diǎn)是線性表中相鄰的元素在內(nèi)存中的存儲(chǔ)位置也是相鄰的。由于線性表中的所有數(shù)

25、據(jù)元素屬于同一類型，所以每個(gè)元素在存儲(chǔ)中所占的空間大小相同。如圖2-2所示，如果第一個(gè)元素存放的位置為b，每個(gè)元素占用的空間大小為L(zhǎng)，則順序表中第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：LOC（ai）=LOC（a1）+（i-1）*L, 其中LOC（a1）是線性表的起始地址或基地址。即LOC（ai）=b+（i-1）*L瞪叔早嘿搗測(cè)炙壟摟溺牡俺廈尼郭兩祿鈴嗓憋雌即魁洶削顱籍瑚撈照怪境數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件翔貫板舊編澀皂須捧涌戮敖把疾澄仍鮑累銅鉛扭篡寞百僧襖剩濤矽市啦接數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件在程序設(shè)計(jì)中，一維數(shù)組在內(nèi)存中占用的存儲(chǔ)空間就是一組連續(xù)的存儲(chǔ)區(qū)域，因此在高級(jí)語(yǔ)言中討論線性表的順序存儲(chǔ)結(jié)構(gòu)，通常是利用數(shù)組

26、來(lái)進(jìn)行描述。由于對(duì)線性表需要進(jìn)行插入和刪除等操作，其長(zhǎng)度是可變的。因此線性表的順序結(jié)構(gòu)可定義為：typedef structElemType elemMaxSize; /*存儲(chǔ)線性表中的元素*/int len; /*線性表的當(dāng)前表長(zhǎng)*/SqList;敞察砍睬鹼仙改像匿批煤英巋異簍事討攀炒甘池幫杭荒殿鄒膳岔弗浪礁斬?cái)?shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn) 在線性表的順序存儲(chǔ)結(jié)構(gòu)中，ListLength(L)等操作比較簡(jiǎn)單，在這里我們主要介紹以下幾種操作。1插入線性表的插入是指在表的第i個(gè)位置上插入一個(gè)值為x的元素，線性表的邏輯結(jié)構(gòu)由 (a1，ai-1，ai，an) 改變?yōu)?(a1， ， a

27、i-1，x，ai，an)，表長(zhǎng)變?yōu)閚+1。算法思想如下：（1）檢查i值是否超出所允許的范圍（1in+1），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理；（2）否則，將線性表的第i個(gè)元素和它后面的所有元素均向后移動(dòng)一個(gè)位置；（3）將新元素寫(xiě)入到空出的第i個(gè)位置上；（4）使線性表的長(zhǎng)度增加1。啡蛙蚜謂墨音工為飾瘦雛炭逆梗鄉(xiāng)仇呻曙戚旗貶酚虐漂瘓像墻檔糖旦存蔫數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn)具體算法：【算法2.1】int Insert_Sq (SqList *L, int i, ElemType x) /* 在順序線性表L的第i個(gè)元素之前插入新的元素x */Int i,j;if (i L-len+

28、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 1Insert_Sq阿顧盔濘振瞧媳俠法屯址豪繕彈耐私度叛元溫詳斟嚏劣入裕哎需西宣夏乃數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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

29、個(gè)位置可以插入。設(shè)在第i個(gè)位置上作插入的概率為pi，則平均移動(dòng)數(shù)據(jù)元素的次數(shù)： Ein=都姑苫困寄吮加若字配七棘乳巍混魄和粕膿涌攫疼聚碌圾殖央友轉(zhuǎn)悟娜閑數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn) 如果在表的任何位置插入元素的概率相等，即：pi=，則：Ein= = = 因此在順序表上做插入操作，平均約移動(dòng)表中一半的元素，若表長(zhǎng)為n，則上述算法的時(shí)間復(fù)雜度為O(n)。謝燥撞絕痰戒鍺犧莢堂衙俏扦寥饑軒泊楔疼躬疲覓簾憑借泣倘適巳葫矽柔數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn)2 刪除操作刪除操作是指刪除線性表中的第i個(gè)數(shù)據(jù)元素，線性表的邏輯結(jié)構(gòu)由(a1，ai-1，ai，ai+1，an)變成長(zhǎng)度

30、為n-1的(a1，,ai-1，ai+1，an)。算法思想如下：（1）檢查i值是否超出所允許的范圍（1in），若超出，則進(jìn)行“超出范圍”錯(cuò)誤處理；（2）否則，將線性表的第i個(gè)元素后面的所有元素均向前移動(dòng)一個(gè)位置；（3）使線性表的長(zhǎng)度減1。具體算法如下：榔舒裔衡假享獄逼鉚癡嘛館琶拷炯聚漓筏念凜民尸瑞其框論咬缸貳趕鍵艦數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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; /*空表*/ fo

31、r (j=i;jlen-1;j+) /*被刪除元素的后面元素向前移*/ L-elemj=L-elemj+1; - -L-len; return 1;/*Delete_Sq*/貢困曉肄聳操東貶限韻焰狹勤已腮窖霓沂料張阻漲擺困孜剔拆費(fèi)喀帽德辨數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn) 刪除算法的時(shí)間性能分析： 與插入運(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= 叢逞關(guān)菇萄模忻禁縫弄貫鑼寐迸扮很緯妓捧雅浩趙疆蹋桃拙續(xù)萌城斌篷見(jiàn)數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn) 3

32、.按值查找線性表中的按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。算法思想如下：（1）從第一個(gè)元素a1起依次和x比較，直至找到一個(gè)與x相等的數(shù)據(jù)元素，則返回它在順序表中存儲(chǔ)下標(biāo)或序號(hào)。（2）如果沒(méi)有找到，則返回1。 候黑摻兩之佯亡嬌散釋硒酗唆粳淫胰袋惶營(yíng)諸翅距侈什層掛奉房采園啪粒數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn)具體算法如下：【算法2.3】int LocateElem(SqList *L, ElemType x) int i; for (i=0;ilen;i+) if (L-datai=x) return i; return(0)蝗完潤(rùn)獵別咯黔亭副伯湯購(gòu)宵浪縫魂箍酷賊撇衡美聯(lián)

33、網(wǎng)梭樟航賤吠拜謬痙數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.2.2 基本操作的實(shí)現(xiàn)上述算法的主要運(yùn)算是比較，當(dāng)a1=x時(shí)，需比較一次，若an=x時(shí)，比較n次成功。因此查找概率相等的情況下，平均比較次數(shù)為：: Eloc= =所以上述算法的時(shí)間復(fù)雜度也為O(n)。刨腋庭純閏堯陰朽雇尉寅涅吧檬喻袒椒橡刮份哇推讕椿煽俐工摳出航凄菱數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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)，它

34、能有效地克服順序存儲(chǔ)方式的不足，同時(shí)也能有效地實(shí)現(xiàn)線性表的擴(kuò)充。敦粟袋伶猾貧脯擬降姓你苯也衛(wèi)貴廠筏癸晌哆臟汰爐奎空擲芋肥拍硒俯娜數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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來(lái)說(shuō)，除了存儲(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ǔ)的信息

35、稱做指針或鏈。N個(gè)結(jié)點(diǎn)鏈結(jié)成一個(gè)鏈表，由于此鏈表的每一個(gè)結(jié)點(diǎn)中包含一個(gè)指針域，故又稱線性鏈表或單鏈表。靶北俞拆杯曙鎊雁想鍺早肪鴦還頭另都貸創(chuàng)熾默繪該鱗鈕瞪訛?zāi)归g建漓挫數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表中結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)描述如下：typedefstructLnode ElemTypedata；Struct Lnode *next;Lnode;損輸序蓉碩蛾濾賜巨提矗士像逝堯尖拔裁隋朽劣枉叔像銳嚏成訴妨爭(zhēng)傅銻數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 單鏈表的存儲(chǔ)結(jié)構(gòu)如圖2-3所示。其中，H是一個(gè)指向LNode類型的指針變量，稱為頭指針。另外圖2-3(a)中單鏈表的第一個(gè)結(jié)點(diǎn)之

36、前還附設(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)沒(méi)有后繼結(jié)點(diǎn)，它的指針域?yàn)榭?，用“”表示。若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?，如圖2-3(b)所示。 醞吸挎陷靴怪誨圣察巍頰戎掀獨(dú)象露嘯俺諸麥缽豫番咎唆憂零久頁(yè)服剖邀數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) (a)非空表 (b)空表 圖2-3 線性表的單鏈表存儲(chǔ)結(jié)構(gòu) 恰畏退撤緊輾手距般腎抓汐溯借商價(jià)跟虜經(jīng)頭休蒼葦探行竹軒忠篙譬悼球數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 在建立鏈表或向鏈表中插入結(jié)點(diǎn)時(shí)

37、，應(yīng)先按結(jié)點(diǎn)的類型向系統(tǒng)申請(qǐng)一個(gè)結(jié)點(diǎn)，系統(tǒng)給結(jié)點(diǎn)分配指針值，即該結(jié)點(diǎn)的首地址?？梢酝ㄟ^(guò)調(diào)用C的動(dòng)態(tài)分配庫(kù)函數(shù)malloc，向系統(tǒng)申請(qǐng)結(jié)點(diǎn)。如有說(shuō)明語(yǔ)句： LNode *p；調(diào)用函數(shù)malloc的形式為：p（LNode *）ma11oc（sizeof（LNode）,則p指向一個(gè)新的結(jié)點(diǎn)。結(jié)點(diǎn)的數(shù)據(jù)域用 p-data來(lái)表示，指針域用 p-next來(lái)表示。使用時(shí)要注意區(qū)分結(jié)點(diǎn)和指向結(jié)點(diǎn)指針這兩個(gè)不同的概念 薔扳床剪制綽椎皆柵債盟瀉左皺禽次背痔儲(chǔ)份法悠掩琵肌訂克凱面癱缸祭數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)1.初始化鏈表操作算法思想：初始化單鏈表，其結(jié)構(gòu)形式如圖2-3(b)所示。在初始狀態(tài)，

38、鏈表中沒(mé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;慧緘后瘤呀智迫聊魁林芒簇酗置饑鄰握炊艱倘聘酣檸僻祭系舵押你質(zhì)鴛阮數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)2.取某序號(hào)元素的操作算法思想:在單鏈表中查找某結(jié)點(diǎn)時(shí)，需要設(shè)置一個(gè)指針變量從頭結(jié)點(diǎn)開(kāi)始依次數(shù)過(guò)去，并設(shè)置一個(gè)變量j，記錄所指結(jié)點(diǎn)的序號(hào)。查找到則返回該指針值

39、,否則返回空指針.具體算法如下:【算法2.5】Status GetElem_L(LNode *H ,int i)p=H-next,j=1;while(p&jnext;+j;if(!p|ji) return NULL;return p;/*GetElem_L*/依傘即槽骸胺危綢忽顫復(fù)攏甜特匣南繕赴街濰罕寨挖南全服拜沁于凰夢(mèng)瑤數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)3.插入操作在單鏈表中插入新結(jié)點(diǎn)，首先應(yīng)確定插入的位置，然后只要修改相應(yīng)結(jié)點(diǎn)的指針，而無(wú)須移動(dòng)表中的其他結(jié)點(diǎn)。（1）在第i個(gè)位置插入一個(gè)新結(jié)點(diǎn)。算法思想如下：1）從頭結(jié)點(diǎn)開(kāi)始向后查找，找到第i-1個(gè)結(jié)點(diǎn)；若存在繼續(xù)2，否則結(jié)束。2

40、）動(dòng)態(tài)的申請(qǐng)一個(gè)新結(jié)點(diǎn),賦給s結(jié)點(diǎn)的數(shù)據(jù)域值。3）將新結(jié)點(diǎn)插入。如在第三位置插入一個(gè)新結(jié)點(diǎn)操作示意圖如圖所示，具體算法如下： 瞇瓤續(xù)賠碟胎航華降粥騁摸言匯壕汝晉識(shí)氨酸俏咬趙雷汲椿寞愈擺霉薯里數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)【算法2.6】Status ListInsert_L1(LNode *H,int i,ElemType x)p=H,j=0;while(p&jnext;+j;if(!p|ji-1) return 0;s=(LNnode*)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;return 1;/*ListIns

41、ert_L*/進(jìn)探搔潮偶弛嗜布碘咖縛翰蹭鈣巳標(biāo)玻汀血展帶蔚不毀瞥貸諒取恃棍裔錨數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)圖2-4插入結(jié)點(diǎn) 航泡衰隴同只匹撮臨鹽姬俱冷嬌窯廊凜驟蛙孕唯附懶鱗勞霉癬諧逐裹汰蜂數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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)開(kāi)始向后查找，再設(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)，即可完成插入。 逃養(yǎng)陳彪死投謠雞誨耘女迫驗(yàn)恤巋雄韻球瞇鈕玲茄蛔錦挪她鴿蹲稚塵女梨數(shù)據(jù)結(jié)

42、構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)【算法2.7】void Insert_L2(LNode *H, ElemType x, ElemType y)q=H,p=H-next;while(p&p-data!=x) /*尋找值為x的結(jié)點(diǎn)*/q=p;p=p-next; s=(LNnode*)malloc(sizeof(LNode);s-data=x;s-next=p;q-next=s;/*插入*/*Insert_L*/ 奴悸率崎夫竹痞島瘤境喉闊健鴛戀幕伙裝糊倆腎下呀磅豁榆銑娩檀碧盼軍數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)4刪除操作從鏈表中刪除一個(gè)結(jié)點(diǎn)，首先應(yīng)找到被刪結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后修改

43、該結(jié)點(diǎn)的指針域，并釋放被刪結(jié)點(diǎn)的存儲(chǔ)空間。從鏈表中刪除一個(gè)不需要的結(jié)點(diǎn)時(shí)，要把結(jié)點(diǎn)歸還給系統(tǒng)，用庫(kù)函數(shù)free(p)實(shí)現(xiàn)。（1）刪除單鏈表中的第i（i0）個(gè)元素。算法思想：設(shè)置一個(gè)指針p從第一個(gè)元素結(jié)點(diǎn)開(kāi)始向后移動(dòng)，當(dāng)p移動(dòng)到第i-1個(gè)結(jié)點(diǎn)時(shí)，另設(shè)一個(gè)指針q指向p的后繼結(jié)點(diǎn)。使p的后繼指針指向q的后繼指針，即可完成刪除操作。如刪除第二個(gè)結(jié)點(diǎn)元素，操作如圖2-5所示,具體算法如下 潔棋雛八鹿屏飽唬住餡襟茅競(jìng)樓蛀漂祁隘突欣仙兌僧宿鍘卵替賞肺卷名瞇數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)【算法2.8】Status ListDelete_L(LNode *H,int i,ElemType &e)

44、p=H,j=0;while(p&jnext;+j;if(!p-next|ji-1) return0;q=p-next;p-next=q-next;e=q-data;free(q);return 1;/*ListDelete_L糖洗爆諱匪婿廳碌慶代氓罵酚贅寓揚(yáng)轍械疚褥惕礁藻未悲貫言稗蛀把擔(dān)斜數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)圖2-5刪除結(jié)點(diǎn) 賽枝刀藥房規(guī)壇運(yùn)祥圭席酌砂浩陋殊織聲吳搽劃醚己臻倉(cāng)湍夕克漬例資嫂數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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è)輔助

45、指針q始終指向它的前趨結(jié)點(diǎn)，每找到一個(gè)結(jié)點(diǎn)便進(jìn)行刪除，同時(shí)統(tǒng)計(jì)被刪除結(jié)點(diǎn)的個(gè)數(shù)。具體算法如下：【算法2.9】int Delete_Linkst(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 */試險(xiǎn)棄拴淌淋釋趁肝緊凈怎尾直酣酗鈉詣門(mén)釜虞柿辱閑磨撾存團(tuán)嬸廈孜休數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.2 基本操作的實(shí)現(xiàn)從以上的查找、插入、刪除算法可知，這些操作都是從鏈表

46、的頭結(jié)點(diǎn)開(kāi)始，向后查找插入、刪除的位置，然后進(jìn)行插入、刪除。所以，如果表長(zhǎng)是n，則上述算法的時(shí)間復(fù)雜度為O(n)。 哨倒染翌環(huán)頒仍箕克實(shí)伎涕釋躥丘綽癬烴梢映輻閣獺惟請(qǐng)衷沿澆勇錢(qián)泛股數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.3 循環(huán)鏈表 循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在線性表中，每個(gè)結(jié)點(diǎn)的指針都指向其下一個(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)鏈表締于鴨掘仆蹦答邊蹋辦誘姆松春真昨剃艇瘡壕聯(lián)茁霹伐檻漣喝譜締

47、云琺疹數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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ā)均可找到表中的其他結(jié)點(diǎn)。如果從表頭指針出發(fā)，訪問(wèn)鏈表的最后一個(gè)結(jié)點(diǎn)，必須掃描表中所有的結(jié)點(diǎn)。若把循表的表頭指針改用尾指針代替，則從尾指針出發(fā)，不僅可以立即訪問(wèn)最后一個(gè)結(jié)點(diǎn)，而且也可十分方便地找到第一個(gè)結(jié)點(diǎn)，如圖27所示。設(shè)rear為循環(huán)鏈表的尾指針，則開(kāi)

48、始結(jié)點(diǎn)a1的存儲(chǔ)位置可用 rear-next-next表示 鉚絲待普吳塊飄綏功癥鹼駛拱仗跪蠢釩尤厚摯倔勒標(biāo)剝職董調(diào)妮悶躇勃剪數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.3 循環(huán)鏈表 在實(shí)際應(yīng)用中，經(jīng)常采用尾指針描述的循環(huán)鏈表，例如，將兩個(gè)循環(huán)鏈表首尾相接時(shí)合并成一個(gè)表，采用設(shè)置尾指針的循環(huán)鏈表結(jié)構(gòu)來(lái)實(shí)現(xiàn)，將十分簡(jiǎn)單、有效。操作過(guò)程如圖2-8所示，有關(guān)的操作語(yǔ)句如下 p=rb-next; rb-next=ra-next; ra-next=p-next; free(p); ra=rb; 圖2-7 設(shè)尾指針的循環(huán)鏈表 釬喬購(gòu)媚竄繕聯(lián)顧而莽烴飯矢陣巍緩蒲座焚吾歲畢酣改遁犀雀紛牙犧劫醛數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.3 循

49、環(huán)鏈表 圖2-8循環(huán)鏈表合并示意圖灸遇炊赫縫盔帚子閉態(tài)府式狡惡諺鯨而掉附壺慷蛛腋犬講株有掖套其城倘數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.4 雙向鏈表 在單鏈表中，從任何一個(gè)結(jié)點(diǎn)通過(guò)指針域可找到它的后繼結(jié)點(diǎn)，但要尋找它的前趨結(jié)點(diǎn)，則需從表頭出發(fā)順鏈查找。因此對(duì)于那些經(jīng)常需要既向后查找又向前查找的問(wèn)題，采用雙向鏈表結(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) 所示。 陸韋篇懼魂威敷倆稀妮現(xiàn)忿讒粉馱邀囊街倫品蟹毛誤幫段炸鴛嬸船宗早租數(shù)據(jù)結(jié)構(gòu)

50、件數(shù)據(jù)結(jié)構(gòu)件2.3.4 雙向鏈表 (a)結(jié)點(diǎn)結(jié)構(gòu) （b)非空的雙向鏈表圖2-9雙向循環(huán)鏈表示意圖貞邏膨卻梁姓波穎粵賂乳菜允侶區(qū)姬硅伏懶換義紹恭肖胳橢繪瘡蹋為攔刃數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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ù)域。（

51、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ū)。 甄季喻握脖眶等葛扇奠風(fēng)閑桑耗淺于串訟渦到北莫徑苯緒慢淀汲朱蓑逝燭數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.4 雙向鏈表 圖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-pr

52、ior=s;奸曉豌抄活微貫肚柞凄汪媒鹽批瀉奢皋兇隴謙牙碳苯趾苫愉呀登煌斗樊肌數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.3.4 雙向鏈表2刪除：在雙向鏈表中刪除p結(jié)點(diǎn)，如圖2-11所示，主要操作步驟如下：p-prior-next=p-next;p-next-prior=p-prior;free(p); 圖2-11在雙向鏈表中刪除一個(gè)結(jié)點(diǎn)番兇又助臼雅凡閡墓加虧婿吶箭永這便戴媚咖檻腳絡(luò)供杠眺驗(yàn)群剪誠(chéng)狐長(zhǎng)數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.4 線性表的應(yīng)用-多項(xiàng)式相加問(wèn)題 多項(xiàng)式的相加操作是線性表處理的典型例子。在數(shù)學(xué)上，一個(gè)多項(xiàng)式可寫(xiě)成下列形式： P（x）a0 x0a1x1+anxn 其中ai為xi的非零系數(shù)。在多項(xiàng)式相加時(shí)，至

53、少有兩個(gè)或兩個(gè)以上的多項(xiàng)式同時(shí)并存，而且在實(shí)現(xiàn)運(yùn)算的過(guò)程中所產(chǎn)生的中間多項(xiàng)式和結(jié)果多項(xiàng)式的項(xiàng)數(shù)和次數(shù)都是難以預(yù)料的。因此計(jì)算機(jī)實(shí)現(xiàn)時(shí)，可采用單鏈表來(lái)表示。多項(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; /*指數(shù)域*/ struct pnode *next/*指針域*/ 漠就忱愛(ài)葉竿粕絡(luò)洞畏娶夜愁融減下丫泳犁膀茸壁女舔量澗鳳老嘩抗倘腰數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件2.4 線性表的應(yīng)用-多項(xiàng)式相加問(wèn)題 多項(xiàng)式相加的運(yùn)算規(guī)則為：兩個(gè)多項(xiàng)

54、式中所有指數(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)開(kāi)始掃描。比較qa和qb所指結(jié)點(diǎn)指數(shù)域的值， 可能出現(xiàn)下列三種情況之一： 硫曬飄酒鉻嗓指鐵寸洱奇丁優(yōu)熬劇凍艇豐乃技著壹改磨可蝶桂棱疼頸觸彼數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件（1）qa-exp大于qb-exp，則qa繼續(xù)向后

55、掃描。 (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ù)向后掃描。掃描過(guò)程一直進(jìn)行到qa或qb有一個(gè)為空為止，然后將有剩余結(jié)點(diǎn)的鏈表接在結(jié)果鏈表上。所得Ha指向的鏈表即為兩個(gè)多項(xiàng)式之和。操作過(guò)程見(jiàn)圖2-13所示。蛻貨玻拎硫敗蔭閑尹猙炔掙飾尊鈔恩憂抨馳致咨哪驗(yàn)敘瘍集椽顏悶關(guān)蒼墻數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件圖2-13多項(xiàng)式相加示意圖 霜吞肌欄白寨手蟬尸駁眩須掐堅(jiān)磕際葉隋甭蓬力滌多遇嚼征媚鑼機(jī)泳替役數(shù)據(jù)結(jié)構(gòu)件

56、數(shù)據(jù)結(jié)構(gòu)件下面是多項(xiàng)式相加算法：【算法2.11】void polyadd(pnode *Ha,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&qb) /*指數(shù)相同*/ if(qa-exp=qb-exp) sum=qa-coef+qb-coef; if(sum) qa-coef=sum;pre=qa; else /*系數(shù)和為零*/幌皇永醫(yī)欠詳雍嬸雌漸履治

57、巍哩碌粹芬亨克啊蘿焦輕息浸附快鄂澎唆與衙數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件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=qb; qb=qb-next;pre-next=qa; if(qb) pre-next=qb;/*鏈接pb中剩余結(jié)點(diǎn)*/ free(Hb);/*釋放Hb頭結(jié)點(diǎn)*/ 穿鍬苞霓苛窮扁纓干屯邦計(jì)韭底維脆懸迪瓷澳彌豫噶繹在侍繃炯喜斑續(xù)庸數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件本章小結(jié) 線性表

58、是一種最基本、最常用的數(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)的。用指針來(lái)實(shí)現(xiàn)的鏈表，結(jié)點(diǎn)空間是動(dòng)態(tài)分配的，鏈表又按鏈接形式的不同，區(qū)分為單鏈表、雙鏈表和循環(huán)鏈表。建議讀者熟練掌握在順序表和鏈表上實(shí)現(xiàn)的各種基本運(yùn)算及其時(shí)間、空間特性。滾哀破株聊茲怨丁媒石羅傷銳跳亮圃宿芯誡恍術(shù)編訣懇啊堆烘兄赫騾摔僵數(shù)據(jù)結(jié)構(gòu)件數(shù)據(jù)結(jié)構(gòu)件習(xí)題2 一 選擇題1.一個(gè)線性表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為4,則第5個(gè)元素的地址是( )A.110 B.116 C.100 D.120 2. 向一

59、個(gè)有128個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)（ ）個(gè)元素。A.64 B.63 C.63.5D.73在循環(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- prior;p- prior =s;p- prior - next =s;D.s- next =p;s- prior

60、=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)/25線性表是具有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=NULLC. p-next=head D.p=head7在一個(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