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();
	}
};