K2工具学习逻辑图思维导图

U85853992

2022-07-02

浏览量: 10

逻辑图

学习课程

思维导图

课程大纲

k2工具是基于微软技术而建立的一个操作平台。

树图思维导图提供《K2工具学习逻辑图》在线思维导图免费制作，点击“编辑”按钮，可对《K2工具学习逻辑图》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：7fbea3925b15e4b8bf2a5a61bd90f4b2

思维导图大纲

第一课：printf语句、数学函数

1.printf 函数(C语言输出)

printf 函数输出

printf(“输出部分”，参数部分); 格式化参数参数 printf(“你是第%d 名”，1);

printf函数格式参数

%d：int %lld： long long %f: float %lf: double %.3f: float 保留小数点后三位 %c: char

printf函数头文件

#include<cstdio>

2.数学函数

abs(求整型绝对值)

int abs(int);求整型绝对值小括号当中的数据类型为整数类型，函数返回值为 int 类型。例：abs(-3)的结果为 3。

fabs(求实型的绝对值)

double fabs(double);求实型的绝对值小括号当中的数据类型为小数类型，函数返回值为 double 类型。例：fabs(3.5)的结果为 3.5。

ceil(取上整)

double ceil(double);取上整，返回不比 x 小的最小整数函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。例：ceil(4.5)的结果为 5。

floor(取下整)

double floor(double); 取下整，返回不比 x 大的最大整数函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。例：floor(4.5)的结果为 4。

pow(计算 x 的 y 次幂)

double pow(double,double);计算 x 的 y 次幂函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。如果题意要求函数输出整型，需要强制类型转换为 int 类型。例：pow(2,3)结果为 8。

sqrt(开平方函数)

double sqrt(double);开平方函数函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。例：sqrt(16)的结果为 4。

第二课：scanf语句、选择结构回顾、嵌套选择结构

1.scanf函数(C语言输入)

scanf函数输入

scanf(“格式化表”，地址表)；样例：scanf(“%d”,&number); 读取用户键盘上的输入，转化为十进制整数，并存入到 number 中。

scanf函数格式化表

%d: 读取一个十进制整数 %f: 读取一个单精度浮点数 %lf: 读取一个双精度浮点数 %c: 读取一个字符

scanf函数头文件

#include<cstdio>

2.选择结构回顾

1、关系运算符和关系表达式

>,<,>=,<=,==,!=6 个关系运算符

2、逻辑运算符

&&(与) ||(或) !(非) a&&b: 当 a, b 均为 1 时，才为 1。 a||b: 当 a, b 中有一个为 1 时，就为 1。 !a : 当 a 为 1，!a 为 0；反之为 1。

3、优先级关系

! 高算术运算符关系运算符 &&和|| 赋值运算符低

4、if 语句单分支形式

执行过程: 当表达式值为真(非 0), 执行语句 1；当表达式值为假(0), 跳过 if 语句单分支结构。

5、if else 语句双分支形式

执行过程: 当表达式值为真(非 0), 执行语句 1；当表达式值为假(0), 执行语句 2。

6、if else 语句多重分支形式

依次判断表达式的值，当出现某个值为真时，则执行对应代码块，否则执行代码块 n。注意：当某一条件为真的时候，则不会向下执行该分支结构的其他语句。与多重 if 区分开！！

3.嵌套选择结构

1、嵌套选择结构

if 语句的嵌套: 在 if 语句中, 又包含一个或多个 if 语句。举例： if(表达式 1){ if (表达式 1){ if(表达式 2) if(表达式2)语句 1 语句 1 else 语句 2 else else 语句 2 if(表达式 3) 语句 3 } else 语句 4 }

2、嵌套选择结构 else 语句配对原则

缺省{ }时，else 总是和它上面离它最近的未配对的 if 配对。

第三课：条件运算符与switch语句、嵌套循环、循环回顾

1.条件运算符

一般形式：表达式 1？表达式 2：表达式 3 执行过程：先计算表达式 1 的值，若为真（非 0）就执行表达式 2；若为假（0），执行表达式 3。例：比较 a,b 两个数中较大的数 int max = a>b ? a : b; 当 a>b 时 max=a,否则 max=b

2. switch 语句

switch 语句是多分支语句，也叫开关语句

switch（表达式）{ case 常量表达式 1 语句 1 break； case 常量表达式 2 语句 2 break； ……. case 常量表达式 n 语句 n break； default: 语句 n+1； }

3.循环回顾

1.while循环

while(1)死循环： while(1){ 输入语句 if(表达式){ break; } 循环语句 }

while(表达式)循环：输入数据 while(表达式){ 执行循环语句 }

2.for循环

for(表达式 1;表达式 2;表达式 3){ 循环语句 }

表达式 1：控制循环变量定义并赋初值表达式 2：控制循环条件表达式 3：控制循环变量变化

for 循环适用于循环次数确定的情况

4.嵌套循环

for(表达式 1;表达式 2;表达式 3){ while(表达式1){ ……. } }

for(表达式 1;表达式 2;表达式 3){ for(表达式 1；表达式 2；表达式 3){ ……. } }

嵌套循环特点： 1、嵌套的循环控制变量不应同名，以免造成混乱。 2、内循环变化快，外循环变化慢。 3、正确确定循环体，循环控制变量与求解的问题挂钩。

第四课：嵌套循环练习、素数判定

1.嵌套循环练习

1. n 层奇数三角形这道题目考察我们通过嵌套循环输出对应图形，根据样例，我们可以将这个图形分成两部分：左侧由空格构成的三角形、右侧由数字和空格构成的数字三角形。通过嵌套循环，外层循环实现行的变化，内层循环设置两个，第一个控制空格的输出，第二个控制数字的输出。推广到 n 层奇数三角形：第 i 行空格个数：n-i 第 i 行数字个数：i 第 i 行数字变化：1~2*i-1,每次加 2

2. 小可幸运数的个数这是一道考察单层循环的题目，看一个数中有几个 1，需要使用数位分离，将输入的整数的每一位都分离出来，依次进行判断，看是否为 1，如果是1，就计数加一，最终输出计器。

3. 小可幸运数的个数* 本题是上一道题目的升级版，现在要判断的不是一个整数中有几个 1，而是 1~a 这个范围内，所有数字中有几个 1，所以需要在刚才的代码基础上，外面再嵌套一层循环，内层循环是对一个数字进行数位分离并计数，外层循环从1~a，每次递一个数字进内层循环。

4. 幸运数的个数这道题目有了上面题目的铺垫之后，就会显得比较简单，两者的区别就是一个是找有几个 1，而本题是找有几个 x，所以基本代码还是一样的，只需要在进行判断时，改一下表达式即可。

5.特殊的 e 根据题目要求 1~n 的所有整数的 1/阶乘的累加和，那首先要求出阶乘，所以嵌套循环，外层每次向内层递数，内层求出阶乘，然后将1/阶乘累加到 sum 中，最终保留小数输出即可。

2.素数判断

1. 判断素数要判断一个数 n 是否为素数，从定义入手，用 2~n-1 之间的所有整数都去尝试是否能够整除 n，如果可以说明 n 不是整数。

2. 范围内的素数上一道题目我们只是判断一个数字究竟是不是素数，而这道题目是找出 0~m 中的素数，由 1 个数变成了多个数字。而我们知道，0 和 1 时不需要进行判断的，所以我们可以直接判断 2~m 中的素数并进行输出即可。判断一个数字是不是素数我们需要使用单层循环，判断范围中的每个数字是不是素数我们可以再套上一层循环，外层循环实现 2~m 之间每一个数字的遍历，内层循环判断当前数字是不是素数，是则输出，不是则继续判断下一个，直到把范围中每一个数字全部判断完为止。

4.再论角谷猜想本题题目比较长，需要做的就是求一个范围内所有整数的数链长度，比较出一个最大值，可以利用嵌套循环来实现，外层循环实现 a 到 b 之间每一个数字的遍历，内层循环对当前数字进行奇数乘 3 加 1，偶数除 2 的操作，直到整数变为 1 为止，然后用求出的链长跟 max 进行比较，最终输出 max。

第五课:枚举及枚举练习

1.枚举

1. 枚举概念

枚举概念枚举法，又称穷举法，指在一个有限的可能的解的集合中，一一列举出集合中的每一个数，用题目给定的检验条件来判断该数是否符合条件。

2. 枚举的两个要素

①枚举的对象及范围

②枚举的条件

3. 枚举习题

2.枚举练习

1. 鸡兔同笼（简化版）鸡兔同笼问题是小学数学中非常经典的题目，同时也是在编程中利用枚举思想解决的一类非常重要的问题，在题目中告诉我们鸡和兔子的总数量（即头的数量）以及腿的数量，接下来我们可以通过枚举的思想来解决，鸡的数量可能范围是 0~n，那么对应的兔子的数量就是 n-鸡的数量，这可以作为枚举的范围，鸡和兔子的数量有了，只需要判断当前情况下腿的数量是否符合题目要求并输出即可。

2. 鸡兔同笼问题这道题是在上题基础上的一个延伸，由判断一组数组变成了判断 a 组测试数据，那么我们只需要在刚才的基础上再套上一层循环，最外层循环循环 a次，表示对 a 组测试数据的逐一处理，每循环一次便输入一组测试数据，同时进行枚举判断，如果有满足要求的解则直接输出，没有的话则输出 No answer。输出的时候不要忘了换行。

3. 百鸡问题百钱百鸡问题，又是一类非常典型的枚举问题，花 100 块钱买 100 只鸡。公鸡 5 块钱 1 只，母鸡 3 块钱 1 只，小鸡 1 块钱 3 只，满足要求的情况不只有一种，我们需要按照公鸡数量从小到大输出每一种情况。最笨的方法就是直接一个三层循环，分别枚举公鸡、母鸡、小鸡的数量同时判断只数够不够 100只，钱数是不是够 100 块，但是三层嵌套循环会使运行时间边长，本着能算不举的原则，我们继续分析。通过进一步分析我们发现，知道公鸡和母鸡的数量之后，小鸡的数量直接用 100 减去公鸡数量再减去母鸡数量就有了，这样的话三层循环就可以变成两层循环了。最后，一个非常容易忽略的点，小鸡是 1 块钱 3 只，那么小鸡的数量肯定是 3 的倍数，这一点一定不能忘了判断！！！

4. 余数相同问题完成了上面几道题之后，这道题就比较好完成了，这道题就是一个常规的枚举题目，确定枚举对象，就是要求的 t，列出枚举范围，因为三个数都小于 100w，那 x 也应该是小于 100w 的，确定判定条件，根据题目要求，余数相同就是 x%t，y%t，z%t，三者要相等，然后输出就可以。需要注意的就是题目要求输出 t 的最小值，所以从小到大枚举，当找到满足题意的答案时，要及时跳出循环，因为只需要一个答案，而不是所有满足题意的可能。

第六课:二维数组及练习

1.二维数组

1. 二维数组定义

二维数组定义一个二维数组可以看作是多个一维数组叠加在一起，二维数组中的每一行都可以看作是一个一维数组。二维数组的声明跟一维数组类似，有两个下标，分别表示行数和列数。

二维数组本质上是以数组作为数组元素的数组，即“数组的数组”，简单来说就是一个二维数组可以看作是多个一维数组叠加在一起，二维数组中的每一行都可以看作是一个一维数组。声明二维数组的一般形式：数据类型数组名[常量表达式][常量表达式]。例如想要声明一个 5 行 5 列的整型二维数组 a： int a[5][5]; 需要注意的是，在进行声明的时候，表示行列的中括号里数字表示二维数组的长度，即二维数组有几行、几列，并且二维数组的行列下标都是从 0 开始，5行 5 列的二维数组，最后一个位置为 a[4][4]。

2. 二维数组使用

1. 二维数组的初始化想要在声明的时候初始化一个二维数组一般形式如下：类型说明符数组名[常量表达式][常量表达式]={数据 1，数据 2，…数据 n}；例如想要给上面声明的二维数组 a 进行初始化，就可以写： int a[5][5]={1，2，3，4，5，6}; 计算机在对二维数组进行初始化的时候，默认是按照行的顺序去遍历数组，所以，上面这种初始化方式，在完成之后，数组中应该是如下样子： 1 2 3 4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 对于剩余位置，计算机会自动用 0 去填充。

2.二维数组练习

1. 电影包场这道题目题干比较长，需要仔细读题，其实就是输入一组数，存入二维数组，遍历二维数组，找不为 0 的位置，找到之后，输出当前位置的行下标和列下标，并且输出当前位置存储的数字。

2. 同行同列的元素对于本题，要求输出与 a[i][j]在同一行、同一列的所有元素，首先使用嵌套for 循环将所有数字存入数组中，接下来，遍历数组的第 i 行和第 j 列，这里因为只是单独的一行或者一列，所以只需要使用单层循环就可以。

3. 最高分数这道题目的难度和综合性较前面的题目都有所提升，我们使用一个二维数组进行存放存放 n 名同学 m 门课的成绩。接下来考虑计算并找出最高分数学生学号和总分的解决方式。因为我们是按行存放，那么一行就是一位同学 m 门课程的成绩。那么我们可以使用累加器，累加每一行的成绩，判断一下是不是当前最高的，如果是的话就记录他的学号和成绩，因此我们可以设置两个变量 flag 和 max，使用 flag 记录学号，也就是行下标，使用 max 记录成绩。

第七课:二维数组练习、矩阵

1.二维数组练习

1. 矩阵斜线和

题目要求我们求 n*n 方阵左上方到右下方斜线上的元素和。首先明确这条斜线其实就是主对角线，主对角线上的元素下标是有明显特点的，主对角线上的行下标和列下标是相等的，即 i==j。那么我们可以先定义一个合适大小的二维数组，将所有的元素存放好之后，接下来遍历这个数组，找出行列相等的位置，将这个数字元素中的值累加到累加其中即可。

2. 计算矩阵最外层元素的和

题目要求 m 行 n 列的矩阵边缘元素和。首先考虑的是先定义二维数组保存m 行 n 列的矩阵元素，m 和 n 的范围为 100 内，定义数组 int a[105][105]。接下来嵌套循环输入填充数组元素，数组元素填充后遍历数组元素并判断数组元素的行列下标是否在最边缘，即行下标在第一行、最后一行、第一列或者最后一列，满足条件累加器累加数组元素。

3.比较相似性

题目要求将两张图像看成相同大小的黑白图像（用 0-1 矩阵来进行表示），求这两张图片的相似度。若两张图片在相同位置上的颜色相同，则称它们在该位置具有相同的像素点。两张图片的相似度定义为相同像素点数占总像素点数的百分比。首先需要定义两个二维数组 int a[105][105]，b[105][105]代表两张相同的图片，接下来输入 m 和 n 代表二维数组的行数和列数。两个嵌套 for 循环填充数组元素，填充数组元素后判断两个二维数组相同位置上的数组元素是否相同，若相同计数器计数相同位置元素相同的数量。最后计数器/总共位置 m*n（百分比的形式）为相同位置数组元素相同所占百分比。

4. 终极 OJ

题干比较长，同学们要善于挖掘出题目的关键信息。通过分析题目我们会发现，题目让我们求出两种不同走法所耗费的时间，比较一些看看谁花费的时间更短，根据题目要求进行输出。那么解决这个问题是第一个比较关键的就是确定走法并知道该如何计算。你是先横着走，然后再竖着走；而小可是先竖着走，然后再横着走，走的时候有两个问题需要解决： ② 拐弯的地方所对应的时间我们只计算一次 ②我们是走到白衣人的面前，所以白衣人所处位置的时间是不需要计算在内的以你花费的时间为例：你是先横着走到白衣人所在列，也就是沿着第 1 行向右移动，此时行不变，列发生变化（1~y）时间为： for(int i=1;i<=y;++i){ sum1=sum1+a[1][j]; } 之后竖着走，也就是沿着第 y 列走到白衣人的面前，在这个地方注意，首先拐弯的地方只需要计算一次时间，其次走到白衣人面前的话不需要计算白衣人所在格子的时间。时间为： for(int i=2;i<=x-1;++i){ sum1=sum1+a[i][y]; } 小可花费的时间类似。

2.矩阵

1. 矩阵的概念

矩阵（Matrix）是一个按照长方阵列排列的数字集合。由 m × n 个数 aij排成的 m 行 n 列的数表称为 m 行 n 列的矩阵，简称 m × n 矩阵。

2. 矩阵加减法

两个行列大小相同的矩阵，对应位置上（数组下标相同的位置）的元素相加（减）的值再放到这个位置上。例：c[i][j]=a[i][j]+b[i][j]; c[i][j]=a[i][j]-b[i][j];

3. 矩阵数乘

矩阵的数乘是指一个数乘以一个矩阵，只要把这个数与矩阵每个元素相乘即可。

4. 矩阵乘法

两个矩阵的乘法仅当第一个矩阵 A 的列数和第二个矩阵 B 的行数相等时才能定义。如 A 是 m×n 矩阵，B 是 n×p 矩阵，它们的乘积 C 是一个 m×p 的矩阵。矩阵 C 的任意一个元素值为： Ci,j = ai,1b1,j + ai,2b2,j +···+ ai,nbn,j

第八课：阶段回顾、选择排序

1.阶段回顾

1. C 语言的输入、输出

1.C语言的输出

1.输出格式

printf(“输出部分”，参数部分); 格式化参数参数 printf(“你是第%d 名”，1);

2.格式化表

%d：int %lld： long long %f: float %.lf: double %.3f: float //保留小数点后三位 %c: char

2.C语言的输入

1.输入格式

scanf(“格式化表”，地址表)；样例：scanf(“%d”,&number); 读取用户键盘上的输入，转化为十进制整数，并存入到 number 中。

2.格式化表

%d：将参数格式化为十进制整数。 %f：将参数格式化为浮点型数。 %c：将参数格式化为单个字符。

2. 数学函数

int abs(int);求整型绝对值

小括号当中的数据类型为整数类型，函数返回值为 int 类型。例：abs(-3)的结果为 3。

double fabs(double);求实型的绝对值

小括号当中的数据类型为小数类型，函数返回值为 double 类型。例：fabs(3.5)的结果为 3.5。

double ceil(double);取上整，

函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。例：ceil(4.5)的结果为 5。

double floor(double); 取下整，

函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。例：floor(4.5)的结果为 4。

double pow(double,double);计算 x 的 y 次幂

函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。如果题意要求函数输出整型，需要强制类型转换为 int 类型。

double sqrt(double);开平方函数

函数的默认返回值为 double 类型，小括号当中的参数为 double 数据类型。例：sqrt(16)的结果为 4。

3. 条件运算符、switch 语句

1.条件运算符

一般形式：表达式 1？表达式 2：表达式 3 执行过程：先计算表达式 1 的值，若为真（非 0）就执行表达式 2；若为假（0），则执行表达式 3。例：比较 a,b 两个数中较大的数 int max=a>b? a : b; 当 a>b 时 max=a,否则 max=b

2.switch语句

1.switch语句是多分支语句，也叫开关语句。

2.一般形式

switch（表达式）{ case 常量表达式 1 语句 1 break； case 常量表达式 2 语句 2 break； ……. case 常量表达式 n 语句 n break； default: 语句 n+1； }

4. 嵌套循环结构

1.循环的嵌套：一个循环体内包含着另一个完整的循环结构，就称为嵌套循环。

2.嵌套循环特点： 1、嵌套的循环控制变量不应同名，以免造成混乱。 2、内循环变化快，外循环变化慢。 3、正确确定循环体，循环控制变量与求解的问题挂钩

5. 枚举

1.概念

枚举法，又称穷举法，指在一个有限的可能的解的集合中，一一列举出集合中的每一个数，用题目给定的检验条件来判断该数是否符合条件，若满足条件，则该数即为问题的一个解；否则，该数就不是该问题的解。枚举其实就是将所有可能的结果都依次去试一遍的过程，是一种简单、暴力的思想。

2. 适用范围

枚举法常用于解决"是否存在"或"有多少种可能"等类型的问题。

3. 枚举的两个要素

①枚举的对象及范围 ②枚举的条件

6. 二维数组

1. 二维数组定义

一个二维数组可以看作是多个一维数组叠加在一起，二维数组中的每一行都可以看作是一个一维数组。二维数组的声明跟一维数组类似，有两个下标，分别表示行数和列数。

二维数组本质上是以数组作为数组元素的数组，即“数组的数组”，简单来说就是一个二维数组可以看作是多个一维数组叠加在一起，二维数组中的每一行都可以看作是一个一维数组。声明二维数组的一般形式：数据类型数组名[常量表达式][常量表达式]。例如想要声明一个 5 行 5 列的整型二维数组a： int a[5][5]; 需要注意的是，在进行声明的时候，表示行列的中括号里数字表示二维数组的长度，即二维数组有几行、几列，并且二维数组的行列下标都是从 0 开始，5行 5 列的二维数组，最后一个位置为 a[4][4]。

2. 二维数组使用

7. 矩阵

1. 矩阵的概念

矩阵（Matrix）是一个按照长方阵列排列的数字集合。由 m × n 个数 aij排成的 m 行 n 列的数表称为 m 行 n 列的矩阵，简称 m × n 矩阵。

2. 矩阵加减法

两个行列大小相同的矩阵，对应位置上（数组下标相同的位置）的元素相加（减）的值再放到这个位置上。例：c[i][j]=a[i][j]+b[i][j]; c[i][j]=a[i][j]-b[i][j];

3. 矩阵数乘

矩阵的数乘是指一个数乘以一个矩阵，只要把这个数与矩阵每个元素相乘即可。

4. 矩阵乘法

2.选择排序

1.选择排序过程

选择排序类似于打擂台的过程，每确定一个位置上的数，该位置上的数都要和后方的所有数进行比较，我们可以理解为没比较之前该位置上的数为守擂人，后方与该数比较的数为攻擂人。用嵌套 for 循环实现打擂台的过程，外层代表守擂的人，内层代表攻擂的人。

以 n 个数从小到大为例： for(int i=0;i<n-1;i++){ for(int j=i+1;j<n;j++{ if（a[i]>a[j]）{ 交换 a[j]和 a[i] } } }

第九课：冒泡排序、排序练习

1. 冒泡排序

1.冒泡排序过程

冒泡排序是相邻两个数之间的比较排序，每轮都从第一个数开始比起，依次往后比较相邻的两个数，每轮比较下来就能确定一个位置，从而实现排序的过程。相邻两个数之间的冒泡排序用嵌套循环实现以 n 个数从小到大冒泡排序为例： for(int i=0;ifor(int j=0;jif（a[j]>a[j+1]){ int t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } }

2.汽车排序

对于这道题目，要求我们实现 n 个汽车按重量从小到大的排序交换的次数。首先我们需要把 n 个数保存到一维数组当中。N 不大于 10000，数组定义可以比 10000 大几个。题目要求相邻两个数进行交换排序，用冒泡排序对 n 个数进行从小到大的排序，若发生交换，用计数器记录交换的次数，最后将计数器里面的值输出。

2.选择、冒泡应用

1、小可的选择排序

对于这道题目，要求我们实现 M 个数据的从小到大排序。首先我们需要把M 个数保存到一维数组中之后再进行排序。M 在 100 以内，数组定义可以比100 大几个。for 循环输入 M 个元素后，接下来用选择排序对 M 个数进行从小到大的排序，最后把排好序的数组元素输出。

2、任命组长

对于这道题目，就是要求对一个无序的待排序列进行排序，排序后输出最小的两个数字就可以，因此我们可以直接对这 n 个数字进行从小到大的排序，这样排完序之后直接将前两个数字输出即可。

3、完美的数组

对于这道题目，比较难懂，首先分析题目，有 n 个数，那么每两个相邻的数就会产生一个差值，就是 n-1 个数，首先输入这 n 个数，然后计算出 n-1 个差值，根据题目要求我们需要取它们的绝对值，这时就需要用到 abs 函数。控制循环变量从 1 到 n-1，每次把 a[i]-a[a+1]的绝对值存入新数组，接下来，对存储数组里面的数字进行排序，因为按照题目要求，如果是完美数组，那这 n-1 个差值绝对值应该正好为 1~n-1 这几个数字，如果数组 1~n-1 所有位置正好就是 1~n-1，就输出‘Jolly ’，否则输出‘ Not Jolly’。

第十课：桶排序

1.桶标记、去重桶排序

1. 桶排序三步法

1. 开桶并初始化为 0

2. 在桶中标记

3. 从头至尾遍历数组进行输出

2. 布尔数据类型

桶排序数组中存储的都是 1 和 0，所以可以考虑使用 bool 类型的数组，bool 类型只有两种值，true 和 false，C++编译器在进行编译时，会将 true转换成 1，将 false 转换成 0，所以 bool 变量也可以是 1 和 0，刚好满足桶排序数组的要求。

3. 去重桶排序

桶排序是一种排序算法，其工作原理是将数组当做一个个的桶，数组下标相当于桶的编号，将待排序的数字，按照对应的下标（编号），在桶中进行标记或者计数，最后遍历数组输出标记过的数组位置的下标。

利用数组下标有序性的特点实现排序的过程

2.不去重桶排序、桶排序应用

1. 不去重桶排序

1. 开桶

不去重桶排序与去重桶排序的开桶要求一致，能够保证可能出现的每一个数字都有一个桶

2. 标记

标记这步开始去重与不去重产生差异，对于不去重的桶排序，我们需要标记每个数字出现的次数，那么每个数组元素都相当于是一个计数器，数一数当前数字共出现多少次

3. 遍历

遍历处理的过程中，我们需要根据具体题目的要求决定遍历输出的方式方法

2. 桶排序题目练习

1.不去重的桶排序

如果我们输入：2 5 2 1 8，想让输出为：1 2 2 5 8，并且不借助已经学过的选择、冒泡排序，那该如何实现呢？在这个问题上，我们发现，重复的数字并没有被去掉，那么我们可以使用不去重的桶排序来解决这个问题。首先需要修改标记方式，因为在这个问题中，我们需要记录相同数字出现的次数，因此每次输入数字写 a[t]++，相当于每次输入一个数字就计一次数，数组当中存储的是数字出现的次数。其次就是在遍历数组输出时，因为现在数组中存储的是数字出现的次数，所以，当前数字出现几次，就输出几次。那么我们需要借助一个嵌套 for 循环来实现。

2.桶排序

题目将 5 个介于 1~9 之间的正整数进行从小到大的排序，那么我们进行处理的过程中可以通过不去重桶排序来实现。首先可能出现的数字介于 1~9 之间，那么我们可以定义一个长度为 10 的数组并进行初始化，接下来进行标记的过程时，因为有 5 个数字需要进行标记，那么我们通过一个 for 循环循环 5 次，每循环一次输入一个数并对当前数字所对应下标的数组元素进行改变，最后通过一个嵌套 for 循环进行输出即可。

3.俄罗斯套娃（不去重）

还是俄罗斯套娃这道题目的背景，现在是不去重的排序，那么我们通过不去重桶排序来实现。首先套娃尺寸介于 1~100 之间，我们定义一个大小为 101 的数组用于进行桶标记，初始化操作一定不要忘了。接下来输入 n 个套娃的尺寸并进行标记，最后使用嵌套循环按照顺序进行输出即可。

4.一起来找 k

本题重点：桶排序解析：本题需要输入 n、k 及 n 个数据，分别代表 n 个数据、第几小的数及具体的数据。如果找到了输出，找不到输出 NO RESULT。解题思路： ①从小到大去重排序 ②从第一个元素开始查找，找够 k 个数，记录当前数据并输出；否则输出 NO RESULT。

第十一课：char类型字符、一维字符数组

1.char类型

1. char 数据类型

char—存储字符的数据类型使用 char 类型变量能够实现字符的存储，像 int 类型变量一样，声明一个char 类型变量就可以，例如：char a='+';

字符的本质：将一个字符存放到计算机中时，实际上并不是把该字符本身放到计算机中去，而是将该字符相应的 ASCII 代码放到计算机中，对于计算机来说，所有的字符都对应着一个唯一的数字。

2. 习题‘小可的计算器’

对于这道题目，输入的 3 个数据，前两个是操作数，第三个是操作符，只需要判断输入的操作符是“+-*/“四种中的哪一种，然后进行相应输出即可，可以使用 if-else if 语句或者 switch 语句。

3. ASCII 码—字符的本质

常用 ASCII 值范围： 48～57 为 0 到 9 十个阿拉伯数字; 65～90 为 26 个大写英文字母; 97～122 为 26 个小写英文字母。

4. getchar( )—能读入空白符的函数

输入字符的时候，用 cin 或者 scanf 是无法读入空格，回车和 Tab 的，但是它们也属于字符，可以用 getchar( )来读入一个字符(加头文件<cstdio>)，例如： char a; a=getchar();

2.一维字符数组、练习题

1. 一维字符数组

一维字符数组存储字符串：一维字符数组能够存储一串字符，数组中每个位置相当于一个字符变量，能够存储单个字符。基本操作如下： char a[10]; cin>>a; cout<<a;

2. cin.getline( )读取字符串

cin.getline( )函数能够读取空格，遇到回车结束，遇到有空格的字符串，可以用 cin.getline(数组名,长度);来输入。遇到没有空格的字符串，可以用 cin>>数组名; 来输入。

3. 字符串相关习题

1、鸭子特工

对于本题，就是需要将输入的字符串存入字符数组中，遍历字符数组，将字母的大小写进行修改，修改大小写可以根据字母的 ASCII 码值，需要知道大写字母跟小写字母的 ASCII 码差值为 32。

2.猜拳

这道题目，需要按照结果情况来编写，共有 3 种情况：Player1 胜、Player2胜、平。根据存储方式与字符串的首字母不同，可以将三种情况的条件列出来解决问题。

第十二课：字符串应用

1.strcpy( )函数

将一个字符数组的值赋值给另一个字符数组，其本质就是把含有'\0'结束符的字符串复制到另一个存储空间。想要把字符串 b 的值赋给字符串 a，不能直接写赋值 a=b，我们可以利用strcpy(a,b)来给 a 赋值，strcpy(a,b)是把字符串 b 的值赋给字符串 a，要用头文件<cstring>。

2.strlen( )函数

计算字符串长度的函数，可以用来计算字符数组中存储字符串的长度，碰到第一个字符串结束符'\0'为止，然后返回计数器值(长度不包含'\0')。

3.strcmp( )函数

用于比较两个字符串并根据比较结果返回整数。基本形式为 strcmp(a,b)，若 a=b，则返回零；若 ab，则返回正数。这里的比较是根据字典序来进行的。

第十三课：二维字符数组、字符串练习1

1.二维字符数组、字符串练习1

1. 二维字符数组的定义

二维字符数组一般用于存储和处理多个字符串，二维字符数组中的每一行均可存储表示一个字符串，即每一行都可以看作一个一维字符数组。

2. 二维字符数组的使用

二维数组的声明： char a[5][10]; 二维字符数组的使用： for(int i=0;i<=4;i++){ cin>>a[i]; } for(int i=0;i<=4;i++){ cout<<a[i]<<endl; }

2.字符串练习2

1、修改格式

这是一道利用 ASCII 码的规律进行大小写转换的题目，注意题目要求，只对字母进行操作。字符串可以分成两个部分进行处理：第一个字符跟后续所有的字符，对于每个字符串的第一个字符如果是字母的话的正确格式应该是大写字母，那么我们需要判断第一个字符是不是小写，是则改成大写；后续所有的字符如果出现字母的话应都是小写字母，那么我们需要判断后续字符串中有没有出现大写字母，如果出现大写字母则改成小写形式。

2、数据修改

这道题目描述比较长，需要仔细读题，大致过程就是，读入 n 组数据，每组数据包括一个账号、密码和邮箱，将这个邮箱与我的邮箱进行对比，如果相同，说明要修改密码，用循环遍历密码字符串，将大写改为小写，小写改为大写，修改完成后输出账号和密码，对于邮箱不相同的，不需要操作。关于'empty'的输出，可以使用 flag 标记，如果 n 次输入中，发现相同的邮箱，修改 flag 的值，最后对 flag 的值进行判断，如果等于其初值，说明没有发现需要修改的，直接输出'empty'。

3、字符排序

对于这道题目，因为是每行都是固定的 3 个字符，所以可以直接用 if 语句进行比较，首先声明、输入 n，执行 n 次循环输入字符串，存入一维字符数组，3 个字符互相比较 ASCII 码值，较小的放到数组 0 号下标，以此类推，排好顺序，输出排好顺序的字符串并换行。

while循环适用于循环次数不确定的情况思维导图模板大纲

待办事项清单思维导图