數(shù)據(jù)結(jié)構(gòu)第二章線性表(2016)

1、第二章 線性表12線性表的概念及運(yùn)算線性表的順序存儲(chǔ) 34線性表的鏈?zhǔn)酱鎯?chǔ)順序表和鏈表的比較 2.1 線性表的概念及運(yùn)算（a1, a2, ai-1，ai, ai1 ，, an）1. 線性表的定義：線性表的定義：n(n0)個(gè)個(gè)相同類型數(shù)據(jù)相同類型數(shù)據(jù)元素元素的的有限序列有限序列。n=0時(shí)稱為時(shí)稱為數(shù)據(jù)元素?cái)?shù)據(jù)元素開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)ai的直接前趨的直接前趨ai的直接后繼的直接后繼下標(biāo)，下標(biāo)，是元素的是元素的序號(hào)，表示元素序號(hào)，表示元素在表中的位置在表中的位置n n為元素總個(gè)為元素總個(gè)數(shù)，即數(shù)，即表長(zhǎng)表長(zhǎng)空表空表終端結(jié)點(diǎn)終端結(jié)點(diǎn)2.1 線性表的概念及運(yùn)算 線性結(jié)構(gòu)的邏輯特征線性結(jié)構(gòu)的邏輯特征: : 對(duì)

2、于一個(gè)非空的線性表對(duì)于一個(gè)非空的線性表: :1) 1) 有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)a a1 1, ,它無(wú)直接前趨它無(wú)直接前趨, ,僅有一個(gè)僅有一個(gè)直接后繼直接后繼a a2 2；2) 2) 有且僅有一個(gè)終端結(jié)點(diǎn)有且僅有一個(gè)終端結(jié)點(diǎn)a an n, ,它無(wú)直接后繼它無(wú)直接后繼, ,僅有一個(gè)直僅有一個(gè)直接前趨接前趨a an-1n-1； 3) 3) 其余的內(nèi)部結(jié)點(diǎn)其余的內(nèi)部結(jié)點(diǎn)a ai i (1in),(1in),都有且僅有一個(gè)直接前趨都有且僅有一個(gè)直接前趨a ai-1i-1和一個(gè)直接后繼和一個(gè)直接后繼a ai+1 i+1 . .a1a3a4ana22.1 線性表的概念及運(yùn)算例例1 分析分

3、析26 個(gè)英文字母組成的英文表個(gè)英文字母組成的英文表 （ A, B, C, D, , Z）學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別年齡年齡班級(jí)班級(jí)2006011810205于春梅于春梅女女 202006級(jí)信計(jì)級(jí)信計(jì)011班班2006011810260何仕鵬何仕鵬男男 192006級(jí)信計(jì)級(jí)信計(jì)011班班2006011810284王王 爽爽女女 192006級(jí)信計(jì)級(jí)信計(jì)012班班2006011810360王亞武王亞武男男 212006級(jí)信計(jì)級(jí)信計(jì)012班班： ：例例2 分析學(xué)生情況登記表分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄數(shù)據(jù)元素都是記錄; 元素間關(guān)系是線性元素間關(guān)系是線性數(shù)據(jù)元素都是字母數(shù)據(jù)元素都是字母; 元素間

4、關(guān)系是線性的。元素間關(guān)系是線性的。2.1 線性表的概念及運(yùn)算2 2 線性表的運(yùn)算線性表的運(yùn)算1) 1) SETNULL(L)SETNULL(L) 置空表置空表2) 2) LENGTH(L)LENGTH(L) 求表長(zhǎng)求表長(zhǎng)3) 3) GET(L,i) GET(L,i) 取表中第取表中第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(1(1 i i LENGTH(L)LENGTH(L) )4) 4) LOCATE(L,x) LOCATE(L,x) 定位定位: : 若若L L中存在一個(gè)值為中存在一個(gè)值為x x的結(jié)點(diǎn)的結(jié)點(diǎn), ,返回該結(jié)點(diǎn)位置返回該結(jié)點(diǎn)位置; ; 若若L L中存在多個(gè)值為中存在多個(gè)值為x x的結(jié)點(diǎn)的結(jié)點(diǎn), ,返回

5、首次找到的位置返回首次找到的位置; ; 若若L L中不存在值為中不存在值為x x的結(jié)點(diǎn)的結(jié)點(diǎn), ,返回一值表示其不存在返回一值表示其不存在. .5) 5) INSERT(L,x,i)INSERT(L,x,i)在在L L的第的第i i個(gè)位置插入一個(gè)值為個(gè)位置插入一個(gè)值為x x的結(jié)點(diǎn)的結(jié)點(diǎn). .6) 6) DELETE(L,i) DELETE(L,i) 刪除刪除L L中第中第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn). .2.2 線性表的順序存儲(chǔ)一一 順序表順序表用一組用一組地址連續(xù)地址連續(xù)的存儲(chǔ)單元依次存的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過(guò)靜態(tài)數(shù)組儲(chǔ)線性表的元素，可通過(guò)靜態(tài)數(shù)組VnVn或動(dòng)態(tài)數(shù)或動(dòng)態(tài)數(shù)組來(lái)實(shí)現(xiàn)。組來(lái)實(shí)

6、現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。線性表的順序表示又稱為線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)或或順序映像順序映像。順序存儲(chǔ)定義：順序存儲(chǔ)定義：順序存儲(chǔ)方法：順序存儲(chǔ)方法：簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰簡(jiǎn)言之，邏輯上相鄰，物理上也相鄰2.2 線性表的順序存儲(chǔ)線性表順序存儲(chǔ)特點(diǎn)：線性表順序存儲(chǔ)特點(diǎn)：1. 邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2. 若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（

7、位置亦可求出（利用數(shù)組下標(biāo)利用數(shù)組下標(biāo)）。計(jì)算方法是（參見(jiàn)存）。計(jì)算方法是（參見(jiàn)存儲(chǔ)結(jié)構(gòu)示意圖）：儲(chǔ)結(jié)構(gòu)示意圖）：設(shè)首元素設(shè)首元素a1的存放地址為的存放地址為L(zhǎng)OC(a1)（稱為稱為基地址基地址），），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為C字節(jié)，字節(jié)，則表中任一數(shù)據(jù)元素的則表中任一數(shù)據(jù)元素的存儲(chǔ)地址存儲(chǔ)地址為：為： LOC(ai+1) = LOC(ai)+C LOC(ai) = LOC(a1) +（i-1） * C (1 i n)注意：注意：C C語(yǔ)言中數(shù)組的下標(biāo)從語(yǔ)言中數(shù)組的下標(biāo)從0 0開(kāi)始，開(kāi)始， 即：即：LnLn的有效范圍是的有效范圍是L0L0Ln-1

8、Ln-12.2 線性表的順序存儲(chǔ)線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 內(nèi)容內(nèi)容 元素在表中的位序元素在表中的位序1 1i i2 2n n空閑區(qū)空閑區(qū)i+1i+1Cb=LOC(a1)b + + C Cb +(i-1)+(i-1)* *C Cb +(n-1)+(n-1)* *C Cb +(max-1)+(max-1)* *C C 順序表是一順序表是一種隨機(jī)存取的種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)，即，即其其查找操作的查找操作的時(shí)間性能為時(shí)間性能為O(1)。2.2 線性表的順序存儲(chǔ)一個(gè)一維數(shù)組，下標(biāo)的范圍是到，每個(gè)

9、一個(gè)一維數(shù)組，下標(biāo)的范圍是到，每個(gè)數(shù)組元素用相鄰的數(shù)組元素用相鄰的4 4個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素址，設(shè)存儲(chǔ)數(shù)組元素 的第一個(gè)字節(jié)的地址是的第一個(gè)字節(jié)的地址是，則，則 的第一個(gè)字節(jié)的地址是的第一個(gè)字節(jié)的地址是 例例1因此：因此：LOC( M3 ) = 98 + 4 (3-0) =110解：解：地址計(jì)算通式為：地址計(jì)算通式為：LOC(ai) = LOC(a0) + L *（i-0）2.2 線性表的順序存儲(chǔ)用數(shù)組用數(shù)組V V來(lái)存放來(lái)存放2626個(gè)英文字母組成的線性個(gè)英文字母組成的線性表（表（a a，b b，c c，z z），寫出在順序結(jié)構(gòu)上），寫出在順序

10、結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C C語(yǔ)言程序。語(yǔ)言程序。 #define n 26int Vn;voidvoid build() / build() /* *字母線性表的生成，即建表操作字母線性表的生成，即建表操作* */ / int i; int i; V0=a; V0=a; for(i=1;i=n-1;i+) for(i=1;i=n-1;i+) Vi=Vi-1+1;Vi=Vi-1+1; 核心語(yǔ)句：核心語(yǔ)句：法法1 Vi= Vi-1+1;1 Vi= Vi-1+1;法法2 Vi=2 Vi=a a+i;+i;法法3 Vi=97+i;3 Vi=97+i;例例22.2 線性表的順序存儲(chǔ)voi

11、dvoid main() / main() /* *主函數(shù)主函數(shù)* */ / build(); build(); display(); display(); getch(); getch(); voidvoid display() / display() /* *字母線性表的顯示，即讀表操作字母線性表的顯示，即讀表操作* */ / int i; int i; for(i=0;in;i+) for(i=0;idatai-1L-datai-1求表長(zhǎng)求表長(zhǎng)LENGTH(L):LENGTH(L):取第取第i i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) GET(L,i):GET(L,i):( (* *L).last+1L).las

12、t+1( (* *L).datai-1L).datai-12.2 線性表的順序存儲(chǔ)二二 基本運(yùn)算基本運(yùn)算1 1 插入插入 Insert(Insert(L,x,iL,x,i) ) (i(i從從1 1開(kāi)始開(kāi)始) )/在線性表在線性表L L的的第第i i個(gè)位置插入值為個(gè)位置插入值為x x的的結(jié)點(diǎn)結(jié)點(diǎn)插入前：插入前：( (a a1, 1, , , aiai-1, -1, aiai, , , , anan) )插入后：插入后：( (a a1, 1, , , aiai-1, -1, x x , , aiai, , , , anan) )ai-1和和ai之間的邏輯關(guān)系發(fā)生了變化之間的邏輯關(guān)系發(fā)生了變化順序存

13、儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反映這個(gè)變化存儲(chǔ)位置要反映這個(gè)變化2.2 線性表的順序存儲(chǔ)33例：（例：（35，12，24，42），在第），在第i=2的位置上插入的位置上插入33。表滿：表滿：last+1=MaxSize合理的插入位置：合理的插入位置：1in+1（i指的是元素的序號(hào)）指的是元素的序號(hào)） 435122442a1a2a3a40 1 2 3 4 表長(zhǎng)表長(zhǎng)422412335什么時(shí)候不能插入什么時(shí)候不能插入？注意邊界條件注意邊界條件2.2 線性表的順序存儲(chǔ)插入算法：插入算法： 在線性表的第在線性表的第i i個(gè)位置插入一個(gè)元素個(gè)位置插入一個(gè)元素實(shí)現(xiàn)步驟：

14、實(shí)現(xiàn)步驟： 將第將第n至第至第i 位的元素向后移動(dòng)一個(gè)位置；位的元素向后移動(dòng)一個(gè)位置； 將要插入的元素寫到第將要插入的元素寫到第i個(gè)位置；個(gè)位置； 表長(zhǎng)加表長(zhǎng)加1。注意：注意：事先應(yīng)判斷事先應(yīng)判斷: 插入位置插入位置i 是否合法是否合法?表是否已滿表是否已滿? for (j=(*L).last;j=i-1;j-) (*L).dataj+1=(*L).dataj; (*L). datai-1=x; (*L).last=(*L).last+1;/ /* * 元素后移一個(gè)位置元素后移一個(gè)位置* */ / /* * 插入插入x */ /* * 表長(zhǎng)加表長(zhǎng)加1 1* */ / 核心語(yǔ)句：核心語(yǔ)句：共移動(dòng)

15、（共移動(dòng)（n-i+1n-i+1）個(gè)元素?。﹤€(gè)元素！2.2 線性表的順序存儲(chǔ)具體實(shí)現(xiàn)：具體實(shí)現(xiàn)：int INSERT(sequenlist *L, datatype x, int i) int j; if ( ) /*判斷是否溢出？判斷是否溢出？*/ printf(“overflow”); return 0; if ( ) /*判斷位置是否合法？判斷位置是否合法？*/ printf(“error”); return 0; else for (j=(*L).last; j=i-1; j-) (*L).dataj+1=(*L).dataj; (*L).datai-1=x; (*L).last=(*L

16、).last+1; return 1;( (* *L).last=maxsize-1L).last=maxsize-1i(i(* *L).last+2)L).last+2)(i1)(i1) |2.2 線性表的順序存儲(chǔ)時(shí)間復(fù)雜度分析：時(shí)間復(fù)雜度分析： 插入算法時(shí)間主要耗費(fèi)在插入算法時(shí)間主要耗費(fèi)在移動(dòng)元素移動(dòng)元素的操作上的操作上 T(n)= O (移動(dòng)元素次數(shù)移動(dòng)元素次數(shù)) 移動(dòng)元素的次數(shù)取決于插入元素的位置。移動(dòng)元素的次數(shù)取決于插入元素的位置。討論：討論：若在長(zhǎng)度為若在長(zhǎng)度為 n 的線性表的第的線性表的第 i 位位 插入一個(gè)元素，則向后插入一個(gè)元素，則向后移動(dòng)元素的次數(shù)移動(dòng)元素的次數(shù)f(n)為為

17、:f(n) =最好最好情況（情況（ i =n+1）：移動(dòng)元素次數(shù)）：移動(dòng)元素次數(shù)0次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(1)。最壞最壞情況（情況（ i =1）：移動(dòng)元素次數(shù)）：移動(dòng)元素次數(shù)n次，時(shí)間復(fù)雜度為次，時(shí)間復(fù)雜度為O(n)。平均平均情況（情況（1in+1）：時(shí)間復(fù)雜度為）：時(shí)間復(fù)雜度為O(n)。 + +- -+ += =11)=1(niiinp + +- -+ + += =11)=1(11niinn2nO(n) n i + 12.2 線性表的順序存儲(chǔ)ai-1和和ai之間的邏輯關(guān)系發(fā)生了變化之間的邏輯關(guān)系發(fā)生了變化順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系順序存儲(chǔ)要求存儲(chǔ)位置反映邏輯關(guān)系存儲(chǔ)位置要反

18、映這個(gè)變化存儲(chǔ)位置要反映這個(gè)變化2 2 刪除刪除 DeleteDelete( (L,iL,i) ) (i(i從從1 1開(kāi)始開(kāi)始) )/刪除刪除線性表線性表L L的的第第i i個(gè)位置個(gè)位置結(jié)點(diǎn)結(jié)點(diǎn)刪除前：刪除前：( (a a1, 1, , , aiai-1, -1, aiai, , , , anan) )刪除后：刪除后：( (a a1, 1, , , aiai-1, -1, ai+1ai+1, , , , anan) )2.2 線性表的順序存儲(chǔ)例：（例：（35, 33, 12, 24, 42），刪除），刪除i=2的數(shù)據(jù)元素。的數(shù)據(jù)元素。 535a1a2a3a40 1 2 3 4422412334

19、a5122442合理的刪除位置：合理的刪除位置：1in（i指的是元素的序號(hào)）指的是元素的序號(hào)）什么時(shí)候不能刪除什么時(shí)候不能刪除？2.2 線性表的順序存儲(chǔ)實(shí)現(xiàn)步驟：實(shí)現(xiàn)步驟： 將第將第i+1 i+1 至第至第n n 位的元素向前移動(dòng)一個(gè)位置；位的元素向前移動(dòng)一個(gè)位置； 表長(zhǎng)減表長(zhǎng)減1 1。注意：注意：事先應(yīng)判斷事先應(yīng)判斷: : 刪除位置刪除位置i i 是否合法是否合法? ? 刪除刪除線性表的第線性表的第i i個(gè)位置上的元素個(gè)位置上的元素for (j=i;j=(*L).last;j+) (*L).dataj-1=(*L).dataj; (*L).last-;/ /* * 元素前移一個(gè)位置元素前移一

20、個(gè)位置* */ /*表長(zhǎng)減表長(zhǎng)減1*/ 核心語(yǔ)句：核心語(yǔ)句：共移動(dòng)（共移動(dòng)（n-in-i）個(gè)元素?。﹤€(gè)元素！2.2 線性表的順序存儲(chǔ)具體實(shí)現(xiàn)：具體實(shí)現(xiàn)：int DELETE(sequenlist *L, int i) int j; if ( ) /*判斷位置是否合法？判斷位置是否合法？*/ printf(“error”); return 0; else for (j=i; j(i(* *L).last+1)L).last+1)(i1)(idata=ch; s-next=head;head=s;依次插入每一個(gè)結(jié)點(diǎn)依次插入每一個(gè)結(jié)點(diǎn) csheadbaheadab2.3.2 單鏈表上的基本運(yùn)算lin

21、klist linklist * *CREATLISTF() /CREATLISTF() /* *頭插法建單鏈表頭插法建單鏈表* */ / char ch; char ch; linklist linklist * *head,head,* *s;s; head=NULL; / head=NULL; /* *單鏈表開(kāi)始為空單鏈表開(kāi)始為空* */ / ch=getchar(); / ch=getchar(); /* *讀入第一個(gè)結(jié)點(diǎn)的值讀入第一個(gè)結(jié)點(diǎn)的值* */ / while(ch!=$) while(ch!=$) s=malloc(sizeof(linklist); / s=malloc(s

22、izeof(linklist); /* *生成新結(jié)點(diǎn)，分配空間生成新結(jié)點(diǎn)，分配空間* */ / s-data=ch; / s-data=ch; /* *給新結(jié)點(diǎn)的數(shù)據(jù)域賦值給新結(jié)點(diǎn)的數(shù)據(jù)域賦值* */ / s-next=head;s-next=head; head=s; head=s; / /* *將新結(jié)點(diǎn)插入到表頭上將新結(jié)點(diǎn)插入到表頭上* */ / ch=getchar(); / ch=getchar(); /* *讀入下一個(gè)結(jié)點(diǎn)的值讀入下一個(gè)結(jié)點(diǎn)的值* */ / return head; return head; / /* *返回單鏈表的頭指針?lè)祷貑捂湵淼念^指針* */ / 2.3.2 單

23、鏈表上的基本運(yùn)算2）尾插法建表：）尾插法建表：即：將新生成的每一個(gè)結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，一即：將新生成的每一個(gè)結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，一個(gè)一個(gè)往后插，直到結(jié)束符為止，需增加一個(gè)個(gè)一個(gè)往后插，直到結(jié)束符為止，需增加一個(gè)尾指針尾指針，使，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。eg: eg: 空表，讀入空表，讀入a b c $a b c $初始化初始化: head=NULL; r=NULL;插入第一個(gè)元素結(jié)點(diǎn)插入第一個(gè)元素結(jié)點(diǎn)headrear a2.3.2 單鏈表上的基本運(yùn)算插入第二個(gè)元素結(jié)點(diǎn)插入第二個(gè)元素結(jié)點(diǎn)csrearhead bsreara依次插入每一個(gè)結(jié)點(diǎn)依次插

24、入每一個(gè)結(jié)點(diǎn)rearheadba算法描述：算法描述：s=malloc(sizeof(linklist); s-data=ch; r-next=s;r=s;2.3.2 單鏈表上的基本運(yùn)算linklist *CREATLISTR() /*尾插法建單鏈表尾插法建單鏈表*/char ch; linklist *head,*s,*r; head=NULL; /*單鏈表開(kāi)始為空單鏈表開(kāi)始為空*/ r=NULL; /*尾指針初值為空尾指針初值為空*/ ch=getchar(); /*讀入第一個(gè)結(jié)點(diǎn)的值讀入第一個(gè)結(jié)點(diǎn)的值*/ while(ch!=$) s=malloc(sizeof(linklist); /*

25、生成新的結(jié)點(diǎn)，給其分配空間生成新的結(jié)點(diǎn)，給其分配空間*/ s-data=ch; /*給新結(jié)點(diǎn)的數(shù)據(jù)域賦值給新結(jié)點(diǎn)的數(shù)據(jù)域賦值*/ r-next=s; /*非空表，新結(jié)點(diǎn)插入尾指針之后非空表，新結(jié)點(diǎn)插入尾指針之后*/ r=s; /*尾指針尾指針r指向新的表尾指向新的表尾*/ ch=getchar(); /*讀入下一個(gè)結(jié)點(diǎn)的值讀入下一個(gè)結(jié)點(diǎn)的值*/ r-next=NULL; /*非空表的尾結(jié)點(diǎn)的指針域置為空非空表的尾結(jié)點(diǎn)的指針域置為空*/ return head; /*返回單鏈表的頭指針?lè)祷貑捂湵淼念^指針*/if(head=NULL) head=s; /*第一個(gè)新結(jié)點(diǎn)直接插入空表中第一個(gè)新結(jié)點(diǎn)直接

26、插入空表中*/ elseif(r!=NULL)2.3.2 單鏈表上的基本運(yùn)算）建立帶頭結(jié)點(diǎn)的單鏈表：）建立帶頭結(jié)點(diǎn)的單鏈表：即：在開(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)（即：在開(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)頭結(jié)點(diǎn)），這樣，無(wú)），這樣，無(wú)論鏈表是否為空，其頭指針始終是指向頭結(jié)點(diǎn)的非空指針。論鏈表是否為空，其頭指針始終是指向頭結(jié)點(diǎn)的非空指針。利用尾插表建表的方法，可以省去空表和非空表的判斷，利用尾插表建表的方法，可以省去空表和非空表的判斷，從而簡(jiǎn)化操作。從而簡(jiǎn)化操作。頭指針頭指針是是指向指向鏈表中鏈表中第一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)（或?yàn)椋ɑ驗(yàn)轭^結(jié)點(diǎn)頭結(jié)點(diǎn)或或?yàn)殚_(kāi)始結(jié)點(diǎn)為開(kāi)始結(jié)點(diǎn)）的的指針指針。頭結(jié)點(diǎn)頭結(jié)點(diǎn)是在鏈表的是

27、在鏈表的開(kāi)始結(jié)點(diǎn)之前附設(shè)開(kāi)始結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只的一個(gè)結(jié)點(diǎn)；數(shù)據(jù)域內(nèi)只放空表標(biāo)志或表長(zhǎng)等信息放空表標(biāo)志或表長(zhǎng)等信息。開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素是指鏈表中存儲(chǔ)線性表第一個(gè)數(shù)據(jù)元素a a1 1。 頭指針頭指針頭結(jié)點(diǎn)頭結(jié)點(diǎn) 開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)a12.3.2 單鏈表上的基本運(yùn)算區(qū)別：區(qū)別： 無(wú)頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)(鏈棧常用鏈棧常用) 有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)(鏈表常用鏈表常用)a1a2/a4a3heada1a2/a4a3head2.3.2 單鏈表上的基本運(yùn)算答：答：討論討論1 1. . 在鏈表中設(shè)置在鏈表中設(shè)置頭結(jié)點(diǎn)頭結(jié)點(diǎn)有什么好處？有什么好處？討論討論2 2. . 如何判別如何

28、判別空表空表？頭結(jié)點(diǎn)頭結(jié)點(diǎn)即在鏈表的開(kāi)始結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)即在鏈表的開(kāi)始結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表點(diǎn)的數(shù)據(jù)域中不存儲(chǔ)線性表的數(shù)據(jù)元素，其作用是為了對(duì)鏈表進(jìn)行操作時(shí)，可以對(duì)進(jìn)行操作時(shí)，可以對(duì)空表、非空表空表、非空表的情況以及對(duì)的情況以及對(duì)開(kāi)始結(jié)點(diǎn)開(kāi)始結(jié)點(diǎn)進(jìn)行進(jìn)行統(tǒng)一處理，編程更方便統(tǒng)一處理，編程更方便,常用頭結(jié)點(diǎn)。常用頭結(jié)點(diǎn)。答：答：無(wú)頭結(jié)點(diǎn)時(shí)，無(wú)頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的值為空當(dāng)頭指針的值為空時(shí)表示空表；時(shí)表示空表；有頭結(jié)點(diǎn)時(shí)，有頭結(jié)點(diǎn)時(shí)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)榭债?dāng)頭結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)表示空表。時(shí)表示空表。頭指針頭指針頭指針頭指針頭結(jié)點(diǎn)頭

29、結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)無(wú)頭結(jié)點(diǎn)有頭結(jié)點(diǎn)有頭結(jié)點(diǎn)hhh=NULLh-next=NULL2.3.2 單鏈表上的基本運(yùn)算linklist *CREATLISTR1() /*尾插法建帶頭結(jié)點(diǎn)的單鏈表尾插法建帶頭結(jié)點(diǎn)的單鏈表*/ char ch; linklist *head,*s,*r; head=malloc(sizeof(linklist); /*生成頭結(jié)點(diǎn)生成頭結(jié)點(diǎn)*/ r=head; /*尾指針初值指向頭結(jié)點(diǎn)尾指針初值指向頭結(jié)點(diǎn)*/ printf(nplease input the value of linklist :n); ch=getchar(); /*讀入第一個(gè)結(jié)點(diǎn)的值讀入第一個(gè)結(jié)點(diǎn)的值*/ w

30、hile(ch!=$) s=malloc(sizeof(linklist); /*生成新的結(jié)點(diǎn)，給其分配空間生成新的結(jié)點(diǎn)，給其分配空間*/ s-data=ch; /*給新結(jié)點(diǎn)的數(shù)據(jù)域賦值給新結(jié)點(diǎn)的數(shù)據(jù)域賦值*/ r-next=s; /*新結(jié)點(diǎn)插入尾指針之后新結(jié)點(diǎn)插入尾指針之后*/ r=s; /*尾指針尾指針r指向新的表尾指向新的表尾*/ ch=getchar(); /*讀入下一個(gè)結(jié)點(diǎn)的值讀入下一個(gè)結(jié)點(diǎn)的值*/ r-next=NULL; /*尾結(jié)點(diǎn)的指針域置為空尾結(jié)點(diǎn)的指針域置為空*/ return head; /*返回單鏈表的頭指針?lè)祷貑捂湵淼念^指針*/時(shí)間復(fù)雜度時(shí)間復(fù)雜度O(n)2.3.2

31、單鏈表上的基本運(yùn)算2單鏈表的查找運(yùn)算單鏈表的查找運(yùn)算1)按序號(hào)查找按序號(hào)查找:查找第查找第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn) 0 i nv核心操作（關(guān)鍵操作）：核心操作（關(guān)鍵操作）：p指針后移指針后移。從頭結(jié)點(diǎn)出發(fā)，通過(guò)。從頭結(jié)點(diǎn)出發(fā)，通過(guò)p指針的反復(fù)后移而將整個(gè)單鏈表指針的反復(fù)后移而將整個(gè)單鏈表“審視審視”一遍的方法稱為一遍的方法稱為掃描掃描（或遍歷）。（或遍歷）。v 需要設(shè)置一個(gè)計(jì)數(shù)器需要設(shè)置一個(gè)計(jì)數(shù)器,隨隨p的后移一起記數(shù)的后移一起記數(shù).heada1pa2panaip查找成功查找成功pin查找失敗查找失敗順藤摸瓜順藤摸瓜p2.3.2 單鏈表上的基本運(yùn)算linklist *GET(linklist *head

32、,int i) /*按序號(hào)查找按序號(hào)查找*/ int j; linklist *p; p=head; j=0; while( ) p=p-next; j+; if(i=j) return p; else return NULL;(p-next!=NULL) & (jnext; while( ) if(p-data!=key) p=p-next; else break; return p;p!=NULL平均時(shí)間復(fù)雜度為平均時(shí)間復(fù)雜度為O(n)2.3.2 單鏈表上的基本運(yùn)算3單鏈表的插入運(yùn)算單鏈表的插入運(yùn)算 假設(shè)假設(shè)p指向某一結(jié)點(diǎn)指向某一結(jié)點(diǎn), s指向待插入的值為指向待插入的值為x的新的新結(jié)點(diǎn)結(jié)點(diǎn)

33、,則根據(jù)插入位置不同可以有則根據(jù)插入位置不同可以有:前插操作前插操作: s插入在插入在p之前之前;后插操作后插操作: s插入在插入在p之后之后;2.3.2 單鏈表上的基本運(yùn)算1) 后插操作后插操作pxss=malloc(sizeof(linklist); s-data=x; Step1:s-next=p-next; Step2:p-next=s;插入步驟（即核心語(yǔ)句）：插入步驟（即核心語(yǔ)句）：思考：步驟思考：步驟1 1和和2 2能互換么？能互換么？ 不能互換！不能互換！12平均時(shí)間復(fù)雜度為平均時(shí)間復(fù)雜度為O(1)2.3.2 單鏈表上的基本運(yùn)算2) 前插操作前插操作pxs12q3分析分析:需要修

34、改需要修改*p的前趨結(jié)點(diǎn)的前趨結(jié)點(diǎn)*q的指針域的指針域,則需確定則需確定*q的的位置位置.由于單鏈表沒(méi)有指向前趨結(jié)點(diǎn)的指針由于單鏈表沒(méi)有指向前趨結(jié)點(diǎn)的指針,則需要從則需要從頭指針開(kāi)始依次找到頭指針開(kāi)始依次找到*p的前趨的前趨*q,然后再改變指針然后再改變指針,做做*q的后插操作的后插操作.2.3.2 單鏈表上的基本運(yùn)算void INSERTBEFORE (linklist *head,linklist *p,datatype x) /*前插：將值為前插：將值為x的新結(jié)點(diǎn)插入的新結(jié)點(diǎn)插入*p之前之前*/ linklist *s,*q; s=malloc(sizeof(linklist); s-d

35、ata=x; q=head; while( q-next!=p ) q=q-next; s-next=p; q-next=s;時(shí)間復(fù)雜度分析：時(shí)間復(fù)雜度分析：最好最好情況（情況（ 在開(kāi)始結(jié)點(diǎn)之前插）：在開(kāi)始結(jié)點(diǎn)之前插）：while執(zhí)行執(zhí)行0次，次，O(1)。最壞最壞情況（情況（ 在最后結(jié)點(diǎn)之前插）：在最后結(jié)點(diǎn)之前插）：while執(zhí)行執(zhí)行n次，次，O(n)。平均平均情況（與情況（與p的位置有關(guān)）：的位置有關(guān)）：時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)。算法時(shí)間主要耗費(fèi)在算法時(shí)間主要耗費(fèi)在while循環(huán)循環(huán)操作操作總結(jié)：此前插算法性能較差總結(jié)：此前插算法性能較差, ,可作進(jìn)一步改進(jìn)可作進(jìn)一步改進(jìn)! !2.

36、3.2 單鏈表上的基本運(yùn)算改進(jìn)：在改進(jìn)：在* *p p之之后插后插入入* *s,s,然后然后交換交換* *s s和和* *p p的數(shù)據(jù)域值的數(shù)據(jù)域值即可即可. .ps12p345x(1) s=malloc(sizeof(linklist); (2) s-data=p-data; (3) s-next=p-next; (4) p-next=s;(5) p-data=x;平均時(shí)間復(fù)雜度為平均時(shí)間復(fù)雜度為O(1)前插操作變?yōu)楹蟛宀僮髑安宀僮髯優(yōu)楹蟛宀僮?2.3.2 單鏈表上的基本運(yùn)算實(shí)現(xiàn)實(shí)現(xiàn) INSERT(L,x,i):分析分析:在單鏈表在單鏈表L的第的第i個(gè)結(jié)點(diǎn)之前插入值為個(gè)結(jié)點(diǎn)之前插入值為x的結(jié)

37、點(diǎn)的結(jié)點(diǎn),可轉(zhuǎn)化為可轉(zhuǎn)化為在第在第i-1個(gè)結(jié)點(diǎn)之后插入個(gè)結(jié)點(diǎn)之后插入.void INSERT(linklist *L,datatype x,int i) linklist *p; int j; j=i-1; /* 第第j-1個(gè)結(jié)點(diǎn)之后個(gè)結(jié)點(diǎn)之后*/ p=GET(L,j); if(p=NULL) printf(errorn); else INSERTAFTER(p,x);平均時(shí)間復(fù)雜度為平均時(shí)間復(fù)雜度為O(n)2.3.2 單鏈表上的基本運(yùn)算4單鏈表的刪除運(yùn)算單鏈表的刪除運(yùn)算 pr分析分析:刪除刪除*p的后繼簡(jiǎn)單的后繼簡(jiǎn)單,設(shè)設(shè)r指向被刪結(jié)點(diǎn)指向被刪結(jié)點(diǎn),則則:刪除步驟（即核心語(yǔ)句）：刪除步驟（即

38、核心語(yǔ)句）：r=p-next; p-next=r-next; free(r);思考：思考： 省略省略free(r); 語(yǔ)句語(yǔ)句行不行？行不行？不行不行! !2.3.2 單鏈表上的基本運(yùn)算實(shí)現(xiàn)實(shí)現(xiàn) DELETE(L,i):分析分析:刪除第刪除第i-1個(gè)結(jié)點(diǎn)的后繼個(gè)結(jié)點(diǎn)的后繼.void DELETE(linklist *L,int i) /*刪除刪除L的第的第i個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)*/ linklist *p; p=GET(L,i-1); if( ) DELETEAFTER(p); else printf(error);(p!=NULL) (p-next!=NULL)&平均時(shí)間復(fù)雜度為平均時(shí)間復(fù)雜度為O(

39、n)2.3.2 單鏈表上的基本運(yùn)算5 5、應(yīng)用舉例：兩個(gè)鏈表的歸并、應(yīng)用舉例：兩個(gè)鏈表的歸并算法要求：算法要求：已知：已知：線性表線性表 A A、B B，分別由，分別由單鏈表單鏈表 LALA、LBLB 存儲(chǔ)，存儲(chǔ)，其中數(shù)據(jù)元素按值其中數(shù)據(jù)元素按值非遞減有序非遞減有序排列。排列。要求：要求：將將 A A、B B 歸并歸并為一個(gè)新的線性表為一個(gè)新的線性表C , C C , C 的數(shù)據(jù)的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表元素仍按值非遞減排列。設(shè)線性表C C由由單鏈表單鏈表LCLC存儲(chǔ)，存儲(chǔ)，要求利用要求利用LALA和和LBLB的原有結(jié)點(diǎn)。的原有結(jié)點(diǎn)。假設(shè)：假設(shè)：A=A=（3 3，5 5，8 8，11

40、11），），B=B=（2 2，6 6，8 8，9 9，1111）預(yù)測(cè)：預(yù)測(cè)：合并后合并后 C =C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 2 , 3 , 5 , 6 , 8 , 8 , 9 , 1111，11 11 ）2.3.2 單鏈表上的基本運(yùn)算用鏈表可表示為：用鏈表可表示為： 3 511 / 8 LaLa 2 611 / 8 LbLb 9 2 3 6 5 LcLc 8 811 / 911頭結(jié)點(diǎn)頭結(jié)點(diǎn)LaLaLbLbLcLc2.3.2 單鏈表上的基本運(yùn)算算法分析：算法分析：算法主要包括：算法主要包括：搜索、比較、插入搜索、比較、插入三個(gè)操作：三個(gè)操作：搜索：搜索：需要

41、需要兩個(gè)指針兩個(gè)指針遍歷兩個(gè)鏈表；遍歷兩個(gè)鏈表；比較：比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大小；比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大??；插入：插入：將兩個(gè)結(jié)點(diǎn)中將兩個(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。2.3.2 單鏈表上的基本運(yùn)算3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb， Pc指向新鏈表當(dāng)前結(jié)點(diǎn)指向新鏈表當(dāng)前結(jié)點(diǎn)Lc Pa3 PcPa5 Pc11Pc2 PbPcPaLa2.3.2 單鏈表上的基本運(yùn)算算法實(shí)現(xiàn)：算法實(shí)現(xiàn)： linklist *MergeList_L(linklist *La, linklist *Lb, linkList *L

42、c) linklist *pa,*pb,*pc; free(Lb); /*釋放釋放Lb的頭結(jié)點(diǎn)的頭結(jié)點(diǎn)*/ return Lc; pc-next = pa?pa:pb ; /*插入剩余結(jié)點(diǎn)插入剩余結(jié)點(diǎn)*/ while(pa&pb) if(pa-datadata) pc-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next; pa=La-next; pb=Lb-next; Lc=pc=La； 思考思考: :若要求不若要求不能有重復(fù)的數(shù)能有重復(fù)的數(shù)據(jù)元素，如何據(jù)元素，如何實(shí)現(xiàn)？實(shí)現(xiàn)？2.3.3 循環(huán)鏈表特點(diǎn)：特點(diǎn)： 3head

43、a1ai-1anaip2.3.3 循環(huán)鏈表如：帶頭結(jié)點(diǎn)的如：帶頭結(jié)點(diǎn)的空空循環(huán)鏈循環(huán)鏈表樣式表樣式head注：將單鏈表的首尾相接，將終端結(jié)點(diǎn)的指針域由空指針改為注：將單鏈表的首尾相接，將終端結(jié)點(diǎn)的指針域由空指針改為指向頭結(jié)點(diǎn)，構(gòu)成指向頭結(jié)點(diǎn)，構(gòu)成單循環(huán)鏈表單循環(huán)鏈表，簡(jiǎn)稱，簡(jiǎn)稱循環(huán)鏈表循環(huán)鏈表。reara1ai-1anai開(kāi)始結(jié)點(diǎn)：開(kāi)始結(jié)點(diǎn)：rear-next-next終端結(jié)點(diǎn)：終端結(jié)點(diǎn)：rear其它形式的循環(huán)鏈表如：帶尾指針的循環(huán)鏈表其它形式的循環(huán)鏈表如：帶尾指針的循環(huán)鏈表 一元多項(xiàng)式加法一元多項(xiàng)式加法2.3.3 循環(huán)鏈表n次多項(xiàng)式形式次多項(xiàng)式形式: F(x)=a0+a1x+a2x2+a3x

44、3+anxncoefexpnext結(jié)點(diǎn)類型說(shuō)明：結(jié)點(diǎn)類型說(shuō)明：typedef struct pnode float coef; /*系數(shù)系數(shù)*/ int exp; /*指數(shù)指數(shù)*/ struct pnode *next;polynode;注：頭結(jié)點(diǎn)的注：頭結(jié)點(diǎn)的coef=0,exp=-1coef=0,exp=-1，多項(xiàng)式中只寫非多項(xiàng)式中只寫非0 0系數(shù)的項(xiàng)系數(shù)的項(xiàng)。eg:A(x)=1+2x2+3x3+4x4 B(x)=x+3x2-3x3+5x5 求：求：A(x)+B(x)=C(x)? 1 24 / 3 A(X)A(X) 0 -1 0 2 34 1 35 /-3 B(X)B(X) 0 -1 1

45、2 35 2.3.3 循環(huán)鏈表 運(yùn)算規(guī)則運(yùn)算規(guī)則（1）指數(shù)相同的項(xiàng)，將其對(duì)應(yīng)系數(shù)相加，若和不）指數(shù)相同的項(xiàng)，將其對(duì)應(yīng)系數(shù)相加，若和不為為0，則形成和多項(xiàng)式中一項(xiàng)；，則形成和多項(xiàng)式中一項(xiàng)；（2）所有指數(shù)不同的項(xiàng)復(fù)制到和多項(xiàng)式中。）所有指數(shù)不同的項(xiàng)復(fù)制到和多項(xiàng)式中。 設(shè)設(shè)q1,q2分別指向多項(xiàng)式分別指向多項(xiàng)式A，B中當(dāng)前檢測(cè)的某一中當(dāng)前檢測(cè)的某一結(jié)點(diǎn)，結(jié)點(diǎn)，q為和多項(xiàng)式中一結(jié)點(diǎn)。為和多項(xiàng)式中一結(jié)點(diǎn)。則：則：2.3.3 循環(huán)鏈表（1）當(dāng)當(dāng)q1-exp=q2-exp，則系數(shù)相加；，則系數(shù)相加； 若和不為若和不為0:生成和多項(xiàng)式生成和多項(xiàng)式C中一新結(jié)點(diǎn)中一新結(jié)點(diǎn)q，q1,q2指針后移；指針后移； 若和為

46、若和為0: q1,q2指針后移。指針后移。（2）當(dāng)當(dāng)q1-expq2-exp 將將B中當(dāng)前結(jié)點(diǎn)中當(dāng)前結(jié)點(diǎn)q2復(fù)制到復(fù)制到和多項(xiàng)式和多項(xiàng)式C中，中，q2指針后移。指針后移。（3）當(dāng)當(dāng)q1-exp exp 將將A中當(dāng)前結(jié)點(diǎn)中當(dāng)前結(jié)點(diǎn)q1復(fù)制到和多項(xiàng)式復(fù)制到和多項(xiàng)式C中，中，q1指針后移。指針后移。（4）若）若A、B中有一個(gè)已經(jīng)處理完，則將未處理完的多項(xiàng)式剩中有一個(gè)已經(jīng)處理完，則將未處理完的多項(xiàng)式剩余項(xiàng)復(fù)制到和多項(xiàng)式余項(xiàng)復(fù)制到和多項(xiàng)式C中。中。2.3.4 雙鏈表priordatanext常用雙向循環(huán)鏈表，如空的常用雙向循環(huán)鏈表，如空的雙向循環(huán)鏈表為：雙向循環(huán)鏈表為：雙鏈表的存儲(chǔ)結(jié)構(gòu)定義：雙鏈表的存儲(chǔ)

47、結(jié)構(gòu)定義：typedef int datatype; typedef struct node datatype data; struct node *prior, *next;dlinklist; dlinklist *head; 2.3.4 雙鏈表ai-1aipai+1p1p2特點(diǎn)：特點(diǎn)： 1. 2. p-prior-next=p=p-next-prior;2.3.4 雙鏈表雙向鏈表的操作雙向鏈表的操作插入實(shí)現(xiàn)插入實(shí)現(xiàn)(后插后插)apxs注意指針修改的注意指針修改的相對(duì)相對(duì)順序順序核心語(yǔ)句：核心語(yǔ)句： s=malloc(sizeof(dlinklist); s-data=x; s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; bcd2.3.4 雙鏈表雙向鏈表的操作雙向鏈表的操作刪除實(shí)現(xiàn)刪除實(shí)現(xiàn)(刪刪p本身本身)ai-1aipai+1核心語(yǔ)句：核心語(yǔ)句： p-prior-next=p-next; p-next-prior=p-prior; free(p); 2.4 順序表和單鏈表的比較存儲(chǔ)分配方式比較存儲(chǔ)分配方式比較順序表順序表采用采用順序存儲(chǔ)順序存儲(chǔ)結(jié)構(gòu)，即用一段地址結(jié)構(gòu)，即用一段地址連續(xù)連續(xù)的的存儲(chǔ)單元存儲(chǔ)單元依次依次存儲(chǔ)線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之存儲(chǔ)線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過(guò)間的邏輯關(guān)系通過(guò)