數(shù)據(jù)結(jié)構(gòu)（C語言版）市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)?wù)n件

數(shù)據(jù)結(jié)構(gòu)（C語言版）數(shù)據(jù)結(jié)構(gòu)（C語言版）第1頁簡介《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)專業(yè)一門專業(yè)基礎(chǔ)課，在計(jì)算機(jī)學(xué)科中起著承上啟下作用，在計(jì)算機(jī)技術(shù)各個(gè)領(lǐng)域也有著廣泛應(yīng)用。學(xué)習(xí)這門課需要程序設(shè)計(jì)語言作為其基礎(chǔ)，學(xué)習(xí)前要有比較扎實(shí)程序設(shè)計(jì)基本功（這部分內(nèi)容本課程中將不予包括），同時(shí)又為后續(xù)數(shù)據(jù)庫等一系列課程提供知識(shí)基礎(chǔ)?！稊?shù)據(jù)結(jié)構(gòu)》這門課程包括數(shù)據(jù)組織、存放以及運(yùn)算普通方法。希望經(jīng)過這門課學(xué)習(xí)，掌握數(shù)據(jù)結(jié)構(gòu)基本概念，掌握求解問題思緒與方法，具備數(shù)據(jù)抽象能力。數(shù)據(jù)結(jié)構(gòu)（C語言版）第2頁數(shù)值問題和非數(shù)值問題比較

數(shù)值問題

對(duì)象：len，wide，area——用數(shù)值表示

對(duì)象之間關(guān)系：

area=lenwide，可用方程或函數(shù)表示。數(shù)據(jù)存放：可用程序設(shè)計(jì)語言中實(shí)型變量存放數(shù)據(jù)。

非數(shù)值問題

對(duì)象：課程——用課程名表示

對(duì)象之間關(guān)系：課程間有“次序”關(guān)系（不能用方程或函數(shù)表示，可用圖來表示）

數(shù)據(jù)存放：數(shù)據(jù)及數(shù)據(jù)之間關(guān)系存放。數(shù)據(jù)結(jié)構(gòu)（C語言版）第3頁第一章緒論學(xué)習(xí)關(guān)鍵點(diǎn)熟悉數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)等基本概念，尤其是數(shù)據(jù)邏輯結(jié)構(gòu)與物理結(jié)構(gòu)概念及其關(guān)系。了解算法定義、算法特征、算法時(shí)間代價(jià)、算法空間代價(jià)。掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度方法。數(shù)據(jù)結(jié)構(gòu)（C語言版）第4頁1.1概述1.2數(shù)據(jù)結(jié)構(gòu)基本概念1.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型1.4算法第一章緒論數(shù)據(jù)結(jié)構(gòu)（C語言版）第5頁1.1概述計(jì)算機(jī)解題步驟詳細(xì)問題數(shù)學(xué)模型算法編程、調(diào)試數(shù)據(jù)處理種類和能力數(shù)(整數(shù),實(shí)數(shù))字符、字符串、文字、圖形、圖象、聲音數(shù)值數(shù)據(jù)

非數(shù)值數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)（C語言版）第6頁1.2數(shù)據(jù)結(jié)構(gòu)基本概念數(shù)據(jù)：是對(duì)客觀事物符號(hào)表示。學(xué)號(hào)姓名語文數(shù)學(xué)C語言601張三855492602李四928464603王五877473604...例：張三C語言考試成績?yōu)?2分，92就是該同學(xué)成績數(shù)據(jù)。數(shù)據(jù)結(jié)構(gòu)（C語言版）第7頁數(shù)據(jù)元素是數(shù)據(jù)基本單位。在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮和處理。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割最小單位。數(shù)據(jù)對(duì)象是性質(zhì)相同數(shù)據(jù)元素集合。一個(gè)數(shù)據(jù)項(xiàng)一個(gè)數(shù)據(jù)元素學(xué)號(hào)姓名語文數(shù)學(xué)C語言601張三855492602李四928464603王五877473604...整個(gè)表統(tǒng)計(jì)是學(xué)生成績數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)（C語言版）第8頁數(shù)據(jù)結(jié)構(gòu)是相互之間存在一個(gè)或各種特定關(guān)系數(shù)據(jù)元素之間集合。數(shù)據(jù)結(jié)構(gòu)分類線性結(jié)構(gòu):元素間為嚴(yán)格一對(duì)一關(guān)系。 如上面成績表中各元素集合:元素間為渙散關(guān)系。數(shù)據(jù)結(jié)構(gòu)（C語言版）第9頁樹形結(jié)構(gòu)：元素間為嚴(yán)格一對(duì)多關(guān)系圖狀結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu)):元素間為多對(duì)多關(guān)系數(shù)據(jù)結(jié)構(gòu)（C語言版）第10頁數(shù)據(jù)結(jié)構(gòu)形式定義為：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：Data-Structure=（D，R）有限個(gè)數(shù)據(jù)元素集合有限個(gè)節(jié)點(diǎn)間關(guān)系集合例4為畢業(yè)設(shè)計(jì)小組設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)。假設(shè)每個(gè)小組關(guān)系由一名教師指導(dǎo)一到十名學(xué)生。則數(shù)據(jù)結(jié)構(gòu)二元組表示以下：

Group=(P,R)

其中：P＝｛T,G1,…,Gn｝1≤n≤10

R＝｛<T,Gi>|1≤i≤n,1≤n≤10｝數(shù)據(jù)結(jié)構(gòu)（C語言版）第11頁邏輯結(jié)構(gòu)：“數(shù)據(jù)結(jié)構(gòu)”定義中“關(guān)系”指數(shù)據(jù)間邏輯關(guān)系，故也稱數(shù)據(jù)結(jié)構(gòu)為邏輯結(jié)構(gòu)。物理結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中表示稱為物理結(jié)構(gòu)。又稱存放結(jié)構(gòu)。計(jì)算機(jī)中存放信息最小單位：位，8位為一字節(jié)，兩個(gè)字節(jié)為一字，字節(jié)、字或更多二進(jìn)制位可稱為位串。次序結(jié)構(gòu)（元素在存放器中相對(duì)位置）鏈?zhǔn)浇Y(jié)構(gòu)（元素地址指針）數(shù)據(jù)結(jié)構(gòu)（C語言版）第12頁元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存放地址存放內(nèi)容Loc(a)=Lo+（i-1)*m次序存放每個(gè)元素所占用存放單元個(gè)數(shù)全部元素存放在一片連續(xù)存貯單元中，邏輯上相鄰元素存放到計(jì)算機(jī)內(nèi)存依然相鄰。數(shù)據(jù)結(jié)構(gòu)（C語言版）第13頁1536元素21400元素11346元素3∧元素41345h鏈?zhǔn)酱娣?/p>

每個(gè)節(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身數(shù)據(jù)，指針域存放指針。數(shù)據(jù)元素之間邏輯上聯(lián)絡(luò)由指針來表達(dá)。全部元素存放在能夠不連續(xù)存貯單元中，但元素之間關(guān)系能夠經(jīng)過地址確定，邏輯上相鄰元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰。數(shù)據(jù)結(jié)構(gòu)（C語言版）第14頁數(shù)據(jù)類型：是一個(gè)值集合和定義在這個(gè)值集上一組操作總稱。比如，C語言中整形變量: 其值為某個(gè)區(qū)間上整數(shù)，定義在其上操作為：加、減、乘、除和取模等算術(shù)運(yùn)算。分類：(按值不一樣特征)原子類型：每一個(gè)對(duì)象僅由單值組成類型；結(jié)構(gòu)類型：每一個(gè)對(duì)象可由若干成份按某種 結(jié)構(gòu)組成類型。1.3數(shù)據(jù)類型和抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)（C語言版）第15頁抽象數(shù)據(jù)類型（ADT）作用：抽象數(shù)據(jù)類型能夠使我們更輕易描述實(shí)際問題。 例：用線性表描述學(xué)生成績表，用樹或圖描述遺傳關(guān)系。定義：一個(gè)數(shù)學(xué)模型以及定義在該模型上一組操作。好處：可提升軟件復(fù)用程度。

使用它人能夠只關(guān)心它邏輯特征，不需要了解它存放方式。定義它人一樣無須要關(guān)心它怎樣存放。數(shù)據(jù)結(jié)構(gòu)（C語言版）第16頁例：線性表這么抽象數(shù)據(jù)類型，其數(shù)學(xué)模型是：數(shù)據(jù)元素集合，該集合內(nèi)元素有這么關(guān)系：除第一個(gè)和最終一個(gè)外，每個(gè)元素有唯一前趨和唯一后繼。能夠有這么一些操作：插入一個(gè)元素、刪除一個(gè)元素等。原子類型值不可分解，如int固定聚合類型值由確定數(shù)目成分按某種結(jié)構(gòu)組成，如復(fù)數(shù)可變聚合類型值成份數(shù)目不確定，如學(xué)生基本情況抽象數(shù)據(jù)類型分類數(shù)據(jù)結(jié)構(gòu)（C語言版）第17頁抽象數(shù)據(jù)類型表示法：一、三元組表示：（D，S，P） 其中D是數(shù)據(jù)對(duì)象，S是D上關(guān)系集，P是對(duì)D基本操作集。二、抽象數(shù)據(jù)類型定義格式： ADT抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象定義> 數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系定義> 基本操作：<基本操作定義> }ADT抽象數(shù)據(jù)類型名數(shù)據(jù)結(jié)構(gòu)（C語言版）第18頁抽象數(shù)據(jù)類型表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型能夠經(jīng)過固有數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來表示和實(shí)現(xiàn)。注1：它有些類似C語言中結(jié)構(gòu)（struct）類型，但增加了相關(guān)服務(wù)。注2：教材中用是類C語言（介于偽碼和C語言之間）作為描述工具。其描述語法見P10-11。數(shù)據(jù)結(jié)構(gòu)（C語言版）第19頁算法定義ispass(intnum[4][4]){inti,j;

for(i=0;i<4;i++) for(j=0;j<4;j++)

if(num[i][j]!=i*4+j+1) return0;return1;

}/*類似華容道游戲中判斷游戲是否結(jié)束算法*/

定義：算法是對(duì)特定問題求解步驟一個(gè)描述，是指令有限序列，其中每條指令表示一個(gè)或多個(gè)操作。

1.4算法數(shù)據(jù)結(jié)構(gòu)（C語言版）第20頁算法特征有窮性：算法必須在有限步內(nèi)結(jié)束；確定性：組成算法操作必須清楚無二義性?？尚行裕航M成算法操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)。輸入：0個(gè)或多個(gè)輸入；輸出：1個(gè)或多個(gè)輸出；有窮性haha()

{/*onlyajoke,donothing.*/

}

main()

{printf("請(qǐng)稍等...您將知道世界未日...");

while(1)

haha();

}確定性floataverage(int*a,intnum)

{inti;longsum=0;

for(i=0;i<num;i++)

sum+=*(a++);

returnsum/num;

}

main()

{intscore[10]={1,2,3,4,5,6,7,8,9,0};

printf("%f",average(score,10);

}輸出getsum(intnum)

{

inti,sum=0;

for(i=1;i<=num;i++)

sum+=i;

}/*無輸出算法沒有任何意義，數(shù)據(jù)結(jié)構(gòu)（C語言版）第21頁正確性可讀性健壯性效率與低存放量需求程序不含語法錯(cuò)誤。max(inta,intb,intc)

{

if(a>b)

{if(a>c)returnc;

elsereturna;

}

}程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求結(jié)果。max(inta,intb,intc)

{

if(a>b)

{if(a>c)returna;

elsereturnc;

}

}/*8,6,7*//*9,3,2*/程序?qū)τ诰倪x擇經(jīng)典、苛刻輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求結(jié)果。max(inta,intb,intc)

{

if(a>b){

if(a>c)returna;elsereturnc;}

else{

if(b>c)returnb;elsereturnc;}

}程序?qū)τ谝磺姓?dāng)輸入數(shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求結(jié)果。算法設(shè)計(jì)要求數(shù)據(jù)結(jié)構(gòu)（C語言版）第22頁算法效率度量算法效率——用依據(jù)該算法編制程序在計(jì)算機(jī)上執(zhí)行所消耗時(shí)間來度量。通慣用事后統(tǒng)計(jì)和事前分析預(yù)計(jì)這種方法。但同一個(gè)算法用不一樣語言、不一樣編譯程序、在不一樣計(jì)算機(jī)上運(yùn)行，效率均不一樣，所以使用絕對(duì)時(shí)間單位衡量算法效率不適當(dāng)。數(shù)據(jù)結(jié)構(gòu)（C語言版）第23頁在三個(gè)整數(shù)中求最大者max(inta,intb,intc)

{if(a>b)

{if(a>c)returna;

elsereturnc;

}

else

{if(b>c)returnb;

elsereturnc;

}/*無需額外存放空間，只需兩次比較*/max(inta[3])

{intc,inti;

c=a[0];

for(i=1;i<3;i++)

if(a[i]>c)c=a[i];

returnc;

}

/*需要兩個(gè)額外存放空間，兩次比較，最少一次賦值*/

/*共需5個(gè)整型數(shù)空間*/100個(gè)整數(shù)同上算法難寫難讀/*共需102個(gè)整型數(shù)空間*/

數(shù)據(jù)結(jié)構(gòu)（C語言版）第24頁算法效率度量事后統(tǒng)計(jì)方法；事前分析估算方法；事前估算法要考慮以下原因：問題規(guī)模；編寫程序時(shí)所用程序設(shè)計(jì)語言；機(jī)器速度；算法所用策略。 撇開這些與機(jī)器軟硬件相關(guān)原因，能夠認(rèn)為一個(gè)特定算法“運(yùn)行工作量”大小只依賴與問題規(guī)模，或者說只是問題規(guī)模函數(shù)。 數(shù)據(jù)結(jié)構(gòu)（C語言版）第25頁例兩個(gè)n*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]； ⑤} 語句①到語句⑤執(zhí)行次數(shù)依次是（n+1），n（n+1），n2，（n+1）n2，n3。它們之和就是該算法時(shí)間開銷 T（n）=2n3+3n2+2n+1 當(dāng)n充分大時(shí)候，T（n）與f（n）=n3數(shù)量級(jí)相同。于是，該算法時(shí)間復(fù)雜度為：T（n）=O（n3），其原語句是語句⑤。 頻度：是指該語句重復(fù)執(zhí)行次數(shù)數(shù)據(jù)結(jié)構(gòu)（C語言版）第26頁算法時(shí)間復(fù)雜度(TimeComplexity) 普通來說，設(shè)算法中全部語句頻度之和記作T(n)，它是問題規(guī)模n某個(gè)函數(shù)f(n)，記作：

T(n)=O(f(n)) 它表示隨問題規(guī)模n增大，算法執(zhí)行時(shí)間增加率與f(n)增加率相同，稱做算法漸近時(shí)間復(fù)雜度，簡稱時(shí)間復(fù)雜度。語句在算法中被重復(fù)執(zhí)行次數(shù)(FrequencyCount)數(shù)據(jù)結(jié)構(gòu)（C語言版）第27頁{++x;s=0;}for(j=1;j<=n;++j) for(k=1;k<=n;++k){ ++x;s+=x; }for(i=1;i<=n;++i){ ++x;s+=x; }T(n)=O(1)T(n)=O(n2)T(n)=O(n)例求下面程序段時(shí)間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)（C語言版）第28頁4. for(i=2;i<=n;++i) for(j=2;k<=i-1;++j) {++x;a[i][j]=x;}語句頻度表示式為(n-1)(n-2)/2T(n)=O(n2)數(shù)據(jù)結(jié)構(gòu)（C語言版）第29頁例冒泡排序算法。voidbubble_sort(inta[],intn){ for(i=n-1,change=TRUE;i>=1&&change;--i){ cha