第9章链表-II.pptx

计算机程序设计 杨文婧 计算机学院611教研室 第9章 链表 上讲知识回顾 为什么要链表 数据在程序运行过程中动态到达，数量未知 链表基本概念 结点（数据、链）、操作、双向链表 单向链表的定义 结点定义、链表整体定义 链表的操作 建立 空链表、一个结点的链表、多个结点的链表 计算机程序设计 2 本讲主要内容 9.2.2 单向链表的操作 遍历、清空、查找、插入结点 删除结点、排序 提高知识 基于单向链表的队列 基于单向链表的栈 双向链表 计算机程序设计 3 链表的遍历 回顾数组遍历 有几步？ 1. 设置临时标签i 2. 让i指向第一个元素 3. 通过i的递增，使i逐 一指向下一个元素 4. 直到最末元素，结束 链表怎么遍历？ 可否4步走？ 有什么问题？ 整数i用什么替代？ 计算机程序设计 4 int A[10]; …… int i; for(i=0;i10;i++) coutA[i]endl; …… . 链表的遍历 计算机程序设计 5 int A[10]; …… int i; for(i=0;i10;i++) coutA[i]endl; …… . struct node { int data; node* next; }; …… node* head; …… node *tmp; for(tmp=head;tmp!=NULL; tmp=tmp-next) couttmp-dataendl; …… 1. 设置临时指针tmp 2. 让tmp指向首结点 3. 使tmp逐一指向下一个结点 4. 直到尾结点，结束 链表的遍历 能否用while循环实现链表的遍历？ 1. 设置临时指针tmp 2. 让tmp指向首结点 3. 使tmp逐一指向下一个结点 4. 直到尾结点，结束 计算机程序设计 6 node *tmp = head; while(tmp) { couttmp-dataendl; tmp = tmp-next; } 链表的遍历 while循环形式 计算机程序设计 7 node *tmp = head; while(tmp) { couttmp-dataendl; tmp = tmp-next; } NULL tail tmp tmp tmp tmp = NULL head 为什么不直接使用head，而要使用临时变量tmp 如何确定链表中 结点的个数 会找不回链表头 边遍历边计数 int c = 0; c++; 清空链表 链表中的结点都是动态申请（new）来的，用完应该把空间还给（ delete ）系统 清空算法应如何设计？ 从头部删还是从尾部删？ 从头部删应该有几步？ 计算机程序设计 8 . NULL head tail 清空链表 从头部删除结点的清空算法 五步走 设置临时指针指向头结点 头指针指向下一个结点 清空临时指针指向的结点 循环，直到链表为空 设置tail指针为NULL 计算机程序设计 9 . while(head!=NULL) { tmp = head; head = head -next; delete tmp; } tail = NULL; NULL tail tmp head head 链表中的结点查找 按序查找 要求： 给定一个正整数m找到第m个结点 把第m个结点的数据进行读取或更新 按序查找算法应该怎么设计？ 查找算法功能上类似于之前所学的哪个算法？ 计算机程序设计 10 遍历算法！ 链表中的结点查找 链表遍历算法 1. 设置临时指针tmp 2. 让tmp指向首结点 3. 使tmp逐一指向下一个结点 4. 直到尾结点，结束 计算机程序设计 11 node *tmp = head; while(tmp) { couttmp-dataendl; tmp = tmp-next; } 缺少什么？？ 缺少计数！！ 链表中的结点查找 可计数的链表遍历算法 1. 设置临时指针tmp（用于遍历），临时整型变量i（用于计数） 2. 让tmp指向首结点，i=0 3. 使tmp逐一指向下一个结点，i 递增1 4. 直到尾结点，结束 计算机程序设计 12 node *tmp = head; int i=0; while(tmp) { i++; couttmp-dataendl; tmp = tmp-next; } 怎么改成遍历到第m个结点结束？ 链表中的结点查找 按序查找算法 类似于遍历，但只遍历到第m个结点 使用临时变量i计数，值初始化为1 判断条件中增加i 提问： 为什么i从1开始？ 计算机程序设计 13 node * tmp = head; int i = 1; wh