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

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

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

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

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

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

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

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

8、Ln-12.2 線性表的順序存儲線性表的順序存儲結(jié)構(gòu)示意圖線性表的順序存儲結(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 順序表是一順序表是一種隨機存取的種隨機存取的存儲結(jié)構(gòu)存儲結(jié)構(gòu)，即，即其其查找操作的查找操作的時間性能為時間性能為O(1)。2.2 線性表的順序存儲一個一維數(shù)組，下標的范圍是到，每個

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

10、結(jié)構(gòu)上生成生成和和顯示顯示該表的該表的C C語言程序。語言程序。 #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; 核心語句：核心語句：法法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 線性表的順序存儲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求表長求表長LENGTH(L):LENGTH(L):取第取第i i個結(jié)點個結(jié)點 GET(L,i):GET(L,i):( (* *L).last+1L).las

12、t+1( (* *L).datai-1L).datai-12.2 線性表的順序存儲二二 基本運算基本運算1 1 插入插入 Insert(Insert(L,x,iL,x,i) ) (i(i從從1 1開始開始) )/在線性表在線性表L L的的第第i i個位置插入值為個位置插入值為x x的的結(jié)點結(jié)點插入前：插入前：( (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、儲要求存儲位置反映邏輯關(guān)系順序存儲要求存儲位置反映邏輯關(guān)系存儲位置要反映這個變化存儲位置要反映這個變化2.2 線性表的順序存儲33例：（例：（35，12，24，42），在第），在第i=2的位置上插入的位置上插入33。表滿：表滿：last+1=MaxSize合理的插入位置：合理的插入位置：1in+1（i指的是元素的序號）指的是元素的序號） 435122442a1a2a3a40 1 2 3 4 表長表長422412335什么時候不能插入什么時候不能插入？注意邊界條件注意邊界條件2.2 線性表的順序存儲插入算法：插入算法： 在線性表的第在線性表的第i i個位置插入一個元素個位置插入一個元素實現(xiàn)步驟：

14、實現(xiàn)步驟： 將第將第n至第至第i 位的元素向后移動一個位置；位的元素向后移動一個位置； 將要插入的元素寫到第將要插入的元素寫到第i個位置；個位置； 表長加表長加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;/ /* * 元素后移一個位置元素后移一個位置* */ / /* * 插入插入x */ /* * 表長加表長加1 1* */ / 核心語句：核心語句：共移動

15、（共移動（n-i+1n-i+1）個元素！）個元素！2.2 線性表的順序存儲具體實現(xiàn)：具體實現(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 線性表的順序存儲時間復(fù)雜度分析：時間復(fù)雜度分析： 插入算法時間主要耗費在插入算法時間主要耗費在移動元素移動元素的操作上的操作上 T(n)= O (移動元素次數(shù)移動元素次數(shù)) 移動元素的次數(shù)取決于插入元素的位置。移動元素的次數(shù)取決于插入元素的位置。討論：討論：若在長度為若在長度為 n 的線性表的第的線性表的第 i 位位 插入一個元素，則向后插入一個元素，則向后移動元素的次數(shù)移動元素的次數(shù)f(n)為為

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

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

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

20、個位置* */ /*表長減表長減1*/ 核心語句：核心語句：共移動（共移動（n-in-i）個元素?。﹤€元素！2.2 線性表的順序存儲具體實現(xiàn)：具體實現(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;依次插入每一個結(jié)點依次插入每一個結(jié)點 csheadbaheadab2.3.2 單鏈表上的基本運算lin

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

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

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

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

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

26、插入空表中*/ elseif(r!=NULL)2.3.2 單鏈表上的基本運算）建立帶頭結(jié)點的單鏈表：）建立帶頭結(jié)點的單鏈表：即：在開始結(jié)點之前附加一個結(jié)點（即：在開始結(jié)點之前附加一個結(jié)點（頭結(jié)點頭結(jié)點），這樣，無），這樣，無論鏈表是否為空，其頭指針始終是指向頭結(jié)點的非空指針。論鏈表是否為空，其頭指針始終是指向頭結(jié)點的非空指針。利用尾插表建表的方法，可以省去空表和非空表的判斷，利用尾插表建表的方法，可以省去空表和非空表的判斷，從而簡化操作。從而簡化操作。頭指針頭指針是是指向指向鏈表中鏈表中第一個結(jié)點第一個結(jié)點（或為（或為頭結(jié)點頭結(jié)點或或為開始結(jié)點為開始結(jié)點）的的指針指針。頭結(jié)點頭結(jié)點是在鏈表的是

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

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

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

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

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

32、,int i) /*按序號查找按序號查找*/ 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平均時間復(fù)雜度為平均時間復(fù)雜度為O(n)2.3.2 單鏈表上的基本運算3單鏈表的插入運算單鏈表的插入運算 假設(shè)假設(shè)p指向某一結(jié)點指向某一結(jié)點, s指向待插入的值為指向待插入的值為x的新的新結(jié)點結(jié)點

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

34、改需要修改*p的前趨結(jié)點的前趨結(jié)點*q的指針域的指針域,則需確定則需確定*q的的位置位置.由于單鏈表沒有指向前趨結(jié)點的指針由于單鏈表沒有指向前趨結(jié)點的指針,則需要從則需要從頭指針開始依次找到頭指針開始依次找到*p的前趨的前趨*q,然后再改變指針然后再改變指針,做做*q的后插操作的后插操作.2.3.2 單鏈表上的基本運算void INSERTBEFORE (linklist *head,linklist *p,datatype x) /*前插：將值為前插：將值為x的新結(jié)點插入的新結(jié)點插入*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;時間復(fù)雜度分析：時間復(fù)雜度分析：最好最好情況（情況（ 在開始結(jié)點之前插）：在開始結(jié)點之前插）：while執(zhí)行執(zhí)行0次，次，O(1)。最壞最壞情況（情況（ 在最后結(jié)點之前插）：在最后結(jié)點之前插）：while執(zhí)行執(zhí)行n次，次，O(n)。平均平均情況（與情況（與p的位置有關(guān)）：的位置有關(guān)）：時間復(fù)雜度為時間復(fù)雜度為O(n)。算法時間主要耗費在算法時間主要耗費在while循環(huán)循環(huán)操作操作總結(jié)：此前插算法性能較差總結(jié)：此前插算法性能較差, ,可作進一步改進可作進一步改進! !2.

36、3.2 單鏈表上的基本運算改進：在改進：在* *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;平均時間復(fù)雜度為平均時間復(fù)雜度為O(1)前插操作變?yōu)楹蟛宀僮髑安宀僮髯優(yōu)楹蟛宀僮?2.3.2 單鏈表上的基本運算實現(xiàn)實現(xiàn) INSERT(L,x,i):分析分析:在單鏈表在單鏈表L的第的第i個結(jié)點之前插入值為個結(jié)點之前插入值為x的結(jié)

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

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

39、n)2.3.2 單鏈表上的基本運算5 5、應(yīng)用舉例：兩個鏈表的歸并、應(yīng)用舉例：兩個鏈表的歸并算法要求：算法要求：已知：已知：線性表線性表 A A、B B，分別由，分別由單鏈表單鏈表 LALA、LBLB 存儲，存儲，其中數(shù)據(jù)元素按值其中數(shù)據(jù)元素按值非遞減有序非遞減有序排列。排列。要求：要求：將將 A A、B B 歸并歸并為一個新的線性表為一個新的線性表C , C C , C 的數(shù)據(jù)的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表元素仍按值非遞減排列。設(shè)線性表C C由由單鏈表單鏈表LCLC存儲，存儲，要求利用要求利用LALA和和LBLB的原有結(jié)點。的原有結(jié)點。假設(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ù)測：預(yù)測：合并后合并后 C =C =（ 2 , 3 , 5 , 6 , 8 , 8 , 9 , 2 , 3 , 5 , 6 , 8 , 8 , 9 , 1111，11 11 ）2.3.2 單鏈表上的基本運算用鏈表可表示為：用鏈表可表示為： 3 511 / 8 LaLa 2 611 / 8 LbLb 9 2 3 6 5 LcLc 8 811 / 911頭結(jié)點頭結(jié)點LaLaLbLbLcLc2.3.2 單鏈表上的基本運算算法分析：算法分析：算法主要包括：算法主要包括：搜索、比較、插入搜索、比較、插入三個操作：三個操作：搜索：搜索：需要

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

42、c) linklist *pa,*pb,*pc; free(Lb); /*釋放釋放Lb的頭結(jié)點的頭結(jié)點*/ return Lc; pc-next = pa?pa:pb ; /*插入剩余結(jié)點插入剩余結(jié)點*/ 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ù)元素，如何實現(xiàn)？實現(xiàn)？2.3.3 循環(huán)鏈表特點：特點： 3head

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

44、3+anxncoefexpnext結(jié)點類型說明：結(jié)點類型說明：typedef struct pnode float coef; /*系數(shù)系數(shù)*/ int exp; /*指數(shù)指數(shù)*/ struct pnode *next;polynode;注：頭結(jié)點的注：頭結(jié)點的coef=0,exp=-1coef=0,exp=-1，多項式中只寫非多項式中只寫非0 0系數(shù)的項系數(shù)的項。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)鏈表 運算規(guī)則運算規(guī)則（1）指數(shù)相同的項，將其對應(yīng)系數(shù)相加，若和不）指數(shù)相同的項，將其對應(yīng)系數(shù)相加，若和不為為0，則形成和多項式中一項；，則形成和多項式中一項；（2）所有指數(shù)不同的項復(fù)制到和多項式中。）所有指數(shù)不同的項復(fù)制到和多項式中。 設(shè)設(shè)q1,q2分別指向多項式分別指向多項式A，B中當(dāng)前檢測的某一中當(dāng)前檢測的某一結(jié)點，結(jié)點，q為和多項式中一結(jié)點。為和多項式中一結(jié)點。則：則：2.3.3 循環(huán)鏈表（1）當(dāng)當(dāng)q1-exp=q2-exp，則系數(shù)相加；，則系數(shù)相加； 若和不為若和不為0:生成和多項式生成和多項式C中一新結(jié)點中一新結(jié)點q，q1,q2指針后移；指針后移； 若和為

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

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特點：特點： 1. 2. p-prior-next=p=p-next-prior;2.3.4 雙鏈表雙向鏈表的操作雙向鏈表的操作插入實現(xiàn)插入實現(xiàn)(后插后插)apxs注意指針修改的注意指針修改的相對相對順序順序核心語句：核心語句： s=malloc(sizeof(dlinklist); s-data=x; s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; bcd2.3.4 雙鏈表雙向鏈表的操作雙向鏈表的操作刪除實現(xiàn)刪除實現(xiàn)(刪刪p本身本身)ai-1aipai+1核心語句：核心語句： p-prior-next=p-next; p-next-prior=p-prior; free(p); 2.4 順序表和單鏈表的比較存儲分配方式比較存儲分配方式比較順序表順序表采用采用順序存儲順序存儲結(jié)構(gòu)，即用一段地址結(jié)構(gòu)，即用一段地址連續(xù)連續(xù)的的存儲單元存儲單元依次依次存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之存儲線性表的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過間的邏輯關(guān)系通過