1-1引言v第一章緒論課程概述兩個例子講什么？課程性質(zhì)課程目標學習方法考核方案Whystudy?Whattostudy？Whataretheoutcomes?Howtostudy?Howto

pass?課程概述v第一章緒論專業(yè)基礎課，在教學計劃中處于核心地位——承上啟下考研——必考，面試——必考（算法與數(shù)據(jù)結(jié)構(gòu)是專業(yè)人士的基本功）數(shù)據(jù)結(jié)構(gòu)程序設計基礎數(shù)學基礎電子技術基礎操作系統(tǒng)編譯原理人工智能圖像處理數(shù)據(jù)庫原理Web信息處理算法設計與分析計算復雜性理論計算機網(wǎng)絡圖、最短路徑、散列表、生成樹棧、隊列、散列、索引檢索、排序廣義表、樹、圖、矩陣、搜索樹棧、隊列、圖、矩陣、索引檢索線性表、樹、排序、索引、檢索表、棧、隊列、樹、散列、排序表、棧、隊列、語法樹、散列課程性質(zhì)屬于武術中的“練功”科目課程性質(zhì)為什么是核心課程？為什么必考？為什么是基本功？What1——數(shù)據(jù)結(jié)構(gòu)課程研究什么？各種數(shù)據(jù)模型在內(nèi)存中的存儲方法及實現(xiàn)方法What2——通過學習數(shù)據(jù)結(jié)構(gòu)課程獲得什么？VonNeumann體系結(jié)構(gòu)只要是程序，無不是以數(shù)據(jù)結(jié)構(gòu)為基礎經(jīng)典數(shù)據(jù)結(jié)構(gòu)和經(jīng)典算法，思想、方法、技術學習過程就像思維體操，在潛移默化中提高程序設計和計算思維能力課程性質(zhì)描述基本數(shù)據(jù)模型的邏輯特征，分析和評價數(shù)據(jù)模型的不同存儲方法，進行存儲結(jié)構(gòu)定義；針對計算機領域的工程問題，構(gòu)建數(shù)據(jù)模型、設計存儲結(jié)構(gòu)、描述存儲示意圖（畢業(yè)要求1.4）。描述數(shù)據(jù)結(jié)構(gòu)的基本操作、經(jīng)典算法、經(jīng)典查找技術和排序技術的執(zhí)行過程，對重要的算法進行復現(xiàn)；針對計算機領域的工程問題，進行算法設計并運用大O記號進行算法性能分析（畢業(yè)要求2.3）。針對計算機領域具有時空性能約束的復雜工程問題，應用數(shù)據(jù)結(jié)構(gòu)的基本原則和方法，通過比較、選擇、優(yōu)化等過程，設計合理的存儲結(jié)構(gòu)和解決方案，進行數(shù)據(jù)表示、算法描述和程序?qū)崿F(xiàn)（畢業(yè)要求2.4）。教學目標理解并掌握基本的數(shù)據(jù)結(jié)構(gòu)和經(jīng)典的算法思想、方法、技術，工具箱

復用、修改、重組、創(chuàng)新培養(yǎng)算法設計和分析能力算法——程序的靈魂，設計算法、評價算法、改進算法培養(yǎng)數(shù)據(jù)結(jié)構(gòu)和算法的運用能力運用程序設計語言解決實際問題的能力，設計優(yōu)美的程序培養(yǎng)計算思維能力計算思維——模型化、形式化、邏輯思維、抽象思維教學目標編程境界會寫程序（程序設計基礎的教學目標之一）會高效地寫程序（代碼量與編程的速度成正比）會寫高效的程序（數(shù)據(jù)結(jié)構(gòu)的教學目標之一）會設計算法（我們一直在努力）發(fā)明（發(fā)現(xiàn)）算法（計算機學者的最高境界）Page06先修知識編程基礎——C++語言的基本語法數(shù)據(jù)表示：常量、變量、數(shù)組、結(jié)構(gòu)體、指針數(shù)據(jù)處理：表達式、語句、三種基本程序結(jié)構(gòu)數(shù)據(jù)傳遞：自定義函數(shù)面向?qū)ο螅侯?、對象、?gòu)造函數(shù)與析構(gòu)函數(shù)、友元函數(shù)、模板、異常處理離散數(shù)學集合、關系、遞推、級數(shù)求和、數(shù)列求和、數(shù)學歸納法、圖（基本概念、算法思想）概率論基礎隨機分布、概率分布、數(shù)學期望學習方法循序漸進，切忌心浮氣躁——練功正確對待考試，學習是一個積累的過程；提高課外學習的時間和質(zhì)量作習題——不做習題等于入寶山而空返知識需要通過練習來加深理解，通過學知識促進能力的提高作實驗——計算機學科的特征：理論與實踐緊密結(jié)合紙上得來總覺淺，絕知此事要躬行；程序設計與算法類競賽讀、仿、練、思——理解

掌握

應用讀：理解科學而不是背誦科學，讓知識活起來仿：在模仿中掌握套路和應用場景，讓學習動起來練：藍橋杯、POJ、杭電ACM、leetcode、CSP，讓實踐躍起來主講教材教育部高等教育精品教材、“十一五”和“十二五”國家級規(guī)劃教材，國家級一流課程配套教材。累計銷量35萬冊，2020-2024年清華大學出版社暢銷圖書，國內(nèi)超過500所高校用作主講教材[1]ThomasH.Corman等.算法導論（第4版）.機械工業(yè)出版社.2022[2]MarkA.Weiss.數(shù)據(jù)結(jié)構(gòu)與算法分析：C語言描述（第4版）.機械工業(yè)出版社.2016[3]SartajSahni.數(shù)據(jù)結(jié)構(gòu)、算法與應用：C++語言描述（第2版）.機械工業(yè)出版社.2015[4]Bentley.黃倩譯.編程珠璣（第2版）.人民郵電出版社.2019參考教材[1]嚴蔚敏等.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學出版社.2010[2]鄧俊輝.數(shù)據(jù)結(jié)構(gòu)（C++語言版）第3版.清華大學出版社.2013[3]程杰.大話數(shù)據(jù)結(jié)構(gòu).清華大學出版社.2020[4]余勇.數(shù)據(jù)結(jié)構(gòu)（101教材）.高等教育出版社.2024參考教材考核方案過程化考核！

過程化考核！

過程化考核！平時測驗：10%，10次，在雨課堂上進行（1）考查剛學過的知識及運用；（2）自學概念性知識，通過做題考查完成情況作業(yè)：10%，5次，在雨課堂上進行（1）階段測試：近期學過的知識及運用；（2）算法設計：滿足一定的時間和空間約束實驗：10%，5次，在實驗中心進行期中考試：10%，第1~5章，在雨課堂或線下進行期末考試：60%，線下進行，進入大考1-1引言v第一章緒論美妙的節(jié)奏【例1-1】美妙的節(jié)奏。給定m個強音節(jié)DUM和n個弱音節(jié)da，如何將強弱音節(jié)均勻分布，得到美妙的節(jié)奏？【想法】設三角符△表示強音節(jié)DUM，圓點符●表示弱音節(jié)da，假設有5個三角符和7個圓點符，把三角符均勻散落到圓點符中的操作步驟如下：第1步把三角符和圓點符放在一行；第2步把右側(cè)5個圓點符放在三角符的下面，得到余數(shù)是兩列；第3步把右側(cè)2個圓點符放在最左側(cè)的兩列下面，得到余數(shù)是三列；第4步把最右側(cè)兩列放在最左側(cè)的兩列下面，得到余數(shù)是一列?！鳌鳌鳌鳌鳌瘛瘛瘛瘛瘛瘛瘛鳌鳌鳌鳌鳌瘛瘛瘛瘛瘛瘛瘛鳌鳌鳌鳌鳌瘛瘛瘛瘛瘛瘛瘛鳌鳌鳌瘛瘛瘛瘛瘛鳌鳌瘛衩烂畹墓?jié)奏至此，只有一列余數(shù)，停止操作，從左至右將符號連接起來，得到排列：用DUM代替三角符，用da代替圓點符，該模式變?yōu)椋哼@個節(jié)奏是南非歌曲的拍手聲。如果再進行旋轉(zhuǎn)，從第三、第四個重音節(jié)開始，則形成了其他節(jié)奏。如果將該模式進行旋轉(zhuǎn)，從第二個重音節(jié)開始，即：這個節(jié)奏是肯尼亞的鼓點模式?！鳌瘛瘛鳌瘛鳌瘛瘛鳌瘛鳌馜UM-da-da-DUM-da-DUM-da-da-DUM-da-DUM-daDUM-da-DUM-da-da-DUM-da-DUM-da-DUM-da-da用不同的節(jié)拍數(shù)和弱音節(jié)數(shù)，可以得到大約40種節(jié)奏模式，這些節(jié)奏存在于世界各地的音樂之中。這是一個簡單的算法（輾轉(zhuǎn)相除法），卻能生成如此多樣的有趣結(jié)果！△△△●●●●●△△●●還原DNA序列【例1-2】近幾十年最重要的科學成就之一就是人類基因組的解碼?；蚪M被編碼在DNA序列中，DNA是一種雙螺旋結(jié)構(gòu)，由四種堿基組成：胞嘧啶（Cytosine）、鳥嘌呤（Guanine）、腺嘌呤（Adenine）和胸腺嘧啶（Thymine）。為確定未知DNA序列的組成，可以先將DNA序列分割成若干含有三個堿基的小片段，如何將這些小片段拼接成DNA序列呢？還原DNA序列【例1-2】還原DNA序列。如何將這些小片段拼接成DNA序列？【想法】假設有以下DNA小片段：GTG、TGG、ATG、GGC、GCG、CGT、GCA、TGC、CAA和AAT，將所有小片段構(gòu)建一個有向圖。其中，邊是長度為3的堿基小片段，取該小片段中前兩個和后兩個高分子，得到邊依附的兩個頂點。找出經(jīng)過所有邊一次且僅一次的回路AT-TG-GC-CG-GT-TG-GG-GC-CA-AA-AT，即歐拉回路，就得到了DNA序列ATGCGTGGCAAT。很多問題抽象的數(shù)據(jù)模型是圖結(jié)構(gòu)，歐拉回路算法