第08讲结构.ppt

虞铭财mingcaiyu 程序设计基础 程序设计基础TheCProgrammingLanguage 结构 程序设计基础TheCProgrammingLanguage 例 求二维平面上两点间的距离 include includestructpoint doublex doubley intmain structpointp1 p2 doubledist scanf lf lf lf lf 例 对候选人得票的统计程序 设有3个候选人 每次输入一个得票的候选人的名字 要求最后输出各人得票结果 structperson charname 20 intcount candidate 3 Li 0 Zhang 0 Fun 0 include includestructperson charname 20 intcount candidate 3 Li 0 Zhang 0 Fun 0 intmain inti j charcandi name 20 for i 0 i 10 i scanf s candi name for j 0 j 3 j if strcmp candi name candidate j name 0 candidate j count printf n for i 0 i 3 i printf 5s d n candidate i name candidate i count 第08讲结构 结构是一个或多个变量的集合 这些变量可能是不同的类型 为了处理的方便而将这些变量组织在一个名字之下 由于结构将一组相关的变量看作一个单元而不是各自独立的实体 因此结构有助于组织复杂的数据 特别是在大型的程序中 一 结构的基本知识 点是最基本的对象 假设用x与y坐标表示它 可以采用结构存放这两个坐标 其声明如下 structpoint doublex doubley 例 关键字struct引入结构声明 结构声明由包含在花括号内的一系列声明组成 关键字struct后面的名字是可选的 称为结构标记 这里是point 结构标记用于为结构命名 代表花括号内的声明 可以用它作为该声明的简写形式 说明 结构中定义的变量称为成员 结构成员 结构标记和普通变量 即非成员 可以采用相同的名字 它们之间不会冲突 因为通过上下文分析总可以对它们进行区分 另外 不同结构中的成员可以使用相同的名字 但是 从编程风格方面来说 通常只有密切相关的对象才会使用相同的名字 说明 1 结构变量的定义 1 在声明结构类型的同时定义变量 struct声明定义了一种数据类型 在标志结构成员表结束的右花括号之后可以跟一个变量表 这与其它基本类型的变量声明是相同的 例如 structpoint x y z 从语法角度来说 这种方式的声明与声明intx y z 具有类似的意义 这两个声明都将x y与z声明为指定类型的变量 并且为它们分配存储空间 2 先声明结构类型再定义变量 如果结构声明的后面不带变量表 则不需要为它分配存储空间 它仅仅描述了一个结构的模板或轮廓 但是 如果结构声明中带有标记 那么在以后定义结构实例时便可以使用该标记定义 例如 对于上面给出的结构声明point 语句stuctpointp 定义了一个structpoint类型的变量p 2 结构变量的引用 在表达式中 可以通过下列形式引用某个特定结构中的成员 结构名 成员其中的结构成员运算符 将结构名与成员名连接起来 3 结构变量的初始化 结构的初始化可以在定义的后面使用初值表进行 初值表中同每个成员对应的初值必须是常量表达式 例如 structpointp1 20 100 自动结构也可以通过赋值初始化 还可以通过调用返回相应类型结构的函数进行初始化 4 对结构变量赋值 虽然C语言规定 结构变量之间一般不能直接赋值 但如果两个结构变量具有相同的类型 那么允许将一个结构变量的值直接赋给另一个结构变量 例如 structpoint doublex doubley p1 10 20 p2 p2 p1 p2 p1 等同于执行了下列语句 p2 x p1 x p2 y p1 y 提示 只有在同一个结构类型中的不同结构变量之间才可以直接赋值 如果两个结构类型不同 即使它们具有相同类型的成员 也不能相互赋值 除了两个相同类型结构变量之间能进行赋值外 一般情况下 对结构成员的操作主要通过成员来进行 而成员能实施的操作由成员本身的类型决定 结构之间不可以进行比较 5 结构的嵌套 可以用对角线上的两个点来定义矩形 相应的结构定义如下 structrect structpointp1 structpointp2 结构rect包含两个point类型的成员 如果按照下列方式声明screen变量 structrectscreen 则可以用语句screen p1 x引用screen的成员p1的x坐标 二 结构数组 在结构数组中 数组元素的类型是同一个结构类型 结构数组的定义方法与基本数据类型的数组定义方法类似 1 结构数组的定义 1 在声明结构类型的同时定义数组 structstudent intnum charname 20 charsex intage floatscore charaddr 30 stu 3 2 先声明结构类型再定义数组 structstudent intnum charname 20 charsex intage floatscore charaddr 30 structstudentstu 3 2 结构数组的初始化 对结构数组 可以按照结构成员初始化或者赋值的方法进行 只是赋值不是对单一的成员而是对数组进行 例如 structstudent intnum charname 20 charsex intage floatscore stu 10 99101 Li M 18 87 5 99102 ZhouFun M 21 99 99104 WangHai F 20 78 5 例 计算学生的总成绩 平均成绩和不及格的人数 structstu intnum char name charsex floatscore boy 5 1101 Liping M 45 1102 Zhangping M 100 1103 Hehe F 92 5 1104 Chenglin F 87 1105 Wanming M 58 includeintmain inti c 0 floatave s 0 for i 0 i 5 i s boy i score if boy i score 60 c 1 printf s 1f n s ave s 5 printf average 1f ncount d n ave c 注意 结构数组在初始化过程中 要注意初始化值与各个结构成员的数据类型的匹配 使用结构数组与使用其它数组一样 采用循环结构比较便利 三 结构指针 结构指针 结构指针类似于普通变量指针 声明structpoint p 将p定义为一个指向structpoint类型对象的指针 p即为该结构 而 p x和 p y则是结构成员 其中 p x中的圆括号是必需的 因为结构成员运算符 的优先级高 表达式 p x的含义等价于 p x 因为x不是指针 所以该表达式是非法的 结构指针 结构指针的使用频率非常高 为了使用方便 C语言提供了另一种简写方式 假定p是一个指向结构的指针 可以用p 结构成员这种形式引用相应的结构成员 运算符 和 都是左结合的 所以 对于下面的声明 structrectr rp 以下4个表达式是等价的 r pt1 x r pt1 xrp pt1 x rp pt1 x 例 对于下面变量定义 哪个表达式是不正确的 structnode intj k x p A p k 2B p k 2C x k 2D x k 2答案 D 例 对于结构声明struct intlen char str p p len将增加len的值 而不是增加p的值 p len将先执行p的加1操作 再对len执行操作 p len先对len执行操作 然后再将p加1 该表达式中的括号可以省略 p str读取的是指针str所指向的对象的值 p str 先读取指针str指向的对象的值 然后再将str加1 p str 将指针str指向的对象的值加1 p str先读取指针str指向的对象的值 然后再将p加1 includeintmain structpoint intx y a 4 1 2 3 3 5 10 12 8 structpoint p a printf d p x printf d p y printf d n a 3 x 例 写出下列程序的运行结果 例 有一个结构体变量stu 内含学生学号 姓名和3门课的成绩 要求在main函数中赋以值 在另一函数print中将它们打印输出 include defineFORMAT s n s n 1f n 1f n 1f n structstudent charnumber 20 charname 20 doublescore 3 stu 09110003201 LiLi 67 5 89 78 6 voidprint structstudent p printf FORMAT p number p name p score 0 p score 1 p score 2 intmain print 注意 千万不要认为结构的长度等于各成员长度的和 因为不同的对象有不同的对齐要求 所以 结构中可能会出现未命名的 空穴 hole 例如 假设char类型占用一个字节 int类型占用4个字节 则下列结构 struct charc inti 可能需要8个字节的存储空间 而不是5个字节 使用sizeof运算符可以返回正确的对象长度 注意 当函数的返回值类型比较复杂时 如结构指针 例如structkey binsearch char word structkey tab intn 很难看出函数名 也不太容易使用文本编辑器找到函数名 我们可以采用另一种格式书写上术语句 structkey binsearch char word structkey tab intn 具体采用哪种写法属于个人的习惯问题 可以选择自己喜欢的方式并始终保持自己的风格 四 结构与函数 结构的合法操作只有几种 作为一个整体复制和赋值 通过 运算符取地址 访问其成员 其中 复制和赋值包括向函数传递参数以及从函数返回值 至少可以通过3种可能的方法传递结构 一是分别传递各个结构成员 二是传递整个结构 三是传递指向结构的指针 这3种方法各有利弊 但如果传递给函数的结构很大 使用指针方式的效率通常比复制整个结构的效率要高 结构与函数 函数makepoint 它带有两个整型参数 并返回一个point类型的结构 makepoint函数 通过x y坐标构造一个点 structpointmakepoint intx inty structpointtemp temp x x temp y y returntemp 注意 参数名和结构成员同名不会引起冲突 事实上 使用重名可以强调两者之间的关系 结构与函数 addpoint函数 将两个点相加 structpointaddpoint structpointp1 structpointp2 p1 x p2 x p1 y p2 y returnp1 其中 函数的参数和返回值都是结构类型 之所以直接将相加所得的结果赋值给p1 而没有使用显式的临时变量存储 是为了强调结构类型的参数和其他类型的参数一样 都是通过值传递的 例 有5个学生 每个学生有3门课的成绩 从键盘输入数据 包括学号 姓名 性别 3门课的成绩 计算出平均成绩 并按平均成绩从高到低进行排序 第1步 声明结构 structstudent charnumber 20 charname 20 floatscore 3 floatave 第2步 输入数据 includevoidinput structstudentstu intn inti j floatsum for i 0 i n i scanf s s stu i number stu i name sum 0 for j 0 j 3 j scanf f 第3步 排序 voidselSort structstudent a intn inti j k structstudentt for i 0 i n 1 i k i for j i 1 j n j if a k ave a j ave k j if k i t a i a i a k a k t 第4步 写main函数进行测试 defineN5intmain inti j structstudentstu N input stu N selSort stu N for i 0 i N i printf n 11s 10s stu i number stu i name for j 0 j 3 j printf 8 2f stu i score j printf 8 2f stu i ave printf n 五 单向链表 链表是一种常见的重要数据结构 它是动态地进行存储分配的 在用数组存放数据时 需要事先定义固定好的数组 在数组元素个数不确定时 可能会发生浪费内存空间的情况 由于链表的各个部分可以不连续存放 长度可以不加限定 并根据需要动态地开辟内存空间 可比较自由方便地插入新元素 结点 故使用链表可以节省内存 并提高操作效率 链表分为单向链表和双向链表 在此 我们只介绍单向链表 单向链表 链表有一个 头指针 变量 图中以head表示 它指向链表的第一个元素 链表中每一元素称为 结点 每个结点都应包括两个部分 用户需要用的实际数据和下一个结点的地址 链表中的最后一个结点称为表尾 其下一个结点的地址值为NULL 表示为空地址 链表的各个结点在内存中可能是不连续存放的 具体存放位置由系统分配 说明 链表根据需要开辟内存单元 如果不提供 头指针 head 则整个链表都无法访问 1 处理动态链表所需的函数 链表是一种动态存储分配的数据结构 在进行动态存储分配的操作中 C语言提供了下面几个常用的函数 处理动态链表所需的函数 void malloc size tsize malloc函数为长度为size的对象分配内存 并返回指向分配区域的指针 若无法满足要求 则返回NULL 该函数不对分配的内存区域进行初始化 处理动态链表所需的函数 void calloc size tnobj size tsize calloc函数为nobj个长度为size的对象分配内存 并返回指向分配区域的指针 若无法满足要求 则返回NULL 该函数不对分配的内存区域进行初始化 处理动态链表所需的函数 void realloc void p size tsize realloc函数将p指向的对象的长度修改为size个字节 如果新分配的内存比原内存大 则原内存的内容保持不变 增加的空间不进行初始化 如果新分配的内存比原内存小 则新分配内存单元不被初始化 realloc函数返回指向新分配空间的指针 若无法满足要求 则返回NULL 在这种情况下 原指针p指向的单元内容保持不变 处理动态链表所需的函数 voidfree void p free函数释放p指向的内存空间 当p的值为NULL时 该函数不执行任何操作 p必须指向先前使用动态分配函数malloc realloc或calloc分配的空间 2 建立动态链表 所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表 即一个一个地开辟结点和输入各结点数据 并建立起前后相链的关系 例 写一函数建立一个有3名学生数据的单向动态链表 声明结构类型 structstudent intnum floatscore structstudent next 分析 设单向链表的表头指针为head 它总是指向第1个结点 尾指针为tail 它总是指向最后1个结点 它们的初始值为NULL 一旦链表中有新的结点加入 把它添加到表尾 即把原来链表的尾结点的next域指向该新增的结点 应该注意的是 建立链表的第1个结点时 整个链表是空的 由于每增加1个结点 要申请1个动态存储空间 以便存放相应的数据 故引入1个临时指针变量p 建立第1个结点 建立第2个结点 建立第3个结点 include include defineLENsizeof structstudent structstudent intnum floatscore structstudent next 建立链表的函数 structstudent creatLink void intnum floatscore structstudent head p tail head tail NULL printf Inputnum score n while scanf d f 3 输出动态链表 逐个输出链表每个结点的数据 voidprintLink structstudent head structstudent p printf nTheStudents srecordsare n if head NULL printf nNoRecords n else for p head p NULL p p next printf d 5 1f n p num p score 输出链表的函数 4 对链表的删除操作 例 写一函数以删除动态链表中符合要求的结点 分析 删除链表中所有符合要求的结点 但需要考虑被删除结点是否为表头 若被删除的结点为表头 则表头要后移 引入两个辅助指针p1 p2 p2始终指向当前准备删除的结点 而p1则总是指向p2的前一个结点 链表结点删除的原则是 先链接 后断开 要删的是第一个结点 要删的不是第一个结点 structstudent delLink structstudent head intnum structstudent p1 p2 while head 删除结点的函数 5 对链表的插入操作 例 链表中的学生记录是按学号由小到大顺序排列的 现要按顺序插入新的学生记录 编写一函数实现此功能 分析 要按顺序正确插入新的结点 首先要找到正确位置 然后插入新的结点 引入3个辅助指针p0 p1 p2 p0指向当前准备插入的结点 而p1则指向第i结点 p2指向第i 1结点 链表结点插入的原则是 先链接 后断开 第1种情况 插在表头 第2种情况 插在中间 第2种情况 插在中间 第2种情况 插在中间 第3种情况 插在表尾 插入结点的函数 structstudent insertLink structstudent head structstudent stud structstudent p0 p1 p2 p2 head p0 stud if head NULL 原链表为空时插入 head p0 p0 next NULL 插入结点的函数 else 原链表不为空时插入 while p0 num p2 num 6 对链表的综合操作 将以上建立 输出 删除 插入的函数组织在一个C程序中 用main函数作主调函数 intmain structstudent head stu intnum floatscore head creatLink printLink head printf nInputthedeletednumber while scanf d printf nInputtheinsertedrecord num score while scanf d f include include includestructlink charname 10 intmark structlink next voidinsert char int structlink head NULL 例 下列程序的功能是创建单向链表 intmain charname 10 intmark structlink t while 1 scanf s d name voidinsert char name intmark structlink p p 3 strcpy p name name p mark mark 4 if head NULL 5 head p 1 insert name mark 2 t NULL t t next 3 structlink malloc sizeof structlink 4 p next NULL 5 p next head include include defineLENsizeof structline defineNULL0structline intnum structline next 例 输入123450后 写出下列程序的运行结果 intmain structline p1 p2 head intj k 0 p1 p2 head structline malloc LEN scanf d p1 head next p1 p1 next for j 1 j d p1 num p1 p1 next 六 类型定义 typedef C语言提供了一个称为typedef的功能 它用来建立新的数据类型名 例如 声明typedefintLength 将Length定义为与int具有同等意义的名字 类型Length可用于类型声明 类型转换等 它和类型int完全相同 例如 Lengthlen maxlen Length lengths typedef定义类型步骤 按定义变量方法先写出定义体 如 inti 将变量名换成新类型名 如 intINTEGER 最前面加typedef 如 typedefintINTEGER 用新类型名定义变量 如 INTEGERi j inta 100 b 100 c 100 inta 100 intARRAY 100 typedefintARRAY 100 ARRAYa b c 例 定义数组类型 例 定义指针类型 char p char s 10 char str char STRING typedefchar STRING STRINGp s 10 例 定义函数指针类型 int p1 p2 int p int POWER typedefint POWER POWERp1 p2 structdate intmonth intday intyear birthday p structdate intmonth intday intyear d structdate intmonth intday intyear DATE typedefstructdate intmonth intday intyear DATE DATEbirthday p 例 定义结构类型 例typedefstructclub charname 20 intsize intyear GROUP typedefGROUP PG PGpclub GROUP为结构类型PG为指向GROUP的指针类型 GROUP pclub structclub pclub 类型定义可以嵌套 注意 typedef中声明的类型在变量名的位置出现 而不是紧接在关键字typedef之后 typedef在语法上类似于存储类extern static等 以大写字母作为typedef定义的类型名的首字母 以示区别 注意 从任何意义上讲 typedef声明并没有创建一种新类型 它只是为某个已存在的类型增加了一个新的名称而已 typedef声明也没有增加任何新的语义 通过这种方式声明的变量与通过普通声明方式声明的变量具有完全相同的属性 实际上 typedef类似于 define语句 但由于typedef是由编译器解释的 因此它的文本替换功能要超过预处理器的能力 注意 除了表达方式更简洁之外 使用typedef还有另外两个重要原因 首先 它可以使程序参数化 以提高程序的可移植性 如果typedef声明的数据类型同机器有关 那么 当程序移植到其他机器上时 只需改变typedef类型定义就可以了 typedef的第二个作用是为程序提供更好的说明性 七 联合 联合是可以 在不同时刻 保存不同类型和长度的对象的变量 编译器负责跟踪对象的长度和对齐要求 联合提供了一种方式 以在单块存储区中管理不同类型的数据 而不需要在程序中嵌入任何同机器有关的信息 联合的目的 一个变量可以合法地保存多种数据类型中任何一种类型的对象 联合 其语法基于结构 unionu tag intival floatfval char sval u 变量u必须足够大 以保存这3种类型中最长的一种 具体长度同具体的实现有关 联合 这些类型中的任何一种类型的对象都可赋值给u 且可使用在随后的表达式中 但必须保证是一致的 读取的类型必须是最后一次存入的类型 程序员负责跟踪当前保存在联合中的类型 如果保存的类型与读取的类型不一致 其结果取决于具体的实现 可以通过下列语法访问联合中的成员 联合名 成员或联合指针 成员它与访问结构的方式相同 联合 联合可以使用在结构和数组中 反之亦可 实际上 联合就是一个结构 它的所有成员相对于基地址的偏移量都为0 此结构空间要大到足够容纳最 宽 的成员 并且 其对齐方式要适合于联合中所有类型的成员 对联合允许的操作与对结构允许的操作相同 作为一个整体单元进行赋值 复制 取地址及访问其中一个成员 联合只能用其第一个成员类型的值进行初始化 例 设有若干个人员的数据 其中有学生和教师 学生的数据中包括 号码 姓名 性别 职业 班级 教师的数据包括 姓名 号码 性别 职业 职务 可以看出 学生和教师所包含的数据是不同的 现要求把它们放在同一表格中 对数据进行输入输出 分析 输入数据 读入号码 姓名 性别 职业 如果职业为学生 则读入班级 否则职业为教师 则读入职务 输出数据 输出号码 姓名 性别 职业 如果职业为学生 输出班级 否则职业为教师 则输出职务 struct intnum charname 20 charsex charjob union intbanji charposition 20 category person 5 includeintmain inti for i 0 i 5 i scanf d s c c printf No namesexjobbanji position n for i 0 i 5 i printf 4d 5s 4c 4c person i num person i name person i sex person i job if person i job s printf 6d n person i category banji elseprintf 6s n person i category position 八 枚举类型 枚举类型是ANSIC新标准所增加的 如果一个变量只有几种可能的值 则可以定义为枚举类型 所谓 枚举 是将变量的值一一列举出来 变量的值只限于列举出来的值的范围内 枚举类型是一种基本数据类型 而不是一种构造类型 因为它不能再分解为任何基本类型 1 枚举类型的声明 enum枚举名 枚举值表 在枚举值表中应罗列出所有可用值 这些值也称为枚举元素 例如 该枚举名为weekday 枚举值共有7个 即一周中的七天 凡被说明为weekday类型变量的取值只能是七天中的某一天 2 枚举变量的定义 设有变量a b c被说明为上述的weekday 可采用下述任一种方式 enumweekday sun mou tue wed thu fri sat enumweekdaya b c 或 enumweekday sun mou tue wed thu fri sat a b c 或 enum sun mou tue wed thu fri sat a b c 3 枚举变量的赋值和使用 枚举值是常量 不是变量 不能在程序中用赋值语句再对它赋值 例如对枚举weekday的元素再作以下赋值 sun 5 mon 2 sun mon 都是错误的 枚举元素本身由系统定义了一个表示序号的数值 从0开始顺序定义为0 1 2 如在weekday中 sun值为0 mon值为1 sat值为6 枚举变量的赋值和使用 枚举值可以用来作判断比较 一个整数不能直接赋给一个枚举变量 只能把枚举值赋予枚举变量 不能把元素的数值直接赋予枚举变量 如 a sum b mon 是正确的 而 a 0 b 1 是错误的 枚举变量的赋值和使用 如一定要把数值赋予枚举变量 则必须用强制类型转换 如 a enumweekday 2 其意义是将顺序号为2的枚举元素赋予枚举变量a 相当于 a tue 注意 枚举元素不是字符常量也不是字符串常量 使用时不要加单 双引号 例 口袋中有红 黄 蓝 白 黑5种颜色的球若干个 每次