第2章 線性表(修改)

1、 本章要點(diǎn)本章要點(diǎn) 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 線性表的順序存儲線性表的順序存儲 線性表的鏈?zhǔn)酱鎯€性表的鏈?zhǔn)酱鎯?順序表和鏈表的比較順序表和鏈表的比較 本章難點(diǎn)本章難點(diǎn) 順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn)順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)及基本運(yùn)算的實(shí)現(xiàn) 2.1 線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu) 2.1.1 線性表的類型定義線性表的類型定義線性表是一種線性結(jié)構(gòu)，線性結(jié)構(gòu)的數(shù)據(jù)元素之間是一種線性表是一種線性結(jié)構(gòu)，線性結(jié)構(gòu)的數(shù)據(jù)元素之間是一種線性關(guān)系，線性關(guān)系的特點(diǎn)如下：線性關(guān)系，線性關(guān)系的特點(diǎn)如下： 在一個線性表中的數(shù)據(jù)元素的類型是相同的，數(shù)據(jù)元素一在一個線性表中的數(shù)據(jù)元素的類型是相同的

2、，數(shù)據(jù)元素一個接一個的排列。個接一個的排列。 存在一個唯一的被稱作存在一個唯一的被稱作“第一個第一個”的數(shù)據(jù)元素。的數(shù)據(jù)元素。 存在唯一的一個被稱作存在唯一的一個被稱作“最后一個最后一個”的數(shù)據(jù)元素。的數(shù)據(jù)元素。 除第一個之外，每個數(shù)據(jù)元素均只有一個前驅(qū)；除最后一除第一個之外，每個數(shù)據(jù)元素均只有一個前驅(qū)；除最后一個之外，每個數(shù)據(jù)元素均只有一個后繼。個之外，每個數(shù)據(jù)元素均只有一個后繼。一個線性表是一個線性表是n (n0)個同類型數(shù)據(jù)元素個同類型數(shù)據(jù)元素a1 , a2 , a3 , ，an的有限序列。記作：的有限序列。記作： （a1 , a2 , a3 , , an ）從定義可以看出，線性表強(qiáng)調(diào)兩

3、個特性：從定義可以看出，線性表強(qiáng)調(diào)兩個特性：（1）任何數(shù)據(jù)元素）任何數(shù)據(jù)元素ai (i=1 , ，n) 必須是同類型的數(shù)據(jù)，例如，必須是同類型的數(shù)據(jù)，例如，如果是記錄，則必須是含有相同數(shù)據(jù)項(xiàng)的記錄；如果是整數(shù)，如果是記錄，則必須是含有相同數(shù)據(jù)項(xiàng)的記錄；如果是整數(shù)，則必須都是整數(shù)，不能將不同性質(zhì)的數(shù)據(jù)列在一個線性表內(nèi)。則必須都是整數(shù)，不能將不同性質(zhì)的數(shù)據(jù)列在一個線性表內(nèi)。（2）另一個是數(shù)據(jù)元素的有序性，數(shù)據(jù)元素在表中的位置決定）另一個是數(shù)據(jù)元素的有序性，數(shù)據(jù)元素在表中的位置決定了它的序號。按照這個次序，元素了它的序號。按照這個次序，元素ai-1 稱為稱為 ai 的直接前趨，的直接前趨，ai 稱為

4、稱為ai-1 的直接后繼（的直接后繼（i=1,2,3,，n）。）。 a1 是表中第一個元素，是表中第一個元素，它沒有前趨；它沒有前趨；an 是表中最后一個元素，它沒有后繼。是表中最后一個元素，它沒有后繼。表中數(shù)據(jù)元素的個數(shù)表中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。長度為稱為線性表的長度。長度為0的線性表稱的線性表稱為為空表空表。稱。稱 i 為為ai在線性表中的在線性表中的位序位序。 2.1.1 線性表的類型定義線性表的類型定義 【例1】英文字母表（A，B，Z）是線性表，表中每個字母是一個數(shù)據(jù)元素（結(jié)點(diǎn)）【例2】一副撲克牌的點(diǎn)數(shù)（2，3，10，J，Q，K，A）也是一個線性表，其中數(shù)據(jù)元素是每張牌的點(diǎn)

5、數(shù)【例3】學(xué)生成績表中，每個學(xué)生及其成績是一個數(shù)據(jù)元素，其中數(shù)據(jù)元素由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。將數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表成為文件。舉例其抽象數(shù)據(jù)類型的定義如下：其抽象數(shù)據(jù)類型的定義如下：ADT List 數(shù)據(jù)對象：數(shù)據(jù)對象：Data ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：R1 |ai-1,aiData, i=2,.,n 線性表中的數(shù)據(jù)元素可以是各種各樣的，只要是屬于同一線性表中的數(shù)據(jù)元素可以是各種各樣的，只要是屬于同一個集合即可。個集合即可。 2.1.1 線性表的類型定義線性表的類型定義數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)

6、層次上的，而運(yùn)算的具數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是定義在邏輯結(jié)構(gòu)層次上的，而運(yùn)算的具體實(shí)現(xiàn)是建立在存儲結(jié)構(gòu)上的，每一種操作的具體實(shí)現(xiàn)只有在體實(shí)現(xiàn)是建立在存儲結(jié)構(gòu)上的，每一種操作的具體實(shí)現(xiàn)只有在確定了線性表的存儲結(jié)構(gòu)之后才能完成。確定了線性表的存儲結(jié)構(gòu)之后才能完成。對于線性表，常用的運(yùn)算有如下幾種：對于線性表，常用的運(yùn)算有如下幾種：(1) 置空表（結(jié)構(gòu)初始化）置空表（結(jié)構(gòu)初始化） init_seqlist(L)；操作結(jié)果：構(gòu)造一個空的線性表操作結(jié)果：構(gòu)造一個空的線性表L。求線性表的長度。求線性表的長度。list_length(L);初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：返回操作結(jié)果：返回

7、L中元素個數(shù)。中元素個數(shù)。 2.1.2 線性表的基本操作線性表的基本操作定位定位:訪問線性表的第訪問線性表的第i個元素。個元素。get_node(L,i);初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：返回操作結(jié)果：返回L中第中第i個元素的值或地址。個元素的值或地址。查找查找 : 在線性表中查找滿足某種條件的數(shù)據(jù)元素。在線性表中查找滿足某種條件的數(shù)據(jù)元素。location_list(L,x);初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：返回操作結(jié)果：返回L中值為給定值中值為給定值x的數(shù)據(jù)元素。的數(shù)據(jù)元素。 2.1.2 線性表的基本操作線性表的基本操作插入插入:在線

8、性表的第在線性表的第i個元素之前，插入一個同類型的元素。個元素之前，插入一個同類型的元素。insert_list(L,i,x);初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：在操作結(jié)果：在L的第的第i個位置插入一個值為個位置插入一個值為x的新元素。的新元素。刪除刪除 : 刪除線性表中第刪除線性表中第i個元素。個元素。delete_list(L,i);初始條件：線性表初始條件：線性表L已存在。已存在。操作結(jié)果：在操作結(jié)果：在L中刪除序號為中刪除序號為i的數(shù)據(jù)元素。的數(shù)據(jù)元素。清除表清除表: 將已有線性表變?yōu)榭毡?，即刪除表中所有元素。將已有線性表變?yōu)榭毡?，即刪除表中所有元素。 2.1

9、.2 線性表的基本操作線性表的基本操作一種數(shù)據(jù)結(jié)構(gòu)只有在內(nèi)存中正確表示出來，才能實(shí)現(xiàn)其基一種數(shù)據(jù)結(jié)構(gòu)只有在內(nèi)存中正確表示出來，才能實(shí)現(xiàn)其基本操作。數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的表示通常有兩種形式，即本操作。數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的表示通常有兩種形式，即順序存順序存儲儲表示和表示和鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯Ρ硎尽＞€性表的順序表示又稱為表示。線性表的順序表示又稱為順序表順序表。 2.2.1順序表順序表用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，這種存儲方式稱為線性表的順序存儲結(jié)構(gòu)。它以元素在計(jì)算機(jī)這種存儲方式稱為線性表的順序存儲結(jié)構(gòu)。它以元素在計(jì)算機(jī)內(nèi)內(nèi)“物理位置相鄰物

10、理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯上相鄰的數(shù)據(jù)元素在物理位置上也是相鄰的。即邏輯上相鄰的數(shù)據(jù)元素在物理位置上也是相鄰的。 2.2線性表的順序存儲線性表的順序存儲線性表的順序存儲結(jié)構(gòu)具有以下基本特點(diǎn)：線性表的順序存儲結(jié)構(gòu)具有以下基本特點(diǎn)：(1) 存儲空間必須是連續(xù)的，預(yù)分配；存儲空間必須是連續(xù)的，預(yù)分配；(2) 邏輯順序與物理順序一致，用物理上的相邏輯順序與物理順序一致，用物理上的相鄰來表示邏輯上的線性關(guān)系。鄰來表示邏輯上的線性關(guān)系。(3)任意相鄰元素之間無空閑空間，且相距為任意相鄰元素之間無空閑空間，且相距為L(4)已知基地址，可以計(jì)

11、算出任意元素的存儲已知基地址，可以計(jì)算出任意元素的存儲地址地址a1a2ai-1aiai+1anlength-1線性表的順序存儲線性表的順序存儲設(shè)設(shè)a1的存儲地址為的存儲地址為Loc(a1)，稱為基址，每個數(shù)據(jù)元素占，稱為基址，每個數(shù)據(jù)元素占d個存儲單元，則第個存儲單元，則第i個數(shù)據(jù)元素的地址為：個數(shù)據(jù)元素的地址為：Loc(ai)Loc(a1)+(i-1)*di n已知順序表的首地址和每個元素所占地址單元的個數(shù)，已知順序表的首地址和每個元素所占地址單元的個數(shù)，就可求出第就可求出第i個數(shù)據(jù)元素的地址。個數(shù)據(jù)元素的地址。 2.2.1 順序表順序表所以稱順序表為一種所以稱順序表為一種隨機(jī)存取隨機(jī)存取的

12、結(jié)構(gòu)的結(jié)構(gòu)知識點(diǎn)回顧:用typedef定義類型可以用可以用typedef聲明新的類型名來代替已有的類型名。聲明新的類型名來代替已有的類型名。例例1：typedef int COUNT; COUNT I,j;例例2：typedef struct int month; int day; int year; DATE; 新類型名新類型名DATE DATE birthday; DATE *p;說明：對于上結(jié)構(gòu)體，說明：對于上結(jié)構(gòu)體，typedef 后跟一個無命名的結(jié)構(gòu)體類后跟一個無命名的結(jié)構(gòu)體類型型例3：typedef struct Node elemtype data; struct Node *n

13、ext; ListNode,*LinkList;Typedef與#define區(qū)別如：Typedef int COUNT;和#define COUNT int 二者不同#define是在預(yù)編譯時處理的，只能做簡單的字符串替換。而typedef是在編譯時處理的，它可以像定義變量的方法那樣聲明一個類型。如：COUNT I ,j;順序表的虛擬實(shí)現(xiàn)：順序表的虛擬實(shí)現(xiàn)：在高級語言中，數(shù)組是采用順序存儲的，所以我們可以用數(shù)組在高級語言中，數(shù)組是采用順序存儲的，所以我們可以用數(shù)組類型來說明順序表的存儲方式。類型來說明順序表的存儲方式。即順序表類型定義即順序表類型定義 2.2.1 順序表順序表#define

14、MAXSIZE 100 /表空間的大小可根據(jù)實(shí)際需要而定，表空間的大小可根據(jù)實(shí)際需要而定，這里假設(shè)為這里假設(shè)為100 typedef int ElemType /ElemType的類型可根據(jù)實(shí)際情況而定，的類型可根據(jù)實(shí)際情況而定，這里假設(shè)為這里假設(shè)為int typedef struct Elemtype dataMAXSIZE; /最多有最多有MAXSIZE個數(shù)據(jù)元素個數(shù)據(jù)元素 int length; /存放數(shù)據(jù)元素的實(shí)際個數(shù)存放數(shù)據(jù)元素的實(shí)際個數(shù) SeqList; /定義了一個新類型：順序表類型定義了一個新類型：順序表類型SeqList list; /定義一個變量：順序表定義一個變量：順序表

15、list為了能夠?qū)樞虮磉M(jìn)行整體引用，通常將為了能夠?qū)樞虮磉M(jìn)行整體引用，通常將data和和length封封裝成一個結(jié)構(gòu)體作為順序表的類型。裝成一個結(jié)構(gòu)體作為順序表的類型。知識點(diǎn)回顧：結(jié)構(gòu)體中成員的表示知識點(diǎn)回顧：結(jié)構(gòu)體中成員的表示表長表長list.length=n；表空標(biāo)志表空標(biāo)志list.length=0；表滿標(biāo)志表滿標(biāo)志list.length=MAXSIZE； 即即0=lengthlength； / 等同于等同于(*pslist).length 表空標(biāo)志表空標(biāo)志pslist-length=0；表滿標(biāo)志表滿標(biāo)志pslist-length=MAXSIZE；數(shù)據(jù)元素?cái)?shù)據(jù)元素pslist-dat

16、a0pslist-datapslist-length-1a1a2ai-1aiai+1an01i-2i-1in-1MAXSIZE-1a1a2ai-1aiai+1anpslist-datapslist-length-1 2.2.1 順序表順序表l注意：注意： 存放線性表結(jié)點(diǎn)的向量空間的大小存放線性表結(jié)點(diǎn)的向量空間的大小MAXSIZE應(yīng)應(yīng)仔細(xì)選值，使其既能滿足表結(jié)點(diǎn)的數(shù)目增加的需求，又仔細(xì)選值，使其既能滿足表結(jié)點(diǎn)的數(shù)目增加的需求，又不致于預(yù)先定義過大而浪費(fèi)存儲空間。不致于預(yù)先定義過大而浪費(fèi)存儲空間。 由于由于C語言中向量的下標(biāo)從語言中向量的下標(biāo)從0開始，所以若開始，所以若L是是SqList類型的指針

17、變量，則類型的指針變量，則a1和和an分別存儲在分別存儲在L.pslist0和和L.pslistlength-1中。中。注意問題：注意問題：l參數(shù)：參數(shù)：值傳遞和地址傳遞的區(qū)別值傳遞和地址傳遞的區(qū)別參數(shù)傳遞的方向參數(shù)傳遞的方向l邊界值的處理：邊界值的處理：在第一個元素前插入在第一個元素前插入在最后一個元素后插入在最后一個元素后插入l當(dāng)刪除或插入元素時，線性表的長度改變當(dāng)刪除或插入元素時，線性表的長度改變l指定的數(shù)據(jù)元素的位置是否合法指定的數(shù)據(jù)元素的位置是否合法 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算 順序表的初始化順序表的初始化初始化即構(gòu)造一個空表。初始化即構(gòu)造一個空表。算法分析算法分析

18、將將pslist設(shè)為指針參數(shù)，動態(tài)分配存儲空間設(shè)為指針參數(shù)，動態(tài)分配存儲空間需考慮問題：需考慮問題：（1）動態(tài)分配空間是否成功）動態(tài)分配空間是否成功（2）表中）表中l(wèi)ength值設(shè)為值設(shè)為0初始化算法實(shí)現(xiàn)：初始化算法實(shí)現(xiàn)：SeqList *init_SeqList() SeqList *pSlist; pSlist=(SeqList *) malloc (sizeof(SeqList); if ( pSlist !=NULL) pSlist-length=0; else printf(“Out of space!”); return(pSlist); main() SeqList *pSlis

19、t; pSlist=init_Seqlist(); 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算j的取值范圍： i-1=j=i-1;j-) dataj+1=dataj;i-1n-1自下而上的向下移動自下而上的向下移動j起始位置起始位置需考慮問題：需考慮問題：(1) 分配時由于向量空間大小在聲明時確定，當(dāng)L-length=MAXSIZE時，表空間已滿，不可再做插入操作；(2) 當(dāng)插入位置i的值為ilength+1或i1時為非法位置，不可做正常插入操作；(3) 移動元素時是整體自下而上的順序； (4) length值增1；插入算法實(shí)現(xiàn)：插入算法實(shí)現(xiàn)：i

20、nt insert_list(SeqList *pslist, int i, Elemtype x ) int j; if (pslist-length =MAXSIZE) printf(“表滿表滿n”); return -1; if (ipslist-length+1) printf(“位置錯位置錯”)；return (0); 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算 for (j=pslist-length-1;j=i-1;j-) pslist-dataj+1=pslist-dataj;/*結(jié)點(diǎn)向后移結(jié)點(diǎn)向后移*/ pslist-datai-1=x;/*插入新元素插入新元素*/ psl

21、ist-length+;/*length仍指向最后元素仍指向最后元素*/ return 1; 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算時間復(fù)雜度分析：時間復(fù)雜度分析：設(shè)在第設(shè)在第i個位置插入的概率為個位置插入的概率為Pi平均移動次數(shù)平均移動次數(shù)Eis(n)= n/2說明做插入操作時，需要移動一半的數(shù)據(jù)元素，時間復(fù)雜說明做插入操作時，需要移動一半的數(shù)據(jù)元素，時間復(fù)雜度為度為O(n)。 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算niiinP1) 1(niin1) 1(11n11na 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算in-1自上而下的向上移動自上而下的向上移動j起始位起始位置置j的

22、取值范圍： i=j=length-1移動語句：For (j=i;jlength的值為的值為0，條件（，條件（ipslist-length）也包括對表空的檢查（符合）也包括對表空的檢查（符合ilength ）；(4)移動元素時是整體自上而下的順序；(5) length值減1； 刪除算法實(shí)現(xiàn)刪除算法實(shí)現(xiàn)int delete_list(SeqList *pslist,int i) int j; if (ipslist-length) printf(“不存在第不存在第i個元素個元素n”); return(0);for (j=i;jlength-1;j+) pslist-dataj-1=pslist-d

23、ataj; pslist-length-; return 1; 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算時間復(fù)雜度分析：時間復(fù)雜度分析：刪除第刪除第i個位置的概率為個位置的概率為Pi平均移動次數(shù)平均移動次數(shù)Ede(n)=說明刪除運(yùn)算時平均需要移動一半的數(shù)據(jù)元素，時間復(fù)雜說明刪除運(yùn)算時平均需要移動一半的數(shù)據(jù)元素，時間復(fù)雜度為度為O(n)。 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算niinP1) 1(n1n1niin1)(2) 1( n 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算 順序表按值查找算法實(shí)現(xiàn)順序表按值查找算法實(shí)現(xiàn)int location_seqlist(SeqList *ps

24、list,elemtype x) int i; i=0; while (ilength-1 & pslist-datai!=x) i+; if (ipslist-length-1) return 1; else return i; /*返回存儲位置返回存儲位置*/ 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算時間復(fù)雜度分析：時間復(fù)雜度分析：本算法的主要運(yùn)算是比較，比較次數(shù)與本算法的主要運(yùn)算是比較，比較次數(shù)與x的位置有的位置有關(guān)，也與表長有關(guān)。關(guān)，也與表長有關(guān)。 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算找到找到找不到找不到最好情況最好情況1 1次次 O(1)O(1) n+1 n+1次次 O(

25、1)O(1)最壞情況最壞情況n n次次O(n)O(n)n+1n+1次次O(n)O(n)平均情況平均情況n/2n/2次次O(n)O(n)n+1n+1次次O(n)O(n) 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算 查找操作算法實(shí)現(xiàn)查找操作算法實(shí)現(xiàn)Elemtype Get_Node(SeqList *pslist,int i) if (i=1 & ilength) return(pslist-datai-1); else printf(“Not exit.n”); return(-1); 求表長算法實(shí)現(xiàn)求表長算法實(shí)現(xiàn)int list_length(SeqList *pslist) return(

26、pslist-length); /求求pslist所指向順序表的長度所指向順序表的長度 2.2.2 順序表的基本運(yùn)算順序表的基本運(yùn)算算法算法5和算法和算法6的時間復(fù)雜度均為的時間復(fù)雜度均為O(1)順序表的劃分。順序表的劃分。將順序表將順序表(a1,a2,，an)重新排列為以重新排列為以a1為界的兩部分：為界的兩部分：a1前前面的值均比面的值均比a1小，小，a1后面的值都比后面的值都比a1大。大。 2.2.3 順序表的應(yīng)用順序表的應(yīng)用1226811191010118122619劃分前劃分前劃分后劃分后算法分析算法分析從第二個元素開始從第二個元素開始 當(dāng)前數(shù)據(jù)比當(dāng)前數(shù)據(jù)比a1大時，不改變其位置，繼

27、續(xù)比較下一個。大時，不改變其位置，繼續(xù)比較下一個。 當(dāng)前數(shù)據(jù)比當(dāng)前數(shù)據(jù)比a1小時，將其前面的元素依次向后移動一個位小時，將其前面的元素依次向后移動一個位置，然后將其置入對應(yīng)單元。置，然后將其置入對應(yīng)單元。 2.2.3 順序表的應(yīng)用順序表的應(yīng)用12268111910將26和12比較，比12大，不用變化，再比較8和12，比12小，則12、26均向后移動l需要一個變量來存放比較的位置，此算法用i來表示數(shù)組下標(biāo)位置。1=i=lengthl當(dāng)需要移動元素時，需要一個變量表示移動的范圍，用j表示。0=jdata0; for (i=1; ilength-1;i+) if (L-dataidatai; for

28、 (j=i-1;j=0;j-) L-dataj+1=L-dataj; L-data0=y; 2.2.3 順序表的應(yīng)用順序表的應(yīng)用順序表的合并。順序表的合并。已知順序表已知順序表LA和和LB中的數(shù)據(jù)元素按值非遞減有序排列，中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將現(xiàn)要求將LA和和LB歸并為一個新的順序表歸并為一個新的順序表LC，且，且LC中的數(shù)據(jù)中的數(shù)據(jù)元素仍按值非遞減有序排列。元素仍按值非遞減有序排列。LA=(1，4，7，10)LB=(2，3，9，12，16)LC=(1，2，3，4，7，9，10，12，16)算法分析算法分析設(shè)設(shè)LC為空表，依次掃描為空表，依次掃描LA和和LB，比較當(dāng)前元素，將較

29、，比較當(dāng)前元素，將較小值的元素賦給小值的元素賦給LC，直到一個線性表掃描完畢，然后將未完，直到一個線性表掃描完畢，然后將未完的順序表中余下部分賦給的順序表中余下部分賦給LC即可。即可。 三個順序表都需要設(shè)個變量存當(dāng)前的位置。三個順序表都需要設(shè)個變量存當(dāng)前的位置。 void union(SeqList LA, SeqList LB,SeqList *LC) int i,j,k; i=0;j=0;k=0; while (i=LA.length-1 & j=LB.length-1) if (LA.dataidatak+=LA.datai+; else LC-datak+=LB.dataj+; whi

30、le (idatak+=LA.datai+; while (jdatak+=LB.dataj+; LC-length=LA.length+LB.length; 2.2.3 順序表的應(yīng)用順序表的應(yīng)用從前面看到，順序存儲結(jié)構(gòu)有特點(diǎn)：從前面看到，順序存儲結(jié)構(gòu)有特點(diǎn)： （1）邏輯順序與物理順序一致）邏輯順序與物理順序一致 （2）隨機(jī)存取）隨機(jī)存取但是，也存在一些缺點(diǎn)：但是，也存在一些缺點(diǎn)： （1）插入、刪除等操作要移動元素）插入、刪除等操作要移動元素 （2）存儲空間是預(yù)分配的，不靈活，浪費(fèi)空間）存儲空間是預(yù)分配的，不靈活，浪費(fèi)空間 （3）表的存儲空間難擴(kuò)充）表的存儲空間難擴(kuò)充 2.3線性表的鏈?zhǔn)酱鎯€

31、性表的鏈?zhǔn)酱鎯δ敲?，有沒有一種靈活的存儲方式呢？那么，有沒有一種靈活的存儲方式呢？回答是肯定的！回答是肯定的！鏈?zhǔn)酱鎯Y(jié)構(gòu)，但是有優(yōu)點(diǎn)，鏈?zhǔn)酱鎯Y(jié)構(gòu)，但是有優(yōu)點(diǎn)，同樣也存在缺點(diǎn)同樣也存在缺點(diǎn) 線性表的鏈?zhǔn)酱鎯Ψ绞剑壕€性表的鏈?zhǔn)酱鎯Ψ绞剑海?）是用一組任意的存儲單元存儲數(shù)據(jù)元素（這組存儲單元）是用一組任意的存儲單元存儲數(shù)據(jù)元素（這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的）?？梢允沁B續(xù)的，也可以是不連續(xù)的）。（2）為了表示線性關(guān)系，對數(shù)據(jù)元素）為了表示線性關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲其本來說，除了存儲其本身的信息之外，還需要存儲直接后繼的存儲位置（也可以是身的信息之外，還需要存儲直接后繼的存

32、儲位置（也可以是前驅(qū)）。前驅(qū)）。這兩部分信息組成數(shù)據(jù)元素的這兩部分信息組成數(shù)據(jù)元素的ai的存儲映象，稱為的存儲映象，稱為結(jié)點(diǎn)結(jié)點(diǎn)（Node）。它包括兩個域：數(shù)據(jù)域和指針域。）。它包括兩個域：數(shù)據(jù)域和指針域。n個結(jié)點(diǎn)鏈結(jié)成一個鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。又個結(jié)點(diǎn)鏈結(jié)成一個鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。又由于每個結(jié)點(diǎn)中只包含一個指針域，故又稱為單鏈表。由于每個結(jié)點(diǎn)中只包含一個指針域，故又稱為單鏈表。 2.3線性表的鏈?zhǔn)酱鎯€性表的鏈?zhǔn)酱鎯?2.3.1 線性鏈表線性鏈表 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn) 存儲空間不一定連續(xù)存儲空間不一定連續(xù) 邏輯關(guān)系由指針來體現(xiàn)邏輯關(guān)系由指

33、針來體現(xiàn)(3) 邏輯上相鄰，物理上不一定相鄰邏輯上相鄰，物理上不一定相鄰(4) 非隨機(jī)存?。樞虼嫒。丛L問任何一個元素非隨機(jī)存?。樞虼嫒。?，即訪問任何一個元素的時間不同。如磁帶和的時間不同。如磁帶和CD注意：注意：鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇鎯Ψ绞街唬粌H可用來表示鏈?zhǔn)酱鎯κ亲畛Ｓ玫拇鎯Ψ绞街?，它不僅可用來表示線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。線性表，而且可用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。 2.3.1 線性鏈表線性鏈表存儲地址存儲地址數(shù)據(jù)域數(shù)據(jù)域指針指針110E150120D110125A160140C120150FNULL160B140125頭指針頭指針head鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱?/p>

34、儲結(jié)構(gòu)例：有線性表例：有線性表h（A,B,C,D,E,F），其對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)），其對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)如圖所示。如圖所示。 2.3.1 線性鏈表線性鏈表datanext 虛擬實(shí)現(xiàn)：虛擬實(shí)現(xiàn)：利用高級語言中的指針來實(shí)現(xiàn)。利用高級語言中的指針來實(shí)現(xiàn)。 結(jié)點(diǎn)定義如下：結(jié)點(diǎn)定義如下：typedef struct Node elemtype data; struct Node *next; ListNode,*LinkList;結(jié)點(diǎn)（結(jié)點(diǎn)（Node）單鏈表中每個結(jié)點(diǎn)的存儲地址是存放在其前趨結(jié)點(diǎn)單鏈表中每個結(jié)點(diǎn)的存儲地址是存放在其前趨結(jié)點(diǎn)next域域中，而起始結(jié)點(diǎn)無前趨，故設(shè)中，而起始結(jié)點(diǎn)無前趨，故設(shè)頭

35、指針頭指針head指向起始結(jié)點(diǎn)。指向起始結(jié)點(diǎn)。定義頭指針變量：定義頭指針變量：LinkList head; LinkNode *p; LinkList head;注意：注意： LinkList和和LNode *是不同名字的同一個指針類型（命是不同名字的同一個指針類型（命名的不同是為了概念上更明確）名的不同是為了概念上更明確） LinkList類型的指針變量類型的指針變量head表示它是單鏈表的頭指針表示它是單鏈表的頭指針 LNode *類型的指針變量類型的指針變量p表示它是指向某一結(jié)點(diǎn)的指表示它是指向某一結(jié)點(diǎn)的指針針 2.3.1 線性鏈表線性鏈表ABCDEFhead鏈表的邏輯結(jié)構(gòu)鏈表的邏輯結(jié)構(gòu)

36、nextdataPpdatapnextl算法中各個域的表示算法中各個域的表示l如定義一個指針如定義一個指針p：lLinklist p(*p).data(*p).nextHead=NULL不帶頭結(jié)點(diǎn)的空表不帶頭結(jié)點(diǎn)的空表ABCDEhead不帶頭結(jié)點(diǎn)的鏈表不帶頭結(jié)點(diǎn)的鏈表 這種鏈表稱為不帶頭結(jié)點(diǎn)的鏈表，但是首結(jié)點(diǎn)無前驅(qū)，很多操作需要單獨(dú)這種鏈表稱為不帶頭結(jié)點(diǎn)的鏈表，但是首結(jié)點(diǎn)無前驅(qū)，很多操作需要單獨(dú)考慮首結(jié)點(diǎn)?？紤]首結(jié)點(diǎn)。 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可存儲如線性表的長度等頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲

37、任何信息，也可存儲如線性表的長度等附加信息。指針域存放首元結(jié)點(diǎn)的地址附加信息。指針域存放首元結(jié)點(diǎn)的地址head帶頭結(jié)點(diǎn)的空表帶頭結(jié)點(diǎn)的空表ABCDEhead附加頭結(jié)點(diǎn)的鏈表附加頭結(jié)點(diǎn)的鏈表頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn)首元結(jié)點(diǎn)首元結(jié)點(diǎn)Headnext=NULL 頭結(jié)點(diǎn)是在鏈表的起始結(jié)點(diǎn)之前附加頭結(jié)點(diǎn)是在鏈表的起始結(jié)點(diǎn)之前附加的一個結(jié)點(diǎn)，有兩個優(yōu)點(diǎn)：的一個結(jié)點(diǎn)，有兩個優(yōu)點(diǎn)：由于起始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指由于起始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，故在鏈表的第一個位置上的操作針域中，故在鏈表的第一個位置上的操作與表中其他位置上操作一致，無須進(jìn)行特與表中其他位置上操作一致，無須進(jìn)行特殊處理。殊處理。

38、無論鏈表是否為空，其頭指針都是指向頭無論鏈表是否為空，其頭指針都是指向頭結(jié)點(diǎn)的非空指針，故此空表和非空表的處結(jié)點(diǎn)的非空指針，故此空表和非空表的處理也統(tǒng)一了。理也統(tǒng)一了。 2.3.2 動態(tài)內(nèi)存分配動態(tài)內(nèi)存分配動態(tài)內(nèi)存分配指在程序執(zhí)行過程中動態(tài)地分配或回收存儲動態(tài)內(nèi)存分配指在程序執(zhí)行過程中動態(tài)地分配或回收存儲空間，在需要時，由系統(tǒng)即時分配?？臻g，在需要時，由系統(tǒng)即時分配。 malloc()函數(shù)函數(shù)void *malloc(unsigned int size)在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。的連續(xù)空間。例例p=(long *) malloc(8

39、)/*開辟長度為開辟長度為8個字節(jié)的內(nèi)存空間，并把起始地址賦給一個指個字節(jié)的內(nèi)存空間，并把起始地址賦給一個指向向long型的指針變量型的指針變量p*/注意注意當(dāng)函數(shù)未能成功分配存儲空間（如內(nèi)存不足）時，返回一當(dāng)函數(shù)未能成功分配存儲空間（如內(nèi)存不足）時，返回一個個NULL指針，即調(diào)用該函數(shù)時檢測返回值是否為指針，即調(diào)用該函數(shù)時檢測返回值是否為NULL并執(zhí)并執(zhí)行相應(yīng)的操作。行相應(yīng)的操作。 2.3.2 動態(tài)內(nèi)存分配動態(tài)內(nèi)存分配例：動態(tài)分配程序例：動態(tài)分配程序 #include /*標(biāo)準(zhǔn)輸入輸出文件標(biāo)準(zhǔn)輸入輸出文件*/#include /*動態(tài)分配文件動態(tài)分配文件*/main() int count,

40、*array; if (array=(int *) malloc(10*sizeof(int)=NULL) printf(“error!”); exit(1); for (count=0;count10;count+) arraycount=count; for (count=0;countnext=NULL; else printf(“out of space!”); return(pLlist); 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算ABCDEheadp 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算帶表頭結(jié)點(diǎn)的單鏈表求表長帶表頭結(jié)點(diǎn)的單鏈表求表長 int length_Link

41、List(LinkList L) Lnode *p; int count; p=L;/*p指向頭結(jié)點(diǎn)指向頭結(jié)點(diǎn)*/ count=0; while (p-next !=NULL) p=p-next; count+;/*p所指的是第所指的是第count個結(jié)點(diǎn)個結(jié)點(diǎn)*/ return count; 此操作遍歷了整個鏈表，時間復(fù)雜度：此操作遍歷了整個鏈表，時間復(fù)雜度：O(n) 此處注意：此處注意：p-next !=NULL與與p !=NULL不同不同請同學(xué)們說出，哪兒不同？請同學(xué)們說出，哪兒不同？ 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算3. 查找操作查找操作 鏈表中按序號查找（查找指定位置的結(jié)

42、點(diǎn)）鏈表中按序號查找（查找指定位置的結(jié)點(diǎn)） 按序號查找是線性表的一種常用運(yùn)算，其功能是按序號查找是線性表的一種常用運(yùn)算，其功能是對給定的鏈表查找表中第對給定的鏈表查找表中第i個結(jié)點(diǎn)，并用一個指針變量個結(jié)點(diǎn)，并用一個指針變量指向該結(jié)點(diǎn)。指向該結(jié)點(diǎn)。算法設(shè)計(jì)算法設(shè)計(jì) 從鏈表的第一個元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)是否是從鏈表的第一個元素結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)是否是第第i個，若是，則返回該結(jié)點(diǎn)的指針；否則繼續(xù)判斷后個，若是，則返回該結(jié)點(diǎn)的指針；否則繼續(xù)判斷后一個，直到表結(jié)束為止。沒有第一個，直到表結(jié)束為止。沒有第i個結(jié)點(diǎn)時返回空。個結(jié)點(diǎn)時返回空。 請同學(xué)們現(xiàn)在自己編寫這個算法請同學(xué)們現(xiàn)在自己編寫這個算法 l當(dāng)

43、做遍歷操作時候，while條件都要加上while (p-next！=NULL &？)或或while (p-next！=NULL | ？)或或while (p！=NULL &？)或或while (p！=NULL | ？)i的合法位置為n，j的取值范圍0-nl若若i1，則while條件中jn+1，則while條件中jnextNULL，此，此時時j=n; (i與與j肯定不相等肯定不相等)l若若1=inext !=NULL & jnext; j+; if (i=j&i!=0) return(p); else return(NULL); 按序號查找鏈表數(shù)據(jù)元素算法一按序號查找鏈表數(shù)據(jù)元素算法一還有其他的

44、表示方法嗎？Int Getelem(linklist l,int I, int *e)P=L-next;J=1;While(p & jnext; +j; If (!p | ji) return -1;E=p-data;Return 1;算法二：算法二： 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算 按值查找操作按值查找操作算法分析算法分析從鏈表的第一個結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)值是否等于從鏈表的第一個結(jié)點(diǎn)起，判斷當(dāng)前結(jié)點(diǎn)值是否等于x，若是，返回該結(jié)，若是，返回該結(jié)點(diǎn)的指針；否則繼續(xù)判斷后一個，直到表結(jié)束，找不到時返回空。點(diǎn)的指針；否則繼續(xù)判斷后一個，直到表結(jié)束，找不到時返回空。 ListNode

45、*Locate_Linklist(LinkList Llist,Elemtype x) ListNode *p; p=Llist-next; /* 設(shè)置初值設(shè)置初值 */ while (p!=NULL & p-data!=x) p=p-next; /*未達(dá)到尾結(jié)點(diǎn)，又未找到值等于未達(dá)到尾結(jié)點(diǎn)，又未找到值等于x的結(jié)點(diǎn)時，繼續(xù)找的結(jié)點(diǎn)時，繼續(xù)找*/ return(p); /* 找到值為找到值為x的結(jié)點(diǎn)，返回它的地址的結(jié)點(diǎn)，返回它的地址 */ 查找算法的時間復(fù)雜度均為查找算法的時間復(fù)雜度均為O(n)算法算法 (1) 分配時由于向量空間大小在聲明時確定，當(dāng)分配時由于向量空間大小在聲明時確定，當(dāng)L-le

46、ngth=MAXSIZE時，表空間已滿，不可再時，表空間已滿，不可再做插入操作；做插入操作；(2) 當(dāng)插入位置當(dāng)插入位置i的值為的值為in+1或或i1時為非法位時為非法位置，不可做正常插入操作；置，不可做正常插入操作；(3) 移動元素時是整體自下而上的順序；移動元素時是整體自下而上的順序； (4) length值增值增1；4. 插入操作插入操作在順序表的插入算法中需考慮問題：在順序表的插入算法中需考慮問題：鏈表的插入算法與順序表插入算法相比較：（1）不存在“表滿”（2）插入位置合理性判斷1=inext=p-next; p-next=s; 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算注意注意兩

47、個指針的操作順序不能交換，否則兩個指針的操作順序不能交換，否則p結(jié)點(diǎn)后面的結(jié)點(diǎn)將被斷開，不能結(jié)點(diǎn)后面的結(jié)點(diǎn)將被斷開，不能實(shí)現(xiàn)正確插入。實(shí)現(xiàn)正確插入。在第在第i位置之前插入一個值為位置之前插入一個值為x的結(jié)點(diǎn)，算法如下：的結(jié)點(diǎn)，算法如下：Int insert_LinkList(LinkList head, int i, Elemtype e) P=head; j=0;While(P & jnext;+j;If(!p|ji-1) return -1;S=(linklist )malloc(sizeof(listnode);S-data=e;S-next=p-next;P-next=s;Return

48、 1; 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算5. 鏈表中刪除結(jié)點(diǎn)鏈表中刪除結(jié)點(diǎn)在順序表中刪除算法需考慮問題：在順序表中刪除算法需考慮問題：(1)如果需如果需ai，應(yīng)先返回，應(yīng)先返回ai的值的值(2)檢查要刪除位置的有效性，檢查要刪除位置的有效性，1in (3)當(dāng)表空時不能做刪除當(dāng)表空時不能做刪除(4)移動元素時是整體自上而下的順序移動元素時是整體自上而下的順序(5) length值減值減1；在鏈表中刪除算法需考慮問題：在鏈表中刪除算法需考慮問題：(1)如果需如果需ai，應(yīng)先返回，應(yīng)先返回ai的值的值(2)檢查要刪除位置的有效性，檢查要刪除位置的有效性，1in (3)當(dāng)表空時不能做刪除

49、當(dāng)表空時不能做刪除(4)不需要移動元素不需要移動元素(5)不需要設(shè)不需要設(shè)Length值值(6)刪除的結(jié)點(diǎn)空間用刪除的結(jié)點(diǎn)空間用free釋放釋放設(shè)設(shè)s指向單鏈表中某個結(jié)點(diǎn)，刪除指向單鏈表中某個結(jié)點(diǎn)，刪除s，首先要找到，首先要找到s的前驅(qū)結(jié)的前驅(qū)結(jié)點(diǎn)點(diǎn)p，指針操作由下：，指針操作由下：p-next=s-next;free(s);a1ai+1anheadai-1aip 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算s刪除鏈表中第刪除鏈表中第i個結(jié)點(diǎn)的基本步驟如下：個結(jié)點(diǎn)的基本步驟如下： 找到第找到第i-1個結(jié)點(diǎn)；若存在，繼續(xù)進(jìn)行，否則結(jié)束。個結(jié)點(diǎn)；若存在，繼續(xù)進(jìn)行，否則結(jié)束。 若存在第若存在第i個

50、結(jié)點(diǎn)，則繼續(xù)個結(jié)點(diǎn)，則繼續(xù)，否則結(jié)束。，否則結(jié)束。 刪除第刪除第i個結(jié)點(diǎn)，結(jié)束。個結(jié)點(diǎn)，結(jié)束。 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算刪除鏈表中第刪除鏈表中第i個結(jié)點(diǎn)的算法如下：個結(jié)點(diǎn)的算法如下：int del_LinkList(LinkList pList,int i) Listnode *p,*q;int j;p=pList;j=0;while(*p).next!=NULL & ji-1) return ERROR;q=(*p).next;(*p).next=(*q).next;free(q);return OK; 2.3.3線性鏈表的基本運(yùn)算線性鏈表的基本運(yùn)算 2.3.3線性鏈表

51、的基本運(yùn)算線性鏈表的基本運(yùn)算練習(xí)：已知已知L是帶表頭結(jié)點(diǎn)的非空單鏈表，且是帶表頭結(jié)點(diǎn)的非空單鏈表，且P結(jié)點(diǎn)結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從既不是首元結(jié)點(diǎn)，也不是尾元結(jié)點(diǎn)，試從下列提供的答案中選擇合適的語句序列。下列提供的答案中選擇合適的語句序列。a.刪除刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是b.刪除刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是_c.刪除刪除P結(jié)點(diǎn)的語句序列是結(jié)點(diǎn)的語句序列是_d.刪除首元結(jié)點(diǎn)的語句序列是刪除首元結(jié)點(diǎn)的語句序列是_e.刪除尾元結(jié)點(diǎn)的語句序列是刪除尾元結(jié)點(diǎn)的語句序列是_lP=Pnext;lPnext=P;lP

52、next=Pnextnext;lP=Pnextnext;lWhile(P!=NULL) P=Pnext;lWhile (Qnext!=NULL) l P=Q; Q=Qnext；l(7) While (Pnext!=Q) P=Pnext;l(8) While (Pnextnext!=Q) P=Pnext;l(9) While (Pnextnext!=NULL) P=Pnext;l(10) Q=P;l(11) Q=Pnext;l(12) P=L;l(13) L=L next;l(14) free(Q);由此可知：要刪除的結(jié)點(diǎn)為Q結(jié)點(diǎn)練習(xí)：a.刪除P結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語句序列是 （11）（3）（1

53、4）b.刪除P結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語句序列是_ (10) (12) (8) (11) (3) (14)c.刪除P結(jié)點(diǎn)的語句序列是_ (10) (12) (7) (3) (14)d.刪除首元結(jié)點(diǎn)的語句序列是_ (12) (10) (11) (3) (14)e.刪除尾元結(jié)點(diǎn)的語句序列是_ (9) (11) (3) (14) 或 (10)/(11) (6) (3) (14)簡述下列算法的功能簡述下列算法的功能 int A(Linklist L) L為不帶頭結(jié)點(diǎn)的鏈表為不帶頭結(jié)點(diǎn)的鏈表 if (L & L next) Q=L; L=L next; P=L; while (P next) P=P nex

54、t; P next=Q; Q next=NULL; return(1); 如果如果L的長度不小于的長度不小于2，則將首元結(jié)點(diǎn)刪掉并插入到表尾。，則將首元結(jié)點(diǎn)刪掉并插入到表尾。 2.3.3補(bǔ)充補(bǔ)充 2.3.3補(bǔ)充補(bǔ)充354728867935473528473586284735在鏈表頭部插入建立單鏈表在鏈表頭部插入建立單鏈表 2.3.3補(bǔ)充補(bǔ)充建立單鏈表算法建立單鏈表算法 LinkList Creat_LinkList1() LinkList L; ListNode *p; int a; int flag; L=NULL; scanf(“ %d ”,&a); while (a != flag) p

55、=(Lnode *) malloc (sizeof(Lnode); p-data=a; p-next=L; L=p; scanf(“ %d ”,&a); return L; 2.3.3補(bǔ)充補(bǔ)充 2.3.3補(bǔ)充補(bǔ)充353535353547472847288647288679在鏈表尾部插入建立單鏈表在鏈表尾部插入建立單鏈表headheadheadheadheadheadrearrearrearrearrearrear 2.3.3補(bǔ)充補(bǔ)充建立單鏈表算法建立單鏈表算法 LinkList Creat_LinkList2() LinkList L; ListNode *p,*rear; int a; in

56、t flag; L=rear=NULL; scanf(“ %d ”,&a); while (a != flag) p=(Lnode *) malloc (sizeof(Lnode); p-data=a; if (L=NULL) L=p;/*處理第一個結(jié)點(diǎn)處理第一個結(jié)點(diǎn)*/ else rear-next=p;/*其它結(jié)點(diǎn)的處理其它結(jié)點(diǎn)的處理*/ rear=p;/*指向新的尾結(jié)點(diǎn)指向新的尾結(jié)點(diǎn)*/ scanf(“ %d ”,&a); if (rear != NULL) rear-next=NULL; return L; 2.3.3補(bǔ)充補(bǔ)充head 2.3.4循環(huán)鏈表及運(yùn)算循環(huán)鏈表及運(yùn)算a1a2an

57、heada1a2anhead 2.3.4循環(huán)鏈表及運(yùn)算循環(huán)鏈表及運(yùn)算單循環(huán)鏈表的連接單循環(huán)鏈表的連接 LinkList connect(LinkList ra,rb) ListNode *p; p=ra-next; ra-next=rb-next-next; free(rb-next); rb-next=p; return(rb); 2.3.4循環(huán)鏈表及運(yùn)算循環(huán)鏈表及運(yùn)算priordatanext 2.3.5雙向鏈表及運(yùn)算雙向鏈表及運(yùn)算a1a2anpheadhead 2.3.5雙向鏈表及運(yùn)算雙向鏈表及運(yùn)算 2.3.5雙向鏈表及運(yùn)算雙向鏈表及運(yùn)算pxs 2.3.5雙向鏈表及運(yùn)算雙向鏈表及運(yùn)算（4

58、）放到最后面是最保險的）放到最后面是最保險的請同學(xué)們寫出當(dāng)請同學(xué)們寫出當(dāng)p指指向第向第i-1個結(jié)點(diǎn)時的個結(jié)點(diǎn)時的操作操作 2.3.5雙向鏈表及運(yùn)算雙向鏈表及運(yùn)算算法：帶頭結(jié)點(diǎn)的雙向鏈表算法：帶頭結(jié)點(diǎn)的雙向鏈表L的第的第i個位置上插入值為個位置上插入值為x的元素。的元素。 int insert_DubList(DulList L,int i,Elemtype x) if(!(p=GetElem_DuL(L,i) return ERROR; if (!(s=(DulList)malloc(sizeof(DulNode) return ERROR; s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return(1);