【導讀】切的關(guān)系，無論是編譯程序還是操作系統(tǒng)，都涉及到數(shù)據(jù)元素在存儲器中的分配問題。在研究信息檢索時也必須考慮如何組織數(shù)據(jù)，以便查找和存取數(shù)據(jù)元素更方便。它是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。系統(tǒng)及其他系統(tǒng)程序和大型應(yīng)用程序的重要基礎(chǔ)。講解了線性表、堆棧和隊列、樹、圖等數(shù)據(jù)結(jié)構(gòu)的概念，該系統(tǒng)具有操作便捷、形。促進作用，而且具有一定的實用價值，能有效地改善數(shù)據(jù)結(jié)構(gòu)算法教學的質(zhì)量和效率，對于其他類似系統(tǒng)也有很大的借鑒意義。

　　

【正文】 ，則應(yīng)將其每個結(jié)點與完全二叉樹上的結(jié)點相對照，存儲在一維數(shù)組的相應(yīng)分量中，如圖 319 所示，二叉樹的順序存儲結(jié)構(gòu)如圖 320 所示 ，圖中以“ 0”表示不存在此結(jié)點。 開始 輸入內(nèi)容 左子樹 數(shù)字大小 右子樹 二叉樹形成 結(jié)束 圖 318 數(shù)組二叉樹流程圖 i/2 i i+1 2i 2i+1 2i+2 2i+3 根據(jù)以上思想，我設(shè)計的結(jié)構(gòu)二叉樹 是順序存儲結(jié)構(gòu)的一種表現(xiàn)，該程序的運行界面如圖 321 所示。 圖 321結(jié)構(gòu)二叉樹的顯示圖 i+1 2i+2 2i+3 i 2i 2i+1 (b) 圖 319 完全二叉樹中結(jié)點 i和 i+1的左右孩子 (a) 結(jié)點 i和 i+1在同一層 (b) 結(jié)點 i和 i+1不在同一層 (c) 6 1 2 3 4 5 0 0 0 0 7 圖 320 二叉樹的順序儲存結(jié)構(gòu) (3)在菜單中，我們通過調(diào)用 WinExec 函數(shù)，以執(zhí)行外部命令的方式，調(diào)用 類別二叉樹 .exe 程序，來完成類別二叉樹的演示。源代碼如下： NewFileName=ExtractFilePath(ApplicationExeName)+類別二叉樹 .exe。 i=WinExec((),SW_SHOWNORMAL)。 在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特性的結(jié)點，或者對樹中全部結(jié)點逐一進行某種處理。這就提出了了一個遍歷二叉樹的問題，如果按某條搜索路徑巡訪樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。“訪問”的含義很廣，可以是對結(jié)點做各種處理，如輸出結(jié)點的信息等。遍歷對線性結(jié)點來說，是容易解決的，而對二叉樹則不然，由于 二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點都可能有兩課子樹，因而需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點能排列在一個線性隊列上，從而便于遍歷。 二叉樹的遞歸定義可知，二叉樹是由 3 個基本單元組成：根結(jié)點、左子樹、右子樹。因此，若能依次遍歷這三部分，便是遍歷了整個二叉樹。假如以 L、 D、 R 分別表示遍歷左子樹、訪問根結(jié)點和遍歷右子樹，則可以 DLR、 LDR、 LRD、 DRL、 RDL、 RLD 這六種遍歷二叉樹的方案。若限定先左后右，則只有前三種情況，分別稱之先序遍歷、中序遍歷和后序遍歷。 遍歷二叉樹的遞歸算法定義：先序遍歷二叉樹的操作 定義，若二叉樹為空，則空操作，否則訪問根結(jié)點，先序遍歷左子樹，先序遍歷右子樹；中序遍歷二叉樹的操作定義，若二叉樹為空，則空操作，否則中序遍歷左子樹，訪問根結(jié)點，中序遍歷右子樹；后序遍歷二叉樹的操作定義，若二叉樹為空，則空操作，否則后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點。 根據(jù)以上思想，我設(shè)計了一個查找結(jié)點的類別二叉樹，運行界面如圖 323 所示。 開始 構(gòu)件二叉樹 顯示內(nèi)容結(jié)構(gòu) 結(jié)束 圖 322 結(jié)構(gòu)二叉樹流程圖 圖 323 二叉樹的基本操作顯示界面 操作模塊的設(shè)計 本部 分主要由兩個文本輸入 /輸出和 3 個按紐組成，如圖 32 所示。主要顯示各種算法的說明，輔助大家更好地學習。 代碼顯示： // void __fastcall TForm1::N10Click(TObject *Sender) { Memo1LinesLoadFromFile()。 } // void __fastcall TForm1::N11Click(TObject *Sender) { Memo1LinesLoadFromFile()。 } // 開始 加入結(jié)點 數(shù)大小 左子樹 右子樹 形成二叉樹 查找結(jié)點 結(jié)束 圖 324 類別二叉樹流程圖 void __fastcall TForm1::N12Click(TObject *Sender) { Memo1LinesLoadFromFile()。 } // void __fastcall TForm1::N13Click(TObject *Sender) { Memo1LinesLoadFromFile()。 } // void __fastcall TForm1::N14Click(TObject *Sender) { Memo1LinesLoadFromFile()。 } // void __fastcall TForm1::Button2Click(TObject *Sender) { Memo1LinesText=。 Memo1SetFocus()。 Memo2LinesText=。 Memo2SetFocus()。 } // void __fastcall TForm1::Button1Click(TObject *Sender) { Memo1LinesSaveToFile()。 } // void __fastcall TForm1::Button3Click(TObject *Sender) { Memo2LinesLoadFromFile()。 } // 4 系統(tǒng)操作 主菜單操作 主菜單運行如圖 32 所示。 菜單選擇，清空文本輸入，開始數(shù)據(jù)結(jié)構(gòu)的算法學習。 線性表操作 線性表 運行如圖 3 3 3 315 所示。 鏈表概念 左邊的數(shù)字是用數(shù)組列出來的；左邊的數(shù)字，則是把輸入所新增的鏈表顯示出來。 鏈表模型 在操作面板中輸入內(nèi)容后，單擊“按紐”即可看到數(shù)據(jù)從前方插入。在操作面板下放，有按照當時時間的先后列出的信息；單擊“清場”按紐即可清除顯示面板對象。在操作面板中輸入內(nèi)容后，單擊“奪后”按紐，即可看到數(shù)據(jù)從后面接續(xù)；當數(shù)據(jù)超出面板時， 以箭頭變化代表存取變化。單擊“列席”即可將已建立的鏈表數(shù)據(jù)輸出于文字表格中，單擊“清場”則可清除其內(nèi)容。 鏈表操作 單擊“加入”按紐以輸入數(shù)據(jù)，連續(xù)建立 7 個鏈表結(jié)點后單擊“顯示”按紐，即得到右方圖示的內(nèi)容；輸入“數(shù)據(jù)五”單擊“查找”按紐，就得到數(shù)據(jù) 5 在第 3 結(jié)點的信息；單擊“刪除”按紐，即跳出刪除結(jié)點的畫面，列表顯示中也少了數(shù)據(jù)五。單擊“顯示”按紐，結(jié)點 3 的位置已由數(shù)據(jù)四取代，數(shù)據(jù)四已接在數(shù)據(jù)六的后方；但我們在單擊“刪除”或“查找”按紐查找數(shù)據(jù)五的時候，就出現(xiàn)沒有這筆數(shù)據(jù)的畫面，單擊“刪除”按紐，面板將鏈表數(shù)據(jù)清除；再單擊“顯示”按紐即可看到鏈表中已沒有鏈及鏈表的結(jié)點了。 雙向鏈表 畫面初始設(shè)置加入指向為“由前”，在鏈表顯示窗口中單擊鼠標右鍵，即彈出快捷菜單，單擊“加入結(jié)點”，連續(xù)加入兩筆數(shù)據(jù)即得圖示的結(jié)果，請隨時注意指針的變化；在“加入指向”面板中點選“往后”，再按右鍵加入兩筆數(shù)據(jù)，即可看見這兩筆數(shù)據(jù)是向后接續(xù)的；單擊鼠標右鍵，選擇“插入接點”選項，即彈出“插入數(shù)據(jù)輸入框”，要求我們安排位置，我們將新數(shù)據(jù)計劃放在數(shù)據(jù)一后方，因此輸入數(shù)據(jù)一；之后彈出“數(shù)據(jù)輸入”的要求，我們輸入數(shù)據(jù)五；彈出項 目管理對話框，告訴我們新結(jié)點的位置在第 3 結(jié)點；可發(fā)現(xiàn)圖中數(shù)據(jù)五已加入成為鏈表的第 3 個結(jié)點。當我們插入結(jié)點的安排位置，是串列中所沒有的時候，就會跳出右方的提示信息；單擊“刪除結(jié)點”，即彈出刪除結(jié)點輸入對話框，要求我們輸入結(jié)點內(nèi)容，我們輸入“數(shù)據(jù)一”；項目管理對話框返回刪除第幾個結(jié)點的信息；單擊”顯示結(jié)點“選項，選擇”右前“或”由后“選項，即可將現(xiàn)有的鏈表內(nèi)容由前往后排顯示于字符傳表格中；圖是由后往前排顯示的結(jié)果；選擇”清楚數(shù)據(jù)“，可以看到數(shù)據(jù)和面板清楚的非常干凈，如果還擔心有結(jié)點的殘留，可以顯示看看是否如此。 如果看不清楚鏈表數(shù)據(jù)與指針動向的話，可以拉動右下方控制條來調(diào)整顯示窗口的背景亮度 樹操作 樹 運行如圖 317 321 323 所示 數(shù)據(jù)二叉樹 輸入幾個數(shù)字就建立起二叉樹的結(jié)構(gòu)，請?zhí)貏e注意數(shù)字的大小與左右連接的關(guān)系；當輸入的時候下方會出現(xiàn)輸入值在樹的第幾層信息。當輸入數(shù)值落于第 5 層之外，程序?qū)@示超出信息。 結(jié)構(gòu)二叉樹 輸入幾個數(shù)字，再點選結(jié)點內(nèi)容，就產(chǎn)生如圖示，將鼠標指針放在結(jié)點上方就會看到結(jié)點索引值；本范例索引值由 0 開始，左、右子樹對應(yīng)索引值，請留心樹狀結(jié)構(gòu)連接的方式，在構(gòu)建樹的 同時，也順便比較內(nèi)容顯示；在本章二叉樹的構(gòu)建，都是在運行時產(chǎn)生新的類別控件，請留意圖形配置與連接的方式。 類二叉樹 在程序中構(gòu)建二叉樹，輸入一個存在的結(jié)點，單擊“查找”按紐，就會產(chǎn)生搜索結(jié)果，內(nèi)容為查找的結(jié)點變?yōu)閳A角長方形且閃爍 3 次后變回橢圓形。 算法說明操作 操作運行如圖 32 所示。 除了可以查看算法說明，使用者可以在第一個文本輸入中寫學習心得，并保存，下次運行系統(tǒng)，單擊顯示修改內(nèi)容按紐，可以在第二個文本輸入中看到自己上次學習的記錄。 結(jié)束語 通過幾個月的學習、實踐， 在老師 和同學幫助下，我所做的演示系統(tǒng)基本成型，下面闡述一下系統(tǒng)的有關(guān)情況。 系統(tǒng)概述： (1)在對數(shù)據(jù)結(jié)構(gòu)課程和 c++builder 開發(fā)工具的基礎(chǔ)上，我們做了線性表、堆棧、隊列、樹、圖 5 個基本結(jié)構(gòu)的算法演示； (2)數(shù)據(jù)結(jié)構(gòu)做為一門計算機的核心課程，我們在做設(shè)計的過程中，更理解到了這一點，本系統(tǒng)都是在基礎(chǔ)結(jié)構(gòu)算法的延伸； (3)本系統(tǒng)可以具有操作便捷、形象生動等特點， 對于深化對數(shù)據(jù)結(jié)構(gòu)算法的理解，提高計算機程序設(shè)計水平具有很好的促進作用，能有效地改善數(shù)據(jù)結(jié)構(gòu)算法教學的質(zhì)量和效率，在學習和生活中，具有較廣泛的應(yīng)用，值得做 進一步的研究和推廣。 問題不足： (1)該系統(tǒng)相對復(fù)雜的演示系統(tǒng)稍顯簡易，只實現(xiàn)了結(jié)構(gòu)的基礎(chǔ)操作，對復(fù)雜算法的演示比較少，如多項式運算、最小生成樹等等； (2)在多數(shù)演示過程中， 沒能實現(xiàn)單步演示 。 這幾個月緊張的畢業(yè)設(shè)計，使我系統(tǒng)地體驗了一個簡單想法轉(zhuǎn)化為一個實際計算機程序項目的整個過程，這個過程使我對 “ 軟件工程 ” 、 “ 可視化編程 ” 等知識有了更切身的體會，提高了我對計算機編程的駕馭能力 本系統(tǒng)的實現(xiàn)主要運用了數(shù)據(jù)結(jié)構(gòu)和 c++ builder 開發(fā)工具，讓我更深刻地理解了數(shù)據(jù)結(jié)構(gòu)這門課程的重要性，也熟悉了 c++ builder 開發(fā)工具， 整個的編程過程，就是我不斷發(fā) 現(xiàn)自己的不足之處、并不斷彌補自己不足之處的過程，但是往往是發(fā)現(xiàn)的問題比彌補上的漏洞多得多 …… 程序的不足之處、過程和函數(shù)的使用方法等等都使我覺得自己應(yīng)該更加地努力。相信在不斷的努力后，我會進一步提高自己的水平，作出更好的成績。 謝 辭 在這四個月的畢業(yè)設(shè)計中，使我深深的認識到制作一個完整的軟件系統(tǒng)是一個既龐大又細致的工作。由于我是名新手，對制作一個這樣的完整的“數(shù)據(jù)結(jié)構(gòu)算法演示系統(tǒng)”有著許多的困難。而在畢業(yè)設(shè)計的這段期間，我要特別感謝 我的指導老師。在畢業(yè)設(shè)計期間，老師淵博的學識，誨人不倦的精神，嚴謹治學的態(tài)度，以及對我們的嚴格要求都使我深深難忘，從中受益非淺。從她身上我學到了很多很多，這些都將指導我今后的