1、計算機考研小組計算機考研小組(100)(100)20102010年計算機考研基礎(chǔ)班講義年計算機考研基礎(chǔ)班講義http:/ 按某種關(guān)系組織起來的一批數(shù)據(jù)。以一按某種關(guān)系組織起來的一批數(shù)據(jù)。以一定的存儲方式把它們存儲到計算機的存儲器定的存儲方式把它們存儲到計算機的存儲器中，并在這些數(shù)據(jù)上定義一個運算集合，這中，并在這些數(shù)據(jù)上定義一個運算集合，這就是數(shù)據(jù)結(jié)構(gòu)。就是數(shù)據(jù)結(jié)構(gòu)。基礎(chǔ)基礎(chǔ) 數(shù)據(jù)指針數(shù)據(jù)域指針域單鏈表結(jié)點結(jié)構(gòu)單鏈表結(jié)點結(jié)構(gòu)typedef struct node et data; struct node *link ; node;結(jié)點的內(nèi)存分配：結(jié)點的內(nèi)存分配： （node *)malloc(

2、sizeof(node)非空表（a)headhead空表（b)headllinkrlinkdata帶頭結(jié)點的雙向鏈表帶頭結(jié)點的雙向鏈表雙向鏈表的結(jié)點結(jié)構(gòu)雙向鏈表的結(jié)點結(jié)構(gòu)40 0 1 00 0 2 0 090 0 0 00 0 0 0 70 0 0 5 0 r c v ma0ma1ma2ma3ma4ma5ma6a=40 9 0 00 0 0 0 00 2 0 0 01 0 0 0 50 0 0 7 0 r c v mb0mb1mb2mb3mb4mb5mb6b= 行域行域 列域列域 值域值域 向下域向下域 向右域向右域棧底bottom棧頂toptop -101234501234501234501

3、2346top top top maxlen-1maxlen-1maxlen-1maxlen-1自由區(qū)lefttoprighttop0maxlen-1a0, a1, a2, a3, a4, ,a i a n-1出隊出隊入隊入隊活動記錄進退棧示意圖活動記錄進退棧示意圖s=fact(1)=1*fact(0)=1s=fact(2)=2*fact(1)=2s=fact(3)=3*fact(2)=6s=fact(4)=4*fact(3)=24s=fact(5)=5*fact(4)=120fact(0)=1調(diào)用者調(diào)用者主函數(shù)mani()n=fact(5)第一層調(diào)用n=5s=5*fact(4)第二層調(diào)用n=

4、4s=4*fact(3)第三層調(diào)用n=3s=3*fact(2)第四層調(diào)用n=2s=2*fact(1)第五層調(diào)用n=1s=1fact(1)=1fact(2)=2fact(3)=6fact(4)=24fact(5)=120輸出s=120.00遞歸調(diào)用過程示意圖遞歸調(diào)用過程示意圖從圖中可看到fact函數(shù)共被調(diào)用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)為主函數(shù)調(diào)用，其它則為在fact函數(shù)內(nèi)調(diào)用。每一次遞歸調(diào)用并未立即得到結(jié)果，而是進一步向深度遞歸調(diào)用，直到n=1或n=0時，函數(shù)fact結(jié)果為1，然后再一一返回計算，最終得到結(jié)果。例例

5、漢諾塔漢諾塔傳說在創(chuàng)世紀(jì)時，在一個叫傳說在創(chuàng)世紀(jì)時，在一個叫brahmabrahma的寺廟里，有三個柱子，其中的寺廟里，有三個柱子，其中一柱上有一柱上有6464個盤子從小到大依次疊放，僧侶的工作是將這個盤子從小到大依次疊放，僧侶的工作是將這6464個盤個盤子從一根柱子移到另一個柱子上。子從一根柱子移到另一個柱子上。 移動時的規(guī)則：移動時的規(guī)則： 每次只能移動一個盤子；每次只能移動一個盤子； 只能小盤子在大盤子上面；只能小盤子在大盤子上面； 可以使用任一柱子。可以使用任一柱子。當(dāng)工作做完之后，就標(biāo)志著世界永遠和平。當(dāng)工作做完之后，就標(biāo)志著世界永遠和平。x y zx y znn 1分析：分析： 設(shè)三根柱子分別為設(shè)三根柱子分別為 x x，y, z , y, z , 盤子在盤子在x x柱上，要移到柱上，要移到z z柱上。柱上。1 1、當(dāng)、當(dāng)n=1n=1時，盤子直接從時，盤子直接從 x x 柱移到柱移到 z z 柱上；柱上；2 2、當(dāng)、當(dāng)n1n1時時, , 則則設(shè)法將前設(shè)法將前n n1 1個盤子借助個盤