c - 在 C 中实现快速排序的分段错误
问题描述
我正在尝试执行Reema Thareja的Data Structures Using C一书中提到的快速排序代码。
问题是我无法将排序后的数组作为输出。相反,当我在数组中添加元素时,输出屏幕消失了,再次运行代码时,我得到以下信息:
我正在使用 Turbo C++ 版本:3.2 编译器
#include <stdio.h>
#include <conio.h>
void quicksort(int arr[],int l,int r);
void main()
{
int arr[10],l,r,i,n;
printf("Enter Array size: ");
scanf("%d",&n);
printf("Enter Elements: ");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
quicksort(arr,0,n-1);
printf("The Sorted Array is: ");
for (i = 0; i < n; i++)
{
printf("%d",arr[i]);
}
getch();
}
int partition(int arr[],int l,int r)
{
int left,right,temp,loc,flag;
loc=left=l;
right=r;
flag=0;
while(flag!=1)
{
while((arr[loc]<=arr[right]) && loc!=right)
{
right--;
}
if(loc==right)
{
flag=1;
}
else if(arr[loc]>arr[right])
{
temp=arr[loc];
arr[loc]=arr[right];
arr[right]=temp;
loc=right;
}
if(flag!=1)
{
while((arr[loc]>=arr[left])&& (loc!=left))
{
left++;
}
if(loc==left)
{
flag=1;
}
else if(arr[loc]<arr[left])
{
temp=arr[loc];
arr[loc]=arr[left];
arr[left]=temp;
loc=left;
}
}
}
return loc;
}
void quicksort(int arr[],int l,int r)
{
int loc;
if(l!=r)
{
loc=partition(arr,l,r);
quicksort(arr,l,loc-1);
quicksort(arr,loc+1,r);
}
}
解决方案
考虑这个函数:
void quicksort(int arr[], int l, int r)
{
int loc;
if(l!=r)
{
loc=partition(arr,l,r);
quicksort(arr,l,loc-1);
quicksort(arr,loc+1,r);
}
}
在这里,我们的基本情况是l==r
。但是如果我们添加一个打印语句(和一些间距)
void quicksort(int arr[], int l, int r)
{
if (l != r)
{
printf("left: %d, right: %d\n", l, r);
fflush(stdout);
//^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
int loc = partition(arr, l, r);
quicksort(arr, l, loc - 1);
quicksort(arr, loc + 1, r);
}
}
并调用它
int arr[] = {4, 8, 1, 4, 5, 1, 8, 5, 7};
int arr_len = 9;
quicksort(arr, 0, arr_len - 1);
我们得到以下输出:
left: 0, right: 8
left: 0, right: 1
left: 0, right: -1
exited, segmentation fault
哎呀:left
是 0 和right
-1,我们调用partition(arr, 0, -1);
了它立即使用语句arr[right]
=>进行越界内存访问arr[-1]
。
if (l < r)
可能是这里的意图:
void quicksort(int arr[], int l, int r)
{
if (l < r)
{
int loc = partition(arr, l, r);
quicksort(arr, l, loc - 1);
quicksort(arr, loc + 1, r);
}
}
这使我们能够正确地建立递归的基本情况。
除了这个错误,我建议在运算符之间使用空格,选择有意义的名称并避免不必要的变量。这方面的一个例子是partition
函数的开头。如所写,它是:
int partition(int arr[],int l,int r)
{
int left,right,temp,loc,flag;
loc=left=l;
right=r;
flag=0;
// ...
但是l
andr
只是被重新分配给left
然后right
在函数的其余部分中未使用。像这样写:
int partition(int arr[], int left, int right)
{
int temp;
int loc = left;
int flag = 0;
// ...
更清楚了,但即使在这里,我们也应该将tmp
(用于交换)移到一个单独的函数中,或者至少将它的范围限制在用于避免陈旧值错误的块中。我们应该#include <stdbool.h>
因为这int flag
实际上是(或使用早期返回来完全消除变量)并改进loc
变量名称(它实际上是我们对整数进行分区的枢轴):
int partition(int arr[], int left, int right)
{
int pivot = left;
bool flag = false; // or remove this completely in favor of `return`
// ...
这干净多了。
此外,void main
应该int main
使用明确的return 0
. 我建议使用现代编译器和开发环境并打开所有警告:
gcc quicksort.c -Wall -Wextra -Werror -O2 -std=c99 -pedantic
这揭示了 中未使用的变量main
,除其他外,通常会减少痛点。
另外,我建议阅读如何调试小程序,这将为您提供必要的工具(概念和软件),以了解程序以定位错误。
推荐阅读
- api - 如何在被 Android 应用调用时保护 API
- php - 在 laravel 中将嵌套的 json 保存到数据库中
- unity3d - 用 StateMachineBehaviour 改变 bool
- html - 使用无线电和表单的 Ajax 请求错误 419
- vue.js - Vue Apollo Graphql 从 wordpress 获取元标记
- spring - 有没有办法在 Spring Cloud Messaging 中配置多个 SQS 侦听器?
- javascript - 如何对firestore进行动态“where”查询
- r - 负方向移动平均线(R预测中的ma)
- c# - 语法错误“,”预期但我找不到它(C# Unity)
- c# - Unity3D中的AR相机黑屏