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

1、第六章 结构和链表,6.1 结构类型 6.2 结构在链表中的应用 6.3 应用程序,说明结 构类型 的关键字,6.1.1 结构类型的说明,C+中的类从C语言中的结构概念演变而来,结构类型说明形式,struct 结构类型标识符 结构成员1; 结构成员2; 结构成员n; ;,类型可任意 （不能为该结构自身）,struct person char name15; char sex; int age; ;,struct date int month; int day; int year; ;,struct man char name15; char sex; int age; date birthda

2、y; ;,如，说明一个结构类型date，含三个整型数据成员,在此基础上，又可说明另一个结构类型man,birthday,Name,sex,age,month,day,year,struct man,结构类型,注意： struct date、 struct man是自己定义的类型名，含义同int、char、float等故可用来作为定义变量的类型。,6.1.2 结构变量的定义及初始化,先说明结构类型再定义结构变量 在说明结构数据类型的同时定义结构变量 省略结构标识符直接定义结构类型变量,struct man man1, man2;,struct man char name15; char sex;

3、 int age; struct date birthday; man1, man2;,struct char name15; char sex; int age; struct date birthday; man1, man2;,无类型名变量,定义:,初始化 : struct person char name15; char sex; int age; p1 = FangMin, F, 24; struct person char name15; char sex; int age; p10 = FangMin, F, 24,LiLin, M, 23;,定义一个结构数组并对其部分元素初始化

4、。,6.1.3 结构变量的访问,1普通结构变量成员的访问 形式：,结构变量名.成员名,strcpy (, Fang Min); m1.sex = F; m1.age = 24; m1.birthday.month = 8;,struct person char name15; char sex; int age; m1 = FangMin, F, 24;,2通过指针对结构变量成员的访问 形式：,(*指向结构的指针).成员名 指向结构的指针-成员名,或,通过指向结构的指针引用结构变量成员,成员访问运算符 优先级最高的 四个运算符之一,括号不能少,如，假设有定义 man m,*p=,

5、m.age = 24; strcpy (, Fang Min); p-age = 18;,则可如下引用结构成员,#include iostream.h #include string.h struct person char name15; char sex; int age; ; void main( ) struct person p1 = Fang Min, m, 24,p2,*p= ,struct abc char name10; float score; s1,s2; s1-name=li_ming ; =li_ming; strcpy(name, li_m

6、ing) ; strcpy(, li_ming); score=90; s2=s1;,【例6.2】 已知有关于学生的结构类型说明，同时定义并初始化了该类型的结构数组，计算该组学生的平均成绩并统计不及格人数。假设学生的信息中包含学号、姓名、性别和成绩。 程序: #include iostream.h struct stu int num; char *name; char sex; float score; student5=101,Li ping,M,45, 102,Zhang ping,M,62.5, 103,He fang,F,92.5, 104,Cheng ling,F,8

7、7, 105,Wang ming,M,58 ;,float ave(struct stu *ps) /指向结构的指针做形式参数 int i; float s=0; for(i=0;iscore; /利用指针访问结构变量的成员 return(s/5); int nopass(struct stu *ps) int c=0,i; for(i=0;iscore60) c+; return c; ,void main() struct stu *ps; ps=student; coutaverage=ave(ps)endl; coutnopass=nopass(ps)endl; ,链表是一种线性表。一

8、个线性表是n(n0)个数据元素的有限序列。在计算机中，线性表可以选择连续存储和链接存储。 连续存储 把数据元素一个接一个地放在一组连续的存储单元之中，也就是把线性表中的数据元素存放在一片连续的存储域。连续存储的线性表称为数组。 因为数组的长度是固定的，而线性表的元素个数通常是不确定的，所以通常将数组定义成充分大，但这样会造成存储空间的浪费。用数组存储线性表的另一个缺点是在进行插入和删除操作时需要移动数据。,6.2 结构的应用链表,链接存储 链接存储的线性表称为链表。元素之间靠指针链接。,特点 每个元素(结点node)由数据域data和指针域next构成,其中指针域指向下一个元素的首地址,最后一

9、个元素的指针为NULL。 结点之间可以连续，可以不连续存储; 结点的逻辑顺序与物理顺序可以不一致; 表可根据需要动态扩充。,下图是一个具有5个数据元素(称为结点)的线性链表(单向链表)。每一个线性链表都有一个表头指针(head)，如果链表是非空链表，则存放第一个结点的起始地址，否则head=NULL。,22 38 46 58 94,存储地址 数据域 指针域,38,head,链表中的每一个结点都是结构类型的变量，应包含两个部分： 数据域和指针域(即下一个结点的地址)。 前面图中的结点和表头指针的类型可以这样说明： struct node int data; struct node *next;

10、; struct node *head;,/指向它所属的结构类型,链表的常见操作有： 1. 建立链表； 2. 输出链表； 3. 确定链表的长度，即统计链表中结点的个数； 4. 查找链表中的某个结点； 5. 在链表中插入一个新的结点； 6. 删除链表中的某个结点。,6.2.1 链表的基本操作方法,1生成结点变量 当向链表中加入新数据时,需要生成一个新结点以存放要加入的新数据。为此,首先要为新结点申请存放空间，有两种常用方法： 使用malloc函数分配空间 假设有定义： struct node int data; struct node *next; *p; /此时p尚没明确的指向单元 则使用如下

11、语句可使p指向一个node类型的结点: p=(struct node *)malloc(sizeof(node)；,关于函数malloc的说明： 功能是分配一个类型为node的结点变量的空间，并返回其首地址。 对该函数的原型说明包含在头文件stdlib.h中。 sizeof是一个求字节数的运算，malloc函数的参数中要给出申请空间的大小。 使用new运算符分配空间 p=new node; 该方法使用起来更加简单，但C语言中不支持此方法。为方便起见，本书中的程序多采用后一种方式来为新结点申请存放空间。,2释放结点变量空间 当删除链表中的结点时，也应该及时地将其占用的存储空间返还给内存。假设下图

12、中p所指向的结点是要删除的结点， 则相对应用malloc函数分配的空间，可以用如下语句释放。 free(p)； 其中free是个函数，其原型说明也包含在头文件“stdlib.h”中。 相对应用new运算符申请的空间，则用如下语句释放。 delete p;,3结点分量的访问 由于在链表中各个结点之间的联系是靠指针域来实现的，所以对结点各成员的访问也是利用指向结点的指针变量来进行的。 对p所指向的结点的数据域的访问： (*p).data 或 p-data /多以后一种方式为常见 对p所指向的结点的指针域的访问： (*p).next 或 p-next /多以后一种方式为常见,【例6.2】假设node

13、是前面已经定义过的结构类型，又有定义node *p, *q，则建立一个如下图所示的包含两个结点的链表。,建立第一个结点需要两步操作。首先为其申请存放空间，然后为其数据域赋值 建立第二个结点。除了和建立第一个结点相同的两步操作外，因为它是链表中的最后一个结点，因此还要将其指针域置为空。 将第二个结点连接到第一个结点之后，即让第一个结点的指针域指向第二个结点。,/或p=(struct node *)malloc(sizeof(struct node); ; /为第二个结点的指针域赋值,10,20,p=new node;,p-data=10;,q=new node;,q-data=20;,NULL,

14、q-next=NULL,p-next=q;,6.2.2 链表的建立,【例6.3】创建一个含有n个结点的、包含一个数据域，且其类型为整型的单链表。 链表的建立过程如下： 首先设置head为NULL，即建立一个空的链表。 申请一个新结点存储区域，让newnode指向该结点，然后向其数据域输入数据。 把newnode所指向的结点插入到链表中。 如果当前链表是空表，newnode所指向的结点应该成为该链表中唯一的一个结点，故head和tail都应该指向该结点。,struct node *head = NULL; struct node *tail,*newnode;,newnode= new node

15、 newnode-data=x;,head=newnode,如果当前链表非空，则newnode所指向的结点应该做为链表中的最后一个结点加入到链表中，故应该将其插在tail指向的结点后面。 重复执行第2、3步共n次。 将最后一个结点的next域置空(NULL)。,tail-next=newnode,tail = newnode,#include iostream.h struct node int data; struct node *next; ; struct node *create(int n ) struct node *head = NULL; struct node *tail,*

16、newnode; int x; for (int i=0; ix; newnode= _ ; /为newnode申请存放空间 newnode-data=x;,new node,也可用如下语句 newnode=( struct node *) malloc(sizeof( struct node);,if(head=NULL) _ ; /newnode成为空表的第一个结点 else _ ;/将newnode连接到原来的表尾 _ ; / newnode成为新的表尾 tail-next=NULL; return(head); void main( ) struct node *head; int n

17、; coutn; head = create(n); ,head=newnode,tail-next=newnode,tail = newnode,6.2.3 单链表的基本操作,1、链表的遍历,由于链表的指针域中包含了后继结点的存储地址，所以只要知道该链表的头指针，即可依次对每个结点进行访问。 【例6.4】输出上例中建立的单链表的各结点的值。 假设定义p是指向链表中结点的工作指针，该指针从表头head开始逐一指向后续的各个结点，每指向一个结点，便通过该指针访问结点的数据域，直到p的值为NULL。,遍历的函数实现如下： void print(struct node *head) struct n

18、ode *p=head; while(p!=NULL) coutdatat; ; /注意不能通过p+实现 指针后移 ,p = p-next,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); ,3、查找结点,【例6.6】在链表中按序号查找第i个结点。 设置一个序号计数器j

19、和一个工作指针p，从表头结点开始，顺着链表的链进行查找。仅当j=i并且p!= NULL时查找成功，否则查找不成功。,void search(struct node *head, int i) int j=1; struct node *p=head; if(idata; else coutillegal index n; ,p=p-next,j=i ; 如果没有behind指针，插入操作仍然可以完成。 newnode-next=front-next; front-next=newnode; 思考题：上述两个语句的次序能否交换？为什么？,newnode-next=behind,front-nex

20、t=newnode,两种特殊情况： 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,struct node * insert(node *head,int x) struct node *behind,*front,*newnode; newnode=new node; newnode

21、-data=x; behind=head; if(head=NULL) /空表 head=newnode;newnode-next=NULL; else /非空表 while(behind!=NULL ,5、删除链表中的某个结点,删除链表中的某个结点，是把被删除结点的后继结点的地址,赋给其前趋结点的指针域或表头指针head，无后继结点时，则赋NULL。,假定p为指向要删除结点的指针，q为指向删除结点前趋的指针。 如果p=head，则删除的是第一个结点，则应修改表头指针head，使其指向第二个结点，并释放第一个结点占据的存储空间。,head=p-next; delete p;,如果删除的是链表的

22、中间结点，则应把被删除结点p的后继结点的地址，赋给其前趋结点q的指针域。如果没有后继结点时，则赋空指针NULL。,q-next=p-next ; delete p;,【例6.8】编写函数实现在头结点为head的链表中删除值为x的结点。 struct node *delnode(node *head,int x) struct node *p,*q; /p为工作指针,q为p的前驱 p = head; if(head=NULL) /空表 coutdata!= x) / 找删除的结点 q=p; p = p-next; if(p=head) /删除第一个结点 head=p-next; delete p

23、; else if(p!=NULL) /删除非表头结点 q-next=p-next ; delete p; else /未找到要删除的元素 coutxdose not exist in the list!n; return head; ,6.2.4带表头结点的单链表,表头结点（又称伪结点）位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的是统一空表与非空表、表头和表中位置的操作形式，简化链表操作的实现。,非空表 空表,在带表头结点的单链表最前端插入新结点,newnode-next = p-link; p-next = newnode;,非空表,空表,可见，空表和非空表的操作是一致的，无需再分别讨论，简化了操作。,q = p-next; p-next = q-next; delete q;,从带表头结点的单链表中删除最前端的结点,可见，即使删除后为空表，也无需修改head，与非空表操作一致,6.3 应用举例,【例6.9】建立一个带表头结点的单链表，要求每次都将最后加入的结点加到最前面，结点中的数据均是不为0的整数（要求输入0时建立过程结束），然后