数据结构——用C语言描述 蔡明志 教学课件 第四章 链表.pdfVIP

21世纪高等院校规划教材 第4章第4章 链链 表表 返回总目录 4.1 ©2006 链表链表  关于链表  单向链表及其插入操作和删除操作  循环链表及其插入操作和删除操作  双向链表及其插入操作和删除操作  链表的应用 4.2 ©2006 关于链表关于链表  链表： 链表（linked list）是由许多节点所组成的。  链表的种类： 链表可分为单向链表（single linked list）、循环链表 （circular linked list）及双向链表（doubly linked list）。 4.3 ©2006 单向链表单向链表  利用数组的方式存放数据时，一般所配置的内存皆会 比实际所要的空间多，会造成空间的浪费，而链表就 不会，因为链表是根据实际的需要配置内存的。  链表在插入与删除时都比数组简单容易，只要利用指 针（pointer）加以处理就可以了。在查找上，数组 比链表来得快，因为从数组索引（index）便可得到 想要的数据；而链表需要花较多的时间去比较方可找 到正确的数据。  链表中的插入与删除操作可分为前端、尾端或是针对 某一特定节点三种操作方式。 4.4 ©2006 插入操作示例(1)插入操作示例(1)  插入链表的前端 假设有一个链表B如图4-2所示。有一节点x将插入于链表的前端，其 操作步骤如下： （1）x=(struct node *) malloc(sizeof(struct node))，如图4-3 所示。 （2）x-next=head-next，如图4-4所示。/* ① */ （3）head-next=x，如图4-5所示。/* ② */ 4.5 ©2006 插入操作示例插入操作示例——步骤示意图步骤示意图  插入链表的前端的操作步骤示意图： 图4-2 链表B的数据结构图 图4-3 执行第（1）步后的链表示意图 图4-4 执行第（2）步后的链表示意图 图4-5 执行第（3）步后的链表示意图 4.6 ©2006 插入操作示例(2)插入操作示例(2) 插入于链表的尾端 假设有一个链表C如图4-6所示 . 将一个节点x插入到链表的尾端，其步骤如下： (1)x=(structnode*)malloc(sizeof(struct node))，如图4-7 所示。 (2)x-next=NULL，如图4-8所示。 (3)p-next=x; 执行第（3）步后的链表示意图如图4-9所示。 4.7 ©2006 插入操作示例插入操作示例——步骤示意图步骤示意图  插入链表的尾端的操作步骤示意图： 图4-6 链表C的数据结构图 图4-7 执行第（1）步后的链