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

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

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

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

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

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

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