Bubblesort 忽略最后一个元素

Question

我正在尝试根据指针指向的字符串对指针数组进行排序。我的 bubblesort 实现似乎忽略了我传递给它的最后一个元素。

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

void swap(char **a,char **b);
int main(void);

int main(void)
{
    char *ptr[1000]; //build an array of 1000 pointers
    short ptrpos = 0; //start at 0th pointer
    char input[500]; 
    printf("Enter strings(names), seperate by newline\nEOF(Ctrl-D) finishes the input process.\n");
    while(fgets(input,sizeof(input),stdin))
    {
        ptr[ptrpos] = malloc(strlen(input)+1); 
        strcpy(ptr[ptrpos],input); 
        ptrpos++; 
    }
    short length = ptrpos-1;

//BEGIN BUBBLE SORT
    for(short h = 1; h < length; h++)
    {
        for(short i = 0;i < length - h; i++)
        {
            if(strcmp(ptr[i],ptr[i+1]) > 0) 
                swap(&ptr[i],&ptr[i+1]); 
        }
    }
//END BUBBLE SORT
    printf("\n----- Sorted List -----\n");
    for(ptrpos = 0;ptrpos <= length;ptrpos++)
        printf("%s",ptr[ptrpos]);

    return 0;
}
void swap(char **a,char **b) //swaps adresses of passed pointers
{
    char *temp = *a;
    *a = *b;
    *b = temp;
}

输出如下所示：

Enter strings(names), seperate by newline
EOF(Ctrl-D) finishes the input process.
Echo
Charlie
Foxtrot
Alpha
Golf
Bravo
Delta

----- Sorted List -----
Alpha
Bravo
Charlie
Echo
Foxtrot
Golf
Delta

为什么最后一个字符串被忽略了？我是否漏掉了一些明显的东西？

Answer 1

数字只是例子。

ptrpos 从 0 开始计数，这意味着如果你有 6 个元素，ptrpos 在你的 while 循环的最后一次迭代之后是 6。当您使用

计算长度时

short length = ptrpos-1;

你得到 length = 5.

您的 for-循环以 counter < length 终止，这意味着它们只计数到 4，这会产生 5 个元素而不是 6。

由于数组的实际长度为6，建议您将上述行改为

short length = ptrpos;

现在 length 等于数组中的元素数。

Answer 2

这是导致问题的原因：

short length = ptrpos-1;

//BEGIN BUBBLE SORT
for(short h = 1; h < length; h++)

将循环更改为

for(short h = 1; h <= length; h++)

或改变 for(ptrpos = 0;ptrpos <= length;ptrpos++) 至
for(ptrpos = 0;ptrpos < length;ptrpos++) 并且，short length = ptrpos;

截至目前，用于排序的循环执行时间比所需时间少了一次。但是，打印的循环执行了预期的次数 for(ptrpos = 0;ptrpos <= length;ptrpos++)。

我会做的更多改进：

检查malloc是否返回NULL，然后再进行访问。

Answer 3

这是一个工作版本，我评论了我的修改

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

void swap(char **a,char **b);
int main(void);

int main(void)
{
    char *ptr[1000]; //build an array of 1000 pointers
    short ptrpos = 0; //start at 0th pointer
    char input[500]; 
    printf("Enter strings(names), seperate by newline\nEOF(Ctrl-D) finishes the input process.\n");
    while(fgets(input,sizeof(input),stdin))
    {
        ptr[ptrpos] = malloc(strlen(input)+1); 
        strcpy(ptr[ptrpos],input); 
        ptrpos++; 
    }
    short length = ptrpos; //removed -1

//BEGIN BUBBLE SORT
    for(short h = 1; h < length; h++)
    {
        for(short i = 0;i < length - h; i++)
        {
            if(strcmp(ptr[i],ptr[i+1]) > 0)
                swap(&ptr[i],&ptr[i+1]); 
        }
    }
//END BUBBLE SORT
    printf("\n----- Sorted List -----\n");
    for(ptrpos = 0;ptrpos < length;ptrpos++) // transofrmed <= in <
        printf("%s",ptr[ptrpos]);

    return 0;
}
void swap(char **a,char **b) //swaps adresses of passed pointers
{
    char *temp = *a;
    *a = *b;
    *b = temp;
}

Bubblesort 忽略最后一个元素

Bubblesort ignores last element

c

sorting

bubble-sort