資源描述：
《鏈表格的操作.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、鏈 表鏈表是一種數(shù)據(jù)結構，其中的各對象通過指針按線性順序排列。鏈表與數(shù)組不同，數(shù)組的線性序是由數(shù)組下標決定的，而鏈表中的順序是由各對象中的指針決定的。鏈表的每個節(jié)點是動態(tài)分配的，鏈表可以用來簡單而靈活地表示動態(tài)集合。單向鏈表特點：每個鏈表有一個頭指針，通過頭指針可以找到第一個節(jié)點；每個節(jié)點都可以通過指針域找到它的后繼，最后一個節(jié)點的指針域為NULL，表示沒有后繼；鏈表不支持隨機訪問，只能通過前一個元素的指針域得知后一個元素的地址，因此只能從頭指針開始順序訪問各節(jié)點。1.1單向鏈表31.1單向鏈表圖1單鏈表4頭
2、文件linkedlist.h/*linkedlist.h*/#ifndefLINKEDLIST_H#defineLINKEDLIST_Htypedefstructnode*link;structnode{unsignedcharitem;linknext;};linkmake_node(unsignedcharitem);voidfree_node(linkp);linksearch(unsignedcharkey);voidinsert(linkp);voiddelete(linkp);#endif5源文件
3、linkedlist.c1、make_node()函數(shù)staticlinkhead=NULL;linkmake_node(unsignedcharitem){linkp=malloc(sizeof*p);p->item=item;p->next=NULL;returnp;}2、free_node()函數(shù)voidfree_node(linkp){free(p);}63、insert()函數(shù)voidinsert(linkp){p->next=head;head=p;}74、delete()函數(shù)voiddelete
4、(linkp){linkpre;if(p==head){head=p->next;return;}for(pre=head;pre;pre=pre->next)if(pre->next==p){pre->next=p->next;return;}}85、traverse()函數(shù)voidtraverse(void(*visit)(link)){linkp;for(p=head;p;p=p->next)printf("%d",p->item);}96、search()函數(shù)linksearch(unsigned
5、charkey){linkp;for(p=head;p;p=p->next)if(p->item==key)returnp;returnNULL;}101.2雙向鏈表雙向鏈表特點：雙鏈表的每個節(jié)點都包含一個關鍵字和兩個指針域：next和prev，分別指向它的后繼節(jié)點與前驅節(jié)點。雙向鏈表可以很好地解決單鏈表刪除末節(jié)點需開銷O(n)時間的問題。111.2雙向鏈表圖2雙鏈表121.2雙向鏈表鏈表的搜索操作LIST-SEARCH(L,k)鏈表的搜索過程采用了簡單的線性查找方法，來找出鏈表L中的第一個具有關鍵字k的節(jié)點
6、，并返回指向該節(jié)點的指針。若表中沒有包含關鍵字k的節(jié)點，則返回NULL。算法描述如下：x=head[L]whilex≠NULLandkey[x]≠kdox=next[x]returnx131.2雙向鏈表鏈表的插入操作LIST-INSERT(L,x)給定一個已設置關鍵字的新節(jié)點x，過程LIST-INSERT(L,x)將x插入到鏈表的前端。算法描述如下：next[x]=head[L]ifhead[L]≠NULLthenprev[head[L]]=xhead[L]=xprev[x]=NULL141.2雙向鏈表鏈表的
7、刪除操作LIST-DELETE(L,x)過程LIST-DELETE(L,x)從鏈表L中刪除一個節(jié)點x，若希望刪除具有關鍵字的節(jié)點，則需要先調(diào)用LIST-SEARCH(L,k)以得到該節(jié)點的指針。算法描述如下：ifprev[x]≠NULLthennext[prev[x]]=next[x]elsehead[L]=next[x]ifnext[x]≠NULLthenprev[next[x]]=prev[x]151.2雙向鏈表雙向循環(huán)鏈表：如果我們把第一個節(jié)點的prev指向最后一個節(jié)點，而把最后一個節(jié)點的next指向第
8、一個節(jié)點，這樣就形成了一個雙向循環(huán)鏈表。哨兵（sentinel）：哨兵（sentinel）是個啞元節(jié)點（dummynode），可以簡化邊界條件，使代碼更緊湊，但對速度并沒有什么幫助。在基于雙向循環(huán)鏈表的實現(xiàn)中，可以設置一個啞元節(jié)點（dummynode）。這個節(jié)點，起哨兵的作用。也就是說它們并不存儲任何實質的數(shù)據(jù)對象。初始時可以將啞元節(jié)點的next指向第一節(jié)點，prev指向最后一個節(jié)點。161.2雙向
