C语言的数组、函数、基础搜索算法

稍微进阶一点，对于学过其他语言的朋友，只需要看看在C里面，它们是怎么写的即可

数组

数组是一种把元素集合在一个地方的方式

数组初步介绍

当我们要存储同一类型的多个变量时，我们使用数组
可以把数组看成一个篮子，相同类型的变量全部放进去 

1
2
3
4
5
6
7
<数组类型> <名字> [大小] ;
如： int GroupA [100];

通俗来说，就是:
<类型> <名称> [元素数量]        这里的类型是指数组内部存储的数据的类型 
	int grades[100]; 
	char weight[20];

数组通过下标 index来访问对应位置的变量，下标从0开始
我们上面定义了大小为100的数组，则下标范围是0-99

元素数量必须是整数

在C99之前：元素数量必须是编译时刻确定的字面量 (不能是变量、程序运行过程中动态产生的数字)

数组定义实例: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
int main(){
	//写一个程序，计算平均数并输出大于平均数的数字 
	
	int x ;
	double sum = 0;
	int cnt = 0 ;
	int number [100]; //定义一个数组，其大小为100个 
	//int 名字A [大小X] 表示这个数组A里面最多可以放 X个int    
	
	scanf("%d",&x);
	while (x! = -1){
		number [cnt] = x ;  //让数组上cnt位置的那个单元=x ；而cnt是递增的，所以x分别会在1，2，3....位置上存放 
		//对数组中的元素进行赋值
		 
		sum += x ;
		cnt ++;
		scanf ("%d",&x);
	} 
	if (cnt > 0 ){
		printf("%f \n",sum/cnt);
		int i ;
		for (i = 0 ; i<cnt;i++){  //进行数组数字的输出。遍历数组
		//遍历数组:浏览整个数组 
		 
			if (number[i]>sum/cnt){//使用数组中的元素 
				printf("%d \n",number[i]);
				//当数组i位置的数符合条件，输出它 
			}
			
		} 
	}
	
	;return 0 ;
}
小结

1.数组中的元素具有相同的数据类型
2.一旦创建，数组不能改变其大小
3.使用数组时在[]中的数字是下标/索引，下标从0开始计数
4.！！无论是编译器还是运行环境，都不会去检查下标是否越界，无论你在读还是写(segmentation fault)
5.数组中的元素在内存中是连续依次排列的
6.可以创建长度为0的数组，但是没什么锤子用

二维数组

我们把数放到一个方形区域里来，通过”行+列”来确定一个元素，就像一个坐标/一个表格
二维数组的定义和使用同一维，不过它有两个中括号，代表行列，先行后列

遍历二维数组将利用嵌套循环
下面是二维数组的定义和使用的例子： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <stdio.h>
int main(void){
	int a [3][5] ; //定义了一个三行五列的矩阵，定义基本都是先行(y数)后列(x数)的
	int therow = 3 ; 
	int thecol = 5 ;
	//二维数组的遍历
	for(int i=0;i< therow ;i++){
		for(int j=0;j<thecol;j++){
			a [i][j] = (i+1)*(j+1) ;  //数组名字+数组下标，就可以表示这是一个普通的变量了，可以在一些地方直接使用
			printf("%d \n",a[i][j]);
		}
	}
	
	//二维数组初始化
	int b [][5] = {
		{1,2,3,4,5},
		{6,2,4,5,7},
		
	};
	/*
		列数是不可以省略的，函数可以让编译器自己整
		每个{}之间使用大括号隔开，最后一个的逗号存不存在无所谓，如果省略，表示“补零”
	*/
	
	; return 0 ;
}

数组的集成初始化

集成初始化时的定位：
1.用[n]在初始化数据中给出定位
2.没有定位的数据会接在前面的位置后面
3.其它位置的数值同前文，补为0
4.也可以不给出数组的大小，让编译器自己算
5.这种做法比较适合初始数据稀疏的数组 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
int main (void){
	
	int a [] = {1,2,3,5,6,7};  //集成初始化
	for(int i=0;i<7;i++){  //这里提一句，很多时候习惯使用<某个阙值
		printf("%d \t",a[i]);
	}
	
	//如果一开始就规定了数组的大小，但是没有填充完数组，那么会把剩余未规定的部分全部初始化为0
	
	//int a [10] ={2};
	
	
	//int b[10] = {[0] = 2 , [2] =3 ,6 ,};  只能在C99下使用				
	
	//sizeof可以给出整个数组所占据的内容的大小，单位为字节。在整形数组中，一个单位4字节
	
	printf("\n %d \n",sizeof(a));
	printf("\n %d \n",sizeof(a[0]));
	printf("\n 所以a的大小就是 %d \n",sizeof(a) / sizeof(a[0]));
	
	//sizeof(a) / sizeof(a[0] 起到了Java中类似与length系列的作用

	; return 0 ; 
}

数组不能直接被赋值，像 int b [] = a 是不行的,我们只能使用遍历来完成这件事
数组作为函数参数时，我们习惯于用另一个参数来传入数组的大小

函数

函数，又叫方法。可以看作函数是一系列代码的代表

定义函数

<返回值> <函数名字>(参数表){
函数执行，如果有返回值的话要return
}

比如我们定义一个加法的函数sum 

1
2
3
4
5
6
7
8
void sum(int begin,int end){
	int i ; 
	int sum = 0 ; 
	for(i=begin ; i<=end ;i++){
		sum+= i;
	}
	printf("%d 到 %d的和是%d \n",begin,end,sum);
}

这个函数的意思就是，输入一个begin和end，得到程序会打印出它们的和

定义的函数要写在用它的地方之前才行，比如我想在主函数中使用sum函数，就要先写它
实例： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
void sum(int begin,int end){
	int i ; 
	int sum = 0 ; 
	for(i=begin ; i<=end ;i++){
		sum+= i;
	}
	printf("%d 到 %d的和是%d \n",begin,end,sum);
}
/*
在这里，我们在主函数之前定义了一个自己的函数sum 
*/
int main (void){
	sum(1,10);//在这里，我们运用了自己的sum函数 
	sum(20,30);
	sum(35,45); 
	; return 0 ;
}

显然，这样子并不美观，那么我们可以先用原型声明来“占位”

原型声明

我们可以现在最开始声明我们这个函数的基本内容，而不写执行代码
然后在主函数结束后，再在后面补上对应的执行代码
比如： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <stdio.h>
//C的编译器是由上而下来分析代码的，这导致你要用的函数需要在前面先写出来
//但是可以把函数头加上分号放在前面，其它部分放在后面，这样就可以了。这个做法叫做  原型声明 
void sum (int a , int b);  //声明 

int main ()
{
	sum(1,10);
	; return 0 ; 
}

void sum (int a, int b){  //定义 
	int i ; 
	int sum = 0 ; 
	for (i =a ; i <=b ; i ++){
		sum +=1 ;  
	}
}

//另外，原型声明里面可以只给参数类型，不给参数名字。因为原型声明的意义就是让编译器知道有这个东西 
```  

### 返回值return
返回返回值的操作是必不可少的，而且要和你所声明的返回值的数据类型对应    
当然，如果你声明返回值是void（无）,那就不用return了   	
```C
#include <stdio.h> 、
//当使用void类型的函数时，函数是没有返回值的，也就是可以没有return 
int max (int a,int b)
{//返回值是int类型的函数max 
	int ret ; 
	if(a>b){
		ret = a ; 
	}else {
		ret = b ; 
	}
	return ret ; //返回一个ret的数值，另外在一个函数里面可以有多个return语句，而且return不一定要在尾（不过这不是单一出口，习惯不好） 
}

int main () {
/* return 
1.return 会停止函数的运行，并且返回一个值
2.写法  return <值> ;  或者  return[表达式] ;
 
*/
int a,b,c ; 
c = max(12,10);
printf("%d \n ",c);


return 0 ; 
}

```  

### 参数传递和本地变量
函数每次运行都产生独立的变量空间   
在这个空间中的变量是它这次运行独有的，称为**本地变量**   
定义在函数内部的变量就是**本地变量/局部变量**    
参数也是**本地变量/局部变量**   

**生存期**：变量从出现到消失的时间     
**作用域**：该变量可以起作用的范围    
对于本地变量，二者属于一个范围，那就是大括号内，我们把他叫**块**  

1.本地变量是定义在块内的，可以是函数块内，也可以是语句块内   
2.程序运行到某个块之前，该块其中的变量是不存在的，离开了之后，其中的变量也会消失	
块外面定义的变量在块里面是依然生效的	
3.如果块里面定义了和外面同名的变量，那么块内的变量会覆盖外面的	
4.一个块中是不能定义同名变量的	
5.本地变量不会被默认初始化，参数在进入函数的时候被初始化了	

在使用函数/方法的时候，目前为止我们传入的只是“值”而非这个变量	
> 后面学到的内容会有传入的是地址/指针...

```C
#include <stdio.h>
//以下内容请利用debug辅助理解

//这样的代码可以完成a、b数值的互换吗   答案是不可以 
void swap(int a , int b);

int main(void){
	int a = 5 ; 
	int b = 16 ; 
	
	swap(a,b);
	printf("a = %d b = %d",a,b);
	return 0 ;
}

void swap(int a,int b){
	//虽然在这里的参数是a b ，刚才传进来的数值也是a b ，但实质上二者是完全不同的东西
	//swap函数中，只是把a的值5，以及把b的值16 给到了swap的形式参数a b 里面，此ab非彼ab
	 
	int t = a ;
	a = b ; 
	b = t ;
}

其它

1.void f(void) 表示f函数没有参数
void f() 表示f函数的参数表未知（传统C）

2.逗号在圆括号内算作标点符号，而不是运算符
f(a,b) 传入a,b
f((a,b)) 传入(a,b)，此时我们要的是(a,b)而非a,b。因此逗号会被当作运算符被使用

3.C语言不允许在函数里面定义函数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
void swap(); //原型声明

int main(void){
	int a = 5 ; 
	int b = 6 ; 
	
	//原型声明的时候外面没有指定参数，在这里外面尝试传入两个int
	swap(a,b); //而事实上，我们的函数会对两个double进行处理，因此结果会出错（但是运行是正常的）
	printf("a = %d , b = %d \n",a,b);
	
	
	;return 0 ; 
}

//注意这里给的是double
void swap (double a , double b){
	int t = a ; 
	printf("IN SWAP,a = %f , b = %f  \n",a,b);
	a = b ; 
	
	b = t ; 
}
```  

## 基础的搜索算法	
这里稍微介绍一下搜索算法	

### 线性搜索
最简单、最基础、最粗暴的搜索：遍历所有数据，检索目标
```C
    int searcher(int key , int a[] , int len){
    //这里附带说明一下，由于C语言的函数的关系，我们最好还是把数组长度直接传进来
    int ret = -1 ; 
    for (int i =0 ; i <len ; i++){
        if (key == a[i]){
            ret = i ; 
            break ; 
        }
    }
    return ret ; 
}

这个方法会查找数组中的某个数，找到了就会输出它的位置，否则输出-1

二分搜索

不断对半分的搜索方法
用的地方是一个已经排序好的数组 , 它的效率显然高于普通遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int search(int key ,  int a[] , int len){
    int left = 0 ;
    int right = len -1 ;
    //定义好边缘的那两个点
    int ret = -1 ;

    while(right > left){
        int mid = (left+right)/2 ;
        if(a[mid] == k){
            ret = mid ; 
            break ;
            //如果找到了就设置ret为这个值并且返回
        }else if (a[mid]>k){
            right = mid -1 ;
        }else{
            left = mid +1 ;
        }
    }
    return ret ; 
}