String类--单例模式等面试题

#include<iostream>
#include<string>
using namespace std;
/*1.题目：如下为类型CMyString的声明，请为该类型添加赋值运算符函数。*/ 
class CMyString
{
public:
	CMyString(char * pData = NULL)
	{
		// 函数的默认参数实现时不需要标明 
		if (pData == NULL)
		{
			m_pData = new char[1];
			m_pData[0] = '\0';
		}
		else
		{
			m_pData = new char[strlen(pData) + 1];
			strcpy(m_pData, pData);
		}
	}
	CMyString(const CMyString&);
	~CMyString(void);
	//CMyString & operator = (const CMyString str)//常规写法
	//{
	//	if (&str != this)//确保不是自己给自己赋值
	//	{
	//		char* tmp = new char[strlen(str.m_pData) + 1];
	//		if (tmp)//保证已开辟到空间再释放原来的字符串
	//		{
	//			strcpy(tmp, str.m_pData);
	//			delete[] m_pData;
	//			m_pData = tmp;
	//		}

	//	}
	//	return *this;
	//}
	//CMyString & operator = (const CMyString &str);//提高效率
	CMyString & operator = (CMyString str)//现代写法，此处直接调CMyString类的拷贝构造函数
	{
		swap(m_pData, str.m_pData);
	}
	void print();
private:
	char * m_pData;
};
CMyString::CMyString(const CMyString & str)
{
	m_pData = new char[strlen(str.m_pData) + 1];
	strcpy(m_pData, str.m_pData); 
}
CMyString::~CMyString() 
{
	delete [] m_pData;
}

2.设计一个类，我们只能生成该类的一个实例。

分析：有时你希望定义一个类成员，使它的使用完全独立于该类的任何对象。通常情况下，类成员必须通过它的类的对象访问，但是可以创建这样一个成员，它能够被它自己使用，而不必引用特定的实例。

在成员的声明前面加上关键字static(静态的)就能创建这样的成员。如果一个成员被声明为static，它就能够在它的类的任何对象创建之前被访问，而不必引用任何对象。你可以将方法和变量都声明为static。

模式动机：如何保证一个类只有一个实例并且这个实例易于被访问呢?定义一个全局变量可以确保对象随时都可以被访问，但不能防止我们实例化多个对象。一个更好的解决办法是让类自身负责保存它的唯一实例。这个类可以保证没有其他实例被创建，并且它可以提供一个访问该实例的方法。这就是单例模式的模式动机。

当声明一个对象时，并不产生static变量的拷贝，而是该类所有的实例变量共同拥有一个static变量。

单例模式有一下特点：

　1、单例类只能有一个实例。

 2、单例类必须自己自己创建自己的唯一实例。

 3、单例类必须给所有其他对象提供这一实例。

单例模式的应用：单例模式是一种常用的软件设计模式。在它的核心结构中只包含一个被称为单例类的特殊类。通过单例模式可以保证系统中一个类只有一个实例而且该实例易于外界访问，从而方便对实例个数的控制并节约系统资源。如果希望在系统中某个类的对象只能存在一个，单例模式是最好的解决方案。

拓展：单例模式确保某个类只有一个实例，而且自行实例化并向整个系统提供这个实例。在计算机系统中，线程池、缓存、日志对象、对话框、打印机、显卡的驱动程序对象常被设计成单例。这些应用都或多或少具有资源管理器的功能。每台计算机可以有若干个打印机，但只能有一个Printer Spooler，以避免两个打印作业同时输出到打印机中。每台计算机可以有若干通信端口，系统应当集中管理这些通信端口，以避免一个通信端口同时被两个请求同时调用。总之，选择单例模式就是为了避免不一致状态，避免政出多头。一个系统中可以存在多个打印任务，但是只能有一个正在工作的任务;一个系统只能有一个窗口管理器或文件系统;一个系统只能有一个计时工具或ID(序号)生成器。如在Windows中就只能打开一个任务管理器。如果不使用机制对窗口对象进行唯一化，将弹出多个窗口，如果这些窗口显示的内容完全一致，则是重复对象，浪费内存资源;如果这些窗口显示的内容不一致，则意味着在某一瞬间系统有多个状态，与实际不符，也会给用户带来误解，不知道哪一个才是真实的状态。因此有时确保系统中某个对象的唯一性即一个类只能有一个实例非常重要。

class Singleton
{
private:
	static Singleton* uniqueInstance;
	Singleton()
	{}
	~Singleton()
	{
		delete uniqueInstance;
	}
	Singleton(const Singleton& s);
	Singleton& operator=(const Singleton& s);
public:
	static Singleton* GetInstance()
	{
		if (uniqueInstance == NULL)
		{
			uniqueInstance = new Singleton();
		}
		return uniqueInstance;
	}
};
Singleton* Singleton::uniqueInstance = NULL;

考虑线程安全，可通过加锁来实现。

3.在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：可通过矩阵特点在矩阵中查找整数。先从右上角寻找，如果小于右上角的数，则此数肯定在该行左侧。

如果小于右上角的数，则此数肯定在该行下侧。

bool SearchNum(int arr[], int row, int col, int num)
{
	if (NULL == arr)
		return false;
	int i, j;
	i = 0;
	j = col;
	while (i <= row - 1 && j >= 0)
	{
		if (arr[i*col + j] == num)
			return true;
		else if (arr[i*col + j] > num)
			j--;
		else
			i++;
	}
	return false;
}

4.

题目：请实现一个函数，把字符串中的每个空格替换成“%20”。例如输入“We are happy.”，则输出“We%20are%20happy.”。

由题意得：此处修改源字符串，可先算出空格数，算出新字符串长度，从后向前拷贝源字符串，当字符为空格时，补20%，否则依次拷贝字符。

void replaceSpace(char string[],int length)//length存储string长度，检测是否可以存下新的字符串
{
	int spaceNum = 0;
	int index = 0;
	if (NULL == string)
		return;
	while (string[index])//等同于string[index]!='\0'
	{
		if (string[index] == ' ')
			spaceNum++;
		index++;
	}
	int newLength = strlen(string) + 2 * spaceNum + 1;
	if (length < newLength)
		return;
	index = strlen(string)-1;
	newLength -= 1;
	while (index!=-1)
	{
		if (string[index] == ' ')
		{
			string[newLength--] = '%';
			string[newLength--] = '0';
			string[newLength--] = '2';
		}
		else
			string[newLength--] = string[index];
		index--;
	}
}

//输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下：

template<class T>

struct LinkNode

{

T _data;

LinkNode* _next;

LinkNode(const T& x)

:_data(x)

, _next(NULL)

{}

};

//递归
template<class T>
void ReverseDisplay(LinkNode<T>* head)
{
	if (head == NULL)
		return;
	if (head->_next == NULL)
	{
		cout << head->_data << " ";
		return;
	}
	ReverseDisplay(head->_next);
	cout << head->_data << " ";
}
//利用栈
template<class T>
void ReverseDisplay(LinkNode<T>* head)
{
	stack<LinkNode<int>*> s;
	LinkNode<T>* cur = head;
	while (cur)
	{
		s.push(cur);
		cur = cur->_next;
	}
	while (!s.empty())
	{
		cur = s.top();
		cout << cur->_data << " ";
		s.pop();
	}
}

6.用两个栈实现一个队列，队列的声明如下，请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入节点和在队列头部删除节点的功能

思路：每次push数据push到栈s1中，第一次pop时将栈s1的数据导入s2中，此时s2栈顶就是刚入进去的数据，下次pop先看s2中有数据没，有数据直接pop,没数据从s1导数据，再pop.

template<class T>
class MyQueue
{
protected:
	stack<T> s1;
	stack<T> s2;
public:
	void appendTail(const T& x)
	{
		s1.push(x);
	}
	void deleteHead()
	{
		if (s2.empty())
		{
			while (!s1.empty())
			{
				s2.push(s1.top());
				s1.pop();
			}
		}
		if (!s2.empty())
			s2.pop();
	}
};