C代码冒泡排序有时不能给出正确的输出

Question

我正在尝试使用冒泡排序法对数字进行排序。但是，有时会输出 returns 一些不正确的答案。

感谢有人可以帮助解决此问题。 C代码和错误输出如下

typedef struct
{
    char pname[2];
    int ptotime;
} data;

int main()
{
    int totalwait = 0;
    data name[] = {{'A', .ptotime = 4},
                   {'B', .ptotime = 6},
                   {'C', .ptotime = 3},
                   {'D', .ptotime = 7},
                   {'E', .ptotime = 2}};

    printf("Process Name\t Process Time \n");

    for (int j = 0; j < 5; j++)
    {
        printf("\t%s\t\t\t\t%d\n", name[j].pname, name[j].ptotime);
    }

    //Shortest job first (SJF) scheduling
    printf("\nShortest job first (SJF) scheduling \n");

    int swapped, temp;

    while (1)
    {
        swapped = 0;

        for (int x = 0; x < 5; x++)
        {
            if (name[x].ptotime >= name[x + 1].ptotime)
            {
                temp = name[x].ptotime;
                name[x].ptotime = name[x + 1].ptotime;
                name[x + 1].ptotime = temp;
                swapped = 1;
                char temp2[2];
                strcpy(temp2, name[x].pname);
                strcpy(name[x].pname, name[x + 1].pname);
                stpcpy(name[x + 1].pname, temp2);
            }
        }

        if (swapped == 0)
        {
            break;
        }
    }
    printf("Process Name\t Process Time \n");

    for (int j = 0; j < 5; j++)
    {
        printf("\t%s\t\t\t\t%d\n", name[j].pname, name[j].ptotime);
    }

    return 0;
}

输出

Process Name     Process Time
        A                               4
        B                               6
        C                               3
        D                               7
        E                               2

Shortest job first (SJF) scheduling
Process Name     Process Time
                                        0
        E                               2
        C                               3
        A                               4
        B                               6

预期输出

Process Name     Process Time
        A                               4
        B                               6
        C                               3
        D                               7
        E                               2

Shortest job first (SJF) scheduling
Process Name     Process Time
        E                               2
        C                               3
        A                               4
        B                               6
        D                               7

Answer 1

这里有问题：

for (int x = 0; x < 5; x++) {
      if (name[x].ptotime >= name[x + 1].ptotime) {

x 可以取的最大值是 4。但是 name[x + 1] 将访问数组末尾之外的一个元素，该数组只有 5 个元素。越界访问数组会产生未定义的行为，并且所有赌注都关闭。

虽然可能还有更多问题。

Answer 2

变化：

for(int x = 0; x < 5; x++) {

进入：

for(int x = 0; x < 4; x++) {

当x=4时，代码比较name[4]和name[5]，但是name[5]越界（唯一有效的元素是name[0].. .name[4]).

Answer 3

在您的交换周期中，此代码段：

for(int x = 0; x < 5; x++)

在最后一次迭代中，您将 name[4+1] 的值复制到 name[4] 就是说您复制了 5 元素数组的第 6 个元素的值，这是 越界访问 是undefined behavior.

使用

for(int x = 0; x < 4; x++)

这样最后一个循环将复制 name[3+1] 到 name[3]，第 5 个元素到第 4 个元素，是预期的行为。

Corrected code

Answer 4

首先不要像 5 一样使用幻数。使用命名常量。

数组名称初始化不正确。您正在使用字符文字来初始化字符数组类型的数据成员 pname，而没有将字符文字括在大括号中。

data name[] = {{'A', .ptotime = 4},
                ^^^
//...

在这个循环中

    for (int x = 0; x < 5; x++)
    {
        if (name[x].ptotime >= name[x + 1].ptotime)
                                    ^^^^^
        //...

存在超出数组的访问。所以程序有未定义的行为。

使用局部变量，例如在使用它们的最短范围内交换变量。

要交换数组名称的元素，不需要交换数组每个元素的每个数据成员。您可以交换整个对象。

这是一个演示程序。

#include <stdio.h>

typedef struct
{
    char pname[2];
    int ptotime;
} data;


int main( void ) 
{ 
    data name[] = 
    {
        { "A", .ptotime = 4 },
        { "B", .ptotime = 6 },
        { "C", .ptotime = 3 },
        { "D", .ptotime = 7 },
        { "E", .ptotime = 2 }
    };
    const size_t N = sizeof( name ) / sizeof( *name );

    printf("Process Name\t Process Time \n");

    for ( size_t i = 0; i < N; i++ ) 
    {
        printf( "\t%s\t\t\t\t%d\n", name[i].pname, name[i].ptotime );
    }

    putchar( '\n' );

    //Shortest job first (SJF) scheduling

    printf("\nShortest job first (SJF) scheduling \n");

    for ( int swapped = 1; swapped; )
    {
        swapped = 0;

        for ( int i = 1; i < N; i++ ) 
        {
            if ( name[i].ptotime < name[i-1].ptotime )
            {
                data tmp = name[i];
                name[i] = name[i-1];
                name[i-1] = tmp;

                swapped = 1;
            }
        }
    }

    printf("Process Name\t Process Time \n");

    for ( size_t i = 0; i < N; i++ ) 
    {
        printf( "\t%s\t\t\t\t%d\n", name[i].pname, name[i].ptotime );
    }

    return 0;
}

它的输出是

Process Name     Process Time 
    A               4
    B               6
    C               3
    D               7
    E               2


Shortest job first (SJF) scheduling 
Process Name     Process Time 
    E               2
    C               3
    A               4
    B               6
    D               7

C代码冒泡排序有时不能给出正确的输出

C code bubble sorting sometimes does not give correct output

c

sorting

struct

bubble-sort