劉華敏

（安徽文達(dá)信息工程學(xué)院計(jì)算機(jī)工程學(xué)院 安徽 合肥 231201）

數(shù)據(jù)結(jié)構(gòu)中的動(dòng)感形態(tài)研究與應(yīng)用實(shí)踐

劉華敏

（安徽文達(dá)信息工程學(xué)院計(jì)算機(jī)工程學(xué)院 安徽 合肥 231201）

《數(shù)據(jù)結(jié)構(gòu)》是計(jì)算機(jī)專業(yè)的一門重要的專業(yè)核心課程，在教學(xué)的過程中引入實(shí)例、動(dòng)畫和圖形等多媒體方式，讓學(xué)生對(duì)教學(xué)內(nèi)容有較直觀的理解。在理論與實(shí)踐結(jié)合的教學(xué)環(huán)節(jié)，引用圖論中廣度優(yōu)先搜索的思想，求解公交查詢系統(tǒng)中獲取“最優(yōu)”換乘路線問題，從理論上升到實(shí)踐，提高學(xué)生解決實(shí)際問題的能力。

多媒體；廣度優(yōu)先搜索；最短路徑

1.數(shù)據(jù)結(jié)構(gòu)中的動(dòng)感形態(tài)研究

1.1 多媒體方式的應(yīng)用

數(shù)據(jù)結(jié)構(gòu)的內(nèi)容比較抽象，學(xué)生在學(xué)習(xí)時(shí)愿意花費(fèi)時(shí)間和精力去學(xué)。但大部分學(xué)生往往感到在學(xué)的過程中力不從心。上課時(shí)老師講解的知識(shí)點(diǎn)能理解，下課后自己無法能靈活運(yùn)用所學(xué)的知識(shí)完成老師布置的實(shí)驗(yàn)作業(yè)和解決與實(shí)際相關(guān)的問題。為了解決在數(shù)據(jù)結(jié)構(gòu)的教學(xué)中普遍存在的這個(gè)問題，要求老師在教學(xué)過程中為學(xué)生建立一個(gè)動(dòng)靜交互的教學(xué)環(huán)境，開闊學(xué)生的視野，豐富學(xué)生的想象力，調(diào)動(dòng)學(xué)生的學(xué)習(xí)興趣，從而大大提高課堂教學(xué)效率[1]。

在教學(xué)中，老師的課件要真正的引入多媒體技術(shù)即融入圖像、動(dòng)畫、、文本等內(nèi)容，使其成為一個(gè)具有直觀性和交互性的課件。著名教育心理學(xué)家梅耶(Richard E.Mayer)的研究和實(shí)驗(yàn)表明，多媒體有下面2個(gè)優(yōu)點(diǎn)：

(1)多媒體性：多表征方式優(yōu)于單表征方式。

(2)鄰近效應(yīng)：言語信息與視覺信息結(jié)合呈現(xiàn)優(yōu)于分離呈現(xiàn)。多個(gè)元素完美的結(jié)合真實(shí)的演示了算法執(zhí)行的過程，可產(chǎn)生1+1〉2的協(xié)同效應(yīng)，抽象算法用形象的、動(dòng)態(tài)的直觀圖表示，讓人容易理解和接受[2]。如講到順序隊(duì)列入隊(duì)和出隊(duì)時(shí)，演示這樣的動(dòng)畫過程如圖1所示。

圖1 順序隊(duì)列入隊(duì)、出隊(duì)操作

動(dòng)畫具有動(dòng)靜結(jié)合、圖文并茂的特點(diǎn)，動(dòng)畫的演示逼真的展現(xiàn)了隊(duì)列入隊(duì)和出隊(duì)的過程，從平面走向三維，從抽象走向直觀，較好的抓住學(xué)生的眼球，集中注意力觀察這一過程，更好的理解隊(duì)列入隊(duì)和出隊(duì)的算法思想。

1.2 色彩元素的滲入

現(xiàn)在的教學(xué)離不開計(jì)算機(jī)輔助教學(xué)手段的支持，以存儲(chǔ)容量大、教師授課進(jìn)度快等特點(diǎn)著稱，這就對(duì)教師的課件質(zhì)量提出了新的要求。色彩在各個(gè)領(lǐng)域扮演的角色和表現(xiàn)形式、手法、目的有所不同，但色彩對(duì)物的表現(xiàn)所追求的和諧之美卻是一致的。因此，配色部分對(duì)于制作數(shù)據(jù)結(jié)構(gòu)課件的人而言無疑是新的挑戰(zhàn)。

針對(duì)數(shù)據(jù)結(jié)構(gòu)內(nèi)容抽象、信息容量大、知識(shí)點(diǎn)復(fù)雜等方面，在課件的制作過程中根據(jù)不同的內(nèi)容選用不同的色彩。

數(shù)據(jù)結(jié)構(gòu)內(nèi)容簡單、易懂的部分，可以選用振奮人心、精神煥發(fā)的色彩配色。例如講到隊(duì)列的入隊(duì)和出隊(duì)的基本操作時(shí)，以選擇紅色或橙色系列作為文字的底色，在暖色系的視覺中輕易獲取知識(shí)點(diǎn)，激發(fā)學(xué)生學(xué)習(xí)的興趣。講到樹、森林遍歷的相關(guān)內(nèi)容時(shí)，可以插入一顆枝繁葉茂的大樹和一片綠樹成蔭的森林，配綠色底紋的文字說明樹的遍歷和森林的遍歷，轉(zhuǎn)換等問題，首先讓學(xué)生在視覺的圖畫中放松心情，產(chǎn)生愉悅的心理；然后在寧靜、能慰藉心靈的色彩中汲取難懂深?yuàn)W的算法，在祥和的狀態(tài)中思考問題，發(fā)揮人的思維，積極開動(dòng)腦筋，主動(dòng)學(xué)習(xí)。

2.圖在公交最優(yōu)路線查詢系統(tǒng)中的應(yīng)用

最近幾年，城市公交系統(tǒng)發(fā)展速度驚人，市民的出行更加便捷。然而，隨著路線的增加，市民在出行時(shí)會(huì)綜合考慮各種因素選擇出行路線。如何在公交問路查詢系統(tǒng)中，根據(jù)出行者的實(shí)際需要獲取“最優(yōu)”換乘路線？要解決這樣的一個(gè)問題，就需要用到《數(shù)據(jù)結(jié)構(gòu)》中的有向圖的相關(guān)知識(shí)。

首先對(duì)給定公交線路構(gòu)成有向路網(wǎng)，然后將該問題的求解歸結(jié)到求單源最短路徑。如果將公交查詢系統(tǒng)中的各種“最優(yōu)”等價(jià)為圖中的“最短”，這個(gè)問題就迎刃而解了。

2.1 圖的表示和術(shù)語

圖由一個(gè)頂點(diǎn)(vertex)的有窮非空集V(G)和一個(gè)弧(arc)的集合E (G)組成，通常記作G=(V,E)。有序?qū)Α磛,w〉表示從v到w的一條弧(arc)，若弧有方向性，通常用一帶方向箭頭的線段表示，即v(沒有箭頭的出發(fā)端)為弧尾，w(帶箭頭的結(jié)束端)為弧頭，此時(shí)的圖稱為有向圖。無序?qū)?v,w)表示從v到w的一條弧，同時(shí)存在w到v的一條弧，此時(shí)的圖稱為無向圖。

在實(shí)際應(yīng)用中，圖的弧或邊往往與具有一定意義的數(shù)相關(guān)，稱這些數(shù)為“權(quán)”。如圖2所示：

圖2 帶權(quán)有向圖G

若有向圖G中n+1個(gè)頂點(diǎn)直接都有弧存在（即〈v0,v1〉,〈v1,v2〉,....,〈vn-1,vn〉是圖 G中的弧)，則這個(gè)頂點(diǎn)的序列{v0,v1,...vn}為從頂點(diǎn) v0到頂點(diǎn)vn的一條有向路徑，路徑中弧的數(shù)目定義為路徑長度。若序列中的頂點(diǎn)都不相同，則為簡單路徑。

2.2 圖的存儲(chǔ)結(jié)構(gòu)

(1)鄰接矩陣。

鄰接矩陣是用于描述圖中頂點(diǎn)之間關(guān)系（及弧或邊的權(quán)）的矩陣，假設(shè)圖中頂點(diǎn)數(shù)為n,則鄰接矩陣A=(ai,j)n*n定義為：

在網(wǎng)的鄰接矩陣的表示中，若Vi和Vj有弧相鄰接時(shí)，ai,j的值應(yīng)為該弧上的權(quán)值，否則為∞。

(2)鄰接表。

鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)表示方法。在有向圖的鄰接表中，從同一頂點(diǎn)出發(fā)的弧鏈接在同一鏈表中，鄰接表中的結(jié)點(diǎn)的個(gè)數(shù)恰為圖中弧的數(shù)目。

圖3 圖G的領(lǐng)接表

2.3 圖的遍歷

圖的遍歷有2種搜素路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。

(1)深度優(yōu)先搜索：假設(shè)圖G中所有的頂點(diǎn)原始狀態(tài)都是沒有訪問的，則選擇某個(gè)頂點(diǎn)作為起點(diǎn)，首先訪問該起點(diǎn)，然后按照深度優(yōu)先遍歷的思想，依次訪問與它相連的各個(gè)未被訪問的鄰接點(diǎn)，直至圖中所有和起點(diǎn)有路徑相連的頂點(diǎn)都被訪問過。如果此時(shí)圖G中還存在其他頂點(diǎn)沒被訪問，則另選一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問結(jié)束。

(2)廣度優(yōu)先搜索：假設(shè)圖G中所有的頂點(diǎn)原始狀態(tài)都是沒有訪問的，則選擇某個(gè)頂點(diǎn)作為起點(diǎn)，首先訪問該起點(diǎn)，由近至遠(yuǎn)，依次訪問和起點(diǎn)有路徑相通的未被訪問的頂點(diǎn)。如果此時(shí)圖中還存在其他頂點(diǎn)沒被訪問，則另選一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問結(jié)束。

3.最短路徑的求解

如果在計(jì)算機(jī)上建立一個(gè)公交咨詢系統(tǒng)，可采用圖或網(wǎng)的結(jié)構(gòu)表示實(shí)際的交通網(wǎng)絡(luò)。在公交咨詢系統(tǒng)中，出發(fā)點(diǎn)A與終點(diǎn)B之間存在的路徑可能有三種情況：①?zèng)]有路徑；②存在唯一的一條路徑；③存在多條路徑。如何求得出發(fā)點(diǎn)A與終點(diǎn)B之間的最短路徑，此時(shí)應(yīng)分析公交線路構(gòu)成的有向路網(wǎng)，根據(jù)“較快捷”、“少步行”及“少換乘”等賦不同的權(quán)值，利用迪杰斯特拉（Dijkstra)算法求解從源點(diǎn)A到終點(diǎn)的最短路徑。

3.1 迪杰斯特拉（Dijkstra)算法

迪杰斯特拉（Dijkstra)提出了一個(gè)按路徑權(quán)值長度遞增的次序產(chǎn)生最短路徑的算法，具體描述如下：

(1)假設(shè)用帶權(quán)的鄰接矩陣arcs[n][n]來表示帶權(quán)有向圖，arcs[i][j]表示弧〈vi,vj〉上的權(quán)值，若〈vi,vj〉不存在，則置arcs[i][j]為∞。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集[3]。那么從v出發(fā)到圖上其余各定點(diǎn)vi可能到達(dá)D[i]=arcs[Locate Vex(G,v)[i] vi∈V。

(2)選擇vj，使得D[j]=Min{D[i]|vi∈V-S}，vj就是當(dāng)前求得的一條從v出發(fā)的最短路徑的終點(diǎn)。令 S=S∪{j}。

(3)修改從v出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短路徑長度。如果D[j]+arcs[j]k]〈D[k]，則修改D[k]為D[k]=D[j]+arcs[j]k]。

(4)重復(fù)(2)(3)共n-1次，由此求得從v到圖上其余各頂點(diǎn)的最短路徑是依路徑長度遞增的序列。

3.2 有向圖G求解的具體過程

帶權(quán)的有向圖G(圖2)中從A到其余各頂點(diǎn)之間的最短路徑。

(1)G的帶權(quán)鄰接矩陣表示如下：

圖4 G的帶權(quán)鄰接矩陣

(2)若對(duì)G運(yùn)用迪杰斯特拉（Dijkstra)算法，則所得從A到其余各頂點(diǎn)的最短路徑，以及運(yùn)算過程中變化的D向量情況，如表1所示：

表1 D向量變化情況

從表1，我們能直觀的了解到圖G中頂點(diǎn)A到其他所有頂點(diǎn)的最短距離A→B=∞，A→C=10，A→D=50等。根據(jù)運(yùn)算結(jié)果繪制的SPF樹如圖5所示：

圖5 有向圖G的SPF樹

4.結(jié)束語

算法的發(fā)展與應(yīng)用是密不可分的，但在學(xué)習(xí)《數(shù)據(jù)結(jié)構(gòu)》的過程中，運(yùn)用動(dòng)靜結(jié)合的教學(xué)方法講授教學(xué)內(nèi)容，將算法與實(shí)際問題相結(jié)合，能靈活的調(diào)動(dòng)學(xué)生學(xué)習(xí)的主動(dòng)性，激發(fā)學(xué)生探求新知識(shí)的興趣，拓展學(xué)生創(chuàng)新能力的培養(yǎng)。以Dijkstra算法為基礎(chǔ)，求解單源最短路徑的實(shí)際問題，將學(xué)生的理論知識(shí)運(yùn)用到實(shí)踐中。隨著公交線路查詢系統(tǒng)的功能不斷的完善，實(shí)時(shí)最優(yōu)路徑的求解是亟需解決的，Dijkstra算法也會(huì)不斷的被改進(jìn)。

［1］張偉.數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題的測試程序輔助構(gòu)建研究[D].廣東：廣東工業(yè)大學(xué)，2012.

［2］張建偉，孫燕青.多媒體與網(wǎng)絡(luò)學(xué)習(xí)的心理機(jī)制[J].外語電化教學(xué)，2004，(4).

［3］嚴(yán)蔚敏等編.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2004.

T-01

A

2095-7327（2017）-08-0161-02

安徽省省級(jí)質(zhì)量工程教學(xué)研究重點(diǎn)項(xiàng)目“基于項(xiàng)目和實(shí)踐技能的應(yīng)用型本科《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)改革研究”研究成果，項(xiàng)目編號(hào)為2014jyxm427。

劉華敏（1978—），女，安徽安慶人，安徽文達(dá)信息工程學(xué)院講師，研究方向?yàn)閿?shù)據(jù)挖掘、程序設(shè)計(jì)和網(wǎng)頁設(shè)計(jì)。