liss.cpp

c++程序实现最长单调序列

/*----------------------------------------------------------------------------------------

功能描述：本程序实现求一个给定数列的最长单调递增子序列的长度和其中的一个序列。

实现方法：在程序中引用一个数组(int)c[i]来表示所有长度为i的单增子序列中末项元素的最小值，
          最终可以求得最长单增序列的长度； 又引用了一个数据结构struct Node，定义了一个
		  以这个数据结构为元素的数组(struct Node)d[i]和c[i]中的i对应起来，其中保存了c[i]
		  中数据更新的过程，根据它可以求得一个最长的单增子序列。

功能展望：该程序可以求得最长单调递增子序列长度length和其中一个子序列，但长度为length的子
		  序列可能有多个，这里就存在一个计数问题。如何求得长度为length的子序列的个数count
		  并根据某种规律列出所有长度为length的单增子序列是一个需要进一步解决的问题。

          作者：  毛毛                                        日期：2007-10-7
------------------------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct Node 
{
	int elem;
	struct Node * next;
};

int bisearch( int *c,int m ,int s);//二分法查找元素
long FileSize(FILE *stream);//计算文件长度
int * GetArray(char * body,int &length);//根据子符数据获得一个整形数组

void main()
{
	FILE * fl=NULL;
	printf("输入要计算的文件名:\n");
	char fileName[100];
	scanf("%s",fileName);
	if((fl=fopen(fileName,"r"))==NULL)
	{
		printf("文件打开错误!\n");
		return;
	}
	long size=FileSize(fl);
	fseek(fl, SEEK_SET, 0); 
	char *body=new char[size];
    fread(body,size-1,1,fl);
	fclose(fl);
	*(body+size-1)='\0';
	int length;
	int * array =GetArray(body,length);
	printf("元素的个数为:%d\nwaiting...\n",length);
	int t1=clock();
    int i,k,s;
	int *c=new int [length];
	struct Node *d=new struct Node [length];
	for(i=0;i<=length;i++)//定义一个数据结构
	{
		d[i].next=NULL;
	}
    s = 1; //s表示当前序列的最长单增子序列的长度，最终表示整个序列的，同时为数组C的有效长度
    c[1] = array[0];//c[i]表示所有长度为i的单增子序列中末项元素的最小值
    for( i = 0; i < length; i ++ )//计算最单增子序列的长度(此方法得于网上)
    {
        k = bisearch( c,array[i],s);
        if( k > s )   
		{
			s++;
		}
        c[k] = array[i];
		struct Node * p =new struct Node;
		p->elem =i;
		p->next =d[k].next;
		d[k].next=p;
    }
    printf( "最长子序列长度为:%d\n", s );
    if(s<=10000)
	{
		printf("子序列之一如下:\n");
		struct Node *p;
		d[s].elem =d[s].next->elem;//确定子序列中最大的元素
		for(i=s-1;i>=1;i--)//依次确定所有元素，按取最小值的原则
		{
			p=d[i].next;
			while(p!=NULL)
			{
				if(p->elem<d[i+1].elem && *(array+p->elem)<*(array+d[i+1].elem))
				{
					d[i].elem =p->elem;	
					break;
				}
				else
				{
					p=p->next;
				}
			}
		}
		for(i=1;i<=s;i++)
		{
		printf("%d ",*(array+d[i].elem));
		}
	}
	int t2=clock();
	double t=(t2-t1)/1000.0;
	printf("耗时:%f秒",t);
	getchar();
	getchar();
};

int bisearch( int *c,int m ,int s)
{
    int mid, low, high;
    low = 1; high = s;
    while( low < high ) {
        mid = (low+high)/2;
        if( c[mid] == m )    return mid;
        if( c[mid] < m )    low = mid+1;
        else    high = mid;
    }
    if( c[low] >= m )    return low;
    else    return low+1;
};

int * GetArray(char * body,int &length)
{
	length=0;
	int i;
	int ch;
	for(i=0;body[i]!='\0';i++)
	{
		 
		if(body[i]==10)
		{
			break;
		}
		else
		{
			ch=body[i]-48;
			length=length*10+ch;
		}	
	}
	i++;
	int *array=new int[length];
	for(int index=0;index<length;index++)
	{
		array[index]=0;
	}
	for(index=0;body[i]!='\0';i++)
	{
		if(body[i]==' ')
			{
				index++;
			}
			else
			{
				ch=body[i]-48;
				array[index]=array[index]*10+ch;
			}			
	}
return array;
};
long FileSize(FILE *stream) 
{ 
   long curpos, length; 
   curpos = ftell(stream); 
   fseek(stream, 0L, SEEK_END); 
   length = ftell(stream); 
   fseek(stream, curpos, SEEK_SET); 
   return length; 
} ;