c第8讲数组一维的使用

1、第八讲 第七章 数组 一维数组的使用典型算法 排序 查找 插入 删除 一维数组的基本概念数组及数组元素的概念数组:是具有一定顺序的一组类型相同、下标不同变量的 集合体。例如：表示A班（n个学生）C语言成绩的一组数据.数组a 2 下标数组名数组元素(下标变量 ) a0,a1,a2,a3,an-1数组元素：组成数组的变量称为该数组的元素。数组及数组元素的概念基本概念数组是由同一名字和相同类型的一组连续内存单元构成的。为了引用数组中的特定位置或元素，我们需要指定数组的名称，并指定数组中特定元素的位置编号，这个位置编号称为数组下标。 方括号中的数组元素下标必须是整数或整数表达式。 数组下标是从0开始的

2、，“数组的第7个元素”的下标是6，而“数组元素7”的下标为7，实际上是指数组的第8个元素。 数组的基本概念例如：整型数组a10，包含十个变量，分别是:a0,a1,a2,a3a9 数组的维 一维数组：数组元素只有一个下标组成的数组。二维数组：数组元素有两个下标组成的数组。 例如：数组 b34,实型,12个变量:b00,b01,b02,b03先定义，后使用 使用原则名字类型大小维数b10,b11,b12,b13b20,b21,b22,b23一维数组的使用 数组的定义类型说明符 数组名常量 ;例如：int a10;整型数组名字为a十个变量a0a1a9 数组的初始化float b5=1,2,3,4,5

3、; 一维数组的存储结构a0a1.a9数组ab0b1.b4数组b1.02.05.0 数组的使用 (1) 数组元素在内存中顺序存放 (2) 数组元素的地址是连续的等价于：float b5=1;float b =1,2 ,3,4,5;b0b1b4数组b1.00.0.0.0一维数组的输入和输出例1 将十个数据输入到数组中，并按下标的逆序输出。void main( ) int a10,i;for(i=0;iai);for(i=9;i=0;i - -)coutai; cout“nResult:”endl;printf(“nInput data:”);使用数组的关键在于控制下标变化aii=09a0a1.a9

4、数组a将数据输入到各个数组元素中一维数组的初始化同简单变量一样，数组元素在说明后就对其赋值，如果用输入语句或赋值语句使数组中的元素得到值，会占用运行时间，因此可以使数组在程序运行之前初始化，即在编译阶段使之得到初值。 例 #include stdio.hmain() int i, a10; for (i = 0;i = 9;i+) scanf(%d,&ai);一维数组的初始化初始化方法：从数组的第一个元素开始依次给出初始值表;表中各值之间用逗号分开，并用一对大括号括起来。 在定义数组时对数组元素赋予初值 int a10=9,1,6,3,4,5, 2,7, 0, 8; 只给一部分元素赋初值 in

5、t a10=0,1,2,3,4; 欲使一个数组中全部元素初值为0，只能写成： int a10 = 0,0,0,0,0,0,0,0,0,0,; 不能写成：int a10 = 0*10;/error 在对全部数组元素赋初值时，可以不指定数组长度 int a =0,1,2,3,4,5;数组排序基本概念排序是根据某个标准，按照指定的次序（升序或降序）组织一组数据的过程。 根据执行效率，排序算法通常分为两大类：顺序排序，一般使用一对嵌套的循环结构，对排序n个元素需要大约n2次比较；对数排序，对排序n个元素一般需要大约nlog2n次比较。本节将介绍3种排序技术：选择排序法插入排序法冒泡排序法排序算法插入排

6、序直接插入排序折半插入排序表插入排序希尔排序交换排序冒泡排序快速排序（不稳定）选择排序归并排序基数排序插入排序 插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。简言之，边插入边排序，保证子序列中随时都是排好序的。直接插入排序新元素插入到哪里？例1：关键字序列T=（13，6，3，31，9，27，5，11）， 请写出直接插入排序的中间过程序列。【13】, 6, 3, 31, 9, 27, 5, 11【6, 13】, 3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3,

7、6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6, 9, 11，13，27, 31】 在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。最简单的排序法！交换排序 两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有： 1) 冒泡排序 2) 快速排序交换排序的基本思想是： 冒泡排序基本思路：每趟不断将记录两两比较，并按

8、“前小后大”（或“前大后小”）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。前提：顺序存储结构 例：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初态：第1趟第2趟第3趟第4趟第5趟54129867103a0a1a2a3a4

9、a5a6a7a8a9a0a1a j a j+1a8a9a1a2第一遍： j=08a1a1a7a0a2a j a j+1a8第二遍： j=07数据个数：n 遍数：i=0n-2 比较：j=0(n-2)-ifor (i=0;in-1;i+)for (j=0;jaj+1) t=aj;aj=aj+1;aj+1=t;冒泡排序（冒泡法）排序的基本思想是：俩俩相邻数据比较交换。冒泡排序（冒泡法）例 用起泡法对10个数排序。#include stdio.h main() int a10=9,8,5,4,2,0,6,1,3,7; int i, j,temp,n = 10; for (i = 0; i =n-2;

10、i+) for (j = 0; j aj+1) temp = aj; aj = aj+1; aj+1 = temp; for (i = 0;i aj+1真for j=1 to n-2-i 假aj aj+1 互换for i=0 to n-2输出:a数组元素比较排序（比较法）排序的基本思想是：俩俩相邻数据比较交换。54129867103a0a1a2a3a4a5a6a7a8a9a0a1a9a i a i+1a9a8a9a1a2a9数据个数：n 遍数：i=0n-2 比较：j=i+1(n-1)for (i=0;in-1;i+)for (j=i+1;jaj) t=ai;ai=aj;aj=t;选择排序（选择

11、法）排序的基本思想是：找出数据中最小元素的位置再交换。54129867103a0a1a2a3a4a5a6a7a8a9a0a1a9a i a i+1a9a8a9a1a2a9数据个数：n 遍数：i=0n-2 比较：j=i+1(n-1)for (i=0;in-1;i+) w=i; for (j=i+1;jaj) w=j; if(w!=i) t=ai;ai=aw;aw=t; 选择排序(选择法）算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。第1次，在数组a的n个数据中选出其小者（只标记其所在位置），若它不在其位置（即

12、其下标不等于1）则与第一个数据进行交换（只需交换一次），经过本次处理后，总可以使得数组a的第1个数据为第1小。第2次，在数组a的后n-1个数据（即出去已经选择的最小者的各数据）中，经过类似的处理后，可以使得数组a的第2个数据为第2小。第i次，在数组a后的n-i+1个数据中，经过类似选择处理后，数组a的第i个数据为第i小。第n-1次，在数组后的2个数据中，经过类似处理后，总可以使数组a的第n-1个数据为第n-1小。而这时候第n个数据是第n小。数组查找基本概念查找是在一组元素中寻找某个指定的目标元素，或者确定该组元素中是否存在目标元素的过程。 进行查找的元素组有时称为查找池（search pool

13、）。 本节将介绍两种查找技术：线性查找（linear search）二分查找（binary search）查 找查找之前要求排序，不然无章可查顺序查找按照排好序的顺序进行查找，比如对一个升序排列的数组中，找到第一个大于需要查找的数为止。折半查找（二分查找）查找算法：12345678910a0a1a2a3a4a5a6a7a8a9查 找例4 查找一个数是否在某数组中出现。 顺序查找 设数组为a，待查找的数为x把x与数组a中的元素从头到尾一 一进行比较输入n,a,x f：标记1：查到0：没查到 for i=0 to n-1x=ai真f=1假void main() int n,x,i,f,a50; s

14、canf(“%d,%d”,&n,&x); f=0; for(i=0;i=n-1;i+) if(x=ai) f=1; if(f) printf(“yes,%d”,i); else printf(“no”); for(i=0;iam,(m,t2)为新的查找范围 t1=m3.若xam,(t1,m)为新的查找范围 t2=mt1:查找范围内下标最小值t2:查找范围内下标最大值m:查找范围内下标中值输入n,a,x t1=0 t2=n-1 当t1amt1=m假t2=m查找输入n,a,x t=0 b=n-1 当tamt=m+1假b=m-1void main()int a50,x,i,n,t1,t2,m,f;

15、cinn; for(i=0;iai; cinx; t1=0;t2=n-1;f=0; while(t1am)t1=m+1; else t2=m-1; if(f=1) cout“Yes,”m; else cout“No;例5 数组a有五个元素，其值分别为：1、2、3、4、5，循环移动该数组的数，使其变成2、3、4、5、1。 m=a0for i=1,4ai-1=ai a4= m待移动数据的下标void main( ) int a5=1,2,3,4,5;m=a0;for (i=1;i=4;i+)ai-1=ai;a4=m;int i,m;for(i=0;inx); f=0; for(i=0;i=n-1;

16、i+) if(x=ai) f=1; break; for(i=0;iai; if(f) for(k=i+1;k=n-1;k+) ak-1=ak; n-; for(i=0;in;i+) couta0?操作真插入点是01xa1?真插入点是1ixai?真插入点是in-1xan-1?真插入点是n-1假插入点是n操作结果数组aa0a1a2a3a4a5a6a7a81085210-1-7数组a插入前插入后4108510-1-7-7224-1012有序插入例7 在一个降序排列的数列中插入一个数，使新数列保持原序。a7a81 向后移动数据2 插入n-1i位置j：a6a7ajaj+1ai=xfor i=0 to

17、n-1xai真break假ai=xfor j=n-1 to i,-1aj+1=ajn+void main( ) int a20,i,j,x,n;scanf(“%d”,&x);for(i=0;iai) break;for(j=n-1;j=i;j- -)aj+1=aj;ai=x;n+;for(i=0;in;i+)printf(“%3d”,ai);for(i=0;iai真break假for j=n-1,i,-1aj+1=aj输入数据输出数据scanf(“%d”,&n);小结有序删除：比如要删除ad这个元素，则： for (j = d+1;j = L;j-) aj+1=aj;第三次实验作业（14周周三

18、提交）第七章（数组）实验： P147: ,2,4,5,6,(8,9,10,11,12)源程序文件命名方式： 例： 7-2.c 表示第七章第二题打包文件方式： 例： 程玉明-工程0901（三）.rar字符数组基本概念字符数组可用一个字符串常量来初始化，例如： char chStr = Hello;在字符串“Hello”中，除包含5个字符之外，还包含一个特殊的字符串结束字符，即NULL字符。所以，chStr数组实际包含了6个元素。C+使用0字符常量来表示NULL字符，所有字符串都必须使用这个字符结束的。排序的引例读入amax=a读入aamax真max=afor i=2 to n读入n输出假给数组t 赋值titw真for i=1 to n-1读入n 假例2 从n个数中找出最大