C语言程序设计基础（通识版 慕课版） 课件 第9章 结构体和动态数据结构

第9章结构体和动态数据结构哈尔滨工业大学9.1结构体类型本节主要讨论如下问题：（1）如何声明结构体类型？如何定义结构体变量、数组或指针？（2）如何访问结构体的成员？对结构体可以执行哪些运算？（3）如何计算结构体在内存中占用的字节数？9.1.1结构体类型的声明和结构体变量的定义如何表示多个学生的信息呢？9.1.1结构体类型的声明和结构体变量的定义内存分配不集中，结构零散，内存管理困难，寻址效率不高对数组赋初值时，易发生错位相同类型的数据单独放在一起存储逻辑相关但类型不同的数据放在一起存储structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[4];};structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[3];};结构体成员(StructureMember)结构体标签(StructureTag)，可省略结构体模板(StructureTemplate)编译器不为其分配内存

关键字typedef为已存在的类型定义一个别名structstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[3];

};typedef

structstudentSTUDENT;typedefstructstudent{

longID;

charname[10];

chargender;

intbirthyear;

intscore[3];

}STUDENT;9.1.1结构体类型的声明和结构体变量的定义（1）先定义结构体类型

再定义变量名structstudentstu1;structstudent{ longID; charname[10]; chargender; intbirthyear; intscore[3];};（2）在定义结构体类型

的同时定义变量structstudent{ longID; charname[10]; chargender; intbirthyear; intscore[3];}stu1;9.1.1结构体类型的声明和结构体变量的定义结构体变量的定义（3）直接定义结构体变量（不指定结构体标签）struct{ longID; charname[10]; chargender; intbirthyear; intscore[3];}stu1;在定义结构体变量的同时对其进行初始化STUDENT

stu1={100310121,"张三",'M',{2001,5,19},{72,83,82}};structstudent

stu1={100310121,"张三",'M',{2001,5,19},{72,83,82}};初始化列表中成员的顺序必须和结构体类型定义的顺序一致9.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;结构体数组的定义和初始化typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[4];}STUDENT;typedefstructdate{ intyear;

intmonth; intday;}DATE;9.1.2结构体成员的初始化和访问结构体指针的定义和初始化

STUDENT

stu1;

STUDENT

*pt;pt=&stu1;如何定义指向结构体变量的指针？

STUDENT

*pt=&stu1;等价于9.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;inta[5];访问数组的元素通过下标（位置）选择数组元素访问结构体变量的成员通过名字访问结构体的成员typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;STUDENTstu;9.1.2结构体成员的初始化和访问访问结构体变量的成员成员选择运算符（圆点运算符）对嵌套的结构体成员，必须以级联方式访问stu1.studentID=100310121;stu1.studentName="张三";//errorstrcpy(stu1.studentName,"张三");stu1.studentSex='M';stu1.birthday.year=2001;stu1.birthday.month=5;stu1.birthday.day=19;9.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;STUDENTstu;如何访问结构体指针变量指向的结构体成员呢？ptstu1成员1成员2成员3成员4成员5通过成员选择运算符访问stu1.studentID=1;(*pt).studentID=1;

通过指向运算符访问pt->studentID=1;通过结构体指针访问结构体成员

STUDENT

stu1;

STUDENT

*pt=&stu1;如何定义指向结构体变量的指针？

9.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;当结构体嵌套时，如何访问结构体指针变量指向的结构体成员？

stu1.

birthday.

year=2001;(*pt).

birthday.

year=2001;

pt->

birthday.

year=2001;通过结构体指针访问结构体成员typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;9.1.2结构体成员的初始化和访问在一个结构体内包含了另一个结构体作为其成员9.1.2结构体成员的初始化和访问typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear;

intmonth; intday;}DATE;typedefstructdate{ intyear;

charmonth[10]; intday;}DATE;STUDENT

stu1={100310121,"张三",'M’,{2001,5,19},{72,83,90,82}};STUDENT

stu1={100310121,"张三",'M’,{2001,"May",19},{72,83,90,82}};

STUDENT

stu[30];

STUDENT

*pt;pt=stu;

如何定义指向结构体数组的指针？

STUDENT

*pt=stu;等价于STUDENT

*pt=&stu[0];等价于ptstu[30]stu[0]stu[1]stu[2]stu[3]stu[4]......stu[29]typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;9.1.2结构体成员的初始化和访问pt->studentID等价于(*pt).studentIDstu[0].studentID如何访问结构体指针指向的结构体数组成员？stu[30]ptstu[0]stu[1]stu[2]stu[3]stu[4]......stu[29]pt++是什么意思？

STUDENT

stu[30];

STUDENT

*pt=stu;pt=&stu[0];

typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;typedefstructdate{ intyear; intmonth; intday;}DATE;9.1.2结构体成员的初始化和访问9.1.3结构体占内存的字节数结构体类型占用内存字节数是所有成员占内存的总和吗？#include<stdio.h>typedefstructsample{charm1;intm2;charm3;}SAMPLE;//定义结构体类型SAMPLEintmain(void){SAMPLEs={'a',2,'b'}; //定义结构体变量s并对其进行初始化

printf("bytes=%d\n",sizeof(s));//打印结构体变量s所占内存字节数

return0;}内存对齐（Memory-alignment）对于大多数计算机，数据项要求从某个数量字节的倍数开始存放short型数据从偶数地址开始存放，而int型数据则被对齐在4字节地址边界为了满足内存地址对齐的要求，需要在较小的成员后加入补位结构体在内存中所占的字节数不仅与所定义的结构体类型有关，还与计算机系统本身有关9.1.4结构体占内存的字节数1.结构体变量的赋值操作typedefstructstudent{longID;charname[10];chargender;intbirthyear;intscore[3];}STUDENT;STUDENT

stu1={100310121,"张三",

'M’,{2001,5,19},{72,83,90,82}};STUDENTstu2;stu2=stu1;只能在相同类型的结构体变量之间进行赋值stu2.ID=stu1.ID;strcpy(,);stu2.gender=stu1.gender;stu2.birthday.year=stu1.birthday.year;stu2.birthday.month=stu1.birthday.month;stu2.birthday.day=stu1.birthday.day;for(i=0;i<3;i++){ stu2.score[i]=stu1.score[i];}9.1.5结构体的相关计算和操作2.结构体变量的取地址值操作9.1.5结构体的相关计算和操作&stu1.ID是结构体变量stu1的ID成员即stu1.ID的地址。不是stu1的地址。虽然&stu1.ID与&stu1具有相同的地址值，但二者的实际内涵是不同的，前者是结构体成员的地址，后者是结构体变量的地址，这两个地址的基类型是不同的。9.2结构体做函数参数向函数传递结构体的单个成员复制单个成员的内容向函数传递结构体的完整结构复制结构体的所有成员【例9.1】复数乘法。方法1：#include<stdio.h>typedefstructcomplex{intreal;intim;}COMPLEX;COMPLEXComplexMultiply(COMPLEXza,COMPLEXzb);intmain(void){COMPLEXx,y,z;scanf("%d+%di",&x.real,&x.im);scanf("%d+%di",&y.real,&y.im);z=ComplexMultiply(x,y);printf("%d+%di\n",z.real,z.im);return0;}//函数功能：计算两个复数之积COMPLEXComplexMultiply(COMPLEXza,COMPLEXzb){COMPLEXzc;zc.real=za.real*zb.real-za.im*zb.im;zc.im=za.real*zb.im+za.im*zb.real;returnzc;}复制结构体的所有成员给函数函数对结构体内容的修改不影响原结构体9.2.1在函数之间传递结构体数据用结构体变量作函数参数，并将函数返回类型定义为结构体类型，以便从函数返回结构体变量的值【例9.1】复数乘法。方法2：#include<stdio.h>typedefstructcomplex{intreal;intim;}COMPLEX;voidComplexMultiply(constCOMPLEXza,constCOMPLEXzb,COMPLEX*zc);intmain(void){COMPLEXx,y,z;scanf("%d+%di",&x.real,&x.im);scanf("%d+%di",&y.real,&y.im);ComplexMultiply(x,y,&z);printf("%d+%di\n",z.real,z.im);return0;}//函数功能：计算两个复数之积voidComplexMultiply(constCOMPLEXza,constCOMPLEXzb,COMPLEX*zc){zc->real=za.real*zb.real-za.im*zb.im;zc->im=za.real*zb.im+za.im*zb.real;}将从函数返回结构体zc修改为用指针变量作函数参数，通过将实参变量z的地址传给形参结构体指针zc，即让zc指向z，从而获得在函数中修改的结构体变量z的值。9.2.1在函数之间传递结构体数据【例9.1】复数乘法。方法3：#include<stdio.h>typedefstructcomplex{intreal;intim;}COMPLEX;voidComplexMultiply(constCOMPLEX*za,constCOMPLEX*zb,COMPLEX*zc);intmain(void){COMPLEXx,y,z;scanf("%d+%di",&x.real,&x.im);scanf("%d+%di",&y.real,&y.im);ComplexMultiply(&x,&y,&z);printf("%d+%di\n",z.real,z.im);return0;}//函数功能：计算两个复数之积voidComplexMultiply(constCOMPLEX*za,constCOMPLEX*zb,COMPLEX*zc){zc->real=za->real*zb->real-za->im*zb->im;zc->im=za->real*zb->im+za->im*zb->real;}如果不希望被调函数修改结构体变量的值，但又希望采用传地址的方式提高数据传递的效率，那么同样可以使用const限定符来保护结构体指针形参指向的数据。9.2.1在函数之间传递结构体数据【例9.2】奥运奖牌排行榜V2.0。修改例8.5程序，用结构体编程，按国名的字典序输出奥运奖牌排行榜。方法1:9.2.2结构体应用实例intmain(void){intn;structcountrycountries[N];printf("Howmanycountries?");scanf("%d",&n);Input(countries,n);StructSort(countries,n);//按国名字典序排序

Output(countries,n);return0;}//函数功能：输入n个国家的名字和奖牌数voidInput(structcountryc[],intn){printf("Inputnamesandmedals:\n");for(inti=0;i<n;i++){ scanf("%s%d",c[i].name,&c[i].medals);}}//函数功能：输出n个国家的名字和奖牌数voidOutput(structcountryc[],intn){printf("Sortedresults:\n");for(inti=0;i<n;i++){printf("%s:%d\n",c[i].name,c[i].medals);}}//函数功能：用结构体数组做函数参数，交换法实现按国名字典序排序voidStructSort(structcountryc[],intn){for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(strcmp(c[j].name,c[i].name)<0)//字符串比较

{SwapStruct(&c[i],&c[j]);}}}}//函数功能：两个structcountry类型的结构体数据互换voidSwapStruct(structcountry*x,structcountry*y){structcountryt;t=*x;*x=*y;*y=t;}9.2.2结构体应用实例【例9.2】奥运奖牌排行榜V2.0。修改例8.5程序，用结构体编程，按国名的字典序输出奥运奖牌排行榜。方法2：9.2.2结构体应用实例//函数功能：输入n个国家的名字和奖牌数voidInput(structcountry*p,intn){printf("Inputnamesandmedals:\n");structcountry*pEnd=p+n;//指向结构体数组最后一个元素的指针

for(;p<pEnd;p++){ scanf("%s%d",p->name,&p->medals);}}//函数功能：输出n个国家的名字和奖牌数voidOutput(structcountry*p,intn){printf("Sortedresults:\n");structcountry*pEnd=p+n;//指向结构体数组最后一个元素的指针

for(;p<pEnd;p++){printf("%s:%d\n",p->name,p->medals);}}//函数功能：用结构体指针做函数参数，交换法实现按国名字典序排序voidStructSort(structcountry*p,intn){for(inti=0;i<n-1;i++){for(intj=i+1;j<n;j++){if(strcmp((p+j)->name,(p+i)->name)<0)//字符串比较

{SwapStruct(p+i,p+j);}}}}9.2.2结构体应用实例如何向函数传递结构体这样的大数据对象小结向函数传递结构体的完整结构向函数传递结构体的首地址向函数传递结构体的完整结构向函数传递结构体的首地址用结构体变量作函数参数用结构体数组/结构体指针作函数参数向函数传递结构体的完整结构向函数传递结构体的首地址用结构体变量作函数参数用结构体数组/结构体指针作函数参数复制整个结构体成员的内容，一组数据仅复制结构体的首地址，一个数据向函数传递结构体的完整结构向函数传递结构体的首地址用结构体变量作函数参数用结构体数组/结构体指针作函数参数复制整个结构体成员的内容，一组数据仅复制结构体的首地址，一个数据参数传递直观，但开销大，效率低参数传递效率高向函数传递结构体的完整结构向函数传递结构体的首地址用结构体变量作函数参数用结构体数组/结构体指针作函数参数复制整个结构体成员的内容，一组数据仅复制结构体的首地址，一个数据参数传递直观，但开销大，效率低参数传递效率高函数内对结构内容的修改不影响原结构体可修改结构体指针所指向的结构体的内容9.3共用体类型和枚举类型用户自定义数据类型结构体，也称结构（struct）把关系紧密且逻辑相关的多种不同类型的的变量，组织到一个统一的名字之下共用体，也称联合（union）把情形互斥但逻辑相关的多种不同类型的变量，组织到一个统一的名字之下structperson

{charname[20];chargender;intage;

union

maritalStatemarital;intmarryFlag;};unionmaritalState{intsingle;/*未婚*/

structmarriedStatemarried;/*已婚*/

structdivorceStatedivorce;/*离婚*/};9.3共用体类型和枚举类型unionmaritalState{intsingle;/*未婚*/

structmarriedStatemarried;/*已婚*/

structdivorceStatedivorce;/*离婚*/};structmarriedState{

structdatemarryDay; charspouseName[20]; intchild;};structdivorceState{

structdatedivorceDay; intchild;};structdate{ intyear; intmonth; intday;};9.3共用体类型和枚举类型structperson{charname[20];charsex;intage;unionmaritalStatemarital;

intmarryFlag;//婚姻状态标记字段};structpersonp1;共用体的一个主要问题：如何标记共用体中当前起作用的成员是哪一个？if(p1.marryFlag==1){ //未婚}elseif(p1.marryFlag==2){ //已婚}else{//离婚}

每次对共用体的成员赋值时，程序负责改变标记字段的内容9.3共用体类型和枚举类型枚举标签9.4枚举类型及其应用枚举（Enumeration）——一一列举应用场合当某些量仅由有限个整型数据值组成时枚举类型的声明

enum

weeks{SUN,MON,TUE,WED,THU,FRI,SAT};

enum

weeks{SUN=7,MON=1,TUE,WED,THU,FRI,SAT}; typedefenumweeks{SUN,MON,TUE,WED,THU,FRI,SAT}WEEKS; enum

weeks

today;

WEEKStoday;值为0值为1枚举常量值为29.4枚举类型及其应用用枚举类型声明结构体中的标记字段structperson{charname[20];chargender;intage;unionmaritalStatemarital;enum{SINGLE,MARRIED,DIVORCE}marryFlag;};structpersonp1;

structperson{charname[20];chargender;intage;unionmaritalStatemarital;intmarryFlag;};structpersonp1;小结两种新的数据类型结构体（struct）共用体（union）关系紧密且逻辑相关的多种不同类型的数据的集合情形互斥但逻辑相关的多种不同类型的数据的集合可以做函数参数和返回值不能做函数参数，不能进行比较操作各成员占相邻的存储单元，用sizeof来计算占用内存的总字节数每一瞬时只能存其中一种类型的成员最后一次赋值的成员起作用对所有成员初始化只能对第一个成员初始化9.5动态内存分配和动态数据结构本节主要讨论如下问题：（1）什么是动态内存分配？如何进行动态内存分配？（2）常见的内存错误有哪些？如何避免这些内存错误？9.5.1动态内存分配C程序中变量的内存分配方式有以下3种：（1）从静态存储区分配（2）在栈上分配（3）从堆上分配1.函数malloc()函数malloc()的原型为：void*malloc(unsignedintsize);2.函数calloc()函数calloc()的函数原型为：void*calloc(unsignedintnum,unsignedintsize);3.函数free()函数free()的函数原型为：voidfree(void*p);4.函数realloc()函数realloc()的函数原型为：void*realloc(void*p,unsignedintsize);9.5.1动态内存分配void*型指针不指定其指向变量的类型，可指向任意类型的变量是一种generic（通用）或typeless（无类型）的指针

使用时，需强转(Type*)为其他类型9.5.1动态内存分配void*

malloc(unsignedintsize);向系统申请size字节的连续内存块，系统找到一块未占用的内存，将其标记为已占用，把首地址返回p=(float*)malloc(n*sizeof(float));free(p);//释放p指向的内存频繁申请/释放，速度慢，易造成内存碎片程序员不释放

内存泄漏释放仍继续使用

野指针空指针的用途

定义指针时进行初始化在程序中常用作状态比较指针不能与非指针类型变量进行比较但可与NULL（即0值）进行相等或不等的关系运算

p=(int*)malloc(n*sizeof(int));if(p==NULL)//判断内存申请是否成功{printf("Noenoughmemory!\n");exit(0);}int*p;Heap（堆区）若申请不成功则返回NULL9.5.1动态内存分配9.5.2动态数据结构之链表本节主要讨论如下问题：（1）何为单向链表？何为单向循环链表？（2）如何对链表进行遍历以及增、删节点的操作？在C语言中，指针之所以重要，原因主要有以下几点：（1）指针作函数参数，提供了一种从函数返回修改的变量值的手段。（2）利用指针的增1和减1运算来寻址数组元素，可以提高程序的执行效率。（3）指针为动态内存分配系统提供了支持。（4）利用指针和动态内存分配实现动态数据结构（如链表、队列、二叉树等）。9.5.2动态数据结构之链表数组（包括结构体数组）实际上是一种线性表的顺序存储方式，像这种用一组地址连续的存储单元存放一个线性表，称为顺序表。优点表中的数据元素在逻辑上和物理上都是相邻的，使用直观，便于实现线性表中任一元素的快速随机存取。缺点插入和删除操作时需要移动大量的数组元素数组属于静态数据结构，数组的长度不能在程序运行时改变数组的长度，实际使用的数组元素个数不能超过定义数组时指定的数组长度的限制，否则就会发生下标越界错误，而低于所设定的最大长度时，又会造成系统资源的浪费，因而空间效率差CB下的错误提示：field'next'hasincompletetypeVC下的错误提示：'next'usesundefinedstruct'link'不能包含本结构体类型的成员系统无法预知占据多少内存

9.5.2动态数据结构之链表可以包含指向本结构体类型的指针变量structlink

{

intdata;

structlink*next;

};//递归数据结构structlink

{

int data;

structlinknext;

};structlink{

int

data;//数据域：存储节点的数据信息

structlink*next;//指针域：存储其直接后继信息};典型代表——单向链表（LinkedTable）用一组任意的存储单元（不一定连续）链式存储线性表数据9.5.2动态数据结构之链表只包含一个指针域，又称线性链表或单向链表9.5.2动态数据结构之链表向单向链表中添加节点分两种情况：原链表为空表、非空表若原链表为空表(head==NULL)，则将新建节点p置为头节点若原链表为非空，则将新建节点newP添加到表尾if(head==NULL)//若链表为空表

{ head=newP; }else { p=head; while(pr->next!=NULL)//若未到表尾 { p=p->next;//pr指向下一节点 } p->next=newP;//末节点指针指向新建节点}newP=(structlink*)malloc(sizeof(structlink));newP->data=nodeData;newP->next=NULL;9.5.2动态数据结构之链表删除节点分两种情况：空表、非空表（待删节点为头节点、非头节点）datanextheaddatanextpr//找待删除节点while(p->data!=nodeData&&p->next!=NULL)//未找到且未到表尾{

pr=p;//在pr中保存当前节点的指针

p=p->next;//p指向当前节点的下一节点}pp待删除节点9.5.2动态数据结构之链表分两种情况：空表、非空表（待删节点为头节点、非头节点）若原链表为空表，则退出程序若待删节点p是头节点，则将head指向当前节点的后继节点即可datanexthead待删除节点datanextp头节点if(p->data==nodeData)//找到待删节点{

if(p==head)//若待删节点p为头节点{ head=p->next;//head指向待删除节点p的后继节点}

else//若待删节点不是头节点{ pr->next=p->next;//前驱节点指向待删节点的后继} free(p); //释放为已删除节点分配的内存}9.5.2动态数据结构之链表若待删节点不是头节点，则前驱节点指向后继节点datanextdatanext待删除节点datanextp中间节点datanext若已搜到表尾（p->next==NULL）仍未找到待删除节点，则显示“未找到”prif(p->data==nodeData)//找到待删节点{ if(p==head)//若待删节点p为头节点{ head=p->next;//head指向待删除节点p的后继节点} else//若待删节点不是头节点{ pr->next=p->next;//前驱节点指向待删节点的后继} free(p); //释放为已删除节点分配的内存}else//找到表尾仍未找到{printf("Notfound!\n");}9.5.2动态数据结构之链表在升序的链表中插入节点分两种情况：空表、非空有序表非空表分三种情况：在头节点前、中间节点、表尾节点后插入新节点若原链表为空表，则将新节点p作为头节点，让head指向新节点phead待插入节点datap∧if(head==NULL)//若原链表为空表{ head=p;//待插入节点作为头节点}else//若原链表为非空{//找待插入位置while(nodeData>pr->data&&pr->next!=NULL){ temp=pr;//在temp中保存当前节点的指针 pr=pr->next;//pr指向当前节点的后继节点

} ……}p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;head9.5.2动态数据结构之链表待插入节点nodeDatanextpdatanextdata∧prprtemp待插入位置p=(structlink*)malloc(sizeof(structlink));p->data=nodeData;p->next=NULL;pr=head;if(head==NULL)//若原链表为空表{ head=p;//待插入节点作为头节点}else//若原链表为非空{

//找待插入位置

while(nodeData>pr->data&&pr->next!=NULL)

{ temp=pr;//在temp中保存当前节点的指针 pr=pr->next;//pr指向当前节点的后继节点

} ……}若原链表非空，则按节点值大小（假设升序）确定插入新节点的位置9.5.2动态数据结构之链表head待插入节点datanextpdatanextdatanextdata∧if(nodeData<=pr->data)//不在表尾插入{

if(pr==head)//若在头节点前插入新节点 { p->next=head;//将新节点指向链头

head=p;//head指向新节点 } else//若在链表中间插入新节点 { pr=temp;