清華大學(xué)10課件

第11章鏈表及其應(yīng)用1本章主要內(nèi)容鏈表的基本概念鏈表的基本操作方法循環(huán)鏈表雙向鏈表鏈表的應(yīng)用2清華大學(xué)黃維通設(shè)計制作11.1鏈表的基本概念3清華大學(xué)黃維通設(shè)計制作structstu{intnum;floatvalue;數(shù)據(jù)域

charname[20];…structstu*next;指針域};鏈表的存儲結(jié)構(gòu)在內(nèi)存空間上由兩個域組成5清華大學(xué)黃維通設(shè)計制作6清華大學(xué)黃維通設(shè)計制作線性表的順序表示和實現(xiàn)用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。通常用數(shù)組來描述。特點：邏輯上相鄰的兩個元素，在物理上也具有相鄰的存儲位置。可以隨機存取任何一個元素。插入和刪除時需要移動大量元素空間不能充分得到利用表的容量難以擴充7清華大學(xué)黃維通設(shè)計制作

從以上討論可知，線性表順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系相鄰的兩個元素，其物理位置也相鄰，因此可以隨機存取表中任意元素，它的存儲位置可以用一個簡單、直觀的表達(dá)式來表示，但刪除、修改時，需移動大量的元素。而鏈?zhǔn)酱鎯Y(jié)構(gòu)：不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)所具有的弱點，但也失去了順序表可隨機存儲的優(yōu)點。9清華大學(xué)黃維通設(shè)計制作定義：線性表是n個數(shù)據(jù)元素的有限序列。線性表的基本操作判斷線性表是否為空構(gòu)造一個空線性表將一個線性表重置為空表求線性表的元素個數(shù)求線性表的第i個元素的值在線性表中查找第一個滿足指定條件的元素求指定元素的前驅(qū)，即為ai前面的元素ai-1求指定元素的后繼在線性表的第i個元素之前插入一個新元素刪除線性表的第i個元素遍歷線性表銷毀一個線性表線性表的定義和基本操作10清華大學(xué)黃維通設(shè)計制作11.1.2動態(tài)內(nèi)存分配在棧上創(chuàng)建：保存函數(shù)內(nèi)的局部變量，函數(shù)結(jié)束時自動地釋放掉內(nèi)存分配方式從靜態(tài)存儲區(qū)域分配：在程序編譯時分配，在程序的整個運行期間都存在。比如全局變量和靜態(tài)變量從堆上分配：即動態(tài)內(nèi)存分配，用malloc向系統(tǒng)申請一連續(xù)的內(nèi)存空間，不再需要時，用free函數(shù)釋放11清華大學(xué)黃維通設(shè)計制作11.2.1鏈表的建立使第一個結(jié)點的next指針指向第二個結(jié)點cursorcursor13清華大學(xué)黃維通設(shè)計制作如何使第二個結(jié)點的next指針指向第三個結(jié)點呢？cursorcursor14清華大學(xué)黃維通設(shè)計制作【例】創(chuàng)建一個包含表頭結(jié)點和10個結(jié)點的鏈表，假設(shè)這個鏈表表征學(xué)生的數(shù)據(jù)，包含學(xué)生的學(xué)號、考試成績。#include"stdlib.h"#include"stdio.h“#defineLENsizeof(structstu)structstu{intnum;floatscore;structstu*next;};15清華大學(xué)黃維通設(shè)計制作tempnode->score=20.5*i+10;cursor->next=tempnode; //將結(jié)點連接到鏈表上cursor=cursor->next; //移到下一個結(jié)點printf("num=%d,score=%f\n",tempnode->num,tempnode->score);}printf("\n");return(mylist);}

17清華大學(xué)黃維通設(shè)計制作調(diào)用create()函數(shù)的主函數(shù)及鏈表輸出函數(shù)print(structstu*list){structstu*cursor;cursor=list;if(list!=NULL)

do{cursor=cursor->next;//依次遍歷鏈表

printf("%d%f\n",cursor->num,cursor->score);}while(cursor->next!=NULL);}voidmain(){intn; //鏈表結(jié)點數(shù)structstu*my_list;scanf("%d",&n); //輸入鏈表結(jié)點數(shù)my_list=create(n); //返回所創(chuàng)建的鏈表print(my_list);}18清華大學(xué)黃維通設(shè)計制作對鏈表結(jié)點的訪問，必須從頭結(jié)點開始，依次遍歷鏈表，直到找到該結(jié)點(如果所要找的數(shù)據(jù)在鏈表的尾結(jié)點上，則需要遍歷整個鏈表才能找到)。而數(shù)組可以通過下標(biāo)快速定位元素的存儲位置。下面給出找第n個結(jié)點的算法。11.2.2鏈表結(jié)點的訪問

19清華大學(xué)黃維通設(shè)計制作【例】鏈表的連接。structstu*link(structstu*list1,structstu*list2){structstu*cursor;cursor=list1;

while(cursor->next!=NULL)cursor=cursor->next; //找到第一個鏈表的最后一個結(jié)點cursor->next=list2->next; //將兩個鏈表連接起來return(list1);}11.2.3同結(jié)構(gòu)鏈表的連接

21清華大學(xué)黃維通設(shè)計制作11.2.4鏈表結(jié)點的插入

第一種情況：在頭結(jié)點之前插入22清華大學(xué)黃維通設(shè)計制作第二種情況：在鏈表的中間位置插入結(jié)點

23清華大學(xué)黃維通設(shè)計制作【例】無表頭結(jié)點的鏈表中結(jié)點的插入structstu*insert_node(structstu*list,structstu*newnode){structstu*cursor;cursor=list;if(cursor==NULL||cursor->num>newnode->num)//鏈表為空，或新結(jié)點的num值在鏈表結(jié)點中是最小的，則插入到第一個結(jié)點的位置。{newnode->next=cursor;list=newnode;}25清華大學(xué)黃維通設(shè)計制作else//插入表中和表尾的情況同時處理{while(cursor->next&&cursor->next->num<newnode->num)

//若cursor不為尾結(jié)點，且下一結(jié)點的num值仍小于newnode的num值，繼續(xù)向后移動光標(biāo)cursor=cursor->next;newnode->next=cursor->next;cursor->next=newnode; //將newnode插入到cursor與cursor->next之間}returnlist;}26清華大學(xué)黃維通設(shè)計制作【例】刪除帶無表頭結(jié)點的鏈表結(jié)點算法structstu*delete_node_withhead(structstu*list,intvalue){structstu*cursor;cursor=list;if(cursor->num==value){list=cursor->next;free(cursor);}

else//刪除頭結(jié)點{while(cursor->next&&cursor->next->num!=value)cursor=cursor->next;//若cursor->next為有效結(jié)點且不是要刪除//的結(jié)點，則cursor指針向后移動。

if(cursor->next)cursor->next=cursor->next->next;}return(list);}29清華大學(xué)黃維通設(shè)計制作【例】刪除不帶有表頭結(jié)點的鏈表結(jié)點算法structstu*delete_node_withouthead(structstu*list,intvalue){structstu*cursor;cursor=list;

while(cursor->next&&cursor->next->num!=value)cursor=cursor->next;if(cursor->next)//若cursor->next為有效結(jié)點且該結(jié)點不//是要刪除的結(jié)點，cursor指針向后移動cursor->next=cursor->next->next;return(list);}30清華大學(xué)黃維通設(shè)計制作【例】鏈表存儲空間的釋放。voidfree_list(structstu*list){structstu*tempnode;while(list){ tempnode=list; list=list->next; free(tempnode);}}11.2.6釋放鏈表存儲空間

31清華大學(xué)黃維通設(shè)計制作11.3循環(huán)鏈表

帶表頭的空循環(huán)鏈表帶表頭的非空的循環(huán)鏈表32清華大學(xué)黃維通設(shè)計制作structstu_dual{intnum;floatscore;structstu_dual*next;//指向后繼結(jié)點的指針structstu_dual*previous;//指向前驅(qū)結(jié)點的指針}11.4雙向鏈表

雙鏈表的結(jié)構(gòu)定義雙向循環(huán)鏈表33清華大學(xué)黃維通設(shè)計制作對鏈表結(jié)點的操作，要先確定結(jié)點位置，然后才進(jìn)行操作，此外，由于鏈表需要額外的空間開銷，這將影響性能11.5鏈表的應(yīng)用

【例】合并兩個有序鏈表的并從大到小順序輸出排序后的結(jié)果#include"stdlib.h"#include"stdio.h"structstu{intnum;structstu*next;};34清華大學(xué)黃維通設(shè)計制作structstu*Merge(structstu*list1,structstu*list2){structstu*cursor1=list1; //指向list1structstu*cursor2=list2; //指向list2structstu*tmp; //保存插入前cursor2的位置

while(cursor1!=NULL&&cursor2!=NULL){if(cursor2->num<=cursor1->num){tmp=cursor2;cursor2=cursor2->next;tmp->next=cursor1; //插入tmplist1=tmp;cursor1=tmp;}35清華大學(xué)黃維通設(shè)計制作elseif(cursor2->num>cursor1->num&&cursor1->next==NULL){cursor1->next=cursor2;break;}elseif(cursor2->num>cursor1->num&&

cursor2->num<=cursor1->next->num){tmp=cursor2; //cursor2位于cursor1之后后移cursor2cursor2=cursor2->next;tmp->next=cursor1->next;//插入cursor2cursor1->next=tmp;}else cursor1=cursor1->next;}list1=list1->next; return(list