不下降序列2.cpp

求解最长不下降序列的程序

#include<iostream.h>

const int dataTable[]={18,7,14,10,12,23,41,16,24,28};
const int n=10;

struct node;
struct followNode//用于记录最长不下降序列中下一个节点信息的结构体

				 //当最长序列中的下一节点有多个选择，即同时存在多条长度相等的最长序列时，
				       //用next指针形成链表，储存出现分支时的节点信息
{
	node *fNode;
	followNode *next;
};
struct node//定义节点结构体
{
	int val;
	node *pre;
	int followCount;//以该点作为首节点的最长不下降序列长
	followNode *follow;//不下降序列中的下一节点链表
}*end;


followNode *CreateFollowNode()
{
	followNode *t=new followNode;
	t->next=NULL;
	t->fNode=NULL;
	return t;
}
node *CreateNode(int val)//初始化节点
{
	node *t=new node;
	t->val=val;
	t->pre=NULL;
	t->follow=CreateFollowNode();
	t->followCount=0;
	return t;
}
void CreateQueue()//将原始数据存入链表
{
	int i=0;
	node *t=CreateNode(dataTable[n-1]);
	node *next=t;
	end=t;
	for(i=n-2;i>=0;i--)
	{
		node *t=CreateNode(dataTable[i]);
		next->pre=t;
		next=t;
	}
}

int Solute(node **longest)
{
	int max;
	node *now=CreateNode(0);
	node *compared=CreateNode(0);
	if(n!=1)now=end->pre;
	else {*longest=end;return 1;}
	while(1)
	{
		compared=end;
		while(now!=compared)
		{
			if(now->val<=compared->val)
				if(now->followCount<compared->followCount+1)
				{
					now->followCount=compared->followCount+1;
					now->follow ->fNode=compared;
					now->follow ->next=NULL;
					if(max<now->followCount+1)
					{
						max=now->followCount+1;
						*longest=now;
					}
				}
				else if(now->followCount==compared->followCount+1)
				{
					followNode *t=now->follow;
					while(t->next !=NULL)
						t=t->next ;
					t->next =CreateFollowNode();
					t->next->fNode=compared;
				}
			compared=compared->pre;
		}
		if(NULL==now->pre)break;
		else now=now->pre;
	}
	return max;
}
void DisplayResult(int length,node *sNode)
{
	int i,count=1;
	node *t=sNode,*pt=t;
	cout<<endl<<"\t已知原数列为：\n\t\t"<<dataTable[0];
	for(i=1;i<n;i++)
		cout<<","<<dataTable[i];
	cout<<endl<<"\t则其最长不下降序列为："<<endl;
	while(count--)
	{
		t=sNode;
		cout<<"\t\t";
		while(1)
		{
			cout<<t->val;
			if(t->follow->fNode==NULL)break;
			pt=t;	
			t=t->follow->fNode;
			if(pt->follow->next!=NULL)
			{
				pt->follow =pt->follow ->next ;
				count++;
			}
			cout <<',';
		}
		cout<<endl;

	}
	cout<<endl<<"\t长度为："<<length<<endl<<endl;
}

void main()
{
	int max;
	node *t=new node;
	CreateQueue();
	max=Solute(&t);
	DisplayResult(max,t);
}