游戲案例分析(1)-數(shù)據(jù)結構和算法

1游戲案例分析2課程考核總學時：48學時考核方式：階段性考核成績比例：平時15%，實驗25%，期末60%3課程主要內(nèi)容簡介主要內(nèi)容：線性表鏈表棧隊列二叉樹設計模式泛型編程、模板、STL容器、向量與迭代器4緒論主要內(nèi)容：什么是數(shù)據(jù)結構根本概念和術語算法和算法分析5數(shù)據(jù)結構：是指相互之間具有(存在)一定聯(lián)系(關系)的數(shù)據(jù)元素的集合。元素之間的相互聯(lián)系(關系)稱為〔邏輯〕結構。數(shù)據(jù)元素之間的邏輯結構有4種根本類型，如下所示。①集合：結構中的數(shù)據(jù)元素除了“同屬于一個集合〞外，沒有其它關系。②線性結構：結構中的數(shù)據(jù)元素之間存在一對一的關系。③樹型結構：結構中的數(shù)據(jù)元素之間存在一對多的關系。④圖狀結構或網(wǎng)狀結構：結構中的數(shù)據(jù)元素之間存在多對多的關系。數(shù)據(jù)結構的概念6集合線性樹圖7邏輯結構與物理結構數(shù)據(jù)元素之間的關系可以是元素之間代表某種含義的自然關系，也可以是為處理問題方便而人為定義的關系，這種“關系〞稱為數(shù)據(jù)元素之間的邏輯關系，相應的結構稱為邏輯結構。數(shù)據(jù)結構在計算機中的表示〔又稱映像〕稱為數(shù)據(jù)的物理結構，又稱存儲結構。8數(shù)據(jù)結構的存儲方式

數(shù)據(jù)結構在計算機內(nèi)存中的存儲包括數(shù)據(jù)元素的存儲和元素之間的關系的表示。元素之間的關系在計算機中有兩種不同的表示方法：順序映像和非順序映像。由此得出兩種不同的存儲結構：順序存儲結構和鏈式存儲結構。順序映像的特點：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結構(關系)。

非順序映像的特點：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer)，用該指針來表示數(shù)據(jù)元素之間的邏輯結構(關系)。9

數(shù)據(jù)的邏輯結構和物理結構是密不可分的兩個方面，一個算法的設計取決于所選定的邏輯結構，而算法的實現(xiàn)依賴于所采用的存儲結構。在C語言中，用一維數(shù)組表示順序存儲結構；用結構體類型表示鏈式存儲結構。例：設有數(shù)據(jù)集合A={3.0,2.3,5.0,-8.5,11.0}，兩種不同的存儲結構。順序結構：數(shù)據(jù)元素存放的地址是連續(xù)的；鏈式結構：數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求?？煞癞嫵鍪疽鈭D？10數(shù)據(jù)結構的三個組成局部：邏輯結構：數(shù)據(jù)元素之間邏輯關系的描述。存儲結構：數(shù)據(jù)元素在計算機中的存儲。數(shù)據(jù)操作：對數(shù)據(jù)要進行的運算。

11數(shù)據(jù)的邏輯結構非線性結構集合圖狀結構有向圖無向圖樹形結構一般樹二叉樹線性結構一般線性表線性表推廣廣義表數(shù)組串受限線性表棧和隊列數(shù)據(jù)邏輯結構層次關系圖線性表樹圖順序存儲結構鏈式存儲結構復合存儲結構邏輯結構物理結構12算法：是對特定問題求解方法(步驟)的一種描述。算法和算法分析13算法的五個重要特性①有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內(nèi)完成。②確定性：算法中每一條指令必須有確切的含義。不存在二義性。③可行性：一個算法是能行的。即算法描述的操作都可以通過已經(jīng)實現(xiàn)的根本運算執(zhí)行有限次來實現(xiàn)。④輸入：一個算法有零個或多個輸入。⑤輸出：一個算法有一個或多個輸出。14設計一個好的算法應考慮到達以下目標：①正確性：算法應滿足具體問題的需求。②可讀性：算法應容易供人閱讀和交流?？勺x性好的算法有助于對算法的理解和修改。③健壯性：算法應具有容錯處理。當輸入非法或錯誤數(shù)據(jù)時，算法應能適當?shù)刈鞒龇错懟蜻M行處理，而不會產(chǎn)生莫名其妙的輸出結果。④效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般地，這兩者與問題的規(guī)模有關。算法設計的要求15

算法執(zhí)行時間需通過依據(jù)該算法編制的程序在計算機上運行所消耗的時間來度量。其方法通常有兩種：事后統(tǒng)計：計算機內(nèi)部進行執(zhí)行時間和實際占用空間的統(tǒng)計。

缺陷：必須先運行依據(jù)算法編制的程序；依賴軟硬件環(huán)境，容易掩蓋算法本身的優(yōu)劣；沒有實際價值。事前分析：求出該算法的一個時間界限函數(shù)。算法效率的度量16與此相關的因素有：依據(jù)算法選用何種策略；問題的規(guī)模；程序設計的語言；編譯程序所產(chǎn)生的機器代碼的質(zhì)量；機器執(zhí)行指令的速度；撇開軟硬件等有關部門因素，可以認為一個特定算法“運行工作量〞的大小，只依賴于問題的規(guī)?！餐ǔＳ胣表示〕，或者說，它是問題規(guī)模的函數(shù)。17算法分析應用舉例算法中根本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作：T(n)=O(f(n))，稱作算法的漸近時間復雜度，簡稱時間復雜度。一般地，常用最深層循環(huán)內(nèi)的語句中的原操作的執(zhí)行頻度(重復執(zhí)行的次數(shù))來表示。18表示時間復雜度的階有：O(1)：常量階O(n)：線性階O(㏒n)：對數(shù)階O(2n)：指數(shù)階O(n2)：平方階O(n㏒n)：線性對數(shù)階O(nk)：k≥2，k次方階〔多項式階〕19例１兩個n階方陣的乘法for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}由于是一個三重循環(huán)，每個循環(huán)從1到n，那么總次數(shù)為：n×n×n=n3時間復雜度為T(n)=O(n3)20例２{++x;s=0;}將x自增看成是根本操作，那么語句頻度為１，即時間復雜度為O(1)。如果將s=0也看成是根本操作，那么語句頻度為２，其時間復雜度仍為O(1)，即常量階。21例３for(i=1;i<=n;++i)

{++x;s+=x;}語句頻度為：2n，其時間復雜度為：O(n)，即為線性階。22例４for(i=1;i<=n;++i)

for(j=1;j<=n;++j)

{++x;s+=x;}

語句頻度為：2n*n=2n2

，其時間復雜度為：O(n2)

，即為平方階。23定理：假設A(n)=amnm+am-1nm-1+…+a1n+a0是一個m次多項式，那么A(n)=O(nm)例５for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i,j]=x;}語句頻度為：1+2+3+…+n-2=(1+n-2)×(n-2)/2=(n-1)(n-2)/2=1/2n2-3/2n+1∴時間復雜度為O(n2)，即此算法的時間復雜度為平方階。一個算法時間為O(1)的算法，它的根本運算執(zhí)行的次數(shù)是固定的。因此，總的時間由一個常數(shù)〔即零次多項式〕來限界。而一個時間為O(n2)的算法那么由一個二次多項式來限界。24以下六種計算算法時間的多項式是最常用的。其關系為：O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)指數(shù)時間的關系為：O(2n)<O(n!)<O(nn)當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊。因此，只要有人能將現(xiàn)有指數(shù)時間算法中的任何一個算法化簡為多項式時間算法，那就取得了一個偉大的成就。有的情況下，算法中根本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同。25例1：素數(shù)的判斷算法。voidprime(intn)/*n是一個正整數(shù)*/{inti=2;while((n%i)!=0&&i*1.0<sqrt(n))i++;if(i*1.0>sqrt(n))printf(“&d是一個素數(shù)\n〞,n);elseprintf(“&d不是一個素數(shù)\n〞,n);}嵌套的最深層語句是i++；其頻度由條件((n%i)!=0&&i*1.0<sqrt(n))決定，顯然i*1.0<sqrt(n)，時間復雜度O(n1/2)。26例2：冒泡排序法。Voidbubble_sort(inta[]，intn){change=false;for(i=n-1;change=TURE;i>1&&change;--i)for(j=0;j<i;++j)if(a[j]>a[j+1]){a[j]←→a[j+1];change=TURE;}}

最好情況：0次最壞情況：1+2+3+?+n-1=n(n-1)/2

平均時間復雜度為：O(n2)27算法的空間分析

空間復雜度：是指算法編寫成程序后，在計算機中運行時所需存儲空間大小的