c++课件-结构与链表.ppt

1 第六章结构和链表 6 1结构类型6 2结构的应用 链表6 3应用举例 2 6 1结构类型 6 1 1结构类型说明 C语言提供了这样一种数据结构 它将不同类型的数据组合成一个有机的整体 结构体 3 structdate intmonth intday intyear structman charname 15 charsex intage datebirthday 如 说明一个结构类型date 含三个整型数据成员 在此基础上 又可说明另一个结构类型man birthday Name sex age month day year structman 结构类型 4 6 1 2结构变量定义及初始化 先说明结构类型再定义结构变量在说明结构数据类型的同时定义结构变量省略结构标识符直接定义结构类型变量 structmanman1 man2 structman charname 15 charsex intage structdatebirthday man1 man2 struct charname 15 charsex intage structdatebirthday man1 man2 无类型名变量 5 structgoods 定义一个商品结构类型 charbh 6 商品编号charmc 20 商品名称floatdj 商品单价intsl 商品数量charjhrq 8 进货日期 g1 10012 shoes 124 100 080912 结构变量也允许在定义的同时给出初值 即初始化 如 structperson charname 15 charsex intage s 10 FangMin F 24 FangHua M 35 定义一个结构数组并对其部分元素初始化 6 6 1 3结构变量的访问 访问形式 结构变量名 成员名 指向结构的指针 成员名指向结构的指针 成员名 或 或 通过指向结构的指针引用结构变量成员 成员访问运算符优先级最高的四个运算符之一 括号不能少 如 假设有定义manm p strcpy m name FangMin p birthday month 8 则可如下引用结构成员 7 例6 1 某商场周年店庆期间对其会员进行积分换购活动 活动内容为允许每天前五名光临的会员用其积分换购相应的商品 假设每100个积分可以换购5元的商品 编程序求该商场店庆期间每天换购出去的商品金额以及会员换购后的剩余积分值 假设会员将全部可能积分全部进行换购 分析 可以将会员卡号和积分组合在一起定义一个结构类型 用结构数组来描述若干会员的信息 如 structcard charnum 10 intscore c 10 8 include iostream h defineN5voidmain structcard charnum 10 intscore c N inti s 0 for i 0 i c i num c i score s s 5 c i score 100 每100分换购5元商品c i score c i score 100 c i score 100 该会员的剩余积分 cout 扣除积分后 n for i 0 i N i cout c i num t c i score endl cout 积分换购金额 s endl 9 链表是一种线性表 一个线性表是n n 0 个数据元素的有限序列 在计算机中 线性表可以选择连续存储和链接存储 连续存储把数据元素一个接一个地放在一组连续的存储单元之中 也就是把线性表中的数据元素存放在一片连续的存储域 连续存储的线性表称为数组 因为数组的长度是固定的 而线性表的元素个数通常是不确定的 所以通常将数组定义成充分大 但这样会造成存储空间的浪费 用数组存储线性表的另一个缺点是在进行插入和删除操作时需要移动数据 6 2结构的应用 链表 10 链接存储链接存储的线性表称为链表 元素之间靠指针链接 特点每个元素 结点node 由数据域data和指针域next构成 其中指针域指向下一个元素的首地址 最后一个元素的指针为NULL 结点之间可以连续 可以不连续存储 结点的逻辑顺序与物理顺序可以不一致 表可根据需要动态扩充 11 下图是一个具有5个数据元素 称为结点 的线性链表 单向链表 每一个线性链表都有一个表头指针 head 如果链表是非空链表 则存放第一个结点的起始地址 否则head NULL 2238465894 存储地址数据域指针域 38 head 12 链表中的每一个结点都是结构类型的变量 应包含两个部分 数据域和指针域 即下一个结点的地址 前面图中的结点和表头指针的类型可以这样说明 structnode intdata structnode next structnode head 指向它所属的结构类型 13 链表的常见操作有 1 建立链表 2 输出链表 3 确定链表的长度 即统计链表中结点的个数 4 查找链表中的某个结点 5 在链表中插入一个新的结点 6 删除链表中的某个结点 14 6 2 1链表的基本操作方法 1 生成结点变量当向链表中加入新数据时 需要生成一个新结点以存放要加入的新数据 为此 首先要为新结点申请存放空间 有两种常用方法 使用malloc函数分配空间假设有定义 structnode intdata structnode next p 此时p尚没明确的指向单元则使用如下语句可使p指向一个node类型的结点 p structnode malloc sizeof node 15 关于函数malloc的说明 功能是分配一个类型为node的结点变量的空间 并返回其首地址 对该函数的原型说明包含在头文件stdlib h中 sizeof是一个求字节数的运算 malloc函数的参数中要给出申请空间的大小 使用new运算符分配空间p newnode 该方法使用起来更加简单 但C语言中不支持此方法 为方便起见 本书中的程序多采用后一种方式来为新结点申请存放空间 16 2 释放结点变量空间当删除链表中的结点时 也应该及时地将其占用的存储空间返还给内存 假设下图中p所指向的结点是要删除的结点 则相对应用malloc函数分配的空间 可以用如下语句释放 free p 其中free是个函数 其原型说明也包含在头文件 stdlib h 中 相对应用new运算符申请的空间 则用如下语句释放 deletep 17 3 结点分量的访问由于在链表中各个结点之间的联系是靠指针域来实现的 所以对结点各成员的访问也是利用指向结点的指针变量来进行的 对p所指向的结点的数据域的访问 p data或p data 多以后一种方式为常见对p所指向的结点的指针域的访问 p next或p next 多以后一种方式为常见 18 例6 2 假设node是前面已经定义过的结构类型 又有定义node p q 则建立一个如下图所示的包含两个结点的链表 建立第一个结点需要两步操作 首先为其申请存放空间 然后为其数据域赋值 建立第二个结点 除了和建立第一个结点相同的两步操作外 因为它是链表中的最后一个结点 因此还要将其指针域置为空 将第二个结点连接到第一个结点之后 即让第一个结点的指针域指向第二个结点 19 或p structnode malloc sizeof structnode 为第二个结点的指针域赋值 10 20 p newnode p data 10 q newnode q data 20 NULL q next NULL p next q 20 6 2 2链表的建立 例6 3 创建一个含有n个结点的 包含一个数据域 且其类型为整型的单链表 链表的建立过程如下 首先设置head为NULL 即建立一个空的链表 申请一个新结点存储区域 让newnode指向该结点 然后向其数据域输入数据 把newnode所指向的结点插入到链表中 如果当前链表是空表 newnode所指向的结点应该成为该链表中唯一的一个结点 故head和tail都应该指向该结点 21 如果当前链表非空 则newnode所指向的结点应该做为链表中的最后一个结点加入到链表中 故应该将其插在tail指向的结点后面 重复执行第2 3步共n次 将最后一个结点的next域置空 NULL 22 include iostream h structnode intdata structnode next structnode create intn structnode head NULL structnode tail newnode intx for inti 0 i x newnode 为newnode申请存放空间newnode data x newnode 也可用如下语句newnode structnode malloc sizeof structnode 23 if head NULL newnode成为空表的第一个结点else 将newnode连接到原来的表尾 newnode成为新的表尾 tail next NULL return head voidmain structnode head intn cout n head create n head newnode tail next newnode tail newnode 24 6 2 3单链表的基本操作 1 链表的遍历 由于链表的指针域中包含了后继结点的存储地址 所以只要知道该链表的头指针 即可依次对每个结点进行访问 例6 4 输出上例中建立的单链表的各结点的值 假设定义p是指向链表中结点的工作指针 该指针从表头head开始逐一指向后续的各个结点 每指向一个结点 便通过该指针访问结点的数据域 直到p的值为NULL 25 遍历的函数实现如下 voidprint structnode head structnode p head while p NULL coutdata t 注意不能通过p 实现指针后移 p p next 26 2 统计结点个数 例6 5 统计例6 3中创建的链表中结点的个数 设置一个工作指针从表头结点开始 每经过一个结点 计数器的值增加1 实现统计的函数形式如下 intcount structnode head structnode p head intn 0 while p NULL n p p next return n 27 3 查找结点 例6 6 在链表中按序号查找第i个结点 设置一个序号计数器j和一个工作指针p 从表头结点开始 顺着链表的链进行查找 仅当j i并且p NULL时查找成功 否则查找不成功 28 voidsearch structnode head inti intj 1 structnode p head if idata elsecout illegalindex n p p next j i p NULL 29 4 在链表中插入结点 假定有一个指针behind指向链表中的某个结点 newnode指向待插入结点 newnode 12 101519 behind front 如果有一个指针front指向behind的前驱 则仅需编写下面的两个语句 即可实现插入 如果没有behind指针 插入操作仍然可以完成 newnode next front next front next newnode 思考题 上述两个语句的次序能否交换 为什么 newnode next behind front next newnode 30 两种特殊情况 1 在表头结点之前插入 2 在尾结点之后插入 newnode head behind 6 7 newnode 8 例6 7 编写函数 实现在头结点为head的链表中插入值为x的结点 newnode next behind head newnode behind next newnode NULL newnode next NULL 31 structnode insert node head intx structnode behind front newnode newnode newnode newnode data x behind head if head NULL 空表 head newnode newnode next NULL else 非空表 while behind NULL 32 5 删除链表中的某个结点 删除链表中的某个结点 是把被删除结点的后继结点的地址 赋给其前趋结点的指针域或表头指针head 无后继结点时 则赋NULL 假定p为指向要删除结点的指针 q为指向删除结点前趋的指针 如果p head 则删除的是第一个结点 则应修改表头指针head 使其指向第二个结点 并释放第一个结点占据的存储空间 head p next deletep 33 如果删除的是链表的中间结点 则应把被删除结点p的后继结点的地址 赋给其前趋结点q的指针域 如果没有后继结点时 则赋空指针NULL q next p next deletep 34 例6 8 编写函数实现在头结点为head的链表中删除值为x的结点 structnode delnode node head intx structnode p q p为工作指针 q为p的前驱p head if head NULL 空表coutdata x 找删除的结点 q p p p next if p head 删除第一个结点 head p next deletep elseif p NULL 删除非表头结点 q next p next deletep else 未找到要删除的元素cout x dosenotexistinthelist n returnhead 35 6 2 4带表头结点的单链表 表头结点 又称伪结点 位于表的最前端 本身不带数据 仅标志表头 设置表头结点的目的是统一空表与非空表 表头和表中位置的操作形式 简化链表操作的实现 非空表空表 36 在带表头结点的单链表最前端插入新结点 newnode next p link p next newnode 非