数组运算
最基础的搜索程序：在给定的数据中，如何找出某个数据是否存在？
#include <stdio.h>
/**
找出key在数组a中的位置
@param key 要寻找的数字
@param a 要寻找的数组
@param length 数组a的长度
@return 如果找到，返回其在a中的位置;如果找不到则返回-1
*/
int search( int key, int a[], int length );
int main(void)
{
int a[] = {2,4,6,7,1,3,5,9,11,13,23,14,32};
int x;
int loc;
printf("请输入一个数字：");
scanf("%d", &x);
loc=search(x, a, sizeof(a)/sizeof(a[0]));
if ( loc !=-1){
printf("%d在第%d个位置上\n", x, loc);
} else {
printf("%d不存在\n", x);
}
return 0;
}
int search(int key, int a[], int length)
{
int ret = -1;
int i;
for ( i=0; i< length; i++) {
if(a[i] == key ) {
ret = i;
break;
}
}
return ret;
}
数组的集成初始化
int a[] = {2,4,6,7,1,3,5,9,11,13,23,14,32};
直接用大括号给出数组的所有元素的初始值
不需要给出数组的大小，编译器会自动数
集成初始化时的定位
int a[10] = {
[0] = 2, [2] = 3, 6,
};
>> a0=2, a2=3, a3=6, 其余都为0
用[n]在初始化数据中给出定位
没有定位的数据接在前面的位置后面
其他位置的值补零
也可以不给出数组大小，让编译器算
特别适合初始数据稀疏的数组
数组的大小
回忆：sizeof能给出整个数组所占据的内容的大小，单位是字节
sizeof(a[0])给出数组中单个元素的大小，于是相除就得到了数组的单元个数，这样的代码，一旦修改数组中初始的数据，不需要修改遍历的代码
数组的赋值
int a[] = {2,4,6,7,1,3,5,9,11,13,23,14,32};
int b[] = a;
错误❌
数组变量本身不能被赋值，要把一个数组的所有元素交给另一个数组，必须采用遍历
正确写法✔：（唯一方法）
for ( i=0; i<length; i++ ) {
b[i] = a[i];
}
遍历数组
- 通常都是使用for循环，让循环变量i从0到<数组的长度，这样循环体内最大的i正好是数组最大的有效下标
常见错误：
①循环结束条件是<=数组长度
②离开循环后，继续用i的值来做数组元素的下标
- 数组作为函数参数时，往往必须再用另一个参数来传入数组的大小。因为不能在[]中给出数组的大小，也不能再利用sizeof来计算数组的元素个数
数组例子
回顾：判断素数
int isPrime(int x);
int main(void)
{
int x;
scanf("%d", &x);
if ( isPrime(x) ) {
printf("%d是素数\n", x);
} else {
printf("%d不是素数\n", x);
}
return 0;
}
最开始的代码：
从2到i-1测试是否可以整除：当n很大时，就会重复很多遍
去掉偶数后从3到i-1，每次加2
int isPrime(int i)
{
int ret = 1;
int k;
if ( i==1 ||
(i%2 == 0 && i!=2 ) )
ret = 0;
for ( k=3; k<i; k+=2) {
if (i%k == 0 ) {
ret = 0;
break;
}
}
return ret;
}
会循环n/2遍
无需到x-1，到sqrt(x)就够了
int isPrime(int i)
{
int ret = 1;
int k;
if ( i==1 ||
(i%2 == 0 && i!=2 ) )
ret = 0;
for ( k=3; k<sqrt(i); k+=2) {
if (i%k == 0 ) {
ret = 0;
break;
}
}
return ret;
}
只需要循环sqrt(x)遍
判断是否能被已知的且<x的素数整除
#include <stdio.h>
int main(void)
{
const int number=100;
int prime [number]={2};
int count=1;
int i=3;
while (count< number ){
if(isPrime(i, prime, count)){
prime [count++]=i;
}
i++;
}
for (i=0; i<number; i++){
printf("%d", prime [i]);
if((i+1)%5) printf("\t");
else printf("\n");
}
return 0;
}
int isPrime(int x, int knownPrimes[], int numberOfKnownPrimes)
{
int ret = 1;
int i;
for (i=0;i<numberOfKnownPrimes; i++){
if(x % knownPrimes[i]==O){
ret =0;
break;
}
}
return ret;
}构造素数表（n以内）
①令x为2
②将2x、3x直到ax<n的数标记为非素数
③令x为下一个没有标记为非素数的数，重复②，直到所有数都尝试完毕
1.开辟prime[n],初始化其所有元素为1，prime[x]为1，表示x是素数
2.令x=2
3.如果x是素数，则对于(i=2;x*i<n;i++)令prime[i*x]=0
4.令x++,如果x<n,重复3，否则结束
二维数组
二维数组
eg. int a[3][5];
通常理解为a是一个3行5列的矩阵：
| a[0][0] | a[0][1] | a[0][2] | a[0][3] | a[0][4] |
| a[1][0] | a[1][1] | a[1][2] | a[1][3] | a[1][4] |
| a[2][0] | a[2][1] | a[2][2] | a[2][3] | a[2][4] |
二维数组的遍历
for ( iii<3; i++ ) {
for ( j=0; j<5; j++ ) {
a[i][j] = i*j;
}
}
a[i][j]是一个int，表示第i行第j列上的单元
（外层遍历行，内层遍历列）
a[i,j]表示：a[j]
二维数组的初始化
列数是必须给出的，行数是可以由编译器自动来数
每行一个{}，逗号分隔
最后的逗号可以存在，如果省略，表示补零
tic-tac-toe游戏
读入一个3×3的矩阵，矩阵中的数字为1表示该位置上有一个X，为0表示为O
程序判断这个矩阵中是否有获胜的一方，输出表示获胜一方的字符X或O，或输出无人获胜
读入矩阵
count int size=3;
int board[size][size];
int i,j;
int num0fX;
int num0fO;
int result = -1; // -1：没人赢，1：X赢，0：O赢
// 读入矩阵
for ( i=0; i<size, i++ ) {
for ( j=0; j<size; j++ ) {
scanf("%d", &board[i][j] );
}
}
检查行
// 检查行
for (i=0; i<size && result ==1;i++) {
num0fO= num0fX=0;for(j=0; j<size; j++) {
if ( board[i][j]==1) {
num0fX ++;}else {
num0fO ++;}
}
if (num0fO = size ){
result=0;
} else if (num0fX== size ){
result=1;
}
}
检查列
if ( result==1){
for (j=0; j<size && result==-1; j++){
num0O = num0fX=0;for (i=0;i<size; i++){
if ( board[i][j]==1) {
num0fX ++;} else {
num0fO ++;
}
}
if(num0fO== size ){
result=0;
} else if (numofX- size ){
result=1;
}}
}
检查对角线
num0fO= num0fX=0;
for(i=0; i<size; i++){
if( board[il[i]==1) {
num0fX ++;
} else {
num0fO ++;}
}
if( num0fO==size ){
result=0;
}else if (numofX== size ){
result=1;num0fO= num0fx=0;
for(i=0;i<size; i++){
if( board[i][size-i-1]==1){
num0fX ++;
} else {
num0fO ++;}
}