線性表是最很簡(jiǎn)單也是最重要的數(shù)據(jù)結(jié)構(gòu)

1、第2章 線性表 概述 線性表是最很簡(jiǎn)單也是最重要的數(shù)據(jù)結(jié)構(gòu)， 它是線性結(jié)構(gòu)。所以我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)從線 性表開(kāi)始。從本章開(kāi)始到第四章都是討論線 性。是整個(gè)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ) 按邏輯結(jié)構(gòu) 、存儲(chǔ)結(jié)構(gòu)、算法設(shè)計(jì)這三個(gè)順 序進(jìn)行分析。 2.1線性表的邏輯結(jié)構(gòu) 線性表（Linear List）是由n（n0）個(gè)數(shù)據(jù)元素（結(jié) 點(diǎn)）a1，a2，an組成的有限序列。 數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度（n=0時(shí)稱為空 表）。 將非空的線性表（n0） 記作：（a1，a2，an） 數(shù)據(jù)元素ai（1in）只是個(gè)抽象符號(hào)，其具體含義 在不同情況下可以不同。 線性表的邏輯結(jié)構(gòu)圖示 a1aian 線性表的例子 【例1】英文字母表（

2、A，B，Z）是線性表，表中每個(gè)字 母是一個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)） 【例2】一副撲克牌的點(diǎn)數(shù)（2，3，10，J，Q，K，A）也 是一個(gè)線性表，其中數(shù)據(jù)元素是每張牌的點(diǎn)數(shù)和花色 【例3】學(xué)生成績(jī)表（見(jiàn)概論中表1.1）中，每個(gè)學(xué)生及其成績(jī) 是一個(gè)數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號(hào)、姓名、各科成績(jī)及 平均成績(jī)等數(shù)據(jù)項(xiàng)組成。 線性表的特征 1.有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a1，沒(méi)有直接前趨， 有且僅有一個(gè)直接后繼a2； 2. 有且僅有一個(gè)終結(jié)結(jié)點(diǎn)an，沒(méi)有直接后繼， 有且僅有一個(gè)直接前趨an-1； 3. 其余的內(nèi)部結(jié)點(diǎn)ai（2in-1）都有且僅有一 個(gè)直接前趨ai-1和一個(gè)ai+1。 常見(jiàn)的線性表的基本運(yùn)算常見(jiàn)的線性表的基

3、本運(yùn)算 常見(jiàn)的基本運(yùn)算有：初始化，求表長(zhǎng)，求第i個(gè)結(jié)點(diǎn)， 查找，插入和刪除等操作。為了盡可能地比較準(zhǔn)確 地描述些運(yùn)算過(guò)程，我們采用類似于函數(shù)的形式對(duì) 它進(jìn)行描述。 這些基本運(yùn)算并不是憑空想出來(lái)，而是根據(jù)實(shí)際應(yīng) 用總結(jié)出來(lái)的。 線性表的ADT表示 ADT LinearList 數(shù)據(jù)元素:D=ai| aiD0,i=1,2,3n,n0,D0某一數(shù)據(jù)對(duì) 象 邏輯結(jié)構(gòu):R=, ai, ai+1 D0,i=1,2,n-1 基本操作: 1 InitList（L） 操作前提：操作前提：L為一個(gè)未初始化的線性表。為一個(gè)未初始化的線性表。 操作結(jié)果：將操作結(jié)果：將L初始化為空表。初始化為空表。 構(gòu)造一個(gè)空的線性表

4、L，即表的初始化。 2. DestroyList(L) 操作前提：線性表L已存在。 操作結(jié)果：將L銷毀。 3. ClearList(L) 操作前提：線性表L已存在。 操作結(jié)果：將L置空 4. IsEmptyList(L) 判斷L是否為空表。如為空返回true，否則返 回faslse 前提：L已存在， 5. ListLength(L) 求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長(zhǎng)。 6. Locate(L,e) 確定元素e在線性表L中的位置。（與書(shū)上不 同） 在L中查找值為x 的結(jié)點(diǎn)，并返回該結(jié)點(diǎn)在L 中的位置。若L中有多個(gè)結(jié)點(diǎn)的值和x 相同， 則返回首次找到的結(jié)點(diǎn)位置；若L中沒(méi)有結(jié)點(diǎn) 的值為x ，則返回一

5、個(gè)特殊值表示查找失敗 7. GetData(L,i) 操作前提：表L已存在，且i值 合法，返 回線性表L中第i個(gè)元素的值。 8. InsList(L,i,e) 在線性表L的第i個(gè)位置上插入一個(gè)元素e，i+1， n的結(jié)點(diǎn)變?yōu)榫幪?hào)為i+1，i+2，n+1的結(jié)點(diǎn)。這 里1in+1，而n是原表L的長(zhǎng)度。插入后，表L的長(zhǎng) 度加1。 9. DeleteList（L,i,e） 刪除線性表L的第i個(gè)結(jié)點(diǎn)，使得原編號(hào)為i+1， i+2，n的結(jié)點(diǎn)變成編號(hào)為i，i+1，n-1的結(jié) 點(diǎn)。這里1in，而n是原表L的長(zhǎng)度。刪除后表L的 長(zhǎng)度減1。并且用e返回這個(gè)刪除元素的值。 長(zhǎng)度減1. ADT LinearList 說(shuō)

6、明 這些操作只是從邏輯結(jié)構(gòu)的角度來(lái)討論的， 主要用來(lái)說(shuō)明這些運(yùn)算的功能，是“做什 么”,至于如何實(shí)現(xiàn)，則要等到討論存儲(chǔ)結(jié)構(gòu) 后才考慮。 2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 概述 順序表 順序表的算法實(shí)現(xiàn) 2.2.1. 概述 簡(jiǎn)單來(lái)說(shuō)了， 本節(jié)就是討論一維數(shù)組的使用。 這在C語(yǔ)言中已經(jīng)詳細(xì)討論過(guò)。 2.2.2. 順序表 1.定義 2.存儲(chǔ)地址公式 3.特點(diǎn) 2.2.1順序表 (1)順序存儲(chǔ)方法 即把線性表的結(jié)點(diǎn)按邏輯次序依次存放在一 組地址連續(xù)的存儲(chǔ)單元里的方法 (2)(2) 順序表（Sequential List） 用順序存儲(chǔ)方法存儲(chǔ)的線性表簡(jiǎn)稱為順序表 （Sequential List）。 內(nèi)存表

7、示 a1,a2,a3,.,ai,.,an 每個(gè)結(jié)點(diǎn)占C個(gè)存儲(chǔ)單元。 a1 . . ai . . an 2. 結(jié)點(diǎn)結(jié)點(diǎn)ai 的存儲(chǔ)地址的存儲(chǔ)地址 設(shè)線性表中所有結(jié)點(diǎn)的類型相同，則每個(gè)結(jié)點(diǎn)所占用存 儲(chǔ)空間大小亦相同。假設(shè)表中每個(gè)結(jié)點(diǎn)占用c個(gè)存儲(chǔ)單元， 其中第一個(gè)單元的存儲(chǔ)地址則是該結(jié)點(diǎn)的存儲(chǔ)地址，并 設(shè)表中開(kāi)始結(jié)點(diǎn)a1的存儲(chǔ)地址（簡(jiǎn)稱為基地址）是LOC （a1），那么結(jié)點(diǎn)ai的存儲(chǔ)地址LOC（ai）可通過(guò)下式計(jì) 算： LOC（ai）= LOC（a1）+（i-1）*c （1in） 思考題 int a10, a2= a3+a5;為什么我們?cè)诔绦蛑幸脭?shù) 組元素時(shí)，沒(méi)有應(yīng)用此地址公式？ 順序表的特點(diǎn) 在

8、順序表中，每個(gè)結(jié)點(diǎn)ai的存儲(chǔ)地址是該結(jié)點(diǎn)在表 中的位置i的線性函數(shù)。只要知道基地址和每個(gè)結(jié)點(diǎn) 的大小，就可在相同時(shí)間內(nèi)求出任一結(jié)點(diǎn)的存儲(chǔ)地 址。是一種隨機(jī)存取結(jié)構(gòu)。隨機(jī)存取結(jié)構(gòu)。 順序表是用向量實(shí)現(xiàn)的線性表，向量的下標(biāo)可以看 作結(jié)點(diǎn)的相對(duì)地址。因此順序表的的特點(diǎn)是邏輯上 相鄰的結(jié)點(diǎn)其物理位置亦相鄰。 4. 存儲(chǔ)結(jié)構(gòu) #define MaxSize 100 /表空間的大小可根據(jù)實(shí)際需要而定，這里假設(shè)為100 typedef struct StudInfo STUDINFO; typedef int ElemType; /DataType的類型可根據(jù)實(shí)際情況而定，這里假設(shè)為int typedef

9、struct ElemType elemMaxSize；/向量data用于存放表結(jié)點(diǎn) int last； /最后一個(gè)元素的下標(biāo) SeqList; ElemType是什么？ 根據(jù)實(shí)際需要，把某個(gè)數(shù)據(jù)類型定義為 ElemType，而且針對(duì)不同的數(shù)據(jù)類型，在程 序上機(jī)測(cè)試，要對(duì)程序做相應(yīng)的修改。 序號(hào)與下標(biāo)(index)關(guān)系 第1個(gè)元素的下標(biāo)為0 第2個(gè)元素的下標(biāo)為1 . 第last+1個(gè)元素的下標(biāo)為last 表的長(zhǎng)度與last的關(guān)系 表的長(zhǎng)度=last+1 2.2.3算法實(shí)現(xiàn) 定義了存儲(chǔ)結(jié)構(gòu)后，就可以討論運(yùn)算實(shí)現(xiàn)。 插入操作 刪除操作 查找操作 1. 插入操作 插入運(yùn)算的邏輯描述插入運(yùn)算的邏輯描述

10、 線性表的插入運(yùn)算是指在表的第線性表的插入運(yùn)算是指在表的第i（1in+1） 個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，使長(zhǎng)度為使長(zhǎng)度為n的線性的線性 表：表： （a1，ai-1，ai，an） 變成長(zhǎng)度為變成長(zhǎng)度為n+1的線性表：的線性表： （a1，ai-1，e，ai，an） 要考慮兩種極端情況要考慮兩種極端情況： 當(dāng)線性表已滿時(shí)，怎么辦？當(dāng)線性表已滿時(shí)，怎么辦？ 當(dāng)插入位置不正確怎么辦？當(dāng)插入位置不正確怎么辦？ 插入過(guò)程說(shuō)明 在順序表中，結(jié)點(diǎn)的物理順序必須和結(jié)點(diǎn)的邏輯順 序保持一致，因此必須將表中位置為n ，n-1，i 上的結(jié)點(diǎn)，依次后移到位置n+1，n，i+1上， 空出第i個(gè)位置，

11、然后在該位置上插入新結(jié)點(diǎn)x。僅 當(dāng)插入位置i=n+1時(shí)，才無(wú)須移動(dòng)結(jié)點(diǎn)，直接將e插 入表的末尾。 插入算法 #define OK 1 #define ERROR 0 void InsertList(SeqList *L，ElemType e，int i) /將新結(jié)點(diǎn) x插入L所指的順序表的第i個(gè)結(jié)點(diǎn)的位置 int j; if (iL-last+2) printf(“position error”);/非法位置，退出運(yùn)行 return ERROR; if (L-last=MaxSize) printf(“Over flown”); return ERROR; for(k=L-last;k=i-1

12、;k-) L-elemk+1=L-elemk; /結(jié)點(diǎn)后移 L-elemi-1=e; /插入x L-last+; /表長(zhǎng)加1 return OK; /插入算法結(jié)束 算法性能分析 最好情況，插入到表的最后，不需要移動(dòng)元 素，可以直接插入e。 最壞情況，插入到第1個(gè)位置，需要移動(dòng)n次。 一般情況，移動(dòng)次數(shù)與插入位置i有關(guān)。 平均情況 設(shè)n+1種等幾率情況。 插入示例 元素 序號(hào) 123456 一標(biāo)012345 元素1 2 15891324 移動(dòng)1 2 15891324 手稿1 2 1535891324 假設(shè)在i=3位置插入一個(gè)35 算法分析 現(xiàn)把一個(gè)數(shù)x插入到第i個(gè)位置。假設(shè)表里已有n個(gè)結(jié) 點(diǎn)。

13、a1a2a3.ai.an 分析 移動(dòng)結(jié)點(diǎn)的次數(shù)由表長(zhǎng)n和插入位置i決定 算法的時(shí)間主要花費(fèi)在for循環(huán)中的結(jié)點(diǎn)后移語(yǔ)句上。 該語(yǔ)句的執(zhí)行次數(shù)是n-i+1。 當(dāng)i=n+1：移動(dòng)結(jié)點(diǎn)次數(shù)為0，即算法在最好時(shí)間復(fù) 雜度是0(1)。 當(dāng)i=1：移動(dòng)結(jié)點(diǎn)次數(shù)為n，即算法在最壞情況下時(shí) 間復(fù)雜度是0(n)。 那么平均來(lái)說(shuō)時(shí)間復(fù)雜度為多少呢？ 時(shí)間復(fù)雜度的推導(dǎo)過(guò)程 插入位置有1到n+1，假 設(shè)機(jī)率均等，每個(gè)位置 的可能性為1/(n+1)。 位置移動(dòng)次 1n 2n-1 . in-i+1 . n+10 2/) 1/() ) 1( ) 1()( 1 1 1 1 nnin inpnE n i n i iIS 平均時(shí)

14、間復(fù)雜度 EIS(n)=n/2 表長(zhǎng)的一半。 所以算法的平均時(shí)間復(fù)度為O(n)。即與表中 已有元素的個(gè)數(shù) 成正比。 2. 刪除操作 刪除操作的邏輯說(shuō)明 刪除操作的算法實(shí)現(xiàn) 刪除操作的性能分析 刪除運(yùn)算的邏輯描述 線性表的刪除運(yùn)算是指將表的第i（1in）個(gè)結(jié)點(diǎn)刪去，使長(zhǎng)度為n的線 性表 （a1，ai-1，ai，ai+1，an） 變成長(zhǎng)度為n-1的線性表 （a1，ai-1，ai+1，an） 注意： 當(dāng)要?jiǎng)h除元素的位置i不在表長(zhǎng)范圍（即i1或iL-length） 時(shí)，為非法位置，不能做正常的刪除操作 順序表刪除操作過(guò)程 后面的元素向前移動(dòng)過(guò)程 刪除算法 int DelList(SeqList *L,

15、int i, ElemType *e) /從L所指的順序表中刪除第i個(gè)結(jié)點(diǎn)ai int k; if(iL-last+1) printf(“刪除位置不存在!”); return ERROR; *e= L-elemi-1; for(k=i;klast;j+) L-elemk-1=L-elemk; /結(jié)點(diǎn)前移 L-last-; /表長(zhǎng)減小 return OK; 時(shí)間復(fù)雜度 Ede(n)=(n-1)/2 所以平均時(shí)間復(fù)雜度為O(n) 3. 查找操作 按序號(hào)查找 GetData(L,i) return L.elemi-1; 按內(nèi)容查找 Locate(L,e) Locate(L,e) int Locate

16、(SeqList L,ElemType e) int i=0; while(i=L.last) if(i=L.last) return i+1; else return -1; 時(shí)間復(fù)雜度 O(n) 例子 兩個(gè)有序表的合并 LA和LB是兩個(gè)順序表，且按非遞減有序排列。 把它們合并成一個(gè)非遞減有序排列。例如 LA=(2,2,3),LB=(1,3,3,4)，合并后為 LC=(1,2,2,3,3,3,4)。 void merge(SeqList *La,SeqList *Lb,SeqList *Lc) int i=0,j=0,k=0; while(ilast else Lc-elemk+=Lb-el

17、emj+; while(ilast) Lc-elemk+=La-elemi; while(jlast) Lc-elemk+= Lb-elemj+; Lc-last = La-last+Lb-last+1; 時(shí)間復(fù)雜度 O(La-last+Lb-last) 順序表的優(yōu)點(diǎn) 存儲(chǔ)效率高，存儲(chǔ)結(jié)構(gòu)本身已表示數(shù)據(jù)的邏 輯結(jié)構(gòu)，無(wú)需額外的存儲(chǔ)空間表示邏輯結(jié)構(gòu)。 隨機(jī)訪問(wèn)某個(gè)元素。 順序表的缺點(diǎn) 插入和刪除操作需要移動(dòng)大量的結(jié)點(diǎn)。 存儲(chǔ)空間分配是靜態(tài)分配。表的大小要事先 確定，這樣會(huì)造成程序不能適應(yīng) 實(shí)際情況的 變化。 如果事先把表長(zhǎng)確定太大，可能會(huì)浪費(fèi)存儲(chǔ) 空間。 如果把表長(zhǎng)確定得太小，可能造成數(shù)據(jù)溢出。

18、 2.3 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 順序表的優(yōu)點(diǎn)：隨機(jī)存取結(jié)構(gòu)，簡(jiǎn)單（用數(shù) 組）方便。 順序表的缺點(diǎn)：插入和刪除需要移動(dòng)大量的 元素(n/2). 這了避免大量結(jié)點(diǎn)移動(dòng)，我們采用了線性表 的另一種結(jié)構(gòu)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 簡(jiǎn)稱為鏈表，它不僅可以用來(lái)表示線性結(jié)構(gòu)， 也可以表示非線性結(jié)構(gòu)。 是最常見(jiàn)的存儲(chǔ)結(jié)構(gòu)之一。 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的具體形式有多種：?jiǎn)捂湵恚?雙鏈表，循環(huán)鏈表等。我們主要討論單鏈表。 2.3.1單鏈表 鏈表的結(jié)構(gòu)示意圖。 現(xiàn)在一個(gè)元素包括二 部分內(nèi)容：一部分是 數(shù)據(jù)本身，另一部分 是下一個(gè)元素的地址。 a3空地址 a0a1的地址 a2a3的地址 a1a2的地址 鏈表結(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu) d

19、ata是數(shù)據(jù)域，存放數(shù)據(jù)信息本身 next是指針域（又稱鏈域）存放下 一個(gè)結(jié)構(gòu)的地址。 線性表的每個(gè)結(jié)點(diǎn)就是通過(guò)指針域 把n個(gè)邏輯上相鄰的結(jié)點(diǎn)鏈接起來(lái)。 由于每個(gè)結(jié)點(diǎn)只有一個(gè)指針域，所 以稱單鏈表。 datanext 結(jié)點(diǎn)定義舉例 Typedef struct Node ElemType data; struct Node *next; Node, *LinkList; Node *,LinkList本質(zhì)上是一樣的，但是一般來(lái)說(shuō)用 LinkList表示整個(gè)鏈表，用Node *表示某個(gè)結(jié)點(diǎn)。 鏈表的表頭結(jié)點(diǎn) 在鏈表操作時(shí)，經(jīng)常需要判斷第一個(gè)結(jié)點(diǎn)是 否存在。這種判斷既浪費(fèi)運(yùn)行時(shí)間，也增加 編程的復(fù)

20、雜性。為此，在建立鏈表時(shí)，先建 立一個(gè)結(jié)點(diǎn)，放在鏈表最前面，這個(gè)結(jié)點(diǎn)不 代表實(shí)際元素。在后續(xù)的鏈表處理過(guò)程中， 這個(gè)表頭結(jié)點(diǎn)永遠(yuǎn)存，給其他操作帶來(lái)許多 便利。 2.3.2單鏈表的基本操作 1.初始化鏈表 2.建立鏈表 3.往鏈表中插入一個(gè)結(jié)點(diǎn) 4.在鏈表刪除一個(gè)結(jié)點(diǎn) 5.遍歷鏈表 1. 初始化單鏈表 void InitList(LinkList *L) *L=(LinkList ) malloc(sizeof(Node); *L-next = NULL; 2. 建立單鏈表 頭插入法 尾插入法 void CreateFromHead(LinkList L) Node *s; char c; in

21、t flag=1; while(flag) c=getchar(); if(c!=$) s = (Node *) malloc(sizeof(Node); s-data= c; s-next= L-next; L-next =s; else flag =0; 尾插入法 新建立的結(jié)點(diǎn)插入到鏈表的末尾 void CreateFromTail(LinkList L) Node *r,*s; int flag =1; r=L; while(flag) c = getchar(); if(c!=$) s=(Node *) malloc(sizeof(Node); s-data =c; r-next=s;

22、 r=s; else flag =0; r-next =NULL; 3.查找 按序號(hào)查找 按值查找 求序號(hào)查找 /L是鏈表，i是元素的序號(hào)，1i n,如果找到，返回該位 置的結(jié)點(diǎn)，仔細(xì)分析，如果i=0，會(huì)怎么樣？ Node *GetNode(LinkList L,int i) int j; Node *p; if(inext!=NULL) j+; if(i=j) return p; else /什么情況出現(xiàn)這種情況 return NULL; 按值查找 Node *Locate(LinkList L,ElemType key) Node *p; p=L-next; while(p!=NULL)

23、if(p-data!=key) p=p-next; else break; return p; /思考題，找不到時(shí)，p為什么值？ 4. 求單鏈表的長(zhǎng)度 int ListLength(LinkList L) Node *p; p=L-next; j=0; while(p) p=p-next; j+; return j; 單鏈表插入操作 問(wèn)題說(shuō)明：在單鏈表中第i個(gè)位置插入一個(gè)數(shù) 據(jù)元素e。 操作的三個(gè)步驟：找到i-1元素的指針； 申請(qǐng)新結(jié)點(diǎn)；插入鏈表。 e1e2e5e4e3 ex 算法 int InsList(LinkList L,int i,ElemType e) Node *pre,*s; i

24、nt k; if(i1) return ERROR; pre=L; k=0; while(pre!=NULL k+; /這里最好使用前面的GetNode函數(shù), 同學(xué)們練習(xí) if(!pre) printf(“cant find the position”); return ERROR; s=(Node * ) malloc(sizeof(Node); s-data =e; s-next = pre-next; pre-next =s; return OK; 單鏈表的刪除操作 e1e2e5e4e3 prep int DelList(LinkList L,int i,ElemType *e) Nod

25、e *pre,*r; int k; pre = L; k=0; while(pre-next!=NULL k+; if(pre-next=NULL) printf(“the node to be delete doesnt exist”); return ERROR; r=pre-next; pre-next = r-nxt; e=r-data; free(r ); return OK; 練習(xí)，用鏈表重做兩個(gè)有序表的合并 LinkList MergeLinkList(LinkList La,LinkList Lb) Node *pa,*pb; LinkList Lc; pa=La-next;

26、pb=Lb-next; Lc = La; Lc-next=NULL; r=Lc; while(pa!=NULL r=pa; pa=pa-next; else r-next=pb; r=pb; pb=pb-next; if(pa) r-next =pa; if(pb) r-nex=pb; free(Lb); return Lc; 循環(huán)鏈表 循環(huán)鏈表是指頭尾相連的鏈表，其實(shí)現(xiàn)算法 與單鏈表類似，但是判斷當(dāng)前結(jié)點(diǎn)p是否為尾 結(jié)點(diǎn)不一樣，p!=NULL，或 p-next!=NULL 對(duì)于循環(huán)鏈表 p!=head,或p-next!= head 循環(huán)鏈表的尾指針 經(jīng)常在尾結(jié)點(diǎn)設(shè)置鏈表指針。 請(qǐng)大家討論 把

27、兩個(gè)循環(huán)鏈表合并成一個(gè) LinkList merge_l(LinkList La,LinkList Lb) Node *p,*q; p=La; q=Lb; while(p-next!=La) p=p-next; while(q-next!=Lb) q=q-next; q-next = La; p-next =Lb-next; free(Lb); return Lb; 在尾結(jié)點(diǎn)設(shè)置指針 一般循環(huán)鏈表在尾結(jié)點(diǎn)設(shè)立一個(gè)指針，重做 上面的這個(gè)例子。 例2-3 循環(huán)鏈表的合并 有兩個(gè)帶表頭的循環(huán)鏈表La,Lb，將它們合并為 一個(gè)循環(huán)鏈表，其頭指針為L(zhǎng)a。 LinkList merge_2(LinkLis

28、t Ra,LinkList Rb) Node *p; p=Ra-next; Ra-next=Rb-next-next; free(Rb-next); Rb-next=p; return Rb; LinkList merge_1(LinkList La,LinkList Lb) Node *p,*q; p=La; q= Lb; while(p-next!=La) p=p-next; while(q-next!=Lb) q=q-next; q-next =La; p-next = Lb-next; free(Lb); Return La; 雙向鏈表 prior datanext prior dat

29、anextprior datanextprior datanext 雙向鏈表 typedef struct DNode ElemType data; struct DNode *prior,*next; DNode,*DoubleList; 帶表頭的雙向鏈表 prior datanextprior datanextprior datanext 雙向鏈表的優(yōu)點(diǎn) 既可以向前找，又可以向后找，因此查找前 驅(qū)結(jié)點(diǎn)非常方便。 某個(gè)結(jié)點(diǎn)為p p-prior-next = p; p-next-prior = p; 雙向鏈表的插入操作 在p結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)s s-data=e; s-prior = p-p

30、rior; p-prior-next =s; s-next =p; p-next =s; 雙向鏈表的刪除操作 刪除p結(jié)點(diǎn) p-prior-next = p-next; p-next-prior = p-prior; free(p); 靜態(tài)鏈表 線性表的應(yīng)用 一元多項(xiàng)式的運(yùn)算 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) struct Polynode double coef; int exp; PolyNode *next; PolyNode,*PolyList; 1.多項(xiàng)式鏈表的建立 Polylist Polycreate() Polynode *head,*rear,*s; head = (Polynode *) malloc(sizeof(Polynode); rear =head; scanf(“%d,%d”, while(c!=0) s = (Polynode *) malloc(sizeof(Polynode