按月归档: 年 月

C++ 智能指针 shared_ptr的实现

dream/ 十月 29, 2018/ C/C++, 数据结构实现/ 0评论

一.实现思路

记录指针的引用计数。每次被复制时,增加计数。每次被赋值时,左侧计数减少,右侧计数增加,同时检查左侧计数是否为0。

从值构造时,new一块空间,并将计数值设置为1。

每次析构时,检查引用计数是否为0,为0则delete构造时new的空间。

默认构造函数可以构造空共享指[……]

阅读全文

各常用排序算法的C++实现及耗时比较

dream/ 十月 28, 2018/ C/C++, 算法及数据结构/ 0评论

一.各算法实现思路

  1. 选择排序:选择出数组中的最小元素,将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素,将它与数组的第二个元素交换位置。不断进行这样的操作,直到将整个数组排序。
  2. 冒泡排序:从左到右不断交换相邻逆序的元素,在一轮的循环之后,可以让未排序的最大元素上浮到右[……]

    阅读全文

使用git clone或push出现SSL错误的解决

dream/ 十月 21, 2018/ git, linux/ 3评论

今天升级Ubuntu18.04后,发现git无法push和clone。提示TLS连接问题,google后发现是由系统的 git 默认使用的 libcurl4-gnutls-dev 造成,可以使用openssl解决。

问题示例:

╰─$ git push origin master
fatal:[......]

阅读全文

斐波那契数列的循环算法以及与递归算法的比较

dream/ 十月 9, 2018/ 算法及数据结构/ 0评论

斐波那契数列是一个常用的用于介绍递归算法的入门题目。但是,实际上,它并不适合用递归计算,因为递归会进行大量重复计算(比如计算Fibonacci(10)实际会计算多次8,7…)。当数量增加时,递归方法所需要的时间会成指数递增。

Fibonacci_Recursive为递归算法,时间复杂度为O[……]

阅读全文

自己动手实现数据结构模板(5):字符串

dream/ 十月 8, 2018/ C/C++, 数据结构实现/ 0评论

字符串的实现借助于动态数组。到动态数组实现的链接。

字符串在动态数组的基础上,增加了从C风格的字符串(即以’\0’结尾的字符数组)构造和追加的相关函数,隐藏并重新实现了print函数,重载了<<运算符以使字符串能够直接输出到标准输出流。

具体实现:

#ifndef DTS_ST[......]

阅读全文

自己动手实现数据结构模板(4):动态数组

dream/ 十月 8, 2018/ C/C++, 数据结构实现/ 0评论

实现了动态增长空间的数组。当数组原空间不足以存储增加的内容时,会重新开辟数组空间并将数据移动到新空间。默认的增长速度为 原空间*2+1 ,再额外+1是为了防止空数组增长出现一直为空的情况(0*2=0)。

该动态数组实现了常用的接口函数(如size,at,append等),重载了可能常用的运算符[……]

阅读全文

一个关于继承时析构函数的BUG

dream/ 十月 1, 2018/ BUG, C/C++, 代码编译/ 0评论

在C++中,子类会自动调用父类的析构函数,这个在有时会导致一些问题。

昨天,我就因为这个遇到了一个迷之BUG。某个类第一次创建它的对象时没有任何问题,但是再创建一个就会导致double free。原因是我在子类的析构函数中又手动调用了父类的析构函数。但我无法理解的是,只调用一次时不出错。[……]

阅读全文

二叉树的非递归遍历

dream/ 十月 1, 2018/ C/C++, 算法及数据结构/ 0评论

对于二叉树的递归版本,请查看此文章中的二叉树定义中的print系列函数。

1.前序遍历

从根结点开始,首先输出,并入栈,然后访问其左子结点直到子结点没有左子结点。

之后出栈,用来逆序访问右子结点。

void traverse_pre(dtsBinaryTreeNode<in[......]

阅读全文