> 文档中心 > 《算法笔记知识点记录》第二章——快速入门4[结构体、输入输出、复杂度和黑盒测试]

《算法笔记知识点记录》第二章——快速入门4[结构体、输入输出、复杂度和黑盒测试]

在这里插入图片描述

☘前言☘

咕咕咕、鸽子精又回来了。🐒
今天是我开坑的第四次发文,大家最近应该都在忙期末把?明天要考六级的我还在写文章是不是疯了-.-
今天是基础知识的最后一次,接下来慢慢就要开始接触算法了,有没有很期待?如果我有哪些没有讲清楚的,欢迎大家联系我,你提出的问题是我修改完善的基础,万分感谢。

  • 欢迎大家加入我的打卡队列,如果你刷完了对你有帮助请你评论一个打卡。
  • 如果你觉得这本书有用的话还希望多多支持作者。

如果觉得这个文章有用还希望大家交出素质三连呀。

🧑🏻作者简介:一个从工业设计改行学嵌入式的年轻人
✨联系方式:2201891280(QQ)
📔源码地址:https://gitee.com/xingleigao/algorithm-notes
全文大约阅读时间: 80min


文章目录

  • ☘前言☘
  • 🍭1. 基础知识点
    • ⚽️1.1 结构体(struct)
      • 🏀1.1.1 结构体的定义
      • 🏈1.1.2 访问结构体内的元素
      • ⚾️1.1.3 结构体的初始化
    • 📡1.2 cin与cout
    • 🎚1.3 浮点数的比较
    • 🥩1.4 复杂度
      • 🍔1.时间复杂度
      • 🍟2.空间复杂度
      • 🌭3.编码复杂度
    • 🥚1.5黑盒测试
      • 🥙1.单点测试
      • 🥗2.多点测试
  • 🐳课后习题

🍭1. 基础知识点

其实上次文章所讲的指针是c语言最难的部分,也不知道大家消化了没有,最好的方式肯定是多做题啦。我补充了一个参考链接,如果还是懵懵懂懂的可以看看上次文章里提到的链接0.0

⚽️1.1 结构体(struct)

到现在,我们了解了基本数据类型的使用(char、int、long long 、double),但是如果我们需要一种情况:实现一个手机通讯录:需要以人为单位,且每个人的内部信息由姓名、年龄、手机号、住址信息之类的不同信息组成,这个时候如果用之前的单种数据就会非常不方便,就需要结构体。

🏀1.1.1 结构体的定义

结构体的基本格式如下:

struct Name{//一些基本数据类型或者自定义的数据类型};

当需要一些相关的变量的放在一起存储的时候,只需要依次写出他们的数据类型和变量名称。
举个栗子🌰

struct studentInfo{int id;char gender; //'F' or 'M'char name[20];char magor[20];}Alice, Bob, stu[1000];

其中studentInfo是结构体类型名。内部定义了id(学号)、gender(性别)、name(姓名)和mahor(专业),这些就是单个学生的信息。而结构体外定义了AliceBob两个结构体变量和一个stu结构体数组。
结构体除了在定义的时候进行定义外,还可以在使用的时候定义

studentInfo Alice;studentInfo stu[1000];

注意:

  1. c语言里的struct不能省略,所以定义一个结构体变量c里面的写法是:
struct studentInfo Alice;
  1. 结构体能定义除自身的的所有数据类型。但是可以定义自身类型的指针
struct node{node n;//错误示例node *next;//c语言里的写法是 struct node *next;}

🏈1.1.2 访问结构体内的元素

访问结构体内的元素有两种方法:.->操作。现在有如下结构体

struct studentInfo{int id;char name[20];studentInfo *next;}stu, *p;

这样多了一个指针来指向下一个学生地址,且定义了普通变量stu和指针变量p
于是访问数组元素的写法如下:

stu.id;stu.name;stu.next;(*p).id;p->name;p->next;

观察上面的写法,其实(*p).idp->id写法是完全等效的。可以说->就是一种简洁写法罢了。不过要注意这种写法是针对指针的,对于stu这种普通的结构体就不能使用!!!

⚾️1.1.3 结构体的初始化

这部分基本上都是C++的写法,C语言没有这些,老老实实自己初始化。。。
一般的做法是先声明一个变量。然后再初始化

stu.id = 1;stu.gender = 'M';

还记得我们平常int类型可以声明的时候顺带初始化写法就是int i = 1;,那么结构体有没有这种写法呢?答案是有的。


构造函数
构造函数就是用来初始化结构体的一种函数,它直接定义在结构体中。
特点是不需要放回类型,且函数名和结构体名相同
一般来说都有一个默认的构造函数就是studentInfo(){}
就是声明的时候对变量不做任何初始化操作。

struct studentInfo{int id;char gender;studentInfo(){}//默认构造函数}

我们也可以手动重构这个函数

struct studnetInfo{int id;char name[20];studentInfo(int _id, int _gender){id = _id;gender = _gender;}}

当然可以做一个简化

struct studentInfo{int id;char name[20];studentInfo(int _id, int _gender) : id(_id), gender(_gender) {}}

这样就可以在声明的时候顺带赋值了
studentInfo stu = studentInfo(10086, 'M');
如果自定义了构造函数,那么就不能不初始化就定义结构体变量。 也就是下面的写法就不合法了。

studentInfo stu;

那如果我们想要都要呢?
这里其实利用的是c++语言的函数多态,我们定义多个同名函数,根据变量数目的多少,进行调用。

#includestruct Point{int x,y;Point(){}//不初始化就定义Point(int _x, int _y) : x(_x), y(_y) {}//用提供的x、y初始化结构体}pt[10];int main(){int num = 0;for(int i = 0;i <= 3;i++)for(int j = 0;j <=3;j++)pt[num++] = Point(i, j);//调用构造函数for(int i = 0;i < num;i++)printf("%d,%d\n",pt[i].x,pt[i].y);return 0 ;}

构造函数在结构体内元素较多的时候能极大的简化我们的代码。

📡1.2 cin与cout

cin
cin的输入输出速度实在是太慢,所以在考试的时候完全不推荐cin来作为输入。
但是之前说过gets被禁用了。gets_s 在c++中又不允许使用,所以我们偶尔需要用cin.getline来读入字符串。
cin.getline(str,1000);的形势读入字符串的时候需要记得#include<iostreamusing namespace std;
还有就是如果读入的是将字符串读入string容器(之后会讲)的话是下面这种形式

string str;getline(cin,str);

cout
完全不推荐0.0

🎚1.3 浮点数的比较

由于计算机中采用有限位的二进制编码,因此浮点数在计算机中的存储并不总是精确的。下图是float和double的二进制存储。
在这里插入图片描述
**在经过大量计算之后,浮点数发生改变。**例如:3.14可能变成3.13999999999或者3.14000000001,这种情况下浮点数就不能使用(==)来判断是否相等了。

一般的做法是引入一个极小数eps来对这种误差进行消除。根据经验表示eps选择1e-8(10-8)比较合适。

那么对应的判断相等和大于小于和大于等于小于等于呢?
我给大家做了个总结的图,记住图就会写代码。
请添加图片描述
附上宏定义的写法:

const double eps = 1e-8;const double pi = acos(-1.0);#define Equ(a, b) ((fabs((a) - (b))) < (eps))#define More(a, b) (((a) - (b)) > (eps))#define Less(a, b) (((a) - (b)) < (eps))#define MoreEqu(a, b) (((a) - (b)) > (-eps))#define LessEqu(a, b) (((a) - (b)) > (eps))

记不住建议就画图 然后对照图些就好了

🥩1.4 复杂度

一般来说复杂度都包含时间复杂度和空间复杂度和编码复杂度。


🍔1.时间复杂度

时间复杂度指的就是需要执行的基本运算的次数所处的量级

for(int i = 0;i < n;i++)sum += a[i];

这个for循环的复杂度就是O(n)

for(int i = 0;i < n;i++){sum += a[i];sum += a[i];}

上面的量级就是在2n,但是两者都是随数量级线性增长的,所以一般我们认为O(2n)O(n)等价。

for(int i = 0; i < n;i++)for(int j = 0;j < n;j++)sum += a[i][j];

上面的基本操作就是量级在O(n2),其消耗的时间随n的增大而呈现平方级增长。
在时间复杂度中,高幂次会吸收低幂级的复杂度
例如:我们认为O(3n2 + n = 2) = O(3n2) = O(n2)。
我们把3这个常数叫做时间复杂度的常数,有些算法比较复杂的时候。可能会出现卡常数的情况,但是一般不带常数讨论复杂度。
对于OJ来说,一秒能承受的运算次数啊大概在107 ~ 108
因此,O(n2)的算法对于n规模为1000可以接受,但是n为100000时间是不可以接受的。
对于不同形式的复杂度的比较:记住五个字常对幂指阶
也就是考研常说的比大小的问题。从前往后复杂度依次升高


🍟2.空间复杂度

与时间复杂度对应的就是空间复杂度,主要取决于开的数组大小一般来说空间不超过100m都是可以接受的,大概对应的数组就是107以上的大小


🌭3.编码复杂度

这是一个定性的概念,如果算法过于冗长就会产生比较长的编码,代码量就比较巨大。
所以大家要用函数去做一些重复的事情,有利于降低编码复杂度。

🥚1.5黑盒测试

黑盒测试是指:系统后台会准备若干测试数据,然后让提交的程序就跑,如果输出的答案与正确答案完全相同(字符串层面的比较) 就通过了黑盒测试,否则返回对应的错误。其中分为单点测试多点测试


🥙1.单点测试

所谓的单点测试就是系统会判断每组数组就是正确,如果通过这组数据就算通过了一组数据,获得对应的分数。PAT和洛谷都是采用的这种形式。这种情况下只需要保证一遍程序的执行就可以了。
举个例子:

#includeint main(){int a, b;scanf("%d %d", &a,&b);printf("%d\n",a + b);return 0;}

这种就是执行完一组数据程序就会正常返回。


🥗2.多点测试

多点测试要求程序一次性运行完所有的数据,否则就是不通过。部分在线评测系统(codeup)采用这种方式。
对于多点测试我们需要知道什么时候程序输入结束。基本上有三种读取方式分别介绍。


2.1while …EOF型
这种题一般不知名何时输入结束,我们就要利用结束符判断程序的结束。
当读到文件结束符的时候,scanf函数会返回EOF
所以我们可以这么写:

while(scanf("%d %d",&a,&b) != EOF){...}

给个例子

#includeint main(){int a, b;while(scanf("%d %d", &a, &b) != EOF)printf("%d\n",a + b);return 0;}

在我们平常测试的时候并不会触发EOF状态。因此如果想要在调试框内手动触发EOF,可以按Ctrl + Z 组合键,屏幕上会显示^Z,按Enter就可以结束了。


2.2while…break型
这种适合当a、b都是0时结束输入

#includeint main(){int a, b;while(scanf("%d %d", &a, &b),a || b){printf("%d\n",a + b);}return 0;}

2.3while(T–)型
这种题目会在一开始给出数据的数量,标准模板如下:

#includeint main(){int T, a, b;scanf("%d", T);while(T--){scanf("%d %d", &a, &b);printf("%d\n",a + b);}return 0;}

再给一个要求两组数据之间有一个空行,最后一组数据后面没有空行

while(T--){int sum = 0;scanf("%d", &n);for(int i = 0;i < n;i++){scanf("%d", &a);sum += a;}printf("%d\n",sum);if(T > 0)puts("");}

最后要说明:

  • 在多点测试中,每一次循环都要重置一下变量和数组,否则下一组数据来临的时候就不是初始状态了,一般使用memsetfill函数来进行。
  • 根据要求灵活修改判断条件格式化输出(不要担心后面会有更多的练习)

🐳课后习题

今天的题目难度也不高,有点多,我写完会放题解,大家写完了可以在评论区打卡哟!题解我放评论区吧,这样不用修改文章。(大家有问题可以联系我,今天太晚了,题解可能会鸽两题 咕咕咕)

题目
2.8小节——C/C++快速入门->结构体(struct)的使用
2.10小节——C/C++快速入门->黑盒测试

题解:评论区见,置顶没有就是我没写完0.0,大佬们刷完打个卡