數(shù)據(jù)結(jié)構(gòu)-jchap大家已經(jīng)有對(duì)本課程了解是什么

課程介大家已經(jīng)有的對(duì)本課程的了解是什《數(shù)據(jù)結(jié)構(gòu)》課程講的是什么《數(shù)據(jù)結(jié)構(gòu)》講哪些內(nèi)容本課程是如何組織這些內(nèi)容的

友

簡(jiǎn)單變 i, x,y,用簡(jiǎn)單變量解決簡(jiǎn)單的數(shù)值計(jì)算問(wèn)結(jié)構(gòu)變量 用結(jié)構(gòu)變量解決的問(wèn)題可以變得稍復(fù)雜點(diǎn) 迷宮、下 語(yǔ)義分 最短路徑問(wèn) 大家已經(jīng)有的對(duì)本課程的了解是什《數(shù)據(jù)結(jié)構(gòu)》課程講的是什么《數(shù)據(jù)結(jié)構(gòu)》講哪些內(nèi)容本課程是如何組織這些內(nèi)容的課程內(nèi)第1 緒 第5 數(shù)組和廣義 第9 查第10章排本課的前本課程要解決的問(wèn)學(xué)習(xí)目部方式以及對(duì)它們的編程方法和技巧。據(jù)結(jié)構(gòu)和結(jié)構(gòu)以及相應(yīng)算法，掌握各種算法在時(shí)間和第一數(shù)據(jù)結(jié)構(gòu)討論的范基本概算法和算法的量數(shù)據(jù)結(jié)構(gòu)討論的 Algorithm+DataStructures=數(shù)據(jù)結(jié)構(gòu):問(wèn)題的數(shù)學(xué)模型。指數(shù)據(jù)的邏輯結(jié)構(gòu) 結(jié)程序設(shè)計(jì)的實(shí)質(zhì)是例如

?基本操作是“比較兩個(gè)數(shù)的大小模型：？取決于整數(shù)值的例二：計(jì)算機(jī)對(duì)

例三：學(xué)生的數(shù)據(jù)庫(kù)管

？概括地說(shuō) 基本概三、抽象數(shù)據(jù)一、數(shù)據(jù)與數(shù)據(jù)數(shù)據(jù)是計(jì)算機(jī)操作的對(duì)象的總稱數(shù)據(jù)元素 數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的例如：描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以年月日稱之為組合帶結(jié)構(gòu)的數(shù)據(jù)元素的集數(shù)據(jù)結(jié)構(gòu)相互之間存在一種或多種特關(guān)系的數(shù)據(jù)元素的集合假設(shè)用4位的十進(jìn)制數(shù)表示一個(gè)含12數(shù)的十進(jìn)制數(shù)

例如3214,6587,9345─a1、a2a3之間存在著“次序”關(guān)系a1,a2、a2,a33214，6587，9345≠ 數(shù)據(jù)結(jié)構(gòu)帶結(jié)構(gòu)的數(shù)據(jù)元素的集又例，在2行3列的二維數(shù)組{a1,a2,a3,a4,a5, 行的次序關(guān)系row=列的次序關(guān)系col=a1a3a5a2a4

a1a2a3a4a5數(shù)據(jù)結(jié)構(gòu)帶結(jié)構(gòu)的數(shù)據(jù)元素的集再例，在一維數(shù)組{a1,a2,a3,a4,a5, 間存在如下的次序關(guān)系{<ai,ai+1>|i=1,2,3,4,種邏輯關(guān)系的數(shù)據(jù)元素的集合數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類圖狀集合結(jié)數(shù)據(jù)結(jié)構(gòu)的形式定義數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元Data_Structures=(D,其中:D是數(shù)據(jù)元素的有限集S是D上關(guān)系的有限集 結(jié)——邏輯結(jié)構(gòu) 器中的映““數(shù)據(jù)元素的映象方A

==

==關(guān)系的映象方法（表示x,y的方）順序映以相對(duì)的位置表示后繼關(guān)系例如:令y的位置和x的位置之間差一個(gè)常量C而C是一個(gè)隱含值，整個(gè)結(jié)構(gòu)中只xy鏈?zhǔn)接骋愿郊有畔?指針)表示后繼關(guān)需要用一個(gè)和x在一起的附加信息指示y的 yxy在Java語(yǔ)言 的數(shù)據(jù)表示方法和結(jié)構(gòu)，類的構(gòu)造函?，F(xiàn)順序結(jié)構(gòu)，用Java語(yǔ)言中提供的“對(duì)象”來(lái)實(shí)現(xiàn)鏈?zhǔn)浇Y(jié)構(gòu)。CC語(yǔ)言中C一個(gè)長(zhǎng)整數(shù)時(shí)，可利用C語(yǔ)言中定義長(zhǎng)整數(shù)typedefintLong_intpackagepublicclassResultsRecordprivateStringstudentNum; //學(xué)號(hào)privateStringstudentName;//學(xué)生privatefloatmathScore;//數(shù)學(xué)分析privatefloatphysicalScore;//普通物理privatefloatalgebraScore;//代數(shù)publicStringgetStudentNum(){returnstudentNum;publicvoidsetStudentNum(StringstudentNum){}-基于數(shù)組的順 的類描述

packagepublicclassSqResultsprivateResultsRecord[] privateint}

數(shù)據(jù)結(jié)構(gòu)（DataStructure）邏輯結(jié)數(shù)據(jù)操

非(1:n 結(jié)性(m:n結(jié)構(gòu)二、數(shù)據(jù)類屬的數(shù)據(jù)類型例如，C語(yǔ)言中提供的基本數(shù)據(jù)類型整型浮點(diǎn)型雙精度

實(shí)型（C++語(yǔ)言字符型邏輯型bool（C++語(yǔ)言數(shù)據(jù)值的集一組三、抽象數(shù)據(jù) DataType簡(jiǎn)稱例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義ADTComplex數(shù)據(jù)對(duì)象D＝{e1,e2｜e1,e2∈RealSet數(shù)據(jù)關(guān)系R1＝{<e1,e2>|e1|e2基本操作

plex(&Z,v1,v2Z,v1和v2plex(GetReal(Z,&realPart操作結(jié)果：用realPart返回復(fù)數(shù)Z的GetImag(Z,&ImagPart操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部Add(z1,z2,&sum初始條件：z1,z2操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的}ADT則Add(z1,z2,z3)操作的結(jié)果z3=z1+數(shù)據(jù)抽象用ADT描述程序處理的實(shí)體數(shù)據(jù)封將實(shí)體的外部特性和 抽象數(shù)據(jù)類型的描述方抽象數(shù)據(jù)類型可用（D，S，P）三元組表示SDPDADT抽象數(shù)據(jù)類型名基本操作：〈基本操作的定義ADT操作結(jié)果：〈操作結(jié)果描賦值參以&初始條描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)操作結(jié)說(shuō)明了操作正常完成之后，數(shù)抽象數(shù)據(jù)類型的表//---- 結(jié)構(gòu)的定 typedefstructfloatfloat 基本操作的函數(shù)原voidAssign(complexfloatrealval,floatimagval//Zrealvalimagval的floatGetReal(cpmplexZ返回復(fù)Z實(shí)部floatGetimag(cpmplexZ返回復(fù)Z虛部voidadd(complexz1,complexcomplex&sum以sum返回兩個(gè)復(fù)z1,z2的 基本操作的voidadd(complexz1,complexcomplex&sum)//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和sum.realpart=z1.realpart+z2.realpart;sum.imagpartz1.imagpartz2.imagpart;}可以采用Java接口表示抽象數(shù)據(jù)類

例：用Java虛部為給定值的復(fù)數(shù)，和修改復(fù)數(shù)的實(shí)//復(fù)數(shù)抽象數(shù)據(jù)類型的接publicinterfaceIComplexpublicdoublegetReal();//取實(shí)publicvoidsetReal(doublereal);修改實(shí)publicdoublegetImag();取虛publicvoidsetImag(doubleimag);修改虛publicvoidadd(IComplexZ兩個(gè)實(shí)數(shù)的}publicclassCompleximplementsIComplexprivatedoublereal;privatedoubleimag;

publicComplex(doublereal,doubleimag)this.real=real;this.imag=imag;} publicdoublegetReal()return 例編寫實(shí)現(xiàn)復(fù)數(shù)抽象數(shù)據(jù)類型的Java代碼publicclassCompleximplementsIComplexpublicvoidsetReal(doublereal){this.real=real;

取虛部publicdoublegetImag()return publicvoidsetImag(doubleimag){this.imag=imag;}Java類代publicclassCompleximplementsIComplex兩個(gè)實(shí)數(shù)的求和publicvoidadd(IComplexZ)if(Z!=null)real+=Z.getReal();imag+=Z.getImag();}}}算法和算法的二、算法設(shè)計(jì)的原 有窮4．有輸

確定 3．可行5．有輸有窮 對(duì)于任意一組合法輸入值在執(zhí)行有窮步驟之后一定能結(jié)束，即算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完確定性對(duì)于每種情況下所應(yīng)執(zhí)行的操可行 有輸出它是一組與“輸入”有確二、算法設(shè)計(jì)的正確可讀健壯高效率與 量需正確首先，算法應(yīng)當(dāng)滿足以特定的“規(guī)說(shuō)明”方式給出的需求程序?qū)τ诰倪x擇的、典型、苛刻通常以c層意義的正確性作為衡可讀 高效率與 量需 三、算法效率的衡量方法和通常有兩種衡量算法效率的方法事后統(tǒng)缺點(diǎn)：1．必須執(zhí)行程 事前分析估算和算法執(zhí)行時(shí)間相關(guān)的因素算法選用的策問(wèn)題的規(guī)編寫程序的編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)計(jì)算機(jī)執(zhí)行指令的速一個(gè)特定算法的“運(yùn)行工作量算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n) T(n)=稱T(n)為算法的(漸近)時(shí)間復(fù)雜度如何估算法的時(shí)間復(fù)雜制結(jié)操算法的執(zhí)行時(shí)元操作(i)的執(zhí)行次數(shù)×元操作(i)的執(zhí)算法的執(zhí)行時(shí)間與元操作執(zhí)行次數(shù)之和成正時(shí)間復(fù)雜度往往不是精確的執(zhí)行次數(shù)，而是估算的數(shù)量級(jí)，它著重體現(xiàn)的是隨著問(wèn)題規(guī)模n的增大，算基本操的元操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。(a)for(i=1;i<=n;i++)forfor(i=1;i<=n;i++)（a）O（1）常量階（b）O（n）線性階（c）O（n平方階算法還可能呈現(xiàn)的時(shí)間雜度有指數(shù)階不同數(shù)量級(jí)時(shí)間復(fù)雜度的形狀如下所平方階0(n2)、立方階0(n3)、…k次方階對(duì)數(shù)階0(log2nvoidmult(inta[],intb[],int&c[] //以二維數(shù) 矩陣元素，c為a和b的乘for(i=1;i<=n; for(j=1;j<=n;++j)個(gè) c[i,j]= for(k=1;k<=n; c[i,j]+= } 時(shí)間復(fù)雜度:例voidselect_sort(int&a[]intn)a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列for(i=0;i<n-1;++i) j= //選擇第i個(gè)最小元 for(k=i+1;k<n;++k排 if(a[k]<a[j])j=if(j!=i)a[j]←→ 比較(數(shù)據(jù)元素)voidbubble_sort(int&a[],intn)三afor(i=n-1,change=TRUE;i>1&&change;--{changeFALSE;change for(j=0;j<i; if(a[j]>{a[j]←→ change=TRUE}//For(i=1;i<=n;i++){for

①②③④c[i][j]=c[i][j]+a[i][j]*b[i][j];⑤}該算法的執(zhí)行時(shí)間是個(gè)語(yǔ)句頻度之和，因此有T(n)=O(2n3+3n2For該程序段的f(n)應(yīng)是x++的頻度，即 nf(n)1(ni) n

i1 所以，T(n)=O(n2while(I<=n)2f(n)<=n即f(n)<=log2nT(n)=O(f(n))=log2n(1)

i(i1) 1j

2 ii j1k i j

i1 i i1n(n1)(2n1)1n(n1) n(n1)(n2) 則該程序段的時(shí)間復(fù)雜度為T(n)=O(n3/6+低次項(xiàng))=O(n3)例八:執(zhí)行語(yǔ)句頻數(shù)與輸入有關(guān)的例在數(shù)值A(chǔ)[0..n-1]中查找給定值K的算法大致如下return①若A中沒(méi)有與K相等的元素，則語(yǔ)句(3)的頻度②若A的最后一個(gè)元素等于K,則語(yǔ)句(3)的頻度f(wàn)(n)是常數(shù)0例有兩個(gè)算法A1和A2求解同一問(wèn)題，時(shí)間算法 量包括輸入數(shù)據(jù)所占空程序本身