第10章结构体与链表.ppt

《第10章结构体与链表.ppt》由会员分享，可在线阅读，更多相关《第10章结构体与链表.ppt（46页珍藏版）》请在三一文库上搜索。

1、第10章 结构体与链表,10.1 结构体类型的定义与变量说明 10.2 结构体类型变量的引用 10.3 结构体与数组 10.4 结构体与指针 10.5 结构体与函数 10.6 链表,10.1 结构体类型的定义与变量说明,10.1.1结构体类型的定义 结构体是具有不同类型的数据的有序集合 结构体定义： struct 结构体类型名 类型标识符 成员名1; 类型标识符 成员名2; 类型标识符 成员名n; ；,struct： 定义结构体类型的关键字； 域： 结构体类型定义中的每1个成员； 成员名的命名规则和变量相同，同一结构体的同层成员不可同名。,例：定义结构体类型student,struct stu

2、dent int num; char name20; char sex; int age; float score; char addr30; ;,struct student应作为一个 整体对待，“;”号不能少!,10.1.2 定义结构体类型变量的定义,一、先定义结构体类型再定义变量名 形式： struct 结构体名 结构体变量名表 例：在前面已定义结构体类型struct student 则可定义：struct student stu1,stu2; stu1,stu2即为struct student类型的变量,二、在定义类型的同时 定义变量 一般形式为： struct 结构体名 成员表列 变

3、量名表列;,struct student int num; char name20; char sex; int age; float score; char addr30; student1,student2;,三、直接定义结构类型 的变量 一般形式为： struct 成员表列 变量名表列; * 不出现结构体名,struct int num; char name20; char sex; int age; float score; char addr30; student1,student2;,10.1.3 结构体类型的嵌套,定义：结构体成员又是一个结构体变量 例: struct date

4、int month; int day; int year; struct student char name20; char sex; int age; struct date birthday; stu1,stu2;,嵌套结构体变量的引用：点标记法，但只能对最低成员进行赋值或存取、运算。 例：stu1.age=20; stu1.dirthday.month=7; stu1.dirthday.day=31; 思考以下的引用 printf(“%d%d%d”,stu1.birthday);() stu1.birthday=12, 31, 1988 ; (),10.2 结构体类型变量引用与初始化,1

5、0.2.1 引用 不能将一个结构体变量作为一个整体进行输入和输出，只能对各个成员分别输入输出 例如： printf(”%d,%s,%c,%d,%f,%sn”,student1);() 引用： student1.num=102;() 成员的引用方式为：结构体变量名. 成员名 注意：成员运算符. 在所有运算符中优先级最高,结构体变量引用方法：,struct clock int hour, minute, second; struct date int year, month, day; struct clock time; today,nextday ; 1. 单独引用结构体变量的成员 today

6、.year=2004; today.time.second=15; 2. 结构体变量作为一个整体引用 nextday=today;,10.2.2 结构体类型变量的初始化,定义时初始化：将各元素初值放在“ ”里赋值给变量。 例： struct student char name20; char sex; int age; float score; stu1, stu2=“Wangwu”,m,20,88.5;,10.3 结构体与数组,10.3.1结构体数组变量的定义 与结构体变量定义类似，只是结构体变量名现为结构体数组变量名 如： struct student int num; char name

7、20; char sex; int age; float score; stu30;,数组各元素在内存中连续存放，如右图所示。,10.3.2结构体数组变量的初始化与引用,初始化：数组=初值表列; 引用： 结构体数组分量 . 结构体成员,struct student int num; char name20; char sex; int age; float score; char addr30; stu3=101,”WGJ”,M,28,88.5,“CS”, 102,”DYH”,F,26,88.0,”CS”, 103,”DYC”,M,24,78.5,”CZ”;,结构体数组程序举例,【例10-5】

8、计算一个班学生的三门课程的平均成绩，并输出该班学生姓名及平均成绩。 程序见下页。,程序,#include #define MAXSIZE 100 struct student char name16;/*学生姓名*/ int grade3,average;/*三门成绩，平均分*/ ;,程序,void main() int i,j,num,s; struct student stuMAXSIZE; printf(“Enter number of students:“); scanf(“%d“, ,10.4 结构体类型与指针,一个结构体变量的指针就是该结构体变量所占据的内存的起始地址。 指针变量可

9、存放结构体变量的指针。 指针变量不仅可以用来指向结构体变量，还可以用来指向结构体数组中的元素。,10.4.1 指向结构体变量的指针,形式：struct 结构体类型名 *结构体指针名 例：struct student stu1,*pst; pst= q=&stu1.num合法,【例10-6】用指向结构体变量的指针来访问学生的各项数据。,#include “string.h“ struct stu int num; char *name; char sex; float score; boy=102,“Zhang ping“,M,78.5,*p;,void main() p= ,10.4.2指向结

10、构体数组的指针,例10-7 输出数组中各元素中各成员的值。,struct student int num; char name20; char sex; int age; ; struct student stu3 =10101,“Zhang“,M,18, 10102,“Li“,M,19, 10103,“Wang“,F,20; /续,main() /*续上页*/ struct student *p; printf(“No. Name Sex Agen“); for (p=stu; pnum, p-name, p-sex, p-age); ,注意事项:,如果p的初值为stu，即指向结构体数组的第

11、1个元素stu0，则p+1指向下1个元素的起始地址stu1。 区别：(+p)-num 和 (p+)-num p已定义为指向struct student类型的指针变量，则p只能指向1个结构体类型数据，而不能指向结构体类型的某一成员（即p的地址不是成员的地址）。 如：p=&stu.name；( 错误),Go5.3.7,10.5 结构体与函数,10.5.1结构体变量作为函数的参数 将1个结构体变量的值传递给1个函数，方法有二： 用结构体变量的成员作参数。用法和普通变量作实参是一样的，属“值传递”方式。 用指向结构体变量/数组的指针作实参，将结构体变量/数组的地址传给形参。,10.5.2 用指向结构体

12、的指针作函数参数,例 编写一个函数，计算指定学生的6科平均成绩，根据平均成绩评定登记。,结构类型： struct student char name20; char num10; float score6; float ave; ;,main() struct student a100; int I,j,n; float sum; scanf(“%d”, ,将6门课程数据输入定义为函数input( )，函数的返回值为结构型地址,struct student input(void) struct student stud; int I; float sum scanf(“%s”,stud.nam

13、e); scanf(“%s”,stud.num); for(I=0;I6;I+) scanf(“%f”, ,main() struct student a100; int I,j,n; struct student input(void); scanf(“%d”, ,假设有： struct point int x,y; ; 函数定义如下： void enter(struct point *p,int n) int I,j; for(I=0;In;I+) printf(“Enter p%d”,I); scanf(“%d,%d”, ,如果在主控函数中定义了结构体数组：struct point a1

14、00; 则调用语句为 enter(a,30);,10.5.3 结构体类型函数,编写程序，查找分数大于或等于90的学生数据 # include struct student char name20; int score; struct student *find(struct student st) int I; for(I=0;I=90) return ,main() int I; struct student st4,*pst; for(I=0;Iname,pst-score); ,10.6 链表,10.6.1 概述 链表存储结构是一种动态数据结构，其特点是它包含的数据对象的个数及其相互关系

15、可以按需要改变，存储空间是程序根据需要在程序运行过程中向系统申请获得，链表也不要求逻辑上相邻的元素在物理位置上也相邻，它没有顺序存储结构所具有的弱点。,1链表结构,（1）头指针变量head指向链表的首结点。 （2）每个结点由2个域组成： 1）数据域存储结点本身的信息。 2）指针域指向后继结点的指针。 （3）尾结点的指针域置为“NULL（空）”，作为链表结束的标志,链表结构的定义,struct student char name10; struct student *next; ; next为student类型指针变量，指向下一个结点的指针域。 结点的变量或指针变量的定义： struct stu

16、dent node,*head; node可以存放一个学生结点 指针head可以存放学生结点的地址。,动态分配存储空间库函数,1void *malloc(unsigned int size); malloc在内存的动态存储区中分配一个size长度的连续存储空间。 例如： int *p; p=(int *)malloc(8); p指示系统分配的4个整型存储单元的起始地址 也可看成包含4个数组元素的p数组：p0,p1,p2,p3,2. void free(void *ptr);,函数free释放由指针变量ptr所指示的内存区域。 例如：free(p); 通过函数free将已分配的内存区域交还系统，

17、使系统可以重新对其进行分配。,【例10-12】动态定义数组。,#include void main() int n,i,*p; printf(“n=“); scanf(“%d“, ,程序运行结果： n=10 0 1 4 9 16 25 36 49 64 81,对链表的基本操作,链表的基本操作有：创建、查找、插入、删除和修改等。 创建链表:从无到有地建立起一个链表。 查找：按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。 插入：在结点ki-1与ki之间插入一个新的结点k，使表的长度增1，且逻辑关系发生如下变化： 插入前，ki-1是ki的前驱，k

18、i是ki-1的后继； 插入后，新插入的结点k成为ki-1的后继、ki的前驱。,链表的删除操作,(4) 删除操作：删除结点ki，使链表的长度减1，且ki-1、ki和ki+1结点之间的逻辑关系发生如下变化： 删除前，ki是ki+1的前驱、ki-1的后继； 删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继。,10.6.2 建立链表,1. 尾插法建立单链表 特点：头指针固定不变，新产生的结点总是链接到链表的尾部。 操作步骤： （1）设head为链表头，last为链表尾结点，head=last=NULL; （2）生成新结点，由p指针指示，并将新结点的地址域清空： p-next=NULL;

19、（3）如果head为NULL，则 head=p; 否则 last-next=p; （4）last=p; （5）重复（2）（4），继续建立新结点。,2. 头插法建立单链表,特点:新产生的结点作为新的链表头插入链表。 操作步骤： （1）head=NULL; （2）生成新结点，指针变量p指向该结点； （3）p-next=head; head=p; （4）重复（2）（3），继续生成下一个链表结点。,10.6.3 链表的访问,1. 输出链表结点 操作步骤： （1）得到链表头结点的地址 head； （2）指针变量p=head; （3）输出p所指结点的成员值; （4）p后移一个结点，p=p-next; （5

20、）重复（3）（4），直到链表为空。,2. 统计链表结点的个数,一般情况下，各个单链表中结点个数是随机的，要想知道表中结点数目，必须从表头开始访问到表尾，逐个统计出结点数目。 3. 查找链表的某个结点 在链表上查找符合某个条件的结点，也必须从链表头开始访问链表。,10.6.4 链表的插入操作,在第n个结点之后插入1个新结点 ,插入操作步骤： （1）q指针指向新结点，i为已访问过的结点数； （2）p=head，r指向p结点的前一个结点； （3）i+，r=p，p=p-next，p结点往前移动一个结点； （4）若inext=head，head=q; （6）若inext=q，q-next=NULL; （

21、7）否则，将q结点插入到第n个结点之后，即插入到r结点与p结点之间：r-next=q，q-next=p; （8）返回链表头head。,10.6.5 链表的删除操作,删除第n个结点 （1）p=head，q指针指向p所指结点的前1个结点； （2）i为访问过的结点数目； （3）i+，q=p，p=p-next，p、q移动1个结点； （4）若p!=NULL且inext; （6）若head=NULL，链表为空，不能删除； （7）若p=NULL，第n个结点不存在，不能删除； （8）找到第n个结点，删除p结点： q-next=p-next; p的前1个结点的next值赋值为p的next域； （9）返回head。,