緒論數(shù)據(jù)結(jié)構(gòu)與算法Java版

第一章緒論教學(xué)內(nèi)容1.2根本概念與術(shù)語(yǔ)1.3算法與算法分析1.4Java提供的泛型方法1.1數(shù)據(jù)結(jié)構(gòu)課程討論的內(nèi)容教學(xué)重點(diǎn)與難點(diǎn)重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的根本概念及有關(guān)術(shù)語(yǔ)算法及算法的分析方法難點(diǎn)：時(shí)間復(fù)雜度的估算課前思考你過去是否聽說過“數(shù)據(jù)結(jié)構(gòu)〞？你知道數(shù)據(jù)結(jié)構(gòu)是一門討論什么內(nèi)容的學(xué)科嗎？NiklausWirth：〔著名的瑞士科學(xué)家沃思教授〕Algorithm+DataStructures=Programs(算法+數(shù)據(jù)結(jié)構(gòu)=程序〕數(shù)據(jù)結(jié)構(gòu):算法:程序:為計(jì)算機(jī)處理問題而編制的一組指令集處理問題的策略〔是對(duì)數(shù)據(jù)運(yùn)算的描述，是程序的邏輯抽象〕問題的數(shù)學(xué)模型，它反映數(shù)據(jù)及其之間關(guān)系?！泊鎯?chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)〕1.1.1求解問題舉例問題求解的主要步驟：1.確定求解問題的數(shù)學(xué)模型；2.確定存儲(chǔ)結(jié)構(gòu)；3.設(shè)計(jì)算法；4.編程并測(cè)試結(jié)果。

程序設(shè)計(jì)的實(shí)質(zhì)是在于解決兩個(gè)主要問題：一是根據(jù)實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)；二是設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。1.1.1求解問題舉例【例1】N個(gè)數(shù)的選擇問題

算法：?模型：?如何選擇？N個(gè)數(shù)在計(jì)算機(jī)中的組織1.1.1求解問題舉例【例2】生產(chǎn)訂單的自動(dòng)查詢問題

算法：?模型：?如何查詢？生產(chǎn)訂單數(shù)據(jù)在計(jì)算機(jī)中的組織1.1.1求解問題舉例【例3】城市網(wǎng)絡(luò)的鋪設(shè)問題

算法：?模型：?如何為城市的各小區(qū)之間鋪設(shè)網(wǎng)絡(luò)線路,使投資最小?(對(duì)n個(gè)小區(qū)只需鋪設(shè)n-1條線路)圖的最小生成樹1.1.1求解問題舉例1.1.2本課程的內(nèi)容方面過程數(shù)據(jù)表示數(shù)據(jù)處理抽象邏輯結(jié)構(gòu)基本運(yùn)算實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)算法評(píng)價(jià)不同數(shù)據(jù)結(jié)構(gòu)的比較和算法性能分析數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容體系:簡(jiǎn)單地說,本課程研究的內(nèi)容包括以下三方面：

1.數(shù)據(jù)的邏輯結(jié)構(gòu)

2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)/物理結(jié)構(gòu)

3.數(shù)據(jù)的運(yùn)算數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型抽象數(shù)據(jù)類型1.2根本概念與術(shù)語(yǔ)1.2.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的總稱。如：實(shí)數(shù)、整數(shù)、字符〔串〕、圖形和聲音等。數(shù)據(jù)(Data):是計(jì)算機(jī)操作對(duì)象的集合。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。是數(shù)據(jù)〔集合〕中的一個(gè)“個(gè)體〞數(shù)據(jù)元素〔DataElement):是數(shù)據(jù)結(jié)構(gòu)中討論的根本單位不同場(chǎng)合也叫結(jié)點(diǎn)、頂點(diǎn)、記錄1.2.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)項(xiàng)〔DataItem〕：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素是由假設(shè)干個(gè)數(shù)據(jù)項(xiàng)組成例如：描述一個(gè)運(yùn)發(fā)動(dòng)的數(shù)據(jù)元素稱之為組合項(xiàng),其它為簡(jiǎn)單項(xiàng)年月日姓名

俱樂部名稱出生日期參加日期職務(wù)業(yè)績(jī)1.2.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)對(duì)象〔DataObject〕：是性質(zhì)相同的數(shù)據(jù)元素的集合例如：學(xué)生成績(jī)表是一個(gè)數(shù)據(jù)對(duì)象學(xué)號(hào)姓名數(shù)學(xué)分析普通物理高等代數(shù)2000120002200032000420005張三李四丁一馬二王五908067985656876790878967876768數(shù)據(jù)對(duì)象中的數(shù)據(jù)元素不會(huì)是孤立的，而是彼此相關(guān)的，這種彼此之間的關(guān)系稱為“結(jié)構(gòu)〞,如書中表1.1、圖1.2(a)、圖1.3都形成了其特定的結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)〔DataStructure〕：邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)操作線性結(jié)構(gòu)(1:1的關(guān)系)樹形結(jié)構(gòu)(1:n的關(guān)系)圖狀結(jié)構(gòu)(m:n的關(guān)系)集合結(jié)構(gòu)(松散關(guān)系)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)散列存儲(chǔ)非線性結(jié)構(gòu)是相互之間存在一種或多種關(guān)系的數(shù)據(jù)元素的集合:創(chuàng)立、銷毀、插入、刪除、修改等邏輯結(jié)構(gòu)可用二元組形式定義為:Data_Structures=(D,R)其中:D是數(shù)據(jù)元素的有限集，

R是D上關(guān)系的有限集。也可用數(shù)據(jù)的邏輯結(jié)構(gòu)圖來(lái)形象表示之。1.2.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)【例1】設(shè)有數(shù)據(jù)結(jié)構(gòu)為：B=〔D，R〕，其中：D={k1,k2,k3,….k9}R={<k1,k3>,<k1,k8>,<k2,k3>,<k2,k4>,<k2,k5>,<k3,k9>,<k5,k6>,<k8,k9>,<k9,k7>,<k4,k7>,<k4,k6>}畫出其邏輯結(jié)構(gòu)的圖示，并確定相對(duì)于關(guān)系R，哪些結(jié)點(diǎn)是開始結(jié)點(diǎn)，哪些是終端結(jié)點(diǎn)？k2k1k4k5k3k8k6k9k7開始結(jié)點(diǎn)為k1,k2(無(wú)前驅(qū)的結(jié)點(diǎn)〕終端結(jié)點(diǎn)為k6,k7(無(wú)后繼的結(jié)點(diǎn)〕【例2】矩陣

中9個(gè)元素之間存在兩種關(guān)系，一種是行關(guān)系，一種是列關(guān)系，試給出其邏輯結(jié)構(gòu)的二元組表示形式。

，，，其邏輯結(jié)構(gòu)的二元組表示形式為：B=〔D，R〕，其中：D={a1,a2,……,a9}R={ROW,COL}ROW={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>,<a7,a8>,<a8,a9>}COL={<a1,a4>,<a4,a7>,<a2,a5>,<a5,a8>,<a3,a6>,<a6,a9>}1.2.2數(shù)據(jù)類型

其實(shí)數(shù)據(jù)類型反映三個(gè)方面的內(nèi)容：存儲(chǔ)結(jié)構(gòu)，取值范圍和允許進(jìn)行的操作。在用高級(jí)程序語(yǔ)言編寫的程序中，每個(gè)數(shù)據(jù)都應(yīng)有一個(gè)所屬的、確定的數(shù)據(jù)類型。在Java語(yǔ)言中，簡(jiǎn)單數(shù)據(jù)可描述為Java內(nèi)置的8種根本的數(shù)據(jù)類型之一；而對(duì)于復(fù)雜數(shù)據(jù)那么可通過類的聲明來(lái)引入新的數(shù)據(jù)類型。其中類的對(duì)象(object)是新的類型的實(shí)例，類的成員變量確定了新的數(shù)據(jù)類型的數(shù)據(jù)表示方法和存儲(chǔ)結(jié)構(gòu)，類的構(gòu)造函數(shù)和成員函數(shù)確定了新的數(shù)據(jù)類型的操作?？捎肑ava語(yǔ)言中的“數(shù)組〞類型來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)，用Java語(yǔ)言中提供的“對(duì)象引用〞來(lái)實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。例如：學(xué)生成績(jī)表基于數(shù)組的順序存儲(chǔ)結(jié)構(gòu)可描述如下：-學(xué)生成績(jī)記錄的類描述packagech01;publicclassResultsRecord{privateStringstudentNum;//學(xué)號(hào)privateStringstudentName;//學(xué)生姓名privatefloatmathScore;//數(shù)學(xué)分析privatefloatphysicalScore;//普通物理privatefloatalgebraScore;//普通物理publicStringgetStudentNum(){ returnstudentNum;}publicvoidsetStudentNum(StringstudentNum){ this.studentNum=studentNum;}……} -基于數(shù)組的順序存儲(chǔ)的類描述packagech01;publicclassSqResults{privateResultsRecord[]listElem；

//存放學(xué)生成績(jī)的存儲(chǔ)空間privateintcluLen;//當(dāng)前學(xué)生成績(jī)表的長(zhǎng)度……} 1.2.3抽象數(shù)據(jù)類型

以后將全部采用Java接口表示抽象數(shù)據(jù)類型。下面通過兩個(gè)具體實(shí)例來(lái)說明抽象數(shù)據(jù)類型的描述和實(shí)現(xiàn)。

抽象數(shù)據(jù)類型(AbstractDataType,簡(jiǎn)稱ADT)是指一數(shù)據(jù)值的集合和定義在這個(gè)集合上的一組操作。它不包括數(shù)據(jù)的計(jì)算機(jī)存儲(chǔ)表示，而且這里的操作是脫離了具體實(shí)現(xiàn)的抽象操作，即不涉及它的實(shí)現(xiàn)細(xì)節(jié)。換句話說，抽象數(shù)據(jù)類型是指隱藏了數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)并且不涉及操作的實(shí)現(xiàn)細(xì)節(jié)的數(shù)據(jù)類型。

例1.3用Java接口來(lái)描述復(fù)數(shù)的抽象數(shù)據(jù)類型。假設(shè)復(fù)數(shù)的操作只包含：構(gòu)造一個(gè)實(shí)部和虛部為給定值的復(fù)數(shù)，讀取和修改復(fù)數(shù)的實(shí)部和虛部，以及兩個(gè)復(fù)數(shù)的求和。

//復(fù)數(shù)抽象數(shù)據(jù)類型的接口表示publicinterfaceIComplex{ publicdoublegetReal();//取實(shí)部

publicvoidsetReal(doublereal);//修改實(shí)部

publicdoublegetImag();//取虛部publicvoidsetImag(doubleimag);//修改虛部

publicvoidadd(IComplexZ);//兩個(gè)實(shí)數(shù)的求和}publicclassCompleximplementsIComplex{

}

例1.4編寫實(shí)現(xiàn)【例1.3】中復(fù)數(shù)抽象數(shù)據(jù)類型的Java類代碼。

privatedoublereal;//實(shí)部privatedoubleimag;//虛部//構(gòu)造一個(gè)實(shí)數(shù)publicComplex(doublereal,doubleimag){ this.real=real; this.imag=imag;}//取實(shí)部publicdoublegetReal(){ returnreal;}……publicclassCompleximplementsIComplex{

}

例1.4編寫實(shí)現(xiàn)【例1.3】中復(fù)數(shù)抽象數(shù)據(jù)類型的Java類代碼。

//修改實(shí)部publicvoidsetReal(doublereal){ this.real=real;}……//取虛部publicdoublegetImag(){

returnimag;}//修改虛部publicvoidsetImag(doubleimag){ this.imag=imag;}publicclassCompleximplementsIComplex{

}

例1.4編寫實(shí)現(xiàn)【例1.3】中復(fù)數(shù)抽象數(shù)據(jù)類型的Java類代碼。

……//兩個(gè)實(shí)數(shù)的求和publicvoidadd(IComplexZ){ if(Z!=null){ real+=Z.getReal(); imag+=Z.getImag(); }}算法的根本概念算法的描述算法分析1.3算法與算法分析1.3.1算法的根本概念何謂算法？

算法是對(duì)特定問題求解步驟的一種描述，是指令的有限序列。其中每條指令表示一個(gè)或多個(gè)操作。嚴(yán)格來(lái)講，一個(gè)算法一般應(yīng)具有以下5種性質(zhì)：1．有窮性

2．確定性3．有效性4．輸入5．輸出算法設(shè)計(jì)的目標(biāo):設(shè)計(jì)算法時(shí)，通常應(yīng)考慮到達(dá)以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率〔時(shí)間與空間〕1.3.1算法的根本概念1.3.2算法的描述

本教程描述算法全部采用Java程序設(shè)計(jì)語(yǔ)言。

【例1】給出求整型數(shù)組a中最大值的算法。publicstaticintmaxEle(int[]a){intn=a.length;intmax=a[0];for(inti=1;i<n;i++){if(max<a[i])max=a[i];}returnmax;}

【例2】給出將整型數(shù)組a中數(shù)據(jù)元素實(shí)現(xiàn)就地逆置的算法。publicstaticvoidreverse(int[]a){}intn=a.length;inttemp;for(inti=0,j=n-1;

i<j;i++,j--){temp=a[i];a[i]=a[j];a[j]=temp;}1.3.2算法的描述1.3.3算法分析

算法分析→算法復(fù)雜度的評(píng)判

算法復(fù)雜度時(shí)間復(fù)雜度空間復(fù)雜度時(shí)間復(fù)雜度通常有兩種衡量算法時(shí)間(效率)的方法:事后統(tǒng)計(jì)法事前分析估算法缺點(diǎn)：1．必須執(zhí)行程序

2．其它因素掩蓋算法本質(zhì)和算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語(yǔ)言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的硬件速度6．程序運(yùn)行的軟件環(huán)境時(shí)間復(fù)雜度一個(gè)特定算法的“運(yùn)行工作量〞的大小，只依賴于問題的規(guī)?！餐ǔＳ谜麛?shù)量n表示〕，或者說，它是問題規(guī)模的函數(shù)。假設(shè)，記為T(n),并將稱T(n)為算法的時(shí)間復(fù)雜度。【定義】算法的時(shí)間復(fù)雜度T(n)=O(f(n))

當(dāng)且僅當(dāng)存在正常數(shù)c和N，對(duì)所有的

n(n≥N)滿足0≤T(n)≤c×f(n)。例如：T(n)=4n3+3n2+2n+1=

O(n3)?其中c=10,N=1如何估算算法的時(shí)間復(fù)雜度？1.3.3算法分析算法=控制結(jié)構(gòu)+原操作〔固有數(shù)據(jù)類型的操作〕算法的執(zhí)行時(shí)間

=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間

與

原操作執(zhí)行次數(shù)之和

成正比

1.3.3算法分析【例1】變量計(jì)量x=0;y=0;s=0;

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

++x;s+=x;}

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

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

++y;s+=y;}語(yǔ)句頻度n+1nn+1n(n+1)n2T(n)=O(n2)1.3.3算法分析【例2】?jī)蓚€(gè)矩陣相乘publicstaticvoidsquareMult(int[][]a,int[][]b,int[][]c,intn){

for(inti=0;j<n;j++)

for(intj=0;j<n;j++){

c[i][j]=0;

for(intk=0;k<n;k++)

c[i][j]+=a[i][k]*b[k][j];

}

}語(yǔ)句頻度nn(n+1)n2n2(n+1)n3T(n)=O(n3)1.3.3算法分析從算法中選取一種對(duì)于所研究的問題來(lái)說是關(guān)鍵操作的原操作，以該關(guān)鍵操作在算法中重復(fù)執(zhí)行的次數(shù)〔語(yǔ)句頻度〕作為算法運(yùn)行時(shí)間的衡量準(zhǔn)那么。1.3.3算法分析【例3】求以下算法的關(guān)鍵操作語(yǔ)句的語(yǔ)句頻度及算法的時(shí)間復(fù)雜度publicstaticmyOut(){

for(i=1;

i<=n;i=10*i)

printf("%4d",i);

}解：設(shè)關(guān)鍵操作語(yǔ)句的語(yǔ)句頻度為f(n),那么有10f(n)≤n,所以f(n)≤log10n故:T(n)=O(log10n)1.3.3算法分析有些算法在規(guī)模相同的情況之下，其語(yǔ)句頻度會(huì)因輸入的數(shù)據(jù)值或輸入的數(shù)據(jù)順序不同而不同，那么時(shí)間復(fù)雜度也會(huì)不同，為此有最好、最壞和平均時(shí)間復(fù)雜度之分。1.3.3算法分析【例4】如下算法實(shí)現(xiàn)的功能是在數(shù)組a[0:n-1]中查找值為x的數(shù)據(jù)元素。假設(shè)找到，那么返回x在a中的位置；否那么，返回-1。求其時(shí)間復(fù)雜度。publicstaticintrSearch(int[]a,intx){

intn=a.length;

for(inti=0;i<n&&!x.equals(a[i]);i++);

if(i==n)

return-1;

else

returni;

}最好時(shí)間復(fù)雜度：O(1)

最壞時(shí)間復(fù)雜度：O(n)

平均時(shí)間復(fù)雜度：O(n)1.3.3算法分析【例5】如下算法是用冒泡排序法對(duì)數(shù)組a中的n個(gè)整型數(shù)據(jù)元素進(jìn)行排序，求該算法的時(shí)間復(fù)雜度。1.3.3算法分析publicstaticvoidbubbleSort(int[]a,intn){

inttemp,flag=1;

for(inti=1;i<n&&flag;i++){

flag=0;

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

if(a[j]>a[j+1]){

flag=1;

temp=a[j];

a[j]=a[j+1];

a[j+1]=tmep;

}

}

}

}最好時(shí)間復(fù)雜度：O(n)

最壞時(shí)間復(fù)雜度：O(n2)按增長(zhǎng)率由小至大的順序排列有：注意多項(xiàng)式時(shí)間算法的時(shí)間復(fù)雜度：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)指數(shù)時(shí)間算法的時(shí)間復(fù)雜度：O(2n)<O(n!)<O(nn)總之，隨著的增大，指數(shù)時(shí)間算法和多項(xiàng)式時(shí)間算法在所需時(shí)間上相差非常懸殊。1.3.3算法分析1.3.4算法舉例【問題描述】給定一整數(shù)序列A1，A2，...An〔可能有負(fù)數(shù)〕，求A1～An的一個(gè)子序列Ai～Aj，使得Ai到Aj的和最大。例如：整數(shù)序列-2,11,-4,13,-5,2,-5,-3,12,-9的最大子序列的和為21〔從A2到A9〕。下面介紹四種實(shí)現(xiàn)方法方法一:窮舉法(書中算法1.1)publicstaticintmaxSub_1(int[]sequence){}intmax=0;intn=sequence.length;intsum=0;//第一重循環(huán)執(zhí)行一次那么計(jì)算出長(zhǎng)度為i的所有子序列和的最大值for(inti=1;i<=n;i++)for(intj=0;j<n;j++){sum=0;for(intk=j;k<j+i&&k<n;k++)sum+=sequence[k];if(sum>max)max=sum;}returnmax;時(shí)間復(fù)雜度:O(n3)方法二:(書中算法1.2)publicstaticintmaxSub_2(int[]sequence){}intmax=0;intn=sequence.length;intsum=0;for(inti=0;i<n;i++){sum=0;

for(intj=i;j<n;j++){sum+=sequence[j];if(sum>max)max=sum;}returnmax;時(shí)間復(fù)雜度:O(n2)方法三:分治法(書中算法1.3)publicstaticintmaxSum(int[]sequence){}if(left==right)if(sequence[left]>0)returnsequenece[left];elsereturn0;

intmid=(left+right)/2;intmaxLeftSum=maxSum(sequenece,left,mid);intmaxRightSum=maxSum(sequenece,mid+1,right);intmaxLeftBorderSum=0,leftBorderSum=0;for(inti=mid;i>=left;i--){leftBorderSum+=sequence[i];if(leftBorderSum>maxLeftBorderSum)maxLeftBorderSum=leftBorderSum;}……方法三:分治法(書中算法1.3)publicstaticintmaxSum(int[]sequence){}intmaxRightBorderSum=0,rightBorderSum=0;for(inti=mid+1;i<=right;i++){rightBorderSum+=sequence[i];if(rightBorderSum>maxRightBorderSum)maxRightBorderSum=rightBorderSum;}returnmax3(maxLeftSum,maxRightSum,maxLeftBorderSum+maxRightBorderSum);時(shí)間復(fù)雜度:O(nlog2n)……方法三:分治法(書中算法1.3)publicstaticintmax3(inta,intb,intc){intmax=a>b:a?b;max=max>c:max?c;retrunmax;}publicstaticintmaxSub_3(int[]sequence){returnmaxSum(a,0,sequence.length-1);}……方法四:動(dòng)態(tài)規(guī)劃法(書中算法1.4)publicstaticintmaxSub_4(int[]sequence){}intmax=0;intn=sequence.length;intsum=0;for(inti=0;i<n;i++){sum+=sequence[i];if(sum>max)max=sum;elseif(sum<0)sum=0;}returnmax;時(shí)間復(fù)雜度:O(n)假設(shè)除去數(shù)據(jù)對(duì)象的根本類型外，實(shí)現(xiàn)方