數(shù)據(jù)結(jié)構(gòu)2015課件introduction

對象=算法+數(shù)據(jù)結(jié)構(gòu)AlgorithmandData高級程序語言設(shè)計3 - B+96.)

#

=C %%%%4- @6- H Algorithm—thekingpinData—variables,databases,Abstraction—conceptualizing,Query—search,conditionals,Sensing&Feedback—robotics迭代Iterations—loops,recursion系統(tǒng)Systems6Asking:Whatisthepowerandlimitofhumanandcomputerintelligence?Asking:Howdifficultistheproblem?Asking:Howcanitbesolved?Asking:HowcantechnologybeappliedtotheAsking:Whatcomputationalstrategiesmightbe77數(shù)據(jù)結(jié)構(gòu)（C語言描述）（修訂版）工業(yè)出版社2014年1月數(shù)據(jù)結(jié)構(gòu)與算法分析——C語言描述（美）MarkAllenWeiss著 馮舜璽譯機械工業(yè)出版社 嚴慰敏清華大學(xué)出版搜索（第三版）美）RobertSedgewick著 算法V（C++實現(xiàn)）——圖算法（第三版）（美）RobertSedgewick著 8SOMETHING啊哈！算法人民郵電出版社，2014年/（visualizingdatastructuresandalgorithmsthroughanimation）網(wǎng)易公開課/國際名校公開課PAT-計算機程序設(shè)計能力考試Google中國、Baidu等企業(yè)優(yōu)先錄用PAT成績優(yōu)2013.11.2第一部 引 第三部 排序與選

樹圖對象=算法+數(shù)據(jù)結(jié)構(gòu)分析問 算法設(shè) 數(shù)學(xué)抽象數(shù)學(xué)問

個較小圓盤的移動問題，以此類推，直至voidhanoi(intn，inta，intb，int{hanoi(n-1,}}Step1Step doStepn1968年美國唐.歐.克努特教授（中文名字高德納，1938~，現(xiàn)代計算機科學(xué)的鼻祖，1974年圖靈獎獲得者）所著的《計算機程序設(shè)計藝術(shù)》（目前正在撰寫第六卷）其操作的著作1999年底被AmericanScientist列為20世界最佳{intlongresult;for(inti=0;i<x;{}}{intlongresult;for(inti=0;i<x;{/*result=2*x;*/result=x+x;}}int–32768~23767+,- 數(shù)組結(jié)構(gòu)記錄結(jié)構(gòu)數(shù)據(jù)類型(Data（本身也是一個復(fù)雜數(shù)據(jù)類型AbstractDataType,優(yōu)勢（P.9-Step1Step doStepn分析問 算法設(shè) 數(shù)學(xué)抽象數(shù)學(xué)問

〖ExampleInsertionSort(方法：Fromthoseintegersthatarecurrentlyunsorted,findthesmallestandplaceitnextinthesortedlist.（自然語言描述）for(i=0;i<n;i++)Examinelist[0]tolist[n-1]andsupposethattheintegerisatInterchangelist[i]and}

Algorithmin可行性：合法輸入正確輸出{process_serial_cmds();*處理串行輸入*/process_kbd_cmds();*處理鍵盤輸入*/adjust_ctrlr_parms();/*調(diào)整CPU參數(shù)*/counter++;/*counter遞增*/} 實例二：插入排序算法（InsertionSort） Matrixvoidadd(

a[][MAX_SIZEb[][MAX_SIZEc[][MAX_SIZErows,intcols{ i,jfor(i=0;i<rows;i++)for(j=0;j<cols;j++)c[i][j]=a[i][j]+b[i][j}

???????????????T(rows,cols)=2*rows*cols+rows+1S(rows,cols)=3*rows*cols+4 實例二：插入排序算法（InsertionSort）INSERTANELEMENTTOASORTEDLISTInput1：listis23567Newelement:InsertthenewelementatthefirstofthelistInput2: listis235678Newelement:InsertthenewelementatthelastofthelistInput3: listis235678Newelement:InsertthenewelementatthemiddleoftheINSERTANELEMENTTOASORTEDLISTInput1：listis23567Newelement: 1??InsertthenewelementatthefirstofthelistInput2: listis235678Newelement: 6??InsertthenewelementatthelastofthelistInput3: listis235678Newelement: 3??Insertthenewelementatthemiddleofthe最壞情況下Tmax(n)=max{t(i)|i∈Dn}最好情況下Tmin(n)=min{t(i)|i∈Dn}情況下Tavg(n)=∑p(i)t(i)（i∈Dn）N→T(N)N→∞時，(T(N)-t(N)T(N)t(N)是T(N)當N→t(N)是T(N)略去低階項留下的主項，比T(n漸近上界符號g(n)f(n)為定義在正數(shù)集上的正函數(shù)f(n)＝O(g(n))使得對所有nn0有：0≤f(n)≤cg(n)2.7N^3+3.8N^2+5.3＝O(N^3)=O(N^4)反例：2.7N^3+3.8N^2+5.3≠O(N^2)O(f)+O(g)=O(max(f,g))O(f)+O(g)=O(f+g)O(f)*O(g)=O(f*g)O(cf)=O(f)g=O(f)可以推導(dǎo)得到O(f)+O(g)O(f)f(n)＝Ω使得對所有n≥n0有0cg(n)2.7N^3+3.8N^2+5.3＝Ω(N^3)=Ω(N^2)反例：2.7N^3+3.8N^2+5.3≠O(N^4)θ同階：f(n)=O(g(n))且f(n)=of(n)＝存在正常數(shù)ε和使得對所有n≥n0有Timeforf(n)instructionsona10^9instr/secnus=microsecond=10-6secondsms=millisecond=10-3secondssec=

min=minuteshr=hoursd=

yr= }T(n)O(n問題描述：已知n個元素存放在區(qū)間[first:last)中，是否等于value，如果不是，就繼續(xù)往下搜索，一直到找到某個數(shù)據(jù)等于value或者搜索整個區(qū)間發(fā)while(first!=last&&returnfirst;=(1-

half=len>>1;//除以2middle=first+half;//中點{first=middle;len=0;}

if 如果value>*middle，接 來的搜索只需要在后半部 進

}}最壞情況：元素value不在數(shù)組中，while E=6

Y#V-1

G% " AVL, Given(possiblynegative)integersA1,A2,…,AN,findmaximumvalue

AkintMaxSubsequenceSum(constintA[],intN{intThisSum,MaxSum,i,j,/* MaxSum= /*initializethemaximumsum/* for(i=0;i<N;i++)/*startfromA[i]/* for(j=i;j<N;j++) /*endatA[j]/* ThisSum=/* for(k=i;k<=j;k++/* ThisSum+=A[k];/*sumfromA[i]toA[j]/* if(ThisSum>MaxSum/* MaxSum=ThisSum;/*updatemaxsum/* return T(N)=O(N3intMaxSubsequenceSum(constintA[],intN{intThisSum,MaxSum,i,/* MaxSum= /*initializethemaximumsum/* for(i=0;i<N;i++) /*startfromA[i]/* ThisSum=/* for(j=i;j<N;j++) /*endatA[j]/* ThisSum+=A[j];/*sumfromA[i]toA[j]/* if(ThisSum>MaxSum/* MaxSum=ThisSum;/*updatemaxsum}/*endforTj}/*endforTi/* return}T(N)=O(N2遞歸的概念（C

intfactorial(int{if(n==0)return1;returnn*factorial(n-1);實例2：Fibonacci數(shù) intfibonacci(int{if(n<=1)returnreturnfibonacci(n-1)+fibonacci(n-}當n=1時，perm(R)=(r),其中r是集合R中唯(r1)perm(R1)，(r2)perm(R2)，…，(rn)

voidperm(intlist[],intk,int int for(i