一个普通技术宅的点点滴滴

0%

本来昨天的计划是研究背包,栈,队列的,但是没想到实际研究起来光一个栈都那么花时间。今天写了一个栈的动态数组实现API,这个API我实现了两种版本,第一种是使用了固定长度的数组来存储,很不方便,使用时必须指定大小,并且经常会有空间浪费或者栈满的需求。使用了动态数组的方法,就能实现栈的高可用性。在栈的元素较少时将栈减小,元素满时扩大。下面是第一种实现和一个测试用例:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct
{
  int * sta;
  int maxSize;
  int nowSize;
  } stack;
//API声明
stack* StackCreate(int size);
int StackPop (stack * sta);
bool StackPush (stack *sta,int i);
int StackSize (stack *sta);
bool StackIsEmpty (stack *sta);
bool StackIsFull (stack *sta);//
void StackFree (stack *sta);
//测试用例
int main(int argc, char const *argv[]) {
  stack *st=StackCreate(100);
  for (int i=0;!StackIsFull(st);i++)
  {
    StackPush(st,i);
  }
  while (!StackIsEmpty(st)) {
    printf("%d ",StackPop(st));
  }
  StackFree(st);
  return 0;
}
//API实现
stack* StackCreate(int size)
{
  stack *temp=malloc(sizeof(stack));
  if (size<1)
  return NULL;
  temp->sta=(int *)malloc(sizeof(int)*size);
  temp->maxSize=size;
  temp->nowSize=0;
  return temp;
}

int StackPop(stack * sta)
{
  if (StackIsEmpty(sta))
  return -1;
  else
  return sta->sta[--sta->nowSize];
}

bool StackPush (stack *sta,int i)
{
  if (StackIsFull(sta))
  return false;
  else
  sta->sta[sta->nowSize++]=i;
  return true;
}
int StackSize (stack *sta)
{
  return sta->nowSize;
}
bool StackIsEmpty (stack *sta)
{
  return sta->nowSize==0;
}
bool StackIsFull (stack *sta)
{
  return sta->nowSize==sta->maxSize;
}
void StackFree(stack *sta) {
  free(sta->sta);
  free(sta);
}

第二种实现我将其打包成了一个库,下面是具体代码:

stacklib.h
#ifndef STACK
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define STACK 0
#endif
#ifndef STACK_INIT_SIZE
#define STACK_INIT_SIZE 3
#endif
typedef struct
{
int * sta;
int maxSize;
int nowSize;
} stack;
stack* StackCreate(void);
int StackPop (stack * sta);
void StackPush (stack *sta,int i);
int StackNowSize (stack *sta);
int StackMaxSize (stack *sta);
bool StackIsEmpty (stack *sta);
//bool StackIsFull (stack *sta);
void StackFree (stack *sta);


stacklib.c
#include “stacklib.h”
stack* StackCreate (void)
{
stack *temp=malloc(sizeof(stack));
temp->sta=(int *)malloc(sizeof(int)*STACK_INIT_SIZE);
temp->maxSize=STACK_INIT_SIZE;
temp->nowSize=0;
return temp->staNULL?NULL:temp;
}
bool StackReSize(stack * sta,int size)
{
if (size<=0)
return false;
int *temp=malloc(sizeof(int)*size);
if (temp
NULL)
return false;
for (int i=0;inowSize;i++)
{
temp[i]=sta->sta[i];
}
free (sta->sta);
sta->sta=temp;
sta->maxSize=size;
return true;
}
int StackPop(stack * sta)
{
if (StackIsEmpty(sta))
return -1;
int i=sta->sta[–sta->nowSize];
if (sta->maxSize/4>=sta->nowSize)//空间过剩时,减少数组容量
{
StackReSize(sta,sta->maxSize/2);
}
return i;
}
void StackPush (stack sta,int i)
{
if (sta->nowSize==sta->maxSize)//空间不够时,扩充数组容量
{
StackReSize(sta,sta->maxSize
2);
}
sta->sta[sta->nowSize++]=i;
}
int StackNowSize (stack *sta)
{
return sta->nowSize;
}
bool StackIsEmpty (stack *sta)
{
return sta->nowSize==0;
}
void StackFree(stack *sta)
{
free(sta->sta);
free(sta);
}
int StackMaxSize(stack *sta)
{
return sta->maxSize;
}

最后,我运用栈来做了一个小计算器,可惜目前还不能实现判断运算的先后顺序,只能人为在每个运算后添加括号进行运算,比如52必须要输入(52)才能计算,代码如下:
#include “stacklib.h”
#ifndef READ_SIZE
#define READ_SIZE 30
#endif
int main(int argc, char const argv[]) {
char ch[READ_SIZE];
fgets (ch,READ_SIZE,stdin);
stack numSta=StackCreate();//数字栈
stack chSta=StackCreate();//操作符栈
bool lastIsNum=false;//标志位,判断上个读取的字符是否是数字
for (int i=0;ch[i]!=’\0’&&ch[i]!=’\n’;i++)
{
switch (ch[i])
{
//若为操作符,压入操作符栈
case ‘+’:
case ‘-’:
case '
’:
case ‘/’:
case ‘%’:
lastIsNum=false;
StackPush(chSta,(int)ch[i]);
break;
case ‘)’😕/右括号表示前面是一个运算,进行运算
{
char op=StackPop(chSta);//取出操作符
int val=StackPop(numSta);//取出右操作数
switch (op)
{
case ‘+’:
val+=StackPop(numSta);
break;
case ‘-’:
val=StackPop(numSta)-val;
break;
case '
’:
val
=StackPop(numSta);
break;
case ‘/’:
val=StackPop(numSta)/val;
break;
case ‘%’:
val=StackPop(numSta)%val;
break;
default:
break;
}
StackPush(numSta,val);
lastIsNum=false;
}
break;
case ‘(’😕/左括号直接丢弃
lastIsNum=false;
break;
default:
if (ch[i]>47&&ch[i]<58)//判断是否为数字
{
if (lastIsNum==true)
{
int temp=StackPop(numSta);
temp=temp*10+(ch[i]-48);
StackPush(numSta,temp);
}
else
{
StackPush(numSta,ch[i]-48);
}
lastIsNum=true;
}
else//未预期的符号
{
printf(“Error\n” );
exit(-1);
}
break;
}
}
printf("%d\n",StackPop(numSta));
StackFree(numSta);
StackFree(chSta);
return 0;
}turn 0;
}

今天解决的算法题目是对于两个数互质的判断,原本我认为这个方法应该不难,但是真正实现起来还是思考良久。问题的关键还是之前我没有考虑其中一个数会等于零,所以导致了一直都不对。最后还是用一个类似欧几里得的递归方法解决了这个问题,C代码如下

bool isPrime (int p,int q)
{
  if (p==0)
    return q==1?true:false;
  if (q==0)
    return p==1?true:false;
  if (p==q)
    return true;
  if (p>q)
    return isPrime(p%q,q);
  else
  return isPrime(p,q%p);
}

明天学习背包,队列和栈,打算学写一个能够直接读取式子的计算器。

今天了解了算法的鼻祖——欧几里得算法(辗转相除法),虽然这个算法是一个挺简单的算法,但是还是花了不少时间去弄懂,也算是体现出了我在算法上的不足。
算法如下:

    int gcd (int p,int q)
    {
      printf("p=%d,q=%d\n",p,q);
      if(p==0)
      return q;
      if(q==0)
      return p;
      if (p>q)
      return gcd(p%q,q);
      else
      return gcd(p,q%p);
    }

BTW,今天读了数学之美,又认识到了很多数学工具在解决实际问题的重要性,特别是概率论,让我受益匪浅。比如,语义识别最有效的方法不是词法分析,而是概率模型。

这个星期又入了几本书,开坑就没好好填完

首先是学习C艹方面,C艹对于类的学习算是告一段落了。C艹到目前为止,给我的一种感觉就是很繁琐。我想可能这也是为什么C艹没能完全取代C语言的地方。

然后开坑算法学习,目前我认为应当打好一些算法的基础,以后对于实际项目会有一定帮助,入了一本《算法》慢慢啃。也许现在的重心还是应当回到对算法的学习上,因为已经有C语言基础的前提下,并不给与去学习C++,并且如果学习以后又用不上就很容易遗忘。

最后是一些其他闲书,一是对ruby语言很感兴趣,可以在闲暇之余了解一番,然后看了一点《数学之美》,就我目前接触到的书而言,吴军博士的书质量都是值得一读的,读了《数学之美》后才明白,原来数学是可以这样使用的,真是有种醍醐灌顶的感觉。��都是值得一读的,读了《数学之美》后才明白,原来数学是可以这样使用的,真是有种醍醐灌顶的感觉。

在继续对《C++ Primer》今天对于C++类的默认构造函数有了新的了解。

默认构造函数是什么?

默认构造函数,就是不包含任何参数,或者所有参数均提供了初始值的构造函数。

什么时候会执行默认构造函数?

当对象被默认初始化或者值初始化时会自动执行默认构造函数。

在很多时候,我们都会用到默认构造函数,而不仅仅是进行默认初始化的时候,所以如果定义了其他构造函数,最好也提供一个默认构造函数,即使这个类并没有一个合法的默认值。

今天基本上都在和DigitalOcean和AWS的客服周旋。。。所以没学什么,稍微了解了一下C++类的作用域。

每个类都会定义它自己的作用域。在类的作用域外,普通的数据和函数成员只能由对象,引用或者指针使用成员运算符访问。

如在Screen类中使用

using pos=int;

的话,在外部就需要用

Screen::pos i;

来声明变量

今天学习的内容是给自己的网站开启全站HTTPS。如果你是在我的博客阅读这篇文章的话,可能已经注意到,我的博客已经开启了全站HTTPS。虽然只是多少了一个S,但是传输过程区别很大。

为什么要切换到全站HTTPS?

因为HTTP是一种明文传输协议,非常容易被截获和修改,为了避免第三方对我们访问网站造成的影响,所以目前国际上都在推广HTTPS,可见HTTPS取代HTTP将是未来的大势所趋。所以我也不例外,加入了这个安全化的浪潮。有的人可能会觉得,不重要的网站不用开启HTTPS,但是无论网站重要与否,当用户访问的时候被恶意修改为钓鱼网站都是我们不想见到的。况且现在升级HTTPS成本很低了,有的机构SSL证书可以直接免费领取,所以升级HTTPS才是正解。

切换HTTPS的步骤

首先申请一个SSL证书,这里既可以选择收费的也可以选择免费的,我推荐使用Let’s encrypt的免费证书,这个证书可以到官网申请。

将这个SSL证书部署到你的服务器上,由于我用的是云空间,直接填写证书和私钥就可以了。

这时就可以通过https访问网站了,但是如果使用HTTP的话,还是能够进入网站,这时我们可以在服务器的Apache配置文件(.htaccess)下对HTTP访问设置301返回,就可以实现强制HTTPS,在文件后加入这几行:

RewriteBase /
RewriteCond %{HTTP:KERSSL} !on
RewriteRule ^.*$ https://%{SERVER_NAME}%{REQUEST_URI} [L,R=301]

做完这些工作,一般来说已经完成了,但是由于现在用的都是各种建站系统,里面的主题插件什么的难免用到外链HTTP资源.所以我们还需要将这些资源文件移动到自己的主机上.
开启浏览器的安全例外,然后在开发者控制台里的"网络"一栏对HTTP请求进行分析(记得禁用缓存),将其中的HTTP外链资源移到本地,再在相应的文件里面修改资源获取地址.就可以真正做到全站HTTPS啦!
HTTP资源文件分析

今天虽然放假了,但是却没怎么看书,因为今天几乎都把时间花在了对github学生包的申请上了。由于这个过程着实踩了不少坑,就在今天的总结分享一下过程。

Github学生包是什么?

Github学生包是一个由github免费提供给学生的福利,里面包括了计算机专业可能用到的很多付费资源,通过认证后即可领取。

怎么通过认证?

Github提供了两种认证方式,一是edu邮箱认证,二是证件认证。作为天朝的学校,基本上是没有edu邮箱的,而即使有edu.cn的邮箱,通过率也很低。所以一般我们使用证件认证。打开github学生包页面,点击"Get your pack"按钮,然后下面会有提示让你进行登陆github账户和学生认证,只要上传你的学生证或者录取通知书就可以了。

领取的学生包都有什么?

  • Atom:这个本来就是一个开源的免费编辑器,写代码和markdown挺好用的。
  • AWS educate:这个是亚马逊为学生提供的学生包,可以提供一个110刀的云服务器的额度。由于需要二次验证,所以我目前为止没有领取。
  • Bitnami:这是一个一键部署云应用的平台
  • CARTO:大数据可视化分析平台
  • Crowdflower:一个通过人工智能机器学习等来完善数据,增强数据的平台
  • Datadog:也是大数据相关
  • DigitalOcean:这个是一个AWS类似的云主机平台,但是由于之前学生优惠被滥用,所以现在不仅将100刀的优惠降为了50刀,并且对于学生资格审查很严格,通过了github认证以后,还要进行paypal或者信用卡认证,甚至可能要求你发身份证自拍照(没错就是我)。
  • Flatron school:一个Web开发的学习平台
  • Github:就读期间可以在Github无限制的创建私人项目
  • Hackhands:一个可以为你提供编程学习在线支持的网站
  • Microsoft Imgine:原来叫做DreamSpark,是微软做的一个学生免费计划,其中最有用的就是Azure云服务的100刀额度,可惜在中国不支持
  • Namecheap:这个可以领取一年的免费.me域名和ssl证书
  • Sendgrid:一个邮件发送平台
  • Sentry:在线调试平台
  • Stripe:支付平台
  • Taplytics:一个移动端A/B测试平台
  • Thinkful:也是一个Web技术学习平台
  • Transifex:也是一个Web技术学习平台
  • Travis CI:一个软件项目的集成整合平台
  • Unreal Engine:大名顶顶的虚幻引擎,可以用来学学游戏制作

应该怎样使用?
以上的这些东西,累计价值可能已经达到了上千刀,但是作为学生,我们没有精力也没有必要去全部都使用,而是选择自己感兴趣的,需要的东西去学习。

最后,且用且珍惜,不要在让这些资源再次因为滥用而减少了。�了。

今天上导论和C语言课的时候,都对于浮点数有讲解,虽然之前已经大概了解浮点数的内容,但是今天对其进行了一些深入的探究,才发现浮点数并没有我想象中那么简单。

浮点数,很多人都只是把他当成一个普通的小数看待,在我之前的理解中,就是用类似科学计数法的方法去表示一个数。今天在通过翻阅wiki,才了解到浮点数的一些定义和奇特的性质,在下面做一些概括:

wikipedia是这样描述浮点数的:

在计算机科学中,浮点(英语:floating point,缩写为FP)是一种对于实数的近似值数值表现法,由一个有效数字(即尾数)加上幂数来表示,通常是乘以某个基数的整数次指数得到。以这种表示法表示的数值,称为浮点数(floating-point number)。利用浮点进行运算,称为浮点计算,这种运算通常伴随着因为无法精确表示而进行的近似或舍入。位(bit)是衡量浮点数所需存储空间的单位,通常为32位或64位,分别被叫作单精度和双精度。有一些计算机提供更大的浮点数,一个浮点数a由两个数m和e来表示:a = m * b^e

举个例子,1.2345这个数的十进制的浮点数表示方法就是12345*10^-4,这个时候我们称10是十进制浮点数的基底,我们要保存这个浮点数,只需要将12345和-4保存下来,就相当于保存了这个数。而二进制的浮点数与这个类似,只是将基底为10换为基底为2罢了。

需要特别说明的是,浮点数并不能精确表达所有实数,所以浮点数往往并不能精确计算。比如,二进制的浮点数中就不能精确的保存0.1这个十进制数,0.1的平方既不是准确的0.01,也不是最接近0.01的可表达的数。单精度(24比特)浮点数表示0.1的结果为

e=-4,m= 110011001100110011001101 (2)

0.100000001490116119384765625

此数的平方是

0.010000000298023226097399174250313080847263336181640625

但最接近0.01的可表达的数是

0.009999999776482582092285156250

所以我们在对于精度有特殊要求的时候应当避开使用浮点数。BTW,浮点加法和乘法不匹配结合律和分配律。

说到浮点数,就不得不提一下目前浮点数的标准IEEE 754,IEEE 754的全称叫做“电气电子工程师学会二进制浮点数算术标准”,在六七十年代,各家厂商使用的浮点数标准是不同的,所以当时的各厂商的计算机之间的兼容性很差。为了改善这个情况,IEEE(电气电子工程师学会(英语:Institute of Electrical and Electronics Engineers,简称为IEEE,是一个建立于1963年1月1日的国际性电子技术与电子工程师协会,亦是世界上最大的专业技术组织之一,制定了许多国际标准)这个组织的浮点数专业小组于七十年代末期开始酝酿浮点数的标准。在1980年,英特尔公司推出了单片的8087浮点数协处理器,其浮点数表示法及定义的运算具有足够的合理性、先进性,于是被IEEE采用作为浮点数的标准,于1985年发布。
浮点数的表示图

如果有兴趣的话,可以到这里详细了解IEEE 754的具体定义,原谅我懒Orz

今天继续对C++类进行了学习,对于类的功能函数有了新的认识

一般来说,类的功能函数应该声明为公共的,但是有时候不同,比如在这种情况

  public:
  Screen& display count (std::ostream &os)
  {
    //Some code
    return *this;
  }

这是一个类内的函数,其作用是输出类中的信息到指定的输出流中。这个函数实际对于类的成员变量并没有修改,所以我们一般会将其声明中加入count来保护,但是由于加入了count后,this是一个常量引用,所以无法正确返回,必须修改成这样。

  public:
  count Screen& display count (std::ostream &os)
  {
    //Some code
    return *this;
  }

但是,这样的话由于返回的对象是一个count,就无法再进行其他写入操作了,比如这样:

  myscr.display(os).write(' ');

我们如果又不想放弃count的保护特性的话,便可以这样处理:

  public:
  Screen& display(std::ostream &os)
  {
    do_display(os);
    return *this;
  }
  const Screen &display (std::ostream &os) const
  {
    do_display(os);
    return *this;
  }
  private:
  void do_display (std::ostream &os) const
  {
      //Some code
  }

这样做,可以在public中对display这个函数进行重载以适应不同的调用情况,同时,用一个私有成员函数进行进行代码复用,这样就可以避开将来修改时可能引入的许多bug。