c - 添加到排序链表时如何避免段错误？

Question

我需要在添加新元素时创建一个新函数，它将它放在列表中，以便列表保持排序顺序。我不确定我的实现是否正确，我与我的小组成员的第一次尝试给出了段错误。当我尝试自己做时，它什么也没做。任何帮助将不胜感激。这是我的代码:

头文件:

typedef struct s{
        int value;
        struct s *next, *previous;
} node, *node_ptr;

c文件:

#include <stdio.h>
#include <stdlib.h>
#include "double.h"

void
print_list(node_ptr list) {
   // walk the list to print out the contents
   while (list) {
        printf("%d ",list->value);
        list = list->next;
   }
   printf("\n");
}

void delete_list(node_ptr list) {
   // walk the list to delete the elements
   node_ptr t;
   while (list) {
        t = list;
        list = list->next;
        free(t);
   }
}

node_ptr new_node(int value) {
   node_ptr t = (node_ptr)malloc(sizeof(node));
   t->value = value;
   t->next = t->previous = NULL;
   return t;
}

node_ptr add_to_back(node_ptr list, int value) {
   node_ptr t = list;
   node_ptr s = new_node(value);
   // special case: starting with an empty list
   if (t == NULL) return s;
   // at this point we know there is a least one element in
   // the list
   while (t->next != NULL)  // walk the list looking for the last element 
     t = t->next;
   // we are at the end so now we arrange the pointers
   t->next = s;
   s->previous = t;
   return list;
}

// my implementation after some research
node_ptr add_sorted(node_ptr list, int value) {
        node_ptr temp = list;
        node_ptr newNode;

        if(temp == NULL || temp->value < newNode->value)
        {
                newNode->next = temp;
                temp = newNode;
        }
        else
        {
                while(temp != NULL && temp->value < value)
                {
                        temp = temp->next;
                }
                newNode->next = temp->next;
                temp->next = newNode;
        }
        return newNode;
}

// second implementation with team
/*
node_ptr add_sorted2(node_ptr list, int value) {
        // This is the function you need to implement
        // when adding a new element place it in the list so that the list stays in sorted order.
        node_ptr temp = list;
        node_ptr n = new_node(value);

        if(temp == NULL)
        {
                temp->value = value;
                temp->next = NULL;
                return n;
        }
        else if(temp->next != NULL) {   
        while(temp->next != NULL) {

                 if(temp->value <= value) {
                        n->next = temp->next;
                        temp->next = n;
                        return n;               
                }
                else if(temp->value > value) {
                        temp = temp->next;
                }
                else {
                        temp->next = n;
                        return n;
                }
        }
        }
        return n; 
}
*/

int
main() {
   int in_val;
   node_ptr my_list = NULL;
   node_ptr sorted_list = NULL;
   scanf("%d",&in_val);
   while (in_val > 0) {  // going to read input until see 0 or negative
           my_list = add_to_back(my_list,in_val);
           sorted_list = add_sorted(sorted_list,in_val);
           scanf("%d",&in_val);
   }
   printf("List:\n");
   print_list(my_list);
   printf("Sorted List:\n");
   print_list(sorted_list);
   delete_list(my_list);
   delete_list(sorted_list);
}

Answer 1

段错误对我来说很清楚，你在这里使用了一个未初始化的指针

if(temp == NULL || temp->value < newNode->value)
//                                  ^

或者任何其他newNode在任何地方的取消引用，因为newNode 从未在您的代码中初始化。

如果 temp == NULL，并且您还没有初始化 newNode，那么未定义的行为。

在保持顺序的情况下将节点添加到列表很容易，

1. 创建新节点
2. 如果成功创建它，遍历列表直到下一个节点比新节点大|小(取决于您想要的顺序)。
3. 找到后，将当前节点的next链接到新节点，next节点应该是新节点的next。

仅此而已。