C++程序设计：第六章 结构和链表

第六章第六章 结构和链表结构和链表6 6.1.1 结构类型结构类型6 6.2.2 结构的应用结构的应用-链表链表6 6.3.3 应用举例应用举例现实生活中的数据现实生活中的数据学生信息学生信息学号姓名性别成绩1150001张小兵男90.351150002李楠女92.13校园一卡通校园一卡通卡号余额身份1150001200学生99088150教师.将不同类型的数据组合成一个有机的整体将不同类型的数据组合成一个有机的整体结构体结构体6.1 6.1 结构类型结构类型 6.1.1 结构类型说明结构类型说明说明结说明结构类型构类型的关键字的关键字 struct 结构类型标识符结构类型标识符 结构成员结构成员1;1;结构成员结构成员2;2;结构成员结构成员n;n;类型可任意类型可任意（不能为该结构自身）（不能为该结构自身）C语言提供了这样一种数据结构：它将不同类型的数据组合成一个有机的整体结构体。struct date int month;int day;int year;struct man char name15;char sex;int age;date birthday;如，说明一个结构类型如，说明一个结构类型datedate，含三个整型数据成员含三个整型数据成员在此基础上，又在此基础上，又可说明另一个结可说明另一个结构类型构类型manmanbirthdayNamesexagemonthdayyear struct man结构类型6.1.2 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;无无类型名变量类型名变量 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;定义一个结构数组并对其部分元素初始化。定义一个结构数组并对其部分元素初始化。6.1.3 6.1.3 结构变量的访问结构变量的访问访问形式：访问形式：结构变量名结构变量名.成员名成员名(*(*指向结构的指针指向结构的指针).).成员名成员名 指向结构的指针指向结构的指针-成员名成员名或或或或通过指向结构的指针引用结构变量成员通过指向结构的指针引用结构变量成员成员访问运算符成员访问运算符优先级最高的优先级最高的四个运算符之一四个运算符之一 括号不能少括号不能少如，假设有定义如，假设有定义man m,*p=&m;strcpy(m.name,Fang Min);p-birthday.month=8;则可则可如下引用结构成员如下引用结构成员【例6.1】某某商商场场周周年年店店庆庆期期间间对对其其会会员员进进行行积积分分换换购购活活动动，活活动动内内容容为为允允许许每每天天前前五五名名光光临临的的会会员员用用其其积积分分换换购购相相应应的的商商品品，假假设设每每100100个个积积分分可可以以换换购购5 5元元的的商商品品，编编程程序序求求该该商商场场店店庆庆期期间间每每天天换换购购出出去去的的商商品品金金额额以以及及会会员员换换购购后后的的剩剩余余积积分分值值。假假设设会会员员将将全全部部可能积分全部进行换购。可能积分全部进行换购。分分析析：可可以以将将会会员员卡卡号号和和积积分分组组合合在在一一起起定定义义一一个个结结构构类类型型，用用结结构数组来描述若干会员的信息。如构数组来描述若干会员的信息。如，struct card char num10;int score;c10;#include iostream.h#define N 5void main()struct card char num10;int score;cN;int i,s=0;for(i=0;ici.numci.score;s=s+5*(ci.score/100);/每每100100分换购分换购5 5元商品元商品 ci.score=ci.score-100*(ci.score/100);/该会员的剩余积分该会员的剩余积分 cout扣除积分后扣除积分后:n;for(i=0;iN;i+)coutci.numtci.scoreendl;cout积分换购金额积分换购金额=sdata=10;q=new node;q-data=20;NULLq-next=NULLp-next=q;6.2.2 6.2.2 链表的建立链表的建立【例例6.36.3】创建一个含有创建一个含有n n个结点的、包含一个数据域，且其类型个结点的、包含一个数据域，且其类型为整型的单链表。为整型的单链表。链表的建立过程如下：链表的建立过程如下：首先设置首先设置headhead为为NULLNULL，即建立一个空的链表。，即建立一个空的链表。申请一个新结点存储区域，让申请一个新结点存储区域，让newnodenewnode指向该结点，然后向其数指向该结点，然后向其数据域输入数据。据域输入数据。把把newnodenewnode所指向的结点插入到链表中。所指向的结点插入到链表中。如果当前链表是空表，如果当前链表是空表，newnodenewnode所指向的结点应该成为该链所指向的结点应该成为该链表中唯一的一个结点，故表中唯一的一个结点，故headhead和和tailtail都应该指向该结点。都应该指向该结点。如果当前链表非空，则如果当前链表非空，则newnodenewnode所指向的结点应该做为链所指向的结点应该做为链表中的最后一个结点加入到链表中，故应该将其插在表中的最后一个结点加入到链表中，故应该将其插在tailtail指指向的结点后面。向的结点后面。重复执行第重复执行第2 2、3 3步共步共n n次。次。将最后一个结点的将最后一个结点的nextnext域置空域置空(NULL)(NULL)。#include iostream.hstruct 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=;/为为newnodenewnode申请存放空间申请存放空间newnode-data=x;new node也可用如下语句也可用如下语句newnode=(struct node*)malloc(sizeof(struct node);if(head=NULL);/newnodenewnode成为空表的第一个结点成为空表的第一个结点 else ;/将将newnodenewnode连接到原来的表尾连接到原来的表尾 ;/newnodenewnode成为新的表尾成为新的表尾 tail-next=NULL;return(head);void main()struct node *head;int n;coutn;head=create(n);head=newnodetail-next=newnodetail=newnode6.2.3 6.2.3 单链表的基本操作单链表的基本操作1 1、链表的遍历、链表的遍历 由于链表的指针域中包含了后继结点的存储地址，所以只要知由于链表的指针域中包含了后继结点的存储地址，所以只要知道该链表的头指针，即可依次对每个结点进行访问。道该链表的头指针，即可依次对每个结点进行访问。【例例6.46.4】输出上例中建立的单链表的各结点的值。输出上例中建立的单链表的各结点的值。分析：分析：假设定义假设定义p p是指向链表中结点的工作指针，该指针从表是指向链表中结点的工作指针，该指针从表头头headhead开始逐一指向后续的各个结点，每指向一个结点，便通过该开始逐一指向后续的各个结点，每指向一个结点，便通过该指针访问结点的数据域，直到指针访问结点的数据域，直到p p的值为的值为NULLNULL。遍历的函数实现如下：遍历的函数实现如下：void print(struct node *head)struct node*p=head;while(p!=NULL)coutdatanext2 2、统计结点个数统计结点个数【例例6.56.5】统计例统计例6.36.3中创建的链表中结点的个数。中创建的链表中结点的个数。分析：分析：设置一个工作指针从表头结点开始，每经过一个结点，设置一个工作指针从表头结点开始，每经过一个结点，计数器的值增加计数器的值增加1 1。实现统计的函数形式如下：。实现统计的函数形式如下：int count(struct node *head)struct node *p=head;int n=0;while(p!=NULL)n+;p=p-next;return(n);3、查找结点【例例6.66.6】在链表中按序号查找第在链表中按序号查找第i i个结点。个结点。分析：分析：设置一个序号计数器设置一个序号计数器j j和一个工作指针和一个工作指针p p，从表头结点开始，从表头结点开始，顺着链表的链进行查找。仅当顺着链表的链进行查找。仅当j=ij=i并且并且p!=NULLp!=NULL时查找成功，否则时查找成功，否则查找不成功。查找不成功。void search(struct node *head,int i)int j=1;struct node *p=head;if(i0)coutillegal indexn;elsewhile(j!=i&p!=NULL)j+;if()coutindexi:data;else coutnextj=i&p!=NULL4 4、在链表中插入结点、在链表中插入结点 假假定定有有一一个个指指针针behind behind 指指向向链链表表中中的的某某个个结结点点，newnodenewnode指指向向待插入结点。待插入结点。newnode12 10 15 19behindfront 如如果果有有一一个个指指针针frontfront指指向向behindbehind的的前前驱驱，则则仅仅需需编编写写下下面面的的两两个语句，即可实现插入。个语句，即可实现插入。;如果没有如果没有behindbehind指针，插入操作仍然可以完成。指针，插入操作仍然可以完成。newnode-next=front-next;front-next=newnode;newnode-next=behindfront-next=newnode两个语句的两个语句的次序能否交次序能否交换？为什么换？为什么？behind7两种特殊情况：两种特殊情况：1.1.在表头结点之前插入：在表头结点之前插入：;2.2.在尾结点之后插入：在尾结点之后插入：;newnodeheadbehind6 7newnode 8 【例例6.76.7】编写函数，实现在头结点为编写函数，实现在头结点为headhead的链表中插入值为的链表中插入值为x x的结点。的结点。newnode-next=behindhead=newnodebehind-next=newnodeNULLnewnode-next=NULLstructstruct node*node*insert(nodeinsert(node*head,inthead,int x)x)structstruct node*behind,*front,*node*behind,*front,*newnodenewnode;newnodenewnode=new node;=new node;newnodenewnode-data=x;behind=head;-data=x;behind=head;if(headif(head=NULL)/=NULL)/空表空表 head=head=newnodenewnode;newnodenewnode-next=NULL;-next=NULL;else /else /非空表非空表 while(behindwhile(behind!=!=NULL&xNULL&xbehind-data)/behind-data)/找插入位置找插入位置 front=behind;behind=front=behind;behind=behindbehind-next;-next;if(behindif(behind=head)/=head)/插到第一个结点前插到第一个结点前 newnodenewnode-next=head;head=-next=head;head=newnodenewnode;else else if(behindif(behind=NULL)/=NULL)/插到最后一个结点后插到最后一个结点后 front-next=front-next=newnodenewnode;newnodenewnode-next=NULL;-next=NULL;else /else /插到插到frontfront之后之后,behind,behind之前之前 front-next=front-next=newnode;newnodenewnode;newnode-next=behind;-next=behind;return head;return head;5 5、删除链表中的某个结点、删除链表中的某个结点 删删除除链链表表中中的的某某个个结结点点，是是把把被被删删除除结结点点的的后后继继结结点点的的地地址址,赋赋给其前趋结点的指针域或表头指针给其前趋结点的指针域或表头指针headhead，无后继结点时，则赋无后继结点时，则赋NULLNULL。假定假定p p为指向要删除结点的指针，为指向要删除结点的指针，q q为指向删除结点前趋的指针。为指向删除结点前趋的指针。如果如果p=headp=head，则删除的是第一个结点，则应修改表头指针，则删除的是第一个结点，则应修改表头指针headhead，使其指向第二个结点，并释放第一个结点占据的存储空间。，使其指向第二个结点，并释放第一个结点占据的存储空间。head=p-next;delete p;如果删除的是链表的中间结点，则应把被删除结点如果删除的是链表的中间结点，则应把被删除结点p p的后继的后继结点的地址，赋给其前趋结点结点的地址，赋给其前趋结点q q的指针域。如果没有后继结的指针域。如果没有后继结点时，则赋空指针点时，则赋空指针NULLNULL。q-next=p-next;delete p;【例例6.86.8】编写函数实现在头结点为编写函数实现在头结点为headhead的链表中删除值为的链表中删除值为x x的结点。的结点。structstruct node*node*delnode(nodedelnode(node*head,inthead,int x)x)structstruct node*p,*q;/p node*p,*q;/p为工作指针为工作指针,q,q为为p p的前驱的前驱 p=head;p=head;if(headif(head=NULL)/=NULL)/空表空表 coutcoutThe list is null!n;data!=x)/-data!=x)/找删除的结点找删除的结点 q=p;p=p-next;q=p;p=p-next;if(pif(p=head)/=head)/删除第一个结点删除第一个结点 head=p-next;delete p;head=p-next;delete p;else else if(pif(p!=NULL)/!=NULL)/删除非表头结点删除非表头结点 q-next=p-next;delete p;q-next=p-next;delete p;else /else /未找到要删除的元素未找到要删除的元素coutcoutxdose not exist in the list!n;xdose not exist in the list!n;return head;6 带表头结点的单链表带表头结点的单链表针对问题:表头结点特殊,在插入和删除结点时要单独处理解决:增加一个伪结点,即表头结点head10203040NULL(1)创建带表头结点的单链表创建带表头结点的单链表Struct node*creat(int n)struct node*head,*tail,*newnode;Int x;head=new node;tial=head;For(int i=1;ix;newnode=new node;newnode-data=x;tail-next=newnode;tail=newnode;tail-next=NULL;return(head);(2)遍历链表 void print(struct node*head)struct node*p;p-head-next;while(p)coutdatanext;(3)结点插入 struct node*insert(struct node *head,int x)struct node*behide,*front,*newnode;newnode=new node;newnode-data=x;front=head;behide=head-next;while(behide&xbehide-data)front=behide;behide=behide-next;If(behide)front-next=newnode;newnode-next=behide;else front-next=newnode;newnode.next=NULL;return(head);（4）结点删除Struct node *delnode(struct node*head,intx)struct node*p,*q;p=head-next;q=head;while(p&p-data!=x)q=p;p=p-next;If(p)q-next=p-next;delete p;elsecoutnext=NULL;while(1)cinx;if(x=0)break;newnode=new node;newnode-data=x;newnode-next=NULL;newnode-next=head-next;/让新结点指向第一个有效结点让新结点指向第一个有效结点 head-next=newnode;/让新结点成为第一个有效结点让新结点成为第一个有效结点 接接whilewhile语句后语句后p=head-next;while(p!=NULL)count+;coutdatanext;coutcount=countendl;