單向鏈表的反轉是一個經常被問到的一個面試題，也是一個非常基礎的問題。比如一個鏈表是這樣的： 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;
}
還有一種利用遞歸的方法。這種方法的基本思想是在反轉當前節點之前先調用遞歸函數反轉後續節點。源代碼如下。不過這個方法有一個缺點，就是在反轉後的最後一個結點會形成一個環，所以必須將函數的返回的節點的next域置爲null。因爲要改變head指針，所以我用了引用。算法的源代碼如下：
linka＊ reverse(linka＊ p,linka＊& head)
{
if(p null || p->next null)
{
head=p;
return p;
}
else
{
linka＊ tmp = reverse(p->next,head);
tmp->next = p;
return p;
}
}
②已知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] = '''' ;
}
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 ;
}
string::~string()
{
delete []m_data ;
}
1.求下面函數的返回值(微軟)
int func(x)
{
int countx = 0;
while(x)
{
countx ++;
x = x&(x-1);
}
return countx;
}
假定x = 9999。 答案：8
思路：將x轉化爲2進制，看含有的1的個數。
2. 什麼是“引用”?申明和使用“引用”要注意哪些問題?
答：引用就是某個目標變量的“別名”(alias)，對應用的操作與對變量直接操作效果完全相同。申明一個引用的'時候，切記要對其進行初始化。引用聲明完畢後，相當於目標變量名有兩個名稱，即該目標原名稱和引用名，不能再把該引用名作爲其他變量名的別名。聲明一個引用，不是新定義了一個變量，它只表示該引用名是目標變量名的一個別名，它本身不是一種數據類型，因此引用本身不佔存儲單元，系統也不給引用分配存儲單元。不能建立數組的引用。
3. 將“引用”作爲函數參數有哪些特點?
(1)傳遞引用給函數與傳遞指針的效果是一樣的。這時，被調函數的形參就成爲原來主調函數中的實參變量或對象的一個別名來使用，所以在被調函數中對形參變量的操作就是對其相應的目標對象(在主調函數中)的操作。
(2)使用引用傳遞函數的參數，在內存中並沒有產生實參的副本，它是直接對實參操作;而使用一般變量傳遞函數的參數，當發生函數調用時，需要給形參分配存儲單元，形參變量是實參變量的副本;如果傳遞的是對象，還將調用拷貝構造函數。因此，當參數傳遞的數據較大時，用引用比用一般變量傳遞參數的效率和所佔空間都好。