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

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

●數(shù)據(jù)元素:數(shù)據(jù)的基本單位,可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨立含義的最小標識單位。

●數(shù)據(jù)結構的定義: ●邏輯結構:從邏輯結構上描述數(shù)據(jù),獨立于計算機。線性結構:一對一關系。線性結構:多對多關系。

●存儲結構:是邏輯結構用計算機語言的實現(xiàn)。順序存儲結構:如數(shù)組。鏈式存儲結構:如鏈表。索引結構:索引表。散列存儲結

構:如散列表。

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

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

于描述機制定義,是導出類型。

●程序設計的實質是對實際問題選擇一種好的數(shù)據(jù)結構,設計一個好的算法。算法取決于數(shù)據(jù)結構。

●算法是一個自定義的計算過程,以一個或多個值輸入,并以一個或多個值輸出。

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

●時間復雜度:是某個算法的時間耗費,它是該算法所求解問題規(guī)模n的函數(shù)。漸近時間復雜度:是指當問題規(guī)模趨向無窮大時，該算法時間復雜度的數(shù)量級。評價一個算法的時間性能時,主要標準就是算法的漸近時間復雜度。

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

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

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

●線性表上定義的基本運算:構造空表:Initlist;求表長:Listlength;取結點:GetNode;查找:LocateNode;插入:InsertList;刪

除:Delete。

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

點相鄰關系是一致的。地址計算:? ●在順序表中實現(xiàn)的基本運算:插入:平均移動結點次數(shù)為?;平均時間復雜度均為?。刪除:平均移動結點次數(shù)為?;平均時間復雜

度均為?。

●線性表的鏈式存儲結構中結點的邏輯次序和物理次序不一定相同,為了能正確表示結點間的邏輯關系,在存儲每個結點值的同時，還存儲了其后繼結點的地址信息。這兩部分信息組成鏈表中的結點結構。一個單鏈表由頭指針的名字來命名。

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

頭結點的算法:對開始結點的操作無需特殊處理,統(tǒng)一了空表和非空表。查找(按序號:與查找位置有關,平均時間復雜度均為?。

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

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

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

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

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

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

●基于時間:順序表是隨機存儲結構,當線性表的操作主要是查找時,宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲

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

●棧是僅限制在表的一端進行插入和刪除運算的線性表,稱插入、刪除這一端為棧頂,另一端稱為棧底。表中無元素時為空棧。棧 的修改是按后進先出的原則進行的,我們又稱棧為LIFO表。通常棧有順序棧和鏈棧兩種存儲結構。

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

轉移的條件。

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

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

為隊尾,隊列的操作原則是先進先出的,又稱作FIFO表.隊列也有順序存儲和鏈式存儲兩種存儲結構。

●隊列的基本運算有六種:置空隊:InitQueue,判隊空:QueueEmpty,判隊滿:QueueFull,入隊:EnQueue,出隊:DeQueue,取

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

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

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

●隊列的鏈式存儲結構稱為鏈隊列,一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進行插入的操作,在表尾增加一個尾

指針,一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中,要注意當原隊中只有一個結點時,出隊后要同進修改頭尾指針并使隊列變空。

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

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

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

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

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

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

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

●串的鏈式存儲就是用單鏈表的方式存儲串值,串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數(shù)據(jù)域為單

個字符。為了解決“存儲密度”低的狀況,可以讓一個結點存儲多個字符,即結點的大小。

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

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

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

個相同的非零元素分配一個存儲空間;對零元素不分配空間。

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

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

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

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

素構成的子表,不能對空表操作

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

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

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

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

●樹的存儲結構多用的是鏈式存儲。二叉樹的鏈式存儲結構,稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域, n+1個空指針。

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

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

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

●樹和森林及二叉樹的轉換是唯一對應的。二叉樹變樹:結點的右孩子與其雙親連。森林變二叉樹:樹變二叉樹,各個樹的根相連。

轉換方法? ●樹的存儲結構:有雙親鏈表表示法:孩子鏈表表示法:雙親孩子鏈表表示法:孩子兄弟鏈表表示法: ●樹的前序遍歷與相對應的二叉樹的前序遍歷一致;樹的后序遍歷與相對應的二叉樹的中序遍歷一致。

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

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

●圖的邏輯結構特征就是其結點的前趨和后繼的個數(shù)都是沒有限制的,即任意兩個結點之間之間都可能相關。

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

●圖的存儲結構:鄰接矩陣表示法:適合稠密圖。無向鄰接矩陣是對稱的。有向行是出度,列是入度。建立鄰接矩陣算法的時間是

O,其時間復雜度為O。鄰接表表示法:適合稀疏圖。時間復雜度為O,空間復雜度為O。

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

點。

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

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

●最短路徑的算法:Dijkstra算法,時間復雜度為O。

●拓撲排序:無前趨的頂點優(yōu)先:每次輸出一個無前趨的結點并刪去此結點及其出邊,最后得到的序列即拓撲序列。無后繼的結點

優(yōu)先:每次輸出一個無后繼的結點并刪去此結點及其入邊,最后得到的序列是逆拓撲序列。

●關于排序

●關鍵字項,關鍵字。

●排序是使文件中的記錄按關鍵字遞增次序排列起來?！窕静僮?比較關鍵字大小;改變指向記錄的指針或移動記錄。

●存儲結構:順序結構、鏈表結構、索引結構。經過排序后這些具有相同關鍵字的記錄之間的相對次序保持不變,則稱這種排序方

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

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

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

●評價排序算法好壞的標準主要有兩條:執(zhí)行時間和所需的輔助空間,另外算法的復雜程序也是要考慮的一個因素。

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

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

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

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

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

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

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

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

3、關鍵字的結構及其初始狀態(tài);●

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

5、語言工具的條件;●

6、存儲結構;時間和輔助空間復雜度?！耜P于查找

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

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

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

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

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

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

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

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

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

第二篇：“數(shù)據(jù)結構”課程總結

“數(shù)據(jù)結構”課程總結

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

一、課程建設指導思想、定位和特色 1．學科地位

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

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

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

采用國內經典教材，結合前沿的研究領域和最新科研動態(tài)，豐富教學內容，讓學生了解數(shù)據(jù)結構的實際應用價值。

采用課堂教學與大作業(yè)相結合，上機實踐為補充的教學模式，培養(yǎng)學生的創(chuàng)業(yè)創(chuàng)新素質和團隊協(xié)作精神。

二、教師隊伍建設

1．良好的學緣結構

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

2．加強學術交流，不斷提高團隊整體教學和科研水平

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

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

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

3．開展科學研究，積極申請科研立項

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

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

三、教學內容、教材建設

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

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

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

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

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

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

四、教學方法和教學手段

1．教學方法

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

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

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

2．教學手段

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

五、課程建設取得的成果

1．教學科研論文

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

赤峰學院學報2009年1月

2.教研課題

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

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

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

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

數(shù)據(jù)結構課程組 2009年5月14日

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

數(shù)據(jù)結構與算法課程學習總結報告

11計本一班 許雪松 1104013018

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

一、數(shù)據(jù)結構與算法知識點

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

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

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

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

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

第六章“特殊矩陣、廣義表及其應用”將學習數(shù)組、稀疏矩陣和廣義表的基本概念，幾種特殊矩陣的存儲結構及其基本運算，在此基礎上學習特殊矩陣的計算算法與廣義表應用等相關問題。本章的重點是相關數(shù)據(jù)結構的存儲結構及其基本運算算法。掌握了特殊矩陣的壓縮存儲結構，在該存儲結構下元素的定位方法，理解了稀疏矩陣的計算和廣義表的存儲結構。

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

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

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

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

二、對各知識點的掌握情況

我對各知識點的掌握情況總結如下：

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

三、學習體會

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

四、對課程教學的建議

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

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

3、學習的積極性很重要，有時候我們花了很長時間去寫實驗報告，也很認真的去理解去掌握，可是最后實驗報告可能就只得了一個C，抄的人反而得A，這樣的話很容易打擊學生的積極性，在后面的實驗報告中沒動力再去認真寫。所以希望老師能在這方面有所調整。

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

第四篇：《數(shù)據(jù)結構》課程教學大綱

《數(shù)據(jù)結構》課程教學大綱

Data Structure 執(zhí)筆人：

編寫日期：

一、課程基本信息

1.課程編號：

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

3.學時/學分： 48 學時（另實驗16學時）/ 4 學分

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

二、課程教學目標及學生應達到的能力

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

三、課程教學內容與基本要求

（一）緒論（3 學時）1．主要內容：

（1）介紹什么是數(shù)據(jù)結構；

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

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

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

（1）了解學習數(shù)據(jù)結構的重要性；

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

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

（二）線性表（6 學時）1．主要內容：

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

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

（1）掌握線性表的定義和特點；

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

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

3．自學內容：

靜態(tài)鏈表。

（三）棧和隊列（5 學時）1．主要內容：

（1）棧和隊列的結構特性和抽象數(shù)據(jù)類型定義；（2）棧和隊列的順序存儲表示和實現(xiàn)；（3）棧和隊列的鏈式存儲表示和實現(xiàn)；（4）棧和隊列在程序設計中的應用。2．基本要求

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

（2）掌握棧的兩種存儲表示和實現(xiàn)，特別注意棧滿棧空的條件；（3）掌握隊列的兩種存儲表示和實現(xiàn)，特別注意隊滿隊空的條件；（4）了解遞歸算法與棧的關系。3．自學內容：

鏈棧，離散事件模擬

（四）串（3 學時）1．主要內容：

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

（2）串的表示和實現(xiàn): 定長順序存儲結構和堆分配存儲結構；（3）串的各種基本操作的實現(xiàn)及其應用；（4）串的模式匹配操作。2．基本要求

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

串操作的應用實例。

（五）數(shù)組和廣義表（4 學時）1．主要內容：

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

（1）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結構中的地址計算方法；（2）掌握對特殊矩陣進行壓縮存儲時的下標變換公式；

（3）熟悉稀疏矩陣的三元組順序表存儲結構下的一般轉置和快速轉置算法；了解十字鏈表等存儲結構；

（4）掌握廣義表的結構特點、取表頭表尾操作，及其存儲表示方法。3．自學內容：

采用十字鏈表存儲結構創(chuàng)建稀疏矩陣。

（六）樹和二叉樹（10 學時）1．主要內容：

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

（2）二叉樹的抽象數(shù)據(jù)類型定義、性質和存儲結構；（3）二叉樹的遍歷；

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

（5）樹的存儲結構、樹和森林的遍歷以及與二叉樹的轉換；（6）Huffman樹及其應用。2．基本要求

（1）掌握樹型結構的特點和基本術語；

（2）熟練掌握二叉樹的性質，了解相應的證明方法；

（3）了解二叉樹的順序存儲結構和鏈式存儲結構，熟練掌握二叉鏈表存儲結構；（4）熟練掌握二叉樹三種遍歷的遞歸算法和中序遍歷非遞歸算法，能靈活運用遍歷算法實現(xiàn)二叉樹的其他操作；

（5）熟練掌握二叉樹的線索化過程，以及在中序線索二叉樹上找結點的前驅與后繼的方法；

（6）熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉換方法；（7）了解Huffman樹的特性，掌握建立Huffman樹和Huffman編碼的方法。3．自學內容：

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

（七）圖（9 學時）1．主要內容：（1）圖的定義和術語；

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

（5）有向無環(huán)圖及其應用：拓撲排序和關鍵路徑；（6）最短路徑問題。2．基本要求

（1）熟悉圖的定義和術語；

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

（5）了解有向無環(huán)圖、AOV網(wǎng)、AOE網(wǎng)及其在實際中的應用，熟悉拓撲排序算法和關鍵路徑算法；

（6）熟悉兩種最短路徑問題求解算法。3．自學內容：

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

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

（八）查找（4 學時）1．主要內容：

（1）查找的基本概念和相關術語；

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

（1）了解查找的作用，熟悉相關術語；

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

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

平衡二叉樹。

（九）內部排序（4 學時）1．主要內容：

（1）排序的基本概念和相關術語；

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

（1）了解排序作用，熟悉相關術語；

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

3．自學內容：

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

四、教學安排建議

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

2.案例分析

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

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

4.實驗安排

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

建議實驗安排為八次，共16學時，分別如下：

實驗1 線性表的順序存儲結構的實現(xiàn)(2學時)

實驗2 線性表的鏈式存儲結構的實現(xiàn)(2學時)

實驗3 棧的算法實現(xiàn)(2學時)

實驗4 隊列的算法實現(xiàn)(2學時)

實驗5 串類型及操作(2學時)

實驗6 二叉樹的建立與遍歷(2學時)

實驗7 圖的建立與遍歷(2學時)

實驗8 查找與排序(2學時)注：教師可根據(jù)教學實際情況（如：學生情況及學時情況等），適當調整實踐教學內容及學時分配。

五、課程考核

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

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

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

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

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

實驗20%：根據(jù)各次實驗完成情況及實驗報告成績進行評定。

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

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

先行課程：《高級程序設計語言》、《離散數(shù)學》

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

七、建議教材及教學參考書

1.教材：

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

[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結構》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結構簡明教程》，清華大學出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結構與算法》，機械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結構》（C語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結構》，西安電子科技大學出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結構》，大連理工大學出版社，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巴斯《計算機算法：設計和分析引論》朱洪等譯，復旦大學出版社，1985

第五篇：數(shù)據(jù)結構課程教學大綱

數(shù)據(jù)結構課程教學大綱

一、課程基本概況

課程名稱：數(shù)據(jù)結構

課程名稱（英文）： Data Structures

課程編號：B09042

課程總學時：60（其中，講課48，實驗12）

課程學分：3

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

開設學期：4

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

先修課程：集合論，圖論，高級語言（結構或記錄，指針）

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

二、課程的性質、目的和任務

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

三、主要內容、重點及深度

本門課程共60學時，其中理論教學48學時，實驗教學12學時。其中，理論教學部分：

第一章

緒論

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

3.計算語句頻度和估算算法時間復雜度的方法（掌握）。

（三）重點與難點

重點：數(shù)據(jù)結構的定義；算法的描述方法。

難點：數(shù)據(jù)結構的定義；算法與程序的區(qū)別；時間復雜度及其計算。

第二章

線性表

（一）目的要求

掌握線性表的邏輯結構；線性表的存儲結構及操作的實現(xiàn)；理解一元多項式的表示；

（二）教學內容 本章知識點：

1.線性表的邏輯結構(掌握)；2.線性表的存儲結構(掌握)；

3.線性表在順序結構和鏈式結構上實現(xiàn)基本操作的方法(掌握)；

4.從時間和空間復雜度的角度比較線性表兩種存儲結構的不同特點及其適用場合(掌握)。

（三）重點與難點

重點：線性表的概念；線性表的順序存儲結構、鏈式存儲結構及其常用算法。難點：鏈式存儲結構及其常用算法；雙向循環(huán)鏈表。

第三章 棧和隊列

（一）目的要求

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

（二）教學內容 本章知識點： 1.棧和隊列的特點(掌握)；

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

（三）重點與難點

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

第四章 串

（一）目的要求

了解串的邏輯結構，存儲結構；掌握串操作的實現(xiàn)(重點難點BF和KMP算法)串的應用。

（二）教學內容 本章知識點：

1.串的七種基本運算的定義（了解）；

2.利用這些基本運算來實現(xiàn)串的其它各種運算的方法(掌握)； 3.在順序存儲結構上實現(xiàn)串的各種操作的方法(掌握)；

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

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

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

（一）目的要求

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

（二）教學內容 本章知識點：1.數(shù)組在以行為主的存儲結構中的地址計算方法(掌握)； 2.矩陣實現(xiàn)壓縮存儲時的下標變換(掌握)；

3.理解稀疏矩陣的兩種存儲方式的特點和適用范圍，領會以三元組表示稀疏矩陣時進行運算采用的處理方法(掌握)；

4.廣義表的定義及其存儲結構，學會廣義表的表頭，表尾分析方法(掌握)； 5.學習編制廣義表的遞歸算法(掌握)。

（三）重點與難點

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

第六章 樹和二叉樹

（一）目的要求

了解樹的基本概念；理解二叉樹的性質和存儲結構；遍歷二叉樹和線索二叉樹；理解樹的存儲結構和遍歷；集合的一種表示方法；掌握哈夫曼樹及其應用；

（二）教學內容 本章知識點： 1.二叉樹的結構特點(理解)；

2.二叉樹的各種存儲結構的特點及適用范圍(掌握)； 3.按各種次序遍歷二叉樹的遞歸和非遞歸算法(掌握)；

4.二叉樹的線索化，在中序線索樹上找給定結點的前驅和后繼的方法(掌握)； 5.樹的各種存儲結構及其特點(掌握)； 6.編寫樹的各種運算的算法(掌握)；

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

（三）重點與難點 重點：二叉樹的概念、性質；二叉樹的遍歷方式；構造二叉排序樹。難點：二叉樹的遍歷方式；二叉排序樹的構造方法；二叉樹的線索化。

第七章 圖

（一）目的要求

理解圖的基本概念；圖的存儲結構；掌握圖的遍歷及應用{最小生成樹，最短路徑等}；拓撲排序和關鍵路徑。

（二）教學內容 本章知識點： 1.熟悉圖的各種存儲結構；

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

4.應用圖的遍歷算法求各種簡單路徑問題（比如，最小生成樹、最短路徑、拓撲排序、關鍵路徑等）(掌握)。

（三）重點與難點

重點：圖的存儲結構；圖的遍歷 難點：圖遍歷的算法；

第八章

動態(tài)存儲管理

（一）目的要求

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

（二）教學內容 本章知識點：

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

2.無用單元收集時的標志算法（了解）。

（三）重點與難點

存儲器分配策略和算法、無用單元收集時的標志算法

第九章

查找

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

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

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

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

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

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

（三）重點與難點

重點：二叉排序樹的構造方法、二叉平衡樹的建立方法；哈希表的構造、應用；

難點：二叉排序樹的構造及應用；哈希表的構造方法；查找的平均長度。

第十章

內部排序

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

（三）重點與難點

重點：各種排序方法的特點及其應用；實現(xiàn)排序的各種算法。難點：各種排序算法的時間復雜度分析。

十一章

外部排序

（一）目的要求

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

（二）教學內容 本章知識點：

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

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

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

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

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

6.最佳歸并樹的構造方法（熟悉）；

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

（三）重點與難點

重點：外部排序過程和實現(xiàn)方法；多路并歸算法及其實現(xiàn)； 難點：最佳并歸樹的構造方法及其應用。

實踐教學部分：上機實驗分4個專題，每個專題可提供2~4個難度不等的題目供選。

實驗一

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

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

（二）實驗過程 編程實現(xiàn)實驗內容。

（三）實驗教學基本要求

通過實例，使學生掌握棧和隊列兩種特殊的線性結構，掌握棧和隊列的特點。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 4學時

實驗二

教學計劃編制問題

（一）實驗內容

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

（二）實驗過程編程實現(xiàn)實驗內容。

（三）實驗教學基本要求

通過實例，使學生熟悉圖的各種存儲結構的特性，掌握如何應用圖結構解決具體問題。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 2學時

實驗三

最小生成樹問題

（一）實驗內容

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

（二）實驗過程 編程實現(xiàn)實驗內容

（三）實驗教學基本要求

通過實例，使學生熟悉圖的各種存儲結構的特性，掌握如何應用圖結構解決具體問題。實驗后學生提交實驗報告。

（四）實驗設備和材料 計算機。

（五）實驗學時 2學時

實驗四

哈希表設計

（一）實驗內容

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

（二）實驗過程 編程實現(xiàn)實驗內容

（三）實驗教學基本要求 掌握索引技術的使用。

（四）實驗設備和材料 計算機

（五）實驗學時 4學時

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

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

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

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

先修課包括：集合論，圖論，高級語言（結構或記錄，指針）；

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

七、建議教材與參考教材

《數(shù)據(jù)結構》（C語言版）

嚴蔚敏等

清華大學出版社

1997 《數(shù)據(jù)結構題集》

嚴蔚敏等

清華大學出版社

1999

《數(shù)據(jù)結構習題與解析》

李春葆

清華大學出版社

2004

八、負責人

撰稿人：劉景匯、李玉香

審稿人：

系（院）領導：