課件計(jì)算機(jī)考研基礎(chǔ)講義數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

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

2、sizeof(node)非空表（a)headhead空表（b)headllinkrlinkdata帶頭結(jié)點(diǎn)的雙向鏈表帶頭結(jié)點(diǎn)的雙向鏈表雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)雙向鏈表的結(jié)點(diǎn)結(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出隊(duì)出隊(duì)入隊(duì)入隊(duì)活動(dòng)記錄進(jìn)退棧示意圖活動(dòng)記錄進(jìn)退棧示意圖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)用過(guò)程示意圖遞歸調(diào)用過(guò)程示意圖從圖中可看到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é)果，而是進(jìn)一步向深度遞歸調(diào)用，直到n=1或n=0時(shí)，函數(shù)fact結(jié)果為1，然后再一一返回計(jì)算，最終得到結(jié)果。例例

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