第一篇：數(shù)據(jù)結(jié)構(gòu)課程總結(jié).[小編推薦]

●數(shù)據(jù):能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。

●數(shù)據(jù)元素:數(shù)據(jù)的基本單位,可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的最小標(biāo)識(shí)單位。

●數(shù)據(jù)結(jié)構(gòu)的定義: ●邏輯結(jié)構(gòu):從邏輯結(jié)構(gòu)上描述數(shù)據(jù),獨(dú)立于計(jì)算機(jī)。線性結(jié)構(gòu):一對一關(guān)系。線性結(jié)構(gòu):多對多關(guān)系。

●存儲(chǔ)結(jié)構(gòu):是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)。順序存儲(chǔ)結(jié)構(gòu):如數(shù)組。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):如鏈表。索引結(jié)構(gòu):索引表。散列存儲(chǔ)結(jié)

構(gòu):如散列表。

●對數(shù)據(jù)的操作:定義在邏輯結(jié)構(gòu)上,每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算集合。常用的有:檢索、插入、刪除、更新、排序。

●數(shù)據(jù)類型:是一個(gè)值的集合以及在這些值上定義的一組操作的總稱。原子類型:簡單類型,由語言提供。結(jié)構(gòu)類型:由用戶借助

于描述機(jī)制定義,是導(dǎo)出類型。

●程序設(shè)計(jì)的實(shí)質(zhì)是對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu),設(shè)計(jì)一個(gè)好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。

●算法是一個(gè)自定義的計(jì)算過程,以一個(gè)或多個(gè)值輸入,并以一個(gè)或多個(gè)值輸出。

●評價(jià)算法的好壞的因素:算法是正確的;執(zhí)行算法的時(shí)間;執(zhí)行算法的存儲(chǔ)空間;算法易于理解、編碼、調(diào)試。

●時(shí)間復(fù)雜度:是某個(gè)算法的時(shí)間耗費(fèi),它是該算法所求解問題規(guī)模n的函數(shù)。漸近時(shí)間復(fù)雜度:是指當(dāng)問題規(guī)模趨向無窮大時(shí)，該算法時(shí)間復(fù)雜度的數(shù)量級(jí)。評價(jià)一個(gè)算法的時(shí)間性能時(shí),主要標(biāo)準(zhǔn)就是算法的漸近時(shí)間復(fù)雜度。

●算法中語句的頻度不僅與問題規(guī)模有關(guān),還與輸入實(shí)例中各元素的取值相關(guān)?！駮r(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為:常數(shù)階、對數(shù)階、線性階、線性對數(shù)階、平方階、立方階、……k次方階、指數(shù)階。

●空間復(fù)雜度:是某個(gè)算法的空間耗費(fèi),它是該算法所求解問題規(guī)模n的函數(shù)?！袼惴ǖ臅r(shí)間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。

●線性表是由n≥0個(gè)數(shù)據(jù)元素組成的有限序列。n=0是空表;非空表,只能有一個(gè)開始結(jié)點(diǎn),有且只能有一個(gè)終端結(jié)點(diǎn)。

●線性表上定義的基本運(yùn)算:構(gòu)造空表:Initlist;求表長:Listlength;取結(jié)點(diǎn):GetNode;查找:LocateNode;插入:InsertList;刪

除:Delete。

●順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲(chǔ)單元中。在存儲(chǔ)單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)

點(diǎn)相鄰關(guān)系是一致的。地址計(jì)算:? ●在順序表中實(shí)現(xiàn)的基本運(yùn)算:插入:平均移動(dòng)結(jié)點(diǎn)次數(shù)為?;平均時(shí)間復(fù)雜度均為?。刪除:平均移動(dòng)結(jié)點(diǎn)次數(shù)為?;平均時(shí)間復(fù)雜

度均為?。

●線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同,為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系,在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還存儲(chǔ)了其后繼結(jié)點(diǎn)的地址信息。這兩部分信息組成鏈表中的結(jié)點(diǎn)結(jié)構(gòu)。一個(gè)單鏈表由頭指針的名字來命名。

●單鏈表運(yùn)算:建立單鏈表(頭插法:生成的順序與輸入順序相反。平均時(shí)間復(fù)雜度均為?。尾插法:平均時(shí)間復(fù)雜度均為?。加

頭結(jié)點(diǎn)的算法:對開始結(jié)點(diǎn)的操作無需特殊處理,統(tǒng)一了空表和非空表。查找(按序號(hào):與查找位置有關(guān),平均時(shí)間復(fù)雜度均為?。

按值:與輸入實(shí)例有關(guān),平均時(shí)間復(fù)雜度均為。插入運(yùn)算:p=GetNode;s-next=p-next;p-next=s;平均時(shí)間復(fù)雜度均為?,刪除運(yùn)算:平均時(shí)間復(fù)雜度均為? ●單循環(huán)鏈表是一種首尾相接的單鏈表,終端結(jié)點(diǎn)的指針域指向開始結(jié)點(diǎn)或頭結(jié)點(diǎn)。鏈表終止條件是以指針等于頭指針或尾指針。

采用單循環(huán)鏈表在實(shí)用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點(diǎn)是查找頭指針和尾指針的時(shí)間都是O?,不用遍歷整個(gè)鏈表。

●雙鏈表就是雙向鏈表,就是在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前趨的指針域prior,形成兩條不同方向的鏈。由頭指針

head惟一確定。雙鏈表也可以頭尾相構(gòu)成雙循環(huán)鏈表。雙鏈表上的插入和刪除時(shí)間復(fù)雜度均為O?。

●順序表和鏈表的比較: ●基于空間:順序表的存儲(chǔ)空間是靜態(tài)分配,存儲(chǔ)密度為1;適于線性表事先確定其大小時(shí)采用。鏈表的存儲(chǔ)空間是動(dòng)態(tài)分配,存儲(chǔ)

密度1;適于線性表長度變化大時(shí)采用。

●基于時(shí)間:順序表是隨機(jī)存儲(chǔ)結(jié)構(gòu),當(dāng)線性表的操作主要是查找時(shí),宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲(chǔ)

結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端,則宜采用尾指針表示的單循環(huán)鏈表。

●棧是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表,稱插入、刪除這一端為棧頂,另一端稱為棧底。表中無元素時(shí)為空棧。棧 的修改是按后進(jìn)先出的原則進(jìn)行的,我們又稱棧為LIFO表。通常棧有順序棧和鏈棧兩種存儲(chǔ)結(jié)構(gòu)。

●棧的基本運(yùn)算有六種:構(gòu)造空棧:InitStack,判?？?StackEmpty,判棧滿:StackFull,進(jìn)棧:Push,退棧:Pop,取棧頂元素: StackTop ●在順序棧中有“上溢”和“下溢”的現(xiàn)象?！吧弦纭笔菞ｍ斨羔樦赋鰲５耐饷媸浅鲥e(cuò)狀態(tài)?！跋乱纭笨梢员硎緱榭諚?因此用來作為控制

轉(zhuǎn)移的條件。

●順序棧中的基本操作有六種:構(gòu)造空棧,判?？?判棧滿,進(jìn)棧,退棧,取棧頂元素 ●鏈棧則沒有上溢的限制,因此進(jìn)棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點(diǎn),只要有鏈表的頭指針就可以了。

●鏈棧中的基本操作有五種:構(gòu)造空棧,判?？?進(jìn)棧,退棧,取棧頂元素 ●隊(duì)列是一種運(yùn)算受限的線性表,插入在表的一端進(jìn)行,而刪除在表的另一端進(jìn)行,允許刪除的一端稱為隊(duì)頭,允許插入的一端稱

為隊(duì)尾,隊(duì)列的操作原則是先進(jìn)先出的,又稱作FIFO表.隊(duì)列也有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)結(jié)構(gòu)。

●隊(duì)列的基本運(yùn)算有六種:置空隊(duì):InitQueue,判隊(duì)空:QueueEmpty,判隊(duì)滿:QueueFull,入隊(duì):EnQueue,出隊(duì):DeQueue,取

隊(duì)頭元素:QueueFront ●順序隊(duì)列的“假上溢”現(xiàn)象:由于頭尾指針不斷前移,超出向量空間。這時(shí)整個(gè)向量空間及隊(duì)列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克

服“假上溢”現(xiàn)象引入循環(huán)向量的概念,是把向量空間形成一個(gè)頭尾相接的環(huán)形,這時(shí)隊(duì)列稱循環(huán)隊(duì)列。

●判定循環(huán)隊(duì)列是空還是滿,方法有三種:一種是另設(shè)一個(gè)布爾變量來判斷;第二種是少用一個(gè)元素空間,入隊(duì)時(shí)先測試%m=front? 滿:空;第三種就是用一個(gè)計(jì)數(shù)器記錄隊(duì)列中的元素的總數(shù)。

●隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列,一個(gè)鏈隊(duì)列就是一個(gè)操作受限的單鏈表。為了便于在表尾進(jìn)行插入的操作,在表尾增加一個(gè)尾

指針,一個(gè)鏈隊(duì)列就由一個(gè)頭指針和一個(gè)尾指針唯一地確定。鏈隊(duì)列不存在隊(duì)滿和上溢的問題。在鏈隊(duì)列的出隊(duì)算法中,要注意當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí),出隊(duì)后要同進(jìn)修改頭尾指針并使隊(duì)列變空。

●串是零個(gè)或多個(gè)字符組成的有限序列。

●概念空串:是指長度為零的串,也就是串中不包含任何字符?？瞻状?指串中包含一個(gè)或多個(gè)空格字符的串。在一個(gè)串中任意

個(gè)連續(xù)字符組成的子序列稱為該串的子串,包含子串的串就稱為主串。子串在主串中的序號(hào)就是指子串在主串中首次出現(xiàn)的位置。

空串是任意串的子串,任意串是自身的子串。

●串分為兩種:串常量在程序中只能引用不能改變;串變量的值可以改變?！翊幕具\(yùn)算有:求串長strlen,串復(fù)制strcpy,串聯(lián)接strcat,串比較charcmp,字符定位strchr。串是特殊的線性表,所以串的存

儲(chǔ)結(jié)構(gòu)與線性表的存儲(chǔ)結(jié)構(gòu)類似。串的順序存儲(chǔ)結(jié)構(gòu)簡稱為順序串?！耥樞虼挚砂创鎯?chǔ)分配的不同分為:靜態(tài)存儲(chǔ)分配:直接用定長的字符數(shù)組來定義。優(yōu)點(diǎn)是涉及串長的操作速度快,但不適合插

入、操作。動(dòng)態(tài)存儲(chǔ)分配:是在定義串時(shí)不分配存儲(chǔ)空間,需要使用時(shí)按所需串的長度分配存儲(chǔ)單元。

●串的鏈?zhǔn)酱鎯?chǔ)就是用單鏈表的方式存儲(chǔ)串值,串的這種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點(diǎn)數(shù)據(jù)域?yàn)閱?/p>

個(gè)字符。為了解決“存儲(chǔ)密度”低的狀況,可以讓一個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)字符,即結(jié)點(diǎn)的大小。

●順序串上子串定位的運(yùn)算:又稱串的“模式匹配”或“串匹配”,是在主串中查找出子串出現(xiàn)的位置。在串匹配中,將主串稱為目標(biāo), 子串稱為模式。這是比較容易理解的,串匹配問題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時(shí)間復(fù)雜度是Om,假如m與n同階的話則它是O。鏈串上的子串定位運(yùn)算位移是結(jié)點(diǎn)地址而不是整數(shù)。

●數(shù)組一般用順序存儲(chǔ)的方式表示。

●存儲(chǔ)的方式有:行優(yōu)先順序,也就是把數(shù)組逐行依次排列。PASCAL、C。列優(yōu)先順序,就是把數(shù)組逐列依次排列。FORTRAN ●地址的計(jì)算方法:按行優(yōu)先順序排列的數(shù)組:LOC(a=?.。按列優(yōu)先順序排列的數(shù)組:LOC(a=?.矩陣的壓縮存儲(chǔ):為多

個(gè)相同的非零元素分配一個(gè)存儲(chǔ)空間;對零元素不分配空間。

●特殊矩陣的概念:所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。

●稀疏矩陣的概念:一個(gè)矩陣中若其非零元素的個(gè)數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個(gè)數(shù),則該矩陣稱為稀疏矩陣。

●特殊矩陣的類型:對稱矩陣:三角矩陣:上三角陣,下三角陣,對角矩陣k=f(I,j, ●廣義表是n個(gè)元素的有限序列,其中的元素是原子或者是一個(gè)廣義表。廣義表表頭和表尾的概念: ●廣義表有兩種表示法,一種是括號(hào)表示法,一種是圖形表示法。

●廣義表有兩個(gè)特殊的基本運(yùn)算:取表頭head:取表中的第一個(gè)數(shù)據(jù)元素,不能對空表操作。取表尾tail;取除表頭外,其余數(shù)據(jù)元

素構(gòu)成的子表,不能對空表操作

●樹是n個(gè)結(jié)點(diǎn)的有限集合,非空時(shí)必須滿足:只有一個(gè)稱為根的結(jié)點(diǎn);其余結(jié)點(diǎn)形成m個(gè)不相交的子集,并稱根的子樹。根是開始

結(jié)點(diǎn);結(jié)點(diǎn)的子樹數(shù)稱度;度為0的結(jié)點(diǎn)稱葉子;度不為0的結(jié)點(diǎn)稱分支結(jié)點(diǎn);除根外的分支結(jié)點(diǎn)稱內(nèi)部結(jié)點(diǎn);●有序樹是子樹有左,右之分的樹;無序樹是子樹沒有左,右之分的樹;森林是m個(gè)互不相交的樹的集合;●樹的四種不同表示方法:樹形表示法;嵌套集合表示法;凹入表示法;廣義表表示法。

●二叉樹的定義:是n≥0個(gè)結(jié)點(diǎn)的有限集,它是空集或由一個(gè)根結(jié)點(diǎn)及兩棵互不相交的分別稱作這個(gè)根的左子樹和右子樹的二叉樹

組成。二叉樹不是樹的特殊情形,與度數(shù)為2的有序樹不同。二叉樹的4個(gè)重要性質(zhì): ●二叉樹的順序存儲(chǔ)結(jié)構(gòu)就是把二叉樹的所有結(jié)點(diǎn)按照層次順序存儲(chǔ)到連續(xù)的存儲(chǔ)單元中。

●樹的存儲(chǔ)結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯?chǔ)。二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個(gè)指針域, n+1個(gè)空指針。

●根據(jù)結(jié)點(diǎn)的次序不同可得三種遍歷:先序遍歷,中序遍歷、后序遍歷。時(shí)間復(fù)雜度為。

●利用二叉鏈表中的n+1個(gè)空指針域來存放指向某種遍歷次序下的前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針,這些附加的指針就稱為“線索”,加

上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效,但對于查找指定結(jié)點(diǎn)的前序前趨和后序后繼并沒有什么作用。

●樹和森林及二叉樹的轉(zhuǎn)換是唯一對應(yīng)的。二叉樹變樹:結(jié)點(diǎn)的右孩子與其雙親連。森林變二叉樹:樹變二叉樹,各個(gè)樹的根相連。

轉(zhuǎn)換方法? ●樹的存儲(chǔ)結(jié)構(gòu):有雙親鏈表表示法:孩子鏈表表示法:雙親孩子鏈表表示法:孩子兄弟鏈表表示法: ●樹的前序遍歷與相對應(yīng)的二叉樹的前序遍歷一致;樹的后序遍歷與相對應(yīng)的二叉樹的中序遍歷一致。

●樹的帶權(quán)路徑長度?最優(yōu)二叉樹?完全二叉樹?哈夫曼樹及其性質(zhì)，●變長編碼技術(shù)可以使頻度高的字符編碼短,而頻度低的字符編碼長,但是變長編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三

個(gè)碼無法在解碼時(shí)確定是哪一個(gè),所以要求在字符編碼時(shí)任一字符的編碼都不是其他字符編碼的前綴,這種碼稱為前綴碼。哈夫曼樹的應(yīng)用。

●圖的邏輯結(jié)構(gòu)特征就是其結(jié)點(diǎn)的前趨和后繼的個(gè)數(shù)都是沒有限制的,即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。

●圖,有向圖,無向圖,簡單路徑,簡單回路,網(wǎng)絡(luò)等及其性質(zhì)。

●圖的存儲(chǔ)結(jié)構(gòu):鄰接矩陣表示法:適合稠密圖。無向鄰接矩陣是對稱的。有向行是出度,列是入度。建立鄰接矩陣算法的時(shí)間是

O,其時(shí)間復(fù)雜度為O。鄰接表表示法:適合稀疏圖。時(shí)間復(fù)雜度為O,空間復(fù)雜度為O。

●圖的遍歷:深度優(yōu)先遍歷:借助于鄰接矩陣的列。使用棧保存已結(jié)點(diǎn)。廣度優(yōu)先遍歷:借助于鄰接矩陣的行。使用隊(duì)列保存已結(jié)

點(diǎn)。

●生成樹的定義:最小生成樹:Prim算法的時(shí)間復(fù)雜度為O與邊數(shù)無關(guān)適于稠密圖。Kruskal算法的時(shí)間復(fù)雜度為O,主要取決于邊

數(shù),較適合于稀疏圖。

●最短路徑的算法:Dijkstra算法,時(shí)間復(fù)雜度為O。

●拓?fù)渑判?無前趨的頂點(diǎn)優(yōu)先:每次輸出一個(gè)無前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊,最后得到的序列即拓?fù)湫蛄?。無后繼的結(jié)點(diǎn)

優(yōu)先:每次輸出一個(gè)無后繼的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其入邊,最后得到的序列是逆拓?fù)湫蛄小?/p>

●關(guān)于排序

●關(guān)鍵字項(xiàng),關(guān)鍵字。

●排序是使文件中的記錄按關(guān)鍵字遞增次序排列起來。●基本操作:比較關(guān)鍵字大小;改變指向記錄的指針或移動(dòng)記錄。

●存儲(chǔ)結(jié)構(gòu):順序結(jié)構(gòu)、鏈表結(jié)構(gòu)、索引結(jié)構(gòu)。經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變,則稱這種排序方

法是穩(wěn)定的,否則排序算法是不穩(wěn)定的。

●排序過程中不涉及數(shù)據(jù)的內(nèi)、外存交換則稱之為“內(nèi)部排序”,反之,若存在數(shù)據(jù)的內(nèi)外存交換,則稱之為外排序。

●內(nèi)部排序方法可分五類:插入排序、選擇排序、交換排序、歸并排序和分配排序。

●評價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條:執(zhí)行時(shí)間和所需的輔助空間,另外算法的復(fù)雜程序也是要考慮的一個(gè)因素。

●插入排序:直接插入排序;逐個(gè)向前插入到合適位置;哨兵有兩個(gè)作用;作為臨變量存放R[i];是在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否

越界;直接插入排序是穩(wěn)定排序。時(shí)間復(fù)雜度為O ?比較次數(shù)為/2;移動(dòng)次數(shù)為?。希爾排序:等間隔的數(shù)據(jù)比較并按要求順序排列,最后間隔為1;希爾排序是就地的不穩(wěn)定排序。時(shí)間復(fù)雜度為O,比較次數(shù)為;移動(dòng)次數(shù)為;●交換排序:冒泡排序:自下向上確定最輕的一個(gè)。自上向下確定最重的一個(gè)。冒泡排序是就地的穩(wěn)定排序。時(shí)間復(fù)雜度為O?比

較次數(shù)為?;移動(dòng)次數(shù)為?;快速排序:以第一個(gè)元素為參考基準(zhǔn),設(shè)定、動(dòng)兩個(gè)指針,發(fā)生交換后指針交換位置,直到指針重合。

重復(fù)直到排序完成?？焖倥判蚴遣环€(wěn)定排序。時(shí)間復(fù)雜度為O?比較次數(shù)為??！襁x擇排序:直接選擇排序;選擇最小的放在比較區(qū)前;直接選擇排序不穩(wěn)定排序。時(shí)間復(fù)雜度為O?。比較次數(shù)為?。堆排序:建堆: 按層次將數(shù)據(jù)填入完全二叉樹,從int處向前逐個(gè)調(diào)整位置。然后將樹根與最后一個(gè)葉子交換值并斷開與樹的連接并重建堆,直到全斷開。堆排序是就地不穩(wěn)定的排序,時(shí)間復(fù)雜度為O,不適宜于記錄數(shù)較少的文件。

●歸并排序:先兩個(gè)一組排序,形成/2組,再將兩組并一組,直到剩下一組為止。歸并排序是非穩(wěn)定排序,時(shí)間復(fù)雜度是O? ●基數(shù)排序:從低位到高位依次對關(guān)鍵字進(jìn)行箱排序。基數(shù)排序是非就穩(wěn)定的排序,時(shí)間復(fù)雜度是O?。

●各種排序方法的比較和選擇: ●

1、待排序的記錄數(shù)目n;n較大的要用時(shí)間復(fù)雜度為O的排序方法;●

2、記錄的大小;記錄大最好用鏈表作為存儲(chǔ)結(jié)構(gòu),而快速排序和堆排序在鏈表上難于實(shí)現(xiàn);●

3、關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài);●

4、對穩(wěn)定性的要求;●

5、語言工具的條件;●

6、存儲(chǔ)結(jié)構(gòu);時(shí)間和輔助空間復(fù)雜度?！耜P(guān)于查找

●查找的同時(shí)對表做修改操作則相應(yīng)的表稱之為動(dòng)態(tài)查找表,否則稱之為靜態(tài)查找表。

●衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)。

線性表查找的方法：順序查找：逐個(gè)查找，ASL=？;二分查找：取中點(diǎn) int 比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹 表示。ASL=？;分塊查找：要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引 表。

二叉排序樹定義是二叉排序樹是空樹或者滿足如下性質(zhì)的二叉樹：若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的 值;若它的右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值;左、右子樹本身又是一棵二叉排序樹。

二叉排序樹的插入、建立、刪除的算法平均時(shí)間性能是

O？。二叉排序樹的刪除操作可分三種情況進(jìn)行處理：*P 是葉子，則直接刪除*P，即將*P 的雙親*parent 中指向*P 的指針域置空即可。*P 只有一個(gè)孩子*child，此時(shí)只需將*child 和*p 的雙親直接連接就可刪去*p。*p 有兩個(gè)孩子，則先將*p 結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)的數(shù) 據(jù)到*p，刪除中序后繼結(jié)點(diǎn)。

關(guān)于 B-樹。它適合在磁盤等直接存取設(shè)備上組織動(dòng)態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。散列技術(shù)：將結(jié)點(diǎn)按其關(guān)鍵字的散列地址存儲(chǔ)到散列表的過程稱為散列。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡單和均勻。常見的散列 函數(shù)構(gòu)的造方法：平方取中法,除余法,相乘取整法,隨機(jī)數(shù)法。

處理沖突的方法：開放定址法：一般形式為?，開放定址法要求散列表的裝填因子 α≤1。開放定址法類型：線性探查法，二次探查 法，雙重散列法。拉鏈法：是將所有關(guān)鍵字為同義詞的結(jié)點(diǎn)在同一個(gè)單鏈表中。拉鏈法的優(yōu)點(diǎn)：拉鏈法處理沖突簡單，且無堆積現(xiàn)象;鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請的適于無法確定表長的情況;拉鏈法中 α 可以大 于 1，結(jié)點(diǎn)較大時(shí)其指針域可忽略，因此節(jié)省空間;拉鏈法構(gòu)造的散列表刪除結(jié)點(diǎn)易實(shí)現(xiàn)。

拉鏈法也有缺點(diǎn)：當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。

第二篇：“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)

“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)

計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)從1994年開始為我校?？粕_設(shè)“數(shù)據(jù)結(jié)構(gòu)”課程，2004年開始為本科生開設(shè)這門課程。由于本門課程的教學(xué)從教材、講授、實(shí)驗(yàn)指導(dǎo)都體現(xiàn)了先進(jìn)的教育理念，該課程的教學(xué)體系科學(xué)、完整，教學(xué)手段與方法先進(jìn)，課程特色鮮明，2006年被評為赤峰學(xué)院本科層次精品課。幾年來，數(shù)據(jù)結(jié)構(gòu)課題組成員從以下幾個(gè)方面對本門課程進(jìn)行了建設(shè)和改革。

一、課程建設(shè)指導(dǎo)思想、定位和特色 1．學(xué)科地位

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門學(xué)科基礎(chǔ)課，是本專業(yè)和相關(guān)專業(yè)必修課。本課程的教學(xué)目標(biāo)是培養(yǎng)學(xué)生通過理解、分析和研究計(jì)算機(jī)處理的數(shù)據(jù)對象的特性，從而選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和相應(yīng)的算法，并熟練掌握算法的時(shí)間分析和空間分析技巧?！皵?shù)據(jù)結(jié)構(gòu)”還是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)部分專業(yè)課的先導(dǎo)課，如“數(shù)據(jù)庫原理與應(yīng)用”、“計(jì)算機(jī)操作系統(tǒng)”、“計(jì)算機(jī)編譯原理”和“面向?qū)ο蟮某绦蛟O(shè)計(jì)”等。所以本課程的教學(xué)效果將直接影響到學(xué)生對其它后續(xù)專業(yè)課的學(xué)習(xí)，因此，該課程在專業(yè)建設(shè)的地位十分重要。

“數(shù)據(jù)結(jié)構(gòu)”是一門應(yīng)用性很強(qiáng)的課程，本課程要求學(xué)生在掌握各種數(shù)據(jù)結(jié)構(gòu)，特別是存儲(chǔ)結(jié)構(gòu)和有關(guān)算法的基礎(chǔ)上，通過大量的上機(jī)實(shí)例把難以理解的、抽象的概念轉(zhuǎn)化為計(jì)算機(jī)能夠正確運(yùn)行的程序，從而提高學(xué)生運(yùn)用所學(xué)知識(shí)解決實(shí)際問題的能力。2．課程特色

根據(jù)課程建設(shè)的規(guī)劃和我系實(shí)際，我們針對《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)開展討論，并就實(shí)驗(yàn)、圖書資料等方面進(jìn)行建設(shè)。在不斷的教學(xué)實(shí)踐中，我們按照精品課建設(shè)要求，積極探索，積累了豐富的教學(xué)經(jīng)驗(yàn)。

采用國內(nèi)經(jīng)典教材，結(jié)合前沿的研究領(lǐng)域和最新科研動(dòng)態(tài)，豐富教學(xué)內(nèi)容，讓學(xué)生了解數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用價(jià)值。

采用課堂教學(xué)與大作業(yè)相結(jié)合，上機(jī)實(shí)踐為補(bǔ)充的教學(xué)模式，培養(yǎng)學(xué)生的創(chuàng)業(yè)創(chuàng)新素質(zhì)和團(tuán)隊(duì)協(xié)作精神。

二、教師隊(duì)伍建設(shè)

1．良好的學(xué)緣結(jié)構(gòu)

任課教師的業(yè)務(wù)水平和教學(xué)水平是影響課程建設(shè)質(zhì)量的重要因素。為此，我們不斷加強(qiáng)師資隊(duì)伍建設(shè)，特別注重青年教師和實(shí)驗(yàn)指導(dǎo)教師的培養(yǎng)。在擔(dān)任該課程教學(xué)任務(wù)的5名教師中，教授1名、副教授2名、講師2名，學(xué)歷結(jié)構(gòu)為碩士4人、學(xué)士1人，45歲以下3人，35歲以下2人。本教師梯隊(duì)學(xué)歷層次較高，職稱、年齡結(jié)構(gòu)合理，便于本門課程的建設(shè)和發(fā)展。

2．加強(qiáng)學(xué)術(shù)交流，不斷提高團(tuán)隊(duì)整體教學(xué)和科研水平

在教學(xué)過程中，我們采取了互相聽課，舉行公開課、觀摩課等方式，經(jīng)常交流教書育人和教學(xué)改革方面的經(jīng)驗(yàn)，不斷提高任課教師的教學(xué)水平和學(xué)術(shù)水平。

以范體貴教授為學(xué)科帶頭人的教學(xué)研究梯隊(duì)，具有豐富的教學(xué)經(jīng)驗(yàn)和高昂的教學(xué)熱情，同時(shí)具備較高的教學(xué)研究和科學(xué)研究水平。教學(xué)梯隊(duì)成員在搞好教學(xué)的同時(shí)，積極申報(bào)承擔(dān)各級(jí)各類教學(xué)研究和科學(xué)研究課題，并參加國內(nèi)外相關(guān)學(xué)科的科研、教學(xué)等方面的學(xué)術(shù)交流活動(dòng)。選派范體貴、門愛華兩位老師參加全國計(jì)算機(jī)年會(huì)和全國數(shù)據(jù)庫學(xué)術(shù)會(huì)議，與國內(nèi)其他高校著名學(xué)者進(jìn)行了教學(xué)、科研等方面的交流，學(xué)到許多寶貴的經(jīng)驗(yàn)和方法。

注重與其他高校的合作和交流，學(xué)習(xí)其他院校好的教學(xué)經(jīng)驗(yàn)和方法。選派主講教師門愛華老師到清華大學(xué)計(jì)算機(jī)系做訪問學(xué)者，訪學(xué)期間門老師聽取了本課程的講授，經(jīng)常與講授本門課程的資深教授嚴(yán)蔚敏老師、殷仁昆老師進(jìn)行交流、學(xué)習(xí)。二位老師都給予了具體的指導(dǎo)和建議，為我校本門課程的改革和發(fā)展提供了有利的幫助。請國內(nèi)著名高校學(xué)者來我系講學(xué)傳授經(jīng)驗(yàn)，在教學(xué)、科研等方面給予具體的指導(dǎo)。2008年10月清華大學(xué)著名數(shù)據(jù)庫專家馮建華教授來我系講學(xué)，課題組成員與馮教授進(jìn)行了深入的交流，在教學(xué)和科研方面都有很大的收獲。

3．開展科學(xué)研究，積極申請科研立項(xiàng)

數(shù)據(jù)結(jié)構(gòu)課題小組成員積極進(jìn)行相關(guān)領(lǐng)域的科學(xué)研究，幾年來發(fā)表相關(guān)論文30余篇，承擔(dān)自治區(qū)級(jí)科研項(xiàng)目四個(gè)，赤峰市科技局科研項(xiàng)目一個(gè)，院級(jí)項(xiàng)目一個(gè)，其中3個(gè)項(xiàng)目已經(jīng)完成并通過驗(yàn)收。目前在研的一個(gè)科研項(xiàng)目是與清華大學(xué)合作申請的計(jì)算機(jī)前沿領(lǐng)域研究課題，相信通過該項(xiàng)目的研究和合作，對我系的科研工作會(huì)起到極大的促進(jìn)作用，同時(shí)能夠使我系科研水平上一個(gè)新的臺(tái)階。課題組成員經(jīng)過幾年的努力，在各方面都取得了一些成績。范體貴、門愛華、張國祥、王玉紅四位教師分別獲得“赤峰學(xué)院課堂教學(xué)質(zhì)量優(yōu)秀獎(jiǎng)”，范體貴、門愛華兩位教師多次獲得“赤峰學(xué)院科研成果優(yōu)秀獎(jiǎng)”的獎(jiǎng)勵(lì)。王玉紅老師獲得“畢業(yè)實(shí)習(xí)優(yōu)秀指導(dǎo)教師“稱號(hào)，門愛華老師2007年、2008年連續(xù)獲得“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎(jiǎng)勵(lì)。

建立了良好的人才培養(yǎng)制度，在學(xué)校和系里的大力支持下，鼓勵(lì)現(xiàn)有教師提高學(xué)歷與引進(jìn)高學(xué)歷教師相結(jié)合，經(jīng)過幾年的建設(shè)，已經(jīng)形成了一支以中青年為主的學(xué)科梯隊(duì)。積極鼓勵(lì)中青年教師到國內(nèi)名校進(jìn)修或攻讀碩士、博士學(xué)位，門愛華、董潔、王玉紅分別考取了東北大學(xué)和遼寧工程技術(shù)大學(xué)的碩士研究生，已圓滿完成學(xué)業(yè)并獲得碩士學(xué)位。

三、教學(xué)內(nèi)容、教材建設(shè)

1．理論環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時(shí)分配

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)科學(xué)課程體系中核心課程之首，作為學(xué)科的專業(yè)基礎(chǔ)課，具有承上啟下的重要作用。對應(yīng)于學(xué)科中問題求解的理論、抽象和設(shè)計(jì)的方法論，本課程內(nèi)容體系結(jié)構(gòu)分為概念表述、構(gòu)建數(shù)據(jù)模型、設(shè)計(jì)算法三個(gè)層面，突出數(shù)據(jù)組織方法與處理技術(shù)，貫穿程序設(shè)計(jì)和軟件工程新思想和新觀點(diǎn)。理論學(xué)時(shí)設(shè)置為72學(xué)時(shí)。

2.實(shí)踐環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時(shí)分配

上機(jī)實(shí)踐和課程設(shè)計(jì)重在培養(yǎng)學(xué)生軟件設(shè)計(jì)的綜合能力。在基本的課程實(shí)習(xí)基礎(chǔ)上,自2001年起開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，使課程的實(shí)踐環(huán)節(jié)總學(xué)時(shí)數(shù)增加到60學(xué)時(shí)。提出了課程設(shè)計(jì)的規(guī)范要求，突出關(guān)鍵技術(shù)要點(diǎn)，貫穿基本技能訓(xùn)練主線，加強(qiáng)實(shí)踐能力培養(yǎng)。

通過課程設(shè)計(jì)的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征，提高了學(xué)生組織數(shù)據(jù)與進(jìn)行編寫大型程序能力，使學(xué)生更好地理解和掌握了算法設(shè)計(jì)所需的技術(shù)，為專業(yè)學(xué)習(xí)打下良好的基礎(chǔ)。課程設(shè)計(jì)題目（動(dòng)態(tài)更新、完善）：航空客運(yùn)訂票系統(tǒng)；電梯模擬；簡單行編輯程序；工資管理系統(tǒng)；醫(yī)院排隊(duì)看病活動(dòng)的模擬；學(xué)籍管理系統(tǒng)；圖書管理系統(tǒng)等。3．教材建設(shè)

教材建設(shè)是課程建設(shè)的重要環(huán)節(jié)。為此，根據(jù)教學(xué)大綱和本課程的發(fā)展需要，在本課程教材的選用上注重教材的先進(jìn)性和科學(xué)性，我們選用了清華大學(xué)出版社嚴(yán)蔚敏教授等編寫的《數(shù)據(jù)結(jié)構(gòu)》（C語言版）作為教材，本書內(nèi)容豐富、體系結(jié)構(gòu)嚴(yán)謹(jǐn)、概念清晰、易學(xué)易懂，也是多所院校指定的考研參考教材，完全適合我系計(jì)算機(jī)科學(xué)與技術(shù)、信息與計(jì)算科學(xué)專業(yè)學(xué)生的需要。任課教師則多方面參考相關(guān)教材，選擇部分編寫精彩的內(nèi)容充實(shí)到教案中。任課教師們廣泛閱讀相關(guān)文獻(xiàn)，了解該領(lǐng)域前沿知識(shí)，并且在授課過程中介紹給學(xué)生，以開闊學(xué)生的視野，拓寬學(xué)生的知識(shí)面。同時(shí)，根據(jù)教材內(nèi)容和實(shí)際教學(xué)要求，編寫了《數(shù)據(jù)結(jié)構(gòu)上機(jī)指導(dǎo)與習(xí)題就解答》，并正式出版了《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教程》一書，該書作為自治區(qū)教育廳統(tǒng)編教材已在各高校廣泛使用。

四、教學(xué)方法和教學(xué)手段

1．教學(xué)方法

在教學(xué)方法上，講課、討論和專題講座等多種形式并用，以科學(xué)、生動(dòng)靈活的講授方式傳授知識(shí)，培養(yǎng)學(xué)生的創(chuàng)造思維。教師在認(rèn)真組織課堂講授，注意各環(huán)節(jié)正常運(yùn)行的同時(shí)，還針對不同的教學(xué)內(nèi)容采取不同的方法進(jìn)行講解，做到課程內(nèi)容既條理清晰、深入淺出，又重點(diǎn)突出、特色鮮明。教學(xué)內(nèi)容靈活，既有必講的內(nèi)容，也有針對不同專業(yè)需要和特點(diǎn)選講的內(nèi)容。

通過布置適量的課后習(xí)題，使學(xué)生能夠進(jìn)一步鞏固和提高對課上所學(xué)知識(shí)的領(lǐng)悟和應(yīng)用能力。我們在選擇習(xí)題時(shí)，一方面注重三基（基本理論，基本方法，基本技能）知識(shí)的掌握，另一方面也充分考慮知識(shí)的靈活應(yīng)用，使學(xué)生能多角度、多方法地解決問題，既鍛煉他們的系統(tǒng)性思維，又提高分析解決問題的能力。每兩周安排一次習(xí)題課，由指導(dǎo)教師集中解決同學(xué)課上課下遇到的問題。

上機(jī)實(shí)踐是學(xué)生對本門課程所學(xué)知識(shí)的一種全面、綜合的能力訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成必不可少的一個(gè)教學(xué)環(huán)節(jié)，也是對課堂教學(xué)效果的一種檢驗(yàn)。通常，實(shí)習(xí)題中的問題比平時(shí)的習(xí)題復(fù)雜得多，也更接近實(shí)際。實(shí)習(xí)題注重原理與應(yīng)用的結(jié)合，目的讓學(xué)生學(xué)會(huì)如何把書上學(xué)到的知識(shí)運(yùn)用于解決實(shí)際問題的過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計(jì)工作所必需的基本技能。同時(shí)，通過實(shí)踐能使書上的知識(shí)變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的作用。平時(shí)的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實(shí)習(xí)題是軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計(jì)，用戶界面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧，可以多人合作，有利于一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，實(shí)踐環(huán)節(jié)中有很重要的一點(diǎn)，就是機(jī)器是比任何教師都嚴(yán)格的主考官。

2．教學(xué)手段

為了適應(yīng)現(xiàn)代化教學(xué)的需求，我們在傳統(tǒng)教學(xué)的基礎(chǔ)上，充分利用現(xiàn)代科學(xué)技術(shù)，廣泛應(yīng)用多媒體教學(xué)課件和教學(xué)軟件。將授課內(nèi)容制作成了圖文并茂的多媒體課件，利用多媒體技術(shù)對數(shù)據(jù)結(jié)構(gòu)輔之以形象的動(dòng)畫，動(dòng)態(tài)演示抽象的復(fù)雜數(shù)據(jù)結(jié)構(gòu)的變化，用板書補(bǔ)充某些推導(dǎo)過程并完成和學(xué)生互動(dòng)的內(nèi)容，改變了以前課堂教學(xué)單調(diào)的弊病，激發(fā)了學(xué)生的學(xué)習(xí)興趣。使用多媒體技術(shù)還可以直接在課堂上演示算法的實(shí)現(xiàn)過程，讓學(xué)生熟悉算法實(shí)現(xiàn)的環(huán)境和方法，增強(qiáng)了該門課的實(shí)踐性，提高了課堂授課效率和教學(xué)質(zhì)量，取得了滿意的教學(xué)效果。教師們?yōu)榱烁玫剡m應(yīng)社會(huì)的發(fā)展和改革的需要，本著強(qiáng)化算法的思想，在現(xiàn)有數(shù)據(jù)結(jié)構(gòu)內(nèi)容的基礎(chǔ)上，補(bǔ)充了新的算法，拓寬了學(xué)生的知識(shí)面。

五、課程建設(shè)取得的成果

1．教學(xué)科研論文

1）The Boundary Element Analysis for The Thermal Conduction of The Thermal Equipment。Proceedings of International Conference on Computational Physics, Rinton Press, US,(2005)199-202（SCI）

2）基于訪問控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究。計(jì)算機(jī)與網(wǎng)絡(luò) 24,(2004)52-53(核刊)3）信息系統(tǒng)在企業(yè)現(xiàn)代化管理中的應(yīng)用。《商場現(xiàn)代化（學(xué)術(shù)版）》，2005.2 25-26(核刊)4）可信網(wǎng)絡(luò)基本概念與基本屬性研究?！冻喾鍖W(xué)院學(xué)報(bào) 》2007.5 5）基于包過濾技術(shù)路由器防火墻在網(wǎng)絡(luò)安全中的研究。《計(jì)算機(jī)應(yīng)用研究》,2007,vol23 6）Research on The Architecture of Tru-Network。2008 International Symposium on Information science and Engineering 7）路由器防火墻對沖擊波、震蕩波病毒的過濾研究?！冻喾鍖W(xué)院學(xué)報(bào)》 2005.1 67-68 8）菲涅耳圓孔衍射的數(shù)值模擬。《赤峰學(xué)院學(xué)報(bào)》 2006.1 9）復(fù)雜軸承流體動(dòng)力學(xué)特性的邊界元分析?！稘櫥c密封》 2006.3(核刊 EI核心刊源)10）三葉軸承流體動(dòng)力學(xué)特性的邊界元分析?！稘櫥c密封》 2006.5(核刊 EI核心刊源)11）164-182Hf核的低能譜和電磁躍遷的相互作用玻色子模型?！陡吣芪锢砼c核物理》 28(12),(2004)119-122(核刊, SCI收錄)12）基于訪問控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究?！队?jì)算機(jī)與網(wǎng)絡(luò)》 2004.24 13）赤峰學(xué)院校園網(wǎng)路由器、交換機(jī)的選型及遠(yuǎn)程登錄。《赤峰教育學(xué)院學(xué)報(bào)》2004.5 81-82 14）《XML數(shù)據(jù)庫存儲(chǔ)策略綜述》 《計(jì)算機(jī)科學(xué)》 2005年9月（核刊）15）《XML數(shù)據(jù)庫結(jié)構(gòu)連接算法之研究》《計(jì)算機(jī)科學(xué)》 2007年6月（核刊）16）《XML中XPath包含關(guān)系判定算法》《內(nèi)蒙古大學(xué)學(xué)報(bào)》2008年10月（核刊）17）《基于關(guān)系數(shù)據(jù)庫的XML數(shù)據(jù)的存儲(chǔ)研究》《赤峰學(xué)院學(xué)報(bào)》 2006年 3 月 18）《XML數(shù)據(jù)庫模式匹配算法研究》 《赤峰學(xué)院學(xué)報(bào)》 2007年 5月 19）《Internet蠕蟲的分析與研究》 《赤峰學(xué)院學(xué)報(bào)》 2005年 4月 20）《如何防止外部網(wǎng)絡(luò)的攻擊》 《赤峰學(xué)院學(xué)報(bào)》 2004年2月 21）《射頻IC卡消費(fèi)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)》 《赤峰學(xué)院學(xué)報(bào)》 2008年10月 22）《XPath片斷的分析與研究》 《赤峰學(xué)院學(xué)報(bào)》 2008年1月 23）《一種基于層次結(jié)構(gòu)的XML編碼技術(shù)》 中國教育信息化》 2009年4月（核刊）24）《VC++實(shí)現(xiàn)圖形、數(shù)據(jù)庫應(yīng)用系統(tǒng)的思路》赤峰教育學(xué)院學(xué)報(bào) 2002年第2月 25）《基于IP組播的多媒體會(huì)議系統(tǒng)的設(shè)計(jì)》 赤峰教育學(xué)院學(xué)報(bào) 2002年6月 26）論文《個(gè)性化WINDOWS系統(tǒng)“開始”菜單》赤峰教育學(xué)院學(xué)報(bào) 2003年4月 27）淺談DEBUG程序的主要命令用法 赤峰學(xué)院學(xué)報(bào) 2007年5月 28）powerpoint技巧在課件制作中的妙用 赤峰學(xué)院學(xué)報(bào) 2006年1月 29）淺談?dòng)肕ASM運(yùn)行匯編程序 赤峰學(xué)院學(xué)報(bào) 2005年 1月 30）XML數(shù)字簽名淺析 赤峰學(xué)院學(xué)報(bào) 2008年 5月 31）《網(wǎng)絡(luò)層的靜態(tài)路由選擇綜述》 赤峰學(xué)院學(xué)報(bào) 2005年3月 32）《離散數(shù)學(xué)在計(jì)算機(jī)教學(xué)中的作業(yè)》 赤峰學(xué)院學(xué)報(bào) 2008年1月 33）《基于模擬退火算法的油井工礦數(shù)據(jù)挖掘的應(yīng)用研究》

赤峰學(xué)院學(xué)報(bào)2009年1月

2.教研課題

1）赤峰學(xué)院校園網(wǎng)項(xiàng)目 赤峰學(xué)院 2002年-2003年（已驗(yàn)收）2）基于IP網(wǎng)QOS動(dòng)態(tài)控制研究 內(nèi)蒙教育廳 2005年-2007年（已結(jié)題）3）基于結(jié)構(gòu)索引XML模式匹配方法研究 內(nèi)蒙教育廳 2005年—2007年（已結(jié)題）4）XML數(shù)據(jù)庫研究 赤峰學(xué)院 2006年—2008年（已結(jié)題）5）CAI系統(tǒng)中知識(shí)個(gè)性化組織與導(dǎo)航研究 內(nèi)蒙教育廳 2003年-2005年（已結(jié)題）6）XML安全數(shù)據(jù)發(fā)布關(guān)鍵問題研究 內(nèi)蒙教育廳 2009年—2010年（在研）3.教學(xué)獲獎(jiǎng)

1）范體貴、門愛華、張國祥、王玉紅分別獲赤峰學(xué)院2005、2006年、2007年、2008年“課堂教學(xué)質(zhì)量優(yōu)秀獎(jiǎng)”；

2）門愛華2007年、2008年連續(xù)獲的“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎(jiǎng)勵(lì)； 3）王玉紅2007年獲院級(jí)“畢業(yè)實(shí)習(xí)優(yōu)秀實(shí)習(xí)指導(dǎo)教師”獎(jiǎng)勵(lì)；

4）2009年《數(shù)據(jù)結(jié)構(gòu)課程教學(xué)和實(shí)踐》課題”獲赤峰學(xué)院“優(yōu)秀教學(xué)成果二等獎(jiǎng)”。

數(shù)據(jù)結(jié)構(gòu)課程組 2009年5月14日

第三篇：數(shù)據(jù)結(jié)構(gòu)與算法課程總結(jié)[模版]

數(shù)據(jù)結(jié)構(gòu)與算法課程學(xué)習(xí)總結(jié)報(bào)告

11計(jì)本一班 許雪松 1104013018

數(shù)據(jù)結(jié)構(gòu)與算法是計(jì)算機(jī)程序設(shè)計(jì)的重要理論技術(shù)基礎(chǔ)，它不僅是計(jì)算機(jī)科學(xué)的核心課程，而且也已經(jīng)成為其他理工專業(yè)的熱門選修課?？偟膩碚f感觸還是比較深的，剛開始上的時(shí)候還蠻簡單的，越到后面感覺越難，算法也更復(fù)雜了，有時(shí)候甚至聽不懂，老師上課時(shí)講的也蠻快的，所以只能靠課下下功夫了。下面是我對本學(xué)期學(xué)習(xí)這門課的總結(jié)。

一、數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)點(diǎn)

第一章的數(shù)據(jù)結(jié)構(gòu)和算法的引入，介紹了數(shù)據(jù)和數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、算法描述工具、算法和算法評價(jià)四個(gè)方面的知識(shí)。

第二章具體地介紹了順序表的概念、基本運(yùn)算及其應(yīng)用?；具\(yùn)算有：初始化表、求表長、排序、元素的查找、插入及刪除等。元素查找方法有：簡單順序查找、二分查找和分塊查找。排序方法有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序及歸并排序等。最后介紹了順序串的概念，重點(diǎn)在于串的模式匹配。

第三章主要介紹的是線性邏輯結(jié)構(gòu)的數(shù)據(jù)在鏈接存儲(chǔ)方法下數(shù)據(jù)結(jié)構(gòu)鏈表的相關(guān)知識(shí)。主要是單鏈表、循環(huán)鏈表的數(shù)據(jù)類型結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)、基本運(yùn)算及其實(shí)現(xiàn)以及鏈表的相關(guān)應(yīng)用問題，在此基礎(chǔ)上介紹了鏈串的相關(guān)知識(shí)。在應(yīng)用方面有多項(xiàng)式的相加問題、歸并問題、箱子排序問題和鏈表在字符處理方面的應(yīng)用問題等。本章未完全掌握的是循環(huán)鏈表的算法問題和C的描述。

第四章介紹在兩種不同的存儲(chǔ)結(jié)構(gòu)下設(shè)計(jì)的堆棧，即順序棧和鏈棧的相關(guān)知識(shí)，了解堆棧的相關(guān)應(yīng)用，掌握應(yīng)用堆棧來解決實(shí)際問題的思想及方法。本章主要內(nèi)容是順序棧和鏈棧的概念、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)定義和基本運(yùn)算算法及其性能分析。本章堆棧算法思想較為簡單，所以能較好掌握。

第五章主要介紹順序存儲(chǔ)和鏈接存儲(chǔ)方法下的兩種隊(duì)列、順序（循環(huán)）隊(duì)列和鏈隊(duì)列的數(shù)據(jù)結(jié)構(gòu)、基本運(yùn)算及其性能分析以及應(yīng)用。順序隊(duì)列(重點(diǎn)是循環(huán)隊(duì)列）和鏈隊(duì)列的概念、數(shù)據(jù)類型描述、數(shù)據(jù)結(jié)構(gòu)和基本運(yùn)算算法及其性能分析等。本章同堆棧有點(diǎn)類似，算法思想較為簡單，所以能較好掌握；但難點(diǎn)重在循環(huán)隊(duì)列隊(duì)空、隊(duì)滿的判斷條件問題。

第六章“特殊矩陣、廣義表及其應(yīng)用”將學(xué)習(xí)數(shù)組、稀疏矩陣和廣義表的基本概念，幾種特殊矩陣的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算，在此基礎(chǔ)上學(xué)習(xí)特殊矩陣的計(jì)算算法與廣義表應(yīng)用等相關(guān)問題。本章的重點(diǎn)是相關(guān)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算算法。掌握了特殊矩陣的壓縮存儲(chǔ)結(jié)構(gòu)，在該存儲(chǔ)結(jié)構(gòu)下元素的定位方法，理解了稀疏矩陣的計(jì)算和廣義表的存儲(chǔ)結(jié)構(gòu)。

第七章二叉樹及其應(yīng)用。分為二叉樹的基本概念、二叉樹存儲(chǔ)結(jié)構(gòu)、二叉樹的遍歷算法、線索二叉樹、二叉樹的應(yīng)用（哈夫曼樹、二叉排序樹、堆和堆排序、基本算法）?；舅惴òǘ鏄涞慕ⅰ⒈闅v、線索化等算法。在此基礎(chǔ)上，介紹二叉樹的一些應(yīng)用問題，包括哈夫曼編碼問題、（平衡）二叉排序樹問題和堆排序問題等。

第八章說的是樹和森林，首先我們要知道樹與二叉樹是不同的概念。課本介紹了樹和森林的概念、遍歷和存儲(chǔ)結(jié)構(gòu)，還有樹、森林和二叉樹的相互關(guān)系，樹或森林怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹和森林等算法。

第九章“散列結(jié)構(gòu)及其應(yīng)用”是邏輯結(jié)構(gòu)“集合型”的數(shù)據(jù)元素在散列存儲(chǔ)方法下的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用知識(shí)內(nèi)容。主要介紹散列函數(shù)的概念、散列結(jié)構(gòu)的概念、散列存儲(chǔ)結(jié)構(gòu)的概念---散列表、散列函數(shù)和散列表中解決沖突的處理方法---開放定址法、鏈地址法以及散列表的基本算法及其性能分析。本章概念較為多，所以掌握不太好。

第十章圖及其應(yīng)用。分為圖的概念、圖的存儲(chǔ)結(jié)構(gòu)及其基本算法、圖的遍歷及算法、有向圖的連通性和最小生成樹、圖的最小生成樹、非連通圖的生成森林算法、最短路徑、有向無環(huán)圖及其應(yīng)用。

二、對各知識(shí)點(diǎn)的掌握情況

我對各知識(shí)點(diǎn)的掌握情況總結(jié)如下：

對于第一章對數(shù)據(jù)結(jié)構(gòu)的概念理解頗深，大概是每次都要談?wù)摰桨?。對算法的時(shí)間性能，空間性能基本了解。這些在后面的章節(jié)都會(huì)有運(yùn)用。第二章本章重點(diǎn)和難點(diǎn)在查找和排序問題的算法思想上，6種排序方法的性能比較。本章未掌握的為希爾排序、快速排序、歸并排序的時(shí)間復(fù)雜度分析。第三章，對鏈表掌握還好，對其數(shù)據(jù)結(jié)構(gòu)進(jìn)行了分析，有循環(huán)鏈表，掌握的不是很好，對其中一些用法不熟練。第四章堆棧，本章堆棧算法思想較為簡單，所以能較好掌握，但表達(dá)式計(jì)算問題未掌握好的。第五章的循環(huán)隊(duì)列隊(duì)空、隊(duì)滿的判斷條件問題掌握的不是很好。第六章的重點(diǎn)是相關(guān)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算算法。掌握了特殊矩陣的壓縮存儲(chǔ)結(jié)構(gòu)，在該存儲(chǔ)結(jié)構(gòu)下元素的定位方法，理解了稀疏矩陣的計(jì)算和廣義表的存儲(chǔ)結(jié)構(gòu)。第七章對二叉樹掌握較好，其概念，存儲(chǔ)，遍歷有很好的掌握。就是對二叉排序樹有點(diǎn)生疏，它的生成算法不是很會(huì)。第八章樹樹與二叉樹之間的轉(zhuǎn)換，森林與二叉樹的轉(zhuǎn)換算法思想基本掌握。第九章散列的一些知識(shí)，沒有深入學(xué)習(xí)，大概了解了散列存儲(chǔ)結(jié)構(gòu)散列表，散列函數(shù)，沖突的處理方法。第十章了解了圖的逆鄰接表的存儲(chǔ)結(jié)構(gòu)，關(guān)鍵路徑求解算法未能掌握好，不能靈活運(yùn)用圖的不同數(shù)據(jù)結(jié)構(gòu)和遍歷算法解決復(fù)雜的應(yīng)用問題。

三、學(xué)習(xí)體會(huì)

剛剛接觸這門課時(shí)，看到課本中全是算法，當(dāng)時(shí)就暈了，因?yàn)槲业腃語言學(xué)的不好，我擔(dān)心會(huì)影響這門課的學(xué)習(xí)，后來上課時(shí)老師說學(xué)習(xí)這門課的基礎(chǔ)是C語言，所以我當(dāng)時(shí)就決定一定要好好補(bǔ)補(bǔ)，爭取不被拖后腿，在學(xué)習(xí)這門課的期間，也遇到了不少問。但是通過學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，讓我對程序有了新的認(rèn)識(shí)，也有了更深的理解。同時(shí)，也讓我認(rèn)識(shí)到，不管學(xué)習(xí)什么，概念是基礎(chǔ)，所有的知識(shí)框架都是建立在基礎(chǔ)概念之上的，所以，第一遍看課本要將概念熟記于心，然后構(gòu)建知識(shí)框架。并且，對算法的學(xué)習(xí)是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。在第二遍看課本的過程中，要注重對算法的掌握。對于一個(gè)算法，讀一遍可能能讀懂，但不可能完全領(lǐng)會(huì)其中的思想。掌握一個(gè)算法，并不是說將算法背過，而是掌握算法的思想。我們需要的是耐心。每看一遍就會(huì)有這一遍的收獲。讀懂算法之后，自己再默寫算法，寫到不會(huì)的地方，看看課本想想自己為什么沒有想到。對算法的應(yīng)用上，學(xué)習(xí)算法的目的是利用算法解決實(shí)際問題。會(huì)寫課本上已有的算法之后，可以借其思想進(jìn)行擴(kuò)展，逐步提高編程能力。

四、對課程教學(xué)的建議

1、課程課時(shí)較緊，課堂上的練習(xí)時(shí)間較少，講解的東西越多，頭腦有時(shí)就很混亂。

2、感覺上課時(shí)的氣氛不是很好，雖然大部分人都在聽，可是效果不是很好。所以希望老師能在授課中間能穿插一些活躍課堂氛圍的話題，可以是大家都非常關(guān)心的一些內(nèi)容，這樣既讓大家能在思考之余有一個(gè)放松，也能夠提高學(xué)生的學(xué)習(xí)積極性和學(xué)習(xí)效率。

3、學(xué)習(xí)的積極性很重要，有時(shí)候我們花了很長時(shí)間去寫實(shí)驗(yàn)報(bào)告，也很認(rèn)真的去理解去掌握，可是最后實(shí)驗(yàn)報(bào)告可能就只得了一個(gè)C，抄的人反而得A，這樣的話很容易打擊學(xué)生的積極性，在后面的實(shí)驗(yàn)報(bào)告中沒動(dòng)力再去認(rèn)真寫。所以希望老師能在這方面有所調(diào)整。

4、雖然講課的時(shí)間很緊，但是還是希望老師能在講述知識(shí)點(diǎn)的時(shí)候能運(yùn)用實(shí)際的調(diào)試程序來給我們講解，這樣的話能讓我們對這些內(nèi)容有更深刻的印象和理解。

第四篇：《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)大綱

Data Structure 執(zhí)筆人：

編寫日期：

一、課程基本信息

1.課程編號(hào)：

2.課程性質(zhì)/類別： 必修課 / 專業(yè)主干課

3.學(xué)時(shí)/學(xué)分： 48 學(xué)時(shí)（另實(shí)驗(yàn)16學(xué)時(shí)）/ 4 學(xué)分

4.適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、網(wǎng)絡(luò)工程、信息管理與信息系統(tǒng)等專業(yè)

二、課程教學(xué)目標(biāo)及學(xué)生應(yīng)達(dá)到的能力

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課、必修課程，主要介紹用計(jì)算機(jī)解決一系列問題特別是非數(shù)值信息處理問題時(shí)所用的各種組織數(shù)據(jù)的方法、存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。通過本課程的學(xué)習(xí)，要求學(xué)生掌握各種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)表示、運(yùn)算方法以及在計(jì)算機(jī)科學(xué)中最基本的應(yīng)用，培養(yǎng)、訓(xùn)練學(xué)生選用合適的數(shù)據(jù)結(jié)構(gòu)和編寫質(zhì)量高、風(fēng)格好的應(yīng)用程序的能力，培養(yǎng)學(xué)生分析問題、解決問題的能力，并為后續(xù)課程的學(xué)習(xí)打下良好的理論基礎(chǔ)和實(shí)踐基礎(chǔ)。

三、課程教學(xué)內(nèi)容與基本要求

（一）緒論（3 學(xué)時(shí)）1．主要內(nèi)容：

（1）介紹什么是數(shù)據(jù)結(jié)構(gòu)；

（2）基本概念和術(shù)語: 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象，以及數(shù)據(jù)結(jié)構(gòu)的定義、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)（理解）數(shù)據(jù)類型、抽象數(shù)據(jù)類型；

（3）抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)；

（4）算法和算法分析: 算法的概念、算法設(shè)計(jì)的要求以及算法效率的度量。2．基本要求

（1）了解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性；

（2）掌握數(shù)據(jù)結(jié)構(gòu)的定義及相關(guān)概念和術(shù)語；（3）了解抽象數(shù)據(jù)類型的定義、表示與實(shí)現(xiàn)方法；（4）理解算法的概念、特點(diǎn)并掌握度量其效率的基本方法。3．自學(xué)內(nèi)容：

類C語言的書寫規(guī)范。

（二）線性表（6 學(xué)時(shí)）1．主要內(nèi)容：

（1）線性表的抽象數(shù)據(jù)類型定義和相關(guān)概念：數(shù)據(jù)項(xiàng)、記錄、文件等；（2）線性表順序存儲(chǔ)表示和基本操作的實(shí)現(xiàn)；（3）線性表的鏈?zhǔn)酱鎯?chǔ)表示和基本操作的實(shí)現(xiàn)；

（4）稀疏多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示和加法的實(shí)現(xiàn)。2．基本要求

（1）掌握線性表的定義和特點(diǎn)；

（2）熟練掌握線性表的順序存儲(chǔ)表示和插入、刪除、查找等實(shí)現(xiàn)算法；

（3）熟練掌握單鏈表、循環(huán)鏈表、雙向鏈表三種鏈表的表示，以及單鏈表的查找、插入、刪除、創(chuàng)建等實(shí)現(xiàn)算法。

3．自學(xué)內(nèi)容：

靜態(tài)鏈表。

（三）棧和隊(duì)列（5 學(xué)時(shí)）1．主要內(nèi)容：

（1）棧和隊(duì)列的結(jié)構(gòu)特性和抽象數(shù)據(jù)類型定義；（2）棧和隊(duì)列的順序存儲(chǔ)表示和實(shí)現(xiàn)；（3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)表示和實(shí)現(xiàn)；（4）棧和隊(duì)列在程序設(shè)計(jì)中的應(yīng)用。2．基本要求

（1）掌握棧和隊(duì)列兩種抽象數(shù)據(jù)類型的特點(diǎn)；

（2）掌握棧的兩種存儲(chǔ)表示和實(shí)現(xiàn)，特別注意棧滿?？盏臈l件；（3）掌握隊(duì)列的兩種存儲(chǔ)表示和實(shí)現(xiàn)，特別注意隊(duì)滿隊(duì)空的條件；（4）了解遞歸算法與棧的關(guān)系。3．自學(xué)內(nèi)容：

鏈棧，離散事件模擬

（四）串（3 學(xué)時(shí)）1．主要內(nèi)容：

（1）串的抽象數(shù)據(jù)類型定義；

（2）串的表示和實(shí)現(xiàn): 定長順序存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；（3）串的各種基本操作的實(shí)現(xiàn)及其應(yīng)用；（4）串的模式匹配操作。2．基本要求

（1）熟悉串的一些基本操作的定義，并能利用基本操作實(shí)現(xiàn)串的其它操作；（2）掌握串的定長順序存儲(chǔ)結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)；（3）掌握串的堆分配存儲(chǔ)結(jié)構(gòu)以及基本操作的實(shí)現(xiàn)；（4）掌握串的簡單模式匹配算法，理解KMP算法。3．自學(xué)內(nèi)容：

串操作的應(yīng)用實(shí)例。

（五）數(shù)組和廣義表（4 學(xué)時(shí)）1．主要內(nèi)容：

（1）數(shù)組的抽象數(shù)據(jù)類型定義及其順序表示和實(shí)現(xiàn)；（2）特殊矩陣和稀疏矩陣的壓縮存儲(chǔ)；（3）廣義表的抽象數(shù)據(jù)類型定義和存儲(chǔ)結(jié)構(gòu)。2．基本要求

（1）了解數(shù)組的兩種存儲(chǔ)表示方法，并掌握數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法；（2）掌握對特殊矩陣進(jìn)行壓縮存儲(chǔ)時(shí)的下標(biāo)變換公式；

（3）熟悉稀疏矩陣的三元組順序表存儲(chǔ)結(jié)構(gòu)下的一般轉(zhuǎn)置和快速轉(zhuǎn)置算法；了解十字鏈表等存儲(chǔ)結(jié)構(gòu)；

（4）掌握廣義表的結(jié)構(gòu)特點(diǎn)、取表頭表尾操作，及其存儲(chǔ)表示方法。3．自學(xué)內(nèi)容：

采用十字鏈表存儲(chǔ)結(jié)構(gòu)創(chuàng)建稀疏矩陣。

（六）樹和二叉樹（10 學(xué)時(shí)）1．主要內(nèi)容：

（1）樹的抽象數(shù)據(jù)類型定義和基本術(shù)語；

（2）二叉樹的抽象數(shù)據(jù)類型定義、性質(zhì)和存儲(chǔ)結(jié)構(gòu)；（3）二叉樹的遍歷；

（4）線索二叉樹的定義、遍歷及線索化二叉樹；

（5）樹的存儲(chǔ)結(jié)構(gòu)、樹和森林的遍歷以及與二叉樹的轉(zhuǎn)換；（6）Huffman樹及其應(yīng)用。2．基本要求

（1）掌握樹型結(jié)構(gòu)的特點(diǎn)和基本術(shù)語；

（2）熟練掌握二叉樹的性質(zhì)，了解相應(yīng)的證明方法；

（3）了解二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，熟練掌握二叉鏈表存儲(chǔ)結(jié)構(gòu)；（4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其他操作；

（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結(jié)點(diǎn)的前驅(qū)與后繼的方法；

（6）熟悉樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；（7）了解Huffman樹的特性，掌握建立Huffman樹和Huffman編碼的方法。3．自學(xué)內(nèi)容：

先序、后序遍歷二叉樹非遞歸算法，層次遍歷二叉樹算法。

（七）圖（9 學(xué)時(shí)）1．主要內(nèi)容：（1）圖的定義和術(shù)語；

（2）圖的四種存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法（鄰接矩陣）、鄰接表、十字鏈表和鄰接多重表；（3）圖的兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷；（4）圖的連通性和最小生成樹；

（5）有向無環(huán)圖及其應(yīng)用：拓?fù)渑判蚝完P(guān)鍵路徑；（6）最短路徑問題。2．基本要求

（1）熟悉圖的定義和術(shù)語；

（2）了解圖的存儲(chǔ)結(jié)構(gòu)，熟練掌握數(shù)組表示法（鄰接矩陣）和鄰接表存儲(chǔ)表示；（3）熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法；（4）掌握無向連通帶權(quán)圖的最小生成樹求解算法；

（5）了解有向無環(huán)圖、AOV網(wǎng)、AOE網(wǎng)及其在實(shí)際中的應(yīng)用，熟悉拓?fù)渑判蛩惴ê完P(guān)鍵路徑算法；

（6）熟悉兩種最短路徑問題求解算法。3．自學(xué)內(nèi)容：

樹的先根遍歷算法與圖的深度優(yōu)先遍歷算法比較；

樹的層次遍歷算法與圖的廣度優(yōu)先遍歷算法比較。

（八）查找（4 學(xué)時(shí)）1．主要內(nèi)容：

（1）查找的基本概念和相關(guān)術(shù)語；

（2）靜態(tài)查找表：順序查找、折半查找和索引順序表查找；（3）動(dòng)態(tài)查找表：二叉排序樹的查找、插入和刪除；（4）哈希表。2．基本要求

（1）了解查找的作用，熟悉相關(guān)術(shù)語；

（2）熟練掌握順序查找、折半查找和索引順序表查找；（3）熟練掌握二叉排序樹的特性、構(gòu)造和查找方法；

（4）熟練掌握哈希表的構(gòu)造方法，特別是哈希函數(shù)和處理沖突方法的選?。唬?）通過分析等概率下的平均查找長度來衡量各種查找方法的效率。3．自學(xué)內(nèi)容：

平衡二叉樹。

（九）內(nèi)部排序（4 學(xué)時(shí)）1．主要內(nèi)容：

（1）排序的基本概念和相關(guān)術(shù)語；

（2）插入排序：直接插入排序、折半插入排序和希爾排序；（3）交換排序：起泡排序和快速排序；（4）選擇排序：簡單選擇排序和堆排序；（5）歸并排序：二路歸并排序；（6）基數(shù)排序：鏈?zhǔn)交鶖?shù)排序；（7）各種內(nèi)部排序方法的比較討論。2．基本要求

（1）了解排序作用，熟悉相關(guān)術(shù)語；

（2）掌握多種排序的基本思想、算法特點(diǎn)和排序過程，分析它們的時(shí)間復(fù)雜度、空間復(fù)雜度和穩(wěn)定性。

3．自學(xué)內(nèi)容：

二路插入排序、表插入排序和樹形選擇排序。

四、教學(xué)安排建議

1.作業(yè)練習(xí) 完成每章的教學(xué)后進(jìn)行布置習(xí)題，使用教材配套的《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》。盡量選擇基礎(chǔ)的并且加注了標(biāo)記的題，應(yīng)注重于精，而不要求多。要求積極獨(dú)立完成所布置的習(xí)題，建議安排至少六次。

2.案例分析

可參考選擇以下一些案例：（1）學(xué)生通訊錄管理系統(tǒng)，（2）表達(dá)式求值問題（3）交通咨詢系統(tǒng)，等。3.專題研討

可參考選擇以下一些：（1）最小生成樹問題（2）航班信息查詢與檢索系統(tǒng)，（3）內(nèi)部排序算法比較，等。

4.實(shí)驗(yàn)安排

為了達(dá)到理論與實(shí)際應(yīng)用的結(jié)合，讓學(xué)生能將所學(xué)知識(shí)應(yīng)用于實(shí)際問題的求解中，培養(yǎng)學(xué)生的實(shí)際動(dòng)手能力，從而加深對概念及所學(xué)知識(shí)的理解，靈活、牢固掌握教材內(nèi)容，提高程序設(shè)計(jì)及解決實(shí)際問題的能力，實(shí)驗(yàn)環(huán)節(jié)的安排非常重要。

建議實(shí)驗(yàn)安排為八次，共16學(xué)時(shí)，分別如下：

實(shí)驗(yàn)1 線性表的順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)(2學(xué)時(shí))

實(shí)驗(yàn)2 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的實(shí)現(xiàn)(2學(xué)時(shí))

實(shí)驗(yàn)3 棧的算法實(shí)現(xiàn)(2學(xué)時(shí))

實(shí)驗(yàn)4 隊(duì)列的算法實(shí)現(xiàn)(2學(xué)時(shí))

實(shí)驗(yàn)5 串類型及操作(2學(xué)時(shí))

實(shí)驗(yàn)6 二叉樹的建立與遍歷(2學(xué)時(shí))

實(shí)驗(yàn)7 圖的建立與遍歷(2學(xué)時(shí))

實(shí)驗(yàn)8 查找與排序(2學(xué)時(shí))注：教師可根據(jù)教學(xué)實(shí)際情況（如：學(xué)生情況及學(xué)時(shí)情況等），適當(dāng)調(diào)整實(shí)踐教學(xué)內(nèi)容及學(xué)時(shí)分配。

五、課程考核

1.考核形式及成績評定辦法

本課程考核形式為：平時(shí)成績占40%，期末考試成績占60%。其中平時(shí)成績的結(jié)構(gòu)分包括：課堂表現(xiàn)10%、平時(shí)作業(yè)10%和實(shí)驗(yàn)20%，期末考試為閉卷筆試考試：120分鐘，卷面分滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。

2.本課程考核的基本要求

課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時(shí)達(dá)到本課程教學(xué)時(shí)數(shù)的1/3，則取消考試資格。

平時(shí)作業(yè)10%：根據(jù)上交次數(shù)及完成情況進(jìn)行評定。

實(shí)驗(yàn)20%：根據(jù)各次實(shí)驗(yàn)完成情況及實(shí)驗(yàn)報(bào)告成績進(jìn)行評定。

期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊(duì)列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點(diǎn)。

六、本課程與其它課程的先行后續(xù)關(guān)系

先行課程：《高級(jí)程序設(shè)計(jì)語言》、《離散數(shù)學(xué)》

后續(xù)課程：《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫理論》、《算法分析與設(shè)計(jì)》等

七、建議教材及教學(xué)參考書

1.教材：

嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學(xué)出版，2012.5 嚴(yán)蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》，清華大學(xué)出版，2012.5 2.參考書：

[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結(jié)構(gòu)簡明教程》，清華大學(xué)出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結(jié)構(gòu)與算法》，機(jī)械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結(jié)構(gòu)》，西安電子科技大學(xué)出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結(jié)構(gòu)》，大連理工大學(xué)出版社，1989

[7] Aho A V, Hopcroft J E, Ullman J D.Data Structures and Algorithms.Addison-Wesley Publishing Company,Inc.,1983

[8] Baron R J, Shapiro L G.Data Structures and their Implementation.Van Nostrand Reinhold Company, 1980

[9] Esakov J, Weiss T.Data Structures: An Advanced Approach Using C.Prentice-Hall, Inc.,1989

[10] [美]S巴斯《計(jì)算機(jī)算法：設(shè)計(jì)和分析引論》朱洪等譯，復(fù)旦大學(xué)出版社，1985

第五篇：數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱

一、課程基本概況

課程名稱：數(shù)據(jù)結(jié)構(gòu)

課程名稱（英文）： Data Structures

課程編號(hào)：B09042

課程總學(xué)時(shí)：60（其中，講課48，實(shí)驗(yàn)12）

課程學(xué)分：3

課程分類：專業(yè)選修課

開設(shè)學(xué)期：4

適用專業(yè)：計(jì)算機(jī)網(wǎng)絡(luò)工程本科

先修課程：集合論，圖論，高級(jí)語言（結(jié)構(gòu)或記錄，指針）

后續(xù)課程：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等

二、課程的性質(zhì)、目的和任務(wù)

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門核心專業(yè)課程，是軟件課程中非常重要的一門課程，在整個(gè)專業(yè)教學(xué)中占有十分重要的地位，是一門理論性非常強(qiáng)的課程。通過課堂教學(xué)、課外練習(xí)和上機(jī)實(shí)習(xí)，使學(xué)生了解數(shù)據(jù)對象的特性，數(shù)據(jù)組織的基本方法，并初步具備分析和解決現(xiàn)實(shí)世界問題在計(jì)算機(jī)中如何表示和處理的能力以及培養(yǎng)良好的程序設(shè)計(jì)技能，為后續(xù)課程的學(xué)習(xí)和科研工作的參與打下良好的基礎(chǔ)。

三、主要內(nèi)容、重點(diǎn)及深度

本門課程共60學(xué)時(shí)，其中理論教學(xué)48學(xué)時(shí)，實(shí)驗(yàn)教學(xué)12學(xué)時(shí)。其中，理論教學(xué)部分：

第一章

緒論

（一）目的要求

了解數(shù)據(jù)結(jié)構(gòu)的意義與發(fā)展過程、數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中的作用、學(xué)習(xí)本課程的目的、任務(wù)及要求。理解數(shù)據(jù)結(jié)構(gòu)的基本概念；算法設(shè)計(jì)；掌握算法的時(shí)間和空間復(fù)雜度。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.相關(guān)的基本概念(掌握)；

2.算法五大要素(掌握)；

3.計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度的方法（掌握）。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法的描述方法。

難點(diǎn)：數(shù)據(jù)結(jié)構(gòu)的定義；算法與程序的區(qū)別；時(shí)間復(fù)雜度及其計(jì)算。

第二章

線性表

（一）目的要求

掌握線性表的邏輯結(jié)構(gòu)；線性表的存儲(chǔ)結(jié)構(gòu)及操作的實(shí)現(xiàn)；理解一元多項(xiàng)式的表示；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.線性表的邏輯結(jié)構(gòu)(掌握)；2.線性表的存儲(chǔ)結(jié)構(gòu)(掌握)；

3.線性表在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法(掌握)；

4.從時(shí)間和空間復(fù)雜度的角度比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：線性表的概念；線性表的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其常用算法。難點(diǎn)：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其常用算法；雙向循環(huán)鏈表。

第三章 棧和隊(duì)列

（一）目的要求

掌握棧的定義，表示及實(shí)現(xiàn)；表達(dá)式求值；棧與遞歸過程；隊(duì)列的定義、表示及實(shí)現(xiàn)。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)： 1.棧和隊(duì)列的特點(diǎn)(掌握)；

2.在兩種存儲(chǔ)結(jié)構(gòu)上棧的基本操作的實(shí)現(xiàn)(掌握)； 3.循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算(熟練掌握)； 4.遞歸算法執(zhí)行過程中棧狀態(tài)的變化過程(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：堆棧和隊(duì)列的概念；遞歸的定義；循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算。難點(diǎn)：遞歸的編程實(shí)現(xiàn)；循環(huán)隊(duì)列和鏈隊(duì)列的基本運(yùn)算。

第四章 串

（一）目的要求

了解串的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)；掌握串操作的實(shí)現(xiàn)(重點(diǎn)難點(diǎn)BF和KMP算法)串的應(yīng)用。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.串的七種基本運(yùn)算的定義（了解）；

2.利用這些基本運(yùn)算來實(shí)現(xiàn)串的其它各種運(yùn)算的方法(掌握)； 3.在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種操作的方法(掌握)；

4.KMP算法，熟悉NEXT函數(shù)和改進(jìn)NEXT函數(shù)的定義和計(jì)算(掌握)； 5.串名的存儲(chǔ)映象和在堆存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)串操作的方法(理解)。

（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：串定義和存儲(chǔ)方法；串的操作 難點(diǎn)：串操作實(shí)現(xiàn)方法

第五章 數(shù)組和廣義表

（一）目的要求

掌握數(shù)組的存儲(chǔ)結(jié)構(gòu)；稀疏矩陣的表示及操作的實(shí)現(xiàn)；廣義表的定義和存儲(chǔ)結(jié)構(gòu)；廣義表的遞歸算法。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：1.數(shù)組在以行為主的存儲(chǔ)結(jié)構(gòu)中的地址計(jì)算方法(掌握)； 2.矩陣實(shí)現(xiàn)壓縮存儲(chǔ)時(shí)的下標(biāo)變換(掌握)；

3.理解稀疏矩陣的兩種存儲(chǔ)方式的特點(diǎn)和適用范圍，領(lǐng)會(huì)以三元組表示稀疏矩陣時(shí)進(jìn)行運(yùn)算采用的處理方法(掌握)；

4.廣義表的定義及其存儲(chǔ)結(jié)構(gòu)，學(xué)會(huì)廣義表的表頭，表尾分析方法(掌握)； 5.學(xué)習(xí)編制廣義表的遞歸算法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：多維數(shù)組元素存儲(chǔ)地址的計(jì)算；稀疏矩陣的三元組表示；廣義表的存儲(chǔ)定義、操作。難點(diǎn)：稀疏矩陣的三元組表示；廣義表的存儲(chǔ)定義、操作。

第六章 樹和二叉樹

（一）目的要求

了解樹的基本概念；理解二叉樹的性質(zhì)和存儲(chǔ)結(jié)構(gòu)；遍歷二叉樹和線索二叉樹；理解樹的存儲(chǔ)結(jié)構(gòu)和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應(yīng)用；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)： 1.二叉樹的結(jié)構(gòu)特點(diǎn)(理解)；

2.二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍(掌握)； 3.按各種次序遍歷二叉樹的遞歸和非遞歸算法(掌握)；

4.二叉樹的線索化，在中序線索樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法(掌握)； 5.樹的各種存儲(chǔ)結(jié)構(gòu)及其特點(diǎn)(掌握)； 6.編寫樹的各種運(yùn)算的算法(掌握)；

7.建立最優(yōu)二叉樹和哈夫曼編碼的方法(掌握)。

（三）重點(diǎn)與難點(diǎn) 重點(diǎn)：二叉樹的概念、性質(zhì)；二叉樹的遍歷方式；構(gòu)造二叉排序樹。難點(diǎn)：二叉樹的遍歷方式；二叉排序樹的構(gòu)造方法；二叉樹的線索化。

第七章 圖

（一）目的要求

理解圖的基本概念；圖的存儲(chǔ)結(jié)構(gòu)；掌握圖的遍歷及應(yīng)用{最小生成樹，最短路徑等}；拓?fù)渑判蚝完P(guān)鍵路徑。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)： 1.熟悉圖的各種存儲(chǔ)結(jié)構(gòu)；

2.了解實(shí)際問題與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系(掌握)； 3.遍歷圖的遞歸和非遞歸算法(掌握)；

4.應(yīng)用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等）(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷 難點(diǎn)：圖遍歷的算法；

第八章

動(dòng)態(tài)存儲(chǔ)管理

（一）目的要求

了解邊界標(biāo)識(shí)法和伙伴系統(tǒng)；無用單元收集和緊縮；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.存儲(chǔ)器分配策略和算法（了解）；

2.無用單元收集時(shí)的標(biāo)志算法（了解）。

（三）重點(diǎn)與難點(diǎn)

存儲(chǔ)器分配策略和算法、無用單元收集時(shí)的標(biāo)志算法

第九章

查找

（一）目的要求

了解靜態(tài)查找表(順序表，有序表，索引順序表)；動(dòng)態(tài)查找表(二叉排序樹，平衡二叉樹，B-樹和B+樹)的建立和查找；掌握哈希表的建立，查找及分析；

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.順序查找、折半查找和索引查找的方法、應(yīng)用(掌握)；

2.二叉排序樹的構(gòu)造方法(掌握)；

3.二叉平衡樹的建立方法(掌握)；

4.B-樹，B+樹和鍵樹的特點(diǎn)以及它們的建立過程（理解）；

5.哈希表的構(gòu)造方法(掌握)；

6.按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)和失敗時(shí)的平均查找長度；

7.哈希表在查找不成功時(shí)的平均查找長度的計(jì)算方法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：二叉排序樹的構(gòu)造方法、二叉平衡樹的建立方法；哈希表的構(gòu)造、應(yīng)用；

難點(diǎn)：二叉排序樹的構(gòu)造及應(yīng)用；哈希表的構(gòu)造方法；查找的平均長度。

第十章

內(nèi)部排序

（一）目的要求

掌握插入排序、交換排序(起泡排序，快速排序)、選擇排序(簡單選擇，樹形選擇，堆)、歸并排序、基數(shù)排序等算法。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.各種排序方法的特點(diǎn)并能靈活應(yīng)用(掌握)； 2.各種方法的排序過程(掌握)；

3.各種排序方法的時(shí)間復(fù)雜度分析(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：各種排序方法的特點(diǎn)及其應(yīng)用；實(shí)現(xiàn)排序的各種算法。難點(diǎn)：各種排序算法的時(shí)間復(fù)雜度分析。

十一章

外部排序

（一）目的要求

理解外部排序的基本方法；掌握敗者樹和多路平衡歸并的實(shí)現(xiàn)；置換--選擇排序；最佳歸并樹。

（二）教學(xué)內(nèi)容 本章知識(shí)點(diǎn)：

1.外部排序的兩個(gè)過程(理解)；

2.外排過程中所需進(jìn)行外存讀/寫次數(shù)的計(jì)算方法(掌握)；

3.敗者樹的建立過程(掌握)；

4.實(shí)現(xiàn)多路歸并的算法(掌握)；

5.置換-選擇排序的過程(掌握)；

6.最佳歸并樹的構(gòu)造方法（熟悉）；

7.按最佳歸并樹的歸并方案進(jìn)行平衡歸并時(shí)，外存讀/寫次數(shù)的計(jì)算方法(掌握)。

（三）重點(diǎn)與難點(diǎn)

重點(diǎn)：外部排序過程和實(shí)現(xiàn)方法；多路并歸算法及其實(shí)現(xiàn)； 難點(diǎn)：最佳并歸樹的構(gòu)造方法及其應(yīng)用。

實(shí)踐教學(xué)部分：上機(jī)實(shí)驗(yàn)分4個(gè)專題，每個(gè)專題可提供2~4個(gè)難度不等的題目供選。

實(shí)驗(yàn)一

停車場管理系統(tǒng)

（一）實(shí)驗(yàn)內(nèi)容 以棧模擬車場，以隊(duì)列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。

（二）實(shí)驗(yàn)過程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。

（三）實(shí)驗(yàn)教學(xué)基本要求

通過實(shí)例，使學(xué)生掌握棧和隊(duì)列兩種特殊的線性結(jié)構(gòu)，掌握棧和隊(duì)列的特點(diǎn)。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。

（五）實(shí)驗(yàn)學(xué)時(shí) 4學(xué)時(shí)

實(shí)驗(yàn)二

教學(xué)計(jì)劃編制問題

（一）實(shí)驗(yàn)內(nèi)容

假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。編制一個(gè)教學(xué)計(jì)劃程序。

（二）實(shí)驗(yàn)過程編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容。

（三）實(shí)驗(yàn)教學(xué)基本要求

通過實(shí)例，使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。

（五）實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)

實(shí)驗(yàn)三

最小生成樹問題

（一）實(shí)驗(yàn)內(nèi)容

利用克魯斯卡爾算法求最小生成樹。以文本形式輸出樹中各條邊以及他們的權(quán)值。

（二）實(shí)驗(yàn)過程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容

（三）實(shí)驗(yàn)教學(xué)基本要求

通過實(shí)例，使學(xué)生熟悉圖的各種存儲(chǔ)結(jié)構(gòu)的特性，掌握如何應(yīng)用圖結(jié)構(gòu)解決具體問題。實(shí)驗(yàn)后學(xué)生提交實(shí)驗(yàn)報(bào)告。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)。

（五）實(shí)驗(yàn)學(xué)時(shí) 2學(xué)時(shí)

實(shí)驗(yàn)四

哈希表設(shè)計(jì)

（一）實(shí)驗(yàn)內(nèi)容

假設(shè)人名為中國人的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測再散列法處理沖突。

（二）實(shí)驗(yàn)過程 編程實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容

（三）實(shí)驗(yàn)教學(xué)基本要求 掌握索引技術(shù)的使用。

（四）實(shí)驗(yàn)設(shè)備和材料 計(jì)算機(jī)

（五）實(shí)驗(yàn)學(xué)時(shí) 4學(xué)時(shí)

五、課程教學(xué)的基本要求和主要環(huán)節(jié)

本課程可采用課堂講授、課堂討論、習(xí)題課等進(jìn)行課堂教學(xué);條件允許可采用CAI、電子教案、幻燈片、參觀等進(jìn)行輔助教學(xué);每章布置3~6道習(xí)題以鞏固教學(xué);在課程后半程，安排3~4個(gè)上機(jī)實(shí)驗(yàn)，讓學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論、方法，分組設(shè)計(jì)幾個(gè)較大的軟件，使理論與實(shí)際相結(jié)合。

考試采用閉卷方式。總成績由平時(shí)成績和考試成績組成。平時(shí)成績占30%，考試成績占70%。

六、本課程與其它課程的聯(lián)系與分工

先修課包括：集合論，圖論，高級(jí)語言（結(jié)構(gòu)或記錄，指針）；

后續(xù)課包括：數(shù)據(jù)庫，編譯原理，操作系統(tǒng)等。

七、建議教材與參考教材

《數(shù)據(jù)結(jié)構(gòu)》（C語言版）

嚴(yán)蔚敏等

清華大學(xué)出版社

1997 《數(shù)據(jù)結(jié)構(gòu)題集》

嚴(yán)蔚敏等

清華大學(xué)出版社

1999

《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》

李春葆

清華大學(xué)出版社

2004

八、負(fù)責(zé)人

撰稿人：劉景匯、李玉香

審稿人：

系（院）領(lǐng)導(dǎo)：