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

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

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的存儲(chǔ)包括數(shù)據(jù)元素的存儲(chǔ)和元素之間的關(guān)系的表示。元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的表示方法：順序映像和非順序映像。由此得出兩種不同的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序映像的特點(diǎn)：用數(shù)據(jù)元素在存儲(chǔ)器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)。

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

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

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

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

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

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

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

{++x;s+=x;}

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

，其時(shí)間復(fù)雜度為：O(n2)

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

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

空間復(fù)雜度：是指算法編寫成程序后，在計(jì)算機(jī)中運(yùn)行時(shí)所需存儲(chǔ)空間大小的