在 C 程序中搜索和排序？

Question

我正在编写一个程序，它从客户端接收一些数字，然后使用冒泡排序功能对它们进行排序，另一个功能从客户端接收一个数字，然后使用二进制搜索功能在另一个数字之间进行搜索。请告知我这个程序的问题是什么？

#include <stdio.h>

int bobsort (int);
int searchi (int);

void main ()
{

    int num, i;
    printf ("Enter Count Number \n");
    scanf ("%d", &num);
    int array[num];
    for (i = 1; i <= num; i++) {
        printf ("Enter Number %d \n", i);
        scanf ("%d", &array[i - 1]);
    }

    bobsort (num);
    searchi (num);

    getch ();

//return 0;
}

//**** function bobsort
void bobsort (int n)
{
    int c, d, swap;
    for (c = 0; c < (n - 1); c++) {
        for (d = 0; d < n - c - 1; d++) {
            if (array[d] > array[d + 1]) {      /* For decreasing order use < */
                swap = array[d];
                array[d] = array[d + 1];
                array[d + 1] = swap;
            }
        }
    }

    printf ("Sorted list in ascending order:\n");

    for (c = 0; c < n; c++)
        printf ("%d\n", array[c]);

    // return 0;
}

//**** function search
int searchi ()
{
    int c, first, last, middle, n, search;

    printf ("Enter value to find\n");
    scanf ("%d", &search);

    first = 0;
    last = n - 1;
    middle = (first + last) / 2;

    while (first <= last) {
        if (array[middle] < search)
            first = middle + 1;
        else if (array[middle] == search) {
            printf ("%d found at location %d.\n", search, middle + 1);
            break;
        } else
            last = middle - 1;

        middle = (first + last) / 2;
    }
    if (first > last)
        printf ("Not found! %d is not present in the list.\n", search);

    return 0;
}

Answer 1

问题出在冒泡排序函数上。您需要用 while 循环替换外部 for 循环，并且当您进行交换时，您需要设置一个标志来指示交换发生了。此外，您的代码在 main 函数内部定义数组而不是全局变量，因此您还需要将指针传递给数组，因为数组在 bobsort 所在的范围之外（换句话说，bobsort 不能'看不到数组）。更正以下代码：

//*********************************function bobsort
void bobsort(int n, int *array)
{
 int   d, swap, flag;  

  flag = 1;
  while (flag != 0)
  {
    flag = 0;
    for (d = 0; d < n - 1; d++)
    {
      if (array[d] > array[d+1]) /* For decreasing order use < */
      {
        swap       = array[d];
        array[d]   = array[d+1];
        array[d+1] = swap;
        flag = 1;
      }
    }
  }

在您的主函数中，将调用更改为：

bobsort(num, &array[0]);

这样，排序函数就可以访问数组并知道它的大小。这样做，当没有更多交换并且列表已排序时，您退出排序例程。附带说明一下，就排序算法而言，冒泡排序非常缓慢且效率低下。梳状排序是更好的例程，并且稍微复杂一些。梳状排序例程的伪代码示例如下所示 (from wikipedia):

function combsort(array input)
    gap := input.size //initialize gap size
    shrink := 1.3 //set the gap shrink factor

    loop until gap = 1 and swapped = false
        //update the gap value for a next comb. Below is an example
        gap := int(gap / shrink)
        if gap < 1
          //minimum gap is 1
          gap := 1
        end if

        i := 0
        swapped := false //see bubblesort for an explanation

        //a single "comb" over the input list
        loop until i + gap > input.size //see shellsort for similar idea
            if input[i] > input[i+gap]
                swap(input[i], input[i+gap])
                swapped := true // Flag a swap has occurred, so the
                                // list is not guaranteed sorted
            end if
            i := i + 1
        end loop

    end loop
end function

我个人使用这个程序进行排序，效果很好。至于你的二分查找功能，我看不出有什么明显的问题。

编辑：我刚刚看到您的搜索功能也缺少参数列表中的数组。就像我对冒泡排序函数所做的那样添加它，并使用 & 运算符以相同的方式调用它。您还使用 n 未初始化。您还需要将数组的大小传递给搜索函数。我重写了函数如下所示：

//**** function search
int searchi (int n, int *array)
{
    int c, first, last, middle, search;

    printf ("Enter value to find\n");
    scanf ("%d", &search);

    first = 0;
    last = n - 1;
    middle = (first + last) / 2;

    while (first <= last) {
        if (array[middle] < search)
            first = middle + 1;
        else if (array[middle] == search) {
            printf ("%d found at location %d.\n", search, middle + 1);
            break;
        } else
            last = middle - 1;

        middle = (first + last) / 2;
    }
    if (first > last)
        printf ("Not found! %d is not present in the list.\n", search);

    return 0;
}

然后你用下面的代码调用：

searchi(num, &array[0]);

这应该能让它正常工作。作为旁注，当您遇到编译器错误时，请注意它告诉您的内容并尝试更正它们。我不知道您使用的是什么编译器，但 clang 比 gcc 更能指出错误并解释问题所在。有一次使用 gcc，我遇到了一些不是很具体的奇怪错误。 3 小时后，我发现问题是与隐藏在系统中的一些晦涩、遥远的头文件中的定义冲突，该头文件是从 5 级以下包含的。

Answer 2

你有几个编译错误，下面我用注释重写了你的代码，以便它可以编译。实际功能似乎工作得很好

最重要的变化是将 array 传递给两个函数。它作为 int* 传递，以便函数可以在 main

的上下文中修改 array

#include <stdio.h>

// Neither one of these need to return a value, both are now void
// Both need to have array passed, added int*
void bobsort(int, int*);
void searchi(int, int*);

int main() {
    int num, i;

    printf("Enter Count Number\n");
    scanf("%d", &num);

    int array[num];
    for (i = 1; i <= num; i++) {
        printf("Enter Number %d\n", i);
        scanf("%d", &array[i-1]);
    }

    // Pass array to both functions
    bobsort(num, array);
    searchi(num, array);

    // Don't know what this was supposed to be, commented out
    //getch();

    return 0;
}

// Receives array from main
void bobsort(int num, int* array) {
    int c, d, swap;
    for (c = 0; c < num-1; c++) {
        for (d = 0; d < num-c-1; d++) {
            if (array[d] > array[d+1]) {
                swap = array[d];
                array[d] = array[d+1];
                array[d+1] = swap;
            }
        }
    }

    printf("Sorted list in ascending order:\n");
    for (c = 0 ; c < num; c++)
        printf("%d\n", array[c]);
}

// Receives array from main
void searchi(int num, int* array) {
    int c, first, last, middle, search;

    printf("Enter value to find\n");
    scanf("%d", &search);

    first = 0;
    last = num-1;
    middle = (first+last)/2;

    while (first <= last) {
        if (array[middle] < search)
            first = middle+1;
        else if (array[middle] == search) {
            printf("%d found at location %d\n", search, middle+1);
            break;
        }
        else
            last = middle-1;

        middle = (first+last)/2;
    }
    if (first > last)
        printf("Not found! %d is not present in the list\n", search);
}

Answer 3

这需要一段时间。让我们从基础开始，首先 main 是一个 int 类型（不管某些编译器让你逃避什么）并且它 returns 是一个 0 或更大的整数值（没有负值返回到 shell）：

int main (void)
 ...
return 0;

接下来，总是初始化你的变量。尝试读取未初始化的值是 未定义的行为（不好）。遍历数组元素时，循环从“0”开始（调整后的元素不是“1”）：

    for (i = 0; i < num; i++) {
        printf (" enter array[%d] ", i);
        scanf ("%d", &array[i]);
    }

您对函数定义和声明有何想法？您不能将函数原型定义为：

int searchi (int);

然后将您的函数声明为：

void searchi ();

这是绝对基本的 (apples != apples) 内务处理。除非你 将数组 和 元素数量 作为参数传递给你的参数，否则你将如何访问数组元素并知道有多少元素职能。即：

void bobsort (int *array, int n)
void searchi (int *array, int n)

如果您希望其他任何东西都能正常工作，就必须在代码中投入精力并修复简单的问题。

接下来，您的 bobsort 代码索引不正确，您必须使用：

    for (c = 0; c < n; c++) {
        for (d = 0; d < n - 1; d++) {
            /* For decreasing order use < */
            if (array[d] > array[d + 1]) {
                swap = array[d + 1];
                array[d + 1] = array[d];
                array[d] = swap;
            }
        }
    }

我不记得我对 searchi 做了什么，除了声明之外，它非常接近。解决上述所有问题会导致如下结果：

#include <stdio.h>

void bobsort (int*, int);
void searchi (int*, int);

int main (void)
{
    int num = 0, i = 0;
    int array[num];

    printf ("\n no. of array elements: ");
    scanf ("%d", &num);

    for (i = 0; i < num; i++) {
        printf (" enter array[%d] ", i);
        scanf ("%d", &array[i]);
    }

    bobsort (array, num);
    searchi (array, num);
    // getch ();

    return 0;
}

/* function bobsort */
void bobsort (int *array, int n)
{
    int c, d, swap;
    c = d = swap = 0;

    for (c = 0; c < n; c++) {
        for (d = 0; d < n - 1; d++) {
            /* For decreasing order use < */
            if (array[d] > array[d + 1]) {
                swap = array[d + 1];
                array[d + 1] = array[d];
                array[d] = swap;
            }
        }
    }

    printf ("\nSorted list in ascending order:\n\n");

    for (c = 0; c < n; c++)
        printf ("%d\n", array[c]);
}

/* function search */
void searchi (int *array, int n)
{
    int first, last, middle, search;
    first = last = middle = search = 0;

    printf (" enter value to find: ");
    scanf ("%d", &search);

    first = 0;
    last = n - 1;
    middle = (first + last) / 2;

    while (first <= last) {
        if (array[middle] < search)
            first = middle + 1;
        else if (array[middle] == search) {
            printf ("%d found at location %d.\n", search, middle + 1);
            break;
        } else
            last = middle - 1;

        middle = (first + last) / 2;
    }
    if (first > last)
        printf ("Not found! %d is not present in the list.\n", search);
}

Use/Output

$ ./bin/array_bsort_srch

 no. of array elements: 5
 enter array[0] 9
 enter array[1] 3
 enter array[2] 5
 enter array[3] 8
 enter array[4] 4

Sorted list in ascending order:

3
4
5
8
9
 enter value to find: 8
8 found at location 4.

如果您在启用 warnings 的情况下进行编译，然后阅读编译器告诉您的内容，那么所有这些问题对您来说应该是显而易见的。无论何时构建任何东西，请至少启用警告：

gcc -Wall -Wextra -o progname progname.c

（只需用您的编译器 exe 名称替换 gcc）如果您正在使用一些 IDE，那么每个 IDE 都会提供一个配置来指定您的编译器选项，确保您启用警告。它们可以帮助您识别可能导致操作不可靠的代码问题。除非您花时间修复警告，否则运行风险由您自行承担。

真的，经过多年的开发，编译器已经确定了哪里存在问题以及问题是什么。它甚至可以为您提供发现错误或警告的确切行号。您只需花时间阅读输出并修复错误和警告。如果您不确定警告或错误的含义，只需将其输入搜索引擎（即 "C copy/paste warning or error"），您将获得大量信息，了解什么是错的，应该做什么寻找，以及如何着手修复它。祝你好运。

在 C 程序中搜索和排序？

search and sorting in c program?

c

arrays

sorting

search

bubble-sort