第12章结构体和共用体.ppt

《第12章结构体和共用体.ppt》由会员分享，可在线阅读，更多相关《第12章结构体和共用体.ppt（118页珍藏版）》请在三一文库上搜索。

1、二进制数类型本不存在 内存里存的内容，你认为它是什么，它就是什么 在早期的机器指令及汇编语言中，数据对象均用二进制数表示，没有类型的概念 一般的CPU只支持两种类型 整数、浮点数,12.1从基本数据类型到抽象数据类型,在高级语言引入了基本数据类型 整型、浮点型、字符型等 不同语言会定义不同的基本类型 基本数据类型并不能方便地解决所有问题 有些语言（如PL/1）中试图规定较多的类型，如数组、树、栈等，但实践证明不是个好办法,12.1从基本数据类型到抽象数据类型,用户自己构造数据类型-复合数据类型 由基本数据类型迭代派生而来，表示复杂的数据对象 典型的代表就是“结构体” 抽象数据类型（Abstra

2、ct Data Type，简称ADT） 在复合数据类型基础上增加了对数据的操作 抽象数据类型进而进化为“类(Class)” 这是一个跨时代的进步 Class是Object-Oriented的一个重要概念,12.1从基本数据类型到抽象数据类型,12.2.1为什么要定义结构体类型,在程序里表示一个人（姓名、年龄、性别），怎么表示？ 想表示多个人呢？ 如何用计算机程序实现下述表格的管理？,数组的解决方法,数组的解决方法,数据的内存管理方式,数组的解决方法,分配内存不集中，寻址效率不高 对数组赋初值时，易发生错位 结构显得零散，不易管理,希望的内存分配图,结构体类型的声明,声明了一个结构体类型,构成结

3、构体的变量称为结构体的成员(Structure Member),结构体的名字称为结构体标签(Structure Tag),结构体类型的声明,结构体模板(Structure Template),Dont forget the semicolon!,形成一个类型声明的样板 用于生成结构体变量 但并未声明结构体变量 因而编译器不为其分配内存,（1）先定义结构体类型，再定义变量名,（2）在定义类型的同时定义变量,（3）直接定义结构体变量（不指定结构体标签）,12.2.2结构体变量的定义,12.2.3用typedef定义数据类型,struct student stu1, stu2;/*It works*

4、/ student stu1, stu2; /*Can this work?*/ struct stu1, stu2; /*Can this work?*/ STUDENT stu1, stu2; /*It works!*/,关键字typedef为一种已存在的类型定义一个别名，并未定义新类型,STUDENT与struct student类型是同义词,等价于,12.2.4结构体变量的初始化,等价于,注意！,嵌套的结构体（Nested Structure）就是在一个结构体内包含了另一个结构体作为其成员,12.2.5嵌套的结构体,结构体定义 可以嵌套,访问结构体变量的成员必须使用成员选择运算符（也称

5、圆点运算符）,12.2.6结构体变量的引用,当出现结构体嵌套时，必须以级联方式访问结构体成员,【例12.1】演示结构体变量的赋值和引用方法,12.2.6结构体变量的引用,按结构体的成员顺序逐一对相应成员进行赋值,格式符%02d中2d前面的前导符0表示输出数据时，若左边有多余位，则补0,【例12.1】若要从键盘输入结构体变量stu1的内容，那么程序如何修改？,两个地址有何不同？,【例12.1】若要从键盘输入结构体变量stu1的内容，那么程序如何修改？,结构体成员的地址与该成员在结构体中所处的位置及其所占内存的字节数相关,结构体变量的地址&stu2是该变量所占内存空间的首地址,12.2.7结构体所

6、占内存的字节数,struct 类型用内存字节数 = ? 是所有成员变量的内存总和吗？,printf(“%dn“, sizeof(struct sample);,用运算符sizeof获得结构体大小 sizeof(变量或表达式) sizeof(类型),12,Why?,printf(“%dn“, sizeof(SAMPLE);,【例12.2】,12.2.7结构体所占内存的字节数,事实上，所有数据类型在内存中都是从偶数地址开始存放的 且结构所占的实际空间一般是按照机器字长对齐的 不同的编译器、平台，对齐方式会有变化 结构体变量的成员的存储对齐规则是与机器相关的 具有特定数据类型的数据项大小也是与机器相

7、关的 所以一个结构体在内存中的存储格式也是与机器相关的,非所有成员变量的内存总和,12个字节,12.3结构体数组的定义和初始化,12.3结构体数组的定义和初始化,建立了数据库中的多条记录，每条对应一个学生信息,【例12.3】利用结构体数组计算每个学生的平均分,教学进程,【例】 有N个学生的信息（包括学号，姓名，成绩），要求：按照成绩的高低顺序存储并输出各学生的信息。 #include #include void main() struct student int num; char name20; int score; s6=1,“aaa“,59,2,“bbb“,78,3,“ccc“,85,

8、4,“ddd“,64,5,“eee“,98,6,“fff“,83; / struct student temp_stu; int i,j,max,temp; char temp_name20;,for(i=0;i6;i+) max=i; for(j=i+1;j=5;j+) if(smax.scoresj.score) max=j; /*temp_stu=si; si=smax; smax=temp_stu;*/ temp=si.num; si.num=smax.num; smax.num=temp; strcpy(temp_name,si.name); strcpy(si.name,smax.

9、name); strcpy(smax.name,temp_name); temp=si.score; si.score=smax.score; smax.score=temp; ,printf(“num name scoren“); for(i=0;i6;i+) printf(“%d %s %dn“,si.num,si.name,si.score); ,12.4结构体指针的定义和初始化,pt,stu1,STUDENT stu1; STUDENT *pt; pt = ,如何定义指向结构体变量的指针？,STUDENT *pt = ,等价于,12.4结构体指针的定义和初始化,如何访问结构体指针变量所

10、指向的结构体成员呢？,STUDENT stu1; STUDENT *pt = ,pt,stu1,通过stu1和成员选择运算符访问结构体成员 stu1. studentID = 1; 通过pt和指向运算符访问结构体成员 (*pt). studentID = 1; pt - studentID = 1;,12.4结构体指针的定义和初始化,pt,stu1,当结构体嵌套时，如何访问结构体指针变量所指向的结构体成员？,stu1. birthday. year = 1999; (*pt). birthday. year = 1999; pt - birthday. year = 1999;,STUDENT

11、 stu1; STUDENT *pt = ,12.4结构体指针的定义和初始化,STUDENT stu30; STUDENT *pt; pt = stu;,如何定义指向结构体数组的指针？,STUDENT *pt = stu;,等价于,STUDENT *pt = ,等价于,pt,stu30,使用pt+，使pt指向stu1 pt - studentID 等价于 stu1. studentID,pt,12.4结构体指针的定义和初始化,STUDENT stu30; STUDENT *pt = stu;,如何访问结构体数组指针指向的结构体成员？,stu30,教学进程,#include struct stu

12、dent int num; char name20; char sex; int age; ;,【例】 有3个学生的信息，放在结构体数组中，要求用指针变量输出 全部学生的信息。,struct student stu3=10101,“Li Lin“,M, 18, 10102,“Zhang Fun“,M, 19, 10104,“Wang Min“,F,20; void main() struct student *p; printf(“ No. Name sex agen“); for (p=stu;pnum, p-name, p-sex, p-age); ,图9-8,教学进程,注意： 如果的初值

13、为stu，即指向第一个元素，则加后p就指向下一个元素。 (+p)-num 先使自加， 然后得到它指向的元素中 的num成员值（即10102）。 (p+)-num 先得到-num的值 （即10101），然后使 自加，指向stu1。,(2) p=&st1.num；是错误的,指向结构体数组的指针,图9-8,12.5向函数传递结构体,向函数传递结构体的单个成员 复制单个成员的内容 函数内对结构内容的修改不影响原结构 向函数传递结构体的完整结构 向函数传递结构体的首地址,struct date int year; int month; int day; ; void func(struct date p

14、) p.year = 2000; p.month = 5; p.day = 22; ,Before function call:1999/04/23,After function call:1999/04/23,结构体变量 作函数参数,【例12.4】,struct date int year; int month; int day; ; void func(struct date *p) p-year = 2000; p-month = 5; p-day = 22; ,Before function call:1999/04/23,After function call:2000/05/22,

15、结构体指针 作函数参数,指针作函数形参 实参必须为地址值,【例12.5】,struct date int year; int month; int day; ; struct date func(struct date p) p.year = 2000; p.month = 5; p.day = 22; return p; ,Before function call:1999/04/23,After function call:2000/05/22,结构体变量 作函数返回值,【例12.6】,12.5向函数传递结构体,向函数传递结构体的完整结构 复制整个结构体成员的内容，多个值 函数内对结构内容

16、的修改不影响原结构 内容传递更直观，但开销大 向函数传递结构体的首地址 用结构体数组/结构体指针作函数参数 仅复制结构体的首地址，一个值 修改结构体指针所指向的结构体的内容 指针传递效率高,教学进程,【例】 有N个结构体变量stu，内含学号、姓名和3门课程的成绩，要求输出平均成绩最高的学生的信息。,#include #define N 3 struct student /要把结构体类型定义为全局的 int num; char name20; float score3; float aver; ; void main() void input(struct student stu); struc

17、t student max (struct student stu); void print(struct student stu); struct student stuN, *p=stu; input(p); print(max(p); ,教学进程,void input(struct student stu) int i; for(i=0;inum, stu-name, ,12.5向函数传递结构体,【例12.7】修改例12.3程序，用结构体数组作函数参数编程并输出计算学生的平均分,12.5向函数传递结构体,【例12.7】修改例12.3程序，用结构体数组作函数参数编程并输出计算学生的平均分,

18、12.5向函数传递结构体,【例12.7】修改例12.3程序，用结构体数组作函数参数编程并输出计算学生的平均分,12.5向函数传递结构体,【例12.7】修改例12.3程序，用结构体数组作函数参数编程并输出计算学生的平均分,下面的结构是什么意思？ struct temp int data; struct temp pt; ; CB下的错误提示： field pt has incomplete type VC下的错误提示： pt uses undefined struct temp 下面的结构是什么意思呢？ struct temp int data; struct temp *pt; ;,可包含指向

19、本结构体类型的指针变量,问题的提出,12.6动态数据结构单向链表,struct Link int data; struct Link *next; ;,链表（Linked Table）:线性表的链式存储结构 特点：用一组任意的存储单元存储线性表的数据；存储单元可以是连续的，也可是不连续的,链表的定义,链表（Linked table）:线性表的链式存储结构 为表示每个元素与后继元素的逻辑关系，除存储元素本身信息外，还要存储其直接后继信息,两部分信息组成一个节点,struct Link int data; struct Link *next; ;,数据域：存储数据元素信息,指针域：存储直接后继的节

20、点信息,链表的定义,链表（Linked Table）:线性表的链式存储结构 为表示每个元素与后继元素的逻辑关系，除存储元素本身信息外，还要存储其直接后继信息,struct Link int data; struct Link *next; ;,n个节点链接成一个链表（因为只包含一个指针域，故又称线性链表或单向链表）,链表是一种常见的重要的数据结构,是动态地进行存储分配的一种结构。 链表的组成： 头指针：存放一个地址，该地址指向一个元素 结点：用户需要的实际数据和链接节点的指针,结点的动态分配,用结构体建立链表： struct student int num； float score； stru

21、ct student *next ；; 其中成员num和score用来存放结点中的有用数据（用户需要用到的数据），next是指针类型的成员，它指向struct student类型数据（这就是next所在的结构体类型）,教学进程,教学进程,#include struct student long num; float score; struct student *next; ; void main() struct student a,b,c,*head,*p; a.num=99101;a.score=89.5; b.num=99103;b.score=90; c. num=99107; c.s

22、core=85;,1. 建立简单的静态链表,【例】 建立上图所示的简链表，它由各学生数据的节点组成。输出各节点中的数据。,head= ,教学进程,教学进程,所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。,2.建立动态链表,教学进程,教学进程,void *malloc(unsigned int size); 在内存的动态存储区分配一个长度为size的连续空间。此函数返回值是一个分配域起始地址（类型void）。如果此函数未能成功执行，则返回空指针（NULL）,void *calloc(unsigned n, unsign

23、ed size); 在内存动态存储区分配n个长度为size的连续空间。函数返回一个指向分配域起始位置的指针。如果分配不成功，则返回NULL 用calloc函数可以为一维数组开辟动态存储空间，n为数组元素个数，每个元素长度为size。,void free ( void *p) 释放由p指向的动态存储区，使这部分内存区能被其他变量使用。P是最近一次调用calloc或malloc函数时返回的值。free函数无返回值。,在链表中查找指定元素,教学进程,建立链表的函数如下: #include #include #define LEN sizeof(struct student) /令LEN代表struc

24、t student类型数据的长度 struct student int num; float score; struct student *next; ,【例】 写一函数建立一个有2名学生学号和成绩的单向动态链表。,教学进程,void main() struct student *head, *p; head=p=( struct student*) malloc(LEN); scanf(“%d,%f”, ,例：写一个函数建立/输出一个有n名学生数据的单向动态链表,对链表的综合操作 （包括对结点的插入删除）,链表的建立,向链表中添加一个新节点,空指针NULL表示链表结尾,链表的头指针：访问链表

25、的关键,链表操作总结,链表的建立,若原链表为空表(head = NULL) ，则将新建节点p置为头节点,(1)head = p,(2) pr = p,(3) pr-next = NULL,链表的建立,若原链表为非空，则将新建节点p添加到表尾,(1) pr-next = p,(2) pr = p,(3) pr-next = NULL,next,根据上述思想编写向链表添加节点数据的程序如下： #include #include struct link *AppendNode(struct link *head); void DisplyNode(struct link *head); void D

26、eleteMemory(struct link *head); struct link int data; struct link *next; ;,int main() int i = 0; char c; struct link *head = NULL; /* 链表头指针 */ printf(“Do you want to append a new node(Y/N)?“); scanf(“ %c“, ,/* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */ struct link *AppendNode(struct link *head) struct li

27、nk *p = NULL, *pr = head; int data; p = (struct link *)malloc(sizeof(struct link); /* 让p指向新建节点 */ if (p = NULL) /* 若为新建节点申请内存失败，则退出程序 */ printf(“No enough memory to allocate!n“); exit(0); ,if (head = NULL) /* 若原链表为空表 */ head = p; /* 将新建节点置为头节点 */ else /* 若原链表为非空，则将新建节点添加到表尾 */ while (pr-next != NULL

28、) /* 若未到表尾，则移动pr直到pr指向表尾 */ pr = pr-next; /* 让pr指向下一个节点 */ pr-next = p; /* 让末节点的指针域指向新建节点 */ printf(“Input node data:“); scanf(“%d“, /* 返回添加节点后的链表的头指针 */ ,/* 函数的功能：显示链表中所有节点的节点号和该节点中数据项内容 */ void DisplyNode(struct link *head) struct link *p = head; int j = 1; while (p != NULL) /* 若不是表尾，则循环打印节点的值 */

29、printf(“%5d%10dn“, j, p-data);/* 打印第j个节点的数据 */ p = p-next; /* 让p指向下一个节点 */ j+; ,/* 函数功能：释放head指向的链表中所有节点占用的内存 */ void DeleteMemory(struct link *head) struct link *p = head, *pr = NULL; while (p != NULL) /* 若不是表尾，则释放节点占用的内存 */ pr = p; /* 在pr中保存当前节点的指针 */ p = p-next; /* 让p指向下一个节点 */ free(pr); /* 释放pr指

30、向的当前节点占用的内存 */ ,链表的删除操作,若原链表为空表，则退出程序 若待删除节点p是头节点，则将head指向当前节点的下一个节点即可删除当前节点,(1) head = p-next,head,(2) free(p),链表的删除操作,若待删除节点不是头节点，则将前一节点的指针域指向当前节点的下一节点即可删除当前节点,(1) pr-next = p-next,若已搜索到表尾（p-next = NULL）仍未找到待删除节点，则显示“未找到”,(2) free(p),#include #include struct link *AppendNode(struct link *head); vo

31、id DisplyNode(struct link *head); void DeleteMemory(struct link *head); struct link *DeleteNode(struct link *head, int nodeData); struct link int data; struct link *next; ;,int main() int i = 0; char c; struct link *head = NULL; /* 链表头指针 */ printf(“Do you want to append a new node(Y/N)?“); scanf(“ %

32、c“, ,/* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */ struct link *AppendNode(struct link *head) struct link *p = NULL; struct link *pr = head; int data; p = (struct link *)malloc(sizeof(struct link); /* 让p指向新建节点 */ if (p = NULL) printf(“No enough memory to allocate!n“); exit(0); ,if (head = NULL) /* 若原链表为空

33、表，则将新建节点置为首节点 */ head = p; else /* 若原链表为非空，则将新建节点添加到表尾 */ while (pr-next != NULL)/* 若未到表尾，则移动pr直到pr指向表尾 */ pr = pr-next; /* 让pr指向下一个节点 */ pr-next = p; /* 将新建节点添加到链表的末尾 */ pr = p; /* 让pr指向新建节点 */ printf(“Input node data:“); scanf(“%d“, /* 返回添加节点后的链表的头节点指针 */ ,/* 函数的功能：显示链表中所有节点的节点号和该节点中数据项内容 */ void

34、DisplyNode(struct link *head) struct link *p = head; int j = 1; while (p != NULL) /* 若不是表尾，则循环打印 */ printf(“%5d%10dn“, j, p-data);/* 打印第j个节点的数据 */ p = p-next; /* 让p指向下一个节点 */ j+; ,/* 函数功能：释放head指向的链表中所有节点占用的内存 */ void DeleteMemory(struct link *head) struct link *p = head, *pr = NULL; while (p != NUL

35、L) /* 若不是表尾，则释放节点占用的内存 */ pr = p; /* 在pr中保存当前节点的指针 */ p = p-next; /* 让p指向下一个节点 */ free(pr); /* 释放pr指向的当前节点占用的内存 */ ,/*函数功能：从head指向的链表中删除一个节点，返回删除节点后的链表的头指针 */ struct link *DeleteNode(struct link *head, int nodeData) struct link *p = head, *pr = head; if (head = NULL) /* 若链表为空表，则退出程序 */ printf(“Linke

36、d Table is empty!n“); return(head); while (nodeData != p-data ,if (nodeData = p-data) /* 若找到节点nodeData，则删除该节点 */ if (p = head) /* 若待删除节点为首节点，则让head指向第2个节点 */ head = p-next; else /*若待删除节点不是首节点，则将前一节点的指针指向当前节点的下一节点*/ pr-next = p-next; free(p); /* 释放为已删除节点分配的内存 */ else /* 没有找到待删除节点 */ printf(“This Node

37、 has not been found!n“); return head; /* 返回删除节点后的链表的头节点指针 */ ,链表的插入操作,若原链表为空表，则将新节点p作为头节点，让head指向新节点p,(1) head = p,p = (struct link *)malloc(sizeof(struct link); p-next = NULL; p-data = nodeData;,链表的插入操作,若原链表为非空，则按节点值（假设已按升序排序）的大小确定插入新节点的位置 若在头节点前插入新节点，则将新节点的指针域指向原链表的头节点，且让head指向新节点,(2) head = p,(1)

38、 p-next = head,链表的插入操作,若在链表中间插入新节点，则将新节点的指针域指向下一节点且让前一节点的指针域指向新节点,(2) pr-next = p,(1) p-next = pr-next,链表的插入操作,若在表尾插入新节点，则末节点指针域指向新节点,(1) pr-next = p,next,链表的输出,遍历链表的所有节点,#include #include struct link *AppendNode(struct link *head); void DisplyNode(struct link *head); void DeleteMemory(struct link *

39、head); struct link *InsertNode(struct link *head, int nodeData); struct link int data; struct link *next; ;,int main() int i = 0; char c; struct link *head = NULL; /* 链表头指针 */ printf(“Do you want to append a new node(Y/N)?“); scanf(“ %c“, ,/* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */ struct link *Append

40、Node(struct link *head) struct link *p = NULL; struct link *pr = head; int data; p = (struct link *)malloc(sizeof(struct link); /* 让p指向新建节点 */ if (p = NULL) printf(“No enough memory to allocate!n“); exit(0); ,if (head = NULL) /* 若原链表为空表，则将新建节点置为首节点 */ head = p; else /* 若原链表为非空，则将新建节点添加到表尾 */ while (

41、pr-next != NULL)/* 若未到表尾，则移动pr直到pr指向表尾 */ pr = pr-next; /* 让pr指向下一个节点 */ pr-next = p; /* 将新建节点添加到链表的末尾 */ pr = p; /* 让pr指向新建节点 */ printf(“Input node data:“); scanf(“%d“, /* 返回添加节点后的链表的头节点指针 */ ,/* 函数的功能：显示链表中所有节点的节点号和该节点中数据项内容 */ void DisplyNode(struct link *head) struct link *p = head; int j = 1; w

42、hile (p != NULL) /* 若不是表尾，则循环打印 */ printf(“%5d%10dn“, j, p-data);/* 打印第j个节点的数据 */ p = p-next; /* 让p指向下一个节点 */ j+; ,/* 函数功能：释放head指向的链表中所有节点占用的内存 */ void DeleteMemory(struct link *head) struct link *p = head, *pr = NULL; while (p != NULL) /* 若不是表尾，则释放节点占用的内存 */ pr = p; /* 在pr中保存当前节点的指针 */ p = p-next;

43、 /* 让p指向下一个节点 */ free(pr); /* 释放pr指向的当前节点占用的内存 */ ,/* 函数功能：在已按升序排序的链表中插入一个节点，返回插入节点后的链表头指针 */ struct link *InsertNode(struct link *head, int nodeData) struct link *pr = head, *p = head, *temp = NULL; p = (struct link *)malloc(sizeof(struct link);/* 让p指向待插入节点 */ if (p = NULL) /* 若为新建节点申请内存失败，则退出程序 */

44、 printf(“No enough memory!n“); exit(0); p-next = NULL; /* 为待插入节点的指针域赋值为空指针 */ p-data = nodeData; /* 为待插入节点数据域赋值为nodeData */ if (head = NULL) /* 若原链表为空表 */ head = p; /* 待插入节点作为头节点 */ ,else /* 若未找到待插入节点的位置且未到表尾，则继续找 */ while (pr-data next != NULL) temp = pr; /* 在temp中保存当前节点的指针 */ pr = pr-next;/* pr指向当

45、前节点的下一节点 */ if (pr-data = nodeData) if (pr = head) /* 若在头节点前插入新节点 */ p-next = head;/* 将新节点的指针域指向原链表的头节点 */ head = p; /* 让head指向新节点 */ else /* 若在链表中间插入新节点 */ pr = temp; p-next = pr-next;/* 将新节点的指针域指向下一节点 */ pr-next = p; /* 让前一节点的指针域指向新节点 */ else /* 若在表尾插入新节点 */ pr-next = p; /* 让末节点的指针域指向新节点 */ return hea