數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容：計(jì)算機(jī)軟件的基礎(chǔ)知識(shí)———數(shù)據(jù)結(jié)構(gòu)課時(shí)安排：數(shù)據(jù)結(jié)構(gòu)——56學(xué)時(shí)上機(jī)——32學(xué)時(shí)課程設(shè)計(jì)——24學(xué)時(shí)機(jī)房教材：《數(shù)據(jù)結(jié)構(gòu)》c語(yǔ)言版本參考書(shū)：數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)的基本概念（第1章緒論）基本的數(shù)據(jù)結(jié)構(gòu)線(xiàn)性結(jié)構(gòu)非線(xiàn)性結(jié)構(gòu)基本的數(shù)據(jù)處理技術(shù)查找技術(shù)（第9章）關(guān)于本書(shū)內(nèi)容編寫(xiě)說(shuō)明基本結(jié)構(gòu)（三部分）排序技術(shù)（第10章）線(xiàn)性表（第2章）棧和隊(duì)列（第3章）串（第4章）數(shù)組和廣義表（第5章）樹(shù)（第6章）圖（第7章）數(shù)據(jù)結(jié)構(gòu)考研的考試形式和試卷結(jié)構(gòu)

試卷滿(mǎn)分及考試時(shí)間本試卷滿(mǎn)分為150分，考試時(shí)間為180分鐘答題方式：答題方式為閉卷、筆試試卷內(nèi)容結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)45分計(jì)算機(jī)組成原理45分操作系統(tǒng)35分計(jì)算機(jī)網(wǎng)絡(luò)25分試卷題型結(jié)構(gòu)單項(xiàng)選擇題80分（40小題，每小題2分）綜合應(yīng)用題70數(shù)據(jù)結(jié)構(gòu)考研大綱【考查目標(biāo)】1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)。2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析。3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。一、線(xiàn)性表（一）線(xiàn)性表的定義和基本操作（二）線(xiàn)性表的實(shí)現(xiàn)1.順序存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.線(xiàn)性表的應(yīng)用二、棧、隊(duì)列和數(shù)組（一）棧和隊(duì)列的基本概念（二）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)（三）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（四）棧和隊(duì)列的應(yīng)用（五）特殊矩陣的壓縮存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)考研大綱三、樹(shù)與二叉樹(shù)（一）樹(shù)的概念（二）二叉樹(shù)1.二叉樹(shù)的定義及其主要特征2.二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.二叉樹(shù)的遍歷4.線(xiàn)索二叉樹(shù)的基本概念和構(gòu)造5.二叉排序樹(shù)6.平衡二叉樹(shù)（三）樹(shù)、森林1.書(shū)的存儲(chǔ)結(jié)構(gòu)2.森林與二叉樹(shù)的轉(zhuǎn)換3.樹(shù)和森林的遍歷（四）樹(shù)的應(yīng)用1.等價(jià)類(lèi)問(wèn)題2.哈夫曼（Huffman）樹(shù)和哈夫曼編碼數(shù)據(jù)結(jié)構(gòu)考研大綱四、圖 （一）圖的概念 （二）圖的存儲(chǔ)及基本操作

1.鄰接矩陣法

2.鄰接表法 （三）圖的遍歷

1.深度優(yōu)先搜索

2.廣度優(yōu)先搜索 （四）圖的基本應(yīng)用及其復(fù)雜度分析

1.最小（代價(jià)）生成樹(shù)

2.最短路徑

3.拓?fù)渑判?/p>

4.關(guān)鍵路徑五、查找（一）查找的基本概念（二）順序查找法（三）折半查找法（四）B-樹(shù)（五）散列（Hash）表及其查找（六）查找算法的分析及應(yīng)用六、內(nèi)部排序 （一）排序的基本概念 （二）插入排序

1.直接插入排序

2.折半插入排序 （三）氣泡排序（bubblesort） （四）簡(jiǎn)單選擇排序 （五）希爾排序（shellsort） （六）快速排序 （七）堆排序 （八）二路歸并排序（mergesort） （九）基數(shù)排序 （十）各種內(nèi)部排序算法的比較 （十一）內(nèi)部排序算法的應(yīng)用數(shù)據(jù)結(jié)構(gòu)的基本概念（第1章緒論）基本的數(shù)據(jù)結(jié)構(gòu)線(xiàn)性結(jié)構(gòu)非線(xiàn)性結(jié)構(gòu)基本的數(shù)據(jù)處理技術(shù)查找技術(shù)（第9章）關(guān)于本書(shū)內(nèi)容編寫(xiě)說(shuō)明基本結(jié)構(gòu)（三部分）排序技術(shù)（第10章）線(xiàn)性表（第2章）棧和隊(duì)列（第3章）串（第4章）數(shù)組和廣義表（第5章）樹(shù)（第6章）圖（第7章）第一章緒言1.1什么是數(shù)據(jù)結(jié)構(gòu)

程序=數(shù)據(jù)結(jié)構(gòu)+算法例1書(shū)目自動(dòng)檢索系統(tǒng)登錄號(hào)：書(shū)名：作者名：分類(lèi)號(hào)：出版單位：出版時(shí)間：價(jià)格：書(shū)目卡片書(shū)目文件按書(shū)名按作者名按分類(lèi)號(hào)索引表線(xiàn)性表例2人機(jī)對(duì)奕問(wèn)題樹(shù)……..……..…...…...…...…...多叉路口交通燈管理問(wèn)題CEDABABACADBABCBDDADBDCEAEBECED圖

結(jié)構(gòu)靜力分析計(jì)算例如:數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題─━線(xiàn)性代數(shù)方程組─━環(huán)流模式方程

(球面坐標(biāo)系)全球天氣預(yù)報(bào)數(shù)據(jù)模型數(shù)據(jù)模型非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題例一:求一組(n個(gè))整數(shù)中的最大值基本操作是“比較兩個(gè)數(shù)的大小”取決于整數(shù)值的范圍算法：?模型：?例二：計(jì)算機(jī)對(duì)弈（跳棋）算法：?模型：?對(duì)弈的規(guī)則和策略棋盤(pán)及棋盤(pán)的格局計(jì)算數(shù)學(xué)需要研究的問(wèn)題數(shù)據(jù)結(jié)構(gòu)定義:是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)（data)—所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)數(shù)據(jù)元素（dataelement）—數(shù)據(jù)的基本單位，也稱(chēng)節(jié)點(diǎn)（node）或記錄（record）數(shù)據(jù)項(xiàng)（dataitem）—有獨(dú)立含義的數(shù)據(jù)最小單位，也稱(chēng)域(field)數(shù)據(jù)結(jié)構(gòu)（datastructure)—數(shù)據(jù)元素和數(shù)據(jù)元素關(guān)系的集合根據(jù)數(shù)據(jù)元素間關(guān)系的基本特性，有四種基本數(shù)據(jù)結(jié)構(gòu)（集合）——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系線(xiàn)性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線(xiàn)性表、棧、隊(duì)列樹(shù)形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹(shù)圖狀結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合。數(shù)據(jù):是計(jì)算機(jī)操作的對(duì)象的總稱(chēng)。是計(jì)算機(jī)處理的信息的某種特定的符號(hào)表示形式。音頻和圖像等數(shù)據(jù)（Data）定義：數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。數(shù)據(jù)包含整型、實(shí)型、布爾型、圖象、字符、聲音等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。C編譯程序源程序（.c）目標(biāo)程序（.obj）可執(zhí)行程序（.exe）C鏈接程序例如對(duì)C源程序是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位

數(shù)據(jù)項(xiàng)：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位數(shù)據(jù)元素可以是數(shù)據(jù)項(xiàng)的集合例如：描述一個(gè)運(yùn)動(dòng)員的數(shù)據(jù)元素可以是稱(chēng)之為組合項(xiàng)數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合假設(shè)用三個(gè)

4位的十進(jìn)制數(shù)表示一個(gè)含

12位數(shù)的十進(jìn)制數(shù)。3214,6587,9345

─

a1(3214),a2(6587),a3(9345)則在數(shù)據(jù)元素a1、a2和a3

之間存在著“次序”關(guān)系

a1,a2

、

a2,a3

3214，6587，9345a1a2a36587，3214，9345a2a1a3≠例如:又例，在2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}中六個(gè)元素之間存在兩個(gè)關(guān)系:行的次序關(guān)系:列的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a5

a2a4a6a1a2a3a4a5a6

數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合再例，在一維數(shù)組{a1,a2,a3,a4,a5,a6}的數(shù)據(jù)元素之間存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}

或者說(shuō)，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合可見(jiàn)，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”數(shù)據(jù)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類(lèi):線(xiàn)性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu)分為：順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素間的邏輯關(guān)系鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)1536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

h

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等

線(xiàn)性結(jié)構(gòu)

非線(xiàn)性結(jié)構(gòu)

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線(xiàn)性表?xiàng)ｊ?duì)樹(shù)形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：數(shù)據(jù)類(lèi)型—高級(jí)語(yǔ)言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱(chēng)例C語(yǔ)言中，提供int,char,float,double等基本數(shù)據(jù)類(lèi)型，數(shù)組、結(jié)構(gòu)體、共用體、枚舉等構(gòu)造數(shù)據(jù)類(lèi)型，還有指針、空(void)類(lèi)型等。用戶(hù)也可用typedef自己定義數(shù)據(jù)類(lèi)型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;抽象數(shù)據(jù)類(lèi)型

(AbstractDataType

簡(jiǎn)稱(chēng)ADT)

是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。假設(shè):z1和z2是上述定義的復(fù)數(shù)則Add(z1,z2,z3)操作的結(jié)果z3=z1+z2即為用戶(hù)企求的結(jié)果ADT有兩個(gè)重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶(hù)的接口（即外界使用它的方法）。數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶(hù)隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類(lèi)型的描述方法抽象數(shù)據(jù)類(lèi)型可用（D，S，P）三元組表示。其中：D是數(shù)據(jù)對(duì)象；

S是D上的關(guān)系集；

P是對(duì)D的基本操作集。ADT

抽象數(shù)據(jù)類(lèi)型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類(lèi)型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

賦值參數(shù)只為操作提供輸入值。引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿(mǎn)足的條件，若不滿(mǎn)足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。例如，抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)的定義：

數(shù)據(jù)對(duì)象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷(xiāo)毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex§1.3抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類(lèi)型需要通過(guò)固有數(shù)據(jù)類(lèi)型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型)來(lái)實(shí)現(xiàn)。例如，對(duì)以上定義的復(fù)數(shù)。typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說(shuō)明void

Assign(complex&Z,

floatrealval,floatimagval)；//

構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval

和imagval

的值float

GetReal(cpmplexZ)；

//返回復(fù)數(shù)Z的實(shí)部值float

Getimag(cpmplexZ)；