教研結合在數據結構課程教學中的應用實踐

[摘 要]科研反哺教學是提高教學質量的有效手段。數據結構是計算機程序設計的重要理論基礎，教學要求學生掌握計算機所加工的數據的結構特性，以便為具體應用所涉及的數據選擇適當的邏輯結構、存儲結構及相應的算法。為了幫助學生更好地掌握理論知識，在教學中引用一個科研實例可以達到更好的教學效果。本文將科研項目中應用循環隊列實現DSP串口通訊數據處理程序，引入到數據結構課程的相關知識點的教學中，讓學生從理論聯系到實踐，更直觀地掌握教學內容。

[關鍵詞]教研結合 數據結構 循環隊列 串口通訊

[中圖分類號] G420 [文獻標識碼] A [文章編號] 2095-3437（2013）05-0069-02

教學與科學研究是高校的兩大重要職能。科學研究是基于解決問題的創新活動，相對于課堂教學被動學習來說，其主動探究的不確定性，可以有效激發學生學習知識的欲望和興趣。[1]

數據結構在計算機科學中是一門綜合性的專業基礎課。不僅是一般程序設計的基礎，而且是設計和實現編譯程序、操作系統、數據庫系統及其他系統程序和大型應用程序的重要基礎。[2]

數據結構課程中討論的隊列是一種重要的線性數據結構，如圖1所示。隊列被廣泛應用在各種軟件系統中，如操作系統中的作業排隊：在允許多道程序同時運行的計算機系統中，如果作業運行的結果都需要通過通道輸出，那就要按請求輸出的先后次序排隊。凡是申請輸出的作業都按時序從隊尾進入隊列，當通道傳輸完畢可以接受新的輸出任務時，隊頭的作業先從隊列中退出做輸出操作。若采用順序存儲結構實現隊列，在進行入隊列操作時，會產生假溢出現象。[3]所以在實際程序設計中，常采用將順序隊列臆造為一個首尾相連的環狀空間，稱之為循環隊列。

在講授到數據結構的循環隊列時，學生往往很難將所學知識與實際應用相結合，不知道書本上的存儲結構和基本算法在解決實際問題時怎樣使用。在此引入科研項目中DSP（Digital Signal Process）串口通訊中通信數據處理程序的設計作為數據結構課程中循環隊列這一知識點的具體用例，來幫助學生理解循環隊列有什么用，怎么用。

串口通訊是DSP與外部交換信息的重要手段。DSP對串口數據的接收是通過系統中斷來進行的。[4]為了保證主程序地正常運行，要求中斷處理例程執行效率高、占用CPU處理時間短[5]。但對串口通訊來講，是在物理層之上再采用某種通信協議進行數據的傳輸，比如Mdobus、TCP/IP協議等。這些協議的實現程序較為復雜，占用CPU處理時間較長。因此，串口通信協議不能直接在串口中斷處理例程中實現。常采用的處理方法是：串口中斷處理例程僅將接收到的數據放置到緩存中；而主程序中的通信數據處理例程對緩存中的數據進行協議解析等處理。在這個過程中中斷接收和串口通信數據處理這兩個異步執行的例程都要訪問同一緩存，它們的運行必須做到完美地協調，否則將會發生嚴重的共享內存訪問沖突問題，而導致通訊失敗。采用循環隊列是實現串口中斷處理例程與通信數據處理例程完美協調工作的有效手段。

一、循環隊列的構造

（一）數據結構

循環隊列在內存空間中的構造如圖2所示。在內存中分配一段存儲空間作為通信數據接收緩存，記緩存大小為S，緩存首地址為pMemHeader，緩存尾地址為pMemTail。有效通信數據是存儲在循環隊列中連續邏輯單元之內的。設置頭指針pHeader指向第一個有效通信數據存儲單元，尾指針pTail指向最后一個有效數據之后的存儲單元。相應的數據結構定義如圖3所示。

緩存從物理意義上講并不是首尾相接的，為將其構造為首尾相接的循環隊列，定義隊列指針移動函數QueuePointerMove（ ），來實現循環隊列指針加1的功能。函數實現如圖4所示，當指針已指向緩存最后一個存儲單元時，執行隊列指針移動函數后指針指向緩存的第一個存儲單元，否則指針直接加1。

（二）入隊操作

定義入隊操作QueueIn（ ）實現在隊尾加入一個新數據的功能。如圖5所示，先向隊尾指針所指向的單元內寫入數據，然后將隊尾指針加1即可。

（三）出隊操作

定義出隊操作QueueOut（ ）實現在隊首刪除一個數據的功能。如圖6所示，首先將隊首數據保存到局部變量data中，然后將隊首指針加1刪除隊首數據，最后返回變量data中的數據。

二、循環隊列在DSP串口通信中的使用

使用循環隊列實現DSP的串口通信，首先應在DSP主程序的初始化階段進行循環隊列的構造，以實現實際存儲空間的分配和各隊列參數的初始賦值；在接收中斷處理例程中調用入隊操作QueueIn（ ）將新接收到的串口數據加入隊尾；在串口數據處理例程中實現串口數據的處理并調用出隊操作QueueOut（ ）將處理過的數據從隊列中刪除。

（一）初始化

DSP主程序的初始化階段進行循環隊列的構造的代碼如圖7所示。首先定義CircleQueue類型的全局變量Queue；在主程序main（ ）的系統初始化階段中對Queue的各成員數據進行初始賦值，包括：緩存大小設置、緩存分配、緩存頭尾指針設置以及隊列頭尾指針設置。

（二）接收中斷處理例程

接收中斷處理例程的實現代碼如圖8所示。首先從串口接收寄存器里讀出接收到的數據，保存到變量data中；然后調用QueueIn（ ）函數將接收到的數據放入循環隊列中；最后清除中斷標志，準備接收下一個串口數據。

（三）串口數據處理例程

串口數據處理例程是由主程序中的一段代碼實現的，如圖9所示。主函數主體是一個無限循環體。每次循環首先判斷隊列是否為空，若隊列不為空才進行通信數據的處理。處理時調用出隊函數QueueOut（ ）取出隊首數據存入局部變量sciData中，同時將隊首數據從隊列中刪除。對取出的數據sciData，不同通信協議其處理方式亦不同，本文不再贅述。

[ 參 考 文 獻 ]

[1] 李俊杰.地方院?；诟咚綄W科平臺的科研反哺教學的理論與實踐探索——以浙江工業大學為例[J].浙江工業大學學報（社會科學版），2011，10（1）：53-56.

[2] 嚴蔚敏等編.數據結構[M].北京：清華大學出版社，2004.

[3] 黃迪明等編.軟件技術基礎[M].成都：電子科技大學出版社，2009.

[4] 劉陵順，高艷麗，張樹團，王昉.TMS320F28335DSP原理及開發編程[M].北京：北京航空航天大學出版社，2011.

[5] 褚東升，孟德國，黎明.μC/OS-Ⅱ中斷底半部機制的設計與實現[J].計算機工程，2011，37（17）：242-244.

[責任編輯：左 蕓]