《數(shù)據(jù)結(jié)構(gòu)》大綱

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

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

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

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

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

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

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