單向鏈表的反轉(zhuǎn)是一個(gè)經(jīng)常被問到的一個(gè)面試題，也是一個(gè)非常基礎(chǔ)的問題。比如一個(gè)鏈表是這樣的： 1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1。
最容易想到的方法遍歷一遍鏈表，利用一個(gè)輔助指針，存儲(chǔ)遍歷過程中當(dāng)前指針指向的下一個(gè)元素，然后將當(dāng)前節(jié)點(diǎn)元素的指針反轉(zhuǎn)后，利用已經(jīng)存儲(chǔ)的指針往后面繼續(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)當(dāng)前節(jié)點(diǎn)之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點(diǎn)。源代碼如下。不過這個(gè)方法有一個(gè)缺點(diǎn)，就是在反轉(zhuǎn)后的最后一個(gè)結(jié)點(diǎn)會(huì)形成一個(gè)環(huán)，所以必須將函數(shù)的返回的節(jié)點(diǎn)的next域置為null。因?yàn)橐淖僪ead指針，所以我用了引用。算法的源代碼如下：
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ù)實(shí)現(xiàn)。
答案：
string::string(const char *str)
{
if ( str null ) //strlen在參數(shù)為null時(shí)會(huì)拋異常才會(huì)有這步判斷
{
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進(jìn)制，看含有的1的個(gè)數(shù)。
2. 什么是“引用”?申明和使用“引用”要注意哪些問題?
答：引用就是某個(gè)目標(biāo)變量的“別名”(alias)，對(duì)應(yīng)用的操作與對(duì)變量直接操作效果完全相同。申明一個(gè)引用的時(shí)候，切記要對(duì)其進(jìn)行初始化。引用聲明完畢后，相當(dāng)于目標(biāo)變量名有兩個(gè)名稱，即該目標(biāo)原名稱和引用名，不能再把該引用名作為其他變量名的別名。聲明一個(gè)引用，不是新定義了一個(gè)變量，它只表示該引用名是目標(biāo)變量名的一個(gè)別名，它本身不是一種數(shù)據(jù)類型，因此引用本身不占存儲(chǔ)單元，系統(tǒng)也不給引用分配存儲(chǔ)單元。不能建立數(shù)組的引用。
3. 將“引用”作為函數(shù)參數(shù)有哪些特點(diǎn)?
(1)傳遞引用給函數(shù)與傳遞指針的效果是一樣的。這時(shí)，被調(diào)函數(shù)的形參就成為原來主調(diào)函數(shù)中的實(shí)參變量或?qū)ο蟮囊粋�(gè)別名來使用，所以在被調(diào)函數(shù)中對(duì)形參變量的操作就是對(duì)其相應(yīng)的目標(biāo)對(duì)象(在主調(diào)函數(shù)中)的操作。
(2)使用引用傳遞函數(shù)的參數(shù)，在內(nèi)存中并沒有產(chǎn)生實(shí)參的副本，它是直接對(duì)實(shí)參操作;而使用一般變量傳遞函數(shù)的參數(shù)，當(dāng)發(fā)生函數(shù)調(diào)用時(shí)，需要給形參分配存儲(chǔ)單元，形參變量是實(shí)參變量的副本;如果傳遞的是對(duì)象，還將調(diào)用拷貝構(gòu)造函數(shù)。因此，當(dāng)參數(shù)傳遞的數(shù)據(jù)較大時(shí)，用引用比用一般變量傳遞參數(shù)的效率和所占空間都好。