C缓冲区溢出中的链表

Question

我要用 C 语言创建一个带有有序插入函数的链表。数组列表是单个链表的数组，我必须生成 10000 个随机数，有时我可以生成 300 或 400 个数字，有时它会失败并给我一个缓冲区溢出异常。我得到这个的原因是什么？

我认为这可能是因为我需要释放一些内存，但在我看来我需要分配的所有内存，没有任何剩余。

发生错误时，调用堆栈显示此行：

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

是导致异常的原因。

它在生成较少数字的情况下正常工作，就像我做 100 个数字一样，输出如下所示： http://gyazo.com/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

我遇到另一个错误：程序 6.exe 中 0x100B26B6 (msvcr110d.dll) 处的未处理异常：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

这不是完整的调用堆栈。完整的调用堆栈长达数英里。

Answer 1

您的打印功能可能已损坏。请注意，您增加的是第 i 个列表大小，而不是您实际插入的列表大小。这肯定会导致以后打印时损坏。仍然有点奇怪，你的失败发生在打印本身之前。

C缓冲区溢出中的链表

Linked List in C buffer overrun

c

linked-list

buffer-overrun