圳职业技术学院 Shenzhen Polytechnic 第十单元:链表 教学内容 链表,用 typedef定义类型 教学目标 应知 了解链表的结构,链表基本操作的含义 能够写出C语言对链表节点的结构描述 能够写出有关链表操作的关键实现语句 应会 有关链表操作的关键实现语句:创建,插入,删除,输出 难点 链表的结构特点和操作处理 1.专业英语词汇 英文词汇 中文名 create 创建 insert 插入 删除 modify 修改 教学方法 形象比喻,注重思路引导 教学过程 1.回答下列问题 什么是链表? 为什么使用链表? 链表的数据结构有何特点 链表结构同数组相比有什么优点? 链表将涉及到我们之前学过的什么内容?又有什么新内容? 静态连表与动态链表有什么区别? 2.动态链表的操作型 假设一个链表由5个节点构成,节点数据是学生的学号和姓名(链表按学生学号的 升序排列),则此链表在内存中的存储方式示意如下 计算机系乌云高娃 Wygwg2lcn. com 第73页共83页
深 圳 职 业 技 术 学 院 Shenzhen Polytechnic 计算机系乌云高娃 Wygw@21cn.com 第 73 页 共 83 页 第十单元：链表 教学内容 链表,用 typedef 定义类型 教学目标 了解链表的结构，链表基本操作的含义 能够写出 C 语言对链表节点的结构描述 应知 能够写出有关链表操作的关键实现语句 应会 有关链表操作的关键实现语句：创建，插入，删除，输出 难点 链表的结构特点和操作处理 1. 专业英语词汇 英文词汇 中文名 create 创建 insert 插入 delete 删除 modify 修改 教学方法 形象比喻，注重思路引导 教学过程 1. 回答下列问题: 什么是链表? 为什么使用链表? 链表的数据结构有何特点 链表结构同数组相比有什么优点? 链表将涉及到我们之前学过的什么内容?又有什么新内容? 静态连表与动态链表有什么区别? 2. 动态链表的操作型 假设一个链表由５个节点构成，节点数据是学生的学号和姓名（链表按学生学号的 升序排列），则此链表在内存中的存储方式示意如下
深圳职业技术学院 Shenzhen Polytechnic 该节点地址 学生学号 学生姓名 节点中的next指针 2000H 9911104 Alice 202BH 2010H 9911129 Tom NULL 2020H 9911118 Jordan 201OH 202BH 9911105 Allen 201AH 201AH 9911108 Rodman 2020H 9911104→9911105→9911108→9911118→9911129 3.创建动态链表 问题:怎样输入节点 怎样使节点相链 思路 ①p1指向新建结点 ②p2=p1;使p2指向新节点,即p2指向链表中最后一个节点 ③pl再指向更新的节点 ④pl=p2-next;使旧节点链上新节点 ⑤p2=pl;使p2指向新节点,即p2指向链表中最后一个节点,再到第③步,如此循环输 入 4.删除结点 问题:怎样找到将要删除的节点 如何实现节点删除 思路 ①假设有a,b,c,d,e五个节点,要删的节点是 ②在链表中寻找要删的节点,先使p1,p2同指头节点,如果不是目标,p1后移 ③如仍然不是目标,p2=p1,p2也已过来 ④p1再指向下一个节点,p1=p1-next ⑤如果发现是目标节点,则删除,p2->next=p1-next,表示删除节点p1.(p2是 p1的前一个节点 5.插入结点 问题:怎样找到插入位置 怎样实现插入 思路 计算机系乌云高娃 Wygwg2lcn. com 第74页共83页
深 圳 职 业 技 术 学 院 Shenzhen Polytechnic 计算机系乌云高娃 Wygw@21cn.com 第 74 页 共 83 页 该节点地址 学生学号 学生姓名 节点中的 next 指针 2000H 9911104 Alice 202BH 2010H 9911129 Tom NULL 2020H 9911118 Jordan 2010H 202BH 9911105 Allen 201AH 201AH 9911108 Rodman 2020H 9911104→9911105→9911108→9911118→9911129 3. 创建动态链表 问题: 怎样输入节点 怎样使节点相链 思路: ① p1 指向新建结点 ② p2 = p1;使 p2 指向新节点,即 p2 指向链表中最后一个节点 ③ p1 再指向更新的节点 ④ p1 = p2 ->next; 使旧节点链上新节点 ⑤ p2 = p1;使 p2 指向新节点,即 p2 指向链表中最后一个节点,再到第③步,如此循环输 入 4. 删除结点 问题: 怎样找到将要删除的节点 如何实现节点删除 思路: ① 假设有 a,b,c,d,e 五个节点,要删的节点是 s ② 在链表中寻找要删的节点,先使 p1,p2 同指头节点,如果不是目标,p1 后移 ③ 如仍然不是目标,p2=p1,p2 也已过来 ④ p1 再指向下一个节点,p1 = p1 ->next ⑤ 如果发现是目标节点,则删除, p2 ->next = p1 -> next,表示删除节点 p1.(p2 是 p1 的前一个节点) 5. 插入结点 问题: 怎样找到插入位置 怎样实现插入 思路:
圳职业技术学院 Shenzhen Polytechnic ①假设p0为待插入节点,先使p1,p2都指向头节点,比较pl-num和p0->num,寻找待 插入位置,如果不是目标,使pl指向下一个节点,再比较pl->nm和p0->num ②如果不是目标位置,使p2指向刚比过的p1,p2=pl ③p1再指向下一节点,p1=pl-next,再比较 ④找到目标位置,插入p0,两条语句p2->next=p0;p0->next=pl;表示p0插入到p2 和p1之间(p2是pl的前一个节点) ⑤如插入到表头:head=p0;p0->next=p1 ⑥如插入到表尾:p1->next=p0;p0->next=NULL; ⑦如插入到空表:head=p0;p0->next=NULL 6.链表输出 思路:从头节点开始(p=head) 打印完指向下一个节点(p=p-next) 直到节点为NULL 学生容易出错的地方 创建链表时每个新节点都应该申请空间 插入、删除操作时的指针移位理解不透 厚最后一个节点的next指针赋值为NULL 问题与讨论 指向结构变量的指针如何定义和使用? 链表的定义和常用操作? 链表节点在C语言中如何描述? 如何申请和释放节点空间? 小结(可由问题与讨论方式给出) 链表是一种动态存储结构,可以按需随时分配存储空间 计算机系乌云高娃 Wygwl2lcn, com第75页共83页
深 圳 职 业 技 术 学 院 Shenzhen Polytechnic 计算机系乌云高娃 Wygw@21cn.com 第 75 页 共 83 页 ① 假设 p0 为待插入节点,先使 p1,p2 都指向头节点,比较 p1->num 和 p0->num,寻找待 插入位置,如果不是目标,使 p1 指向下一个节点,再比较 p1->num 和 p0->num ② 如果不是目标位置,使 p2 指向刚比过的 p1, p2 = p1 ③ p1 再指向下一节点,p1 = p1 -> next ,再比较 ④ 找到目标位置,插入 p0, 两条语句 p2->next=p0; p0->next=p1;表示 p0 插入到 p2 和 p1 之间（p2 是 p1 的前一个节点） ⑤ 如插入到表头: head=p0; p0->next=p1; ⑥ 如插入到表尾: p1->next=p0; p0->next=NULL; ⑦ 如插入到空表: head=p0; p0->next=NULL; 6. 链表输出 思路: 从头节点开始（p=head） 打印完指向下一个节点(p=p->next) 直到节点为 NULL 学生容易出错的地方 创建链表时每个新节点都应该申请空间 插入、删除操作时的指针移位理解不透 最后一个节点的 next 指针赋值为 NULL 问题与讨论 指向结构变量的指针如何定义和使用？ 链表的定义和常用操作？ 链表节点在 C 语言中如何描述？ 如何申请和释放节点空间？ 小结（可由问题与讨论方式给出） 链表是一种动态存储结构，可以按需随时分配存储空间
圳)职业技术学院 Shenzhen Polytechni 课后任务 日 整理课堂笔记 尝试调通链表程序 计算机系乌云高娃 Wygwl2lcn, com第76页共83页
深 圳 职 业 技 术 学 院 Shenzhen Polytechnic 计算机系乌云高娃 Wygw@21cn.com 第 76 页 共 83 页 课后任务 整理课堂笔记 尝试调通链表程序