數(shù)據(jù)結(jié)構(gòu)第一章1第1頁(yè)，共34頁(yè)，2023年，2月20日，星期六本次課堂教學(xué)內(nèi)容課程簡(jiǎn)介教學(xué)環(huán)節(jié)組成教材和教學(xué)參考書(shū)教學(xué)要求任課教師簡(jiǎn)介第一章概述2第2頁(yè)，共34頁(yè)，2023年，2月20日，星期六課程簡(jiǎn)介“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)類專業(yè)重要的專業(yè)技術(shù)基礎(chǔ)課程，是提高軟件設(shè)計(jì)水平以及學(xué)習(xí)后續(xù)課程所必需的基礎(chǔ)。課程中介紹軟件設(shè)計(jì)中常用的基本技術(shù)，包括：常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)及其在計(jì)算機(jī)中的存儲(chǔ)結(jié)構(gòu)和各種操作的實(shí)現(xiàn)：線性表、串、棧、隊(duì)列、數(shù)組、樹(shù)和二叉樹(shù)、圖、文件等軟件設(shè)計(jì)中常用的排序和查找方法及其性能?；舅惴ㄔO(shè)計(jì)技術(shù)通過(guò)對(duì)這些內(nèi)容的學(xué)習(xí)，熟練地掌握各種常用結(jié)構(gòu)的特性，各種運(yùn)算的實(shí)現(xiàn)方法及其性能，并能在實(shí)際應(yīng)用中根據(jù)具體問(wèn)題的要求設(shè)計(jì)出合理的數(shù)據(jù)結(jié)構(gòu)和運(yùn)算。然而，由于該課程中的內(nèi)容多，而且許多內(nèi)容較抽象，特別是其中大量的算法以及所用到的遞歸技術(shù)，以及缺乏有效的實(shí)驗(yàn)條件，使學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的難度較大。3第3頁(yè)，共34頁(yè)，2023年，2月20日，星期六教學(xué)環(huán)節(jié)組成整個(gè)課程的教學(xué)包括：課堂教學(xué)、實(shí)驗(yàn)教學(xué)和課程設(shè)計(jì)。共有6.5個(gè)學(xué)分課堂教學(xué)：64課時(shí)1-16周，周學(xué)時(shí)4，保留一周備用系統(tǒng)學(xué)習(xí)相關(guān)的知識(shí)體系和應(yīng)用方法----基礎(chǔ)理論實(shí)驗(yàn)教學(xué)：16學(xué)時(shí)由多個(gè)實(shí)驗(yàn)單元組成，以上機(jī)調(diào)試算法和程序的形式，分別圍繞各部分的知識(shí)及其應(yīng)用方法，驗(yàn)證、綜合運(yùn)用所學(xué)知識(shí)，提高解決實(shí)際問(wèn)題的能力。課程設(shè)計(jì)：集中1周半時(shí)間對(duì)具有更大規(guī)模的，以數(shù)據(jù)結(jié)構(gòu)方法和技術(shù)為主要手段，通過(guò)綜合性設(shè)計(jì)方式，實(shí)現(xiàn)問(wèn)題求解。在此基礎(chǔ)上，撰寫(xiě)設(shè)計(jì)報(bào)告，描述求解的相關(guān)方法。4第4頁(yè)，共34頁(yè)，2023年，2月20日，星期六教材和參考書(shū)教材：數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)，C++語(yǔ)言描述（英文版），RobertL.Kruse,AlexanderJ.Ryba，高等教育出版社)。

教材和參考書(shū)照片\高教社外文版教材.JPG《計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)軟件系列課程實(shí)踐教程》，胡學(xué)鋼，王浩主編，合肥工業(yè)大學(xué)出版社，2005。

教材和參考書(shū)照片\實(shí)踐教程.JPG說(shuō)明：每本教材都有其優(yōu)點(diǎn)和適用條件，但也存在不足。不能僅限于一本教材，需多方面參考，應(yīng)多讀幾本，互為補(bǔ)充。5第5頁(yè)，共34頁(yè)，2023年，2月20日，星期六教材和參考書(shū)（2）教學(xué)參考書(shū)：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版），嚴(yán)蔚敏，吳偉民編著，清華大學(xué)出版社，1999?！稊?shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)指導(dǎo)》，胡學(xué)鋼著，清華大學(xué)出版社，1999?！稊?shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》，胡學(xué)鋼主編，高等教育出版社，2008。1。

教材和參考書(shū)照片\胡學(xué)鋼教材.JPG6第6頁(yè)，共34頁(yè)，2023年，2月20日，星期六學(xué)習(xí)要求和建議

教學(xué)的每個(gè)方面都是圍繞總體目標(biāo)來(lái)開(kāi)展的，有自身的教學(xué)目標(biāo)和規(guī)律，不僅需要投入精力，而且還要注意學(xué)習(xí)方法。為此，提出如下的學(xué)習(xí)要求和建議。課堂教學(xué)是構(gòu)建完整知識(shí)體系的關(guān)鍵關(guān)于知識(shí)體系：包括多個(gè)方面（知識(shí)點(diǎn)）----顯現(xiàn)的靜態(tài)性知識(shí)各知識(shí)點(diǎn)間具有一定的聯(lián)系----隱含的動(dòng)態(tài)性知識(shí)，例如，關(guān)于某項(xiàng)知識(shí)的背景，解決問(wèn)題的方法和技術(shù)，可能存在的問(wèn)題，求解方法的性能及其選擇方法，應(yīng)用價(jià)值等。對(duì)知識(shí)體系的教學(xué)任課教師在教學(xué)過(guò)程中，會(huì)以多種方式，結(jié)合自己的教學(xué)、研究積累來(lái)介紹，引導(dǎo)建立知識(shí)體系。學(xué)習(xí)中，不僅要理解和掌握各知識(shí)點(diǎn)，同時(shí)還要注意知識(shí)點(diǎn)之間的聯(lián)系，學(xué)會(huì)用發(fā)展的觀點(diǎn)來(lái)理解知識(shí)，掌握能力。各教學(xué)環(huán)節(jié)，包括課堂教學(xué)、作業(yè)、復(fù)習(xí)、實(shí)驗(yàn)和課程設(shè)計(jì)，都是圍繞此目的來(lái)開(kāi)展的。7第7頁(yè)，共34頁(yè)，2023年，2月20日，星期六學(xué)習(xí)要求和建議（續(xù)1）課堂教學(xué)的要求：不曠課、遲到、早退------保持聽(tīng)課和知識(shí)的完整性。事先作必要的預(yù)習(xí)------有備而來(lái)，主動(dòng)學(xué)習(xí)，而不是被動(dòng)學(xué)習(xí)認(rèn)真聽(tīng)課，記筆記------便于后續(xù)的復(fù)習(xí)和回憶，因?yàn)閱渭兊穆?tīng)課達(dá)不到“完全錄音”的效果。認(rèn)真完成作業(yè)：幫助復(fù)習(xí)、深化，乃至綜合理解和運(yùn)用知識(shí)提交作業(yè)，作業(yè)本，電子信箱，網(wǎng)站平時(shí)成績(jī)的計(jì)算方法，考試的門檻總結(jié)和復(fù)習(xí)：學(xué)習(xí)需要不斷升華，提升對(duì)知識(shí)的理解深度。

--------從厚到薄，從薄到厚

--------實(shí)踐，認(rèn)識(shí)，再實(shí)踐，再認(rèn)識(shí)

--------溫故而知新考勤的要求：必要的督促，作為平時(shí)成績(jī)的組成部分。必須學(xué)會(huì)按照規(guī)則辦事。8第8頁(yè)，共34頁(yè)，2023年，2月20日，星期六學(xué)習(xí)要求和建議（續(xù)2）實(shí)驗(yàn)教學(xué)作為教學(xué)的重要組成部分關(guān)于實(shí)踐：實(shí)踐是認(rèn)識(shí)的源泉。實(shí)踐是檢驗(yàn)知識(shí)的唯一標(biāo)準(zhǔn)。實(shí)踐是培養(yǎng)能力的基礎(chǔ)。實(shí)踐是創(chuàng)新的保證。用人單位，尤其是企業(yè)需要有實(shí)踐經(jīng)歷的畢業(yè)生。實(shí)踐教學(xué)是實(shí)現(xiàn)教學(xué)目標(biāo)的重要組成部分是檢驗(yàn)和深化理論知識(shí)的重要手段實(shí)際解決問(wèn)題的能力培養(yǎng)創(chuàng)新意識(shí)和能力的培養(yǎng)良好治學(xué)態(tài)度的培養(yǎng)9第9頁(yè)，共34頁(yè)，2023年，2月20日，星期六學(xué)習(xí)要求和建議（續(xù)3）實(shí)驗(yàn)教學(xué)的要求每項(xiàng)實(shí)驗(yàn)任務(wù)都是需要完成的。實(shí)驗(yàn)前，要認(rèn)真準(zhǔn)備：理解教學(xué)要求，編寫(xiě)實(shí)驗(yàn)程序，組織好實(shí)驗(yàn)數(shù)據(jù)，并估計(jì)可能出現(xiàn)的問(wèn)題。提交實(shí)驗(yàn)預(yù)習(xí)報(bào)告。（上網(wǎng)）實(shí)驗(yàn)過(guò)程中：認(rèn)真觀察過(guò)程，記錄數(shù)據(jù)和結(jié)果，并分析有關(guān)的原因，及時(shí)調(diào)整。實(shí)驗(yàn)后：在系統(tǒng)分析試驗(yàn)數(shù)據(jù)和結(jié)果的基礎(chǔ)上，對(duì)相關(guān)的原理進(jìn)行總結(jié)。提交實(shí)驗(yàn)報(bào)告，培養(yǎng)良好的治學(xué)態(tài)度，掌握描述規(guī)范。平時(shí)成績(jī)的計(jì)算方法，考試的門檻10第10頁(yè)，共34頁(yè)，2023年，2月20日，星期六學(xué)習(xí)要求和建議（續(xù)4）課程設(shè)計(jì)：綜合型、提高性的設(shè)計(jì)訓(xùn)練課程設(shè)計(jì)的要求：選題：能達(dá)到充分的鍛煉----量力而行，認(rèn)真設(shè)計(jì)：?jiǎn)栴}建模，數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，算法設(shè)計(jì)，性能指標(biāo)要求，求解性能分析撰寫(xiě)設(shè)計(jì)報(bào)告：作為一種基本的能力敘述設(shè)計(jì)，并作必要的分析和描述培養(yǎng)嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度未來(lái)工作中的基本能力：業(yè)務(wù)報(bào)告，學(xué)術(shù)論文，畢業(yè)論文，著作，工作報(bào)告等。成績(jī)?cè)u(píng)定的依據(jù)11第11頁(yè)，共34頁(yè)，2023年，2月20日，星期六全課程的內(nèi)容第一章概述第二章順序棧第三章順序隊(duì)列第四章鏈棧和鏈隊(duì)列第五章線性表第六章遞歸技術(shù)第七章樹(shù)和二叉樹(shù)第八章圖結(jié)構(gòu)第九章查找第十章排序第十一章數(shù)組和廣義表12第12頁(yè)，共34頁(yè)，2023年，2月20日，星期六任課教師簡(jiǎn)介胡學(xué)鋼1983年7月任教至今，先后主講十多門本科和研究生課程。愿望：希望自己的學(xué)生都能成才，并為此而不斷地探索和努力。希望成為學(xué)生的知心朋友！現(xiàn)在的基本情況如下：合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院副院長(zhǎng)，分管本科教學(xué)合肥工業(yè)大學(xué)人工智能與數(shù)據(jù)挖掘研究室教授研究團(tuán)隊(duì)有教師、博士、碩士研究生數(shù)十人針對(duì)急劇增長(zhǎng)的各類數(shù)據(jù)，開(kāi)展從數(shù)據(jù)中發(fā)現(xiàn)知識(shí)的課題研究。目前的主要研究方向：算法設(shè)計(jì)，數(shù)據(jù)挖掘，知識(shí)工程本科教學(xué)：以數(shù)據(jù)結(jié)構(gòu)為主，目前是安徽省級(jí)精品課程另外還主講：計(jì)算機(jī)科學(xué)技術(shù)導(dǎo)論，數(shù)據(jù)挖掘13第13頁(yè)，共34頁(yè)，2023年，2月20日，星期六任課教師簡(jiǎn)介其他的工作兼職：教育部計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)指導(dǎo)委員會(huì)委員安徽省高校計(jì)算機(jī)教育研究會(huì)副理事長(zhǎng)安徽省教學(xué)名師安徽省精品課程“數(shù)據(jù)結(jié)構(gòu)”建設(shè)項(xiàng)目主持人學(xué)?！俺绦蛟O(shè)計(jì)技術(shù)”教學(xué)團(tuán)隊(duì)負(fù)責(zé)人安徽省水平考試專家組組長(zhǎng)聯(lián)絡(luò)方式Email:jsjxhuxg@辦公室電編：230009，傳晶：非常認(rèn)真和敬業(yè)，教學(xué)效果優(yōu)異，熱心為人是學(xué)生的好朋友14第14頁(yè)，共34頁(yè)，2023年，2月20日，星期六第一章概述

主要內(nèi)容

1.1

研究?jī)?nèi)容

1.2術(shù)語(yǔ)

1.3算法及其描述

1.4算法分析

15第15頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.1研究?jī)?nèi)容數(shù)據(jù)結(jié)構(gòu)課程的研究?jī)?nèi)容：軟件設(shè)計(jì)中常用的基本技術(shù)包括哪些基本技術(shù)？下面從采用計(jì)算機(jī)來(lái)解決實(shí)際問(wèn)題的過(guò)程中所涉及到的各步驟中的相關(guān)技術(shù)來(lái)對(duì)此作一分析：在用計(jì)算機(jī)解決實(shí)際問(wèn)題時(shí)，一般要經(jīng)過(guò)以下幾個(gè)步驟：首先，對(duì)具體問(wèn)題抽象出數(shù)學(xué)模型，然后針對(duì)數(shù)學(xué)模型設(shè)計(jì)出求解算法，選擇或設(shè)計(jì)合適的數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)相關(guān)數(shù)據(jù)，最后編出程序上機(jī)調(diào)試，直至得到最終的解答。下面簡(jiǎn)述各環(huán)節(jié)的有關(guān)內(nèi)容。16第16頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.1研究?jī)?nèi)容問(wèn)題求解之一：?jiǎn)栴}建模：一般情況下，實(shí)際應(yīng)用問(wèn)題可能會(huì)各式各樣，例如我們所熟悉的工資表的處理問(wèn)題，學(xué)生成績(jī)管理問(wèn)題，電話號(hào)碼查詢，數(shù)據(jù)加密、壓縮問(wèn)題等。這些問(wèn)題無(wú)論是所涉及到的數(shù)據(jù)還是其操作要求都可能存在一定的差異。盡管如此，許多應(yīng)用問(wèn)題之間還是具有一定的相似之處的。例如，雖然工資表和學(xué)生成績(jī)表的具體信息（欄目）不同，但如果將兩個(gè)表中的每個(gè)人的工資信息和成績(jī)信息分別看作一個(gè)整體，則這兩個(gè)表結(jié)構(gòu)之間就有了某些共性。從操作方面來(lái)看，雖然對(duì)這兩種表的操作存在差異，但也存在一些相同或相似的基本操作。例如，查詢一個(gè)人的工資信息和成績(jī)信息，修改有關(guān)信息等。17第17頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.1研究?jī)?nèi)容正因?yàn)樵S多不同的問(wèn)題之間存在著的某些共性，可以將一個(gè)具體問(wèn)題用這些共性的形式描述出來(lái)-----建立模型。建立問(wèn)題的模型通常包括：所描述問(wèn)題中的數(shù)據(jù)對(duì)象，對(duì)象間關(guān)系的描述，問(wèn)題求解的要求及方法等方面。建立問(wèn)題模型的好處：通過(guò)建立模型，就可以將一個(gè)具體的問(wèn)題轉(zhuǎn)換為所熟悉的模型，然后借助于這一模型來(lái)實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)及許多數(shù)學(xué)課程中就介紹了許多模型。例如，要描述一個(gè)群體中個(gè)體之間的關(guān)系時(shí)，可以采用”數(shù)據(jù)結(jié)構(gòu)”和”離散數(shù)學(xué)”中所介紹的圖結(jié)構(gòu)。要描述一個(gè)工程內(nèi)的關(guān)系或進(jìn)展情況時(shí)，我們可以采用”數(shù)據(jù)結(jié)構(gòu)”中所介紹的AOV網(wǎng)或AOE網(wǎng)等。即使所建立的模型沒(méi)有現(xiàn)成的求解方法，借助于已有的模型的適當(dāng)組合也相對(duì)易于構(gòu)造求解方法。18第18頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.1研究?jī)?nèi)容問(wèn)題求解之二：構(gòu)造求解算法在構(gòu)建問(wèn)題模型之后，使一個(gè)具體的問(wèn)題就轉(zhuǎn)變成了一個(gè)用模型所描述的抽象的問(wèn)題。借助于這一模型以及已有的知識(shí)（例如數(shù)據(jù)結(jié)構(gòu)中有關(guān)圖結(jié)構(gòu)的基本知識(shí)），我們可以相對(duì)容易地描述出原問(wèn)題的求解方法，即算法。從某種意義上說(shuō)，該算法不僅能實(shí)現(xiàn)原問(wèn)題的求解，而且還可能實(shí)現(xiàn)許多類似的具體問(wèn)題的求解，盡管這些具體問(wèn)題的背景及其描述形式可能存在較大的差異。19第19頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.1研究?jī)?nèi)容問(wèn)題求解之三：選擇或設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)在構(gòu)造出求解算法之后，需要考慮在計(jì)算機(jī)上實(shí)現(xiàn)求解了。為此，需要做兩方面的工作：選擇或設(shè)計(jì)合適的存儲(chǔ)結(jié)構(gòu)，以便將問(wèn)題所涉及到的數(shù)據(jù)（包括數(shù)據(jù)中的基本對(duì)象及對(duì)象之間的關(guān)系）存儲(chǔ)到計(jì)算機(jī)中。不同的存儲(chǔ)形式對(duì)問(wèn)題的求解實(shí)現(xiàn)有較大的影響，所占用的存儲(chǔ)空間也可能有較大的差異。編寫(xiě)程序，實(shí)現(xiàn)問(wèn)題求解。存儲(chǔ)形式和問(wèn)題要求決定了編寫(xiě)程序的方法。問(wèn)題求解之四：測(cè)試在編寫(xiě)出完整的程序之后，需要經(jīng)過(guò)測(cè)試才能交付使用。20第20頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.1研究?jī)?nèi)容問(wèn)題求解的過(guò)程框架：實(shí)際問(wèn)題求解算法測(cè)試程序設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)組織數(shù)據(jù)結(jié)構(gòu)課程中的內(nèi)容數(shù)學(xué)模型抽象

構(gòu)造求解算法

數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

程序?qū)崿F(xiàn)

數(shù)據(jù)結(jié)構(gòu)：計(jì)算機(jī)類專業(yè)核心課程之一21第21頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.2術(shù)語(yǔ)下面介紹課程中所涉及到的一些術(shù)語(yǔ)數(shù)據(jù)（data）——能夠輸入到計(jì)算機(jī)中，并能被計(jì)算機(jī)處理的符號(hào)的集合。例如，工資表，學(xué)生成績(jī)，電話號(hào)碼簿，電子字典，一個(gè)家族關(guān)系的表示形式、表示一個(gè)群體中個(gè)體之間關(guān)系的圖形描述等。如圖圖1-1.doc所示。編號(hào)姓名基本工資獎(jiǎng)金……工資表示例AA2A1A11A3A12A311A21A32A31A121家族關(guān)系示例22第22頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.2術(shù)語(yǔ)

A1A2A3A5A4A6A8A7群體之間的認(rèn)識(shí)關(guān)系圖23第23頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.2術(shù)語(yǔ)雖然數(shù)據(jù)的形式及運(yùn)算存在較大的差異，但存在共性：由若干具有獨(dú)立意義的個(gè)體所組成，個(gè)體間存在著某些關(guān)系。對(duì)這些數(shù)據(jù)的運(yùn)算也有某些相似之處。例如，在家族關(guān)系數(shù)據(jù)中，組成數(shù)據(jù)的基本個(gè)體是個(gè)人信息，其中各人之間存在著多種關(guān)系，如父子關(guān)系、兄弟關(guān)系、祖先－后代關(guān)系等。其中有些關(guān)系是直接表示出來(lái)的，還有一些關(guān)系則是隱含的。對(duì)家族關(guān)系數(shù)據(jù)，通常要涉及到查詢特定個(gè)體間的關(guān)系、插入和刪除個(gè)體等。24第24頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.2術(shù)語(yǔ)數(shù)據(jù)可以分解為元素的集合數(shù)據(jù)元素（dataelement）——構(gòu)成數(shù)據(jù)的基本單位（具有完整的獨(dú)立意義）。

例如工資表中的個(gè)人工資信息，成績(jī)表中的學(xué)生成績(jī)信息，家族關(guān)系中的個(gè)人等。在有些場(chǎng)合下，也稱之為元素、記錄、結(jié)點(diǎn)、頂點(diǎn)等。數(shù)據(jù)項(xiàng)（字段）——元素的具體描述信息。圖1-1.doc25第25頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.2術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)（datastructure）——構(gòu)成數(shù)據(jù)的元素之間的結(jié)構(gòu)關(guān)系。數(shù)據(jù)元素之間存在以下幾類內(nèi)在的關(guān)系：線性結(jié)構(gòu)：元素之間具有次序關(guān)系樹(shù)形結(jié)構(gòu)（樹(shù)型結(jié)構(gòu)）圖結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）集合邏輯結(jié)構(gòu)26第26頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.2術(shù)語(yǔ)邏輯結(jié)構(gòu)——元素之間的內(nèi)在結(jié)構(gòu)關(guān)系（邏輯關(guān)系）線性、樹(shù)形（樹(shù)型）、圖（網(wǎng)狀）、集合存儲(chǔ)結(jié)構(gòu)——數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中的實(shí)現(xiàn)形式運(yùn)算------對(duì)數(shù)據(jù)所施加的運(yùn)算。有關(guān)數(shù)據(jù)結(jié)構(gòu)幾個(gè)方面的聯(lián)系圖邏輯結(jié)構(gòu)分析

運(yùn)算實(shí)現(xiàn)（算法）

運(yùn)算定義

存儲(chǔ)結(jié)構(gòu)抽象數(shù)據(jù)類型（ADT）

數(shù)據(jù)結(jié)構(gòu)的組成27第27頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.3算法及其描述算法——特定問(wèn)題的求解方法。較為粗略。另一種定義：指令的有限序列滿足：

(1)輸入0～n個(gè)

(2)輸出1～n個(gè)

(3)確定性（無(wú)二義性）：指令的描述是確定的，使得對(duì)相同的輸入能產(chǎn)生相同的輸出結(jié)果。

(4)有限性：指令的執(zhí)行次數(shù)有限。

(5)可行性：算法中的每條指令可用計(jì)算機(jī)指令的有限次執(zhí)行來(lái)實(shí)現(xiàn)。28第28頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.3算法及其描述算法描述語(yǔ)言

易懂，靈活

自然語(yǔ)言不準(zhǔn)確

準(zhǔn)確，嚴(yán)格

計(jì)算機(jī)語(yǔ)言死板

偽語(yǔ)言（類語(yǔ)言）：類pascal、類C、類C++

算法舉例：

1.求最大公因子（輾轉(zhuǎn)相除法）

2.韓信點(diǎn)兵問(wèn)題

3.幻方問(wèn)題（縱橫圖）29第29頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.4算法分析算法的衡量指標(biāo)：在正確性的前提下，重點(diǎn)關(guān)注以下指標(biāo):

（1）時(shí)間性能——運(yùn)行算法所需的時(shí)間開(kāi)銷。（2）空間性能——運(yùn)行算法所需的輔助空間的規(guī)模。（3）其它性能——如可讀性/可移植性等。時(shí)間性能（時(shí)間復(fù)雜度）的描述方法討論：

(1)以運(yùn)行算法d的機(jī)器時(shí)間開(kāi)銷來(lái)度量問(wèn)題是：與具體機(jī)器相關(guān)，難以比較

（2）以算法中語(yǔ)句的執(zhí)行次數(shù)來(lái)衡量問(wèn)題是：計(jì)算麻煩，可以簡(jiǎn)化為（3）以算法中語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)來(lái)替代。

30第30頁(yè)，共34頁(yè)，2023年，2月20日，星期六1.4算法分析數(shù)量級(jí)：如果變量n的函數(shù)f(n)和g(n)滿足：

limf(n)/g(n)=常數(shù)k(k≠∞,0)，則稱f(n)和g(n)是同一數(shù)量級(jí)的，