05 第五章 数组.pptx

第1页：第五章数组导览

第五章数组章节封面，标示本章主线：概述、一维数组、多维数组与字符数组。

第2页：引入数组的示例

例：给出10个儿童的体重，求平均体重并打印低于平均体重的数值

用10个独立变量 w1~w10 需要写10次 scanf 和10次判断，代码冗长；改用数组后可用循环统一处理。

#include <stdio.h> #define SIZE 10 main() { int w[SIZE]; int t = 0, i; for (i = 0; i < SIZE; i++) scanf("%d", &w[i]); for (i = 0; i < SIZE; i++) t += w[i]; t = t / 10; for (i = 0; i < SIZE; i++) if (w[i] < t) printf("%d\n", w[i]); }

第3页：数组的概念

数组：构造数据类型之一，是一组有序的、类型相同的数据的集合，用数组名标识；元素属同一数据类型，用数组名和下标确定。

第4页：一维数组的定义

一维数组定义：数据类型 数组名[常量表达式];

• [ ] 是数组运算符，单目运算符，优先级(1)，左结合
• 不能用 ( )；数组名须为合法标识符；常量表达式表示元素个数，下标从0开始
• 例：int a[6]; 编译时分配连续内存，内存字节数 = 数组维数 * sizeof(元素类型)
• 数组名表示内存首地址，是地址常量，等价于 &a[0]
• 不能用变量定义数组维数：int i=15; int data[i]; 为非法
• C语言不对数组作越界检查，data[5]=10 越界使用需自行避免

第5页：一维数组的引用

一维数组引用：

• 数组必须先定义，后使用
• 只能逐个引用数组元素，不能一次引用整个数组
• 数组元素表示形式：数组名[下标]
• 例：int a[10]; printf("%d", a); 是错误的，应改为循环逐个输出 a[i]

数组元素在功能上等价于一个一般的变量， toddlers 可以参与各类运算。

第6页：一维数组的初始化

一维数组初始化：在定义数组时为数组元素赋初值。

• 数组不初始化，其元素值为随机数
• static 数组若不初始化，系统自动赋0值
• 当全部数组元素赋初值时，可不指定数组长度：int a[]={1,2,3,4,5,6}; 由编译系统据初值个数确定维数
• 部分初始化：不足的后续元素自动初始化成0，int a[5]={6,2,3}; 得 6,2,3,0,0
• 初值个数超过数组长度非法：int a[3]={6,2,3,5,1};

第7页：数组初始化的常见错误

数组定义中的常见错误：

int a[5]; a = {2, 4, 6, 8, 10}; char name[0]; float weight[10.3]; int array[-100]; 

合法示例：#define N 6 后 int a[N], b['B'-60], c[]={1,2,3,4,5,6};

第8页：求十个整数最值

例：找10个整数的最大值和最小值

步骤：1、输入；2、处理：初值 max=min=x[0]，循环比较，若 max<x[i] 则 max=x[i]，若 min>x[i] 则 min=x[i]；3、输出 max 与 min。

#include <stdio.h> #define SIZE 10 main() { int x[SIZE], i, max, min; printf("Enter 10 integers:\n"); for (i = 0; i < SIZE; i++) { printf("%d:", i + 1); scanf("%d", &x[i]); } max = min = x[0]; for (i = 1; i < SIZE; i++) { if (max < x[i]) max = x[i]; if (min > x[i]) min = x[i]; } printf("Maximum value is %d\n", max); printf("Minimum value is %d\n", min); }

第9页：用数组求Fibonacci数列

例：求 Fibonacci 数列前20个数

数列：1，1，2，3，5，8，… 递推式 f[i]=f[i-2]+f[i-1]。

#include <stdio.h> main() { int i; int f[20] = {1, 1}; for (i = 2; i < 20; i++) f[i] = f[i-2] + f[i-1]; for (i = 0; i < 20; i++) { if (i % 5 == 0) printf("\n"); printf("%6d", f[i]); } }

第10页：顺序查找示意

顺序查找 Linear search：数组 a 的元素为 3, 12, -5, 6, 142, 21, -17, 45，从下标0开始逐个与待查值比较。

查找 21：从 a[0] 起依次比较，遇到 a[5]=21 时匹配成功，输出 Found it。

第11页：顺序查找失败情况

顺序查找（查找失败）：查找 20 时，从 a[0] 一直比较到 a[N-1]，都不相等，指针越出数组末尾，输出 Not found。

顺序查找的平均比较次数为 (N+1)/2，时间复杂度 O(n)。

第12页：顺序查找程序

顺序查找程序

#include <stdio.h> #define N 8 main() { int a[N] = {3, 12, -5, 6, 142, 21, -17, 45}; int i = 0, x = 21; while (a[i] != x && i < N) i++; if (i < N) printf("Found it!"); else printf("Not found!"); }

循环条件中 i<N 防止数组越界。思考：能否做得更好？——有序表可用折半查找。

第13页：折半查找算法

折半查找 Binary search

适用条件

采用数组存储的有序表

查找过程

每次将待查记录所在区间缩小一半

1. 数组 r 长 n，low、high、mid 分别指向待查区间的下界、上界和中点，k 为给定值
2. 初始令 low=1，high=n，mid=(low+high)/2
3. 让 k 与 r[mid] 比较：k==r[mid] 查找成功；k<r[mid] 则 high=mid-1；k>r[mid] 则 low=mid+1
4. 重复上述操作，直至 low>high 时查找失败

第14页：折半查找成功示例

折半查找：找 37

下标: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 元素: 5 13 19 21 37 56 64 75 80 88 92 100 111 120 125 low high mid

初始 low=0，high=14，mid=7（元素75）；37<75 故 high=mid-1；再取 mid=3（元素21），37>21 故 low=mid+1；再取 mid=5（元素56），继续缩小区间后命中 37，输出 Found it。

第15页：折半查找失败示例

折半查找：找 90

下标: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 元素: 5 13 19 21 37 56 64 75 80 88 92 100 111 120 125 low high mid

反复折半后区间缩小到 low>high，仍未出现 90，输出 Not found!。折半查找时间复杂度为 O(log₂n)。

第16页：折半查找程序

折半查找程序

#include <stdio.h> #define N 10 int r[N], low, high, mid, k; printf("Input 10 sorted numbers:\n"); for (k = 0; k < N; k++) scanf("%d", &r[k]); printf("Input number k:\n"); scanf("%d", &k); low = 0; high = N - 1; while (low <= high) { mid = (low + high) / 2; if (k > r[mid]) low = mid + 1; else if (k < r[mid]) high = mid - 1; else { printf("%d\n", mid); break; } } if (low > high) printf("Search Failure.\n");

第17页：冒泡法排序思想

冒泡排序 Bubble Sort

排序过程：

1. 比较第一个数与第二个数，若为逆序 a[0]>a[1] 则交换；再比较第二个与第三个；依次类推至第 n-1 与第 n 个数——第一趟冒泡排序，结果最大的数被安置在最后一个元素位置上
2. 对前 n-1 个数进行第二趟冒泡排序，结果使次大的数被安置在第 n-1 个元素位置
3. 重复上述过程，最多经过 n-1 趟冒泡排序后排序结束

第18页：冒泡排序过程演示

冒泡排序过程演示：7个元素经过第一趟、第二趟……第六趟起泡排序，每趟结束后当前未排定部分的最大元素沉到本趟末尾，小的元素象气泡一样上浮，最多 N-1 趟。

第19页：冒泡排序程序

冒泡排序程序（输入N个整数存于 a[0]~a[N-1]，排序后输出）

#include <stdio.h> #define N 7 main() { int a[N], i, k, t; printf("Input %d numbers:\n", N); for (i = 0; i < N; i++) scanf("%d", &a[i]); for (k = 1; k <= N - 1; k++) for (i = 0; i <= N - k - 1; i++) if (a[i] > a[i+1]) { t = a[i]; a[i] = a[i+1]; a[i+1] = t; } for (i = 0; i < N; i++) printf("%d ", a[i]); }

第20页：冒泡排序的改进

冒泡排序的结束条件改进：若在某一趟排序过程中没有进行「交换记录」操作，则整个排序结束。

流程图中在每趟开始前把标志置为「无交换」，一旦发生交换则修改标志，趟循环条件变为「k<=N-1 且 发生过交换」。

第21页：冒泡排序改进版程序

#include <stdio.h> #define N 7 main() { int a[N], i, k, t; int flag = 1; printf("Input %d numbers:\n", N); for (i = 0; i < N; i++) scanf("%d", &a[i]); for (k = 1; k <= N - 1 && flag == 1; k++) { flag = 0; for (i = 0; i <= N - k - 1; i++) if (a[i] > a[i+1]) { t = a[i]; a[i] = a[i+1]; a[i+1] = t; flag = 1; } } for (i = 0; i < N; i++) printf("%d ", a[i]); }

第22页：选择法排序思想

选择排序 Selection Sort

排序过程：

1. 首先通过 N-1 次比较，从 N 个数中找出最小的，将它与第一个数交换——第一趟选择排序，结果最小的数被安置在第一个元素位置上
2. 再通过 N-2 次比较，从剩余的 N-1 个数中找出关键字次小的记录，将它与第二个数交换——第二趟选择排序
3. 重复上述过程，共经过 N-1 趟排序后排序结束

第23页：选择排序过程示例

简单选择排序过程示例：初始关键字序列 34 49 28 31 52 51 12，每趟在未排序部分用 k 记录最小元素下标，趟末与 i 位置交换。

初始: 34 49 28 31 52 51 12 第一趟: 12 49 28 31 52 51 34 第二趟: 12 28 49 31 52 51 34 第三趟: 12 28 31 49 52 51 34 第四趟: 12 28 31 34 52 51 49 第五趟: 12 28 31 34 49 51 52 第六趟: 12 28 31 34 49 51 52

共 n-1 趟完成排序。

第24页：选择排序程序

选择排序程序

#include <stdio.h> #define N 7 main() { int a[N], i, j, k, t; printf("Input numbers:\n"); for (i = 0; i < N; i++) scanf("%d", &a[i]); for (i = 0; i < N - 1; i++) { k = i; for (j = i + 1; j < N; j++) if (a[j] < a[k]) k = j; if (i != k) { t = a[i]; a[i] = a[k]; a[k] = t; } } printf("The sorted numbers:\n"); for (i = 0; i < N; i++) printf("%d ", a[i]); }

第25页：二维数组的定义与存储

二维数组定义：数据类型 数组名[常量表达式][常量表达式];

• 元素个数 = 行数 * 列数；例 int a[3][4]; float b[2][5]; int c[2][3][4];
• 不能写成 int a[3,4];
• 元素存放顺序：内存是一维的，二维数组按行序优先，多维数组最右下标变化最快

例：int a[3][2] 的存储顺序为 a[0][0]、a[0][1]、a[1][0]、a[1][1]、a[2][0]、a[2][1]。

第26页：二维数组的理解

二维数组理解：int a[3][4]; 中 a[0]、a[1]、a[2] 分别是3个长度为4的一维数组；int c[2][3][4] 由 2×3 个长度为4的一维数组组成。

a 是由3个一维数组组成的数组，下标从0起，引用形式为 数组名[行下标][列下标]。

第27页：二维数组初始化

二维数组元素的初始化

• 分行初始化：int a[2][3]={{1,2,3},{4,5,6}}; 可部分初始化 int a[2][3]={{1,2},{4}}; 得 1 2 0 / 4 0 0
• 按元素存储顺序初始化：int a[2][3]={1,2,3,4,5,6};；部分初始化 int a[2][3]={1,2,4}; 得 1 2 4 / 0 0 0
• 第一维长度可缺省：int a[][3]={1,2,3,4,5}、int a[][3]={{1},{4,5}}
• 三维数组：int c[2][3][4]={{{1,2,3,4},{2,3,4,5},{3,4,5,6}},{{4,5,6,7},{5,6,7,8},{6,7,8,9}}};

第28页：二维数组初始化的易错对比

易错对比：

int a[2][3]={{5,6},{7,8}}; int a[2][3]={5,6,7,8}; 

非法写法：int a[][10]; 未初始化且缺省第一维；double f[2][]={1.2,2.2}; 第二维不可缺省。数组初始化时只有第一维长度可缺省。

第29页：求二维数组最大元素

例：求二维数组中最大元素值及其行列号

#include <stdio.h> main() { int a[3][4]={{1,2,3,4},{9,8,7,6},{-10,10,-5,2}}; int i, j, row=0, colum=0, max; max = a[0][0]; for (i = 0; i <= 2; i++) for (j = 0; j <= 3; j++) if (a[i][j] > max) { max = a[i][j]; row = i; colum = j; } printf("max=%d,row=%d,colum=%d\n", max, row, colum); }

输出：max=10,row=2,colum=1

第30页：三个学生四门课成绩表

例：统计三个学生四门课程的总分和平均分

定义 #define S 3、#define C 4，用 int a[S+2][C+2] 存放个人总分、单科总分与平均分。

第31页：字符数组的定义与初始化

字符数组：定义 char c[10], ch[3][4];；初始化可分逐个字符赋值与用字符串常量两种方式。

• char ch[6]={"Hello"}; 等价 char ch[6]="Hello"; 等价 char ch[]="Hello";（自动加 '\0'）
• char ch[5]={'B','o','y'}; 得 B o y \0 \0
• char ch[5]={'H','e','l','l','o'}; 存满5个字符，没有 '\0' 结束符，作为字符串使用会有问题
• char str[]="Hello"; 与 char str[]={'H','e','l','l','o'}; 占用字节数不同，前者6字节

第32页：二维字符数组初始化

二维字符数组初始化

char color[][5]={{'R','e','d'},{'B','l','u','e'}, {'G','r','e','e','n'},{'C','y','a','n'}, {'B','l','a','c','k'}};

用字符串常量更简洁：

char fruit[][7]={"Apple","Orange","Grape","Pear","Peach"};

每行按下标 fruit[0]~fruit[4] 存放，不足部分补 '\0'。

第33页：字符串与结束标志

字符串：

• C语言无字符串变量，用字符数组处理字符串
• 字符串结束标志：'\0'

例：字符串 "hello" 在内存中为 h e l l o \0，对应 ASCII 码 104 101 108 108 111 0，共占6字节。

第34页：字符串的输入输出

字符串输入输出

• 逐个字符 I/O：%c，用循环逐个 scanf 与 printf
• 整个字符串 I/O：%s，scanf("%s", str); 要求用字符数组名作地址，不加 &；输入串长度必须小于数组维数；遇空格或回车结束，自动加 '\0'
• 输出用字符数组名，遇 '\0' 结束；&str[0] 与 str 等价

char str[15]; scanf("%s", str); printf("%s", str);

第35页：用%s输出时的结束条件

用 "%s" 输出时，遇 '\0' 结束

char a[5]={'H','e','l','l','o'}; printf("%s\n", a); char a[]="Hello"; printf("%s\n", a); 

第36页：多个结束标志的情况

#include <stdio.h> main() { char a[]={'h','e','l','\0','l','o','\0'}; printf("%s\n", a); }

输出：hel。数组中有多个 '\0' 时，遇第一个 '\0' 即结束，后面的 l o 不再输出。

第37页：数组维数与溢出问题

#include <stdio.h> main() { char c, a[8]; scanf("%s", a); c = 'X'; printf("%s\n%c\n", a, c); }

输入 "hello" 时结果正常；输入 "helloboy" 时串长超过8，'\0' 写越界覆盖了变量 c，输出出错。故输入字符串长度必须小于字符数组维数。

第38页：scanf连续输入字符串

#include <stdio.h> main() { char a[15], b[5], c[5]; scanf("%s", a); printf("a=%s\n", a); scanf("%s%s%s", a, b, c); printf("a=%s\nb=%s\nc=%s\n", a, b, c); }

输入 How are you? 时，scanf 的 %s 遇空格结束，三次读取分别得到 How、are、you?。为避免上一次输入在缓冲区留下的垃圾字符，可在下次读入前调用 fflush(stdin); 清空缓冲区。

第39页：含空格字符串的输入方法

例：要输入字符串 "This is a string."，哪个不能实现？

• （A）scanf("%17s", s); — 不能：%s 遇空格即结束，只能得到 This
• （B）for(k=0;k<17;k++) s[k]=getchar(); s[k]='\0'; — 可以：逐字符读入含空格的17个字符
• （C）while((c=getchar())!=' ') s[k++]=c; — 可以：读到换行前的所有字符，含空格

第40页：字符数组的特殊性

字符数组的特殊性

• 定义与初始化：int a[]={1,2,3,4,5}; 与 char str[]="Hello"; 都可在定义时整体赋初值
• 输入与输出：整型数组只能逐个 %d 处理；字符数组既可逐个 %c，也可用 %s 整体输入输出
• 不能在定义后用赋值语句整体赋字符串

第41页：gets与puts函数

字符串输入输出函数（头文件 string.h）

puts

格式 puts(字符数组名) 或 puts(字符串常量)；向显示器输出字符串，输出完自动换行；字符数组必须以 '\0' 结束

gets

格式 gets(字符数组名)；从键盘输入以回车结束的字符串放入数组，并自动加 '\0'；输入串长度应小于数组维数

char string[80]; printf("Input a string:"); gets(string); puts(string);

第42页：字符串连接函数strcat

字符串连接函数 strcat

格式

strcat(字符数组1, 字符数组2)

功能

把字符数组2连到字符数组1后面

返值

返回字符数组1的首地址

说明

字符数组1必须足够大；连接前两串均以 '\0' 结束，连接后串1的 '\0' 被取消，只在新串最后保留一个 '\0'

第43页：字符串拷贝函数strcpy

字符串拷贝函数 strcpy

格式

strcpy(字符数组1, 字符串2)

功能

将字符串2拷贝到字符数组1中去

返值

返回字符数组1的首地址

说明

字符数组1必须足够大；拷贝时 '\0' 一同拷贝；不能使用赋值语句整体赋值

char str1[20], str2[20]; str1 = {"Hello!"}; str2 = str1; 

第44页：字符串比较函数strcmp

字符串比较函数 strcmp

格式

strcmp(字符串1, 字符串2)

比较规则

对两串从左向右逐个字符比较（按 ASCII 码），直到遇到不同字符或 '\0' 为止

返值

串1 < 串2 返回负整数；串1 > 串2 返回正整数；串1 == 串2 返回零

说明

字符串比较不能用 ==，必须用 strcmp

例：strcmp("hellogirls", "helloboys") 比较到 'g' 与 'b' 处，返回 'g'-'b' 即正5。

第45页：字符串长度函数strlen

字符串长度函数 strlen：格式 strlen(字符数组)，计算字符串实际长度，不包括 '\0' 在内。

说明：第2、3例中的 \0 与 \0 后紧跟数字构成的转义序列在 '\0' 处即结束串，故长度分别为3与1。

第46页：字符串反向程序

例：字符串反向——在字符串中将首尾字符进行对调

#include <stdio.h> #include <string.h> main() { char str[80], c; int i, k; gets(str); i = strlen(str); i--; for (k = 0; k < i; k++, i--) { c = str[i]; str[i] = str[k]; str[k] = c; } puts(str); }

第47页：字符串连接程序设计

例：将两个字符串连接后输出长度

#include <stdio.h> #include <string.h> main() { char str1[10], str2[10], str[20]; int len; gets(str1); gets(str2); if (strcmp(str1, str2) > 0) { strcpy(str, str1); strcat(str, str2); } else if (strcmp(str1, str2) < 0) { strcpy(str, str2); strcat(str, str1); } else { strcpy(str, str1); } len = strlen(str); puts(str); printf("Len=%d\n", len); }

第48页：字符串连接结果示意

连接结果示意：str1 为 "hellogirl"，str2 为 "helloboys"，经 strcpy(str, str1); strcat(str, str2); 后 str 中存放 "hellogirlhelloboys"，末尾补一个 '\0'，中间原 str1 的结束标志被取消。

第49页：求N个字符串中最大串

例：查找 N 个字符串中最大的一个

#include <stdio.h> #include <string.h> #define N 3 main() { char maxstr[20], str[N][20]; int i; for (i = 0; i < N; i++) gets(str[i]); strcpy(maxstr, str[0]); for (i = 1; i < N; i++) if (strcmp(maxstr, str[i]) < 0) strcpy(maxstr, str[i]); printf("The largest string is: %s\n", maxstr); }

第50页：本章小结

本章小结

• 数组的概念：数据集合
• 定义：类型、数组名、数组维数
• 初始化：一般形式和缺省形式
• 元素引用：数组名和下标
• 编程方法：排序、交换、插入、查找；常用字符串函数 gets、puts、strcpy、strcat、strlen、strcmp
• 排序算法：冒泡法与选择法；查找算法：顺序法与折半法