C程序设计课件第07章.ppt

第第第第7 7章章章章 结构体结构体结构体结构体n结构体由许多组织在一起的数据项组成，这些数据项不需要属于同一类型n结构体可以容纳需要的任意多数据项n结构体中的变量称为结构体元素或结构体成员struct studentcharname11;intgrade;intnumber;姓名姓名年级年级学号学号学生学生声明结构体变量n一旦定义了结构体，就可以声明一个或多个该类型的变量n示例：struct student h1;n这条语句将会预留足够的内存来存放该结构体中的所有项struct studentcharname11;intgrade;intnumber;h1,h2;struct student h1;struct student h2;struct student h3,h4;定义时定义时,声明结构体变量声明结构体变量先定义先定义,后声明后声明 结构体类型与结构变量的最大区别在于：结构变量占有一定的内存空间，而结构体类型只是一种数据类型的结构描述，并不占用内存空间。struct box float length;float width;float height;它表明struct box结构体类型由大括号中所列的一些数据项组成，共需占用4x3=12个字节。在此之后，若进行结构变量的定义如：struct box box1;表明box1为struct box结构体类型变量，它占用了12个字节的内存单元。初始化结构体nstudent 类型的变量 h1 和 h2 可以按照下面的方式进行声明和初始化：struct student h1=“张三张三”,3,20050101;struct student h2=“李四李四”,3,20050102;struct studentcharname11;intgrade;intnumber;结构体中使用的赋值语句n可以使用一条简单的赋值语句将一个结构体变量的值赋给另一个相同类型的结构体变量n例如，如果 h1 和 h2 是同一类型的结构体变量，那么下列语句是有效的：h2=h1;访问结构体元素n结构体元素通过使用点运算符（.）来引用，这个运算符也称为成员运算符n语法：结构体变量名.元素名n示例：cin h1.name;n#include nvoid main()nnstruct studentnnchar name10;nint chinese;nint english;nscore;ncoutscore.name;ncoutscore.chinese;ncoutscore.english;n /为结构体元素赋值为结构体元素赋值ncout姓名:score.nameendl;ncout语文:score.chineseendl;ncout英语:score.englishendl;n/输出结构体元素结构体范例结构体范例结构体数组n首先定义结构体，然后声明该类型的数据变量n示例：struct student stu5;n访问数组 stu的第三个元素中的变量 number:stu2.number结构体数组的初始化n结构体数组是通过用一对大括号将其元素值列表括起来进行初始化的n示例：struct student stu3=“张三张三”,3,20050101,“李四李四”,3,20050102,“赵飞赵飞”,3,20050103【例】计算学生的平均成绩并统计出不及格的人数。#include struct stu int num;char name20;char sex;float score;student3=200001,Li li,W,99,200002,Wang hai,M,85,200003,Liu ying,W,50;void main()int i,n;float average,sum;n=0;sum=0;for(i=0;i3;i+)sum+=studenti.score;if(studenti.score60)n+=1;coutsumendl;average=sum/3;coutaverageendln 运算符用于通过指针来访问结构体的元素n示例：struct student*p,h1;p=&h1;coutname;这三种用于表示结构成员的形式是完全等效的。结构变量.成员名 (*结构指针变量).成员名 结构指针变量-成员名 请注意分析下面几种运算：s-n 得到s指向的结构变量中的成员n的值 s-n+得到s指向的结构变量中的成员n的值，用完该值后使 它加1 +s-n 得到s指向的结构变量中的成员n的值使之加1【例】通过结构指针引用结构体成员。#include iostream.hstruct stu int num;char name20;char sex;float score;student1=102,Zhang ping,M,78.5,*s;void main()s=&student1;/*给结构指针变量赋值*/coutstudent1.numstudent1.nameendl;cout(*s).num(*s).nameendl;coutnumnameendl;指向结构数组指向结构数组指向结构数组指向结构数组 当结构指针指向一个结构数组时，该指针变量的值是整个结构数组的首地址。【例】用指针变量输出结构数组。#include iostream.hstruct stu long int num;char name20;char sex;float score;student3=200001,Li li,W,99,200002,Wang hai,M,85,200003,Liuying,W,50;void main()struct stu*s;for(s=student;sstudent+3;s+)coutnumnameendl;结构指针作函数参数结构指针作函数参数结构指针作函数参数结构指针作函数参数 使用结构指针，即用指向结构变量（或数组）的结构指针作函数参数进行传送，这时由实参向形参传递的是地址，属于“地址传递”方式，减少了时间和空间上的开销。【例】用结构指针变量作函数参数编程，计算一组学生的平均成绩【例】用结构指针变量作函数参数编程，计算一组学生的平均成绩#include iostream.hstruct stu long int num;char name20;char sex;float score;student3=200001,Li li,W,99,200002,Wang hai,M,85,200003,Liuying,W,50;void average(struct stu*ps)int n=0,i;float ave,s=0;for(i=0;iscore;ave=s/3;coutaverage=avenum=102;strcpy(s-name,Zhang ping);s-sex=M;s-score=62.5;coutnumnameendl;coutsexscoreendl;free(s);链表的使用链表的使用链表的使用链表的使用 链表是一种常见的、重要的数据结构，它采用动态的分配办法为一个结构体分配内存空间。一方面需要时就分配一块空间用来存放，从而节约了宝贵的内存资源；且便于删除与加入。另一方面，在动态分配时，每个结点之间可以是不连续的(结点内是连续的)，结点之间的联系是通过指针来实现的，即在结点结构中定义一个成员项用来存放下一结点的首地址，这个用于存放地址的成员，常把它称为指针域。这样一种连接方式，如同一条一环接一环的链子，在数据结构中称之为“链表”。struct stustruct stu int num;int num;int score;int score;struct stu*next;struct stu*next;在该结构体中前两个成员项组成数据域，最后一个成员项在该结构体中前两个成员项组成数据域，最后一个成员项nextnext构构成指针域，它是一个指向成指针域，它是一个指向struct stustruct stu类型的结构指针变量。类型的结构指针变量。单链表的常用操作：结点的插入、删除、检索和排序等。单链表的常用操作：结点的插入、删除、检索和排序等。新项目插在表头新项目插在表头新项目插在表中间新项目插在表中间新项目新项目infoinfo1 1infoinfo3 30infoinfo2 2新项目插在表尾新项目插在表尾新项目新项目infoinfo1 1infoinfo3 30infoinfo2 2新项目新项目infoinfo1 1infoinfo3 30infoinfo2 2新项目新项目0infoinfo1 1infoinfo3 3infoinfo2 2 建立链表建立链表建立链表建立链表【例】编写一个建立单向链表的函数，存放学生数据。#include#include#include malloc.h#include malloc.h#define NULL 0#define NULL 0 /*/*令令NULLNULL为为0 0，用它表示空地址，用它表示空地址*/*/#define LEN sizeof(struct stu)#define LEN sizeof(struct stu)struct stustruct stu long int num;long int num;float score;float score;struct stu*next;struct stu*next;int n;int n;struct stu*creat()struct stu*creat()/*/*此函数返回一个指向链表头的指针此函数返回一个指向链表头的指针*/*/struct stu*head,*p1,*p2;struct stu*head,*p1,*p2;n=0;n=0;/*n/*n为结点的个数为结点的个数*/*/p1=p2=(struct stu*)malloc(LEN);p1=p2=(struct stu*)malloc(LEN);/*/*开辟一个新单元开辟一个新单元*/*/cinp1-nump1-score;cinp1-nump1-score;head=NULL;head=NULL;while(p1-num!=0)while(p1-num!=0)n=n+1;n=n+1;if(n=1)head=p1;if(n=1)head=p1;else p2-next=p1;else p2-next=p1;p2=p1;p2=p1;p1=(struct stu*)malloc(LEN);p1=(struct stu*)malloc(LEN);cinp1-nump1-score;cinp1-nump1-score;p2-next=NULL;p2-next=NULL;return(head);return(head);/*/*返回链表的头地址返回链表的头地址*/*/图7-1、图7-2、图7-3、图7-4、图7-5表示出creat函数的执行过程。图7-1图7-2图7-3(a)图7-3(b)图7-3(c)图7-4(a)图7-4(b)图7-4(c)图7-5链表的输出链表的输出链表的输出链表的输出将链表中各结点的数据依次输出，首先要知道链表头元素的地址。将链表中各结点的数据依次输出，首先要知道链表头元素的地址。程序执行过程可见程序执行过程可见图图7-67-6所示。所示。【例】写一个函数，输出链表中所有结点。【例】写一个函数，输出链表中所有结点。void print(head)void print(head)/*/*由实参将已有的链表的头指针传给被调函数由实参将已有的链表的头指针传给被调函数*/*/struct stu*head;struct stu*head;struct student*p;struct student*p;p=head;p=head;/*p/*p指向头结点指向头结点*/*/while(p!=NULL)while(p!=NULL)coutnumscoreendl;/*coutnumscorenext;p=p-next;/*/*使使p p指向下一个结点指向下一个结点*/*/图7-6链表的删除操作链表的删除操作链表的删除操作链表的删除操作 从一个链表中删除一个结点，并不是真正从内存中把它抹去，而是把它从链表中分离开来。分析：设两个指针变量p1和p2，先使p1指向第一个结点。删除一个结点有两种情况：一种情况一种情况是要删除结点是第一个结点，此时只需使head指向第二个结点即可，即head=p1-next，其过程如图7-7所示。另一种情况另一种情况是被删除结点不是第一个结点，可使被删除结点的前一结点指向被删结点的后一结点，即p2-next=p1-next，其过程如图7-8所示。【例】写一个函数，删除链表中的指定结点，以指定的学号作为删除结点的标志。函数dele编写如下：struct stu *dele(struct stu*head,long int num)struct stu *dele(struct stu*head,long int num)struct stu *p1,*p2;struct stu *p1,*p2;链表的删除操作链表的删除操作链表的删除操作链表的删除操作if(head=NULL)if(head=NULL)/*/*如为空表，如为空表，输出提示信息输出提示信息*/*/return head;return head;p1=head;p1=head;while(p1-num!=num&p1-next!=NULL)/*while(p1-num!=num&p1-next!=NULL)/*当不是要删除的结当不是要删除的结点，而且也不是最后一个结点时，继续循环点，而且也不是最后一个结点时，继续循环*/*/p2=p1;p1=p1-next;p2=p1;p1=p1-next;/*/*后移一个结点后移一个结点*/*/if(p1-num=num)if(p1-num=num)/*/*找到要删除的结点找到要删除的结点*/*/if(p1=head)head=p1-next;/*if(p1=head)head=p1-next;/*为第一结点为第一结点headhead指向第二指向第二结点结点*/*/else p2-next=p1-next;else p2-next=p1-next;/*/*不是第一个结点，使要删除结点从链表中不是第一个结点，使要删除结点从链表中脱离脱离*/*/链表的删除操作链表的删除操作链表的删除操作链表的删除操作n=n-1;n=n-1;free(p1);free(p1);else else CoutThe node not been foud!;Coutnext=p1;head=p0;p0-next=p1;head=p0;见见图图7-9(b)7-9(b)。第三种情况是在其它位置插入，见第三种情况是在其它位置插入，见图图7-9(c)7-9(c)。p0-next=p1;p2-next=p0;p0-next=p1;p2-next=p0;最后一种情况是在表末插入，见最后一种情况是在表末插入，见图图7-9(d)7-9(d)。p1-next=p0;p0-next=NULL;p1-next=p0;p0-next=NULL;【例】写一个函数，在学生数据链表中，按学号顺序插入一个结点。【例】写一个函数，在学生数据链表中，按学号顺序插入一个结点。struct stu*insert(struct stu*head,struct stu*stud)struct stu*insert(struct stu*head,struct stu*stud)struct stu *p0,*p1,*p2;struct stu *p0,*p1,*p2;p1=head;p1=head;/*/*指向第一个结点指向第一个结点*/*/p0=stud;p0=stud;/*/*指向要插入的结点指向要插入的结点*/*/if(head=NULL)if(head=NULL)/*/*空表插入空表插入*/*/head=p0;head=p0;p0-next=NULL;p0-next=NULL;/*/*将将p0p0指向的结点作第一个结点指向的结点作第一个结点*/*/else else while(p0-nump1-num)&(p1-next!=NULL)while(p0-nump1-num)&(p1-next!=NULL)p2=p1;p2=p1;p1=p1-next;p1=p1-next;/*/*找插入位置找插入位置*/*/if(p0-numnum)if(p0-numnum)if(head=p1)head=p0;if(head=p1)head=p0;/*/*在第一结点之前插入在第一结点之前插入*/*/else p2-next=p0;/*else p2-next=p0;/*在其它位置插入在其它位置插入*/*/p0-next=p1;p0-next=p1;else else p1-next=p0;p1-next=p0;p0-next=NULL;p0-next=NULL;/*/*在表末插入在表末插入*/*/n=n+1;n=n+1;return(head);return(head);图7-9(a)图7-9(b)图7-9(c)图7-9(d)栈栈栈是一种栈是一种线性表线性表，对栈的所有操作发生在这个表的同一端，该端称为栈，对栈的所有操作发生在这个表的同一端，该端称为栈的的“顶顶”，另一端称为栈的，另一端称为栈的“底底”。由于插入和删除都在栈顶进行，因此删除的将是最新插入的成员，所以由于插入和删除都在栈顶进行，因此删除的将是最新插入的成员，所以栈又被称为栈又被称为“后进先出表后进先出表（LIFO表或下推表）表或下推表）”。描述一个栈通常需要一个变量和三个函数：变量用于记录当前的栈顶位描述一个栈通常需要一个变量和三个函数：变量用于记录当前的栈顶位置；函数包括将数据项压入栈的置；函数包括将数据项压入栈的push()、从栈顶弹出一个成员的、从栈顶弹出一个成员的pop()、读栈顶成员的读栈顶成员的top()。有时还需要引入一个变量标识栈内数据对象数目。有时还需要引入一个变量标识栈内数据对象数目或者栈底的位置。或者栈底的位置。stackstackINFOINFONODE*NODE*datadatapNextpNextdatadatapNextpNextdatadatapNextpNext.栈通常以顺序方式存储。栈通常以顺序方式存储。如果栈中所有项目类型相同，并且项目总如果栈中所有项目类型相同，并且项目总数具有上限，那么这个栈可以一维数组方数具有上限，那么这个栈可以一维数组方式实现，这种实现方式栈的基本操作十分式实现，这种实现方式栈的基本操作十分简单，缺点是对栈成员的总数有限制，且简单，缺点是对栈成员的总数有限制，且成员一般要具有相同类型。成员一般要具有相同类型。栈的比较灵活的实现方式是采用单链表。栈的比较灵活的实现方式是采用单链表。联合体联合体联合体联合体 将几种不同类型的变量存放在同一段内存单元中的结构称为“联合体”，也称为“共用体”。“联合体”与“结构体”有一些相似之处，但两者有本质上的不同。在结构体中各成员有各自的内存空间，一个结构变量的总长度是各成员长度之和；而在联合体中，各成员共享一段内存空间，一个联合变量的长度等于各成员中最长的长度。联合体类型的声明联合体类型的声明联合体类型的声明联合体类型的声明声明一个联合体类型的一般形式为：声明一个联合体类型的一般形式为：union union ;例如：例如：union perdata union perdata int class;int class;char office10;char office10;在使用联合体类型数据时要注意它具有以下一些特点：在使用联合体类型数据时要注意它具有以下一些特点：（1 1）一个联合变量，每次只能赋予一个成员值。）一个联合变量，每次只能赋予一个成员值。（2 2）联合变量中起作用的成员是最后一次存放的成员。）联合变量中起作用的成员是最后一次存放的成员。（3 3）不允许对联合变量作初始化赋值，赋值只能在程序中进行。）不允许对联合变量作初始化赋值，赋值只能在程序中进行。【例】编写程序使用联合体类型数据来保存数据。【例】编写程序使用联合体类型数据来保存数据。#include void main()union t char*name;int age;int income;union t list;coutsizeof(union t*)endl;/*输出联合体类型长度输出联合体类型长度*/list.name=Zhang hai;/*第一次赋值第一次赋值*/coutlist.nameendl;list.age=20;/*第二次赋值第二次赋值*/coutlist.ageendl;list.income=2500;/*第三次赋值第三次赋值*/coutlist.incomeendl;coutlist.namelist.agelist.incomeendl;/*输出各成员值输出各成员值*/枚举类型声明的一般形式为：枚举类型声明的一般形式为：enum enum ;例如：例如：enum weekday enum weekday sun,mon,tue,wed,thu,fri,sat sun,mon,tue,wed,thu,fri,sat ;枚举类型枚举类型枚举类型枚举类型 (1)(1)先声明后定义先声明后定义enum weekday enum weekday .;enum weekday a,b,c;enum weekday a,b,c;(2)(2)声明的同时定义声明的同时定义enum weekday enum weekday .a,b,c;a,b,c;(3)(3)直接定义直接定义 enum enum .a,b,c;a,b,c;#include#include enum weektypeSun,Mon,Tues,Wed,Thur,Fri,Satnday;enum weektypeSun,Mon,Tues,Wed,Thur,Fri,Satnday;void main()void main()int nindex;int nindex;char*pstr;char*pstr;while(cinnindex)while(cinnindex)switch(nindex)switch(nindex)case Sun:pstr=Sunday;break;case Sun:pstr=Sunday;break;case Mon:pstr=Monday;break;case Mon:pstr=Monday;break;case Tues:pstr=Tuesday;break;case Tues:pstr=Tuesday;break;case Wed:pstr=Wednesday;break;case Wed:pstr=Wednesday;break;case Thur:pstr=Thursday;break;case Thur:pstr=Thursday;break;case Fri:pstr=Friday;break;case Fri:pstr=Friday;break;case Sat:pstr=Saturday;break;case Sat:pstr=Saturday;break;default:break;default:break;coutpstrendl;coutpstrendl;