C语言程序设计PPT课件第12章结构体和共用体.ppt

《C语言程序设计PPT课件第12章结构体和共用体.ppt》由会员分享，可在线阅读，更多相关《C语言程序设计PPT课件第12章结构体和共用体.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第第第12121212章章章章 结构体和结构体和结构体和结构体和共用体共用体共用体共用体2023/1/162/60本章学习内容本章学习内容 结构体数据类型，共用体数据类型，枚举数据类型，结构体数据类型，共用体数据类型，枚举数据类型，结构体数据类型，共用体数据类型，枚举数据类型，结构体数据类型，共用体数据类型，枚举数据类型，定义数据类型的别名定义数据类型的别名定义数据类型的别名定义数据类型的别名 结构体变量、结构体数组、结构体指针的定义和初结构体变量、结构体数组、结构体指针的定义和初结构体变量、结构体数组、结构体指针的定义和初结构体变量、结构体数组、结构体指针的定义和初始化始化始化始化 结构体

2、成员的引用，成员选择运算符，指向运算符结构体成员的引用，成员选择运算符，指向运算符结构体成员的引用，成员选择运算符，指向运算符结构体成员的引用，成员选择运算符，指向运算符 向函数传递结构体变量、结构体数组、结构体指针向函数传递结构体变量、结构体数组、结构体指针向函数传递结构体变量、结构体数组、结构体指针向函数传递结构体变量、结构体数组、结构体指针 动态数据结构、动态链表动态数据结构、动态链表动态数据结构、动态链表动态数据结构、动态链表2023/1/163/60 二进制数二进制数类型本不存在类型本不存在内存里存的内容，你认为它是什么，它就内存里存的内容，你认为它是什么，它就内存里存的内容，你认为

3、它是什么，它就内存里存的内容，你认为它是什么，它就是什么是什么是什么是什么在早期的机器指令及汇编语言中，数据对在早期的机器指令及汇编语言中，数据对在早期的机器指令及汇编语言中，数据对在早期的机器指令及汇编语言中，数据对象均用二进制数表示，没有类型的概念象均用二进制数表示，没有类型的概念象均用二进制数表示，没有类型的概念象均用二进制数表示，没有类型的概念 一般的一般的CPU只支持两种类型只支持两种类型整数、浮点数整数、浮点数整数、浮点数整数、浮点数12.112.1从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型2023/1/164/

4、60 在高级语言引入了基本数据类型在高级语言引入了基本数据类型整型、浮点型、字符型等整型、浮点型、字符型等整型、浮点型、字符型等整型、浮点型、字符型等不同语言会定义不同的基本类型不同语言会定义不同的基本类型不同语言会定义不同的基本类型不同语言会定义不同的基本类型基本数据类型并不能方便地解决所有问题基本数据类型并不能方便地解决所有问题基本数据类型并不能方便地解决所有问题基本数据类型并不能方便地解决所有问题 有些语言（如有些语言（如有些语言（如有些语言（如PL/1PL/1）中试图规定较多的类型，如）中试图规定较多的类型，如）中试图规定较多的类型，如）中试图规定较多的类型，如数组、树、栈等，但实践证

5、明不是个好办法数组、树、栈等，但实践证明不是个好办法数组、树、栈等，但实践证明不是个好办法数组、树、栈等，但实践证明不是个好办法12.112.1从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型2023/1/165/60 用户自己构造数据类型用户自己构造数据类型用户自己构造数据类型用户自己构造数据类型-复合数据类型复合数据类型复合数据类型复合数据类型由基本数据类型迭代派生而来，表示复杂的数据对象由基本数据类型迭代派生而来，表示复杂的数据对象由基本数据类型迭代派生而来，表示复杂的数据对象由基本数据类型迭代派生而来，表示复杂的数据对象

6、典型的代表就是典型的代表就是典型的代表就是典型的代表就是“结构体结构体结构体结构体”抽象数据类型（抽象数据类型（抽象数据类型（抽象数据类型（Abstract Data TypeAbstract Data Type，简称，简称，简称，简称ADTADT）在复合数据类型基础上增加了对数据的操作在复合数据类型基础上增加了对数据的操作在复合数据类型基础上增加了对数据的操作在复合数据类型基础上增加了对数据的操作 抽象数据类型进而进化为抽象数据类型进而进化为抽象数据类型进而进化为抽象数据类型进而进化为“类类类类(Class)”(Class)”这是一个跨时代的进步这是一个跨时代的进步这是一个跨时代的进步这是一

7、个跨时代的进步ClassClass是是是是Object-OrientedObject-Oriented的一个重要概念的一个重要概念的一个重要概念的一个重要概念12.112.1从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型从基本数据类型到抽象数据类型2023/1/166/60为什么要定义结构体类型为什么要定义结构体类型 在程序里表示一个人（姓名、年龄、性别在程序里表示一个人（姓名、年龄、性别在程序里表示一个人（姓名、年龄、性别在程序里表示一个人（姓名、年龄、性别），），），），怎么表示？怎么表示？怎么表示？怎么表示？想表示多个人呢？想表示多个人呢？想表示多个

8、人呢？想表示多个人呢？如何用计算机程序实现下述表格的管理？如何用计算机程序实现下述表格的管理？如何用计算机程序实现下述表格的管理？如何用计算机程序实现下述表格的管理？2023/1/167/60数组的解决方法数组的解决方法2023/1/168/60数组的解决方法数组的解决方法2023/1/169/60 数据的内存管理方式数据的内存管理方式 数组的解决方法数组的解决方法分配内存不集中，寻址效率不高分配内存不集中，寻址效率不高 对数组赋初值时，易发生错位对数组赋初值时，易发生错位 结构显得零散，不易管理结构显得零散，不易管理2023/1/1610/60希望的内存分配图希望的内存分配图 2023/1/

9、1611/60结构体结构体类型类型的声明的声明声明了一个结构体类型声明了一个结构体类型构成结构体的变量构成结构体的变量称为结构体的成员称为结构体的成员(Structure Member)结构体的名字结构体的名字称为结构体标称为结构体标签签(Structure Tag)2023/1/1612/60结构体结构体类型类型的声明的声明结构体模板结构体模板(Structure Template)Dont forget the semicolon!形成一个类型声明的样板形成一个类型声明的样板形成一个类型声明的样板形成一个类型声明的样板用于生成结构体变量用于生成结构体变量用于生成结构体变量用于生成结构体变量

10、但并未声明结构体变量但并未声明结构体变量但并未声明结构体变量但并未声明结构体变量因而编译器不为其分配内存因而编译器不为其分配内存因而编译器不为其分配内存因而编译器不为其分配内存 2023/1/1613/60（1 1）先定义结构体类型，再定义变量名）先定义结构体类型，再定义变量名（2 2）在定义类型的同时定义变量）在定义类型的同时定义变量（3 3）直接定义结构体变量（不指定结构体标签）直接定义结构体变量（不指定结构体标签）结构体结构体结构体结构体变量变量变量变量的定义的定义的定义的定义2023/1/1614/60用用typedef定义数据类型定义数据类型structstruct students

11、tudent stu1,stu2;stu1,stu2;/*It works*/*It works*/studentstudent stu1,stu2;stu1,stu2;/*Can this work?*/*Can this work?*/structstruct stu1,stu2;stu1,stu2;/*Can this work?*/*Can this work?*/STUDENTSTUDENT stu1,stu2;stu1,stu2;/*It works!*/*It works!*/关键字关键字typedef为一种为一种已存在的已存在的类型定义一个类型定义一个别名别名，并未定义新类型，

12、并未定义新类型STUDENT与与struct student类型是类型是同义词同义词2023/1/1615/60等价于等价于结构体变量的初始化结构体变量的初始化结构体变量的初始化结构体变量的初始化等价于等价于注意！注意！2023/1/1616/60 嵌套的结构体（嵌套的结构体（嵌套的结构体（嵌套的结构体（Nested StructureNested Structure）就是在一个）就是在一个）就是在一个）就是在一个结构体内包含了另一个结构体作为其成员结构体内包含了另一个结构体作为其成员结构体内包含了另一个结构体作为其成员结构体内包含了另一个结构体作为其成员 嵌套的结构体嵌套的结构体结构体定义结

13、构体定义可以嵌套可以嵌套2023/1/1617/60 访问结构体变量的成员必须使用访问结构体变量的成员必须使用访问结构体变量的成员必须使用访问结构体变量的成员必须使用成员选择运算符成员选择运算符成员选择运算符成员选择运算符（也称圆点运算符）（也称圆点运算符）（也称圆点运算符）（也称圆点运算符）结构体变量的引用结构体变量的引用 当出现结构体嵌套时，必须当出现结构体嵌套时，必须当出现结构体嵌套时，必须当出现结构体嵌套时，必须以级联方式访问结构体成员以级联方式访问结构体成员以级联方式访问结构体成员以级联方式访问结构体成员2023/1/1618/60【例例例例12.112.1】演示结构体变量的赋值和引

14、用方法演示结构体变量的赋值和引用方法演示结构体变量的赋值和引用方法演示结构体变量的赋值和引用方法结构体变量的引用结构体变量的引用按结构体的成员顺序逐按结构体的成员顺序逐一对相应成员进行赋值一对相应成员进行赋值格式符格式符%02d中中2d前面的前导符前面的前导符0表示输表示输出数据时，若左边有多余位，则补出数据时，若左边有多余位，则补02023/1/1619/60 【例例例例12.112.1】若要从键若要从键若要从键若要从键盘输入结盘输入结盘输入结盘输入结构体变量构体变量构体变量构体变量stu1stu1的内的内的内的内容，那么容，那么容，那么容，那么程序如何程序如何程序如何程序如何修改？修改？修

15、改？修改？两个地址有何不同？两个地址有何不同？2023/1/1620/60 【例例例例12.112.1】若要从键若要从键若要从键若要从键盘输入结盘输入结盘输入结盘输入结构体变量构体变量构体变量构体变量stu1stu1的内的内的内的内容，那么容，那么容，那么容，那么程序如何程序如何程序如何程序如何修改？修改？修改？修改？结构体成员的地址与结构体成员的地址与该成员在结构体中所该成员在结构体中所处的位置及其所占内处的位置及其所占内存的字节数相关存的字节数相关结构体变量的地址结构体变量的地址&stu2是该变量所占是该变量所占内存空间的首地址内存空间的首地址2023/1/1621/60结构体所占内存的字

16、节数结构体所占内存的字节数 struct struct 类型用内存字节数类型用内存字节数类型用内存字节数类型用内存字节数 =?=?是所有成员变量的内存总和吗？是所有成员变量的内存总和吗？是所有成员变量的内存总和吗？是所有成员变量的内存总和吗？printf(%dn,sizeof(printf(%dn,sizeof(structstruct samplesample););用运算符用运算符用运算符用运算符sizeofsizeof获得结构体大小获得结构体大小获得结构体大小获得结构体大小sizeofsizeof(变量或表达式变量或表达式变量或表达式变量或表达式)sizeofsizeof(类型类型类型类

17、型)12printf(%dn,sizeof(printf(%dn,sizeof(SAMPLESAMPLE););【例例例例12.212.2】2023/1/1622/60结构体所占内存的字节数结构体所占内存的字节数事实上，所有数据类型在内存中都是从事实上，所有数据类型在内存中都是从偶数偶数偶数偶数地址开始存放的地址开始存放的且结构所占的实际空间一般是按照机器字长对齐的且结构所占的实际空间一般是按照机器字长对齐的不同的编译器、平台，对齐方式会有变化不同的编译器、平台，对齐方式会有变化结构体变量的成员的存储结构体变量的成员的存储对齐规则对齐规则对齐规则对齐规则是与机器相关的是与机器相关的具有特定数据

18、类型的具有特定数据类型的数据项大小数据项大小数据项大小数据项大小也是与机器相关的也是与机器相关的所以一个结构体在内存中的存储格式也是与机器相关的所以一个结构体在内存中的存储格式也是与机器相关的12个字节个字节chchf fchchchchchchf f2023/1/1623/6012.3结构体结构体数组数组的定义和初始化的定义和初始化2023/1/1624/6012.3结构体结构体数组数组的定义和初始化的定义和初始化建立了数据库中的多条记录，每条对应一个学生信息建立了数据库中的多条记录，每条对应一个学生信息2023/1/1625/60 【例例例例12.312.3】利用利用利用利用结构体数组计结

19、构体数组计结构体数组计结构体数组计算每个学生的算每个学生的算每个学生的算每个学生的平均分平均分平均分平均分2023/1/1626/6012.4结构体结构体指针指针的定义和初始化的定义和初始化ptstu1 STUDENTSTUDENT stu1;stu1;STUDENTSTUDENT *pt;pt;pt=pt=&stu1;stu1;成员成员1成员成员2成员成员3成员成员4成成员员5 如何定义指向如何定义指向如何定义指向如何定义指向结构体变量结构体变量结构体变量结构体变量的指针？的指针？的指针？的指针？STUDENTSTUDENT *pt=pt=&stu1;stu1;等价于等价于2023/1/16

20、27/6012.4结构体结构体指针指针的定义和初始化的定义和初始化 如何访问如何访问如何访问如何访问结构体指针变量结构体指针变量结构体指针变量结构体指针变量所指向的所指向的所指向的所指向的结构体成员呢？结构体成员呢？结构体成员呢？结构体成员呢？STUDENTSTUDENT stu1;stu1;STUDENTSTUDENT *pt=pt=&stu1;stu1;ptstu1成员成员1成员成员2成员成员3成员成员4成成员员5 通过通过通过通过s stu1tu1和和和和成员选择运算符成员选择运算符成员选择运算符成员选择运算符访问结构体成员访问结构体成员访问结构体成员访问结构体成员stu1.stu1.s

21、tudentID=1;studentID=1;通过通过通过通过ptpt和和和和指向运算符指向运算符指向运算符指向运算符访问结构体成员访问结构体成员访问结构体成员访问结构体成员(*pt).(*pt).studentID=1;studentID=1;pt-pt-studentID=1;studentID=1;2023/1/1628/6012.4结构体结构体指针指针的定义和初始化的定义和初始化ptstu1成员成员1成员成员2成员成员3成员成员4成成员员5 当结构体当结构体当结构体当结构体嵌套嵌套嵌套嵌套时，如何访问结构体时，如何访问结构体时，如何访问结构体时，如何访问结构体指针变量所指向的结构体成员

22、？指针变量所指向的结构体成员？指针变量所指向的结构体成员？指针变量所指向的结构体成员？stu1.stu1.birthday.birthday.year=1999;year=1999;(*pt).(*pt).birthday.birthday.year=1999;year=1999;pt-pt-birthday.birthday.year=1999;year=1999;STUDENTSTUDENT stu1;stu1;STUDENTSTUDENT *pt=pt=&stu1;stu1;2023/1/1629/6012.4结构体结构体指针指针的定义和初始化的定义和初始化 STUDENTSTUDENT

23、 stu30;stu30;STUDENTSTUDENT *pt;pt;pt=stu;pt=stu;如何定义指向如何定义指向如何定义指向如何定义指向结构体数组结构体数组结构体数组结构体数组的指针？的指针？的指针？的指针？STUDENTSTUDENT *pt=stu;pt=stu;等价于等价于STUDENTSTUDENT *pt=&stu0;pt=&stu0;等价于等价于ptstu30stu0stu1stu2stu3stu4stu5.stu292023/1/1630/60使用使用使用使用pt+pt+，使，使，使，使ptpt指向指向指向指向stu1stu1pt-pt-studentIDstudent

24、ID等价于等价于等价于等价于 stu1.stu1.studentIDstudentIDpt12.412.4结构体结构体结构体结构体指针指针指针指针的定义和初始化的定义和初始化的定义和初始化的定义和初始化 STUDENTSTUDENT stu30;stu30;STUDENTSTUDENT *pt=stu;pt=stu;如何访问如何访问如何访问如何访问结构体数组指针结构体数组指针结构体数组指针结构体数组指针指向的指向的指向的指向的结构体成员？结构体成员？结构体成员？结构体成员？stu30stu0stu1stu2stu3stu4stu5.stu292023/1/1631/6012.5向函数传递结构体

25、向函数传递结构体 向函数传递结构体的向函数传递结构体的单个成员单个成员复制单个成员的内容复制单个成员的内容复制单个成员的内容复制单个成员的内容函数内对结构内容的修改不影响原结构函数内对结构内容的修改不影响原结构函数内对结构内容的修改不影响原结构函数内对结构内容的修改不影响原结构 向函数传递结构体的向函数传递结构体的完整结构完整结构 向函数传递结构体的向函数传递结构体的首地址首地址2023/1/1632/60struct date int year;int month;int day;void func(struct date p)p.year=2000;p.month=5;p.day=22;B

26、efore function call:1999/04/23Before function call:1999/04/23After function call:1999/04/23After function call:1999/04/23结构体结构体结构体结构体变量变量变量变量作函数参数作函数参数作函数参数作函数参数 【例例例例12.412.4】2023/1/1633/60struct date int year;int month;int day;void func(struct date*p*p)p-p-year=2000;p-p-month=5;p-p-day=22;Before f

27、unction call:1999/04/23Before function call:1999/04/23After function call:After function call:2000/05/222000/05/22结构体结构体结构体结构体指针指针指针指针作函数参数作函数参数作函数参数作函数参数指针作函数形参指针作函数形参实参必须为地址值实参必须为地址值 【例例例例12.512.5】2023/1/1634/60struct date int year;int month;int day;struct datestruct date func(struct date p p)p.p.

28、year=2000;p.p.month=5;p.p.day=22;return p;return p;Before function call:1999/04/23Before function call:1999/04/23After function call:After function call:2000/05/222000/05/22结构体变量结构体变量结构体变量结构体变量作函数作函数作函数作函数返回值返回值返回值返回值 【例例例例12.612.6】2023/1/1635/6012.5向函数传递结构体向函数传递结构体 向函数传递结构体的完整结构向函数传递结构体的完整结构复制整个结构体

29、成员的内容，多个值复制整个结构体成员的内容，多个值复制整个结构体成员的内容，多个值复制整个结构体成员的内容，多个值函数内对结构内容的修改不影响原结构函数内对结构内容的修改不影响原结构函数内对结构内容的修改不影响原结构函数内对结构内容的修改不影响原结构内容传递更直观，但内容传递更直观，但内容传递更直观，但内容传递更直观，但开销大开销大开销大开销大 向函数传递结构体的首地址向函数传递结构体的首地址用用用用结构体数组结构体数组结构体数组结构体数组/结构体指针作结构体指针作结构体指针作结构体指针作函数参数函数参数函数参数函数参数仅复制结构体的首地址，一个值仅复制结构体的首地址，一个值仅复制结构体的首地

30、址，一个值仅复制结构体的首地址，一个值修改结构体指针所指向的结构体的内容修改结构体指针所指向的结构体的内容修改结构体指针所指向的结构体的内容修改结构体指针所指向的结构体的内容指针传递效率高指针传递效率高指针传递效率高指针传递效率高2023/1/1636/6012.5向函数传递结构体向函数传递结构体 【例例例例12.712.7】修改例修改例修改例修改例12.312.3程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数编程并输出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分 2023/1/

31、1637/6012.5向函数传递结构体向函数传递结构体 【例例例例12.712.7】修改例修改例修改例修改例12.312.3程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数编程并输出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分 2023/1/1638/6012.5向函数传递结构体向函数传递结构体 【例例例例12.712.7】修改例修改例修改例修改例12.312.3程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数编程并输

32、出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分 2023/1/1639/6012.5向函数传递结构体向函数传递结构体 【例例例例12.712.7】修改例修改例修改例修改例12.312.3程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数程序，用结构体数组作函数参数编程并输出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分编程并输出计算学生的平均分 2023/1/1640/60用户自定义的数据类型用户自定义的数据类型用户自定义的数据类型用户自定义的数据类型 结构体结构体（StructStruc

33、t）把把把把关系紧密关系紧密关系紧密关系紧密且且且且逻辑相关逻辑相关逻辑相关逻辑相关的多种的多种的多种的多种不同类型不同类型不同类型不同类型的变量，的变量，的变量，的变量，组织到统一的名字之下组织到统一的名字之下组织到统一的名字之下组织到统一的名字之下占用占用占用占用相邻相邻相邻相邻的一段内存单元的一段内存单元的一段内存单元的一段内存单元 共用体，也称联合共用体，也称联合（UnionUnion）把把把把情形互斥情形互斥情形互斥情形互斥但但但但逻辑相关逻辑相关逻辑相关逻辑相关的多种的多种的多种的多种不同类型不同类型不同类型不同类型的变量，的变量，的变量，的变量，组织到统一的名字之下组织到统一的名

34、字之下组织到统一的名字之下组织到统一的名字之下占用占用占用占用同一段同一段同一段同一段内存单元，每一时刻只有一个数据起内存单元，每一时刻只有一个数据起内存单元，每一时刻只有一个数据起内存单元，每一时刻只有一个数据起作用作用作用作用2023/1/1641/6012.6共用体共用体structstruct sample sample shortshort i;i;charchar ch;ch;floatfloat f;f;0 x0037b00unionunion sample sample shortshort i;i;charchar ch;ch;floatfloat f;f;printf(%d

35、n,sizeof(struct sample);printf(%dn,sizeof(struct sample);8个字节个字节i ichchf f4个字节个字节printf(%dn,sizeof(union sample);printf(%dn,sizeof(union sample);i ichchf f 【例例例例12.812.8】2023/1/1642/6012.6共用体共用体 sizeof(union number)sizeof(union number)取决于取决于取决于取决于占空间最多占空间最多占空间最多占空间最多的那个成员的那个成员的那个成员的那个成员变量变量变量变量0 x00

36、37b00同一内存单元在每一瞬时只能存放其中一种类型的成员同一内存单元在每一瞬时只能存放其中一种类型的成员起作用的成员是起作用的成员是最后一次存放最后一次存放最后一次存放最后一次存放的成员，不能作为函数参数的成员，不能作为函数参数不能进行比较操作，只能对第一个成员初始化不能进行比较操作，只能对第一个成员初始化f f4个字节个字节2023/1/1643/6012.612.6共用体共用体共用体共用体2023/1/1644/6012.612.6共用体共用体共用体共用体2023/1/1645/60枚举数据类型枚举数据类型 枚举枚举枚举枚举（EnumerationEnumeration）数据类型数据类型

37、数据类型数据类型描述的是一组整型值的集合描述的是一组整型值的集合描述的是一组整型值的集合描述的是一组整型值的集合用于当某些量仅由有限个数据值组成时用于当某些量仅由有限个数据值组成时用于当某些量仅由有限个数据值组成时用于当某些量仅由有限个数据值组成时 enumenum weeks SUN,MON,TUE,WED,THU,FRI,SAT;weeks SUN,MON,TUE,WED,THU,FRI,SAT;enumenum weeks weeks todaytoday;enum enum response no,yes,none;response no,yes,none;enum enum resp

38、onse response answeranswer;todaytoday =TUE;=TUE;answeranswer=yes;=yes;enum enum response no=-1,yes=1,none=0;response no=-1,yes=1,none=0;其值为其值为2 2其值为其值为1 12023/1/1646/60 下面的结构是什么意思？下面的结构是什么意思？下面的结构是什么意思？下面的结构是什么意思？struct struct temp temp intint data;data;structstruct temp pt;temp pt;CBCBCBCB下的错误提示：下的

39、错误提示：下的错误提示：下的错误提示：field pt has incomplete typefield pt has incomplete type VCVCVCVC下的错误提示：下的错误提示：下的错误提示：下的错误提示：pt uses undefined struct temppt uses undefined struct temp 下面的结构是什么意思呢？下面的结构是什么意思呢？下面的结构是什么意思呢？下面的结构是什么意思呢？struct struct temp temp intint data;data;structstruct temp*pt;temp*pt;结构体声明时不能结构体

40、声明时不能包含本结构体类型包含本结构体类型成员，成员，系统将无法系统将无法为这样的结构体类为这样的结构体类型分配内存型分配内存 可包含指向本结构体可包含指向本结构体类型的指针变量类型的指针变量问题的提出问题的提出问题的提出问题的提出2023/1/1647/60动态数据结构动态数据结构单向链表单向链表structstruct Link Link intint data;data;structstruct Link*next;Link*next;datanextheaddatanextdatanextdataNULL 链表链表（Linked TableLinked Table）:线性表的链式存储结

41、构线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数特点：用一组任意的存储单元存储线性表的数特点：用一组任意的存储单元存储线性表的数特点：用一组任意的存储单元存储线性表的数据；存储单元可以是连续的，也可是不连续的据；存储单元可以是连续的，也可是不连续的据；存储单元可以是连续的，也可是不连续的据；存储单元可以是连续的，也可是不连续的2023/1/1648/60链表的定义链表的定义datanextheaddatanextdatanextdataNULL 链表链表（Linked tableLinked table）:线性表的链式存储结构线性表的链式存储结构为表示每个元素与后继元素的逻辑关系

42、，除存为表示每个元素与后继元素的逻辑关系，除存为表示每个元素与后继元素的逻辑关系，除存为表示每个元素与后继元素的逻辑关系，除存储元素本身信息外，还要存储其直接后继信息储元素本身信息外，还要存储其直接后继信息储元素本身信息外，还要存储其直接后继信息储元素本身信息外，还要存储其直接后继信息两部分信息组两部分信息组成一个节点成一个节点structstruct Link Link intint data;data;structstruct Link*next;Link*next;2023/1/1649/60datanextheaddatanextdatanextdataNULL数据域：存储数据数据域：

43、存储数据元素信息元素信息指针域：存储直接指针域：存储直接后继的节点信息后继的节点信息链表的定义链表的定义链表的定义链表的定义 链表链表（Linked TableLinked Table）:线性表的链式存储结构线性表的链式存储结构为表示每个元素与后继元素的逻辑关系，除存为表示每个元素与后继元素的逻辑关系，除存为表示每个元素与后继元素的逻辑关系，除存为表示每个元素与后继元素的逻辑关系，除存储元素本身信息外，还要存储其直接后继信息储元素本身信息外，还要存储其直接后继信息储元素本身信息外，还要存储其直接后继信息储元素本身信息外，还要存储其直接后继信息structstruct Link Link int

44、int data;data;structstruct Link*next;Link*next;n个节点链接成一个链表（因为只包含一个指针域，故又个节点链接成一个链表（因为只包含一个指针域，故又称线性链表或单向链表）称线性链表或单向链表）2023/1/1650/60链表的建立链表的建立 向链表中添加一个新节点向链表中添加一个新节点向链表中添加一个新节点向链表中添加一个新节点data=Anodedata=Bnodedata=C nodehead空指针空指针空指针空指针NULLNULLNULLNULL表示表示表示表示链表结尾链表结尾链表结尾链表结尾链表的头指针：链表的头指针：链表的头指针：链表的头指

45、针：访问链表的关键访问链表的关键访问链表的关键访问链表的关键2023/1/1651/60链表的建立链表的建立 若原链表为空表若原链表为空表若原链表为空表若原链表为空表(head=NU(head=NULL)LL)，则将新，则将新，则将新，则将新建建建建节点节点节点节点p p置为头节点置为头节点置为头节点置为头节点 head(1)head=p(1)head=pdatanext p新建节点新建节点新建节点新建节点(2)pr=ppr(3)pr-next=NULL2023/1/1652/60datanext新建节点新建节点新建节点新建节点p链表的建立链表的建立 若原链表为非空，则将新建节点若原链表为非空

46、，则将新建节点若原链表为非空，则将新建节点若原链表为非空，则将新建节点p p添加到表尾添加到表尾添加到表尾添加到表尾 (1)pr-next=p(1)pr-next=p(2)pr=pheaddataprpr(3)pr-next=NULLnext2023/1/1653/60链表的删除操作链表的删除操作 若原链表为空表，则退出程序若原链表为空表，则退出程序若原链表为空表，则退出程序若原链表为空表，则退出程序 若待删除节点若待删除节点若待删除节点若待删除节点p p是头节点，则将是头节点，则将是头节点，则将是头节点，则将headhead指向当前指向当前指向当前指向当前节点的下一个节点即可删除当前节点节点

47、的下一个节点即可删除当前节点节点的下一个节点即可删除当前节点节点的下一个节点即可删除当前节点 datanext(1)head=p-next(1)head=p-nexthead待删除节点待删除节点待删除节点待删除节点datanext p头节点头节点头节点头节点(2 2)free(p)free(p)2023/1/1654/60链表的删除操作链表的删除操作 若待删除节点不是头节点，则将前一节点的指若待删除节点不是头节点，则将前一节点的指若待删除节点不是头节点，则将前一节点的指若待删除节点不是头节点，则将前一节点的指针域指向当前节点的下一节点即可删除当前节针域指向当前节点的下一节点即可删除当前节针域指

48、向当前节点的下一节点即可删除当前节针域指向当前节点的下一节点即可删除当前节点点点点(1)pr-next=p-next(1)pr-next=p-nextdatanextdatanext待删除节点待删除节点待删除节点待删除节点datanext p中间节点中间节点中间节点中间节点datanext 若已搜索到表尾若已搜索到表尾若已搜索到表尾若已搜索到表尾（p-next=NULLp-next=NULL）仍未找仍未找仍未找仍未找到待删除节点，则显示到待删除节点，则显示到待删除节点，则显示到待删除节点，则显示“未找到未找到未找到未找到”(2 2)free(p)free(p)2023/1/1655/60链表的

49、插入操作链表的插入操作 若原链表为空表，则将新节点若原链表为空表，则将新节点若原链表为空表，则将新节点若原链表为空表，则将新节点p p作为头节点，作为头节点，作为头节点，作为头节点，让让让让headhead指向新节点指向新节点指向新节点指向新节点p p head待插入节点待插入节点待插入节点待插入节点data p(1)head(1)head=p=pp=(struct link*)malloc(sizeof(struct link);p=(struct link*)malloc(sizeof(struct link);p-next=NULL;p-next=NULL;p-data=nodeData

50、;p-data=nodeData;2023/1/1656/60链表的插入操作链表的插入操作 若原链表为非空，则按节点值（假设已按升序若原链表为非空，则按节点值（假设已按升序若原链表为非空，则按节点值（假设已按升序若原链表为非空，则按节点值（假设已按升序排序）的大小确定插入新节点的位置排序）的大小确定插入新节点的位置排序）的大小确定插入新节点的位置排序）的大小确定插入新节点的位置 若在头节点前插入新节点，则将新节点的指针若在头节点前插入新节点，则将新节点的指针若在头节点前插入新节点，则将新节点的指针若在头节点前插入新节点，则将新节点的指针域指向原链表的头节点域指向原链表的头节点域指向原链表的头节