經典指數          
原因
807
瀏覽數
0
收藏數
 

分布式系統中的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. 為該算法設計并實現單元測試

     舉報   糾錯  
該題目由題來君提供于 2015-10-08 16:59
 
切換
1 個答案

//對輸入序列,進行排序,同時找到保序子序列(每個序號位置之后的序號都大于它,如上題: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->snsn)

{

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->snsn)

{

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->snsn)//比下一個標志位小的,按一行輸出

{

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;

}

舉報   題來君 · 2015-12-29 23:30
 
切換
撰寫答案
广西快三结果控 安徽十一选五走势图一定牛手机版 河北11选五怎么看号 深圳风采中国福利彩票双色球 北京赛车 官方app下载 北京跑车时时彩走势图 湖北11选5任选基本走 北京快乐8推荐和预测 分分彩玩法互补漏洞 黑龙江22选5开奖结果查询表 内蒙快3走势图今天