插入已排序的链接列表

试图编写一个函数，要求用户输入一个整数，然后按升序将其插入到链接列表中。插入已排序的链接列表

typedef struct _listnode{ 
    int item; 
    struct _listnode *next; 
} ListNode;   

typedef struct _linkedlist{ 
    int size; 
    ListNode *head; 
} LinkedList;   

void insertSortedLinkedList(LinkedList *l) 
{ 
    ListNode *cur; 
    int x; 
    printf("please input an integer you want to add to the linked list:"); 
    scanf("%d", &x); 

    if (l->head == NULL) // linkedlist is empty, inserting as first element 
    { 
     l->head = malloc(sizeof(ListNode)); 
     l->head->item = x; 
     l->head->next = NULL; 
    } 
    else 
    { 
     cur = l->head; 
     if (x < cur->item) // data is smaller than first element, we will insert at first element and update head. 
     { 
      cur->next->item = cur->item; // store current element as next element. 
      cur->item = x; 
      cur->next = cur->next->next; 
     } 
    } 
    l->size++; 
}

函数尚未完成，但为什么我的代码不工作，如果数据比第一个元素小？

来源

2015-04-05 Ng Hui Xiong

请注意，以下划线开头的名字基本上是为'实现'使用的（它稍微比这更微妙，但只是稍微有点）。避免使用这些名字。 – 2015-04-05 05:47:25

首先，你需要为新元素创建节点，就像这样：

ListNode* newNode = malloc(sizeof(ListNode)); 
newNode ->item = x;

现在改变你的代码：

if (x < l->head->item) // data is smaller than first element, we will insert at first element and update head. 
    { 
     newNode->next = l->head; 
     l->head = newNode; 
    } 
}

像你说的代码是不完整的肯定和循环经列表直到找到插入新节点的正确位置。

可以编写1个代码来处理所有情况。处理这些情况的一种常见方式是这样做，即让节点位于链接列表的头部。

来源

2015-04-05 05:48:44 Mzf

插入函数的else分支假定cur->next不是NULL（因为您将值设置为cur->next->item）。现在设想插入两个数字（第二个小于第一个）。在第一次插入中，l->head->next设置为NULL。因此，在第二次插入时，程序在尝试将cur->next->item设置为某个值时会崩溃。您应创建节点（即通过malloc()分配内存），根据需要初始化节点以包含字段，然后将其设置为cur->next。

来源

2015-04-05 05:47:48

插入已排序的链接列表

回答

相关问题