C語言數組運算

數組運算例子

判斷素數

構造素數表

欲構造n以内的素數表

1.令x為2

2.将2x，3x，4x直至ax<n的數标記為非素數

3.令x為下一個沒有被标記為非素數的數，重複2；

   直到所有的數都已經嘗試完畢

構造素數表

欲構造n以内(不含n)的素數表

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，否則結束

#include <stdio.h>
int main(){			//從小到大構造一個素數表 
	int maxNumber;
	scanf("%d",&maxNumber);		//求maxNumber以内的素數 
	int isPrime[maxNumber];
	int i;
	int x;
	for (i=0;i<maxNumber;i++){		//先令isPrime裡面的資料全為1 
		isPrime[i]=1;
	}
	for (x=2;x<maxNumber;x++){		//從2開始逐1來建構isPrime 
		if (isPrime[x]){			//如果是素數的 繼續。。。 
			for (i=2;i*x<maxNumber;i++){		//将對i倍數的x都标記為0 即都标記為非素數 
				isPrime[i*x]=0;
			}
		}
	}
	for (i=2; i<maxNumber;i++){		//最後再周遊isPrime是1的資料 
		if(isPrime[i]){
			printf("%d\t",i);
		}
	}
	printf("\n");
}
/* 
算法不一定和人的思考方式相同 
*/            

####################

搜尋

在一個數組中找到某一個數的位置(或确認是否存在)

基本方法: 周遊

#include <stdio.h>
int search(int key,int a[],int len);
int main(){
	int a[]={3,25,45,78,65,21,47,52,12,};
	int r=search(12,a,sizeof(a)/sizeof(a[0]));
	printf("%d\n",r);
	return 0;		
} 
int search(int key,int a[],int len){
	int ret =-1;						//當沒找到 就還是-1 
	for (int i=0;i<len;i++){
		if (key==a[i]){
			ret =i;
			break;
		}
	}
	return ret;
}
           

' 資料結構——散清單 hash table

二分法！！！——需要資料有序

*對大量資料進行搜尋的時候，二分法效率高

搜尋次數

#include <stdio.h>			//選擇排序 
 int max(int a[],int len){		//找最大值的位置 
 	int maxid=0;
 	for(int i=1;i<len;i++){
 		if(a[i]>a[maxid]){
 			maxid=i;
		 }
	 }
	 return maxid;
 } 
 int main(){
 	int a[]={2,45,4,90,14,365,54,65,11,};
 	int len=sizeof(a)/sizeof(a[0]);
 	for (int i=len-1;i>0;i--){
	 	int maxid=max(a,i+1);
		int t=a[maxid];
		a[maxid]=a[i];
		a[i]=t;
	}
	for( int i=0;i<len;i++){
		printf("%d\t",a[i]);
	}
}