C面試題3

《2018 iOS面試題系列》

143. 枚舉元素本身由系統(tǒng)定義了一個表示序號的數(shù)值，從0 開始順序定義為0喻频，1，2…吨掌。如在weekday中，sun值為0脓恕，mon值為1膜宋， …,sat值為6。

main(){
　enum weekday
　{ 
　　sun,mon,tue,wed,thu,fri,sat
　} a,b,c;
　a=sun;
　b=mon;
　c=tue;
　printf("%d,%d,%d",a,b,c);
}

只能把枚舉值賦予枚舉變量炼幔，不能把元素的數(shù)值直接賦予枚舉變量秋茫。如：a=sum;b=mon; 是正確的。而：a=0;b=1; 是錯誤的乃秀。如一定要把數(shù)值賦予枚舉變量肛著，則必須用強(qiáng)制類型轉(zhuǎn)換圆兵，如：a=(enum weekday)2;其意義是將順序號為2的枚舉元素賦予枚舉變量a，相當(dāng)于：a=tue; 還應(yīng)該說明的是枚舉元素不是字符常量也不是字符串常量枢贿，使用時不要加單殉农、雙引號。

main(){
　enum body
　{
　　a,b,c,d 
　} month[31],j;
　int i;
　j=a;
　for(i=1;i<=30;i++){
　　month[i]=j;
　　j++;
　　if (j>d) j=a;
　}
　for(i=1;i<=30;i++){
　　switch(month[i])
　　{
　　　case a:printf(" %2d %c\t",i,'a'); break;
　　　case b:printf(" %2d %c\t",i,'b'); break;
　　　case c:printf(" %2d %c\t",i,'c'); break;
　　　case d:printf(" %2d %c\t",i,'d'); break;
　　　default:break;
　　}
　}
　printf("\n");
}

144．用折半查找法求一個數(shù)局荚？數(shù)組a已按從小到大的順序排列

while((!sign) && (bott <= top))
{
    mid=(bott + top)/2;
     if(number ==a[mid])
    {
        local=mid;
        printf(“the local is %d\n”,local);
        printf(“the number is%d\n”, number);
        sign =true;
}
else if(number <a[min])
   top = mid -1;
else
   bott=mid+1;
}

145．有一個字符串超凳，將字符串從第m個字符開始全部復(fù)制到另一個新字符串?

void copystr( char *p1, char *p2, int m)
{
    int n=0;
    while(n<m-1)
    {
        n++;
        p1++;
}
while(*p1 !=’/0’)
{
    *p2=*p1;
    p1++;
    p2++;
}
*p2=’/0’;
}

146．排序問題：

問題一：寫出冒泡排序

void bubble_sort(int arr[], int len)
{
    for (int i = 0; i < len - 1; i++) {
        for (int j = len - 1; j > i; j--) {
           if (arr[j] < arr[j - 1]) {
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
         }
      }
  }
}

問題二：寫出選擇法排序
void select_sort(int arr[], int len)
{
    for (int i = 0; i < len; i++) {
        int index = i;
        for (int j = i + 1; j < len; j++) {
            if (arr[j] < arr[index])
                index = j;
         }
         if (index != i)
         {
            int temp = arr[i];
            arr[i] = arr[index];
            arr[index] = temp; 
        }
    }
}

注釋：
以下為一個用C描述的函數(shù)實(shí)現(xiàn)上述排序：

　　void sort(int array[],int n) 
　　{ // n 為數(shù)組元素個數(shù) 
　　int i,j,k,temp; // i 為基準(zhǔn)位置，j 為當(dāng)前被掃描元素位置耀态，k 用于暫存出現(xiàn)的較小的元素的位置 
　　for(i=0;i<n-1;i++) 
　　{k=i;//初始化為基準(zhǔn)位置 
　　for(j=i+1;j<n;j++) 
　　{ 
　　if (array[j]<array[k]) k=j ; // k 始終指示出現(xiàn)的較小的元素的位置 
　　if(k!=i) 
　　{ temp=array[i]; 
　　array[i]=array[k]; 
　　array[k]=temp; // 將此趟掃描得到的最小元素與基準(zhǔn)互換位置 
　　} 
　　} //for 
　　} 
　　} 

　　其實(shí)現(xiàn)相對簡單轮傍，效率比較低，時間復(fù)雜度為O(n2) （n 的平方） 首装，為就地排序创夜。

鏈表問題匯總

147寫一函數(shù)creat, 用來建立一個動態(tài)鏈表，各結(jié)點(diǎn)數(shù)據(jù)由鍵盤輸入仙逻。

struct student
 {
    long num;
    float score;
    stuent *next;
 };
 
 student *creat (void)
 {
    student *head;
    student *p1=null,*p2=null;
    int n=0;
    p1=p2=new student;
    cin>>p1->num>>p1->score;
    head=null;
    while(p1->num !=0)
    {
        n=n+1;
        if(1==n) head=p1;
        else  
         p2->next=p1;
        p2=p1;
        p1= new student;
        cin>>p1->mum>>p1->score;
    }
    p2->next =NULL;
    return (head);
 }

148驰吓，寫一print函數(shù)，將鏈表中的各數(shù)據(jù)遍歷輸出

  void print(student *head )
  {
    student *p;
    cout<<"there"<<n<<"records"<<endl;
    p=head;
    if(head!=NULL)
    do
    {
        cout<<p->num<<" "<<p->score<<endl;
        p=p->next;
    }while(p!=NULL)
  }

149．寫一del函數(shù)桨醋，用來刪除動態(tài)鏈表中棚瘟，指定的結(jié)點(diǎn)數(shù)據(jù)

 void *del(student *head, long num)
 {
    student *p1,*p2;
    if(head==NULL)
    {return (head);}
    p1=head;
    while(num!=p1->num && p1->next !=NULL)
    {
        p2=p1;
        p1=p1->next;
    }
    if(num == p1->num)
    {
        if(p1==head)
                head=p1->next;
        else
                p2->next=p1->next;
        cout<<"delete:"<<num<<endl;
        n=n-1;
    }
    else
        cout<<"can not find"<<num;
    return(head);
 }

150 寫一函數(shù)insert,用來向動態(tài)鏈表插入一結(jié)點(diǎn)

 Student *insert(student *head, student *stud)
 {
    student *p0 ,*p1, *p2;
    p1=head;
    p0=stud;
    if(head == NULL)
    {
        head=p0;
        p0->next=NULL;
    }
    else
    {
        while((p0->num >p1->num) && (p1->next!=NULL) )
        {
            p2=p1;
            p1=p1->next;
        }
        if(p0->num <= p1->num)
        {
            if(head ==p1)
                head=p0;
            else
                p2->next=p0;
            p0->next=p1;
        }
        else
        {
            p1->next=p0;
            p0->next=NULL;  
        }
    }
    n=n+1;
    return(head);
  
 }

151 鏈表題：一個鏈表的結(jié)點(diǎn)結(jié)構(gòu)

struct Node
{
int data ;
Node *next ;
};
typedef struct Node Node ;

(1)已知鏈表的頭結(jié)點(diǎn)head,寫一個函數(shù)把這個鏈表逆序 ( Intel)

Node * ReverseList(Node *head) //鏈表逆序
{
if ( head == NULL || head->next == NULL )
return head;
Node *p1 = head ;
Node *p2 = p1->next ;
Node *p3 = p2->next ;
p1->next = NULL ;
while ( p3 != NULL )
{
p2->next = p1 ;
p1 = p2 ;
p2 = p3 ;
p3 = p3->next ;
}
p2->next = p1 ;
head = p2 ;
return head ;
}

(2)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序喜最。(保留所有結(jié)點(diǎn)偎蘸，即便大小相同）

Node * Merge(Node *head1 , Node *head2)
{
if ( head1 == NULL)
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
Node *p1 = NULL;
Node *p2 = NULL;
if ( head1->data < head2->data )
{
head = head1 ;
p1 = head1->next;
p2 = head2 ;
}
else
{
head = head2 ;
p2 = head2->next ;
p1 = head1 ;
}
Node *pcurrent = head ;
while ( p1 != NULL && p2 != NULL)
{
if ( p1->data <= p2->data )
{
pcurrent->next = p1 ;
pcurrent = p1 ;
p1 = p1->next ;
}
else
{
pcurrent->next = p2 ;
pcurrent = p2 ;
p2 = p2->next ;
}
}
if ( p1 != NULL )
pcurrent->next = p1 ;
if ( p2 != NULL )
pcurrent->next = p2 ;
return head ;
}

(3)已知兩個鏈表head1 和head2 各自有序，請把它們合并成一個鏈表依然有序瞬内，這次要求用遞歸方法進(jìn)行迷雪。 (Autodesk)

答案：
Node * MergeRecursive(Node *head1 , Node *head2)
{
if ( head1 == NULL )
return head2 ;
if ( head2 == NULL)
return head1 ;
Node *head = NULL ;
if ( head1->data < head2->data )
{
head = head1 ;
head->next = MergeRecursive(head1->next,head2);
}
else
{
head = head2 ;
head->next = MergeRecursive(head1,head2->next);
}
return head ;
}

152.利用鏈表實(shí)現(xiàn)將兩個有序隊(duì)列A和B合并到有序隊(duì)列H中，不準(zhǔn)增加其他空間虫蝶。

請?zhí)峁┤稽c(diǎn)的程序

以升序?yàn)槔?while(a != NULL && b!= NULL)
{
if (a->data < b->data)
{
h->data = a->data;
a = a->next;
}
else if (a->data == b->data)
{
h->data = a->data;
a = a->next;
b = b->next;
}
else
{
h->data = b->data;
b = b->next
}
h = h->next;
}
if (a == NULL)
{
while (b != NULL)
{
h->data = b->data;
h = h->next;
b = b->next;
}
}
else 
{
while(a != NULL)
{
h->data = a->next;
h = h->next;
a = a->next;
}
}

153單向鏈表的反轉(zhuǎn)是一個經(jīng)常被問到的一個面試題章咧，也是一個非常基礎(chǔ)的問題能真。比如一個鏈表是這樣的： 1->2->3->4->5 通過反轉(zhuǎn)后成為5->4->3->2->1赁严。最容易想到的方法遍歷一遍鏈表，利用一個輔助指針粉铐，存儲遍歷過程中當(dāng)前指針指向的下一個元素疼约，然后將當(dāng)前節(jié)點(diǎn)元素的指針反轉(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)當(dāng)前節(jié)點(diǎn)之前先調(diào)用遞歸函數(shù)反轉(zhuǎn)后續(xù)節(jié)點(diǎn)。源代碼如下汤踏。不過這個方法有一個缺點(diǎn)织鲸，就是在反轉(zhuǎn)后的最后一個結(jié)點(diǎn)會形成一個環(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;
     }
}

154 對如下雙鏈表

typedef struct _node
{
int iData;
struct _node *pPrev;
struct _node *pNext;
}node;

a.請寫出代碼，將noden插入到nodep后盾饮。
b.如果多線程同時訪問此鏈表采桃，需要加鎖，請說明以下步驟
(a)申請內(nèi)存給n.
(b)N數(shù)據(jù)初始化丘损。
(c)插入
注意加鎖和解鎖的時機(jī)普办。

node* insert(node* p, node* n)
{
if ((p == NULL) || (n == NULL))
{
return NULL;
}

if (p->pNext != NULL)
{
p->pNext->pPrev = n;
}

n->pPrev = p;
n->pNext = p->pNext;
p->pNext = n;

return n;
}

155、試創(chuàng)建二叉數(shù)徘钥，并寫出常見的幾種遍歷方式 ?

#include "stdio.h"
#include "string.h"
#include <stdlib.h>
#define NULL 0
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

BiTree Create(BiTree T){
    char ch;
    ch=getchar();
    if(ch=='0')
T=NULL;
    else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
    printf("Error!");
T->data=ch;
T->lchild=Create(T->lchild);
T->rchild=Create(T->rchild);
    }
    return T;
}

void Preorder(BiTree T){
     if(T){
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}//先序遍歷

void Inorder(BiTree T){
    if(T){
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}//中序遍歷

void Postorder(BiTree T){
    if(T){
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}//后序遍歷

156衔蹲、前序遍歷輸入，如圖所示,寫出后序遍歷輸出結(jié)果呈础？

例如二叉樹：
輸入序列ABD..EH...CF.I..G..
輸出結(jié)果為：?

答案：
輸出結(jié)果為：DHEBIFGCA

★不用庫函數(shù),用C語言實(shí)現(xiàn)將一整型數(shù)字轉(zhuǎn)化為字符串★

方法1：
int getlen(char *s){
int n;
for(n = 0; *s != '\0'; s++)
n++;
return n;
}
void reverse(char s[])
{
int c,i,j;
for(i = 0,j = getlen(s) - 1; i < j; i++,j--){
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
void itoa(int n,char s[])
{
int i,sign;
if((sign = n) < 0)
n = -n;
i = 0;
do{/*以反序生成數(shù)字*/
s[i++] = n%10 + '0';/*get next number*/
}while((n /= 10) > 0);/*delete the number*/

if(sign < 0)
s[i++] = '-';

s[i] = '\0';
reverse(s);
}

方法2:
#include <iostream>
using namespace std;

void itochar(int num);

void itochar(int num)
{
int i = 0;
int j ;
char stra[10];
char strb[10];
while ( num )
{
stra[i++]=num%10+48;
num=num/10;
}
stra[i] = '\0';
for( j=0; j < i; j++)
{
strb[j] = stra[i-j-1];
}
strb[j] = '\0';
cout<<strb<<endl;

}
int main()
{
int num;
cin>>num;
itochar(num);
return 0;
}

最后編輯于：2018.03.26 14:43:28

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末舆驶，一起剝皮案震驚了整個濱河市，隨后出現(xiàn)的幾起案子而钞，更是在濱河造成了極大的恐慌沙廉，老刑警劉巖，帶你破解...
沈念sama閱讀 218,122評論 6贊 505
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件臼节，死亡現(xiàn)場離奇詭異撬陵，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)网缝，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,070評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門巨税，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人粉臊，你說我怎么就攤上這事草添。” “怎么了扼仲？”我有些...
開封第一講書人閱讀 164,491評論 0贊 354
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵远寸，是天一觀的道長。經(jīng)常有香客問我屠凶，道長驰后，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,636評論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任阅畴，我火速辦了婚禮倡怎，結(jié)果婚禮上迅耘，老公的妹妹穿的比我還像新娘贱枣。我一直安慰自己监署，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,676評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布纽哥。她就那樣靜靜地躺著钠乏，像睡著了一般。火紅的嫁衣襯著肌膚如雪春塌。梳的紋絲不亂的頭發(fā)上晓避，一...
開封第一講書人閱讀 51,541評論 1贊 305
城市分裂傳說
那天，我揣著相機(jī)與錄音只壳，去河邊找鬼俏拱。笑死，一個胖子當(dāng)著我的面吹牛吼句，可吹牛的內(nèi)容都是我干的锅必。我是一名探鬼主播，決...
沈念sama閱讀 40,292評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼惕艳，長吁一口氣：“原來是場噩夢啊……” “哼搞隐！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起远搪，我...
開封第一講書人閱讀 39,211評論 0贊 276
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤劣纲，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后谁鳍，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體癞季，經(jīng)...
沈念sama閱讀 45,655評論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,846評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年棠耕，在試婚紗的時候發(fā)現(xiàn)自己被綠了余佛。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,965評論 1贊 348
活死人
序言：一個原本活蹦亂跳的男人離奇死亡窍荧，死狀恐怖辉巡，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情蕊退，我是刑警寧澤郊楣，帶...
沈念sama閱讀 35,684評論 5贊 347
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站瓤荔，受9級特大地震影響净蚤，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜输硝，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,295評論 3贊 329
男人毒藥：我在死后第九天來索命
文/蒙蒙一今瀑、第九天我趴在偏房一處隱蔽的房頂上張望忘晤。院中可真熱鬧，春花似錦弧轧、人聲如沸矾削。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,894評論 0贊 22
一樁弒父案哥童，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽挺份。三九已至，卻和暖如春贮懈，著一層夾襖步出監(jiān)牢的瞬間匀泊，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 33,012評論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工朵你，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留各聘，地道東北人。一個月前我還...
沈念sama閱讀 48,126評論 3贊 370
代替公主和親
正文我出身青樓抡医，卻偏偏與公主長得像伦吠，于是被迫代替她去往敵國和親。傳聞我的和親對象是個殘疾皇子魂拦，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,914評論 2贊 355