C++面試題集4

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

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

網上轉的，一開始也沒有注意到最開始的半句。

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

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

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

二. 一次遍歷 找 鏈表倒數第n個節點

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

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++學習筆記

1.?????? 日期轉成字符串：

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

2.?????? 字符串轉成日期：

COleDateTime dt;

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

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

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

4.?????? vc開發環境沒有自動提示時:

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

5.?????? 利用_variant_t 取數據庫數據的方法:

?? _variant_t ibb;

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

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

?????? {

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

?????? }

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

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

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

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

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

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

9.?????? DECLARE_DYNCREATE（類名）,IMPLEMENT_DYNCREATE(類名，基類名)? 使得由CObject繼承來的類在程序運行的時候能夠動態的創建。

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

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

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

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

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

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

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