数组
一、数组简介
C 语言支持数组数据结构，它可以存储一个固定大小的相同类型元素的顺序集合。数组是用来存储一系列数据，但它往往被认为是一系列相同类型的变量。
数组的声明并不是声明一个个单独的变量，比如 number0、number1、...、number99，而是声明一个数组变量，比如 numbers，然后使用 numbers[0]、numbers[1]、...、numbers[99] 来代表一个个单独的变量。数组中的特定元素可以通过索引访问。
所有的数组都是由连续的内存位置组成。最低的地址对应第一个元素，最高的地址对应最后一个元素。
array.jpg
二、动手编写一个简单的数组程序
#include <stdio.h>
int main()
{
int a[5] = {2, 4, 5, 8, 20};
for(int i = 0; i <= 4; i++)
{
printf("a[%d] = %d\n", i, a[i]);
}
return 0;
}
运行结果：
a[0] = 2
a[1] = 4
a[2] = 5
a[3] = 8
a[4] = 20
分析：
（1）int a[5]; 这是声明了一个数组，数组类型为整型，数组名为a，数组大小为5，表示可以放5个整型元素。
（2）a[5] = {2, 4, 5, 8, 20}，这是赋值语句，类比于a = 1。不过通常说成是数组的初始化，而不是给数组赋值。注意，是用大括号把元素包含在内，而不是中括号或小括号。
（3）数组的下标是从0开始的，所以本程序中的五个元素为a[0], a[1], a[2], a[3], a[4]，而不是a[1], a[2], a[3], a[4], a[5]。这从for循环也可以看出，for循环是从0增加到4，而不是从1增加到5。如果要获取a[5]或a[6]，编译器会报数组越界的错误或者直接取到了0！。
（4）假如数组的大小为size，那么元素的最大下标为size - 1。以本程序为例，大小为5，则最大下标为4，即只能取到a[4]。
（5）如果把在数组声明后直接初始化，类似本程序这样的，可以不用写数组大小，运行效果完全一样。
#include <stdio.h>
int main()
{
int a[] = {2, 4, 5, 8, 20};
for(int i = 0; i <= 4; i++)
{
printf("a[%d] = %d\n", i, a[i]);
}
return 0;
}
三、逐个给数组元素赋值
#include <stdio.h>
int main()
{
int a[5];
for(int i = 0; i <= 4; i++)
{
a[i] = 2 * i;
printf("a[%d] = %d\n", i, a[i]);
}
return 0;
}
运行结果：
a[0] = 0
a[1] = 2
a[2] = 4
a[3] = 6
a[4] = 8
注意，在声明数组int a[5]的时候，因为不是立即初始化（跟上面的例子不一样），则数组大小（这里为5），不能省略。
四、浮点数数组
#include <stdio.h>
int main()
{
float a[4] = {1.1, 2.2, 3.33, 5.555};
for(int i = 0; i <= 3; i++)
{
printf("a[%d] = %f\n", i, a[i]);
}
return 0;
}
运行结果：
a[0] = 1.100000
a[1] = 2.200000
a[2] = 3.330000
a[3] = 5.555000
五、字符数组
#include <stdio.h>
int main()
{
char c[] = {'H', 'e', 'l', 'l', 'o', '!'};
for(int i = 0; i < 6; i++)
{
printf("%c", c[i]);
}
return 0;
}
运行结果：
Hello!
六、如果没有显示写出数组长度，求数组长度
#include <stdio.h>
int main()
{
int a[] = {2, 4, 5, 8 ,20};
printf("Size of int: %ld\n", sizeof(int));
printf("Length of a: %ld\n", sizeof(a));
printf("Size of a: %ld\n", sizeof(a) / sizeof(int));
printf("====================\n");
float b[] = {2.0, 3.2, 5.13, 8.8888,20};
printf("Size of float: %ld\n", sizeof(float));
printf("Length of b: %ld\n", sizeof(b));
printf("Size of b: %ld\n", sizeof(b) / sizeof(float));
printf("====================\n");
double d[] = {2.0, 3.2, 5.13, 8.8888,20};
printf("Size of double: %ld\n", sizeof(double));
printf("Length of d: %ld\n", sizeof(d));
printf("Size of d: %ld\n", sizeof(d) / sizeof(double));
printf("====================\n");
char c[] = {'H', 'e', 'l', 'l', 'o', '!'};
printf("Size of char: %ld\n", sizeof(char));
printf("Length of c: %ld\n", sizeof(c));
int size = sizeof(c) / sizeof(char);
printf("Size of c: %d\n", size);
return 0;
}
运行结果：
Size of int: 4
Length of a: 20
Size of a: 5
====================
Size of float: 4
Length of b: 20
Size of b: 5
====================
Size of double: 8
Length of d: 40
Size of d: 5
====================
Size of char: 1
Length of c: 6
Size of c: 6
分析：
以int a[] = {2, 4, 5, 8 ,20}; 为例：
整型数每个占4字节，所以sizeof(int) = 4字节
数组a包含了5个整型数，计算出a的长度（即有多少个字节）sizeof(a) = 20字节
相除即得到a的大小（即个数）为sizeof(a) / sizeof(int) = 5个元素
字符串
在 C 语言中，字符串实际上是使用 null 字符 '\0' 终止的一维字符数组。
（一）下面是一个定义字符串的例子。由于在数组的末尾存储了空字符，所以字符数组的大小比单词 "Hello" 的字符数多一个。
char str[ ] = {'H', 'e', 'l', 'l', 'o', '\0'};
但是在算字符串的长度时，最后的空字符‘\0’不算在内。
验证程序：
#include <stdio.h>
#include <string.h>
int main ()
{
char str[] = {'H', 'e', 'l', 'l', 'o', '\0'};
printf("string1: %s\n", str);
int len1 = sizeof(str) /sizeof(char);
int len2 = strlen(str);
printf("The size of array is %d\n", len1);
printf("The length of string1 is %d\n", len2);
return 0;
}
运行结果：
string1: Hello
The size of array is 6
The length of string1 is 5
以下是 C/C++ 中定义的字符串的内存表示：
string.jpg
（二）还可以把字符串的定义写为char str[] = "Hello";
#include <stdio.h>
#include <string.h>
int main ()
{
char str[] = "Hello";
printf("string1: %s\n", str);
int len1 = sizeof(str) /sizeof(char);
int len2 = strlen(str);
printf("The size of array is %d\n", len1);
printf("The length of string1 is %d\n", len2);
return 0;
}
运行结果：
string1: Hello
The size of array is 6
The length of string1 is 5
可见结果是完全一样的。
二进制与十进制之间的转换
一、二进制转换为十进制的C语言代码
#include <stdio.h>
#include <string.h>
int binary2decimal(char str[])
{
int sum = 0;
int j = 1;
int pos = strlen(str) - 1;
for(; pos >= 0; pos--)
{
sum += (str[pos] - '0') * j;
j *= 2;
}
return sum;
}
int main()
{
// 字符用单引号，字符串用双引号
int result = binary2decimal("1101");
printf("Output decimal: %d\n", result);
return 0;
}
运行结果：
Output decimal: 13
思路：
以"1101"为例。
（1）先计算出最右侧的“1”， sum("1") = 1
（2）再计算出最右侧的“01”，并且要用到上次计算的结果。sum("01") = sum("0") + sum("1") = 1
（3）再计算出最右侧的“101”，并且要用到上次计算的结果。sum("101") = sum("1") + sum("01") = 4 + 1 = 5
（4）最后计算出“1101”，并且要利用上次计算的结果。sum("1101") = sum("1") + sum("101") = 8 + 5 = 13
程序分析：
（1）for(; pos >= 0; pos--)
这里第一个表达式没有内容，那是因为在上一步已经赋值了，这里可以省略。
（2）sum += (str[pos] -‘0’) * j 等价于 sum = sum + (str[pos] - ‘0’) * j
j *= 2 等价于 j = j * 2
（3）数组的下标是从左往右递增的。
例1：str[] = “abcde”，则str[0] = ‘a’, str[1] = ‘b’, str[2] = ‘c’, str[3] = ‘d’, str[4] = ‘e’
例2：str[] = “1101”，则str[0] = ‘1’，str[1] = ‘1’, str[2] = ‘0’, str[3] = ‘1’
二进制与数组相反，二进制的最低位在最右边，最高位在最左边。十进制也是如此。
比如二进制1101，第0位的值是1，第1位的值是0，第2位的值是1，第3位的值是1。
程序中的for采用了从高位向低位递减，就是因为二进制与数组的下标顺序相反。
（4）for的计算过程
刚开始时，pos = strlen(“1101”) - 1 = 4 - 1 = 3
① 第1 次循环，pos = 3，str[pos] - ‘0’ = ‘1’ - ‘0’ = 49 - 48 = 1, sum = sum + 1 * j = 0 + 1 * 1 = 1, j = j * 2 = 1 * 2 = 2, pos自减后变为2
② 第2次循环，pos = 2, str[pos] - ‘0’ = ‘0’ - ‘0’= 48 - 48 = 0，sum = sum + 0 * j = 1 + 0 * 2 = 1, j = j * 2 = 2 * 2 = 4，pos自减后变为1
③ 第3次循环，pos = 1, str[pos] - ‘0’ = ‘1’ - ‘0’= 49 - 48 = 1，sum = sum + 1 * j = 1 + 1 * 4 = 5, j = j * 2 = 4 * 2 = 8，pos自减后变为0
④ 第4次循环，pos = 0, str[pos] - ‘0’ = ‘1’ - ‘0’= 49 - 48 = 1，sum = sum + 1 * j = 5 + 1 * 8 = 13, j = j * 2 = 8 * 2 = 16，pos自减后变为-1，循环结束。
所以，最终的结果就是13
二、十进制转换为二进制的C语言代码
#include<stdio.h>
void decimal2binary(int dec)
{
if(dec / 2)
{
decimal2binary(dec / 2); // 递归
}
printf("%d", dec % 2);
}
int main()
{
int num = 6;
printf("%d转化为二进制:", num);
decimal2binary(num);
return 0;
}
运行结果：
6转化为二进制:110
程序分析：
（1）这里decimal2binary()函数调用了decimal2binary()函数，说明用到了递归。
（2）程序中，运算符“/”表示除号。
例1：6 / 2 = 3
例2：3 / 2 = 1
例3：1 / 2 = 0
运算符“%”表示求余数。
例4：6 % 2 = 0
例5：3 % 2 = 1
例3：1 % 2 = 1
（3）递归调用过程
第一次在main()中调用decimal2binary(6) ①
在这个函数中，if(6 / 2) = if(3)判断为真，
所以会调用decimal2binary(3) ②
在这个函数中，if(3 / 2) = if(1)判断为真，
所以会调用decimal2binary(1) ③
在这个函数中，if(1 / 2) = if(0)判断为假。递归结束。
所以，这里decimal2binary()总共被调用了三次，第一次是在main()中调用的，第二次和第三次都是自己调用自己。
按照递归函数从外到内，再从内到外的执行顺序，这里的执行顺序是①-->②-->③-->②-->①
执行decimal2binary(1)时，因为if不成立，所以跳过if语句，执行printf语句。因为1 % 2 = 1，所以打印出了1。
接着跳出本次递归，继续执行decimal2binary(3)，执行printf语句。因为3 % 2 = 1，所以打印出了1。
接着跳出本次递归，继续执行decimal2bianry(6)，执行printf语句，因为6 % 2 = 0，所以打印出了0。
这时所有的递归都结束了。所以最终打印出来的结果是110
（4）递归调用完全展开的代码为：
// 执行deimal2binary(6)
if(6 / 2) // 6 / 2 = 3, 条件为真
{
// 执行decimal2binary(3)
if(3 / 2) // 3 / 2 = 1, 条件为真
{
// 执行decimal2binary(1)
if(1 / 2) // 1 / 2 = 0, 条件为假
{
// 这里的句子不被执行，所以不再递归
}
printf("%d", 1 % 2); // 打印出1，控制台中可看到“1”
}
printf("%d", 3 % 2); // 打印出1，控制台中可看到“11”
}
printf("%d", 6 % 2); // 打印出0，控制台中可看到“110”，即最终结果
这样，假如不写decimal2bianry函数的话，整个程序可以写成
#include<stdio.h>
int main()
{
int num = 6;
printf("%d转化为二进制：",num);
if(6 / 2) // 条件为真
{
if(3 / 2) // 条件为真
{
if(1 / 2) // 条件为假
{
// 无论什么语句，都不会被执行
}
printf("%d", 1 % 2); // 打印出1，控制台中可看到“1”
}
printf("%d", 3 % 2); // 打印出1，控制台中可看到“11”
}
printf("%d", 6 % 2); // 打印出0，控制台中可看到“110”，即最终结果
return 0;
}
运行结果：
6转化为二进制:110
这里因为6比较小，产生的if语句只有三个，所以像上面这样直接写也不算太麻烦。
但是，假如是一个很大的十进制要转化为二进制，比如500000000，会有很多个if语句，不可能直接在main函数里写这么多if语句。这样就有必要独立写一个decimal2binary函数，让main去调用decimal2binary，decimal2binary再调用自己，几行代码就能搞定，程序看起来就简洁多了。
当然，还可以用for来实现，也会很简单。不过咱们这个程序的另一目的是为了强化学习递归思想。
（5）程序的执行流程图为：
位运算符
位运算符有四个：“与（&）”、“或（|）”、“异或（^）”、“按位取反（~）”。
在了解位运算符之前，请先复习逻辑运算符：
小朋友学C语言（12）：逻辑运算符
位运算,就是对应的bit参与运算,结果是整型数。
逻辑运算，是两个逻辑变量（0或1，非0都算做1)参与运行,结果是逻辑值（0或1）。
（一）位运算符“与”（&）
运算规则：
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0
例1：13 & 6 = 4
与.png
注意：13在计算机里实际占32位，在1101的左边还有28个0，为了表示简便，将左侧的28个0都省略了。
同样，6的二制式形式0100的最左边也有28个0。
编程验证：
#include <stdio.h>
int main()
{
int a = 13;
int b = 6;
int result = a & b;
printf("%d & %d = %d\n", a, b, result);
return 0;
}
运行结果：
13 & 6 = 4
（二）位运算符“或”（|）
运算规则：
1 | 1 = 1
1 | 0 = 1
0 | 1 = 1
0 | 0 = 0
例2：13 | 2 = 15
或.png
程序验证：
#include <stdio.h>
int main()
{
int a = 13;
int b = 2;
printf("%d & %d = %d\n", a, b, a | b);
return 0;
}
运行结果：
13 & 2 = 15
（三）位运算符“异或”（^）
运算规则（相同为0，不同为1）：
1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0
例3：13 ^ 7 = 10
异或.png
验证程序：
#include <stdio.h>
int main()
{
int a = 13;
int b = 7;
printf("%d & %d = %d\n", a, b, a ^ b);
return 0;
}
运行结果：
13 & 7 = 10
（四）位运算符“按位取反”（~）
运算规则：
~1 = 0
~0 = 1
例4：~1 = -2（这里的-1指的是十进制的-1，二进制为00000000 00000000 00000000 00000001）
分析
计算机是以补码的形式存放整数的。
对于正整数来说，原码、反码、补码一样。
对于负整数来说，补码 = 反码 + 1
1的补码是00000000，00000000，00000000，00000001
使用取反运算符后，变为11111111，11111111，11111111，11111110
注意，这是一个补码。最高位是1，表示它是一个负数。
负数的原码 = 补码 - 1，再取反
11111111,11111111,11111111,11111110 - 1 = 111111111,11111111,11111111,11111101
取反（注意符号位不参与取反）后为10000000，00000000，00000000，00000010
这个数即为十进制的-2
#include <stdio.h>
int main()
{
int a = 1;
printf("~%d = %d", a, ~a);
return 0;
}
运行结果：
~1 = -2两数交换
（一）
#include <stdio.h>
int main()
{
int a = 10;
int b = 5;
printf("Before swap: a = %d, b = %d\n", a, b);
int temp = a;
a = b;
b = temp;
printf("After swap: a = %d, b = %d\n", a, b);
return 0;
}
运行结果：
Before swap: a = 10, b = 5
After swap: a = 5, b = 10
分析：temp = a，这里等号表示赋值。左边的temp表示变量，右边的a表示a的值。
只能把一个常量（a的值）赋值给变量（temp）。
不要理解成是把变量a赋值给变量temp。因为变量不能赋值给变量。
temp = a，得到temp = 10
a = b，得到a = 5
b = temp，得到 b = 10
（二）
#include <stdio.h>
int main()
{
int a = 10;
int b = 5;
printf("Before swap: a = %d, b = %d\n", a, b);
a ^= b;
b ^= a;
a ^= b;
printf("After swap: a = %d, b = %d\n", a, b);
return 0;
}
运行结果：
Before swap: a = 10, b = 5
After swap: a = 5, b = 10
分析：请用笔和纸计算下面三个式子的值
a ^= b（等价于a = a ^ b。表示先求a和b的异或结果，再把结果赋值给a。)
b ^= a（等价于b = b ^ a）
a ^= b（等价于a = a ^ b）
（三）
#include <stdio.h>
int main()
{
int a = 10;
int b = 5;
printf("Before swap: a = %d, b = %d\n", a, b);
a = a + b;
b = a - b;
a = a - b;
printf("After swap: a = %d, b = %d\n", a, b);
return 0;
}
运行结果：
Before swap: a = 10, b = 5
After swap: a = 5, b = 10
分析：请口算或用纸笔计算下面三个式子：
a = a + b;
b = a - b;
a = a - b;
（四）注意
如果数很大的话，采用（三）中的方法，a = a + b这一步，有可能发出内存溢出现象
#include <stdio.h>
int main()
{
int a = 2147483647;
int b = 1;
printf("Before swap: a = %d, b = %d\n", a, b);
a = a + b;
printf("After addition: a = %d\n", a);
b = a - b;
a = a - b;
printf("After swap: a = %d, b = %d\n", a, b);
return 0;
}
运行结果：
Before swap: a = 2147483647, b = 1
After addition: a = -2147483648
After swap: a = 1, b = 2147483647
这里a + b得到的竟然是一个负数！这是什么回事呢？
这跟整型的取值范围有关。int类型占4个字节，也就是32位。
最左边那位为符号，0代表正号，1代表负号。
| 二进制 | 十进制 |
|---|---|
| 00000000,00000000,00000000,00000001 | 1 |
| 10000000,00000000,00000000,00000001 | -1 |
| 01111111,11111111,11111111,11111111 | 2147483647 |
| 1111111,11111111,11111111,11111111 | -2147483647 |
| 00000000,00000000,00000000,00000000 | 0 |
| 10000000,00000000,00000000,00000000 | 这是多少呢? |
这里10000000,00000000,00000000,00000000相当于十进制的多少呢？是-0吗？
如果是-0的话，因为0无所谓正负，-0就是0，这会导致计算机里面有两种方式表示0。这是不允许的。那么这个数到底表示多少呢？
事实上，这个数很特殊。最左边的1不仅表示负号，还参与了运算
10000000,00000000,00000000,00000000
= - 2 ^ 31
= - 2147483648
这样，程序中a = a + b得到了负数就好理解了。
接下来因为减掉之后，数变小了，又变回正常的正数了。
从这里可以看出，int类型的取值范围为[-2147483648, 2147483647], 即[-2^31, 2^31-1]
（五）结论
（1）使用（三）中的方法交换两数后，如果数很大的话 ，中间a = a + b有可能得到错误的值，但最终的结果是正确的。
（2）如果数很大的话，比如a = 2147483647; b = 1;a = a + b的期望结果是214748364，但是因为这个数不在int的取值范围内，所以得到了一个负数。这个叫做内存溢出（可联想为：米缸装满了，再也装不进去，继续装的话，米就会溢出来了）。
内存溢出是一种程序漏洞，有可能被黑客所利用并攻击（可联想为：米被老鼠吃了）。
所以，建议不要使用（三）中的方法来交换两个数。
冒泡排序
（一）基本原理（由小到大）：
将相邻两个数比较，将大的调到后头。如果有n个数，则要进行n-1趟比较。
在第1趟中要进行n-1次两两比较，在第j趟比较中要进行n-j次两两比较。
1.png
上图中有5个数，要进行5 - 1 = 4趟比较。
第1趟，要进行n - 1 = 4次两两比较；
第2趟，要进行5 - 2 = 3次两两比较；
第3趟，要进行5 - 3 = 2次两两比较；
第4趟，要进行5 - 4 = 1次两两比较。
（二）代码实现
1 C语言实现
#include <stdio.h>
// 打印数组，方便观察结果
void print_array(int a[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
// 冒泡排序算法
void bubble_sort(int a[], int n)
{
// j表示第几轮比较
for(int j = 0; j < n - 1; j++)
{
// i表示待比较的第几个元素
for(int i = 0; i < n - 1 - j; i++)
{
if(a[i] > a[i+1])
{
a[i] ^= a[i+1];
a[i+1] ^= a[i];
a[i] ^= a[i+1];
}
// 打印每一轮比较，每次交换后的结果
print_array(a, n);
}
printf("********************\n");
}
}
int main ()
{
int a[] = {5, 4, 3, 2, 1};
int count = sizeof(a) / sizeof(int); // 求数组元素个数
bubble_sort(a, count);
return 0;
}
分析：
bubble_sort函数中，有两层循环。外层用j来自增，内层用i来自增。
外层的循环自增的慢，内层的循环自增的快。
内层的循环i要都自增完，外层的j才会自加1。
执行过程为：
j = 0, i = 0, if(a[0] > a[1])为真，a[0]与a[1]交换，数组变为{4,5,3,2,1}
j = 0, i = 1, if(a[1] > a[2])为真，a[1]与a[2]交换，数组变为{4,3,5,2,1}
j = 0, i = 2, if为真，a[2]与a[3]交换，数组变为{4, 3, 2, 5, 1}
j = 0, i = 3, if为真，a[3]与a[4]交换，数组变为{4, 3, 2, 1, 5}，
此时最大的5已经挪到最后的位置，接下来5就不用再处理。
j = 1, i = 0, if为真，a[0]与a[1]交换，数组变为{3, 4, 2, 1, 5}
j = 1, i = 1, if为真，a[1]与a[2]交换，数组变为{3, 2, 4, 1, 5}
j = 1, i = 2, if为真，a[2]与a[3]交换，数组变为{3, 2, 1, 4, 5}，
此时4已经挪到倒数第二个位置，接下来4和5就不用再处理。
j = 2, i = 0, if为真，a[0]与a[1]交换，数组变为{2, 3, 1, 4, 5}
j = 2, i = 1, if为真，a[1]与a[2]交换，数组变为{2, 1, 3, 4, 5}，
此时3已经挪到倒数第三个位置，接下来3、4和5就不用再处理。
j = 3, i = 0, if为真，a[0]与a[1]交换，数组变为{1, 2, 3, 4, 5}，
此时2已经挪到倒数第四个位置，接下来2、3、4和5就不用再处理。
剩余一个数1，也不用交换了。至此排序完毕。
输出结果：
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
********************
3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
********************
2 3 1 4 5
2 1 3 4 5
********************
1 2 3 4 5
********************选择排序
（一）基本原理（由小到大）：
如果有n个数，需要比较n-1轮：
第1轮，将n个数中最小的数与a[0]对换，当然若a[0]就是最小的数则不用对换。
第2轮，将a[1]到a[n-1]中最小的数与a[1]对换，当然若a[1]就是最小的数则不用对换。
……
第n-1轮，将最后的两个数，即a[n-2]与a[n-1]比较，若a[n-2] > a[n-1]，则对换。至此，排序完毕。
（二）例子
例1：a[] = {5, 1, 2, 3, 4}
分析 ：需要比较n - 1 = 4轮。
第1轮，a[1]=1是5个元素中最小的，并且a[1]不等于a[0]，则对换a[1]与a[0]。对换后数组变为a[] = {1,5,2,3,4}
第2轮，对于a[]的后四个元素来说，a[2]=2是最小的，并且a[2]不等于a[1]，则对换a[2]与a[1]。对换后数组变为a[] = {1, 2, 5, 3, 4}
第3轮，对于a[]的后三个元素来说，a[3]=3是最小的，并且a[3]不等于a[2]，则对换a[3]与a[2]。对换后数组变为a[] = {1, 2, 3, 5, 4}
第4轮，对于a[]的最后两个元素来说，a[4]=4是最小的，并且a[4]不等于a[3]，则对换a[4]与a[3]。对换后数组变为a[] = {1, 2, 3, 4, 5}
至此，排序结束。
1.png
例2：b[] = {1, 3, 5, 4, 2, 6}
分析：需要比较n - 1 = 5轮。
第1轮，b[0]就是六个元素中最小的数，不用对换。
第2轮，对于后五个元素来说，b[4] = 2是最小的数，b[4]不等于b[1]，则对换b[4]和b[1]，对换后，数组变为b = {1, 2, 5, 4, 3, 6}。
第3轮，对于后四个元素来说，b[4] = 3是最小的数，b[4]不等于b[2]，则对换b[4]和b[2]，对换后，数组变为b = {1, 2, 3, 4, 5, 6}。
第4轮，对于后三个元素来说，b[3] = 4是最小的数，不用对换。
第5轮，对于最后两个元素来说，b[4] = 5是最小的数，不用对换。至此排序结束。
2.png
（三）编程实现
#include<stdio.h>
// 打印数组，方便观察结果
void print_array(int a[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
// 选择排序算法
void select_sort(int a[],int n)
{
int i, j, min;
// i代表比较的轮数，i的取值范围是0到n-2，共n-1轮
for(i = 0; i < n - 1; i++)
{
/* min表示本轮比较中，最小元素的下标。
这里先赋值为i，也就是本轮比较的首个元素所在的位置。
下面根据比较结果，有可能变化，也有可能不变。*/
min = i;
// a[i]右侧的所有元素都与a[i]比较
for(j = i + 1; j < n; j++)
{
// 若发现有更小的数，把该数的下标赋值给min
// min在这个循环里可能会不断变化，最后会停在最小数所在的下标
if(a[j] < a[min])
{
min = j;
}
}
// 如果min与i不相等，说明a[i]右侧有比a[i]更小的数（可能不止一个）
// 则a[min]就是a[i]右侧最小的数，将a[i]与a[min]互换位置
if(min != i)
{
a[min] ^= a[i];
a[i] ^= a[min];
a[min] ^= a[i];
}
printf("After %d round sort, the array is:", i + 1);
print_array(a, n);
}
}
int main()
{
int b[] = {5, 1, 2, 3, 4};
int cnt = sizeof(b) / sizeof(int);
select_sort(b, cnt);
return 0;
}
运行结果：
After 1 round sort, the array is:1 5 2 3 4
After 2 round sort, the array is:1 2 5 3 4
After 3 round sort, the array is:1 2 3 5 4
After 4 round sort, the array is:1 2 3 4 5
（四）程序分析：
n - 1 = 4轮比较中，共产生了十次循环。分别是
i = 0, j = 1
i = 0, j = 2
i = 0, j = 3
i = 0, j = 4
i = 1, j = 2
i = 1, j = 3
i = 1, j = 4
i = 2, j = 3
i = 2, j = 4
i = 3, j = 4
具体执行如下：
i = 0, min = 0
j = 1, 第一个if成立，min = 1
j = 2, 第一个if不成立，min仍然为1
j = 3, 第一个if不成立，min仍然为1。
j = 4, 第一个if不成立，min仍然为1。内循环结束，跳出内循环 。第二个if成立，a[0]与a[min]（即a[1]）对换，数组变为{1, 5, 2, 3, 4}
i = 1, min = 1
j = 2, 第一个if成立，min = 2
j = 3, 第一个if不成立，min仍然为2。
j = 4, 第一个if不成立，min仍然为2。内循环结束，跳出内循环 。第二个if成立，a[1]与a[min]（即a[2]）对换，数组变为{1, 2, 5, 3, 4}
i = 2, min = 2
j = 3, 第一个if成立，min = 3
j = 4, 第一个if不成立，min仍然为3。内循环结束，跳出内循环 。第二个if成立，a[2]与a[min]（即a[3]）对换，数组变为{1, 2, 3, 5, 4}
i = 3, min = 3
j = 4, 第一个if成立，min = 4。内循环结束，跳出内循环 。第二个if成立，a[3]与a[min]（即a[4]）对换，数组变为{1, 2, 3, 4, 5}
至此，外循环结束，跳出外循环，继续执行下面的代码。
指针
（一）内存地址
#include <stdio.h>
int main()
{
int var1 = 20;
printf("变量var1的值为：%d\n", var1);
printf("变量var1的内存地址为：%p\n", &var1);
return 0;
}
运行结果：
变量var1的值为：20
变量var1的内存地址为：0x7ffd7ed6060c
这里20这个值是放在内存中地址为7ffd7ed6060c的空间中，0x是代表十六进制的意思。
1.png
（二）指针
指针是一个变量，其值为另一个变量的地址，即，内存位置的直接地址。就像其他变量或常量一样，您必须在使用指针存储其他变量地址之前，对其进行声明。
#include <stdio.h>
int main ()
{
int var = 20; /* 变量var的声明 */
int *p; /* 指针变量p的声明 */
p = &var; /* 在指针变量中存储 var 的地址，也就是给指针变量赋值 */
/* var在内存中的地址 */
printf("Address of var: %p\n", &var );
/* 在指针变量中存储的地址 */
printf("Address stored in p: %p\n", p );
/* 指针本身在内存中的地址 */
printf("Address of p: %p\n", &p);
/* 使用变量访问值 */
printf("var = %d\n", var);
/* 使用指针访问值 */
printf("*p = %d\n", *p );局部变量和全局变量
（一）局部变量
在某个函数或块的内部声明的变量称为局部变量。它们只能被该函数或该代码块内部的语句使用。局部变量在函数外部是不可知的。下面是使用局部变量的实例。在这里，所有的变量 a、b 和 c 是 main() 函数的局部变量。
例1：
#include <stdio.h>
int main ()
{
/* 局部变量声明 */
int a, b;
int c;
/* 实际初始化 */
a = 5;
b = 10;
c = a + b;
printf ("a = %d, b = %d and c = %d\n", a, b, c);
return 0;
}
运行结果：
a = 5, b = 10 and c = 15
（二）全局变量
全局变量是定义在函数外部，通常是在程序的顶部。全局变量在整个程序生命周期内都是有效的，在任意的函数内部能访问全局变量。
全局变量可以被任何函数访问。也就是说，全局变量在声明后整个程序中都是可用的。
例2：
#include <stdio.h>
/* 全局变量声明 */
int g;
int main ()
{
/* 局部变量声明 */
int a, b;
/* 实际初始化 */
a = 5;
b = 10;
g = a + b;
printf ("a = %d, b = %d and g = %d\n", a, b, g);
return 0;
}
运行结果：
a = 5, b = 10 and g = 15
（三）局部变量覆盖全局变量
在程序中，局部变量和全局变量的名称可以相同，但是在函数内，局部变量的值会覆盖全局变量的值。
例3：
#include <stdio.h>
/* 全局变量声明 */
int g = 50;
int main ()
{
printf ("g = %d\n", g);
printf("内存地址:%p\n", &g);
/* 局部变量声明并初始化 */
int g = 8;
printf ("g = %d\n", g);
printf("内存地址:%p", &g);
return 0;
}
运行结果：
g = 50
内存地址:0x601040
g = 8
内存地址:0x7ffcc207febc递归解决汉诺塔
（一）汉诺塔介绍
汉诺塔（Hanoi Tower）问题是源于印度一个古老传说：
在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
考虑一下把64片金片，由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢?这里需要递归的方法。假设有n片，移动次数是f(n).显然f(1)=1,f(2)=3,f(3)=7，且f(k+1)=2*f(k)+1。此后不难证明f(n)=2^n-1。
n=64时，假如每秒钟移动一次，共需多长时间呢？
2 ^ 64 - 1 = 18446744073709551615秒!
一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒。
这表明移完这些金片需要5845.54亿年以上。而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845.54亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭！
（二）训练
在纸上画出n = 1, n = 2, n = 3, n = 4时的挪动步骤
（三）算法思想
hanoi.jpg
将圆盘编号按从上到下的顺序表示为1，2，3……，n-1，n。
把所有的盘子分成两部分：上面的n-1个，第n个圆盘（即最下面的那个）。
（1）把上面的n-1个圆盘从柱子A移动到柱子B上，这一过程需要借助柱子C。
（2）把第n个圆盘从柱子A移动到柱子C上。这样第n个圆盘就放到了目标位置上。
（3）把上面的n-1个圆盘从柱子B移动到柱子C上，这一过程需要借助柱子A。
这里（1）用到了递归，可以拆分成很多个步骤（1）、（2）、（3），当n为1时递归结束。
同理（3）也用到了递归，可以拆分成很多个步骤（1）、（2）、（3），当n为1时递归结束。
（四）例子
例1：n = 2
要把两个盘子从A挪到C。分成三步：
（1）把上面那个盘子从A挪到B，需要1步
（2）把下面那个盘子从A挪到C，需要1步
（3）把上面那个盘子从B挪到C，需要1步
这样，两个盘子都从A挪到C上面了，任务完成！共需要1 + 1 + 1 = 3步。
例2：n =3
要把三个盘子从A挪到C。分成三大步：
（1）把上面两个盘子从A挪到B，需要3步
（2）把最下面那个盘子从A挪到C，需要1步
（3）把上面两个盘子从B挪到C，需要3步
这样，三个盘子都从A挪到C上面了，任务完成！共需要3 + 1 + 3 = 7步。
例3：n = 4
要把四个盘子从A都挪到C。分成三大步：
（1）把上面三个盘子从A挪到B，需要7步（具体可分为３步+1步+3步；3步又可以分为1步+1步+１步，这就是递归）
（2）把最下面那个盘子从A挪到C，需要1步
（3）把上面三个盘子从B移到C，需要7步
这样，四个盘子都挪到C上面了，任务完成！共需要7 + 1 + 7 = 15步。
例4：n = 5
要把五个盘子从A都挪到C。分成三大步：
（1）把上面四个盘子从A挪到B，需要15步
（2）把最下面那个盘子从A挪到C，需要1步
（3）把上面四个盘子从B移到C，需要15步
这样，五个盘子都挪到C上面了，任务完成！共需要15 + 1 + 15 = 31步。
（五）C语言实现
#include <stdio.h>
void hanoi(int n, char pillar1, char pillar2, char pillar3); // 函数声明
void move(int n, char pillar_from, char pillar_to); // 函数声明
int count; // 全局变量
int main()
{
int n;
// 输入汉诺塔层数（即金片数量）
printf("Please input the layer number of Hanoi Tower: ");
scanf("%d",&n);
// 目的：借助于B，把n个金片从A移动到C
hanoi(n, 'A', 'B', 'C');
return 0;
}
void hanoi(int n, char pillar1, char pillar2, char pillar3)
{
// 递归终止条件
if (n == 1)
{
move(n, pillar1, pillar3);
}
else
{
// 借助于pillar3，把上面的n-1个金片从pillar1移动到pillar2
hanoi(n - 1, pillar1, pillar3, pillar2);
// 把最下面的第n个金片从pillar1移动到pillar3
move(n, pillar1, pillar3);
// 借助于pillar1，把上面的n-1个金片从pillar2移动到pillar3
hanoi(n - 1, pillar2, pillar1, pillar3);
}
}
void move(int n, char pillar_from, char pillar_to)
{
count++; // 统计移动次数
printf("step %d: move layer %d, %c --> %c\n", count, n, pillar_from, pillar_to);
}
运行结果：
Please input the layer number of Hanoi Tower: 1
step 1: move layer 1, A-->C
Please input the layer number of Hanoi Tower: 2
step 1: move layer 1, A-->B
step 2: move layer 2, A-->C
step 3: move layer 1, B-->C
Please input the layer number of Hanoi Tower: 3
step 1: move layer 1, A-->C
step 2: move layer 2, A-->B
step 3: move layer 1, C-->B
step 4: move layer 3, A-->C
step 5: move layer 1, B-->A
step 6: move layer 2, B-->C
step 7: move layer 1, A-->C
说明：include的下面两行，分别是两个函数的声明。
为什么需要函数声明呢？因为编译器读取程序的时候，是从上到下读的，在main()函数中调用了这两个函数。但是编译器在调用的时候还不知道这两个函数是在哪里定义的。所以需要在main()函数的上方进行声明，告诉编译器“有这个东西，稍后会给出定义”。就是提前打招呼的意思。
以前那些课程，为什么都不需要函数声明呢？那是因为以前的所有程序，都把被调用的函数写到了main()函数的上方。编译器先读取被调用的函数，再读取main()函数，调用时已经知道之前有定义过，所以就不需要先声明了。
关注微信公众号请扫二维码