重庆邮电大学计算机科学与技术学院

1、重庆邮电大学计算机科学与技术学院 冯 潇 ,一维数组及其应用,2020/9/5,数组的定义、引用、初始化和输出 和数组有关的经典算法 冒泡法、选择法、折半查找法、求集合中最大或最小的元素 向函数传递一维数组,主要内容,2020/9/5,重点、难点,对数组名的理解 和数组有关的经典算法（难点） 冒泡法排序、选择法排序 顺序查找法、折半查找法,2020/9/5,假设集合中有班上30个同学的高数成绩，找出高数成绩的最高分，并将最高分打印到屏幕上 算法分析： 定义变量存放全班30个同学的高数成绩，定义变量MaxScore，初值为0 MaxScore = 元素1; /*假设集合中第一个元素值最大*/ f

2、or(i=0;i MaxScore) MaxScore = 元素i ,找出全班高数成绩的最高分,2020/9/5,保存大量同类型的相关数据 如矩阵运算，表格数据等,数组（Array）的作用,2020/9/5,数组的定义,语法格式： 类型名 数组名下标1下标2下标n； 下标为1个时为一维数组，依此类推 下标必须是一个常量表达式，只能用方括符括起来 数组大小最好用宏来定义，以适应未来可能的变化 #define SIZE 10int aSIZE; 数组特点 快速地随机访问 一旦定义，不能改变大小,2020/9/5,数组元素的引用,格式 数组名 下标； 下标表示当前元素相对于第一元素的偏移量 当使用数

3、组名时，代表数组的首地址 二维数组的引用 注意区分数组定义和数组引用 注意下标越界问题 数组不能整体引用 对数组每个元素的使用与普通变量无异,2020/9/5,全部赋初值 char ch4=h,a,l,0; int arr=3,7,5,8; 部分赋初值 float f10=1.7,2.1; 二维数组的初始化 int a23=1,2,3,4,5,6; int a3=1,2,3,4,5,6; int a3=1,2,4;,数组的初始化,double arr3; arr3=1.1;,2020/9/5,数组的物理存储结构,按行顺序存放数组,2020/9/5,只能逐个对数组元素进行操作（字符数组例外）,输

4、入方法：,int a10,i;,输入第i个数组元素：,scanf(%d,输入整个数组元素：,for (i=0;i10;i+) scanf(%d,输出方法：,输出第i个数组元素：,printf(%d,ai);,输出整个数组元素：,for (i=0;i10;i+) printf(%d,ai);,一维数组的输入和输出,2020/9/5,用法一：求表达式计算结果类型所占用的字节数 sizeof(表达式) int a = 5; sizeof(a+5); 用法二：求某种类型所占用的字节数 sizeof(数据类型名) x = sizeof(double)+2; printf(“%d”,x);,sizeof运

5、算符,2020/9/5,#include #define ARR_SIZE 30 int main() int scoreARR_SIZE=0, MaxScore=0, i; printf(Please enter scores:); for(i=0;iARR_SIZE;i+) scanf(%d, ,经典算法：找出集合中最大元素,2020/9/5,MaxScore = score0; /* 假设第一个元素是最大值 */ for(i = 0;i ARR_SIZE; i+) if(MaxScore scorei) MaxScore = scorei; printf(MaxScore = %dn,M

6、axScore); return 0; ,2020/9/5,打印出成绩为100分同学的学号,int main() int scoreARR_SIZE=0, i,flag=1; for(i=0;iARR_SIZE;i+) /*顺序扫描数组中每个元素*/ if(100=scorei) printf(No=%dt,i+1); flag=0; if(flag) printf( not found!n); return 0; ,2020/9/5,折半查找,基本思想 使用均分确定法，找出区间中的中点元素，如果待查信息的值小于中点元素值，则找出中点前半部分的中点元素，反之找出后半部分的中点元素，再进行比较，

7、然后再折半，直到区间无法继续二分 但折半法的前提是数据必须事先经过排序,2020/9/5, int main() int scoreARR_SIZE=0, i; int low,high,mid; printf(Please enter scores:); for(i=0;iARR_SIZE;i+) scanf(%d,2020/9/5,low = 0; high = ARR_SIZE - 1; while(low scoremid) low = mid + 1; else printf(No %d,mid); return 0; ,2020/9/5,按从高到低的分数对全班同学的成绩进行排序 算

8、法： 冒泡法 选择法,对全班的高数成绩进行排序,2020/9/5,核心思想 将相邻元素进行比较，较小（较大）的放在前面,冒泡法排序,5 6 7 8,6 5 7 8,6 7 5 8,6 7 8 5,6 7 8,7 6 8,7 8,8 7 6 5,7 8 6, int main() int scoreARR_SIZE = 0,i,j,temp; for(i=0;i ARR_SIZE - 1;i+) for(j=0;jARR_SIZE-i;j+) if(scorejscorej+1) temp = scorej; scorej = scorej+1; scorej+1 = temp; return

9、0; ,核心代码,2020/9/5,冒泡法核心思想,共有m个数，则需进行m-1轮比较，每轮比较完成后，最大(小)的值沉底，每轮比较交换m-i次 外层循环控制比较轮数，内层循环控制交换次数,5 6 7 8,6 5 7 8,6 7 5 8,6 7 8 5,7 6 8 5,7 8 6 5,7 8 6 5,1,2,3,8 7 6 5,2020/9/5,交换法排序,2020/9/5,2020/9/5, int main() int scoreARR_SIZE=0,i,j,k,temp; for(i=0;iARR_SIZE;i+) k = i; /*假设第i个元素最大*/ for(j=i+1;jARR_S

10、IZE;j+) if(scorekscorej) k=j; if(k!=i) temp = scorek; scorek = scorej; scorej = temp return 0; ,核心代码,2020/9/5,第i轮比较时，假设本论第一个待比较元素最大，然后找出i+1后面的所有数中最大的数，将其下标值赋给k，再用k和i进行比较，如果k不等于i，说明假设不成立，将k所对应的数和所所对应的数据进行交换 相较冒泡法排序，该算法虽然比较的次数不变，但是交换的次数最多只有i-1次。,交换法核心思想,2020/9/5,作业,分别用选择法和冒泡法对数组进行排序 在排序后用折半法查找数组中是否有元素值为77，如果有，输出该元素的下标 下面程序模拟了骰子的6000次投掷，用rand()函数产生1-6之间的随机数face，然后统计1-6每一面出现的机会(概率)存放到数组frequency中,#include #include #include int main() int face, roll, frequency7 = 0; srand(time(NULL); for (