《數(shù)據(jù)結構》大綱

1、1《數(shù)據(jù)結構數(shù)據(jù)結構》學習指導學習指導說明：說明：本指導以《數(shù)據(jù)結構》(C語言版)(嚴蔚敏等編著清華大學出版社1997年出版，國家級優(yōu)秀教材特等獎)和《數(shù)據(jù)結構題集》(嚴蔚敏等編著清華大學出版社1999年出版)為教學主要參考書。一、緒論一、緒論1、學習目的：學習目的：明確數(shù)據(jù)結構課程在本專業(yè)知識結構中的地位，作用。課程的特點，教學的要求，方法。明確數(shù)據(jù)結構所研究的問題以及有關基本概念。初步掌握抽象數(shù)據(jù)類型的表示與實現(xiàn)，初步明確算法分析的

2、作用與分析的重點，初步掌握算法分析的方法。2、學習重點：、學習重點：數(shù)據(jù)的邏輯結構、存儲結構及其算法，數(shù)據(jù)結構的有關概念，抽象數(shù)據(jù)類型及其表示與實現(xiàn)，算法，算法設計的要求，算法的時間復雜度和算法的空間復雜度。3、學習難點：、學習難點：數(shù)據(jù)結構的有關概念，抽象數(shù)據(jù)類型的表示與實現(xiàn)；算法的時間復雜度分析。4、課程內容與基本要求、課程內容與基本要求(一)數(shù)據(jù)結構的引入(1)三個世界：現(xiàn)實世界，信息世界，機器世界。數(shù)據(jù)結構要解決的就是實現(xiàn)從現(xiàn)實

3、世界到信息世界，再由信息世界到機器世界的轉換，從而實現(xiàn)用計算機來解決問題的目的。(2)非數(shù)值問題(結合三個世界講)：控制，管理，數(shù)據(jù)處理(3)數(shù)值問題：數(shù)值計算(4)數(shù)據(jù)結構：從學科角度講，數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機操作對象以及他們之間的關系和操作等等的學科。(二)課程的地位，性質，作用。(1)地位:計算機專業(yè)的核心課程之一。(2)性質:算法理論基礎和軟件設計的技術基礎課。(3)作用:程序設計的基礎，編譯程序，操

4、作系統(tǒng)，數(shù)據(jù)庫系統(tǒng)及軟件系統(tǒng)和應用程序的基礎(三)數(shù)據(jù)結構的產生和發(fā)展(四)課程的特點，學習的要求教材：《數(shù)據(jù)結構》(C語言版)嚴蔚敏等編著北京清華大學出版社1997年參考書：《數(shù)據(jù)結構》許卓群等編著北京高等教育出版社1987年數(shù)據(jù)結構實用教程》（CC描述）徐孝凱北京清華大學出版社1999年3(2)算法的五個特性①有窮性②確定性③可行性④輸入⑤輸出(3)算法設計的要求①正確性②可讀性③健壯性④效率與低存儲量需求(4)算法效率的度量①事后

5、統(tǒng)計方法②事前分析估算的方法(5)時間復雜度：△時間復雜度的確定：算法中基本操作，重復執(zhí)行的次數(shù)是問題規(guī)模n的基本函數(shù)f(n)，算法的時間量度記做T(n)=O(f(n))，則f(n)為該問題的漸進時間復雜，簡稱時間復雜度?！髦恍柽x擇一種基本操作來討論算法的時間復雜度。只需求出它關于n的增長率為何即可?！骶€性查找的平均時間復雜度和最壞時間復雜度。(6)空間復雜度：算法的存儲空間需求。5、作業(yè)、作業(yè)P71.3，1.5，P81.8中(1)、(

6、3)、（5）、(7)、(8)P101.12，1.14二、線性表二、線性表1、學習目的：學習目的：明確線性表的概念與基本運算；明確順序表和鏈表的定義、組織形式、結構特征和類型說明；熟練掌握線性表的順序存儲結構和鏈接存儲結構（單鏈表、循環(huán)鏈表、雙向鏈表）及其基本運算的實現(xiàn)原理和方法。2、學習重點：、學習重點：線性表的定義及邏輯上的特點；順序表上插入、刪除和定位運算的實現(xiàn)；單鏈表的結構特點及類型說明；頭指針和頭結點的作用及區(qū)別；指針操作；定位

7、、刪除、插入運算在單鏈表上的實現(xiàn)；循環(huán)鏈表、雙鏈表的結構特點；循環(huán)鏈表、雙鏈表上刪除與插入運算的實現(xiàn)。3、學習難點：、學習難點：指針操作；刪除、插入運算中的指針操作順序；雙鏈表上指針的操作順序。4、課程內容與基本要求、課程內容與基本要求(一)線性表類型的定義(1)線性表的四個特性(2)定義(3)抽象數(shù)據(jù)類型線性表的定義(二)線性表的順序表示和實現(xiàn)(1)有關概念①線性表的順序表示②存儲位置公式③線性表的動態(tài)分配順序存儲結構，及初始化的操作