C++第六章结构和链表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第六章 结构和链表,6,.1,结构类型,6,.2,结构的应用,-,链表,6,.3,应用举例,1,6.1,结构类型,6.1.1,结构类型说明,说明结,构类型,的关键字,struct,结构类型标识符,结构成员,1;,结构成员,2;,结构成员,n;,;,类型可任意,（不能为该结构自身）,C,语言提供了这样一种数据结构：它将不同类型的数据组合成一个有机的整体,结构体。,2,struct,date,int,month;,int,day;,int,year;,;,struct,man,char name15;,char sex;,int,age;,date birthday;,;,如，说明一个结构类型,date,，,含三个整型数据成员,在此基础上，又可说明另一个结构类型,man,birthday,Name,sex,age,month,day,year,struct,man,结构类型,3,6.1.2,结构变量定义及初始化,先说明结构类型再定义结构变量,在说明结构数据类型的同时定义结构变量,省略结构标识符直接定义结构类型变量,struct,man man1,man2;,struct,man,char name15;,char sex;,int,age;,struct,date birthday;,man1,man2;,struct,char name15;,char sex;,int,age;,struct,date birthday;,man1,man2;,无,类型名变量,4,struct,goods /,定义一个商品结构类型,char bh6;/,商品编号,char mc20;/,商品名称,float,dj,;/,商品单价,int,sl,;/,商品数量,char jhrq8;/,进货日期,g1=10012,shoes,124,100,080912,；,结构变量也允许在定义的同时给出初值，即初始化。如：,struct,person,char name15;,char sex;,int,age;s10=Fang Min,F,24,Fang Hua,M,35;,定义一个结构数组并对其部分元素初始化。,5,6.1.3,结构变量的访问,访问形式：,结构变量名,.,成员名,(*,指向结构的指针,).,成员名,指向结构的指针,-,成员名,或,或,通过指向结构的指针引用结构变量成员,成员访问运算符,优先级最高的,四个运算符之一,括号不能少,如，假设有定义,man m,*p=,strcpy,(m.name,Fang Min);,p-birthday.month=8;,则可,如下引用结构成员,6,【,例,6.1】,某商场周年店庆期间对其会员进行积分换购活动，活动内容为允许每天前五名光临的会员用其积分换购相应的商品，假设每,100,个积分可以换购,5,元的商品，编程序求该商场店庆期间每天换购出去的商品金额以及会员换购后的剩余积分值。假设会员将全部可能积分全部进行换购。,分析：可以将会员卡号和积分组合在一起定义一个结构类型，用结构数组来描述若干会员的信息。如，,struct,card,char num10;,int score;,c10;,7,#include,iostream.h,#define N 5,void main(),struct,card,char num10;,int score;,cN;,int,i,s,=0;,for(i,=0;ici.numci.score;,s=s+5*(ci.score/100);/,每,100,分换购,5,元商品,ci.score,=ci.score-100*(ci.score/100);/,该会员的剩余积分,cout,扣除积分后,:n;,for(i,=0;i,N;i,+),cout,ci.num,t,ci.score,endl,;,cout,积分换购金额,=sdata=10;,q=new node;,q-data=20;,NULL,q-next=NULL,p-next=q;,19,6.2.2,链表的建立,【,例,6.3】,创建一个含有,n,个结点的、包含一个数据域，且其类型为整型的单链表。,链表的建立过程如下：,首先设置,head,为,NULL,，即建立一个空的链表。,申请一个新结点存储区域，让,newnode,指向该结点，然后向其数据域输入数据。,把,newnode,所指向的结点插入到链表中。,如果当前链表是空表，,newnode,所指向的结点应该成为该链表中唯一的一个结点，故,head,和,tail,都应该指向该结点。,20,如果当前链表非空，则,newnode,所指向的结点应该做为链表中的最后一个结点加入到链表中，故应该将其插在,tail,指向的结点后面。,重复执行第,2,、,3,步共,n,次。,将最后一个结点的,next,域置空,(NULL),。,21,#include,iostream.h,struct,node,int,data;,struct,node *next;,;,struct,node *,create(int,n),struct,node *head=NULL;,struct,node *tail,*,newnode,;,int,x;,for(,int,i=0;ix;,newnode,=;/,为,newnode,申请存放空间,newnode,-data=x;,new node,也可用如下语句,newnode,=(,struct,node*),malloc(sizeof,(,struct,node);,22,if(head,=NULL),;/,newnode,成为空表的第一个结点,else,;/,将,newnode,连接到原来的表尾,;/,newnode,成为新的表尾,tail-next=NULL;,return(head,);,void main(),struct,node *head;,int,n;,cout,n;,head=,create(n,);,head=,newnode,tail-next=,newnode,tail=,newnode,23,6.2.3,单链表的基本操作,1,、链表的遍历,由于链表的指针域中包含了后继结点的存储地址，所以只要知道该链表的头指针，即可依次对每个结点进行访问。,【,例,6.4】,输出上例中建立的单链表的各结点的值。,假设定义,p,是指向链表中结点的工作指针，该指针从表头,head,开始逐一指向后续的各个结点，每指向一个结点，便通过该指针访问结点的数据域，直到,p,的值为,NULL,。,24,遍历的函数实现如下：,void,print(struct,node *head),struct,node*p=head;,while(p,!=NULL),cout,datanext,25,2,、统计结点个数,【,例,6.5】,统计例,6.3,中创建的链表中结点的个数。,设置一个工作指针从表头结点开始，每经过一个结点，计数器的值增加,1,。实现统计的函数形式如下：,int,count(struct,node *head),struct,node *p=head;,int,n=0;,while(p!=NULL),n+;,p=p-next;,return(n,);,26,3,、查找结点,【,例,6.6】,在链表中按序号查找第,i,个结点。,设置一个序号计数器,j,和一个工作指针,p,，从表头结点开始，顺着链表的链进行查找。仅当,j=i,并且,p!=NULL,时查找成功，否则查找不成功。,27,void,search(struct,node *head,int,i),int,j=1;,struct,node *p=head;,if(i,0),cout,illegal indexn;,else,while(j,!=i&p!=NULL),j+;,;,if(),cout,data;,else,cout,next,j=,i&p,!=NULL,28,4,、在链表中插入结点,假定有一个指针,behind,指向链表中的某个结点，,newnode,指向待插入结点。,newnode,12,10 15 19,behind,front,如果有一个指针,front,指向,behind,的前驱，,则仅需编写下面的两个语句，即可实现插入。,;,;,如果没有,behind,指针，插入操作仍然可以完成。,newnode,-next=front-next;,front-next=,newnode,;,思考题：上述两个语句的次序能否交换？为什么？,newnode,-next=behind,front-next=,newnode,29,behind,7,两种特殊情况：,1.,在表头结点之前插入：,;,;,2.,在尾结点之后插入：,;,;,newnode,head,behind,6,7,newnode,8,【,例,6.7】,编写函数，实现在头结点为,head,的链表中插入值为,x,的结点。,newnode,-next=behind,head=,newnode,behind-next=,newnode,NULL,newnode,-next=NULL,30,struct,node*,insert(node,*,head,int,x),struct,node*behind,*front,*,newnode,;,newnode,=new node;,newnode,-data=x;behind=head;,if(head,=NULL)/,空表,head=,newnode,;,newnode,-next=NULL;,else /,非空表,while(behind,!=,NULL&x,behind-data)/,找插入位置,front=behind;behind=,behind,-next;,if(behind,=head)/,插到第一个结点前,newnode,-next=head;head=,newnode,;,else,if(behind,=NULL)/,插到最后一个结点后,front-next=,newnode,;,newnode,-next=NULL;,else /,插到,front,之后,behind,之前,front-next=,newnode;newnode,-next=behind;,return head;,31,5,、删除链表中的某个结点,删除链表中的某个结点，是把被删除结点的后继结点的地址,赋给其前趋结点的指针域或表头指针,head,，,无后继结点时，则赋,NULL,。,假定,p,为指向要删除结点的指针，,q,为指向删除结点前趋的指针。,如果,p=head,，则删除的是第一个结点，则应修改表头指针,head,，使其指向第二个结点，并释放第一个结点占据的存储空间。,head=p-next;,delete p;,32,如果删除的是链表的中间结点，则应把被删除结点,p,的后继结点的地址，赋给其前趋结点,q,的指针域。如果没有后继结点时，则赋空指针,NULL,。,q-next=p-next;,delete p;,33,【,例,6.8】,编写函数实现在头结点为,head,的链表中删除值为,x,的结点。,struct,node*,delnode(node,*,head,int,x),struct,node*p,*q;/p,为工作指针,q,为,p,的前驱,p=head;,if(head,=NULL)/,空表,cout,data!=x)/,找删除的结点,q=p;p=p-next;,if(p,=head)/,删除第一个结点,head=p-next;delete p;,else,if(p,!=NULL)/,删除非表头结点,q-next=p-next;delete p;,else /,未找到要删除的元素,cout,x,next=p,-,link;,p,-,next=,newnode,;,head,newnode,head,newnode,插入,head,newnode,head,newnode,插入,p,p,p,p,非空表,空表,可见，空表和非空表的操作是一致的，无需再分别讨论，,简化,了操作。,36,q=p,-,next;,p,-,next=q,-,next;,delete q;,从带表头结点的单链表中删除最前端的结点,head,head,head,head,p,q,p,q,可见，即使删除后为空表，也无需修改,head,，与非空表操作一致,37,6.3,应用举例,【,例,6.9】,建立一个带表头结点的单链表，要求每次都将最后加入的结点加到最前面，结点中的数据均是不为,0,的整数（要求输入,0,时建立过程结束），然后统计结点个数并输出结点中的所有数据。,分析,根据题意，建立该链表的过程是不断向表头插入新结点的过程。考虑到题目要求建立的是一个含表头结点的单链表，因此新结点应加入到伪结点的后面，成为第一个有效结点。,38,#include,iostream.h,struct,node,int,data;,struct,node*next;,;,void main(),struct,node *head,*,newnode,*p;,int,x,count,=0;,head=new node;,head-next=NULL;,while(1),cin,x;,if(x,=0)break;,newnode,=new node;,newnode,-data=x;,newnode,-next=NULL;,newnode,-next=head-next;/,让新结点指向第一个有效结点,head-next=,newnode,;/,让新结点成为第一个有效结点,接,while,语句后,p=head-next;,while(p,!=NULL),count+;,cout,datanext;,cout,count=count,endl,;,39,