第七章 结构体与共用体

本章内容 结构体 结构structure 共用体 联合union 类型的定义结构体变量 结构体数组结构体变量 结构体数组与指针 函数的关系用结构体实现动态数据结构链表的概念及操作原理 从基本数据类型到抽象数据类型 二进制数在早期的机器指令及汇编语言中 数据对象均用二进制数表示 没有类型的概念 基本数据类型在高级语言中引入了基本数据类型 整型 实型 字符型等基本数据类型不能方便的解决所有问题 有些语言 如PL 1 中试图规定较多的类型 如数组 树 栈等 但实践证明不是个好办法 用户自己构造数据类型 复合数据类型表示复杂的数据对象 典型的代表就是 结构体 数组 指针也可算作此类 抽象数据类型 AbstractDataType 简称ADT 在复合数据类型基础上增加了对数据的操作类 跨时代的进步例如汽车就是一种ADT 思考一个问题 在程序里表示一个人 姓名 年龄 性别 怎么表示 想表示多个人呢 如何用计算机程序实现下述表格的管理 表8 1某学校学生成绩管理表 数组的解决方法 intstudentId 30 最多可以管理30个学生 每个学生的学号用数组的下标表示 charstudentName 10 30 charstudentSex 2 30 inttimeOfEnter 30 入学时间用int表示 intscoreComputer 30 计算机原理课的成绩 intscoreEnglish 30 英语课的成绩 intscoreMath 30 数学课的成绩 intscoreMusic 30 音乐课的成绩 数组的解决方法 intstudentId 30 1 2 3 4 5 6 charstudentName 10 30 令狐冲 林平之 岳灵珊 任莹莹 charstudentSex 2 30 男 男 女 女 inttimeOfEnter 30 1999 1999 1999 1999 intscoreComputer 30 90 78 89 78 intscoreEnglish 30 83 92 72 95 intscoreMath 30 72 88 98 87 intscoreMusic 30 82 78 66 90 数组的解决方法 数据的内存管理方式 数组的解决方法 分配内存不集中 寻址效率不高对数组进行赋初值时 容易发生错位结构显得比较零散 不容易管理 希望的内存分配图 结构体的解决方法 structSTUDENT intstudentID 每个学生的序号 charstudentName 10 每个学生的姓名 charstudentSex 4 每个学生的性别 inttimeOfEnter 每个学生的入学时间 intscoreComputer 每个学生的计算机原理成绩 intscoreEnglish 每个学生的英语成绩 intscoreMath 每个学生的数学成绩 intscoreMusic 每个学生的音乐成绩 structSTUDENT是一个类型structSTUDENTstudents 4 students 0 studentNamestudents 0 Sex它们都是变量 一般称为结构的成员变量 用户自定义的数据类型 结构体 把关系紧密且逻辑相关的多种不同类型的变量组织到统一的名字之下 也称复合数据类型这种类型的变量占用相邻的一段内存单元共用体 把情形互斥但又逻辑相关的多种不同类型的变量组织在一起这种类型的变量占用同一段内存单元 因此每一时刻只有一个数据起作用 structstudent intnum charname 20 charsex intage floatscore charaddr 30 structuredefinition形成一个样板 用于生成结构体变量 一般形式 struct结构体名 类型关键字成员名1 类型关键字成员名2 类型关键字成员名n 构成结构体的变量称为结构体的成员 member 也称元素 element 或域 filed 结构体的定义只定义了数据的形式 即声明了一种复杂的数据类型 并未生成任何变量 结构体的定义 先定义结构体类型再定义变量名 在定义类型的同时定义变量 直接定义结构体变量 不出现结构体名 structstudentstudent1 student2 structstudent intnum charname 20 charsex intage floatscore charaddr 30 student1 student2 struct intnum charname 20 charsex intage floatscore charaddr 30 student1 student2 结构体变量的定义 结构体变量的定义 用typedef为已存在的类型定义新名字structstudent intnum charname 20 charsex intage floatscore charaddr 30 typedefstructstudentSTUD STUDstudent1 student2 用STUD代替structstudent类型 结构体定义可以嵌套 structdate intmonth intday intyear typedefstructdateDATE structstudent intnum charname 20 charsex intage DATEbirthday charaddr 30 student1 student2 structstudent占用内存字节数 double占用内存字节数 8 结构体变量的定义 结构 Structure 的内存占用 一个结构变量的成员变量在内存中是相邻的整个结构变量的将占用多少内存呢 是所有成员变量的内存总和吗 事实上 所有数据类型在内存中都是从偶数地址开始存放的 且结构所占的实际空间一般是按照机器字长对齐的不同的编译器 不同的平台 对齐方式会有变化 不过一般的编译器都可以设定按照多大对齐我们可以用sizeof来获得结构的大小 结构体指针 structpoint intx inty structpointpt 定义结构体变量 structpoint ppt 定义结构体指针 ppt 指向运算符 第二种更常用 定义 structSTUDENT intstudentID charstudentName 10 charstudentSex 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENTstu 30 结构体数组 structSTUDENT intstudentID charstudentName 10 charstudentSex 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENTstu 30 1 令狐冲 男 1999 12 20 90 83 72 82 2 林平之 男 1999 07 06 78 92 88 78 3 岳灵珊 女 1999 07 06 89 72 98 66 4 任莹莹 女 1999 07 06 78 95 87 90 初始化 结构体数组 例8 1 洗牌和发牌模拟 一付扑克有52张牌 分为4种花色 Suit 黑桃 Spades 红桃 Hearts 草花 Clubs 方块 Diamonds 每种花色有13张牌面 Face A 2 3 4 5 6 7 8 9 10 Jack Queen King设计一个结构体表示一张牌 由两个成分组成 花色 牌面 structCARD charsuit 10 charface 10 structCARDcard 52 顺序存放扑克牌 intresult 52 存放洗牌发牌结果 char suit Spades Hearts Clubs Diamonds char face A 2 3 4 5 6 7 8 9 10 jack Queen King 例8 1 洗牌和发牌模拟 发牌过程将52张牌按照随机的顺序存放算法步骤 产生0 51的随机数 将其放于result i 内 i i 1如果i 51 则重复第2步 否则 结束循环输出结果存在一个致命的问题 在重复第2步时 产生的随机数可能与以前产生的随机数相同 相同意味着52张牌中出现2张以上相同的牌 例8 1 洗牌和发牌模拟 解决方法增加一步 判断新产生的随机数以前是否出现过如果出现过 则放弃 如果以前未出现过 则保留算法步骤 产生0 51的随机数m 将其放于result i 内 判断result i 在以前 result 0 result i 1 是否出现过 如果出现过 则回到第2步 如果没出现过 则i i 1如果i 51 则重复第2 3步 否则 结束循环输出结果 例8 1 洗牌和发牌模拟 算法缺陷 随着随机数数量的增加 新的随机数与已经产生的随机数相同的可能性越来越大 有可能出现算法延迟问题高效算法将按照花色与牌面的顺序存放的牌 card i 随机打乱每次循环 程序选择一个0 51的随机数j 然后将数组中当前的CARD结构card i 与随机选出的j所在的数组元素card j 结构进行交换 主函数以外 include include include includeStructCARD charsuit 10 charface 10 main char suit Spades Hearts Clubs Diamonds char face A 2 3 4 5 6 7 8 9 10 jack Queen King inti j intresult 52 0 structCARDcard 52 for i 0 i 52 i result i 1 for i 0 i 52 i strcpy card i suit suit i 13 strcpy card i face face 1 13 srand time NULL i 0 While 1 result i rand 52 for j 0 j 51 break for i 0 i 52 i printf 10s 5s n card result suit card result i face 高效算法 include include include includeStructCARD charsuit 10 charface 10 main char suit Spades Hearts Clubs Diamonds char face A 2 3 4 5 6 7 8 9 10 jack Queen King inti j structCARDcard 52 temp for i 0 i 52 i result i 1 for i 0 i 52 i strcpy card i suit suit i 13 strcpy card i face face 1 13 srand time NULL for j 0 j 52 j j rand 52 temp card i card i card j card j temp for i 0 i 52 i printf 10s 5s n card result suit card result i face 结构体数组的指针 structSTUDENT pt pt stu stu 0 stu 1 stu 2 pt pt stu 3 for pt stu ptscoreComputer sum 1 sum 1 pt scoreEnglish sum 2 sum 2 pt scoreMath sum 3 sum 3 pt scoreMusic for i 0 i 4 i average i sum i 4 printf 20s 4 2f n name i average i 例8 2 利用指向结构体数组的指针计算学生各科的平均成绩 例8 2 main structSTUDENT pt floatsum 4 0 0 average 4 0 0 inti char name scoreofComputer scoreofEnglish scoreofMath scoreofMusic pt stu pt指向结构体数组的第一个元素 for pt stu ptscoreComputer sum 1 sum 1 pt scoreEnglish sum 2 sum 2 pt scoreMath sum 3 sum 3 pt scoreMusic for i 0 i 4 i average i sum i 4 printf 20s 4 2f n name i average i 例8 1 洗牌和发牌模拟 P329 用结构体数组做函数参数 函数功能 将52张牌按黑桃 红桃 草花 方块花色顺序 面值按A K的顺序排列函数参数 结构体数组wCard 表示不同花色和面值的52张牌指针变量wFace 表示指向面值字符串数组face 的指针指针变量wSuit 表示指向花色字符串数组suit 的指针函数返回值 无 voidFillCard structCARDwCard char wFace char wSuit inti for i 0 i 52 i strcpy wCard i suit wSuit i 13 strcpy wCard i face wFace i 13 用结构体指针做函数参数 函数功能 将52张牌的顺序打乱 函数参数 结构体数组变量wCard 表示52张牌函数返回值 无 voidShuffle structCARD wCard inti j structcardtemp for i 0 i 52 i j rand 52 j random 52 TC的库函数 temp wCard i wCard i wCard j wCard j temp 洗牌过程 例8 1 洗牌和发牌模拟 P323 用结构体指针做函数参数 函数功能 输出发牌结果函数参数 结构体数组变量wCard 表示有52张牌函数返回值 无 voidDeal structCARD wCard inti for i 0 i 52 i 输出发牌结果 printf 10s 10s n wCard i suit wCard i face 例8 1 洗牌和发牌模拟 P313 结构体与函数 向函数传递结构体的单个成员单向值传递 函数内对结构内容的修改不影响原结构向函数传递结构体的完整结构单向值传递 函数内对结构内容的修改不影响原结构 开销大向函数传递结构体的首地址用结构体数组或者结构体指针做函数参数除提高效率外 还可以修改结构体指针所指向的结构体的内容 思考 下面的结构什么意思 structtemp intdata structtemppt TC下的错误提示 Undefinedstructure temp StructuresizetoolargeVC下的错误提示 pt usesundefinedstruct temp 下面的的呢 structtemp intdata structtemp pt 动态数据结构 结构体声明时不能包含自我 但可以包含指向本结构体类型的指针变量链表 Linkedtable structLink intdata structLink next 优点 可以在任意位置很方便地插入和删除节点 缺点 1 不能实现快速查找 如折半查找 2 容易出现断裂 2020 4 16 40 动态链表生成步骤 1 建立一个结构体 注 体内一定有一个指向自身指针域 2 定义三个该结构类型的指针变量 指针变量head 存储链的头地址 指针变量p 存储当前结点地址 指针变量pr 存储链尾结点地址 3 利用函数申请一个存储该结构的空间 第一次申请 首地址分别存入head p pr 后续申请 首地址送p p的值送pr的指针域 最后一次操作 链尾结点的指针域存空值 反复多次 head p pr 1 若原链表为空 则将新节点置为首节点 p head 2 若原链表不为空 则将新节点填到表尾 head pr next p pr pr next 动态建立链表 1 链表结构structLink intdata structLink next include includeStructLink AppendNode structLink head VoidDispLink structLink head VoidDeleteMemory structLink head structLink intdata structLink next main inti charc structLink head NULL printf Doyouwanttoappendanewnode Y N scanf c structLink AppendNode structLink head structLink p NULL structLink pr head intdata p structLink malloc sizeof structLink if p NULL printf Noenoughmemorytoalloc exit 0 if head NULL head p else while pr next NULL pr pr next pr next p 将新建节点添加在文件尾 pr p printf Inputnotedate scanf d voidDispLink structLink head structLink p head intj 1 while p NULL printf 5d 10d n j p data p p next j j voidDeleteMemory structLink head structLink p head pr NULL while p NULL pr p p p next free pr 链表的删除操作 head p 待删节点不是首节点的节点删除过程 pr p 由pr next p next完成 structlink DelNode structLink head intnodedata structlink p head pr head if head NULL printf NoLinktable n return head while nodeData p data 链表的插入操作 structlink InsertNode structLink head intnodedata structlink p head pr head temp NULL p structLink malloc sizeof structLink if p NULL printf Noenoughmemorytoalloc exit 0 p next NULL 置新节点的指针域为空 p data nodedata 为新节点数据域赋值nodedata if head NULL head p else 若未找到待插入的节点位置继续找 while pr datanext NULL temp pr pr pr next if pr data notedata if pr head 在首节点前插入新节点 p next head head p else 在链表中插入新节点 pr temp p next pr next pr next p else pr next p 在表尾插入新节点 returnhead 位字段 想表达人的姓名 出生年 月 日 都定义什么类型的成员变量 st