链表的操作ppt课件

1、链表链表是一种数据结构，其中的各对象通过指针按线性顺序排列。链表与数组不同，数组的线性序是由数组下标决定的，而链表中的顺序是由各对象中的指针决定的。链表的每个节点是动态分配的，链表可以用来简单而灵活地表示动态集合。单向链表特点：单向链表特点： 每个链表有一个头指针，通过头指针可以找到第一个节点； 每个节点都可以通过指针域找到它的后继，最后一个节点的指针域为NULL，表示没有后继； 链表不支持随机访问，只能通过前一个元素的指针域得知后一个元素的地址，因此只能从头指针开始顺序访问各节点。 1.1 单向链表单向链表 1.1 单向链表单向链表 图图1 单链表单链表头文件头文件 linkedlist.h

2、/* linkedlist.h */#ifndef LINKEDLIST_H#define LINKEDLIST_Htypedef struct node *link;struct node unsigned char item; link next;link make_node(unsigned char item);void free_node(link p);link search(unsigned char key);void insert(link p);void delete(link p);#endif源文件源文件 linkedlist.c 1、make_node()函数函数st

3、atic link head = NULL;link make_node(unsigned char item) link p = malloc(sizeof *p); p-item = item; p-next = NULL; return p;2、free_node()函数函数void free_node(link p) free(p);3、insert()函数函数void insert(link p) p-next = head; head = p; 4、delete()函数函数void delete(link p) link pre; if (p = head) head = p-ne

4、xt; return; for (pre = head; pre; pre = pre-next) if (pre-next = p) pre-next = p-next; return; 5、traverse()函数函数void traverse(void (*visit)(link) link p; for (p = head; p; p = p-next) printf(%dn, p-item);6、search()函数函数link search(unsigned char key) link p; for (p = head; p; p = p-next) if (p-item = k

5、ey) return p; return NULL;1.2 双向链表双向链表双向链表特点：双向链表特点： 双链表的每个节点都包含一个关键字和两个指针域：next和prev，分别指向它的后继节点与前驱节点。双向链表可以很好地解决单链表删除末节点需开销O(n)时间的问题。1.2 双向链表双向链表图图2 双链表双链表1.2 双向链表双向链表 链表的搜索操作链表的搜索操作 LIST-SEARCH(L, k) 链表的搜索过程采用了简单的线性查找方法，来找出链表L中的第一个具有关键字k的节点，并返回指向该节点的指针。若表中没有包含关键字k的节点，则返回NULL。算法描述如下：x = headLwhile

6、x NULL and keyx kdo x = nextxreturn x1.2 双向链表双向链表 链表的插入操作链表的插入操作 LIST-INSERT(L, x) 给定一个已设置关键字的新节点x，过程LIST-INSERT(L, x)将x插入到链表的前端。算法描述如下：nextx = headLif headL NULL then prevheadL = x headL = xprevx = NULL1.2 双向链表双向链表 链表的删除操作链表的删除操作 LIST-DELETE(L, x) 过程 LIST-DELETE(L, x)从链表L中删除一个节点x，若希望删除具有关键字的节点，则需要先

7、调用LIST-SEARCH(L, k)以得到该节点的指针。算法描述如下：if prevx NULL then nextprevx = nextx else headL = nextxif nextx NULL then prevnextx = prevx1.2 双向链表双向链表双向循环链表：双向循环链表：如果我们把第一个节点的prev指向最后一个节点，而把最后一个节点的next指向第一个节点，这样就形成了一个双向循环链表。哨兵（哨兵（sentinelsentinel）：）： 哨兵（sentinel）是个哑元节点（dummy node），可以简化边界条件，使代码更紧凑，但对速度并没有什么帮助。在

8、基于双向循环链表的实现中，可以设置一个哑元节点（dummy node）。这个节点，起哨兵的作用。也就是说它们并不存储任何实质的数据对象。初始时可以将哑元节点的next指向第一节点，prev指向最后一个节点。1.2 双向链表双向链表 在一个带哨兵的环形双向链表中，哨兵节点介于头和尾之间，用nilL来表示。可以通过nextnilL来访问表头，而用prevnilL来访问表尾。同样地，表尾的next域和表头的prev域都指向nilL。 因为nextnilL指向表头，我们可以去掉属性headL，把对它的引用换成对nextnilL的引用。一个空链表仅含哨兵节点，这时nextnilL和prevnilL都可以设置成nilL。1.2 双向链表双向链表 链表的搜索操作链表的搜索操作 LIST-SEARCH(L, k) 链表的搜索代码，对NULL和headL的引用做了改动。算法描述如下：x = nextnilLwhile x nilL and keyx kdo x = nextxreturn x1.2 双向链表双向链表 链表的插入操作链表的插入操作 LIST-INSERT(L, x)算法描述如下：nextx = nextnilLprevnextnilL = xnextni