單鏈表算法的動態(tài)演示系統(tǒng)設計與實現(xiàn)

謝嘉，徐勇，梁后軍

（安徽財經大學計算機系，蚌埠　233030）

單鏈表算法的動態(tài)演示系統(tǒng)設計與實現(xiàn)

謝嘉，徐勇，梁后軍

（安徽財經大學計算機系，蚌埠233030）

0　引言

《數(shù)據(jù)結構》是計算機科學與技術專業(yè)的核心課程，它著力培養(yǎng)學生對于數(shù)據(jù)分析和算法規(guī)劃的綜合能力，而傳統(tǒng)的教學模式使得算法教學相對困難，本系統(tǒng)的出現(xiàn)正是為了解決這樣一個現(xiàn)狀，系統(tǒng)通過編程技術實現(xiàn)了《數(shù)據(jù)結構》經典算法的動態(tài)演示，使算法理解起來更為直觀。本系統(tǒng)主要展示了單鏈表的插入和刪除算法。

1　系統(tǒng)設計

本動態(tài)演示系統(tǒng)針對由清華大學出版社出版的C語言版《數(shù)據(jù)結構》教材進行設計與開發(fā)，由于采用C#語言來編寫C語言算法的演示動畫，所以需要使用C#語言按照C語言風格編寫一樣的算法流程來控制整個演示系統(tǒng)，實際運行的是C#版本的相應算法，其中變量跟蹤模塊顯示的地址是依據(jù)GCC編譯器編譯的C語言的可執(zhí)行文件的內存布局模擬出來的，基于這樣的基本思想，本演示系統(tǒng)得以開發(fā)。

引入多線程的目的是為了減小本數(shù)據(jù)結構動態(tài)演示系統(tǒng)在并發(fā)執(zhí)行時所付出的時間和空間的開銷。因為父子線程的并行，所以資源的共享和互斥問題顯得尤為重要。歸納起來面臨的問題有：

（1）系統(tǒng)中的控件屬于子線程，子線程也擁有自己的窗口，但在Debug版本中卻不能隨便修改窗口控件的屬性，否則會產生跨線程操作的異常。采取的措施是在線程構造函數(shù)中設其控件屬性為假。

（2）多線程編程會遇到線程的同步與互斥問題，為了簡化操作，避免因為線程間異步執(zhí)行而導致數(shù)據(jù)的不一致性。采取的措施是在子線程開啟后，部分變量僅僅在子線程被構造時被賦值，或者只有主線程才會修改其值，這樣保證了操作的原子性。

（3）主線程控制子線程的開啟、掛起、恢復與停止，而C#提供的 Thread類的 Abort、Suspend、Resume方法，均有一定的缺陷，其中部分函數(shù)已經被微軟淘汰，這些函數(shù)會因為資源未及時釋放而異常。又不能通過約束使用者的正確操作來保證系統(tǒng)的健壯性，所以只能通過設置開關變量來實現(xiàn)。

2　系統(tǒng)設計

該數(shù)據(jù)結構演示系統(tǒng)的算法核心包括三部分，分別是C語言版本源代碼的滾動、對算法中出現(xiàn)的棧變量和堆變量的跟蹤以及動畫的同步演示，由于系統(tǒng)中涉及的每個算法，都是由這核心的三個步驟組成，因此以單鏈表的插入算法為例來敘述整個實現(xiàn)的核心思想。

本系統(tǒng)首先實例化一個Model_List_Control類對象，即演示界面子窗口，通過TreeView控件選擇需要演示的具體算法，不同的選擇將導致以不同參數(shù)實例化的List_Thread類對象，即子線程對象的創(chuàng)建。在單擊開始按鈕時，會調用List_Thread類的t_Start函數(shù)，這是真正意義上的子線程的開啟。此時子線程與主線程并行。子線程不停地演示經典算法，主線程則用于控制子線程的狀態(tài)，例如掛起、恢復、停止以及設置其休眠時間。

該系統(tǒng)采用了面向對象的思想，封裝了多個類。下面詳細介紹使用的類。

（1）定義被演示的數(shù)據(jù)結構所需的對象類

由于C#指針的使用不同于C語言，所以不能直接定義結構類似的節(jié)點，取而代之的是自定義的Lin-kNode類，重要成員如下：

（2）自定義子線程類

由于系統(tǒng)提供的Thread類成員函數(shù)有缺陷，在使用不恰當?shù)臅r候會產生異常，所以自定義子線程類List_Thread再次封裝了系統(tǒng)的Thread類，用于控制線程的開啟、停止、掛起、恢復，提高了算法的健壯性，重要成員如下：

（3）定義動態(tài)演示子模塊界面類

Model_List_Control子模塊是該系統(tǒng)的重要組成部分。算法演示過程中的元素本質是屬性被修改的Label標簽類型，預先定義了10個標簽代表這些數(shù)據(jù)結構元素，這限制了用戶最大可以控制的線性長度為10。添加用于開始、暫停、停止、重置按鈕，用于調用自定義子線程的函數(shù)相應，只有在恰當?shù)臅r機（例如線程只有被開啟，才有可能被停止、掛起或者關閉）才會執(zhí)行，這是多線程編寫中比較麻煩和復雜的部分，需要嚴密的思考各種可能出現(xiàn)的情況，才能避免因為未及時釋放線程資源或者多次釋放導致的進程異常。重要成員如下：

從操作系統(tǒng)吞吐量和運行效率角度考慮，多線程無疑比傳統(tǒng)的單線程編程模式有很大的優(yōu)勢。傳統(tǒng)的單線程編程模式，處理機調度的對象是進程，當進程執(zhí)行在某個函數(shù)內部時，如果希望執(zhí)行同進程的其他函數(shù)是無法實現(xiàn)的。上文提到自定義子線程類List_Thread類中的ThreadProc函數(shù)是線程的回調函數(shù)，這是最核心的函數(shù)，一旦線程開啟就意味著函數(shù)的執(zhí)行，函數(shù)執(zhí)行完畢也就代表線程的結束。所以在函數(shù)內部調用了阻塞函數(shù)ShowDialog，保證按條件執(zhí)行完畢后線程才能結束，自定義子線程類部分源代碼如下：

［1］羅福強，楊劍，張敏輝.C#程序設計經典教程［M］.北京：清華大學出版社，2012.

［2］嚴蔚敏.數(shù)據(jù)結構（C語言版）.北京：清華大學出版社，2005.

［3］Daniel Solis.C#圖解教程：人們郵電出版社，2008.

Single Linked List;Dynamic Demonstration;C#;Multi-thread

Design and Implementation of Dynamic Demo System of Single Linked List

XIE Jia，XU Yong，LIANG Hou-jun
（Department of Computer Science&Technology，Anhui University of Finance&Economics，Bengbu 233030）

1007-1423（2015）28-0061-05

10.3969/j.issn.1007-1423.2015.28.015

徐勇（1978-），男，博士，教授，碩士生導師，研究方向為社會計算、信息安全、數(shù)據(jù)挖掘

梁后軍（1979-），男，博士，副教授，研究方向為計算機網(wǎng)絡

2015-08-04

2015-09-26

介紹了在.NET平臺下，使用C#語言開發(fā)關于單鏈表算法的動態(tài)演示系統(tǒng)，算法包括單鏈表的插入與刪除。核心部分使用了多線程技術。

單鏈表；動態(tài)演示；C#；多線程

安徽財經大學教研項目（No.acjyzd201433）、國家社科基金規(guī)劃項目（No.15BTQ043）、教育部人文社會科學研究基金面上項目（No.12YJA630136）、安徽省自然科學基金面上項目（No.1408085MF127）、安徽省高校省級優(yōu)秀青年人才基金重點項目（No.2013SQRL031ZD）、安徽財經大學學科特區(qū)“企業(yè)信息管理與數(shù)據(jù)挖掘”建設項目資助

謝嘉（1994-），本科生

Introduces the dynamic demonstration system of single linked list algorithm based on.NET platform，including insertion and deletion of single linked list.The core technology of the system is multi-thread technology.