C语言结构体2011.ppt

1 本章内容 结构体 结构structure 类型共用体 联合union 类型结构体变量 结构体数组 结构体指针向函数传递结构体用结构体指针实现动态数据结构链表的概念及操作原理 第9章结构体 2 从基本数据类型 复合数据类型到抽象数据类型 二进制数 类型本不存在内存里存的内容 你认为它是什么 它就是什么在早期的机器指令及汇编语言中 数据对象均用二进制数表示 没有类型的概念一般的CPU只支持两种类型整数 浮点数 3 从基本数据类型 复合数据类型到抽象数据类型 在高级语言引入了基本数据类型整型 浮点型 字符型等不同语言会定义不同的基本类型基本数据类型并不能方便地解决所有问题有些语言 如PL 1 中试图规定较多的类型 如数组 树 栈等 但实践证明不是个好办法 4 从基本数据类型 复合数据类型到抽象数据类型 用户自己构造数据类型 复合数据类型由基本数据类型迭代派生而来 表示复杂的数据对象典型的代表就是 结构体 数组和指针 5 抽象数据类型 AbstractDataType 简称ADT 在复合数据类型基础上增加了对数据的操作抽象数据类型进而进化为 类 Class 这是一个跨时代的进步Class是Object Oriented的一个重要概念 从基本数据类型 复合数据类型到抽象数据类型 6 思考一个问题 在程序里表示一个人 姓名 年龄 性别 怎么表示 想表示多个人呢 如何用计算机程序实现下述表格的管理 表9 1某学校学生成绩管理表 7 数组的解决方法 intstudentId 30 最多可以管理30个学生 每个学生的学号用数组的下标表示 charstudentName 30 10 charstudentGender 30 2 inttimeOfEnter 30 入学时间用int表示 intscoreComputer 30 计算机原理课的成绩 intscoreEnglish 30 英语课的成绩 intscoreMath 30 数学课的成绩 intscoreMusic 30 音乐课的成绩 8 intstudentId 30 1 2 3 4 5 6 charstudentName 30 10 令狐冲 林平之 岳灵珊 任莹莹 charstudentGender 30 2 男 男 女 女 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 数组的解决方法 9 数据的内存管理方式 数组的解决方法 10 数据的内存管理方式 数组的解决方法 分配内存不集中 寻址效率不高对数组进行赋初值时 容易发生错位结构显得比较零散 不容易管理 11 希望的内存分配图 12 结构体的解决方法 structSTUDENT intstudentID 每个学生的序号 charstudentName 10 每个学生的姓名 charstudentGender 4 每个学生的性别 inttimeOfEnter 每个学生的入学时间 intscoreComputer 每个学生的计算机原理成绩 intscoreEnglish 每个学生的英语成绩 intscoreMath 每个学生的数学成绩 intscoreMusic 每个学生的音乐成绩 structSTUDENT是一个类型structSTUDENTstudents 4 students 0 studentIDstudents 0 scoreComputer它们都是变量 一般称为结构的成员变量 13 用户自定义的数据类型 结构体 把关系紧密 且逻辑相关的多种不同类型的变量 组织到统一的名字之下占用相邻的一段内存单元共用体 把情形互斥 但逻辑相关的多种不同类型的变量 组织到统一的名字之下占用同一段内存单元 每一时刻只有一个数据起作用 14 形成一个样板用于生成结构体变量 struct结构体名 类型关键字成员名1 类型关键字成员名2 类型关键字成员名n 构成结构体的变量称结构体成员 member 也称域 filed 结构体类型的定义 structstudent intnum charname 20 charGender intage floatscore charaddr 30 15 structstudent intnum charname 20 charGender intage floatscore charaddr 30 struct结构体名 类型关键字成员名1 类型关键字成员名2 类型关键字成员名n 结构体类型的定义 只定义了数据的形式 即声明了一种复杂的数据类型 并未生成任何变量 16 先定义结构体类型再定义变量名 在定义类型的同时定义变量 直接定义结构体变量 不出现结构体名 structstudentstudent1 student2 structstudent intnum charname 20 charGender intage floatscore charaddr 30 student1 student2 struct intnum charname 20 charGender intage floatscore charaddr 30 student1 student2 结构体变量的定义 17 定义自己的类型名 structstudentstudent1 student2 Itworks studentstudent1 student2 Canthiswork typedefstructstudentSTUD STUDstudent1 student2 Itworks typedef为一种已存在的类型定义一个新名字 STUD与structstudent类型是同义词 structstudent intnum charname 20 charGender intage floatscore charaddr 30 18 struct类型的特点 是一个一个普通的类型可以定义该类型的变量 数组 指针 可以做函数的参数类型和返回值类型它的成员可以是任意类型基本类型 数组 指针 结构体 共用体 struct类型的变量两个结构体变量之间可以相互赋值所以做为函数的参数时 是传值调用可以取地址 不可直接参与算术和比较运算面向对象和数据库是struct思想的发展 19 结构体的内存占用 double占用内存字节数 8struct类型用内存字节数 是所有成员变量的内存总和吗 structnumber shorti charch floatf printf d n sizeof structnumber 用运算符sizeof获得结构体大小sizeof 变量或表达式 sizeof 类型 8 Why 20 结构体的内存占用 事实上所有数据类型在内存中都是从偶数地址开始存放的且结构所占的实际空间一般是按照机器字长对齐的不同的编译器 平台 对齐方式会有变化结构体变量的成员的存储对齐规则是与机器相关的具有特定数据类型的数据项的大小也是与机器相关的所以一个结构体在内存中的存储格式也是与机器相关的 非所有成员变量的内存总和 8个字节 21 structSTUDENT intstudentID charstudentName 10 charstudentGender 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENTstu 30 结构体数组 structdate intyear intmonth intday 结构体定义可以嵌套 22 structSTUDENTstu 30 1 令狐冲 男 1999 08 26 90 83 72 82 2 林平之 男 1999 08 26 78 92 88 78 3 岳灵珊 女 1999 08 26 89 72 98 66 4 任莹莹 女 1999 08 26 78 95 87 90 初始化 结构体数组 structSTUDENT intstudentID charstudentName 10 charstudentGender 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic 23 structSTUDENTstu 30 1 令狐冲 男 1999 08 26 90 83 72 82 2 林平之 男 1999 08 26 78 92 88 78 3 岳灵珊 女 1999 08 26 89 72 98 66 4 任莹莹 女 1999 08 26 78 95 87 90 初始化 建立了数据库中的多条记录 每条对应一个学生信息 24 结构体变量的指针 pStu stu structSTUDENT intstudentID charstudentName 10 charstudentGender 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENTstu 定义结构体变量 structSTUDENT pStu 定义结构体指针 pStu 25 pStu stu structSTUDENT intstudentID charstudentName 10 charstudentGender 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENTstu 定义结构体变量 structSTUDENT pStu 定义结构体指针 pStu 如何访问结构体的成员 通过stu和成员运算符访问结构体成员stu studentID 1 通过pStu和指向运算符访问结构体成员 pStu studentID 1 pStu studentID 1 26 structSTUDENT intstudentID charstudentName 10 charstudentGender 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENTstu 定义结构体变量 structSTUDENT pStu 定义结构体指针 pStu 如何访问嵌套的结构体的成员 stu timeOfEnter year 1999 pStu timeOfEnter year 1999 pStu timeOfEnter year 1999 structdate intyear intmonth intday 27 思考题 structpoint intx inty structrect structpointpt1 structpointpt2 structrectrt structrect rp 下面表达式哪些合法 rt pt1 x rp pt1 xrp pt1 xrt pt1 x上面合法的表达式都是等价的吗 28 structSTUDENTstu 4 1 令狐冲 男 1999 08 26 90 83 72 82 2 林平之 男 1999 08 26 78 92 88 78 3 岳灵珊 女 1999 08 26 89 72 98 66 4 任莹莹 女 1999 08 26 78 95 87 90 结构体数组的指针 pStu stu 4 structSTUDENT intstudentID charstudentName 10 charstudentGender 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENT pStu 定义结构体指针 pStu stu 相当于pStu 29 使用pStu i 使pStu指向stu i pStu studentID等价于stu i studentID 如何访问结构体数组元素的成员 pStu stu 4 structSTUDENT intstudentID charstudentName 10 charstudentGender 4 structdatetimeOfEnter intscoreComputer intscoreEnglish intscoreMath intscoreMusic structSTUDENT pStu 定义结构体指针 pStu stu 相当于pStu 30 向函数传递结构体 向函数传递结构体的单个成员复制单个成员的内容函数内对结构内容的修改不影响原结构向函数传递结构体的完整结构 向函数传递结构体的首地址 31 structdate intyear intmonth intday voidfunc structdatep p year 2000 p month 5 p day 22 intmain structdated d year 1999 d month 4 d day 23 printf d d d n d year d month d day func d printf d d d n d year d month d day return0 1999 4 23 1999 4 23 结构体变量做函数参数 32 structdate intyear intmonth intday voidfunc structdate p p year 2000 p month 5 p day 22 intmain structdated d year 1999 d month 4 d day 23 printf d d d n d year d month d day func 1999 4 23 2000 5 22 结构体指针做函数参数 指针做函数形参实参必须为地址值 33 structdate intyear intmonth intday structdatefunc structdatep p year 2000 p month 5 p day 22 intmain structdated d year 1999 d month 4 d day 23 printf d d d n d year d month d day d func d printf d d d n d year d month d day return0 结构体变量做函数返回值 存在一个错误 34 structdate intyear intmonth intday structdatefunc structdatep p year 2000 p month 5 p day 22 returnp intmain structdated d year 1999 d month 4 d day 23 printf d d d n d year d month d day d func d printf d d d n d year d month d day return0 1999 4 23 2000 5 22 结构体变量做函数返回值 35 向函数传递结构体 向函数传递结构体的完整结构复制整个结构体成员的内容 多个值函数内对结构内容的修改不影响原结构内容传递更直观 但开销大向函数传递结构体的首地址用结构体数组 结构体指针做函数参数仅复制结构体的首地址 一个值修改结构体指针所指向的结构体的内容指针传递效率高 36 实例9 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 牌面 char suit Spades Hearts Clubs Diamonds char face A 2 3 4 5 6 7 8 9 10 jack Queen King 37 实例9 1 洗牌和发牌模拟 structCARD charsuit 10 花色 charface 10 牌面 structCARDcard 52 依次存放扑克牌的花色和牌面 如何表示第1张牌的花色和牌面 card 0 suitcard 0 face 未洗牌情况下 第1张牌花色Spades 牌面A 洗牌后 第1张牌不一定为Spades和A 38 实例9 1 洗牌和发牌模拟 structCARD charsuit 10 花色 charface 10 牌面 structCARDcard 52 依次存放扑克牌的花色和牌面 如何顺序输出一副新扑克牌 花色和牌面未打乱 呢 39 实例9 1 洗牌和发牌模拟 如何用函数实现 40 实例9 1 洗牌和发牌模拟 函数功能 将52张牌按黑桃 红桃 草花 方块花色顺序 面值按A K顺序排列函数参数 结构体数组wCard 表示不同花色和面值的52张牌指针数组wFace 指向面值字符串指针数组wSuit 指向花色字符串函数返回值 无 voidFillCard structCARDwCard char wSuit char wFace inti for i 0 i 52 i strcpy wCard i suit wSuit i 13 strcpy wCard i face wFace i 13 41 函数功能 输出发牌结果函数参数 结构体数组wCard 表示有52张牌函数返回值 无 voidDeal structCARD wCard inti for i 0 i 52 i printf 10s 5s n wCard i suit wCard i face 实例9 1 洗牌和发牌模拟 42 实例9 1 洗牌和发牌模拟 洗发牌过程将52张牌按照随机的顺序存放算法步骤 产生0 51的随机数 将其放于result i 内i i 1如果i 51 则重复第1步 否则 结束循环输出结果存在一个致命的问题 在重复第1步时 产生的随机数可能与以前产生的随机数相同 相同意味着52张牌中出现2张以上相同的牌 43 实例9 1 洗牌和发牌模拟 解决方法增加一步 判断新产生的随机数以前是否出现过如果出现过 则放弃 如果以前未出现过 则保留算法步骤 产生0 51的随机数m 将其放于result i 内判断result i 在以前 result 0 result i 1 是否出现过如果出现过 则回到第1步如果没出现过 则i i 1如果i 51 则重复第1 2步 否则 结束循环输出结果 44 实例9 1 洗牌和发牌模拟 算法缺陷 随着生成随机数数量的增加 新的随机数与已经产生的随机数相同的可能性越来越大 有可能出现算法延迟问题高效算法先将52张牌按照花色与牌面顺序存放 card i 再将其随机打乱每次循环 程序选择一个0 51的随机数j 然后将数组中当前的元素card i 与随机选出的元素card j 进行交换 45 函数功能 将52张牌的顺序打乱 函数参数 结构体数组wCard 表示52张牌函数返回值 无 voidShuffle structCARD wCard inti j structCARDtemp for i 0 i 52 i j rand 52 temp wCard i wCard i wCard j wCard j temp 实例9 1 洗牌和发牌模拟 内容回顾 结构类型定义 将相关的不同类型数据组织在一起统一管理struct结构体名 类型关键字成员名1 类型关键字成员名2 类型关键字成员名n 结构变量定义可以与定义类型一起进行structstudentstudent1 student2 46 47 数组 线性表的顺序表示方式 A B C D E 0 1 2 3 4 元素 序号 A B C 0 1 2 3 4 元素 下标 5 优点 便于快速 随机存取线性表中任一元素 缺点 插入和删除操作需要移动大量元素 X A B 0 1 2 3 4 元素 下标 48 数组 线性表的顺序表示方式 A B C D E 0 1 2 3 4 元素 序号 缺点 属于静态内存分配 程序一旦运行长度不能改变 若想改变 只能修改程序 一旦确定 会带来两个问题 1 不能超过数组元素最大长度的限制 否则溢出 2 数组元素低于所设定的最大长度 将造成系统资源的浪费 49 思考 能否有一个办法 保证系统资源的最合理运用 当我们需要添加一个元素时 程序会自动添加 当我们需要减少一个元素时 程序会自动放弃该元素原来占有的内存 动态数据结构结构体动态内存分配 50 思考 下面的结构是什么意思 structtemp intdata structtemppt VC下的错误提示 pt uses temp whichisbeingdefined下面的结构是什么意思呢 structtemp intdata structtemp pt 可包含指向本结构体类型的指针变量 51 链表的定义 structLink intdata structLink next 链表 Linkedtable 线性表的链式存储结构特点 用一组任意的存储单元存储线性表的数据 存储单元可以是连续的 也可是不连续的 52 链表的定义 structLink intdata structLink next 链表 Linkedtable 线性表的链式存储结构为表示每个元素与后继元素的逻辑关系 除存储元素本身信息外 还要存储其直接后继信息 两部分信息组成一个结点 53 链表的定义 structLink intdata structLink next 链表 Linkedtable 线性表的链式存储结构为表示每个元素与后继元素的逻辑关系 除存储元素本身信息外 还要存储其直接后继信息 数据域 存储数据元素信息 指针域 存储直接后继的节点信息 54 链表的定义 structLink intdata structLink next 链表 Linkedtable 线性表的链式存储结构n个节点链接成一个链表 因为只包含一个指针域 故又称线性链表或单向链表 数据域 存储数据元素信息 指针域 存储直接后继的节点信息 55 链表的典型实现 C语言代码 空指针NULL表示链表结尾 structLink intdata structLink next 链表的头指针 便于操作 56 链表的插入操作 在x后插入新节点t malloc sizeof structNode t next x next x next t B x A 57 链表的删除操作 删除节点x nextt x next x next t next free t B C x A 58 引入链表后 用户就可以根据需要在程序的运行过程中动态分配存储空间 动态存储分配需要利用以下C语言库函数 1 函数malloc 函数功能 函数原型 void malloc unsignedintsize 在内存的动态存储区中分配一个长度为size的连续存储空间 其中 形参size为无符号整数 是函数malloc要求分配存储空间的字节个数 函数返回值为一个指针 它指向所分配存储空间的起始地址 若函数返回值为0 则表示未能成功申请到内存空间 函数类型为void 表示返回的指针不指向任何具体的类型 10 6链表 59 int p int lp p int malloc 8 lp int malloc 12 head structstudent malloc sizeof structstudent 例如 malloc 8 通过函数malloc向系统申请8个字节的内存空间 其起始地址通过函数值返回 若要求用一个指针变量 具有某种类型 指向这个起始地址 则需要显式进行类型转换 例如 10 6链表 60 2 函数calloc函数原型 void calloc unsignedintn unsignedintsize 函数功能 在内存的动态存储区域中分配n个长度为size的连续存储空间 函数的返回值为分配域的起始地址 如果分配不成功 则返回值为0 例如 int p p int calloc 3 8 分配3个8字节的的连续存储空间 并将其起始地址赋给整型指针p 10 6链表 61 3 函数free 函数原型 voidfree void ptr 函数功能 释放由指针变量ptr为所指示的内存区域 其中 ptr一个指针变量 指向最近一次调用函数malloc或calloc时所分配的连续存储空间的首地址 通过函数free将已分配的内存区域交还系统 使系统可以重新对其进行分配 例如 int p p long malloc 8 free p 10 6链表 62 链表的定义 structLink intdata structLink next 链表 Linkedtable 线性表的链式存储结构n个节点链接成一个链表 因为只包含一个指针域 故又称线性链表或单向链表 数据域 存储数据元素信息 指针域 存储直接后继的节点信息 63 建立链表 1 建立链表就是指从无到有地建立起一个链表 即一个个地输入各结点数据 并建立起前后相链的关系 例9 2 编写一个建立单向链表的函数 存放学生数据 函数create可编写如下 include stdio h include stdlib h defineNULL0 令NULL为0 用它表示空地址 defineLENsizeof structstu LEN代表structstu结构体类型数据的长度 structstu intnum floatscore structstu next 64 建立链表 2上接1 intn structstu creat 此函数带回一个指向链表头的指针 structstu head p1 p2 n 0 n为结点的个数 p1 p2 structstu malloc LEN 开辟一个新单元 scanf d f 65 建立链表 3上接2 p2 p1 p1 structstu malloc LEN scanf d f 下图表示出creat函数的执行过程 66 67 68 69 70 71 72 73 74 75 链表的输出 将链表中各结点的数据依次输出 首先要知道链表头元素的地址 设一个指针变量p 指向第一个结点 待输出p所指的结点数据后 使p后移一个结点再输出 直至链表的尾结点止 程序执行过程可见下图所示 例9 3 写一个函数 输出链表中所有结点 voidprint structstu head 由实参即将已有的链表的头指针传给被调函数 structstu p printf nNow these drecordsare n n p head p指向头结点 while p NULL printf d 2f n p num p score 输出所指结点的数据域 p p next 使p指向下一个结点 76 77 链表的删除操作 从一个链表中删除一个结点 并不是真正从内存中把它抹去 而是把它从链表中分离开来 可以通过改变链表的链接关系完成 分析 设两个指针变量p1和p2 先使p1指向第一个结点 删除一个结点有两种情况 一种情况是要删除结点是第一个结点 此时只需使head指向第二个结点即可 即head p1 next 其过程如下图所示 另一种情况是被删除结点不是第一个结点 可使被删除结点的前一结点指向被删结点的后一结点 即p2 next p1 next 其过程如后图所示 例9 4 写一个函数 删除链表中的指定结点 以指定的学号作为删除结点的标志 函数dele编写如下 structstu dele structstu head intnum structstu p1 p2 78 链表的删除操作 if head NULL 如为空表 输出提示信息 printf nemptylist n returnNULL p1 head while p1 num num 不是第一个结点 使要删除结点从链表中脱离 79 链表的删除操作 n n 1 free p1 elseprintf Thenodenotbeenfoud n returnhead 返回head值 80 81 82 83 84 链表的插入操作 在一个链表的指定位置插入结点 首先要求链表本身必须是已按某种规律排好序的 按照排序的规律确定好新结点在链表中的位置 并将其连入链表中即可 分析 设被插入结点的指针为p0 p1指向第一个结点 可在四种不同情况下插入 第一种情况是原链表是空链表 只需使head指向被插入结点即可 见下图a 第二种情况是被插入结点值最小 则应插入到第一个结点之前 这种情况下使head指向被插入结点 被插入结点的指针域指向原来的第一个结点即可 即用p0 next p1 head p0 完成 见图 b 第三种情况是在其它位置插入 见图 c 这种情况下 使插入位置的前一结点的指针域指向被插入结点 使被插入结点的指针域指向插入位置的后一结点 即用p0 next p1 p2 next p0 来完成 85 链表的插入操作 最后一种情况是在表末插入 见图 d 这种情况下使原链表中的末结点指针域指向被插入结点 被插入结点指针域置为NULL 即用p1 next p0p0 next NULL 来完成 例9 5 写一个函数 在学生数据链表中 按学号顺序插入一个结点 structstu insert structstu head structstu stud structstu p0 p1 p2 p1 head 指向第一个结点 p0 stud 指向要插入的结点 if head NULL 空表插入 head p0 p0 next NULL 将p0指向的结点作第一个结点 86 链表的插入操作 else while p0 num p1 num 87 链表的插入操作 else p1 next p0 p0 next NULL 在表末插入 n n 1 return head 88 图 a 89 图 b 90 图 c 91 图 d 92 例9 6 例9 6 将以上建立链表 输出链表 删除结点 插入结点的函数组织在一个程序中 用main函数作主调函数 程序名为linkdemo cpp main函数内容如下 其位置在以上各函数之后 include stdio h intmain structstu head stud intnum printf inputrecords n head creat 调用creat函数建立链表并把头指针返回给head print head 调用print函数输出链表 printf Inputthedeletednumber scanf d 调用dele函数删除一个结点 93 例9 6 print head 调用print函数输出链表 printf Inputtheinsertednumberandscore scanf d f 运行情况如下 inputrecords 输入 96001859600275 2960056200 94 例9 6 Now these3recordsare 9600185 009600275 209600562 00Inputthedeletednumber 输入 96002Now these2recordsare 9600185 009600562 00Inputtheinsertnumberandscore 输入 960