链表访问冲突写入位置

Question

我正在编写一个程序，使用 SSN 进行 LSD 基数排序。该程序会将数字解析为 3 位数字并执行 3 次传递。每次传递我都将数字存储到相应的数组元素 bucket[] 中;如果有重复项，我会在该位置创建一个链表，并将重复的链表存储在已经存在的链表后面。当我尝试插入链表的末尾时，代码中断。

编辑新错误消息

class node
{ 
public:
    node(int n, node *p){data=n;next=p;}
    int data;
    node *next;
};

void genData(int *dta, int n) 
{
for(int i=0; i < n; i++)// generate the social security numbers at random
    dta[i] =  rand()%889 + 111 + 1000*(rand()%889 + 111) + 1000000*                            (rand()%889 + 111);
 }
int radixSort(int *dta, int n, int *out)
{ 
// the dta array contains the data to be sorted.
// n is the number of data items in the array
// out is the array to put the sorted data
node *bucket[1000]; // declare an array of 1000 linked lists (head pointers)
int count = 0; // use this to count the instructions to graph the big-o
for(int i = 0; i < n; i++)out[i] = dta[i]; 
for (int pass = 0; pass < 3; pass++)
{
    for (int j = 0; j < 1000; j++){
        bucket[j] = NULL;
    }
    delete bucket;
    delete[]bucket;
    for (int i = 0; i < n; i++){
        int index=0;
        switch (pass)
        {
        case 0:
            index = out[i] % 1000;
        case 1:
            index = (out[i]/1000) % 1000;
        case 2:
            index = out[i] / 1000000;
        };
        if (bucket[index] = NULL){
            bucket[index] = new node(out[i], NULL);
        }
        else{
            node *cur=bucket[index];
            while (cur->next!= nullptr){   //****access violation reading location
                cur = cur->next;
            }
            node *ptr = new node(out[i], NULL);
            cur->next = ptr;
        }
    }
    int idx = 0;
    for (int i = 0; i < 1000; i++){
        if (bucket[i] == NULL) continue;
        else{
            out[idx] = bucket[i]->data;
            idx++;
            count++;
        }
    }
}

Answer 1

代码中存在许多问题：

1. 在您的 switch-语句中，您有类似 index == out[i] % 1000; 那些进行比较的行，我怀疑这是您想要的。作业使用单个 =
2. 您的初始化for (int j = 0; j < 1000; j++){bucket[j] = NULL;}不会检查其中是否已经有指针 - 这将导致第一次传递后内存泄漏。 请记住：每个new都需要一个delete。
3. 这就是可能破坏您的代码的原因：一旦cur是nullptr，while (cur!= NULL){cur = cur->next;}就会退出while循环 - 这意味着在2行后尝试取消引用它是试图取消引用nullptr，这是一个坏主意。为了获得最后一个元素，您可能想要检查的是'while(cur->next ！= nullptr(

请注意：如果您的编译器支持nullptr那么使用它是个好主意，即使您可能需要通过适当的标志启用 C++11。