维数组及冒泡排序.ppt

第5章 数组,5.1 数组 5.1.1一维数组 1、数组概念的引入(必要性) 如用以解决从键盘输入任意100个数，输出这些的半值这样的问题。 概念：数组由若干个类型相同的元素组成，每个元素就是一个变量，每个数组都有一个名称，称为数组名。,第5章 数组,2、一维数组的定义 一维数组是指数组元素只有一个下标的数组。 定义一维数组的一般格式如： 类型名 数组名整型常量表达式， 如：int a5; 该语句 (1)定义了一个名为a的一维数组。 (2)方括号中的5规定该数组最多容纳5个元素。 (3)类型名int规定了这5个元素均为整型变量。 (4)C语言规定数组第一个元素的下标(数组下标的下界)为0；因此最后一个元素的下标(数组下标的上界)为数组元素个数减1,第5章 数组,3、一维数组元素的使用 数组定义后，就可以在程序中使用数组元素。 格式如下： 数组名下标表达式 如：int a10; a0=0; a1=1; a2=a0+a1;,第5章 数组,使用数组元素应注意： (1)系统在内存中为数组分配一块连续的存储单元，最低的地址对应于第一个数组元素，最高的地址对应于最后一个数组元素。每个数组元素等同于一个变量。,(2)C语言中，不能对一个数组整体赋值。 如： int a10, b10, k; for (k=0;k10;k+) scanf(“%d”,对数组元素输入值，并倒序输出 void main() int a10,k; for (k=0;k=0;k-) printf(“%3d”,ak); printf(“n”); ,第5章 数组,(3) 在使用数组元素时，数组元素中的下标表达式的值必须是整型。 下标表达式值的下限为0，值的上限为该数组元素的个数减1。 使用数组时注意其下标不要越界。如果下标越界，程序无法得到正确的结果。,第5章 数组,4、数组元素的初始化 (1)定义数组时不对数组元素赋初值。 a、动态数组 未加说明定义的数组均为动态数组，定义动态数组时不对元素赋初值，则数组元素的值为不确定值。,第5章 数组,B、静态数组 定义时加static说明。 定义数组时不对元素赋初值，则所有元素初值为0。 如：static int b10; 这样，数组b中各元素(b0b9)值均为0。,第5章 数组,2)定义数组时对元素赋初值。 一般形式为：,static 类型名 数组名整型常量表达式=常量1，常量2，,例：int a10=1,2,3,4,5,6,7,8,9,10; 该语句定义了一个动态数组，并对该动态数组进行了初始化。,注意： 1、所赋初值的类型必须与说明的类型一致。 2、在指定初值时，第一个值赋给下标为0的元素。 3、不可能跳过前面的元素给后面的元素赋初值。,第5章 数组,注意： 1、如果初值的数据个数比数组元素少，则系统自动给后面的元素补赋初值0。 2、如果初值的数据个数比数组元素多，则在编译时提示出错信息： too many initializers. 3、初始化时不指定数组长度。 C语言中，可以在初始化时，不指定数组长度的个数。 例：int a =1,2,3,4,5; 这里，花括号里列出了5个初始化数据，它隐含地定义了该数组共有5个元素。等价于： int a5=1,2,3,4,5;,6、一维数组应用举例。,例5.6 在一个无序且不重复的数据中查找一个数，有则显示所在位置，无则显示“Not Exist!” #include void main() int a15=21,13,52,0,-25,6,18,1,36,2,-20,17,9,33,8; int i,x,f_at,flag=0; /*flag用于做是否找到的标记*/ printf(“Input a number to be searched:“); scanf(“%d“, ,例子5.7折半查找：在一个升序且不重复的数据中查找一个数，有则显示所在位置，无则显示“Not Exist!”,void main() int a10=7，9，12，18，21，25，33，39，45，60; int x,left=0,mid,right=9,flag=0; /*flag用于做是否找到的标记*/ printf(“Input a number to be searched:“); scanf(“%d“, ,第5章 数组,6、一维数组应用举例3。,经典算法介绍： 排序问题是程序设计中的典型问题之一，所谓排序就是将数组中的各元素的值按从小到大的顺序或按从大到小的顺序重新排列。 排序过程一般都要进行元素值的比较和元素值的交换。 分析: 冒泡排序法的基本思想是: 假设有N个数据放在数组a中,现要把这N个数从小到大排序. 第一:在a0到aN-1的范围内,依次比较两个相邻元素的值,若aJaJ+1,则交换aJ与aJ+1,J的值取0,1,2,N-2;经过这样一趟冒泡,就把这N个数中最大的数放到aN-1中.,第5章 数组,第二:再在a0到aN-2的范围内再进行一趟冒泡,又将该范围内的最大值换到了aN-2中. 第三:依次进行下去,最多只要进行N-1趟冒泡,就可完成排序.,例1:用冒泡排序法对8个整数6,8,5,4,6,9,3,2进行从小到大排序.,第四:如果在某趟冒泡过程中没有交换相邻的值,则说明排序已完成,可以提前结束处理.,第5章 数组 之 冒泡法排序,第二讲 冒泡法排序与选择法排序 冒泡法排序： 现假设有8个随机数已经在数组中，开始排序 初始状态： 数组a a0 a1 a2 a3 a4 a5 a6 a7 第一趟排序： 两两相邻比较： 一趟最后结果：,第二趟冒泡排序： 此时的待排序元素 a0 a1 a2 a3 a4 a5 a6 a7 同样对待排序元素两两比较后结果为： 这是第三趟冒泡的待排序元素 再来第三趟冒泡排序： 结果为：,第5章 数组 之 冒泡法排序,第5章 数组 之 冒泡法排序,同样第四趟结果为： 第五趟结果为： 第六趟结果为： 第七趟结果（最终）为：,冒泡法程序,main( ) int i,j,a8,temp,swap; clrscr( ); for(i=0;i8;i+) scanf(“%d“,for(i=0;i8;i+) printf(“%d,“,ai); printf(“n“); ,for(i=0;iaj+1) temp=aj; aj=aj+1; aj+1=temp; ,注：对n个元素冒泡排序第i趟排序的待排序元素是a0到an-i,swap=0; swap=1; if (!swap) break;,第5章 数组 之 冒泡法排序,swap 变量的作用 如果在某趟冒泡过程