孫召偉,趙建利,朱東生

數(shù)據(jù)結(jié)構(gòu)中遞歸轉(zhuǎn)非遞歸算法分析及模型設(shè)計研究

孫召偉1,趙建利2,朱東生3

(1.河北省大中專院校學生信息咨詢與就業(yè)指導中心,河北石家莊 050061;2.河北工業(yè)大學電氣工程學院,天津 300130;3.河北師范大學數(shù)學與信息科學學院,河北石家莊 050016)

為構(gòu)建數(shù)據(jù)結(jié)構(gòu)中遞歸算法的統(tǒng)一知識體系,分析了常見數(shù)據(jù)結(jié)構(gòu)的遞歸本質(zhì)及遞歸算法的組成要素,提出了遞歸算法轉(zhuǎn)非遞歸算法的一般原則,根據(jù)遞歸算法的分類設(shè)計轉(zhuǎn)換模型,通過實例分析其可行性。

遞歸算法;數(shù)據(jù)結(jié)構(gòu);非遞歸;模型設(shè)計

遞歸以其思路明確、代碼簡潔在數(shù)據(jù)結(jié)構(gòu)算法中,特別是在解決樹、圖等問題過程中得到了廣泛應用[1-6]。但其求解過程中系統(tǒng)開辟的棧,以存儲每一層的返回點、局部量等信息,開銷大,算法運行效率較低,且遞歸層次深,易造成棧溢出等問題。為了避免這種情況的發(fā)生,通常采用算法實現(xiàn)遞歸到非遞歸的轉(zhuǎn)換。文獻[7]—文獻[9]給出了針對某些特定問題的遞歸到非遞歸的轉(zhuǎn)換算法。

集合、線性表、廣義表、樹、圖這5大數(shù)據(jù)結(jié)構(gòu)都可以看作是由某一個元素和所有后繼構(gòu)成的相同的數(shù)據(jù)結(jié)構(gòu)所組成,遞歸是眾多數(shù)據(jù)結(jié)構(gòu)物理構(gòu)造和邏輯意義上的統(tǒng)一體。這使得與數(shù)據(jù)結(jié)構(gòu)相關(guān)的眾多遞歸算法在表現(xiàn)形式上有許多共性,將它們轉(zhuǎn)換為非遞歸算法時有一些通用模型。

1 遞歸算法的一般模型

1.1 常見數(shù)據(jù)結(jié)構(gòu)的遞歸本質(zhì)

所有的線性關(guān)系可以理解成由第1個元素和(除去第1個元素)剩余的元素組成,而剩余的元素又是一個相對較小的線性關(guān)系,如圖1所示。

圖1 線性表的遞歸結(jié)構(gòu)Fig.1 Recursion structure of linear list

廣義表可以理解成由第1個元素和(除去第1個元素)剩余元素的廣義表組成,如圖2所示。

圖2 廣義表的遞歸結(jié)構(gòu)Fig.2 Recursion structure of generalized list

樹是由根和除根外的若干棵子樹組成,如圖3所示。圖可以理解成由某一頂點(起始點 —任意頂點都可作為起始點)及所有后繼節(jié)點為起始點形成的子圖組成,如圖4所示。

數(shù)據(jù)結(jié)構(gòu)都是由某一個元素和所有后繼構(gòu)成的相同的數(shù)據(jù)結(jié)構(gòu)組成,數(shù)據(jù)結(jié)構(gòu)的定義基本上是遞歸的。

1.2 遞歸算法一般模型

遞歸算法由2部分組成:1)最小問題,稱為基本項;2)原問題與子問題的關(guān)系。它包含2部分內(nèi)容,一是可以繼續(xù)分解的子問題,稱為遞歸項;二是不能繼續(xù)劃分的子問題,稱為有解子問題。一般的表現(xiàn)形式如下。

最小問題決定了遞歸的出口。不能繼續(xù)劃分的子問題是按照問題的要求被處理,如輸出、比較大小等。研究遞歸算法,主要是研究有解子問題,線性表處理的是第1個元素,樹處理的是樹根,廣義表處理的是第1個節(jié)點,圖處理的是起始頂點。根據(jù)遞歸項中有解子問題的處理順序,將遞歸分為前序遞歸、中序遞歸和后序遞歸。

2 遞歸轉(zhuǎn)非遞歸

2.1 一般原則

本文提出了一個自然問答系統(tǒng)，對于事實性問題，它能夠生成完整自然語言句子形式的答案。首先獲得大量的問題答案對，并將其與知識庫進行對齊，為模型訓練提供數(shù)據(jù)基礎(chǔ)。然后提出了基于全局知識表示的兩階段答案生成模型。對于一個問題，第一階段基于全局知識表示匹配想對應的事實三元組；第二階段結(jié)合匹配事實和問題利用序列學習模型分別從前向和后向兩個方法生成答案句子。在公開數(shù)據(jù)集的實驗結(jié)果表明了該方法的有效性。未來計劃從下面兩個方向擴展現(xiàn)有的工作：(1)回答復雜的問題，它不僅需要檢索多個事實，各個事實之間可能具有更復雜的結(jié)構(gòu)；(2)設(shè)計更加靈活的模型納入更多的外部資源(文本等)。

在將遞歸算法轉(zhuǎn)換為非遞歸算法時,對遞歸算法中3項內(nèi)容的處理對應3個基本原則。

原則1 有解子問題的處理不變。原來是輸出內(nèi)容現(xiàn)在仍是輸出,原來是求和現(xiàn)在仍是求和。對當前節(jié)點的處理方式不會發(fā)生變化。

原則2 遇到遞歸項,一要入、出棧,二要進行循環(huán)。一般情況下,有幾個遞歸語句就要有幾重循環(huán),而有時循環(huán)的重數(shù)可以簡化。碰到遞歸語句要入棧,為的是將來某個時候訪問當前節(jié)點或當前節(jié)點的后繼;遞歸調(diào)用結(jié)束時要出棧,為的是訪問當前節(jié)點或是將其后繼節(jié)點入棧。對于尾遞歸,可以不進行入棧,而對于多條遞歸語句的后序遞歸,一個節(jié)點可能要多次入棧和出棧,需要作標記。

原則3 遞歸出口成為循環(huán)結(jié)束條件。循環(huán)結(jié)束條件除了遞歸出口之外還有“棧不空”這個條件。

2.2 前序遞歸轉(zhuǎn)非遞歸

前序遞歸指遞歸項中先處理有解子問題,再處理可繼續(xù)劃分的子問題。一條遞歸語句的前序遞歸主要是針對線性表的,轉(zhuǎn)換過程簡單。如果為尾遞歸(即遞歸語句出現(xiàn)在代碼最后),則只需直接進行縮小問題規(guī)模的操作,不用入棧。

2.2.1 2條遞歸語句

2條遞歸語句的遞歸算法主要針對廣義表和二叉樹,轉(zhuǎn)換模型見模型1。此遞歸算法的遞歸項中有2個遞歸調(diào)用,按照一般原則,算法結(jié)構(gòu)應為雙重循環(huán)。內(nèi)層循環(huán)由第6行的遞歸語句轉(zhuǎn)換而來,外層循環(huán)由第7行的遞歸語句轉(zhuǎn)換而來。模型1見圖5。

圖5 模型1Fig.5 Conversion model 1

2)有解子問題的處理不變。

3)第6行的遞歸語句。實參入棧,問題規(guī)模變小;從頭執(zhí)行(就是循環(huán))。入棧內(nèi)容是當前節(jié)點,因為當前節(jié)點的右子樹還沒被訪問過。

4)遇到遞歸結(jié)束,出棧,并對棧中元素進行適當?shù)奶幚怼?/p>

5)第7行的遞歸語句。由于是尾遞歸,所以不用入棧,只是問題規(guī)模的縮小。外層循環(huán)結(jié)束的條件,除了是基本項的非之外,還增加了對棧非空的判定。

2.2.2 多條遞歸語句轉(zhuǎn)換一般形式

多條遞歸語句的遞歸算法主要針對廣義表、樹和圖。轉(zhuǎn)換時可以在訪問該節(jié)點的時候,用一個循環(huán)就將這個節(jié)點的所有后繼都入棧,從而將循環(huán)的重數(shù)簡化為兩重。具體過程的模型見圖6,一般模型見圖7。

圖6 模型2Fig.6 Coversion model 2

圖7 模型3Fig.7 Conversion model 3

2.3 多條語句的后序遞歸轉(zhuǎn)非遞歸

在多條遞歸語句的后序遞歸中,一個節(jié)點可能會多次入棧和出棧,為了確定是否到了訪問該節(jié)點的時機,增加1個標志來表示該節(jié)點當前的訪問狀態(tài),而且標志信息同該節(jié)點一起入棧、出棧。

1)增加1個結(jié)構(gòu)體,作為存儲入棧信息。2)一般模型(見圖7)。一般的,如果當前節(jié)點沒有右子樹,在第1次入棧時就可將其標志置為0,這樣可以減少一些不必要的入棧和出棧操作。即灰色代碼部分可以改寫為

帶標志的節(jié)點入棧。

3 結(jié) 語

在詳細分析遞歸算法組成要素的基礎(chǔ)上,根據(jù)遞歸算法的分類,系統(tǒng)地提出了遞歸轉(zhuǎn)非遞歸的一般原則和實用模型,完善了數(shù)據(jù)結(jié)構(gòu)中遞歸算法的知識體系,為研究眾多與數(shù)據(jù)結(jié)構(gòu)相關(guān)遞歸算法的轉(zhuǎn)換過程提供了有效的解決方案,可推廣性強。

[1] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實用教程[M].北京:清華大學出版社,2004.

[2] 嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:清華大學出版社,1997.

[3] BRASSARD G,BRA TLEY P.Fundamentals of Algorithmics[M].London:Prentice-Hall International,1996.

[4] 周 康,同小軍,許 進.基于閉環(huán)DNA模型的八皇后問題算法[J].計算機工程與應用(Computer Engineering and Applications),2007,43(6):4-6.

[5] 田烽楠,王 于.求解0-1背包問題算法綜述[J].軟件導刊(Software Guide),2009,8(1):59-61.

[6] 張 斌,金晨輝.基于回溯法的逆推攻擊[J].電子與信息學報(Journal of Electronics and Info rmation Technology),2008,30(10):2 464-2 467.

[7] 游 珍,薛錦云.Hanoi塔非遞歸算法的形式化推導和正確性驗證[J].計算機研究與發(fā)展(Journal of Computer Research and Development),2008(S1):143-147.

[8] 朱振元,朱 承.遞歸算法的非遞歸化實現(xiàn)[J].小型微型計算機系統(tǒng)(Journal of Chinese Computer Systems),2003(3):567-570.

[9] 孫 涌.遞歸算法的非遞歸實現(xiàn)[J].計算機研究與發(fā)展(Journal of Computer Research and Development),1995(11):1-7.

Analysis and model design of conversion algorithm from recursion to non-recursion in data structure

SUN Zhao-wei1,ZHAO Jian-li2,ZHU Dong-sheng3

(1.Hebei College Students Information and Emp loyment Center,Shijiazhuang Hebei 050061,China;2.School of Electrical Engineering and Automation,Hebei University of Technology,Tianjin 300130,China;3.College of Mathematics and Information Science,Hebei No rmal University,Shijiazhuang Hebei 050016,China)

In order to construct the scientific systematization of know ledge of recursion in data structure,this paper analyzed the recursion essence of common data structure and the componentsof recursive algo rithm,then p roposed the general p rincip les of the conversion from recursion to non-recursion.Based on the classifications of the recursion algo rithm,it also designed the conversion model w hose p ractical is verified.

recursion algo rithm;data structure;non-recursion;model design

TP183

A

1008-1542(2011)01-0043-04

2010-07-15;責任編輯:張 軍

孫召偉(1978-),男,河北趙縣人,學士,主要從事數(shù)據(jù)挖掘與算法分析方面的研究。