【正文】 主講 丁柏秀 ： Tel： 13514465778 ： 178143370 ?Teaching Material ? Text Book – Data Structure And Algorithms In C++——second edition. ? Reference Book – 王紅梅 .數(shù)據(jù)結(jié)構(gòu)（ C＋＋版） .清華大學出版社 – Mark Allen Weiss. Data Structures amp。 algorithm analysis in C++(second edition) – 嚴蔚敏 .數(shù)據(jù)結(jié)構(gòu) .清華大學出版社 .1997 Study Highlight ? Time Complexity(算法與時間復(fù)雜度 ) k?m39。pleksiti] ? Linear List(線性表 ) ? Stack and Queue (棧和隊列） ? General List (廣義線性表 ) ? Tree and Binary Tree(樹與二 叉 樹 ) ? Graph(圖 ) ? Searching (查找 ) ? Sorting(排序 ) ? 算法與數(shù)據(jù)結(jié)構(gòu)是計算機科學的兩大支柱 計算機科學早期定義為：研究算法的科學 近期定義為：研究數(shù)據(jù)的科學 ? 數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計的基礎(chǔ) ? 是計算機科學中一門綜合性專業(yè)課程 ? 尼克勞斯．沃思（ Niklaus Wirth） : 瑞士計算機科學家。PASCAL之父，結(jié)構(gòu)化程序設(shè)計的首創(chuàng)者，獲得 1984年圖靈獎。 Program=Data Structure +Algorithm ? 使用最適當?shù)?【 數(shù)據(jù)結(jié)構(gòu) 】 ，才能夠設(shè)計出最有效率的 【 算法 】 ，進而轉(zhuǎn)換成為有效率的 【 程序 】 。 qual to 這句話從此就成了計算機學科的一句名言，數(shù)據(jù)結(jié)構(gòu) 是一門和程序設(shè)計密切相關(guān)的課程 Data Structure Mainly Content 87352545 電子商務(wù)學院電話號碼 130012 長春工程學院郵編 510103780618748 身份證號碼 例 1： 87352545130012510103780618748 結(jié)論 1. 雜亂的數(shù)據(jù)不能表達和交流信息 例 2: 電話號碼簿 (a1， b1) (a2， b2)?( an， bn) 其中： ai為某人姓名， bi為該人的電話號碼。 要求：設(shè)計一個算法，給定一個姓名時，能查出此人的電話號碼。 ? 如果姓名和電話號碼的排列次序無規(guī)律， 則只能逐一比較姓名進行查找 ? 如果姓名按字典順序組織，則查找就快捷多了 結(jié)論 2. 數(shù)據(jù)之間是有聯(lián)系的 這些聯(lián)系常常影響算法的選擇和效率。 《 DS》 就是要研究數(shù)據(jù)之間的聯(lián)系。 Data Structure Mainly Content 例 3：大學學生管理機構(gòu) 長春工程學院 土木 ．．電信 ．．． 09級 10級 11級 … 本科 ?？? 張三 李四 結(jié)論３． 數(shù)據(jù)之間是有結(jié)構(gòu)的 例３中數(shù)據(jù)之間呈分層結(jié)構(gòu)（ Tree） 《 DS》 就是要研究數(shù)據(jù)之間的各類結(jié)構(gòu)。 Data Structure Mainly Content 例４：圖書目錄管理 設(shè)每個書目含：書名，作者，登錄號，分類，出版年月 對圖書目錄常有如下操作： 查找：某書在書庫中是否存在？ 插入：購進新書時的登錄； 刪除：報廢或丟失的書，需從目錄中去掉； 結(jié)論４． 在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運算 《 DS》 要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運算。 Data Structure Mainly Content 綜上所述： 《 DS》 主要研究內(nèi)容： 數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系； 對每種結(jié)構(gòu)定義相適應(yīng)的各種運算； 設(shè)計出相應(yīng)的算法； 分析算法的效率。 常見的數(shù)據(jù)結(jié)構(gòu)有：表 (linear list) 、 數(shù)組 (array)、串 (string)、棧 (stack)、 隊列 (queue)、 樹 (tree)、 圖(graph) 等。 方法：查找（ search）、 排序 (sort) Study Purpose about Data Structure 數(shù)據(jù)結(jié)構(gòu)課程的三級標準 1. 掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型和相應(yīng)的存儲結(jié)構(gòu) 2. 提高閱讀和編寫算法的能力 3. 能針對給定問題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計和分析算法 C++語言 數(shù)據(jù)結(jié)構(gòu) 軟件工程 掌握基本編程方法 掌握數(shù)據(jù)組織和數(shù)據(jù)處理的方法 掌握大型軟件開發(fā)方法 學習識字 學習寫作文 學習寫小說 基本要求 課程關(guān)系 與語文學習過程類比 本課程在計算機專業(yè)課程中所處的地位 課程性質(zhì) ? 數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的專業(yè)基礎(chǔ)課 公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)方向課、專業(yè)選修課 ? 在教學計劃中的地位：核心專業(yè)基礎(chǔ)課、承上啟下 前導(dǎo)課：高等數(shù)學、離散數(shù)學、程序設(shè)計語言 后續(xù)課：數(shù)據(jù)庫、操作系統(tǒng)、編譯原理 …… ? 屬于武術(shù)中的“練功”科目 “練武不練功，到頭一場空” ? 考研 ?需要大家課后自己復(fù)習的內(nèi)容： 第 0章 預(yù)備知識 學習目標 ?掌握基本的數(shù)據(jù)結(jié)構(gòu) 工具箱 → 復(fù)用、修改、重組 ?培養(yǎng)算法設(shè)計能力、程序設(shè)計能力 算法 —— 程序的靈魂 問題求解過程：問題 → 想法 → 算法 → 程序 ?培養(yǎng)算法分析能力 評價算法、改進算法 學習要求 ? 循序漸進，切忌心浮氣躁 提高課外學習的時間和內(nèi)容 理解科學而不是背誦科學 → 讀書 正確對待考試 ? 作習題 華羅庚：“學數(shù)學不做習題等于入寶山而空返” ? 作實驗 計算機學科是一門 科學性與工程性 并重的學科，表現(xiàn)為理論和實踐緊密結(jié)合的特征。 成績組成 ? 平時成績 10％：出勤＋作業(yè) ? 實驗成績 20％：出勤＋程序＋報告 ? 期末考試成績 70％ Chapter 1: Introduction ?History of Data Structure ?Research objects ?Basic concepts ?Algorithm and algorithm analysis basic content： 1938年出生， 25歲畢業(yè)于加州理工學院數(shù)學系，博士畢業(yè)后留校任教，28歲任副教授。 30歲時，加盟斯坦福大學計算機系，任教授。從 31歲起，開始出版他的歷史性經(jīng)典巨著： The Art of Computer Programming 他計劃共寫 7卷，然而出版三卷之后，已震驚世界，使他獲得計算機科學界的最高榮譽圖靈獎，此時，他年僅 36歲。 數(shù)據(jù)結(jié)構(gòu)的創(chuàng)始人 —— 克努思 History 程序設(shè)計的實質(zhì)是什么 ? data presentation ： 將數(shù)據(jù)存儲在計算機中 data processing ： 處理數(shù)據(jù)，求解問題 數(shù)據(jù)結(jié)構(gòu)問題起源于程序設(shè)計 實例：學生成績管理系統(tǒng) ? 數(shù)據(jù)結(jié)構(gòu)隨著程序設(shè)計的發(fā)展而發(fā)展 計算機學科的飛速發(fā)展是其他任何學科所無法比擬的 。 1. No structure stage: 20世紀 40~60年代 ,計算機主要用于科學計算 . Application Field ：科學計算； Processed data ：數(shù)值型數(shù)據(jù) The relationship among data ：數(shù)學方程或數(shù)學模型 History