使用冒泡排序对字符串数组进行排序

Question

如有任何帮助，我们将不胜感激。我正在尝试使用以下代码使用冒泡排序对数组中包含的 12 个字符串按字母顺序排序：

#include <stdio.h>
#include <string.h>
int main()
{
   //initialising variables and the array
   char *DT [12] = { "James Smith DT01 DT265A", "John Murphy DT02 DT265A", "Robert Lam DT03 DT265A", "Michael Martin DT04 DT265A", "William Brown DT05 DT265A", "David Roy DT06 DT265A", "Richard Tremblay DT07 DT265A", "Joseph Lee DT08 DT265A", "Thomas Gagnon DT09 DT265A", "Charles Wilson DT10 DT265A", "Chris Philips DT11 DT265A", "Henry Hill DT12 DT265A"  } ;
   char temp[100];
   int n = sizeof(DT)/sizeof(DT[0]);

   //Implementing Algorithm using bubble sort to sort string array
   //
   for (int j = 0 ; j < n - 1 ; j++ )
   {
      for (int i = j + 1 ; i < n ; i++ )
      {
         if( strcmp(DT[j], DT[i]) > 0 ) 
         {
            strcpy(temp, DT[j]);
            strcpy(DT[j], DT[i]);
            strcpy(DT[i], temp);
         }//end if
      }//end for
   }//end for
   printf("Strings in sorted order are : ");
   for (int i=0; i<n; i++)
   {
      printf("\n String %d is %s", i+1, DT[i]);
   }

   getchar();
   getchar();
   return 0;
}//end main()

我得到的输出是：

排序后的字符串是：

字符串 1 是 A

字符串 2 是 A

字符串 3 是 2vid Roy DT06 DT265A

弦 4 是 Roy DT06 DT265A

字符串 5 是 Charles Wilson DT10 DT265A

字符串 6 是

字符串 7 是 Chris Philips DT11 DT265A

字符串 8 是 06 DT265A

弦 9 是 avidRoy DT06 DT265A

字符串 10 是 mith DT01 DT265David Roy Dyy DT06 DT265A

字符串 11 是 y DT06 DT265A

字符串 12 是 y DT06 DT265A

Answer 1

问题是您试图覆盖文字字符串的内容，而 C 中的文字字符串是只读数组字符数。

与其尝试复制字符串本身，不如复制指针。如

char *temp = DT[j];
DT[j] = DT[i];
DT[i] = temp;

另一种可能的解决方案是将 DT 改为数组的数组：

char DT[12][100] = { ... };

确保辅助数组的大小足以容纳最长的字符串（加上一个，因为您当然也需要 space 作为终止符）。

Answer 2

您不能对只读字符串使用 strcpy。当您键入 "James Smith DT01 DT265A" 并影响其地址时，此字符串是只读的。

所以如果你想保持这种方式，你可以更换

char temp[100];
...
        strcpy(temp, DT[j]);
        strcpy(DT[j], DT[i]);
        strcpy(DT[i], temp);

来自

char *temp;
...
        temp = DT[j];
        DT[j] = DT[i];
        DT[i] = temp;

Answer 3

您可以使用 char arr[][MAX] 并使用以下函数进行排序：

void sortStrings(char arr[][MAX], int n)
{
    char temp[MAX];

    // Sorting strings using bubble sort
    for (int j=0; j<n-1; j++)
    {
        for (int i=j+1; i<n; i++)
        {
            if (strcmp(arr[j], arr[i]) > 0)
            {
                strcpy(temp, arr[j]);
                strcpy(arr[j], arr[i]);
                strcpy(arr[i], temp);
            }
        }
    }
}

Answer 4

你有一个指向字符串文字的指针数组

char *DT [12] = { "James Smith DT01 DT265A", ... };

然后您试图更改字符串文字。

strcpy(DT[j], DT[i]);
strcpy(DT[i], temp);

但是您不能更改字符串文字。任何更改字符串文字的尝试都会导致未定义的行为。

来自 C 标准（6.4.5 字符串文字）

7 It is unspecified whether these arrays are distinct provided their elements have the appropriate values. If the program attempts to modify such an array, the behavior is undefined.

您需要交换的是指向字符串文字的指针。

还要考虑到您错误地实施了冒泡排序算法。事实上，您实施了低效的选择排序。冒泡排序算法基于比较相邻元素。

并且根据 C 标准，不带参数的函数 main 应声明为

int main( void )

这是一个演示程序，展示了如何将冒泡排序算法应用于您的数组。

#include <stdio.h>
#include <string.h>

int main(void) 
{
    enum { N = 12 };
    char * DT[N] = 
    { 
        "James Smith DT01 DT265A", 
        "John Murphy DT02 DT265A", 
        "Robert Lam DT03 DT265A", 
        "Michael Martin DT04 DT265A", 
        "William Brown DT05 DT265A", 
        "David Roy DT06 DT265A", 
        "Richard Tremblay DT07 DT265A", 
        "Joseph Lee DT08 DT265A", 
        "Thomas Gagnon DT09 DT265A", 
        "Charles Wilson DT10 DT265A", 
        "Chris Philips DT11 DT265A", 
        "Henry Hill DT12 DT265A"  
    };

    for ( size_t n = N, last; !( n < 2 ); n = last )
    {
        for ( size_t i = last = 1; i < n; i++ )
        {
            if ( strcmp( DT[i], DT[i-1] ) < 0 )
            {
                char *tmp = DT[i];
                DT[i] = DT[i-1];
                DT[i-1] = tmp;
                last = i;
            }
        }
    }

    puts( "Strings in sorted order are" );

    for ( size_t i = 0; i < N; i++ )
    {
        printf( "String %zu is %s\n", i + 1, DT[i] );
    }

    return 0;
}

程序输出为

Strings in sorted order are
String 1 is Charles Wilson DT10 DT265A
String 2 is Chris Philips DT11 DT265A
String 3 is David Roy DT06 DT265A
String 4 is Henry Hill DT12 DT265A
String 5 is James Smith DT01 DT265A
String 6 is John Murphy DT02 DT265A
String 7 is Joseph Lee DT08 DT265A
String 8 is Michael Martin DT04 DT265A
String 9 is Richard Tremblay DT07 DT265A
String 10 is Robert Lam DT03 DT265A
String 11 is Thomas Gagnon DT09 DT265A
String 12 is William Brown DT05 DT265A

如果你想处理一个包含字符串的二维字符数组那么程序可以看下面的方式

#include <stdio.h>
#include <string.h>

int main(void) 
{
    enum { M = 12, N = 100 };
    char DT[M][N] = 
    { 
        "James Smith DT01 DT265A", 
        "John Murphy DT02 DT265A", 
        "Robert Lam DT03 DT265A", 
        "Michael Martin DT04 DT265A", 
        "William Brown DT05 DT265A", 
        "David Roy DT06 DT265A", 
        "Richard Tremblay DT07 DT265A", 
        "Joseph Lee DT08 DT265A", 
        "Thomas Gagnon DT09 DT265A", 
        "Charles Wilson DT10 DT265A", 
        "Chris Philips DT11 DT265A", 
        "Henry Hill DT12 DT265A"  
    };

    for ( size_t n = M, last; !( n < 2 ); n = last )
    {
        for ( size_t i = last = 1; i < n; i++ )
        {
            if ( strcmp( DT[i], DT[i-1] ) < 0 )
            {
                char tmp[N];
                strcpy( tmp, DT[i] );
                strcpy( DT[i], DT[i-1] );
                strcpy( DT[i-1], tmp );
                last = i;
            }
        }
    }

    puts( "Strings in sorted order are" );

    for ( size_t i = 0; i < M; i++ )
    {
        printf( "String %zu is %s\n", i + 1, DT[i] );
    }

    return 0;
}

其输出与上图相同

使用冒泡排序对字符串数组进行排序

Sorting an array of strings with Bubble sort

c

sorting

string

algorithm

bubble-sort