7.1 数组运算
7.1.1 数组运算
数组的集成初始化
int a[]={
2,4,6,7,1,3,5,9,11,13,23,14,32};
- 直接用大括号给出数组的所有元素的初始值；
- 不需要给出数组的大小，编译器自动数数
集成初始化时的定位
int a[10]={
[0]=2,[2]=3,6,
}
- 用[n]在初始化数据中给出定位；
- 没有定位的数据接在前面的未知后面；
- 其他位置地值补零；
- 也可以不给出数组大小，让编译器算；
- 特别适合初始数据稀疏的数组。
数组的大小
- sizeof给出整个数组所占据的内容的大小，单位是字节
sizeof(a)/sizeof(a[0]);
- sizeof(a[0])给出数组中单个元素的大小，于是相除就得到了数组的单元个数；
- 这样的代码一旦修改数组的初始的数据，不需要修改遍历的代码；
数组的赋值
- 数组本身不能被赋值；
- 要把一个数组的所有元素交给另一个数组，必须采用遍历。
for(i=0;i<length;i++){
b[i]=a[i];
}
遍历数组
- 通常使用for循环，让循环变量i从0到<数组的长度，这样循环体内的最大的i正好是数组最大的有效下标；
- 常见错误是循环结束条件为i<=数组长度，或离开循环后继续用i的值做数组元素的下标。
数组作为函数的参数时往往必须再用另一个参数来传入数组的大小。因为数组在作为函数的参数时，不能在[]中给出数组的大小，不能再利用sizeof来计算数组的元素个数。
7.1.2 数组例子：素数
判断一个数是不是素数，main函数代码如下
int main(void)
{
int x;
scanf("%d", &x);
if(isPrime(x)){
printf("%d是素数", x);
}else{
printf("%d不是素数", x);
}
return 0;
}
isPrime函数代码如下
//从2到x-1测试是否可以被整除
int isPrime(int x)
{
int ret=1;
int i;
if(x==1)
ret=0;
for(i=2;i<x;i++){
if(x%i==0){
ret=0;
break;
}
}
return ret;
}
//
- 对于n要循环n-1遍；
- 当n很大时就是n遍。
//去掉偶数后，从3到x-1，每次加2
int isPrime(int x)
{
int ret=1;
int i;
if(x==1||
(x%2==0&&x!=2))
ret=0;
for(i=3;i<x;i++){
if(x%i==0){
ret=0;
break;
}
}
return ret;
}
//
- 如果x是偶数，立刻是非素数；
- 否则要循环(x-3)/2+1遍；
- 当n很大时就是n/2遍。
//无须到x-1，到sqrt就可以了
int isPrime(int x)
{
int ret=1;
int i;
if(x==1||
(x%2==0&&x!=2))
ret=0;
for(i=3;i<sqrt(x);i++){
if(x%i==0){
ret=0;
break;
}
}
return ret;
}
//需要在前面加上#include <math.h>
//判断能否被已知的且<x的素数整除
#include <stdio.h>
int isPrime(int x,int knownPrimes[],int numberOfknownPrimes)
{
int ret=1;
int i;
for(i=0;i<numberOfknownPrimes;i++){
if(i%numberOfknownPrimes==0){
ret=0;
break;
}
}
return ret;
}
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");
esle printf("\n");
}
return 0;
}
还有一种思路，构造素数表。
构造n以内（不含）的素数表
- 令x=2；
- 将2x、3x、4x直至ax<n的数标记为非素数；
- 令x为下一个没有被标记为非素数的数，重复2；直到所有的数都已经尝试完毕。
伪代码如下
- 开辟prime[n]，初始化其所有元素为1，prime[x]为1表示为素数；
- 令x=2;
- 如果x是素数，则对于(i=2;xi<n;i++)令prime[ix]=0；
- 令x++，如果x<n,重复3，否则结束。
代码如下
#include <stdio.h>
#include <math.h>
int isPrime(int x)
{
int ret=1;
int i;
if(x==1||
(x%2==0&&x!=2))
ret=0;
for(i=3;i<sqrt(x);i++){
if(x%i==0){
ret=0;
break;
}
}
return ret;
}
int main()
{
const int maxNumber=100;
int isPrime[maxNumber];
int i;
int x;
for(i=0;i<maxNumber;i++){
isPrime[i]=1;
}
for(x=2;x<maxNumber;x++){
if(isPrime[x]){
for(i=2;i*x<maxNumber;i++){
isPrime[i*x]=0;
}
}
}
for(i=2;i<maxNumber;i++){
if(isPrime[i]){
printf("%d\t",i);
}
}
printf("\n");
return 0;
}
算法不一定和人的思考方式相同。
7.2 搜索
7.2.1 线性搜索
搜索
- 在一个数组中找到某个数的位置（或确认是否存在）；
- 基本方法：遍历
代码如下
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+1;
break;
}
}
return ret;
}
int main()
{
int a[]={
9,5,1,7,8,6,2,3,4};
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;
}
输入
请输入一个数字：5
5在第2个位置上
要注意单一出口的原则
一专多能是不好的代码
7.2.2 搜索的例子
输入1，程序输出penny;
输入5，程序输出nickel;
输入10，程序输出dime;
输入25，程序输出quarter;
输入50，程序输出half-dollar;
可以将1、5、10、25、50和penny、nickel、dime、quarter、half-dollar各做一个数组然后一一对应。
代码如下
#include <stdio.h>
int amount[]={
1,5,10,25,50};
char *name[]={
"penny","nickel","dime","quarter","half-dollar"};
int search(int key,int a[],int len)
{
int i,ret=-1;
for(i=0;i<len;i++)
{
if(key==a[i]){
ret=i;
break;
}
}
return ret;
}
int main()
{
int k;
scanf("%d", &k);
int r=search(k,amount,sizeof(amount)/sizeof(amount[0]));
if(r>-1){
printf("%s\n", name[r]);
}
return 0;
}
输出
5
nickel
但是这种结构是割裂的。还有一种方法。
代码如下
#include <stdio.h>
int amount[]={
1,5,10,25,50};
char *name[]={
"penny","nickel","dime","quarter","half-dollar"};
struct{
int amount;
char *name;
}coins[]={
{
1,"penny"},
{
5,"nickel"},
{
10,"dime"},
{
25,"quarter"},
{
50,"half-dollar"}
};
int search(int key,int a[],int len)
{
int i,ret=-1;
for(i=0;i<len;i++)
{
if(key==a[i]){
ret=i;
break;
}
}
return ret;
}
int main()
{
int k;
int i;
scanf("%d", &k);
//int r=search(k,amount,sizeof(amount)/sizeof(amount[0]));
for(i=0;i<sizeof(coins)/sizeof(coins[0]);i++)
{
if(k==coins[i].amount){
printf("%s\n",coins[i].name);
break;
}
}
// if(r>-1){
// printf("%s\n", name[r]);
// }
return 0;
}
输出
10
dime
这种做法对cache更为友好。
7.2.3 二分搜索
代码如下
int search(int key,int a[],int len)
{
int ret=-1;
int left=0;
int right=len-1;
while(right>left)
{
mid=(right+left)/2;
if(a[mid]==k){
ret=mid;
break;
}else if(a[mid]<k){
left=mid+1;
}else{
right=mid-1;
}
}
return ret;
}
二分搜索最大的好处是效率。对于一个总数为n的数组来说，搜索的最大次数为log2n。
二分法的前提是数组已经按照大小依次排好序
7.3 排序初步
7.3.1 选择排序
如何将无序的数组排列成有序呢？
代码如下
#include <stdio.h>
int max(int a[],int len)
{
int maxid=0;
int i;
for(i=0;i<len;i++)
{
if(a[i]>a[maxid]){
maxid=i;
}
}
return maxid;
}
int main()
{
int a[]={
2,9,32,4,23,5,25,242,3414,1,3,123};
int len=sizeof(a)/sizeof(a[0]);
int i;
//选择排序
for(i=len-1;i>0;i--)
{
int maxid=max(a,i+1);
//swap a[maxid],a[len-1]
int t=a[maxid];
a[maxid]=a[i];
a[i]=t;
}
for(i=0;i<len;i++)
{
printf("%d ",a[i]);
}
return 0;
}
输出
1 2 3 4 5 9 23 25 32 123 242 3414
![[网鼎杯 2020 朱雀组]phpweb](https://img-blog.csdnimg.cn/img_convert/a404a4237fdec0feb92af881eaa8d0fa.png)
