程序員考試下午試題程序填空解題方法

字號(hào):

一、步驟
     1、理解題意:
     主要是根據(jù)問題的描述,確定問題的已知條件,并了解算法(程序)要達(dá)到的目的。通俗講,就是要知道問題的輸入和輸出。
     2、確定算法:
     每個(gè)題目在前面都有描述,通過對(duì)描述的分析,要確定題目應(yīng)該屬于哪一類數(shù)據(jù)結(jié)構(gòu)以及相應(yīng)的算法。有些題目可能不屬于任何數(shù)據(jù)結(jié)構(gòu),則它可能與某類算法(8類)有關(guān);但也有一些算法純粹是數(shù)學(xué)方法。
     在描述中同時(shí)要理解算法過程。在分析算法時(shí),可以以某個(gè)具體實(shí)例來試驗(yàn)。
     3、理解程序:
     分析程序結(jié)構(gòu),如果有很多子函數(shù),首先弄清楚各函數(shù)之間的關(guān)系和各函數(shù)的作用;如果程序較長(zhǎng),則應(yīng)該根據(jù)算法過程,把每個(gè)程序段與算法的每個(gè)過程對(duì)應(yīng)起來,確定相應(yīng)的程序段功能。
     在程序中,已經(jīng)定義了某些變量,則在理解程序時(shí),首先必須理解這些變量的含義
     4、根據(jù)C語(yǔ)言的語(yǔ)法填空。
     二、示例
     【示例】2004年上半年程序員下午試題試題六
     [函數(shù)說明]
     函數(shù)DelAInsB(LinkedList La,LinkedList lb,int key1,int key2,int len)的功能是,將線性表A中關(guān)鍵碼為keyl的結(jié)點(diǎn)開始的len個(gè)結(jié)點(diǎn),按原順序移至線性表B中關(guān)鍵碼為key2的結(jié)點(diǎn)之前,若移動(dòng)成功,則返回0;否則返回-1。線性表的存儲(chǔ)結(jié)構(gòu)為帶頭結(jié)點(diǎn)的單鏈表,La為表A的頭指針,Lb為表B的頭指針。單鏈表結(jié)點(diǎn)的類型定義為:
     typedef struct node{
     int key;
     struct node*next;
     }*Linkedhist;
     [函數(shù)]
    (1) int DelllnsB(LinkedLiSt La,LinkedList Lb,int keyl,int key2,int len)
    (2) { LinkedList ?p,q,s,prep,pres;
    (3)  int k;
    (4)  if (!La->next || !Lb->next || len<=0) return-1;
    (5)  p = La->next; prep = La;
    (6)  while (p && p->key != keyl) { /* 查找表A中鍵值為key1的結(jié)點(diǎn) */(7)   prep = p;p = p->next;
    (8)  }
    (9)  if (!p) return -1; /* 表A中不存在鍵值為key1的結(jié)點(diǎn) */
    (10)  q = p; k = 1;
    (11)  while (q && __(1)__) { /* 在表A中找出待刪除的len個(gè)結(jié)點(diǎn) */
    (12)   __(2)__; k++;
    (13)  }
    (14)  if (!q) return -1; /* 表A中不存在要被刪除的len個(gè)結(jié)點(diǎn) */
    (15)  s = Lb->next; __(3)__;
    (16)  while (s && s->key != key2) { /* 查找表B中鍵值為key2的結(jié)點(diǎn) */(17)   pres = s; s = s->next;
    (18)  }
    (19)  if (!s) return -1; /* 表B中不存在鍵值為key2的結(jié)點(diǎn) */
    (20)  __(4)__ =q->next; /* 將表A中的len個(gè)結(jié)點(diǎn)刪除 */
    (21)  q->next= ??(5) ;
    (22)  pres->next = p; /* 將len個(gè)結(jié)點(diǎn)移至表B */
    (23)  return 0;
    (24)  }
     1、理解題目:
     已知條件為兩個(gè)鏈表La和Lb,最后得到的結(jié)果也是兩個(gè)鏈表,只不過是La中的部分結(jié)點(diǎn)移動(dòng)到Lb中,因此,本問題主要是解決是怎么移動(dòng)的。
     2、算法:
     在題目中沒有給出結(jié)點(diǎn)移動(dòng)的算法,我們先可以結(jié)合實(shí)例自己設(shè)計(jì)一個(gè)算法,然后看是不是與程序中的算法一致。如果不是,則再找算法。
     實(shí)例:
    如圖所示,如果我們找到實(shí)線的指針,它們分別指向La中的Key1結(jié)點(diǎn)(p指針)、Key1的前一個(gè)結(jié)點(diǎn)(q指針)、Aj(從Key1結(jié)點(diǎn)開始的第len個(gè)結(jié)點(diǎn),r指針)和Lb中的Key2的前一個(gè)結(jié)點(diǎn)(s指針),則根據(jù)鏈表操作,用圖中的虛線指針連接,我們就可以把La中從Key1結(jié)點(diǎn)開始的共len個(gè)結(jié)點(diǎn)全部移動(dòng)到Lb鏈表中。因此算法大致如下:
     (1)找到p和q指針;
     (2)找到r指針;
     (3)找到s指針;
     (4)r->next=s->next(即把Aj結(jié)點(diǎn)連接到K2結(jié)點(diǎn)之前);
     (5)s->next=q(即把K1結(jié)點(diǎn)連接到原來Lb中K2結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的后面);
      注意:經(jīng)過(4)、(5)兩步操作,即實(shí)現(xiàn)了移動(dòng)操作。
     (6)要注意的是現(xiàn)在La鏈表已經(jīng)斷開,也必須重新連接上,故要:
     但是注意一下程序,就會(huì)發(fā)現(xiàn)里面有很多判斷,主要是看判斷是否可以移動(dòng)。我們考慮后(也可以看程序)發(fā)現(xiàn),在以下幾種情況下,操作不能進(jìn)行:
     (1)La或Lb是空鏈表;
     (2)len表示個(gè)數(shù)的值,因此不能不大于0;
     (3)La中不存在Key1的結(jié)點(diǎn);
     (4)La中從Key1結(jié)點(diǎn)開始的結(jié)點(diǎn)個(gè)數(shù)小于len個(gè);
     (4)Lb中不存在Key2的結(jié)點(diǎn);
     3、現(xiàn)在主要是看程序結(jié)構(gòu)是不是和我們自己考慮的算法符合。
     程序段(5)~(8):其中有p指針在向后移動(dòng),一直到Key1為止,因此,它們的功能就是找到指向Key1結(jié)點(diǎn)的指針;同時(shí),另有一個(gè)指針prep一直在p的后面,因此它就是指向Key1的前一個(gè)結(jié)點(diǎn)的指針。
     程序段(10)~(13):其中有一個(gè)k變量,每次循環(huán)后增加1,因此它是一個(gè)計(jì)數(shù)器。通過計(jì)數(shù)len次,就可以找到從Key1結(jié)點(diǎn)開始的第len個(gè)結(jié)點(diǎn)。這時(shí),應(yīng)該有一個(gè)指針(q)同時(shí)移動(dòng),使得這個(gè)指針就是指向第len個(gè)結(jié)點(diǎn)的指針。
     程序段(15)~(18):其中有s指針在向后移動(dòng),一直到Key2為止,因此,它們的功能就是找到指向Key2的前一個(gè)結(jié)點(diǎn)的指針。
     程序段(20)~(22):就是移動(dòng)La中的結(jié)點(diǎn)到Lb,并把La中斷開的鏈表連接。從上述的分析發(fā)現(xiàn),程序結(jié)構(gòu)是和我們自己考慮的算法一致的。
     4、考慮細(xì)節(jié),并填空。
    (1)我們的目的是找指向第len個(gè)結(jié)點(diǎn)的指針,找到后循環(huán)應(yīng)該結(jié)束,因此,要填k ?。?)q指針應(yīng)該同時(shí)移動(dòng),故應(yīng)填:q=q->next
    (3)這一段程序的功能是找到指向Key2的前一個(gè)結(jié)點(diǎn)的指針。其中s指針是指向Key2結(jié)點(diǎn)的,而pres指針跟在s后面。但是pres指針缺少初值,因此,這兒應(yīng)該給pres賦值。故,應(yīng)填:pres=Lb。
    (4)程序塊(20)、(21)、(22)的功能是移動(dòng)La中的結(jié)點(diǎn)到Lb,并把La中斷開的鏈表連接。根據(jù)鏈表操作的方法,顯然(20)是把La中斷開的鏈表連接,因此,(4)應(yīng)該填:prep->next;而(21)、(22)是移動(dòng)La中的結(jié)點(diǎn)到Lb,因此,(5)應(yīng)該填:pres->next。