N个正整数联接成最小整数

本文主要是介绍N个正整数联接成最小整数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。

例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355

分析：

其实这题就是将这些整数以字符串方式排序，整数的第一位越小，其越靠前；若第一位相同则同理比较第二位。依次类推，直至能确定其顺序。当其中一个数是另一个数的部分时，如32（记为A）和321（记为B）,则比较B(321)与B的剩余位(1)与A的连接(即132)的大小。

代码如下：

#include<iostream>
using namespace std;
struct Node
{
char str[11];
Node* next;
};
int Compare(const char* str1,const char* str2)
{
char c1=str1[0],c2=str2[0];
int i=1;
while(c1==c2)
{
c1=str1[i];
c2=str2[i];
if(c1=='\0')
{
if(c2=='\0') return 0;
char temp[10];
strcpy(temp,str2+i);
strcat(temp,str1);
return Compare(str2,temp);
}
if(c2=='\0')
{
char temp[10];
strcpy(temp,str1+i);
strcat(temp,str2);
return Compare(temp,str1);
}
i++;
}
return c1-c2;
}
void main()
{
int n,arr[100],i;
cout<<"请输入要输整数的个数：";
cin>>n;
for(i=0;i<n;i++)
{
cout<<"请输入第 "<<(i+1)<<" 个整数：";
cin>>arr[i];
}
//排序
Node *head=new Node;
Node *p=new Node;
head->next=p;
p->next=NULL;
itoa(arr[0],p->str,10);
Node *newNode;
bool isEnd;
for(i=1;i<n;i++)
{
//生成新节点
newNode=new Node;
itoa(arr[i],newNode->str,10);
newNode->next=NULL;
//插入节点
p=head;
isEnd=false;
while(Compare(newNode->str,p->next->str)>=0)
{
if(p->next->next==NULL)
{
isEnd=true;
break;
}
p=p->next;
}
if(isEnd) p->next->next=newNode;
else 
{
newNode->next=p->next;
p->next=newNode;
}
}
cout<<"有上述整数连接成的最小整数是：";
p=head->next;
while(p!=NULL)
{
cout<<p->str<<" ";
p=p->next;
}
cout<<endl;
}