嵌入式入门Day25

数据结构Day 6,IO Day1

查找算法
- 顺序查找
- 折半查找（二分查找）
- 哈希查找
IO
- 概念
- 标准IO
- - 创建递归索引（用于查询结构体定义）
- 文件IO
- 标准IO缓冲区指针
- 相关函数

在这里插入图片描述

查找算法

顺序查找

关键字：分为主关键字和次关键字
主关键字：可以唯一识别的信息，如身份证、学号等等
次关键字：可以识别到若干个信息，如姓名，年龄等可以重复的信息
顺序查找概念：按照顺序逐一比较，查找某个关键字是否存在线性表中
顺序查找的时间复杂度O(n)

折半查找（二分查找）

前提：需要顺序存储，记录有序
折半查找：取顺序表的中值比较，每次排除一半的数据
折半查找的时间复杂度尾O（log2n）

#include <stdio.h>

#define MAX 100
typedef struct
{
	char name[20];
	char sex[8];
	int age;
}Stu;
typedef struct
{
	Stu data[MAX];
	int len;
}Seqlist, *Seqlist_ptr;

int main(int argc, const char *argv[])
{
	int age;			//记录用户输入的年龄数据
	int i;				//低位下标
	int j; 				//高位下标
	int mid;			//中间下标
	int flag = 0; 		//查找标志位
	//直接定义并初始化一个顺序表
	Seqlist S = {5,{{"小胖","男",30},{"细狗","男",28},{"黑狗","女",25},{"添狗","男",21},{"狼狗","女",19}}};
	printf("请输入要查找的年龄:");
	scanf("%d",&age);
	//初始化下标
	i = 0;
	j = S.len-1;
	//下标相遇结束循环
	while(i <= j)
	{
		//计算中点下标
		mid = (i+j)/2;
		//输入数据与中点比较，如果小于中点数据，就去低位区寻找，反之去高位区寻找，如果相等查找结束
		if(age < S.data[mid] && i <= j)
		{
			j = mid - 1;
		}else if(age > S.data[mid] && i <= i)
		{
			i = mid + 1;
		}else
		{
			printf("查找成功，该学生是:%s\n", S.data[mid].name);
			flag = 1; 		//查找成功标志置1
			break;
		}
	}
	if(flag == 0)
	{
		printf("查找失败\n");
	}
	return 0;
}

哈希查找

哈希表概念：利用哈希函数关键字代入哈希函数，算出下标，把关键字存入下标对应的数组中。
哈希表的构建：哈希函数，数组，解决冲突方法。
哈希函数构建方法：直接定址法，数字分析法，平方取中，除留余数
- 直接定址法：采用某个线性函数产生的地址作为下标。eg：f(x) =2*x+1
- 数字分析法：取数字的前两位或者后三位作为下标。
- 平方取中法：将关键字平方后取中间某几位作为下标。
- 除留余数法（常用）：将关键字模某个值，产生的下标作为地址eg：f(x) = x%13;
解决冲突方法：线性探测再散列，二次探测再散列，再哈希（重新构建新的哈希函数）等。
- 冲突：不同关键字带入哈希函数得到相同下标。
- 线性探测再散列:逐一往后+1的方式探测。
- 二次探测再散列：逐一往后+i^2方式探测。
- 再哈希：重新构建新的哈希函数。
  时间复杂度O(1)。

假设由关键字：{12，14，21，36，18，66，16}构建哈希表，哈希函数是H(key) = key%7
采用线性探测解决冲突，表中初始值为-1.请构建哈希表。

#include <stdio.h>

int main(int argc, const char *argv[])
{
	ins sub; 			//存储临时下标
	int hash[20];		//定义长度为20的哈希表
	//将哈希表中所有元素的值初始化为-1
	for(int i = 0; i < 20; i++)
	{
		hash[i] = -1;
	}
	
	//定义数组存储待处理数据
	int arr[7] = {12,14,21,36,18,66,16};
	for(int i = 0; i < 7; i++)
	{
		sub = a[i]%7; 		//将数组中的元素传入哈希函数计算下标
		while(-1 != hash[sub]) 		//如果发生冲突，则进行线性探测
		{
			sub = (sub+1)%13;
		}
		hash[sub] = arr[i];	//将数据放入哈希表中
	}
	
	//哈希查找
	int temp;
	int count = 0; 			//统计查找次数
	printf("请输入要查找的数据:");
	scanf("%d", &temp);
	sub = temp%7;
	while(hash[sub] != temp)	//未找到该数据
	{
		sub = (sub+1)%7;		//进行线性探测
		count++;
		if(count % 13 == 0)
		{
			break; 				//已经全部查找过了
		}
	}
	if(count == 13)
	{
		printf("查找失败\n");
	}else
	{
		printf("要查找的数据在%d位\n", sub+1);
	}
	return 0;
}

IO

概念

学习方法：不要死记硬背，学会使用man手册查，加上有道翻译去理解。

input：输入，output：输出

IO是计算机中的输入/输出（Input/Output）的简称，指的是计算机系统与外部设备之间进行数据交换的过程。输入是指将外部数据传输到计算机系统中，输出是指将计算机系统中的数据传输到外部设备中。
标准IO，也称为高级IO，是C语言标准库提供的一种IO操作方式。它使用文件流指针（如stdin、stdout、stderr）作为操作入口，通过缓冲机制（全缓冲、行缓冲、不缓冲）来管理数据的输入和输出。标准IO提供了丰富的函数接口，如fopen、fclose、fread、fwrite等，方便开发者进行文件操作
文件IO，也称为低级IO，是Linux系统调用提供的一种IO操作方式。它通过文件描述符（0，1，2）来访问文件，文件描述符是一个非负整数，用于标识打开的文件。文件IO没有缓冲机制，直接对文件进行读写操作。常见的文件IO函数有open、close、read、write等。

标准IO

标准IO依赖C标准库，使用时调用C标准库的函数，在写入或者读取数据时，标准IO先将数据放入缓冲区，当缓冲区满了或者刷新时机到了，标准IO会调用文件IO将数据写入硬件或者从硬件读取出来。
标准IO = 文件IO+缓冲区
标准IO函数：scanf/printf getchar/putchar gets/puts
文件IO依赖于系统调用，文件IO没有缓冲区，每一次调用，系统都会进行一次内核态到用户态的切换，也就是每一次调用系统都处于阻塞状态，等待用户程序执行完成，所以文件IO调用时非常浪费系统开销。

创建递归索引（用于查询结构体定义）

进入 cd /usr/include 专门用来存放头文件的目录
进入 cd /usr/include 专门用来存放头文件的目录
vim -t 想要查看的数据名前两步是一次性操作，之后想要查看其他内容，直接执行第三步即可

文件IO

依赖系统调用，由内核封装的一系列函数，可以直接作用于操作系统，每一次调用操作系统都处于阻塞状态，等待文件IO进程的完成，所以使用文件IO系统开销非常大。

标准IO缓冲区指针

stdin：标准输入流指针，调用标准IO输入函数时，标准IO输入函数操作的指针，将数据放入stdin指向的缓冲区。
stdout：标准输出流指针，调用标准IO输出函数时，标准IO输出函数操作的指针，将数据从stdout指向的缓冲区输出。
stderr：标准出错流指针，调用标准IO错误函数时，标准IO错误函数操作的指针，没有缓冲区，出错信息会立刻显示出来。

相关函数

fopen fclose

#include <stdio.h>

       FILE *fopen(const char *pathname, const char *mode);
       功能：打开文件
       参数1：指向文件的指针（一般写成路径）
           绝对路径：home/ubuntu/24101/IO/IO-1/1.txt 是从家目录出发的一整条完整的路径。
           相对路径：/1.txt 当前文件夹下的某个文件。
       参数2：打开模式由6种可选
           r：只读方式打开文件，光标位于文件的开头。
           r+：读写方式打开文件，光标位于文件的开头。
           w：只写方式打开文件，如果文件不存在就创建文件，如果文件存在就清空文件内容，
           光标位于文件的开头。
           w+：读写方式打开文件，如果文件不存在就创建文件，如果文件存在就清空文件内容，
           光标位于文件的开头。
           a：追加写的方式打开文件，如果文件不存在就创建文件，光标位于文件的末尾
           a+：读和追加写的方式打开文件，如果文件不存在就创建文件，读的时候光标位于文件的开
           头，写的时候光标位于文件的末尾。                                 
    返回值：成功返回指向打开的文件指针，失败返回NULL，并置位错误码。
    
     #include <stdio.h>

       int fclose(FILE *stream);
       功能：关闭文件指针指向的文件，将光标重置到文件开头。
       参数1：文件指针
       返回值：成功返回0，失败返回EOF(-1)并置位错误码。

fgetc fputc

#include <stdio.h>

       int fgetc(FILE *stream);
    功能：从stream指向的文件中，读取一个单字符。
    参数：指向文件的指针
    返回值：成功返回读取的字符，读取到文件末尾或者失败返回EOF（-1）
    
     #include <stdio.h>

       int fputc(int c, FILE *stream);
       功能：将字符c写入到stream指向的文件中
       参数1：字符变量或者常量
       参数2：指向文件的指针
       返回值：成功返回写入的字符，失败返回EOF(-1)

fgets fputs

#include <stdio.h>
       char *fgets(char *s, int size, FILE *stream);
       功能：从stream指向的文件中读取size-1个字符放入s指向的缓冲区，在末尾加上'\0'。
       读取时连同换行一起读取。
       参数1：字符串存储的起始地址。
       参数2：读取的大小size-1个字符
       参数3：文件指针。
       返回值：成功返回读取的字符串，失败或者读取到文件末尾返回NULL.
#include <stdio.h>

      
       int fputs(const char *s, FILE *stream);
       功能：将s指向的字符串写入到stream指向的文件
       参数1：字符串起始地址
       参数2：文件指针
       返回值：成功返回非负数，失败返回EOF(-1)

sprintf snprintf

#include <stdio.h>

     
       int sprintf(char *str, const char *format, ...);
       功能：将变量常量按照格式转换字符的形式写入到字符串str中
       参数1：字符数组或者字符串
       参数2：格式控制字符串
       参数3，4，5，6...:要写入字符串的数据（变量或者常量）
        eg：
        sprintf(str,"%s %d %f","班长是好人",100,12.5);
        但是无法预知要写入的字符串长度，可能会导致str的溢出
       int snprintf(char *str, size_t size, const char *format, ...);
        功能：将变量常量按照格式转换字符的形式写入到字符串str中
        参数1：字符数组或者字符串
        参数2：要写入的字节个数
        参数3：格式控制字符串
        参数4，5，6...:要写入字符串的数据（变量或者常量）