0

我已经实现了快速排序。但是这段代码给了我分段错误。

#include<stdio.h>
#include<stdlib.h>
void Quick_Sort(int *a,int p,int r);
int partition(int *a,int p,int r);
int main(){
    int testcase,num,search;
    int i,j,*array;
    scanf("%d",&testcase);
    for(i=0;i<testcase;i++){
        scanf("%d",&num);
        array=malloc(sizeof(int)*num);
        for(j=0;j<num;j++){
            scanf("%d",(array+j));
        }
        Quick_Sort(array,0,num-1);
        scanf("%d",&search);
        /*for(j=0;j<num;j++){
            if(search==*(array+j)){
                printf("%d\n",j+1 );
                break;
            }

        }*/
    }
    for(i=0;*(array+i)!='\0';++i){
        printf("%d ",*(array+i));
    }
}
void Quick_Sort(int *a,int p,int r){
    int q;
    if(p<r){
        q=partition(a,p,r);
        Quick_Sort(a,p,q);
        Quick_Sort(a,q+1,r);
    }
}
int partition(int *a,int p,int r){
    int i,j,x,temp;
    i=p-1;
    j=r+1;
    x=*(a+p);
    while(1){
        do{
        j=j-1;
    }
    while(x<=(*(a+j)));

    do{
        i=i+1;
    }
    while(x>=(*(a+i)));

    if(i<j){
        temp=*(a+i);
        *(a+i)=*(a+j);
        *(a+j)=temp;
    }else{
        return j;
    }
}
4

2 回答 2

2

读取数据

您的数据文件的结构似乎是：

T
N1 V11 V12 V13 ... V1N S1
N2 V21 V22 V23 ... V2N S2
...

你有一个测试用例的总数，T。然后对于每个测试用例，你在数组中有许多条目（N1、N2 等），每次后面跟着适当数量的值，V 1 1 .. V 1 N，以及您应该搜索的备用值（所有描述都使用基于 1 的数组表示法；在 C 中，您将使用基于 0 的数组）。虽然我已经在一行中显示了每个测试集的数据，但实际的数据文件可以以任何顺序排列数字——所有内容都可以在一行上，或者每个数字在自己的一行上，可能带有空白分隔它们的行，或这些格式的任何混合。

您显示的main()程序在读取该数据方面做得不是特别好。它缺乏所有的错误检查。它使用（合法但）奇怪的*(array + i)符号而不是更容易理解的array[i]符号，显然是相信它会更有效。当您使用指针来提高效率时，您不会i在取消引用指针之前继续添加值。您的代码动态分配内存，但从不释放它，严重泄漏。

使用下标符号读取数据

在这个修改后的代码中，我return 1;用来退出程序。它也应该打印一条错误消息，但我有点懒惰。

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

int main(void)
{
    int testcase, num, search;
    int i, j, *array;
    if (scanf("%d", &testcase) != 1)
        return 1;

    for (i = 0; i < testcase; i++)
    {
        if (scanf("%d", &num) != 1)
            return 1;
        array = malloc(sizeof(int)*num);
        if (array == 0)
            return 1;
        for (j = 0; j < num; j++)
        {
            if (scanf("%d", &array[j]) != 1)
                return 1;
        }
        //Quick_Sort(array, 0, num-1);
        if (scanf("%d", &search) != 1)
            return 1;
        for (j = 0; j < num; j++)
        {
            if (search == array[j])
            {
                printf("%d\n", j+1);
                break;
            }
        }
        // Print the array - best encapsulated in a small function
        for (j = 0; j < num; j++)
        {
            printf(" %d", array[j]);
            if (j % 10 == 9)
                putchar('\n');
        }
        if (j % 10 != 0)
            putchar('\n');
        // Prevent memory leaks
        free(array);
    }
    return 0;
}

我顺便指出，无论快速排序是否对数据进行排序，搜索循环都将起作用。它没有利用数组已排序的事实。您可以在排序之前和之后打印数据。您应该标记输出以识别您正在打印的内容。例如，搜索代码可能会这样写：

printf("Found %d at %d\n", search, j);

您也无法确定何时未找到正在搜索的值。

在读取数据之后和处理数据之前打印数据通常也是一个好主意，以确保您的程序正在获取您期望的数据。如果程序未处理您认为正在处理的数据，则可能会导致混乱。

请注意，除了“它们是有效整数”之外，此代码不会对数组中的值做出任何假设。它确实检查每个输入操作。虽然看起来很乏味，但有必要避免麻烦。

使用指针表示法读取数据

以下是或多或少惯用指针的代码：

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

int main(void)
{
    int testcase;
    if (scanf("%d", &testcase) != 1)
        return 1;

    for (int i = 0; i < testcase; i++)
    {
        int num;
        if (scanf("%d", &num) != 1)
            return 1;
        int *array = malloc(sizeof(int)*num);
        if (array == 0)
            return 1;
        int *end = array + num;
        int *ptr;
        for (ptr = array; ptr < end; ptr++) 
        {
            if (scanf("%d", ptr) != 1)
                return 1;
        }

        //Quick_Sort(array, 0, num-1);

        int search;
        if (scanf("%d", &search) != 1)
            return 1;
        for (ptr = array; ptr < end; ptr++) 
        {
            if (search == *ptr)
            {
                break;
            }
        }
        if (ptr < end)
            printf("Found %d at %td\n", search, ptr - array + 1);
        else
            printf("Missing %d\n", search);

        // Print the array - best encapsulated in a small function
        printf("Array (%d):", num);
        int j;
        for (j = 0; j < num; j++)
        {
            printf(" %d", array[j]);
            if (j % 10 == 9)
                putchar('\n');
        }
        if (j % 10 != 0)
            putchar('\n');

        // Prevent memory leaks
        free(array);
    }
    return 0;
}

如果使用索引编写打印循环是最简单的，所以我没有将其更改为使用指针。可以这样做，但是使用(ptr - array)而不是j在“是时候打印换行符”代码中使用它会变得不那么值得。该代码使用 C99 功能，例如在需要时声明变量以及值的t限定符。它也可以写成使用 VLA 而不是.%tdptrdiff_tmalloc()

样本输入数据

3
2 1 2 1
3 3 2 0 1
4 5 4 3 2 4

样本输出

Found 1 at 1
Array (2): 1 2
Missing 1
Array (3): 3 2 0
Found 4 at 2
Array (4): 5 4 3 2

工作快速排序代码

您的分区算法有缺陷。它是固定的，并标记了关键更改。我在整理问题时使用的调试脚手架留在原地，许多指导我的打印操作被注释掉了。阅读Jon Bentley 的Programming Pearls，尤其是“第 11 列：排序”（第 11 章，但这些章节最初是 ACM 通讯中的列，因此称为第 11 列）。这是解决问题时的宝贵指南。

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

void Quick_Sort(int *a, int p, int r);
static int  partition(int *a, int p, int r);

static void dump_partition(char const *tag, int const *data, int lo, int hi);

/* Debugging functions */
static void check_sorted(int const *data, int lo, int hi);
static int *copy_partition(int const *data, int lo, int hi);
static void check_consistency(int const *a1, int const *a2, int lo, int hi);

int main(void)
{
    int testcase, num, search;
    int i, j, *array;
    if (scanf("%d", &testcase) != 1)
        return 1;

    for (i = 0; i < testcase; i++)
    {
        if (scanf("%d", &num) != 1)
            return 1;
        array = malloc(sizeof(int)*num);
        if (array == 0)
            return 1;
        for (j = 0; j < num; j++)
        {
            if (scanf("%d", &array[j]) != 1)
                return 1;
        }

        printf("\nData set %d:\n", i);
        int *copy = copy_partition(array, 0, num-1);
        dump_partition("Before:", array, 0, num-1);
        //dump_partition("Copy", copy, 0, num-1);
        Quick_Sort(array, 0, num-1);
        dump_partition("After: ", array, 0, num-1);
        check_sorted(array, 0, num-1);
        check_consistency(array, copy, 0, num-1);
        free(copy);

        if (scanf("%d", &search) != 1)
            return 1;
        for (j = 0; j < num; j++)
        {
            if (search == array[j])
                break;
        }
        if (j < num && search == array[j])
            printf("Found %d at %d\n", search, j+1);
        else
            printf("Missing %d\n", search);

        // Prevent memory leaks
        free(array);
    }
    return 0;
}

/* Although we're interested in data[lo]..data[hi], the copy must have data[0]..data[lo-1] too */
static int *copy_partition(int const *data, int lo, int hi)
{
    assert(lo <= hi);
    size_t nbytes = (hi + 1) * sizeof(int);
    int *space = (int *)malloc(nbytes);
    if (space == 0)
    {
        fputs("Out of memory\n", stderr);
        exit(1);
    }
    memmove(space, data, nbytes);
    return(space);
}

/* Check that the two arrays contain the same sets of data */
/* Each value in a1 must be present in a2 and vice versa */
static void check_consistency(int const *a1, int const *a2, int lo, int hi)
{
    int *a3 = copy_partition(a1, lo, hi);
    int  a3_lo = lo;
    int  a3_hi = hi;
    //printf("-->> check_consistency:\n");
    //dump_partition("a1", a1, lo, hi);
    //dump_partition("a2", a2, lo, hi);
    //dump_partition("a3", a3, lo, hi);
    for (int i = lo; i <= hi; i++)
    {
        int found = 0;
        for (int j = a3_lo; j <= a3_hi; j++)
        {
            if (a2[i] == a3[j])
            {
                /* Found a match for a2[i] at a3[j] */
                /* Move a3[j] to end of array and ignore it from here on */
                //printf("Found a2[%d] = %d at a3[%d] = %d\n", i, a2[i], j, a3[j]);
                int t = a3[a3_hi];
                a3[a3_hi] = a3[j];
                a3[j] = t;
                a3_hi--;
                //dump_partition("a3-free", a3, a3_lo, a3_hi);
                //dump_partition("a3-used", a3, a3_hi+1, hi);
                found = 1;
                break;
            }
        }
        if (!found)
        {
            printf("No value %d for a2[%d] in a1\n", a2[i], i);
            dump_partition("a2", a2, lo, hi);
            dump_partition("a1-free", a3, a3_lo, a3_hi);
            dump_partition("a1-used", a3, a3_hi+1, hi);
        }
    }
    free(a3);
    //printf("<<-- check_consistency\n");
}

static void dump_partition(char const *tag, int const *data, int lo, int hi)
{
    printf("%s [%d..%d]%s", tag, lo, hi, (hi - lo) > 10 ? "\n" : "");
    int i;
    for (i = lo; i <= hi; i++)
    {
        printf(" %2d", data[i]);
        if ((i - lo) % 10 == 9)
            putchar('\n');
    }
    if ((i - lo) % 10 != 0 || i == lo)
        putchar('\n');
}

static void check_sorted(int const *data, int lo, int hi)
{
    //printf("-->> check_sorted:\n");
    for (int i = lo; i < hi; i++)
    {
        if (data[i] > data[i+1])
            printf("Out of order: a[%d] = %d bigger than a[%d] = %d\n", i, data[i], i+1, data[i+1]);
    }
    //printf("<<-- check_sorted\n");
}

void Quick_Sort(int *a, int p, int r)
{
    if (p < r)
    {
        int q = partition(a, p, r);
        //dump_partition("Lo Range", a, p, q-1);
        //printf("Pivot: a[%d] = %d\n", q, a[q]);
        //dump_partition("Hi Range", a, q+1, r);
        Quick_Sort(a, p, q-1);          // JL: Optimization
        Quick_Sort(a, q+1, r);
    }
}

static int partition(int *a, int p, int r)
{
    assert(p <= r);
    if (p == r)                         // JL: Key change
        return p;                       // JL: Key change
    int i = p;                          // JL: Key change
    int j = r + 1;
    int x = a[p];
    //printf("-->> partition: lo = %d, hi = %d, pivot = %d\n", p, r, x);
    while (1)
    {
        do
        {
            j--;
            //printf("---- partition 1: a[%d] = %d\n", j, a[j]);
        }   while (x < a[j]);           // JL: Key change

        do
        {
            i++;
            //printf("---- partition 2: a[%d] = %d\n", i, a[i]);
        }   while (i <= r && x > a[i]); // JL: Key change

        if (i <= j)                     // JL: Key change
        {
            //printf("---- partition: swap a[%d] = %d with a[%d] = %d\n", i, a[i], j, a[j]);
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        else
        {
            // This swap step is crucial.
            int temp = a[p];            // JL: Key change
            a[p] = a[j];                // JL: Key change
            a[j] = temp;                // JL: Key change
            //dump_partition("a-lo", a, p, j-1);
            //printf("a-pivot[%d] = %d\n", j, a[j]);
            //dump_partition("a-hi", a, j+1, r);
            //printf("<<-- partition: return j = %d; a[%d] = %d; (i = %d; a[%d] = %d)\n", j, j, a[j], i, i, a[i]);
            return j;
        }
    }
}

扩展样本输入

10

2 1 2 1
3 3 2 0 1
4 5 4 3 2 4
4 3 1 9 3 8
5 3 4 1 9 3 8
9 3 6 4 9 5 1 9 3 3 8
10 3 6 4 9 6 5 1 9 3 3 8

16
3 6 4 9 6 5 1 9 3 3
8 2 1 7 3 5
3

26
3 6 4 9 6 5 1 9 3 3
2 7 8 2 0 8 4 4 7 5
8 2 1 7 3 5
7

96
3 6 4 9 6 5 1 9 3 3
4 0 5 0 7 5 6 3 6 0
1 2 0 7 3 1 7 6 2 3
0 4 6 6 9 8 9 5 3 4
1 9 2 9 2 7 5 9 8 9
4 7 5 8 7 8 5 8 2 7
5 8 2 9 8 3 7 6 5 3
9 1 2 0 3 4 6 5 1 0
2 7 8 2 0 8 4 4 7 5
8 2 1 7 3 5
6

扩展样本输出

Data set 0:
Before: [0..1]  1  2
After:  [0..1]  1  2
Found 1 at 1

Data set 1:
Before: [0..2]  3  2  0
After:  [0..2]  0  2  3
Missing 1

Data set 2:
Before: [0..3]  5  4  3  2
After:  [0..3]  2  3  4  5
Found 4 at 3

Data set 3:
Before: [0..3]  3  1  9  3
After:  [0..3]  1  3  3  9
Missing 8

Data set 4:
Before: [0..4]  3  4  1  9  3
After:  [0..4]  1  3  3  4  9
Missing 8

Data set 5:
Before: [0..8]  3  6  4  9  5  1  9  3  3
After:  [0..8]  1  3  3  3  4  5  6  9  9
Missing 8

Data set 6:
Before: [0..9]  3  6  4  9  6  5  1  9  3  3
After:  [0..9]  1  3  3  3  4  5  6  6  9  9
Missing 8

Data set 7:
Before: [0..15]
  3  6  4  9  6  5  1  9  3  3
  8  2  1  7  3  5
After:  [0..15]
  1  1  2  3  3  3  3  4  5  5
  6  6  7  8  9  9
Found 3 at 4

Data set 8:
Before: [0..25]
  3  6  4  9  6  5  1  9  3  3
  2  7  8  2  0  8  4  4  7  5
  8  2  1  7  3  5
After:  [0..25]
  0  1  1  2  2  2  3  3  3  3
  4  4  4  5  5  5  6  6  7  7
  7  8  8  8  9  9
Found 7 at 19

Data set 9:
Before: [0..95]
  3  6  4  9  6  5  1  9  3  3
  4  0  5  0  7  5  6  3  6  0
  1  2  0  7  3  1  7  6  2  3
  0  4  6  6  9  8  9  5  3  4
  1  9  2  9  2  7  5  9  8  9
  4  7  5  8  7  8  5  8  2  7
  5  8  2  9  8  3  7  6  5  3
  9  1  2  0  3  4  6  5  1  0
  2  7  8  2  0  8  4  4  7  5
  8  2  1  7  3  5
After:  [0..95]
  0  0  0  0  0  0  0  0  1  1
  1  1  1  1  1  2  2  2  2  2
  2  2  2  2  2  3  3  3  3  3
  3  3  3  3  3  3  4  4  4  4
  4  4  4  4  5  5  5  5  5  5
  5  5  5  5  5  5  6  6  6  6
  6  6  6  6  6  7  7  7  7  7
  7  7  7  7  7  7  8  8  8  8
  8  8  8  8  8  8  9  9  9  9
  9  9  9  9  9  9
Found 6 at 57

该代码还在一些更大的数据集（2097 个随机条目等）上进行了测试。当数据很大时，自动检查功能至关重要——因此check_sorted()和check_consistency(). 他们检查数据是否按排序顺序输出，以及守恒属性，即输入中的所有值是否出现在输出中（与它们出现在输入中的频率一样）。排序不应该添加新数据或删除预先存在的数据。

于 2013-11-01T15:20:48.477 回答
0

正如评论中所指出的*(array + i) != '\0'，您的打印循环的循环结束测试是一个错误。 array保存普通整数，并且 C 也认为'\0'是整数 0，因为它认为所有字符文字值都是整数，并且比较是合法的，但是因为这是一个（希望）排序的整数数组，可能有任何值（包括负值和 0）可能是某些测试数据中有多个 0，或者在这种情况下更可能是测试数据中没有 0。如果您弄清楚此代码在这些情况下会做什么，那么您应该了解错误。

于 2013-11-01T14:20:58.430 回答