數(shù)據(jù)結(jié)構(gòu)課程總結(jié)
數(shù)據(jù)：能夠被計算機(jī)識別、存儲和加工處理的信息的載體。
數(shù)據(jù)元素：數(shù)據(jù)的基本單位，可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是具有獨(dú)立含義的最小標(biāo)識單位。數(shù)據(jù)結(jié)構(gòu)的定義：
邏輯結(jié)構(gòu)：從邏輯結(jié)構(gòu)上描述數(shù)據(jù)，獨(dú)立于計算機(jī)。線性結(jié)構(gòu)：一對一關(guān)系。線性結(jié)構(gòu)：多對多關(guān)系。
存儲結(jié)構(gòu)：是邏輯結(jié)構(gòu)用計算機(jī)語言的實現(xiàn)。順序存儲結(jié)構(gòu)：如數(shù)組。鏈?zhǔn)酱鎯Y(jié)構(gòu)：如鏈表。索引結(jié)構(gòu)：索引表。散列存儲結(jié)構(gòu)：如散列表。
對數(shù)據(jù)的操作：定義在邏輯結(jié)構(gòu)上，每種邏輯結(jié)構(gòu)都有一個運(yùn)算集合。常用的有：檢索、插入、刪除、更新、排序。
數(shù)據(jù)類型：是一個值的集合以及在這些值上定義的一組操作的總稱。原子類型：簡單類型，由語言提供。結(jié)構(gòu)類型：由用戶借助于描述機(jī)制定義，是導(dǎo)出類型。
程序設(shè)計的實質(zhì)是對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，設(shè)計一個好的算法。算法取決于數(shù)據(jù)結(jié)構(gòu)。算法是一個自定義的計算過程，以一個或多個值輸入，并以一個或多個值輸出。
評價算法的好壞的因素：算法是正確的;執(zhí)行算法的時間;執(zhí)行算法的存儲空間;算法易于理解、編碼、調(diào)試。
時間復(fù)雜度：是某個算法的時間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)。漸近時間復(fù)雜度：是指當(dāng)問題規(guī)模趨向無窮大時，該算法時間復(fù)雜度的數(shù)量級。評價一個算法的時間性能時，主要標(biāo)準(zhǔn)就是算法的漸近時間復(fù)雜度。
算法中語句的頻度不僅與問題規(guī)模有關(guān)，還與輸入實例中各元素的取值相關(guān)。
時間復(fù)雜度按數(shù)量級遞增排列依次為：常數(shù)階、對數(shù)階、線性階、線性對數(shù)階、平方階、立方階、……k次方階、指數(shù)階。空間復(fù)雜度：是某個算法的空間耗費(fèi)，它是該算法所求解問題規(guī)模n的函數(shù)。算法的時間復(fù)雜度和空間復(fù)雜度合稱算法復(fù)雜度。
線性表是由n≥0個數(shù)據(jù)元素組成的有限序列。n=0是空表;非空表，只能有一個開始結(jié)點，有且只能有一個終端結(jié)點。
線性表上定義的基本運(yùn)算：構(gòu)造空表：Initlist；求表長：Listlength；取結(jié)點：GetNode；查找：LocateNode；插入：InsertList；刪除：Delete。
順序表是按線性表的邏輯結(jié)構(gòu)次序依次存放在一組地址連續(xù)的存儲單元中。在存儲單元中的各元素的物理位置和邏輯結(jié)構(gòu)中各結(jié)點相鄰關(guān)系是一致的。地址計算：？
在順序表中實現(xiàn)的基本運(yùn)算：插入：平均移動結(jié)點次數(shù)為？;平均時間復(fù)雜度均為？。刪除：平均移動結(jié)點次數(shù)為？;平均時間復(fù)雜度均為？。
線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中結(jié)點的邏輯次序和物理次序不一定相同，為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還存儲了其后繼結(jié)點的地址信息。這兩部分信息組成鏈表中的結(jié)點結(jié)構(gòu)。一個單鏈表由頭指針的名字來命名。
單鏈表運(yùn)算：建立單鏈表（頭插法：生成的順序與輸入順序相反。平均時間復(fù)雜度均為？。尾插法：平均時間復(fù)雜度均為？。加頭結(jié)點的算法：對開始結(jié)點的操作無需特殊處理，統(tǒng)一了空表和非空表。查找（按序號：與查找位置有關(guān)，平均時間復(fù)雜度均為？。按值：與輸入實例有關(guān)，平均時間復(fù)雜度均為。插入運(yùn)算：p=GetNode;s-next=p-next;p-next=s;平均時間復(fù)雜度均為？，刪除運(yùn)算：平均時間復(fù)雜度均為？）
單循環(huán)鏈表是一種首尾相接的單鏈表，終端結(jié)點的指針域指向開始結(jié)點或頭結(jié)點。鏈表終止條件是以指針等于頭指針或尾指針。采用單循環(huán)鏈表在實用中多采用尾指針表示單循環(huán)鏈表。優(yōu)點是查找頭指針和尾指針的時間都是O？，不用遍歷整個鏈表。
雙鏈表就是雙向鏈表，就是在單鏈表的每個結(jié)點里再增加一個指向其直接前趨的指針域prior，形成兩條不同方向的鏈。由頭指針head惟一確定。雙鏈表也可以頭尾相構(gòu)成雙循環(huán)鏈表。雙鏈表上的插入和刪除時間復(fù)雜度均為O？。
順序表和鏈表的比較：
基于空間：順序表的存儲空間是靜態(tài)分配，存儲密度為1;適于線性表事先確定其大小時采用。鏈表的存儲空間是動態(tài)分配，存儲密度1;適于線性表長度變化大時采用。
基于時間：順序表是隨機(jī)存儲結(jié)構(gòu)，當(dāng)線性表的操作主要是查找時，宜采用。以插入和刪除操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。
棧是僅限制在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，稱插入、刪除這一端為棧頂，另一端稱為棧底。表中無元素時為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的，我們又稱棧為LIFO表。通常棧有順序棧和鏈棧兩種存儲結(jié)構(gòu)。
棧的基本運(yùn)算有六種：構(gòu)造空棧：InitStack，判�？眨篠tackEmpty，判棧滿：StackFull，進(jìn)棧：Push，退棧：Pop，取棧頂元素：StackTop
在順序棧中有“上溢”和“下溢”的現(xiàn)象。“上溢”是棧頂指針指出棧的外面是出錯狀態(tài)。“下溢”可以表示棧為空棧，因此用來作為控制轉(zhuǎn)移的條件。
順序棧中的基本操作有六種：構(gòu)造空棧，判�？眨袟M，進(jìn)棧，退棧，取棧頂元素
鏈棧則沒有上溢的限制，因此進(jìn)棧不要判棧滿。鏈棧不需要在頭部附加頭結(jié)點，只要有鏈表的頭指針就可以了。鏈棧中的基本操作有五種：構(gòu)造空棧，判棧空，進(jìn)棧，退棧，取棧頂元素
隊列是一種運(yùn)算受限的線性表，插入在表的一端進(jìn)行，而刪除在表的另一端進(jìn)行，允許刪除的一端稱為隊頭，允許插入的一端稱為隊尾，隊列的操作原則是先進(jìn)先出的，又稱作FIFO表.隊列也有順序存儲和鏈?zhǔn)酱鎯煞N存儲結(jié)構(gòu)。
隊列的基本運(yùn)算有六種：置空隊：InitQueue，判隊空：QueueEmpty，判隊滿：QueueFull，入隊：EnQueue，出隊：DeQueue，取隊頭元素：QueueFront
順序隊列的“假上溢”現(xiàn)象：由于頭尾指針不斷前移，超出向量空間。這時整個向量空間及隊列是空的卻產(chǎn)生了“上溢”現(xiàn)象。為了克服“假上溢”現(xiàn)象引入循環(huán)向量的概念，是把向量空間形成一個頭尾相接的環(huán)形，這時隊列稱循環(huán)隊列。
判定循環(huán)隊列是空還是滿，方法有三種：一種是另設(shè)一個布爾變量來判斷;第二種是少用一個元素空間，入隊時先測試%m=front)?滿：空;第三種就是用一個計數(shù)器記錄隊列中的元素的總數(shù)。隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為鏈隊列，一個鏈隊列就是一個操作受限的單鏈表。為了便于在表尾進(jìn)行插入的操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地確定。鏈隊列不存在隊滿和上溢的問題。在鏈隊列的出隊算法中，要注意當(dāng)原隊中只有一個結(jié)點時，出隊后要同進(jìn)修改頭尾指針并使隊列變空。
串是零個或多個字符組成的有限序列。
概念空串：是指長度為零的串，也就是串中不包含任何字符。空白串：指串中包含一個或多個空格字符的串。在一個串中任意個連續(xù)字符組成的子序列稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現(xiàn)的位置�？沾侨我獯淖哟�，任意串是自身的子串。
串分為兩種：串常量在程序中只能引用不能改變;串變量的值可以改變。
串的基本運(yùn)算有：求串長strlen，串復(fù)制strcpy，串聯(lián)接strcat，串比較charcmp，字符定位strchr。串是特殊的線性表，所以串的存儲結(jié)構(gòu)與線性表的存儲結(jié)構(gòu)類似。串的順序存儲結(jié)構(gòu)簡稱為順序串。
順序串又可按存儲分配的不同分為：靜態(tài)存儲分配：直接用定長的字符數(shù)組來定義。優(yōu)點是涉及串長的操作速度快，但不適合插入、操作。動態(tài)存儲分配：是在定義串時不分配存儲空間，需要使用時按所需串的長度分配存儲單元。
串的鏈?zhǔn)酱鎯褪怯脝捂湵淼姆绞酱鎯Υ�，串的這種鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈串。鏈串與單鏈表的差異只是它的結(jié)點數(shù)據(jù)域為單個字符。為了解決“存儲密度”低的狀況，可以讓一個結(jié)點存儲多個字符，即結(jié)點的大小。
順序串上子串定位的運(yùn)算：又稱串的“模式匹配”或“串匹配”，是在主串中查找出子串出現(xiàn)的位置。在串匹配中，將主串稱為目標(biāo)，子串稱為模式。這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標(biāo)串T中首次出現(xiàn)的有效位移或者是全部有效位移。最壞的情況下時間復(fù)雜度是Om)，假如m與n同階的話則它是O。鏈串上的子串定位運(yùn)算位移是結(jié)點地址而不是整數(shù)。
數(shù)組一般用順序存儲的方式表示。
存儲的方式有：行優(yōu)先順序，也就是把數(shù)組逐行依次排列。PASCAL、C。列優(yōu)先順序，就是把數(shù)組逐列依次排列。FORTRAN地址的計算方法：按行優(yōu)先順序排列的數(shù)組：LOC（a）=？.。按列優(yōu)先順序排列的數(shù)組：LOC（a）=？.矩陣的壓縮存儲：為多個相同的非零元素分配一個存儲空間;對零元素不分配空間。
特殊矩陣的概念：所謂特殊矩陣是指非零元素或零元素分布有一定規(guī)律的矩陣。
稀疏矩陣的概念：一個矩陣中若其非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個數(shù)，則該矩陣稱為稀疏矩陣。特殊矩陣的類型：對稱矩陣：三角矩陣：上三角陣,下三角陣,對角矩陣k=f(I,j)，
廣義表是n個元素的有限序列，其中的元素是原子或者是一個廣義表。廣義表表頭和表尾的概念：廣義表有兩種表示法，一種是括號表示法，一種是圖形表示法。
廣義表有兩個特殊的基本運(yùn)算：取表頭head：取表中的第一個數(shù)據(jù)元素，不能對空表操作。取表尾tail;取除表頭外，其余數(shù)據(jù)元素構(gòu)成的子表，不能對空表操作
樹是n個結(jié)點的有限集合，非空時必須滿足：只有一個稱為根的結(jié)點;其余結(jié)點形成m個不相交的子集，并稱根的子樹。根是開始結(jié)點;結(jié)點的子樹數(shù)稱度;度為0的結(jié)點稱葉子;度不為0的結(jié)點稱分支結(jié)點;除根外的分支結(jié)點稱內(nèi)部結(jié)點;
有序樹是子樹有左，右之分的樹;無序樹是子樹沒有左，右之分的樹;森林是m個互不相交的樹的集合;樹的四種不同表示方法：樹形表示法;嵌套集合表示法;凹入表示法;廣義表表示法。
二叉樹的定義：是n≥0個結(jié)點的有限集，它是空集或由一個根結(jié)點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成。二叉樹不是樹的特殊情形，與度數(shù)為2的有序樹不同。二叉樹的4個重要性質(zhì)：
二叉樹的順序存儲結(jié)構(gòu)就是把二叉樹的所有結(jié)點按照層次順序存儲到連續(xù)的存儲單元中。
樹的存儲結(jié)構(gòu)多用的是鏈?zhǔn)酱鎯�。二叉樹的鏈�(zhǔn)酱鎯Y(jié)構(gòu)，稱為二叉鏈表。它就是由根指針root唯一確定的。共有2n個指針域，n+1個空指針。
根據(jù)結(jié)點的次序不同可得三種遍歷：先序遍歷，中序遍歷、后序遍歷。時間復(fù)雜度為。
利用二叉鏈表中的n+1個空指針域來存放指向某種遍歷次序下的前趨結(jié)點和后繼結(jié)點的指針，這些附加的指針就稱為“線索”，加上線索的二叉鏈表就稱為線索鏈表。線索使得查找中序前趨和中序后繼變得簡單有效，但對于查找指定結(jié)點的前序前趨和后序后繼并沒有什么作用。
樹和森林及二叉樹的轉(zhuǎn)換是唯一對應(yīng)的。二叉樹變樹：結(jié)點的右孩子與其雙親連。森林變二叉樹：樹變二叉樹，各個樹的根相連。轉(zhuǎn)換方法?
樹的存儲結(jié)構(gòu)：有雙親鏈表表示法：孩子鏈表表示法：雙親孩子鏈表表示法：孩子兄弟鏈表表示法：樹的前序遍歷與相對應(yīng)的二叉樹的前序遍歷一致;樹的后序遍歷與相對應(yīng)的二叉樹的中序遍歷一致。樹的帶權(quán)路徑長度?最優(yōu)二叉樹?完全二叉樹?哈夫曼樹及其性質(zhì)，
變長編碼技術(shù)可以使頻度高的字符編碼短，而頻度低的字符編碼長，但是變長編碼可能使解碼產(chǎn)生二義性。如00、01、0001這三個碼無法在解碼時確定是哪一個，所以要求在字符編碼時任一字符的編碼都不是其他字符編碼的前綴，這種碼稱為前綴碼。哈夫曼樹的應(yīng)用。
圖的邏輯結(jié)構(gòu)特征就是其結(jié)點的前趨和后繼的個數(shù)都是沒有限制的，即任意兩個結(jié)點之間之間都可能相關(guān)。圖，有向圖，無向圖，簡單路徑,簡單回路,網(wǎng)絡(luò)等及其性質(zhì)。
圖的存儲結(jié)構(gòu)：鄰接矩陣表示法：適合稠密圖。無向鄰接矩陣是對稱的。有向行是出度，列是入度。建立鄰接矩陣算法的時間是O，其時間復(fù)雜度為O。鄰接表表示法：適合稀疏圖。時間復(fù)雜度為O，空間復(fù)雜度為O。
圖的遍歷：深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已結(jié)點。廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊列保存已結(jié)點。
生成樹的定義：最小生成樹：Prim算法的時間復(fù)雜度為O與邊數(shù)無關(guān)適于稠密圖。Kruskal算法的時間復(fù)雜度為O，主要取決于邊數(shù)，較適合于稀疏圖。
最短路徑的算法：Dijkstra算法，時間復(fù)雜度為O。
拓?fù)渑判颍簾o前趨的頂點優(yōu)先：每次輸出一個無前趨的結(jié)點并刪去此結(jié)點及其出邊，最后得到的序列即拓?fù)湫蛄�。無后繼的結(jié)點優(yōu)先：每次輸出一個無后繼的結(jié)點并刪去此結(jié)點及其入邊，最后得到的序列是逆拓?fù)湫蛄小?/p>
關(guān)于排序
關(guān)鍵字項，關(guān)鍵字。
排序是使文件中的記錄按關(guān)鍵字遞增次序排列起來。
基本操作：比較關(guān)鍵字大小;改變指向記錄的指針或移動記錄。
存儲結(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)部排序方法可分五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。
評價排序算法好壞的標(biāo)準(zhǔn)主要有兩條：執(zhí)行時間和所需的輔助空間，另外算法的復(fù)雜程序也是要考慮的一個因素。
插入排序：直接插入排序;逐個向前插入到合適位置;哨兵有兩個作用;作為臨變量存放R[i];是在查找循環(huán)中用來監(jiān)視下標(biāo)變量j是否越界;直接插入排序是穩(wěn)定排序。時間復(fù)雜度為O？比較次數(shù)為/2;移動次數(shù)為？。希爾排序：等間隔的數(shù)據(jù)比較并按要求順序排列，最后間隔為1;希爾排序是就地的不穩(wěn)定排序。時間復(fù)雜度為O，比較次數(shù)為;移動次數(shù)為;
交換排序：冒泡排序：自下向上確定最輕的一個。自上向下確定最重的一個。冒泡排序是就地的穩(wěn)定排序。時間復(fù)雜度為O？比較次數(shù)為？;移動次數(shù)為？;快速排序：以第一個元素為參考基準(zhǔn)，設(shè)定、動兩個指針，發(fā)生交換后指針交換位置，直到指針重合。重復(fù)直到排序完成。快速排序是不穩(wěn)定排序。時間復(fù)雜度為O？比較次數(shù)為？。
選擇排序：直接選擇排序;選擇最小的放在比較區(qū)前;直接選擇排序不穩(wěn)定排序。時間復(fù)雜度為O？。比較次數(shù)為？。堆排序：建堆：按層次將數(shù)據(jù)填入完全二叉樹，從int處向前逐個調(diào)整位置。然后將樹根與最后一個葉子交換值并斷開與樹的連接并重建堆，直到全斷開。堆排序是就地不穩(wěn)定的排序，時間復(fù)雜度為O，不適宜于記錄數(shù)較少的文件。
歸并排序：先兩個一組排序，形成/2組，再將兩組并一組，直到剩下一組為止。歸并排序是非穩(wěn)定排序，時間復(fù)雜度是O？基數(shù)排序：從低位到高位依次對關(guān)鍵字進(jìn)行箱排序�；鶖�(shù)排序是非就穩(wěn)定的排序，時間復(fù)雜度是O？。各種排序方法的比較和選擇：
1、待排序的記錄數(shù)目n;n較大的要用時間復(fù)雜度為O的排序方法;
2、記錄的大小;記錄大最好用鏈表作為存儲結(jié)構(gòu)，而快速排序和堆排序在鏈表上難于實現(xiàn);3、關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài);4、對穩(wěn)定性的要求;5、語言工具的條件;
6、存儲結(jié)構(gòu);時間和輔助空間復(fù)雜度。關(guān)于查找
查找的同時對表做修改操作則相應(yīng)的表稱之為動態(tài)查找表，否則稱之為靜態(tài)查找表。衡量查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是在查找過程中對關(guān)鍵字需要執(zhí)行的平均比較次數(shù)。線性表查找的方法：順序查找：逐個查找，ASL=？;二分查找：取中點int比較，若小就比左區(qū)間，大就比右區(qū)間。用二叉判定樹表示。ASL=？;分塊查找：要求“分塊有序”，將表分成若干塊內(nèi)部不一定有序，并抽取各塊中的最大關(guān)鍵字及其位置建立有序索引表。
二叉排序樹定義是二叉排序樹是空樹或者滿足如下性質(zhì)的二叉樹：若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值;若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值;左、右子樹本身又是一棵二叉排序樹。
二叉排序樹的插入、建立、刪除的算法平均時間性能是O？。
二叉排序樹的刪除操作可分三種情況進(jìn)行處理：*P是葉子，則直接刪除*P，即將*P的雙親*parent中指向*P的指針域置空即可。*P只有一個孩子*child，此時只需將*child和*p的雙親直接連接就可刪去*p。*p有兩個孩子，則先將*p結(jié)點的中序后繼結(jié)點的數(shù)據(jù)到*p，刪除中序后繼結(jié)點。
關(guān)于B-樹。它適合在磁盤等直接存取設(shè)備上組織動態(tài)的查找表，是一種外查找算法。建立的方式是從下向上拱起。
散列技術(shù)：將結(jié)點按其關(guān)鍵字的散列地址存儲到散列表的過程稱為散列。散列函數(shù)的選擇有兩條標(biāo)準(zhǔn)：簡單和均勻。常見的散列函數(shù)構(gòu)的造方法：平方取中法,除余法,相乘取整法,隨機(jī)數(shù)法。
處理沖突的方法：開放定址法：一般形式為?，開放定址法要求散列表的裝填因子α≤1。開放定址法類型：線性探查法，二次探查法，雙重散列法。拉鏈法：是將所有關(guān)鍵字為同義詞的結(jié)點在同一個單鏈表中。
拉鏈法的優(yōu)點：拉鏈法處理沖突簡單，且無堆積現(xiàn)象;鏈表上的結(jié)點空間是動態(tài)申請的適于無法確定表長的情況;拉鏈法中α可以大于1，結(jié)點較大時其指針域可忽略，因此節(jié)省空間;拉鏈法構(gòu)造的散列表刪除結(jié)點易實現(xiàn)。
拉鏈法也有缺點：當(dāng)結(jié)點規(guī)模較小時，用拉鏈法中的指針域也要占用額外空間，還是開放定址法省空間。
擴(kuò)展閱讀：“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)
“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)
計算機(jī)科學(xué)與技術(shù)專業(yè)從1994年開始為我校�？粕_設(shè)“數(shù)據(jù)結(jié)構(gòu)”課程，201*年開始為本科生開設(shè)這門課程。由于本門課程的教學(xué)從教材、講授、實驗指導(dǎo)都體現(xiàn)了先進(jìn)的教育理念，該課程的教學(xué)體系科學(xué)、完整，教學(xué)手段與方法先進(jìn)，課程特色鮮明，201*年被評為赤峰學(xué)院本科層次精品課。幾年來，數(shù)據(jù)結(jié)構(gòu)課題組成員從以下幾個方面對本門課程進(jìn)行了建設(shè)和改革。一、課程建設(shè)指導(dǎo)思想、定位和特色1．學(xué)科地位
“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)科學(xué)與技術(shù)專業(yè)的一門學(xué)科基礎(chǔ)課，是本專業(yè)和相關(guān)專業(yè)必修課。本課程的教學(xué)目標(biāo)是培養(yǎng)學(xué)生通過理解、分析和研究計算機(jī)處理的數(shù)據(jù)對象的特性，從而選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)的算法，并熟練掌握算法的時間分析和空間分析技巧�！皵�(shù)據(jù)結(jié)構(gòu)”還是計算機(jī)科學(xué)與技術(shù)專業(yè)部分專業(yè)課的先導(dǎo)課，如“數(shù)據(jù)庫原理與應(yīng)用”、“計算機(jī)操作系統(tǒng)”、“計算機(jī)編譯原理”和“面向?qū)ο蟮某绦蛟O(shè)計”等。所以本課程的教學(xué)效果將直接影響到學(xué)生對其它后續(xù)專業(yè)課的學(xué)習(xí)，因此，該課程在專業(yè)建設(shè)的地位十分重要。
“數(shù)據(jù)結(jié)構(gòu)”是一門應(yīng)用性很強(qiáng)的課程，本課程要求學(xué)生在掌握各種數(shù)據(jù)結(jié)構(gòu)，特別是存儲結(jié)構(gòu)和有關(guān)算法的基礎(chǔ)上，通過大量的上機(jī)實例把難以理解的、抽象的概念轉(zhuǎn)化為計算機(jī)能夠正確運(yùn)行的程序，從而提高學(xué)生運(yùn)用所學(xué)知識解決實際問題的能力。2．課程特色
根據(jù)課程建設(shè)的規(guī)劃和我系實際，我們針對《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)開展討論，并就實驗、圖書資料等方面進(jìn)行建設(shè)。在不斷的教學(xué)實踐中，我們按照精品課建設(shè)要求，積極探索，積累了豐富的教學(xué)經(jīng)驗。
采用國內(nèi)經(jīng)典教材，結(jié)合前沿的研究領(lǐng)域和最新科研動態(tài)，豐富教學(xué)內(nèi)容，讓學(xué)生了解數(shù)據(jù)結(jié)構(gòu)的實際應(yīng)用價值。
采用課堂教學(xué)與大作業(yè)相結(jié)合，上機(jī)實踐為補(bǔ)充的教學(xué)模式，培養(yǎng)學(xué)生的創(chuàng)業(yè)創(chuàng)新素質(zhì)和團(tuán)隊協(xié)作精神。二、教師隊伍建設(shè)
1．良好的學(xué)緣結(jié)構(gòu)
任課教師的業(yè)務(wù)水平和教學(xué)水平是影響課程建設(shè)質(zhì)量的重要因素。為此，我們不斷加強(qiáng)師資隊伍建設(shè)，特別注重青年教師和實驗指導(dǎo)教師的培養(yǎng)。在擔(dān)任該課程教學(xué)任務(wù)的5名教師中，教授1名、副教授2名、講師2名，學(xué)歷結(jié)構(gòu)為碩士4人、學(xué)士1人，45歲以下3人，35歲以下2人。本教師梯隊學(xué)歷層次較高，職稱、年齡結(jié)構(gòu)合理，便于本門課程的建設(shè)和發(fā)展。
2．加強(qiáng)學(xué)術(shù)交流，不斷提高團(tuán)隊整體教學(xué)和科研水平
在教學(xué)過程中，我們采取了互相聽課，舉行公開課、觀摩課等方式，經(jīng)常交流教書育人和教學(xué)改革方面的經(jīng)驗，不斷提高任課教師的教學(xué)水平和學(xué)術(shù)水平。
以范體貴教授為學(xué)科帶頭人的教學(xué)研究梯隊，具有豐富的教學(xué)經(jīng)驗和高昂的教學(xué)熱情，同時具備較高的教學(xué)研究和科學(xué)研究水平。教學(xué)梯隊成員在搞好教學(xué)的同時，積極申報承擔(dān)各級各類教學(xué)研究和科學(xué)研究課題，并參加國內(nèi)外相關(guān)學(xué)科的科研、教學(xué)等方面的學(xué)術(shù)交流活動。選派范體貴、門愛華兩位老師參加全國計算機(jī)年會和全國數(shù)據(jù)庫學(xué)術(shù)會議，與國內(nèi)其他高校著名學(xué)者進(jìn)行了教學(xué)、科研等方面的交流，學(xué)到許多寶貴的經(jīng)驗和方法。
注重與其他高校的合作和交流，學(xué)習(xí)其他院校好的教學(xué)經(jīng)驗和方法。選派主講教師門愛華老師到清華大學(xué)計算機(jī)系做訪問學(xué)者，訪學(xué)期間門老師聽取了本課程的講授，經(jīng)常與講授本門課程的資深教授嚴(yán)蔚敏老師、殷仁昆老師進(jìn)行交流、學(xué)習(xí)。二位老師都給予了具體的指導(dǎo)和建議，為我校本門課程的改革和發(fā)展提供了有利的幫助。請國內(nèi)著名高校學(xué)者來我系講學(xué)傳授經(jīng)驗，在教學(xué)、科研等方面給予具體的指導(dǎo)。201*年10月清華大學(xué)著名數(shù)據(jù)庫專家馮建華教授來我系講學(xué)，課題組成員與馮教授進(jìn)行了深入的交流，在教學(xué)和科研方面都有很大的收獲。
3．開展科學(xué)研究，積極申請科研立項
數(shù)據(jù)結(jié)構(gòu)課題小組成員積極進(jìn)行相關(guān)領(lǐng)域的科學(xué)研究，幾年來發(fā)表相關(guān)論文30余篇，承擔(dān)自治區(qū)級科研項目四個，赤峰市科技局科研項目一個，院級項目一個，其中3個項目已經(jīng)完成并通過驗收。目前在研的一個科研項目是與清華大學(xué)合作申請的計算機(jī)前沿領(lǐng)域研究課題，相信通過該項目的研究和合作，對我系的科研工作會起到極大的促進(jìn)作用，同時能夠使我系科研水平上一個新的臺階。課題組成員經(jīng)過幾年的努力，在各方面都取得了一些成績。范體貴、門愛華、張國祥、王玉紅四位教師分別獲得“赤峰學(xué)院課堂教學(xué)質(zhì)量優(yōu)秀獎”，范體貴、門愛華兩位教師多次獲得“赤峰學(xué)院科研成果優(yōu)秀獎”的獎勵。王玉紅老師獲得“畢業(yè)實習(xí)優(yōu)秀指導(dǎo)教師“稱號，門愛華老師201*年、201*年連續(xù)獲得“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎勵。
建立了良好的人才培養(yǎng)制度，在學(xué)校和系里的大力支持下，鼓勵現(xiàn)有教師提高學(xué)歷與引進(jìn)高學(xué)歷教師相結(jié)合，經(jīng)過幾年的建設(shè)，已經(jīng)形成了一支以中青年為主的學(xué)科梯隊。積極鼓勵中青年教師到國內(nèi)名校進(jìn)修或攻讀碩士、博士學(xué)位，門愛華、董潔、王玉紅分別考取了東北大學(xué)和遼寧工程技術(shù)大學(xué)的碩士研究生，已圓滿完成學(xué)業(yè)并獲得碩士學(xué)位。三、教學(xué)內(nèi)容、教材建設(shè)
1．理論環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時分配
“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)科學(xué)課程體系中核心課程之首，作為學(xué)科的專業(yè)基礎(chǔ)課，具有承上啟下的重要作用。對應(yīng)于學(xué)科中問題求解的理論、抽象和設(shè)計的方法論，本課程內(nèi)容體系結(jié)構(gòu)分為概念表述、構(gòu)建數(shù)據(jù)模型、設(shè)計算法三個層面，突出數(shù)據(jù)組織方法與處理技術(shù)，貫穿程序設(shè)計和軟件工程新思想和新觀點。理論學(xué)時設(shè)置為72學(xué)時。
2.實踐環(huán)節(jié)教學(xué)內(nèi)容及學(xué)時分配
上機(jī)實踐和課程設(shè)計重在培養(yǎng)學(xué)生軟件設(shè)計的綜合能力。在基本的課程實習(xí)基礎(chǔ)上,自201*年起開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，使課程的實踐環(huán)節(jié)總學(xué)時數(shù)增加到60學(xué)時。提出了課程設(shè)計的規(guī)范要求，突出關(guān)鍵技術(shù)要點，貫穿基本技能訓(xùn)練主線，加強(qiáng)實踐能力培養(yǎng)。
通過課程設(shè)計的訓(xùn)練，突出構(gòu)造性思維訓(xùn)練的特征，提高了學(xué)生組織數(shù)據(jù)與進(jìn)行編寫大型程序能力，使學(xué)生更好地理解和掌握了算法設(shè)計所需的技術(shù)，為專業(yè)學(xué)習(xí)打下良好的基礎(chǔ)。課程設(shè)計題目（動態(tài)更新、完善）：航空客運(yùn)訂票系統(tǒng)；電梯模擬；簡單行編輯程序；工資管理系統(tǒng)；醫(yī)院排隊看病活動的模擬；學(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ī)科學(xué)與技術(shù)、信息與計算科學(xué)專業(yè)學(xué)生的需要。任課教師則多方面參考相關(guān)教材，選擇部分編寫精彩的內(nèi)容充實到教案中。任課教師們廣泛閱讀相關(guān)文獻(xiàn)，了解該領(lǐng)域前沿知識，并且在授課過程中介紹給學(xué)生，以開闊學(xué)生的視野，拓寬學(xué)生的知識面。同時，根據(jù)教材內(nèi)容和實際教學(xué)要求，編寫了《數(shù)據(jù)結(jié)構(gòu)上機(jī)指導(dǎo)與習(xí)題就解答》，并正式出版了《數(shù)據(jù)結(jié)構(gòu)實驗教程》一書，該書作為自治區(qū)教育廳統(tǒng)編教材已在各高校廣泛使用。四、教學(xué)方法和教學(xué)手段
1．教學(xué)方法
在教學(xué)方法上，講課、討論和專題講座等多種形式并用，以科學(xué)、生動靈活的講授方式傳授知識，培養(yǎng)學(xué)生的創(chuàng)造思維。教師在認(rèn)真組織課堂講授，注意各環(huán)節(jié)正常運(yùn)行的同時，還針對不同的教學(xué)內(nèi)容采取不同的方法進(jìn)行講解，做到課程內(nèi)容既條理清晰、深入淺出，又重點突出、特色鮮明。教學(xué)內(nèi)容靈活，既有必講的內(nèi)容，也有針對不同專業(yè)需要和特點選講的內(nèi)容。
通過布置適量的課后習(xí)題，使學(xué)生能夠進(jìn)一步鞏固和提高對課上所學(xué)知識的領(lǐng)悟和應(yīng)用能力。我們在選擇習(xí)題時，一方面注重三基（基本理論，基本方法，基本技能）知識的掌握，另一方面也充分考慮知識的靈活應(yīng)用，使學(xué)生能多角度、多方法地解決問題，既鍛煉他們的系統(tǒng)性思維，又提高分析解決問題的能力。每兩周安排一次習(xí)題課，由指導(dǎo)教師集中解決同學(xué)課上課下遇到的問題。
上機(jī)實踐是學(xué)生對本門課程所學(xué)知識的一種全面、綜合的能力訓(xùn)練，是與課堂聽講、自學(xué)和練習(xí)相輔相成必不可少的一個教學(xué)環(huán)節(jié)，也是對課堂教學(xué)效果的一種檢驗。通常，實習(xí)題中的問題比平時的習(xí)題復(fù)雜得多，也更接近實際。實習(xí)題注重原理與應(yīng)用的結(jié)合，目的讓學(xué)生學(xué)會如何把書上學(xué)到的知識運(yùn)用于解決實際問題的過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計工作所必需的基本技能。同時，通過實踐能使書上的知識變“活”，起到深化理解和靈活掌握教學(xué)內(nèi)容的作用。平時的練習(xí)較偏重于如何編寫功能單一的“小”算法，而實習(xí)題是軟件設(shè)計的綜合訓(xùn)練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧，可以多人合作，有利于一整套軟件工程規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。此外，實踐環(huán)節(jié)中有很重要的一點，就是機(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)輔之以形象的動畫，動態(tài)演示抽象的復(fù)雜數(shù)據(jù)結(jié)構(gòu)的變化，用板書補(bǔ)充某些推導(dǎo)過程并完成和學(xué)生互動的內(nèi)容，改變了以前課堂教學(xué)單調(diào)的弊病，激發(fā)了學(xué)生的學(xué)習(xí)興趣。使用多媒體技術(shù)還可以直接在課堂上演示算法的實現(xiàn)過程，讓學(xué)生熟悉算法實現(xiàn)的環(huán)境和方法，增強(qiáng)了該門課的實踐性，提高了課堂授課效率和教學(xué)質(zhì)量，取得了滿意的教學(xué)效果。教師們?yōu)榱烁玫剡m應(yīng)社會的發(fā)展和改革的需要，本著強(qiáng)化算法的思想，在現(xiàn)有數(shù)據(jù)結(jié)構(gòu)內(nèi)容的基礎(chǔ)上，補(bǔ)充了新的算法，拓寬了學(xué)生的知識面。五、課程建設(shè)取得的成果
1．教學(xué)科研論文
1）TheBoundaryElementAnalysisforTheThermalConductionofTheThermalEquipment。ProceedingsofInternationalConferenceonComputationalPhysics,RintonPress,US,(201*)199-202（SCI）
2）基于訪問控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究。計算機(jī)與網(wǎng)絡(luò)24,(201*)52-53(核刊)
3）信息系統(tǒng)在企業(yè)現(xiàn)代化管理中的應(yīng)用�！渡虉霈F(xiàn)代化（學(xué)術(shù)版）》，201*.225-26(核刊)
4）可信網(wǎng)絡(luò)基本概念與基本屬性研究。《赤峰學(xué)院學(xué)報》201*.5
5）基于包過濾技術(shù)路由器防火墻在網(wǎng)絡(luò)安全中的研究�！队嬎銠C(jī)應(yīng)用研
究》,201*,vol23
6）ResearchonTheArchitectureofTru-Network。201*International
SymposiumonInformationscienceandEngineering
7）路由器防火墻對沖擊波、震蕩波病毒的過濾研究。《赤峰學(xué)院學(xué)報》201*.1
67-68
8）菲涅耳圓孔衍射的數(shù)值模擬。《赤峰學(xué)院學(xué)報》201*.9）復(fù)雜軸承流體動力學(xué)特性的邊界元分析。《潤滑與密封》201*.3(核刊EI
核心刊源)
10）三葉軸承流體動力學(xué)特性的邊界元分析。《潤滑與密封》201*.5(核刊EI
核心刊源)
11）164-182Hf核的低能譜和電磁躍遷的相互作用玻色子模型�！陡吣芪锢砼c核
物理》28(12),(201*)119-122(核刊,SCI收錄)
12）基于訪問控制列表的路由器防火墻在網(wǎng)絡(luò)安全中的應(yīng)用研究�！队嬎銠C(jī)與網(wǎng)
絡(luò)》201*.24
13）赤峰學(xué)院校園網(wǎng)路由器、交換機(jī)的選型及遠(yuǎn)程登錄�！冻喾褰逃龑W(xué)院學(xué)報》
201*.581-82
14）《XML數(shù)據(jù)庫存儲策略綜述》《計算機(jī)科學(xué)》201*年9月（核刊）15）《XML數(shù)據(jù)庫結(jié)構(gòu)連接算法之研究》《計算機(jī)科學(xué)》201*年6月（核刊）16）《XML中XPath包含關(guān)系判定算法》《內(nèi)蒙古大學(xué)學(xué)報》201*年10月（核刊）17）《基于關(guān)系數(shù)據(jù)庫的XML數(shù)據(jù)的存儲研究》《赤峰學(xué)院學(xué)報》201*年3月18）《XML數(shù)據(jù)庫模式匹配算法研究》《赤峰學(xué)院學(xué)報》201*年5月19）《Internet蠕蟲的分析與研究》《赤峰學(xué)院學(xué)報》201*年4月20）《如何防止外部網(wǎng)絡(luò)的攻擊》《赤峰學(xué)院學(xué)報》201*年2月21）《射頻IC卡消費(fèi)系統(tǒng)的設(shè)計與實現(xiàn)》《赤峰學(xué)院學(xué)報》201*年10月22）《XPath片斷的分析與研究》《赤峰學(xué)院學(xué)報》201*年1月23）《一種基于層次結(jié)構(gòu)的XML編碼技術(shù)》中國教育信息化》201*年4月（核刊）24）《VC++實現(xiàn)圖形、數(shù)據(jù)庫應(yīng)用系統(tǒng)的思路》赤峰教育學(xué)院學(xué)報201*年第2月25）《基于IP組播的多媒體會議系統(tǒng)的設(shè)計》赤峰教育學(xué)院學(xué)報201*年6月26）論文《個性化WINDOWS系統(tǒng)“開始”菜單》赤峰教育學(xué)院學(xué)報201*年4月27）淺談DEBUG程序的主要命令用法赤峰學(xué)院學(xué)報201*年5月28）powerpoint技巧在課件制作中的妙用赤峰學(xué)院學(xué)報201*年1月29）淺談用MASM運(yùn)行匯編程序赤峰學(xué)院學(xué)報201*年1月30）XML數(shù)字簽名淺析赤峰學(xué)院學(xué)報201*年5月31）《網(wǎng)絡(luò)層的靜態(tài)路由選擇綜述》赤峰學(xué)院學(xué)報201*年3月32）《離散數(shù)學(xué)在計算機(jī)教學(xué)中的作業(yè)》赤峰學(xué)院學(xué)報201*年1月33）《基于模擬退火算法的油井工礦數(shù)據(jù)挖掘的應(yīng)用研究》
赤峰學(xué)院學(xué)報201*年1月
2.教研課題
1）赤峰學(xué)院校園網(wǎng)項目赤峰學(xué)院201*年-201*年（已驗收）2）基于IP網(wǎng)QOS動態(tài)控制研究內(nèi)蒙教育廳201*年-201*年（已結(jié)題）3）基于結(jié)構(gòu)索引XML模式匹配方法研究內(nèi)蒙教育廳201*年201*年（已結(jié)題）4）XML數(shù)據(jù)庫研究赤峰學(xué)院201*年201*年（已結(jié)題）5）CAI系統(tǒng)中知識個性化組織與導(dǎo)航研究內(nèi)蒙教育廳201*年-201*年（已結(jié)題）6）XML安全數(shù)據(jù)發(fā)布關(guān)鍵問題研究內(nèi)蒙教育廳201*年201*年（在研）3.教學(xué)獲獎
1）范體貴、門愛華、張國祥、王玉紅分別獲赤峰學(xué)院201*、201*年、201*年、201*年“課堂教學(xué)質(zhì)量優(yōu)秀獎”；
2）門愛華201*年、201*年連續(xù)獲的“畢業(yè)論文優(yōu)秀指導(dǎo)教師”獎勵；3）王玉紅201*年獲院級“畢業(yè)實習(xí)優(yōu)秀實習(xí)指導(dǎo)教師”獎勵；
4）201*年《數(shù)據(jù)結(jié)構(gòu)課程教學(xué)和實踐》課題”獲赤峰學(xué)院“優(yōu)秀教學(xué)成果二等獎”。
數(shù)據(jù)結(jié)構(gòu)課程組201*年5月14日
友情提示：本文中關(guān)于《數(shù)據(jù)結(jié)構(gòu)課程總結(jié)》給出的范例僅供您參考拓展思維使用，數(shù)據(jù)結(jié)構(gòu)課程總結(jié)：該篇文章建議您自主創(chuàng)作。
來源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問題，請聯(lián)系我們及時刪除。
公文素材庫友情提示：本網(wǎng)站所有內(nèi)容為共享上傳提供，不涉及任何商業(yè)利益，本站對此不承擔(dān)任何保證責(zé)任！
Copyright © m.seogis.com Corporation, All Rights Reserved 共享時代 共享你我他 版權(quán)所有