1第一頁，共七十二頁，2022年，8月28日什么是數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)類型及面向?qū)ο蟾拍钏惴ǘx模板算法簡單性能分析與度量第一章數(shù)據(jù)結(jié)構(gòu)概念第二頁，共七十二頁，2022年，8月28日“學(xué)生”表格第三頁，共七十二頁，2022年，8月28日“課程”表格第四頁，共七十二頁，2022年，8月28日學(xué)生(學(xué)號,姓名,性別,籍貫)課程(課程號,課程名,學(xué)分)選課(學(xué)號,課程號,成績)

“選課單”包含如下信息

學(xué)號課程編號成績時(shí)間

學(xué)生選課系統(tǒng)中實(shí)體構(gòu)成的網(wǎng)狀關(guān)系第五頁，共七十二頁，2022年，8月28日UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp第六頁，共七十二頁，2022年，8月28日數(shù)據(jù)（data）數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識別和處理的符號的集合。數(shù)據(jù)的分類：數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)第七頁，共七十二頁，2022年，8月28日姓名所在院系性別出生日期年月職務(wù)業(yè)績數(shù)據(jù)元素(dataelement)數(shù)據(jù)的基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)(DataItem)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識單位。數(shù)據(jù)元素又稱為元素、結(jié)點(diǎn)、記錄。第八頁，共七十二頁，2022年，8月28日什么是數(shù)據(jù)結(jié)構(gòu)定義:由某一數(shù)據(jù)元素的集合以及該集合中所有數(shù)據(jù)元素之間的關(guān)系組成。記為：Data_Structure={D,R}其中，D是某一數(shù)據(jù)元素的集合，R是該集合中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。第九頁，共七十二頁，2022年，8月28日例：N個(gè)網(wǎng)點(diǎn)之間的連通關(guān)系

樹形關(guān)系網(wǎng)狀關(guān)系156152436243第十頁，共七十二頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形式包括三個(gè)方面：數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲內(nèi)的表示，即數(shù)據(jù)的存儲表示；數(shù)據(jù)的運(yùn)算，即對數(shù)據(jù)元素施加的操作。第十一頁，共七十二頁，2022年，8月28日數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題抽象出來的數(shù)據(jù)模型；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無關(guān)；數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對存儲位置無關(guān)。第十二頁，共七十二頁，2022年，8月28日數(shù)據(jù)的邏輯結(jié)構(gòu)分類線性結(jié)構(gòu)

線性表非線性結(jié)構(gòu)

樹圖（或網(wǎng)絡(luò)）第十三頁，共七十二頁，2022年，8月28日線性結(jié)構(gòu)樹形結(jié)構(gòu)樹二叉樹二叉搜索樹bindevetclibuser14131211234567891031587101199874566231311第十四頁，共七十二頁，2022年，8月28日堆結(jié)構(gòu)

“最大”堆“最小”堆123548711102916410121151236987第十五頁，共七十二頁，2022年，8月28日圖結(jié)構(gòu)網(wǎng)絡(luò)結(jié)構(gòu)12543611331814665161921125634第十六頁，共七十二頁，2022年，8月28日數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)；數(shù)據(jù)的存儲結(jié)構(gòu)依賴于計(jì)算機(jī)語言。順序存儲表示鏈接存儲表示索引存儲表示散列存儲表示主要用于內(nèi)存的存儲表示主要用于外存(文件)的存儲表示第十七頁，共七十二頁，2022年，8月28日抽象數(shù)據(jù)類型及面向?qū)ο蟾拍顢?shù)據(jù)類型

定義：一組性質(zhì)相同的值的集合,以及定義于這個(gè)值集合上的一組操作的總稱.C語言中的數(shù)據(jù)類型

charintfloatdoublevoid

字符型整型浮點(diǎn)型雙精度型無值第十八頁，共七十二頁，2022年，8月28日構(gòu)造數(shù)據(jù)類型由基本數(shù)據(jù)類型或構(gòu)造數(shù)據(jù)類型組成。構(gòu)造數(shù)據(jù)類型由不同成分類型構(gòu)成?；緮?shù)據(jù)類型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類型就是數(shù)據(jù)結(jié)構(gòu)，不過它是從編程者的角度來使用的。數(shù)據(jù)類型是模板，必須定義屬于某種數(shù)據(jù)類型的變量，才能參加運(yùn)算。第十九頁，共七十二頁，2022年，8月28日抽象數(shù)據(jù)類型

(ADTs:AbstractDataTypes)抽象數(shù)據(jù)類型是由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型。特點(diǎn)是：信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離。抽象數(shù)據(jù)類型可用（D,S,P）三元組表示，其中，D是數(shù)據(jù)元素的集合（簡稱數(shù)據(jù)對象），S是D上的關(guān)系集合，P是對D的基本操作集合。

第二十頁，共七十二頁，2022年，8月28日抽象數(shù)據(jù)類型查找登錄刪除修改

符號表第二十一頁，共七十二頁，2022年，8月28日抽象數(shù)據(jù)類型的描述其中數(shù)據(jù)對象、數(shù)據(jù)之間的關(guān)系用偽碼描述；基本操作定義格式為ADT抽象數(shù)據(jù)類型名{ 數(shù)據(jù)對象：〈數(shù)據(jù)對象的定義〉 數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉 基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名基本操作名（參數(shù)表）前置條件：〈先決條件描述〉后置條件：〈操作結(jié)果描述〉第二十二頁，共七十二頁，2022年，8月28日基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果?！扒爸脳l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的先決條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息?！昂笾脳l件”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若前置條件為空，則省略之。第二十三頁，共七十二頁，2022年，8月28日自然數(shù)的抽象數(shù)據(jù)類型定義ADT

NaturalNumberisobjects:一個(gè)整數(shù)的有序子集合,它開始于0,結(jié)束于機(jī)器能表示的最大整數(shù)(MaxInt)。Function:對于所有的x,y

NaturalNumber;

False,TrueBoolean,+、-、<、==、=等都是可用的服務(wù)。

Zero():NaturalNumber

//前置條件：無//后置條件：返回自然數(shù)0

第二十四頁，共七十二頁，2022年，8月28日

IsZero(x):Boolean

//前置條件：x為NaturalNumber

//后置條件：if(x==0)then返回True

else返回FalseAdd(x,y):NaturalNumber

//前置條件：x,y為NaturalNumber且x+y≤MaxInt

//后置條件：返回x+ySubtract(x,y):NaturalNumber

//前置條件：x,y為NaturalNumber且x≥y

//后置條件：返回

x-y

第二十五頁，共七十二頁，2022年，8月28日

Equal(x,y):Boolean

//前置條件：x,y為NaturalNumber

//后置條件：

if(x==y)返回Trueelse返回FalseSuccessor(x):NaturalNumber

//前置條件：x為NaturalNumber

//后置條件：if(x==MaxInt)

返回xelse返回x+1end

NaturalNumber第二十六頁，共七十二頁，2022年，8月28日面向?qū)ο蟮母拍蠲嫦驅(qū)ο?對象＋類＋繼承＋通信對象在應(yīng)用問題中出現(xiàn)的各種實(shí)體、事件、規(guī)格說明等。由一組屬性值和在這組值上的一組服務(wù)（或稱操作）構(gòu)成。與C中構(gòu)造數(shù)據(jù)類型不同在于：C中的構(gòu)造數(shù)據(jù)類型的變量僅涉及屬性值，與操作分離，而C++中的對象則不然。第二十七頁，共七十二頁，2022年，8月28日類(class)，實(shí)例(instance)具有相同屬性和服務(wù)的對象歸于同一類，形成類。類中的對象為該類的實(shí)例。同一類的實(shí)例共享類的屬性和類的操作；通過繼承共享其父類的公共的和保護(hù)性的屬性和操作；同一類的不同實(shí)例有不同的屬性值。第二十八頁，共七十二頁，2022年，8月28日四邊形類及其對象屬性aPoint1aPoint2aPoint3aPoint4服務(wù)Draw()move(x,y)contains(aPoint)屬性值屬性值quadrilateral1quadrilateral2(35,10)(50,10)(35,25)(50,25)(45,65)(50,45)(65,66)(60,70)Draw()move(x,y)contains(aPoint)Draw()move(x,y)contains(aPoint)服務(wù)服務(wù)quadrilateral第二十九頁，共七十二頁，2022年，8月28日繼承派生類（子類）：四邊形，三角形，…基類（父類）：多邊形派生類繼承的特性+特有的特性基類多邊形四邊形三角形六邊形第三十頁，共七十二頁，2022年，8月28日通信消息傳遞C++中消息傳遞的方式：定義：Pointp;voidmove(intΔx,intΔy);使用：p.move(x,y);C中則不同，需使用函數(shù)調(diào)用方式：定義：Pointp;voidmove(Pointq,intΔx,intΔy);使用：move(p,x,y);

第三十一頁，共七十二頁，2022年，8月28日Draw()move(x,y)contains(aPoint)PolygonreferencePointVerticesPolygon類referencePointVerticesDraw()move(x,y)contains(aPoint)Polygon的子類Quadrilateral類Quadrilateral第三十二頁，共七十二頁，2022年，8月28日算法定義定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列特性：輸入有0個(gè)或多個(gè)輸入輸出有一個(gè)或多個(gè)輸出(處理結(jié)果)確定性每步定義都是確切無歧義的有窮性算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性每一條運(yùn)算應(yīng)足夠基本第三十三頁，共七十二頁，2022年，8月28日事例學(xué)習(xí)：選擇排序問題明確問題：遞增排序解決方案：逐個(gè)選擇最小數(shù)據(jù)算法框架：

for(inti=0;i<n-1;i++){//n-1趟 從a[i]檢查到a[n-1];

若最小整數(shù)在a[k],交換a[i]與a[k];}細(xì)化程序：程序SelectSort算法設(shè)計(jì)

自頂向下，逐步求精

第三十四頁，共七十二頁，2022年，8月28日

voidselectSort(inta[],constintn){

//對n個(gè)整數(shù)a[0],a[1],…,a[n-1]按遞增順序排序for(inti=0;i<n-1;i++){

intk=i;

//從a[i]查到a[n-1],找最小整數(shù),在a[k]

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

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

inttemp=a[i];a[i]=a[k];a[k]=temp;}}

第三十五頁，共七十二頁，2022年，8月28日模板(template)定義

適合多種數(shù)據(jù)類型的類定義或算法，在特定環(huán)境下通過簡單地代換，變成針對具體某種數(shù)據(jù)類型的類定義或算法。第三十六頁，共七十二頁，2022年，8月28日用模板定義用于排序的數(shù)據(jù)表類#ifndefDATALIST_H#defineDATALIST_H#include<iostream.h>//K是表項(xiàng)關(guān)鍵碼類型template<classK,classE> //E是表項(xiàng)類型classdataList{ private:E*element; intlistSize; voidswap(intm1,intm2);intminKey

(intlow,inthigh);第三十七頁，共七十二頁，2022年，8月28日

public:dataList

(intsize=10):listSize(size),element(new

E[size]){}~dataList(){delete[]element;} voidsort();friendostream&operator<<(ostream&

outStream,dataList<K,E>&outList);friendistream&operator>>(istream&

inStream,dataList<K,E>&inList);};

#endif第三十八頁，共七十二頁，2022年，8月28日類中所有操作作為模板函數(shù)的實(shí)現(xiàn)template<classK,classE>voiddataList

<K,E>::swap

(intm1,intm2){

//交換由m1,m2為下標(biāo)的數(shù)組元素的值Etemp=element

[m1];

element

[m1]=element

[m2];

element[m2]=temp;};第三十九頁，共七十二頁，2022年，8月28日template<classK,classE>intdataList<K,E>::minKey

(intlow,inthigh){//查找數(shù)組Element[low]到Element[high]中具//有最小關(guān)鍵碼值的表項(xiàng)，函數(shù)返回其位置intmin=low;for(inti=low+1,i<=high,i++) if(element[i]<element[min]) min=i; returnmin;};定義的重載操作第四十頁，共七十二頁，2022年，8月28日template<classK,classE>ostream&operator<<(ostream&outStream,

dataList<K,E>outList){outStream<<“輸出數(shù)組內(nèi)容:\n”;for(inti=0;i<outList.listSize;i++)

outStream<<outList.element[i];

outStream<<endl;ouStream<<“輸出數(shù)組當(dāng)前大小:”<<

outList.listSize<<endl;returnoutStream;}

第四十一頁，共七十二頁，2022年，8月28日

template<classK,classE>istream&

operator>>(istream&inStream,

dataList<K,E>inList){//輸入對象為inList，輸入流對象為inStream

cout<<“輸入數(shù)組當(dāng)前大小:”;

instream>>inList.listSize; cout<<“輸入數(shù)組元素值:\n”; for(inti=0;i<inList.listSize;i++){

cout

<<“元素”<<i<<“:”;

inStream>>inList.element[i];}returninStream;}第四十二頁，共七十二頁，2022年，8月28日template<classK,classE>voiddataList<K,E>::sort(){//按非遞減順序?qū)istSize個(gè)關(guān)鍵碼element[0]到//element[ArraySize-1]排序for(inti=0;i<=listSize-2;i++){intj=minKey(i,listSize-1);if(j!=i)swap(j,i);}}#endif第四十三頁，共七十二頁，2022年，8月28日使用模板的選擇排序算法的主函數(shù)

#include<iostream.h>

#include“dataList.h”constintSZ=10;intmain(){

structsick{

//患者

intkey;

char*name[15];intage;

char*address[30];

booloperator<(sick

x){returnkey<x.key;}

};

第四十四頁，共七十二頁，2022年，8月28日dataList<int,sick>TestList(SZ);

cin

>>TestList;

cout

<<TestList<<endl;TestList.Sort();

cout

<<TestList<<endl;

return0;}

定義對象時(shí)，代入實(shí)際數(shù)據(jù)類型重載友元操作標(biāo)準(zhǔn)I／O操作消息通信第四十五頁，共七十二頁，2022年，8月28日算法簡單性能分析與度量算法的性能標(biāo)準(zhǔn)算法的后期測試算法的事前估計(jì)第四十六頁，共七十二頁，2022年，8月28日算法的性能標(biāo)準(zhǔn)正確性(Correctness)

算法應(yīng)滿足具體問題的需求。可讀性(Readability)

算法應(yīng)該容易閱讀。以有利于閱讀者對程序的理解。效率效率指的是算法執(zhí)行的時(shí)間和空間利用率。通常這兩者與問題的規(guī)模有關(guān)。健壯性(Robustness)

算法應(yīng)具有容錯(cuò)處理的功能。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對其作出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。第四十七頁，共七十二頁，2022年，8月28日算法的后期測試對一個(gè)算法要作出全面的分析可分成兩個(gè)階段進(jìn)行，即事前分析和事后測試事前分析要求事前求出該算法的一個(gè)時(shí)間界限函數(shù)。事后測試則要求在算法執(zhí)行后通過算法執(zhí)行的時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料來分析。事后分析要求在算法中的某些部位插裝時(shí)間函數(shù)

time

()，測定算法完成某一功能所花費(fèi)時(shí)間。第四十八頁，共七十二頁，2022年，8月28日例如，給出順序搜索(SequenialSearch)算法intseqsearch(inta[],intn,intx){//在a[0],…,a[n-1]中搜索與給定值x相等的元//素，函數(shù)返回其位置，失敗返回-1。

inti=0;

while(i<n&&a[i]!=x)

i++;

if(i==n)return

-1;

returni;}

第四十九頁，共七十二頁，2022年，8月28日

插裝time()的計(jì)時(shí)程序

doublestart,stop;time(&start);

intk=seqsearch(a,n,x);time(&stop);

doublerunTime=stop-start;

cout<<""<<n<<""<<runTime<<endl;事實(shí)上，算法運(yùn)行時(shí)間要受輸入規(guī)模、利用編譯程序生成的目標(biāo)代碼的質(zhì)量、計(jì)算機(jī)程序指令系統(tǒng)的品質(zhì)和速度等制約。第五十頁，共七十二頁，2022年，8月28日算法的事前估計(jì)算法的事前估計(jì)主要包括時(shí)間復(fù)雜性和空間復(fù)雜性的分析：問題的規(guī)模：如：矩陣的階數(shù)、圖的結(jié)點(diǎn)個(gè)數(shù)、被分類序列的正整數(shù)個(gè)數(shù)等。時(shí)間復(fù)雜性：算法所需時(shí)間和問題規(guī)模的函數(shù)，記為T(n)。當(dāng)n

時(shí)的時(shí)間復(fù)雜性，稱為漸進(jìn)時(shí)間復(fù)雜性。空間復(fù)雜性：算法所需空間和問題規(guī)模的函數(shù)。記為S(n)。當(dāng)n時(shí)的時(shí)間復(fù)雜性，稱為漸進(jìn)空間復(fù)雜性。第五十一頁，共七十二頁，2022年，8月28日空間復(fù)雜度度量存儲空間的固定部分

程序指令代碼的空間，常數(shù)、簡單變量、定長成分(如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等)變量所占空間可變部分

尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和delete命令動態(tài)使用空間第五十二頁，共七十二頁，2022年，8月28日時(shí)間復(fù)雜度度量編譯時(shí)間運(yùn)行時(shí)間程序步語法上或語義上有意義的一段指令序列；執(zhí)行時(shí)間與問題規(guī)模無關(guān)；例如：聲明語句：程序步數(shù)為0;表達(dá)式：程序步數(shù)為1第五十三頁，共七十二頁，2022年，8月28日程序步確定方法插入計(jì)數(shù)全局變量count建表，列出個(gè)語句的程序步例以迭代方式求累加和的函數(shù)floatsum(floata[],intn){

floats=0.0;

for(inti=0;i<n;i++)s=s+a[i];

returns;}第五十四頁，共七十二頁，2022年，8月28日在求累加和程序中加入count語句floatsum(floata[],intn){float

s=0.0;count++; //count統(tǒng)計(jì)執(zhí)行語句條數(shù)

for(inti=0;i<n;i++){count+=2;//針對for語句 s+=a[i]; count++;//針對賦值語句} count+=2; //針對for的最后一次count++; //針對return語句

returns;}

執(zhí)行結(jié)束得程序步數(shù)count=3*n+4第五十五頁，共七十二頁，2022年，8月28日程序的簡化形式

voidsum(floata[],intn){for(inti=0;i<n;i++)count+=3;count+=4;}第五十六頁，共七十二頁，2022年，8月28日注意：

一個(gè)語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。

例如：賦值語句x=sum(R,n)本身程序步數(shù)為1；一次執(zhí)行對函數(shù)sum(R,n)的調(diào)用需要的程序步數(shù)為3*n+4；一次執(zhí)行的程序步數(shù)為

1+3*n+4=3*n+5第五十七頁，共七十二頁，2022年，8月28日計(jì)算累加和程序

程序步數(shù)計(jì)算工作表格第五十八頁，共七十二頁，2022年，8月28日時(shí)間復(fù)雜度的漸進(jìn)表示法例求兩個(gè)n階方陣的乘積C=ABvoidMatrixMultiply(intA[n][n],intB[n][n],

intC[n][n]){for(inti=0;i<n;i++)

…2n+2

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

…n(2n+2)

C[i][j]=0;

…n2

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

…n2(2n+2)

C[i][j]=C[i][j]+A[i][k]*B[k][j];

…n3

}}3n3+5n2+4n+2第五十九頁，共七十二頁，2022年，8月28日時(shí)間復(fù)雜度的漸進(jìn)表示法算法中所有語句的頻度之和是矩陣階數(shù)n的函數(shù)

T(n)=

3n3+5n2+4n+2一般地，稱n是問題的規(guī)模。則時(shí)間復(fù)雜度T(n)是問題規(guī)模n的函數(shù)。當(dāng)n趨于無窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級（階）稱為算法的漸進(jìn)時(shí)間復(fù)雜度

T(n)=O(n3)─大O表示法第六十頁，共七十二頁，2022年，8月28日加法規(guī)則針對并列程序段

T(n,m)=T1(n)+T2(m) =O(max(f(n),g(m)))

各種函數(shù)的增長趨勢

c<log2n<n<nlog2n<n2<n3<2n<3n<n!第六十一頁，共七十二頁，2022年，8月28日T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)變量計(jì)數(shù)for(inti=0;i<n;i++)

for(intj=0;j<n;j++)y++;T1

(n)=O(1)T2(n)=O(n)T3(n)=O(n2)x=0;y=0;for(intk=0;k<n;k++)x++;第六十二頁，共七十二頁，2022年，8月28日乘法規(guī)則針對嵌套程序段

T(n,m)=T1(n)*T2(m)

=O(f(n)*g(m))

漸進(jìn)的空間復(fù)雜度

S(n)=O(f(n))兩個(gè)并列循環(huán)的例子第六十三頁，共七十二頁，2022年，8月28日

voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){//x中各行

sum[i]=0.0;//數(shù)據(jù)累加

for(intj=0;j<n;j++) sum[i]+=x[i][j];

}

for(i=0;i<m;i++)//打印各行數(shù)據(jù)和

cout<<i<<“:”<<sum[i]<<endl;}

漸進(jìn)時(shí)間復(fù)雜度為O(max(m*n,m))第六十四頁，共七十二頁，2022年，8月28日起泡排序voidbubbleSort(inta[],intn){

//對表a[]逐趟比較,n是表當(dāng)前長度

for(inti=1;i<=n-1;i++){//n-1趟

for(intj=n-1;j>=i;j--)//n-i次比較

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

inttmp=a[j-1];a[j-1]=a[j];

a[j]=tmp;

} //一趟比較}}

第六十五頁，共七十二頁，2022年，8月28日漸進(jìn)時(shí)間復(fù)雜度O(f(n)*g(n))=

O(n2)

BubblrSort

外層循環(huán)

n-1趟內(nèi)層循環(huán)n-i

次比較第六十六頁，共七十二頁，2022年，8月28日有時(shí),算法的時(shí)間復(fù)雜度不僅依賴于問題規(guī)模n，還與輸入實(shí)例的初始排列有關(guān)。在數(shù)組A[n]

中查找給定值k

的算法：

inti=n