第7单元 电子课件.ppt

第7单元基本数据结构 作者 林厚从 信息学奥赛课课通 C 第1课结构体的引入和应用 学习目标1 理解结构体的概念和应用背景 2 学会使用结构体解决一些实际问题 结构体 在存储和处理大批量数据时 一般会使用数组来实现 但是每一个数据的类型及含义必须一样 如果需要把不同类型 不同含义的数据当作一个整体来处理 如1000个学生的姓名 性别 年龄 体重 成绩等 怎么处理呢 C 提供了结构体 struct 来解决这类问题 1 结构体的定义 C 中的结构体是由一系列具有相同类型或不同类型的数据构成的数据集合 也叫结构 使用结构体 必须要先声明一个结构体类型 再定义和使用结构体变量 结构体类型的声明格式如下 struct类型名 数据类型1成员名1 数据类型2成员名2 定义结构体变量 定义结构体变量格式如下 struct结构体类型名变量名列表 也可以把结构体类型声明和变量定义合在一起 格式如下 struct类型名 数据类型1成员名1 数据类型2成员名2 变量名 2 结构体的使用 结构体变量具有以下特点 1 可以对结构体变量的整体进行操作 例如 swap a i a j 2 可以对结构体变量的成员进行操作 引用结构体变量中成员的格式为 结构体变量名 成员名 3 结构体变量的初始化方法与数组类似 例1 学生信息 问题描述 输入一个学生的信息 包括姓名 性别 年龄 体重 再输出这些信息 输入格式 一行 依次是学生的姓名 性别 年龄 体重 输出格式 一行 依次是姓名 性别 年龄 体重 体重保留一位小数 输入样例 zhangsanm2090 5 输出样例 zhangsanm2090 5 p7 1 1 includeusingnamespacestd structstudent stringname charsex intage doubleweight intmain studentstu cin stu name stu sex stu age stu weight cout stu name stu sex stu age cout fixed setprecision 1 stu weight endl return0 例2 年龄排序 问题描述 输入n个学生的信息 包括姓名 性别 出生年月 要求按年龄从小到大依次输出这些学生的信息 数据保证没有学生同年同月出生 输入格式 第一行一个整数n 表示学生人数 n 100 接下来n行 每一行依次输入学生的姓名 性别 出生年份 出生月份 输出格式 按年龄从小到大 一行输出一个学生的原始信息 输入样例 5Johnmale199912Davidfemale19998Jasonmale199811Jackfemale19988Kittyfemale20007 输出样例 Kittyfemale20007Johnmale199912Davidfemale19998Jasonmale199811Jackfemale19988 p7 1 2 includeusingnamespacestd structstu stringname stringsex intyear month constintMAXN 110 stua MAXN intmain intn cin n for inti 1 i a i name a i sex a i year a i month for inti 1 i n i for intj i 1 j n j if a i year a j year a i year a j year 例3 猴子选大王 问题描述 有n只猴子围成一圈 从1 n编号 大家决定从中选出一个大王 经过协商 决定选大王的规则为 从编号为1的猴子开始报数 报到k的猴子出圈 然后再从下一只开始继续报1到k 最后剩下来的那一只就是大王 要求编程从键盘输入n k 输出成为大王的猴子编号 输入格式 一行两个正整数n和k 2 n 1000 2 k 10 9 输出格式 一行一个正整数 代表猴王的编号 输入样例 32 输出样例 3 问题分析 本题采用 模拟 法实现 可以定义一个一维数组来模拟猴子在不在圈内 用a i 代表第i只猴子的状态 0代表出圈 1代表在圈内 然后不断的扫描这个一维数组 如果猴子在圈内 则计数器加1 如果不在就不加 当计数器到达k时 就把当前这只猴子标志出圈 然后作出一些相关的处理 当还剩一只猴子的时候就停止操作 输出剩下的圈内这只猴子的编号 以上算法的最大问题是 如果猴子数比较多 不断扫描一维数组的时候会很慢 特别是当大部分猴子都已经出圈 会扫描很多无猴子的 无效 操作 如果建立一个循环链表 那么在扫描的时候就不会出现无猴子还扫描的情况 在猴子出圈的时候只需要在链表中删除一个元素 这样效率会提高很多 具体操作如下 定义一个结构体monkey 里面有两个参数 一个代表猴子编号 另一个记录这只猴子的下一只猴子的编号 注意一开始每只猴子的下一只猴子的编号是本身的编号加1 最后一只猴子的下一只猴子的编号是1号 如果需要删除3号猴子 那么只需要把当前3号猴子前一只猴子2号的下一只猴子序号 指向当前猴子3号的下一只猴子序号4 具体程序参考教材228页 229页 实践巩固 第2课结构体的扩展 学习目标1 理解运算符重载的含义及其使用 2 理解成员函数的含义及其使用 结构体的扩展 在C 中 由于类 class 技术的出现使结构体功能得到了很大的增强 本课简单介绍一些与信息学竞赛有关的运算符重载和成员函数知识 其他更详细 复杂的内容请参阅相关书籍和资料 1 运算符重载 运算符重载 常用于解决结构体或自定义数据类型的加法 减法等特殊含义的运算 运算符重载的一般格式为 类型名operator运算符 const类型名变量 const 例1 作业统计 问题描述 为了了解学生的课后作业负担情况 需要统计学生连续若干天完成作业所需的总时间 现在 输入某位学生n天完成作业的时间 格式为时 分 秒 最后输出这位学生n天完成作业的总时间 秒 输入格式 第1行一个正整数n 表示有n天 第2 第n 1行 每行3个整数 分别代表时 分 秒 输出格式 一行信息 表示这个学生完成作业的总时间 具体格式见输出样例 输入样例 3120301204511930 输出样例 4hour0minute45second 问题分析 本题需要把若干时间 时 分 秒 相加 但又不是普通的加法运算 所以 可以利用运算符重载 另外定义一个 运算 实现对两个结构体变量的加法 p7 2 1 includeusingnamespacestd structworktime 声明一个结构体类型worktime记录学生完成作业的时间inthr minut sec hr minut sec分别代表时分秒worktimeoperator constworktimex const 对 进行重新定义worktimetmp tmp sec sec x sec 60 tmp minut minut x minut sec x sec 60 60 tmp hr hr x hr minut x minut sec x sec 60 60 returntmp intmain worktimestu sum intn cin n sum hr sum minut sum sec 0 for inti 1 i stu hr stu minut stu sec sum sum stu 两个结构体sum和stu通过重载 运算符进行加法运算 cout sum hr hour sum minut minute sum sec second return0 2 成员函数 在C 中 允许在结构中定义函数 该函数称为 成员函数 描述形式如下 struct结构名 数据成员成员函数 例2 身高问题 问题描述 输入n个学生的信息 每个学生信息包括姓名 身高 学号 编程输出身高最高的学生的信息 输入格式 第1行一个正整数n 表示学生个数 n 100 以下n行 每一行依次输入学生的姓名 身高 学号 输出格式 输出最高的学生信息 如存在身高一样的请输出学号小的那个同学 输入样例 5Johaviason16820160309Jacitt输出样例 Davip7 2 2 includeusingnamespacestd structstu stringname intheigh intnum voidinput cin name heigh num voidoutput cout n for inti 1 imaxn heigh maxn a i elseif a i heigh maxn heigh 实践巩固 第3课共用体的引入和应用 学习目标1 理解共用体的概念和应用背景 2 学会使用共用体解决一些实际问题 共用体 在C 中 共用体也称联合 union 是一种数据格式 能存储不同类型数据 但同一时间只能存储其中的一种类型数据 例如 存放一个人的信息 如果是成年人 存放他的身份证号码 否则 存放他的学籍号 这里面就有两个成员 但是任何一个人只能使用其中的一个 使用共用体前必须先声明一个共用体类型 才可以定义和使用共用体变量 例如 要声明一个记录个人信息的共用体 可以这样 unionperson 声明一个共用体类型personcharid 18 声明一个字符数组 存储身份证号码intnum 声明一个整数 存放学籍号 例1 成绩统计 问题描述 兴趣小组收集学员成绩信息 每个学员的成绩有两种表示方法 一种用best good poor三种等级来表示 还有一种就是直接用分数来表示 百分制 请保存学员成绩信息 并且统计有多少人是用等级来表示成绩的 用分数来表示成绩的人的平均分是多少 取整就行 输入格式 第1行一个正整数n 表示学员人数 n 1000 第2 n 1行 每行一个字符和一个字符串 中间用一个空格隔开 第一个字符表示这个学生成绩类型 有C N两种分别代表等级表示和分数表示 第二个字符串表示成绩信息 输出格式 一行两个整数 分别表示用等级表示成绩的人数和用分数表示成绩人的平均分 取整 中间用一个空格隔开 输入样例 5CbestCgoodN90CpoorN98 输出样例 394 p7 3 1 includeusingnamespacestd intmain unionres 声明一个共用体rescharrank 5 用等级表示成绩intx 用分数表示成绩 structstu charf 代表学生用哪种方式记录成绩resscore 定义score为共用体 stua 1001 intn count 0 num 0 cin n for inti 1 i a i f switch a i f case C for intj 0 j a i score rank j count break case N cin a i score x num a i score x cout count num n count endl return0 实践巩固 第4课文件 学习目标学会使用stream类流文件进行数据的输入输出 文件 C 程序和文件缓冲区交流的方式有流式和I O方式两种 信息学竞赛中一般使用流式文件操作 流式文件类型一般分为stream类的流文件和文件指针FILE两种 本课只介绍stream类的流文件 1 stream类流文件的操作 ifstreamfin 输入流文件名 作用是定义一个输入流文件类型变量fin 初始化指向引号中指定的文本文件 ofstreamfout 输出流文件名 作用是定义一个输出流文件类型变量fout 初始化指向引号中指定的文本文件 fin 变量名 或fout 变量名 作用是从fin文件中输入数据给某个变量 或者把某个变量的值输出到fout文件中 这两个语句类似于cin和cout fin close 或fout close 作用是关闭输入文件 输出文件 如果文件没有关闭 则程序结束时会自动关闭 因此比赛时一般省略不写 例1 求和 问题描述 从文本文件sum in中读入n个正整数 要求对这n个数中的奇数和偶数分别求和 再将结果写到文本文件sum out中 输入格式 第1行一个正整数n 1 n 5000 第2 n 1行 每行一个正整数 每个数都在1 20000之间 输出格式 共有两行 每行包含一个整数 第一行为输入文件中的所有奇数之和 第二行为输入文件中的所有偶数之和 输入样例 5310758 输出样例 1518 p7 4 1 include includeusingnamespacestd ifstreamfin sum in ofstreamfout sum out intmain intn x s1 0 s2 0 fin n for inti 1 i x if x 2 1 s1 x elses2 x fout s1 endl s2 endl fin close fout close return0 2 文件的重定向 在C 中 cin使用的输入设备是键盘 称之为 标准输入 stdin cout使用的输出设备是显示器 称之为 标准输出 stdout C 可以使用freopen函数把stdin和stdout重新定向到某一个指定的文件 使原来的标准输入 输出变成指定文件的输入 输出 具体语句格式为 freopen 输入流文件名 r stdin freopen 输出流文件名 w stdout 经过重定向后 任何对stdin stdout的操作都变成了对输入流文件 输出流文件的操作 例2 替换型密码 问题描述 简单的替换型密码是很弱的 它通过将每个字母替换成另外一个字母来加密一个字母组成的信息 考虑下面的替换型密码描述 ABCDEFGHIJKLMNOPQRSTUVWXYZNOPQRSTUVWXYZABCDEFGHIJKLM这样的描述表示当输入中出现 A 的时候 输出中应该出现的是 N 同理 每个 B 都变成 O 以此类推 一直到 Z 都变成 M 这个特殊的替换型密码的例子被称为 rot13 旋转13 rotate 13的简称 有一个有趣的特性 它是自解密的 将信息再加密一次就会得到原始的信息 这样的密码中 单词 CAT 就会成为 PNG 而句子 NOWISTHETIMEFORALLGOODPEOPLETOPROGRAMWELL 就成了 ABJVFGURGVZRSBENYYTBBQCRBCYRGBCEBTENZJRYY 注意 所有的空格 标点符号以至于任何不在字符集A Z中的字符都不变 请写一个程序来实现替换型密码 输入格式 第1行 没有空格隔开的乱序的26个字母A Z 这些字母被用于描述替换型密码 第2行 一段长度在1 80之间的内容 这段内容将被加密 不会有小写字母出现 标点符号 空格和数字都可能出现 没有奇怪的字符 像退格 响铃字符之类 出现 输出格式 一行输入内容加密后的一行文本 输入样例 NOPQRSTUVWXYZABCDEFGHIJKLMNOWISTHETIMEFORALLGOODPEOPLETOPROGRAMWELL 输出样例 ABJVFGURGVZRSBENYYTBBQCRBCYRGBCEBTENZJRYY p7 4 2 includeusingnamespacestd intmain freopen subcip in r stdin freopen subcip out w stdout strings pass getline cin pass getline cin s for inti 0 i s size i if isupper s i s i pass s i 65 cout s endl return0 例3 统计奇数 问题描述 输入若干正整数 统计并输出其中奇数的个数 输入格式 若干正整数 不超过10000个 输出格式 一行一个数 表示奇数的个数 输入样例 245 输入样例 1 问题分析 当不知道输入数据的个数时 可以使用while cin x 来不断读入数据 直到文件里所有数据都读完为止 p7 4 3 includeusingnamespacestd intmain intx s 0 freopen odd in r stdin freopen odd out w stdout while cin x if x 2 1 s cout s endl return0 实践巩固 第5课队列 学习目标1 理解队列的概念及其基本操作 2 学会使用队列解决一些实际问题 队列 队列是一种操作 或者说运算 受到限制的特殊线性表 其插入操作限定在表的一端进行 称为 入队 其删除操作则限定在表的另一端进行 称为 出队 插入一端称为队尾 rear 删除一端称为队头 front 队列 队列也被称作 先进先出 线性表 FIFO FirstInFirstOut 类似于生活中排队购票 先来先买 后来后买 在不断入队 出队的过程中 队列将会呈现出以下几种状态 队空 队列中没有任何元素 队满 队列空间已全被占用 溢出 当队列已满 却还有元素要入队 就会出现 上溢 overflow 当队列已空 却还要做 出队 操作 就会出现 下溢 underflow 两种情况合在一起称为队列的 溢出 1 队列的基本操作 具体参见教材245页 246页 1 初始化 2 判空 3 求队列中实际元素的个数 4 入队 入队操作前 需要判断队列是否已满 5 出队 出队操作前 需要判断队列是否为空 6 取队首元素 2 循环队列 随着入队与出队操作的不断进行 队头指针在数组中不断向队尾方向移动 而在队头前面产生了一片不能利用的 空闲区 当队尾指针指向数组最后一个位置 即rear maxn时 如果再有元素入队就会出现 溢出 这种溢出称作 假溢出 如何解决这种情况呢 一种方法是每次出队操作时 都向 空闲区 整体移动一位 带来的后果是时间复杂度高了 另一种方法是让数组首尾相连 形成 环 状 即所谓的 循环队列 2 循环队列 循环队列初始时 front rear 0 如果maxn个元素一个个依次入队 则rear maxn 此时再有元素入队 则它会被存放在q 0 这个单元 也会出现front rear 0 与队空时的状态一样 解决方法是少用一个元素空间 约定数据入队前 测试 队尾指针在循环意义下加1后是否等于头指针 作为判断 队满 的条件 循环队列的实际长度为 rear front maxn maxn 循环队列的重要操作修改如下 使用q 0 这个单元 1 判断队满 如果 rear 1 maxn front 则队列已满 2 入队 如果队列未满 则执行 rear rear 1 maxn q rear x 3 出队 如果队列不为空 则执行 front front 1 maxn 3 队列的应用举例 例1 周末舞会 问题描述 假设在周末舞会上 男士们和女士们进入舞厅时 各自排成一队 跳舞开始时 依次从男队和女队的队头上各出一人配成舞伴 规定每个舞曲只能有一对跳舞者 若两队初始人数不相同 则较长的那一队中未配对者等待下一轮舞曲 现要求写一个程序 模拟上述舞伴配对问题 输入格式 第1行两个正整数 表示男士人数m和女士人数n 1 m n 1000 第2行一个正整数 表示舞曲的数目k k 1000 输出格式 共k行 每行两个数 之间用一个空格隔开 表示配对舞伴的序号 男士在前 女士在后 输入样例 246 输出样例 112213241122 问题分析 显然 舞伴配对的顺序符合 先进先出 所以用两个队列分别存放男士队伍和女士队伍 然后 模拟k次配对 每次取各队队头元素 配对 输出 并进行 出队 和重新 入队 操作 参考程序参见教材247页 248页 例2 取牌游戏 问题描述 小明正在使用一堆共K张纸牌与N 1个朋友玩取牌游戏 其中 N K 100000 2 N 100 K是N的倍数 纸牌中包含M K N张 good 牌和K M张 bad 牌 小明负责发牌 他当然想自己获得所有 good 牌 他的朋友怀疑他会欺骗 所以他们给出以下一些限制 以防小明耍诈 1 游戏开始时 将最上面的牌发给小明右手边的人 2 每发完一张牌 他必须将接下来的P张牌 1 P 10 一张一张地依次移到最后 放在牌堆的底部 3 以逆时针方向 连续给每位玩家发牌 小明迫切想赢 请你帮助他算出所有 good 牌放置的位置 以便他得到所有 good 牌 牌从上往下依次标注为 1 2 3 输入格式 第1行 3个用一个空格间隔的正整数N K和P 输出格式 M行 从顶部按升序依次输出 good 牌的位置 输入样例 392 输出样例 378 问题分析 方法1 利用普通队列模拟 结合题目中的条件1和3 可以推出 小明是第n个拿到牌的 根据数据范围大致推出队列存储容量上界为K 10 N 100000 N 1100000 参考程序参见教材248页 249页 方法2 利用循环队列模拟实现 参考程序参见教材249页 250页 实践巩固 第6课队列的应用 学习目标1 使用队列解决一些实际应用问题 2 学会用队列实现简单的宽度优先搜索 例1 Blah数集 问题描述 数学家高斯小时候偶然间发现一种有趣的自然数集合Blah 对于以a为基的集合Blah定义如下 1 a是集合Blah的基 且a是Blah的第一个元素 2 如果x在集合Blah中 则2x 1和3x 1也都在集合Blah中 3 没有其他元素在集合Blah中了 现在小高斯想知道如果将集合Blah中元素按照升序排列 第n个元素会是多少 注意 集合中没有重复的元素 输入格式 一行两个正整数 分别表示集合的基a以及所求元素序号n 1 a 50 1 n 1000000 输出格式 一行一个正整数 表示集合Blah的第n个元素值 输入样例1 1100 输出样例1 418 输入样例2 285437 输出样例2 900585 问题分析 根据条件 除了第一个数a以外 可以把数集q 的所有数分成两个子集 一个是用2x 1来表示的数的集合1 另一个是用3x 1来表示的数的集合2 两个集合要保持有序非常容易 只需用两个指针two和three来记录 其中two表示集合1下一个要产生的数是由q two 2 1得到 three表示集合2下一个要产生的数是由q three 3 1得到 接下来比较q two 2 1和q three 3 1的大小关系 1 如果q two 2 1q three 3 1 则把q three 3 1加入数集中 3 如果q two 2 1 q three 3 1 则取任意其一加入数集中即可 所以 本题就是利用队列先进先出的特点 模拟n个数依次产生的过程 p7 6 1 includeusingnamespacestd intq 1000011 intmain inta n x two three rear cin a n two three rear 1 q 1 a while rear n if 2 q two 1 3 q three 1 rear q rear 3 q three 1 three elseif 2 q two 1 3 q three 1 rear q rear 2 q two 1 two else rear q rear 3 q three 1 two three cout q n endl return0 例2 关系网络 问题描述 有n个人 他们的编号为1 n 其中有一些人相互认识 现在x想要认识y 可以通过他所认识的人来认识更多的人 如果a认识b b认识c 那么a可以通过b来认识c 求出x最少需要通过多少人才能认识y 输入格式 第1行3个整数n x y 2 n 100 接下来的n行是一个n n的邻接矩阵 a i j 1表示i认识j a i j 0表示不认识 保证i j时 a i j 0 并且a i j a j i 输出格式 一行一个整数 表示x认识y最少需要通过的人数 数据保证x一定能认识y 输入样例 5150100010110010100110100010 输出样例 2 问题分析 本题是求最优值问题 显然 如果x和y本身就认识 则答案是0 否则 答案至少为1 如果x和y通过z这一个人就间接认识 那么答案是1 可以通过穷举z来实现 否则 答案至少为2 如此做下去 一定能找到答案 最大为n 2 这种算法叫作 宽度优先搜索 简称 宽搜 具体实现需要通过一个队列在实现过程中扩展到所有人 把x加入队列并设置为队头元素 设q x 1 0 从队头开始进行宽搜 穷举邻接矩阵的第x行 看x认识谁 判断a x j 1 认识的人 j 全部依次入队 并且q j 1 如果出现了y 则输出q f 1 1 结束搜索 否则 取出队头元素继续宽搜 p7 6 2 includeusingnamespacestd intq 10010 2 a 110 110 boolp 110 intmain inti j r f tmp x y n memset p true sizeof p cin n x y for i 1 i a i j f r 1 q f 0 x q f 1 0 p x false while f r tmp q f 0 if tmp y cout q f 1 1 endl return0 for i 1 i n i if a i tmp 1 例3 图的宽度优先遍历 问题描述 读入一个用邻接矩阵存储的无向图 输出它的宽度优先遍历序列 输入格式 第1行1个正整数n 表示图中顶点数 2 n 100 接下来的n行是一个n n的邻接矩阵 a i j 1表示顶点i和顶点j之间有直接边相连 a i j 0表示没有直接边相连 保证i j时 a i j 0 并且a i j a j i 输出格式 输出1 n的某一种排列 表示从顶点1开始 对该图进行宽度优先遍历得到的顶点序列 每两个数之间用一个 分隔 输入样例 80110000010011000100000110100010001000100000110000010000100100010 输出样例 1 2 3 4 5 7 8 6 问题分析 图7 6 1所示为图的宽度优先遍历 用队列来实现图的宽度优先遍历 先从某个顶点出发 把这个顶点入队 作为队首元素 然后把跟队首元素相连的顶点再依次入队 最后队首元素出队 接着再把新的队首元素相连的所有顶点入队 新的队首元素出队 如此下去 直到所有元素都出队 出队的顺序就是图的宽度优先遍历序列 p7 6 3 includeusingnamespacestd constintN 110 inta N N q N h N intmain intn cin n for inti 1 i a i j cout 1 q 1 1 h 1 1 for intl 1 r 1 l r l intu q l for inti 1 i n i if a u i 实践巩固 第7课栈 学习目标1 理解栈的概念及其基本操作 2 学会使用栈解决一些实际问题 栈也是一种操作 或者说运算 受到限制的特殊线性表 其插入和删除操作都限制在表的一端进行 这一端被称为 栈顶 top 相对的另一端称为 栈底 bottom 插入操作称为 进栈 PUSH 或者 压栈 删除操作称为 出栈 POP 栈的特点是 先进后出 FILO FirstInLastOut 1 栈的基本操作 具体参见教材260页 261页 1 初始化 2 判空 3 求栈中实际元素的个数 4 进栈 压栈 5 出栈 6 取栈顶元素 2 栈的应用举例 例1 程序员输入问题 问题描述 程序员输入程序出现差错时 可以采取以下的补救措施 按错了一个键时 可以补按一个退格符 以表示前一个字符无效 发现当前一行有错 可以按一个退行符 以表示 与前一个换行符之间的字符全部无效 输入格式 输入一行字符 个数不超过100 输出格式 输出一行字符 表示实际有效字符 输入样例 sdfosif for ii 1 i 8 i 输出样例 for i 1 i 8 i 问题分析 通过栈的操作 模拟这一过程 1 逐行处理 处理完一行后输出结果 栈重新置空 2 对于每行 逐个字符处理 既不是退格符 也不是退行符 则将该字符压栈 是退格符 则出栈 是退行符 就把栈置空 p7 7 1 includeusingnamespacestd intmain freopen editor in r stdin freopen editor out w stdout chars 110 inttop 0 stringstr while getline cin str for inti 0 i str size i switch str i case top break case top 0 break default top s top str i for inti 1 i top i cout s i cout endl return0 例2 溶液模拟器 问题描述 小谢虽然有很多溶液 但是还是没有办法配成想要的溶液 因为万一倒错了就没有办法挽回了 因此 小谢到网上下载了一个溶液配置模拟器 模拟器在计算机中构造一种虚拟溶液 然后可以虚拟地向当前虚拟溶液中加入一定浓度 一定体积的这种溶液 模拟器会快速地算出倒入后虚拟溶液的浓度和体积 当然 如果倒错了可以撤销 模拟器的使用步骤如下 1 为模拟器设置一个初始体积和浓度V0 C0 2 进行一系列操作 模拟器支持两种操作 P v c 操作 表示向当前的虚拟溶液中加入体积为v浓度为c的溶液 Z操作 撤销上一步的P操作 输入格式 第一行两个整数 表示V0和C0 0 C0 100 第二行一个整数n 表示操作数 n 10000 接下来n行 每行一条操作 格式为 P v c或Z 其中 代表一个空格 当只剩初始溶液的时候 再撤销就没有用了 任意时刻质量不会超过2 31 1 输出格式 n行 每行两个数Vi Ci 其中Vi为整数 Ci为实数 保留5位小数 其中 第i行表示第i次操作以后的溶液体积和浓度 输入样例 1001002P1000Z 输出样例 20050 00000100100 00000 问题分析 使用栈来模拟实现 1 读入撤销时 栈顶元素出栈 2 读入溶液时 把新的溶液的体积和浓度压栈 3 每次操作完 输出栈顶的体积和浓度 p7 7 2 includeusingnamespacestd constintN 10010 structnode intw doublec a N intmain freopen simulator in r stdin freopen simulator out w stdout intv n c top 1 cin v c n a top w v a top c c 将初始溶液入栈while n charch cin ch if ch Z 实践巩固 第8课栈的应用 学习目标1 使用栈解决一些实际应用问题 2 学会用栈实现简单的深度优先搜索 例1 括号匹配 问题描述 假设表达式中允许包含圆括号和方括号两种括号 其嵌套的顺序随意 如 或 等为正确的匹配 或 或 均为错误的匹配 本题的任务是检验一个给定表达式中的括号是否正确匹配 输入一个只包含圆括号和方括号的字符串 判断字符串中的括号是否匹配 匹配就输出 OK 不匹配就输出 Wrong 输入格式 一行字符 只含有圆括号和方括号 个数小于255 输出格式 匹配就输出一行文本 OK 不匹配就输出一行文本 Wrong 输入样例 输出样例 Wrong 问题分析 一个匹配的括号序列 必定是左 右圆括号 方括号的数量一样多 但是反过来 一样多不一定是匹配的 定义一个字符型的栈来维护左括号 按顺序处理括号序列 1 遇到左括号 将它压栈 2 遇到右括号 检查栈顶元素与右括号是否匹配 如果匹配 将栈顶左括号出栈 否则 判断出序列不匹配 结束 如果读到了右括号 而栈为空 也不匹配 如果序列处理完毕 栈非空 也不匹配 具体程序参考教材267页 例2 表达式求值 问题描述 给定一个只包含加法和乘法的算术表达式 请编程计算表达式的值 输入格式 输入仅有一行 为需要计算的表达式 表达式中只包含数字 加法运算符 和乘法运算符 且没有括号 所有参与运算的数字均为0 2 31 1之间的整数 输入数据保证这一行只有0 9 这12种字符 输出格式 输出只有一行 包含一个整数 表示这个表达式的值 注意 当答案长度多于4位时 请只输出最后4位 前导0不输出 输入样例1 1 1 3 4 输出样例1 8 输入样例2 1 1234567890 1 输出样例2 7891 输入样例3 1 1000000003 1 输出样例3 4 输入输出样例说明 样例1计算的结果为8 直接输出8 样例2计算的结果为1234567891 输出后4位 即7891 样例3计算的结果为1000000004 输出后4位 即4 数据范围 对于30 的数据 0 表达式中加法运算符和乘法运算符的总数 100 对于80 的数据 0 表达式中加法运算符和乘法运算符的总数 1000 对于100 的数据 0 表达式中加法运算符和乘法运算符的总数 100000 问题分析 由于只有加号和乘号 只要从左往右扫一遍 如果遇到乘号直接计算 做乘法 如果遇到加号 若后面没有符号或者后面一个符号也是加号 则直接计算 做加法 否则 先把后面紧接着的连续的乘号算完 最后再加 算法实现中 只要设置一个栈保存没有立即进行的加法 扫描结束后再一起处理栈中的加法运算 同时 因为把一个数字串转换成数也需要单独编写一个子程序 最后 还要注意实现过程中及时对10000取模 具体程序参考教材269页 例3 图的深度优先遍历 问题描述 读入一个用邻接矩阵存储的无向图 输出它的深度优先遍历序列 输入格式 第1行1个正整数n 表示图中的顶点数 2 n 100 接下来的n行是一个n n的邻接矩阵 a i j 1表示顶点i和顶点j之间有直接边相连 a i j 0表示没有直接边相连 保证i j时 a i j 0 并且a i j a j i 输出格式 输出1 n的某一种排列 表示从顶点1开始 对该图进行深度优先遍历得到的顶点序列 每两个数之间用一个 分隔 输入样例 80110000010011000100000110100010001000100000110000010000100100010 输出样例 1 2 4 6 5 3 7 8 问题分析 图的深度优先遍历如图7 8 1所示 用手工栈来实现图的深度优先遍历 先任意找一个顶点入栈 即为栈顶元素 然后找到跟栈顶元素相连的一个顶点入栈 接着继续把跟栈顶元素相连的一个顶点入栈 若栈顶元素没有相连的顶点或者相连的顶点都已经入过栈那么栈顶元素就出栈 循环操作直到栈为空 那么元素的入栈顺序就是图的深度优先遍历 具体程序参考教材270页 实践巩固 第9课哈希表 学习目标初步掌握哈希表的基本思想和简单应用 哈希表 哈希表 也称散列表 是一种高效的数据结构 它的最大优点就是把数据存储和查找所消耗的时间大大降低 几乎可以看成是O 1 的 而代价是消耗比较多的内存 在当前竞赛可利用内存空间越来越多 程序运行时间控制的越来越紧的情况下 以空间换时间 的做法还是值得的 另外 哈希表的编程复杂度比较低也是它的优点之一 1 哈希表的基本概念 哈希表的基本原理是使用一个下标范围比较大的数组A来存储元素 设计一个函数h 对于要存储的线性表的每个元素node 取一个关键字key 算出一个函数值h key 把h key 作为数组下标 用A h key 这个数组单元来存储node 也可以简单的理解为 按照关键字为每一个元素 分类 然后将这个元素存储在相应 类 所对应的地方 这一过程称为 直接定址 1 哈希表的基本概念 但是 不能够保证每个元素的关键字与函数值是一一对应的 因此极有可能出现对于不同的元素 却计算出了相同的函数值 这样就产生了 冲突 换句话说 就是把不同的元素分在了相同的 类 之中了 假设一个结点的关键字值为key 把它存入哈希表的过程是根据确定的函数h计算出h key 的值 如果以该值为地址的存储空间还没有被占用 那么就把结点存入该单元 如果此值所指单元里已存储了别的结点 即发生了冲突 那么就再用