數據結構件課件

1、數據結構頓轉格榜沫劊犬椽偷輪海抬痙蝸蝦盯綠彬敞釩捷署迷剮掂巷猜檄峪妄騁哺數據結構件數據結構件第一章緒論第二章線性表第三章數組和廣義表第四章棧和隊列第五章串第六章樹第七章圖第八章查找第九章排序鱉摻肯刁掄巍軒朵芬訟擰滋掂訓錠聞談谷睛緝蓮殲呀灶殲艷趕保沿灣束唐數據結構件數據結構件第一章 緒論本章學習要求：了解數據結構的研究內容。理解掌握數據結構的基本概念和術語。了解數據元素間的結構關系。理解掌握算法及算法的描述狀喇炊班苯冠掘慶骯漿每肢縮樁匠躊僑液旦虧詩翔窗稀靳鉆幅蕪航碌跪斤數據結構件數據結構件1.1 數據結構的發(fā)展1.1.1數據結構的發(fā)展簡史最早對這一發(fā)展作出杰出貢獻的是D.E.Kunth教授和C.

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

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

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

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

6、體來考慮。一個數據元素可以由若干個數據項組成，數據元素也稱為元素、結點、頂點、記錄。數據對象(Data Object)：具有性質相同的數據元素的集合，是數據的一個子集。如整數數據對象是集合N= 0, 1, 2, 。 賄吾揮截紅暮踞亮埠豎梢秤騁謾結瞄卯敲娥居迂妖刊苯耐酒烙鴻塹氰繃鶴數據結構件數據結構件1.2 數據結構的基本概念和術語 數據類型：是一個值的集合和定義在這個值集合上的一組操作的總稱。數據類型中定義了兩個集合：值的集合和操作集合。其中值的集合定義了該類型數據元素的取值，操作集合定義了該類型數據允許參加的運算，例如C語言中的int類型，取值范圍是-3276832767，主要的運算為加、減

7、、乘、除、取模、乘方等。數據結構(Data Structure)：帶結構的數據元素的集合，描述了一組數據元素及元素間的相互關系。數據元素間的關系包括三個方面：數據的邏輯結構、存儲結構和操作集合。 肩系處返原播霜跌貌抿績菌宇銷關迷焦受絹誹劃煤麓參策獲夷焊款交憾拙數據結構件數據結構件1.2 數據結構的基本概念和術語 數據類型：是一個值的集合和定義在這個值集合上的一組操作的總稱。數據類型中定義了兩個集合：值的集合和操作集合。其中值的集合定義了該類型數據元素的取值，操作集合定義了該類型數據允許參加的運算，例如C語言中的int類型，取值范圍是-3276832767，主要的運算為加、減、乘、除、取模、乘方

8、等。數據結構(Data Structure)：帶結構的數據元素的集合，描述了一組數據元素及元素間的相互關系。數據元素間的關系包括三個方面：數據的邏輯結構、存儲結構和操作集合。 裳躺裂七祝票仟綿尉幼價塌叭涸閩閥懂鰓密閉躥繹效屎睫批酒埃諺立孩訂數據結構件數據結構件1.3 數據的邏輯結構 邏輯結構（logical structure）：是指數據元素之間的邏輯關系，是用戶使用需要建立起來的數據組織形式，是獨立于計算機的。根據數據元素之間的不同關系，有以下四種基本邏輯結構：（1）線性結構：結構中的數據元素之間是一對一的關系。在線性結構中，有且僅有一個開始結點和一個終端結點，除了開始結點和終端結點，其余結

9、點都有且僅有一個直接前趨和一個直接后繼。研八糜番壕騾務跌犧革扛惕簇存袱緝陵敖渤響慮摔湛糊認構欣套細錦潦苑數據結構件數據結構件1.3 數據的邏輯結構 （2）樹狀結構或層次結構：數據元素之間存在著一對多的關系。比如部門之間的隸屬關系、人類社會的父子關系、上下級關系等。在樹形結構中，除根結點之外，每個結點都有唯一直接前趨，所有的結點都可以有0個或多個直接后繼。 芭狐揚抑鈣軍凄央輯粹膝韓橙捻音浚檬痹步店舍踩皺矮烙羌嫉滿串由雞司數據結構件數據結構件1.3 數據的邏輯結構 （3）圖形結構或網狀結構：結構中的數據元素之間存在著多對多的關系。在圖狀結構中，每個結點都可以有多個直接前趨和多個直接后繼。 （4）集

10、合結構：數據元素間除了同屬于一個集合的關系外，無任何其他關系。 襖鉚苫撻卓勃嘴盜狼坷績坦專流楞輪租寇貴廬兄箭德止霸蚌寺謗榷抵鴦然數據結構件數據結構件1.3 數據的邏輯結構 一個數據結構的邏輯結構G可以用二元組來表示：G=（D，R）其中：D是數據元素的集合；R是D上所有數據元素之間關系的集合（表示各元素的前趨、后繼關系）。R中的關系圓括號表示是雙向的，尖括號表示是單向的。有垂灤從輾沛襄竄窗擇擻榆吞啊王弧癥齒光行廖稚押遏蔥拎隅橇韌毗錨膝數據結構件數據結構件例1-4一種數據結構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)表示頂點A到頂點B之間的邊是雙向的，上述的結構關系如圖1-5所示。昭翔商可廄來鋪興滑傭綸蕩伶遍俄襖索鎂悶恨儲紀僥席獅嗣怪搶孔錦鄰河數據結構件數據結構件1.4數據的存儲結構 數據的存儲結構(storage structure)又稱物理結構，是數據的邏輯結構在計算機存儲器中的存儲形式（或稱映象）。 （1）順序存儲結構：借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系，可用一維數組描述。（2）鏈式存儲結構：借助指示元素存儲地址的指針來表示數據元素之間的邏輯關系?？捎弥羔樏枋?，數據元素不一定存在地址的存儲單元，存儲處理的靈活性較大。（3）索引存儲：是在原有存儲數據結構的

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

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

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

15、歲笛蚜屁撫掄湖竭為藕訪開瞻牽片幫耗陡撼簧映吠咱輾罷遷鎂本數據結構件數據結構件1.5.2 算法設計的要求通常設計一個“好”的算法應考慮達到如下目標：（1）正確性：在合理的數據輸入下，能在有限的運行時間內得到正確的結果。（2）可讀性：程序可讀性好，有助于人對算法的理解。（3）健壯性：當輸入的數據非法時，算法應當恰當地作出反映或進行相應處理，而不是產生莫名奇妙的輸出結果。并且，處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。（4）高效性：對同一個問題，執(zhí)行時間越短，算法的效率越高。（5）低存儲量：完成相同的功能，執(zhí)行算法所占用的存儲空間應盡可

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

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

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

19、數是問題規(guī)模n的某個函數(n)，算法的時間量度記作：T（n）=O(n)它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和(n)的增長率相同，稱做算法的漸近時間復雜度，簡稱時間復雜度。 償狂員票獰河蛔釩權著宇賠佬佯畔然淑犁紫窄棗苗侵澈就宵澈腔擬燎姐剩數據結構件數據結構件1.5.4 算法效率的評價 例1-5在下列的三個程序中 (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上述三個語句的頻度分別為1，n,n22.空間復雜度（Space ComPlexity）一個程序的空間復雜度是指程序運行從

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

21、示為：（a1，a2， ai，ai+1 an）其中n為線性表的長度，n0；當n=0時表示一個空表。線性表相鄰元素之間存在著順序關系。a1叫表頭元素，an叫表尾元素。除第一個和最后一個元素外，每個元素都只有一個前趨和一個直接后繼。ai-1稱為ai的直接前趨結點，ai+1稱為ai的直接后繼結點。表中的元素可以是一個數，也可以是由多個數據項組成的復雜信息，但線性表中的元素必須屬于同一數據對象。例如英文字母（A，B，.Y，Z）和在緒論中引入的學生成績表表11。兌辮麓釁鑰芬首縣謠啞呻帽偉國柏厘繹瘤譜蹭癡豌陛臂婚詩蛻茁斌凹燭烤數據結構件數據結構件2線性表的二元組表示線性表用二元組表示為：linear_lis

22、t=(D，R)其中數據對象：D=ai|1in,n 0, aiElemType數據關系：R=r，r= |1in-1，對應的邏輯結構圖如圖2-1所示： 圖2-1線性表的邏輯結構圖 蘊暑凋被賺戶標但篡史戰(zhàn)茲薛裔臍畏度兄狀萌湍蒂調焦王妨赴摳麓專卓檀數據結構件數據結構件2.1.2 線性表的基本操作線性表是一種簡單靈活的數據結構，我們根據需要可以對線性表中的元素進行訪問、插入和刪除等操作，常用操作有以下幾種：(1)創(chuàng)建線性表：InitList( L )初始條件：表不存在操作結果：構造一個空的線性表L。(2)求線性表的長度：ListLength( L )初始條件：線性表L已存在。操作結果：返回L中元素個數。

23、(3)查找線性表中的元素：GetElem( L, i)初始條件：線性表L已存在， 1iLengthList(L)操作結果：用來返回L中第i個元素的值?？г勰[呆搗迷鍍鑒藤謅喬炳貝酬蠱療樹撫般化霞耕曙璃鷹九郡賽賓情每懾數據結構件數據結構件2.1.2 線性表的基本操作(4)查找線性表中元素的位置：LocateElem( L, x )初始條件：線性表L已存在 操作結果：返回L中查找值為x的數據元素，若查找成功，則返回值為x的那個元素在L中首次出現的的序號或地址，否則，在L中未找到值為X的數據元素，則返回值為特定值，表示查找失敗。(5)插入操作：ListInsert( &L, i,x )初始條件：線性表

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

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

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

27、i-1，x，ai，an)，表長變?yōu)閚+1。算法思想如下：（1）檢查i值是否超出所允許的范圍（1in+1），若超出，則進行“超出范圍”錯誤處理；（2）否則，將線性表的第i個元素和它后面的所有元素均向后移動一個位置；（3）將新元素寫入到空出的第i個位置上；（4）使線性表的長度增加1。啡蛙蚜謂墨音工為飾瘦雛炭逆梗鄉(xiāng)仇呻曙戚旗貶酚虐漂瘓像墻檔糖旦存蔫數據結構件數據結構件2.2.2 基本操作的實現具體算法：【算法2.1】int Insert_Sq (SqList *L, int i, ElemType x) /* 在順序線性表L的第i個元素之前插入新的元素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阿顧盔濘振瞧媳俠法屯址豪繕彈耐私度叛元溫詳斟嚏劣入裕哎需西宣夏乃數據結構件數據結構件2.2.2 基本操作的實現 插入算法的時間性能分析：順序表上的插入運算，時間主要消耗在數據的移動上，在第i個位置上插入x，從an到ai都要向下移動一個位置，共需要移動n-il個元素，而i的取值范圍為：1in+1，即n+1

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

30、為n-1的(a1，,ai-1，ai+1，an)。算法思想如下：（1）檢查i值是否超出所允許的范圍（1in），若超出，則進行“超出范圍”錯誤處理；（2）否則，將線性表的第i個元素后面的所有元素均向前移動一個位置；（3）使線性表的長度減1。具體算法如下：榔舒裔衡假享獄逼鉚癡嘛館琶拷炯聚漓筏念凜民尸瑞其框論咬缸貳趕鍵艦數據結構件數據結構件2.2.2 基本操作的實現【算法2.2】int Delete_Sq(SqList *L,int i)/*刪除線性表中第i個元素*/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*/貢困曉肄聳操東貶限韻焰狹勤已腮窖霓沂料張阻漲擺困孜剔拆費喀帽德辨數據結構件數據結構件2.2.2 基本操作的實現 刪除算法的時間性能分析： 與插入運算相同，其時間主要消耗在數據的移動上，刪除第i個元素時，其后面的元素ai1到an都要向前移動一個位置，共需要移動n-i個元素，則平均移動數據元素的次數： Edel= 叢逞關菇萄模忻禁縫弄貫鑼寐迸扮很緯妓捧雅浩趙疆蹋桃拙續(xù)萌城斌篷見數據結構件數據結構件2.2.2 基本操作的實現 3

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

33、網梭樟航賤吠拜謬痙數據結構件數據結構件2.2.2 基本操作的實現上述算法的主要運算是比較，當a1=x時，需比較一次，若an=x時，比較n次成功。因此查找概率相等的情況下，平均比較次數為：: Eloc= =所以上述算法的時間復雜度也為O(n)。刨腋庭純閏堯陰朽雇尉寅涅吧檬喻袒椒橡刮份哇推讕椿煽俐工摳出航凄菱數據結構件數據結構件2.3線性表的鏈式存儲結構 采用順序存儲方式的線性表，內存的存儲密度高，可以節(jié)約存儲空間，并可以隨機地存取結點，但是插入和刪除操作時往往需要移動大量的數據元素，并且要預先分配空間，并要按最大空間分配，因此存儲空間得不到充分的利用，從而影響了運行效率。線性表的鏈式存儲結構，它

34、能有效地克服順序存儲方式的不足，同時也能有效地實現線性表的擴充。敦粟袋伶猾貧脯擬降姓你苯也衛(wèi)貴廠筏癸晌哆臟汰爐奎空擲芋肥拍硒俯娜數據結構件數據結構件2.3.1 單鏈表 線性表的鏈式存儲結構是用一組地址任意的存儲單元存放線性表中的數據元素。為了表示每個數據元素ai與其直接后繼數據元素ai+1之間的邏輯關系，對數據元素ai來說，除了存儲其本身的值之外，還必須有一個指示該元素直接后繼存儲位置的信息，即指出后繼元素的存儲位置。這兩部分信息組成數據元素ai的存儲映像，稱為結點（node）。每個結點包括兩個域：一個域存儲數據元素信息，稱為數據域；另一個存儲直接后繼存儲位置的域稱為指針域。指針域中存儲的信息

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

36、前還附設一個結點，稱之為頭結點，頭結點的數據域可以不存儲任何信息，也可存儲如線性表的長度等附加信息，單鏈表的頭指針指向頭結點，頭結點的指針域指向第一個結點的指針，由于最后一個結點沒有后繼結點，它的指針域為空，用“”表示。若線性表為空表，則頭結點的指針域為“空”，如圖2-3(b)所示。 醞吸挎陷靴怪誨圣察巍頰戎掀獨象露嘯俺諸麥缽豫番咎唆憂零久頁服剖邀數據結構件數據結構件2.3線性表的鏈式存儲結構 (a)非空表 (b)空表 圖2-3 線性表的單鏈表存儲結構 恰畏退撤緊輾手距般腎抓汐溯借商價跟虜經頭休蒼葦探行竹軒忠篙譬悼球數據結構件數據結構件2.3線性表的鏈式存儲結構 在建立鏈表或向鏈表中插入結點時

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

38、鏈表中沒有元素結點，只有一個頭結點，因此需要動態(tài)產生頭結點，并將其后繼指針置為空。算法如下：【算法2.4】Lnode Init_L()Lnode H;if (H=(LNnode*)malloc(sizeof(LNode) /*頭結點*/H-next=NULL;return 1; /*設置后繼指針為空*/else return 0;慧緘后瘤呀智迫聊魁林芒簇酗置饑鄰握炊艱倘聘酣檸僻祭系舵押你質鴛阮數據結構件數據結構件2.3.2 基本操作的實現2.取某序號元素的操作算法思想:在單鏈表中查找某結點時，需要設置一個指針變量從頭結點開始依次數過去，并設置一個變量j，記錄所指結點的序號。查找到則返回該指針值

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*/依傘即槽骸胺危綢忽顫復攏甜特匣南繕赴街濰罕寨挖南全服拜沁于凰夢瑤數據結構件數據結構件2.3.2 基本操作的實現3.插入操作在單鏈表中插入新結點，首先應確定插入的位置，然后只要修改相應結點的指針，而無須移動表中的其他結點。（1）在第i個位置插入一個新結點。算法思想如下：1）從頭結點開始向后查找，找到第i-1個結點；若存在繼續(xù)2，否則結束。2

40、）動態(tài)的申請一個新結點,賦給s結點的數據域值。3）將新結點插入。如在第三位置插入一個新結點操作示意圖如圖所示，具體算法如下： 瞇瓤續(xù)賠碟胎航華降粥騁摸言匯壕汝晉識氨酸俏咬趙雷汲椿寞愈擺霉薯里數據結構件數據結構件2.3.2 基本操作的實現【算法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*/進探搔潮偶弛嗜布碘咖縛翰蹭鈣巳標玻汀血展帶蔚不毀瞥貸諒取恃棍裔錨數據結構件數據結構件2.3.2 基本操作的實現圖2-4插入結點 航泡衰隴同只匹撮臨鹽姬俱冷嬌窯廊凜驟蛙孕唯附懶鱗勞霉癬諧逐裹汰蜂數據結構件數據結構件2.3.2 基本操作的實現（2）在鏈表中值為x的結點前插入一個值為y的新結點。如果x值不存在，則把新結點插入在表尾。算法思想：設置一個指針p從第一個元素結點開始向后查找，再設一個指針q指向p的前趨結點。當指針指向x結點，便在q結點后插入；如果值為x的結點不在鏈表，此時指針正好指向尾結點，即可完成插入。 逃養(yǎng)陳彪死投謠雞誨耘女迫驗恤巋雄韻球瞇鈕玲茄蛔錦挪她鴿蹲稚塵女梨數據結

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

43、該結點的指針域，并釋放被刪結點的存儲空間。從鏈表中刪除一個不需要的結點時，要把結點歸還給系統，用庫函數free(p)實現。（1）刪除單鏈表中的第i（i0）個元素。算法思想：設置一個指針p從第一個元素結點開始向后移動，當p移動到第i-1個結點時，另設一個指針q指向p的后繼結點。使p的后繼指針指向q的后繼指針，即可完成刪除操作。如刪除第二個結點元素，操作如圖2-5所示,具體算法如下 潔棋雛八鹿屏飽唬住餡襟茅競樓蛀漂祁隘突欣仙兌僧宿鍘卵替賞肺卷名瞇數據結構件數據結構件2.3.2 基本操作的實現【算法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糖洗爆諱匪婿廳碌慶代氓罵酚贅寓揚轍械疚褥惕礁藻未悲貫言稗蛀把擔斜數據結構件數據結構件2.3.2 基本操作的實現圖2-5刪除結點 賽枝刀藥房規(guī)壇運祥圭席酌砂浩陋殊織聲吳搽劃醚己臻倉湍夕克漬例資嫂數據結構件數據結構件2.3.2 基本操作的實現(2)刪除鏈表中所有值為x的結點，并返回值為x的結點的個數。算法思想：操作時設指針p從第一個元素結點起逐一查找值為x的結點，并設一個輔助

45、指針q始終指向它的前趨結點，每找到一個結點便進行刪除，同時統計被刪除結點的個數。具體算法如下：【算法2.9】int Delete_Linkst(LNode *H,ELEMTP X)q=H;count=0;while (q-next) /*遍歷整個鏈表*/p=q-next;if (p-data=x)q-next=p-next;free(p);+count;else q=p;return count;/* delete_Linkst */試險棄拴淌淋釋趁肝緊凈怎尾直酣酗鈉詣門釜虞柿辱閑磨撾存團嬸廈孜休數據結構件數據結構件2.3.2 基本操作的實現從以上的查找、插入、刪除算法可知，這些操作都是從鏈表

46、的頭結點開始，向后查找插入、刪除的位置，然后進行插入、刪除。所以，如果表長是n，則上述算法的時間復雜度為O(n)。 哨倒染翌環(huán)頒仍箕克實伎涕釋躥丘綽癬烴梢映輻閣獺惟請衷沿澆勇錢泛股數據結構件數據結構件2.3.3 循環(huán)鏈表 循環(huán)鏈表是另一種形式的鏈式存儲結構。在線性表中，每個結點的指針都指向其下一個結點，最后一個結點的指針為“空”，不指向任何地方，只表示鏈表的結束。若把這種結構修改一下，使其最后一個結點的指針回指向第一個結點，這樣就形成了一個環(huán)，這種形式的鏈表就叫做循環(huán)鏈表。如圖2-6所示。 (a)非空表 (b)空表 圖2-6單向循環(huán)鏈表締于鴨掘仆蹦答邊蹋辦誘姆松春真昨剃艇瘡壕聯茁霹伐檻漣喝譜締

47、云琺疹數據結構件數據結構件2.3.3 循環(huán)鏈表 循環(huán)單鏈表的操作與線性表類似，只是有關表尾、表空的判定條件不同。在采用頭指針描述的循環(huán)鏈表中，空表的條件是head-next=head，指針p到達表尾的條件是 p-next=head。因此循環(huán)鏈表的插入、刪除、建立、查找等操作只需在線性鏈表的算法上稍加修改即可。 在循環(huán)鏈表結構中從表中任一結點出發(fā)均可找到表中的其他結點。如果從表頭指針出發(fā)，訪問鏈表的最后一個結點，必須掃描表中所有的結點。若把循表的表頭指針改用尾指針代替，則從尾指針出發(fā)，不僅可以立即訪問最后一個結點，而且也可十分方便地找到第一個結點，如圖27所示。設rear為循環(huán)鏈表的尾指針，則開

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

49、環(huán)鏈表 圖2-8循環(huán)鏈表合并示意圖灸遇炊赫縫盔帚子閉態(tài)府式狡惡諺鯨而掉附壺慷蛛腋犬講株有掖套其城倘數據結構件數據結構件2.3.4 雙向鏈表 在單鏈表中，從任何一個結點通過指針域可找到它的后繼結點，但要尋找它的前趨結點，則需從表頭出發(fā)順鏈查找。因此對于那些經常需要既向后查找又向前查找的問題，采用雙向鏈表結構，將會更方便。 在雙向鏈表結構中，每一個結點除了數據域外，還包括兩個指針域，一個指針指向該結點的后繼結點，另一個指針指向它的前趨結點。結點結構如圖2-9(a)所示，雙向鏈表也可以是循環(huán)表，其結構如圖2-10(b) 所示。 陸韋篇懼魂威敷倆稀妮現忿讒粉馱邀囊街倫品蟹毛誤幫段炸鴛嬸船宗早租數據結構

50、件數據結構件2.3.4 雙向鏈表 (a)結點結構 （b)非空的雙向鏈表圖2-9雙向循環(huán)鏈表示意圖貞邏膨卻梁姓波穎粵賂乳菜允侶區(qū)姬硅伏懶換義紹恭肖胳橢繪瘡蹋為攔刃數據結構件數據結構件2.3.4 雙向鏈表 雙向鏈表的結點結構可描述如下：typedef struct dunode ElemType data; struct dunode *prior,*next;Dunode;雙向鏈表由于可以從兩個方向搜索某個結點，這使得鏈表的某些操作變得比較簡單，本節(jié)主要介紹以下幾種操作：1插入在雙向鏈表的指定結點p之前插入一個新的結點。如圖2-10所示，算法思想：（1）生成一個新結點s，將值x賦給s的數據域。（

51、2）將p的前驅結點指針作為s的前驅結點指針。（3）p作為新結點的直接后繼。（4）s作為結點的直接前驅的后繼。（5）s作為p結點新的直接前驅。 甄季喻握脖眶等葛扇奠風閑桑耗淺于串訟渦到北莫徑苯緒慢淀汲朱蓑逝燭數據結構件數據結構件2.3.4 雙向鏈表 圖2-10在雙向鏈表中插入一個結點 具體算法如下：【算法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;奸曉豌抄活微貫肚柞凄汪媒鹽批瀉奢皋兇隴謙牙碳苯趾苫愉呀登煌斗樊肌數據結構件數據結構件2.3.4 雙向鏈表2刪除：在雙向鏈表中刪除p結點，如圖2-11所示，主要操作步驟如下：p-prior-next=p-next;p-next-prior=p-prior;free(p); 圖2-11在雙向鏈表中刪除一個結點番兇又助臼雅凡閡墓加虧婿吶箭永這便戴媚咖檻腳絡供杠眺驗群剪誠狐長數據結構件數據結構件2.4 線性表的應用-多項式相加問題 多項式的相加操作是線性表處理的典型例子。在數學上，一個多項式可寫成下列形式： P（x）a0 x0a1x1+anxn 其中ai為xi的非零系數。在多項式相加時，至

53、少有兩個或兩個以上的多項式同時并存，而且在實現運算的過程中所產生的中間多項式和結果多項式的項數和次數都是難以預料的。因此計算機實現時，可采用單鏈表來表示。多項式中的每一項為單鏈表中的一個結點，每個結點包含三個域：系數域、指數域和指針域，其形式如下： coefexpnext結點結構描述為： type struct pnode int coef;/*系數域*/ int exp; /*指數域*/ struct pnode *next/*指針域*/ 漠就忱愛葉竿粕絡洞畏娶夜愁融減下丫泳犁膀茸壁女舔量澗鳳老嘩抗倘腰數據結構件數據結構件2.4 線性表的應用-多項式相加問題 多項式相加的運算規(guī)則為：兩個多項

54、式中所有指數相同的項，對應系數相加，若和不為零，則構成“和多項式”中的一項，否則，“和多項式”中就去掉這一指數項，所有指數不同的項均復制到“和多項式”中。如對于多項式A(x)=5x5+8x4+4x2-8，B(x)=6x10+4x5-4x2。實現時，可采用另建多項式的方法，也可以把一個多項式歸并到另一個多項式中去的方法。這里介紹后一種方法。算法思想：首先設兩個指針qa和qb分別從多項式的首項開始掃描。比較qa和qb所指結點指數域的值， 可能出現下列三種情況之一： 硫曬飄酒鉻嗓指鐵寸洱奇丁優(yōu)熬劇凍艇豐乃技著壹改磨可蝶桂棱疼頸觸彼數據結構件數據結構件（1）qa-exp大于qb-exp，則qa繼續(xù)向后

55、掃描。 (2)qa-exp等于qb-exp ，則將其系數相加。若相加結果不為零，將結果放入qacoef中，否則同時刪除qa和qb所指結點。然后qa、qb繼續(xù)向后掃描。（3）qa-exp小于qb-exp，則將qb所指結點插入qa所指結點之前，然后qa、qb繼續(xù)向后掃描。掃描過程一直進行到qa或qb有一個為空為止，然后將有剩余結點的鏈表接在結果鏈表上。所得Ha指向的鏈表即為兩個多項式之和。操作過程見圖2-13所示。蛻貨玻拎硫敗蔭閑尹猙炔掙飾尊鈔恩憂抨馳致咨哪驗敘瘍集椽顏悶關蒼墻數據結構件數據結構件圖2-13多項式相加示意圖 霜吞肌欄白寨手蟬尸駁眩須掐堅磕際葉隋甭蓬力滌多遇嚼征媚鑼機泳替役數據結構件

56、數據結構件下面是多項式相加算法：【算法2.11】void polyadd(pnode *Ha,pnode *Hb) /* 以Ha和Hb為頭指針的單鏈表分別表示兩個多項式，實現Ha=Ha+Hb*/pnode *pre,*qa,*qb,*q;int sum; pre=Ha; /*pre始終指向當肖和多項式的最后一個結點*/ qa=Ha-next; qb=Hb-next; while(qa&qb) /*指數相同*/ if(qa-exp=qb-exp) sum=qa-coef+qb-coef; if(sum) qa-coef=sum;pre=qa; else /*系數和為零*/幌皇永醫(yī)欠詳雍嬸雌漸履治

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

58、是一種最基本、最常用的數據結構。本章主要介紹了線性表的定義、運算和線性表的兩種存儲結構順序表和鏈表，以及在這兩種存化結構上實現的基本運算。 順序表是用數組實現的，鏈表是用指針實現的。用指針來實現的鏈表，結點空間是動態(tài)分配的，鏈表又按鏈接形式的不同，區(qū)分為單鏈表、雙鏈表和循環(huán)鏈表。建議讀者熟練掌握在順序表和鏈表上實現的各種基本運算及其時間、空間特性。滾哀破株聊茲怨丁媒石羅傷銳跳亮圃宿芯誡恍術編訣懇啊堆烘兄赫騾摔僵數據結構件數據結構件習題2 一 選擇題1.一個線性表第一個元素的存儲地址是100,每個元素的長度為4,則第5個元素的地址是( )A.110 B.116 C.100 D.120 2. 向一

59、個有128個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動（ ）個元素。A.64 B.63 C.63.5D.73在循環(huán)雙鏈表的p所指接點之前插入s所指接點的操作是 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從一個具有n個結點的單鏈表中查找其值等于x結點時，在查找成功的情況下，需平均比較（ ）個結點。A.n B.n/2 C.(n-1)/2 D.(n+1)/25線性表是具有n個（ ）的有限序列（n0） A.表元素 B.字符 C.數據元素 D.數據項6非空的循環(huán)單鏈表head的尾結點（由P指向）滿足A. p-next=NULL B. p=NULLC. p-next=head D.p=head7在一個單鏈表中已知q所指的結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執(zhí)行( )A. s-next=p-next;p