堆棧和二叉樹數(shù)據(jù)結(jié)構(gòu)在DNA計算機中的設(shè)計與實現(xiàn).pdf

1、自從1994年Adleman用DNA鏈解決一個簡單有向哈密頓圖問題以來，DNA計算已經(jīng)形成國際科學(xué)前沿領(lǐng)域內(nèi)研究的一個新的熱點，引起許多不同學(xué)科學(xué)者們的興趣。DNA計算機的研制需要諸如生物工程、計算機科學(xué)等許多學(xué)科的共同協(xié)作攻關(guān)。已有研究表明DNA計算機具備完整的圖靈機功能，這為DNA計算機能否成為目前意義下真正的計算機提供理論支持。DNA計算機要走向?qū)嶋H應(yīng)用，必須像電子計算機一樣，需要解決DNA計算機中信息的組織問題，這就需要合理的數(shù)

2、據(jù)結(jié)構(gòu)來有效地組織DNA計算機需要處理的信息。因此，數(shù)據(jù)結(jié)構(gòu)的設(shè)計對DNA計算機的具體實現(xiàn)有重要研究價值。 首先，本文在參考已有隊列數(shù)據(jù)結(jié)構(gòu)設(shè)計方法的基礎(chǔ)上，提出了DNA計算機中堆棧數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法。該方法根據(jù)堆棧的特點，利用兩種不同的限制性內(nèi)切酶完成入棧和出棧操作。并給出DNA計算機中堆棧存儲結(jié)構(gòu)的形式描述；詳細闡述了DNA計算機中堆棧初始化、入棧、出棧、判斷空堆棧等操作的生物實現(xiàn)方法；給出一個具體的DNA編碼以及算法實例，

3、實例仿真了DNA計算機中該算法的運行機制，實例結(jié)果表明此堆棧數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法在DNA計算機上切實可行。 然后，提出了DNA計算機中基于順序存儲方式的二叉樹數(shù)據(jù)結(jié)構(gòu)的設(shè)計方法。該方法利用DNA分子和限制性內(nèi)切酶的生物特性，完成二叉樹的順序存儲結(jié)構(gòu)和基本操作。并給出一個二叉樹的DNA編碼以及仿真實例，實例結(jié)果表明該設(shè)計方法在DNA計算機上的可行性。 最后，給出DNA計算機中二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)的形式描述。在連接酶的作用下，各