已知入栈输入序列,求不可能的出栈序列

【数据结构题目】设栈的输入序列是1,2,3,4,则不可能的出栈序列为:

A:1,2,4,3

B:2,1,3,4

C:1,4,3,2

D:4,3,1,2

E:3,2,1,4

解答:D

栈的特点是先入后出(FILO)。

A:1入栈,1出栈,2入栈,2出栈,34入栈,4出栈,3出栈;

B:12入栈,2出栈,1出栈,3入栈,3出栈,4入栈,4出栈;

C:1入栈,1出栈,234入栈,4出栈,3出栈,2出栈;

E:123入栈,3出栈,2出栈,1出栈,4入栈,4出栈。

已知二叉树的中根序列和后根序列,确定树的结构。

已知二叉树的中根序列和后根序列,确定一个树的结构。

比如:已知二叉树的

中根序列:c,b,d,e,a,g,i,h,j,f

后根序列:c,e,d,b,i,j,h,g,f,a

求:二叉树的结构。

具体求解方法:

中序遍历:左根右。

后序遍历:左右根。

1. 由后根序列可知a为整个树的根, (c,b,d,e) 属于其左子树,(g,i,h,j,f)属于其右子树,即有:

2. 由后根序列(c, e, d, b)可知,b为a左子树的根;由中根序列(c, b, d, e)可知,c为b的左子树,(d, e)为b的右子树。由后根序列(I, j, h, g, f)可知,f为a的右子树的根;由中根序列(g, I, h, j, f)可知,(g, i, h, j)为f的左子树,f的右子树为空。即有:

3. 由后跟序列(e, d)可知,d为根;由中根序列(d, e)可知,e为d的右子树,d的左子树为空。由后根序列(i, j, h, g)可知,g为根;有中根序列(g, i, h, j)可知,(i, h, j)为g的左子树,g的右子树为空。即有:

4. 由后根序列(i, j, h)可知,h为根;由中根序列ihj可知,i为h的左子树,j为h的右子树。即有:

 

CGAL使用注意事项:添加编译需要的宏定义

CGAL函数库的源代码中存在很多根据宏定义判断函数实现方式的编译分治,在项目中使用CGAL函数库时,为了防止出现不可预知的编译错误,应该在编译代码前为项目添加预编译宏定义。

以MSVC为例:在项目工程属性(Properties)->Configuration->C/C++->Preprecessor->Preprocessor Definitions中添加如下的宏定义即可。

CGAL_USE_MPFR
CGAL_USE_GMP
CGAL_EIGEN3_ENABLED

 

在windows下编译boost开源库

一、从项目网站下载boost源代码

http://www.boost.org/users/download/

二、编译boost库

1. 生成编译工具集(b2.exe等)

解压源文件代码到指定的boost根目录,并执行该目录下的批处理文件:bootstrap.bat,编译生成b2.exe等文件

2. 编译生成函数库

// vc2009-32位
b2.exe --build-dir="boost_root_dir" --toolset=msvc-9.0 --built-type=complete stage

// vc2009-64位
b2.exe --build-dir="boost_root_dir" --toolset=msvc-9.0 --build-type=complete architecture=x86 address-model=64 stage

// vc2010-32位
b2.exe --build-dir="boost_root_dir" --toolset=msvc-10.0 --built-type=complete stage

// vc2010-64位
b2.exe --build-dir="boost_root_dir" --toolset=msvc-10.0 --build-type=complete architecture=x86 address-model=64 stage

// vc2013-32位
b2.exe --build-dir="boost_root_dir" --toolset=msvc-12.0 --built-type=complete stage

// vc2013-64位
b2.exe --build-dir="boost_root_dir" --toolset=msvc-13.0 --build-type=complete architecture=x86 address-model=64 stage

// 其中--build-dir="boost_root_dir"用于指定boost解压后的目录,可视情况决定是否省略。

 注意事项:编译结果保存在stage\lib目录内,不同配置的编译结果会相互覆盖,在编译完成后最好及时将结果保存到其他位置

在VS中使用CUDA时的一些注意事项

1. 尽量不要将__host__函数与(__device__以及__globle__)函数放在同一个文件中,否则调试时会出现当前statement指针错行的问题。(bug?)

2. 如何解决VS中无法使用NSight同时对GPU和CPU代码设置断点进行调试的问题。

指针与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);
}