數(shù)據(jù)結(jié)構(gòu)核心算法可視化系統(tǒng)設(shè)計與實(shí)現(xiàn)

慕巖磊，耿耀君

（西北農(nóng)林科技大學(xué)信息工程學(xué)院，咸陽712100）

0 引言

《數(shù)據(jù)結(jié)構(gòu)》是電子信息類專業(yè)一門十分重要的專業(yè)課，是《操作系統(tǒng)》、《計算機(jī)網(wǎng)絡(luò)》等諸多課程的先修課。編寫程序時，選擇優(yōu)良的數(shù)據(jù)結(jié)構(gòu)，可以提高算法效率以及系統(tǒng)質(zhì)量。如今我國的數(shù)據(jù)結(jié)構(gòu)教學(xué)，主要還是以“課本+PPT”的形式進(jìn)行，不僅枯燥而且使學(xué)生難以理解相關(guān)概念。故需要一種更加直觀有關(guān)的方法來幫助學(xué)生學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)。

1 系統(tǒng)實(shí)現(xiàn)

相比于文字，人們對圖形和動畫有著更加直觀的理解。利用它們來進(jìn)行學(xué)習(xí)，可以極大地提高學(xué)習(xí)效率。數(shù)據(jù)結(jié)構(gòu)核心算法可視化系統(tǒng)正好給學(xué)生及廣大計算機(jī)愛好者提供了一個這樣的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的良好環(huán)境。學(xué)生可以在該系統(tǒng)中選擇需要學(xué)習(xí)的數(shù)據(jù)結(jié)構(gòu)，通過觀看系統(tǒng)內(nèi)的標(biāo)準(zhǔn)算法的動畫演示進(jìn)行學(xué)習(xí)，也可以自己動手編寫程序，觀看自己所寫程序的運(yùn)行過程的動畫來學(xué)習(xí)。

如圖1 所示，該系統(tǒng)主要由界面和邏輯功能代碼兩個模塊組成。

界面模塊主要功能如下：

（1）接收用戶請求。

（2）對用戶請求做出響應(yīng)，進(jìn)行相應(yīng)的動畫演示。

圖1 系統(tǒng)模塊圖

邏輯功能代碼模塊主要功能如下：

（1）通過編譯器對程序進(jìn)行詞法分析和語法分析，如出現(xiàn)詞法或語法錯誤則報錯。

（2）對無語法錯誤的程序進(jìn)行語義分析，生成繪圖指令系列的中間代碼。

（3）繪圖指令解析程序?qū)L圖指令進(jìn)行解析，調(diào)用相應(yīng)的繪圖函數(shù)進(jìn)行動畫演示。

通過使用本系統(tǒng)，能將傳統(tǒng)的“課堂+多媒體”的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)方式，轉(zhuǎn)變?yōu)椤皠赢嬚故?自主動手編程”的模式。對于學(xué)生來說既能夠方便學(xué)生學(xué)習(xí)，又能夠提高學(xué)習(xí)者的動手編程能力。

2 實(shí)現(xiàn)方法

本系統(tǒng)開發(fā)將基于面向?qū)ο蟪绦蛟O(shè)計方法，采用增量迭代方式開發(fā)。

2.1 簡易編譯器

數(shù)據(jù)結(jié)構(gòu)計算機(jī)存儲、組織數(shù)據(jù)的方式，本質(zhì)上為一組抽象的概念，可以使用任何一種編程語言實(shí)現(xiàn)。本項(xiàng)目采用C 語言編譯器進(jìn)行開發(fā)。

編譯器主要負(fù)責(zé)對程序進(jìn)行詞法分析和語法分析，報告程序存在的詞法和語法錯誤。編譯器的開發(fā)遵循C89 標(biāo)準(zhǔn)，采用Flex+Bison+C++的技術(shù)。以下是具體被調(diào)用的相關(guān)內(nèi)容及步驟。

（1）詞法分析：系統(tǒng)后端接收到前端傳過來的程序源碼，對其進(jìn)行掃描，根據(jù)詞法規(guī)則識別單詞。若存在無法識別的單詞，則為詞法錯誤，需向前端發(fā)送錯誤消息。若不存在錯誤，則將該單詞轉(zhuǎn)化為指定的字符序列。

（2）語法分析：詞法分析得到的字符序列根據(jù)文法規(guī)則轉(zhuǎn)換為語法樹。遍歷語法樹，不符合C 語言文法結(jié)構(gòu)的部分將報告給前端界面。

（3）語義分析：審查每個語法成分的語義。若語義正確，則生成對應(yīng)的繪圖指令序列，否則向前端報錯。

編譯器開發(fā)過程如下：

（1）簡化C 語言詞法和文法

完整的C 語言所包含的內(nèi)容比較龐大復(fù)雜，開發(fā)完整的C 編譯器工作量大，且也沒有必要。根據(jù)系統(tǒng)需求，對C 語言進(jìn)行了適當(dāng)簡化，詞法部分去除了auto、extern 等16 個關(guān)鍵字，保留了余下的16 個關(guān)鍵字。此外，去除了>>、&等不常用運(yùn)算符。文法部分，刪減并修改了部分C 文法。如刪除了文法

abstract_declarator->pointer|direct_abstract_declara -tor|pointer direct_abstract_declarator，

將struct_declarator_list->struct_declarator|struct_declarator_list‘,’struct_declarator

修改為struct_declarator_list->declarator|struct_declarator_list‘,’declarator。

（2）詞法分析

通過使用Flex 語言，將C 語言的詞法規(guī)則用正規(guī)表達(dá)式編寫，得到對應(yīng)詞法規(guī)則文件。由Flex 翻譯器將該文件翻譯成一個C 語言源文件，之后將該文件由g++編譯，得到詞法分析器。詞法分析器能夠識別用戶源程序，將其轉(zhuǎn)換為指定的字符序列。如用戶程序存在詞法錯誤，如標(biāo)識符以數(shù)字開頭，則進(jìn)行報告。

（3）語法分析

將C 語言文法根據(jù)巴科斯范式（BNF）進(jìn)行編寫，定義規(guī)約方式。編譯完成后交由Bison 編譯器編譯得到y(tǒng).tab.h 和y.tab.c 文件。詞法分析得到的字符序列可由編譯得到的C 語言程序轉(zhuǎn)化為語法樹。遍歷語法樹通過C++語言程序?qū)崿F(xiàn)。若出現(xiàn)語法錯誤則向用戶報告錯誤。

（4）語義分析

語義分析程序采用C++語言開發(fā)，通過再次遍歷語法樹，進(jìn)而分析程序語義。生成的類匯編語言的繪圖指令序列以C 語言字符串的形式輸出。

2.2 繪圖指令

微觀上看，數(shù)據(jù)結(jié)構(gòu)算法的原子操作為：為數(shù)據(jù)申請內(nèi)存、釋放內(nèi)存空間、移動指針、訪問數(shù)組元素等。繪圖指令與這些原子操作相對應(yīng)，在底層將用戶自編的數(shù)據(jù)結(jié)構(gòu)算法程序規(guī)范化，便于后續(xù)繪圖操作的統(tǒng)一處理。

繪圖指令序列是編譯器的輸出，它是標(biāo)準(zhǔn)程序和用戶自定義程序的另一種表示，目的是便于后續(xù)的繪圖操作。在繪圖指令中包含兩種指令：控制指令和繪圖指令?？刂浦噶畲碓闯绦蛑械姆种Ш脱h(huán)結(jié)構(gòu)。

繪圖指令借鑒匯編語言編寫，一條C 語言語句對應(yīng)多條繪圖指令，代表算法中的產(chǎn)生繪圖語義的原子操作。

2.3 繪圖指令解析程序

繪圖指令解析程序由C++語言編寫。該程序借鑒Win32 消息處理模型，實(shí)現(xiàn)繪圖指令到繪圖函數(shù)的對應(yīng)關(guān)系。

當(dāng)其接收到編譯器編譯生成的繪圖指令序列之后，繪圖指令解析程序?qū)χ噶钸M(jìn)行識別，決定所需要調(diào)用的繪圖函數(shù)。為了加快繪圖指令解析的速度，將采用哈希表等數(shù)據(jù)結(jié)構(gòu)來組織繪圖指令及繪圖函數(shù)。

2.4 界面動畫

繪圖動畫采用并行機(jī)制，系統(tǒng)調(diào)用繪圖函數(shù)進(jìn)行圖形繪制，對算法的執(zhí)行情況進(jìn)行展示。動畫演示的同時，將當(dāng)前動畫所對應(yīng)的核心代碼行也在代碼窗口標(biāo)注出來，代碼與動畫同時展示。每執(zhí)行一行代碼，都有相應(yīng)的動畫演示對其進(jìn)行解釋，二者同步，不出現(xiàn)延遲或超前的現(xiàn)象。

無論哪種數(shù)據(jù)結(jié)構(gòu)，其中包含大量結(jié)點(diǎn)。由于需要對數(shù)據(jù)結(jié)構(gòu)進(jìn)行動態(tài)演示，所以需要對結(jié)點(diǎn)進(jìn)行統(tǒng)一的操作和管理。自己定義數(shù)據(jù)結(jié)構(gòu)去管理這些結(jié)點(diǎn)是非常困難的，無法達(dá)到預(yù)期目的。故需要一種較為方便的方式來完成。通過使用Qt 的GraphicsView 框架，利用對模型和視圖結(jié)構(gòu)的圖形管理，從而實(shí)現(xiàn)對結(jié)點(diǎn)的管理。此外，GraphicsView 框架提供坐標(biāo)變換和圖元組等多種方便的功能，為對結(jié)點(diǎn)的操作提供便利。

對于一種數(shù)據(jù)結(jié)構(gòu)來說，選擇合適的結(jié)點(diǎn)表現(xiàn)形式能產(chǎn)生更好的繪制效果。對于順序表、鏈表等，選擇矩形繪制結(jié)點(diǎn)較好。而對于樹和圖等，則選擇圓形來進(jìn)行繪制。故我們采用兩個類：ball 類和rect 類對結(jié)點(diǎn)進(jìn)行管理和操作。其中ball 為圓形類，rect 為矩形類。

我們可以在不同的數(shù)據(jù)結(jié)構(gòu)上執(zhí)行不同的操作，故將一種數(shù)據(jù)結(jié)構(gòu)封裝為一個類，由該類對其進(jìn)行管理和操作。類中的一個函數(shù)對應(yīng)一種操作。

GraphicsView 框架結(jié)構(gòu)主要包含三個類：QGraphicsScene（容器）、QGraphicsView（視圖）和QGraphicsItem（圖形項(xiàng)）。QGraphicsView 提供一個可視的窗口，用于顯示場景中的項(xiàng)目，一個場景中可以有多個視口。QGraphicsScene 通過與之相連的QGraphicsView類來與外界進(jìn)行互操作。QGraphicsItem 是場景中各個項(xiàng)目的基礎(chǔ)類。ball 類和rect 類為QGraphicsItem 的子類，Item 類及其子類可以處理鼠標(biāo)點(diǎn)擊、移動、釋放等事件。一種數(shù)據(jù)結(jié)構(gòu)的算法動畫為一個函數(shù)，由一個場景QGraphicsScene 對象以及若干個Item 子類對象完成。在函數(shù)內(nèi)通過在適當(dāng)位置創(chuàng)建Item 類對象并將其加入場景中，配合定時器進(jìn)行展示。

2.5 用戶界面

界面由功能選擇菜單、動態(tài)的圖形演示、同步的算法程序代碼顯示、算法說明等部分組成。界面上方為功能選擇菜單，左側(cè)為算法選擇區(qū)，右下方為算法程序代碼同步演示區(qū)。正在執(zhí)行的語句以高亮顯示。隨著算法的執(zhí)行，高亮部分逐行移動算法圖形動態(tài)演示區(qū)的顯示區(qū)也跟著變化。中央?yún)^(qū)域?yàn)樗惴▌赢嬔菔緟^(qū)，它根據(jù)算法的執(zhí)行過程顯示對應(yīng)的動畫。界面下方為動畫速度調(diào)節(jié)，可以調(diào)整算法演示的速度。

用戶界面采用Qt 技術(shù)進(jìn)行開發(fā)。通過使用信號/槽機(jī)制，當(dāng)用戶發(fā)出請求時，相應(yīng)組件發(fā)出信號。與該信號建立的連接槽，則可以接收該信號并做出回應(yīng)，完成對用戶請求的反饋。

3 結(jié)語

本文介紹了一種基于自制編譯器和Qt 的數(shù)據(jù)結(jié)構(gòu)核心算法可視化系統(tǒng)的設(shè)計與開發(fā)。該系統(tǒng)包含了簡易C 語言編譯器、繪圖指令解析程序、用戶界面等組成部分。用戶可以觀看系統(tǒng)內(nèi)的標(biāo)準(zhǔn)程序的運(yùn)行動畫來學(xué)習(xí)，亦可自己動手編寫程序，觀看其動畫來。系統(tǒng)通過自制編譯器來將程序轉(zhuǎn)化為自定義指令，利用Qt中GraphicsView 框架來進(jìn)行繪圖動畫操作，出色地完成了預(yù)期功能。在《數(shù)據(jù)結(jié)構(gòu)》課程中使用本系統(tǒng)，可以把“學(xué)與練”結(jié)合起來，提高學(xué)生的學(xué)習(xí)興趣，降低學(xué)習(xí)難度。此軟件在經(jīng)過后期的一些細(xì)節(jié)優(yōu)化后，即將投入到以后的《數(shù)據(jù)結(jié)構(gòu)》課程中，相信它可以使本來抽象難懂的數(shù)據(jù)結(jié)構(gòu)變得簡單易學(xué)起來，成為學(xué)生們在學(xué)習(xí)過程中的良師益友。