分布式系统中的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->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) { 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<sub_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; }