劉超

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

[關(guān)鍵詞]主要矛盾；成人教育；數(shù)據(jù)結(jié)構(gòu)；授課

[中圖分類號(hào)]G642

[文獻(xiàn)標(biāo)識(shí)碼]A

[文章編號(hào)]1671-5918（2018）03-0143-03

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

一、數(shù)據(jù)結(jié)構(gòu)的前生今世

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

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

二、數(shù)據(jù)結(jié)構(gòu)在國開教學(xué)的現(xiàn)狀

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

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

三、教學(xué)變革的思考及實(shí)踐

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

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

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

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

教學(xué)設(shè)計(jì)安排：

我在平時(shí)的上課實(shí)驗(yàn)中，把這門課的一節(jié)分了四個(gè)部分。

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

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

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

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

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

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

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

1.線性結(jié)構(gòu)的描述及雙鏈表的操作

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

2.圖形描述；對(duì)比數(shù)組和雙鏈表的結(jié)構(gòu)

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

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

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

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

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

分析這個(gè)算法時(shí)間復(fù)雜度；

For（i=0；i

{操作}

3.提出問題

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

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

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

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

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

21mod5=1；

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

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

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

這一步很關(guān)進(jìn)?？梢詫⒁粋€(gè)key轉(zhuǎn)換成一個(gè)固定的位置。這就是為什么快的原因。

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

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

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

設(shè)計(jì)的題目主要是學(xué)生對(duì)鏈表和哈希表的認(rèn)識(shí)，及對(duì)這兩種數(shù)據(jù)結(jié)構(gòu)的操作的時(shí)間復(fù)雜度的直觀概念及印象。

聽取學(xué)生提出的問題，回答并進(jìn)行解析。

（四）第四步：實(shí)驗(yàn)

找出提供100條學(xué)生的信息，用學(xué)號(hào)作為關(guān)鍵字，讓學(xué)生對(duì)數(shù)據(jù)進(jìn)行存儲(chǔ)及查找的操作；

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

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

四、課程教學(xué)變革總結(jié)

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

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

參考文獻(xiàn)：

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

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

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

[4]姚麗莎.項(xiàng)目驅(qū)動(dòng)教學(xué)在數(shù)據(jù)結(jié)構(gòu)課程教學(xué)中的應(yīng)用研究[J].赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2017，33（3）.