數(shù)據(jù)結(jié)構(gòu)在有機化學(xué)中的應(yīng)用

1、數(shù)據(jù)結(jié)構(gòu)在有機化學(xué)中的應(yīng)用The Application of Data Structure to Organic Chemistry南京市金陵中學(xué) 高二（13）班 祝云篪ABSTRACT: The rapid development of computer science and technology has influenced many disciplines, including organic chemistry. The objective of this study is to explore the uses and efficiency of data structure,

2、an important component of computer science, which is widely used in organic chemistry. This study focuses on the application to the storage of chemical structures of organic compounds and relevant calculation. The findings of the study include the following: 1. Strings apply well to the input of str

3、ucture formula; 2. Linear structures are useful for chemical calculating; 3. Tree and graph structures make it convenient to store chemical structures.一.研究背景 2013年10月9日，2013年諾貝爾化學(xué)獎在瑞典揭曉，猶太裔美國理論化學(xué)家馬丁·卡普拉斯(Martin Karplus)、美國斯坦福大學(xué)生物物理學(xué)家邁克爾·萊維特(Michael Levitt)和南加州大學(xué)化學(xué)家亞利耶·瓦謝爾(Arieh Warshe

4、l)因給復(fù)雜化學(xué)體系設(shè)計了多尺度模型而分享獎項。 諾貝爾化學(xué)獎評選委員會說，卡普拉斯、萊維特和瓦謝爾研究的開創(chuàng)性在于，他們讓經(jīng)典物理學(xué)與迥然不同的量子物理學(xué)在化學(xué)研究中“并肩作戰(zhàn)”。以前，化學(xué)家必須二選其一。依靠用塑料棒和桿創(chuàng)建模型的經(jīng)典物理學(xué)方法的優(yōu)勢在于計算簡單且能為大分子建模，但其無法模擬化學(xué)反應(yīng)。而如果化學(xué)家選擇使用量子物理學(xué)計算化學(xué)反應(yīng)過程，但巨大的計算量使得其只能應(yīng)付小分子。為此，在20世紀70年代，這三位科學(xué)家設(shè)計出這種多尺度模型，讓傳統(tǒng)的化學(xué)實驗走上了信息化的快車道。 多尺度復(fù)雜化學(xué)系統(tǒng)模型的出現(xiàn)無疑翻開了化學(xué)史的“新篇章”。化學(xué)反應(yīng)發(fā)生的速度堪比光速。剎那間，電子就從一個原子

5、核跳到另一個原子核，以前，對化學(xué)反應(yīng)的每個步驟進行追蹤幾乎是不可能完成的任務(wù)。而在由這三位科學(xué)家研發(fā)出的多尺度模型的輔助下，化學(xué)家們讓計算機做“做幫手”來揭示化學(xué)過程。例如，在模擬藥物如何同身體內(nèi)的目標蛋白耦合時，計算機會對目標蛋白中與藥物相互作用的原子執(zhí)行量子理論計算；而使用要求不那么高的經(jīng)典物理學(xué)來模擬其余的大蛋白，從而精確掌握藥物發(fā)生作用的全過程。諾貝爾化學(xué)獎評選委員會在當天發(fā)表的聲明中說，對化學(xué)家來說，計算機是同試管一樣重要的工具，計算機對真實生命的模擬已為化學(xué)領(lǐng)域大部分研究成果的取得立下了“汗馬功勞”。通過模擬，化學(xué)家能更快獲得比傳統(tǒng)實驗更精準的預(yù)測結(jié)果。以上為2013年諾貝爾化學(xué)獎

6、的頒獎情況。今天，以計算機及其網(wǎng)絡(luò)深入到社會的各個層面為標志的數(shù)字化新世紀已經(jīng)到來，也將使傳統(tǒng)化學(xué)發(fā)生深刻的變化。化學(xué)已由只實驗不計算，演變?yōu)橄葘嶒炘儆嬎悖脖貙⒅鸩窖葑優(yōu)橄扔嬎阍賹嶒?；計算機化學(xué)和計算化學(xué)的結(jié)合已開始孕育一個新的更帶數(shù)字化色彩的學(xué)科方向-Model Chemistry(模型化學(xué)，Pople語)；基于web技術(shù)的化學(xué)應(yīng)用軟件已經(jīng)出現(xiàn)。這些都表明數(shù)字化化學(xué)將與數(shù)字化社會一起到來。 計算機化學(xué)(Computer chemistry)是應(yīng)用計算機研究化學(xué)反應(yīng)和物質(zhì)變化的科學(xué)。以計算機為技術(shù)手段，建立化學(xué)化工信息資源化和智能化處理的理論和方法，認識物質(zhì)、改造物質(zhì)、創(chuàng)造新物質(zhì)和認識反應(yīng)、

7、控制反應(yīng)過程和創(chuàng)造新反應(yīng)、新過程是計算機化學(xué)研究的主體。它的興起與發(fā)展是與計算機技術(shù)的發(fā)展和計算機的普及緊密聯(lián)系的。目前計算機化學(xué)覆蓋的領(lǐng)域主要有： 1化學(xué)數(shù)據(jù)挖掘(Data mining)； 2化學(xué)結(jié)構(gòu)與化學(xué)反應(yīng)的計算機處理技術(shù)； 3計算機輔助分子設(shè)計； 4計算機輔助合成路線設(shè)計； 5計算機輔助化學(xué)過程綜合與開發(fā)； 6化學(xué)中的人工智能方法等。 本篇論文即是對領(lǐng)域2中的有機物化學(xué)結(jié)構(gòu)計算機處理技術(shù)進行研究。有機化學(xué)又稱為碳化合物的化學(xué)，是研究有機化合物的組成、結(jié)構(gòu)、性質(zhì)、制備方法與應(yīng)用的科學(xué)，是化學(xué)中極重要的一個分支【1】。和無機物相比，有機物數(shù)目眾多，可達幾千萬種。而無機物目卻只發(fā)現(xiàn)數(shù)十萬種

8、，因為有機化合物的碳原子的結(jié)合能力非常強，可以互相結(jié)合成碳鏈或碳環(huán)。碳原子數(shù)量可以是1、2個，也可以是幾千、幾萬個，許多有機高分子化合物（聚合物）甚至可以有幾十萬個碳原子。此外，有機化合物中同分異構(gòu)現(xiàn)象非常普遍，這也是有機化合物數(shù)目繁多的原因之一。 而當今世界，計算機技術(shù)快速發(fā)展，存儲功能強大、運算速度極快的計算機便可以方便的處理種類復(fù)雜、結(jié)構(gòu)繁多的有機物化學(xué)結(jié)構(gòu)，以便未來的研究工作。二.研究意義 1.高二即將系統(tǒng)學(xué)習(xí)有機化學(xué)，此研究有利于當前的預(yù)習(xí)工作與將來的化學(xué)學(xué)習(xí)。 2.高一下學(xué)期信息競賽輔導(dǎo)主講數(shù)據(jù)結(jié)構(gòu)，此研究過程將是一個極好的實戰(zhàn)演練機會； 3.研究過程中，通過查閱資料，可獲取大量與

9、計算機、化學(xué)乃至數(shù)學(xué)、物理等其他學(xué)科有關(guān)的知識，有利于將來的職業(yè)選擇； 4.研究過程中編寫的程序可供同學(xué)們使用，一方面可有助于他們的化學(xué)學(xué)習(xí)，另一方面可引起他們對計算機科學(xué)的關(guān)注，培養(yǎng)他們的計算機思維。 三.研究方法研究方法主要有查閱資料和實戰(zhàn)編程。資料分計算機和化學(xué)兩部分。計算機方面看數(shù)據(jù)結(jié)構(gòu)和算法，主要有算法導(dǎo)論圖論；有機化學(xué)則是邢其毅基礎(chǔ)有機化學(xué)、胡弘紋有機化學(xué)。實戰(zhàn)編程，主要運用作者最熟悉的PASCAL語言。四.研究過程1.線性結(jié)構(gòu) 線性表【2】是一個線性結(jié)構(gòu)，它是一個含有n0個結(jié)點的有限序列，對于其中的結(jié)點，有且僅有一個開始結(jié)點沒有前驅(qū)但有一個后繼結(jié)點，有且僅有一個終端結(jié)點沒有后繼但

10、有一個前驅(qū)結(jié)點，其它的結(jié)點都有且僅有一個前驅(qū)和一個后繼結(jié)點。一般地，一個線性表可以表示成一個線性序列：k1,k2,kn，其中k1是開始結(jié)點，kn是終端結(jié)點。 在實際應(yīng)用中，線性表都是以棧、隊列、字符串、數(shù)組等特殊線性表的形式來使用的。 下面來看其具體運用（1）字符串：讀入如圖4-1，這是一個2-羥基丙醛的結(jié)構(gòu)簡式，若將其寫在一個輸入行之內(nèi)，根據(jù)規(guī)范，應(yīng)寫成CH3C(OH)HCHO 。由此，可以發(fā)現(xiàn)改寫結(jié)構(gòu)簡式中，單鍵被省略，支鏈用括號表示，化學(xué)式中只留下數(shù)字、括號和字母，因此，可以由線性的字符串輸入。在此總結(jié)三條規(guī)律：圖4-1使用結(jié)構(gòu)簡式，一行輸入用括號代替價鍵表示支鏈 正常大小數(shù)字 （這點是

11、由于計算機本身的限制）圖4-2根據(jù)以上原則，輸入2-羥基丙醛的化學(xué)式應(yīng)為：(2)棧：計算圖4-3 棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入?；驂簵＃前研略胤诺綏ｍ斣氐纳厦?，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。 此項性質(zhì)，有利于對化學(xué)物質(zhì)中的元素進行統(tǒng)計工作。 案例I 不飽和度不飽和度 (英文名稱:Degree of unsaturation)，又稱缺氫指數(shù)或者環(huán)加雙鍵指數(shù)(index

12、 of hydrogen deficiency (IHD) or rings plus double bonds)是有機物分子不飽和程度的量化標志，用希臘字母表示，在有機化學(xué)中用來幫助畫化學(xué)結(jié)構(gòu)，在推斷有機化合物結(jié)構(gòu)時很有用，可以幫助使用者確定要畫的化合物有多少個環(huán)、雙鍵、和叁鍵。 公式：=1+1/2Ni(Vi-2)其中，Vi 代表某元素的化合價，Ni 代表該種元素原子的數(shù)目， 代表總和。這種方法適用于復(fù)雜的化合物。 =C+1(HN)/2其中，C 代表碳原子的數(shù)目，H 代表氫和鹵素原子的總數(shù)，N 表氮原子的數(shù)目，氧和其他二價原子對不飽和度計算沒有貢獻，故不需要考慮氧原子數(shù)。這種方法只適用于含碳

13、、氫、單價鹵素、氮和氧的化合物。這里以第二種方法為例。 算法簡述 設(shè)立兩個棧，元素棧（符號棧）與數(shù)字棧； 將化學(xué)式以字符串形式讀入，具體要求之前已明確； 讀入同時判斷所讀字符為數(shù)字還是元素符號，兩棧使用同一top指針，若為元素，則toptop+1； 將字符分別壓入相應(yīng)棧； 掃描元素棧，統(tǒng)計碳數(shù)、氫數(shù)、氮數(shù)、鹵素數(shù)； 代入公式求解，輸出。源代碼1. var s,n:array1.100of string;2. ch:char;3. w,ans,c,h,x,i,top:integer;4. begin5. top:=0;ans:=0;c:=0;h:=0;6. while not eoln do7.

14、 begin8. read(ch);9. if(ord(ch)>=65)and(ord(ch)<=90)then10. begin inc(top);stop:=stop+ch;end11. else if(ord(ch)>=97)and(ord(ch)<=122)then12. stop:=stop+ch else13. ntop:=ntop+ch;14. end;15. for i:=1 to top do16. begin17. if ni='' then ni:='1'18. if si='C' then begi

15、n val(ni,x,w);c:=c+x;end19. else if si='H' then begin val(ni,x,w);h:=h+x;end20. else if(si='F')or(si='Cl')21. or(si='Br')or(si='I') then begin val(ni,x,w);ans:=ans-x;end22. else if si='N' then begin val(ni,x,w);ans:=ans+x;end;23. end;24. ans:=(c*2+2-h+

16、ans)div 2;25. writeln('?',ans);26. readln(x);27. end. 以下是部分測試結(jié)果。圖4-4圖4-5圖4-62.樹形結(jié)構(gòu)樹狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n(n>=1)個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做"樹"是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點:每個節(jié)點有零個或多個子節(jié)點;沒有父節(jié)點的節(jié)點稱為根節(jié)點;每一個非根節(jié)點有且只有一個父節(jié)點;除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹。樹又分為有序樹和無序樹。圖4-8圖4-7如圖4-7，這是一個乙基的示意圖?？梢园?/p>

17、端基看作樹根，將其建成一棵三叉樹（圖4-8）：由上可知，有機基團可看為三叉有序樹，有機物本身便是三叉無序樹。因此，我們可以利用樹的存儲，來存儲化學(xué)物質(zhì)。 樹的存儲輸入可用廣義表或前序遍歷形式。這里采用后者。例：-CH3轉(zhuǎn)化為：-CH#H#H#其中“#”表示無節(jié)點。 然后就可以建樹存儲了。 案例II 集團次序比較 次序規(guī)則內(nèi)容【3】： 圖4-9 次序規(guī)則的使用（1）原子：原子序數(shù)大的排在前面，同位素質(zhì)量數(shù)大的優(yōu)先。幾種常見原子的優(yōu)先次序為：I>Br>Cl>S>P>O>N>C>H（2）飽和基團：如果第一個原子序數(shù)相同，則比較第二個原子的原子序數(shù)，依次

18、類推。常見的烴基優(yōu)先次序為： (CH3)3C->(CH3)2CH->CH3CH2->CH3-（3）不飽和基團：可看作是與兩個或三個相同的原子相連。不飽和烴基的優(yōu)先次序為:-CCH>-CH=CH2>(CH3)2CH-（4）若與雙鍵碳原子相連的基團互為順反異構(gòu)時，Z型先于E型。 次序規(guī)則主要應(yīng)用于烷烴的系統(tǒng)命名和烯烴中幾何異構(gòu)體的命名。 此案例不包含第四條。算法簡述 字符串讀入兩個化學(xué)式，將其轉(zhuǎn)化為前序遍歷形式； 建三叉樹； 逐層各原子排序，逐一比較； 輸出。 源代碼1. uses math;2. type tree=array1.300of string;3. ma

19、x=array0.300of longint;4. const e:array0.15of string=5. (' ','H','D','T','Li','B','C','N','O','F','Si','P','S','Cl','Br','I');6. var t1,t2:tree;7. max1,max2:max;8. s1,s2,s3

20、,s4:string;9. i,j,k,l,n:longint;10. procedure swap(var a,b:longint);11. var t:longint;12. begin13. t:=a;14. a:=b;15. b:=t;16. end;17.18. procedure change(var st:string);19. var i,j,k,l,n:longint;20. s:string;21. begin22. delete(st,1,1);23. i:=0;/branch24. while i<length(st) do25. begin26. inc(i);

21、27. if sti=')' then28. for j:=i-1 downto 1 do29. if stj='(' then30. begin31. s:=copy(st,j+1,i-j-1);32. if ord(sti+1)>=65 then33. begin k:=1;delete(st,j,i-j+1);end else34. begin k:=ord(sti+1)-48;delete(st,j,i-j+2);end;35. for l:=1 to k do insert(s,st,j);36. end;37. end;38. i:=0;/va

22、lence bond39. while i<length(st) do40. begin41. inc(i);42. case sti of43. '=':begin44. delete(st,i,1);45. st:=st+'#'46. n:=length(st);47. s:=copy(st,i,n-i+1);48. insert(s,st,n+1);49. end;50. '?:begin51. delete(st,i,1);52. st:=st+'#'53. n:=length(st);54. s:=copy(st,i,n-

23、i+1);55. insert(s,st,n+1);56. n:=length(st);57. insert(s,st,n+1);58. end;59. end;60. end;61. i:=0;/element62. while i<length(st) do63. begin inc(i);64. if sti+1<>'#' then begin65. if(ord(sti+1)>=65)and(ord(sti+1)<97)then j:=1 else66. begin67. if ord(sti+1)>=97 then68. begin

24、69. s:=sti+sti+1;70. if ord(sti+2)>=65 then j:=171. else begin j:=ord(sti+2)-48;72. delete(st,i+2,1);end;73. for k:=1 to j-1 do74. insert(s,st,i);75. end else76. begin77. s:=sti;78. j:=ord(sti+1)-48;79. delete(st,i+1,1);80. for k:=1 to j-1 do81. insert(s,st,i);82. end;83. end;84. end;end;85. i:=0

25、;86. while i<length(st) do begin inc(i);87. if(ord(sti+1)<90)and(ord(sti)<95)then88. case sti of89. 'H':insert('#',st,i+1);90. 'D':insert('#',st,i+1);91. 'T':insert('#',st,i+1);92. 'F':insert('#',st,i+1);93. 'I':insert(

26、'#',st,i+1);94. 'O':if(sti-1='C')or(sti-5='C')then95. begin96. insert('#O#',st,i+1);97. i:=i+7;98. end else insert('#',st,i+1);99. 'S':if(sti-1='C')or(sti-5='C')then100. begin101. insert('#S#',st,i+1);102. i:=i+7;103. en

27、d else insert('#',st,i+1);104. 'N':insert('#',st,i+1);105. 'P':insert('#',st,i+1);106. 'B':insert('#',st,i+1);107. end else if(sti<>'#')and(ord(sti)<95)then insert('#',st,i+2);108. end;109. end;110.111. procedure create

28、(i:longint;var t:tree;var st:string);112. begin113. inc(j);114. if stj='#' then ti:=' '115. else116. begin117. if ord(stj+1)<95 then ti:=stj118. else begin ti:=stj+stj+1;delete(st,j+1,1);end;119. create(3*i-1,t,st);120. create(3*i,t,st);121. create(3*i+1,t,st);122. end;123. end;12

29、4.125. procedure compare(i:longint);126. var j,k1,K2,l1,l2:longint;127. begin128. if s3=s4 then begin writeln(s3,'=',s4);exit;end;129. fillchar(max1,sizeof(max1),0);130. fillchar(max2,sizeof(max2),0);131. k1:=0;K2:=0;132. begin133. for j:=(trunc(power(3,i-1)-1)div 2+1)to(trunc(power(3,i)-1)d

30、iv 2)do134. begin135. for l1:=0 to 15 do if el1=t1j then break;136. inc(k1);max1k1:=l1;137. for l2:=0 to 15 do if el2=t2j then break;138. inc(k2);max2k2:=l2;139. end;140. for l1:=1 to k1-1 do141. for l2:=l1+1 to k1 do142. if max1l1<max1l2 then swap(max1l1,max1l2);/sort143. for l1:=1 to k2-1 do144. for l2:=l1+1 to k2 do145. if max2l1<max2l2 then swap(max2l1,max2l2);/sort146. for j:=1 to k1 do147. if max1j>max2j then begin writeln(s3,'&