關于《數據結構》在成人教育中授課方式的變革思考及實驗

劉超

[摘要]數據結構作為計算機專業的一門基礎課程，對學生理解計算機這門學科有著基礎性的作用。對以后的系統框架，程序編寫等都有至關重要的作用。我認為提高這門課的教學質量，首先要轉變觀念。這個觀念就是成教的學生學習的內容比較膚淺，不需要學習太多的內容。有這個先入為主的觀念就不會有積極性去提高教學質量，不會深入研究這門課的如何才有更好的教學效果。不能否認成教的學生有自己的特點，有經驗有想法，但時間不固定，這就需要我們成人教育的老師對這門課如何教，如何學有自己思路，不能完全照搬普通高校教材，僅僅進行簡化。這篇文章就是我對者們如何在成人教育中如何教授的思考及實施。

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

[中圖分類號]G642

[文獻標識碼]A

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

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

一、數據結構的前生今世

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

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

二、數據結構在國開教學的現狀

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

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

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

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

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

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

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

教學設計安排：

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

（一）第一步（3分鐘）引入新授內容

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

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

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

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

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

（二）第二步（12分鐘）講授新的課程內容

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

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

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

數組：內容連續存放；

雙鏈表；數據之間通過地址來進行鏈接；

雙聯表的主要特點：

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

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

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

For（i=0；i

{操作}

3.提出問題

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

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

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

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

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

21mod5=1；

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

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

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

這一步很關進。可以將一個key轉換成一個固定的位置。這就是為什么快的原因。

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

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

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

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

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

（四）第四步：實驗

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

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

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

四、課程教學變革總結

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

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

參考文獻：

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

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

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

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