課件計算機考研基礎講義數(shù)據(jù)結構基礎

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

2、sizeof(node)非空表（a)headhead空表（b)headllinkrlinkdata帶頭結點的雙向鏈表帶頭結點的雙向鏈表雙向鏈表的結點結構雙向鏈表的結點結構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調用者調用者主函數(shù)mani()n=fact(5)第一層調用n=5s=5*fact(4)第二層調用n=

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

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