pailiezuhe.txt

实现了字典序求全排列的算法和组合算法． 用C++实现排列组合算法(排列仅实现字典序法,程序见附件)

#include   <iostream.h>  
#include   <list.h>  
   
  char*   trimStr(char   *str)  
  {  
  char   *p;  
  p=str;  
  while(p[0]=='   ')  
  p++;  
  return   p;  
  }  
  list<char*>   parseToList(char   *str,char   *dlm)  
  {  
  char   *oneword;  
  list<char*>   lst;  
  char   str1[1024];  
  strcpy(str1,str);  
  char   *p1;  
    char   *p2;  
  char   *p3;  
  p1=str1;  
  p2=p1;  
  while(p1)  
  {      
  p2=p1;  
  p1=strstr(p1,dlm);  
  if(p1)  
  {  
  p3=p1;  
  p1++;  
  *p3=0;  
  }  
  oneword=new   char[strlen(p2)+1];  
  strcpy(oneword,p2);  
  lst.push_back(oneword);  
   
   
  }  
  return   lst;  
  }  
  list<char*>   strAddList(char*   str,list<char*>   lst)  
  {  
  list<char*>   result;  
  char   *p;  
    list<char*>::iterator   it;  
  int   slen=strlen(str);  
  for(it=lst.begin();it!=lst.end();it++)  
  {  
  p=new   char[slen+strlen(*it)+2];  
  strcpy(p,str);  
  strcat(p,"   ");  
  strcat(p,*it);  
  result.push_back(p);  
  }  
  return   result;  
  }  
  list<char*>   addList(list<char*>   lst1,list<char*>   lst2)  
  {  
  char   *p;  
  list<char*>   result;  
  list<char*>::iterator   it1;  
  for(it1=lst1.begin();it1!=lst1.end();it1++)  
  {  
  p=new   char[strlen(*it1)+1];  
  strcpy(p,*it1);  
  result.push_back(p);  
  }  
  for(it1=lst2.begin();it1!=lst2.end();it1++)  
  {  
  p=new   char[strlen(*it1)+1];  
  strcpy(p,*it1);  
  result.push_back(p);  
  }  
  return   result;  
  }  
   
  list<char*>   combo(char   *str,int   n,int   m)  
  {  
  list<char*>   strlst;  
  strlst=parseToList(str,"   ");  
  int   i=strlst.size();  
  list<char*>::iterator   it;  
   
  char   *argStr;  
  char   *oneCombo;  
  char   *one;  
  char   temp[10];  
  list<char*>   result;  
  if(m==1)  
  {  
   
  for(it=strlst.begin();it!=strlst.end();it++)  
  {  
  oneCombo=new   char[strlen(*it)+1];  
  strcpy(oneCombo,*it);  
  result.push_back(oneCombo);  
  }  
  return   result;  
  }else  
  if(n==m)  
  {  
  one=new   char[100];  
  one[0]=0;  
  for(it=strlst.begin();it!=strlst.end();it++)  
  {  
  strcat(one,"   ");  
  sprintf(temp,"%s",*it);  
  strcat(one,temp);  
  }  
  strcpy(one,trimStr(one));  
  oneCombo=new   char[strlen(one)+1];  
  strcpy(oneCombo,one);  
  result.push_back(oneCombo);  
  return   result;  
  }else  
  {  
  argStr=new   char[1024];  
  argStr[0]=0;  
   
  it=strlst.begin();  
  for(int   k=0;k<=n-m;k++)  
        // for(it=strlst.begin();it!=strlst.end();it++)  
  {       list<char*>::iterator   it2;  
  int   j=0;  
  it2=it;  
  argStr[0]=0;  
  for(it2++;it2!=strlst.end();it2++)  
  {  
  j++;  
  strcat(argStr,"   ");  
  strcat(argStr,*it2);  
   
  }  
  strcpy(argStr,trimStr(argStr));  
  list<char*>   parLst;  
  parLst=strAddList(*it,combo(argStr,j,m-1));  
  result=addList(result,parLst);  
  it++;  
  }  
  return   result;  
  }  
   
  }  
  int   main(int   argc,   char*   argv[])  
  {  
  char     str1[100];  
  strcpy(str1,"hello   world   fsrong   and   xxf");  
  list<char*>   lst;  
  list<char*>::iterator   it;  
  lst=   combo(str1,5,2);  
  for(it=lst.begin();it!=lst.end();it++)  
  cout<<*it<<endl;  
   
  cin>>str1;  
  return   0;  
  }