《數(shù)據(jù)結(jié)構(gòu)》中典型算法的動(dòng)態(tài)演示畢業(yè)設(shè)計(jì)論文

PAGEPAGE44目錄TOC\o"1-3"\u中文摘要 III英文摘要 IV前言 11緒論 21.1問題背景 21.2開發(fā)環(huán)境 21.3開發(fā)工具簡(jiǎn)介 21.3.1C語言圖形程序設(shè)計(jì) 21.3.2圖形模式下的漢字顯示 51.3.3Turboc(V2.0)編譯錯(cuò)誤信息 61.4其它相關(guān)工具軟件 71.4.1Dos屏幕下程序截圖工具介紹及Dos抓圖技巧 71.4.1拓?fù)鋱D制作工具億圖V1.6.3 72需求分析 82.1問題定義 82.1.1問題分析 82.1.2用戶目標(biāo) 82.2系統(tǒng)的功能需求 82.2.1正確表達(dá)算法 82.2.2功能實(shí)用化 82.2.3具體演示功能 82.3系統(tǒng)的其他需求 92.3.1界面友好性 92.3.2系統(tǒng)的運(yùn)行環(huán)境及可靠性要求 93概要設(shè)計(jì) 103.1方案確定 103.2系統(tǒng)結(jié)構(gòu) 103.2.1系統(tǒng)結(jié)構(gòu)總框圖 103.2.2模塊功能說明 113.2.3算法演示子模塊中要注意的問題 114詳細(xì)設(shè)計(jì) 124.1數(shù)據(jù)設(shè)計(jì) 124.2系統(tǒng)主程序界面設(shè)計(jì) 124.3演示模塊流程圖 124.3.1冒泡演示流程圖 124.3.2漢諾塔演示流程圖 144.3.3二叉樹演示流程圖 154.3.4單鏈表演示流程圖 165系統(tǒng)功能實(shí)現(xiàn) 175.1歡迎界面模塊編碼 175.2主程序模塊編碼 195.3冒泡排序模塊編碼 225.4漢諾塔模塊編碼 245.5二叉樹遍歷模塊編碼 295.6鏈表模塊編碼 335.7退出模塊編碼 366系統(tǒng)測(cè)試 396.1系統(tǒng)測(cè)試常用的測(cè)試方法 396.2測(cè)試范圍與主要內(nèi)容 396.3黑盒測(cè)試用例 396.4測(cè)試報(bào)告 406.5改進(jìn)建議與措施 40結(jié)束語 41參考文獻(xiàn) 42致謝 43《數(shù)據(jù)結(jié)構(gòu)》中典型算法的動(dòng)態(tài)演示計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)劉俊坤指導(dǎo)老師：符開耀摘要：數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)專業(yè)的一門綜合性專業(yè)基礎(chǔ)課，對(duì)后續(xù)課程的學(xué)習(xí)極其重要。但該課程涉及大量的概念、定義、模型和算法，顯得很抽象和深?yuàn)W。在教學(xué)過程中，如果能加以計(jì)算機(jī)輔助教學(xué)，可以提高教學(xué)效果，所以編寫這樣的程序不僅有助于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，同時(shí)也大大增強(qiáng)了學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的編程能力。這是因?yàn)椋环矫胬盟惴ㄑ菔鞠到y(tǒng)的生動(dòng)性和直觀性，使教學(xué)內(nèi)容條理化和形象化，降低了對(duì)知識(shí)理解的難度；另一方面，由于演示系統(tǒng)的趣味性和交互性，有利于激發(fā)學(xué)生濃厚的學(xué)習(xí)興趣，使其愿學(xué)、樂學(xué)。本系統(tǒng)以清華大學(xué)出版社出版的C語言版《數(shù)據(jù)結(jié)構(gòu)》為藍(lán)本，合理地選擇數(shù)據(jù)結(jié)構(gòu)中四個(gè)經(jīng)典算法并在系統(tǒng)中進(jìn)行有機(jī)地組合,形成優(yōu)化的動(dòng)態(tài)演示系統(tǒng)。它可適應(yīng)讀者對(duì)算法的演示數(shù)據(jù)和過程執(zhí)行的控制方式的不同需求,在計(jì)算機(jī)的屏幕上顯示算法執(zhí)行過程中數(shù)據(jù)的邏輯結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)的變化狀況或遞歸算法執(zhí)行過程中棧的變化狀況。可視化是演示系統(tǒng)應(yīng)該具備的要求。本系統(tǒng)采用C語言圖形編程技術(shù)來實(shí)現(xiàn)軟件的可視化。因?yàn)镃語言的圖形編程對(duì)大多數(shù)人來說比較陌生，甚至讓人誤解C不能進(jìn)行圖形編程。通過本系統(tǒng)的設(shè)計(jì)，讓大家知道C語言也可以進(jìn)行圖形編程，從而進(jìn)行可視化設(shè)計(jì)與開發(fā)。關(guān)鍵詞：算法；動(dòng)態(tài)演示；圖形編程；可視化Thedynamicdemonstrationoftypicalalgorithminthe"DataStructures"ComputerScienceandTechnologyLiuJunkunTutor:FuKaiyaoAbstract：Asone

computer-specializedcomprehensivebasiccourse,theconstructionofdataisextremelyimportanttothefollowingcurriculumstudy.Becausethiscurriculuminvolves

massiveconcepts,

definitions,

modelsand

operationalgorithms,thus

itseemsveryabstractandabstruse.Intheteachingprocess,however,ifit

beperformedthroughcomputer-aidedinstruction,itmay

improvetheteachingeffect,thereforecompilingsuchprocedurescannotonlybehelpfultothestudyofconstructionofdata,butalsogreatlystrengthenthestudent'sstudyinterest,sharpenthestudent'sprogrammingability.Thisisbecause,ontheonehand,algorithmdemonstrationsystem'svividnessanddirect-viewing,makethecontentinorderland

visual,reducetheknowledgeitselfdifficultydegree;Ontheotherhand,interestandtheinteractionasaresultofthedemonstrationsystem,

areadvantageoustostimulatethestudents’strongstudyinterest,causethemtobewillingto

study.ThissystemtakesQinghuaUniversitypublishinghousepublicationClanguageversion"Constructionofdata"asamainsource,reasonablychoosesfourclassicalalgorithmsintheconstructionofdataandcarriesoninthesystemorganicallycombinations,formstheoptimizeddynamicdemonstrationsystem.Itmayadaptthereaders’differentdemandstothealgorithmdata-inandcontrolmodestheprocessexecution,anddemonstratesinthealgorithmimplementationonthecomputerscreenthedatalogicalorganizationeitherthememorystructurechangeconditionorthestackchangeconditionintherecursionalgorithmimplementation.Visualizationdemonstrationsystemshouldbeavailable.ThesystemusedCprogramminglanguagegraphicssoftwaretechnologytoachievethevisualization.Cprogramminglanguageforgraphicsis

unfamiliar

tous,

orweevenmisleadC

notfor

graphicsprogramming.Throughthedesignofthissystem,weknowCprogramminglanguagecanbegraphic,andcancarryoutvisibledesign.Keywords:Datastructures;Dynamicdemonstration;Graphprogramming;Visible前言學(xué)習(xí)編寫計(jì)算機(jī)程序設(shè)計(jì)僅僅了解計(jì)算機(jī)語言是不夠的，還必須掌握數(shù)據(jù)組織、存儲(chǔ)和運(yùn)算的一般方法，這些都是數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容，也是我們進(jìn)行計(jì)算機(jī)程序設(shè)計(jì)的重要基礎(chǔ)。由于數(shù)據(jù)結(jié)構(gòu)的原理和算法比較抽象，因此要理解和掌握其中的原理就比較困難。本文通過對(duì)幾個(gè)經(jīng)典算法的研究，并進(jìn)行動(dòng)態(tài)演示，使得能更好地了解算法的來龍去脈，更好地理解算法，抓住算法的本質(zhì)，因而更好地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程。本文的目的是將抽象算法轉(zhuǎn)為形象的演示。本文從軟件工程的角度出發(fā)，嚴(yán)格按照軟件開發(fā)的基本步驟，開發(fā)了一個(gè)數(shù)據(jù)結(jié)構(gòu)中幾個(gè)典型算法的可視化演示系統(tǒng)，并給出了C語言實(shí)現(xiàn)各功能模塊的思想及相關(guān)核心代碼，充分體現(xiàn)了C語言知識(shí)的綜合運(yùn)用，特別是平時(shí)大家接觸較少的圖形編程。由于編程水平有限以及時(shí)間倉促，故本系統(tǒng)難免有各種各樣的不足，希望各位老師和朋友提出意見，在此衷心感謝！1緒論1.1問題背景數(shù)據(jù)結(jié)構(gòu)是一門比較難學(xué)的課程，在教學(xué)過程中，如果能加以計(jì)算機(jī)輔助教學(xué)，可以提高教學(xué)效果，所以編寫這樣的程序不僅有助于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)，同時(shí)也大大增強(qiáng)了學(xué)生的學(xué)習(xí)興趣，提高學(xué)生的編程能力。由于數(shù)據(jù)結(jié)構(gòu)的原理和算法比較抽象，因此要理解和掌握其中的原理就比較困難。本系統(tǒng)通過對(duì)幾個(gè)經(jīng)典的算法進(jìn)行動(dòng)態(tài)演示，讓人能更好地了解算法的來龍去脈，更好地理解算法，抓住算法的本質(zhì)，從而更好地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程。1.2開發(fā)環(huán)境開發(fā)環(huán)境：TurboC(V2.0)運(yùn)行環(huán)境：Windows98/2000/XP/DOS系列平臺(tái)1.3開發(fā)工具簡(jiǎn)介1.3.1C語言圖形程序設(shè)計(jì)計(jì)算機(jī)圖形程序設(shè)計(jì)是程序設(shè)計(jì)中比較困難而且又吸引人的部分。為了方便用戶設(shè)計(jì)圖形程序，不同版本的C語言編譯程序提供了許多圖形的庫函數(shù)。用戶在設(shè)計(jì)圖形程序時(shí)，只需要調(diào)用相應(yīng)的庫函數(shù)即可。在ANSIC中沒有對(duì)圖形庫函數(shù)的要求，各版本的C語言編譯環(huán)境圖形庫函數(shù)都不相同，下面以Turboc2.0的圖形庫來介紹圖形程序設(shè)計(jì)[2]。Turboc2.0為用戶提供了一個(gè)功能很強(qiáng)的圖形函數(shù)庫，又稱為Borland圖形接口（BGI）。編寫圖形程序時(shí)用到的一些圖形庫函數(shù)均包括在graphics.lib中。用到這些函數(shù)時(shí)，必須把圖形頭文件graphics.h包含進(jìn)來[6]。計(jì)算機(jī)顯示器的顯示模式按功能可以分為字符模式和圖形模式兩大類。因此要進(jìn)行圖形編程，首先要對(duì)圖形模式進(jìn)行初始化。不同的顯示器適配器有不同的圖形分辨率。即使是同一顯示器適配器，在不同模式下也有不同分辨率。因此，在屏幕作圖之前，必須根據(jù)顯示器適配器的種類將顯示器設(shè)置成為某種圖形模式。在未設(shè)置圖形模式之前，微機(jī)系統(tǒng)默認(rèn)屏幕為文本模式(80列，25行字符模式)，此時(shí)所有圖形函數(shù)均不能工作。設(shè)置屏幕為圖形模式，可用下列圖形初始化函數(shù)：voidfarinitgraph(intfar*gdriver，intfar*gmode，char*path);其中g(shù)driver和gmode分別表示圖形驅(qū)動(dòng)器和模式，path是指圖形驅(qū)動(dòng)程序所在的目錄路徑。圖形驅(qū)動(dòng)程序由TurboC出版商提供，文件擴(kuò)展名為．BGI。根據(jù)不同的圖形適配器有不同的圖形驅(qū)動(dòng)程序。例如對(duì)于EGA、VGA圖形適配器的圖形驅(qū)動(dòng)程序?yàn)镋GAVGA.BGI。有時(shí)編程者并不知道所用的圖形顯示器適配器種類，而且我們?yōu)榱藢⒕帉懙某绦蚩梢杂糜诓煌瑘D形驅(qū)動(dòng)器，增強(qiáng)程序的通用性，我們通常不指定圖形顯示器適配器種類，而使用TurboC提供了一個(gè)自動(dòng)檢測(cè)顯示器硬件的函數(shù)，其調(diào)用格式為：voidfardetectgraph(int*gdriver,*gmode);例1：自動(dòng)進(jìn)行硬件測(cè)試后進(jìn)行圖形初始化[2]#include"graphics.h"main(){intgdriver,gmode;detectgraph(&gdriver,&gmode);/*自動(dòng)測(cè)試硬件*/printf("driveris%d,modeis%d\n",gdriver,gmode);/*輸出結(jié)果*/getch();initgraph(&gdriver,&gmode,"");/*根據(jù)測(cè)試結(jié)果初始化圖形*/circle(320,240,50);getch();closegraph();}上例程序中先對(duì)圖形顯示器自動(dòng)檢測(cè)，然后再用圖形初始化函數(shù)進(jìn)行初始化設(shè)置。其中，closegraph()為退出圖形狀態(tài)的函數(shù)，其調(diào)用格式為：voidfarclosegraph(void)；調(diào)用該函數(shù)后可退出圖形狀態(tài)而進(jìn)入文本方式，并釋放用于保存圖形驅(qū)動(dòng)程序和字體的系統(tǒng)內(nèi)存。同時(shí)TurboC提供了一種更簡(jiǎn)單的初始化圖形的方法，即用gdriver=DETECT語句后再跟initgraph()函數(shù)就行了。比如，上例可改為如例2的情形[2]。例2：對(duì)例1的修改#include"graphics.h"main(){intgdriver=DETECT,gmode;initgraph(&gdriver,&gmode,"");circle(320,240,50);getch();closegraph();}對(duì)圖形模式進(jìn)行了初始化后，接下來要進(jìn)行的工作是對(duì)于圖形模式的屏幕顏色設(shè)置以及如何清屏。對(duì)于圖形模式的屏幕顏色設(shè)置，分為背景色的設(shè)置和前景色的設(shè)置。在Turboc中分別使用以下兩個(gè)函數(shù)：背景色設(shè)置函數(shù)：voidfarsetbkcolor(intcolor);該函數(shù)將使背景按照參數(shù)color指定的顏色來進(jìn)行顯示。前景色設(shè)置函數(shù)：voidfarsetcolor(intcolor);該函數(shù)將使前景按照參數(shù)color指定的顏色來進(jìn)行顯示。清除圖形屏幕內(nèi)容使用清屏函數(shù)，其調(diào)用格式如下voidfarcleardevice(void);該函數(shù)清除整個(gè)屏幕的內(nèi)容，可以在繪圖前調(diào)用這個(gè)函數(shù)進(jìn)行清屏或者在畫新圖形時(shí)調(diào)用該函數(shù)清除以前畫的圖形。有關(guān)顏色設(shè)置、清屏函數(shù)的使用請(qǐng)看例3的示例[2]。例3：清屏函數(shù)的使用#include"stdio.h"#include"graphics.h"main(){intgdriver,gmode,i,j;gdriver=DETECT;initgraph(&gdriver,&gmode,"");/*圖形初始化*/setbkcolor(0);/*設(shè)置圖形背景*/cleardevice();setcolor(1);/*設(shè)置不同作圖色*/circle(319,239,20);/*畫圓*/setbkcolor(1);/*設(shè)置不同背景色*/cleardevice();}getch();closegraph();}另外，TURBOC也提供了幾個(gè)獲得現(xiàn)行顏色設(shè)置情況的函數(shù)。intfargetbkcolor(void);返回現(xiàn)行背景顏色值。intfargetcolor(void);返回現(xiàn)行作圖顏色值。intfargetmaxcolor(void);返回最高可用的顏色值。接下來介紹一些基本的圖形函數(shù)：畫點(diǎn)函數(shù)：voidfarputpixel(intx,inty,intcolor);畫線函數(shù)：Turboc提供了一系列畫線函數(shù)，下面介紹其中最常用的一種：voidfarline(intx0,inty0,intx1,inty1);畫(x0,y0)到(x1,y1)的直線。圖形填充函數(shù)：voidfarsetfillstyle(intpattern,intcolor);color的值是當(dāng)前屏幕圖形模式時(shí)顏色的有效值。圖形模式下的文本輸出函數(shù)：voidfarouttextxy(intx,inty,charfar*textstring);該函數(shù)輸出字符串指針textstring所指的文本在規(guī)定的(x,y)位置。其中x和y為象元坐標(biāo)。1.3.2圖形模式下的漢字顯示在編寫一些應(yīng)用軟件時(shí)，為了使軟件更為通俗淺顯、易學(xué)易用，具備漢字的用戶界面是必不可少的條件。在文本模式下，只要有漢字操作系統(tǒng)的支持，顯示漢字是不成問題的。只要用printf或cprintf就可以了。在圖形模式下顯示漢字就稍稍麻煩些。我們可以定義一個(gè)函數(shù)來用于漢字的顯示。這個(gè)函數(shù)不需要漢字系統(tǒng)的支持，但用到其中的字庫文件[2]。下面我看一個(gè)例子是如何實(shí)現(xiàn)漢字顯示的。例4：圖形模式下16點(diǎn)陣漢字的顯示voidHZ16(intx0,inty0,intw,intcolor,char*s)/*橫坐標(biāo),縱坐標(biāo),字間隔,漢字顏色,漢字字符串*/{FILE*fp;registercharbuffer[32];registercharstr[2];unsignedlongfpos;/*fpos為最終偏移動(dòng)量*/registerinti,j,k;fp=fopen("hzk16","r");/*打開16*16漢字庫*/while(*s)/*一直到字符串結(jié)束為止*/{if(*s<0)/*漢字輸出*/{str[0]=(*s)-0xa0;str[1]=*(s+1)-0xa0;fpos=((str[0]-1)*94+(str[1]-1))*32L;/*計(jì)算漢字在hzk16的偏移量*/fseek(fp,fpos,SEEK_SET);/*指針移動(dòng)到當(dāng)前位置*/fread(buffer,32,1,fp);/*讀取一個(gè)漢字到數(shù)組中*/for(i=0;i<16;i++)/*16行*/for(j=0;j<2;j++)/*兩個(gè)字節(jié)*/for(k=0;k<8;k++)/*8位*/if(((buffer[i*2+j]>>(7-k))&0x1)!=NULL)/*是一就畫點(diǎn)*/putpixel(x0+8*j+k,y0+i,color);s+=2;/*一個(gè)漢字占兩個(gè)字節(jié)，現(xiàn)在將指針移動(dòng)兩個(gè)字節(jié)*/x0+=w;/*顯示坐標(biāo)也按照間隔移動(dòng)*/}else/*顯示非漢字字符*/{settextstyle(0,0,1);setcolor(color);str[0]=*s;str[1]=0;outtextxy(x0,y0+7,str);/*顯示單個(gè)字符*/x0+=w-7;/*顯示單個(gè)字符后的x坐標(biāo)變化*/s++;/*指針移動(dòng)到下一個(gè)字節(jié)*/}}fclose(fp);/*關(guān)閉16*16漢字庫*/}1.3.3Turboc(V2.0)編譯錯(cuò)誤信息為了幫助讀者調(diào)試程序和分析程序，下面簡(jiǎn)單介紹程序出錯(cuò)的種類[1]。Turboc(V2.0)的源程序錯(cuò)誤分為三種類型：致命錯(cuò)誤、一般錯(cuò)誤和警告。其中，致命錯(cuò)誤通常是內(nèi)部編譯出錯(cuò)；一般錯(cuò)誤指程序的語法錯(cuò)誤、磁盤或內(nèi)存存取錯(cuò)誤或命令行錯(cuò)誤等；警告則只是指出一些得懷疑的情況，它并不防止編譯的進(jìn)行。下面按字母順序A～Z分別列出致命錯(cuò)誤及一般錯(cuò)誤信息，英漢對(duì)照及處理方法：(1)致命錯(cuò)誤英漢對(duì)照及處理方法：A-B致命錯(cuò)誤Badcallofin-linefunction(內(nèi)部函數(shù)非法調(diào)用)分析與處理：在使用一個(gè)宏定義的內(nèi)部函數(shù)時(shí)，沒能正確調(diào)用。一個(gè)內(nèi)部函數(shù)以兩個(gè)下劃線(__)開始和結(jié)束。Irreducableexpressiontree(不可約表達(dá)式樹)分析與處理：這種錯(cuò)誤指的是文件行中的表達(dá)式太復(fù)雜，使得代碼生成程序無法為它生成代碼。這種表達(dá)式必須避免使用。Registerallocationfailure(存儲(chǔ)器分配失敗)分析與處理：這種錯(cuò)誤指的是文件行中的表達(dá)式太復(fù)雜，代碼生成程序無發(fā)把它生成代碼。此時(shí)應(yīng)簡(jiǎn)化這種繁雜的表達(dá)式或干脆避免使用它。(2)一般錯(cuò)誤信息英漢照及處理方法詳見參考文獻(xiàn)[1]1.4其它相關(guān)工具軟件1.4.1Dos屏幕下程序截圖工具介紹及Dos抓圖技巧現(xiàn)在的抓圖軟件基本上都只能在Windows下運(yùn)行，可有時(shí)候我們還需要在純DOS下（注意：不是Windows中的DOS模式）進(jìn)行屏幕抓取工作?？梢酝ㄟ^安裝虛擬機(jī)來解決這個(gè)問題，但是很麻煩，怎么辦呢？下面介紹一個(gè)工具Graffix，幫你完成純DOS下的截圖任務(wù)。用Graffix完成抓圖操作一般情況下都要分成兩個(gè)主要步驟：先將屏幕捕捉AT格式然后用附帶的轉(zhuǎn)換工具將ATF格式轉(zhuǎn)換為GIF或者PCX圖像格式。（1）ATF文件的獲得①進(jìn)入純DOS后，在命令行后輸入“DGFX”并回車，將出現(xiàn)用法提示（圖1），可以看到抓取熱鍵是“Ctrl+ALT＋空格鍵”。從內(nèi)存卸載此程序的命令是“DGFX/U”。②運(yùn)行需要抓圖的程序，出現(xiàn)待抓畫面后，按下熱鍵，屏幕彈出提示（圖2），輸入文件名后按F1鍵可以將畫面抓取為ATF格式，如果直接按Enter鍵，則得到的是TXT文本格式。（2）將ATF轉(zhuǎn)換為GIF/PCX圖像格式ATF格式的圖片不能被Windows下應(yīng)用程序所識(shí)別，因此我們需要將前面抓取到的ATF格式轉(zhuǎn)換為GIF或者PCX格式。①在DOS提示符后輸入“A2B”，回車，輸入ATF文件名，之后在屏幕上會(huì)顯示該ATF文件的內(nèi)容。②再次按下熱鍵“CTRL+ALT+空格”，會(huì)出現(xiàn)“SAVEINWHICHFORMATGIFORPCX（G/P）”的提示（詢問你是將文件保存為GIF還是PCX格式），此時(shí)若按下字母G，則通過下面的步驟會(huì)將ATF轉(zhuǎn)換為GIF格式；如按字母“P”則可得到PCX格式。③輸入最終要得到的文件的主文件名并回車?，F(xiàn)在進(jìn)入軟件目錄看看，是不是得到所需要的GIF或PCX圖像文件了？若要抓取的程序畫面本身是圖形模式，則將直接得到GIF或PCX圖像格式的文件，從而可以省略轉(zhuǎn)換步驟。1.4.1拓?fù)鋱D制作工具億圖V1.6.3億圖是一款類似Visio的流程圖、網(wǎng)絡(luò)圖繪制軟件，新穎小巧，功能強(qiáng)大，可以很方便的繪制各種專業(yè)的業(yè)務(wù)流程圖，程序流程圖，數(shù)據(jù)流程圖，網(wǎng)絡(luò)拓?fù)鋱D等。它在設(shè)計(jì)時(shí)采用全拖曳式操作，最大限度的簡(jiǎn)化用戶的工作量，方便易用；提供各種圖形模板庫，方便專業(yè)人士的使用；提供強(qiáng)大的圖文混排和所見即所得的圖形打印。2需求分析2.1問題定義2.1.1問題分析本系統(tǒng)要完成的工作是通過對(duì)數(shù)據(jù)結(jié)構(gòu)中經(jīng)典算法的模擬，經(jīng)用戶輸入數(shù)據(jù)和對(duì)數(shù)據(jù)處理后最終以圖形的方式實(shí)時(shí)顯示在屏幕上，從而使得抽象的算法形象化、生動(dòng)化。用戶通過使用這個(gè)動(dòng)態(tài)的演示軟件就能很好的理解算法的含義。2.1.2用戶目標(biāo)本系統(tǒng)可適應(yīng)讀者對(duì)算法的輸入數(shù)據(jù)和過程執(zhí)行的控制方式的不同需求,在計(jì)算機(jī)的屏幕上顯示算法執(zhí)行過程中數(shù)據(jù)的邏輯結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)的變化狀況或遞歸算法執(zhí)行過程中棧的變化狀況。整個(gè)系統(tǒng)使用鍵盤操作和菜單驅(qū)動(dòng)方式。每個(gè)菜單項(xiàng)對(duì)應(yīng)一個(gè)動(dòng)作或一個(gè)子菜單。系統(tǒng)一直處于選擇菜單項(xiàng)或執(zhí)行動(dòng)作狀態(tài),直到選擇了退出動(dòng)作為止。用戶的目標(biāo)也就是該演示系統(tǒng)所希望達(dá)到的目的。2.2系統(tǒng)的功能需求系統(tǒng)的功能需求也即是本系統(tǒng)要實(shí)現(xiàn)的具體內(nèi)容。算法演示系統(tǒng)要求能夠動(dòng)態(tài)演示《數(shù)據(jù)結(jié)構(gòu)》中的算法的執(zhí)行過程。用戶可以自由選擇演示的算法，且在執(zhí)行某一個(gè)特定算法操作演示前提示用戶輸入操作元素及操作方法。由于時(shí)間有限而要演示的算法很多，故這里我以幾個(gè)經(jīng)典算法為例子，實(shí)現(xiàn)它們的動(dòng)態(tài)演示并掌握這種方法，起到拋磚引玉的作用，希望大家能夠不斷完善這個(gè)系統(tǒng)。本系統(tǒng)要演示的內(nèi)容包括四個(gè)經(jīng)典算法：冒泡排序、漢諾塔的遞歸算法、單鏈表建立和二叉樹的建立與遍歷，由主界面菜單顯示。2.2.1正確表達(dá)算法這是最基本的一項(xiàng)要求，算法演示的目的本來就是讓大家更好地學(xué)習(xí)理解算法，演示只是一種手段，目的是降低知識(shí)難度，傳遞知識(shí)，因此首先得保證知識(shí)的正確性。2.2.2功能實(shí)用化為了真正起到深入理解算法的效果，系統(tǒng)使用多種演示手段如單步跟蹤和連續(xù)執(zhí)行等多種調(diào)用方式來演示算法的執(zhí)行過程。為了針對(duì)用戶的各種需要，演示的速度可以由用戶自己調(diào)節(jié)。2.2.3具體演示功能冒泡排序算法=1\*GB3①選擇系統(tǒng)自動(dòng)產(chǎn)生隨機(jī)數(shù)據(jù)和手動(dòng)輸入數(shù)據(jù)兩種方式；=2\*GB3②選擇自動(dòng)排序和手動(dòng)單步排序兩種方式；=3\*GB3③屏幕上顯示算法執(zhí)行過程并輸出所有排序序列。漢諾塔遞歸算法=1\*GB3①任意輸入演示的個(gè)數(shù)；=2\*GB3②選擇電腦自動(dòng)演示和手動(dòng)單步執(zhí)行兩種方式；=3\*GB3③若選擇電腦自動(dòng)演示請(qǐng)輸入速度；=4\*GB3④屏幕上顯示算法執(zhí)行過程。單鏈表=1\*GB3①自由輸入接點(diǎn)數(shù)據(jù)；=2\*GB3②屏幕上顯示算法執(zhí)行過程并輸出單鏈表。二叉樹算法=1\*GB3①選擇系統(tǒng)自動(dòng)產(chǎn)生隨機(jī)二叉樹和手動(dòng)輸入數(shù)據(jù)產(chǎn)生兩種方式；=2\*GB3②選擇電腦自動(dòng)演示和手動(dòng)單步執(zhí)行兩種方式；=3\*GB3③屏幕上顯示算法執(zhí)行過程并輸出三種遍歷序列。2.3系統(tǒng)的其他需求2.3.1界面友好性系統(tǒng)界面設(shè)計(jì)遵循實(shí)用、方便的原則，各種操作簡(jiǎn)單明了。系統(tǒng)具備鍵盤接口，接受鍵盤輸入。為了加深對(duì)算法的理解，可允許用戶通過輸入不同的初始數(shù)據(jù)來觀察算法的具體的執(zhí)行情況。系統(tǒng)演示插入了適當(dāng)?shù)恼f明和注釋信息，以幫助使用者對(duì)演示過程的理解，為滿足各種不同層次用戶的要求，各種提示信息用中文方式。2.3.2系統(tǒng)的運(yùn)行環(huán)境及可靠性要求在保證了系統(tǒng)功能的前提下，適當(dāng)降低了對(duì)系統(tǒng)運(yùn)行環(huán)境的要求，以便系統(tǒng)可以在配置較低的軟件環(huán)境中運(yùn)行。對(duì)各種有意或無意的誤操作，系統(tǒng)能正確處理，不會(huì)自動(dòng)中止。3概要設(shè)計(jì)3.1方案確定本系統(tǒng)要求實(shí)現(xiàn)幾種不同算法的演示功能，故可遵循結(jié)構(gòu)化程序設(shè)計(jì)思想來進(jìn)行本系統(tǒng)的設(shè)計(jì)自頂向下，逐步求精，將設(shè)計(jì)任務(wù)劃分成許多子任務(wù)，即分解成多子功能模塊進(jìn)行設(shè)計(jì)。本系統(tǒng)采用結(jié)構(gòu)化編程，編寫主模塊來調(diào)用不同的演示模塊。主模塊的菜單是選擇演示模塊的入口。對(duì)每一個(gè)演示模塊，系統(tǒng)定義了公用的接口，每編寫一個(gè)新模塊，只需要連接到主界面模塊即可。調(diào)用某個(gè)模塊時(shí)，只需要執(zhí)行語句system（）；括號(hào)里面加入模塊函數(shù)名。當(dāng)需要加入新模塊時(shí)，將程序加入到系統(tǒng)文件中，編譯即可[3]。3.2系統(tǒng)結(jié)構(gòu)3.2.1系統(tǒng)結(jié)構(gòu)總框圖軟件系統(tǒng)的結(jié)構(gòu)如圖3-1所示。有了系統(tǒng)總體結(jié)構(gòu)圖，我們就可以逐個(gè)模塊的詳細(xì)設(shè)計(jì)，直至所有的模塊完全實(shí)現(xiàn)。為了增強(qiáng)系統(tǒng)的維護(hù)性和可擴(kuò)充性，總框圖中的各個(gè)模塊基本是相互獨(dú)立的，用戶只需通過鍵盤即可方便地進(jìn)入各個(gè)模塊，實(shí)現(xiàn)不同模塊的跳轉(zhuǎn)。圖3-1數(shù)據(jù)結(jié)構(gòu)算法動(dòng)態(tài)演示系統(tǒng)結(jié)構(gòu)總框圖3.2.2模塊功能說明對(duì)本系統(tǒng)的功能進(jìn)行分析后可做如下的模塊化設(shè)計(jì)：主程序模塊實(shí)現(xiàn)的功能：完成選項(xiàng)菜單的顯示，及對(duì)各模塊的調(diào)用。歡迎界面模塊實(shí)現(xiàn)的功能：完成對(duì)系統(tǒng)的初始化及界面顯示。冒泡排序模塊實(shí)現(xiàn)的功能：完成冒泡算法的演示。漢諾塔模塊實(shí)現(xiàn)的功能：完成漢諾塔算法的演示。二叉樹遍歷模塊實(shí)現(xiàn)的功能：完成二叉樹遍歷算法的演示。鏈表模塊實(shí)現(xiàn)的功能：完成單鏈表建立算法的演示。系統(tǒng)介紹的模塊：對(duì)系統(tǒng)簡(jiǎn)單的介紹。退出界面模塊：退出圖形模式，關(guān)閉系統(tǒng)。3.2.3算法演示子模塊中要注意的問題對(duì)一個(gè)具體的算法演示子模塊，須滿足單步執(zhí)行，連續(xù)執(zhí)行，速度可調(diào)，任意時(shí)刻復(fù)位等復(fù)雜功能，設(shè)計(jì)一個(gè)接收鍵盤輸入的字符函數(shù)[7]實(shí)現(xiàn)。在使用中，只需要簡(jiǎn)單把接收鍵盤輸入的字符函數(shù)語句插入演示流程的不同地方，就能達(dá)到上述要求。調(diào)速的話還要用到延遲函數(shù)，還有系統(tǒng)自動(dòng)產(chǎn)生演示數(shù)據(jù)的話需要使用隨機(jī)數(shù)發(fā)生函數(shù)，所有的算法演示均調(diào)用此類函數(shù)完成，使編程統(tǒng)一，方便。4詳細(xì)設(shè)計(jì)4.1數(shù)據(jù)設(shè)計(jì)本系統(tǒng)的設(shè)計(jì)以數(shù)組和結(jié)構(gòu)體為基類型，其他數(shù)據(jù)類型相輔來完成。在數(shù)據(jù)選擇和輸入方面，系統(tǒng)提供兩種方式：一是系統(tǒng)自動(dòng)隨機(jī)產(chǎn)生，二是用戶手動(dòng)輸入數(shù)據(jù)并支持自動(dòng)執(zhí)行和單步操作。4.2系統(tǒng)主程序界面設(shè)計(jì)歡迎界面：雪花飛舞，標(biāo)題漢字顯示并閃爍，顏色循環(huán)改變，顯示系統(tǒng)開發(fā)人員信息。系統(tǒng)介紹：系統(tǒng)簡(jiǎn)單介紹。菜單界面：提供選擇要演示的內(nèi)容。退出界面：星空燦爛，標(biāo)題漢字顯示并閃爍，顏色循環(huán)改變，并在一次循環(huán)之后退出系統(tǒng)。4.3演示模塊流程圖4.3.1冒泡演示流程圖由于冒泡排序這個(gè)算法我們已經(jīng)非常熟悉，因此在這里具體排序算法不是我們關(guān)心的問題，我們要關(guān)心的是怎么樣將它的排序過程動(dòng)態(tài)地演示出來。該演示算法的基本思想是：用戶進(jìn)入程序后，可選擇系統(tǒng)隨機(jī)產(chǎn)生待排序的數(shù)據(jù)或者是自己手動(dòng)輸入數(shù)據(jù)（當(dāng)然不能超過個(gè)數(shù)限制，否則超出部分會(huì)無效）；然后用戶還可以選擇系統(tǒng)自動(dòng)排序或者是手動(dòng)單步執(zhí)行排序，這兩種方式的區(qū)別在于選擇了前者排序?qū)⒆詣?dòng)進(jìn)行直到結(jié)束，而選擇后者的話每進(jìn)行完一趟排序程序暫停，等待用戶按任意鍵繼續(xù)執(zhí)行下一趟排序，直到全部排序結(jié)束退出。由圖4-1可知，此冒泡排序算法演示分以下幾個(gè)步驟：用戶進(jìn)入程序后，選擇產(chǎn)生演示數(shù)據(jù)的方式；用戶選擇演示方式；演示完畢退出。由此，該算法要設(shè)置三個(gè)標(biāo)志變量，分別用來判斷數(shù)據(jù)產(chǎn)生方式、排序演示方式和排序是否完成。冒泡排序的基本原理是對(duì)存放原始數(shù)據(jù)的數(shù)組，按從前往后的方向進(jìn)行多次掃描，每次掃描稱為一趟。當(dāng)發(fā)現(xiàn)相鄰兩個(gè)數(shù)據(jù)的次序與排序要求的大小次序不符合時(shí)，即將這兩個(gè)數(shù)據(jù)進(jìn)行互換。這樣，較小的數(shù)據(jù)就會(huì)逐個(gè)向前移動(dòng)，好像氣泡向上浮起一樣。此演示流程中將每一趟排序后的數(shù)據(jù)都顯示在屏幕上，通過每一趟的數(shù)據(jù)對(duì)比，讓人容易理解排序過程中數(shù)據(jù)怎么一步一步交換的，數(shù)據(jù)是怎么樣變成有序的。當(dāng)然具體的數(shù)據(jù)動(dòng)態(tài)交換過程我們會(huì)在系統(tǒng)功能實(shí)現(xiàn)這一章中詳細(xì)介紹，這里只談?wù)麄€(gè)演示的流程。該演示算法流程圖如圖4-1。圖4-1冒泡算法演示流程4.3.2漢諾塔演示流程圖這里我們主要關(guān)心的是漢諾塔的移盤過程。該演示程序的思想是：用戶在進(jìn)入程序后，先輸入想要演示的盤子個(gè)數(shù)，然后再選擇是否自動(dòng)演示，若選擇自動(dòng)演示的話，輸入演示速度；若是手動(dòng)執(zhí)行的話，移盤一次程序暫停一下，然后按任意鍵繼續(xù)執(zhí)行直到完成。該演示算法流程圖如圖4-2。圖4-2漢諾塔演示流程4.3.3二叉樹演示流程圖該演示程序的思想是：用戶在運(yùn)行程序后，可選擇系統(tǒng)隨機(jī)生成二叉樹或者手動(dòng)產(chǎn)生，若是手動(dòng)的話用戶自己輸入結(jié)點(diǎn)數(shù)值；然后用戶可以選擇系統(tǒng)自動(dòng)和手動(dòng)兩種遍歷方式。這兩種方式的區(qū)別在于選擇了前者遍歷將自動(dòng)進(jìn)行直到結(jié)束并在屏幕上顯示遍歷序列，而選擇后者的話每遍歷一個(gè)結(jié)點(diǎn)暫停，等待用戶按任意鍵繼續(xù)執(zhí)行，直到全部結(jié)點(diǎn)遍歷完畢。該演示算法流程圖如圖4-3。圖4-3二叉樹演示流程4.3.4單鏈表演示流程圖該演示的思想是：程序一運(yùn)行便進(jìn)入圖形模式，隨之對(duì)鏈表進(jìn)行一系列的初始化，然后用戶輸入接點(diǎn)字符，程序接收后在屏幕上生成一個(gè)單鏈表結(jié)點(diǎn)，如果輸入ESC字符的話，停止生成結(jié)點(diǎn)，鏈表建立完成，或者結(jié)點(diǎn)數(shù)超過限制也將停止建立結(jié)點(diǎn)。該算法流程圖如圖4-4。圖4-4單鏈表演示流程5系統(tǒng)功能實(shí)現(xiàn)5.1歡迎界面模塊編碼本系統(tǒng)的歡迎界面是一個(gè)雪花飛舞的場(chǎng)景，系統(tǒng)標(biāo)題和作者信息在場(chǎng)景中不斷閃爍變色。關(guān)鍵技術(shù)：畫雪景、讓字循環(huán)變色模塊實(shí)現(xiàn)步驟：１、定義雪花的結(jié)構(gòu)及其一些基本參數(shù)２、保存雪花３、畫雪花４、讓字閃爍并循環(huán)變色核心代碼實(shí)現(xiàn)如下：定義雪花的結(jié)構(gòu)及其一些基本參數(shù)structSnow/*雪花的一些參數(shù)*/{intx;inty;intspeed;/*雪花的速度*/}snow[100];實(shí)現(xiàn)對(duì)雪花的保存首先定義兩個(gè)指針變量來作為保存空間：void*save1,*save2;/*保存空間*/然后我們通過定義一個(gè)函數(shù)來申請(qǐng)空間，具體實(shí)現(xiàn)對(duì)雪花的保存。voidCopy(void)/*保存區(qū)域*/{setcolor(0);setfillstyle(SOLID_FILL,15);fillellipse(200,200,4,4);size=imagesize(196,196,204,204);/*定義保存圖象區(qū)域大小*/save1=malloc(size);/*申請(qǐng)空間*/save2=malloc(size);getimage(196,196,204,204,save1);/*保存雪花*/getimage(96,96,104,104,save2);/*保存背景黑色*/}開始正式畫雪花首先來做一些初始工作，定義幾個(gè)變量：intsnownum=0;/*雪的個(gè)數(shù)*/intsize;/*保存區(qū)域的大小*/然后自定義一個(gè)具體的畫雪函數(shù)來實(shí)現(xiàn)畫雪景：voidDrawSnow(void){intj=0;inti;intsx[62];randomize();for(i=0;i<62;i++)/*定義雪花的x坐標(biāo)*/sx[i]=(i+2)*10;cleardevice();while(!kbhit()){if(snownum!=100)/*生成新的雪花*/{ snow[snownum].speed=12+random(5);/*速度隨機(jī)定，但不小于9*/ i=random(62); snow[snownum].x=sx[i];/*隨機(jī)取x坐標(biāo)*/ snow[snownum].y=10-random(100);}for(i=0;i<snownum;i++)/*去雪*/ putimage(snow[i].x,snow[i].y,save2,COPY_PUT);if(snownum!=100) snownum++;setfillstyle(SOLID_FILL,15);/*畫雪*/for(i=0;i<snownum;i++){ snow[i].y+=snow[i].speed; putimage(snow[i].x,snow[i].y,save1,COPY_PUT); if(snow[i].y>500) snow[i].y=10-random(200);}}實(shí)現(xiàn)字體閃爍并循環(huán)變色這個(gè)問題相對(duì)來說比較簡(jiǎn)單，我們能夠用if語句來實(shí)現(xiàn)對(duì)字體顏色的變化：首先我們定義一個(gè)變量j，初始化為零，假設(shè)我們要使字體在三種顏色之間循環(huán)變化的話，我們可以這樣做，讓j%3這個(gè)式子作為if語句的基本判斷條件，我可以設(shè)定：j%3=0，字體顯示藍(lán)色；j%3=1，字體顯示紅色；j%3=2，字體顯示黃色。每顯示一種顏色后j自加1，這樣字體將在這三種顏色間循環(huán)，形成歡迎界面中閃爍動(dòng)人的一幕。歡迎界面效果如圖5-1。圖5-1歡迎界面5.2主程序模塊編碼系統(tǒng)主界面完成選項(xiàng)菜單的顯示，及對(duì)各模塊的調(diào)用。關(guān)鍵技術(shù)：畫選擇菜單、模塊調(diào)用模塊實(shí)現(xiàn)步驟：１、畫選擇菜單；２、實(shí)現(xiàn)對(duì)各模塊的調(diào)用。核心代碼實(shí)現(xiàn)如下：畫選擇菜單首先要做的對(duì)菜單的顯示[14]，菜單一般是下拉式的，而我這里做的是直接選擇項(xiàng)菜單，按上下鍵進(jìn)行選擇，當(dāng)選中某一項(xiàng)的話，選擇項(xiàng)以高亮度顯示，小球移動(dòng)到選擇項(xiàng)處。下面我們來畫選擇的小球體[14]：我們先定義一個(gè)畫球體的函數(shù)voidDrawBall(intx,inty,intcolor)/*x和y為坐標(biāo)，color為球的顏色*/{setcolor(0);setfillstyle(SOLID_FILL,color);fillellipse(x,y+10,10,10);}接下來畫選項(xiàng)菜單，選擇項(xiàng)菜單用一個(gè)自定義函數(shù)Choose()實(shí)現(xiàn)，主要代碼如下：…setcolor(11);rectangle(40,40,600,440);/*畫邊框線/setcolor(13);settextstyle(0,0,3);/*標(biāo)題大一些*/HZ16(100,70,30,4,"請(qǐng)您選擇要演示的算法");settextstyle(0,0,2);/*其它選項(xiàng)小一些*/HZ16(200,150,30,4,"起泡排序");/*起泡排序*/HZ16(200,190,30,1,"漢諾塔");/*漢諾塔*/HZ16(200,230,30,2,"單鏈表的建立");/*單鏈表的建立*/HZ16(200,270,30,14,"二叉樹遍歷");/*二叉樹遍歷*/HZ16(200,310,30,10,"系統(tǒng)介紹");/*系統(tǒng)介紹*/HZ16(200,350,30,5,"結(jié)束程序");/*結(jié)束程序*/…

有了選擇菜單，我們還需要選擇菜單的循環(huán)條件，它通過下面的語句來判斷是否循環(huán)：…if(key==ESC)/*退出系統(tǒng)*/ break; if(key==UP)/*上鍵盤操作*/[12] { DrawBall(keyx,keyy,BLACK);/*先用黑色在原來位置去除球*/ if(keyy!=150) keyy-=40;/*球的縱坐標(biāo)*/ else keyy=350; DrawBall(keyx,keyy,11);/*新位置輸出球*/ } if(key==DOWN)/*下鍵盤操作*/ { DrawBall(keyx,keyy,BLACK);/*先用黑色在原來位置去除球*/ if(keyy!=350) keyy+=40; else keyy=150; DrawBall(keyx,keyy,11);/*新位置輸出球*/ }…實(shí)現(xiàn)對(duì)各模塊的調(diào)用接下來的事情是對(duì)各模塊的調(diào)用，先將各模塊代碼編譯成可執(zhí)行文件，然后用函數(shù)system（）調(diào)用這些可執(zhí)行文件就行了。其主要代碼如下：…if(key==ENTER)/*確定鍵*/ { switch(keyy)/*判斷內(nèi)容*/ { case150:system("bubble");yes=0;break;/*調(diào)用起泡排序*/ case190:system("hanoi");yes=0;break;/*調(diào)用漢諾塔*/ case230:system("list");yes=0;break;/*調(diào)用鏈表*/ case270:system("tree");yes=0;break;/*調(diào)用二叉樹*/ case310:system("help");yes=0;break;/*調(diào)用系統(tǒng)介紹*/ case350:yes=0;oyes=0;/*退出選項(xiàng)*/ }/*endswitch*/

…菜單界面效果如圖5-2：圖5-2主界面5.3冒泡排序模塊編碼本模塊要實(shí)現(xiàn)冒泡排序的演示過程，因此在算法執(zhí)行過程中，每發(fā)生一次交換，都將在屏幕上顯示出來。關(guān)鍵技術(shù)：顯示輸出數(shù)組、畫交換箭頭、清除交換區(qū)域模塊實(shí)現(xiàn)步驟：1、實(shí)現(xiàn)數(shù)組的輸出顯示2、畫交換箭頭3、清除交換區(qū)域核心代碼實(shí)現(xiàn)如下：這里我們主要要解決的問題是在圖形模式下輸出整個(gè)待排序的數(shù)組元素，還有就是在交換過程中高亮度顯示要交換的兩個(gè)數(shù)，并畫出交換箭頭，其它要注意的是具體排序過程中判斷發(fā)生交換的標(biāo)志，以及結(jié)束標(biāo)志和手動(dòng)和電腦自動(dòng)標(biāo)志。實(shí)現(xiàn)數(shù)組的輸出顯示專門定義一個(gè)函數(shù)來解決數(shù)組顯示的問題，主要代碼如下：voidPr(inta[],intn)/*輸出數(shù)組*/{inti;charnum[5];settextstyle(0,0,2);/*設(shè)置輸出樣式*/setcolor(GREEN);/*設(shè)置輸出顏色*/for(i=100;i<500;i+=50)/*i控制顯示位置和計(jì)算數(shù)組下標(biāo)*/{sprintf(num,"%d",a[(i-100)/50]);/*將數(shù)值轉(zhuǎn)化為字符串*/outtextxy(i,n,num);/*輸出字符串*/}}畫交換箭頭這里用畫線函數(shù)畫五根線組成一雙向箭頭線來表示兩個(gè)數(shù)發(fā)生交換，代碼如下：voidDrawChange(inti,intj)/*畫交換箭頭*/{setcolor(6);line(j*50+120,i+8,j*50+140,i+8);/*按給出的坐標(biāo)位置畫直線*/line(j*50+120,i+8,j*50+120+5,i+4);line(j*50+120,i+8,j*50+120+5,i+12);line(j*50+140,i+8,j*50+140-5,i+4);line(j*50+140,i+8,j*50+140-5,i+12);}清除交換區(qū)域數(shù)據(jù)交換過程中要注意的問題：因?yàn)槿绻麅蓚€(gè)數(shù)發(fā)生交換的話，首先將這兩個(gè)數(shù)加亮顯示。這兩個(gè)數(shù)將交換位置，因此得將交換好后的數(shù)據(jù)重新顯示在數(shù)組中來，這樣就得覆蓋掉以前的數(shù)據(jù)，這里我們用畫黑矩形的方式把這行給刪除，具體代碼如下：…inti,j,t,flag;charnum1[5],num2[5];for(i=0;i<n-1;i++)/*冒泡排序*/{flag=0;/*設(shè)置數(shù)據(jù)交換標(biāo)志*/for(j=0;j<n-1-i;j++){ Pr(a,i*40+80);/*輸出數(shù)*/ setcolor(BLUE);/*輸出要比較的兩個(gè)數(shù)*/ sprintf(num1,"%d",a[j]);/*將兩個(gè)數(shù)字轉(zhuǎn)成字符串輸出*/ outtextxy(100+j*50,i*40+80,num1); sprintf(num2,"%d",a[j+1]); outtextxy(100+(j+1)*50,i*40+80,num2); sleep(1);/*暫停運(yùn)行一秒*/ setfillstyle(SOLID_FILL,BLACK); bar(0,i*40+60,640,i*40+100);*//*只顯示當(dāng)前兩個(gè)要交換的數(shù)據(jù)*/ if(a[j]>a[j+1])/*如果前面的大于后面的*/ {flag=1;/*置交換標(biāo)志*/ DrawChange(i*40+80,j);/*畫交換箭頭*/ setcolor(RED); outtextxy(100+j*50,i*40+80,num1); outtextxy(100+(j+1)*50,i*40+80,num2); t=a[j];/*交換*/ a[j]=a[j+1]; a[j+1]=t; sleep(1); setfillstyle(SOLID_FILL,BLACK);/*黑矩型的方式把這行給刪除*/ bar(0,i*40+60,640,i*40+100);…演示效果如圖5-3：圖5-3冒泡排序演示5.4漢諾塔模塊編碼漢諾塔問題是一個(gè)經(jīng)典的遞歸問題。它給出的圓盤移動(dòng)條件是：一次僅能移動(dòng)一個(gè)盤，且不允許大盤放在小盤的上面[1]。算法演示思想[10]：設(shè)要解決的的漢諾塔共有Ｎ個(gè)圓盤，對(duì)Ａ桿上的全部Ｎ個(gè)圓盤從小到大順序編號(hào)，最小的圓盤為１號(hào)，次之為２號(hào)，依次類推，則最下面的圓盤的編號(hào)為Ｎ。第一步：先將問題簡(jiǎn)化。假設(shè)Ａ桿上只有一個(gè)圓盤，即漢諾塔只有一層Ｎ１，則只要將１號(hào)盤從Ａ桿上移到Ｂ桿上即可。第二步：對(duì)於一個(gè)有Ｎ（Ｎ＞１）個(gè)圓盤的漢諾塔，將Ｎ個(gè)圓盤分成兩部分：上面的Ｎ－１個(gè)圓盤和最下面的Ｎ號(hào)圓盤。第三步：將“上面的Ｎ－１個(gè)圓盤”看成一個(gè)整體，為了解決Ｎ個(gè)圓盤的漢諾塔，可以按下面圖示的方式逕行操作：將Ａ桿上面的Ｎ－１個(gè)盤子，借助Ｂ桿，移到Ｃ桿上；圖5-4漢諾塔解決方法示意圖（1）將Ａ桿上剩余的Ｎ號(hào)盤子移到Ｂ桿上；圖5-5漢諾塔解決方法示意圖（2）將Ｃ桿上的Ｎ－１個(gè)盤子，借助Ａ桿，移到Ｂ桿上。圖5-6漢諾塔解決方法示意圖（3）按照上面的想法，我們要演示的就是具體的移盤操作。關(guān)鍵技術(shù)：畫盤子、移盤、顯示移盤步驟實(shí)現(xiàn)步驟：1、畫盤子；2、移盤、顯示移盤步驟。核心代碼實(shí)現(xiàn)如下：畫盤子首先定義一下盤子的結(jié)構(gòu)：structH{intdata[15];/*存放每個(gè)盤的代號(hào)*/inttop;/*每個(gè)塔的具體高度*/}num[3];/*三個(gè)塔*/接下來要定義一些標(biāo)志變量來判斷運(yùn)行方式，比如：intcomputer=1;/*自動(dòng)控制與手動(dòng)控制的標(biāo)志*/intspeed=0;/*全局變量speed主要是演示過程的速度*/然后要處理輸入數(shù)據(jù)越界的情況，因?yàn)楸P子個(gè)數(shù)過多，將很難實(shí)現(xiàn)，因此這里以0<n<10為界限，越界的話n當(dāng)10處理。代碼如下：…if(n<1||n>10)n=10;/*越界的話n當(dāng)10處理*/…下面來開始畫盤子：首先初始化三個(gè)地方塔的高度，代碼如下：…for(i=0;i<3;i++)num[i].top=-1;/*三個(gè)地方的高度開始都為-1*/…然后畫一開始的塔座A上的盤子，代碼如下：…for(i=0;i<n;i++)/*畫一開始的塔座A上的盤子*/{num[0].top++;/*棧的高度加1*/num[0].data[num[0].top]=i;/*最大的盤子代號(hào)為0，依次為1，2，…n-1*/color=num[0].data[num[0].top]+1;/*盤子的顏色代碼為棧頂盤子代號(hào)加1*/setfillstyle(SOLID_FILL,color);bar(100-(33-3*num[0].data[num[0].top]),400-20*i-8,100+(33-3*num[0].data[num[0].top]),400-20*i+8);/*畫矩形*/}setcolor(YELLOW);outtextxy(180,450,"anykeytocontinue");settextstyle(0,0,2);outtextxy(90,420,"A");/*塔座標(biāo)志*/outtextxy(240,420,"B");outtextxy(390,420,"C");…移盤、顯示移盤步驟接下來要做的解決移盤問題并顯示移盤步驟，這個(gè)過程的代碼如下：…inti;charnum1[3],num2[3];sprintf(num1,"%c",x-32);/*將小寫變成大寫，并轉(zhuǎn)換成字符串輸出*/sprintf(num2,"%c",y-32);setfillstyle(SOLID_FILL,BLACK);/*把原來的地方移去涂黑*/bar(0,0,640,60);setcolor(RED);outtextxy(150,30,num1);/*輸出移動(dòng)過程*/outtextxy(200,30,">");outtextxy(310,30,num2);settextstyle(0,0,2);setfillstyle(SOLID_FILL,BLACK);/*把原來的地方移去涂黑*/bar(100+150*(x-97)-(33-3*num[x-97].data[num[x-97].top]),400-20*num[x-97].top-8,100+150*(x-97)+(33-3*num[x-97].data[num[x-97].top]),400-20*num[x-97].top+8);num[y-97].top++;/*入棧，目標(biāo)點(diǎn)的top加1*/num[y-97].data[num[y-97].top]=num[x-97].data[num[x-97].top];/*在目標(biāo)點(diǎn)盤子的代號(hào)與源點(diǎn)盤子的代號(hào)相同*/num[x-97].top--;/*出棧，原來地方的top減1*/setfillstyle(SOLID_FILL,num[y-97].data[num[y-97].top]+1);/*盤子顏色代碼是棧頂盤子代號(hào)加1*/bar(100+150*(y-97)-(33-3*num[y-97].data[num[y-97].top]),400-20*num[y-97].top-8,100+150*(y-97)+(33-3*num[y-97].data[num[y-97].top]),400-20*num[y-97].top+8);…有個(gè)問題要注意的是怎么實(shí)現(xiàn)手動(dòng)控制，其實(shí)用下面的代碼就可以了：…if(computer)/*自動(dòng)控制就用sleep延時(shí)函數(shù)*/sleep(speed);/*延時(shí)函數(shù)*/elsegetch();/*手動(dòng)控制的話就自己按鍵盤來控制*/…演示效果如圖5-7：圖5-7漢諾塔演示5.5二叉樹遍歷模塊編碼本模塊演示思想[10]：由系統(tǒng)或者手動(dòng)建立一棵二叉樹，然后依次對(duì)其進(jìn)行三種遍歷，每遍歷到一個(gè)結(jié)點(diǎn)，將那個(gè)結(jié)點(diǎn)亮點(diǎn)顯示，并在屏幕上輸出遍歷序列[2]。關(guān)鍵技術(shù)：畫二叉樹、圖形模式下顯示創(chuàng)建好的樹、遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)模塊實(shí)現(xiàn)步驟：1、畫二叉樹；2、圖形模式下顯示創(chuàng)建好的樹；3、清除二叉樹區(qū)域；4、遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)。核心代碼實(shí)現(xiàn)如下：畫二叉樹首先定義一下二叉樹接點(diǎn)的結(jié)構(gòu)以及一些基本變量標(biāo)志位：intnodeNUM=0;/*統(tǒng)計(jì)當(dāng)前的結(jié)點(diǎn)數(shù)字,最多26個(gè)*/charway;/*自動(dòng)建立樹和手動(dòng)建立樹的標(biāo)志,2手動(dòng),1自動(dòng)*/intflag;/*單步執(zhí)行與自動(dòng)執(zhí)行的標(biāo)志*/charstr[3];/*顯示結(jié)點(diǎn)數(shù)據(jù)的字符串*/typedefstructTREE{chardata;/*樹的結(jié)點(diǎn)數(shù)據(jù)*/structTREE*lchild;structTREE*rchild;intx;/*樹的x坐標(biāo)*/inty;/*樹的y坐標(biāo)*/}Tree;structOUTPUT{intx;/*三種遍歷的x坐標(biāo)*/inty;/*三種遍歷的y坐標(biāo)*/intnum;}s;要進(jìn)行二叉樹的遍歷，首先得創(chuàng)建一棵樹，這里我們分兩步走：一、我們先進(jìn)行文本模式下的創(chuàng)建樹；二、用圖形顯示創(chuàng)建好的樹。接下來我們先進(jìn)行第一步，代碼如下：首先我們對(duì)數(shù)據(jù)越界進(jìn)行處理，如下：…if(h==5||nodeNUM==9)/*如果樹的層次已經(jīng)到5或者結(jié)點(diǎn)數(shù)到達(dá)9個(gè)就自動(dòng)返回NULL*/ {returnNULL;}…具體建樹過程代碼：Tree*InitTree(inth,intt,intw){charch;Tree*node;if(way=='1')/*自動(dòng)建立的賦值*/{ch=65+random(25);node=(Tree*)malloc(sizeof(Tree));node->data=ch;node->x=t;/*樹的x坐標(biāo)是傳遞過來的橫坐標(biāo)*/node->y=h*50;/*樹的y坐標(biāo)與層次大小有關(guān)*/nodeNUM++;node->lchild=InitTree(h+1,t-w,w/2);node->rchild=InitTree(h+1,t+w,w/2);}if(way=='2')/*手動(dòng)建立需要自己輸入*/{if(h==5||nodeNUM==9)/*如果樹的層次已經(jīng)到5或者結(jié)點(diǎn)樹到達(dá)9就自動(dòng)返回NULL*/ {returnNULL;}ch=getch();printf("%c",ch);node=(Tree*)malloc(sizeof(Tree));node->data=ch;node->x=t;/*樹的x坐標(biāo)是傳遞過來的橫坐標(biāo)*/node->y=h*50;/*樹的y坐標(biāo)與層次大小有關(guān)*/nodeNUM++;node->lchild=InitTree(h+1,t-w,w/2);node->rchild=InitTree(h+1,t+w,w/2);}returnnode;}圖形模式下顯示創(chuàng)建好的樹用圖形顯示創(chuàng)建好的樹代碼如下：voidDrawTree(Tree*t){if(t!=NULL){setcolor(BLACK);setfillstyle(SOLID_FILL,BLACK);fillellipse(t->x,t->y,9,9);setcolor(WHITE);circle(t->x,t->y,10);/*畫圓*/sprintf(str,"%c",t->data);/*將內(nèi)容轉(zhuǎn)換成字符串輸出*/outtextxy(t->x-3,t->y-2,str);if(t->lchild!=NULL)/*左子樹*/{ line(t->x-5,t->y+12,t->lchild->x+5,t->lchild->y-12); DrawTree(t->lchild);}if(t->rchild!=NULL)/*右子樹*/{ line(t->x+5,t->y+12,t->rchild->x-5,t->rchild->y-12); DrawTree(t->rchild);}}}清除二叉樹區(qū)域在遍歷二叉樹之前，我們要注意或者是思考一個(gè)問題，當(dāng)我們對(duì)一棵二叉樹進(jìn)行了先序遍歷之后，我們馬上還要對(duì)它進(jìn)行余下的中序遍歷和后序遍歷操作，因此要求二叉樹恢復(fù)到遍歷前的樣子，因此要求我們局部清屏，這里我們用畫黑矩形的方式實(shí)現(xiàn)[10]，代碼如下：voidClrScr();/*清空樹的區(qū)域*/{setcolor(BLACK);setfillstyle(SOLID_FILL,BLACK);bar(0,20,640,280);}遍歷時(shí)顯示每個(gè)結(jié)點(diǎn)這個(gè)過程要做的事情是填充結(jié)點(diǎn)、將遍歷次序用數(shù)字顯示在樹的結(jié)點(diǎn)上和輸出遍歷序列。它的具體代碼如下：voidDrawNode(Tree*t,intcolor){setfillstyle(SOLID_FILL,color);fillellipse(t->x,t->y,10,10);setcolor(RED);sprintf(str,"%c",t->data);/*將內(nèi)容轉(zhuǎn)換成字符串輸出*/outtextxy(t->x-3,t->y-2,str);setcolor(color);outtextxy(s.x,s.y,str);setcolor(RED);sprintf(str,"%d",s.num);/*將遍歷次序用數(shù)字顯示在樹的結(jié)點(diǎn)上*/outtextxy(t->x-3,t->y-20,str);s.num++;sleep(1);}演示效果如圖5-8：圖5-8二叉樹演示5.6鏈表模塊編碼算法演示思想：用戶每輸入一個(gè)結(jié)點(diǎn)字符，產(chǎn)生一個(gè)結(jié)點(diǎn)，顯示過程。關(guān)鍵技術(shù)[10]：畫結(jié)點(diǎn)框、結(jié)點(diǎn)之間的連線模塊實(shí)現(xiàn)步驟：1、對(duì)創(chuàng)建鏈表前的界面進(jìn)行設(shè)計(jì)和初始化；2、畫結(jié)點(diǎn)框和連線3、對(duì)數(shù)據(jù)溢出進(jìn)行處理。核心代碼以及相關(guān)演示界面如下：對(duì)創(chuàng)建鏈表前的界面進(jìn)行設(shè)計(jì)和初始化首先定義一下鏈表結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)[4]：typedefcharElemType;typedefstructLNode{ ElemTypedata; structLNode*next; }LNode,*LinkList;接下來對(duì)創(chuàng)建鏈表前的界面進(jìn)行設(shè)計(jì)和初始化，核心代碼如下：…DestroyList_L(head); InitList_L(head); length=ListLength_L(head); setfillstyle(SOLID_FILL,WHITE); setbkcolor(2); HZ16(10,460,20,14,"單鏈表的建立"); setfillstyle(SOLID_FILL,GREEN); setcolor(YELLOW); rectangle(2,100,10,120); line(11,115,19,115);line(19,115,15,112);line(19,115,15,118); HZ16(10,52,20,14,"請(qǐng)輸入結(jié)點(diǎn)的字符（按ＥＳＣ結(jié)束）：");…此處演示效果如圖5-9圖5-9單鏈表的建立(1)畫結(jié)點(diǎn)框和連線然后來畫結(jié)點(diǎn)框和連線，核心代碼如下：…ch=getch(); while(ch!=ESC&&length<7) { if(length!=0)/*畫結(jié)點(diǎn)與結(jié)點(diǎn)之間的連線*/[6] { line(60+83*(length-1),145,80+83*(length-1),145); line(80+83*(length-1),145,80+83*(length-1),115); line(80+83*(length-1),115,100+83*(length-1),115);line(96+83*(length-1),112,100+83*(length-1),115);line(96+83*(length-1),118,100+83*(length-1),115); } for(j=200;j>=0;j--) { bar(20+83*length,101+j,60+83*length,161+j); rectangle(20+83*length,100+j,60+83*length,160+j); line(20+83*length,130+j,60+83*length,130+j); sound(1000-30*j); delay(1); nosound(); } str[0]=ch; outtextxy(24+83*(length),103,str); ListInsert_L(head,length+1,ch); length=ListLength_L(head);…此處演示效果如圖5-10圖5-10單鏈表的建立(2)對(duì)數(shù)據(jù)溢出進(jìn)行處理。最后，我們要對(duì)數(shù)據(jù)溢出進(jìn)行處理，將最后接點(diǎn)的指針域置空，核心代碼如下：…settextstyle(0,HORIZ_DIR,1); outtextxy(24+83*(length-1),141,"NULL"); sleep(1); if(length==7) { bar(10,52,640,75);/*清除前面的文字*/ HZ16(10,52,20,YELLOW,"單鏈表長(zhǎng)度超出屏幕長(zhǎng)度，即將退出。");sleep(1); }…此處演示效果如圖5-11圖5-11單鏈表的建立(3)5.7退出模塊編碼關(guān)鍵技術(shù)：畫星星核心代碼實(shí)現(xiàn)如下[6]：首先先定義星星的一些基本參數(shù)：structStar/*星星的一些參數(shù)*/{intx;inty;intcolor;}star[200];然后定義一個(gè)函數(shù)用來畫燦爛星空[5]，代碼如下：voidDrawStar(void){inti;cleardevice();setcolor(GREEN);settextstyle(0,0,2);while(!kbhit()){for(i=0;i<200;i++)/*隨機(jī)生成星星*/{ star[i].x=random(640); star[i].y=random(480); star[i].color=random(13)+1;