數據結構核心算法可視化系統設計與實現

慕巖磊，耿耀君

（西北農林科技大學信息工程學院，咸陽712100）

0 引言

《數據結構》是電子信息類專業一門十分重要的專業課，是《操作系統》、《計算機網絡》等諸多課程的先修課。編寫程序時，選擇優良的數據結構，可以提高算法效率以及系統質量。如今我國的數據結構教學，主要還是以“課本+PPT”的形式進行，不僅枯燥而且使學生難以理解相關概念。故需要一種更加直觀有關的方法來幫助學生學習數據結構。

1 系統實現

相比于文字，人們對圖形和動畫有著更加直觀的理解。利用它們來進行學習，可以極大地提高學習效率。數據結構核心算法可視化系統正好給學生及廣大計算機愛好者提供了一個這樣的學習數據結構的良好環境。學生可以在該系統中選擇需要學習的數據結構，通過觀看系統內的標準算法的動畫演示進行學習，也可以自己動手編寫程序，觀看自己所寫程序的運行過程的動畫來學習。

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

界面模塊主要功能如下：

（1）接收用戶請求。

（2）對用戶請求做出響應，進行相應的動畫演示。

圖1 系統模塊圖

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

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

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

（3）繪圖指令解析程序對繪圖指令進行解析，調用相應的繪圖函數進行動畫演示。

通過使用本系統，能將傳統的“課堂+多媒體”的數據結構學習方式，轉變為“動畫展示+自主動手編程”的模式。對于學生來說既能夠方便學生學習，又能夠提高學習者的動手編程能力。

2 實現方法

本系統開發將基于面向對象程序設計方法，采用增量迭代方式開發。

2.1 簡易編譯器

數據結構計算機存儲、組織數據的方式，本質上為一組抽象的概念，可以使用任何一種編程語言實現。本項目采用C 語言編譯器進行開發。

編譯器主要負責對程序進行詞法分析和語法分析，報告程序存在的詞法和語法錯誤。編譯器的開發遵循C89 標準，采用Flex+Bison+C++的技術。以下是具體被調用的相關內容及步驟。

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

（2）語法分析：詞法分析得到的字符序列根據文法規則轉換為語法樹。遍歷語法樹，不符合C 語言文法結構的部分將報告給前端界面。

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

編譯器開發過程如下：

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

完整的C 語言所包含的內容比較龐大復雜，開發完整的C 編譯器工作量大，且也沒有必要。根據系統需求，對C 語言進行了適當簡化，詞法部分去除了auto、extern 等16 個關鍵字，保留了余下的16 個關鍵字。此外，去除了>>、&等不常用運算符。文法部分，刪減并修改了部分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 語言的詞法規則用正規表達式編寫，得到對應詞法規則文件。由Flex 翻譯器將該文件翻譯成一個C 語言源文件，之后將該文件由g++編譯，得到詞法分析器。詞法分析器能夠識別用戶源程序，將其轉換為指定的字符序列。如用戶程序存在詞法錯誤，如標識符以數字開頭，則進行報告。

（3）語法分析

將C 語言文法根據巴科斯范式（BNF）進行編寫，定義規約方式。編譯完成后交由Bison 編譯器編譯得到y.tab.h 和y.tab.c 文件。詞法分析得到的字符序列可由編譯得到的C 語言程序轉化為語法樹。遍歷語法樹通過C++語言程序實現。若出現語法錯誤則向用戶報告錯誤。

（4）語義分析

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

2.2 繪圖指令

微觀上看，數據結構算法的原子操作為：為數據申請內存、釋放內存空間、移動指針、訪問數組元素等。繪圖指令與這些原子操作相對應，在底層將用戶自編的數據結構算法程序規范化，便于后續繪圖操作的統一處理。

繪圖指令序列是編譯器的輸出，它是標準程序和用戶自定義程序的另一種表示，目的是便于后續的繪圖操作。在繪圖指令中包含兩種指令：控制指令和繪圖指令。控制指令代表源程序中的分支和循環結構。

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

2.3 繪圖指令解析程序

繪圖指令解析程序由C++語言編寫。該程序借鑒Win32 消息處理模型，實現繪圖指令到繪圖函數的對應關系。

當其接收到編譯器編譯生成的繪圖指令序列之后，繪圖指令解析程序對指令進行識別，決定所需要調用的繪圖函數。為了加快繪圖指令解析的速度，將采用哈希表等數據結構來組織繪圖指令及繪圖函數。

2.4 界面動畫

繪圖動畫采用并行機制，系統調用繪圖函數進行圖形繪制，對算法的執行情況進行展示。動畫演示的同時，將當前動畫所對應的核心代碼行也在代碼窗口標注出來，代碼與動畫同時展示。每執行一行代碼，都有相應的動畫演示對其進行解釋，二者同步，不出現延遲或超前的現象。

無論哪種數據結構，其中包含大量結點。由于需要對數據結構進行動態演示，所以需要對結點進行統一的操作和管理。自己定義數據結構去管理這些結點是非常困難的，無法達到預期目的。故需要一種較為方便的方式來完成。通過使用Qt 的GraphicsView 框架，利用對模型和視圖結構的圖形管理，從而實現對結點的管理。此外，GraphicsView 框架提供坐標變換和圖元組等多種方便的功能，為對結點的操作提供便利。

對于一種數據結構來說，選擇合適的結點表現形式能產生更好的繪制效果。對于順序表、鏈表等，選擇矩形繪制結點較好。而對于樹和圖等，則選擇圓形來進行繪制。故我們采用兩個類：ball 類和rect 類對結點進行管理和操作。其中ball 為圓形類，rect 為矩形類。

我們可以在不同的數據結構上執行不同的操作，故將一種數據結構封裝為一個類，由該類對其進行管理和操作。類中的一個函數對應一種操作。

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

2.5 用戶界面

界面由功能選擇菜單、動態的圖形演示、同步的算法程序代碼顯示、算法說明等部分組成。界面上方為功能選擇菜單，左側為算法選擇區，右下方為算法程序代碼同步演示區。正在執行的語句以高亮顯示。隨著算法的執行，高亮部分逐行移動算法圖形動態演示區的顯示區也跟著變化。中央區域為算法動畫演示區，它根據算法的執行過程顯示對應的動畫。界面下方為動畫速度調節，可以調整算法演示的速度。

用戶界面采用Qt 技術進行開發。通過使用信號/槽機制，當用戶發出請求時，相應組件發出信號。與該信號建立的連接槽，則可以接收該信號并做出回應，完成對用戶請求的反饋。

3 結語

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