C语言算法(二分查找、文件读写)

2024-01-08 19:29:31

二分查找

前提条件:数据有序,随机访问

#include <stdio.h>

int binary_search(int arr[],int n,int key);

int main(void) {}

int search(int arr[],int left,int right,int key) {
	//边界条件
	if(left > right) return -1;
	//int mid = (left + right) / 2;
	//防止溢出
	int mid = left + ((right - left) >> 1);
	if(key < arr[mid]) {
		return search(arr,left,mid - 1,key);
	}else fi(key > arr[mid]) {
		return search(arr,mid + 1,right,key);
	}else {
		return mid;
	}
}
//递归
int binary_search(int arr[],int n,int key) {
	return search(arr,0,n-1,key);
}
//循环
int binary_search(int arr[]],int n,int key) {
	if(n == 0) return -1;
	int left = 0,right = n-1;
	while(left <= right) {
		int mid = left + ((right - left) >> 1);
		if(key < arr[mid]) {
			right = mid - 1;
		}else if(key > arr[mid]) {
			left = mid + 1 ;
		}else {
			return mid;
		}
	}
	return -1;
}

二分查找的局限性
(1)二分查找依赖顺序表的结构,需要你有序性
(2)二分查找针对的是有序数据
(3)数据量太小没必要进行二分查找;
a)二分查可以减少比较操作;
b)比较操作很耗时
(4)数据量太大也不适合二分查找
(5)动态数据也不适合二分查找
(6)动态数据查找:平衡二叉树,哈希表

二分查找变种
(1)查找第一个与key值相同的元素
(2)查找最后一个与key值相同的元素
(3)查找最后一个小于等于key值的元素
(4)查找第一个大于等于key值的元素

//查找第一个与key值相同的元素
int binary_search1(int arr[],int n,int key) {
	int left = 0,right = n - 1;
	while(left <= right) {
		int mid = left + ((right-left) >> 1);
		if(key < arr[mid]) {
			right = mid - 1;
		}else if(key > arr[mid]) {
			left = mid + 1;
		}else {
			if(mid == left || arr[mid - 1] < key) {
				return mid;
			}
			right = mid - 1;
		}
	}
	return -1;
}
//查找最后一个与key值先沟通呢房的人元素
//查找最后一个小于等于key值的元素
int binary_search2(int arr[],int n,int key) {
	int left = 0,right = n - 1;
	while(left <= right) {
		int mid = left + ((right-left) >> 1);
		if(arr[mid] > key) {
			right = mid - 1;
		}else {
			if(mid == right || arr[mid + 1] > key) {
				return mid;
			}
			left  = mid +1;
		}
	}
	return -1;
}

文件

流:表示任意输入的源或输出的目的地
在这里插入图片描述

文件缓冲
缓冲区的分类:
满缓冲区:当缓冲区空的时候才会向缓冲区中写入数据,当缓冲区满的时候才会从缓冲区中读取数据
行缓冲区:每次从输入流中读取一行数据,每次也只会从缓冲区中被输出流读取一行数据
无缓冲区:不会进行缓冲,数据直接写到我们的目标文件内之中
在这里插入图片描述

刷新缓冲区
ffluh:刷新输出流中的数据到实际中的文件中去

标准流
在c语言中流对应的数据类型是—>FILE结构体
使用FILE*表示一个流
其中回从出流的起始位置,目前流读取到的位置

这三个标准流可以直接使用,使用完毕之后也不需要关闭
stdin:标准输入流,一般将其和键盘关联起来
stdout:标准输出流,一般将其和显示器关联起来
stderr:标准错误流,一般将其哦和显示器关联起来

文本文件和二进制文件
打开之后可以看得懂的就是文本文件,存储的是字符数据
打开之后看不懂的就是二进制文件,存储的是二进制形式数据

文本文件有两个特殊的性质:
(1)文本文件有行的概念,二进制文件没有行的概念【Linux中换行\n,windows中换行\r/\n
(2)文本文件可能包含一个特殊的文件末尾:EOF 【windows中表示文件末尾\x1a(使用快捷键ctrl + z可以向输入流中输入一个结尾字符)】

文本文件存储数据:优点:方便人类阅读和编辑;缺点:占用空间大
二进制文件存储数据:缺点:人类看不懂,不方便编辑;优点:占用空间小

打开文件和关闭文件
fopen打开文件
在这里插入图片描述

filename:文件路径
mode:打开文件的方式
文件路径分为绝对路径(从根目录,盘符开始,一致到文件所在的位置)和相对路径(从当前工作目录开始,一致到文件所在的位置)
打开方式:
r(rt)—>read只读,要求文件事先存在;
w(wt)—>write只写模式,不要求文件存在,如果文件存在,写之前会清空原文件内容;
a(at)—>append追加不要求文件存在,如果文件存在,不会清空源文件的内容
r+(rb+)—>可读可写,要求文件存在,如果写数据会清空数据
w+(wb+)—>可读可写,不要求文件存在
a+(ab+)—>可读可写,不要求文件存在,不会清空原有数据
以上方法用于读写文本文件,读写二进制文件为rb,wb,ab,rb+,wb+,ab+

fclose:关闭文件
在这里插入图片描述
如果成功关闭返回0;否则返回EOF

文件的读写
文本文件的读写
fgetc:一次读一个字符, 可以从任意输入流中读数据
fputc:一次写一个字符,可以将数据写到任意的输出流中
fgets:一次读取一行,读到换行符为止,可以从任意的流中读取字符串
fputs:把一个字符串写入到一个输出流中
fscanf:用格式化的方式将数据从标准输入流stdin中读入
fprintf:用格式化的方式将数据写到stdout标准输出流中

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
从stream流中读取最多count个数据到str中,遇到换行符就停止读入,会将存储数据的st指针返回回来,如果失败会返回空指针

在这里插入图片描述
将str字符串写出到输出流stream中

#define _CRT_SECURE_NO_WARINGS
#include <stdio.h>
#include <stdlib.h>
#define N 100
int main(int argc,char *argv[]) {
	if(argc != 3) {
		fprintf(stderr,"Invalid arguments.\n");//向stderr错误输出流中输入错误信息
		exit(1);
	}
	FILE* src = fopen(argv[1],"r");//打开文件
	if(src == NULL) {
		printf("Error:open %s failed.\n",argv[1]);
		exit(1);
	}
	FILE* dest = fopen(argv[2],"w");
	if(dest == NULL) {
		printf("Error:open %s failed.\n",argv[2]);
		fclose(src);
		exit(1);
	}
	//读写数据
	//每次读取字符
	//int ch;
	//while((ch = fgetc(src) != EOF)) {
	//	fputc(ch,dest);//将字符写入dest流中
	//}
	//读写一行数据
	char buf[N];
	while(fgets(buf,N,src) != NULL) {
		fputs(buf,dest);
	}
	//关闭流
	fclose(src);
	fclose(dest);
	
	return 0;
}
#include <stdio.h>

typedef struct student_s{
	int number;
	char name[25];
	int chinese;
	int math;
	int english;
}Student;

int main(void) {
	//序列化:把内存中的对象持久化(格式:文本格式)xml,json存在磁盘中
	Student s = {1,"xixi",100,100,100};
	
	FILE* fp = fopen("student.dat","w");
	if(fp == NULL) {
		fprintf(stderr,"Error:open student.dat failed.\n");
		exit(1);
	}
	fprintf(fp,"%d %s %d %d %d\n",s.number,s.name,s.chinese,s.math,s.english);
	fclose(fp);
	//反序列化:把持久化的数据加载到内存,斌生产对应的对象
	FILE* fp = fopen("student.dat","r");
	if(fp == NULL) {
		fprintf(stderr,"Error:open student.dat failed.\n");
		exit(1);
	}
	Student s;
	fscanf(fp,"%d%s%d%d%D",&s.number,&s.name,&s.chinese,&s.math,&s.english);
	fclose(fp);
	return 0;	
}

二进制文件的读写

在这里插入图片描述

buffer:把文件中的数据读到buffer中
size:每个元素的大小
count:表示又多少个元素
stream:需要从那个数据流中读取数据
返回值是成功读入数据的个数

在这里插入图片描述

buffer:内存中的对象,我们要将内存buffer中的数据写入到文件中
size:每个对象的大小
count:要写的对象的数量
stream:要写到的目标输出流
返回值是成功写出对象的个数, 一般情况下返回值和count值是相同的

#define _CRT_SECURE_NO_WARINGS
#include <stdio.h>
#include <stdlib.h>
#define N 4096
int main(int argc,char *argv[]) {
	if(argc != 3) {
		fprintf(stderr,"Invalid arguments.\n");//向stderr错误输出流中输入错误信息
		exit(1);
	}
	FILE* src = fopen(argv[1],"rb");//打开文件
	if(src == NULL) {
		printf("Error:open %s failed.\n",argv[1]);
		exit(1);
	}
	FILE* dest = fopen(argv[2],"wb");
	if(dest == NULL) {
		printf("Error:open %s failed.\n",argv[2]);
		fclose(src);
		exit(1);
	}
	//读写数据
	char buf[4096]; 
	int n;//读入数据的个数
	while((n = fread(buf, 1, N, src)) != 0) {//从src中的数据读入到buf中
	fwrite(buf, 1, n, dest);//将src中的数据写入到dest中去
		
	}
	//关闭流
	fclose(src);
	fclose(dest);
	
	return 0;
}
//二进制形式序列化
#include <stdio.h>

typedef struct student_s{
	int number;
	char name[25];
	int chinese;
	int math;
	int english;
}Student;

int main(void) {
	//序列化:把内存中的对象持久化(格式:文本格式)xml,json存在磁盘中
	Student s = {1,"xixi",100,100,100};
	
	FILE* fp = fopen("student.dat","wb");
	if(fp == NULL) {
		fprintf(stderr,"Error:open student.dat failed.\n");
		exit(1);
	}
	fwrite(&s,sizeof(s),1,fp);
	fclose(fp);
	
	//反序列化:把持久化的数据加载到内存,斌生产对应的对象
	FILE* fp = fopen("student.dat","rb");
	if(fp == NULL) {
		fprintf(stderr,"Error:open student.dat failed.\n");
		exit(1);
	}
	Student s;
	fread(&s,sizeof(s),1,fp);
	fclose(fp);
	return 0;	
}

文件定位

查找文件中对应的位置,可以改变读写指针位置
int fseek(FILE* stream,long int offset,int whence)
offset:以字节为单位计算偏移量
whence:参照点【whence取值:(1)SEEK_SET:文件的起始位置;(2)SEEK_CUR:文件的当前位置;(3)SEEK_END:文件的末尾位置】
移动到文件的开始:fseek(stream,0L,SEEK_SET);<==>rewind(stream);
往回移动10个字节:fseek(stream,-10L,SEEK_CUR);
移动到文件的末尾:fseek(stream,0L,SEEK_END);
打印当前文件的位置(相对于SEEK_SET而言)
long ftell(FILE* stream)
可以将处于任意读写位置的指针指向开始位置
void rewind(FILE* stream)

#include <stdio.h>

typedef struct student_s{
	int number;
	char name[25];
	int chinese;
	int math;
	int english;
}Student;

int main(void) {
	//序列化:把内存中的对象持久化(格式:文本格式)xml,json存在磁盘中
	Student s = {1,"xixi",100,100,100};
	
	FILE* fp = fopen("student.dat","wb+");
	if(fp == NULL) {
		fprintf(stderr,"Error:open student.dat failed.\n");
		exit(1);
	}
	fwrite(&s,sizeof(s),1,fp);
	
	//反序列化:把持久化的数据加载到内存,斌生产对应的对象
	Student s1;
	rewind(fp);//重定向文件位置 <==>fseek(fp,0L,SEEK_SET)
	fread(&s1,sizeof(s1),1,fp);
	fclose(fp);
	return 0;	
}

错误处理
在这里插入图片描述
如果数值计算、文件读写发生错误,系统调用(sysytem call)会把errno设置为对应的值

#include <stdio.h>
#include <errno.h>
#inlcude <math.h>

int main(void) {
	printf("%d\n",errno);//0
	printf("%s\n",strerror(errno));//No error
	perror("Error");// Error:No error
	log(0,0);
	printf("%d\n",errno);//34
	printf("%s\n",strerror(errno));// Result too large
	perror("Error");//Error: Result too large
	//虽然errnno可以告诉我们发生错误的系统的调用返回的值,但是我们很难去确定齐放回的数值表示什么含义我们可以使用strerror(errno)打印其字符串表达
	
	return 0;
}

文章来源:https://blog.csdn.net/qq_48627750/article/details/135361595
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。