自定义模块
模块内容加载中...
红黑树的设计和实现
2008-12-15 0:23:08 阅读33 评论0 152008/12 Dec15
红黑树是一种比较重要的数据结构，但是很多数据结构和算法的书上仅仅粗略的介绍，尤其国内出版的数据结构和算法教材，很多甚至只字不提。鉴于此，这里给出一些简明扼要的介绍，并给出C++实现的代码。
一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：
1. 每个结点或者为黑色或者为红色。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL指针)都是黑色的。
4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。
5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。
下图中描述的是插入和删除一个节点用到的基本原理。[注意：旋转变色方法有多种，下图仅给出一种]
一棵红黑树是指一棵满足下述性质的二叉搜索树（BST, binary search tree）：
1. 每个结点或者为黑色或者为红色。
2. 根结点为黑色。
3. 每个叶结点(实际上就是NULL指针)都是黑色的。
4. 如果一个结点是红色的，那么它的两个子节点都是黑色的（也就是说，不能有两个相邻的红色结点）。
5. 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。
下图中描述的是插入和删除一个节点用到的基本原理。[注意：旋转变色方法有多种，下图仅给出一种]
functional
2008-12-15 0:20:30 阅读22 评论0 152008/12 Dec15
#ifndef FUNCTIONAL_H_
#define FUNCTIONAL_H_
template <class Arg, class Result>
struct unary_function
{
typedef Arg argument_type;
typedef Result result_type;
};
template <class Arg1, class Arg2, class Result>
struct binary_function
{
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
#define FUNCTIONAL_H_
template <class Arg, class Result>
struct unary_function
{
typedef Arg argument_type;
typedef Result result_type;
};
template <class Arg1, class Arg2, class Result>
struct binary_function
{
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
iterator
2008-12-15 0:15:30 阅读31 评论0 152008/12 Dec15
#ifndef ITERATOR_H_
#define ITERATER_H_
#include <cstddef>
using std::ptrdiff_t;
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
template <class
#define ITERATER_H_
#include <cstddef>
using std::ptrdiff_t;
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};
template <class
type_traits
2008-12-15 0:14:28 阅读34 评论0 152008/12 Dec15
#ifndef TYPE_TRAITS_H_
#define TYPE_TRAITS_H_
#include <wchar.h>
struct false_type {};
struct true_type {};
template <class type>
struct type_traits
{
typedef true_type this_dummy_member_must_be_first;
typedef false_type has_trivial_default_constructor;
typedef fal
#define TYPE_TRAITS_H_
#include <wchar.h>
struct false_type {};
struct true_type {};
template <class type>
struct type_traits
{
typedef true_type this_dummy_member_must_be_first;
typedef false_type has_trivial_default_constructor;
typedef fal
memory
2008-12-15 0:12:52 阅读24 评论0 152008/12 Dec15
#ifndef MEMORY_H_
#define MEMORY_H_
#include <cstddef>
#include <new>
#include <cstring>
using std::size_t;
using std::ptrdiff_t;
#include "type_traits.hpp"
#include "pair.hpp"
#include "iterator.hpp"
template <typename T>
static inline T* allocate(size_t n, T*) { return (T*)(operator new(n * sizeof (T))); }
template <typename T, typename Value>
#define MEMORY_H_
#include <cstddef>
#include <new>
#include <cstring>
using std::size_t;
using std::ptrdiff_t;
#include "type_traits.hpp"
#include "pair.hpp"
#include "iterator.hpp"
template <typename T>
static inline T* allocate(size_t n, T*) { return (T*)(operator new(n * sizeof (T))); }
template <typename T, typename Value>
Why Java Will Always Be Slower than C++
2008-11-26 16:27:00 阅读46 评论0 262008/11 Nov26
by Dejan Jelovic
"Java is high performance. By high performance we mean adequate. By adequate we mean slow." - Mr. Bunny
Anybody that has ever used a non-trivial Java program or has programmed in Java knows that Java is slower
约索夫环问题用数组实现
2008-11-17 21:33:09 阅读25 评论0 172008/11 Nov17
#include <iostream>
#include <cstdlib>
#include <vector> //当作数组用
#include <ctime>
void output_format(size_t d) //格式化输出一点信息
{
if(d % 100 == 11 || d % 100 == 12 || d % 100 == 13)
std::cout << "th";
else
switch(d % 10)
{
case 1: std::cout << "st"; break;
case 2: std::cout << "nd"; break;
#include <cstdlib>
#include <vector> //当作数组用
#include <ctime>
void output_format(size_t d) //格式化输出一点信息
{
if(d % 100 == 11 || d % 100 == 12 || d % 100 == 13)
std::cout << "th";
else
switch(d % 10)
{
case 1: std::cout << "st"; break;
case 2: std::cout << "nd"; break;