第8次课--链表结点的插入和删除.pptVIP

教案 主要内容 链表结点的插入 单链表结点的插入（1） 单链表结点的插入（2） 单链表结点的插入（3） 单链表结点的插入（4） 单链表结点插入举例 主函数模块 插入子模块 链表结点的删除 单链表结点的删除（1） 单链表结点的删除（2） 单链表结点删除举例 删除子模块 任务相关部分 本次课总结 下课 《C语言与数据结构》 第6次课-----循环结构 * 第7章 第8次课----链表结点的插入和删除 《C语言与数据结构》 1.单链表中结点插入算法的实现 2.单链表中结点删除算法的实现 教学重点 考虑带附加头结点和不带附加头结点两种情况 教学难点 通过本次课的学习，使学生掌握单链表中结点的插入与删除方法。 教学目标 链表结点的插入和删除 教学主题 单链表中结点插入算法实现 单链表中结点插入举例 单链表中结点删除算法实现 单链表中结点删除举例 在链表中插入结点有很多情况。 下面以带附加头结点的单链表为例进行介绍。 在指定结点的后面插入新结点 插入过程图示（在p结点后面插入新结点q）： 实现语句： q-next = p-next; p-next = q; 在指定结点的前面插入新结点 在p结点前面插入新结点q的步骤： （1）寻找p结点的前驱结点，使s指向它。 （2）在s结点的后面插入q结点。 实现语句： s=head; while (s-next!=p) s=s-next; q-next = s-next; s-next = q; 在值为x的结点后插入一个值为y的结点 步骤： （1）申请一个结点空间，用q指向它，并把y放入其中。 （2）在链表中查找值为x的结点，找到后用p指向它。 （3）在p结点后插入q结点。 实现语句： 看源程序(8_1) 在值为x的结点前插入一个值为y的结点 步骤： （1）申请一个结点空间，用q指向它，并把y放入其中。 （2）在链表中查找值为x的结点，找到后用p指向它，pf指向它的前驱结点。 （3）在pf结点后插入q结点。 实现语句（两种方法）： 看源程序(8_2) 看源程序(8_3) 【补例】将【例7-5】改成用菜单选择实现，并在此基础上增加插入功能。 分析 插入时，按照以下几种情况进行： （1）插入到链首。 （2）插入到链尾。 （3）插入到指定值的后面。 （4）插入到指定值的前面。 【补例】将【例7-5】改成用菜单选择实现，并在此基础上增加插入功能。 主函数流程图 源程序 运行程序(8_4) 看源程序(8_4) 【补例】将【例7-5】改成用菜单选择实现，并在此基础上增加插入功能。 插入子函数流程图 源程序 运行程序(8_4) 看源程序(8_4) 思考：不用附加头结点，任何修改？(8_6) 在链表中删除结点也有很多情况。 下面以带附加头结点的单链表为例进行介绍。 删除指定结点 删除过程图示（删除q结点的后继结点p）： 实现语句： q-next = p-next; free(p); 删除值为x的结点 步骤： （1）在链表中查找值为x的结点，找到后用p指向它，q指向它的前驱结点。 （2）使p结点脱离链表。 （3）释放p结点的内存空间。 实现语句： 看源程序(8_5) 【补例】在【例7-5】的基础上增加删除功能。 分析 删除时，按照以下几种情况进行： （1）删除链首结点。 （2）删除链尾结点。 （3）删除指定值的结点。 【补例】在【例7-5】的基础上增加删除功能。 删除子函数流程图 源程序 运行程序(8_4) 看源程序(8_4) 思考：不用附加头结点，任何修改？(8_6) 任务程序中的功能“添加一个学生”和“删除一个学生”，实际上就是在链表中插入和删除结点的过程。 单链表中结点插入算法实现 单链表中结点插入举例 单链表中结点删除算法实现 单链表中结点删除举例 使用时，直接删除本页！ 精品课件，你值得拥有！ 精品课件，你值得拥有！ 使用时，直接删除本页！ 精品课件，你值得拥有！ 精品课件，你值得拥有！ 《C语言与数据结构》 第6次课-----循环结构 * 第7章 第8次课----链表结点的插入和删除 《C语言与数据结构》 * *