-3

我正在对链表进行练习。当我在列表开头输入值并且值小于列表中的值时，它会起作用。但是当数字更大时，我会遇到分段错误。有人想下面的代码有什么问题吗？

//标题（称为headeroef）：

typedef struct node
{
    int n;
    struct node* next;
}    node;

//其他代码

#include <cs50.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

#include "headeroef.h" 

void insert(void);
void traverse(void);

node* first = NULL;

int main (void)

{

    int c;
    do

        {
            printf("Print instructions: \n"
                   "1. insert\n"
                   "2. Delete\n");

            printf("Command: ");
            c = GetInt();

            switch(c)

                {
                case 1: insert(); break;
                }
        }

    while (c!=0);

}
void insert(void)

{
    node* newPtr = malloc(sizeof(node));
    printf("Number to insert: \n");
    newPtr->n = GetInt();
    newPtr->next = NULL;

    if (first == NULL)
        {
            first = newPtr; 
        }

    else if(newPtr->n < first->n)
        {
            newPtr->next = first;
            first = newPtr;
        }

    else 
        {
            node* predPtr = first;

            //Dit houdt dus als in als aan deze else wordt voldaan!
            while (true)

                {
                    if (predPtr->n == newPtr->n)
                        {
                            free(newPtr);
                            break;
                        }
                    else if (predPtr->next->n > newPtr->n)
                        {
                            //Hiermee doe je weer die swap
                            newPtr->next = predPtr->next;
                            predPtr->next = newPtr;
                            break;
                        }
                    //Uitzoeken waarom hier een segmentation fault komt.s           
                }          
        }   
    traverse();  

}

void traverse(void)

{
    printf("The list is now\n");
    node* ptr = first;
    while (ptr!=NULL)

        {
            printf("%i\n", ptr->n);
            ptr = ptr->next;
        }
}
4

3 回答 3

2

遍历列表以搜索插入点的while(true)循环不会检查它是否已到达列表的末尾，从而NULL最终取消引用指针。

predPtr当指向链表的最后一个节点时，这个检查会导致问题：

if (predPtr->next->n > newPtr->n)

什么时候predPtr是最后一个节点，predPtr->next是NULL，所以采取predPtr->next->n是未定义的行为。

于 2014-05-29T07:51:03.100 回答
1

假设您5在列表中有一个数字，并且您想添加7.

因为first不是NULL，并且您尝试插入的数字不小于第一个，所以它最终出现在最后一个块中：

node* predPtr = first;
//Dit houdt dus als in als aan deze else wordt voldaan!
while (true)
{
    if (predPtr->n == newPtr->n)
    {
        free(newPtr);
        break;
    }
    else if (predPtr->next->n > newPtr->n)
    {
        //Hiermee doe je weer die swap
        newPtr->next = predPtr->next;
        predPtr->next = newPtr;
        break;
    }
    //Uitzoeken waarom hier een segmentation fault komt.s           
}

因为您没有尝试插入重复项，所以第一if条语句是无关紧要的。组合：

node* predPtr = first;
while (true) {
    :
    else if (predPtr->next->n > newPtr->n)

是什么导致你的崩溃，因为predPtr->next是 NULL （只有5元素），所以predPtr->next->n将取消引用空指针。

在尝试取消引用之前，您基本上需要检测到这一点。如果您到达最后一个元素并且它仍然小于您尝试插入的元素，则需要附加它而不是从列表的末尾运行。

使用当前代码执行此操作的最简单方法可能是将while循环更改为：

while (true) {
    // gooi als identiek.

    if (predPtr->n == newPtr->n) {
        free(newPtr);
        break;
    }

    // voegen als aan het einde van de lijst

    if (predPtr->next == NULL) {
        predPtr->next = newPtr;
        break;
    }

    // steek indien minder

    if (predPtr->next->n > newPtr->n) {
        newPtr->next = predPtr->next;
        predPtr->next = newPtr;
        break;
    }

    // vooruit naar volgend element.

    predPtr = predPtr->next;
}

您会注意到我还在循环底部添加了语句以在列表中前进。没有这个，你几乎肯定会在某个时候陷入无限循环。

你也可以重构你的循环以使用不同的结束条件，但这需要更多的工作，而且我并不热衷于做比我必须做的更多的事情，除非我按小时支付:-)

于 2014-05-29T07:56:32.340 回答
0 
else if (predPtr->next->n > newPtr->n)

您检查 predPtr->next->n 而不检查 next 是否为空。此外，while(true) 循环可能永远不会结束。

于 2014-05-29T07:53:40.967 回答