第12章-结构体和数据结构基础课件.ppt

1、版权所有，违者必究哈尔滨工业大学哈尔滨工业大学计算机科学与技术学院计算机科学与技术学院苏小红苏小红第12章 结构体和数据结构基础C语言程序设计第12章 结构体和共用体第12章 学习内容n结构体，共用体，枚举类型n结构体变量、数组、指针的定义n结构体成员的引用n向函数传递结构体n动态数据结构：链表、栈、队列、二叉树2/65C语言程序设计第12章 结构体和共用体n对计算机系统和硬件，类型的概念不存在因为在冯.诺依曼体系结构中，程序中的数据和代码都是以二进制存储的机器指令及汇编语言中，数据对象均用二进制数表示内存里存的内容都是二进制数，你将它解释成什么，它就是什么12.1从基本数据类型到抽象数据类型

2、3/65C语言程序设计第12章 结构体和共用体n在高级语言引入基本数据类型的目的有效地组织数据，规范数据的使用，提高程序的可读性不同语言会定义不同的基本类型高级语言中预先定义的类型是远远不够的l有些语言（如PL/1）中试图规定较多的类型，如数组、树、栈等，但实践证明不是个好办法12.1从基本数据类型到抽象数据类型4/65C语言程序设计第12章 结构体和共用体n有没有一种类型能很好地定义学生（包括姓名、学号、性别、年龄等信息）呢？n有没有一种类型能很好地定义纸牌（包括花色和牌面）呢？nC语言允许用户自定义数据类型典型的代表就是“结构体”一种构造数据类型12.1从基本数据类型到抽象数据类型5/65

3、C语言程序设计第12章 结构体和共用体n有没有一种类型能定义车呢？除车的属性，还包括对车的操作（启动、加速、减速、刹车等）n抽象数据类型（Abstract Data Type,ADT）不单纯是数据的集合，增加了对数据的操作类型的表示和操作的实现细节对外是不可见的能达到更好的信息隐藏效果12.1从基本数据类型到抽象数据类型6/65C语言程序设计第12章 结构体和共用体nC+中的类(Class)结构体可看成是所有成员都是public的类但不能将C+看成是带类的C，是思考问题角度的转变面向过程(Process Oriented)分析问题的处理步骤，通过函数（过程）调用处理问题以功能为中心来设计功能模

4、块面向对象(Object Oriented)将问题分解为对象，而不是步骤建立对象的目的不是为了完成一个步骤，数据为中心以对象为基础，以事件或消息来驱动对象执行操作12.1从基本数据类型到抽象数据类型7/65C语言程序设计第12章 结构体和共用体12.2.1为什么要定义结构体类型n在程序里表示一个人（姓名、性别、年龄），怎么表示？n想表示多个人呢？n如何用计算机程序实现下述表格的管理？8/65C语言程序设计第12章 结构体和共用体数组的解决方法12.2.1为什么要定义结构体类型9/65C语言程序设计第12章 结构体和共用体12.2.1为什么要定义结构体类型10/65C语言程序设计第12章 结构体

5、和共用体数组的解决方法分配内存不集中，寻址效率不高 对数组赋初值时，易发生错位 结构零散，内存管理困难12.2.1为什么要定义结构体类型11/65C语言程序设计第12章 结构体和共用体希望的内存分配图 12.2.1为什么要定义结构体类型12/65C语言程序设计第12章 结构体和共用体结构体类型的声明声明了一个结构体类型声明了一个结构体类型构成结构体的变量称为构成结构体的变量称为结构体的成员结构体的成员(Structure Member)结构体的名字称为结结构体的名字称为结构体标签构体标签(Structure Tag)13/65C语言程序设计第12章 结构体和共用体结构体类型的声明结构体模板结构

6、体模板(Structure Template)14/65C语言程序设计第12章 结构体和共用体结构体类型的声明定义为何种类型更好？定义为何种类型更好？15/65C语言程序设计第12章 结构体和共用体（1）先定义结构体类型再定义变量名）先定义结构体类型再定义变量名（2）在定义结构体类型的同时定义变量）在定义结构体类型的同时定义变量（3）直接定义结构体变量（不指定结构体标签）直接定义结构体变量（不指定结构体标签）12.2.2 结构体变量的定义16/65C语言程序设计第12章 结构体和共用体12.2.3 用typedef定义数据类型名struct student stu1,stu2;/*It wor

7、ks*/STUDENT stu1,stu2;/*It works!*/student stu1,stu2;/*Can this work?*/struct stu1,stu2;/*Can this work?*/关键字关键字typedef为一种为一种已存在的已存在的类型定义一个类型定义一个别名别名，并未定义新，并未定义新类型类型struct student与与STUDENT类型是类型是同义词同义词17/65C语言程序设计第12章 结构体和共用体等价于等价于12.2.4 结构体变量的初始化18/65C语言程序设计第12章 结构体和共用体n结构体定义可嵌套嵌套的结构体（Nested Structu

8、re）在一个结构体内包含了另一个结构体作为其成员 12.2.5 嵌套的结构体19/65C语言程序设计第12章 结构体和共用体n访问结构体变量的成员成员选择运算符（也称圆点运算符）12.2.6 结构体变量的引用n对嵌套的结构体成员，必须以级联方式访问STUDENT stu1;20/65C语言程序设计第12章 结构体和共用体等价于等价于12.2.6 结构体变量的引用21/65C语言程序设计第12章 结构体和共用体【例12.1】演示结构体变量的赋值和引用方法按结构体的成员顺序逐一对相应成员进行赋值格式符%02d中2d前面的前导符0表示输出数据时，若左边有多余位，则补012.2.6 结构体变量的引用2

9、2/65C语言程序设计第12章 结构体和共用体 若不用初始化的方法，而用从键盘输入的方法输入结构体变量stu1的内容，那么程序如何修改？两个地址有何不同？23/65C语言程序设计第12章 结构体和共用体结构体成员的地址与该成员在结构体中所处的位置及其所占内存的字节数相关结构体变量的地址&stu2是该变量所占内存空间的首地址24/65C语言程序设计第12章 结构体和共用体12.2.7 结构体所占内存的字节数nstruct 类型用内存字节数=?n是所有成员占内存的总和吗？n用获得结构体大小 【例12.2】typedef struct sample char m1;int m2;char m3;SA

10、MPLE;25/65C语言程序设计第12章 结构体和共用体结构体实际所占的内存空间一般是按照机器字长对齐的结构体实际所占的内存空间一般是按照机器字长对齐的不同的系统和编译器，内存对齐不同的系统和编译器，内存对齐(Memory-alignment)方式不同方式不同为了满足处理器的对齐要求，可能会在较小的成员后加入补位为了满足处理器的对齐要求，可能会在较小的成员后加入补位结构体变量的成员的内存对齐方式是与机器相关的结构体变量的成员的内存对齐方式是与机器相关的所以结构体在内存中所占的字节数也是与机器相关的所以结构体在内存中所占的字节数也是与机器相关的12.2.7 结构体所占内存的字节数26/65C语

11、言程序设计第12章 结构体和共用体32位体系结构中，位体系结构中，int值被对齐在值被对齐在4字节地址边界，字节地址边界，保证了一个保证了一个int型数总能通过一次内存操作被访问到，型数总能通过一次内存操作被访问到，每次内存访问是在每次内存访问是在4字节对齐的地址处读取或存入字节对齐的地址处读取或存入32位整数位整数读取存储在没有对齐的地址处的读取存储在没有对齐的地址处的32位整数，需两次内存访问，且从取到的位整数，需两次内存访问，且从取到的64位中位中提取相关的提取相关的32位需额外的操作，性能下降位需额外的操作，性能下降12.2.7 结构体所占内存的字节数n为什么要满足内存对齐的要求呢?2

12、7/65C语言程序设计第12章 结构体和共用体typedef struct sample char m1;int m2;char m3;SAMPLE;typedef struct sample char m1;char m3;int m2;SAMPLE;12.2.7 结构体所占内存的字节数28/65C语言程序设计第12章 结构体和共用体12.3 结构体数组的定义和初始化29/65C语言程序设计第12章 结构体和共用体建立了数据库中的多条记录，每条对应一个学生信息建立了数据库中的多条记录，每条对应一个学生信息12.3 结构体数组的定义和初始化30/65C语言程序设计第12章 结构体和共用体 【例

13、12.3】利用结构体数组，计算每个学生的平均分31/65C语言程序设计第12章 结构体和共用体12.4结构体指针的定义和初始化ptstu1 STUDENT stu1;STUDENT *pt;pt=&stu1;成员成员1成员成员2成员成员3成员成员4成成员员5n如何定义指向结构体变量的指针？等价于等价于32/65C语言程序设计第12章 结构体和共用体n如何访问结构体指针变量指向的结构体成员呢？ptstu1成员成员1成员成员2成员成员3成员成员4成成员员5n通过成员选择运算符访问n通过指向运算符访问12.4结构体指针的定义和初始化33/65C语言程序设计第12章 结构体和共用体ptstu1成员成员

14、1成员成员2成员成员3成员成员4成成员员5n当结构体嵌套时，如何访问结构体指针变量所指向的结构体成员？12.4结构体指针的定义和初始化34/65C语言程序设计第12章 结构体和共用体 STUDENT stu30;STUDENT *pt;pt=stu;n如何定义指向结构体数组的指针？等价于等价于等价于等价于ptstu30stu0stu1stu2stu3stu4stu5.stu2912.4结构体指针的定义和初始化35/65C语言程序设计第12章 结构体和共用体使用使指向 ptn如何访问结构体指针指向的结构体数组成员？stu30stu0stu1stu2stu3stu4stu5.stu2912.4结构

15、体指针的定义和初始化36/65C语言程序设计第12章 结构体和共用体12.5 向函数传递结构体n向函数传递结构体的单个成员复制单个成员的内容n向函数传递结构体的完整结构复制结构体的所有成员n向函数传递结构体的首地址仅复制一个地址值37/65C语言程序设计第12章 结构体和共用体结构体变量作函数参数int main(void)struct date d;d.year=1999;d.month=4;d.day=23;printf(Before function call:%d/%02d/%02dn,d.year,d.month,d.day);Func(d);/*结构体变量作函数实参，传值调用结构体

16、变量作函数实参，传值调用*/printf(After function call:%d/%02d/%02dn,d.year,d.month,d.day);return 0;struct date int year;int month;int day;void Func(struct date p)p.year=2000;p.month=5;p.day=22;【例12.4】函数对结构体内容的修改不影响原结构体38/65C语言程序设计第12章 结构体和共用体int main(void)struct date d;d.year=1999;d.month=4;d.day=23;printf(Befor

17、e function call:%d/%02d/%02dn,d.year,d.month,d.day);Func(&d);/*结构体变量结构体变量的地址的地址作函数实参，传地址调用作函数实参，传地址调用*/printf(After function call:%d/%02d/%02dn,d.year,d.month,d.day);return 0;结构体指针作函数参数【例12.5】结构体指针作函数形参实参必须为地址值struct date int year;int month;int day;void Func(struct date*p)p-year=2000;p-month=5;p-day

18、=22;39/65C语言程序设计第12章 结构体和共用体结构体变量做函数返回值int main(void)struct date d;d.year=1999;d.month=4;d.day=23;printf(Before function call:%d/%02d/%02dn,d.year,d.month,d.day);d=Func(d);/*结构体变量作函数实参，传值调用结构体变量作函数实参，传值调用*/printf(After function call:%d/%02d/%02dn,d.year,d.month,d.day);return 0;struct date int year;i

19、nt month;int day;struct date Func(struct date p)p.year=2000;p.month=5;p.day=22;return p;【例12.6】返回结构体变量的值也可以得到修改的结构体内容，但效率低40/65C语言程序设计第12章 结构体和共用体 【例12.7】修改例12.3程序，用结构体数组作函数参数编程计算并输出学生的平均分 aver放到结构体成员中精简参数传递个数使函数接口更简洁 结构体作函数参数的好处？typedef struct student long studentID;char studentName10;char studentS

20、ex;DATE birthday;int score4;float aver;STUDENT;41/65C语言程序设计第12章 结构体和共用体用户自定义的数据类型n结构体（struct）把关系紧密且逻辑相关的多种不同类型的变量，组织到统一的名字之下n共用体，也称联合（union）把情形互斥但逻辑相关的多种不同类型的变量，组织到统一的名字之下42/65C语言程序设计第12章 结构体和共用体12.6 共用体struct sample short i;char ch;float f;0 x0037b00union sampleshort i;char ch;float f;【例12.8】43/65C

21、语言程序设计第12章 结构体和共用体nsizeof(union number)取决于占空间最多占空间最多的那个成员变量0 x0037b00n同一内存在每一瞬时只能存放其中一种类型的成员n起作用的成员是最后一次存放的成员12.6 共用体44/65C语言程序设计第12章 结构体和共用体12.6 共用体45/65C语言程序设计第12章 结构体和共用体12.6 共用体46/65C语言程序设计第12章 结构体和共用体12.7 枚举数据类型n枚举（Enumeration）数据类型描述一组有限个数据值组成的整型值的集合基本数据类型enum weeks SUN,MON,TUE,WED,THU,FRI,SAT;

22、enum weeks today;today =TUE;/值为值为2 enum response no,yes,none;enum response answer;answer=no;/值为值为0 enum response no=-1,yes=1,none=0;47/65C语言程序设计第12章 结构体和共用体n下面的结构是什么意思？struct temp int data;struct temp pt;nCB下的错误提示：field pt has incomplete typenVC下的错误提示：pt uses undefined struct temp结构体声明时不能包含本结构体类型的成员

23、系统无法预知这样的结构体需要占据多少内存 12.8 动态数据结构单向链表48/65C语言程序设计第12章 结构体和共用体n下面的结构是什么意思？struct temp int data;struct temp pt;n下面的结构是什么意思呢？struct temp int data;struct temp*pt;这样的结构体类型有什么用呢？12.8 动态数据结构单向链表可包含指向本结构体类型的指针变量49/65C语言程序设计第12章 结构体和共用体struct link int data;struct link*next;n动态数据结构的典型代表链表（Linked Table）特点：用一组任意

24、的存储单元存储线性表数据存储单元可以是连续的，也可以是不连续的12.8 动态数据结构单向链表data=Anodedata=Bnodedata=Cnodehead空指针空指针NULL表示链表结尾表示链表结尾头指针：头指针：访问链表访问链表的关键的关键数据域：存储节点的数据信息指针域：存储直接后继信息n个节点链接成一个表线性表的链式存储结构因只包含一个指针域，故又称线性链表或单向链表50/65C语言程序设计第12章 结构体和共用体向链表中添加节点n若原链表为空表(head=NULL)，则将新建节点p置为头节点 headdatanext p新建节点新建节点(2)pr=ppr(3)pr-next=NU

25、LL51/65C语言程序设计第12章 结构体和共用体datanextp向链表中添加节点n若原链表为非空，则将新建节点p添加到表尾(2)pr=pheaddataprpr(3)pr-next=NULLnext52/65C语言程序设计第12章 结构体和共用体链表的删除操作n若原链表为空表，则退出程序 n若待删除节点p是头节点，则将head指向当前节点的下一个节点即可删除当前节点 datanextheaddatanext p53/65C语言程序设计第12章 结构体和共用体链表的删除操作n若待删除节点不是头节点，则将前一节点的指针域指向当前节点的下一节点datanextdatanextdatanext

26、pdatanextn若已搜索到表尾（p-next=NULL）仍未找到待删除节点，则显示“未找到”pr54/65C语言程序设计第12章 结构体和共用体链表的插入操作n若原链表为空表，则将新节点p作为头节点，让head指向新节点p headdata p(2)p-next=NULL55/65C语言程序设计第12章 结构体和共用体链表的插入操作n若原链表为非空，则按节点值的大小（假设已升序排序）确定插入新节点的位置n若在头节点前插入节点，则将新节点的指针域指向原链表的头节点，且让head指向新节点headdatanext pdatanextdatanextdata56/65C语言程序设计第12章 结构

27、体和共用体datanext链表的插入操作n若在链表中间插入新节点，则将新节点的指针域指向下一节点且让前一节点的指针域指向新节点datanext pdatanextdatanextdatapr57/65C语言程序设计第12章 结构体和共用体datanext链表的插入操作n若在表尾插入新节点，则末节点指针域指向新节点datanext pprdatanext(2)p-next=NULL58/65C语言程序设计第12章 结构体和共用体双向链表struct DNode int data;struct DNode*prior,*next;/分别指向前驱和后继节点分别指向前驱和后继节点;struct lin

28、k int data;struct link*next;3next2next1next4head3nextprior3nexthead3prior3nextpriorC语言程序设计第12章 结构体和共用体单循环链表struct link int data;struct link*next;类型定义相似，但初始化和删除后继节点的操作实现不同类型定义相似，但初始化和删除后继节点的操作实现不同3next2next1next4headC语言程序设计第12章 结构体和共用体12.9.1 栈和队列/队列的队列的链式存储链式存储typedef struct queue int data;struct que

29、ue*front;/指向队头指向队头 struct queue*rear;/指向队尾指向队尾QUEUE;/队列的队列的顺序存储顺序存储typedef struct queue int dataMax;int front；/控制队头控制队头 int rear;/控制队尾控制队尾QUEUE;/栈的栈的顺序存储顺序存储typedef struct stack int dataMax;int top;/控制栈顶控制栈顶STACK;/栈的栈的链式存储链式存储typedef struct stack int data;struct stack*next;/指向栈顶指向栈顶STACK;C语言程序设计第12章

30、 结构体和共用体栈的应用实例：计算逆波兰表达式n中缀表示：二元运算符置于两个运算对象之间a+bn后缀表示：运算符置于其运算对象之后，逆波兰表达式a b+a+ba b c+d*+a+(b+c)*d abcab+cab+cda(b+c)*da+(b+c)*dC语言程序设计第12章 结构体和共用体栈的应用实例：计算逆波兰表达式int main(void)char wordN;NodeType d1,d2,d3;STACK stack;stack.top=0;/初始化栈顶初始化栈顶 while(scanf(%s,word)=1&word0!=#)if(isdigit(word0)d1.ival=ato

31、i(word);Push(&stack,d1);else d2=Pop(&stack);d1=Pop(&stack);d3=OpData(&d1,&d2,word0);Push(&stack,d3);d1=Pop(&stack);/弹出栈顶保存的最终计算结果弹出栈顶保存的最终计算结果 printf(%dn,d1.ival);return 0;typedef struct data int type;/数据类型数据类型 union int ival;dat;/数据的值数据的值NodeType;typedef struct stack NodeType dataN;int top;/控制栈顶控制栈

32、顶STACK;/栈的顺序存储栈的顺序存储n如何输入逆波兰表达式 3 5 6+2*+C语言程序设计第12章 结构体和共用体栈的应用实例：计算逆波兰表达式/函数功能：弹出栈顶数据并返回函数功能：弹出栈顶数据并返回NodeType Pop(STACK*stack)stack-top=stack-top-1;return stack-datastack-top;1002003004005000*pPushPop/函数功能：将数据函数功能：将数据data压入堆栈压入堆栈void Push(STACK*stack,NodeType data)memcpy(&stack-datastack-top,&dat

33、a,sizeof(NodeType);stack-top=stack-top+1;*pPush(&stack,d1);/入栈入栈d2=Pop(&stack);/出栈出栈C语言程序设计第12章 结构体和共用体栈的应用实例：计算逆波兰表达式/函数功能：对函数功能：对d1和和d2执行运算执行运算op，并返回计算结果，并返回计算结果NodeType OpData(NodeType*d1,NodeType*d2,int op)NodeType res;res=OpInt(d1-ival,d2-ival,op);return res;/函数功能：对整型的数据函数功能：对整型的数据d1和和d2执行运算执行运

34、算op，并返回计算结果，并返回计算结果NodeType OpInt(int d1,int d2,int op)NodeType res;switch(op)case+:res.ival=d1+d2;break;case-:res.ival=d1-d2;break;case*:res.ival=d1*d2;break;case/:res.ival=d1/d2;break;return res;C语言程序设计第12章 结构体和共用体循环队列的应用实例：舞伴配对n假设在大学生的周末舞会上，男、女学生各自排成一队。n舞会开始时，依次从男队和女队的队头各出一人配成舞伴。n如果两队初始人数不等，则较长的那

35、一队中未配对者等待下一轮舞曲。n要求男、女学生人数及其姓名以及舞会的轮数，由用户从键盘输入，屏幕输出每一轮舞伴的配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。n避免避免“假满假满”问题问题C语言程序设计第12章 结构体和共用体循环队列的应用实例：舞伴配对/函数功能：创建一个队列函数功能：创建一个队列void CreatQueue(QUEUE*Q)int n,i;Q-front=Q-rear=0;printf(请输入跳舞人数：请输入跳舞人数：);scanf(%d,&n);Q-qSize=n+1;printf(请输入各舞者人名：请输入各舞者人名：);for(i=0

36、;ielemi);Q-rear=n;C语言程序设计第12章 结构体和共用体循环队列的应用实例：舞伴配对/函数功能：循环队列出队，即删除队首元素函数功能：循环队列出队，即删除队首元素void DeQueue(QUEUE*Q,char*str)strcpy(str,Q-elemQ-front);Q-front=(Q-front+1)%Q-qSize;/函数功能：判断循环队列是否为空函数功能：判断循环队列是否为空int QueueEmpty(const QUEUE*Q)if(Q-front=Q-rear)/队列为空队列为空 return 1;else return 0;/函数功能：取出队首元素，队头

37、指针不改变函数功能：取出队首元素，队头指针不改变void GetQueue(const QUEUE*Q,char*str)strcpy(str,Q-elemQ-front);C语言程序设计第12章 结构体和共用体循环队列的应用实例：舞伴配对int main(void)QUEUE man,women;printf(男队：男队：n);CreatQueue(&man);printf(女队：女队：n);CreatQueue(&women);DancePartners(&man,&women);return 0;/函数功能：根据队列长短确定如何调用舞伴配对函数函数功能：根据队列长短确定如何调用舞伴配对函

38、数void DancePartners(QUEUE*man,QUEUE*women)if(man-qSize qSize)Match(man,women);else Match(women,man);C语言程序设计第12章 结构体和共用体循环队列的应用实例：舞伴配对/函数功能：舞伴配对函数功能：舞伴配对void Match(QUEUE*shortQ,QUEUE*longQ)int n;char str1N,str2N;printf(请输入舞会的轮数：请输入舞会的轮数：);scanf(%d,&n);while(n-)/循环循环n轮次轮次 while(!QueueEmpty(shortQ)/短队列

39、不为空短队列不为空 if(QueueEmpty(longQ)longQ-front=(longQ-front+1)%longQ-qSize;DeQueue(shortQ,str1);DeQueue(longQ,str2);printf(配对的舞者：配对的舞者：%s%sn,str1,str2);shortQ-front=(shortQ-front+1)%shortQ-qSize;if(QueueEmpty(longQ)longQ-front=(longQ-front+1)%longQ-qSize;GetQueue(longQ,str1);printf(第一个出场的未配对者的姓名：第一个出场的未配

40、对者的姓名：%sn,str1);C语言程序设计第12章 结构体和共用体12.9.2 树和图n结构中数据元素（节点）之间存在一对多的层次关系typedef struct BiTNodeint data;struct BiTNode*lchild;/左子树左子树struct BiTNode*rchild;/右子树右子树BI_TREE;C语言程序设计第12章 结构体和共用体二叉树n二叉树的特点二叉树的特点1 1）每个结点最多有两棵子树。）每个结点最多有两棵子树。2 2）左子树和右子树是有序的。）左子树和右子树是有序的。3 3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。）即使树中某结点

41、只有一棵子树，也要区分它是左子树还是右子树。4 4）二叉树有）二叉树有5 5种基本形态：空树，只有一个根结点，根结点只有左子树，根种基本形态：空树，只有一个根结点，根结点只有左子树，根结点只有右子树，根结点既有左子树也有右子树结点只有右子树，根结点既有左子树也有右子树。n典型的递归数据结构典型的递归数据结构要么要么为为空空要么要么由根结点由根结点、左右、左右子树组成，而子树组成，而左、右左、右子树分别是一棵二叉树子树分别是一棵二叉树C语言程序设计第12章 结构体和共用体二叉树的遍历操作124536742516374526731typedef struct BiTNodeint data;str

42、uct BiTNode*lchild;/左子树左子树struct BiTNode*rchild;/右子树右子树BI_TREE;C语言程序设计第12章 结构体和共用体二叉树的遍历操作/函数功能：二叉树先序遍历函数功能：二叉树先序遍历int PreOrderTraverse(BI_TREE*root,void(*visit)(int)if(root=NULL)return 1;(*visit)(root-data);if(PreOrderTraverse(root-lchild,visit)if(PreOrderTraverse(root-rchild,visit)return 1;return

43、0;1245367C语言程序设计第12章 结构体和共用体二叉树的遍历操作/函数功能：二叉树中序遍历函数功能：二叉树中序遍历int MidOrderTraverse(BI_TREE*root,void(*visit)(int)if(root=NULL)return 1;if(MidOrderTraverse(root-lchild,visit)(*visit)(root-data);if(MidOrderTraverse(root-rchild,visit)return 1;return 0;4251637C语言程序设计第12章 结构体和共用体二叉树的遍历操作/函数功能：二叉树后序遍历函数功能：

44、二叉树后序遍历int PostOrderTraverse(BI_TREE*root,void(*visit)(int)if(root=NULL)return 1;if(PostOrderTraverse(root-lchild,visit)if(PostOrderTraverse(root-rchild,visit)(*visit)(root-data);return 1;return 0;1245367C语言程序设计第12章 结构体和共用体图n数据元素（顶点）之间存在邻接关系，又称多对多关系一个图G是由两个集合V和E组成n用二元组表示123564无向图带权图123564有向图12356423

45、571346有向无环图12356423571346C语言程序设计第12章 结构体和共用体DFS遍历BFS遍历图的遍历图的遍历C语言程序设计第12章 结构体和共用体12.9.3 数据的逻辑结构和存储结构逻辑逻辑结构结构集合集合结构结构线性线性结构结构层次层次结构结构网状网状结构结构存储存储结构结构顺序顺序存储存储索引索引存储存储散列散列存储存储链式链式存储存储C语言程序设计第12章 结构体和共用体小结n两种新的数据类型n结构体类型的声明，结构体变量、数组、指针的定义n结构体成员的引用成员选择运算符，成员指向运算符结构体（结构体（struct）共用体（共用体（unionunion）关系紧密且逻辑相

46、关的多种不同类型的数据的集合情形互斥但逻辑相关的多种不同类型的数据的集合可以做函数参数不能做函数参数，不能进行比较操作各成员占相邻的存储单元，用sizeof来计算占用内存的总字节数同一内存在每一瞬时只能存放其中一种类型的成员对所有成员初始化只能对第一个成员初始化80/65C语言程序设计第12章 结构体和共用体n如何向函数传递结构体小结向函数向函数传递结构体的传递结构体的完整结构完整结构向函数向函数传递结构体的传递结构体的首地址首地址用结构体变量作函数参数用结构体数组/结构体指针作函数参数复制整个结构体成员的内容，一组数据仅复制结构体的首地址，一个数据参数传递直观，但开销大，效率低参数传递效率高

47、函数内对结构内容的修改不影响原结构体可以修改结构体指针所指向的结构体的内容81/65C语言程序设计第12章 结构体和共用体小结定长数组定长数组动态数组动态数组动态数据结构动态数据结构（动态链表）（动态链表）优点优点内存连续，可随机访问内存连续，可随机访问使用直观方便，适用于存储长度固定的数据集合适用于长度在程序运行时才能确切知道的数据集合适用于长度在程序运行过程中动态变化的集合缺点缺点属于静态内存分配，程序一旦运行长度不能改变，若想改变，只能修改程序，空间效率差，易越界出错需整体分配和释放内存内存不连续，不可随机访问，操作较为复杂n静态数据结构和动态数据结构的区别82/65C语言程序设计本章知识点小结和MOOC对应的视频83/52C语言程序设计第12章 结构体和共用体SuXiaoHongSuXiaoHongnQ&A84/65