首页 > 编程语言 > 详细

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

时间：2016-01-27 14:40:01      阅读：340      评论：0      收藏：0      [点我收藏+]

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

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

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

技术分享


内容简介：探秘算法世界，求索数据结构之道；汇集经典问题，畅享编程技法之趣；点拨求职热点，敲开业界名企之门。本书围绕算法与数据结构这个话题，循序渐进、深入浅出地介绍了现代计算机技术中常用的四十余个经典算法，以及回溯法、分治法、贪婪法和动态规划等算法设计思想。在此过程中，本书也系统地讲解了链表（包括单向链表、单向循环链表和双向循环链表）、栈、队列（包括普通队列和优先级队列）、树（包括二叉树、哈夫曼树、堆、红黑树、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


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


P118：游标类的定义


template <class T> class Iterator{

	ListNode<T>* cur;

	public:
		Iterator():cur(NULL){};
		Iterator(ListNode<T>* point):cur(point){}

		friend T operator ++(Iterator& it);		//前缀
		friend T operator ++ (Iterator& it,int);	//后缀

		friend bool operator == (Iterator& it,ListNode<T>* point);
		friend bool operator !=  (Iterator& it,ListNode<T>* point);
		friend ostream& operator<< (ostream& stream,Iterator& it);

		void operator= (ListNode<T>* point);
		ListNode<T>*& GetCur();
};

P119：游标类的实现


//前缀运算符，先返回cur所指结点中的数据
//再使cur向后移动
template <class T> 
T operator++(Iterator<T>& it){ 
it.GetCur() = it.GetCur()->GetLink();
T data;
data = it.GetCur()->GetData();
	return data;
}

//后缀运算符，先使cur向后移动一个结点
//再返回cur所指结点中的数据
template <class T> 
T operator++(Iterator<T>& it,int){
	T data;
	data = it.GetCur()->GetData();
	it.GetCur() = it.GetCur()->GetLink();
	return data;
}

//判断cur是否等于point
template <class T>
bool operator==(Iterator<T>& it,ListNode<T>* point){
	return it.GetCur() == point;
}

//判断cur是否不等于point
template <class T>
bool operator!=(Iterator<T>& it,ListNode<T>* point){
	return it.GetCur() != point;
}

//输出cur所指结点中的数据
template <class T> 
ostream& operator<<(ostream& stream,Iterator<T>& it){
	stream<<it.GetCur()->GetData();
	return stream;
}

//把point的值赋给cur
template <class T>
void Iterator<T>::operator = (ListNode<T>* point){
	cur = point;
}

//返回cur
template <class T>
ListNode<T>*& Iterator<T>::GetCur(){
	return cur;
}

P120：双向链表游标类的定义


template <class T> class Iterator{

	DouListNode<T>* cur;

	public:
		Iterator():cur(NULL){};
		Iterator(DouListNode<T>* point):cur(point){}
		friend T operator++(Iterator& it);			//前缀
		friend T operator++(Iterator& it,int);		//后缀
		friend T operator--(Iterator& it);			//前缀
		friend T operator--(Iterator& it,int);		//后缀
		friend bool operator==(Iterator& it,DouListNode<T>* point);
		friend bool operator!=(Iterator& it,DouListNode<T>* point);
		friend ostream& operator<< (ostream& stream,Iterator& it);
		void operator= (DouListNode<T>* point);
		DouListNode<T>*& GetCur();
};



P121：双向链表游标类的实现


template <class T> 
T operator++(Iterator<T>& it){
	it.GetCur() = it.GetCur()->GetLink();
	T data;
	data = it.GetCur()->GetData();
	return data;
}

template <class T> 
T operator++(Iterator<T>& it,int){
	T data;
	data = it.GetCur()->GetData();
	it.GetCur() = it.GetCur()->GetLink();
	return data;
}

template <class T> 
T operator--(Iterator<T>& it){
	it.GetCur() = it.GetCur()->GetPrior();
	T data;
	data = it.GetCur()->GetData();
	return data;
}

template <class T> 
T operator--(Iterator<T>& it,int){
	T data;
	data = it.GetCur()->GetData();
	it.GetCur() = it.GetCur()->GetPrior();
	return data;
}

template <class T> 
bool operator==(Iterator<T>& it,DouListNode<T>* point){
	return it.GetCur() == point;
}

template <class T>
bool operator!=(Iterator<T>& it,DouListNode<T>* point){
	return it.GetCur() != point;
}

template <class T> 
ostream& operator<<(ostream& stream,Iterator<T>& it){
	stream<<it.GetCur()->GetData();
	return stream;
}

template <class T>
void Iterator<T>::operator = (DouListNode<T>* point){
	cur = point;
}

template <class T> 
DouListNode<T>*& Iterator<T>::GetCur(){
	return cur;
}

P122：STL中的list使用示例


#include "stdafx.h"
#include <iostream>
#include <string>
#include <cstdlib>
#include <list>

using namespace std;

int _tmain(int argc, _TCHAR* argv[]) {
	list<int> myList1;
	myList1.push_front(10);
	cout << myList1.size() << endl; //链表长度为 1

	list<string> myList2 (10);
	cout << myList2.size() << endl; //链表长度为 10

	list<double> myList3 (2, 4.6);   //初始值为4.6
	cout << myList3.back() << endl;
	myList3.pop_back();
	cout << myList3.empty() << endl;

	system("PAUSE");
	return 0;
}

P122：STL中的list使用示例2


#include "stdafx.h"
#include <iostream>
#include <string>
#include <cstdlib>
#include <list>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	string str[] = {"Today ","is ","not ","Friday."};
	list<string> eraseThird;
	for(int i = 0; i < 4; i++)
		eraseThird.push_back(str[i]);
	
	// 删除链表中的第3个元素
	list<string>::iterator third = eraseThird.begin();
	++third;
	++third;
	eraseThird.erase(third);

	list<string>::iterator third2 = eraseThird.begin();
	third2 ++;
	third2 ++;
	eraseThird.insert(third2, "not ");


	list<string>::iterator it = eraseThird.begin() ;
	while (it != eraseThird.end()) {
		cout << *it ;
		++it;
	}
	cout<<endl;


	list<int> list1(15, 3);
	list<int> list2(16, 2);

	list<int>::iterator insertMass = list1.begin();
	insertMass++;

	list1.insert(insertMass, list2.begin(), list2.end());
	cout << list1.size() << endl;

	system("PAUSE");
    return 0;
}

P129：顺序栈的实现


template <class T>
class ArrayStack{

	int size;
	int tos; //栈顶索引。
	T* contain;

public:
	ArrayStack():size(0),tos(-1),contain(NULL){}
	ArrayStack(int MaxSize);
	void Push(T& element);
	T& GetTop();
	T& Pop();
	bool IsEmpty();
	void MakeEmpty();
};


template<class T>

ArrayStack<T>::ArrayStack(int MaxSize)

{//构造函数

    size= MaxSize;

    tos =-1; //初始化tos于栈底处。

    contain= new T[size];

}

 

template<class T>

void ArrayStack<T>::Push(T& element)

{//向栈中添加新元素

    assert(tos!= size-1);

    contain[++tos]= element;

}

 

template<class T>

T& ArrayStack<T>::Pop()

{//从栈中删除元素

    assert(tos!=-1);

    returncontain[tos--];

}

 

template<class T>

T& ArrayStack<T>::GetTop()

{//返回栈顶元素

    assert(tos!=-1);

    returncontain[tos];

}

 

template<class T>

void ArrayStack<T>::MakeEmpty()

{//置空栈

    tos =-1;

}

 

template<class T>

bool ArrayStack<T>::IsEmpty()

{//判断栈是否为空。

    returntos==-1;
}



P131：链式栈的实现


#ifndef LINKSTACK_H
#define LINKSTACK_H

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

template <class T>
class LinkStackNode{

	public :
		T data;
		LinkStackNode<T>* link;
		LinkStackNode(T& value):link(NULL),data(value){}
};

template <class T>
class LinkStack{

		LinkStackNode<T>* tos;

	public :
		LinkStack():tos(NULL){}
		void Push(T& value);
		T& GetTop();
		T Pop();
		bool IsEmpty();
		void MakeEmpty();
};

template<class T>
void LinkStack<T>::Push(T& value){
	LinkStackNode<T>* add = new LinkStackNode<T>(value);
	add->link = tos;
	tos = add;
}

template<class T>
T& LinkStack<T>::GetTop(){
	return tos->data;
}

template<class T>
T LinkStack<T>::Pop(){

	assert(tos!=NULL);
	LinkStackNode<T>* old = tos;
	tos = tos->link;
	T data = old->data;
	delete old;
	return data;
}

template<class T>
bool LinkStack<T>::IsEmpty()
{
	return tos == NULL;
}

template<class T>
void LinkStack<T>::MakeEmpty()
{
	while(!this->IsEmpty()){
		this->Pop();
	}
}

#endif



P132：括号匹配问题


请参见博文——括号匹配问题与经典笔试面试题目解析


（链接地址：http://blog.csdn.net/baimafujinji/article/details/50465482）


P134：停车场模拟问题


car.h文件


#ifndef CAR_H
#define CAR_H

#include <iostream>
#include <string>

using namespace std;

//Declaration of class car. 
//Instances of class car need to store the license plate
//and the number of times the car has been moved while it has been parked in the lot. 
class car {
  
private:
	string license;
	int movedTimes;
public:
	car(string,int);
	string getLicense()const;
	int getMovedTimes()const;
	void move();
	virtual ~car();
    
};

#endif

car.cpp文件



#include "car.h"

using namespace std;

//构造函数
car::car(string license,int):movedTimes(0),license(license){}
//析构函数
car::~car(){}
//返回车辆被移动的次数
int car::getMovedTimes()const
{
	return movedTimes;
}
//返回车辆的代号
string car::getLicense()const
{
	return license;
}
//当车被移动时，属性movedTimes 自加1
void car::move()
{
	movedTimes++;
}


main.cpp文件


#include <string>
#include <STACK>
#include <iostream>
#include <fstream>
#include "car.h"

using namespace std;

#define EXIT_FAILURE 0
#define EXIT_SUCCESS 1

int main(int argc, char *argv[])
{ 
	//The user should specify the data file to use via the command-line. 
	if (argc != 2) {
        cerr << "Usage: " << argv[0] << " data-file\n";
		cerr << "You shoud use this program in the cmd line"<<endl;
        return EXIT_FAILURE;
    }
	//Judge whether the file exists or not
	//Then open the file for reading or writing
	string in_fileName = argv[1];
	string out_fileName = "result.txt";
	ifstream infs(in_fileName.c_str());
	ofstream outfs(out_fileName.c_str());
	if(!infs){
		cerr<<"Can‘t open the file "<<in_fileName<<endl;
		return EXIT_FAILURE;
	}
	if(!outfs){
		cerr<<"Can‘t open the file "<<out_fileName<<endl;
		return EXIT_FAILURE;
	}

	//Declare a stack object to represent the single-aisle parking lot. 
	//This object must be of type stack<car*> 
	//To preserve the order of the other cars, a temporary stack of type pointer to car should be used. 
	stack<car*> parking_lot, tempStack;
	car *pcar;
	string license_plate,action;

	//Unless the file ends, then read it.
	while(!infs.eof())
	{
		infs>>license_plate>>action;
		//For each arrival, instantiate an object of type car in the free store
		if(action=="arrives")
		{
			if(parking_lot.size()<5)
			{
				pcar=new car(license_plate,0);
				parking_lot.push(pcar);
			}
			//Output a meaningful message if the parking lot is full. 
			//The lot is full when the stack contains five elements.
			else
				outfs<<"Sorry "<<license_plate<<" , The lot is full ! "<<endl;
		}
		//For each departure, remove the corresponding car pointer from the stack
		else if(action=="departs")
		{
			while(!parking_lot.empty()&&parking_lot.top()->getLicense() != license_plate)
			{
				tempStack.push(parking_lot.top());
				parking_lot.top()->move();
				parking_lot.pop();
			}
			//Output the number of times this car was moved while it was parked in the lot
			if(parking_lot.top()->getLicense() == license_plate)
			{
				outfs<<parking_lot.top()->getLicense()<<" was moved "<<parking_lot.top()->getMovedTimes()<<" times while it was here"<<endl;
				delete parking_lot.top();
				parking_lot.pop();
			}
			else
				outfs<<"Exception!"<<endl;
			while(!tempStack.empty())
			{
				parking_lot.push(tempStack.top());
				tempStack.pop();
			}	
		}
	}
	//Output the number of times each car that remains in the lot (if there are any) was moved. 
	outfs<<"\n\nThese cars are still in the lot \n\n";
	while(!parking_lot.empty())
	{
		outfs<<parking_lot.top()->getLicense()<<" was moved "<<parking_lot.top()->getMovedTimes()<<" times while it was here"<<endl;
		delete parking_lot.top();
		parking_lot.pop();
	}
	outfs.close();
	infs.close();
	cout<<"The result.txt is created ,you can check it now!"<<endl;

	return EXIT_SUCCESS;
}


用于测试的data.txt文件，测试结果请参见P134之图5-4


A arrives
A departs
B arrives
C arrives
D arrives
C departs
E arrives
F arrives
G arrives
B departs
H arrives
D departs
E departs
I arrives
I departs
J arrives
F departs
K arrives
L arrives
M arrives
H departs
N arrives
J departs
K departs
O arrives
P arrives
P departs
O departs
L departs

P138：循环队列的实现


template <class T>
class CirQueue{
	int size;
	int front;
	int back;
	T* contain;

public:
	CirQueue():size(0),front(0),back(0),contain(NULL){}
	CirQueue(int MaxSize);
	void EnQueue(T& element);
	T DelQueue();
	T& GetFront();
	void MakeEmpty();
	bool IsEmpty();
	bool IsFull();
};

template <class T>
CirQueue<T>::CirQueue(int MaxSize):size(MaxSize+1),front(0),back(0)
{//构造函数
	contain = new T[MaxSize+1];
}

template <class T>
void CirQueue<T>::EnQueue(T& element)
{//向队列中添加新元素
	assert(!IsFull());
	contain[back] = element;
	back = (back+1)%size;
}

template <class T>
T CirQueue<T>::DelQueue()
{//从队列中删除元素
	int old = front;
	front = (front+1)%size;
	return contain[old];
}

template <class T>
T& CirQueue<T>::GetFront()
{//返回队头元素
	assert(!IsEmpty());
	return contain[front];
}

template <class T>
void CirQueue<T>::MakeEmpty()
{//置空队列
	front = back = 0;
}

template <class T>
bool CirQueue<T>::IsEmpty()
{//判断队列是否为空
	return front == back;
}

template <class T>
bool CirQueue<T>::IsFull()
{//判断队列是否已满
	return (back+1)%size == front;
}


P140：链式队列的实现


#ifndef LINKQUEUE_H
#define LINKQUEUE_H

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

template <class T>
class LinkQueue{

	struct LinkQueueNode
	{
		T    data;
		LinkQueueNode *link;
		LinkQueueNode(T & theData, LinkQueueNode * n = NULL ): data( theData ), link( n ) { }
	};
	LinkQueueNode* front;
	LinkQueueNode* back;

public:
	LinkQueue();
	~LinkQueue();
	void EnQueue(T& element);
	T DelQueue();
	T& GetFront();
	void MakeEmpty();
	bool IsEmpty();
};

template <class T>
LinkQueue<T>::LinkQueue()
{
	front = back = NULL;
}

template <class T>
LinkQueue<T>::~LinkQueue()
{
	this->MakeEmpty();
}

template <class T>
void LinkQueue<T>::EnQueue(T& value)
{
	if(this->IsEmpty())
		front = back = new LinkQueueNode(value);
	else
		back = back->link = new LinkQueueNode(value);
}

template <class T>
T LinkQueue<T>::DelQueue()
{
	LinkQueueNode* old = front;
	T data = old->data;
	front = front->link;
	delete old;
	return data;
}

template <class T>
T& LinkQueue<T>::GetFront()
{
	assert(!IsEmpty());
	return front->data;
}

template <class T>
void LinkQueue<T>::MakeEmpty()
{
	while(!this->IsEmpty()){
		this->DelQueue();
	}
}

template <class T>
bool  LinkQueue<T>::IsEmpty()
{
	return front == NULL;
}
#endif


P142：舞伴问题


#include "stdafx.h"
#include "LinkQueue.h"
#include <string>
#include <iostream>

using namespace std;

struct dancer{
	string name;
	char sex;
};

int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"请输入舞者总数:";
	int num;
	cin>>num;
	LinkQueue<dancer> Mdancer;
	LinkQueue<dancer> Fdancer;
	for(int i=0;i<num;i++){
		cout<<"请输入舞者性别(f or m)及姓名:";
		char sex;
		cin>>sex;
		string name;
		cin>>name;
		dancer newdancer;
		newdancer.name = name;
		newdancer.sex = sex;
		if(sex == ‘f‘)
			Fdancer.EnQueue(newdancer);
		if(sex == ‘m‘)
			Mdancer.EnQueue(newdancer);
	}

	while(!Mdancer.IsEmpty() && !Fdancer.IsEmpty()){
		cout<<Mdancer.DelQueue().name<<"\t<---->\t"<<Fdancer.DelQueue().name<<endl;
	}

	if(!Mdancer.IsEmpty()){
		cout<<"Mr. "<<Mdancer.GetFront().name<<" is waiting!"<<endl;
	}
	else if(!Fdancer.IsEmpty()){
		cout<<"Ms. "<<Fdancer.GetFront().name<<" is waiting!"<<endl;
	}
	else
		cout<<"OK!"<<endl;

	system("PAUSE");
	return 0;
}


P144：杨辉三角问题

请参见博文——杨辉三角与一道经典笔试面试题目


（链接地址：http://blog.csdn.net/baimafujinji/article/details/50436170）


P145：游程编码问题


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

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	queue<int> picture;
	char a;
	float pow = 0;
	float oriSize;
	cout<<"请输入01序列(以#结束):";
	do{
		cin>>a;
		if(a!=‘#‘)
			picture.push(a);
	}while(a != ‘#‘);

	char pic = picture.front();
	picture.pop();
	int size = picture.size()+1;
	oriSize = size;

	cout<<"编码后:";
	while(!picture.empty()){
		if(pic == picture.front()){
			pic = picture.front();
			picture.pop();
		}
		else{
			cout<<size - picture.size();
			pow++;
			size = picture.size();
			pic = picture.front();
			picture.pop();
		}
	}
	cout<<size<<endl;
	pow++;
	cout<<"压缩率为:"<<pow/oriSize<<endl;

	system("PAUSE");
	return 0;
}


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

原文：http://blog.csdn.net/baimafujinji/article/details/50485591
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！