longest_common_sub-sequence.c

求最长公共子序列

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 100
#define MAX1 1000
#define MAX2 3000
#define MAX3 10000

static int temp[MAX3];
static int length = 0;

//////////////////////////////////////////////////////////////////
//////////////////////*法一：转化为LCS问题求解*///////////////////
//////////////////////比较原序列与排好序的序列的LCS即可///////////
void lcs_length(int *x , int *y , int *b,int xlen,int ylen)
{
	int i,j,k;
	int c[MAX][MAX];
	
	for(i=0;i<=xlen;i++)
		c[i][0] = 0;
	for(j=0;j<=ylen;j++)
		c[0][j] = 0;
	for(i=0;i<=xlen;i++)
		for(j=0;j<=ylen;j++)
	  {
		  if(x[i] == y[j])
      { 
		     c[i][j] = c[i-1][j-1] + 1;
	       k = i*(ylen+1) + j;
	       b[k] = 1;  //表示斜上
			}
			else if(c[i-1][j] >= c[i][j-1])
	    {
				c[i][j] = c[i-1][j];
				k = i*(ylen+1) + j;
				b[k] = 2;  //表示向上
		  }
			else
	    {
				c[i][j] = c[i][j-1];
				k = i*(ylen+1) + j;
				b[k] = 3;   //表示向左
			}
		}
}
void LCS(int *b,int *x,int i,int j,int t)
{
	int k;
	if(i == -1 || j == -1)
		return ;
	k = i*(t+1) + j;
	if(b[k] == 1)
	{
		LCS(b,x,i-1,j-1,t);
		temp[length++] = x[i];
	}
	else if(b[k] == 2)
		LCS(b,x,i-1,j,t);
	else
		LCS(b,x,i,j-1,t);
}

void QuickSort(int *a,int l,int h)//递归的快速排序
{
	int i,j;
	int sep,t;
	i = l;
	j = h;
	sep = a[(l+h)/2];
	do	{
		while (a[i]<sep)
           i++;
		while (a[j]>sep)
		   j--;
		if(i<=j)
		{
			t=a[i];
			a[i++]=a[j];
			a[j--]=t;
		}
	}while (i<=j);
	if(l<j)
		QuickSort(a,l,j);
	if(i<h)
		QuickSort(a,i,h);
	return;
}
	
/////////////////////////////////////////////////////////////
/////////////////////法二：动态规划法///////////////////////
int DymLis(int x[],int xlen)  //返回LIS的个数
{
    int Len = 1;
    int up,low,mid;  //二分查找的上下界与中点
    int tt[MAX3] ; //中间存储lis的数组    
    int i;
    tt[0] = 0;
    tt[1] = x[0]; 
    for(i=0; i< xlen; i++)
    {
        up = 0;
        low = Len;
        while(up <= low)
        {
           mid = (up + low)/2 ;
           if(tt[mid] < x[i])
               up = mid + 1;
           else
               low = mid - 1;
        }
        tt[up] = x[i];
        if(up > Len) Len++ ;
     }
     for(i=0; i< Len ; i++)
        temp[i] = tt[i+1];
     return Len;
}
void copyArray(int x[],int y[],int length)  //将x数组前面长length的部分复制给y
{
    for(int i=0;i<length;i++)
       y[i] = x[i];
    return;
}

////////////////////////////////
int main()
{ 
   /////////////declaration//////////
   int x1[MAX1],x2[MAX2],x3[MAX3];

   int b[MAX] = {0};
   int i;
   int *p;
   //////////initialize all the arrays///////
   srand(time(0));
   for(i=0;i<MAX1;i++)
	   x1[i] = (rand()+1)%(MAX1+1);
   for(i=0;i<MAX2;i++)
	   x2[i] = (rand()+1)%(MAX2+1);
   for(i=0;i<MAX3;i++)
	   x3[i] = (rand()+1)%(MAX3+1);

   printf("注释：此次实验做出了两种方法，最长公共子序列方法与动态规划方法。如果使用前者，而序\
列较大的话，所需的二维数组会很大，而此时内存是无法在栈内给其分配空间的，所以只能能过读写文\
件来实现大数组的情况，在此没有做此项功能，只简单实现在最长公共子序列的方法，下以｛1，4，6，9，\
3，2，11，5，10｝为例测试其是否成功\n\
因为第二种动态规划的方法更简便，时间复杂度更小，为O(nlgn)，而且不存大需要较大数组的情况！\n\n\
   \n");
   printf("////////////Method by LCS(Longest Common Subsequence)--smart Test////////////");
   int x[10] = {4,1,6,9,3,2,11,5,10,8};
   printf("\n\nThe Original Sequence is：  ");
   for(i=0;i<10;i++)
       printf("%d ",x[i]);
   printf("\nIts LIS is：   ");
   int y[10] ;
   copyArray(x,y,10);
   QuickSort(y,0,9);
   lcs_length(x,y,b,10,10);
   LCS(b,x,10,10,10);
   length--;
   int lisx[length];
   copyArray(temp,lisx,length);
   for(i=0;i<length;i++)
       printf("%d ",lisx[i]);

    printf("\n///////////////Dynamic Programming---By binary searching Method///////////\n\n");
    printf("Generate three random arrays，respectively, n = 1000,3000,10000\n\
Every Longest Increasing Subsequence of them is as followings:\n");
    printf("n=1000:\n\t");
    int len1 = DymLis(x1,MAX1);
    int ll1[len1];
    copyArray(temp,ll1,len1);
    for(i=0;i<len1;i++)
       printf("%d ",ll1[i]);
    
    printf("\n\nn=3000:\n\t");   
    int len2 = DymLis(x2,MAX2);
    int ll2[len2];
    copyArray(temp,ll2,len2);
    for(i=0;i<len2;i++)
       printf("%d ",ll2[i]);

    printf("\n\nn=10000:\n\t");   
    int len3 = DymLis(x3,MAX3);
    int ll3[len3];
    copyArray(temp,ll3,len3);
    for(i=0;i<len3;i++)
       printf("%d ",ll3[i]);
    printf("\n\n");
       
    printf("Press any button to end...\n");
    char c = getchar();
    return 0;
   
}