通信原理大綜合課件軟件

1數(shù)據(jù)結(jié)構(gòu)與算法

2

○學(xué)習(xí)的目的：為了分析待處理的對象的特性以及各處理對象之間的存在關(guān)系。

概述2.1學(xué)習(xí)目的因此，簡單說來，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作等的學(xué)科。

3

2．1．1數(shù)據(jù)結(jié)構(gòu)對數(shù)據(jù)處理的重要性數(shù)據(jù)結(jié)構(gòu)可描述為Group=（D，R）學(xué)生成績查詢學(xué)號姓名成績9861109張卓1009861107劉忠賞959861103胡孝臣86交通路燈問題4

數(shù)據(jù):所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號集合.數(shù)據(jù)元素:

數(shù)據(jù)的基本單位,也稱結(jié)點(diǎn)或記錄.數(shù)據(jù)結(jié)構(gòu):

相互間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合.

基本概念5

數(shù)據(jù)結(jié)構(gòu)：由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。記為：

Data_Structure={D,R}

其中，D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是一門研究數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法的學(xué)科。6

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A.線性結(jié)構(gòu)B.非線性結(jié)構(gòu)A.順序存儲(chǔ)

B.鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)2．1．2數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)主要問題：7

集合:數(shù)據(jù)元素之間屬于一個(gè)集合,別無其他關(guān)系.

線性結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素存在一個(gè)對一個(gè)的關(guān)系.

樹結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素存在一個(gè)對多個(gè)的關(guān)系.

圖結(jié)構(gòu):結(jié)構(gòu)中的數(shù)據(jù)元素存在多個(gè)對多個(gè)的關(guān)系.1234數(shù)據(jù)的邏輯結(jié)構(gòu)8

樹形結(jié)構(gòu)例子——結(jié)點(diǎn)間具有分層次的連接關(guān)系HBCDEFGA9

1423

D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213

D={1,2,3}R={<1,2>,<2,3>,<3,2>,<1,3>}

圖形結(jié)構(gòu)例子——結(jié)點(diǎn)間的連結(jié)是任意的10

元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m數(shù)據(jù)的順序存儲(chǔ)11

1536元素21400元素11346元素3∧元素41345存儲(chǔ)地址存儲(chǔ)內(nèi)容指針

1345元素1

1400

1346元素4∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1346h數(shù)據(jù)的鏈?zhǔn)酱鎯?chǔ)12

????????????

程序＝算法＋數(shù)據(jù)結(jié)構(gòu)

程序設(shè)計(jì)的實(shí)質(zhì)是選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)一個(gè)好的算法。算法取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。13

2.1.3算法的基本概念

1算法：是對特定問題求解步驟的一種描述。算法的四個(gè)特性：有窮性確定性可行性有輸出14

12Voidexam1(){n=2;while(n%2==0)n=n+2;printf(“%d\n”,n);}Voidexam2(){y=0;x=5/y;printf(“%d%d”,x,y);}15

評價(jià)算法：正確性、易讀性、健壯性、運(yùn)行時(shí)間及占用空間。

正確性：正確與否可讀性：容易閱讀健壯性：容錯(cuò)處理效率和低存儲(chǔ)量需求：

和算法執(zhí)行時(shí)間相關(guān)的因素有：1）算法所用“策略”；2）算法所解問題的“規(guī)?！?；3）編程所用“語言”；4）“編譯”的質(zhì)量；5）執(zhí)行算法的計(jì)算機(jī)的"速度"。16

for(i=1;i<=n;i++)/*n+1*/for(j=1;j<=n;j++)/*n*(n+1)*/{c[i][j]=0;/*n2*/for(k=1;k<=n;k++)/*n2(n+1)*/c[i][j]=c[i][j]+a[i][k]*b[k][j];/*n3*/}T(n)=2n3+3n2+2n+1兩個(gè)n階矩陣相乘的算法2算法的復(fù)雜度：時(shí)間復(fù)雜度：評估算法的時(shí)間增長趨勢。影響運(yùn)行時(shí)間的因素：語句執(zhí)行的次數(shù)(頻度)

執(zhí)行每行語句所需的時(shí)間(與算法無關(guān))T(n)=2n3+3n2+2n+1當(dāng)n趨向充分大時(shí)，T(n)/n3的值趨于常數(shù)算法時(shí)間復(fù)雜度表示為T(n)=O(n3)17

當(dāng)問題的規(guī)模n趨于無窮大時(shí)，把時(shí)間復(fù)雜度T(n)的數(shù)量級（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度（有時(shí)簡稱為時(shí)間復(fù)雜度）。

嚴(yán)格的數(shù)學(xué)定義為：若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，當(dāng)存在兩個(gè)正的乘數(shù)C和n0時(shí)，使得對所有的成立，則都有這時(shí)稱T(n)的時(shí)間復(fù)雜度為f(n)數(shù)量級。18

例：x=0;y=0;for(k=1;k<=n;k++)x++;for(i=1;i<=n;i++)for(j=1;j<=n;j++)//n*ny++;一般情況下，對步進(jìn)循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，而忽略循環(huán)體中步長加1、終值判斷、控制轉(zhuǎn)移等成分。時(shí)間復(fù)雜度是以算法中頻度最大的語句來衡量。19

voidselect_sort(inta[],intn)

{

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

for(i=0;i<n-1;++i){

j=i;

for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;

if(j!=i){w=a[j];a[j]=a[i];a[i]=w;}}

}20

例：x=1;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x++;21??????Ⅰ

1

2如果算法的執(zhí)行時(shí)間是一個(gè)與問題規(guī)模n無關(guān)的常數(shù)，則算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。空間復(fù)雜度：指算法中所需的輔助空間單元。交換i和j的內(nèi)容。Temp=i;i=j