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