![C语言从入门到精通(微视频精编版)](https://wfqqreader-1252317822.image.myqcloud.com/cover/269/27563269/b_27563269.jpg)
第7章 数组的应用
(视频讲解:44分钟)
在编写程序的过程中,经常会遇到使用大量数据的时候,处理每一个数据就要有一个相对应的变量,如果每一个变量都要单独进行定义的话就会变得很烦琐,使用数组就可以解决这种问题。数组将一些有关联的相同的数据类型集合到一个数组变量中,方便数据的存储和使用。
本章致力于使读者掌握一维数组和二维数组的作用,并且能用所学知识解决一些实际的问题。掌握字符数组的使用及相关的操作。通过一维数组和二维数组了解有关多维数组的内容。最后学习数组在排序算法中的应用。
学习摘要:
一维数组和二维数组的定义和引用
多维数组的基本知识
数组的排序算法
7.1 一维数组
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P151_20415.jpg?sign=1739599751-kXHnaONXKaaYkcF9rJklfr2iX2TMYJ6A-0-f56365cb2edb289edd6f1fdd7f81d3fc)
视频讲解
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P151_20428.jpg?sign=1739599751-cSMCSG9ywbHoSOEJWI82fUbNTXTbTgMs-0-594e7aaec21b46321a1c500dc95b856d)
动图演示
7.1.1 一维数组的定义和引用
一维数组的定义
一维数组是用以存储一维数列中数据的集合。
一维数组的一般形式如下:
类型说明符 数组标识符[常量表达式];
类型说明符表示数组中所有元素的类型。
数组标识符就是这个数组型变量的名称,命名规则与变量名一致。
常量表达式定义了数组中存放的数据元素的个数,即数组长度。例如iArray[5],数字5表示数组中有5个元素,下标从0开始,到4结束。
例如,定义一个数组:
int iArray[5];
代码中的int为数组元素的类型,而iArray表示的是数组变量名,括号中的5表示的是数组中包含的元素个数。
注意
在数组iArray[5]中只能使用iArray[0]、iArray[1]、iArray[2]、iArray[3]、iArray[4],而不能使用iArray[5],若使用iArray[5]会出现下标越界的错误。
一维数组的引用
数组定义完成后就要使用该数组,可以通过引用数组元素的方式,使用该数组中的元素。
数组元素的一般表示形式如下:
数组标识符[下标];
例如,引用一个数组变量iArray中的第3个变量:
iArray[2];
iArray是数组变量的名称,2为数组的下标。有的读者会问:“为什么使用第3个数组元素,而使用的数组下标是2呢?”。在上面介绍过数组的下标是从0开始的,也就是说下标为0表示的是第一个数组元素。
说明
下标可以是整型常量或整型表达式。
【例7.1】 使用数组保存数据。(实例位置:资源包\源码\07\7.01)
在本实例中,使用数组保存用户输入的数据,然后将数组元素输出。运行程序,在窗体输入5个数,可以使用空格分隔。按回车键,将输入的数据存储到数组中,并输出到窗体上,显示效果如图7.1所示。
在本实例中,程序定义变量index用于控制循环。通过语句“int iArray[5]”定义,该数组有5个元素,程序中用到的iArray[index]就是对数组元素的引用。程序代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P152_20569.jpg?sign=1739599751-HAiGyyFjbdQXw9tzuyCQZUq8Sb9TzTxC-0-968fcb4e56cfccb4cc8a4614cbd4de6f)
图7.1 使用数组保存数据
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P152_74368.jpg?sign=1739599751-izdifyte47CDU7917vIt8iSb8hgen8IW-0-fd514f3283548d776eb571d73760e91a)
7.1.2 一维数组初始化
一维数组的初始化可以用以下几种方法实现。
(1)在定义数组时直接对数组元素赋初值,例如:
int i,iArray[6]={1,2,3,4,5,6};
该方法是将数组中的元素值全部放在一对花括号中。通过定义和初始化之后,数组中的元素iArray[0]=1,iArray[1]=2,iArray[2]=3,iArray[3]=4,iArray[4]=5,iArray[5]=6。
【例7.2】 初始化一维数组。(实例位置:资源包\源码\07\7.02)
在本实例中,对定义的数组变量进行初始化操作,然后隔位输出。运行程序,显示效果如图7.2所示。
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P152_20572.jpg?sign=1739599751-1Ni1Yjm6oUmiUYPTyHyUKHKUzH5R7geR-0-4cd1c708887cf2bb83cc7592310ef969)
图7.2 初始化一维数组
实现代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P153_74374.jpg?sign=1739599751-iqtZsewWU8tp6Lv81TdzlbvIvlTWT5WS-0-501dde499445d8213529b1879c6755cc)
说明
在程序中,定义一个数组变量iArray并且对其进行初始化赋值。使用for循环输出数组中的元素,在循环中,控制循环变量使其每次循环增量为2。这样根据下标进行输出时,就会得到隔一个元素输出的效果了。
(2)可以只给一部分元素赋值,未赋值的部分元素值为0。
第二种为数组初始化的方式是对其中部分元素进行赋值,例如:
int iArray[6]={0,1,2};
数组变量iArray包含6个元素,但在初始化的时候只给出了3个值。于是数组中前三个元素的值对应括号中给出的值,在数组中没有得到值的元素默认被赋值为0。
【例7.3】 赋值数组中的部分元素。(实例位置:资源包\源码\ 07\7.03)
在本实例中,定义数组并且对其进行初始化赋值,但只为其中一部分元素赋值,然后将数组中的所有元素进行输出。观察输出的元素数值。运行程序,显示效果如图7.3所示。
实现代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P153_20733.jpg?sign=1739599751-UTxuVfwPwVWjDzBT1o8ZYP3SCq7c1sOU-0-59eff27f86ff1cdc24c7e6a4a4e5b886)
图7.3 赋值数组中的部分元素
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P153_74375.jpg?sign=1739599751-f13IjaWkwKzPYueAsskqzftaiHO3z903-0-21f3d1f782a85ebf6e4108232234c15f)
说明
在程序代码中,可以看到为数组部分元素赋值操作和为数组元素全部赋值的操作是一样的,只不过在括号中给出的元素数值比数组元素数量少。
(3)在对全部数组元素赋初值时,可以不指定数组长度。
之前在定义数组时,都在数组变量后指定了数组的元素个数。C语言还允许在定义数组时不指定数组长度,例如:
int iArray[]={1,2,3,4};
像上面的语句,大括号中有4个元素,系统就会根据给定的元素值的个数来定义数组的长度,所以该数组变量的长度为4。
注意
在定义数组时假如定义的长度为10,就不能使用省略数组长度的定义方式,必须写成:
int iArray[10]={1,2,3,4};
【例7.4】 不指定数组的元素个数。(实例位置:资源包\源码\07\7.04)
在本实例中,定义数组变量时不指定数组的元素个数,直接对其进行初始化操作,然后将其中的元素值输出显示。运行程序,显示效果如图7.4所示。
实现代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P154_20848.jpg?sign=1739599751-9pFA6lGrQ6ZzEY9MsG522wBjvhOThsyx-0-cc0cdfb959a221808aaadab2112bdaf8)
图7.4 不指定数组的元素个数
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P154_74382.jpg?sign=1739599751-SaJojDFNg4XRnGVYL5ZDYkq2LdUeW0JC-0-bbaa84c6e1ef5cda39775e7617e79300)
7.1.3 一维数组应用
例如,一个班级会有很多学生的姓名,为了将这些学生的姓名管理起来,可以使用一种方式存储这些姓名。这时就可以使用数组来保存这些学生的姓名,方便进行管理。
【例7.5】 使用数组保存学生姓名。(实例位置:资源包\源码\07\7.05)
在实例中,要使用数组保存学生的姓名,那么数组中的每一个元素都应该是可以保存字符串的类型,这里使用字符指针类型。运行程序,显示效果如图7.5所示。
实现代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P155_20973.jpg?sign=1739599751-j1vVcLcCu2VdIyheZgOAubhK1bBtH6Ex-0-4c6c0a99e48c769ea18d9df9b22484ca)
图7.5 使用数组保存学生姓名
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P155_74391.jpg?sign=1739599751-fmA0WyCVm6z9CZmp6vbrTI0VPYjujdfL-0-ebf18cf1efe65939cc1528110aeee82f)
在程序中的代码可以看到,“char* ArrayName[5]”定义了一个具有5个字符指针元素的数组。然后利用每个元素保存一个学生的姓名,使用for循环将其数组中保存的姓名数据输出。
7.2 二维数组
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P155_20978.jpg?sign=1739599751-qsXgcnj7UevqRArKD5la3fvMa8yvUeMd-0-8d759b42733fef1e6482fe94fe586828)
视频讲解
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P155_20990.jpg?sign=1739599751-7vgVjmenPLml39pXz9HL6JGoNXRccaRi-0-6064d7c2899e3c2c8cf3980047971e7c)
动图演示
7.2.1 二维数组的定义和引用
(1)二维数组的定义
二维数组的定义和一维数组相同,其一般形式如下:
数据类型 数组名[常量表达式1][常量表达式2];
其中,常量表达式1被称为行下标,常量表达式2被称为列下标。如果有二维数组array[n][m],则二维数组的下标取值范围如下:
行下标的取值范围为0~n-1。
列下标的取值范围为0~m-1。
二维数组的最大下标元素是array[n-1][m-1]。
例如,定义一个3行4列的整型数组:
int array[3][4];
说明了一个3行4列的数组,数组名为array,其下标变量的类型为整型。该数组的下标变量共有3×4个,即:
array[0][0],array[0][1],array[0][2],array[0][3]
array[1][0],array[1][1],array[1][2],array[1][3]
array[2][0],array[2][1],array[2][2],array[2][3]
在C语言中,二维数组是按行排列的,即按行顺次存放。先存放array[0]行,再存放array[1]行。每行中有4个元素也依次存放。
(2)二维数组的引用
二维数组元素的一般形式如下:
数组名[下标][下标];
说明
下标可以是整型常量或整型表达式。
例如对一个二维数组的元素进行引用:
array[1][2];
这行代码表示的是对array数组中第2行的第3个元素进行引用。
注意
不管是行下标或者是列下标,其索引都是从0开始的。
这里和一维数组一样要注意下标越界的问题,例如:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P156_74399.jpg?sign=1739599751-TqbdmVz6zRkGbsBWj0MeghmdSgB5bn9I-0-03e521a51b87bb25d79fb04938e0ec43)
上面这种代码的表示方法是错误的:首先array为2行4列的数组,那么它的行下标的最大值为1,列下标的最大值为3,所以array[2][4]超过了数组的范围,下标越界。
7.2.2 二维数组初始化
二维数组和一维数组一样,也可以在声明变量时对其进行初始化。在给二维数组赋初值时,有以下4种情况。
(1)可以将所有数据写在一个大括号内,按照数组元素排列顺序对元素赋值。例如:
int array[2][2] = {1,2,3,4};
如果大括号内的数据少于数组元素的个数时,系统将默认没被赋值的元素值为0。
在为所有元素赋初值时,可以省略行下标,但是不能省略列下标。例如:
int array[][3] = {1,2,3,4,5,6};
系统会根据数据的个数进行分配,一共有6个数据,而数组每行分为3列,当然可以确定数组为2行。
(2)也可以分行给数组元素赋值,例如:
int a[2][3] = {{1,2,3},{4,5,6}};
(3)在分行赋值时,可以只对部分元素赋值,例如:
int a[2][3] = {{1,2},{4,5}};
在上行代码中,各个元素的值如下:
a[0][0]的值是1。
a[0][1]的值是2。
a[0][2]的值是0。
a[1][0]的值是4。
a[1][1]的值是5。
a[1][2]的值是0。
说明
还记得在前面介绍一维数组初始化的情况吗?如果只给一部分元素赋值,则未赋值的部分元素值为0。
(4)二维数组也可以直接对数组元素赋值,例如:
int a[2][3]; a[0][0] = 1; a[0][1] = 2;
这种赋值的方式,就是使用数组中引用的元素。
【例7.6】 使用二维数组保存数据。(实例位置:资源包\源码\ 07\7.06)
本示例将实现为二维数组元素赋值,并显示二维数组的操作。运行程序,显示效果如图7.6所示。
实现代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P157_21153.jpg?sign=1739599751-6yUu5BpeGabJAgqlpOwGKCzZzOvghbE8-0-ec55575aa3021981ac84e2bc267cac59)
图7.6 使用二维数组保存数据
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P157_74410.jpg?sign=1739599751-JKx6Z01eLHZLOt4EasduuNHFTyBBv4wy-0-bd17ef748e82ac6ad482342c7502043d)
在程序中根据每一次的提示,输入相应数组元素的数据,然后先将这个2行3列的数组输出。在输出数组元素时,为了使输出的数据容易观察,使用\t转换字符来控制间距。
7.2.3 二维数组应用
【例7.7】 任意输入一个3行3列的二维数组,求各元素之和。(实例位置:资源包\源码\07\7.07)
在本实例中,使用二维数组保存一个3行3列的数组,利用双重循环访问数组中的每一个元素,然后对每个元素进行累加计算。运行程序,显示效果如图7.7所示。
实现代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P158_21365.jpg?sign=1739599751-T8KRT1o7xLSDelo6OklK4mZQlS83QTff-0-04772de9c7b8c4eb9e469724faf902a0)
图7.7 求各元素之和
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P158_74413.jpg?sign=1739599751-ty4HWHCSiQvIIh7iGc3gsmRPlk2JGgCj-0-a3539b0a314e878f223165085b4597da)
7.3 多维数组
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P159_21485.jpg?sign=1739599751-rmNpRFbmoPiSHXpvx71IZZ1tQB1hQoB9-0-11e0821cd9587de0003da15abdf0fede)
视频讲解
多维数组的定义和二维数组相同,只是下标更多,一般形式如下:
数据类型 数组名[常量表达式1][常量表达式2]…[常量表达式n];
例如定义多维数组如下:
int iArray1[3][4][5]; int iArray2[4][5][7][8];
在上面的代码中分别定义了一个三维数组iArray1和一个四维数组iArray2。由于数组元素的位置都可以通过偏移量计算,所以对于三维数组a[m][n][p]来说,元素a[i][j][k]所在的位置是从a[0][0][0]算起,到(i*n*p+j*p+k)个单位的地方。
7.4 数组的排序算法
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P159_21498.jpg?sign=1739599751-nDbJlsBeB4ZvOUFPE6b4ZKfV3wWQcOPE-0-070a32f9a32f77f9247871d94b51c0e0)
视频讲解
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P159_21509.jpg?sign=1739599751-QfEr6V5SRCIo7dCcGyNy71eOwhif3phe-0-f8c3b8673770be59248217e3bf8ba4c5)
动图演示
通过前面的内容,读者已经了解到数组的理论知识,虽然数组是一组有序数据的集合,但是这里的有序指的是,数组元素在数组中所处的位置,而不是根据数组元素的数值大小进行排列的顺序,那么如何才能将数组元素按照数值的大小进行排列呢?可以通过一些排序算法来实现,本节将带领读者了解一下数组的排序算法。
7.4.1 选择法排序
选择排序法是指每次选择所要排序的数组中最大值(最小值)的数组元素,将这个数组元素的值与最前面没有进行排序的数组元素的值互换。
下面以数字9、6、15、4、2为例,对这几个数字进行排序,每次交换的顺序如表7.1所示。
表7.1 选择法排序
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-T160_74418.jpg?sign=1739599751-IfBVQx3XcO1v8jTGGeqzhNP7cCZJ95XP-0-b7a0dee912bcb5314ebda0b34a5ea105)
由表7.1可以发现,在第一次排序过程中,将第一个数字和最小的数字进行了位置互换,而第二次排序过程中,将第二个数字和剩下的数字中最小的数字进行了位置互换,以此类推,每次都将下一个数字和剩余的数字中最小的数字进行位置互换,直到将一组数字按从小到大排序位置。
下面通过实例来看一下,如何通过程序使用选择法实现数组元素的从小到大排序。
【例7.8】 选择法排序。(实例位置:资源包\源码\07\7.08)
在实例中,声明了一个整型数组和两个整型变量,其中整型数组用于存储用户输入的数字,而整型变量用于存储数值最小的数组元素的数值和该元素的位置,然后通过双层循环进行选择法排序,最后将排序好的数组进行输出。运行程序,显示效果如图7.8所示。
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P160_21618.jpg?sign=1739599751-iL8krmj6zIrb3mVuxY0RPjmDHd7pMzRc-0-394d8dd84a78737e73431b28dca154ec)
图7.8 选择法排序
实现过程如下:
(1)声明一个整型数组,并通过键盘为数组元素赋值。
(2)设置一个嵌套循环,第一层循环为前9个数组元素,并在每次循环时将对应当前次数的数组元素设置为最小值(例如,当前是第3次循环,那么将数组中第3个元素,也就是下标为2的元素设置为当前的最小值),然后在第二层循环中,循环比较该元素之后的各个数组元素,并将每次比较的结果中较小的数设置为最小值,在第二层循环结束时,将最小值与开始时设置为最小值的数组元素进行互换。当所有循环都完成以后,就将数组元素按照从小到大的顺序重新排列了。
(3)循环输出数组中的元素,并在输出5个元素以后进行换行,在下一行输出后面的5个元素。
代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P160_74421.jpg?sign=1739599751-9C30k4zAEKpjFybuoKd967xMfNZAywif-0-1e3db9239441a81490e68968550182de)
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P161_74422.jpg?sign=1739599751-mXXjblpdWiT3CA5PiiVeQVCR1JbxZUHt-0-58a3a207d5063c61a1411f7335e2cb2a)
7.4.2 冒泡法排序
冒泡排序法指的是在排序时,每次比较数组中相邻的两个数组元素的值,将较小的数(从小到大排列)排在较大的数前面。
下面以数字9、6、15、4、2为例,对这几个数字进行排序,每次排序的顺序如表7.2所示。
表7.2 冒泡法排序
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-T162_74429.jpg?sign=1739599751-XxpQe7dGVtFcJAub2r7tMoz8y77gGf7N-0-b686e0ed74342e9fc155ecfe38a099bb)
由表7.2可以发现,在第一次排序过程中,将最小的数字移动到第一的位置,并将其他数字依次向后移动,而第二次排序过程中,将从第二个数字开始的剩余数字中选择最小的数字移动到第二的位置,剩余数字依次向后移动,以此类推,每次都将从下一个数字开始的剩余的数字中选择最小的数字,移动到当前剩余数字的最前方,直到将一组数字按从小到大的顺序排序完成为止。
下面通过实例来看一下,如何通过程序使用冒泡法实现数组元素的从小到大排序。
【例7.9】 冒泡法排序。(实例位置:资源包\源码\07\7.09)
在实例中,声明了一个整型数组和一个整型变量,其中整型数组用于存储用户输入的数字,而整型变量则作为两个元素交换时的中间变量,然后通过双层循环进行冒泡法排序,最后将排序好的数组进行输出。运行程序,显示效果如图7.9所示。
实现过程如下:
(1)声明一个整型数组,并通过键盘为数组元素赋值。
(2)设置一个嵌套循环,第一层循环为后9个数组元素,然后在第二层循环中,从最后一个数组元素开始向前循环,直到前面第一个没有进行排序的数组元素,循环比较这些数组元素,如果在比较中,后一个数组元素的值小于前一个数组元素的值,则将两个数组元素的值进行互换,当所有循环都完成以后,就将数组元素按照从小到大的顺序重新排列了。
(3)循环输出数组中的元素,并在输出5个元素以后进行换行,在下一行输出后面的5个元素。
代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P162_22051.jpg?sign=1739599751-k1097gzY1apFZk17lopaQKjIV0hPBc2C-0-82f9149c923beacbb2d39aed2f0afe61)
图7.9 冒泡法排序
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P162_74424.jpg?sign=1739599751-7TomSahZNsAObBHuoMPqhWMMO6E2ImDc-0-2a01f88e2673815b46a10c2844e7b4ef)
7.4.3 交换法排序
交换法是将每一位数与其后的所有数一一比较,如果发现符合条件的数据则交换数据。首先,用第一个数依次与其后面的所有数进行比较,当存在比其值大(小)的数,则交换这两个数,继续向后比较其他数直至最后一个数。然后在使用第二个数与其后面的数进行比较,当存在比其值大(小)的数,则交换这两个数,继续向后比较其他数直至最后一个数。以此类推,直至最后一个数比较完成。
下面以数字9、6、15、4、2为例,对这几个数字进行排序,每次排序的顺序如表7.3所示。
表7.3 交换法排序
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-T163_74433.jpg?sign=1739599751-LiYK8y5FNVMzNnb9HGkZAqoiKIC8J2ET-0-cd85151d43ebf2b3ac06671ea3c75552)
由表7.3可以发现,在第一次排序过程中,将第一个数与后边的数依次进行比较,首先比较9和6,9大于6,交换两个数的位置,然后数字6成为第一个数字。用6和第三个数字15进行比较,6小于15,保持原来的位置。然后用6和4进行比较,6大于4,交换两个数字的位置。再用当前数字4与最后的数字2进行比较,4大于2,则交换两个数字的位置。从而得到表7.3中第一次的排序结果,然后使用相同的方法,从当前第二个数字9开始,继续和后边的数字进行比较,如果遇到比当前数字小的数字则交换位置,以此类推,直到将一组数字按从小到大的顺序排序完毕为止。
下面通过实例来看一下,如何通过程序使用交换法实现数组元素的从小到大排序。
【例7.10】 交换法排序。(实例位置:资源包\源码\07\7.10)
在实例中,声明了一个整型数组和一个整型变量,其中整型数组用于存储用户输入的数字,而整型变量则作为两个元素交换时的中间变量,然后通过双层循环进行交换法排序,最后将排序好的数组进行输出。运行程序,显示效果如图7.10所示。
实现过程如下:
(1)声明一个整型数组,并通过键盘为数组元素赋值。
(2)设置一个嵌套循环,第一层循环为前9个数组元素,然后在第二层循环中,使用第一个数组元素分别与后边的数组元素依次进行比较,如果后边的数组元素值小于当前数组元素值,则交换两个元素值,然后使用交换后的第一个数组元素继续与后边的数组元素进行比较,直到本次循环结束,将最小的数组元素值交换到第一个数组元素的位置,然后从第二个数组元素开始,继续与后面的数组元素进行比较,以此类推,直到循环结束,就将数组元素按照从小到大的顺序重新排列了。
(3)循环输出数组中的元素,并在输出5个元素以后进行换行,在下一行输出后面的5个元素。
代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P164_22425.jpg?sign=1739599751-aJ57kh4Zh9DeJMYvjbb5yaqxgqYdNPIW-0-4f123903e4392f49e5d75b647819f40f)
图7.10 交换法排序
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P164_74438.jpg?sign=1739599751-HQyc1S1bF9OdMsXp4bDGFRnmxiA3K1kj-0-b1cb61d04e155099f5705cd9a6aaefef)
7.4.4 插入法排序
插入法较为复杂,它的基本工作原理是,抽出一个数据,在前面的数据中寻找相应的位置插入,然后继续下一个数据,直到完成排序。
下面以数字9、6、15、4、2为例,对这几个数字进行排序,每次排序的顺序如表7.4所示。
表7.4 插入法排序
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-T165_74442.jpg?sign=1739599751-Tk4BgHFLZUKIR8gmKwDhW0SzLjFk8DMO-0-64230b62a069e3360ff1bdda48d434b3)
由表7.4可以发现,在第一次排序过程中,将第一个数取出来并放置在第一个的位置,然后取出第二个数,并使用第二个数与第一个数进行比较,如果第二个数小于第一个数,则将第二个数排在第一个数之前,否则,将第二个数排在第一个数之后。然后取出下一个数,先与排在后面的数字进行比较,如果当前数字比较大,则排在最后;如果当前的数字比较小,还要与之前的数字进行比较,如果当前的数字比前面的数字大,则将当前数字排在比它小的数字和比它大的数字之间,如果没有比当前数字小的数字,则将当前数字排在最前方。以此类推,不断取出需要排序的数字与排序好的数字进行比较,并插入到相应的位置,直到将一组数字按从小到大的顺序排序完毕为止。
下面通过实例来看一下,如何通过程序使用交换法实现数组元素的从小到大排序。
【例7.11】 插入法排序。(实例位置:资源包\源码\07\7.11)
在实例中,声明了一个整型数组和两个整型变量,其中整型数组用于存储用户输入的数字,而两个整型变量分别作为两个元素交换时的中间变量和记录数组元素的位置,然后通过双层循环进行交换法排序,最后将排序好的数组进行输出。运行程序,显示效果如图7.11所示。
实现过程如下:
(1)声明一个整型数组,并通过键盘为数组元素赋值。
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P166_22767.jpg?sign=1739599751-Vgl3Yv62RDdNSYmAK3bkuQhUMyhZXGcl-0-dbbe5f631b41f4d588865a5e9a7d0fa3)
图7.11 插入法排序
(2)设置一个嵌套循环,第一层循环为后9个数组元素,将第二个元素赋值给中间变量,并记录前一个数组元素的下标位置。然后在第二层循环中,首先要判断是否满足循环的条件,允许循环的条件是记录的下标位置必须大于等于第一个数组元素的下标位置,并且中间变量的值小于之前设置下标位置的数组元素。如果满足循环条件,则将设置下标位置的数组元素值赋值给当前的数组元素,然后将记录的数组元素下标位置向前移动一位,继续进行循环判断。内层循环结束以后,将中间变量中保存的数值,赋值给当前记录的下标位置之后的数组元素,继续进行外层循环,将数组中下一个数组元素赋值给中间变量,再通过内层循环进行排序。以此类推,直到循环结束,就将数组元素按照从小到大的顺序重新排列了。
(3)循环输出数组中的元素,并在输出5个元素以后进行换行,在下一行输出后面的5个元素。
代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P166_74447.jpg?sign=1739599751-SGwIjBPJtM6SYCZG4VpbZPjqZFRPUcdY-0-fd55e727f47135d62bf1db4f2b79d314)
7.4.5 折半法排序
折半法排序又称为快速排序,是选择一个中间值middle,然后把比中间值小的数据放在左边,比中间值大的数据放在右边(具体的实现方法是从两边的数据中找,找到一对后交换位置),然后对两边分别递归的过程。
下面以数字9、6、15、4、2为例,对这几个数字进行排序,每次排序的顺序如表7.5所示。
表7.5 插入法排序
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-T167_74452.jpg?sign=1739599751-NEu7AiGJni5gZ6SHux8QOZZYKAWr9KVJ-0-af0fad45536fe17da463549da90c266f)
由表7.5可以发现,在第一次排序过程中,首先获取数组中间元素的值15,从左右两侧分别取出数组元素与中间值进行比较,如果左侧取出的值比中间值小,则取下一个数组元素与中间值进行比较,如果左侧取出的值比中间值大,则交换两个互相比较的数组元素值;而右侧的比较正好与左侧相反,当右侧取出的值比中间值大时,取前一个数组元素的值与中间值进行比较,如果右侧取出的值比中间值小,则交换两个互相比较的数组元素值。当中间值两侧的数据都比较一遍以后,数组以第一个元素为起点,以中间值的元素为终点,用上面的比较方法继续进行比较;而右侧以中间值的元素为起点,以数组最后一个元素为终点,用上述方法进行比较。当比较完成以后,继续以减半的方式进行比较,直到将一组数字按从小到大的顺序排序完毕为止。
下面通过实例来看一下,如何通过程序使用交换法实现数组元素的从小到大排序。
【例7.12】 折半法排序。(实例位置:资源包\源码\07\7.12)
在实例中,声明了一个整型数组,用于存储用户输入的数字,再定义一个函数,用于对数组元素进行排序,最后将排序好的数组进行输出。运行程序,显示效果如图7.12所示。
实现过程如下:
(1)声明一个整型数组,并通过键盘为数组元素赋值。
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P168_23095.jpg?sign=1739599751-x0TPUtzNcuZcy6pX0KLhX9Y4szIKQUJ6-0-dc13ab46bb0166079af3b33fd95f0120)
图7.12 折半法排序
(2)定义一个函数,用于对数组元素进行排序,函数的3个参数分别表示递归调用时,数组最开始的元素和最后元素的下标位置以及要排序的数组。声明两个整型变量,作为控制排序算法循环的条件,分别将两个参数赋值给变量i和j,i表示左侧下标,j表示右侧下标。首先使用do-while语句设计外层循环,条件为i小于j,表示如果两边的下标交错,就停止循环。内层两个循环分别用来比较中间值两侧的数组元素,当左侧的数值小于中间值时,取下一个元素与中间值进行比较,否则退出第一个内层循环;当右侧的数值大于中间值时,取前一个元素与中间值进行比较,否则退出第二个内层循环。然后判断i的值是否小于等于j,如果是,则交换以i和j为下标的两个元素值,继续进行外层循环。当外层循环结束以后,用从数组第一个元素到以j为下标的元素为参数递归调用该函数,同时,用以i为下标的数组元素到数组最后一个参数作为参数递归调用该函数,以此类推,直到将数组元素按照从小到大的顺序重新排列为止。
(3)循环输出数组中的元素,并在输出5个元素以后进行换行,在下一行输出后面的5个元素。
代码如下:
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P168_74459.jpg?sign=1739599751-CeESlwSgvBsUoR2oxVjjL4zqXr26fMAY-0-71b260efd49f0ea905a97b1a647edfc8)
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P169_74461.jpg?sign=1739599751-a8Y66VlTGVhhMbbTa9zU0LEAXtgdPuQf-0-0953fe8e91d780a7531af1de8137021b)
注意
为了实现折半法排序,需要使用函数的递归,这部分内容将会在后面章节进行介绍,读者可以参考后面的内容进行学习。
7.4.6 排序算法的比较
在前面已经介绍了5种排序方法,那么读者在进行数组排序时应该使用哪一种方法呢?这就需要用户根据需要来进行选择。下面来对这5种排序方法进行简单的比较。
(1)选择法排序
选择法排序在排序过程中共需进行n(n-1)/2次比较,最坏的情况下互相交换n-1次。选择法排序简单、容易实现,适用于数量较小的排序。
(2)冒泡法排序
最好的情况下,就是正序,所以只要比较一次就行了;最坏的情况下,就是逆序,要比较n^2次才行。冒泡法排序是较稳定的排序方法,当待排序列有序时,效果比较好。
(3)交换法排序
交换法排序和冒泡法情况类似,正序时最快,逆序时最慢,排列有序的数据时效果最好。
(4)插入法排序
此算法需要经过n-1次插入过程,如果数据恰好插入到序列的最后端,则不需要移动数据,可节省时间,所以若原始数据基本有序,此算法可有较快的运算速度。
(5)折半法排序
折半法排序对于n较大时,是排序速度最快的排序算法,但当n很小时,此方法往往比其他排序算法还要慢。另外,折半法排序是不稳定的,对有相同关键字的数据,排序后的结果可能会次序颠倒。
插入法、冒泡法、交换法排序的速度较慢,但参加排序的序列局部或整体有序时,这种排序方法能达到较快的速度。而在这种情况下,折半法排序会显得速度较慢。当n较小时,且对稳定性无要求时宜用选择排序法,对稳定性有要求时宜用插入法或冒泡法排序。
7.5 实战
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P170_23386.jpg?sign=1739599751-1R3AMIex3dUzi6Vc3KQhxaTVzPFECW2o-0-02516def3c2bcc673413b39b0c81e598)
视频讲解
7.5.1 选票统计
班级竞选班长,共有3个候选人,输入参加选举的人数及每个人选举的内容,输出3个候选人最终的得票数及无效选票数。运行结果如图7.13所示。(实例位置:资源包\源码\07\实战\01)
本实例是一个典型的一维数组应用,这里需要强调的一点就是,C语言规定只能逐个引用数组元素而不能一次引用整个数组,在本程序中,这点体现在对数组元素进行判断时,只能通过for语句对数组中的元素逐个进行引用。
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P170_23381.jpg?sign=1739599751-Yx4SGd9JruD9XOdeegQ4opDxkiYdQo1m-0-98ed2db35b44758e125d6836cc8ad5d4)
图7.13 选票统计
7.5.2 模拟比赛打分
首先从键盘中输入选手人数,然后输入裁判对每个选手的打分情况,假设裁判有5位,在输入完所有数据之后,输出每个选手的总成绩。运行结果如图7.14所示。(实例位置:资源包\源码\07\实战\02)
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P171_23400.jpg?sign=1739599751-Fs4RSwLasU6Y0Kb3vAEp8WHaIjawcncq-0-3200628175ad3977b95c14fb947ca1d3)
图7.14 模拟比赛打分
程序中使用了嵌套的for循环,外层的for循环是控制选手人数变化的,内层for循环是控制5个裁判打分情况的。这里要注意由于不知道选手的人数,所以存储裁判所打分数的数组的大小是随着选手人数变化的,因为有5个裁判,所以当数组下标能被5整除时则跳出内层for循环,此时计算出的总分是5名裁判给一名选手打分的结果,将此时计算出的总成绩存到另一个数组中。输出选手成绩时也是遵循上面规律的。
7.5.3 统计学生成绩
输入学生的学号及语文、数学、英语成绩,输出学生各科成绩信息及平均成绩。运行结果如图7.15所示。(实例位置:资源包\源码\07\实战\03)
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P171_23406.jpg?sign=1739599751-J1TPXzfUrDfR5j3fC725PB7icTK0iGlK-0-c57ce706fb26df949680c843afaf8ac7)
图7.15 统计学生成绩
7.5.4 矩阵的转置
将一个二维数组的行和列元素互换,存到另一个二维数组中。运行结果如图7.16所示。(实例位置:资源包\源码\07\实战\04)
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P172_23416.jpg?sign=1739599751-5M5aaLZUerpYfKjZ8pkRHdCyuznA39Xb-0-2d98540ab266e3b0f29c002e74d97360)
图7.16 矩阵转置
7.5.5 设计魔方阵
魔方阵就是由自然数组成的方阵,方阵的每个元素都不相等,且每行和每列以及主副对角线上的各元素之和都相等。运行结果如图7.17所示。(实例位置:资源包\源码\07\实战\05)
![](https://epubservercos.yuewen.com/E2F069/15825991605218906/epubprivate/OEBPS/Images/Figure-P172_23421.jpg?sign=1739599751-zoLUYDtEdH6FJ1PiTvQjzuXV5DhGwztD-0-5dc06e71d2bd1a0aa74ec3203ed77e01)
图7.17 设计魔方阵