數(shù)據結構經典算法演示系統(tǒng)論文

1、摘要本文所涉及的應用程序作為多媒體課堂教學的輔助工具，為數(shù)據結構課程的算法演示課件，旨在增加課堂教學手段的多樣性和教學的生動性。本軟件是為了豐富課堂教學手段，提高數(shù)據結構教學質量而開發(fā)的。它包括數(shù)據結構一書中的幾個經典算法。是在Microsoft Visual C+ 2003環(huán)境下開發(fā)的。它為數(shù)據結構課程中幾個經典算法提供一種形象的動畫表達方式。本文從總體出發(fā)，逐步細化，介紹了該軟件的設計、開發(fā)的基本情況。并帶有相應的截圖和一些典型源代碼，以方便說明和理解。關鍵詞：多媒體課件，數(shù)據結構課程，VCABSTRACTThe application program referred in this p

2、aper is an assistant implement for multimedia class. Its an arithmetic_demonstrate_application for Data Structure. The purpose of this application program is to offer more teaching instrumentality and make the process of teaching much more vivid. This application program is being designed to offer m

3、ore teaching instrumentality, and the exaltation data structure teaching quality. It has several famous arithmetic of Data Structure. And the tool of exploitation is Microsoft Visual C+ 2003.This application can offer a kind of way that can bring forth that arithmetic vividly. Its begun with collect

4、ivity, and then introduces the basic cases of design and exploitation for this software bit by bit imperceptibly. There are some pictures of the application and some typical code to explain the application in this paper, too.Keywords: multimedia courseware, data structure course, VC目錄 TOC o 1-3 h z

5、u HYPERLINK l _Toc169519283 摘要 PAGEREF _Toc169519283 h I HYPERLINK l _Toc169519284 ABSTRACT PAGEREF _Toc169519284 h II HYPERLINK l _Toc169519285 第1章 緒論 PAGEREF _Toc169519285 h 1 HYPERLINK l _Toc169519286 1.1 開發(fā)演示系統(tǒng)的背景 PAGEREF _Toc169519286 h 1 HYPERLINK l _Toc169519287 1.2 數(shù)據結構經典算法演示系統(tǒng)的研究內容 PAGEREF

6、_Toc169519287 h 2 HYPERLINK l _Toc169519288 1.3 開發(fā)該系統(tǒng)的可行性 PAGEREF _Toc169519288 h 2 HYPERLINK l _Toc169519289 1.4 演示系統(tǒng)在教學中的優(yōu)點 PAGEREF _Toc169519289 h 3 HYPERLINK l _Toc169519290 第2章 系統(tǒng)概述及開發(fā)工具 PAGEREF _Toc169519290 h 4 HYPERLINK l _Toc169519291 2.1 演示系統(tǒng)設計要求 PAGEREF _Toc169519291 h 4 HYPERLINK l _Toc1

7、69519292 2.2演示系統(tǒng)的需求分析 PAGEREF _Toc169519292 h 4 HYPERLINK l _Toc169519293 2.2.1 應用對象 PAGEREF _Toc169519293 h 5 HYPERLINK l _Toc169519294 2.2.2 應用環(huán)境 PAGEREF _Toc169519294 h 5 HYPERLINK l _Toc169519295 2.2.3 任務分析 PAGEREF _Toc169519295 h 5 HYPERLINK l _Toc169519296 2.3 演示系統(tǒng)總體規(guī)劃 PAGEREF _Toc169519296 h

8、6 HYPERLINK l _Toc169519297 2.3.1 開發(fā)過程應遵循的要求 PAGEREF _Toc169519297 h 6 HYPERLINK l _Toc169519298 2.3.2 系統(tǒng)組成 PAGEREF _Toc169519298 h 7 HYPERLINK l _Toc169519299 2.3.3 功能要求 PAGEREF _Toc169519299 h 7 HYPERLINK l _Toc169519300 2.4 選用MFC進行系統(tǒng)開發(fā) PAGEREF _Toc169519300 h 8 HYPERLINK l _Toc169519301 2.5 本章小結

9、PAGEREF _Toc169519301 h 9 HYPERLINK l _Toc169519302 第3章 演示系統(tǒng)設計 PAGEREF _Toc169519302 h 10 HYPERLINK l _Toc169519303 3.1 系統(tǒng)組成 PAGEREF _Toc169519303 h 10 HYPERLINK l _Toc169519304 3.2 各個功能模塊的要求 PAGEREF _Toc169519304 h 11 HYPERLINK l _Toc169519305 3.2.1 主界面功能要求 PAGEREF _Toc169519305 h 11 HYPERLINK l _T

10、oc169519306 3.2.2 表與棧 PAGEREF _Toc169519306 h 11 HYPERLINK l _Toc169519307 3.2.3 棧的遞歸過程漢諾塔 PAGEREF _Toc169519307 h 12 HYPERLINK l _Toc169519308 3.2.4 最短路徑 PAGEREF _Toc169519308 h 13 HYPERLINK l _Toc169519309 3.3 本章小結 PAGEREF _Toc169519309 h 14 HYPERLINK l _Toc169519310 第4章 演示系統(tǒng)實現(xiàn) PAGEREF _Toc1695193

11、10 h 15 HYPERLINK l _Toc169519311 4.1 系統(tǒng)框架的實現(xiàn) PAGEREF _Toc169519311 h 15 HYPERLINK l _Toc169519312 4.2 順序表演示模塊的實現(xiàn) PAGEREF _Toc169519312 h 17 HYPERLINK l _Toc169519313 4.2.1 設計思想 PAGEREF _Toc169519313 h 17 HYPERLINK l _Toc169519314 4.2.2 算法演示流程圖 PAGEREF _Toc169519314 h 18 HYPERLINK l _Toc169519315 4.

12、2.3 關鍵技術的實現(xiàn) PAGEREF _Toc169519315 h 18 HYPERLINK l _Toc169519316 4.3 鏈表演示模塊的實現(xiàn) PAGEREF _Toc169519316 h 21 HYPERLINK l _Toc169519317 4.3.1 設計思想 PAGEREF _Toc169519317 h 21 HYPERLINK l _Toc169519318 4.3.2 成品展示 PAGEREF _Toc169519318 h 21 HYPERLINK l _Toc169519319 4.4 漢諾塔演示模塊的實現(xiàn) PAGEREF _Toc169519319 h 2

13、2 HYPERLINK l _Toc169519320 4.4.1 設計思想 PAGEREF _Toc169519320 h 22 HYPERLINK l _Toc169519321 4.4.2 用遞歸互換法解決漢諾塔問題的流程圖 PAGEREF _Toc169519321 h 24 HYPERLINK l _Toc169519322 4.4.3 關鍵代碼展示 PAGEREF _Toc169519322 h 25 HYPERLINK l _Toc169519323 4.4.4 成品展示 PAGEREF _Toc169519323 h 28 HYPERLINK l _Toc169519324 4

14、.5 最短路徑演示模塊的實現(xiàn) PAGEREF _Toc169519324 h 30 HYPERLINK l _Toc169519325 4.5.1 設計思想 PAGEREF _Toc169519325 h 30 HYPERLINK l _Toc169519326 4.5.2 算法演示流程圖 PAGEREF _Toc169519326 h 32 HYPERLINK l _Toc169519327 4.5.3 關鍵代碼展示 PAGEREF _Toc169519327 h 33 HYPERLINK l _Toc169519328 4.5.4 成品展示 PAGEREF _Toc169519328 h

15、35 HYPERLINK l _Toc169519329 4.6 系統(tǒng)模塊間的聯(lián)系 PAGEREF _Toc169519329 h 37 HYPERLINK l _Toc169519330 4.7 本章小結 PAGEREF _Toc169519330 h 37 HYPERLINK l _Toc169519331 第5章 結論 PAGEREF _Toc169519331 h 38 HYPERLINK l _Toc169519332 致謝 PAGEREF _Toc169519332 h 39 HYPERLINK l _Toc169519333 參考文獻 PAGEREF _Toc169519333

16、h 40 HYPERLINK l _Toc169519334 附錄 PAGEREF _Toc169519334 h 41第1章 緒論數(shù)據結構是計算機科學與技術專業(yè)的核心基礎課程之一。但是它概念抽象，算法枯澀難懂，難以提起學生的學習興趣。如何有效的讓學生掌握該課程是一個值得研究的問題。計算機輔助教學（CAI）作為一種先進的教學手段正逐步滲透到各類學校的各個學科，多媒體技術給CAI注入了新的活力。由于多媒體技術能夠綜合處理文本、圖像、動畫、音頻、視頻等多種媒體, 并通過視覺、聽覺對人體產生多重感官刺激, 從而使學生在較短的時間內獲得較多的信息量。本文重點介紹如何用MFC開發(fā)的幾個數(shù)據結構經典算法的

17、演示系統(tǒng)（下文簡稱為演示系統(tǒng)），并討論實現(xiàn)中的一些關鍵技術。 開發(fā)演示系統(tǒng)的背景數(shù)據結構是計算機相關專業(yè)的一門重要的專業(yè)基礎課。它主要研究計算機加工對象的邏輯結構、數(shù)據在計算機中的表示形式以及實現(xiàn)各種基本操作的算法，該課程在計算機科學與技術的專業(yè)教學中的地位可用四個詞概括：核心、基礎、紐帶、橋梁?！昂诵摹奔粗高@門課在計算機專業(yè)中占有非常重要的地位，是一門核心基礎課。數(shù)據是計算機處理的對象，使用計算機就是對數(shù)據進行加工處理的過程，因而數(shù)據的組織與結構被確立為計算機科學中最為基本的內容。數(shù)據結構課程以問題求解方法、程序設計方法及一些典型的數(shù)據結構算法為研究對象，要求學生學會分析數(shù)據對象特征，掌握數(shù)

18、據組織方法和計算機的表示方法，為數(shù)據選擇適當?shù)倪壿嫿Y構、存儲結構以及相應的處理算法，培養(yǎng)學生良好的程序設計風格，因而數(shù)據結構課程是計算機專業(yè)的一門核心課程?！盎A”指該課程為后續(xù)多門計算機專業(yè)課提供了必要的基礎。如操作系統(tǒng)、數(shù)據庫原理、編譯原理、算法分析與設計、軟件工程、計算機網絡、人工智能等都需要數(shù)據結構作為課程的基礎；同時這門課又是橫貫數(shù)學與計算機、計算機硬件與軟件并將數(shù)學與計算機、計算機軟件與硬件有機的融合在一起的一門學科，是將計算機理論與上機實踐融合在一起的一門學科，是它們之間的“紐帶”。沒有它作為基礎，后繼大部分課程將不能展開，也就是說。這門課程是通往其它課程的一座“橋梁”。因此大力

19、加強數(shù)據結構課程的建設，提高數(shù)據結構課程的教學質量，有利于教學改革和教育創(chuàng)新，有利于創(chuàng)新人才的培養(yǎng)。努力提高數(shù)據結構課程的教學質量，對于新一輪的以創(chuàng)新教育和素質教育為主要內容的教學改革將起到積極的推進和示范作用。1.2 數(shù)據結構經典算法演示系統(tǒng)的研究內容為了適應課堂教學的要求，數(shù)據結構經典算法演示系統(tǒng)應該具有：（1）軟件界面的設計要求：較強的交互能力、動態(tài)的算法演示、形象的圖形設計、充分應用聲音和色彩體現(xiàn)算法的細節(jié)、屏幕設計簡潔明快、屏幕元素布局合理、突出教學內容的重點等等；（2）軟件中不僅包含主要的教學內容，而且還應提供一些特殊例題的算法演示，用以擴大學生的編程思維能力，從而實現(xiàn)用形象的圖形

20、界面為學生搭起通向掌握抽象思維方法的橋梁；（3）軟件中通過圖形演繹出來的所有算法思想必須準確；（4）操作簡單，易于理解，符合Windows的操作規(guī)則，便于使用；（5）軟件在設計開發(fā)過程中具有自身的規(guī)范，而對于教學軟件來說，設計開發(fā)者應該在遵循一般規(guī)范的基礎上，深入研究學與教的原理，在有關科學理論指導下設計開發(fā)教學軟件。1.3 開發(fā)該系統(tǒng)的可行性傳統(tǒng)教學模式注重基礎知識理論的掌握。用大量的時問講定義、語法、概念語句，對學生的要求是注重接受、理解、記憶，講課方式是老師講、學生聽。學生掌握的知識比較抽象、機械、靜止、片面和孤立，缺乏創(chuàng)造性，嚴重影響了學生就業(yè)和個人發(fā)展。因此使當前的大學生具備扎實基礎

21、知識的同時又具備解決實際問題、批判性思維和創(chuàng)造性思維，發(fā)展合作能力與自主學習能力，是目前急待解決的問題，也是人們進行教學改革的思路。 在教學過程中的具體做法是：開始上課時演示一個精心設計的、 吸引學生注意并包含當天上課新內容的運行結果。這個過程實際上也就是向學生提出了一個新的問題。給學生一定的時間去思考，然后在講授?；蛘呤橇粝聠栴}讓同學們在課下去想辦法解決然后在上機時實現(xiàn)。這樣一步一步地分析問題解決問題拓展問題有助于促進學生創(chuàng)造性思維的形成。1.4 演示系統(tǒng)在教學中的優(yōu)點（1）可視化教學軟件不像教材那樣枯燥乏味，教師可以利用它來吸引學生的注意力；（2）可視化教學軟件可將文字、數(shù)據、圖片、影片動

22、態(tài)地整合在一起；（3）可視化教學軟件可以讓學生體會在大量不同的數(shù)據結構下，算法執(zhí)行效率的差異；（4）學生在課后可利用可視化教學軟件探索算法的執(zhí)行過程，提高學生個別化學習能力；（5）加強刺激，加深印象。第2章 系統(tǒng)概述及開發(fā)工具數(shù)據結構幾個經典算法的演示系統(tǒng)作為一個教學軟件，要求界面清新簡單，可操作性強，與使用者的操作系統(tǒng)兼容性強。本軟件是在Windows XP操作系統(tǒng)下用MFC開發(fā)的，可在裝有VC+（2003版）的使用Windows XP操作系統(tǒng)的電腦上使用。 演示系統(tǒng)設計要求算法演示軟件服務于教學目的，其設計目標是通過演示以最大限度地幫助學習者理解算法，并掌握其實質。演示內容包括：程序的運行

23、過程、數(shù)據結構的變化及一些動態(tài)結果。其是一個可視化軟件。開發(fā)數(shù)據結構幾個經典算法的演示系統(tǒng)的過程包括五個基本的步驟：需求分析、設計、制作、成品使用、評價和修改。其工作流程如圖2-1所示。評價和修改設 計教學目標教學內容教學策略結構設計腳本編寫制作工具選擇素材準備開發(fā)實施成品使用需求分析應用對象應用環(huán)境任務分析圖2-1數(shù)據結構幾個經典算法演示系統(tǒng)的開發(fā)過程演示系統(tǒng)的需求分析需求分析就是分析軟件用戶的需求是什么。如果投入大量的人力、物力、財力和時間開發(fā)出的軟件卻沒人要，那所有的投入都是徒勞。如果費了很大的精力，開發(fā)一個軟件，最后卻不滿足用戶的要求，從而要重新開發(fā)過，這種返工是讓人痛心疾首的。需求分

24、析之所以重要，就因為他具有決策性，方向性，策略性的作用，他在軟件開發(fā)的過程中具有舉足輕重的地位。大家一定要對需求分析具有足夠的重視。在一個大型 HYPERLINK :/ itisedu /phrase/200602281706245.html t _new 軟件系統(tǒng)的開發(fā)中，它的作用要遠遠大于 HYPERLINK :/ itisedu /phrase/200602281641255.html t _new 程序代碼的編寫。 應用對象在第一章已經講過的數(shù)據結構教學中的困難中可以看出，教學活動需要注入新活力，使用演示系統(tǒng)輔助教學是很好的選擇，也就是說它有應用前景，由老師利用該演示系統(tǒng)指導學生學習數(shù)

25、據結構或者學生利用該演示系統(tǒng)自主復習數(shù)據結構。它的應用對象是學習數(shù)據結構的學生。數(shù)據結構的概念晦澀難懂，尤其是在當今學生學習主動性不是很好的環(huán)境下，學生就很難掌握該課程了。有的時候直觀的演示可能比詳盡的概念解釋更易讓學生學習到知識。數(shù)據結構幾個經典算法的演示系統(tǒng)大致能滿足教師授課的需要，給學生以直觀的教學印象，讓學生清楚的知道數(shù)據怎么變化的，調動學生學習的積極性。不過該系統(tǒng)不是完善的，只有有限的幾個算法演示。開發(fā)該系統(tǒng)只希望能起到拋磚引玉的作用，給學生帶來一定的啟發(fā)。 應用環(huán)境開發(fā)該演示系統(tǒng)的目的是為了在教學中引入新的教學手段，調動學生學習積極性，提供教師授課的方便。該系統(tǒng)的是在Windows

26、 XP操作系統(tǒng)下實現(xiàn)的，這樣符合大多數(shù)教學所用的計算機所采用的系統(tǒng)，方便軟件在不同計算機之間的轉移。它可以是教師使用或者學生使用，軟件界面的簡單使得不同知識層次的人使用起來不會有麻煩。 任務分析使用該演示系統(tǒng)是為了促進學生對數(shù)據結構課程的理解，提高數(shù)據結構課程的教學質量。在現(xiàn)代化的教學過程中，由于多媒體輔助教學能夠化靜為動，寓教于樂，培養(yǎng)和激發(fā)學生的學習興趣；能使抽象問題形象化，便于學生對知識點的理解和運用；能節(jié)約傳統(tǒng)的板書時間，開闊知識面，增加信息量，提高學習效率，所以這種教學手段被廣泛采用。但是濫用多媒體輔助教學，不但不能達到預期的教學效果，反而會分散學生的注意力，削弱了教師在教學過程中應

27、起的主導作用，甚至影響學生的學習積極性。因此要注意怎么使用軟件。雖然教學課件已經事先做好，但不是說在課堂上教師只要在教師用機的位置上單純地“演示”課件就可以了，這樣可能會出現(xiàn)學生看了很多，聽了很多，卻不知道要學什么，而事與愿違。其實，多媒體輔助教學作為一種現(xiàn)代化的教學手段，是用來提高課堂教學的效率、突破重點難點、解決一些傳統(tǒng)教學不易解決的問題。教師應該憑自身豐富的教學經驗和生動的講解，通過師生間的情緒感染，來調動學生學習的積極性，并使學生能夠自覺的參與到新的教學當中去。另外，事先做好的課件靈活性可能較差，有時會限制教師的臨場發(fā)揮，這時就要求教師應積極有效地利用投影儀等現(xiàn)代媒體輔助教學，來解決這

28、個矛盾。2.3 演示系統(tǒng)總體規(guī)劃 開發(fā)過程應遵循的要求（1）符合一般環(huán)境需求?？梢暬浖南到y(tǒng)平臺必須符合學生一般常接觸的環(huán)境?，F(xiàn)在常見到的不外乎是Java Applet和應用軟件。對于Java Applet而言，是屬于客戶機/ 服務器架構。學生必須經由網絡的連接，將需求傳送至服務器端，然后才能執(zhí)行。如此，對于缺乏網絡或網絡不順暢的教學環(huán)境而言，就容易受到限制。對于應用軟件而言，要求系統(tǒng)簡潔，小巧便于移動。（2）界面設計的便利性。在有限時間內，學生不應花費太多的時間去摸索復雜困難的學生界面。所以在接口設計上，必須以學生操作方便為原則。（3）提供學生輸入數(shù)據。當學生初次使用可視化軟件時，系統(tǒng)必須

29、告知其所接受的數(shù)據形態(tài)和范圍。如利用系統(tǒng)自行產生數(shù)據的功能，讓學生便于執(zhí)行算法。如此可以鼓勵學生主動去探索各種情況下算法的執(zhí)行效率。（4）學生控制。不同的學生，其吸收知識的速度不一定相同。因而，讓學生自行掌握學習的速度是有必要的。在可視化軟件中可提供調整動畫執(zhí)行過程的延遲時間，或是利用單步執(zhí)行按鍵，讓學生自行控制學習速度。此外還原鍵也是讓學生往回追溯不懂之處的重要按鍵之一。（5）算法的全貌瀏覽。當學生想快速觀看算法的部分片段時，提供快速執(zhí)行功能是有其必要性的。學生可直接執(zhí)行算法的某一時點，或大略觀看演算法的執(zhí)行全貌。（6）提供偽碼的對照。單純展示算法執(zhí)行過程，只能讓學生在算法程序上有所了解。若

30、要讓學生在概念上更加清楚，則提供算法的偽碼是一個好方法。（7）相關輔助信息。例如對于不熟悉算法的學生而言，可提供相關的背景數(shù)據與算法所要達成的目標。2.3.2 系統(tǒng)組成演示系統(tǒng)包含教五個教學單元：順序表的插入和刪除、鏈表的插入、棧的遞歸過程漢諾塔、最短路徑。每個單元的內容相互獨立，并由主菜單調入。每個單元都有各自的功能，可由主菜單進入各個獨立單元。系統(tǒng)的總體框架如下圖2-2。順序表鏈表棧最短路徑插入刪除插入漢諾塔迪杰斯特拉歡迎界面圖2-2 演示系統(tǒng)總體框架2.3.3 功能要求（1）用動態(tài)圖形對數(shù)據結構中如: 線形表的插入刪除算法、漢諾塔及最短路徑問題進行了形象直觀、準確生動的演示。能夠很好地幫

31、助學生深入理解算法，有利于培養(yǎng)學生的抽象能力；（2）系統(tǒng)控制能力強, 具有暫停、重復和恢復等功能；（3）良好的操作界面, 同時支持鍵盤和鼠標, 操作簡單。菜單提示, 可點對象醒目；（4）軟件腳本根據由嚴蔚敏編著的國優(yōu)教材數(shù)據結構一書編寫的。內容編排合理, 教學功能強；（5）交互性強。系統(tǒng)中使用的大部分參數(shù)可由使用者自行設置。學習內容及學習進度也可由使用者自行選擇；（6）系統(tǒng)采用模塊化結構, 可維護性強。2.4 選用MFC進行系統(tǒng)開發(fā)該演示系統(tǒng)使用了大量的視圖界面作為演示系統(tǒng)的操作界面，而且演示系統(tǒng)為了用戶的使用方便采取的是基于對話框的結構構架，利用微軟基本類庫MFC（Microsoft Fou

32、ndation Class）能夠很好的開發(fā)出符合這種需要的軟件，因此選擇使用MFC以及Visual C+開發(fā)系統(tǒng)來編寫自己的基于Windows 的應用程序。MFC提供了很多的圖形控件，可以比較方便的設計出算法演示系統(tǒng)的界面。MFC是微軟為Windows 程序員提供的一個面向對象的Windows 編程接口, 它大大簡化了Windows 編程工作。該層次結構包容了Windows API 中的用戶界面部分, 并使程序員能夠很容易地以面向對象的方式建立Windows 應用程序。這種層次結構適用于所有版本的Windows , 并彼此兼容。基礎類庫的核心是以C + + 形式封裝了大部分的Windows A

33、PI。類庫表示窗口, 對話框, 設備上下文, 公共GDI 對象如畫筆、調色板、控制框和其他標準的Windows 部件。這些類提供了一個面向Windows 中結構的簡單的C + + 成員函數(shù)的接口。MFC的本質就是一個包含了許多微軟公司已經定義好的對象的類庫，我們知道，雖然我們要編寫的程序在功能上是千差萬別的，但從本質上來講，都可以化歸為用戶界面的設計，對文件的操作，多媒體的使用，數(shù)據庫的訪問等等一些最主要的方面。這一點正是微軟提供MFC類庫最重要的原因，在這個類庫中包含了一百多個程序開發(fā)過程中最常用到的對象。在進行程序設計的時候，如果類庫中的某個對象能完成所需要的功能，這時我們只要簡單地調用已

34、有對象的方法就可以了。我們還可以利用面向對象技術中很重要的“繼承”方法從類庫中的已有對象派生出我們自己的對象，這時派生出來的對象除了具有類庫中的對象的特性和功能之外，還可以由我們自己根據需要加上所需的特性和方法，產生一個更專門的，功能更為強大的對象。當然，你也可以在程序中創(chuàng)建全新的對象，并根據需要不斷完善對象的功能。正是由于MFC編程方法充分利用了面向對象技術的優(yōu)點，它使得我們編程時極少需要關心對象方法的實現(xiàn)細節(jié)，同時類庫中的各種對象的強大功能足以完成我們程序中的絕大部分所需功能，這使得應用程序中程序員所需要編寫的代碼大為減少，有力地保證了程序的良好的可調試性。最后要指出的是MFC類庫在提供的

35、對象的各種屬性和方法都是經過謹慎的編寫和嚴格的測試，可靠性很高，這就保證了使用MFC類庫不會影響程序的可靠性和正確性。2.5 本章小結本章是對系統(tǒng)的概述以及開發(fā)工具的介紹。詳細說明了系統(tǒng)的需求分析。系統(tǒng)是在Windows XP系統(tǒng)下使用MFC構架的，并說明了使用MFC構架系統(tǒng)的優(yōu)越性。第3章 演示系統(tǒng)設計一個好的計算機應用軟件，都是經過程序員冷靜的思考，詳盡的分析而產生的。設計遠比編程重要。設計的過程就是將事務處理抽象成計算機模型的過程。本章詳細的介紹演示系統(tǒng)的系統(tǒng)組成與各個功能模塊的要求。3.1 系統(tǒng)組成該演示系統(tǒng)是幾個經典數(shù)據結構算法的演示系統(tǒng)。這幾個經典算法分別是順序表的插入、刪除算法，

36、鏈表的插入算法，棧的遞歸過程中的漢諾塔，使用迪杰斯特拉算法求最短路徑。系統(tǒng)設計圖如下圖3-1所示。由圖3-1可以看到，系統(tǒng)設計是采用模塊化思想，這樣每個算法之間都是獨立的，便于系統(tǒng)維護，也便于以后再向里面添加新的算法。每個算法演示下面都有其詳細的操作界面。以順序表插入為例子，它的具體設計思想如下圖3-2所示。其他各個算法的演示大致和順序表插入算法相同，有方便的操作，動態(tài)的圖形演示和跟隨程序運行的偽代碼。歡迎界面線性表鏈表棧最短路徑順序表插入順序表刪除返回鏈表刪除返回漢諾塔返回最短路徑返回圖3-1演示系統(tǒng)總體設計順序表的插入操作模塊演示模塊算法說明圖形演示偽代碼暫停返回單步執(zhí)行恢復插入元素輸入數(shù)

37、據圖3-2順序表插入算法演示模塊3.2 各個功能模塊的要求3.2.1 主界面功能要求主界面是一個選擇界面，它們的功能是轉到下一個界面。(1)順序表:它的作用是轉到順序表插入刪除算法選擇界面。(2)鏈表:它的作用是轉到鏈表插入算法選擇界面。(3)棧:它的作用是轉到漢諾塔算法選擇界面。(4)最短路徑:它的作用是轉到迪杰斯特拉算法選擇界面。二級界面同樣是一個選擇界面，它們的功能是轉到相應算法演示界面。它們的要求如附錄。3.2.2 表與棧該演示系統(tǒng)演示算法中有關表的演示有兩個：順序表和鏈表。它們都是數(shù)據結構課程的基本知識，在實際中也有很廣的用途。算法說明：對演示算法的說明，該系統(tǒng)的教學對象對算法概念不

38、清楚時可以查看，或者讓初學者知道該算法是怎么樣的。因此算法說明應該能清楚的表明算法的思想。輸入數(shù)據：輸入數(shù)據就是向系統(tǒng)中寫入數(shù)據，為演示做好準備。輸入數(shù)據時彈出一個對話框，在指定地方輸入數(shù)據，并且有說明什么樣的數(shù)據是系統(tǒng)允許的。輸入非法數(shù)據時系統(tǒng)將不能接受或者彈出錯誤提示。插入元素：該功能允許用戶輸入要插入的元素，并把要插入的位置表示出來。同樣的，系統(tǒng)對插入的元素有要求，當輸入非法時將不能把數(shù)據寫入系統(tǒng)。（順序表中插入位置不能為負數(shù)。）恢復：在演示完成后如果用戶想要再進行一次演示或者演示途中想重新看的時候，可以用這個功能來把數(shù)據恢復到演示之前的狀態(tài)，即輸入元素和插入元素之后的狀態(tài)。執(zhí)行：在輸入

39、數(shù)據和插入元素步驟之后，可以使用該功能來進行算法的演示。它將在算法演示完成后停下來，并且有提示算法演示完成了。單步：為了教學的方便，設置了這個單步功能。它可以使程序一個語句一個語句的執(zhí)行，類似看電影中的慢鏡頭，可以讓學習者更清楚的看到程序執(zhí)行的過程。它需要操作者手動點擊，點擊一次執(zhí)行一次該功能。暫停：該功能是能夠讓使用者在程序執(zhí)行過程中把程序停下來。對學習者尤其有用，當遇到不太了解的地方時，可以把程序停下來仔細揣摩。當想要繼續(xù)演示下去時，可以點擊執(zhí)行來繼續(xù)操作。返回：該功能是把算法演示界面返回到上一個選擇界面。圖形演示：在輸入數(shù)據后演示模塊就把數(shù)據生成一個順序表，插入的數(shù)據在順序表上方顯示。在

40、元素移動時以閃爍的箭頭表示移動方向。而后元素移動到相應位置。 這個功能是在一個系統(tǒng)分配固定的范圍執(zhí)行的，因此對要演示的數(shù)據有要求，即輸入的數(shù)據長度不能超出它的范圍。偽代碼：偽代碼是便于學習者理解算法的，它在學習中被廣泛應用。本演示系統(tǒng)使用的偽代碼和數(shù)據結構（嚴蔚敏）版一書很貼切，體現(xiàn)了為教學而制作軟件的目的。在程序執(zhí)行時，該偽代碼以紅色顯示正在執(zhí)行的語句，提示醒目方便學習。3.2.3 棧的遞歸過程漢諾塔漢諾塔演示模塊設計為四個不分，因為對它的演示比對線性表的演示要復雜。它采用遞歸互換法來解決漢諾塔問題。功能設計如下圖3-3。漢諾塔操作模塊演示模塊圖形演示偽代碼棧地址展示步驟展示返回單步暫停執(zhí)行

41、恢復輸入數(shù)據算法說明圖3-3 漢諾塔演示模塊同順序表算法中相同功能就不重復敘述了，下面著重介紹不同的地方。輸入數(shù)據：漢諾塔的輸入數(shù)據是要求輸入演示盤子的個數(shù)。這個數(shù)據的輸入依然有限制，限制輸入自然數(shù)在12以內。圖形演示：漢諾塔的圖形演示包括基座和盤子的顯示?；话愠尸F(xiàn)的是倒T型圖形。盤子以黑色矩形圖形表示，矩形按從小到大表示盤子的順序。步驟展示：漢諾塔演示中，當盤子數(shù)目稍多時，盤子的移動步驟是相當復雜的。這個時候僅僅觀看圖形的移動很可能記不清盤子到底是怎么移動的。該功能就是記錄盤子的移動步驟，使用戶及其對象能對照步驟加深對漢諾塔的理解。棧地址展示：該功能是展示漢諾塔演示時，代表盤子的數(shù)據在棧

42、中的地址。從表面到深入了解數(shù)據的變化。3.2.4 最短路徑它與表的演示有所不同。本演示系統(tǒng)是使用迪杰斯特拉算法求最短路徑，這個算法注重的是算法的思想。它求解從原點出發(fā)的各有向路徑的從小到大的排列，但是算法最終確實得到了從原點到圖中其余各點的最短路徑，可以說這是個副產品，對于算法的終結條件也應該以求得了原點到圖中其余各點的最短路徑為宜。清楚了算法的這種巧妙構思后，理解算法本身就不是難題了。它比表的功能多了幾個：新建節(jié)點：這個同表的輸入數(shù)據，但由于這是圖的演示，輸入數(shù)據變成了建節(jié)點。該功能允許用戶在演示模塊上建立節(jié)點。在創(chuàng)建過程中節(jié)點可以按用戶心意隨意移動。添加線：圖的節(jié)點之間需要線來連接，這種線

43、是有向線段。連接好節(jié)點之后可以鼠標雙擊連線，在彈出的對話框填寫權值，這個權值也是有要求的。當節(jié)點移動時，連線的連接兩節(jié)點的作用并沒有消失。創(chuàng)建結束：當節(jié)點和連線好了之后，確人不需要修改之后可以點擊此鍵準備演示，該功能執(zhí)行后，節(jié)點和權值將不能再進行修改。設置起點：該算法實際上是求出起點到各個節(jié)點的最短路徑，在本小節(jié)開頭已經說過，兩點之間的最短路徑只是這個算法的副產物。設置起點能夠指定一個節(jié)點作為該部分演示的原點。設置了起點后就可以開始演示了。演示模塊：這個演示界面中，矩形框架里面是圖的數(shù)據。路徑是起點到各個節(jié)點之間的最短路徑，如果沒有，則顯示沒有路徑。3.3 本章小結 本章是對演示系統(tǒng)的總體規(guī)劃

44、和各個功能模塊的要求說明。介紹了系統(tǒng)的組成部分，并分模塊的詳細介紹了各個模塊的功能要求。第4章 演示系統(tǒng)實現(xiàn)基于Windows XP操作系統(tǒng)的數(shù)據結構幾個經典算法的演示系統(tǒng)是用MFC制作的，它是單文檔多視圖結構。本系統(tǒng)作為教學軟件，設計時充分考慮了軟件的適用性和風格，它簡單易用，交互性強。本演示系統(tǒng)，從以下幾個方面一步步達到第三章提出的設計要求：(1)主體歡迎界面(2)選擇算法界面(3)順序表演示界面(4)鏈表演示界面(5)漢諾塔演示界面(6)最短路徑演示界面4.1 系統(tǒng)框架的實現(xiàn)該系統(tǒng)是基于單文檔多視圖結構構架的，通過發(fā)送消息來實現(xiàn)各個界面之間的轉換?？梢杂锰砑淤Y源功能制作一個基本的視圖，然

45、后在上面加上各種控件，再對各個控件做細化處理。如下圖4-1。同樣的，先把所有的界面都這樣的畫出來，但是這樣的界面都是孤立的，它們之間沒有任何關系。每個單獨的界面里面也沒有填寫程序。這只是做一個框架出來。然后就要對界面進行處理。在大多數(shù)的界面設計中，并不是所有元素都具有相同的重要性，精心設計將保證較重要的元素對用戶來說處在一目了然的位置。重要的和需要經常訪問的元素應當處于顯著的位置，次要的元素應處于次要的位置。我們習慣的閱讀順序一般是從左到右，從上到下。可以說，用戶第一看到的是屏幕的左上部分，因此，主要的元素應放在這里，而類似“確定”、“下一步”之類的按鍵則應處于屏幕的右下方，因為用戶通常是在完

46、成了整個窗口的工作后才訪問它們3。最后形成的主界面如下圖4-2所示：它有一個說明和四個主按鍵，通過它們就可以使用到這個演示系統(tǒng)的全部功能。而且它的界面簡單清新，也可以為以后向里面添加新的算法做好準備。圖4-1添加資源圖4-2是主選擇界面，圖4-3是第二級選擇界面。它們之間的轉化是通過一個消息函數(shù)來實現(xiàn)的。其代碼如下：void CViewHello:OnBnClickedButton2()/ TODO: 在此添加控件通知處理程序代碼this-GetParent()-SendMessage(WM_DLF_SHOW_VIEW,IDD_FORMVIEW_DIJKSTRA);消息發(fā)送后，系統(tǒng)就重畫視圖，

47、如圖4-3視覺上的效果就是從圖4-2界面轉到了圖4-3界面。演示系統(tǒng)的退出可以通過點對話框右上的來實現(xiàn)。 圖4-2完成后的主界面圖4-3最短路徑選擇算法界面4.2 順序表演示模塊的實現(xiàn)4.2.1 設計思想順序表算法演示模塊有兩個部分：順序表的插入和順序表的刪除。順序表的算法說明：線形表的順序存儲結構中，由于邏輯上相鄰的數(shù)據元素在物理位置上也相鄰，因此，除非插入位置I的值等于表長加1（即插入表尾之后），否則都必須移動元素才能反映這個邏輯關系的變化。一般情況下，在第I（0=In?I=I+1I=1, B(I)=13=1 打印B(J) J=1, ,2n-1終止圖4-10 用遞歸互換法實現(xiàn)n個盤子的移動

48、 關鍵代碼展示演示模塊的關鍵技術在順序表中已經詳細說明了。本演示系統(tǒng)在四大模塊的設計上所用的關鍵技術都和類似，因此這里就不重復敘述這些關鍵技術的實現(xiàn)而是展示一些在漢諾塔演示模塊中實現(xiàn)這些關鍵技術的部分代碼。.1 繪制圖形在系統(tǒng)分配好的動畫演示區(qū)模塊中，由程序把該演示區(qū)長度等分為6個部分，在奇數(shù)等分地方即1，3，5等分地方畫2個矩形圖形。它們在視覺效果上一個為豎直的矩形一個為橫向的矩形，呈倒T狀。并且把它們填充成紫色矩形塊，用它們表示漢諾塔的基座x，y，z。表示盤子的圖形是黑色的矩形塊，它們是以紫色橫向矩形塊的上邊為最大的盤子與基座的接觸面，以豎直的紫色矩形塊為柱子(以它呈對稱狀)而繪制的。CR

49、ect rect;CString strTemp;GetClientRect(&rect);int x = rect.right;int y = rect.bottom;/繪制矩形rect.SetRect(x/6-10, 50, x/6+10, y-50);MemDC.FillRect(rect, &newBrush);rect.SetRect(x/6-50, y-50, x/6+50, y-70);MemDC.FillRect(rect, &newBrush);rect.SetRect(x/2-10, 50, x/2+10, y-50);MemDC.FillRect(rect, &newBr

50、ush);rect.SetRect(x/2-50, y-50, x/2+50, y-70);MemDC.FillRect(rect, &newBrush);rect.SetRect(x*5/6-10, 50, x*5/6+10, y-50);MemDC.FillRect(rect, &newBrush);rect.SetRect(x*5/6-50, y-50, x*5/6+50, y-70);MemDC.FillRect(rect, &newBrush);int heigh = y - 70;int step = 4;CBrush newBrush2;newBrush2.CreateSolid

51、Brush(RGB(0,50,105);if (mpArry != NULL)for (int i=0; iATotal; i+)rect.SetRect(x/6+step*mpArry-Ai, heigh-i*10, x/6-step*mpArry-Ai, heigh-i*10-9);MemDC.FillRect(rect, &newBrush2);for (int i=0; iBTotal; i+)rect.SetRect(x/2+step*mpArry-Bi, heigh-i*10,x/2-step*mpArry-Bi,heigh-i*10-9);MemDC.FillRect(rect,

52、 &newBrush2);for (int i=0; iCTotal; i+) rect.SetRect(x*5/6+step*mpArry-Ci, heigh-i*10, x*5/6-step*mpArry-Ci, heigh-i*10-9);MemDC.FillRect(rect, &newBrush2);.2 展示偽代碼前面說過，偽代碼展示區(qū)是基于List Control控件構架的。設計該模塊就是為了把偽代碼展示給學習者觀看，并且使偽代碼變紅顯示和動畫演示保持同步。for (int i=0; iCODE_LINES; i+)int line = mListSF.GetItemCount(

53、);mListSF.InsertItem(line, mExplaini);.3 恢復功能在算法演示過程中暫停，單步和演示完成狀態(tài)下，用戶可以把演示中變化了的數(shù)據恢復到剛輸入到演示系統(tǒng)的狀態(tài)。這個功能的實現(xiàn)原理是：在把數(shù)據輸入到系統(tǒng)中時，程序自動把輸入的數(shù)據備份。當使用恢復功能時，系統(tǒng)把備份的數(shù)據調出而實現(xiàn)對數(shù)據的恢復。mArry.Total = dlg.num;/保存漢諾塔的盤子數(shù)mArry.n = mArry.Total;/設置盤符(柱子)mArry.x = 1;mArry.y = 2;mArry.z = 3;mArry.ATotal = mArry.Total;/剛開始所有盤放在A柱/設

54、置多個盤子的大小for (int i=0; irectNodeMap.left)& (point.xrectNodeMap.top)& (point.yrectNodeMap.left)& (point.xrectNodeMap.top)& (point.yrectNodeMap.bottom)mNodeNum = -1;/調用函數(shù)判斷鼠標所在位置是否在節(jié)點上int k = mArry.ChickNode(point.x-rectNodeMap.left, point.y-rectNodeMap.top);if (kmArry.GetNodeFactCount()/在節(jié)點上，把節(jié)點編號保存在這

55、里mNodeNum = k;if (AddLineFlage = 1)/添加線狀態(tài)mLineNum = mArry.AddLine(mNodeNum); /判斷鼠標位置是否在節(jié)點上if (mLineNum = -1)/不在節(jié)點上，彈出消息MessageBox(無法連線，請先點中節(jié)點！);AddLineFlage = 0;SetStatus(Inition);4.5.4 成品展示畫圖區(qū)是為輸入數(shù)據做準備的。這個部分主要是能識別鼠標的信息。畫圖的很多地方都要通過鼠標來實現(xiàn)。當點擊新建節(jié)點時，激活了畫圖區(qū)的識別功能。鼠標在畫圖區(qū)點擊左鍵時，程序在這個點畫出一個圓點，并在上面標志為A，以此來表示節(jié)點的

56、順序。已經畫了一個節(jié)點之后，鼠標點在這個上面不放時，程序相應部分得以激活，這時可以在畫圖區(qū)拖動該節(jié)點移動到想要移動到的位置。連線的實現(xiàn)符合大多軟件的習慣。在連接兩個節(jié)點時，點擊一個節(jié)點不放移動鼠標，到達到另外一個節(jié)點時松開，連線就成立了。并且以有箭頭指向連線方向。如果點擊一個節(jié)點開始并不放鼠標左鍵移動到一個沒有節(jié)點的位置時放開鼠標，連線將不能被創(chuàng)建。這樣就保證了每條連線的可靠性。在靠近箭頭的位置上，每條連線都有一個小圓圈。這個圓圈是設置權值的標志位置，在鼠標雙擊該圓圈時，將會彈出一個對話框，在這個對話框輸入該條路徑的權值。在這些信息輸入同時，畫圖區(qū)右邊的矩陣顯示出各節(jié)點之間路徑的權值。其中負值

57、1表示沒有路徑。這些如下圖4-16。圖4-16 帶權有向圖G6的演示界面迪杰斯特拉算法求的是一個節(jié)點到其他各個節(jié)點間的最短路徑。因此，演示前，要設置一個起點。設置起點是由一個對話框實現(xiàn)的。在彈出的對話框輸入起點起點的標志符號。例如設置A節(jié)點為起點。在對話框中輸入大寫字母A。在設置完起點后，對演示的準備就完成了。可以點擊執(zhí)行來演示該算法。演示中會把該起點到其他各個節(jié)點的最短路徑在演示界面的左下方位置展示出來。有向圖G6的演示結果如下圖4-17。圖4-17向圖G6的演示結果4.6 系統(tǒng)模塊間的聯(lián)系該演示系統(tǒng)是應用模塊化思想構建的。每個模塊和總體框架都有其相似點。對一個系統(tǒng)的設計，一致性應該保持。這

58、個前面已經說過這樣設計軟件的優(yōu)點了。在該系統(tǒng)中，每個二級界面返回主歡迎界面所用的消息函數(shù)是一樣的。這是系統(tǒng)設計上的一致性。各個演示模塊所用背景圖片一致。這樣給用戶心理上帶來熟悉感。每個模塊演示完成時都會彈出顯示“演示完成”的對話框。4.7 本章小結 本章詳細的說明了數(shù)據結構幾個經典算法演示系統(tǒng)的各個功能模塊的實現(xiàn)思想與方法。以各種完成后的作品的截圖來說明系統(tǒng)達到的目標。并且介紹了在設計軟件中的一些優(yōu)秀思想。第5章 結論在本次畢業(yè)設計的過程中，通過指導老師的耐心指導和自身的學習及努力，對數(shù)據結構知識和教學軟件有了進一步的提高。在整個設計過程中深深地體會到要把所學的知識理論變成可實際應用的系統(tǒng)時所

59、面臨的種種困難，認識到提高運用知識、解決實際問題的能力是十分重要的。在該軟件的設計與實現(xiàn)過程中，有幾個方面是關鍵。首先是系統(tǒng)界面的清新簡單和各個模塊設計的一致性。其次是為教學效果而完成的一些功能的實現(xiàn)，比如對單步執(zhí)行程序的設計。再次，作為一個教學軟件，該系統(tǒng)所演示的幾個經典算法是不夠的，為了以后能夠添加其他的算法演示，采用模塊化設計思想。在設計和實現(xiàn)的過程中，遇到不少問題。在老師幫助指導和本人努力下，本課題所涉及的難題都已經基本解決，滿足本次畢業(yè)設計的要求。本演示系統(tǒng)作為一個多媒體動態(tài)教學演示課件，在畢業(yè)設計過程中完成的部分還有欠缺。但由于找工作和時間的緊缺，一些設想并沒有去實現(xiàn)。如在算法演示

60、過程中播放適當?shù)囊魳凤@然也能提高學生的學習興趣，以及為更適合不同的使用者而應該設計的演示速度模塊。這些設想有待以后再實現(xiàn)。關于本次畢業(yè)設計，由于設計經驗的不足和所掌握知識的限制，該演示系統(tǒng)雖然已經能實現(xiàn)對一些算法很好的演示，但在某些方面還有更加優(yōu)秀的演示方法、某些功能設計構想還沒有完整的表達出來。通過本次設計的學習和實踐，對理論知識的認識有了進一步的加強，實踐能力和獨立思考的能力都得到了提高，這是在書本上所學不到的。這次畢業(yè)設計過程中所積累的經驗將為本人在今后工作崗位上發(fā)揮自己的才能奠定堅實的基礎。致謝本課題在選題及研究過程中得到老師的悉心指導。他們多次詢問研究進程，并為我指點迷津，幫助我開拓