排序时出现分段错误 [英] Segmentation Fault While Sorting
问题描述
我已经实现了快速排序.但是这段代码给了我分段错误.
I have implemented quick-sort.But this code is giving me segmentation fault.
#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;
}
}
推荐答案
读取数据
您的数据文件的结构似乎是:
Reading the data
Your data file seems to be structured as:
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的数组).尽管我已经在同一行上显示了每个测试集的数据，但是实际的数据文件可能具有按任意顺序排列的数字-一切都可能在一行上，或者每个数字在自己的一行上可能带有空白分隔它们的行，或这些格式的任意混合.
You have a total number of test cases, T. Then for each test case, you have a number of entries in the array (N1, N2, etc), each time followed by the appropriate number of values, V11 .. V1N, and a spare value which you're supposed to search for (all described using 1-based array notations; in C, you'll be using 0-based arrays). Although I've shown the data for each test set all on a single line, the actual data file could have the numbers laid out in any sequence — everything could be on one line, or each number on a line of its own possibly with blank lines separating them, or any mixture of these formats.
您显示的main()程序在读取该数据方面做得并不是特别好.它缺少所有错误检查.它使用(合法但奇怪的)*(array + i)表示法，而不是更简单地理解array[i]表示法，显然是相信它会更有效.当使用指针来提高效率时，在引用指针取消引用之前，不要一直在值上添加i.您的代码动态分配内存，但从不释放内存，这非常可怕.
The main() program you show does not do a particularly good job of reading that data. It lacks all error checking. It uses the (legal but) bizarre *(array + i) notations instead of the simpler to understand array[i] notation, apparently in the belief that it will be more efficient. When you use pointers for efficiency, you don't keep on adding i to the value before dereferencing the pointer. Your code dynamically allocates memory but never frees it, leaking horribly.
在此修订的代码中，我正在使用return 1;退出程序.它也应该显示一条错误消息，但是我有点懒.
In this revised code, I'm using return 1; to exit from the program. It should print an error message too, but I'm moderately lazy.
#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;
}
我顺便指出，无论QuickSort是否对数据进行排序，搜索循环都将起作用；它没有利用数组已排序的事实.您可以在排序之前和之后打印数据.您应该标记输出以标识要打印的内容.例如，搜索代码可能写为:
I note in passing that the search loop will work whether or not the QuickSort sorts the data; it makes no use of the fact that the array is sorted. You could print the data before the sort and after the sort. You should tag the output to identify what you're printing. For example, the search code might write:
printf("Found %d at %d\n", search, j);
您也无法确定何时找不到要搜索的值.
You also do not identify when the value being searched for is not found.
通常最好将已读取的数据打印在读取后和处理之前，以确保您的程序正在获取您期望的数据.如果程序无法处理您认为正在处理的数据，则可能导致混乱.
It is also often a good idea to print the data you read after you've read it and before you process it, just to make sure that your program is getting the data you expect it to get. It can lead to confusion if the program isn't working on the data you think it is working on.
请注意，除了它们是有效整数"之外，此代码对数组中的值没有任何假设.并且它确实检查每个输入操作.尽管看起来很乏味，但必须避免麻烦.
Note that this code does not make any assumptions about the values in the arrays beyond 'they are valid integers'. And it does check every input operation. Tedious though it may seem, it is necessary to head off trouble.
这里是或多或少地习惯使用指针的代码:
Here is code making more or less idiomatic use of pointers:
#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功能，例如在需要时声明变量，并在%td中的t限定符中指定ptrdiff_t值.也可以编写为使用VLA代替malloc().
The printing loop is simplest if written using indexing, so I didn't change it to use pointers. It could be done, but using (ptr - array) instead of j in the 'is it time to print a newline' code makes it less worthwhile. The code uses C99 features like declaring variables as they're needed and the t qualifier in %td for the ptrdiff_t value. It could be written to use a VLA instead of malloc(), too.
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)撰写的编程珍珠，尤其是专栏" 11:排序"(第11章，但这些章节最初是ACM通讯中的各列，因此称为第11列).这是解决问题时的宝贵指导.
Working Quicksort Code
Your partition algorithm was defective. It is fixed, with key changes marked. The debugging scaffolding that I used while sorting out the issues is left in place, with many of the printing operations that guided me commented out. Read Programming Pearls by Jon Bentley, especially 'Column 11: Sorting' (chapter 11, but the chapters were originally columns in the Communications of the ACM, hence the designation Column 11). It was an invaluable guide while fixing the problems.
#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().他们检查数据是否按排序顺序输出，以及保存属性，即输入中的所有值都出现在输出中(与它们在输入中出现的频率一样).排序不应该添加新数据或删除现有数据.
The code was also tested on some bigger data sets (2097 random entries, etc). Automated check functions are crucial when the data is that big — hence check_sorted() and check_consistency(). They check that the data is output in sorted order, and the conservation property, that all the values in the input appear in the output (as often as they appeared in the input). Sorting is not supposed to add new data or remove pre-existing data.
这篇关于排序时出现分段错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
