分布式系统中的RPC请求经常出现乱序的情况。 写一个算法来将一个乱序的序列保序输出。例如,假设起始序号是1，对于(1, 2, 5, 8, 10, 4, 3, 6, 9, 7)这个序列，输出是: 1 2 3, 4, 5 6 7, 8, 9, 10 上述例子中，3到来的时候会发现4,5已经在了。因此将已经满足顺序的整个序列（3, 4, 5）输出为一行。 要求： 1. 写一个高效的算法完成上述功能，实现要尽可能的健壮、易于维护 2. 为该算法设计并实现单元测试
//对输入序列，进行排序，同时找到保序子序列（每个序号位置之后的序号都大于它，如上题：1 2 3 6 7），然后按规则输出
//vs2008，win32编程
// baoxu.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "stdlib.h"
struct Node
{
int sn;
Node* next;
};
void order_preserve(Node* first)
{
if(first==NULL)
{
printf("未输入序号\n");
return;
}
printf("输入序号序列：\n");
Node* tem=first;
printf("%d",tem->sn);
tem=tem->next;
while(tem!=NULL)
{
printf(" %d",tem->sn);
tem=tem->next;
}
printf("\n");
Node*
order_first=new Node;
order_first->next=new Node;
Node*
temp=order_first->next;
temp->sn=first->sn;
temp->next=NULL;
Node* temp_pre=order_first;
Node* sub_order_first=new Node;
sub_order_first->next=new
Node;
Node* sub_temp=sub_order_first->next;
sub_temp->sn=first->sn;
sub_temp->next=NULL;
Node*
sub_temp_pre=sub_order_first;
first=first->next;
while(first!=NULL)
{
//插入排序
while(temp!=NULL)
{
if(first->sn
{
temp_pre->next=new Node;
temp_pre->next->next=temp;
temp_pre->next->sn=first->sn;
break;
}
temp_pre=temp;
temp=temp->next;
}
if(temp==NULL)
{
temp_pre->next=new Node;
temp_pre->next->next=temp;
temp_pre->next->sn=first->sn;
}
//找符合保序的子序列
while(sub_temp!=NULL)
{
if(first->sn
{
sub_temp->sn=first->sn;
sub_temp=sub_temp->next;
sub_temp_pre->next->next=NULL;
Node* te=NULL;
while(sub_temp!=NULL)
{
te=sub_temp->next;
delete sub_temp;
sub_temp=te;
}
break;
}
sub_temp_pre=sub_temp;
sub_temp=sub_temp->next;
}
if(sub_temp==NULL)
{
sub_temp_pre->next=new Node;
sub_temp_pre->next->sn=first->sn;
sub_temp_pre->next->next=NULL;
}
temp=order_first->next;
temp_pre=order_first;
sub_temp=sub_order_first->next;
sub_temp_pre=sub_order_first;
first=first->next;
}
//保序输出序列
Node*
tempt;
tempt=order_first->next;
delete order_first;
order_first=tempt;
tempt=sub_order_first->next->next;
delete
sub_order_first->next;
delete sub_order_first;
sub_order_first=tempt;
if(order_first!=NULL)
{
printf("序号序列的保序输出为：\n%d",order_first->sn);
tempt=order_first->next;
delete order_first;
order_first=tempt;
while(order_first!=NULL&&sub_order_first!=NULL)
{
if(order_first->sn
{
printf(",%d",order_first->sn);
tempt=order_first->next;
delete order_first;
order_first=tempt;
}
else
{
printf("\n%d",order_first->sn);
tempt=order_first->next;
delete order_first;
order_first=tempt;
tempt=sub_order_first->next;
delete sub_order_first;
sub_order_first=tempt;
}
}
while(order_first!=NULL)
{
printf(",%d",order_first->sn);
tempt=order_first->next;
delete order_first;
order_first=tempt;
}
printf("\n");
}
else//没必要
{
printf("未输入序号\n");
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Node*
first=new Node;
first->next=NULL;
Node* temp=first;
printf("请输入序号序列，结束输入0：\n");
//std::cout<<'
';
int te;
while(1)
{
scanf("%d",&te);
if(te<=0)
{
temp->next=NULL;
break;
}
temp->next=new
Node;
temp=temp->next;
temp->sn=te;
}
order_preserve(first->next);
while(first!=NULL)
{
temp=first->next;
delete first;
first=temp;
}
system("pause");
return 0;
}
