數據結構與算法講解(已修改)

　

【正文】 主講老師：劉斌 Email: ： 1263447339 結構 :實體 +關系，把某些成份按一定的規律或方式組織在 一起的實體或某些成分組織在一起的方式 ?在這里，我們把實體看作數據 算法是對特定問題求解方法和步驟的一種描述。 ?大公因數的求解算法 ?元二次方程的求解 ?周長、圓面積 ?方體的表面積和邊長 ?排序 ?治、貪心、動態規劃 ?? ?程序：為計算機解決問題編制的指令集，是按照事先設計的功能和性能要求執行的指令序列 ?從程序設計的觀點來看， ?信息的表示：“數據結構”研究的問題 ?信息的處理：“算法”研究的問題 ?了解計算機原理、掌握程序設計的必由之路。 ?學會怎樣組織信息，以便支持高效的數據處理 ?掌握常用的數據結構及其應用 ?學會合理組織數據、有效地處理數據 ?基本掌握算法的設計與分析方法 ?提高程序設計能力 ?學會分析和研究計算機處理的數據對象的特性 ,掌握 常用數據結構內在的邏輯關系、在機內的存儲表示 ,掌 握常用數據結構上的運算操作的動態性質和執行算法 . ?能夠為實際應用選擇適當的數據結構、存儲結構和相應算法； ?初步掌握算法性能的分析方法。 ?聽課，思考，提問，討論 ?三人行，必我我師焉 ?學而不思則罔，思而不學則殆 ?不恥下問 ?獨學而無友則孤陋而寡聞 ? 上機 ?紙上得來終覺淺，絕知此事要躬行 ? 聽懂很容易，學會才是真 教材： ?廖明宏等， 《 數據結構與算法 (第 4版 )》 ，高等教育，2022年 11月。 參考書： ?算法與數據結構 C語言描述（第 2版）， 張乃孝主編，高等教育出版社 ,2022,1 ?數據結構 C語言版，（有配套習題集與習題解 答）嚴蔚敏等，清華大學出版社 ?數據結構算法與應用 C++語言描述，大量的習 題），網上 PDF格式，翻譯教材 ? 北大計算機系課程資源 (包含課程的視頻 ,C++語言 ) ? 西北工業大學“數據結構” (包含課程的視頻 ) ? “算法 +數據結構” ? 專業實驗室服務器 網址： 用戶名和初始密碼都是學號。 可以提交作業、答疑和下載一些資源。只能在校園網內使用。 總成績 =平時成績 (40%)+期末考試成績 (60%) 上機作業（一定要按時交） 20% 平時成績 40% 隨堂提問 +考勤 15% 上機考勤 5% 期末考試成績 60% 注重綜合能力的考評，平時表現突出、上機能力較強的 (如完成附加題 )可以得到獎勵加分，不超過 5分。 上機作業 ? 程序編寫 ? 程序調試 ? 運行結果 ? 網上提交 ? 上機環境 VC++ ? 要求 ?認真準備，有備而來； ?嚴禁玩游戲； ?及時向老師反映問題； ?培養獨立解決問題的能力。 數據結構的研究對象 數據結構的發展概況 抽象數據型 (ADT) 算法及其復雜性 逐步求精的程序設計方法 關于描述語言 基本概念和術語 四種基本的數據結構 數據結構的研究對象 1. 數據 : 數據是用于描述客觀事物的數值、字符，以及一切可以輸入到計算機中的并由計算機程序加以處理的符號的集合。其范圍隨著計算機技術的發展而不斷發展。 2. 數據元素 數據的基本單位是數據元素，在計算機程序中通常作為一個整體進行考慮和處理。 3. 數據項 是數據的不可分割的最小單位，一個數據元素可由若干個數據項組成。 4. 數據對象 性質相同的元素的集合叫做數據對象。 數據元素在機內的位串表示，即數據元素在計算機內的映象。 /字段 當數據元素由若干個數據項組成時，位串中對應于各個數據項的子串稱為域 /字段，是數據元素中數據項在計 算機中的映象。 計算機程序所作用的一組數據通常稱為信息表，是數據對象在計算機中的映象。 數據結構指的是數據元素之間的相互關系，這種關系是抽象的，即并不涉及數據元素的具體內容。是數據元素及其相互間的關系的數學描述。 (1)邏輯結構 數據結構中描述的是數據元素之間的抽象關系 (邏輯 關系 )，稱為邏輯結構。 (2)存儲結構 /物理結構 數據結構在計算機中的表示（映象）稱為存儲結構 /物 理結構。 (3)數據元素之間的關系（邏輯結構）在計算機中有兩 種表示方法：順序映象 (表示 )和非順序映象 (表示 )，從而 導致兩種不同的存儲結構：順序結構和鏈式結構。 順序映象（表示）的特點是借助數據元素在存儲器中的相對位置來表示數據元素之間的邏輯關系。 非順序映象（表示）的特點是借助指示數據元素存儲地址的指針來表示數據元素之間的邏輯關系。 結構中的數據元素之間除了 屬于同一個集合的關系 之外，別無其他關系。關系比較松散，可用其他結構來表示。 結構中的數據元素之間存在一個對一個的關系，即線性關系，每個元素至多有一個直接前導和后繼。 結構中的數據元素之間存在一個對多個的關系，即層次關系，即每一層上的元素可能與下層的多個元素相關，而至多與上層的一個元素相關。 /圖型結構 結構中的數據元素之間存在多個對多個的關系，即任意關系，任何元素之間都可能有關系。 一般將邏輯結構分為線性結構（ 2）和非線性結構（ 1， 3，4 ）兩種。 結構中的數據元素之間存在多個對多個的關系，即任意關系，任何元素之間都可能有關系 ,各種數據結構的性質 (邏輯結 構 )。 (物理結構 /存 儲結構 )。 (算法 )。 。 ,如數據分類 ,檢索 . (1)計算機科學及其應用的發展使數據結構成為獨立學科 . (2)以數據為中心的程序設計方法推動了數據結構的發展 .