C++程序语言08B.ppt

《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;p=p->next){//处理当前结点，访问成员（p->成员）}注意

2、：若函数的形式参数为Player*&head，则在函数体中不要轻易地改变head的指向；若函数的形式参数为Player*head，则改变形参head的指向不影响实参head的指向。遍历链表之——输出所有结点的数据voidShow(constPlayer*node)//输出一个结点的数据{cout<num<<””<name;for(inti=0;i

3、out<<”链表为空。”<next;//参见下一节程序有格式控制的输出}}遍历链表之——释放所有结点这一操作与结点的数据域无关，故可设计成函数模板templatevoidFreeList(T*&head){T*p;while(head!=NULL){p=head;head=head->next;//要求指向下一结点的成员名为nextdeletep;//隐含假定所有的结点皆为堆结点}}上述函数模板适用于多种类型的单向链表，只要求结点结构体

4、中指向下一个结点的指针成员名称为next链表中的所有结点均为堆结点遍历链表之——统计计算统计链表中的结点数由于此项操作与结点的数据域无关，故也可写成函数模板templateintCount(T*head){intn=0;T*p;for(p=head;p!=NULL;p=p->next)n++;returnn;}遍历链表之——统计计算统计满足如下条件的选手（结点）数有三名及三名以上的评委给该选手的分数低于8.5分。intStat(Player*head){intn=0,m,i;Player*p;for(p=head;p!=NULL;p=p->next){m=0;fo

5、r(i=0;i=3)n++;}returnn;}定位某结点——定位、继续定位根据编号查找结点从链首起，依次比较结点数据域中的相应数据项，若找到则返回该结点的地址（不必遍历整个链表）；否则，约定返回NULLPlayer*Search(Player*head,intnum){Player*p;for(p=head;p!=NULL;p=p->next)if(p->num==num)break;returnp;}定位某结点——定位、继续定位查找名次为k的结点特点：可能存在多个满足条件的结点需要定位、继续定位Player*Lo

6、cate(Player*head,intrank,intrestart=0){staticPlayer*p=head;//采用了静态局部指针变量Player*temp;if(restart)p=head;//restart非零时从头开始for(;p!=NULL;p=p->next)if(p->rank==rank)break;temp=p;if(p)p=p->next;//下一次继续搜索的起点returntemp;}voidFind(Player*head){intn,rank;Player*p;cout<<”查询所有第k名的结点。请输入k:”;cin>>rank;n=0;p=Loca

7、te(head,rank,1);//从头开始while(p!=NULL){Show(p);//输出指针p的目标对象的数据成员值n++;p=Locate(head,rank);//继续定位}cout<<”共有”<