C++ 筆試題

①鏈表反轉

單向鏈表的反轉是一個經常被問到的一個面試題，也是一個非常基礎的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉後成為5->4->3->2->1。

最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然後將當前節點元素的指針反轉後，利用已經存儲的指針往後面繼續遍歷。源代碼如下：

struct linka {
int data;
linka* next;
};
void reverse(linka*& head) {
if(head ==NULL)
                  return;
linka *pre, *cur, *ne;
pre=head;
cur=head->next;
while(cur)
{
   ne = cur->next;
   cur->next = pre;
   pre = cur;
   cur = ne;
}
head->next = NULL;
head = pre;
}

②已知String類定義如下：

class String
{
public:
String(const char *str = NULL); // 通用構造函數
String(const String &another); // 拷貝構造函數
~ String(); // 析構函數
String & operater =(const String &rhs); // 賦值函數
private:
char *m_data; // 用於保存字符串
};

嘗試寫出類的成員函數實現。

String::String(const char *str)
{
if ( str == NULL ) //strlen在參數為NULL時會拋異常才會有這步判斷
{
m_data = new char[1] ;
m_data[0] = '\0' ;
}
else
{
m_data = new char[strlen(str) + 1];
strcpy(m_data,str);
}

}

String::String(const String &another)
{
m_data = new char[strlen(another.m_data) + 1];
strcpy(m_data,other.m_data);
}

String& String::operator =(const String &rhs)
{
if ( this == &rhs)
return *this ;
delete []m_data; //刪除原來的數據，新開一塊內存
m_data = new char[strlen(rhs.m_data) + 1];
strcpy(m_data,rhs.m_data);
return *this ;
}