嵌入式入门Day25

🕗 发布于 2024-12-08 03:07 c语言 数据结构

数据结构Day 6,IO Day1

查找算法
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...:要写入字符串的数据（变量或者常量）

原文地址：https://blog.csdn.net/2301_77682837/article/details/144282280

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【CSS in Depth 2 精译_066】11.2 颜色的定义（上）：实现示例页中的基础样式及初步布局
下一篇：qt QNetworkAccessManager详解

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14