第一篇：數(shù)據(jù)結(jié)構(gòu)學習總結(jié)
數(shù)據(jù)結(jié)構(gòu)與算法課程論文綜述
摘要
如何合理的組織數(shù)據(jù)、高效率的處理數(shù)據(jù)是擴大計算機應用領(lǐng)域、提高軟件效率的關(guān)鍵。在軟件開發(fā)過程中要求“高效地”組織數(shù)據(jù)和設(shè)計出“好的”算法，并使算法用程序來實現(xiàn)，通過調(diào)試而成為軟件，必須具備數(shù)據(jù)結(jié)構(gòu)領(lǐng)域和算法設(shè)計領(lǐng)域的專門知識。
《數(shù)據(jù)結(jié)構(gòu)與算法》課程就是主要學習在軟件開發(fā)中涉及的各種常用數(shù)據(jù)結(jié)構(gòu)及其常用算法，在此基礎(chǔ)上，學習如何利用數(shù)據(jù)結(jié)構(gòu)和算法解決一些基本的應用問題。
課程主要內(nèi)容
本學期一共學習了十章的內(nèi)容，下面就這十章的內(nèi)容作了詳細的介紹。第一章：數(shù)據(jù)結(jié)構(gòu)與算法概述
本章主要是對數(shù)據(jù)、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、算法及算法分析等基本概念的掌握，而如何合理地組織數(shù)據(jù)、高效地處理數(shù)據(jù)正是擴大計算機領(lǐng)域、提高軟件效率的關(guān)鍵，所以對這些概念的理解就顯得十分重要。
數(shù)據(jù)是指描述客觀事物的數(shù)值、字符、相關(guān)符號等所有能夠輸入到計算機中并能被計算機程序處理的符號的總稱，其基本單位是數(shù)據(jù)元素，而數(shù)據(jù)類型是一個同類值的集合和定義在這個值集上的一組操作的總稱。在高級程序語言中定義一種數(shù)據(jù)類型時，編譯程序編譯系統(tǒng)就能獲得如下信息：（1）、一組性質(zhì)相同的值的集合；（2）、一個預訂的存儲體系；（3）、定義在這個值集合上的一組操作。數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間的關(guān)系，它包括數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、一組運算集合；數(shù)據(jù)的邏輯結(jié)構(gòu)分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。數(shù)據(jù)的存儲方法有：順序存儲方法、鏈接存儲方法、索引存儲方法和散列存儲方法。接下來便是關(guān)于算法的有關(guān)概念，算法是為解決一個特定問題而采取的確定的有限步驟集合，它具有有窮性、確定性、可行性、輸入和輸出。關(guān)于算法的性能分析，分為時間性能分析和空間性能分析。第二章：順序表及其應用
本章主要是對順序表、順序表的結(jié)構(gòu)、數(shù)據(jù)類型、基本算法及相關(guān)應用的介紹。順序表是一種簡單而常用的數(shù)據(jù)結(jié)構(gòu)，其應用范圍較為廣泛，包括查找問題、排序問題、字符處理問題等內(nèi)容。第三章：鏈表及其應用
鏈表是一種簡單、常用的數(shù)據(jù)結(jié)構(gòu)，與順序表相比，具有插入、刪除結(jié)點不需要移動元素，不必事先估計存儲空間大小等優(yōu)點，操作較為靈活。它有六種基本運算：（1）、置空表（2）、求表長（3)、按序號取元素（4）、按值查找
(5)、插入（6）、刪除。
單鏈表即鏈表的每個結(jié)點只有一個指針域，用來存儲其直接后繼的存儲位置。但是這樣就使得對結(jié)點前面的元素的操作很困難，所以就在每個結(jié)點增加一個指向其前驅(qū)結(jié)點的指針域，從而構(gòu)成雙向鏈表。同時由于每個結(jié)點的地址既存放在其前驅(qū)結(jié)點的后繼指針中，又存放在其后繼結(jié)點的前驅(qū)指針域中，所以雙向鏈表的插入操作分為前插和后插。第四章：堆棧及其應用
首先要明白棧是一種受限制的線性結(jié)構(gòu)，遵守“先進后出”的規(guī)則，其插入與刪除操作都在棧頂進行。
其次根據(jù)順序存儲和鏈接存儲，棧分為順序棧和鏈棧。其中順序棧棧是用地址連續(xù)的存儲空間依次存儲棧中數(shù)據(jù)元素，并記錄當前棧頂數(shù)據(jù)元素的位置；基本算法包括置空棧、判棧空、判棧滿、取棧頂元素、入棧和出棧。而鏈棧則使用鏈式存儲堆棧的數(shù)據(jù)元素，并記錄當前棧頂數(shù)據(jù)元素的位置；每個結(jié)點包括data數(shù)據(jù)域：用來存放數(shù)據(jù)元素的值，next指針域：用來存放其直接后繼結(jié)點的存儲地址，其基本運算和順序棧相同。
最后是關(guān)于堆棧的應用：（1）、數(shù)值轉(zhuǎn)換問題；由于在將十進制數(shù)N轉(zhuǎn)換為d進制數(shù)時，最先得到的余數(shù)是d進制數(shù)的最低位，在顯示結(jié)果時需要最后輸出；而最后求得的余數(shù)是d進制數(shù)的最高位，需要最先輸出。這與棧的“先入后出”性質(zhì)相吻合，所以可用棧來存放逐次求得的余數(shù)，然后輸出。（2）、括號匹配問題；當讀取一個表達式時，一旦讀到括號就進棧，而讀到下一個括號時就與棧中括號比較，若相匹配，則出棧，否則繼續(xù)讀取表達式。到最后，如果棧為空棧，則說明括號匹配，否則括號不匹配。第五章：隊列及其應用
首先和棧一樣，要知道隊列是一種受限制的線性結(jié)構(gòu)，遵守“先進先出”的規(guī)則，其插入在隊尾、刪除在對頭。
其次根據(jù)順序存儲和鏈式存儲，隊列也分為順序隊列和鏈隊列。其中順序隊列是用地址連續(xù)的向量空間依次存儲隊列中的元素，同時記錄當前對頭元及隊尾元素在向量中的位置。然后是鏈隊列，即在存儲器中占用任意的、連續(xù)或不連續(xù)的物理存儲區(qū)域，使用動態(tài)結(jié)點空間分配；在這其中，值得注意的是鏈隊列不存在隊滿的情況。
第六章：特殊矩陣、廣義表及其應用
首先是關(guān)于矩陣的概念即存儲方法；
1、二維數(shù)組中元素aij的地址為：（1）、以行序為主存儲，Loc（aij）=Loc（a00）+[j*（m+1）+i]*d（2）、以列序為主存儲，Loc（aij）=Loc（a00）+[i*（n+1）+j]*d，其中m為行數(shù)、n為列數(shù)、d為每個元素所占的存儲單元的個數(shù)。
2、對稱矩陣：即將下三角存儲在一個一維數(shù)組sa[k]中，其中0≤k<(n+1)/2；當i≥j時，k=i*（i+1）/2+j，當i 3、三角矩陣：和對稱矩陣的存儲思路一樣用一維數(shù)組sa[k]存儲，若是上三角矩陣（下三角中元素均為常數(shù)c），則當i≥j時，k=i*（i+1）/2+j，當i 4、對角矩陣：同樣存儲在一維數(shù)組sa[k]中，k=2i+j 5、稀疏矩陣：即矩陣中非零元素個數(shù)遠遠小于矩陣元素個數(shù)，可用三元組表存儲，將非零元素的值與其行號、列號存放在一起。 其次是關(guān)于廣義表的概念；廣義表是n（n≥0）個元素a1、a2、a3、?、an的有限序列，而ai或是原子或是一個廣義表，所以廣義表是遞歸定義。第七章：二叉樹及其應用 首先關(guān)于二叉樹的概念及其性質(zhì)；二叉樹是由n（n≥0）個結(jié)點組成的有限集合。在這其中有兩種特殊的二叉樹，滿二叉樹和完全二叉樹。同時二叉樹具有如下五個性質(zhì)：（1）、在二叉樹的第i層上至多有2（i-1）個結(jié)點（i>0）（2）、深度為k的二叉樹至多有2（k）-1個結(jié)點（k>0）（3）、對任意一棵非空二叉樹，若果其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1（4）、有n個結(jié)點的完全二叉樹（n>0）的高度為∟log2n」+1（5）、若對滿二叉樹或完全二叉樹按照“從上到下，每層從左到右，根結(jié)點編號為1”的方式編號，則編號為i的結(jié)點，它的兩個孩子結(jié)點編號分別為2i和2i+1，它的父節(jié)點編號為i/2。 其次是二叉樹的存儲結(jié)構(gòu)分為順序存儲和鏈接存儲。順序存儲是按在完全二叉樹中的編號順序，依次存儲在一維數(shù)組中。這樣的存儲方式可以很方便地找到任一結(jié)點的父結(jié)點及左右孩子，但對于一般的二叉樹會造成很大的空間浪費，且在插入或刪除結(jié)點時需大量移動節(jié)點，不利于運算的實現(xiàn)。那么就引出了二叉樹的鏈接存儲，每個結(jié)點包括三個域，lchild指針域：記錄該結(jié)點左孩子的地址、rchild指針域：記錄該結(jié)點右孩子的地址、data域：存儲該結(jié)點的信息。 接下來是二叉樹的遍歷及線索化，不僅要能對二叉樹進行遍歷、線索化操作，而且還要能夠根據(jù)給出的遍歷結(jié)果構(gòu)造出二叉樹。最后是二叉樹的應用，例如哈夫曼樹：為數(shù)據(jù)壓縮提供了一種方法、二叉排序樹：即中序遍歷的結(jié)果是遞增的有序序列。 第八章：樹和森林及其應用 首先是關(guān)于樹和森林的有關(guān)概念及存儲結(jié)構(gòu)；樹或森林與二叉樹之間有一個自然地一一對應關(guān)系，任何一個森林或一棵樹可以唯一地對應到一棵二叉樹；反之，任何一棵二叉樹也能唯一地對應到一個森林或一棵樹。在這里，要會如何將樹或森林轉(zhuǎn)換成二叉樹、二叉樹轉(zhuǎn)換成樹或森林。對于樹的順序存儲結(jié)構(gòu)：雙親表示法，鏈接存儲結(jié)構(gòu)：（1）、孩子表示法（2）、孩子兄弟表示法，只需了解。 其次是樹和森林的遍歷，要知道樹只有先序遍歷和后序遍歷、森林只有先序遍歷和中序遍歷，且（1）、樹的先序遍歷與二叉樹的先序遍歷相同（2）、樹的后序遍歷與二叉樹的中序遍歷相同（3）、森林的先序遍歷和中序遍歷分別與二叉樹的先序遍歷和中序遍歷結(jié)果相同。 最后是樹的一個典型應用——B樹，它是一種平衡的多路查找樹，學習是根據(jù)實例走一遍算法，理解算法即可。第九章：散列結(jié)構(gòu)及其應用 散列結(jié)構(gòu)是以存儲結(jié)點中的關(guān)鍵字作為自變量，通過確定的函數(shù)H（即散列函數(shù)或哈希函數(shù)）進行計算，把所求的函數(shù)值作為地址存儲該結(jié)點。 首先是散列函數(shù)有：（1）、直接定址法（2）、除留余數(shù)法（3）、數(shù)字分析法（4）、平方取中法（5）、折疊法 其次是沖突處理，由于散列函數(shù)很可能將不同的關(guān)鍵字計算出相同的散列地址，所以就需要為發(fā)生沖突的關(guān)鍵字結(jié)點找到一個“空”的散列地址。沖突處理的方法有 1、開放定址法：Hi=（H（key）+di）mod m，i=1,2,3，?，K（K≤m-1）例如（1）、線性探測再散列，取di=1,2,3，?，m-1（2）、二次探測再散列，取di=1（2），-1（2），2（2），-2（2），?（3）、偽隨機探測再散列，取di=偽隨機數(shù)； 2、鏈地址法：在散列表的每一個存儲單元中增加一個指針域，把產(chǎn)生沖突的關(guān)鍵字以鏈表結(jié)構(gòu)存放在指針指向的單元中。第十章：圖及其應用 首先是圖的有關(guān)概念；圖是一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組表示，形式化定義為：Graph（V，VR），其中V={x|x∈dataobject}，R={VR}，VR={＜x，y＞ P（x，y）∧（x，y∈V）}。頂點的度、入度和出度，以頂點V為頭的弧的數(shù)目稱為V的入度，以頂點V為尾的弧的數(shù)目稱為V的出度，而出度與入度之和即為頂點V的度。 其次是圖的存儲結(jié)構(gòu)；（1）、鄰接矩陣（2)、鄰接表 最后的圖遍歷和圖的典型應用；對于遍歷圖的深度優(yōu)先算法或廣度優(yōu)先算法、最小生成樹的普利姆算法或克魯斯卡爾算法、最短路徑的迪杰特斯拉算法和弗洛伊德算法以及有向無環(huán)圖拓撲排序算法，都需要根據(jù)實例走一遍算法，從而掌握這些算法。 心得體會 最開始學習這門課時，我對它沒有很深刻的認識，只是聽說這門課比較難。學習起來會比較累。通過這一學期的學習也確實證實了這一點。在學習這門課的過程中自己也確實遇到了一些問題，主要是書本上的知識與老師的講解都比較容易理解，但是當自己利用已學的知識編寫程序時就感到非常的棘手，很多時候都是把大概的算法思想想出來后，又把書本上的程序抄寫一遍來完成程序的編寫。針對這一問題以后自己會盡量學習擺脫掉書本，自己慢慢學會獨立編寫程序。 結(jié)語 通過對數(shù)據(jù)結(jié)構(gòu)與算法的整理和實際應用，我深刻了解到數(shù)據(jù)結(jié)構(gòu)與算法的重要性，同時也加深了對它的認識和了解，了解到了數(shù)據(jù)結(jié)構(gòu)與算法在生活、工作等生活各個方面的重要性和不可缺少性。我通過整理數(shù)據(jù)結(jié)構(gòu)與算法的學習而獲得的極大收獲。我相信這次的學習會對我以后的學習和工作產(chǎn)生非常大的影響力。 參考文獻 《數(shù)據(jù)結(jié)構(gòu)與算法》（第二版）王昆侖 李紅 主編 數(shù)據(jù)結(jié)構(gòu)學習總結(jié) 通過一學期對《數(shù)據(jù)結(jié)構(gòu)與算法》的學習，大概的了解了基本的數(shù)據(jù)結(jié)構(gòu)和相應的一些算法。下面總結(jié)一下自己一個學期學習的收獲和心得。 數(shù)據(jù)結(jié)構(gòu)是什么： 數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或者存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。 數(shù)據(jù)結(jié)構(gòu)重要性： 一般認為，一個數(shù)據(jù)結(jié)構(gòu)是由數(shù)據(jù)元素依據(jù)某種邏輯聯(lián)系組織起來的。對數(shù)據(jù)元素間邏輯關(guān)系的描述稱為數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)必須在計算機內(nèi)存儲，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)形式，是其在計算機內(nèi)的表示；此外討論一個數(shù)據(jù)結(jié)構(gòu)必須同時討論在該類數(shù)據(jù)上執(zhí)行的運算才有意義。一個邏輯數(shù)據(jù)結(jié)構(gòu)可以有多種存儲結(jié)構(gòu)，且各種存儲結(jié)構(gòu)影響數(shù)據(jù)處理的效率。在許多類型的程序的設(shè)計中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個基本的設(shè)計考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗表明，系統(tǒng)實現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴重的依賴于是否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時候事情也會反過來，我們根據(jù)特定算法來選擇數(shù)據(jù)結(jié)構(gòu)與之適應。不論哪種情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。選擇了數(shù)據(jù)結(jié)構(gòu)，算法也隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構(gòu)造的關(guān)鍵因素。這種洞見導致了許多種軟件設(shè)計方法和程序設(shè)計語言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計語言就是其中之一。 常見的數(shù)據(jù)結(jié)構(gòu)： 1.順序表： 定義：順序表是在計算機內(nèi)存中以數(shù)組的形式保存的線性表,是指用一組地址連續(xù)的存儲單元依次存儲數(shù)據(jù)元素的線性結(jié)構(gòu)。線性表采用順序存儲的方式存儲就稱之為順序表。順序表是將表中的結(jié)點依次存放在計算機內(nèi)存中一組地址連續(xù)的存儲單元中?；具\算： 置表空：Sqlsetnull（L）判表滿：Sqlempty（L） 求表長：Sqllength(L) 插入：Sqlinsert（L,i,x） 按序號取元素：Sqlget（L,i） 刪除：Sqldelete(L,i)按值查找：Sqllocate(L,x)2.鏈表 定義：鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點（鏈表中每一個元素稱為結(jié)點）組成，結(jié)點可以在運行時動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域，另一個是存儲下一個結(jié)點地址的指針域。相比于線性表順序結(jié)構(gòu)，鏈表比較方便插入和刪除操作。分類：單鏈表—用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。 循環(huán)鏈表—循環(huán)鏈表是另一種形式的鏈式存貯結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)?；具\算：建立鏈表，插入節(jié)點，刪除節(jié)點。 3.堆棧 定義：堆棧都是一種數(shù)據(jù)項按序排列的數(shù)據(jù)結(jié)構(gòu)，只能在一端(稱為棧頂(top))對數(shù)據(jù)項進行插入和刪除。要點：堆：順序隨意棧：后進先出(Last-In/First-Out)。基本算法： 置空棧：InitStack（S） 判?？眨篠tackEmpty（S） 判棧滿：StackFull（S） 取棧頂元素：GetTop（S） 入棧：Push（S） 出棧：Pop(S)4.隊列 定義：隊列是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。在隊列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將最后被刪除的元素，因此隊列又稱為“先進先出”（FIFO—first in first out）的線性表。 分類：順序隊列；鏈隊； 基本運算：初始化隊列 Qini(Q) 入隊 QADD(Q,X) 出隊 QDel(Q,X) 判斷隊列是否為qempty(Q) 判斷隊列是否為滿qfull(Q)5.特殊矩陣 分類：對陣矩陣；三角矩陣；稀疏矩陣； 6.二叉樹 定義：二叉樹是每個節(jié)點最多有兩個子樹的有序樹。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i-1次方個結(jié)點；深度為k的二叉樹至多有2^(k)-1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)(即葉子結(jié)點數(shù))為n0，度為2的結(jié)點數(shù)為n2，則n0 = n2 + 1。(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層(1～h-1)的結(jié)點數(shù)都達到最大個數(shù)，第 h 層有葉子節(jié)點，并且葉子節(jié)點都是從左到右依次排布，這就是完全二叉樹。 (2)滿二叉樹——除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉結(jié)點都處在最底層的二叉樹,。 (3)深度——二叉樹的層數(shù)，就是高度。性質(zhì)： (1)在二叉樹中，第i層的結(jié)點總數(shù)不超過2^(i-1)； (2)深度為h的二叉樹最多有2^h-1個結(jié)點(h>=1)，最少有h個結(jié)點；(3)對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1； (4)具有n個結(jié)點的完全二叉樹的深度為int（log2n）+1 (5)有N個結(jié)點的完全二叉樹各結(jié)點如果用順序方式存儲，則結(jié)點之間有如下關(guān)系： 若I為結(jié)點編號則 如果I<>1，則其父結(jié)點的編號為I/2；如果2*I<=N，則其左兒子（即左子樹的根結(jié)點）的編號為2*I；若2*I>N，則無左兒子；如果2*I+1<=N，則其右兒子的結(jié)點編號為2*I+1；若2*I+1>N，則無右兒子。 (6)給定N個節(jié)點，能構(gòu)成h(N)種不同的二叉樹。h(N)為卡特蘭數(shù)的第N項。h(n)=C(n,2*n)/(n+1)。 （7）設(shè)有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i。 二叉樹遍歷： 遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點，使每一個結(jié)點都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實質(zhì)上是將二叉樹的各個結(jié)點轉(zhuǎn)換成為一個線性序列來表示。 設(shè)L、D、R分別表示遍歷左子樹、訪問根結(jié)點和遍歷右子樹，則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD（稱為后根次序遍歷）。 (1)前序遍歷 訪問根；按前序遍歷左子樹；按前序遍歷右子樹(2)中序遍歷 按中序遍歷左子樹；訪問根；按中序遍歷右子樹(3)后序遍歷 按后序遍歷左子樹；按后序遍歷右子樹；訪問根 （4）層次遍歷 即按照層次訪問，通常用隊列來做。訪問根，訪問子女，再訪問子女的子女（越往后的層次越低）（兩個子女的級別相同）。7.散列 定義：若結(jié)構(gòu)中存在和關(guān)鍵字K相等的記錄，則必定在f(K)的存儲位置上。由此，不需比較便可直接取得所查記錄。稱這個對應關(guān)系f為散列函數(shù)(Hash function)，按這個思想建立的表為散列表。 散列函數(shù)：直接定址法；除留余數(shù)法；數(shù)字分析法；平方取中法；折疊法。沖突處理方法：開放地址法（線性探測再散列，二次探測再散列，偽隨機探測再散列）鏈地址法。8.圖 定義：一種較線性表和樹更為復雜的數(shù)據(jù)結(jié)構(gòu)。 存儲結(jié)構(gòu)：鄰接矩陣；鄰接表；逆鄰接表；十字鏈表；鄰接多重表。圖的遍歷： 深度優(yōu)先遍歷：深度優(yōu)先遍歷的思想類似于樹的先序遍歷。其遍歷過程可以描述為：從圖中某個頂點v出發(fā)，訪問該頂點，然后依次從v的未被訪問的鄰接點出發(fā)繼續(xù)深度優(yōu)先遍歷圖中的其余頂點，直至圖中所有與v有路徑相通的頂點都被訪問完為止。 廣度優(yōu)先遍歷：對圖的廣度優(yōu)先遍歷方法描述為：從圖中某個頂點v出發(fā)，在訪問該頂點v之后，依次訪問v的所有未被訪問過的鄰接點，然后再訪問每個鄰接點的鄰接點，且訪問順序應保持先被訪問的頂點其鄰接點也優(yōu)先被訪問，直到圖中的所有頂點都被訪問為止。下面是對一個無向圖進行廣度優(yōu)先遍歷的過程。 查找算法 1.順序查找：在一個已知無(或有序）序隊列中找出與給定關(guān)鍵字相同的數(shù)的具體位置。原理是讓關(guān)鍵字與隊列中的數(shù)從第一個開始逐個比較，直到找出與給定關(guān)鍵字相同的數(shù)為止。 2.折半查找：首先，假設(shè)表中元素是按升序排列，將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。 3.分塊查找：先選取各塊中的最大關(guān)鍵字構(gòu)成一個索引表；查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中； 然后，在已確定的塊中用順序法進行查找。4.二叉排序樹： 定義：二叉排序樹（Binary Sort Tree）又稱二叉查找樹。它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；（3）左、右子樹也分別為二叉排序樹； 查找：若根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點的關(guān)鍵字值，遞歸查左子樹。若大于根結(jié)點的關(guān)鍵字值，遞歸查右子樹。若子樹為空，查找不成功。 排序算法： 1.直接插入排序：插入排序的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個新的、個數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時間復雜度為O(n^2)。是穩(wěn)定的排序方法。插入算法把要排序的數(shù)組分成兩部分：第一部分包含了這個數(shù)組的所有元素，但將最后一個元素除外，而第二部分就只包含這一個元素。在第一部分排序后，再把這個最后元素插入到此刻已是有序的第一部分里的位置。 2.希爾排序：先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取第二個增量d2 3.冒泡排序：依次比較相鄰的兩個數(shù)，將小數(shù)放在前面，大數(shù)放在后面。即在第一趟：首先比較第1個和第2個數(shù)，將小數(shù)放前，大數(shù)放后。然后比較第2個數(shù)和第3個數(shù)，將小數(shù)放前，大數(shù)放后，如此繼續(xù)，直至比較最后兩個數(shù)，將小數(shù)放前，大數(shù)放后。至此第一趟結(jié)束，將最大的數(shù)放到了最后。在第二趟：仍從第一對數(shù)開始比較（因為可能由于第2個數(shù)和第3個數(shù)的交換，使得第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一的位置上已經(jīng)是最大的），第二趟結(jié)束，在倒數(shù)第二的位置上得到一個新的最大數(shù)（其實在整個數(shù)列中是第二大的數(shù)）。如此下去，重復以上過程，直至最終完成排序。 4.快速排序：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。 5.直接選擇排序：第一次從R[0]~R[n-1]中選取最小值，與R[0]交換，第二次從R{1}~R[n-1]中選取最小值，與R[1]交換，....第i次從R[i-1]~R[n-1]中選取最小值，與R[i-1]交換.....第n-1次從R[n-2]~R[n-1]中選取最小值，與R[n-2]交換,總共通過n-1次,得到一個按排序碼從小到大排列的有序序列。 6.歸并排序：申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；重復直到某一指針達到序列尾；另一序列剩下的所有元素直接復制到合并序列尾。 心得：無論我們學習什么課程，概念永遠是基礎(chǔ)，所有的知識都是建立在基礎(chǔ)概念之上的。我們要將概念熟記于心，然后構(gòu)建知識框架。數(shù)據(jù)結(jié)構(gòu)包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。線性結(jié)構(gòu)包括線性表、棧、隊列、串、數(shù)組、廣義表等，棧和隊列是操作受限的線性表，串的數(shù)據(jù)對象約束為字符集，數(shù)組和廣義表是對線性表的擴展：表中的數(shù)據(jù)元素本身也是一個數(shù)據(jù)結(jié)構(gòu)。除了線性表以外，棧是重點，因為棧和遞歸緊密相連，遞歸是程序設(shè)計中很重要的一種工具。樹狀結(jié)構(gòu)中的重點自然是二叉樹和哈弗曼樹了。對于二叉樹的很多操作都是基于對二叉樹的遍歷，掌握了如何遍歷，很多問題也就迎刃而解了，比如對二叉樹結(jié)點的查找訪問、統(tǒng)計二叉樹中葉子結(jié)點的數(shù)目、求二叉樹的深度等。哈弗曼編碼也有著很廣泛的應用。對于圖狀結(jié)構(gòu)，主要學習圖的存儲結(jié)構(gòu)及圖的遍歷。對算法的學習是學習數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。要注重對算法的掌握。對于一個算法，如果我們不是很理解的話，可以手動將算法走一遍，慢慢理解該算法的思想。學習這門課程的最終目的，還是要學會如何設(shè)計算法，這需要我們長期的練習和思考。 《數(shù)據(jù)結(jié)構(gòu)與算法》課程學習總結(jié)報告 本學期開設(shè)的《數(shù)據(jù)結(jié)構(gòu)與算法》課程已經(jīng)告一段落，現(xiàn)就其知識點及其掌握情況、學習體會以及對該門課程的教學建議等方面進行學習總結(jié)。 一、《數(shù)據(jù)結(jié)構(gòu)與算法》知識點 第一章是這門學科的基礎(chǔ)章節(jié)，從整體方面介紹了“數(shù)據(jù)結(jié)構(gòu)和算法”，同時引入相關(guān)的學術(shù)概念和術(shù)語，如數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)類型以及數(shù)據(jù)結(jié)構(gòu)的定義。重點是數(shù)據(jù)結(jié)構(gòu)的括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運算集合的含義及其相互聯(lián)系。數(shù)據(jù)結(jié)構(gòu)和兩大邏輯結(jié)構(gòu)的4四種常用存儲方法；邏輯結(jié)構(gòu)分為四類：集合型、線性、樹形和圖形結(jié)構(gòu)，數(shù)據(jù)元素的存儲結(jié)構(gòu)分為：順序存儲、鏈接存儲、索引存儲和散列存儲四類。難點是算法復雜度的分析方法和性能的分析。 第二章詳細地分析了順序表。介紹了順序表的相關(guān)概念及其有關(guān)運算?；具\算有：初始化表、求表長、排序、元素的查找、插入及刪除等。元素查找方法有：簡單順序查找、二分查找和分塊查找。排序方法有：直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序及歸并排序等，在各種算法思想的先分析后，要弄清各種算法的時間復雜度與空間性能的優(yōu)點和缺點，在什么特定的場合適合哪種算法思想。最后介紹了順序串的概念，順序串是順序表的一個特例；區(qū)別在于組成順序串的數(shù)據(jù)元素是一組字符，其重點在于串的模式匹配。 第三章介紹鏈表。鏈表中數(shù)據(jù)元素的存儲不一定是連續(xù)的，還可以占用任意的、不連續(xù)的物理存儲區(qū)域。與順序表相比，鏈表的插入、刪除不需要移動元素，給算法的效率帶來較大的提高，且在存儲空間上有動態(tài)申請的優(yōu)點。這一章中介紹了鏈表的節(jié)點結(jié)構(gòu)、靜態(tài)與動態(tài)鏈表的概念、鏈表的基本運算（如求表長、插入、查找、刪除等）、單鏈表的建立（頭插法和尾插法）以及雙向循環(huán)鏈表的定義、結(jié)構(gòu)、功能和基本算法。弄清其個運算的算法思想及其時間復雜度和空間性能。最后介紹了鏈表之中存儲結(jié)構(gòu)在實際中的相關(guān)應用。 第四章，堆棧是運算受限制的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同，不同的是堆棧須遵循“先進后出”的規(guī)則，對堆棧的操作只能在棧頂進行；堆棧在文字處理，匹配問題和算術(shù)表達式的求值問題方面的應用。 第五章，隊列是一種夠類似堆棧的線性結(jié)構(gòu)。其基本運算方法與順序表和鏈表運算方法基本相同，不同的是堆棧須遵循“先進先出”的規(guī)則，對堆棧的操作只能在棧頂進行；其運算有入隊、出隊等操作。在介紹隊列時，提出了循環(huán)隊列的概念，以避免“假溢出”的現(xiàn)象。 第六章介紹了特殊矩陣和廣義表的概念與應用。其中，特殊矩陣包括對稱矩陣、三角矩陣、對角矩陣和稀疏矩陣，書中分別詳細介紹了它們的存儲結(jié)構(gòu)。其中三元組和十字鏈表這兩種結(jié)構(gòu)尤為重要；對著兩種結(jié)構(gòu)的建立了應用要掌握。稀疏矩陣的應用包括轉(zhuǎn)置和加法運算等。最后介紹了廣義表的相關(guān)概念及存儲結(jié)構(gòu)，關(guān)于它的應用，課本中舉了m元多項式的表示問題。 第七章二叉樹的知識是重點內(nèi)容。在介紹有關(guān)概念時，提到了二叉樹的性質(zhì)以及兩種特殊的二叉樹：完全二叉樹和滿二叉樹。接著介紹二叉樹的順序存儲和鏈接存儲以及生成算法。重點介紹二叉樹的遍歷算法（遞歸算法、先序、中序和后序遍歷非遞歸算法）和線索二叉樹。二叉樹的應用：基本算法、哈弗曼樹、二叉排序樹和堆排序，其中關(guān)于二叉排序樹和哈弗曼書的構(gòu)建是重點。 第八章介紹了樹。樹與二叉樹是不同的概念。教材介紹了樹和森林的概念、遍歷和存儲結(jié)構(gòu)，還有樹、森林和二叉樹的相互關(guān)系，樹或森林怎樣轉(zhuǎn)化成二叉樹，二叉樹又如何轉(zhuǎn)換為樹和森林等算法。 第九章，散列結(jié)構(gòu)是一種查找效率很高的一種數(shù)據(jù)結(jié)構(gòu)。本章的主要知識點有：散列結(jié) 構(gòu)的概念及其存儲結(jié)構(gòu)、散列函數(shù)、兩種沖突處理方法、線性探測散列和鏈地址散列的基本算法以及散列結(jié)構(gòu)的查找性能分析。 最后一章介紹了圖的概念及其應用，是本書的難點。圖的存儲結(jié)構(gòu)的知識點有：鄰接矩陣、鄰接表、逆鄰接表、十字鏈表和鄰接多重表。圖的遍歷包括圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷。其余知識點有：有向圖、連通圖、生成樹和森林、最短路徑問題和有向無環(huán)圖及其應用。有向無環(huán)圖重點理解AOV網(wǎng)和拓撲排序及其算法。 二、對各知識點的掌握情況 總體來看，對教材中的知識點理解較為完善，但各個章節(jié)均出現(xiàn)有個別知識點較為陌生的現(xiàn)象，對某些具體的問題和應用仍有一些模糊與措手。各個章節(jié)出現(xiàn)的知識點理解和掌握情況明確一下。 第一章中我對數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)的概念理解較為透徹，熟悉數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。算法的時間、空間性能分析是重點，同樣也是難點，尤其是空間性能分析需要加強。在某些強大與復雜的算法面前的處理有些棘手。 第二章，順序表的概念、生成算法理解較為清晰，并且熟悉簡單順序查找和二分查找，對分塊查找較為含糊。刪除方面的問題比較容易些。排序問題中，由于冒泡排序在大一C語言課上已經(jīng)學習過，再來學習感覺相對輕松些。對插入排序和選擇排序理解良好，但是，在實際運用中仍然出現(xiàn)明顯不熟練的現(xiàn)象。由于在歸并排序?qū)W習中感覺較吃力，現(xiàn)在對這種排序方法仍然非常模糊，所以需要花較多的時間來補習。此外串的模式匹配也是較難理解的一個地方。 第三章鏈表中，除對雙向循環(huán)鏈表這一知識點理解困難之外，在對鏈表進行插入刪除和排序相關(guān)操作上同順序表的操作基本相當。其他的知識點像單鏈表的建立和基本算法等都較為熟悉。 第四章和第五章有關(guān)堆棧以及隊列的知識點比較少，除有關(guān)算法較為特殊以外，其余算法都是先前學過的順序表和鏈表的知識，加上思想上較為重視，因此這部分內(nèi)容是我對全書掌握最好的一部分。在一些實際問題的應用與處理方面，對其進行存儲結(jié)構(gòu)的選擇還是需要認真考慮的。在算法的時間復雜度和空間性能的分析仍有些困難。 第六章的學習感覺較為困難的部分在于矩陣的應用上。在矩陣的存儲結(jié)構(gòu)中，使用三元組表發(fā)相對較為簡單，而使用十字鏈表就有些困難了。但在某些問題的處理上又必須或從節(jié)省空間考慮采用十字鏈表來處理，想矩陣的加法運算。廣義表的定義還是比較容易理解的，其存儲結(jié)構(gòu)也不難掌握，關(guān)于應用也只局限于在多項式的表示上。 第七章是全書的重點。在這一章中概念和定義都很多，有些很昏人但都很重要，要區(qū)分開來。二叉樹的性質(zhì)容易懂卻很難記憶。對二叉樹的存儲結(jié)構(gòu)和遍歷算法這部分內(nèi)容掌握較好，能夠熟練運用。關(guān)于二叉排序樹和的哈弗曼樹卻相對有些壓力，其生成和對其關(guān)鍵字的插入和刪除時重點。 第八章關(guān)于樹的分析，首先要明確樹和二叉樹的區(qū)別，以及書中的相關(guān)定義和概念。關(guān)于二叉樹、樹和森林之間的轉(zhuǎn)換和遍歷方法是重點，但不算是難。接著就是數(shù)的存儲結(jié)構(gòu)的選擇及轉(zhuǎn)化為二叉樹的算法，這部分有些吃力。再就介紹了特殊的樹-B樹，關(guān)于對B樹的操作，插入關(guān)鍵字是中帶領(lǐng)和難點。 第九章散列結(jié)構(gòu)這一章理解比較完善的知識點有：基本概念和存儲結(jié)構(gòu)。散列函數(shù)中直接定址法和除留余數(shù)法學得比較扎實，對數(shù)字分析法等方法則感覺較為陌生。對兩種沖突處理的算法思想的理解良好，問題在于用C語言描述上。 最后一章，圖及其應用中，相關(guān)定義及其概念很多，容易混淆，這就要慢慢來，仔細分辨。圖的鄰接矩陣、鄰接表表示法及其之間的轉(zhuǎn)換時重點和難點。而對十字鏈表和鄰接多重表的表示法則較為陌生。感覺理解較為吃力的內(nèi)容有圖的遍歷（包括深度和廣度優(yōu)先遍歷），以及最小生成樹的問題。最短路徑、AOV網(wǎng)、關(guān)鍵路徑、AOE網(wǎng)和拓撲排序的學習也是相對較輕松的。，三、學習體會 在學習開始，王教授就明確提出它不是一種計算機語言，不會介紹新的關(guān)鍵詞，而是通過學習可以設(shè)計出良好的算法，高效地組織數(shù)據(jù)。一個程序無論采用何種語言，其基本算法思想不會改變。聯(lián)系到在大一和大二上學期學習的C和C++語言，我深刻認識到了這一點?！败浖_發(fā)好比寫作文，計算機語言提供了許多華麗的辭藻，而數(shù)據(jù)結(jié)構(gòu)則考慮如何將這些辭藻組織成一篇優(yōu)秀的文章來?！痹趯W習這門課中，要熟悉對算法思想的一些描述手段，包括文字描述、圖形描述和計算機語言描述等。因此，計算機語言基礎(chǔ)是必須的，因為它提供了一種重要的算法思想描述手段——機器可識別的描述。 這門課結(jié)束之后，我總結(jié)了學習中遇到的一些問題，最為突出的，書本上的知識與老師的講解都比較容易理解，但是當自己采用剛學的知識點編寫程序時卻感到十分棘手，有時表現(xiàn)在想不到適合題意的算法，有時表現(xiàn)在算法想出來后，只能將書本上原有的程序段謄寫到自己的程序中再加以必要的連接以完成程序的編寫。針對這一情況，我會嚴格要求自己，熟練掌握算法思想，盡量獨立完成程序的編寫與修改工作，只有這樣，才能夠提高運用知識，解決問題的能力。 四、對《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學的建議 1、建議在上課過程中加大隨堂練習的分量，以便學生能當堂消化課堂上學習的知識，也便于及時了解學生對知識點的掌握情況，同時有助于學生保持良好的精神狀態(tài)。 2、建議在課時允許的情況下，增加習題課的分量，通過課堂的習題講解，加深對知識點的掌握，同時對各知識點的運用有一個更為直觀和具體的認識。 以上便是我對《數(shù)據(jù)結(jié)構(gòu)與算法》這門課的學習總結(jié)，我會抓緊時間將沒有吃透的知識點補齊。今后我仍然會繼續(xù)學習，克服學習中遇到的難關(guān)，在打牢基礎(chǔ)的前提下向更深入的層面邁進！ 數(shù)據(jù)結(jié)構(gòu)學習（C++）——樹（總結(jié)） happycock（原作）CSDN 才剛開了個頭，就要說再見了——在樹這里，除了二叉樹，別的都還沒有講。為什么可以總結(jié)了呢？因為前面已經(jīng)涉及到了樹的兩個基本用途，而如果再講B＋、B－，就不能不提到搜索，如果是勝者樹就不能不提到排序。為此，把這部分放到后面。我前面所做的努力，只是讓你有個基本概念，什么時候記得用樹。樹的兩個基本用途，可以用物質(zhì)和精神來比喻。 一個用途是做為數(shù)據(jù)儲存，儲存具有樹結(jié)構(gòu)的數(shù)據(jù)——目錄、族譜等等。為了在實際上是線性的儲存載體上（內(nèi)存、磁盤）儲存非線性的樹結(jié)構(gòu)，必須有標志指示出樹的結(jié)構(gòu)。因此，只要能區(qū)分根和子樹，樹可以采取各種方法來儲存——多叉鏈表、左子女－右兄弟二叉鏈表、廣義表、多維數(shù)組。由于操作的需求，儲存方法并不是隨意選取的。比如，在并查集的實現(xiàn)上，選取的是雙親鏈表。 一個用途是做為邏輯判斷，此時會常常聽到一個名詞——判定樹。最常用的結(jié)構(gòu)是二叉樹，一個孩子代表true，一個孩子代表false。關(guān)于多叉判定樹，有個例子是求8皇后的全部解——這個連高斯都算錯了（一共是92組解，高斯最開始說76組解），我們比不上高斯，但是我們會讓computer代勞。 就像哲學界到現(xiàn)在還糾纏于物質(zhì)和精神本源問題，實際上在樹這里也是如此。有些情況下，并不能區(qū)分是做為儲存來用還是做為判斷來用，比如搜索樹，既儲存了數(shù)據(jù)，還蘊涵著判斷。 和后面的圖相比，樹更基本，也更常用。你可以不知道最短路徑怎么求，卻每時每刻都在和樹打交道——看看你電腦里的文件夾吧。 最后，附帶一個求N皇后的全部解的程序。 #include #define N 8 int layout[N];//布局 int key = 0; int judge(int row, int col)//判斷能否在（row，col）放下 { int i;for(i = 0;i < row;i++){if(layout[i] == col)return 0;//同一列if(icol)return 0;//同一條主對角線} if(i + layout[i] == row + col)return 0;//同一條副對角線 return 1; } void lay(int row)//在row行上放Queen { int i;if(row == N)//放完N個Queen輸出布局 { }printf(“n%02d ”, ++key);for(i = 0;i < N;i++)printf(“%c%d ”, layout[i] + 'a', i + 1);} else {for(i = 0;i < N;i++)//在i列上放Queen} {} layout[row] = i;if(judge(row, i))lay(row + 1); int main() { } lay(0);return 0; “數(shù)據(jù)結(jié)構(gòu)”課程總結(jié) 計算機科學與技術(shù)專業(yè)從1994年開始為我校?？粕_設(shè)“數(shù)據(jù)結(jié)構(gòu)”課程，2004年開始為本科生開設(shè)這門課程。由于本門課程的教學從教材、講授、實驗指導都體現(xiàn)了先進的教育理念，該課程的教學體系科學、完整，教學手段與方法先進，課程特色鮮明，2006年被評為赤峰學院本科層次精品課。幾年來，數(shù)據(jù)結(jié)構(gòu)課題組成員從以下幾個方面對本門課程進行了建設(shè)和改革。 一、課程建設(shè)指導思想、定位和特色 1．學科地位 “數(shù)據(jù)結(jié)構(gòu)”是計算機科學與技術(shù)專業(yè)的一門學科基礎(chǔ)課，是本專業(yè)和相關(guān)專業(yè)必修課。本課程的教學目標是培養(yǎng)學生通過理解、分析和研究計算機處理的數(shù)據(jù)對象的特性，從而選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應的算法，并熟練掌握算法的時間分析和空間分析技巧?！皵?shù)據(jù)結(jié)構(gòu)”還是計算機科學與技術(shù)專業(yè)部分專業(yè)課的先導課，如“數(shù)據(jù)庫原理與應用”、“計算機操作系統(tǒng)”、“計算機編譯原理”和“面向?qū)ο蟮某绦蛟O(shè)計”等。所以本課程的教學效果將直接影響到學生對其它后續(xù)專業(yè)課的學習，因此，該課程在專業(yè)建設(shè)的地位十分重要。 “數(shù)據(jù)結(jié)構(gòu)”是一門應用性很強的課程，本課程要求學生在掌握各種數(shù)據(jù)結(jié)構(gòu)，特別是存儲結(jié)構(gòu)和有關(guān)算法的基礎(chǔ)上，通過大量的上機實例把難以理解的、抽象的概念轉(zhuǎn)化為計算機能夠正確運行的程序，從而提高學生運用所學知識解決實際問題的能力。2．課程特色 根據(jù)課程建設(shè)的規(guī)劃和我系實際，我們針對《數(shù)據(jù)結(jié)構(gòu)》課程教學開展討論，并就實驗、圖書資料等方面進行建設(shè)。在不斷的教學實踐中，我們按照精品課建設(shè)要求，積極探索，積累了豐富的教學經(jīng)驗。 采用國內(nèi)經(jīng)典教材，結(jié)合前沿的研究領(lǐng)域和最新科研動態(tài)，豐富教學內(nèi)容，讓學生了解數(shù)據(jù)結(jié)構(gòu)的實際應用價值。 采用課堂教學與大作業(yè)相結(jié)合，上機實踐為補充的教學模式，培養(yǎng)學生的創(chuàng)業(yè)創(chuàng)新素質(zhì)和團隊協(xié)作精神。 二、教師隊伍建設(shè) 1．良好的學緣結(jié)構(gòu) 任課教師的業(yè)務水平和教學水平是影響課程建設(shè)質(zhì)量的重要因素。為此，我們不斷加強師資隊伍建設(shè)，特別注重青年教師和實驗指導教師的培養(yǎng)。在擔任該課程教學任務的5名教師中，教授1名、副教授2名、講師2名，學歷結(jié)構(gòu)為碩士4人、學士1人，45歲以下3人，35歲以下2人。本教師梯隊學歷層次較高，職稱、年齡結(jié)構(gòu)合理，便于本門課程的建設(shè)和發(fā)展。 2．加強學術(shù)交流，不斷提高團隊整體教學和科研水平 在教學過程中，我們采取了互相聽課，舉行公開課、觀摩課等方式，經(jīng)常交流教書育人和教學改革方面的經(jīng)驗，不斷提高任課教師的教學水平和學術(shù)水平。 以范體貴教授為學科帶頭人的教學研究梯隊，具有豐富的教學經(jīng)驗和高昂的教學熱情，同時具備較高的教學研究和科學研究水平。教學梯隊成員在搞好教學的同時，積極申報承擔各級各類教學研究和科學研究課題，并參加國內(nèi)外相關(guān)學科的科研、教學等方面的學術(shù)交流活動。選派范體貴、門愛華兩位老師參加全國計算機年會和全國數(shù)據(jù)庫學術(shù)會議，與國內(nèi)其他高校著名學者進行了教學、科研等方面的交流，學到許多寶貴的經(jīng)驗和方法。 注重與其他高校的合作和交流，學習其他院校好的教學經(jīng)驗和方法。選派主講教師門愛華老師到清華大學計算機系做訪問學者，訪學期間門老師聽取了本課程的講授，經(jīng)常與講授本門課程的資深教授嚴蔚敏老師、殷仁昆老師進行交流、學習。二位老師都給予了具體的指導和建議，為我校本門課程的改革和發(fā)展提供了有利的幫助。請國內(nèi)著名高校學者來我系講學傳授經(jīng)驗，在教學、科研等方面給予具體的指導。2008年10月清華大學著名數(shù)據(jù)庫專家馮建華教授來我系講學，課題組成員與馮教授進行了深入的交流，在教學和科研方面都有很大的收獲。 3．開展科學研究，積極申請科研立項 數(shù)據(jù)結(jié)構(gòu)課題小組成員積極進行相關(guān)領(lǐng)域的科學研究，幾年來發(fā)表相關(guān)論文30余篇，承擔自治區(qū)級科研項目四個，赤峰市科技局科研項目一個，院級項目一個，其中3個項目已經(jīng)完成并通過驗收。目前在研的一個科研項目是與清華大學合作申請的計算機前沿領(lǐng)域研究課題，相信通過該項目的研究和合作，對我系的科研工作會起到極大的促進作用，同時能夠使我系科研水平上一個新的臺階。課題組成員經(jīng)過幾年的努力，在各方面都取得了一些成績。范體貴、門愛華、張國祥、王玉紅四位教師分別獲得“赤峰學院課堂教學質(zhì)量優(yōu)秀獎”，范體貴、門愛華兩位教師多次獲得“赤峰學院科研成果優(yōu)秀獎”的獎勵。王玉紅老師獲得“畢業(yè)實習優(yōu)秀指導教師“稱號，門愛華老師2007年、2008年連續(xù)獲得“畢業(yè)論文優(yōu)秀指導教師”獎勵。 建立了良好的人才培養(yǎng)制度，在學校和系里的大力支持下，鼓勵現(xiàn)有教師提高學歷與引進高學歷教師相結(jié)合，經(jīng)過幾年的建設(shè)，已經(jīng)形成了一支以中青年為主的學科梯隊。積極鼓勵中青年教師到國內(nèi)名校進修或攻讀碩士、博士學位，門愛華、董潔、王玉紅分別考取了東北大學和遼寧工程技術(shù)大學的碩士研究生，已圓滿完成學業(yè)并獲得碩士學位。 三、教學內(nèi)容、教材建設(shè) 1．理論環(huán)節(jié)教學內(nèi)容及學時分配 “數(shù)據(jù)結(jié)構(gòu)”是計算機科學課程體系中核心課程之首，作為學科的專業(yè)基礎(chǔ)課，具有承上啟下的重要作用。對應于學科中問題求解的理論、抽象和設(shè)計的方法論，本課程內(nèi)容體系結(jié)構(gòu)分為概念表述、構(gòu)建數(shù)據(jù)模型、設(shè)計算法三個層面，突出數(shù)據(jù)組織方法與處理技術(shù)，貫穿程序設(shè)計和軟件工程新思想和新觀點。理論學時設(shè)置為72學時。 2.實踐環(huán)節(jié)教學內(nèi)容及學時分配 上機實踐和課程設(shè)計重在培養(yǎng)學生軟件設(shè)計的綜合能力。在基本的課程實習基礎(chǔ)上,自2001年起開設(shè)了數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，使課程的實踐環(huán)節(jié)總學時數(shù)增加到60學時。提出了課程設(shè)計的規(guī)范要求，突出關(guān)鍵技術(shù)要點，貫穿基本技能訓練主線，加強實踐能力培養(yǎng)。 通過課程設(shè)計的訓練，突出構(gòu)造性思維訓練的特征，提高了學生組織數(shù)據(jù)與進行編寫大型程序能力，使學生更好地理解和掌握了算法設(shè)計所需的技術(shù)，為專業(yè)學習打下良好的基礎(chǔ)。課程設(shè)計題目（動態(tài)更新、完善）：航空客運訂票系統(tǒng)；電梯模擬；簡單行編輯程序；工資管理系統(tǒng)；醫(yī)院排隊看病活動的模擬；學籍管理系統(tǒng)；圖書管理系統(tǒng)等。3．教材建設(shè) 教材建設(shè)是課程建設(shè)的重要環(huán)節(jié)。為此，根據(jù)教學大綱和本課程的發(fā)展需要，在本課程教材的選用上注重教材的先進性和科學性，我們選用了清華大學出版社嚴蔚敏教授等編寫的《數(shù)據(jù)結(jié)構(gòu)》（C語言版）作為教材，本書內(nèi)容豐富、體系結(jié)構(gòu)嚴謹、概念清晰、易學易懂，也是多所院校指定的考研參考教材，完全適合我系計算機科學與技術(shù)、信息與計算科學專業(yè)學生的需要。任課教師則多方面參考相關(guān)教材，選擇部分編寫精彩的內(nèi)容充實到教案中。任課教師們廣泛閱讀相關(guān)文獻，了解該領(lǐng)域前沿知識，并且在授課過程中介紹給學生，以開闊學生的視野，拓寬學生的知識面。同時，根據(jù)教材內(nèi)容和實際教學要求，編寫了《數(shù)據(jù)結(jié)構(gòu)上機指導與習題就解答》，并正式出版了《數(shù)據(jù)結(jié)構(gòu)實驗教程》一書，該書作為自治區(qū)教育廳統(tǒng)編教材已在各高校廣泛使用。 四、教學方法和教學手段 1．教學方法 在教學方法上，講課、討論和專題講座等多種形式并用，以科學、生動靈活的講授方式傳授知識，培養(yǎng)學生的創(chuàng)造思維。教師在認真組織課堂講授，注意各環(huán)節(jié)正常運行的同時，還針對不同的教學內(nèi)容采取不同的方法進行講解，做到課程內(nèi)容既條理清晰、深入淺出，又重點突出、特色鮮明。教學內(nèi)容靈活，既有必講的內(nèi)容，也有針對不同專業(yè)需要和特點選講的內(nèi)容。 通過布置適量的課后習題，使學生能夠進一步鞏固和提高對課上所學知識的領(lǐng)悟和應用能力。我們在選擇習題時，一方面注重三基（基本理論，基本方法，基本技能）知識的掌握，另一方面也充分考慮知識的靈活應用，使學生能多角度、多方法地解決問題，既鍛煉他們的系統(tǒng)性思維，又提高分析解決問題的能力。每兩周安排一次習題課，由指導教師集中解決同學課上課下遇到的問題。 上機實踐是學生對本門課程所學知識的一種全面、綜合的能力訓練，是與課堂聽講、自學和練習相輔相成必不可少的一個教學環(huán)節(jié)，也是對課堂教學效果的一種檢驗。通常，實習題中的問題比平時的習題復雜得多，也更接近實際。實習題注重原理與應用的結(jié)合，目的讓學生學會如何把書上學到的知識運用于解決實際問題的過程中去，培養(yǎng)從事軟件開發(fā)設(shè)計工作所必需的基本技能。同時，通過實踐能使書上的知識變“活”，起到深化理解和靈活掌握教學內(nèi)容的作用。平時的練習較偏重于如何編寫功能單一的“小”算法，而實習題是軟件設(shè)計的綜合訓練，包括問題分析，總體結(jié)構(gòu)設(shè)計，用戶界面設(shè)計，程序設(shè)計基本技能和技巧，可以多人合作，有利于一整套軟件工程規(guī)范的訓練和科學作風的培養(yǎng)。此外，實踐環(huán)節(jié)中有很重要的一點，就是機器是比任何教師都嚴格的主考官。 2．教學手段 為了適應現(xiàn)代化教學的需求，我們在傳統(tǒng)教學的基礎(chǔ)上，充分利用現(xiàn)代科學技術(shù)，廣泛應用多媒體教學課件和教學軟件。將授課內(nèi)容制作成了圖文并茂的多媒體課件，利用多媒體技術(shù)對數(shù)據(jù)結(jié)構(gòu)輔之以形象的動畫，動態(tài)演示抽象的復雜數(shù)據(jù)結(jié)構(gòu)的變化，用板書補充某些推導過程并完成和學生互動的內(nèi)容，改變了以前課堂教學單調(diào)的弊病，激發(fā)了學生的學習興趣。使用多媒體技術(shù)還可以直接在課堂上演示算法的實現(xiàn)過程，讓學生熟悉算法實現(xiàn)的環(huán)境和方法，增強了該門課的實踐性，提高了課堂授課效率和教學質(zhì)量，取得了滿意的教學效果。教師們?yōu)榱烁玫剡m應社會的發(fā)展和改革的需要，本著強化算法的思想，在現(xiàn)有數(shù)據(jù)結(jié)構(gòu)內(nèi)容的基礎(chǔ)上，補充了新的算法，拓寬了學生的知識面。 五、課程建設(shè)取得的成果 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)代化（學術(shù)版）》，2005.2 25-26(核刊)4）可信網(wǎng)絡基本概念與基本屬性研究?！冻喾鍖W院學報 》2007.5 5）基于包過濾技術(shù)路由器防火墻在網(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）復雜軸承流體動力學特性的邊界元分析。《潤滑與密封》 2006.3(核刊 EI核心刊源)10）三葉軸承流體動力學特性的邊界元分析。《潤滑與密封》 2006.5(核刊 EI核心刊源)11）164-182Hf核的低能譜和電磁躍遷的相互作用玻色子模型?！陡吣芪锢砼c核物理》 28(12),(2004)119-122(核刊, SCI收錄)12）基于訪問控制列表的路由器防火墻在網(wǎng)絡安全中的應用研究?！队嬎銠C與網(wǎng)絡》 2004.24 13）赤峰學院校園網(wǎng)路由器、交換機的選型及遠程登錄?！冻喾褰逃龑W院學報》2004.5 81-82 14）《XML數(shù)據(jù)庫存儲策略綜述》 《計算機科學》 2005年9月（核刊）15）《XML數(shù)據(jù)庫結(jié)構(gòu)連接算法之研究》《計算機科學》 2007年6月（核刊）16）《XML中XPath包含關(guān)系判定算法》《內(nèi)蒙古大學學報》2008年10月（核刊）17）《基于關(guān)系數(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)的設(shè)計與實現(xiàn)》 《赤峰學院學報》 2008年10月 22）《XPath片斷的分析與研究》 《赤峰學院學報》 2008年1月 23）《一種基于層次結(jié)構(gòu)的XML編碼技術(shù)》 中國教育信息化》 2009年4月（核刊）24）《VC++實現(xiàn)圖形、數(shù)據(jù)庫應用系統(tǒng)的思路》赤峰教育學院學報 2002年第2月 25）《基于IP組播的多媒體會議系統(tǒng)的設(shè)計》 赤峰教育學院學報 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)控制研究 內(nèi)蒙教育廳 2005年-2007年（已結(jié)題）3）基于結(jié)構(gòu)索引XML模式匹配方法研究 內(nèi)蒙教育廳 2005年—2007年（已結(jié)題）4）XML數(shù)據(jù)庫研究 赤峰學院 2006年—2008年（已結(jié)題）5）CAI系統(tǒng)中知識個性化組織與導航研究 內(nèi)蒙教育廳 2003年-2005年（已結(jié)題）6）XML安全數(shù)據(jù)發(fā)布關(guān)鍵問題研究 內(nèi)蒙教育廳 2009年—2010年（在研）3.教學獲獎 1）范體貴、門愛華、張國祥、王玉紅分別獲赤峰學院2005、2006年、2007年、2008年“課堂教學質(zhì)量優(yōu)秀獎”； 2）門愛華2007年、2008年連續(xù)獲的“畢業(yè)論文優(yōu)秀指導教師”獎勵； 3）王玉紅2007年獲院級“畢業(yè)實習優(yōu)秀實習指導教師”獎勵； 4）2009年《數(shù)據(jù)結(jié)構(gòu)課程教學和實踐》課題”獲赤峰學院“優(yōu)秀教學成果二等獎”。 數(shù)據(jù)結(jié)構(gòu)課程組 2009年5月14日第二篇：數(shù)據(jù)結(jié)構(gòu)學習總結(jié)
第三篇：數(shù)據(jù)結(jié)構(gòu)總結(jié)[推薦]
第四篇：數(shù)據(jù)結(jié)構(gòu)學習(C)樹(總結(jié))
第五篇：“數(shù)據(jù)結(jié)構(gòu)”課程總結(jié)
點擊咨詢 