謝嘉，徐勇，梁后軍

（安徽財(cái)經(jīng)大學(xué)計(jì)算機(jī)系，蚌埠　233030）

單鏈表算法的動(dòng)態(tài)演示系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)

謝嘉，徐勇，梁后軍

（安徽財(cái)經(jīng)大學(xué)計(jì)算機(jī)系，蚌埠233030）

0　引言

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

1　系統(tǒng)設(shè)計(jì)

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

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

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

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

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

2　系統(tǒng)設(shè)計(jì)

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

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

該系統(tǒng)采用了面向?qū)ο蟮乃枷?，封裝了多個(gè)類。下面詳細(xì)介紹使用的類。

（1）定義被演示的數(shù)據(jù)結(jié)構(gòu)所需的對(duì)象類

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

（2）自定義子線程類

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

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

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

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

［1］羅福強(qiáng)，楊劍，張敏輝.C#程序設(shè)計(jì)經(jīng)典教程［M］.北京：清華大學(xué)出版社，2012.

［2］嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京：清華大學(xué)出版社，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-），男，博士，教授，碩士生導(dǎo)師，研究方向?yàn)樯鐣?huì)計(jì)算、信息安全、數(shù)據(jù)挖掘

梁后軍（1979-），男，博士，副教授，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)

2015-08-04

2015-09-26

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

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

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

謝嘉（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.