String類--單例模式等面試題

#include<iostream>
#include<string>
using namespace std;
/*1.題目：如下為類型CMyString的聲明，請(qǐng)為該類型添加賦值運(yùn)算符函數(shù)。*/ 
class CMyString
{
public:
	CMyString(char * pData = NULL)
	{
		// 函數(shù)的默認(rèn)參數(shù)實(shí)現(xiàn)時(shí)不需要標(biāo)明 
		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)//常規(guī)寫法
	//{
	//	if (&str != this)//確保不是自己給自己賦值
	//	{
	//		char* tmp = new char[strlen(str.m_pData) + 1];
	//		if (tmp)//保證已開(kāi)辟到空間再釋放原來(lái)的字符串
	//		{
	//			strcpy(tmp, str.m_pData);
	//			delete[] m_pData;
	//			m_pData = tmp;
	//		}

	//	}
	//	return *this;
	//}
	//CMyString & operator = (const CMyString &str);//提高效率
	CMyString & operator = (CMyString str)//現(xiàn)代寫法，此處直接調(diào)CMyString類的拷貝構(gòu)造函數(shù)
	{
		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.設(shè)計(jì)一個(gè)類，我們只能生成該類的一個(gè)實(shí)例。

分析：有時(shí)你希望定義一個(gè)類成員，使它的使用完全獨(dú)立于該類的任何對(duì)象。通常情況下，類成員必須通過(guò)它的類的對(duì)象訪問(wèn)，但是可以創(chuàng)建這樣一個(gè)成員，它能夠被它自己使用，而不必引用特定的實(shí)例。

在成員的聲明前面加上關(guān)鍵字static(靜態(tài)的)就能創(chuàng)建這樣的成員。如果一個(gè)成員被聲明為static，它就能夠在它的類的任何對(duì)象創(chuàng)建之前被訪問(wèn)，而不必引用任何對(duì)象。你可以將方法和變量都聲明為static。

模式動(dòng)機(jī)：如何保證一個(gè)類只有一個(gè)實(shí)例并且這個(gè)實(shí)例易于被訪問(wèn)呢?定義一個(gè)全局變量可以確保對(duì)象隨時(shí)都可以被訪問(wèn)，但不能防止我們實(shí)例化多個(gè)對(duì)象。一個(gè)更好的解決辦法是讓類自身負(fù)責(zé)保存它的唯一實(shí)例。這個(gè)類可以保證沒(méi)有其他實(shí)例被創(chuàng)建，并且它可以提供一個(gè)訪問(wèn)該實(shí)例的方法。這就是單例模式的模式動(dòng)機(jī)。

當(dāng)聲明一個(gè)對(duì)象時(shí)，并不產(chǎn)生static變量的拷貝，而是該類所有的實(shí)例變量共同擁有一個(gè)static變量。

單例模式有一下特點(diǎn)：

　1、單例類只能有一個(gè)實(shí)例。

 2、單例類必須自己自己創(chuàng)建自己的唯一實(shí)例。

 3、單例類必須給所有其他對(duì)象提供這一實(shí)例。

單例模式的應(yīng)用：單例模式是一種常用的軟件設(shè)計(jì)模式。在它的核心結(jié)構(gòu)中只包含一個(gè)被稱為單例類的特殊類。通過(guò)單例模式可以保證系統(tǒng)中一個(gè)類只有一個(gè)實(shí)例而且該實(shí)例易于外界訪問(wèn)，從而方便對(duì)實(shí)例個(gè)數(shù)的控制并節(jié)約系統(tǒng)資源。如果希望在系統(tǒng)中某個(gè)類的對(duì)象只能存在一個(gè)，單例模式是最好的解決方案。

拓展：?jiǎn)卫Ｊ酱_保某個(gè)類只有一個(gè)實(shí)例，而且自行實(shí)例化并向整個(gè)系統(tǒng)提供這個(gè)實(shí)例。在計(jì)算機(jī)系統(tǒng)中，線程池、緩存、日志對(duì)象、對(duì)話框、打印機(jī)、顯卡的驅(qū)動(dòng)程序?qū)ο蟪１辉O(shè)計(jì)成單例。這些應(yīng)用都或多或少具有資源管理器的功能。每臺(tái)計(jì)算機(jī)可以有若干個(gè)打印機(jī)，但只能有一個(gè)Printer Spooler，以避免兩個(gè)打印作業(yè)同時(shí)輸出到打印機(jī)中。每臺(tái)計(jì)算機(jī)可以有若干通信端口，系統(tǒng)應(yīng)當(dāng)集中管理這些通信端口，以避免一個(gè)通信端口同時(shí)被兩個(gè)請(qǐng)求同時(shí)調(diào)用。總之，選擇單例模式就是為了避免不一致?tīng)顟B(tài)，避免政出多頭。一個(gè)系統(tǒng)中可以存在多個(gè)打印任務(wù)，但是只能有一個(gè)正在工作的任務(wù);一個(gè)系統(tǒng)只能有一個(gè)窗口管理器或文件系統(tǒng);一個(gè)系統(tǒng)只能有一個(gè)計(jì)時(shí)工具或ID(序號(hào))生成器。如在Windows中就只能打開(kāi)一個(gè)任務(wù)管理器。如果不使用機(jī)制對(duì)窗口對(duì)象進(jìn)行唯一化，將彈出多個(gè)窗口，如果這些窗口顯示的內(nèi)容完全一致，則是重復(fù)對(duì)象，浪費(fèi)內(nèi)存資源;如果這些窗口顯示的內(nèi)容不一致，則意味著在某一瞬間系統(tǒng)有多個(gè)狀態(tài)，與實(shí)際不符，也會(huì)給用戶帶來(lái)誤解，不知道哪一個(gè)才是真實(shí)的狀態(tài)。因此有時(shí)確保系統(tǒng)中某個(gè)對(duì)象的唯一性即一個(gè)類只能有一個(gè)實(shí)例非常重要。

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;

考慮線程安全，可通過(guò)加鎖來(lái)實(shí)現(xiàn)。

3.在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

思路：可通過(guò)矩陣特點(diǎn)在矩陣中查找整數(shù)。先從右上角尋找，如果小于右上角的數(shù)，則此數(shù)肯定在該行左側(cè)。

如果小于右上角的數(shù)，則此數(shù)肯定在該行下側(cè)。

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.

題目：請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把字符串中的每個(gè)空格替換成“%20”。例如輸入“We are happy.”，則輸出“We%20are%20happy.”。

由題意得：此處修改源字符串，可先算出空格數(shù)，算出新字符串長(zhǎng)度，從后向前拷貝源字符串，當(dāng)字符為空格時(shí)，補(bǔ)20%，否則依次拷貝字符。

void replaceSpace(char string[],int length)//length存儲(chǔ)string長(zhǎng)度，檢測(cè)是否可以存下新的字符串
{
	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--;
	}
}

//輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過(guò)來(lái)輸出每個(gè)結(jié)點(diǎn)的值。鏈表結(jié)點(diǎn)定義如下：

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.用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列，隊(duì)列的聲明如下，請(qǐng)實(shí)現(xiàn)它的兩個(gè)函數(shù)appendTail和deleteHead,分別完成在隊(duì)列尾部插入節(jié)點(diǎn)和在隊(duì)列頭部刪除節(jié)點(diǎn)的功能

思路：每次push數(shù)據(jù)push到棧s1中，第一次pop時(shí)將棧s1的數(shù)據(jù)導(dǎo)入s2中，此時(shí)s2棧頂就是剛?cè)脒M(jìn)去的數(shù)據(jù)，下次pop先看s2中有數(shù)據(jù)沒(méi)，有數(shù)據(jù)直接pop,沒(méi)數(shù)據(jù)從s1導(dǎo)數(shù)據(jù)，再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();
	}
};