指针与const限定符


(1) 指向const对象的指针(常量指针)

// 常量指针的两种形式
const int *ptr; // 推荐
int const *ptr;

C++强制指向const对象的指针必须具有const特性。此处const限定的了ptr指针所指向的对象的类型,而不是ptr指针本身。如果有需要,可以给指向const对象的指针重新赋值,使其指向另一个const对象;但不能通过该指针修改其指向的对象的值。

(2) const指针(指针常量)

double *const ptr;


指针本身的值不能改变,必须在定义时初始化。
(3) 指向const对象的const指针>

const int *const ptr;

栈(stack):后入先出(LIFO),有入栈Push、出栈Pop等操作。


一个简单的栈(Stack)实现(基于数组):

#pragma once
#include 
#include 

using namespace std;

template 
class MyStack
{
public:
	MyStack(void) : top(-1) {}
	~MyStack(void) {}

	void Push(const T &data);
	const T& Pop();

	int GetStackSize() {return stackSize;}
	void Output();	// 输出栈中数据(测试用)

private:

	int top;	// 栈顶
	T S[stackSize];	// 栈缓冲区

};

template 
void MyStack::Push(const T &data)
{
	assert(top < GetStackSize()-1);	// 防止栈上溢

	top++;
	S[top] = data;
}

template 
const T& MyStack::Pop()
{
	assert(top>=0);	// 防止栈下溢

	return S[top--];
}

template 
void MyStack::Output()
{
	for (int i=0; i<=top; ++i )
	{
		cout << S[i] << " ";
	}
	cout << endl;
}


测试代码:

#include "stdafx.h"
#include "MyStack.h"

int _tmain(int argc, _TCHAR* argv[])
{
	MyStack stack;

	stack.Push(2);
	stack.Push(1);
	stack.Push(5);
	stack.Push(10);
	stack.Output();

	stack.Pop();
	stack.Pop();
	stack.Pop();
	stack.Output();

	stack.Push(7);
	stack.Push(9);
	stack.Pop();
	stack.Output();

	return 0;
}


二叉查找树


二叉查找树(Binary Search Tree):

二叉查找树是一种特殊的二叉树。树中的每一个节点都父节点,左子节点,右子节点。左子节点小于等于该节点,右子节点大于等于该节点。

二叉查找树包含Search, Minimum, Maximum, Predecessor(前趋), Successor(后续), Insert, Delete等操作。这些操作的时间复杂度均为$$O(h)$$,其中h为树的高度。

二叉查找树实现代码(部分功能):

// BinarySearchTree.h
#pragma once
#include 

using namespace std;

template  class BinarySearchTree;

// 树的节点
template 
class TreeNode
{
	friend BinarySearchTree;
public:
	TreeNode(){data = 0; parent = 0; left = 0; right = 0;};
	TreeNode(T value) {data = value; parent = 0; left = 0; right = 0;}
private:
	T data;	
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;	
};

// 二叉查找树
template 
class BinarySearchTree
{
public:
	BinarySearchTree(void) {root = 0;}
	BinarySearchTree(T* dataArray, int count)	// 使用数组构造二叉查找树
	~BinarySearchTree(void) { }

	void InOrderTreeWalk();
	void Insert(T value);
	void Delete(T value);
	int MaxValue();	// 函数返回值:0-找到最大值 -1-未找到最大值(空树)
	int MinValue();	// 函数返回值:0-找到最小值 -1-未找到最小值(空树)
	int Successor(T value);	// 返回值为0/-1,表示是否找到
	int Predecessor(T value); // 返回值为0/-1,表示是否找到

private:
	void InOrderTreeWalk(TreeNode *node);			// 按顺序输出树中的所有数据
	TreeNode* Search(T target, TreeNode *node);	// 在树中查找给定的某个关键字对应的节点
	TreeNode* Search(T target);
	TreeNode* Minimum(TreeNode *node);			// 查询树中关键字最小的节点	
	TreeNode* Maximum(TreeNode *node);			// 查找树中关键字最大的节点
	TreeNode* Successor(TreeNode *node);			// 返回指定节点的后继节点
	TreeNode* Predecessor(TreeNode *node);		// 返回指定节点的前趋节点
	void Insert(TreeNode *node);						// 插入新节点
	TreeNode* Delete(TreeNode *node);				// 删除指定节点

private:
	TreeNode *root;
};

template 
BinarySearchTree::BinarySearchTree(T* dataArray, int count)
{
	root = 0;
	for (int i=0; i<count; ++i)
	{
		Insert(dataArray[i]);
	}
		
}

template 
void BinarySearchTree::InOrderTreeWalk()
{
	InOrderTreeWalk(root);
	cout << endl;
}

template 
void BinarySearchTree::Insert(T value)
{
	TreeNode* newNode = new TreeNode(value);
	Insert(newNode);
}

template 
void BinarySearchTree::Delete(T value)
{
	TreeNode* delNode = Search(value);
	if (delNode != 0)
		Delete(delNode);
}

template 
int BinarySearchTree::MaxValue()
{
	if (root == 0)
	{
		cout << "The tree is empty." << endl;
		return -1;
	}

	cout << "The max value is " << Maximum(root)->data << endl; // 输出最大值

	return 0;
}

template 
int BinarySearchTree::MinValue()
{
	if (root == 0)
	{
		cout << "The tree is empty." << endl;
		return -1;
	}

	cout << "The min value is " << Minimum(root)->data << endl; // 输出最大值

	return 0;
}

template 
int BinarySearchTree::Successor(T value)
{
	TreeNode* node = Search(value);
	TreeNode* successor = 0;

	if (node == 0)	// 输入value在树中不存在
	{
		cout << value << " is not exit in tree." << endl;
		return -1;
	}

	successor = Successor(node);
	if (successor == 0)
	{
		cout << "There is no successor of " << value << " in the tree." << endl;
		return -1;
	}
	else
		cout << "The successor of "<< value << " is " << successor->data << endl;

	return 0;
}

template 
int BinarySearchTree::Predecessor(T value)
{
	TreeNode* node = Search(value);
	TreeNode* predecessor = 0;

	if (node==0)
	{
		cout << value <<" is not exit in the tree." << endl;
		return -1;
	}

	predecessor = Predecessor(node);
	if (predecessor == 0)
	{
		cout << "There is no predecessor of " << value << " in the tree." << endl;
		return -1;
	}
	else
		cout << "The predecessor of " << value << " is " << predecessor->data << endl;

	return 0;
}


template 
void BinarySearchTree::InOrderTreeWalk(TreeNode *node)
{
	if (node == 0)
		return;
	else 
	{
		InOrderTreeWalk(node->left);
		cout << node->data << " ";
		InOrderTreeWalk(node->right);
	}
}


template 
TreeNode* BinarySearchTree::Search(T target)
{
	return Search(target, root);
}

template 
TreeNode* BinarySearchTree::Search(T target, TreeNode *node)
{
	if (node == 0 || node->data == target)
		return node;

	if (target < node->data)
		return Search(target, node->left);
	else
		return Search(target, node->right);
}

template 
TreeNode* BinarySearchTree::Minimum(TreeNode *node)
{
	while (node!=0 && node->left!=0)
	{
		node = node->left;
	}

	return node;
}

template 
TreeNode* BinarySearchTree::Maximum(TreeNode *node)
{
	while (node!=0 && node->right!=0)
	{
		node = node->right;
	}

	return node;
}

template 
TreeNode* BinarySearchTree::Successor(TreeNode *node)
{
	if (node->right != 0)
		return Minimum(node->right);

	while (node->parent!=0 && node == node->parent->right)	// parent.data < node.data
	{
		node = node->parent;
	}

	return node->parent;
}

template 
TreeNode* BinarySearchTree::Predecessor(TreeNode *node)
{
	if (node->left != 0)
		return Maximum(node->left);

	while (node->parent!=0 && node==node->parent->left) // parent.data > node.data
	{
		node = node->parent;
	}

	return node->parent;
}


template 
void BinarySearchTree::Insert(TreeNode *node)
{
	TreeNode *parentNode = 0;
	TreeNode *currentNode = root;

	while (currentNode != 0)	// 确定node的父节点(即插入位置)
	{
		parentNode = currentNode;
		if (node->data < currentNode->data)
			currentNode = currentNode->left;
		else
			currentNode = currentNode->right;
	}

	node->parent = parentNode;

	if (parentNode == 0)	// 空树
		root = node;
	else
	{
		if (node->data < parentNode->data)	// 确定node为父节点的左子结点还是右子节点
			parentNode->left = node;
		else
			parentNode->right = node;
	}
}

template 
TreeNode* BinarySearchTree::Delete(TreeNode *node)
{
	// 确定需要删除的节点的位置
	TreeNode* delNode;
	if (node->left==0 || node->right==0)
		delNode = node;
	else
		delNode = Successor(node);


	// 
	TreeNode* nonNullChildNode;
	if (delNode->left != 0)
		nonNullChildNode = delNode->left;
	else
		nonNullChildNode = delNode->right;

	if (nonNullChildNode != 0)
		nonNullChildNode->parent = delNode->parent;

	if (delNode->parent == 0)
		root = nonNullChildNode;
	else if (delNode == delNode->parent->left)
		delNode->parent->left = nonNullChildNode;
	else
		delNode->parent->right = nonNullChildNode;

	if (delNode != node)
		node->data = delNode->data;

	return delNode;

}


测试程序:

// main.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "BinarySearchTree.h"

int _tmain(int argc, _TCHAR* argv[])
{
	int data[] = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};

// 	BinarySearchTree bst;
// 	for (int i=0; i<sizeof(data)/sizeof(int); ++i)
// 	{
// 		bst.Insert(data[i]);
// 	}

	BinarySearchTree bst(data, sizeof(data)/sizeof(int));
	
	cout << sizeof(data) << endl;
	bst.InOrderTreeWalk();
	bst.MaxValue();
	bst.MinValue();
	bst.Delete(6);
	bst.InOrderTreeWalk();
	bst.Successor(20);
	bst.Predecessor(2);
	bst.Predecessor(13);

	return 0;
}


随机构造的二叉查找树:

使用随机方法由输入序列构造二叉查找树,它通过按随机的顺序,将序列中各元素插入一颗初始为空的树。输入元素的各种排列是等概率的。

随机构造的二叉查找树的期望高度为:$$O(\lg{n})$$。

对上述程序中的部分代码进行修改即可使用随机方法构造二叉查找树,修改、添加的代码如下:

#include 
#include 

template 
class BinarySearchTree
{
public:
	BinarySearchTree(T* dataArray, int count);	// 使用数组构造二叉查找树(随机构造版本)

private:
	void RandomizedInsert(T* dataArray, int start, int end);	// 随机插入算法
};

template 
BinarySearchTree::BinarySearchTree(T* dataArray, int count)
{
	root = 0;
	srand(time(0));	// 初始化随机数
	RandomizedInsert(dataArray, 0, count-1);
		
}

template 
void BinarySearchTree::RandomizedInsert(T* dataArray, int start, int end)
{
	if (start > end)
		return;

	if (start == end)
	{
		Insert(dataArray[start]);
		return;
	}

	int randPos = start + (double)rand() / RAND_MAX * (end-start);	// 随机选择插入元素
	Insert(dataArray[randPos]);
	RandomizedInsert(dataArray, start, randPos-1);
	RandomizedInsert(dataArray, randPos+1, end);
}

使用模板类为什么出现“unresolved external symbol”?

在使用模板类时,如果将模板类的声明和实现分别放在.H和.CPP文件中的话,在使用该模板类时会遇到连接错误:“Wunresolved external symbol”。

原因如下:模板类、模板函数直到其被使用时才会实例化,当一个模板类被使用时,编译器需要其成员函数的完整代码才可以建立指定类型的函数版本。然而,当函数实现在额外的.CPP文件中时,编译器无法获得函数的完整代码,无法实例化指定类型的函数。

解决方法:

1) 将模板类的声明和实现全部放在.h文件中(建议采用此方式)

2) 将所有模板类的成员函数声明为内嵌函数(inline)

3) 在模板类的成员函数前添加export(部分编译器不支持)

参考资料:stackoverflow

派生类的构造与析构


(1) 函数执行顺序

派生类构造时:首先调用基类的构造函数,然后调用派生类自身的构造函数。

派生类析构时:首先调用派生类自身的析构函数,然后调用各基类的构造函数。

#include 

class A
{
public:
	A(void)
	{
		cout << "base: A constructor" << endl;
	};

	~A(void)
	{
		cout << "base: A destructor" << endl;
	};
};

class B : public A
{
public:
	B(void)
	{
		cout << "B constructor" << endl;
	};

	~B(void)
	{
		cout << "B destructor" << endl;
	};
};

int main(int argc, char* argv[])
{
	//A a;
	B b;
	return 0;
}

程序输出:

base: A constructor
derived: B constructor
derived: B destructor
base: A destructor


(2) 构造函数参数传递

sizeof(指针变量名)及sizeof(数组名)

#include 

int main(int argc, char* argv[])
{
	char a[] = "hello world!";
	char *b;
	char c[3];
	char *d = "world";

	printf("sizeof a=%d\n", sizeof(a));	// 返回数组大小
	printf("sizeof b=%d\n", sizeof(b));	// 返回指针大小
	printf("sizeof c=%d\n", sizeof(c)); // 返回指针大小
	printf("sizeof d=%d\n", sizeof(d)); // 返回数组大小

	return 0;
}

32位机器上程序的输出结果为:

a=13
b=4
c=3
d=4

由此可见,sizeof(数组名)会返回数组的大小(数组元素数量*sizeof(数组类型))(对于字符串数组包含末尾的空),而sizeof(指针变量名)会返回指针变量本身的大小。

两正整数的最大公约数(辗转相除法,Stein算法)


(1)辗转相除法(欧几里得算法)

辗转相除法基本思想:两正整数的最大公约数等于较大的数对较小的数取模的结果与较小的数的最大公约数,即:
$$!gcd(a,b)=gcd(b, a\%b), a\geq{b}$$$

#include 

using namespace std;

// greatest common divisor
// 仅用于计算两正整数的最大公约数
// 辗转相除法: gcd(a,b)=gcd(b, a%b), a>=b
int gcd(int a, int b)
{
	if (a=b
	{
		a = a^b;
		b = a^b;
		a = a^b;
	}

	if (b!=0)
		return gcd(b, a%b);
	else 
		return a;
}

int main(int argc, char *argv[])
{
	cout << gcd(33, 77) << endl;

	return 0;
}


(2) Stein算法

前面的辗转相除法在处理较小的数时具有相当高的效率,但当处理大数时取模运算需用试商法计算,这大大增加了算法的时间复杂度。Stein算很好的解决了辗转相除法的缺陷。

算法思想:

1) 如果a==0,返回b;

2) 如果b==0,返回a;

3) 如果a、b均为偶数,返回2*gcd(a/2, b/2);

4) 如果a为偶数,b为奇数,返回gcd(a/2, b);

5) 如果a为奇数,b为偶数,返回gcd(a, b/2);

6) 如果a、b均为奇数,返回gcd((a-b)/2, b)(a>=b时,可在算法开始出比较a、b,保证a>=b)。

#include 

using namespace std;

// greatest common divisor
// 仅用于计算两正整数的最大公约数
// Stein算法:使用位移和减法代替除法和取模运算,以解决辗转相除法处理的缺点。
int gcd(int a, int b)
{
	if (a=b
	{
		a = a^b;
		b = a^b;
		a = a^b;
	}

	// if (a==0)
	// 	return b;
	
	if (b==0)
		return a;
	
	if ((a&0x1)==0 && (b&0x1)==0)	// a,b均为偶数
		return 2*gcd(a>>1, b>>1);

	if ((a&0x1)==0 && (b&0x1)!=0)	// a为偶数,b为奇数
		return gcd(a>>1, b);

	if ((a&0x1)!=0 && (b&0x1)==0)	// a为奇数,b为偶数
		return gcd(a, b>>1);

	if ((a&0x1)!=0 && (b&0x1)!=0)	// a,b均为奇数
		return gcd((a-b)>>1, b);

}

int main(int argc, char *argv[])
{
	cout << gcd(33, 77) << endl;

	return 0;
}

不使用临时变量交换两个变量的值

使用异或操作可以在不使用临时变量的情况下交换两变量的值。

异或操作符:^

对于位操作:0^0=0, 1 ^ 1 = 0, 0 ^ 1 = 1 ^ 0 = 1。

对于一个变量a:a ^ a = 0; a ^ 0 = a。

#include 

void swap(int &a, int &b)
{
	a = a ^ b;	// a' = a ^ b
	b = a ^ b;	// b' = a' ^ b = (a ^ b) ^ b = a ^ (b ^ b) = a ^ 0 = a
	a = a ^ b;	// a = a' ^ b' = (a ^ b) ^ a = (a ^ a) ^ b = 0 ^ b = b;
}

int main(int argc, char *argv[])
{
	int a = 5, b = 3;

	printf("a = %d\n", a);
	printf("b = %d\n", b);

	swap(a, b);

	printf("a = %d\n", a);
	printf("b = %d\n", b);

	return 0;
}

顺序统计学:如寻找序列中的第i小的元素

(1) 寻找序列中第i小的元素

基本思想(递归划分):

1) 使用快速排序中使用的方法对序列进行划分(最好使用随机版本),并返回划分位置(划分使得划分点左侧元素的值小于等于x,右侧的元素的值大于等于x)。

2) 若划分位置==i,则返回划分位置处的值;划分位置i,从划分位置右侧继续划分。

3) 重复上述过程,直到划分位置等于i。

期望时间复杂度:$$\Theta(n)$$。

最差时间复杂度:$$\Theta(n^2)$$。