将节点插入已排序的双向链表

Question

我正在尝试在排序链表中输入一个新节点。我不知道这段代码有什么问题。

Node* SortedInsert(Node *head,int data)
{
    struct Node *temp=head,*p=NULL;
    struct Node *newNode=(struct Node*)malloc(sizeof(struct Node));
    newNode->data=data;
    newNode->next=NULL;
    newNode->prev=NULL;
    if(!head){
        return newNode;
    }

    while((data>=(temp->data)) && temp!=NULL){
        p=temp;
        temp=temp->next;
    }
    if(temp==NULL){
        p->next=newNode;
        newNode->prev=p;
        return head;
    }
    if(p==NULL){
        head->prev=newNode;
        newNode->next=head;
        return newNode;
    }

    p->next=newNode;
    newNode->prev=p;
    newNode->next=temp;
    temp->prev=newNode;

    return head;
}

Answer 1

行

while((data>=(temp->data)) && temp!=NULL){

应该阅读

while(temp!=NULL && (data>=(temp->data))){

您需要先测试 temp 不是 NULL，否则您可能会进行无效读取，从而导致访问冲突。

Answer 2

看来 Eelke 的回答是关键问题。这是一个使用 Node 的 typedef 来消除对 struct Node 的需要的示例，因为它在示例代码中的使用并不一致：

#include <malloc.h>
#include <stdio.h>

typedef struct Node_{
    struct Node_ *next;
    struct Node_ *prev;
    int data;
}Node;

Node* SortedInsert(Node *head,int data)
{
    Node *temp=head,*p=NULL;
    Node *newNode=(Node*)malloc(sizeof(Node));
    newNode->data=data;
    newNode->next=NULL;
    newNode->prev=NULL;
    if(!head){
        return newNode;
    }
    while(temp!=NULL && (data>=(temp->data))){
        p=temp;
        temp=temp->next;
    }
    if(temp==NULL){
        p->next=newNode;
        newNode->prev=p;
        return head;
    }
    if(p==NULL){
        head->prev=newNode;
        newNode->next=head;
        return newNode;
    }
    p->next=newNode;
    newNode->prev=p;
    newNode->next=temp;
    temp->prev=newNode;
    return head;
}

int main(int argc, char *argv[])
{
Node * head = NULL;
Node *pNode;
    head = SortedInsert(head, 2);
    head = SortedInsert(head, 5);
    head = SortedInsert(head, 3);
    head = SortedInsert(head, 4);
    head = SortedInsert(head, 1);
    while(head){        /* scan to last */
        pNode = head;
        head = head->next;
    }
    while(pNode){       /* follow last to first */
        printf("%d\n", pNode->data);
        head = pNode;
        pNode = pNode->prev;
    }
    printf("\n");
    while(head){        /* follow first to last and free */
        printf("%d\n", head->data);
        pNode = head;
        head = head->next;
        free(pNode);
    }
    return(0);
}

将节点插入已排序的双向链表

Inserting a node into a sorted doubly linked list

c

linked-list

sorted

doubly-linked-list