C语言学习笔记02
2022-02-05 本文已影响0人
Nefelibatas
数组
声明与初始化 int b[size] //数组容量为size，4*size个字节，size必须是确定值
赋值 int b[2] = {0,1}
素数筛
1.标记一个范围内的数字是否是合数，没有被标记的则为素数
2.算法复杂度为O(N),时间复杂度为O(NloglogN)
3.总体思想是用素数去标记掉不是素数的数字，如i是素数，2i,3*i...就都不是素数
用素数标记合数
int prime[100] = {0}; //特殊方法，将prime数组中所有元素设置为0，初始化
假设当i为合数时标记为1，int prime[i] = 1;
第一版,时间复杂度O(N^2)
#include <stdio.h>
int is_prime(int n){ //判断n是否为素数
for(int i =2;i<n;i++){
if(n%i == 0) return 0; //合数
}
return 1; //素数返回1
}
int main(){
int n;
scanf("%d",&n);
for(int i = 2;i <= n;i++){
if(!is_prime(i)) continue; //i不是素数跳过本次循环
print("%d\n",i);
}
return 0;
}
查看运行时间
#include <stdio.h>
int is_prime(int n){ //判断n是否为素数
for(int i =2;i<n;i++){
if(n%i == 0) return 0; //合数
}
return 1; //素数返回1
}
int main(){
const int n=100;
scanf("%d",&n);
for(int i = 2;i <= n;i++){
if(!is_prime(i)) continue; //i不是素数跳过本次循环
print("%d\n",i);
}
return 0;
}
//time ./a.out >out 检测运行时间,重定向到out文件中
第二版，降低时间复杂度
#include <stdio.h>
#include <math.h>
int is_prime(int n){ //判断n是否为素数
for(int i =2;i<=sqrt(n);i++){ //2到sqrt n中寻找即可
if(n%i == 0) return 0; //合数
}
return 1; //素数返回1
}
int main(){
const int n=100;
scanf("%d",&n);
for(int i = 2;i <= n;i++){
if(!is_prime(i)) continue; //i不是素数跳过本次循环
print("%d\n",i);
}
return 0;
第三版，函数调用降低时间复杂度
#include <stdio.h>
#include <math.h>
int is_prime(int n){ //判断n是否为素数
for(int i =2, I = sqrt(n); i<=I;i++){ //反执行1次
if(n%i == 0) return 0; //合数
}
return 1; //素数返回1
}
int main(){
const int n=100;
scanf("%d",&n);
for(int i = 2;i <= n;i++){
if(!is_prime(i)) continue; //i不是素数跳过本次循环
print("%d\n",i);
}
return 0;
}
第四版
#include <stdio.h>
#include <math.h>
# define MAX_N 10000
int prime[MAX_N+5] = {0};//初始化中的清空，开打有容错可能
void init_prime(){ //判断n是否为素数
for(int i =2; i <= MAX_N;i++){
if(prime[i]) continue; //prime[]==0即为素数
prime[++prime[0]] = i;
for(int j = 2,I = MAX_N/i; j <= I ; j++){
prime[j*i] = 1; //在i为素数的情况下标记其倍数为合数
}
}
return;
}
int main(){
init_prime();
for(int i =1; i<=prime[0];i++){
printf("%d\n",prime[i]);
}
return 0;
}
练习：指定范围内的质数
对于一个大于 1 的整数，如果除了 1 和它本身，它不再被其它正整数整除，
那么我们说它是一个质数。请对于给定的一个大于 1 的正整数 N
（你可以认为测评机给出的 N 均小于等于106 ），
和一个大于 1 的正整数 M（你可以认为测评机给出的 M 均小于等于 106 ），
N 一定大于 M，请按从小到大的顺序输出所有小于等于 N 且大于等于 M 的质数。
#include <stdio.h>
# define MAX_N 1000000
int prime[MAX_N+5] = {0};//初始化中的清空，开打有容错可能
void init_prime(){ //判断n是否为素数
for(int i =2; i <= MAX_N;i++){
if(prime[i]) continue; //prime[]==0即为素数
prime[++prime[0]] = i;
for(int j = 2,I = MAX_N/i; j <= I ; j++){
prime[j*i] = 1; //在i为素数的情况下标记其倍数为合数
}
}
return ;
}
int main(){
init_prime();
int n,m;
scanf("%d%d",&n,&m);
for(int i =1; i <= prime[0] && prime[i] <= n;i++){
if(prime[i]< m) continue;
printf("%d\n",prime[i]);
}
return 0;
}
练习：五位质数回文数
质数：除了 1 和它本身，没有其他因数。
回文数：正着看和反着看完全一样的数，如 12321,59595。
给定两个五位正整数 a,b，找出这两个数之间（含）所有既是质数又是回文数的数。
#include <stdio.h>
#include <math.h>
//回文
int is_server(int n){
int x=n,temp = 0;
while(x){
temp = temp*10+x%10;
x /= 10;
}
return temp == n;
}
int is_prime(int n){
for (int i=2,I=sqrt(n);i<=I;i++){
if(n%i == 0) return 0;
}
return 1;
}
int main(){
int a,b;
scanf("%d%d",&a,&b);
for(int i=a,j=0;i<=b;i++){
if(!is_server(i) || !is_prime(i)) continue;
j++ && printf(" ");
printf("%d",i);
}
printf("\n");
return 0;
}
折半（二分）查找
#include <stdio.h>
int binary_search(int *arr,int n,int x){
int head =0,tail = n-1,mid;
while(head <= tail){
mid = (head + tail)/2;
if(arr[mid] == x) return mid;
if(arr[mid] < x) head = mid+1; //中间值比目标值小，往右边查找
else tail = mid -1;
}
return -1;
}
int main(){
int arr[100],n;
scanf("%d",&n);
for (int i=0; i < n;i++){
scanf("%d",&arr[i]); //读入数据到数组中
}
int x;
while(~scanf("%d",&x)){ //while(~x)
//循环从输入流读取m和n，直到遇到EOF为止，等同于while (scanf("%d",&x)!=EOF)。scanf()函数返回成功赋值的数据项数，出错时则返回，EOF定义为-1。
// ~是按位取反，-1十六进制补码表示为0x ffffffff，f是二进制的1111，取反后就全部变成0了，于是while结束。
//只有返回值为EOF（即-1）时，其取反的的值（即while循环的判断条件）才为0，才能结束循环，其它输入情况下（无论是否输入成功）while循环的判断条件为非0，即为真。
printf("%d\n",binary_search(arr,n,x));
}
return 0;
}
折半（二分）查找,递归版本
#include <stdio.h>
int binary_search(int *arr,int l,int r,int x){
if(l > r) retutn -1;
int mid = (l+r)/2;
if(arr[mid] == x) return mid;
if(arr[mid] < x) l = mid + 1;
else r = mid - 1;
return binary_search(arr,l,r, x);
}
int main(){
int arr[100],n;
scanf("%d",&n);
for (int i=0; i < n;i++){
scanf("%d",&arr[i]); //读入数据到数组中
}
int x;
while(~scanf("%d",&x)){
printf("%d\n",binary_search(arr,0,n-1, x);
}
return 0;
}
数组操作
#include <stdio.h>
int main(){
int arr[400] = {0}; //数组清空操作
//打印地址
printf("%p\n",arr,arr+1); //相邻元素差（偏移）4个字节，与其类型（int）相关,改为char则相差1个字节
printf("&arr[0]=%p\n",&arr[0]);
scanf("%d",&arr[i]);
scanf("%d",arr+i); //等价，取地址
return 0;
}
数据传参
#include <stdio.h>
void func(int *num){ //只要表现形式一致性就可以传参
num[0] = 123;
printf("func : num = %p,num+1=%p\n",num,num+1);
return ;
}
int main(){
int arr[400] = {0}; //arr与num本质不同，arr是数组，num是指针变量
printf("arr=%p, arr+1 = %p\n",arr,arr+1);
func(arr)
return 0;
}
指针变量大小与操作系统有关，32位操作系统占4字节，64位占8字节
高维数组传参1
#include <stdio.h>
void func(int num[400][20]){ //也可省略成int num[][20]
num[0][0] = 123;
printf("func : num = %p,num+1=%p\n",num,num+1);
return ;
}
int main(){
int arr[400][20] = {0};
printf("arr=%p, arr+1 = %p\n",arr,arr+1);
func(arr)
return 0;
}
高维数组传参2
#include <stdio.h>
void func(int (*num)[20]){ //也可省略成int num[][20]
num[0][0] = 123;
printf("func : num = %p,num+1=%p\n",num,num+1);
return ;
}
int main(){
int arr[400][20] = {0};
printf("arr=%p, arr+1 = %p\n",arr,arr+1);
func(arr)
return 0;
}
预处理命令-宏定义
//定义符号常量
#define PI 3.14
//定义傻瓜表达式,只进行符号替换不进行结果计算
#define MAX(a,b) (a)>(b)?(a):(b)
//定义代码段
#define P(a){ \
printf("%d",a);\
//需要连接符\..\作为仅定义一行宏定义
}
预处理命令过程
1.C源码
预处理阶段，进行所有宏定义与预处理命令进行符号替换
2.编译源码：语法分析、词法分析等，处于编译期
3.对象文件：生成中间文件.obj
4.链接：生成可执行程序.out文件
字符串
定义字符数组：char str[size];
初始化字符数组：
char str[] = "he o"; //整个字符串复制给数组str[],遇到'\0'（类似flag标记）停止。
//ASCALL码映射下，任何字符都会转化为数字，'\0' = 0
char str[size] = {'h','e','o'};
练习
#include <stdio.h>
int main(){
char str[] = "hello world"; //str字符大小多算一个'\0'，大小为12
char str2[22] = {'h','e','l','l','o','w',' ','w','o','r','l','d'};//str2大小为11，空格不算
//char str2[] = {'h','e','l','l','o','w',' ','w','o','r','l','d','\0'};
printf("str=%lu,str2=%lu\n",sizeof(str),sizeof(str2));
printf("strlen(str2)=%ld\n",strlen(str2));
return 0;
}
字符串相关操作,头文件string.h
//内置函数，见文档手册
strlen(str); // 计算字符串长度，以\0作为结束符
strcmp(str1,str2); // 字符串比较（数值与字符）
strcpy(dest,src);// 字符串拷贝
strcmp(str1,str2,n);// 安全的字符串比较
strcpy(str1,src2,n);// 安全的字符串拷贝
memcpy(str1,src2,n);// 内存拷贝
memcMP(str1,src2,n);// 内存比较
memcpy(str1,c,n);// 内存设置
memset(arr,0,sizeof(arr));//清空全为0
memset(arr,1,sizeof(arr)); //int类型为4个字节，所以不会是全为1
memset(arr,-1,sizeof(arr)); //全为-1，因为-1的二进制为全1
复杂结构与指针
1.结构体，本质就是类型
struct person{ //person为结构体名
//基础字段
char name[20];//每个类型字节不同 1字节
int age; //4字节
char gender; //1字节
float height; //4字节
}; //注意有;可直接加入变量名
//内部字段的访问
//1.直接引用
struct person Yu;
Yu.age;
//2.间接引用,有地址即间接
struct person *p = &Yu;
p->age;
struct类型大小,sizeof()不是函数但表现的像一个函数，宏定义
基础字段大小累加+复杂结构对其方式申请的内存（以基础字段中最大类型n字节对齐）
//注：char类型大小为1个字节，申请的空间为4字节（最大），剩余3个字节空间，但是int age需要4个字节空间，所以跳过继续申请一个4字节空间,同理，最终需要4+4+4+4=16字节。
代码练习
struct node1{ //8字节
char a;
char b;
int c;
}
struct node1{ //12字节
char a;
int c;
char b;
}
//相同类型的存储最好是写在一块省空间
int main(){
printf("sizeof(node1)=%lu\n",sizeof(struct node1));
printf("sizeof(node2)=%lu\n",sizeof(struct node2));
return 0;
}
练习2
struct person{
char name[20]; //数组中20，开3块内存，3*8
int age;
char gender;
double height;
};
// 另一种定义
#include <stdio.h>
#include <string.h>
struct person{
char name[20]; //数组中20，开3块内存，3*8
int age;
char gender;
double height;
}Yu; //也可以定义为结构体数组Yu[20]
int main(){
//struct person Yu;
struct person *p = &Yu;
strcpy(Yu.name,"xxxx");
scanf("%s",p->name); // 间接引用
scanf("%s\n",Yu.name); // 直接引用,Yu.name本身就是name[20]的首地址
printf("%s\n",Yu.name);
printf("sizeof(person)=%lu\n",sizeof(struct person)); //40个字节
printf("my name is %s\n",Yu.name);
return 0;
}
//共用体（共同利用），本质也是类型
union register{ //union+名字 表示类型
struct{ //匿名结构体，仅能使用一次 struct+名字 表示类型
unsigned char byte1;
unsigned char byte2;
unsigned char byte3;
}bytes; //bytes结构体类型变量
unsigned int number; //无符号的 unsigned，number值域[0,2^32-1]
};
