C++面試題集4

一. 華為一道面試題-1-n排序

有N個(gè)大小不等的自然數(shù)（1--N），請(qǐng)將它們由小到大排序。
要求程序算法：時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。

網(wǎng)上轉(zhuǎn)的，一開始也沒有注意到最開始的半句。

算法：N個(gè)不等的自然數(shù)1~N，排序完成后必然為1~N。所以可以一次遍歷，遇到a[i]!=i的就把a(bǔ)[i]和a[a[i]]交換。

void sort(int a[], int n)
{
?int i;
?int t; /*臨時(shí)變量：空間復(fù)雜度O(1)*/

?for (i=1; i<n+1; i++) /*時(shí)間復(fù)雜度O(n)*/
?{
?while(a[i]!=i)
? {
?t = a[a[i]];
?a[a[i]] = a[i];//排好一個(gè)元素
?a[i] = t;
? }
?}
}

二. 一次遍歷 找 鏈表倒數(shù)第n個(gè)節(jié)點(diǎn)

?一道面試題目，阿明和晨晨看到并且告訴我答案的。要求通過一次遍歷找到鏈表中倒數(shù)第n個(gè)節(jié)點(diǎn)，鏈表可能相當(dāng)大，可使用輔助空間，但是輔助空間的數(shù)目必須固定，不能和n有關(guān)。
算法思想：兩根指針，第一根先出發(fā)，相距n步后第二根出發(fā)。然后同時(shí)步進(jìn)，直到第一根指針達(dá)到末尾。

struct iNode {
int value;
iNode * next;
};
iNode * getresult(iNode * head,int n)
{

iNode *pfirst;
iNode *psecond;

pfirst=head;
int counter;

for(counter=0;counter<n;counter++) {
?pfirst=pfirst->next;
}

psecond=head;

while(pfirst!=NULL) {
?pfirst=pfirst->next;
?psecond=psecond->next;
}

return psecond;

}

三. VC++學(xué)習(xí)筆記

1.?????? 日期轉(zhuǎn)成字符串：

?? COleDateTime??? ww;
ww=COleDateTime::GetCurrentTime();
AfxMessageBox(ww.Format("%Y-%m-%d %H:%M:%S"));

2.?????? 字符串轉(zhuǎn)成日期：

COleDateTime dt;

?????? dt.ParseDateTime(“2006-08-08 08:08:08”);

3.?????? 資源文件

資源文件名:xxx.rc,其中要包含的主要文件:resource.h和afxres.h

4.?????? vc開發(fā)環(huán)境沒有自動(dòng)提示時(shí):

?? 刪除 目錄下的ncb文件 ，再打開一般就ok了

5.?????? 利用_variant_t 取數(shù)據(jù)庫(kù)數(shù)據(jù)的方法:

?? _variant_t ibb;

?????? ibb=(_variant_t)rs->GetCollect("inta");

?????? if(ibb.vt!=VT_NULL)

?????? {

????????????? m_b=ibb.lVal;

?????? }

6.?????? 平時(shí)取記錄集字段值的方法:

?? (LPCTSTR)(_bstr_t)rs->GetCollect("datea")

7.?????? DoModal()可以返回兩個(gè)結(jié)果 IDOK,IDCANCEL,他們都是int型，分別是：1,2。通過EndDialog(IDOK)的方式返回。

8.?????? 一般將數(shù)據(jù)庫(kù)連接方面的信息放到app中。則AfxGetApp()非常重要，如；

?? CAdo2App* mapp=（CAdo2App*）AfxGetApp();

?? Map->conn->Execute(sql,NULL,adCmdText);

9.?????? DECLARE_DYNCREATE（類名）,IMPLEMENT_DYNCREATE(類名，基類名)? 使得由CObject繼承來的類在程序運(yùn)行的時(shí)候能夠動(dòng)態(tài)的創(chuàng)建。

10.?? DECLARE_DYNAMIC（類名）,IMPLEMENT_DYNAMIC(類名，基類名)? 可以在運(yùn)行時(shí)獲得該類的信息

11.?? DECLARE_SERIAL（類名）,IMPLEMENT_SERIAL(類名，基類名,0)為一個(gè)可以串行化的CObject派生類產(chǎn)生必要的C++標(biāo)題代碼

12.?? 獲得文檔的方法： CMainFrame * pFrame=(CMainFrame *) AfxGetMainWnd();

CPClientDoc * pDoc =(CPClientDoc *) pFrame->GetActiveDocument();
?

13.?? 獲得視圖的方法：CMainFrame * pFrame=(CMainFrame *) AfxGetMainWnd();

myView =(CPClientView*) pFrame->GetActiveView();

14.?? 如果要引用全局變量或者全局方法，須在當(dāng)前類中引入：extern 名字;