大连理工大学 盘锦校区基础教学部
12
第十讲——数组、冒泡排序
数组初始化
3. 在对全部元素赋初值时，可以不指定数组长度； 例： double a[5] = {0.0, 1.0, 2.0, 3.0, 4.0}; 可以写成： double a[] = {0.0, 1.0, 2.0, 3.0, 4.0};
注意：后者，{}中有 5 个数，系统会自动定义数组a 的长度为5；但若定义的数组长度与提供初值个数不相 同，则数组长度不能省略；
大连理工大学 盘锦校区基础教学部
13
第十讲——数组、冒泡排序
数组初始化
注意： int array1[5] int array2[5] int array3[5] int array4[5]
大连理工大学 盘锦校区基础教学部
29
第十讲——数组、冒泡排
序
冒泡排序程序
// 外层循环 // 内层循环
大连理工大学 盘锦校区基础教学部
30
第十讲——数组、冒泡排序
数据交换
数据交换分析：
tmp = array[i]; array[i] = array[i+1]; array[i+1] = tmp; 考虑问题：用函数实现数据交换？
大连理工大学 盘锦校区基础教学部
17
第十讲——数组、冒泡排序
数组应用例子
大连理工大学 盘锦校区基础教学部
18
第十讲——数组、冒泡排序
数组应用例子
大连理工大学 盘锦校区基础教学部
19
第十讲——数组、冒泡排序
数组应用例子
切一刀
切二刀
切三刀
ቤተ መጻሕፍቲ ባይዱ
切四刀
令 q(n) 表示切 n 刀能分成的块数，由上图可知
q(1) = 1 + 1 = 2 q(2) = 1 + 1 + 2 = 4 q(3) = 1 + 1 + 2 + 3 = 7 q(4) = 1 + 1 + 2 + 3 + 4 = 11
a
a 00 a 10 a 20
a a a
0 1
1 1
2 1
a 12 a 22 a
0 2
例： int m1[4][5];
float m2[3][3];
大连理工大学 盘锦校区基础教学部
35
第十讲——数组、冒泡排序
注意：a[i] 表示第i行元素的首地址； 例： a[i] 的值 与 & a[i][0]的值相同； int a[3][4]; 看成一维数组：
《C++语言程序设计》
第十讲 数组、冒泡排序
第十讲——数组、冒泡排序
数组 数组： 1. 用一个统一的名字代表一批数据，而用序号或 下标来区分各个数据； 2. 有序数据的集合；
大连理工大学 盘锦校区基础教学部
2
第十讲——数组、冒泡排序
数组 1. 数组是有类型的； 2. 同一数组中的每一个元素都必须是同一数据类型； 3. 数组在内存中占一片连续的内存单元；
第十讲——数组、冒泡排序
i=4 a[4] 8 8 8 8 8 8 8 8
i=5 a[5] 9 9 9 9 9 9 9 9 j=5
26
j=3
j=4
大连理工大学 盘锦校区基础教学部
第十讲——数组、冒泡排序
冒泡排序算法分析
从表中可以看出最大的一个数第一遍扫描就交换到a[5]中。如 果将a[0]视为水面，a[5]视为水底： 最重的（最大的）一个数 9 最先沉到水底，交换到a[5]; 次重的 8 第二遍扫描交换到 a[4]; 再重的 5 第三遍扫描交换到 a[3]; … 依此类推，有 6 个数，后 5 个数到位需 5 遍扫描，第 6 个 最轻的自然落在 a[0] 中。因此，6 个数只需 5 遍扫描，令扫 描遍数为 j, j = n – j, n = 6。
= = = =
{1,2,3,4,5,6}; // 错：初始值个数太多 {1,,2,3,4}; // 错：不能以逗号方式省略 {1,2,3,}; // 错：不能以逗号方式省略 // 错：初始值不能为空 {};
int array5[5] = {1,2,3}; // 可以 // 可以 int array6[5] = {0};
大连理工大学 盘锦校区基础教学部
20
第十讲——数组、冒泡排序
分析：
切一刀
切二刀
切三刀
切四刀
在切法上是让每两条线都有交点。用归纳法可得出 q(n) = q(n-1) + n
q(0) = 1 (边界条件)
大连理工大学 盘锦校区基础教学部
21
第十讲——数组、冒泡排序
数组应用例子
参考程序：
大连理工大学 盘锦校区基础教学部
若：
int a[5]; // 定义 则 a 的值，与 &a[0] 的值相同；
同理，a + 1 的值，和 &a[1] 的值相同；都指向a[1]
大连理工大学 盘锦校区基础教学部
34
第十讲——数组、冒泡排序
二维数组
二维数组定义的一般形式： 类型名 数组名[常量表达式][常量表达式]
例:
int a[3][3]
第十讲——数组、冒泡排序
i=4 a[4] 2 2 2 2 2 9 0 0 0 0 0
i=5 a[5] 0 0 0 0 0 0 9 9 9 9 9 j=2
25
j=1
2 2 4 大连理工大学 盘锦校区基础教学部 2 8 4 8 4 2
冒泡排序法
i=0 a[0] 中间结果 5>4; 5,4 互换 5>2; 5, 2 互换 5>0; 5, 0 互换 5 到达位置 4>2; 4, 2互换 4>0; 4, 0互换 4 到达位置 5 5 4 4 4 4 2 2 i=1 a[1] 4 4 5 2 2 2 4 0 i=2 i=3 a[2] a[3] 2 2 2 5 0 0 0 4 0 0 0 0 5 5 5 5
大连理工大学 盘锦校区基础教学部
15
第十讲——数组、冒泡排序
数组应用
注意： 数组下标，从 0 开始； 例： double array[4];
其中的元素为： array[0], array[1],array[2],array[3]
大连理工大学 盘锦校区基础教学部
16
第十讲——数组、冒泡排序
数组使用例子
地址传递函数
再考虑： void swap(int *px, int *py) // 形参为指针变量 { int tmp = *px; *px = *py; *py = tmp; }
大连理工大学 盘锦校区基础教学部
33
第十讲——数组、冒泡排序
数组名与指针的关系
数组名字是地址常量；值 等价于 数组首元素地址；
大连理工大学 盘锦校区基础教学部
3
第十讲——数组、冒泡排序
数组定义
定义一维数组的一般格式为：
类型名 数组名[常量表达式]；
例如：
float sheep[10]; 它表示数组名为 sheep, 且类型为实型，有 10 个元 素；
大连理工大学 盘锦校区基础教学部
4
第十讲——数组、冒泡排序
数组定义
例如： 类型名 数组名[常量表达式]
例： int n; n = 5; int a[n]; // 不合法
因为 n 是变量，不是常量
大连理工大学 盘锦校区基础教学部
9
第十讲——数组、冒泡排序
数组定义说明 #define N 100 #define M 200 int a[N]; long b[N+M]; // // // // 宏定义，N为常数 100 宏定义，M为常数200 定义有100个元素的整型数组a 定义有300个元素的长整型数组b
大连理工大学 盘锦校区基础教学部
6
第十讲——数组、冒泡排序
数组定义说明
3. 数组下标从 0 开始。如果定义 5 个元素，是从 0 个元素至第 4 个元素；
a 下标 0
1
2
3
4
例：
int a[5] 定义了 5 个数组元素如下：
a[0], a[1], a[2], a[3], a[4]
这是 5 个带下标的变量，这 5 个变量的类型是相同的
22
第五章——车身抗撞性
冒泡排序法 8 a 下标 0 9 1 5 2 4 3 2 4 0 5
希望排成： 0 2 a 下标 0 1
4
5 3
8 4
9 5
2
23
第十讲——数组、冒泡排序
冒泡排序法
问题： 将几个数从小到大排序并输出
大连理工大学 盘锦校区基础教学部
24
冒泡排序法
i=0 a[0] 初始值 8<9; 顺序不动 9>5; 9, 5 互换 9>4; 9, 4 互换 9>2; 9, 2 互换 9>1; 9, 0 互换 9 到达位置 8>5; 8, 5互换 8>4; 8, 4互换 8>2; 8, 2互换 8>0; 8, 0互换 8 8 8 8 8 8 8 8 5 5 5 i=1 a[1] 9 9 9 5 5 5 5 5 8 i=2 i=3 a[2] a[3] 5 5 5 9 4 4 4 4 4 4 4 4 9 2 2
11
第十讲——数组、冒泡排序
数组初始化
2. 只给一部分元素赋值 例： float a[10] = {0.0, 1.0};
定义数组 a 有 10 个元素，但花括号内只提供 2 个 初值，这表示只给前面 2 个元素赋初值，后 8 个元 素值默认为 0； // a[0] = 0.0; a[1] = 1.0; a[2] ~ a[9] 均为 0；