Связанный список в переполнении буфера C

Я должен сделать связанный список в C с упорядоченной функцией вставки. Списки массивов представляют собой массив отдельных связанных списков, и мне нужно сгенерировать 10000 случайных чисел, а иногда я могу сгенерировать 300 или 400 чисел, а иногда это дает сбой и дает мне исключение переполнения буфера. По какой причине я получаю это?

Я думал, что это может быть потому, что мне нужно освободить часть памяти, но мне кажется, что мне нужна вся память, которую я выделяю, ничего не осталось.

Когда возникает ошибка, стек вызовов показывает эту строку:

struct Node *newNode = (struct Node *)malloc(sizeof(*newNode));

это то, что вызывает исключение.

Он работает правильно с меньшим количеством генерируемых чисел, например, если я сделаю 100 чисел, вывод будет выглядеть следующим образом: 18a9ba87611f5676d6fa7b6229fc41e0 Конечно, это не полный вывод, но идея такова.

// Program 6.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <time.h>
#include <stdlib.h>


#define MAX 200

void orderedInsert(struct Node **, int);
void printList(struct Node **, int);


struct List{
    int size;
    struct Node *front;
};

struct Node{
    int value;
    struct Node *next;
};

void main(){

struct List lists[MAX];
int i, random;

for(i = 0; i < MAX; i++){
    lists[i].front = 0;
    lists[i].size = 0;
}
srand(time(NULL));

for(i = 0; i < 100; i++){
    random = rand() % 10000000;
    orderedInsert( &(lists[random%MAX].front), random);
    (lists[i].size)++;
}

for(i = 0; i < MAX; i++){
    printf("%d ", i);
    printList( &(lists[i].front), lists[i].size);
}


scanf_s("%d", NULL);

}


void orderedInsert(struct Node **front, int value){

struct Node *newNode = (struct Node *)malloc(sizeof(*newNode));
struct Node *temp, 
            *prev;

newNode->value = value;


if(*front == NULL){
    *front = newNode;
    newNode->next = 0;
    return;
}

if((*front)->value > newNode->value){
    newNode->next = *front;
    *front = newNode;
    return;
}
temp = (*front)->next;
prev = *front;

while(temp != NULL && temp->value < newNode->value){
    prev = temp;
    temp = temp->next;
}
newNode->next = temp;
prev->next = newNode;

}

void printList(struct Node **front, int value){

struct Node *temp;
temp = *front;

if(temp){
    printf("The list contains elements: %d", temp->value);
    temp = temp->next;

    while(temp != NULL){
        printf(", %d", temp->value);
        temp = temp->next;
    }

    }
    printf("\n");

}

Вот полный стек вызовов, если вам это нужно:

    msvcr110d.dll!_crt_debugger_hook(int _Reserved) Line 57 C
    Program 6.exe!__raise_securityfailure(_EXCEPTION_POINTERS * ExceptionPointers) Line 67  C
    Program 6.exe!__report_gsfailure() Line 235 C
    msvcr110d.dll!ValidateLocalCookies(void (unsigned int) * CookieCheckFunction, _EH4_SCOPETABLE * ScopeTable, char * FramePointer) Line 198   C
    msvcr110d.dll!_except_handler4_common(unsigned int * CookiePointer, void (unsigned int) * CookieCheckFunction, _EXCEPTION_RECORD * ExceptionRecord, _EXCEPTION_REGISTRATION_RECORD * EstablisherFrame, _CONTEXT * ContextRecord, void * DispatcherContext) Line 329 C
    Program 6.exe!_except_handler4(_EXCEPTION_RECORD * ExceptionRecord,          _EXCEPTION_REGISTRATION_RECORD * EstablisherFrame, _CONTEXT * ContextRecord, void * DispatcherContext) Line 94 C
    ntdll.dll!77e2b499()    Unknown
    [Frames below may be incorrect and/or missing, no symbols loaded for        ntdll.dll]  
    ntdll.dll!77e2b46b()    Unknown
    ntdll.dll!77e2b40e()    Unknown
    ntdll.dll!77de0133()    Unknown
    msvcr110d.dll!malloc(unsigned int nSize) Line 56    C++
>   Program 6.exe!orderedInsert(Node * * front, int value) Line 59  C
    Program 6.exe!main(...) Line 42 C
    Program 6.exe!__tmainCRTStartup() Line 536  C
    cd001c1d()  Unknown

Я получил еще одну ошибку: необработанное исключение по адресу 0x100B26B6 (msvcr110d.dll) в программе 6.exe: 0xC0000005: место чтения с нарушением прав доступа 0x0146F78F.

Стек вызовов для этого:

>   msvcr110d.dll!_nh_malloc_dbg_impl(unsigned int nSize, int nhFlag, int      nBlockUse, const char * szFileName, int nLine, int * errno_tmp) Line 239 C++
    Program 6.exe!orderedInsert(Node * * front, int value) Line 59  C
    Program 6.exe!main(...) Line 42 C
    Program 6.exe!__tmainCRTStartup() Line 536  C
    a500201d()  Unknown

Это не полный стек вызовов. Полный стек вызовов имеет длину в несколько миль.


person Sam Burns    schedule 25.04.2015    source источник
comment
(struct Node *)malloc(sizeof(*newNode)) должно быть malloc(sizeof(struct Node))   -  person SleuthEye    schedule 25.04.2015
comment
Я получаю синтаксическую ошибку, если я это делаю. Ошибка: значение типа void* нельзя использовать для инициализации сущности типа Node*   -  person Sam Burns    schedule 25.04.2015
comment
@SamBurns Я предполагаю, что вы компилируете это как исходный файл C с помощью Visual Studio.   -  person WhozCraig    schedule 25.04.2015
comment
Да, нам не разрешено использовать C++   -  person Sam Burns    schedule 25.04.2015
comment
Компилятор VS, даже в C-режиме, будет жаловаться на malloc присваивания непосредственно типизированным указателям, таким как ваш. Обычно это плохая идея приводить malloc. Вы, очевидно, включаете правильные вещи, чтобы получить правильный прототип для malloc, иначе вы получили бы два предупреждения/ошибки (одно для неявного объявления malloc, другое для попытки присвоить int к указателю). Несмотря на это, проверьте переключатели компилятора и убедитесь, что вы компилируете как код C для вашего файла .c. Если да, то IntelliSense по-прежнему будет ругаться, но он должен выдавать предупреждение только во время компиляции.   -  person WhozCraig    schedule 25.04.2015
comment
Я изменил его, перейдя в свойства проекта > Свойства конфигурации > C/C++ > Дополнительно > Компилировать как > Компилировать как код C (/TC) Это правильный способ?   -  person Sam Burns    schedule 25.04.2015
comment
Похоже, вы сделали это правильно. И к вашей реальной проблеме, где-то в вашем коде вы, вероятно, повреждаете кучу, и побочный эффект (ы) этого вызова неопределенного поведения возникает в этом malloc, когда цепочка кучи обнаруживается как плохая. Не очень помогает, но это то, к чему это в конечном итоге приведет.   -  person WhozCraig    schedule 25.04.2015
comment
Я предполагаю, что это не связано, но ближе к концу main читает scanf_s("%d", NULL);: что это? почему НУЛЬ?   -  person Diego    schedule 25.04.2015
comment
Просто чтобы приостановить программу, чтобы я мог посмотреть на вывод.   -  person Sam Burns    schedule 25.04.2015
comment
да, но функция сохранит значение, прочитанное как NULL, что неверно   -  person Diego    schedule 25.04.2015
comment
Я даже никогда ничего не ввожу, но с тех пор я изменил его на я, чтобы быть уверенным. Он не делает ничего другого.   -  person Sam Burns    schedule 25.04.2015
comment
У вас возможно повреждение функции печати. Обратите внимание, вы увеличиваете i-й размер списка, а не тот, в который вы фактически вставляете. Это обязательно приведет к повреждению позже при печати.   -  person SomeWittyUsername    schedule 25.04.2015
comment
Вот в чем проблема, я не понял. Спасибо, поместите это в ответ, чтобы я мог принять его.   -  person Sam Burns    schedule 25.04.2015


Ответы (1)


У вас возможно повреждение функции печати. Обратите внимание, вы увеличиваете i-й размер списка, а не тот, в который вы фактически вставляете. Это обязательно приведет к повреждению позже при печати. Тем не менее, немного странно, что ваш сбой происходит до того, как вы доберетесь до самой печати.

person SomeWittyUsername    schedule 25.04.2015
comment
Я думаю, будущим читателям будет полезно указать, что я изменил (lists[i].size)++; to (списки[random%MAX].size)++; - person Sam Burns; 25.04.2015