链表格的操作.ppt

《链表格的操作.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、链　表链表是一种数据结构，其中的各对象通过指针按线性顺序排列。链表与数组不同，数组的线性序是由数组下标决定的，而链表中的顺序是由各对象中的指针决定的。链表的每个节点是动态分配的，链表可以用来简单而灵活地表示动态集合。单向链表特点：每个链表有一个头指针，通过头指针可以找到第一个节点；每个节点都可以通过指针域找到它的后继，最后一个节点的指针域为NULL，表示没有后继；链表不支持随机访问，只能通过前一个元素的指针域得知后一个元素的地址，因此只能从头指针开始顺序访问各节点。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()函数staticlinkhead=NULL;linkmake_node(unsignedcharitem){linkp=malloc(sizeof*p);p->item=item;p->next=NULL;returnp;}2、free_node()函数voidfree_node(linkp){free(p);}63、insert()函数voidinsert(linkp){p->next=head;head=p;}74、delete()函数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()函数voidtraverse(void(*visit)(link)){linkp;for(p=head;p;p=p->next)printf("%d",p->item);}96、search()函数linksearch(unsigned

5、charkey){linkp;for(p=head;p;p=p->next)if(p->item==key)returnp;returnNULL;}101.2双向链表双向链表特点：双链表的每个节点都包含一个关键字和两个指针域：next和prev，分别指向它的后继节点与前驱节点。双向链表可以很好地解决单链表删除末节点需开销O(n)时间的问题。111.2双向链表图2双链表121.2双向链表链表的搜索操作LIST-SEARCH(L,k)链表的搜索过程采用了简单的线性查找方法，来找出链表L中的第一个具有关键字k的节点

6、，并返回指向该节点的指针。若表中没有包含关键字k的节点，则返回NULL。算法描述如下：x=head[L]whilex≠NULLandkey[x]≠kdox=next[x]returnx131.2双向链表链表的插入操作LIST-INSERT(L,x)给定一个已设置关键字的新节点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中删除一个节点x，若希望删除具有关键字的节点，则需要先调用LIST-SEARCH(L,k)以得到该节点的指针。算法描述如下：ifprev[x]≠NULLthennext[prev[x]]=next[x]elsehead[L]=next[x]ifnext[x]≠NULLthenprev[next[x]]=prev[x]151.2双向链表双向循环链表：如果我们把第一个节点的prev指向最后一个节点，而把最后一个节点的next指向第

8、一个节点，这样就形成了一个双向循环链表。哨兵（sentinel）：哨兵（sentinel）是个哑元节点（dummynode），可以简化边界条件，使代码更紧凑，但对速度并没有什么帮助。在基于双向循环链表的实现中，可以设置一个哑元节点（dummynode）。这个节点，起哨兵的作用。也就是说它们并不存储任何实质的数据对象。初始时可以将哑元节点的next指向第一节点，prev指向最后一个节点。161.2双向