c - 如果元素在中间，则双向链表插入排序不起作用

Question

我的问题是当我插入数字时它可以工作但是如果我想在中间插入它会被插入但不打印下一个节点我不知道它是删除它们还是无权访问它们。

struct node {
    int data ;
    struct node *prev;
    struct node *next;
};

struct node* head = NULL;

这是有问题的函数插入。

void insert(int key) {
    struct node *pred=head, *succ;
    struct node *temp2, *temp;
    if (head==NULL) {
        head = (struct node *) malloc(sizeof(struct node));
        head->data = key;
        head->prev = NULL;
        head->next = NULL;
    } else {
        temp2 = (struct node*) malloc(sizeof(struct node));
        temp2->data =  key;
        temp = head;
        while(temp->next!=NULL && temp->next->data < key) {
            pred= temp->next;
            temp = temp->next;
        }
        printf("******pred : %d \n",pred->data);
        //printf("******temp-next %d \n",temp->next->data);
        if (temp->data < key) {
            temp->next = temp->next->next;
            temp->next = temp2;
            temp2->prev = temp;
            temp2->next = pred->next->next;
        } else {     
            //temp2->next= temp;
            //temp->prev = NULL; 
            temp2->next = head;
            //head->prev = temp2;
            head = temp2;
            printf("**** temp : %d",temp->data);
            printf("**** temp2 : %d",temp2->data);
            printf("here\n");
            //temp = temp2 ->prev;
            //temp->prev = NULL;        
        }           
    }
}

Answer 1

I would suggest you to fix names of variables temp1,2. It complicates a lot understanding of the code.
In the while() loop there is pred and temp variables which have the same value. Then why not just remove one of them?
Right after the while() loop there is a check for value - but while() loop has already checked item temp for this condition while looping through the items. So this check is wrong.
Now you already know that item "temp" is less than key, but next item, if it is not NULL is greater. So you have to check if it is NULL or not.
If it is NULL then you have to add new item to the end of the list.
If it is not NULL then you have to add item right after current item "temp" and before "temp->next" because "temp->next" is already greater than current item "temp" and new item.

Below a code for using in case of if statement then header is not NULL (with some variables renamed for clearness):

{   
    assert(head != NULL); // head not NULL already
    newItem = (struct node*) malloc(sizeof(struct node));
    newItem->data =  key;
    currItem = head;

    while(currItem->next!=NULL && currItem->next->data < key){
        currItem = currItem->next;}

    if(currItem->next == NULL){ // append new item to the end of list
        currItem->next = newItem;
    }               
    else{ // insert somewhere in the middle (next item key is greater than current key)
        newItem->next = curr->next;
        currItem->next = newItem;
    }           
}

Answer 2

The insert in the middle code (last if-statement in the posted code example) should work better like this:

    if (temp->data < key) {
        // Insert in the middle
        temp->next = temp2;
        temp2->prev = temp;
        temp2->next = pred->next->next;
        temp2->next->prev = temp2;       // Added
    } else {     
        // Insert last                   // Changed entire block
        temp2->prev= temp;     
        temp->next = temp2; 
        temp2->next = null;
    }           

Answer 3

对于维护 a 的双向链表tail将是对称的。没有那个，我会这样做。

整个插入：

struct node* prev = NULL;
struct node* ptr;
for (ptr = head; ptr != NULL && key < ptr->data; ptr = ptr->next) {
    prev = ptr;
}

struct node* baby = (struct node *) malloc(sizeof(struct node));
baby->data = key;
baby->prev = prev;
baby->next = ptr;
if (prev != null) {
    prev->next = baby; // Link in from previous
}
if (ptr != null) {
    ptr->prev = baby; // Link in from next
}
if (head == NULL) {
    head = baby;
}

Answer 4

重新安排了一下：

temp = calloc(1, sizeof(struct node)); // 0's node
temp->data=key;  

if ( head == NULL ) // empty
{
  temp = head; // done
}
else if ( head->data < key ) // first element already larger
{
  temp->next = head;
  head->prev = temp;
  head = temp;
}
else // find larger key
{
  struct node *pred = NULL; // technically head->prev
  struct node *succ = head;      

  while( succ != NULL && succ->data < key )
  { 
    pred = succ;  // previous
    succ = succ->next;
  } 

  // went to end of list, so append to end
  if ( succ == NULL )
  {
    temp->prev = pred;
    pred->next = temp;
  }
  else // found one larger
  {
    temp->next = succ;
    temp->prev = succ->prev;
  }
}