c - 是什么导致读取访问冲突/溢出？

问题描述

我正在尝试编写一个程序，该程序通过选择排序对大小为 N 的数组进行排序，然后对该数组中的随机数进行二进制搜索并显示该数字所在的索引。我注意到，如果没有我的二进制搜索功能，当 N 大于 1e5 时，我开始出现堆栈溢出，当我尝试运行二进制搜索时，我遇到了错误“读取访问冲突”。我将非常感谢任何帮助，特别是考虑到我的 N 应该是 1e6。

   #define N 10
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//function prototypes
void selectionSort(int array[], size_t length);
void swap(int* elementPtr, int* element2Ptr);
void printPass(int array[], size_t length, unsigned int pass, size_t index);
size_t binarySearch(const int b[], int searchKey, size_t low, size_t high);

unsigned long long int counter = 0;
unsigned long long int counter2 = 0;
long long unsigned int counter3 = 0;


int main(void) {
    int array[N];
    srand(time(NULL));
    for (size_t i = 0; i < N; i++) {
        array[i] = rand() % 90 + 10; // give each element a value
    }

    /*
    puts("Unsorted array:");

    for (size_t i = 0; i < N; i++) { //print the array
        printf("%d  ", array[i]);
    }
    puts("{\n");
    */

    selectionSort(array, N);

    /*
    puts("Sorted array:");

    for (size_t i = 0; i < N; i++) { //print the array
        printf("%d  ", array[i]);
    }
    */

    printf("\nTotal amount of comparisons: %d\n", counter);
    printf("Total amount of swaps: %d", counter2);

    int value = rand() % N + 1;
    int index = binarySearch(array, value, 0, N);
    printf("\nThe amount of times the value was compared was: %d\n", counter3);
    if (index != -1) {
        printf("%d was first found on index %d\n", value, index);
    }
    else printf("%d was not found on the array\n", value);

}


void selectionSort(int array[], size_t length) {
    //loop over length - 1 elements
    for (size_t i = 0; i < length - 1; i++) {
        size_t smallest = i; //first index of remaining array
        //loop to find index of smallest element
        for (size_t j = i + 1; j < length; j++) {
            counter++;
            if (array[j] < array[smallest]) {
                smallest = j;
            }
        }
        swap(array + i, array + smallest); //swap smallest element
        //printPass(array, length, i + 1, smallest); //output pass
    }
}

//function that swaps two elements in the array
void swap(int* elementPtr,int* element2Ptr)
{
    counter2++;
    int temp;
    temp = *elementPtr;
    *elementPtr = *element2Ptr;
    *element2Ptr = temp;

}

//function that prints a pass of the algorithm
void printPass(int array[], size_t length, unsigned int pass, size_t index) {
    printf("After pass %2d: ", pass);

    //output elements till selected item
    for (size_t i = 0; i < index; i++) {
        printf("%d ", array[i]);
    }
    printf("%d ", array[index]); //indicate swap

    //finish outputting array
    for (size_t i = index + 1; i < length; i++) {
        printf("%d ", array[i]);
    }
    printf("%s", "\n               "); //for alignment

    //indicate amount of array that is sorted
    for (unsigned int i = 0; i < pass; i++) {
        printf("%s", "-- ");
    }
    puts(""); //add newline
}

size_t binarySearch(const int b[], int searchKey, size_t low, size_t high) {
    counter3++;
    if (low > high) {
        return -1;
    }
    size_t middle = (low + high) / 2;

    if (searchKey == b[middle]) {
        return middle;
    }

    else if (searchKey < b[middle]) {
        return binarySearch(b, searchKey, low, middle - 1);
    }

    else {
        return binarySearch(b, searchKey, middle + 1, high);
    }
}

标签： crecursionoverflow

c - 是什么导致读取访问冲突/溢出？

问题描述

解决方案

推荐阅读