2018年物联网学生科协软件第二次培训总结

2018年物联网学生科协软件第二次培训总结

文章目录

• 2018年物联网学生科协软件第二次培训总结
• • 一、数组—-多数据存储
  • • 1. 数组的定义
    • 2. 数组的声明
    • 3. 数组的初始化
    • 4. 数组中元素的访问
    • 5.数组的内存分配
  • 二、数值交换问题
  • • 1. 最常用的方法—-建立临时变量
    • 2. 数学计算的方法
    • 3. 异或运算的方法
    • 4. 数组换标不换值的方法
  • 三、 基本的排序算法
  • • 1. 冒泡排序（升序）
    • 2. 选择排序（升序）
    • 3. 插入排序（升序）
  • 四、 字符与字符串
  • • 1. 字符的概念
    • 2. 字符的输入与输出
    • 3. 字符串的概念
    • 4. 字符串的初始化
    • 5. 字符串的输入与输出
    • 6. 关于字符串的常用函数
  • 五、有趣的小算法
  • • 贪心算法
    • • 贪心选择 — 第一个基本要素

一、数组—-多数据存储

1. 数组的定义

数组是c语言中的一种复合数据类型，是相同数据类型的有序集合。

2. 数组的声明

数据类型 数组名[下标个数];

3. 数组的初始化

(1).

(2).

(3).

4. 数组中元素的访问

通过数组下标来访问每个元素

小代码示例：

5.数组的内存分配

当编译器对以上代码进行编译时，就会为数组分配内存单元。 假设计算机指定数组score中的元素从地址为1000的地方开始存放。
具体分配原理如下图所示：

二、数值交换问题

1. 最常用的方法—-建立临时变量

小代码示例：

2. 数学计算的方法

小代码示例：

缺点：两个数的和可能会越界，适用于两个比较小的数

3. 异或运算的方法

小代码示例：

思路：将a,b转换为二进制数(10 = 01010，20 = 10010)
按位异或（两个值相同为0，不同为1）

4. 数组换标不换值的方法

小代码示例：

思路：用数组元素作为数组的下标，这种方法换逻辑不换存储

三、 基本的排序算法

1. 冒泡排序（升序）

基本操作：比较数组中相邻的元素。如果这个数比它后一个大，就交换它们两个。
第一步：从数组第一和第二个元素（第一对）开始，执行基本操作，直到数组末尾的两个元素（最后一对）。这样执行一遍后，最后的元素会是数组中最大的数。
第二步：重复基本操作，但每次操作的元素会少一个（因为执行完n次操作后，前n个最大的元素会被排好序），直到没有任何一对数字需要比较。冒泡排序完成。

小代码示例：

2. 选择排序（升序）

基本操作：每次找出操作序列中最小的数放到最前面。
第一步：第一次操作遍历整个序列，将最小的元素放到首位。
第二步：重复基本操作，第n次操作从序列第n个元素开始遍历序列，将最小的元素放到序列第n个位置。直到某次操作序列中没有元素可以遍历。选择排序完成。

图解如下：

3. 插入排序（升序）

基本操作：将有序序列的后一个元素插入到序列当中，使其依然有序。
第一步：假设初始时有序序列中只有第一个元素，此时执行基本操作，会将第二个元素排好序。此时有序序列中有两个元素。
第二步：重复基本操作，有序序列的长度不断增加。当有序序列中的元素个数和原序列相等时，即所有元素均有序排列时，插入排序完成。

图解如下：

四、 字符与字符串

1. 字符的概念

字符型数据包括 字符常量 和 字符变量。

(1). 字符常量：

• 概念 ：
  是单引号括起来的一个字符。例如：‘a’、‘b’、‘=’、‘都是合法的字符常量。
• 特点 ：
  ①字符常量只能用单引号括起来，不能用双引号或者其他字符；
  ②字符常量只能是单个字符，不能是字符串；
  ③字符可以是字符集中的任意字符，但数字被定义为字符型之后不能参与数值的运算。（比如：‘3’和3）
• 特殊的字符常量：
  在上次培训我们提到的转义字符是一种特殊的字符常量，其具有特定的含义不同于字符原有的意义即为”转义”。
  

(2). 字符变量：

• 字符型变量用来存储字符数据，即单个字符。
• 字符变量的类型说明符是char。
  注意： ①每个字符变量被分配一个字节的内存空间，因此只能存放一个字符；
  代码小示例：

字符值是以ASCII码的形式存放在变量的内存单元之中的。

2. 字符的输入与输出

小练习： 输入一个字母，将其大写转小写，小写转大写。

小代码示例：

3. 字符串的概念

从形式上看，一个字符串就是用一对双引号括起来的一串字符,其双引号是该字符串的起，止标志符，它不属于字符串本身的字符。
例：
“string”
“物联网院学生科协”

4. 字符串的初始化

字符型数组表示字符串

注意： 在进行逐个元素初始化时，必须明确写出字符串结束符’ ’

5. 字符串的输入与输出

小练习：输入一个字符串，将其大写转小写，小写转大写。

小代码示例：

6. 关于字符串的常用函数

函数：函数是一个封装一个功能的代码块，便于重复使用。主要是传入参数，获得返回值，或者在函数内对参数进行操作。其中关于字符串的常用函数都在头文件里，即在使用时要在最上面加上 #include

(1). 求字符串长度—-strlen函数

①功能：计算字符串的长度

②返回值：返回字符串的实际长度，不包括‘ ’在内

③注意：在求字符串长度的过程中，遇到字符串‘ ’就结束，只计算起始位置到‘ ’前面的字符个数，例如：strlen(“AB CD EF”)的结果是2

sizeof()与strlen()函数的区别：
sizeof()计算的是系统为变量分配的内存空间的大小，会加上隐藏结束符的长度。

(2). 字符串拷贝

• strcpy函数

①功能：将字符串s2复制到s1指定的地址（即将字符串s2拷贝到s1中去）

②返回值：字符串s1的首地址。

③注意：字符串s1必须是数组或者已经分配空间的字符型指针，并且空间足够大，该函数不分配空间；拷贝时‘ ’一同被拷贝；不能使用赋值语句给一个字符数组赋值；

• strncpy函数

功能：将s2的前n个字符复制到s1中对应的地址, 并在末尾加‘ ’ ；

(3). 字符串连接—-strcat函数

①功能：将字符数组s2连接到字符数组s1尾部
②说明：字符数组s1必须空间足够大（s1的存储空间≥strlen(s1）+strlen(s2)+1),连接前，两串均以‘ ’结束，连接后，串s1原来的‘ ’被覆盖，新得到的字符串最后加‘ ’；调用此函数后，s1的长度等于s1、s2两个字符串长度之和。

小代码示例：

(4). 字符串比较—-strcmp函数

①功能：比较字符串s1和s2。
②比较规则：对两个串从左向右逐个字符比较（ASCII码），直到遇到不同的字符或者‘ ’为止；
③返回值：返回int型整数。
（1）若s1 （2）若s1 > s2，返回正整数；
（3）若s1 = s2，返回零；
注意： 字符串比较不能用“==”，必须用strcmp;

以上函数的综合使用
小代码示例：

五、有趣的小算法

贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，将整体最优问题分解为局部来考虑，做出的是在某种意义上的局部最优解。

贪心选择 — 第一个基本要素

贪心选择是指，所求问题的整体最优解可以通过一系列局部最优的选择来达到。
对于一个具体问题，要确定它是否具有贪心选择的性质，我们必须证明每一步所作的贪心选择最终能得到问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。

• 贪心算法相关经典问题：
  货币选择问题、背包问题、区间调度问题、字典序最小问题

小练习： 双11已经不远了，但一橙小萌新很苦恼，因为他每个月的15号才能收到生活费。为了解决这个问题，他决定提前向妈妈索要11月份的生活费，但他的妈妈却没有那么容易将钱给他。妈妈说：你不是在学编程吗你告诉我，如果接下来几个月的生活费我都不用移动支付的方式，而是以纸币的形式给你，我最少要准备多少张人民币呢回答出来就提前给你11月份的生活费，否则你双11就别买东西了！
一橙小萌新想买的罗技鼠标在购物车里很久了，要是错过双11就太悲伤了，你们快帮帮他吧！（假设每个月的生活费是整数。人民币一共有100元、50元、10元、5元、2元和1元六种）。

Input
输入数据第1行是一个整数n（n Output
输出一个整数x，表示至少需要准备的人民币张数。每个输出占一行。
Sample Input
3 1 2 3
Sample Output
4

小代码示例：

思路：从大面值钞票往下选，便是最少的张数。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

来源：HHUCESTA