烷烃所有同分异构体的计算机求解.doc

烷烃所有同分异构体的计算机求解

摘要：
本文提出了烷烃同分异构体在计算机中的两种表示方法，并用来求解输出指定碳原子个数烷烃的所有同分异构体的分子构造问题。
正文：
在种类繁多的有机化合物中，烃是最简单的一种。它的特点是只含有碳和氢两种元素。而烷烃又是烃中构造最简单的。它的分子中碳原子都是饱和4价的，碳原子之间只以单键相互连接，其余的价则完全与氢原子相连。在计算机表示中只需表示出其碳链即可。
在多碳原子的烷烃中由于分子中碳链构造的不同，同一种烷烃会存在多种同分异构体。例如丁烷有两种分子构造：
　　　　　　　　　　　　　　Ｃ
　　　　　　　　　　　　　　｜
Ｃ－Ｃ－Ｃ－Ｃ　　　　　　　Ｃ－Ｃ－Ｃ
当碳原子数较少时，其同分异构体数量也较少，凭直观还易于写出其所有的同分异构体；但当碳原子数增加时，其同分异构体数将迅速增加（见表一）
表一、烷烃构造异构体数目
碳原子数
异构体数
碳原子数
异构体数
1
1
7
9
2
1
8
18
3
1
9
35
4
2
10
75
5
3
11
4347
6
5
12
366319
从表中可看出表明并没有求烷烃同分异构体数的通式，表一的结果是30年代有人用数学上的图论的方法推算出来的。但这种方法并不能给出某种烷烃具体的同分异构体结构式。如果手工求算要寻找大量的碳原子组合方式，最困难的一点是判断求出的同分异构体与已有的是否重复。用计算机来求解关键也一样，下面分别从算法、数据结构和编程实现三方面来讨论。
一、 算法
用计算机解决这个问题实际上模拟了人在解决这个问题时的方法。先写出一个最简单碳链——只有两个碳原子的碳链：
1 4
3 Ｃ—Ｃ 6
2 5
然后可在这个基础上进一步扩展。具体方法为向这个碳原子加入新的碳原子。现在可供扩展碳原子的位置有六个，可逐一试放。放在一个位置后，与已得到的构造进行比较，如果重复则只算一种；如果构造不同，则把这种新的构造储存下来。在本例中显然六个位置放置后都只算同一种。对于四个碳原子的情况，是根据三个碳原子的结果再推算的。在三个碳原子的结构基础上对新形成的八个空位来试放第四个碳原子，判断重复性，可得两个同分异构体。五个碳原子的情况又是由四个碳原子的两个同分异构体再扩展而来。按这样的算法，实际上计算N个碳原子的烷烃时都要从三个碳原子的情况一步步推过来。
二、 数据结构
1、 碳链的计算机表示
碳链可看作是一种无根树结构，每一个碳原子作为一个结点。结点下子树的个数为该结点的度。碳链这种树结构的储存可用邻接矩阵和广义表两种方式。
使用邻接矩阵来表示各结点之间的连通性。对碳链上每个碳原子都编上号。如1号碳原子和2号碳原子相连，则矩阵元素a12和a21均置为1，若无连通关系则置0。例如下面一个碳链的邻接矩阵表示为

１２３４５６７
１
２
３
４
５
６
７
０１００１１１
１０１１０００
０１０００００
０１０００００
１００００００
１００００００
１００００００

这种表示的优点为扩展碳原子很方便。例如要在上例2号碳原子的右边再增加一个8号碳原子只需将邻接矩阵扩展为8阶方阵，并置元素a28与a82为1，其余新增元素为0即可完成。
另一种表示碳链的方法是用广义表。用字符Ｃ表示一个碳原子，用“（”和“）”表示层次关系，类似于集合。如上例的碳链，用广义表可表示为
Ｃ（Ｃ（ＣＣ）ＣＣＣ）
↑　↑　↑↑　↑↑↑
表示碳原子： 1 2 　 3 4 5 6 7
可见广义表可直接用一个字符串来表示。这种表示方法的好处为判断所求碳链是否重复时较方便，因为重复的异构体的邻接矩阵经过一定的算法可转化成唯一一种广义表，另外广义表储存时也比较方便。
2、树的两种储存结构的互换
由于程序算法在扩展结点时使用邻接矩阵，判重时使用广义表，因此两种储存结构要相互转换。
广义表转化为邻接矩阵相对简单，可用递归过程实现，在此不再赘述。
邻接矩阵转化为广义表时，为了使重复的同分异构体转化为相同的广义表，必须对邻接矩阵进行以下处理：
(1) 按每个结点的度进行由大到小的排序，若度相同，则比较子结点的度的总和。前面例子中的邻接矩阵即是以排好序的。
(2) 以度最大的第一个结点为根构造广义表，也可用递归方法实现。
三、 编程实现
在具体实现时，所用编程语言为Visual C++ 6.0，使用了MFC的SDI界面。可分为以下几个主要部分：
1、 类M2LISTS实现邻接矩阵到广义表的转换
class M2LISTS
{
int N;
char str[LISTS_LENGTH];
void matrix2lists(int,int);
public:
char *initiate(int);
};
void M2LISTS::matrix2lists(int previous,int pt)
{
int flag=0,i;
strcat(str,"C");
for(i=0;i<N;i++)
if(MC[pt][i]==1&&i!=previous)
{
if(!flag) strcat(str,"(");
flag=1;
matrix2lists(pt,i);
}
if(flag==1) strcat(str,")");
}
char *M2LISTS::initiate(int width)
{
strcpy(str,"");
N=width;
matrix2lists(-1,0);
return str;
}

2、 类L2MATRIX实现广义表到邻接矩阵的转换
class L2MATRIX
{
int k;
UINT p;
char ch;
char str[40];
void lists2matrix(int);
public:
void initiate(char *);
};
void L2MATRIX::lists2matrix(int last)
{
ch=str[p];
do
{
p++;
switch(ch)
{
case 'C':
k++;
if(!(last==k))
{
M[last][k]=1;
M[k][last]=1;
}
break;
case '(':
lists2matrix(k);
break;
case ')':
return;
}
ch=str[p];
}while(p<strlen(str));
}
void L2MATRIX::initiate(char lists[])
{
int i,j;
p=0; k=-1;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
M[i][j]=0;
strcpy(str,lists);
lists2matrix(0);
}

3、 类SBD是对邻接矩阵进行按度排序
class SBD
{
private:
int myn;
st treesort[10]; //st是用来储存结点信息的结构，重载了操作符=
int findnext(int,int);
int compud(int,int,int,int);
int partsort(int,int);
int old2new(int);
public:
void sort(int);
};
void SBD::sort(int n)
{
int j,i,next;
myn=n;
for(i=0;i<myn;i++)
for(j=0;j<myn;j++)
MC[i][j]=0; //MC用来储存排序后的邻接矩阵
for(i=0;i<myn;i++) //计算每个结点的度
{
treesort[i].degree=compud(-1,i,1,1);
treesort[i].nodelevel=1;
treesort[i].p=i;
}
j=0;
partsort(j,myn); //对所有结点进行第一趟排序
int dtemp,flag;
while(j<myn)
{
flag=1;
next=findnext(j,treesort[j].degree); //寻找下一个与当前结点度相同的结点
for(i=j;i<=next;i++) //对度相同的结点再计算子结点度的总和
{
dtemp=compud(-1,treesort[i].p,1,++treesort[i].nodelevel);
if(dtemp)
{
treesort[i].degree+=dtemp;
flag=0;
}
}
if(j==i-1) j++; //如果这个度只有一个碳原子，处理下一个
else if(partsort(j,i)&&flag) j=i; //否则按新计算的度再排序，flag避免对两个对称碳原子进行无限制比较
}
for(i=0;i<myn;i++) //生成按度排好序的邻接矩阵
for(j=0;j<myn;j++)
if(M[treesort[i].p][j]==1) MC[i][old2new(j)]=1;
}
int SBD::partsort(int begin,int end) //对编号从begin到end的结点按度进行直接插入排序
{
int i,j,x,flag=1;
st temp;
for(i=begin+1;i<end;i++)
{
temp=treesort[i]; //重载了st结构的操作符”=”，简化程序
j=i-1;
x=treesort[i].degree;
while(j>=begin&&x>treesort[j].degree)
{
treesort[j+1]=treesort[j];
j--;
flag=0;
}
treesort[j+1]=temp;
}
if(flag) return 1;
else return 0;
}
int SBD::findnext(int curr,int d) //寻找下一个度相同的结点
{
int i,r;
for(i=curr;i<myn;i++)
if(treesort[i].degree==d) r=i;
return r;
}
int SBD::compud(int previous,int curr,int currnl,int nodelevel) //计算一个结点的度，nodelevel为所需计算到的结点深度
{
int i,total=0;
for(i=0;i<myn;i++)
if(M[curr][i]==1&&i!=previous)
if(currnl==nodelevel) total++;
else total+=compud(curr,i,currnl+1,nodelevel);
return total;
}
int SBD::old2new(int j) //转换一个结点排序前的下标到排序后的下标
{
int i;
for(i=0;i<myn;i++)
if(treesort[i].p==j) return i;
return i;
}

4、 求同分异构体的主程序
int j,k,newptr=0;
UINT i,n;
char *str;
oldptr=0;
L2MATRIX l2m;
M2LISTS m2l;
SBD sort_by_order;
for(k=0;k<LISTS_STORAGE;k++) //分配储存广义表的空间，olddata储存前一次已求出的同分异构体，newdata储存本次求出的同分异构体
{
olddata[k]=new char[LISTS_LENGTH];
newdata[k]=new char[LISTS_LENGTH];
}
n=2;
strcpy(olddata[0],"C(C)");
for(n=2;n<m_cno;n++)
{
for(j=0;j<=oldptr;j++) //对前一次的每一种同分异构体进行扩展
{
l2m.initiate(olddata[j]); //将前一次的同分异构体由广义表转化为邻接矩阵
for(i=0;i<n;i++) //扩展每一个能扩展的位置
{
if(CompuD(i,n)<4) //判断碳原子的价是否已满
{
M[i][n]=1; //扩展
M[n][i]=1;
sort_by_order.sort(n+1); //将扩展后的邻接矩阵按度排序
str=m2l.initiate(n+1); //将已按度排序的邻接矩阵转化为广义表
if(Judge(str,newptr)) //判重
{
strcpy(newdata[newptr],str); //如与已求得的同分异构体不重复，储存之
newptr++;
}
M[i][n]=0;
M[n][i]=0;
}
}
}
for(k=0;k<LISTS_STORAGE;k++) //将已求好的当前碳原子数的同分异构体转存，为下次扩展做好准备
strcpy(olddata[k],newdata[k]);
oldptr=newptr-1;
newptr=0;
}
char buffer[4];
_itoa(oldptr+1,buffer,10);
CString mystr="同分异构体总数：";
mystr+=buffer;
AfxMessageBox(mystr);
for(k=0;k<LISTS_STORAGE;k++) //删除分配的内存
{
strcpy(result[k],olddata[k]);
delete olddata[k];
delete newdata[k];
}

5、 在屏幕上输出同分异构体
先将广义表转化为邻接矩阵,再利用递归算法画出碳原子构造。
void CCarbonView::DrawCarbon(CDC *pDC,int pt,int previous,int prevplace,CPoint currpoint,UINT size)
{
extern NO;
int place=0,i;
CPoint mypoint;
for(i=0;i<NO;i++)
if(M[pt][i]==1&&i!=previous)
{
do { place++; } while (place==prevplace); //避免与上一个碳原子画重
switch(place) //判断碳链四个不同伸展方向，分别画出
{
case 1:
mypoint=currpoint;
mypoint.y+=logFont.lfHeight/2;
pDC->MoveTo(mypoint);
mypoint.x-=size;
pDC->LineTo(mypoint);
mypoint.x-=logFont.lfWidth;
mypoint.y-=logFont.lfHeight/2;
pDC->TextOut(mypoint.x,mypoint.y,"C");
DrawCarbon(pDC,i,pt,2,mypoint,size);
break;
case 2:
mypoint=currpoint;
mypoint.y+=logFont.lfHeight/2;
mypoint.x+=logFont.lfWidth;
pDC->MoveTo(mypoint);
mypoint.x+=size;
pDC->LineTo(mypoint);
mypoint.y-=logFont.lfHeight/2;
pDC->TextOut(mypoint.x,mypoint.y,"C");
DrawCarbon(pDC,i,pt,1,mypoint,size);
break;
case 3:
mypoint=currpoint;
mypoint.x+=logFont.lfWidth/2;
pDC->MoveTo(mypoint);
mypoint.y-=logFont.lfHeight;
pDC->LineTo(mypoint);
mypoint.x-=logFont.lfWidth/2;
mypoint.y-=logFont.lfHeight;
pDC->TextOut(mypoint.x,mypoint.y,"C");
DrawCarbon(pDC,i,pt,4,mypoint,size-10);
//size-10避免后一层碳原子与前一层碳原子画在一起
break;
case 4:
mypoint=currpoint;
mypoint.x+=logFont.lfWidth/2;
mypoint.y+=logFont.lfHeight;
pDC->MoveTo(mypoint);
mypoint.y+=logFont.lfHeight;
pDC->LineTo(mypoint);
mypoint.x-=logFont.lfWidth/2;
pDC->TextOut(mypoint.x,mypoint.y,"C");
DrawCarbon(pDC,i,pt,3,mypoint,size-10);
}
}
}
完整程序可见盘中Carbon子目录，是VC6的一个Project。另有可执行文件Carbon.EXE。
这样，用计算机求烷烃所有同分异构体的工作基本完成，不光可以知道每种烷烃的异构体数目，而且还可输出具体构造，在化学上也有实际意义。下一步可改进的地方是改善内存的动态分配方式，使之可处理更多碳原子的烷烃，并加上将结果储存为文件、打印输出等功能。