C++程序语言08B.ppt

1、C+程序设计实用教程,清华大学出版社 2008,第8章链表,第2讲,第8章 链表,结构体 链表的概念 链表的操作 小结,本章要点 链表操作,要求 完成一个应用程序,8.3 链表的操作,8.3.1 遍历 输出所有结点的数据 释放所有的结点所占用的堆空间 统计计算 定位某结点及继续定位 8.3.2 插入一个结点 插入到首结点前 插入到链表中间（包括追加到链尾） 8.3.3 删除一个结点 删除链首结点 删除链表中间某结点（包括删除尾结点） 8.3.4 链表版“评委评分”程序清单,8.3.1 遍历,典型的遍历操作采用与下面类似的循环语句 Player *p; for(p=head; p!=NULL;

2、p=p-next) / 处理当前结点，访问成员（p-成员） 注意： 若函数的形式参数为 Player * for(int i=0; inext; / 参见下一节程序有格式控制的输出 ,遍历链表之释放所有结点,这一操作与结点的数据域无关，故可设计成函数模板 template void FreeList(T * / 隐含假定所有的结点皆为堆结点 上述函数模板适用于多种类型的单向链表，只要求 结点结构体中指向下一个结点的指针成员名称为next 链表中的所有结点均为堆结点,遍历链表之统计计算,统计链表中的结点数 由于此项操作与结点的数据域无关，故也可写成函数模板 template int Count(

3、T *head) int n=0; T *p; for(p=head; p!=NULL; p=p-next) n+; return n; ,遍历链表之统计计算,统计满足如下条件的选手（结点）数 有三名及三名以上的评委给该选手的分数低于8.5分。 int Stat(Player *head) int n=0, m, i; Player *p; for(p=head; p!=NULL; p=p-next) m = 0; for(i=0; i=3) n+; return n; ,定位某结点定位、继续定位,根据编号查找结点 从链首起，依次比较结点数据域中的相应数据项， 若找到则返回该结点的地址（不必遍

4、历整个链表）； 否则，约定返回NULL Player *Search(Player *head, int num) Player *p; for(p=head; p!=NULL; p=p-next) if(p-num = num) break; return p; ,定位某结点定位、继续定位,查找名次为 k 的结点 特点：可能存在多个满足条件的结点 需要定位、继续定位 Player*Locate(Player*head,int rank,int restart=0) static Player *p=head; / 采用了静态局部指针变量 Player *temp; if(restart) p

5、 = head; / restart非零时从头开始 for( ; p!=NULL; p=p-next) if(p-rank = rank) break; temp = p; if(p) p = p-next; / 下一次继续搜索的起点 return temp; ,void Find(Player *head) int n, rank; Player *p; cout rank; n = 0; p = Locate(head, rank, 1); / 从头开始 while(p!=NULL) Show(p); / 输出指针p的目标对象的数据成员值 n+; p = Locate(head, rank

6、); / 继续定位 cout ”共有 ” n ” 位选手并列第 ” rank ” 名。” endl; ,8.3.2 插入一个结点,插入到链首结点前(成为新的链首结点) 包括插入一个结点到空链表中（已经介绍，略） 插入到中间 追加(到链尾结点后，成为新的尾结点） 后两种情形的处理方法相同； 需要排除空链表的情形； 插入一个结点的操作与插入点前后的两个结点相关。查找前一个结点（“前哨”）成为算法实现的关键。,head,18,18, 定位前哨, 创建堆对象 成员赋值, 新结点指向 下一个结点, 前哨结点 指向新结点,8.3.3 删除一个结点,删除链首结点 已经介绍（略） 删除链表中间某结点 删除尾结点 后两种情形的处理方法相同 需要排除空链表的情形 删除一个结点的操作与待删结点前后的两个结点相关。查找前一个结点（“前哨”）成为算法实现的关键。,10, 定位前哨, 记录待删结点地址, 前哨结点指向待删 结点的下一结点, 释放待删结点所占 用的堆内存空间,隐含假定： 结点均为堆对象,8.3.4 链表版“评委评分”程序设计,constest.h 声明结构体类型 函数原型 constest.cpp 函数定义 Main.cpp