C/C++筆試忍法帖05——資料結構篇6.用兩個棧實作一個隊列的功能？要求給出算法和思路！

(1)冒泡排序； O（n^2）

(2)選擇排序； 直接選擇排序是O(n^2)

(3)插入排序；直接插入排序是 O（n^2）

(4)快速排序； O(nlog2 n)

(5)堆排序；   O(nlog2

n)

(6)歸并排序； O(nlog2

2.程式設計，請實作一個c語言中類似atoi的函數功能（輸入可能包含非數字和空格）

3.在排序方法中，關鍵碼比較次數與記錄地初始排列無關的是     D

A. Shell排序      B. 歸并排序       C. 直接插入排序     D. 選擇排序

5. 編寫strcat函數(6分)

已知strcat函數的原型是char *strcat (char *strDest, const char *strSrc);

其中strDest 是目的字元串，strSrc 是源字元串。

（1）不調用C++/C 的字元串庫函數，請編寫函數 strcat

答：

VC源碼：

char * __cdecl strcat (char * dst, const char * src)

{

char * cp = dst;

while( *cp )

cp++; /* find end of dst */

while( *cp++ = *src++ ) ; /* Copy src to end of dst */

return( dst ); /* return dst */

}

（2）strcat能把strSrc 的内容連接配接到strDest，為什麼還要char * 類型的傳回值？

答：友善指派給其他變量

答 ：設2個棧為A,B, 一開始均為空.

    入隊:

     将新元素push入棧A;

   出隊:

    (1)判斷棧B是否為空；

    (2)如果不為空，則将棧A中所有元素依次pop出并push到棧B；

    (3)将棧B的棧頂元素pop出；

7.連結清單反轉

單向連結清單的反轉是一個經常被問到的一個面試題，也是一個非常基礎的問題。比如一個連結清單是這樣的：

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; 

8.編寫strcpy函數（10分）

已知strcpy函數的原型是

        char *strcpy(char *strDest, const char *strSrc);

        其中strDest是目的字元串，strSrc是源字元串。

（1）不調用C++/C的字元串庫函數，請編寫函數 strcpy

char *strcpy(char *strDest, const char *strSrc);

     assert((strDest!=NULL) && (strSrc !=NULL)); // 2分

     char *address = strDest;                    // 2分

     while( (*strDest++ = * strSrc++) != ‘ 0’ )     // 2分

        NULL ;

     return address ;                           // 2分

（2）strcpy能把strSrc的内容複制到strDest，為什麼還要char * 類型的傳回值？

答：為了實作鍊式表達式。                                               // 2分

例如： int length = strlen( strcpy( strDest, “hello world”) );