数组出现的理由及一维数组的应用11-5日

友情提示:由于上课期间发现了几个代码错误,已订正,谢谢大家。电脑近期出现了故障,装的软件全是乱码,所以近期无法调试程序,嘿嘿,正好你们可以找找错误哦。

## 1. 数组出现的理由

问题1:如何求解从键盘输入的n个数据的和?
大家都知道,针对这个问题,可以通过循环来实现。

#include
int main()
{
	int n,sum=0,i,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&t);
		sum=sum+t;
	}
	printf("sum=%d\n",t);
	return 0;	
}
  • **分析:**用t来依次存储这n个数据。新输入的数据会将上一个数据覆盖掉,最终t里面存储的是最后一次输入的数据。前n-1个数据并未得到保存。
  • 思考:如果遇到需要保存所有原始数据的情况,例如有时候需要核对数据,计算的结果对不对呀;随后可能还需要对这些数据进行其它操作呢。此刻,我们该怎么办呢?
    显然很简单,定义n个变量即可,让n个数据分别存储到这n个变量里面。如果n很小,例如n=3,声明3个int变量就可以了。如果n为10000呢,就需要声明10000个int变量,其繁琐程度可想而知。用什么方法来处理这10000个变量呢?可采用数组,它就是用于存储和处理大量同类型数据的数据结构。
    - 什么是数组?
    数组属于自定义数据类型,用于
    存储和处理
    大量同类型数据的数据结构。如何声明一个数组呢?必须确定三个方面:确定数组的名称;确定数组元素的类型;确定数组的结构(维数及每一维的大小)。
    int a[3];
    定义一个数组a,里面有3个元素,分别用a[0]、a[1]和a[2]来表示,元素类型均为int。
    int b[3]={1,2,3};
    定义一个数组b,并初始化3个元素的值:b[0]=1, b[1]=2, b[2]=3,所有元素均为int。
    问题:如何求解从键盘输入的10个数据相加的和(保存这10个数据)?
#include
int main()
{
	int a[10],sum=0,i;
	for(i=0;i<10;i++)
	{
		scanf("%d",&a[i]);
		sum=sum+a[i];
	}
	printf("sum=%d\n",sum);
	return 0;	
}

其实,细心的我们可以发现,采用数组的方法并没有节省内存空间,也没有节省变量。如果我们不采用数组,就需要定义10个变量来存储10个数据,采用数组的话,是将这10个数据存放在数组a中,用a[i]来表示数组中的各个元素。
由此可知:与定义10个变量来存储10个数据的方法相比,采用数组只是在程序的描述上更加方便而已。

  • 一维数组的常见操作
    C语言常常要对数组进行遍历(访问各个元素)、寻找最值(寻找最大或最小值)、排序等操作,灵活地使用数组对实际开发很重要。

3.1 数组的遍历

数组的遍历指的是:依次访问数组中的各个元素。
编程实例:定义一个数组a,将1,2,3,4,5这5个数据存储在a中,并将它们输出。
将a中各个元素输出,所以说需要访问各个元素,由于数组元素的表示方法为:a[i]。所以可采用循环语句,并且用标号i递增的方法。

#include
int main( )
{
	int a[5]={1,2,3,4,5},i;
	for(i=0;i<5;i++)
		printf("%d\t",a[i]);
	printf("\n");
	return 0;
}

3.2 数组的最值

编程实例:从1,5,3,8,6,12,90,0,13,5中找出最大值和最小值,并输出。
分析:定义数组来存储这10个元素,先假定数组中下标为0的元素是最大值;然后将最大值与数组中下标为1的元素进行相比,如果后者大于最大值,则用后者替代最大值;依次类推,一直到将下标为9的元素与最大值进行比较后为止。
同理,先假定数组中下标为0的元素是最小值;然后将最小值与数组中下标为1的元素进行相比,如果后者小于最小值,则用后者替代最小值;依次类推,一直到将下标为9的元素与最小值进行比较后为止。

#include
int main()
{
	int a[10]={1,5,3,8,6,12,90,0,13,5},i;
	int max,min;
	max=min=a[0];
	for(i=1;i<10;i++)
	{
		if(a[i]>max)
			max=a[i];
		if(a[i]

3.3数组的排序

在操作数组时,经常需要对数组中的元素进行排序,有三个比较常见的排序算法:选择排序、冒泡排序和插入排序。

3.3.1选择排序

问题:输入6个学生的成绩,将其从小到大进行排序。
分析:可将6个数据存入一个数组中。采用选择排序算法来进行排序。具体步骤如下:
步骤1:在数组中选择出最小的元素,将其与下标为0的元素进行交换,即数组的首元素存放的是最小的数据;
步骤2:由于下标为0的位置已是最小数据,所以需要从下标为1开始一直到下标为5的元素中找出最小的元素,将它与下标为1的元素进行交换,即整个数组中次小的元素放在了下标为1的位置;
步骤3:由于下标为0和下标为1的位置已是最小及次小数据,所以需要从下标为2开始一直到下标为5的元素中找出最小的元素,将它与下标为2的元素进行交换,即整个数组中第三小的元素放在了下标为2的位置;
依次类推。。。。
最后一个步骤:数组中只剩两个元素了,也即下标为4和下标为5两个元素,比较二者大小,判断是否交换。排序完成。
如何编程实现上述排序过程呢?
肯定要用到循环,第一层循环计数从0到4,来控制比较的趟数。6个元素一共需要比较5趟,所以循环计数从0到4,一共是5;第二层循环计数从i+1到5(5为最后一个元素的下标),来控制每趟需要进行比较的次数。
注意:在程序中,min不是存储最小的数据,min是最小元素在数组中的下标。

#include
int main()
{
	double score[6];
	int i,j,min,temp;
	for(i=0;i<6;i++)
		scanf("%lf",&score[i]);
	for(i=0;i<5;i++)
		{
			min=i;
			for(j=i+1;j<6;j++)
				if(score[j]

因为min是所要查找范围内的最小元素的下标,所以当min!=i时,说明score[i]不是所要查找范围内的最小元素,要将score[min]换到下标为i的位置。当min==i时,说明score[i]就是所要查找范围内的最小元素,无需交换。
思考:能不能把选择排序操作放在一个子函数中实现,main函数向它传递数据,由子函数来完成排序,最终排序后的数据反馈给main函数。这样的话,排序的子函数可以被很多人拷贝走直接来实现,多方便呀。

#include
void SelSort(double s[],int n)
{
	int i,j,min,temp;
	for(i=0;i

子函数SelSort的形参:double s[],int n。s接收主函数传递过来的数组,n接收数组的大小。
重磅抛出问题:s是子函数SelSort的一个形参,因而是它的局部变量,在子函数中排序的是s中数据元素,那么主函数中的score数组中的元素会不会被排序???

3.3.2冒泡排序

同样的问题:输入6个学生的成绩,将其从小到大进行排序。
冒泡排序名字的由来;在冒泡排序的过程中,不断地比较数组中相邻的两个元素,较小者向上浮,较大者往下沉,整个过程和水中气泡上升的原理相似。
具体步骤如下:
步骤1:从下标为0的元素开始,将相邻的两个元素依次进行比较,直到最后两个元素完成比较。在进行比较的过程中,如果前一个元素(下标小的)比后一个元素(下标大的)大,则进行位置的交换;这一趟下来,数组中最后一个元素就是整个数组中的最大值;
步骤2:除最后一个已知是最大值的元素(下标为5)外。从下标为0的元素开始,将相邻的两个元素依次进行比较,直到最后两个元素(二者的下标分别是3和4)完成比较。在进行比较的过程中,如果前一个元素(下标小的)比后一个元素(下标大的)大,则进行位置的交换;这一趟下来,数组中倒数第二个元素就是整个数组中的次大值。
步骤3:除最后两个已知是最大和次大值的元素(下标为5和4)外。从下标为0的元素开始,将相邻的两个元素依次进行比较,直到最后两个元素(二者的下标分别是2和3)完成比较。在进行比较的过程中,如果前一个元素(下标小的)比后一个元素(下标大的)大,则进行位置的交换;这一趟下来,数组中倒数第三个元素就是整个数组中的第三大值。
依次类推。。。。
最后一个步骤:数组中只剩两个元素了,也即下标为0和下标为1两个元素,比较二者大小,判断是否交换。排序完成。
如何编程实现上述排序过程呢?
肯定要用到循环,第一层循环计数i从0到4,来控制比较的趟数。6个元素一共需要比较5趟,所以循环计数从0到4,一共是5;第二层循环计数j从0到4-i,来控制每趟需要进行比较的次数。举个例子,我们可以发现,第0趟需要比较5次,第1趟需要比较4次。。。第4趟需要比较1次。
也就是说:当i=0时,j控制比较次数为5,需从0,1,2,3,4变换,因而j的值最大等于4-i;当i=1时,j控制比较次数为4,需从0,1,2,3变换,因而j的值最大也等于4-i;。。。
程序为:

#include
int main()
{
	double score[6];
	int i,j,temp;
	for(i=0;i<6;i++)
		scanf("%lf",&score[i]);
	for(i=0;i<5;i++)
		for(j=0;j<=4-i;j++)
			if(score[j]

思考:能不能把冒泡排序操作放在一个子函数中实现,main函数向它传递数据,由子函数来完成排序,最终排序后的数据反馈给main函数。

#include
void BubbleSort(double s[],int n)
{
	int i,j,temp;
	for(i=0;i

子函数BubbleSort的形参:double s[], int n。s接收主函数传递过来的数组,n接收数组的大小。
重磅抛出问题:s是子函数BubbleSort的一个形参,因而是子函数的局部变量,在子函数中排序的是s中数据元素,那么主函数中的score数组中的元素会不会被排序???

3.3.3插入排序

插入排序指的是:将一个待排序的元素插入到已经排序的元素中的适当位置,直到所有元素插入完毕。
同样的问题:输入6个学生的成绩,将其从小到大进行排序。采用插入排序的具体步骤如下:
步骤1:将下标为0的元素视为已排序好的元素。
步骤2:将下标为1的元素与下标为0的元素进行比较,如果其小于下标为0的元素,则将下标为0的元素向后移动,存放在下标为1的位置上,原本在下标为1的元素则存放在下标为0的位置(如果下标为1的元素大于下标为0的元素,则不执行任何操作)。这样下标为0和1的元素就是排好序的。
步骤3:将下标为2的元素与下标为1的元素进行比较,如果其小于下标为1的元素,则将下标为1的元素向后移动,存放在下标为2的位置上,继续将下标为2的元素与下标为0的元素进行比较,如果其小于下标为0的元素,则将下标为0的元素向后移动,存放在下标为1的位置,原本在下标为2的元素则放在下标为0的位置。这样前三个元素就是排好序的。注意:如果下标为2的元素大于下标为1的元素,则不进行移动,并且不再继续将其与下标为0的元素进行比较。如果下标为2的元素大于下标为0的元素,则将下标为2的元素插入到下标为1的位置。
以此类推。。。
步骤n:将最后一个元素与前面的元素进行比较,找到它的位置,插入即可,排序完成。

#include
int main()
{
	double score[6];
	int i;
	for(i=0;i<6;i++)
		scanf("%lf",&score[i]);
	for(i=1;i<6;i++)
	{
		temp=score[i];
		j=i;
		while(j>0&&score[j-1]>temp)
		{
			score[j]=score[j-1];
			j--;
		}
		score[j]=temp;
	}
	for(i=0;i<6;i++)
		printf("%lf\t",score[i]);
	return 0;
}

采用子函数的实现形式如下:

#include
void InsertSort(double s[],int n)
{
	double temp;
	int i,j;
	for(i=1;i0&&s[j-1]>temp)
		{
			s[j]=s[j-1];
			j--;
		}
		s[j]=temp;
	}	
}
int main()
{
	double score[6];
	int i;
	for(i=0;i<6;i++)
		scanf("%lf",&score[i]);
	InsertSort(score,6);
	for(i=0;i<6;i++)
		printf("%lf\t",score[i]);
	return 0;
}

3.4二分查找法

有时候我们还需要查找数组中的某一个元素。前面已经讲过如何查找数组中的最大或最小值。

3.4.1 无序数组的查找

对于一个无序的数组来说,需要从数组的第0个元素开始一直到数组的最后一个元素为止。

#include
int main()
{
	int a[10],i,s;
    for(i=0;i<10;i++)
    	scanf("%d",&a[i]);
    printf("input the data that you needs select");
    scanf("%d",s);
	for(i=0;i<10;i++)
	{
		if(a[i]==s)
			printf("a[%d]=%d\n",i,a[i]);
	}	
	return 0;
}    

如果a[i]==s则找到了该元素,如果数组中有多个相同的该元素,可继续找;如果数组中的元素均不相同,在找到该元素后,就采用break结束循环。

3.4.2 有序数组的查找

对于一个有序的数组来说,如果还从数组的开头一一查找的话,效率太低了。可采用二分查找法。
二分查找法,又称为折半查找法。具体步骤如下:
步骤1:找到数组的中间位置,将要查找的数据与中间位置上的数据进行比较,若相等,则查找成功;否则从中间位置将数组一分为二。
步骤2:如果要查找的数据小于中间位置上的数据,则在数组的前半部分进行查找;否则在后半部分查找;
步骤3:重复步骤2,直到找到所需的数据,即查找成功;如果没有找到所需的数据,说明该数据不存在。
问题:在有序数组中寻找数据。

#include
int main()
{
	int score[6]={11,22,4466,88,99};
	int lower,high,mid,m;
	lower=0;high=5;
	scanf("%d",m);
	while(lower<=high)
	{
		mid=(lower+high)/2;
		if(score[mid]==m)
		{
			printf("success!\n");
			break;
		}	
		else if(score[mid]