| by msbeta | No comments

数据结构与算法-计算二叉树中节点的最大距离

1.问题定义

如果把二叉树看做无向图,我们姑且定义二叉树的“距离”为节点之间边的个数。现在要计算二叉树中相距最远的两个节点之间的距离。

二叉树的节点距离计算有几种情况:

1) 根节点为空,路径长度为0;

2) 根节点非空的情况下,分为两种情况:

情况A: 路径经过左[……]

继续阅读

Read More
| by msbeta | 1 comment

C++多线程编程-智能指针shared_ptr

1、shared_ptr的引用计数是线程安全的么?

shared_ptr的引用计数是线程安全的。

2、shared_ptr对象是线程安全的么?

shared_ptr对象不是线程安全的。如果多个线程读写同一个shared_ptr对象,需要加锁。注意,这里说的shared_ptr对象本[……]

继续阅读

Read More
| by msbeta | No comments

C/C++:如何定义和初始化二维数组

在C/C++中有很多定义数组的方式,在日常的应用中也会高频用到,今天一起看看有哪些定义和初始化二维数组的方式。

1、C/C++语言原始数组的方式

数组是C语言的原住民了,在第一代C语言中就已经出现了,在初学者的C/C++的入门书籍中也有详细的介绍。它对二维数组的定义如下:

co[……]

继续阅读

Read More
| by msbeta | No comments

链表的二分搜索实现-跳跃表

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。

—-by 发明者

在redis中有序集合就使用到了跳跃表。

跳跃表允许快速查询一个有序连续元素的数据链表,它的效率可以做到和二分相同,都是[……]

继续阅读

Read More
| by msbeta | No comments

数据结构算法-多叉树遍历算法及其在路径查找中的应用(c++)

1、多叉树遍历算法的代码实现

树是数据结构中的一个基础的算法,课本上一般以二叉树为例,讲解树的各种遍历算法,那么针对于n叉树(n>2),如何实现对应的算法呢。它们的道理其实是完全相通的。

首先定义树的节点的结构。树的节点结构大体可以分为两个部分:数据域和链接域。数据域中包含所有的数[……]

继续阅读

Read More
| by msbeta | No comments

C++中如何检测字符串是否以指定字符串结尾

C++经常需要检测字符串是否以指定字符串结尾,但STL中没有提供endsWith()函数。本文主要讨论如何实现C++的endsWith()函数的功能。

1.std::string endWith() using std::string::compare() and std::all_of()[……]

继续阅读

Read More
| by msbeta | No comments

C++中检查字符串是否以指定字符串开头

在C++中,std::string没有提供starts_with()函数用来检查字符串是否以指定字符串开头.本文讨论如何使用std::string::find和Boost库实现starts_with()的功能.

1.使用STL的string::find()函数实现starts_with()功能[……]

继续阅读

Read More