算法之美_源代码发布（9）

本文辑录了《算法之美——隐匿在数据结构背后的语言》（电子工业出版社2016年出版）一书第10章前半部分之代码（P321~P357）。全文目录、“45个算法”目录、“22个经典问题目录”，以及有奖捉虫活动详情请见如下链接：http://blog.csdn.net/baimafujinji/article/details/50484348

附录中的经典笔试、面试问题参考答案请见：

http://blog.csdn.net/baimafujinji/article/details/50484683

In general， 我不太喜欢翻开一本书（技术书），里面密密麻麻的全部都是代码。所以我也希望能够在我的书中留下更多空间去讨论原理。当然，代码也很重要，所有的一切原理最终都要落实到代码上。为此我习惯于在博客中上传代码，而非是把他们全部罗列到书中去挤占篇幅。

如果你是该书的读者，强烈建议你加入算法学习群（495573865），内有更多资源等你，而你在读书中遇到的疑问也将得到我第一时间的解答。更多关注本博客，我将陆续发布该书全部源代码至本博客。

P327： 向量集合的声明部分

VecSet.h文件

#ifndef VECSET_H
#define VECSET_H
#include <iostream>
#include <assert.h>
using namespace std;

const int DefaultSize = 100;

class VecSet
{
		int* contain;
		int size;
	public:

	VecSet(int MaxSize = DefaultSize);
	~VecSet();
	
	void Add(int add);
	void Del(int del);
	void MakeEmpty();
	int GetSize(){return size;}
	bool IsMember(const int x);
	VecSet& operator+(VecSet& another);
	VecSet& operator-(VecSet& another);
	VecSet& operator*(VecSet& another);
	VecSet& operator=(VecSet& another);
	bool operator==(VecSet& another);
	friend ostream& operator<<(ostream& stream,VecSet& set);
};

#endif

P329： 向量集合的实现部分

VecSet.cpp文件

#include "VecSet.h"

VecSet::~VecSet()
{
	if(contain != NULL)
		delete [] contain;
}

VecSet::VecSet(int MaxSize):size(MaxSize){
	assert(MaxSize>0);
	contain = new int[size];
	assert(contain != NULL); 
    MakeEmpty();
}

void VecSet::Add(int add){
	assert(add>=0 && add<size);
	contain[add]=1;
}

void VecSet::Del(int del){
	assert(del>=0 && del<size);
	contain[del]=0;
}

void VecSet::MakeEmpty(){
	for(int i=0;i<size;i++){
		contain[i]=0;
	}
}

bool VecSet::IsMember(const int x)
{
	assert(x >= 0 && x < size);
	return contain[x] != 0;
}

VecSet& VecSet::operator+(VecSet& another){
	assert(this->GetSize() == another.GetSize());
	VecSet* temp = new VecSet(this->GetSize()); 
	for(int i=0;i<size;i++){
		(*temp).contain[i] = contain[i]||another.contain[i];
	}
	return *temp;
}

VecSet& VecSet::operator-(VecSet& another){
	assert(this->GetSize() == another.GetSize());
	VecSet* temp = new VecSet(this->GetSize()); 
	for(int i=0;i<size;i++){
		(*temp).contain[i] = contain[i]&&(!another.contain[i]);
	}
	return *temp;
}

VecSet& VecSet::operator*(VecSet& another){
	assert(this->GetSize() == another.GetSize());
	VecSet* temp = new VecSet(this->GetSize()); 
	for(int i=0;i<size;i++){
		(*temp).contain[i] = contain[i]&&another.contain[i];
	}
	return *temp;
}

VecSet& VecSet::operator=(VecSet& another){
	assert(this->GetSize() == another.GetSize());
	for(int i=0;i<size;i++){
		contain[i] = another.contain[i];
	}
	return 
		*this;
}

bool VecSet::operator == (VecSet& another){
	assert(this->GetSize() == another.GetSize());
	for(int i=0;i<size;i++){
		if(contain[i] != another.contain[i]){
			return false;
		}
	}
	return true;
}

ostream& operator<<(ostream& stream,VecSet& set){
	for(int i=0;i<set.GetSize();i++){
		if(set.IsMember(i)) cout<<i<<" ";
	}
	cout<<endl;
	return
		stream;
}

向量集合测试程序

#include <iostream>
#include "VecSet.h"

using namespace std;

int main(int argc, char** argv) {
	
	VecSet a(8);
	VecSet b(8);
	VecSet c(8);
	
	for(int i=1; i<=5; i++){
		a.Add(i);
	}
	
	b.Add(2);
	b.Add(3);
	b.Add(4);
	b.Add(5);
	b.Add(7);		
	b.Del(4);
 
	cout<< a * b;
	cout<< a + b;
	cout<< a - b;
	c = b;
	cout<<c;
	cout<<(c==b);
	
	return 0;
}

P332：链表集合的实现

ListSet.h文件

#ifndef LISTSET_H
#define LISTSET_H

#include <iostream>

using namespace std;

template <class T> class ListSet;

template <class T>
class ListSetNode
{
	friend class ListSet<T>;
	T data;
	ListSetNode<T>* link;
public:
	ListSetNode() :link(NULL){}
	ListSetNode(T value) :link(NULL), data(value){}
};

template <class T>
class ListSet
{
	ListSetNode<T>* head;
	ListSetNode<T>* tail;

public:
	ListSet();
	~ListSet();
	ListSet(ListSet & lset);

	void Add(T add);
	void Del(T del);
	bool IsEmpty();
	void MakeEmpty();
	ListSet<T>& operator+(ListSet<T>& another);
	ListSet<T>& operator-(ListSet<T>& another);
	ListSet<T>& operator*(ListSet<T>& another);
	ListSet<T>& operator=(ListSet<T>& another);
	bool operator==(ListSet<T>& another);
	void Output();
	ListSetNode<T>* GetHead(){ return head; }
};

template <class T>
ListSet<T>::ListSet()
{
	this->head = new ListSetNode<T>();
	this->tail = this->head;
}

template <class T>
ListSet<T>::~ListSet()
{
	MakeEmpty();
	delete head;
}

template <class T>
void ListSet<T>::Add(T value)
{
	ListSetNode<T>* add = new ListSetNode<T>(value);
	ListSetNode<T>* preCurrent = head;				//记录当前结点
	ListSetNode<T>* current = preCurrent->link;		//记录当前结点的前驱结点
	while (current != NULL && current->data < value)		//寻找插入位置
	{
		preCurrent = current;
		current = preCurrent->link;
	}
	if (head == tail && current == NULL)				//向空链表中插入结点
	{
		head->link = add;
		tail = add;
	}
	if (head != tail && current == NULL)				//向链表尾插入值add
	{
		preCurrent->link = add;
		add->link = NULL;
		tail = add;
	}
	if (current != NULL && current->data == value)		//链表中已存在值add
	{
		return;
	}
	if (current != NULL && current->data > value)
	{
		preCurrent->link = add;
		add->link = current;
	}
}

template <class T>
void ListSet<T>::Del(T del)
{
	ListSetNode<T>* preCurrent = head;
	ListSetNode<T>* current = preCurrent->link;
	while (current != NULL && current->data != del)				//寻找删除结点
	{
		preCurrent = current;
		current = preCurrent->link;
	}
	if (current != NULL)
	{
		preCurrent->link = current->link;
		if (current->link == NULL){ tail = preCurrent; }		//更新表尾指针
		delete current;
	}
}

template <class T>
bool ListSet<T>::IsEmpty()
{
	return head == tail;								//判断集合是否为空
}

template <class T>
void ListSet<T>::MakeEmpty()
{
	ListSetNode<T>* current = head->link;
	ListSetNode<T>* del = NULL;
	while (head->link != NULL)					//循环删除集合中的元素
	{
		head->link = current->link;
		del = current;
		current = current->link;
		delete del;								//调用delete释放当前结点
	}
	tail = head;
}

template <class T>
ListSet<T>& ListSet<T>::operator=(ListSet<T>& another)
{
	MakeEmpty();
	ListSetNode<T>* current = another.head->link;
	while (current != NULL)
	{
		Add(current->data);
		current = current->link;
	}
	return *this;
}

template <class T>
ListSet<T>::ListSet(ListSet<T>& lset)
{
	this->head = new ListSetNode<T>();
	this->tail = this->head;

	ListSetNode<T>* current = lset.head->link;
	while (current != NULL)
	{
		Add(current->data);
		current = current->link;
	}

}

template <class T>
ListSet<T>& ListSet<T>::operator+(ListSet<T>& another)
{
	ListSet<T>* tmpSet = new ListSet(another);
	ListSetNode<T>* current = this->head->link;
	while (current != NULL)
	{
		tmpSet->Add(current->data);
		current = current->link;
	}

	return *tmpSet;							//返回当前集合的引用
}

template <class T>
ListSet<T>& ListSet<T>::operator-(ListSet<T>& another)
{
	ListSet<T>* tmpSet = new ListSet(*this);
	ListSetNode<T>* current = another.head->link;
	while (current != NULL)
	{
		tmpSet->Del(current->data);
		current = current->link;
	}
	return *tmpSet;
}

template <class T>
ListSet<T>& ListSet<T>::operator*(ListSet<T>& another)
{
	ListSet<T>* tmpSet = new ListSet(*this);
	*tmpSet = *this - another;
	*tmpSet = *this - *tmpSet;
	return *tmpSet;
}

template <class T>
bool ListSet<T>::operator==(ListSet<T>& another)
{
	ListSetNode<T>* current1 = head->link;
	ListSetNode<T>* current2 = another.head->link;
	while (current1 != NULL)
	{
		if (current2 == NULL){ return false; }
		if (current1->data != current2->data){ return false; }
		current1 = current1->link;
		current2 = current2->link;
	}
	if (current2 != NULL){ return false; }
	return true;
}

template <class T>
void ListSet<T>::Output()
{
	ListSetNode<T>* current = this->GetHead()->link;
	while(current != NULL){
		cout << current->data << " ";
		current = current->link;
	}
	cout << endl;
}

#endif

基于链表实现的集合之测试程序

#include "stdafx.h"
#include "ListSet.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	ListSet<int> listSetA;
	ListSet<int> listSetB;
	ListSet<int> listSetC;
		
	for (int i = 1; i <= 5; i++)
	{
		listSetA.Add(i);
	}
//	cout << listSetA.IsEmpty()<<endl;
//	listSetA.MakeEmpty();
//	cout << listSetA.IsEmpty()<<endl;
//	listSetC = listSetA;
//	listSetC.Output();

	ListSet<int> listSetD(listSetA);
	cout << (listSetA == listSetD) << endl;

	listSetB.Add(2);
	listSetB.Add(3);
	listSetB.Add(5);
	listSetB.Add(7);
	listSetB.Add(8);
	listSetB.Add(5);
	listSetB.Del(8);

	listSetC = listSetA + listSetB;
	listSetC.Output();

	listSetC = listSetA - listSetB;
	listSetC.Output();

	listSetC = listSetA * listSetB;
	listSetC.Output();

	system("PAUSE");
	return 0;
}

P336：字典

Item.h文件

#ifndef _ITEM_H_
#define _ITEM_H_

#include <iostream>
#include <string.h>

using namespace std;

class Item {

	string english;
	string chinese;
	Item*  link;

public:

	Item() : link(NULL){}
	Item(string en, string ch) : link(NULL), english(en),chinese(ch) {}
	~Item(){};
	void SetLink(Item* next);
	Item*  GetLink();
	string GetIndex();
	string GetValue();
};

void Item::SetLink(Item* next){
	link = next;
}

Item* Item::GetLink(){
	return link;
}

string Item::GetIndex(){//返回结点中的数据
	return english;
}

string Item::GetValue(){//返回结点中的数据
	return chinese;
}

#endif

#ifndef _DICTIONARY_H_
#define _DICTIONARY_H_

#include "Item.h"

class Dictionary{

	Item* head;
	Item* tail;

public:
	Dictionary();
	virtual ~Dictionary();

	bool Add(string en, string ch);
	bool Del(string en);
	string Search(string en);
	int GetCount();
	void RemoveAll();
};

Dictionary::Dictionary()
{
	head = new Item();
	tail = head;
	tail->SetLink(NULL);
}

Dictionary::~Dictionary()
{
	RemoveAll();
	delete head;
}

bool Dictionary ::Add(string en, string ch){
	Item* add = new Item(en, ch);
	tail->SetLink(add);
	tail = tail->GetLink();
	tail->SetLink(NULL);
	if (tail != NULL)
		return true;
	else
		return false;
}

bool Dictionary::Del(string en){

	Item* cur, *curPre;
	cur = head;
	curPre = cur->GetLink();

	while (cur != NULL){
		if (curPre->GetIndex() == en)
			break;
		cur = cur->GetLink();
		if (cur !=NULL)
			curPre = curPre->GetLink();
	}

	if (tail == curPre)
		tail = cur;
	cur->SetLink(curPre->GetLink());  //将被删除结点从链表中摘下
	delete curPre;

	if (curPre != NULL)
		return true;
	else
		return false;
}

string  Dictionary::Search(string en) {

	Item* cur;
	cur = head->GetLink();
	while (cur != NULL){
		if (en == cur->GetIndex())
			break;
		cur = cur->GetLink();
	}
	if (cur != NULL)
		return cur->GetValue(); //返回结点中的 value
	else
		return "Cannot find";
}

int Dictionary::GetCount() {
	int count = 0;
	Item* current = head->GetLink();
	while (current != NULL) {
		++count;
		current = current->GetLink();  //顺序移动cur 
	}
	return count;
}

void Dictionary::RemoveAll() { //删除所有结点
	Item* cur;
	while (head->GetLink() != NULL) {
		cur = head->GetLink();
		head->SetLink(cur->GetLink());
		delete cur;
	}
	tail = head; //置表尾为表头处
}

#endif

字典测试程序

#include "stdafx.h"
#include <iostream>
#include "Dictionary.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	Dictionary dic;

	dic.Add("box", "盒子");
	dic.Add("apple", "苹果");
	dic.Add("tree", "树");
	dic.Add("good", "好的");
	dic.Add("swim", "游泳");
	dic.Add("interesting", "有趣的");

	cout << dic.Search("good").c_str() << endl;
	cout << dic.Search("interesting").c_str() << endl;

	dic.Del("box");
	dic.Del("interesting");

	cout << dic.Search("box").c_str() << endl;
	cout << dic.Search("interesting").c_str() << endl;
	cout << dic.Search("apple").c_str() << endl;

	system("PAUSE");
	return 0;
}

P343

template <class T>
class Item{
	int key;
	T data;
public:
	Item():key(-1){}
	Item(int keyInput,T value):key(keyInput),data(value){assert(key>=0);}
	int GetKey(){return key;}
	T GetData(){return data;}
	friend ostream& operator<<(ostream& stream,Item<T>& item);
};

template <class T>
class OrderSearch{
	Item<T>* contain;
	int size;
public:
	OrderSearch():contain(NULL),size(0){}
	OrderSearch(int maxSize);
	void Add(Item<T> add);
	int GetSize(){return size;}
	Item<T>* GetContain(){return contain;}
	Item<T>& Search(int k);
	friend ostream& operator<<(ostream& stream,OrderSearch<T>& set);
};

P344

template <class T>
ostream& operator<<(ostream& stream,Item<T>& item){
	cout<<"key:"<<item.GetKey()<<"\t"<<"data:"<<item.GetData()<<endl;
	return stream;
}

P345

template <class T>
OrderSearch<T>::OrderSearch(int maxSize)
{
	contain = new Item<T>[maxSize];					//建立数组，存放二元组
	size = maxSize;									//记录数组大小
	for(int i=0;i<maxSize;i++)						//初始化字典
	{
		Item<T> ini;
		contain[i] = ini;
	}
}

template <class T>
void OrderSearch<T>::Add(Item<T> add)
{
	assert(add.GetKey()>=0 && add.GetKey()<size);		//判断key的合法性
		contain[add.GetKey()] = add;					//添加二元组
}

template <class T>
Item<T>& OrderSearch<T>::Search(int k)
{
	assert(k>=0 && k<size);								//判断key的合法性
	return contain[k];									//返回二元组
}

template <class T>
ostream& operator<<(ostream& stream,OrderSearch<T>& set)
{
	for(int i=0;i<set.GetSize();i++)
	{
		if(set.GetContain()[i].GetKey() != -1)
		{
			cout<<"key:"<<set.GetContain()[i].GetKey()<<"\t";
			cout<<"data:"<<set.GetContain()[i].GetData()<<endl;
		}
	}
	return stream;
}

P346

template <class T>
int BinarySearch(List<T>& dic, T& item) {

	int lowKey = 0;
	int highKey = dic.GetCount() - 1;
	int midKey;

	while (lowKey <= highKey)
	{
		midKey = (lowKey + highKey) / 2;				//寻找中间结点
		if (dic.GetAt(midKey) < item)
		{
			lowKey = midKey + 1;						//在右半集合中搜索
   	    }
		else if (dic.GetAt(midKey) > item)
		{
			highKey = midKey - 1;						//在左半集合中搜索
		}
		else 
			return midKey;
	}
	return -1;
}

P351-1：  BKDR散列

连同测试程序一并给出。你会发现这个算法在处理C语言关键字时可以获得非常小的冲突率。例如当我们去HASHSIZE为101时，就可以做到完全没有冲突。

#include <iostream>
#include <string>
#include <iomanip>
#include <stdint.h>

using namespace std;

#define HASHSIZE 101


string keywords[] = {
  "auto",   "break",  "case",     "char",   "const",    "continue", "default",  "do",
  "double", "else",   "enum",     "extern", "float",    "for",      "goto",     "if",
  "int",    "long",   "register", "return", "short",    "signed",   "sizeof",   "static",
  "struct", "switch", "typedef",  "union",  "unsigned", "void",     "volatile", "while"
};

unsigned long BKDRHash(const string& str)  
{
	unsigned long seed = 31;
	unsigned long hashval = 0; 
    
	for(int i = 0; i < str.length(); i++)
		hashval = hashval * seed + str[i];
	return hashval % HASHSIZE;  
}


int main(int argc, char** argv) {

  int size, pos;
  int count[HASHSIZE];
  
  for(int i = 0; i < HASHSIZE; i++)
     count[i] = 0;

  size = sizeof(keywords) / sizeof(keywords[0]);
  for(int i = 0;i < size; i++)
    count[BKDRHash(keywords[i])]++;

  for(int i = 0; i < size; i++) {
    pos = BKDRHash(keywords[i]);
    cout<<setw(8)<<keywords[i]<<setw(5)<<pos<<setw(5)<<count[pos]<<endl;
  }

	return 0;
}

P351-2：  RS散列（连同测试程序一并给出）

#include <iostream>
#include <string>
#include <iomanip>
#include <stdint.h>

using namespace std;

#define HASHSIZE 41


string keywords[] = {
  "auto",   "break",  "case",     "char",   "const",    "continue", "default",  "do",
  "double", "else",   "enum",     "extern", "float",    "for",      "goto",     "if",
  "int",    "long",   "register", "return", "short",    "signed",   "sizeof",   "static",
  "struct", "switch", "typedef",  "union",  "unsigned", "void",     "volatile", "while"
};

unsigned long RSHash(const string& str)  
{
	unsigned long a = 31415, b = 27183;  
	unsigned long hashval = 0;  
	for(int i = 0; i < str.length(); i++)  
	{  
		hashval = (hashval * a + str[i])%HASHSIZE;  
		a = a * b % (HASHSIZE-1);  
	}  
	return hashval;  
}


int main(int argc, char** argv) {

	int size, pos;
	int count[HASHSIZE];
  
	for(int i = 0; i < HASHSIZE; i++)
		count[i] = 0;

	size = sizeof(keywords) / sizeof(keywords[0]);
	size = 32;
	for(int i = 0;i < size; i++)
		count[RSHash(keywords[i])]++;

	for(int i = 0; i < size; i++) {
		pos = RSHash(keywords[i]);
		cout<<setw(8)<<keywords[i]<<setw(5)<<pos<<setw(5)<<count[pos]<<endl;
	}

	return 0;
}

P352：  FNV散列（连同测试程序一并给出）

#include <iostream>
#include <string>
#include <iomanip>
#include <stdint.h>

using namespace std;

//const long offsetbasis32 = 2166136261;
#define FNV_32_INIT ((uint32_t)0x811c9dc5)
//const long FNVprime32 = 16777619;
#define FNV_32_PRIME ((uint32_t)0x01000193)

unsigned long FNV1a_32_Hash(const string& str)  
{  
	unsigned long hashval = FNV_32_INIT;  
	for(int i = 0; i < str.length(); i++)  
	{  
		hashval = hashval ^ str[i];  
	//	hashval = hashval * FNV_32_PRIME;
	//  上面一句代码等价于下面之位操作 
		hashval += (hashval <<1) + (hashval <<4) 
				+ (hashval <<7) + (hashval <<8) + (hashval <<24);
	
	}
	return hashval;  
}

//const long offsetbasis64 = 14695981039346656037;
//#define FNV_64_INIT ((uint64_t)0x14650FB0739D0383);
#define FNV_64_INIT ((uint64_t)0xcbf29ce484222325ULL);
//const long FNVprime64 = 1099511628211;
#define FNV_64_PRIME ((uint64_t)0x100000001b3ULL)

uint64_t FNV1a_64_Hash(const char* bp, size_t len)  
{  
	uint64_t hval = FNV_64_INIT;  
	const char *be = bp + len;  
	while (bp < be) {  
		hval ^= (uint64_t) *bp++;  
		hval += (hval << 1) + (hval << 4) + (hval << 5) + (hval << 7) + (hval << 8) + (hval << 40);  
	}  
	return hval;  
}

int main(int argc, char** argv) {

	string str = "interesting";
	cout<<hex<<FNV1a_32_Hash(str)<<endl;
	cout<<hex<<FNV1a_64_Hash(str.c_str(), str.length())<<endl;
	
	return 0;
}

内容简介：探秘算法世界，求索数据结构之道；汇集经典问题，畅享编程技法之趣；点拨求职热点，敲开业界名企之门。本书围绕算法与数据结构这个话题，循序渐进、深入浅出地介绍了现代计算机技术中常用的四十余个经典算法，以及回溯法、分治法、贪婪法和动态规划等算法设计思想。在此过程中，本书也系统地讲解了链表（包括单向链表、单向循环链表和双向循环链表）、栈、队列（包括普通队列和优先级队列）、树（包括二叉树、哈夫曼树、堆、红黑树、AVL树和字典树）、图、集合（包括不相交集）与字典等常用数据结构。同时，通过对二十二个经典问题（包括约瑟夫环问题、汉诺塔问题、八皇后问题和骑士周游问题等）的讲解，逐步揭开隐匿在数据结构背后的算法原理，力图帮助读者夯实知识储备，激活思维技巧，并最终冲破阻碍编程能力提升的重重藩篱。辅有完整的C++源代码，并穿插介绍了STL中的各种容器。

网上书店：

China-pub中国互动出版网：http://product.china-pub.com/4911922

当当网：http://product.dangdang.com/23851244.html

亚马逊：http://www.amazon.cn/%E7%AE%97%E6%B3%95%E4%B9%8B%E7%BE%8E-%E9%9A%90%E5%8C%BF%E5%9C%A8%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E8%83%8C%E5%90%8E%E7%9A%84%E5%8E%9F%E7%90%86-%E5%B7%A6%E9%A3%9E/dp/B01AGNUIE8/ref=sr_1_8?ie=UTF8&qid=1453527399&sr=8-8&keywords=%E5%B7%A6%E9%A3%9E

算法之美_源代码发布（9）

原文：http://blog.csdn.net/baimafujinji/article/details/50652798