chap2_用c语言编写程序1-3 - c程序设计基础

Chap 7 数 组,7.1 投票情况统计7.2 找出矩阵中最大值所在的位置7.3 判断回文,本章要点,什么是数组? 为什么要使用数组?如何定义数组?如何引用数组元素?二维数组的元素在内存中按什么方式存放?什么是字符串? 字符串结束符的作用是什么?如何实现字符串的存储和操作，包括字符串的输入和输出?怎样理解C语言将字符串作为一个特殊的一维字符数组?,7.1 投票情况统计,输入一个正整数n (1n10)，再输入n个整数，用选择法将它们从小到大排序后输出。 7.1.1 程序解析7.1.2 一维数组的定义和引用7.1.3 一维数组的初始化7.1.4 使用一维数组编程,7.1.1 程序解析,【例7-1】调查电视节目欢迎程度。某电视台要进行一次对该台8个栏目(设相应栏目编号为18)的受欢迎情况，共调查了1000位观众，现要求编写程序，输入每一位观众的投票，每位观众只能选择一个最喜欢的栏目投票，统计输出各栏目的得票情况。分析：本题涉及新问题如何存储8个栏目计票数据,# includeint main( void ) int i,response, count9; /* 设立得票计数器 */ for(i = 1; i 8) /* 检查是否有效票*/ printf(this is a bad response: %dn,response); else countresponse+; /* 对应栏目得票加1 */ printf(result:n); /* 输出得票情况 */ for(i = 1;i = 8;i+) printf(%4d%4dn,i,counti); return 0;,例7-1程序,7.1.2 一维数组的定义和引用,1. 数组的一般概念数组是按序排列的同类型变量的集合，是一组具有相 同名字, 不同下标的下标变量。下标变量又称数组元素，形式为：数组名下标 如：a0、a1、a2、a3、a9数组名表示整个数组，如：a下标指出该数组元素在数组中的位置。有1个下标的下标变量所组成的数组称为一维数组； 有2个下标的下标变量所组成的数组称为二维数组。 如：x1、y5 数组x和y都是一维数组 a12、b23 数组a和b都是二维数组,7.1.2 一维数组的定义和引用,2. 一维数组的定义 定义的一般形式 类型名 数组名数组长度；类型名：数组元素的数据类型数组名：数组的名称，标识符数组长度：常量表达式，指定数组元素的个数 例如： int a10; 定义一个含有10个整型元素的数组a char c81; 定义一个含有81个字符元素的数组c float f5; 定义一个含有5个实型元素的数组 f,7.1.2 一维数组的定义和引用,数组中元素的下标从0开始依次编号。经定义的数组,编译后, 会分配到一段 连续的内存单元。如有定义int a10; , 情况如图所示，a0, a1, a9依 次连续存储。数组名(如a )是一个地址常量，存放 数组内存空间的首地址。也就是第1 个元素的存储地址，即a和&a0同值。各个元素的存储地址用数组的首地址以及每个元 素所需的字节数，均可计算得到。,7.1.2 一维数组的定义和引用,数组定义中的数组长度只能是常量表达式，不能 含变量。如以下定义是非法的： int n, m=10; double an, bm;同类型数组、变量可一起定义: int i, a10, b20;,7.1.2 一维数组的定义和引用,3. 一维数组的引用 只能引用单个数组元素，不能一次引用整个数组。 数组元素的引用方法有两种：下标法和指针法。下标法引用一维数组元素的形式为： 数组名下标 其中下标为整型表达式，取值范围是: 0, 数组长 度-1，它表示了元素在数组中的顺序位置。数组元素又称下标变量，使用方法与同类型变量 完全相同。编译时，不检查数组元素的下标是否越界。,7.1.3 一维数组的初始化,数组初始化就是在定义数组时，对数组元素赋值。 其一般形式为： 类型名 数组名数组长度 = 初值表;初值表中用逗号分隔的各值为将依次赋予各对应 元素的初值，必须是常量表达式，且类型应与数 组的类型相一致。例如， int a10 = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; 字符数组初始化有两种形式char b6=C,h,i,n,a,0;char s6=China; 或 char s6=China;,7.1.3 一维数组的初始化,允许只给部分元素赋初值(其余元素初始化为0 )。 如：int a10=1, 2, 3, b10= 0 ; 如对全部元素都赋初值，可缺省数组长度，数组 长度为初值表中初值的个数。例如， int a = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10; char s = China; 对数组未指定初始化自动类型数组，各元素的值是随机的未知值。全局数组和静态数组，各元素值则会自动初始 化为0。,7.1.3 一维数组的初始化,一维数组的输入和输出对数组元素赋初值，更多的是通过键盘输入的 方法。如输入长度为n的整型数组a的各元： for( i=0; i 1 ),例7-2程序,#include int main(void) int i, fib10 = 1, 1; for(i = 2; i 10; i+) fibi = fibi - 1 + fibi - 2; for(i = 0; i 10; i+) printf(%6d, fibi); if(i + 1)%5=0) printf(n); return 0;,运行结果: 1 1 2 3 5 8 13 21 34 55,7.1.4 使用一维数组编程,【例7-3】输入5个整数，将它们存入数组 a 中，再输入一个数x，然后在数组中查找x，如果找到，输出相应的最小下标，否则，输出“Not Found”。分析：这是个查找问题中的顺序查找问题。通过遍历(扫描)数组a，对数组各元逐个比较是否 等于x即可。最后判断是否未找到，可用标志法或break法。,例7-3程序,#include int main(void) int i, flag, x, a5; printf(Enter 5 integers: ); for(i = 0; i 5; i+) scanf(%d, ,运行结果1: Enter 5 integers: 2 9 8 1 6 Enter x: 9 Index is 1,运行结果2: Enter 5 integers: 2 9 8 1 6 Enter x: 7 Not Found,7.1.4 使用一维数组编程,【例7-4】输入一个正整数n(1 n 11), 再输入n个 整数，将它们存入数组 a 中。 输出最小值和它所对应的下标。 将最小值与第一个数交换，输出交换后的n个数。分析： 这是个求最值问题。可先假定a0最小，即最小元素的下标index=0，然后遍历数组a，各元素逐个与aindex比较，若小于，则其下标存入index，这样就是使 index 中始终是到当前为止的最小元素的下标 。,7.1.4 使用一维数组编程,实现语句： for(index = i = 0; in; i+) if(ai aindex) index = i; 交换两个变量的值有多种方法：借助第三者 t = a; a = b; b = t;不借助第三者 a =a+b; b= a-b; a =a-b; a = b; b =a; a = b; 或写成 a = b = a = b;,#include int main(void) int i, index, n, a10, t; printf(Enter n: ); scanf(%d, ,例7-4程序,例7-4程序,t = aindex; aindex = a0; a0=t; for(i = 0; i n; i+) printf(%d , ai); return 0;,运行结果:Enter n: 6Enter 6 integers: 2 9 -1 8 1 6min is -1 sub is 2-1 9 2 8 1 6,7.1.4 使用一维数组编程,【例7-5】选择排序法。输入一个正整数n(1 n 10)，再输入n个整数，用选择法将它们从小到大排序后输出。,例7-5程序,#include int main(void) int i, j, k, n, t, a10; printf(Enter n: ); scanf(%d, ,例7-5程序,printf(After sorted: ); for(i = 0; i n; i+) printf(%d , ai); return 0;,运行结果: Enter n: 10Enter 10 integers: 3 5 2 8 1 22 89 0 -1 7After sorted: -1 0 1 2 3 5 7 8 22 89,选择法排序,选择法排序的基本思想是： 通过比较找到最小数，如不是第1个数，则与第1个数交换，再在余下的数(即第2个开始)中找到最小数，如不是第 2 个数，则与第 2 个数交换，再在余下的数(即第3个开始)中找到最小数，如不是第 3 个数，则与第 3 个数交换，依此类推，n 个数经过 n-1 轮比较即可完成排序。,选择法排序,选择法排序的实现1：int n=5, i, j, t;int a5 = 3, 5, 2, 8, 1;for(i = 0; i aj) t = ai; ai = aj; aj = t; ,选择法排序的实现1流程：,选择法排序,选择法排序的实现2：int n=5, i, j, k, t;int a5 = 3, 5, 2, 8, 1; for(i = 0; i aj) k = j; if(k != i) t=ai; ai=aj; aj=t; ,选择法排序的实现2流程：,冒泡法排序,冒泡法排序1的基本思想是： 从第n个数开始，依次比较相邻两个数，即第n个与第n-1个、第n-1个与第n-2个、 ，每次比较，若不满足由小到大的顺序，则两者对调位置，通过一轮比较，参加比较的数中的最小数就“上升”到它们中最前面的位置，下一轮再从第n个数开始，把余下的数依次比较，这样，通过n-1轮比较，就完成了全部n个数的升序排列。在第i轮比较时，从第 1个位置开始已排序定位了i-1个数，余下n-i+1个数，需两两比较 n-i次。,冒泡法排序,冒泡法排序1的实现：int n=5, i, j, t;int a5 = 3, 5, 2, 8, 1;for(i = 0; i i; j-) if(aj aj-1) t = aj; aj = aj-1; aj-1 = t; ,冒泡法排序,冒泡法排序2的基本思想是： 从第1个数开始，依次比较相邻两个数，即第1个与第2个、第2个与第3个、 ，每次比较，若不满足由小到大的顺序， 则两者对调位置， 通过一轮比较，参加比较的数中的最大数就 “ 下沉 ” 到它们中最后面的位置，下一轮再从第1个数开始，把余下的数依次比较，这样，通过n-1轮比较，就完成了全部n个数的升序排列。在第i轮比较时，从第 n个位置开始向前已排序定位了i-1个数，余下 n-i+1个数，需两两比较n-i次,冒泡法排序,冒泡法排序2的实现：int n=5, i, j, t;int a5 = 3, 5, 2, 8, 1;for(i = 0; i aj+1) t = aj; aj = aj+1; aj+1 = t; ,7.1.4 使用一维数组编程,【例7-6】二分查找法。设已有一个10个元素的整形数组a，且按值从小到大有序。输入一个整数 x，然后在数组中查找x，如果找到，输出相应的下标,否则，输出“Not Found”。 设：待查数在变量x中； 变量low 用于存放查找范围的顶部位置； 变量mid 用于存放查找范围的中间位置； 变量high 用于存放查找范围的底部位置；,二分法查找流程图,#include int main(void) int low, high, mid, n=10, x, a10=1,2,3,4,5,6,7,8,9,10; printf(Enter x: ); scanf(%d,例7-6程序,运行结果1:Enter x: 8Index is 7,运行结果2:Enter x: 71Not Found,7.2 找出矩阵中最大值所在的位置,将1个3*2的矩阵存入1个3*2的二维数组中，找出最大值以及它的行下标和列下标，并输出该矩阵。 7.2.1 程序解析7.2.2 二维数组的定义和引用7.2.3 二维数组的初始化7.2.4 使用二维数组编程,7.2.1 程序解析,【例7-7】将1个 3*2的矩阵存入1个 3*2 的二维数组 中，找出最大值以及它的行下标和列下标，并输出 该矩阵。分析：涉及新问题：二维数组求最值方法与【例7-4】的一维数组中求最值方 法类似。row 记录最大值的行下标 col 最大值的列下标 arowcol 就是最大值,#include int main(void) int i, j, col, row, a32; printf(Enter 6 integers:n) ; for(i = 0; i 3; i+) for(j = 0; j 2; j+) scanf(%d, ,例7-7程序,例7-7程序,row = col = 0; for(i = 0; i arowcol) row = i; col = j; printf(max = a%d%d = %dn, row, col, arowcol); return 0;,运行结果:Enter 6 integers: 3 2 10 -9 6 -1 3 2 10 -9 6 -1max = a10 = 10,7.2.2 二维数组的定义和引用,1. 二维数组的定义 定义的一般形式 类型名 数组名行长度列长度 其中行长度和列长度只能是常量表达式。 如： int a32; 定义3行2列的二维数组a, 各元素为： a00 a01 a10 a11 a20 a21 如图所示，按行存放在一段连续的内存中。,7.2.2 二维数组的定义和引用,二维数组是一维数组的数组 可以把a看作含有a0、a1和a2共3个元素的一 维数组，而a0、a1和a2又都是含有2个元素 的一维数组，a0、a1和a2就是这3个一维数 组的名字，即： a: a0: a00 a01 a1: a10 a11 a2: a20 a21,7.2.2 二维数组的定义和引用,2. 二维数组的引用 数组元素的引用方法有两种：下标法和指针法。 下标法引用二维数组元素的形式为： 数组名行下标 列下标 其中： 行、列下标 可以是整型表达式； 行下标 取值范围: 0, 行长度-1； 列下标 取值范围: 0, 列长度-1。,7.2.3 二维数组的初始化,1. 分行赋初值的一般形式 类型名 数组名行长度列长度 = 初值表0, , 初值表k, ; 其中初值表k中的数据依次赋给k行的元素。 例如：int a32=1,2,3,4,5,6;2. 顺序赋初值的一般形式 类型名 数组名行长度列长度 = 初值表; 按数组元素在内存中的存放顺序，把初值表中的数 据依次赋给元素。 例如：int a32=1,2,3,4,5,6;,7.2.3 二维数组的初始化,3. 初始化说明允许只给部分元素赋初值(其余元素初始化为0) int a34=8,4, 5, 4; int a34=8,4,2,1,5;当用分行赋值给出了所有行，或者当用顺序赋值给出全部数组元素初始化值时，可以缺省行长度 int a 4=8,4, 5,4; int a 4= 8,4,2,1, 5,7,0,3, 4,0,9,6;对数组未指定初始化自动类型数组，各元素值是随机的未知值。全局数组和静态数组，各元素值自动赋初值0。,7.2.3 二维数组的初始化,二维数组的输入和输出对数组元素赋初值，更多的是通过键盘输入的方法。 如输入n行m列的整型数组a的各元： for( i=0; in; i+ ) for( j=0; jm; j+ ) scanf(%d, ,7.2.4 使用二维数组编程,【例7-8】定义1个 3*2的二维数组a，数组元素的值 由下式给出，按矩阵的形式输出a。aij = i + j（0i2，0j1）,例7-8程序,#include int main(void) int i, j, a32; for(i = 0; i 3; i+) for(j = 0; j 2; j+) aij = i + j; for(i = 0; i 3; i+) for(j = 0; j 2; j+) printf(%4d, aij); printf(n); return 0;,运行结果: 0 1 1 2 2 3,7.2.4 使用二维数组编程,【例7-9】输入一个正整数n(1n6)，根据下式 生成1个n*n的方阵，然后将该方阵转置(行列互换) 后输出。 aij = i * n + j + 1（0in-1，0jn-1） 例如，当n=3时，有： 转置前 转置后 1 2 3 1 4 7 4 5 6 2 5 8 7 8 9 3 6 9,7.2.4 使用二维数组编程,矩阵术语与二维数组下标的对应关系：int aNN; N是正整数aij：i、j的取值范围0，N-1设N为3，用二维数组a表示N*N方阵时：a00 a01 a02a10 a11 a12a20 a21 a22,7.2.4 使用二维数组编程,遍历主对角线：for(i = 0; i N; i+) aii = ; 遍历副对角线：for(i = 0; i N; i+) aiN-1-i = ; 遍历上三角：for(i = 0; i N; i+) for(j = i; j N; j+) aij = ; 遍历下三角：for(i = 0; i N; i+) for(j = 0; j = i; j+) aij = ; ,#include int main(void) int i, j, n, t, a66; printf(Enter n: ); scanf(%d, ,例7-9程序,例7-9程序,for(i = 0; i 3; i+) for(j = 0; j = 0 ,Enter a string: ab1cb23adi