劉超

[摘要]數(shù)據(jù)結構作為計算機專業(yè)的一門基礎課程，對學生理解計算機這門學科有著基礎性的作用。對以后的系統(tǒng)框架，程序編寫等都有至關重要的作用。我認為提高這門課的教學質量，首先要轉變觀念。這個觀念就是成教的學生學習的內(nèi)容比較膚淺，不需要學習太多的內(nèi)容。有這個先入為主的觀念就不會有積極性去提高教學質量，不會深入研究這門課的如何才有更好的教學效果。不能否認成教的學生有自己的特點，有經(jīng)驗有想法，但時間不固定，這就需要我們成人教育的老師對這門課如何教，如何學有自己思路，不能完全照搬普通高校教材，僅僅進行簡化。這篇文章就是我對者們?nèi)绾卧诔扇私逃腥绾谓淌诘乃伎技皩嵤?/p>

[關鍵詞]主要矛盾；成人教育；數(shù)據(jù)結構；授課

[中圖分類號]G642

[文獻標識碼]A

[文章編號]1671-5918（2018）03-0143-03

十九大報告中提出當前的社會主要矛盾已經(jīng)發(fā)生改變，現(xiàn)在的主要矛盾為“由我國社會主要矛盾已經(jīng)轉化為人民日益增長的美好生活需要和不平衡不充分的發(fā)展之間的矛盾?！斌w現(xiàn)在教育領域就是由以前的想上學到上好學的變化，這就要求我們成教人必須提高自己，鉆研自己的專業(yè)，提高自己授課能力為解決教育領域的主要矛盾貢獻自己的力量。

一、數(shù)據(jù)結構的前生今世

數(shù)據(jù)結構指相互之間存在著一種或多種關系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素的關系。在不同教材中，對數(shù)據(jù)結構也有不同的描述，Sartaj Sahni在《數(shù)據(jù)結構、算法與應用》中描述數(shù)據(jù)結構是數(shù)據(jù)對象，以及存在于該對象的實例和組成實例的數(shù)據(jù)元素之間的各種聯(lián)系。這些聯(lián)系可以通過定義相關的函數(shù)來給出?！盋lifford A.Shaffer的《數(shù)據(jù)結構與算法分析》中定義為數(shù)據(jù)結構是ADT（抽象數(shù)據(jù)類型Abstract Data Type）的物理實現(xiàn)?！盧obert L.Kruse在《數(shù)據(jù)結構與程序設計》一書中，將一個數(shù)據(jù)結構的設計過程分成抽象層、數(shù)據(jù)結構層和實現(xiàn)層。其中，抽象層是指抽象數(shù)據(jù)類型層，它討論數(shù)據(jù)的邏輯結構及其運算，數(shù)據(jù)結構層和實現(xiàn)層討論一個數(shù)據(jù)結構的表示和在計算機內(nèi)的存儲細節(jié)以及運算的實現(xiàn)。而數(shù)據(jù)結構作為一個單獨的學科是1968年由美國的Donald Ervin Knuth教授的《計算機程序設計藝術》的第一卷《基本算法》較系統(tǒng)地闡述了數(shù)據(jù)的邏輯結構和存儲結構及其操作?？傊?，對數(shù)據(jù)結構的講解中定義一半都是包含數(shù)據(jù)和數(shù)據(jù)之間的關系兩部分。

數(shù)據(jù)結構作為計算機專業(yè)的一門基礎課程，對學生理解計算機這門學科有著基礎性的作用。對以后的系統(tǒng)框架，程序編寫等都有至關重要的作用。在成人教育中，報名計算機專業(yè)的同學一直不是很多，這就與我們這些課程的教學質量上不去有很大的關系。

二、數(shù)據(jù)結構在國開教學的現(xiàn)狀

我認為提高這門課的教學質量，首先要轉變觀念。這個觀念就是成教的學生學習的內(nèi)容比較膚淺，不需要學習太多的內(nèi)容。有這個先人為主的觀念就不會有積極性去提高教學質量，不會深入研究這門課的如何才有更好的教學效果。實際上，成教讀計算機的同學，特別是本科的同學既然要讀這個專業(yè)，很多都是從事計算機這一行業(yè)的，特別是部分同學還從事了開發(fā)工作，有一定的實際開發(fā)經(jīng)驗，在實際學習中他們更想將學到的東西進行理論聯(lián)系實踐，這反而比普通教育的難度更高。反觀普通高等教育中的計算機專業(yè)的同學基本是沒有編程經(jīng)驗的。他們在學習的過程中對數(shù)據(jù)組合的，程序的設計，系統(tǒng)的效率思考并沒有那么深刻。這是簡單將這些概念存在腦海里，主要用于應付以后的考試。

成教就不一樣了，比如他的在實際開發(fā)的過程中調用過哈希函數(shù)，對實際項目運行過程中的數(shù)據(jù)存儲是以哈希表的格式存儲還是鏈表的格式存儲，有直觀的感受，會對不同的數(shù)據(jù)結構格式的使用造成對運行效率產(chǎn)生的影響有深刻的認識，對數(shù)據(jù)存儲使用什么的結構就有自己的想法和問題。如果我們在教學過程深入思考這一點，這門課的教學難度就要比普通高等學校的教學高出一個層次。

三、教學變革的思考及實踐

在教學中如何深入淺出的講解這門課，就要將理論和實際相結合。這門課在前面講述了隊列，鏈表，樹，圖，哈希表等幾種基本結構后，重點內(nèi)容就是這個幾種基本結構下的遍歷，搜索，插入，刪除等操作。重點和難點就是樹，圖，哈希表等幾種結構的遍歷操作，這個操作也是整個數(shù)據(jù)結構的基礎。在理解了幾種基礎結構后，重點如何重點突出的理解這幾種操作及應用了。

這篇文章由于篇幅限制，重點講了變革的第一次課的授課，也是最有代表性的一次課。

數(shù)據(jù)結構中的常用的幾種數(shù)據(jù)類型，我們選用用鏈表和哈希表來舉例說明。選鏈表的原因是這個結構比較容易理解，操作起來也比較簡單。選用哈希表是因為這個方法實際應用比較廣，效率高，學生在學習過程中和實際工作容易結合，且算法比較成熟，各種變種比較多，可應用于很多環(huán)境中。

排序通常被用作各種計算機科學類的人門問題，以展示一系列算法。我們在數(shù)據(jù)結構的選擇冒泡排序來進行一次排序算法的演示，至于數(shù)據(jù)結構使用的采用的是單鏈表還是雙鏈表或者順序存儲都是屏蔽了交換細節(jié)，不影響算法。

教學設計安排：

我在平時的上課實驗中，把這門課的一節(jié)分了四個部分。

（一）第一步（3分鐘）引入新授內(nèi)容

同學們，我們學習計算機專業(yè)要做的就是對信息進行處理。信息在計算機中就是數(shù)據(jù)，如何操作數(shù)據(jù)，首先要知道數(shù)據(jù)是什么樣子的。根據(jù)數(shù)據(jù)間的邏輯關系，把數(shù)據(jù)合理有效地存儲到計算機中，并使用合理的算法對其進行相應的處理。這就是我們的這門課，數(shù)據(jù)結構。

數(shù)據(jù)：是描述和量化客觀事物和信息等的符號；數(shù)據(jù)元素是數(shù)據(jù)的基本單位；

數(shù)據(jù)結構：是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。

現(xiàn)在我們選用我們常用的數(shù)據(jù)類型，就是我們的學生檔案信息來作為數(shù)據(jù)結構的描述，比如我們把學生的相關信息，學生學號作為一個數(shù)據(jù)項（也可以認為是一個數(shù)據(jù)元素），數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小單位。我們也可以把多個數(shù)據(jù)項如（學號，姓名，年齡，性別，電話等）多個數(shù)據(jù)元素合成為一個數(shù)據(jù)元素，來統(tǒng)一處理。

處理什么呢？我們的著眼點是數(shù)據(jù)間的位置關系，數(shù)據(jù)間是否存在直接或者間接的聯(lián)系等方面，

（二）第二步（12分鐘）講授新的課程內(nèi)容

1.線性結構的描述及雙鏈表的操作

比如我們把我們的學生信息抽象為一個接著一個排列的，呈現(xiàn)出線性排列的關系。為了避開使用指針這個較為抽象的概念，我們使用雙鏈表的結構來存儲學生數(shù)據(jù)。

2.圖形描述；對比數(shù)組和雙鏈表的結構

數(shù)組：內(nèi)容連續(xù)存放；

雙鏈表；數(shù)據(jù)之間通過地址來進行鏈接；

雙聯(lián)表的主要特點：

一個數(shù)據(jù)元素由三部分組成，前驅，數(shù)據(jù)項，后驅。前驅內(nèi)存放的是前面一個節(jié)點的地址，數(shù)據(jù)項存放的是這個數(shù)據(jù)具體內(nèi)容，比如學生的（學號，姓名，年齡，性別等）。后驅存放的是后面一個節(jié)點的地址。

講述數(shù)組和雙鏈表的優(yōu)缺點。數(shù)組，數(shù)據(jù)存放時間復雜度為Of（n），空間復雜度。機器語言及自然語言描述雙鏈表的查找，插入，刪除等的操作；

分析這個算法時間復雜度；

For（i=0；i

{操作}

3.提出問題

我們現(xiàn)在使用的數(shù)據(jù)比如一個班，只有幾十個人，查起來當然非?？?，但一個學校呢？就會有幾千人，一個學校呢？幾萬人，歷屆學生呢，幾十萬人；一個省呢？幾千萬，全國呢？幾億學生了，當數(shù)據(jù)量非常大的時候，這個效率就非常嚇人了；等待的時間就會非常長，這個用戶體驗就非常差了。

引出哈希表的使用（可以使用分庫分表的操作，但具體先不談）：

我們數(shù)組和鏈表的查找就是在比較基礎上進行的，還有后面要講的樹，圖等等都是在比較的基礎上進行的。這個計算效率并不高。我們現(xiàn)在大量的數(shù)據(jù)操作經(jīng)常使用的方法是使用哈希表來進行的，這個有什么特點呢，就是記錄的關鍵字值與該記錄的存儲位置之間建立一個對應關系。

舉例：將4個數(shù)據(jù)的關鍵值為{8，10，14，21}的數(shù)據(jù)存儲到表長為5的哈希表中，定義計算哈希地址的哈希函數(shù)為H（K）=K mod 5，K是關鍵值。

得到如圖所示的存儲：8mod5=3（取余數(shù)）10mod5=0；14mod5=4；

21mod5=1；

這個例子的數(shù)據(jù)量非常小，但是大家可以看出查找一個數(shù)據(jù)只需要兩步，根據(jù)關鍵值找相應的hashcode（哈希碼），然后根據(jù)哈希碼找到相應的地址。如果數(shù)據(jù)量有上百萬萬，上千萬的話，如果只有兩步就可以查到所需的關鍵值，這個效率就非常高了。

步驟1根據(jù)key得到hashcode方法：int hash=hash（key.hashCode（））；

步驟2根據(jù)hashcode得到對應的位置方法：inti=index-For（hash，table，length）；

這一步很關進?？梢詫⒁粋€key轉換成一個固定的位置。這就是為什么快的原因。

哈希算法的缺點主要是在前期進行解決，比如根據(jù)的數(shù)據(jù)量的大小確定哈希表的大小，及確定使用的哈希函數(shù)，還有沖突的解決。實際中可以根據(jù)關鍵值的增大調整哈希表的長度，進行重構。

無論中間使用什么樣沖突處理，對于大數(shù)據(jù)量的存儲操作來說，兩步就可以找到關鍵值效率都是非常高的，相對于鏈表的時間復雜度為Of（n），節(jié)省的時間都是非?？捎^的。

（三）第三步：討論與提問

設計的題目主要是學生對鏈表和哈希表的認識，及對這兩種數(shù)據(jù)結構的操作的時間復雜度的直觀概念及印象。

聽取學生提出的問題，回答并進行解析。

（四）第四步：實驗

找出提供100條學生的信息，用學號作為關鍵字，讓學生對數(shù)據(jù)進行存儲及查找的操作；

可以使用自然語言或高級語言中的C，c++，java，c#等都可以，循環(huán)要表達出來；

如果這部分學生的實踐經(jīng)驗較好，則兩種結構每人都要寫；如果實踐經(jīng)驗不好，則每人寫一種，水平較好的寫哈希表的操作。根據(jù)最后的學生實驗結果來總結這門課的授課結果。

四、課程教學變革總結

這門課在課后和學生的討論中發(fā)現(xiàn)，學生基本能夠理解這兩種數(shù)據(jù)結構的算法，能夠用自然語言描述出來，而且對數(shù)據(jù)結構這門課有了初步的興趣，基本達到了教學目標。

課程教學變革的第一次后的學生學習情況是對這門課程非常重要的總結及反思，后續(xù)的樹圖的查詢遍歷亦是非常重要的內(nèi)容，后面的課程會根據(jù)第一次的課程進行總結后在進行變革，目標就是讓學生在盡量短的面授課時間內(nèi)，對數(shù)據(jù)結構的幾種重要結構及遍歷算法有深刻的印象。希望看到本文的讀者有興趣和作者討論這門課的教學變革。

參考文獻：

[1]周維.基于共享內(nèi)存的多核時代數(shù)據(jù)結構研究[J].軟件學報，2016，27（4）.

[2]唐艷琴.“數(shù)據(jù)結構”小班化教學探討[J].計算機工程與科學，2014，36（zl）.

[3]湯瓊.基于PBL和LBL的數(shù)據(jù)結構教學研究與實踐[_！|.浙江中醫(yī)藥大學學報2011，35（6）.

[4]姚麗莎.項目驅動教學在數(shù)據(jù)結構課程教學中的應用研究[J].赤峰學院學報（自然科學版），2017，33（3）.