單向鏈表的反轉(zhuǎn)是一個經(jīng)常被問到的一個面試題，也是一個非常基礎的問題。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1。
最容易想到的方法遍歷一遍鏈表，利用一個輔助指針，存儲遍歷過程中當前指針指向的下一個元素，然后將當前節(jié)點元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲的指針往后面繼續(xù)遍歷。源代碼如下：
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;
}
還有一種利用遞歸的方法。這種方法的基本思想是在反轉(zhuǎn)當前節(jié)點之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點。源代碼如下。不過這個方法有一個缺點，就是在反轉(zhuǎn)后的最后一個結(jié)點會形成一個環(huán)，所以必須將函數(shù)的返回的節(jié)點的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;
}
}
�、谝阎猻tring類定義如下：
class string
{
public:
string(const char *str = null); // 通用構(gòu)造函數(shù)
string(const string &another); // 拷貝構(gòu)造函數(shù)
~ string(); // 析構(gòu)函數(shù)
string & operater =(const string &rhs); // 賦值函數(shù)
private:
char *m_data; // 用于保存字符串
};
嘗試寫出類的成員函數(shù)實現(xiàn)。
答案：
string::string(const char *str)
{
if ( str null ) //strlen在參數(shù)為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; //刪除原來的數(shù)據(jù)，新開一塊內(nèi)存
m_data = new char[strlen(rhs.m_data) + 1];
strcpy(m_data,rhs.m_data);
return *this ;
}
string::~string()
{
delete []m_data ;
}
1.求下面函數(shù)的返回值(微軟)
int func(x)
{
int countx = 0;
while(x)
{
countx ++;
x = x&(x-1);
}
return countx;
}
假定x = 9999。 答案：8
思路：將x轉(zhuǎn)化為2進制，看含有的1的個數(shù)。
2. 什么是“引用”?申明和使用“引用”要注意哪些問題?
答：引用就是某個目標變量的“別名”(alias)，對應用的操作與對變量直接操作效果完全相同。申明一個引用的時候，切記要對其進行初始化。引用聲明完畢后，相當于目標變量名有兩個名稱，即該目標原名稱和引用名，不能再把該引用名作為其他變量名的別名。聲明一個引用，不是新定義了一個變量，它只表示該引用名是目標變量名的一個別名，它本身不是一種數(shù)據(jù)類型，因此引用本身不占存儲單元，系統(tǒng)也不給引用分配存儲單元。不能建立數(shù)組的引用。
3. 將“引用”作為函數(shù)參數(shù)有哪些特點?
(1)傳遞引用給函數(shù)與傳遞指針的效果是一樣的。這時，被調(diào)函數(shù)的形參就成為原來主調(diào)函數(shù)中的實參變量或?qū)ο蟮囊粋�別名來使用，所以在被調(diào)函數(shù)中對形參變量的操作就是對其相應的目標對象(在主調(diào)函數(shù)中)的操作。
(2)使用引用傳遞函數(shù)的參數(shù)，在內(nèi)存中并沒有產(chǎn)生實參的副本，它是直接對實參操作;而使用一般變量傳遞函數(shù)的參數(shù)，當發(fā)生函數(shù)調(diào)用時，需要給形參分配存儲單元，形參變量是實參變量的副本;如果傳遞的是對象，還將調(diào)用拷貝構(gòu)造函數(shù)。因此，當參數(shù)傳遞的數(shù)據(jù)較大時，用引用比用一般變量傳遞參數(shù)的效率和所占空間都好。