JZ-C-33

剑指offer第三十三题：把数组排成最小的数
  1 //============================================================================
  2 // Name        : JZ-C-33.cpp
  3 // Author      : Laughing_Lz
  4 // Version     :
  5 // Copyright   : All Right Reserved
  6 // Description : 把数组排成最小的数
  7 //============================================================================
  8 
  9 #include <iostream>
 10 #include <string>
 11 #include "string.h"
 12 #include <algorithm>
 13 #include <stdio.h>
 14 using namespace std;
 15 
 16 int compare(const void* strNumber1, const void* strNumber2);
 17 
 18 // int型整数用十进制表示最多只有10位
 19 const int g_MaxNumberLength = 10;
 20 
 21 char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1];
 22 char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1];
 23 
 24 void PrintMinNumber(int* numbers, int length)
 25 {
 26     if(numbers == NULL || length <= 0)
 27         return;
 28 
 29     char** strNumbers = (char**)(new int[length]);
 30     for(int i = 0; i < length; ++i)
 31     {
 32         strNumbers[i] = new char[g_MaxNumberLength + 1];
 33         sprintf(strNumbers[i], "%d", numbers[i]);
 34     }
 35 
 36     qsort(strNumbers, length, sizeof(char*), compare);//从小到大排序，排序规则为compare函数★
 37 
 38     for(int i = 0; i < length; ++i)
 39         printf("%s", strNumbers[i]);
 40     printf("
");
 41 
 42     for(int i = 0; i < length; ++i)
 43         delete[] strNumbers[i];
 44     delete[] strNumbers;
 45 }
 46 
 47 // 如果[strNumber1][strNumber2] > [strNumber2][strNumber1], 返回值大于0
 48 // 如果[strNumber1][strNumber2] = [strNumber2][strNumber1], 返回值等于0
 49 // 如果[strNumber1][strNumber2] < [strNumber2][strNumber1], 返回值小于0
 50 int compare(const void* strNumber1, const void* strNumber2)//这里定义排序规则★
 51 {
 52     // [strNumber1][strNumber2]
 53     strcpy(g_StrCombine1, *(const char**)strNumber1);
 54     strcat(g_StrCombine1, *(const char**)strNumber2);
 55 
 56     // [strNumber2][strNumber1]
 57     strcpy(g_StrCombine2, *(const char**)strNumber2);
 58     strcat(g_StrCombine2, *(const char**)strNumber1);
 59 
 60     return strcmp(g_StrCombine1, g_StrCombine2);
 61 }
 62 
 63 // ====================测试代码====================
 64 void Test(char* testName, int* numbers, int length, char* expectedResult)
 65 {
 66     if(testName != NULL)
 67         printf("%s begins:
", testName);
 68 
 69     if(expectedResult != NULL)
 70         printf("Expected result is: 	%s
", expectedResult);
 71 
 72     printf("Actual result is: 	");
 73     PrintMinNumber(numbers, length);
 74 
 75     printf("
");
 76 }
 77 
 78 void Test1()
 79 {
 80     int numbers[] = {3, 5, 1, 4, 2};
 81     Test("Test1", numbers, sizeof(numbers)/sizeof(int), "12345");
 82 }
 83 
 84 void Test2()
 85 {
 86     int numbers[] = {3, 32, 321};
 87     Test("Test2", numbers, sizeof(numbers)/sizeof(int), "321323");
 88 }
 89 
 90 void Test3()
 91 {
 92     int numbers[] = {3, 323, 32123};
 93     Test("Test3", numbers, sizeof(numbers)/sizeof(int), "321233233");
 94 }
 95 
 96 void Test4()
 97 {
 98     int numbers[] = {1, 11, 111};
 99     Test("Test4", numbers, sizeof(numbers)/sizeof(int), "111111");
100 }
101 
102 // 数组中只有一个数字
103 void Test5()
104 {
105     int numbers[] = {321};
106     Test("Test5", numbers, sizeof(numbers)/sizeof(int), "321");
107 }
108 
109 void Test6()
110 {
111     Test("Test6", NULL, 0, "Don't print anything.");
112 }
113 
114 
115 int main(int argc, char** argv)
116 {
117     Test1();
118     Test2();
119     Test3();
120     Test4();
121     Test5();
122     Test6();
123 
124     return 0;
125 }