Python程序設(shè)計(jì)實(shí)踐 課件 ch02 問(wèn)題求解與計(jì)算思維

第二章問(wèn)題求解與計(jì)算思維浙江省普通本科高?！笆奈濉敝攸c(diǎn)教材Python程序設(shè)計(jì)實(shí)踐教程01計(jì)算概述PARTONE1.幾何法時(shí)期：割圓術(shù)最早計(jì)算圓周率的方法是割圓術(shù)。魏晉時(shí)期的數(shù)學(xué)家劉徽首創(chuàng)割圓術(shù)，為計(jì)算圓周率建立了嚴(yán)密的理論和完善的算法。所謂割圓術(shù)，就是不斷倍增圓內(nèi)接正多邊形的邊數(shù)，求出圓周率。劉徽從圓內(nèi)接正6邊形開(kāi)始，每次都把邊數(shù)加倍，直至圓內(nèi)接正96邊形，算得圓周率為157/50（即3.14）。后來(lái)，他在此基礎(chǔ)上又計(jì)算出了圓內(nèi)接正3072邊形的面積，得到圓周率的近似值為3927/1250（即3.1416）。南北朝時(shí)期的數(shù)學(xué)家祖沖之進(jìn)一步求出了圓內(nèi)接正12288邊形和圓內(nèi)接正24576邊形的面積，得出3.1415926<π<3.1415927。在之后的800年里，祖沖之計(jì)算出的圓周率是最準(zhǔn)確的。2.解析法時(shí)期：無(wú)窮級(jí)數(shù)分析法割圓術(shù)的煩瑣計(jì)算促使人們探索新的計(jì)算方法，通過(guò)無(wú)窮乘積、無(wú)窮連分?jǐn)?shù)、無(wú)窮級(jí)數(shù)等各種計(jì)算方法，圓周率的計(jì)算精度迅速增加。1706年，英國(guó)數(shù)學(xué)家梅欽率先將圓周率突破百位。1948年，英國(guó)的弗格森和美國(guó)的倫奇共同發(fā)表了π的808位小數(shù)值，成為人工計(jì)算圓周率的最高紀(jì)錄。

【例2-1】格里高利公式求圓周率利用格里高利公式（）求圓周率。3.計(jì)算機(jī)時(shí)期：蒙特卡羅法計(jì)算機(jī)的出現(xiàn)使圓周率的計(jì)算速度和精度有了突飛猛進(jìn)的發(fā)展。2011年10月16日，日本長(zhǎng)野縣飯?zhí)锸泄镜穆殕T近藤茂利用家用計(jì)算機(jī)將圓周率計(jì)算到小數(shù)點(diǎn)后10萬(wàn)億位。圖2-2圓及其外接正方形畫一個(gè)圓的外接正方形，假設(shè)圓的半徑是1，那么圓的面積是π，外接正方形的面積是4，如圖2-2所示。任意產(chǎn)生正方形內(nèi)的一個(gè)點(diǎn)，該點(diǎn)落在圓內(nèi)的概率=圓面積/正方形面積，即π/4。3.計(jì)算機(jī)時(shí)期：蒙特卡羅法蒙特卡羅法利用了概率統(tǒng)計(jì)的思想，使用隨機(jī)數(shù)來(lái)解決計(jì)算問(wèn)題。隨著實(shí)驗(yàn)次數(shù)增多，會(huì)出現(xiàn)概率收斂，計(jì)算值會(huì)更好地逼近精確解，這使求得的解是可以接受的。蒙特卡羅法在金融工程學(xué)、宏觀經(jīng)濟(jì)學(xué)、計(jì)算物理學(xué)等領(lǐng)域中有著廣泛的應(yīng)用。蒙特卡羅法利用了概率統(tǒng)計(jì)的思想，使用隨機(jī)數(shù)來(lái)解決計(jì)算問(wèn)題。隨著實(shí)驗(yàn)次數(shù)增多，會(huì)出現(xiàn)概率收斂，計(jì)算值會(huì)更好地逼近精確解，這使求得的解是可以接受的。蒙特卡羅法在金融工程學(xué)、宏觀經(jīng)濟(jì)學(xué)、計(jì)算物理學(xué)等領(lǐng)域中有著廣泛的應(yīng)用。02求解計(jì)算機(jī)問(wèn)題PARTTWO1.計(jì)算機(jī)解題的特性日常生活中有許多應(yīng)用順序流程的例子，炒菜時(shí)要根據(jù)一定的次序投放食材與調(diào)味品；網(wǎng)絡(luò)購(gòu)物時(shí)要通過(guò)規(guī)定的步驟完成購(gòu)物過(guò)程，如選擇商品、填寫數(shù)據(jù)、付款等；使用自動(dòng)提款機(jī)進(jìn)行交易時(shí)，需要依次完成插卡、輸入密碼、選擇金融交易方式、輸入金額等步驟。

當(dāng)我們要解決的問(wèn)題比較復(fù)雜時(shí)，可以將大問(wèn)題分成幾個(gè)較小的問(wèn)題，再設(shè)計(jì)較小問(wèn)題的解決方案。計(jì)算機(jī)解題的特性是根據(jù)所設(shè)計(jì)的步驟按順序執(zhí)行，每次執(zhí)行都會(huì)獲得一致的結(jié)果。由于垂直式思維的推理結(jié)論具有正確性、系統(tǒng)性、普遍性，所以大部分步驟能轉(zhuǎn)換成可以執(zhí)行的步驟。2.計(jì)算機(jī)解題的應(yīng)用（1）科學(xué)計(jì)算

科學(xué)計(jì)算是計(jì)算機(jī)應(yīng)用的一個(gè)重要領(lǐng)域，如高能物理、工程設(shè)計(jì)、地震預(yù)測(cè)、氣象預(yù)報(bào)、航天技術(shù)等。同時(shí)，由于計(jì)算機(jī)具有很高的運(yùn)算速度、精度及邏輯判斷能力，出現(xiàn)了計(jì)算力學(xué)、計(jì)算物理、計(jì)算化學(xué)、生物控制等新學(xué)科。（3）計(jì)算機(jī)輔助系統(tǒng)

計(jì)算機(jī)輔助系統(tǒng)包括計(jì)算機(jī)輔助設(shè)計(jì)（CAD）、計(jì)算機(jī)輔助工藝過(guò)程設(shè)計(jì)（CAPP）、計(jì)算機(jī)輔助制造（CAM）、計(jì)算機(jī)輔助教學(xué)（CAI）等。（2）數(shù)據(jù)處理

數(shù)據(jù)處理是指通過(guò)計(jì)算機(jī)獲取、加工、處理各種數(shù)據(jù)及數(shù)據(jù)可視化，提高管理效率，如管理信息系統(tǒng)（MIS）、物資需求計(jì)劃（MRP）、企業(yè)資源計(jì)劃（ERP）、制造執(zhí)行系統(tǒng)（MES）、電子商務(wù)系統(tǒng)等。2.計(jì)算機(jī)解題的應(yīng)用（4）生產(chǎn)自動(dòng)化

生產(chǎn)自動(dòng)化包括工業(yè)流程控制、流水線控制、無(wú)人工廠等。（6）生活出行

網(wǎng)絡(luò)信息資源的深層次利用和網(wǎng)絡(luò)應(yīng)用的日趨大眾化正在改變著我們的工作方式和生活方式。（5）人工智能

生產(chǎn)自動(dòng)化包括人臉識(shí)別、藥物研發(fā)、機(jī)器人、交通等場(chǎng)景應(yīng)用。3.計(jì)算機(jī)解題的基本步驟問(wèn)題分析與建模1對(duì)現(xiàn)實(shí)問(wèn)題進(jìn)行分析、抽象，建立相應(yīng)的數(shù)學(xué)模型，把對(duì)現(xiàn)實(shí)問(wèn)題的求解轉(zhuǎn)化為對(duì)抽象數(shù)學(xué)模型的求解，滿足計(jì)算機(jī)處理問(wèn)題的特點(diǎn)和基本要求。問(wèn)題分析與建模時(shí)首先要確定問(wèn)題的邏輯結(jié)構(gòu)和基本功能，然后在結(jié)合數(shù)學(xué)、物理、計(jì)算機(jī)等的基礎(chǔ)上，建立相關(guān)數(shù)學(xué)模型。數(shù)學(xué)建模是一種數(shù)學(xué)思考方法，是指運(yùn)用數(shù)學(xué)語(yǔ)言和方法，通過(guò)抽象、簡(jiǎn)化建立能近似刻畫并解決實(shí)際問(wèn)題。3.計(jì)算機(jī)解題的基本步驟算法設(shè)計(jì)與實(shí)現(xiàn)2算法設(shè)計(jì)與實(shí)現(xiàn)是指設(shè)計(jì)解決某一特定問(wèn)題或某一類問(wèn)題的一系列步驟，并且要求這些步驟可以通過(guò)計(jì)算機(jī)的基本操作來(lái)實(shí)現(xiàn)。算法設(shè)計(jì)完成后，要將其表示成計(jì)算機(jī)語(yǔ)言，從而能夠通過(guò)計(jì)算機(jī)來(lái)解決現(xiàn)實(shí)中的具體問(wèn)題。算法分析3算法分析是指對(duì)所設(shè)計(jì)算法的性能特征進(jìn)行分析、評(píng)價(jià)和總結(jié)。03計(jì)算思維PARTTHREE1.思維和思維過(guò)程

思維（Thinking）是人類對(duì)情感、信息處理過(guò)程的一種概括和抽象，是一種心理活動(dòng)的反映，是人腦從對(duì)客觀事物的直接感知過(guò)渡到抽象思維的升華，反映了客觀事物的本質(zhì)與規(guī)律。思維是通過(guò)一系列比較復(fù)雜的操作來(lái)實(shí)現(xiàn)的，如分析與綜合、比較、抽象與概括等，通常具有概括性、間接性、能動(dòng)性三大特性。1.思維和思維過(guò)程（1）概括性在人的感性基礎(chǔ)上，將一類事物的共同特性和本質(zhì)規(guī)律抽象出來(lái)，加以歸納與概括。例如，人類通過(guò)長(zhǎng)期對(duì)地球氣候和植物生長(zhǎng)規(guī)律的觀察，總結(jié)出了二十四節(jié)氣與種植時(shí)節(jié)。（2）間接性將非直接的事物作為媒介，來(lái)反映事物的特征或規(guī)律。例如，醫(yī)生根據(jù)醫(yī)學(xué)知識(shí)和臨床經(jīng)驗(yàn)，結(jié)合病人的癥狀和化驗(yàn)結(jié)果，推斷出病人的病情。（3）能動(dòng)性思維不僅能認(rèn)識(shí)和反映客觀規(guī)律，而且能改造客觀世界。例如，人類認(rèn)識(shí)了萬(wàn)有引力，還發(fā)射了人造衛(wèi)星、太空飛船。2.科學(xué)思維傳統(tǒng)的科學(xué)研究手段理論研究和實(shí)驗(yàn)研究，計(jì)算則是兩種研究的一種輔助手段。隨著計(jì)算技術(shù)和計(jì)算機(jī)技術(shù)的迅速發(fā)展，計(jì)算已上升為科學(xué)研究的一種手段，它直接并有效地為科學(xué)研究服務(wù)。科學(xué)思維（ScientificThinking）理論認(rèn)識(shí)及其過(guò)程，即通過(guò)整理和改造感性階段獲得的大量材料，形成概念、判斷、推理，反映事物的本質(zhì)和規(guī)律。2.科學(xué)思維理論思維（TheoreticalThinking）又稱為邏輯思維1通過(guò)抽象和概括，描述事物的本質(zhì)，用科學(xué)的方法探尋概念之間的聯(lián)系。它以推理和演繹為特征，以數(shù)學(xué)學(xué)科為代表。通過(guò)觀察和實(shí)驗(yàn)獲取自然規(guī)律、法則的一種思維方法。它以觀察和歸納自然規(guī)律為特征，以物理學(xué)科為代表。實(shí)驗(yàn)思維（ExperimentalThinking）又稱為實(shí)證思維22.科學(xué)思維計(jì)算思維（ComputationalThinking）又稱為構(gòu)造思維3從具體的算法設(shè)計(jì)規(guī)范入手，通過(guò)算法過(guò)程的構(gòu)造與實(shí)施來(lái)解決特定問(wèn)題。它以設(shè)計(jì)和構(gòu)造為特征，以計(jì)算學(xué)科為代表。3.理解計(jì)算思維

計(jì)算思維的認(rèn)識(shí)過(guò)程計(jì)算思維的定義計(jì)算思維的特征計(jì)算機(jī)科學(xué)與計(jì)算思維010203044.計(jì)算思維的應(yīng)用計(jì)算生物學(xué)1計(jì)算生物學(xué)是生物學(xué)的一個(gè)分支，用于開(kāi)發(fā)和應(yīng)用數(shù)據(jù)分析及理論、數(shù)學(xué)建模、計(jì)算機(jī)仿真等，并應(yīng)用于生物學(xué)、行為學(xué)、社會(huì)群體研究的一門學(xué)科，如基因測(cè)序、蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)等。4.計(jì)算思維的應(yīng)用計(jì)算化學(xué)2計(jì)算化學(xué)主要用計(jì)算機(jī)程序和方法對(duì)特定的化學(xué)問(wèn)題進(jìn)行研究，如數(shù)值計(jì)算（量子化學(xué)和結(jié)構(gòu)化學(xué)中的演繹計(jì)算、分析化學(xué)中的條件模擬、化工過(guò)程中的應(yīng)用計(jì)算等）、化學(xué)模擬、模式識(shí)別等。4.計(jì)算思維的應(yīng)用計(jì)算數(shù)學(xué)3計(jì)算數(shù)學(xué)也叫作數(shù)值計(jì)算方法或數(shù)值分析，如數(shù)值計(jì)算和分析、系統(tǒng)建模和仿真、數(shù)字信號(hào)處理、數(shù)據(jù)可視化、財(cái)務(wù)與金融工程計(jì)算、軟件機(jī)器人等。4.計(jì)算思維的應(yīng)用其他學(xué)科領(lǐng)域4許多其他學(xué)科通過(guò)抽象建模，將研究從定性分析轉(zhuǎn)化為定量研究，將計(jì)算思維應(yīng)用于經(jīng)濟(jì)學(xué)、管理科學(xué)、法學(xué)、文學(xué)、藝術(shù)、體育等社會(huì)科學(xué)領(lǐng)域。計(jì)算思維改變了各學(xué)科領(lǐng)域的研究模式，如計(jì)算機(jī)博弈論改變了經(jīng)濟(jì)學(xué)家的思考方法。1994年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)授予約翰·納什（JohnNash）、萊茵哈德·澤爾騰（ReinhardSelten）、約翰·海薩尼（JohnC.Harsanyi）三位博弈論專家，他們有力地證明了博弈論在現(xiàn)代經(jīng)濟(jì)學(xué)中的地位。5.為什么要倡導(dǎo)計(jì)算思維計(jì)算思維就是用計(jì)算機(jī)科學(xué)解決問(wèn)題的思維，它是每個(gè)人都應(yīng)該具備的基本技能，不僅僅屬于計(jì)算機(jī)科學(xué)家。計(jì)算思維訓(xùn)練對(duì)計(jì)算機(jī)應(yīng)用人才的培養(yǎng)是極為重要的，它不僅能使學(xué)生理解計(jì)算機(jī)的實(shí)現(xiàn)機(jī)制和約束條件，有利于學(xué)生進(jìn)行發(fā)明和創(chuàng)新，更重要的是有利于提高學(xué)生的信息素養(yǎng)，也就是處理計(jì)算機(jī)問(wèn)題時(shí)應(yīng)有的思維方法、表達(dá)形式、行為習(xí)慣。因此，提高計(jì)算機(jī)基礎(chǔ)教學(xué)的質(zhì)量，增強(qiáng)學(xué)生的計(jì)算思維能力，是培養(yǎng)應(yīng)用型、創(chuàng)新型人才的必然要求。盡管計(jì)算機(jī)科學(xué)不等于程序設(shè)計(jì)，但不可否認(rèn)的是，學(xué)習(xí)程序設(shè)計(jì)方法是理解計(jì)算機(jī)的最好途徑。編程思維是無(wú)止境的，不同問(wèn)題有不同的分析方法、算法、代碼實(shí)現(xiàn)方法。在教學(xué)中有意識(shí)地引導(dǎo)學(xué)生多視角、多方位地進(jìn)行編程思考，會(huì)使學(xué)生的思維能力得到跳躍式擴(kuò)展和提高。（1）計(jì)算思維與數(shù)學(xué)基礎(chǔ)的構(gòu)建計(jì)算機(jī)科學(xué)在本質(zhì)上源于數(shù)學(xué)思維，它的形式化解析基礎(chǔ)筑于數(shù)學(xué)之上。（2）計(jì)算思維與計(jì)算機(jī)科學(xué)導(dǎo)論的學(xué)習(xí)為了對(duì)計(jì)算機(jī)科學(xué)的課程體系和知識(shí)體系有比較清晰的了解，必須站在計(jì)算思維的高度和廣度來(lái)了解和掌握計(jì)算機(jī)學(xué)科的基本概念、基本方法、發(fā)展趨勢(shì)，知曉學(xué)科的內(nèi)涵和本質(zhì)，將其作為計(jì)算機(jī)科學(xué)的導(dǎo)學(xué)部分。6.如何培養(yǎng)和訓(xùn)練計(jì)算思維（3）計(jì)算思維與思維能力的培養(yǎng)計(jì)算思維是人類求解問(wèn)題的一條途徑。過(guò)去，人們認(rèn)為計(jì)算機(jī)科學(xué)家的思維就是用計(jì)算機(jī)去編程，這種認(rèn)識(shí)是片面的。計(jì)算思維不僅是程序化的，而是在抽象的多個(gè)層次上進(jìn)行思維。（4）計(jì)算思維與應(yīng)用能力的培養(yǎng)目前，計(jì)算機(jī)應(yīng)用已經(jīng)深入到各行各業(yè)中，融入人類活動(dòng)中，解決了大量計(jì)算時(shí)代之前無(wú)法解決的問(wèn)題。（5）計(jì)算思維與創(chuàng)新能力的培養(yǎng)創(chuàng)新是一個(gè)民族生存、發(fā)展和進(jìn)步的原動(dòng)力。計(jì)算思維的培養(yǎng)對(duì)創(chuàng)新能力的培養(yǎng)至關(guān)重要，創(chuàng)新要靠科學(xué)素養(yǎng)和理解科學(xué)，靠科學(xué)的思想方法。6.如何培養(yǎng)和訓(xùn)練計(jì)算思維04算法PARTFOUR1.算法及其描述算法概述1算法解決特定問(wèn)題的方法或步驟，或者說(shuō)，算法是為解決一類特定問(wèn)題而設(shè)計(jì)的確定的、有限的操作步驟。算法是程序設(shè)計(jì)的關(guān)鍵，找不到算法就無(wú)法編寫計(jì)算機(jī)程序，也就無(wú)法用計(jì)算機(jī)來(lái)解決問(wèn)題。廣義上

算法是指通過(guò)運(yùn)算的方式，按照某種機(jī)械的步驟逐步求解問(wèn)題。狹義上

算法是解決一個(gè)問(wèn)題采取的方法和步驟的描述，如圖2-8所示。圖2-8狹義的算法1.算法及其描述算法的分類2不是所有算法都適合在計(jì)算機(jī)上執(zhí)行，能在計(jì)算機(jī)上執(zhí)行的算法就是計(jì)算機(jī)算法。計(jì)算機(jī)算法可以分為兩類：一類是數(shù)值算法，另一類是非數(shù)值算法。1.算法及其描述算法的特性3（1）有窮性一個(gè)算法必須在執(zhí)行有限個(gè)計(jì)算步驟后終止。（2）確定性一個(gè)算法給出的每個(gè)計(jì)算步驟都必須是精確定義、無(wú)二義性的。（3）有效性算法中的每個(gè)步驟都必須被有效地執(zhí)行，并能得到確定的結(jié)果。（4）有零個(gè)或多個(gè)輸入信息一個(gè)算法可以沒(méi)有輸入信息，也可以有一個(gè)或多個(gè)輸入信息，這些輸入信息是算法的初始數(shù)據(jù)。（5）有一個(gè)或多個(gè)輸出信息一個(gè)算法應(yīng)有一個(gè)或多個(gè)輸出信息，沒(méi)有輸出信息的算法是沒(méi)有意義的。1.算法及其描述如何發(fā)現(xiàn)算法4（1）第一階段：分析、理解、抽象、歸納問(wèn)題。（2）第二階段：尋找一個(gè)可能解決問(wèn)題的思路。（3）第三階段：用數(shù)學(xué)語(yǔ)言將其表達(dá)出來(lái)。（4）第四階段：闡明算法并選用合適的數(shù)據(jù)結(jié)構(gòu)，用程序?qū)⑵渚帉懗鰜?lái)。（5）第五階段：評(píng)估算法的準(zhǔn)確度以及算法是否有潛力作為一個(gè)解決問(wèn)題的工具。2.算法的表示形式自然語(yǔ)言1自然語(yǔ)言就是人們?nèi)粘Ｊ褂玫恼Z(yǔ)言，可以是漢語(yǔ)、英語(yǔ)或其他語(yǔ)言。用自然語(yǔ)言表示算法的優(yōu)點(diǎn)是通俗易懂，缺點(diǎn)是文字冗長(zhǎng)，容易出現(xiàn)歧義性。偽代碼2偽代碼是介于自然語(yǔ)言和計(jì)算機(jī)語(yǔ)言之間的文字和符號(hào)（包括數(shù)學(xué)符號(hào)），如同寫一篇文章，自上而下地寫下來(lái)，每一行（或幾行）表示一個(gè)基本操作。偽代碼不使用圖形符號(hào)，因此書(shū)寫方便、格式緊湊，也比較易懂，便于向計(jì)算機(jī)語(yǔ)言程序轉(zhuǎn)換。2.算法的表示形式流程圖3流程圖是一種傳統(tǒng)的算法表示方法，它使用不同的幾何圖形框來(lái)代表不同性質(zhì)的操作，用流程線來(lái)指示算法的執(zhí)行方向。流程圖直觀形象、易于理解，所以應(yīng)用廣泛。05數(shù)據(jù)結(jié)構(gòu)PARTFIVE1.數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)（DataStructure）計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)主要包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的物理（存儲(chǔ)）結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算結(jié)構(gòu)。2.常用的數(shù)據(jù)結(jié)構(gòu)（1）數(shù)組（Array）在程序設(shè)計(jì)算法中，為了處理方便，把具有相同類型的若干變量有序地組織起來(lái)，這些按序排列的同類數(shù)據(jù)元素的集合稱為數(shù)組。數(shù)組是n（n>1）個(gè)相同類型的數(shù)據(jù)元素a0，a1，…，an-1構(gòu)成的有限序列，該有限序列存儲(chǔ)在一塊地址連續(xù)的內(nèi)存單元中，可以把它看作一種長(zhǎng)度固定的線性表。（2）棧（Stack）棧是只能在某一端插入和刪除數(shù)據(jù)的特殊線性表。它按照“先入后出”的原則存儲(chǔ)數(shù)據(jù)，先進(jìn)入的數(shù)據(jù)被壓入棧底，最后進(jìn)入的數(shù)據(jù)在棧頂，讀取數(shù)據(jù)時(shí)從棧頂開(kāi)始彈出數(shù)據(jù)（最后進(jìn)入的數(shù)據(jù)第一個(gè)被讀?。鐖D2-11所示。特點(diǎn)：先入后出、后入先出；除了頭、尾節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)后繼和一個(gè)前驅(qū)。2.常用的數(shù)據(jù)結(jié)構(gòu)（3）隊(duì)列（Queue）隊(duì)列是一種特殊的線性表，它只允許在表的前端（Front）進(jìn)行刪除操作，以及在表的后端（Rear）進(jìn)行插入操作。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列是按照“先入先出”和“后入后出”的原則組織數(shù)據(jù)的。隊(duì)列中沒(méi)有元素時(shí)稱為空隊(duì)列。特點(diǎn)：先入先出，后入后出；除了尾節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)后繼；除了頭節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有一個(gè)前驅(qū)。（4）鏈表（LinkedList）鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，它既可以表示線性結(jié)構(gòu)，也可以表示非線性結(jié)構(gòu)。數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。每個(gè)節(jié)點(diǎn)包括兩部分，一是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，二是存儲(chǔ)下個(gè)節(jié)點(diǎn)地址的指針域。2.常用的數(shù)據(jù)結(jié)構(gòu)（5）樹(shù)（Tree）樹(shù)是由n（n≥0）個(gè)節(jié)點(diǎn)組成的有限集合，若n=0，稱為空樹(shù)；若n>0，則滿足以下兩個(gè)條件。①有一個(gè)特定的稱為根（Root）的節(jié)點(diǎn)，它只有直接后繼，但沒(méi)有直接前驅(qū)。②除根節(jié)點(diǎn)以外的其他節(jié)點(diǎn)可以劃分為m（m≥0）個(gè)互不相交的有限集合（T0,T1,…,Tm-1），集合Ti（i=0,1,…,m-1）又是一棵樹(shù)，稱為根的子樹(shù)。（6）圖（Graph）圖由節(jié)點(diǎn)的有窮集合V和邊的集合E組成。為了與樹(shù)形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常將節(jié)點(diǎn)稱為頂點(diǎn)，邊是頂點(diǎn)的有序偶對(duì)。如果兩個(gè)頂點(diǎn)之間存在一條邊，就表示這兩個(gè)頂點(diǎn)具有相鄰關(guān)系。圖被廣泛應(yīng)用于各個(gè)領(lǐng)域，可以解決很多實(shí)際問(wèn)題。圖的應(yīng)用有求最短路徑、拓?fù)渑判?、關(guān)鍵路徑等。06算法評(píng)價(jià)PARTSIX1.算法的評(píng)價(jià)標(biāo)準(zhǔn)（1）正確性：算法的執(zhí)行結(jié)果應(yīng)當(dāng)滿足規(guī)定的功能和性能要求。（2）可讀性：算法應(yīng)當(dāng)思路清晰、層次分明、簡(jiǎn)單明了、易讀易懂。（3）健壯性：算法應(yīng)具有對(duì)不合理數(shù)據(jù)的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。。（4）高效性：算法應(yīng)有較高的時(shí)間效率。（5）低存儲(chǔ)量需求：存儲(chǔ)量是指算法執(zhí)行過(guò)程中需要的最大存儲(chǔ)空間，即有效使用存儲(chǔ)空間。2.時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度（TimeComplexity）是指算法運(yùn)行的時(shí)間，是算法所求解的問(wèn)題規(guī)模n的函數(shù)，通常記為T(n)。時(shí)間復(fù)雜度是算法的時(shí)間代價(jià)，用執(zhí)行算法所需的基本操作（原操作）次數(shù)來(lái)描述，以基