大數據背景下高職院校《數據結構》課程的教學改革初探

鄭春紅，王偉

（青島職業技術學院信息學院，青島266000）

0 引言

隨著人工智能、物聯網、云計算的興起，大數據越來越受到廣泛關注。大數據時代，以海量數據為中心的管理和處理技術已取得良好的發展態勢，大數據產業應用推進勢頭良好，在金融、醫療健康、汽車交通、文化娛樂、電子商務等應用領域不斷創新發展。

大數據技術中較為核心的技術如Hadoop、HBase、Hive、Spark 等，這些核心技術的很多核心理念都是建立在計算機專業基礎課程之上的，如數據結構、數據庫原理、Linux 操作系統等。例如，Hadoop 技術中利用Map/Reduce 框架計算時，Map 結果在shuffle 階段進行分區、排序、合并，再進入Reduce 規約階段。其中，排序過程為了提高內存利用率循環利用內存空間，如80%（默認）寫，處理后放到外存一個文件，寫的過程其他20%空間可以繼續寫，原來80%處理完釋放后又可以利用，其原理運用的就是數據結構中的循環隊列；再比如，Hadoop 技術采用HDFS 分布式文件管理系統管理數據，Map/Reduce 框架中一個Reduce 可以保證輸出結果有序，多個Reduce 要保證輸出數據全局有序，Map輸出結果要根據Reduce 的個數，采用除留余數法將數據分配到對應的Reduce 中進行計算，其方法采用的就是數據結構中的Hash 函數。

本文主要分析《數據結構》課程與大數據技術的關系并探索大數據背景下《數據結構》課程的改革。

1 高職院校《數據結構》課程建設現狀

（1）亟待開發大數據背景下適合高職院校大數據專業學生的《數據結構》校本課程

目前，隨著大數據技術的不斷發展，高職院校計算機專業相繼開設大數據專業，《數據結構》作為專業核心課程，即是前面課程的升華，也是后續課程的先導，應緊密結合大數據的相關技術理論，將知識點與大數據內容建立鏈接，突出重點，通過實踐踐行大數據相關理論。現在，高職院校亟待開發適合高職院校大數據專業學生的《數據結構》校本課程及資源。

（2）數據結構教學內容與新技術發展脫節

數據結構主要內容有線性表、棧和隊列、串、數組和廣義表、樹和二叉樹、圖、查找、排序等，內容抽象、繁雜，并且后續章節知識點較為復雜，高職院校學生難以理解和掌握。內容設置上，每章節的知識點及實踐教學案例素材較為傳統且陳舊，與大數據等新型技術的發展脫節嚴重，難以起到對后續章節的先導作用。

（3）師資隊伍的培訓有待提高[1]

目前，大數據專業科班出身的教師資源有限，專業教師大多通過短期或中長期培訓學習大數據技術，自身的大數據理論水平和專業水平極為有限，實踐能力相對缺乏，將大數據核心理論技術融入《數據結構》課程的能力有限。

2 將大數據融入《數據結構》課程的建設方案

（1）將數據結構內容與大數據技術進行鏈接

《數據結構》作為計算機專業核心課程，亟待融入大數據前沿理論和技術的相關知識。同時，由于《數據結構》課程較為抽象，學生在學習時如果能知道該知識點在當前計算機行業前沿技術上的具體應用，會極大地提高學生的學習興趣，提高教學效果。本文結合數據結構的主要內容，以及大數據技術理論與技術的發展，總結了大數據技術中用到的數據結構，并將其融入到《數據結構》課程的教學內容中。激發學生的學習興趣，培養學生的大數據思維，為后續課程做充分的引導作用。

（2）將大數據技術滲入數據結構實踐教學中[2-3]

①線性表與內存調度優化

線性表中比較特殊的兩類數據結構有棧和隊列，它們的操作具有局限性。棧是限定插入刪除操作只能在一端進行的線性表，因此具有“先進后出”的特點。隊列是限定插入在表的一端執行，刪除在另一端，因此具有“先進先出”的特點。

在傳統的《數據結構》教學實踐中，通常用括號匹配檢驗、表達式求值等作為棧這部分內容的實踐教學案例，用銀行排隊叫號、圖的廣度優先遍歷等作為隊列這部分內容的實踐教學案例。

由于在大數據技術中也廣泛應用棧和隊列的結構，可以將全新的案例引入到實踐教學中[4]。

在HBase 數據庫中，每個元素對同一份數據有多個版本，根據唯一的時間戳來區分版本，時間戳就是HBase 在寫數據時自動獲取的毫秒級系統時間，當用戶查詢數據時，默認將最新版本數據顯示給用戶，即后寫入的數據最先顯示給用戶，這就是利用棧的后進先出的特點實現的。

在Hadoop 的MapReduce 計算框架中，Map 輸出數據經過分區、排序、溢寫到外存文件，再作為Reduce 的輸入進行計算。中間的排序過程是將數據讀到內存進行插入排序，內存滿了就溢出了。為了防止溢出，會循環利用內存空間，默認可以設置80%內存用于寫數據，當該部分內存空間寫滿后，自動寫到外存，其余20%空間可以繼續寫，原來80%處理完釋放后又可以利用，因此不會影響其他數據的寫入內存過程，避免了內存溢出。這里的循環利用內存空間的方法，就是依據循環隊列的原理實現的。

②樹與決策樹

樹是用來模擬具有樹狀結構性質的數據集合，主要內容有二叉樹及遍歷算法、平衡二叉樹、哈夫曼樹等，通常用哈夫曼編碼作為樹這部分內容的實踐教學案例。

在大數據中，樹型邏輯結構有廣泛的應用。例如HBase 數據庫中存放的數據，多是半結構化或非結構化的數據，如XML 文檔樹、HBase 數據模型等。

樹在機器學習中也有所應用，可以作為教學案例融入《數據結構》的課堂教學中。例如決策樹。決策樹（Decision Tree）也叫分類樹，是一種樹形結構，樹中每個分支節點可以表示一個屬性，每個分支代表一種輸出，每個葉子可以代表一種類別，在已知各種情況發生概率的基礎上，通過構成決策樹構造的預測模型，可以用于評價項目風險，判斷其可行性。

例如，表1 記錄的是近半個月天氣情況及小明外出踢足球的數據，圖1 是根據表1 數據創建的決策樹，有了決策樹，就可以根據未來天氣情況來預測小明是否會外出踢足球。通過這個例子，可以讓學生理解樹形結構的應用，了解決策樹的作用，為學生今后接觸機器學習算法做準備。具體的決策樹構造過程，即由給定數據集構造決策樹的過程，可不做贅述。

圖1 預測小明是否外出踢足球的決策樹

數據結構中的圖結構是包含若干頂點的集合，以及表示頂點之間關系的邊的集合。圖的常見應用有社交網絡、交通網絡等。

在大數據分析技術中，機器學習的無監督學習領域有一種基于劃分的聚類方法：K-means（k-均值）算法。該算法基于圖這類數據結構，將海量樣本集中的每個樣本看作是圖中的一個頂點，K 值是要聚成的類別數量，算法首先隨機在圖中取k 個假定的中心點（種子點），然后對需要分類的其他所有點分別求到這k 個種子點的距離，距離哪個種子點最近就聚到那類。接下來，在每個點群中選取新的點群中心，再迭代上述過程。

將K-means 算法與圖這部分知識相鏈接，可以拓展學生的四維空間，開拓學生的大數據方面的知識視野。

④哈希表與數據分布式存儲及HBase 表設計優化

順序查找、二分查找、哈希表是數據結構中的三大查找方法。其中，哈希表是將關鍵碼值通過哈希函數映射到表中一個位置，從而可以直接通過關鍵碼值直接訪問數據的數據結構。主要內容有哈希函數的選取及沖突處理方法，在傳統實踐教學中，通常已單機小數量集為例，將哈希表的查找效率與線性表的順序存儲和鏈式存儲的查找效率做比較，來驗證其不僅是一種高效的存儲結構，還是一種常見的高效的查找方法。

在大數據技術中，海量數據的存儲和處理是在分布式集群上實現的，如何實現分布式存儲和實現高效率的查找是一個關鍵的問題，而哈希表在這時發揮了它的優勢。

在Hadoop 的MapReduce 計算框架中，Mapper 任務劃分數據的過程就是Partition（分區），分區的過程就是將大量數據按照關鍵字值決定Mapper 輸出記錄被送到哪個Reducer 上處理，這一過程就是哈希分區。分區后可以實現并行處理數據，從而提高計算效率。

在HBase 中，表的索引是通過鍵值來實現的，表中數據通過RowKey（行鍵）按字典順序排序后，進行分區，分布式存儲到多個region（分區）。如果數據聚集存儲到部分region，而其余region 空閑，這將導致在分布式系統中不能并發工作，也會降低查詢效率。為了使負載均衡，在設計RowKey 時，可以遵循散列原則，將RowKey 的最高位作為散列字段，由程序循環生成，這樣可以實現將數據均衡分布在每個Region，實現負載均衡，提高查詢效率。

通過引入上述案例，可以讓學生理解哈希表不僅可以實現單機小數據集的高效存儲和查詢，在數據的分布式存儲中也有著非常廣泛的實際應用。

⑤排序算法在大數據技術中的應用

數據結構中的排序算法有內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。在教學過程中，重點內容是內部排序中的選擇排序、插入排序、交換排序。

在海量數據的分布式存儲中，排序是極為關鍵和重要的一項工作。例如，與傳統數據庫不同，在HBase中，表是三維的，由行鍵、列鍵（列族：列名）、時間戳組成。為了便于對數據的訪問，表中每行按行鍵的字典順序升序排序，行鍵相同的按列鍵升序排序，如果行鍵和列鍵都相同，則按時間戳降序排序。排序后，按行鍵檢索時，即可快速定位分區，查找到指定行并返回最新版本數據。

通過這個案例可以加深學生對排序應用的理解，并對排序在大數據技術中的重要性有一個初步的了解。

（3）創新教學模式，培養學生的大數據思維和創新能力

①創新改進教學方法[5]，激發學生學習興趣

大數據時代背景下，教師在充分了解學生的學習狀態、知識水平、能力特長的同時，要積極改進教學方法，合理規劃課堂教學過程，充分調動學生學習的積極性和主動性，提高教學效果。

②合理應用網絡資源，引導學生自主學習

授人以魚不如授人以漁，教會學生知識不如教會學生學習的方法。大數據時代，網絡學習資源豐富，教師可以通過藍墨云班課等教學平臺分享與課程內容相關的網絡資源，為學生提供學習的第二課堂，引導學生自主學習。

③構建數據結構的大數據實驗平臺，為實踐教學提供豐富的案例和實驗。

為了將數據結構相關的大數據技術引入課堂教學內容，可以在實訓室搭建大數據實驗平臺，例如Hadoop、HBase 等，教師可以通過大數據實驗平臺演示教學案例，也可以讓學生在平臺環境下進行實踐練習，在實踐中理解數據結構中的知識在大數據中的實際應用，培養學生的大數據思維和創新能力。

3 結語

大數據技術發展如火如荼，其技術理論與傳統專業基礎課程密切相關，數據結構作為計中的線性表、隊列、樹、圖、排序等內容在大數據相關技術理論中均有廣泛實踐應用，將數據結構內容與大數據前沿技術相結合，探索《數據結構》課程教學改革，可以在《數據結構》課程教學過程中有的放矢，激發學生學習興趣，培養學生大數據思維。今后，隨著對大數據技術的進一步深入了解，可以開發數據結構與大數據相關的綜合實踐教學內容。