C程序设计：结构类型和链表.ppt

1 第7章结构和链表 7 1结构类型和结构变量7 2结构数组7 3结构与函数7 4链表7 5联合 7 6位域7 7枚举7 8类型定义7 9变量定义 2 基本类型 如整型 实型 字符型等 构造类型 数组 每个元素都是属于同一个类型 结构类型 不同的数据类型组成一个整体方便引用 例如 一个学生数据实体可能有以下多项信息学号 姓名 性别 年龄 成绩 家庭地址intcharcharintfloatchar说明 这类实体的数据因所包含的成员类型不同 不能用单个数组来表示 也不便将它们的成员分拆成多个独立的简单变量 因为这样会失去实体的整体性 7 1结构类型和结构变量 3 结构类型形式 struct结构类型名 成员说明表 其中关键字 struct 引出结构类型的定义 结构类型名 结构类型的标记 用来定义引用该结构的结构变量 成员说明表 指明该结构类型的各成员的数据类型和名称 每个成员的说明形式为 类型成员名 1 结构类型 4 例 学生基本信息的结构类型 structstudent intnumber 学号 charname 20 姓名 设姓名少于20个字符 charsex 性别 charaddress 40 家庭地址 说明 在C 中 如果不会引起混淆 例如 结构类型与结构变量同名 引用结构类型可以不用struct引导 结构类型例 5 当结构类型中的某个成员又是另一个结构类型时 这种结构类型是一种嵌套的结构类型 例如 给上述学生信息增加出生日期 并将出生日期定义为一种包含日 月 年3项信息的结构类型 则更完整的学生信息类型就被定义成嵌套的结构类型 嵌套的结构类型 6 structDate 说明一个日期 intday 日 intmonth 月 intyear 年 structstudent intnumber 学号 charname 20 姓名 charsex 性别 Datebirthday 采用C 句法 birthday的类型是结构类型Date 如果采用C句法 则在Date之前用struct引导 charaddress 40 家庭地址 嵌套的结构类型例 7 在结构类型定义中 详细列出了结构类型所包含的每个成员的名称及其类型 实际上 结构类型定义只是表明一类实体其数据属性的 模式 并不定义一个特定的数据实体 因此不要求分配存储单元 程序如果要实际使用结构类型所描述的数据信息 就必须定义结构变量 结构变量要占用存储单元 能存放如结构类型所描述的具体数据 对结构类型和结构变量 我们可以简单地理解为 结构类型是表示数据框架的描述文本 结构变量才能存放实际数据 2 结构变量 8 一 先定义结构类型 再声明结构变量形式 struct结构类型名结构变量名表 C句法 结构类型名结构变量名表 C 句法例如 利用前面已定义的结构类型student声明结构变量代码 structstudentst1 st2 C句法 studentst1 st2 C 句法其中 student为结构类型名 st1和st2为结构变量 说明 结构变量声明后 每个结构变量的成员名称 成员个数和各成员的数据类型与结构类型定义中的成员名称 成员个数和各成员的数据类型相一致 结构变量的定义 9 结构变量内存分配单元 10 二 在定义结构类型的同时声明结构变量 一般形式 struct结构类型名 成员说明表 结构变量表 结构变量的定义 例如 structstuSType intnumber 学号 charname 20 姓名 intscore 成绩 stuS 11 在定义结构变量的同时给它赋初值 称为结构变量的初始化 结构变量初始化时 要按结构类型定义中成员的顺序逐一给出各成员的初值 例如 structpoint 说明绘图程序的坐标类型 intx inty p1 20 50 p2 p1的x值为20 p1的y值为50 说明 也可以在定义结构类型与声明结构变量分开的情况下 在声明结构变量时进行初始化 例如 structpointp3 10 40 p4 20 50 结构变量初始化 12 要注意结构类型名和结构变量名的区别 不能对结构类型名进行赋值 存取或运算 因为类型不占用存储空间 而结构变量会占用存储空间 定义时可以赋初值 定义后可引用 结构变量初始化的时间 静态的和全局的结构变量初始化在程序执行之前完成 静态的结构变量未指定初值时 值自动置0 局部结构变量初始化是程序控制每次进入它所属辖域时创建并初始化 未指定初值的局部结构变量其初值是不确定的 结构变量初始化说明 13 可以定义指向结构的指针变量 结构指针变量简称结构指针 例如 structDate pd date3 定义变量 pd pd指向date3 表示 定义结构指针pd和结构变量date3 并使结构指针pd指向结构变量date3 即结构指针pd的内容为结构变量date3所占据的存储块的首地址 结构变量初始化说明 14 一 引用结构变量1 用结构变量名直接引用结构变量例如 structstudent intnumber 学号 charname 20 姓名 floatscore 成绩 st1 10001 Zhangping 85 0 st2 st2 st1 将结构变量st1作为整体赋值给结构变量st2 说明 两个结构变量必须是同类型的 3 结构变量的引用 15 2 指向结构变量的指针间接引用结构变量例如 structstudent intnumber 学号 charname 20 姓名 floatscore 成绩 st1 10001 Zhangping 85 0 st2 student p1 定义结构指针变量p1 并指向结构变量st1的首地址 3 结构变量的引用 16 二 引用结构成员1 使用结构变量和成员运算符引用方法 结构变量名 成员名其中 点符号 是结构的成员运算符 是优先级最高运算符之一 假设有前面定义的类型为stuSType的结构变量stuS例如 stuS name 直接引用stuS结构变量的name成员 3 结构变量的引用 17 引用结构变量的成员无非是对该成员进行输入输出 赋值 运算等操作 例如 printf 学号 d姓名 s成绩 d n stuS number stuS name stuS score 输出学生stuS的信息 代码 stuS score 5 更新学生stuS的成绩 strcpy stuS name Liming 更正学生stuS的姓名 3 结构变量的引用 18 2 使用结构指针和指针运算符引用方法 指针变量名 成员名其中 是指针运算符 它是由减号 和大于号 两个字符组成 请注意中间不能有空格符 其优先级与成员运算符 一样 也是优先级最高的运算符之一 继续使用前面定义的结构变量stuS 可以使用结构指针间接引用stuS结构变量的成员 stuSType sp 修改成绩 二 引用结构成员 19 3 使用结构指针和成员运算符引用方法 指针变量名 成员名其中 圆括号是必要的 若省略 由于成员运算符 优先级高于 将会导致编译错误 例如 stuSType sp 二 引用结构成员 20 1 不能直接对结构变量进行输入或输出 只允许对结构变量的成员变量进行输入和输出 例如 对于前面定义的类型为student的结构变量st1 以下分别是错误和正确的代码 printf s st1 错误 st1是结构变量不能直接输出 printf s st1 name 正确 仅输出st1的name成员 引用结构变量或成员注意 21 2 如果结构中的成员本身也是一个结构类型 在引用该成员的成员时需使用多个成员运算符 将嵌套的结构成员一级一级地连续指定 例如 想引用前面定义的类型为student的结构变量st1中成员birthday成员year 正确的写法是 st1 birthday year 引用结构变量或成员注意 22 includestructstuScore 定义结构 charname 20 intchinese intmath voidmain floataver1 aver2 aver3 stuScorest1 st2 st3 采用C 句法 定义3个结构变量 printf 请输入3位学生的姓名 语文成绩 数学成绩 n scanf s d d st1 name 例7 1 利用结构变量 输入3个学生的姓名 语文成绩和数学成绩 然后计算每个学生的平均成绩并输出 23 aver1 st1 chinese st1 math 2 0 计算平均成绩 aver2 st2 chinese st2 math 2 0 aver3 st3 chinese st3 math 2 0 printf 姓名 t语文 t数学 t平均成绩 n printf s t 4d t 4d t 6 2f n st1 name st1 chinese st1 math aver1 printf s t 4d t 4d t 6 2f n st2 name st2 chinese st2 math aver2 printf s t 4d t 4d t 6 1f n st3 name st3 chinese st3 math aver3 例7 1 程序续 24 从例7 1中可以看出 一个结构变量只能存放一个学生的基本信息 如果要描述两个学生的信息需要有两个结构变量 依此类推 当要描述一个班级的学生时 独立定义同样类型的许许多多结构变量的方法显然是不可取的 在C程序设计中 一般用结构类型描述个体的信息结构 用数组表示个体的集合 当数组的元素是结构时 这种数组就称为结构数组 例如 用结构数组表示一个班级学生 数组的元素存储一个学生的有关信息 这样 能充分反映班级的整体性 程序处理也变得更为方便 7 2结构数组 25 定义结构数组与定义结构变量的方法类似也有两种方法 1 先定义结构类型 再声明结构数组structstuScore charname 20 intchinese intmath stuScorest 3 1 结构数组的定义 2 在定义结构类型的同时声明结构数组structstuScore charname 20 intchinese intmath st 3 26 与结构变量初始化相仿 在定义结构数组时 也可给结构数组赋初值 例如 structstuScore charname 20 intchinese intmath st 3 Zhang 80 85 Li 85 90 Wang 90 70 结构数组的初始化 27 结构数组的引用实际上是对每个元素中的成员进行引用 与引用结构成员类似 也有以下3种方法 1 使用结构数组元素和成员运算符方法 结构数组名 元素下标 结构成员名例如 printf s st 0 name 输出第1个学生的姓名 即Zhang 2 结构数组的引用 28 2 结构数组的引用 2 使用结构指针和指针运算符方法 指针变量名 成员名例如 stuScore sp st 定义结构指针sp 指向结构数组st首元素 printf s n sp name 输出第1个学生的姓名 即Zhang sp 结构指针指向下一个元素 printf s n sp name 输出第2个学生的姓名 即Li 29 2 结构数组的引用 3 使用结构指针和成员运算符方法 指针变量名 成员名例如 stuScore spt st 定义stuScore结构指针spt 指向结构数组st首元素 printf s n spt name 输出学生st 0 的姓名 即Zhang spt 结构指针指向下一个元素 指向st 1 printf s n spt name 输出学生st 1 的姓名 即Li 30 includestructstuScore charname 20 intchinese intmath voidmain inti floataver 3 stuScorest 3 定义结构数组 含3个元素 printf 请输入3位学生的姓名 语文成绩 数学成绩 n 例7 2 利用结构数组 输入3个学生的姓名 语文成绩和数学成绩 然后计算每个学生的平均成绩并输出 31 for i 0 i 3 i scanf s d d st i name 例7 2 程序续 32 在C语言中 函数的形参可以是变量 指针 数组 也允许是一个结构 将一个结构传递给函数有三种方式 传递单个成员 传递整个结构 传递指向结构的指针 传递单个成员或整个结构给函数在C中认为是值调用 即在被调用的函数中尽管修改了形参的值 但不会改变调用函数时提供的实参变量的值 7 3结构与函数 33 将结构成员作为实参传递给一个函数 实际上和其他基本数据类型的传递方法相同 例7 3 输入年月日 输出该年中的第几天 includeintdayTable 12 31 28 31 30 31 30 31 31 30 31 30 31 31 29 31 30 31 30 31 31 30 31 30 31 平年或闰年 structDate 定义一个Date结构类型 intday intmonth intyear intyearDay date 定义一个Date结构类型的结构变量 1 结构成员作为函数参数 34 intdayofYear intd intm inty 计算年中第几天函数 inti leap day d leap y 4 0 返回计算的结果 例7 3 程序续 dayofYear 函数 35 voidmain intleap days printf DateConversionProgram n printf Year scanf d 例7 3 程序续 主函数 36 leap date year 4 0 例7 3 程序续 主函数 37 程序运行时 输入的数据与输出的结果如下 例7 3 程序运行结果 38 使用结构作为实参传递给一个函数 实际上将这个结构的所有成员都传递给了被调用函数的形参 以例7 3程序为例 对主函数中对函数dayofYear的调用 原来使用表示日 月 年的3个结构成员作为实参改为用一个结构变量date作为实参 即将代码date yearDay dayofYear date day date month date year 改写成date yearDay dayofYear date 2 结构作为函数参数 39 对应的dayofYear函数也要作如下的修改 intdayofYear Dated 计算年中第几天函数 inti leap day d day leap d year 4 0 返回计算的结果 2 结构作为函数参数 40 指向结构的指针作为函数的形参 实参可以是结构的地址 也可以是指向结构的指针变量 仍以例7 3程序为例 主函数中对函数dayofYear的调用 原来使用结构变量date作为实参现改为用结构变量date的地址作为实参 即将代码date yearDay dayofYear date 改写成dayofYear 2 结构指针作为函数参数 41 对应的dayofYear函数也要作如下的修改 计算年中第几天函数 无返回值 voiddayofYear Date dp inti leap day dp day leap dp year 4 0 计算结果回填到yearDay成员 没有return语句 2 结构作为函数参数 42 1 结构或结构成员作为函数参数是值传递方式 在被调用函数dayofYear中必须用return语句返回结果 如果不用return语句 写成 d yearDay day 主函数不能获得函数结果 因为函数的形参是函数的局部变量 函数调用时 将结构date的各成员值依次送给形参d的各成员中 以后函数对d作任何的改变与date无关 对结构 结构成员与结构指针作为函数参数作一个总结 main函数调用语句dayofYear函数date结构 实参 d结构 形参 43 2 使用结构地址或结构指针作为函数的参数 函数调用时 虽只传递结构的地址给结构指针形参 但通过该结构指针形参间接引用所指向的结构变量 因此 函数既可以引用结构指针形参所指向结构的成员 也可把计算结果存储于结构指针形参所指向结构的成员中 对结构 结构成员与结构指针作为函数参数作一个总结 date结构 形参dp 44 将结构date作为实参传递给dayofYear函数的结构类型形参d 但计算结果是通过returnday 语句返回到主函数的调用语句 如果希望将计算的结果先保存到结构类型形参d的成员yearDay中 然后返回结构类型形参d的值 可以对函数dayofYear重新改写如下 DatedayofYear Dated inti leap d yearDay d day leap d year 4 0 返回结构类型 4 函数返回结构类型值 45 在主函数中 调用dayofYear函数后把返回的结构赋值给结构变量date 调用语句也作相应的修改 即将date yearDay dayofYear date 改写成date dayofYear date 调用带有结构类型形参的函数时 实参结构的各成员的值需要全部拷贝给形参结构的相应成员 费时间又费空间 一般情况下 以传递结构地址或指针为好 4 函数返回结构类型值 46 变量 通过变量定义引入 程序执行时 不能显式地用语句随意生成变量和消去变量 数组 必须事先定义固定的长度 即元素个数 有时存放的数据不确定时 往往把数组定得足够大 按数据对象可能最多情况来设定变量或数组 称为静态方法 而按需要用随时生成和消去数据对象 数据之间的关系也能由程序随时设定和改变 这种实现方法称为动态方法 如链表 7 4链表 47 head 链表的 头指针 变量 存放的是地址 指向链表的第一个元素 或称表元 结点 链表元素 分成两部分 存放实际的数据和后继表元指针 单向链表结构示意图 空链表示意图 1 什么是链表 48 链表与数组相比较 主要有以下几个方面的区别 数组的元素个数在数组定义时指定 元素个数是固定的 链表表元的存储空间是在程序执行时由程序动态向系统申请的 链表的表元个数可按需要增减 数组的元素顺序关系由元素在数组中的下标确定 链表表元顺序关系由表元的指针实现 在数组中插入或删除表元 要移动部分表元的存储位置 在链表中插入或删除表元 不要移动表元 仅改变表元的指针指向即可 链表与数组的区别 49 动态数据结构中的数据对象是一种结构变量 它除有一些成员存储数据信息外 还有存储指针的成员 最简单情况是结构包含有指向与自己同样结构的指针 例如 structintNode 整数链表表元类型 intvalue 存放整数 intNode next 存放后继表元的指针 利用指针成员next 可把一个intNode类型的结构与另一个同类型的结构链接起来 用于描述动态数据结构中两数据对象之间的关系 2 动态变量 50 动态数据结构中的变量称为动态变量 动态变量能由程序调用库函数 显式地随意生成和释放 消去 在C语言中 有malloc和calloc两个库函数用于生成动态变量 另有一个库函数free用于释放动态变量 2 动态变量 51 格式 void malloc size 功能 向系统申请size个字节的连续空间 如果申请成功 函数的返回值是指向已分配的连续空间开始地址的指针 如果因动态存储区域的内存已分配完 而不能满足这次申请要求 函数将返回0 NULL 值 说明 由于malloc 函数的返回值是void类型 无类型 的指针值 程序需将该返回值强制转换成某种特定的指针类型 例如 intNode p p intNode malloc sizeof intNode 1 malloc 函数 52 2 calloc 函数 格式 void calloc n size 功能 向系统申请n块size个字节的连续空间 即n size个字节 如果申请成功 函数的返回值是指向已分配的连续空间的开始地址的指针 如果申请不成功 则返回NULL值 说明 calloc 与malloc 函数一样 返回值是一个无类型的指针值 程序需将该返回值强制转换成某种特定的指针类型 函数calloc 与函数malloc 比较 除多一个参数外 在功能上 函数calloc 还给分配的空间完成清0的工作 而函数malloc 通常不另还做清0的工作 53 2 calloc 函数 例如 申请能存储100个整数的存储块 int p p int calloc 100 sizeof int 也可以使用malloc函数实现 如 p int malloc 100 sizeof int 利用上述函数返回的存储块的首地址 就能如同普通数组一样访问这存储块中100个元素 习惯称这样的数组为动态数组 例如 以下代码置这个动态数组的值为1至100的整数 for intk 0 k 100 k p k k 1 54 3 free 函数 格式 voidfree ptr 功能 释放由ptr所指向的存储块 说明 ptr的值必须是调用函数malloc 或calloc 时的返回值 即为动态申请内存得到的一块连续存储空间的地址 以上三个函数中 形参n和size为unsigned类型 ptr为指针类型 函数malloc 和calloc 返回的是系统分配的连续存储空间的首地址 其类型为void 程序将这个返回值强制转换成某种指针类型后 赋值给某个指针变量 然后用这个指针变量间接引用存储空间的相应成员 55 主要包括建立空的单链表 创建一个表元 遍历单链表 查找指定值的表元 插入一个表元 删除一个表元等 假定存储一个学生信息的链表表元类型定义如下 structstuS 学生链表表元结构类型 intnumber 学号 charname 20 姓名 intscore 成绩 stuS next 指向后继表元的指针 stuS head p p1 p2 head是链表的头指针 其余是工作指针 3 单链表上的基本操作 56 单链表的建立过程是从空链表 没有链表表元 开始 逐步插入新表元的过程 要建立空链表首先应让 头指针 为空 即设置变量head为NULL 例如 head NULL 说明 建立以head为链表头指针的空链表 1 建立空链表 57 假设要创建一个新的学生 该生的学号 姓名和成绩从键盘输入 程序应首先向系统申请对应该生的表元的存储空间 然后输入该生的信息存入这个表元 例如 p stuS malloc sizeof stuS p指向申请到的存储块 scanf d s d 后继表元地址为空 2 创建一个表元 58 stuS createStudent intnum char name ints 学生的学号 姓名和成绩 stuS p stuS malloc sizeof stuS p number num 学号 strcpy p name name 姓名 p score s 成绩 p next NULL 后继表元地址为空 returnp 例7 4 编写创建一个学生表元的函数 59 所谓遍历链表是顺序访问链表中的表元 对各表元作某种处理 例如 顺序输出链表各表元的数据 遍历单链表需从链表的首表元开始 沿着表元的链接顺序逐一考察链表的每个表元 直至链表结束 假设用工作指针p遍历整个链表 p的初值应该是链表的头指针 循环条件是指针p还指向某个表元 即p不等于NULL 循环要做的工作包括输出p所指向的表元的值 和准备考察下一个表元 p p next实现 3 遍历链表 60 voidtravelStuLink stuS head stuS p head if head NULL printf n目前在链表中没有学生 n return printf n目前在链表中的学生如下 n while p NULL printf d t s t d n p number p name p score p p next 准备访问下一个表元 例7 5 编写创建一个学生表元的函数 61 在链表中查找指定值的表元可能有以下几个目的 获取该表元的详细信息 对找到的表元进行修改 将查到的表元删除 在查到的表元之前插入一个新表元等 查找分为两种 无序链表上的查找 有序链表上的查找 4 在链表中查找表元 62 例7 6 编写无序学生链表上的查找函数 在无序链表上查找从链表头指针所指的第一个表元出发 顺序查找 若发现有指定值的表元 以指向该表元的指针值为查找结果 若查找至链表末尾 未发现有指定值的表元 查找结果为NULL 表示链表中没有指定值的表元 stuS searchSLink stuS h intnum h为头指针 num为要查找的学号 stuS v h 工作指针v的初值是链表的头指针 while v NULL 63 在有序链表上查找 有序链表的表元是按值从小到大顺序链接的 在顺序查找循环中 当发现还有表元 并且该表元的值比寻找值小时 应继续查找 反之 若不再有表元 或当前表元值不比寻找值小 则查找应结束 查找循环结束后 仅当还有表元 并且当前表元的值与寻找值相等情况下 才算找到 函数返回当前表元的指针 否则 链表中没有要寻找的表元 函数应该返回NULL 64 例7 7 编写有序学生链表上的查找函数 从链表的首表元开始 循环条件是还有表元 且表元的值小于寻找值 循环体要做的工作是准备考察下一个学生 寻找循环结束后 在有当前表元 且当前表元的值是要寻找值情况下 函数才返回当前表元的指针 否则 函数返回NULL stuS searchSOLink stuS h intkey h为头指针 key为要查找的学号 stuS v h 工作指针v的初值是链表的头指针 while v NULL 65 在链表中插入一个表元 可以插在链表的最前面 作为首表元 最后面 作为尾表元 也可以插在指定的表元之后 在首表元之前插入新表元在原来的首表元之前插入一个新表元 插入的表元将成为链表新的首表元 这个工作包括将链表原来的首表元接在新插入的表元后面 并修改链表的头指针 使链表的头指针指向新插入的表元 设指针p指向新申请到的表元地址 实现这个功能的代码如下 p next head 新表元指向原首表元地址 使原首表元成为后继表元 head p 头指针指向新表元 使新表元成为首表元 5 在链表中插入新表元 66 插入新表元之前的状态 插入新表元之后的状态 执行p next head 执行head p 在首表元之前插入新表元 图示 67 假设指针w指向指定的表元 w不是NULL 指针p指向要插入的表元 插入工作包含两个基本动作 a 将w所指向的表元的后继表元指针复制给p所指向的表元的后继指针域 即原先w所指向表元的后继表元成为p所指向表元的后继表元 用代码p next w next实现 b 将p的值复制给w所指表元的后继指针域 即让p所指的表元成为w所指表元的后继表元 用代码w next p实现 这样 以下两行代码就能实现在w所指的表元之后插入p所指的表元的操作 p next w next w next p 在指定的表元之后插入新表元 68 插入新表元之前的状态 插入新表元之后的状态 执行p next w next 执行w next p 在指定的表元之后插入新表元 图示 69 例7 8 编写在学生链表中 在指定学生之后插入一个新学生的函数 voidinsert stuS head intnum num为要查找的学号 stuS w head p while w NULL p作为 w的后继表元 70 设要插入的新表元由指针p所指 将p所指表元添加到链表末尾的操作可由以下3个操作步骤完成 a 从头指针开始依次找到最后的表元 由指针w指向最后的表元 b 将指针p所指表元成为指针w所指的后继表元 用代码w next p实现 c 将新表元的后继表元设置为空 用代码p next NULL实现 在尾表元之后插入新表元 71 插入新表元之前的状态 插入新表元之后的状态 执行w next p 执行p next NULL 在链表末尾插入新表元 图示 72 例7 9 编写在学生链表的末尾接上一个新学生的函数 stuS append stuS head stuS w head p p stuS malloc sizeof stuS p指向新申请的表元 printf 请输入学号 姓名 成绩 scanf d s d 返回头指针 73 要将一表元从链表中删除 首先要在链表中查找该表元 若未找到 则不用做删除工作 在删除时还要考虑两种不同的情况 如果删除的是首表元要修改链表头指针 如果删除的表元不是链表的首表元 则要更改删除表元的前驱表元的后继指针 假设指针变量p1的初值指向首表元 通过循环 p1依次指向下一个表元 使用p1 p1 next实现 指针变量p2总是指向p1的前导表元 使用p2 p1实现 6 从链表中删除表元 74 从链表删除指定值的表元 图示 删除表元之前的状态 删除首表元之后的状态 head 删除非首表元之后的状态 75 p head 将首表元的指针保存到指针变量p if p 判是否为空链表 head head next 让链表的头指针指向首表元的后继表元 p next NULL 删除的表元脱离链表 删除单链表的首表元 删除单链表中的某表元p w next w是要删除表元的前驱表元的指针 w next p next p是要删除表元的指针 p next NULL 删除的表元脱离链表 76 例7 10 编写在学生链表中删除指定学号的表元的函数 stuS delStu stuS head intnum num为要查找的学号 stuS w p if head NULL returnNULL p head 让p指向链表的首表元 while p NULL 返回头指针 77 include include includestructstuS intnumber 学号 charname 20 姓名 intscore 成绩 stuS next 其他函数应插在主函数之前 主函数1 78 voidmain stuS head NULL char menu 1在链表末尾添加新表元 2在指定表元之后插入新表元 3显示链表中所有表元 4删除链表中指定表元 inti ans number while 1 printf n请选择下列菜单命令 n for i 0 menu i 0 0 i printf t s n menu i 显示在链表上操作的菜单 printf t其他选择 非1 4 结束本程序运行 n scanf d 主函数2 79 switch ans case1 head append head break case2 printf 请输入插入学生的学号 scanf d 主函数3 80 例7 11 写一个函数 输入n个整数 并按整数的输入顺序建立一个整数单链表 算法思想 为加快新表元添加到链表的末尾 引入指向链表的末尾表元的指针变量tail 链表的初始状态为空链表 即头指针head和末尾表元指针tail都为NULL 每输入一个大于0的整数时 向系统申请一个表元的存储空间并赋给指针变量p 将输入的整数存入新表元并将新表元接在链表的末尾 当输入一个小于或等于0的整数时 函数运行结束并返回链表的头指针head 4 单链表程序设计实例 81 连接前的状态 连接后的状态 例7 11 图示 82 include includestructintNode intvalue structintNode next 建立正整数链表的函数 structintNode createList structintNode head tail p 链表头尾指针 intn 存放读入的整数 head tail NULL 初始时为空链表 printf 请输入一个整型数据 0时运行结束 scanf d 例7 11 程序 83 while n 0 有整数读入 p structintNode malloc sizeof structintNode 申请一个表元的存储空间 p value n 输入的整数存入新表元 p next NULL 新表元为最后一个表元 if head NULL head tail p 当空链表时 新表元作为首表元 elsetail tail next p 非空链表时 新表元接在链表的末尾 printf 请输入一个整型数据 0时运行结束 scanf d 返回链表的头指针head 例7 11 程序 续 84 主函数 voidmain structintNode p q q createList 当函数返回时 q为头指针 while q printf d n q value 依次显示链表中的表元值 p q next free q q p 或者这三行写成p q q q next free p 例7 11 程序 续 85 算法思想 为程序处理方便 引入指向当前要考察的表元的指针变量v和指向当前要考察的表元前一个表元的指针变量u 链表的初始状态为空链表 即头指针head为NULL 每输入一个大于0的整数时 向系统申请一个表元的存储空间并赋给指针变量p 将输入的整数n存入新表元 寻找新表元插入的位置 从链表的首表元开始考察 与输入的整数n比较 若n 当前表元的值 则考察下一个表元 否则新表元插在当前表元之前 当输入一个小于或等于0的整数时 函数运行结束并返回链表的头指针head 例7 12 编写一个函数 输入n个整数 建立一个按值从小到大顺序链接的链表 86 include includestructintNode intvalue structintNode next 建立有序的正整数链表的函数 structintNode createSortList structintNode u v p head NULL u指向上一个表元 v指向下一个表元 intn printf 请输入一个整型数据 0时运行结束 scanf d 例7 12 程序 87 while n 0 有整数读入 p structintNode malloc sizeof structintNode p value n 输入的整数存入新表元 v head 从首表元开始考察 while v NULL 返回链表的头指针head 例7 12 程序 续 88 主函数 voidmain structintNode p q q createSortList 当函数返回时 q为头指针 while q printf d n q value 依次显示链表中的表元值 p q next free q q p 例7 12 程序 续 89 例7 13 实现将一个已知链表颠倒排列 即将链头当链尾 链尾当链头 颠倒前的状态 颠倒后的状态 90 例7 13 链表颠倒 图示 颠倒前 第1次循环 第2次循环 第3次循环 head p2 next p1 p2 p2 head p2 next p1 91 voidreverse intNode h intNode p v1 v2 v1 NULL 开始颠倒时 已颠倒部分为空 v2 h next v2指向链表的首表元 while v2 NULL 还未颠倒完 循环 p v2 next v2 next v1 v1 v2 v2 p h next v1 return 例7 13 链表颠倒 函数 92 联合类型和结构类型类似 都可以定义和使用不同类型的成员数据 但在联合类型中 所有成员是共享同一个存储空间 任一时刻只存储其中一个成员 因此 联合也被称之为共用体 联合的目的是表达某种数据在不同时刻取不同类型的值 7 5联合 93 格式 union联合类型名 成员说明表 例如 unionData intival charchval floatfval 表示 定义一个名为Data的联合类型 能存储整型 字符型或浮点型的数据 1 联合类型与联合变量的定义 94 在程序中如果要使用联合类型的数据 就必须定义联合变量 定义联合变量也与定义结构变量一样 可以先定义联合类型再定义联合变量 也可在定义联合类型同时定义联合变量 例如 以上已定义了联合类型Data 再定义联合变量 unionDatax y C语言句法 Dataa b C 句法 1 联合类型与联合变量的定义 也可以联合类型与联合变量一起定义 例如 unionData intival charchval floatfval u v 95 格式 联合变量名 成员名例如 前面定义了联合类型Data及联合变量x y 下面就可以正确地引用了 x ival 引用联合变量x的成员ival y chval 引用联合变量y的成员chval 注意 只引用联合变量是错误的 例如 printf d x 错误的引用 说明 这是因为联合变量中的存储的是某个成员的值 不存储联合的所有成员 2 联合变量中成员的引用 96 1 一个联合可以存放多种不同类型的数据 但实际上只存储着其中的一种数据 而不是同时存放着多种数据 存于联合中的值是最近一次存入的值 存入新值后 原有的值就全部或部分被新值所覆盖 例如 x ival 1 x fval 2 0 x chval 完成以上三个赋值后 只有x chval是有效的 而x ival或x fval中的值已经变成无意义的了 使用联合变量 注意1 97 2 联合类型变量定义时可以初始化 但只能对该变量的第一个成员置初值 例如 Datax 1 将数值1赋给x的ival成员 注意花括号是必须的 下面的写法是错误的 Datax 1 2 0 不能同时给3个成员赋值 使用联合变量 注意2 98 3 联合变量的开始地址和它的成员变量的开始地址是相同 例如 给联合变量u赋一个long型值 则u s 0 u s 1 u s 2 u s 3 是对long类型值按照字节的分拆 使用联合变量 注意3 99 4 函数的形参类型不能是联合类型 函数的结果类型也不能是联合类型 但指向联合的指针可以作为函数形参 函数也可以返回指向联合的指针 5 联合可出现在结构类型中 联合也可包含有结构和数组 引用结构中的联合 或联合中的结构与引用嵌套结构成员的书写形式完全一样 使用联合变量 注意4 5 100 在某些应用中 需要标志某些对象的状态或特征 这可分别用一个机器字中的一位二进制位或连续若干二进制位代表不同属性的状态 例如 某台计算机配置的磁盘机中的控制状态寄存器的字长为16位 自右至左 第0位至第15位 设某些位的意义如下 第15位 置1表示数据传送发生错误 第7位 置1表示设备已准备好 可传送数据 第6位 置1允许响应中断 第2位 置1表示读 第1位 置1表示写 7 6位域 101 实现上述要求可以给对应字中的某些二进位定义一系列表示特征的代码 如 defineERROR0100000 对应第15位错误标志 defineREADY0200 对应第7位准备好 defineIENABLE0100 对应第6位允许中断 defineREAD04 对应第2位读 defineWRITE02 对应第1位写 7 6位域 102 在编译程序处理符号表时 为了区分每个标识符的类别属性 如变量名 函数名 类型名 及全局的 静态的等 描述类别属性的最简单方法是把表示类别属性的字符或整数中的某些二进位作为标志位使用 例如 defineVARIABLEO1 第0位表示变量名 defineFUNCTION02 第1位表示函数名 defineTYPE04 第2位表示类型名 defineEXTERNAL010 第3位表示外部的 defineSTATICAL020 第4位表示静态的 通常称这种表示法为字位标志法 所有的数字必定是2的若干次幂 对这些位可以进行移位 屏蔽 求补等运算 就能实现对属性值的测试 存储等 7 6位域 103 例1 flg VARIABLE EXTERNAL STATICAL 表示 将flg置成变量 全局 静态的 例2 flg表示 将flg置成非变量 非全局 非静态的 说明 利用 提供的位域机制 能直接定义和存取字中的字段 字段是机器字存储单元中的一串连续的二进位 字段的定义和存取的方法建立在结构基础上 7 6位域 104 structid atr unsignedvariable 1 unsignedfunction 1 unsignedtype 1 unsignedexternal 1 unsignedstatical 1 structid atrflg 说明 flg包含五个字段 其中每个字段的长度均为1 为特别强调它们是无正负号的量 定义它们是unsigned型的 7 6位域 字段名 字段长度 105 structins type unsignedop 6 操作码占前6位 unsignedflg 2 特征码占2位 unsignedoperand1 4 第一操作数占4位 unsignedoperand2 4 第二操作数占4位 instruction 引用字段的方法 类似于引用结构的成员 如 instruction op表示引用instruction的op字段 另外 字段可以认为是一个无符号整数 像别的整数一样可出现在算术表达式中 如 flg variable flg external flg statical 1 7 6位域 106 条件 if flg extermal 0表示 测试flg的相应位是否都为0 说明 1 一个字段只能在同一个整数字中 即限制字段不能跨越整数字的边界 如果剩余的位太少不够下一个字段时 下一个字段将占用下一个整数字 2 字段可以不命名 称作无名字段 但无名字段仅用于填充 3 使用字