慕巖磊，耿耀君

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

0 引言

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

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

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

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

界面模塊主要功能如下：

（1）接收用戶請(qǐng)求。

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

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

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

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

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

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

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

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

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

2.1 簡(jiǎn)易編譯器

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

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

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

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

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

編譯器開(kāi)發(fā)過(guò)程如下：

（1）簡(jiǎn)化C 語(yǔ)言詞法和文法

完整的C 語(yǔ)言所包含的內(nèi)容比較龐大復(fù)雜，開(kāi)發(fā)完整的C 編譯器工作量大，且也沒(méi)有必要。根據(jù)系統(tǒng)需求，對(duì)C 語(yǔ)言進(jìn)行了適當(dāng)簡(jiǎn)化，詞法部分去除了auto、extern 等16 個(gè)關(guān)鍵字，保留了余下的16 個(gè)關(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）詞法分析

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

（3）語(yǔ)法分析

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

（4）語(yǔ)義分析

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

2.2 繪圖指令

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

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

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

2.3 繪圖指令解析程序

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

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

2.4 界面動(dòng)畫(huà)

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

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

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

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

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

2.5 用戶界面

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

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

3 結(jié)語(yǔ)

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