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;
}