Вставка узла в связанный список c

Question

Хорошо. Это код для вставки узла в связанный список.

vec_store содержит последовательность и размер. Переменная seq содержит векторы и указатель. и vec_mag принимает величину векторов.

По какой-то причине (vec_mag(v)<=vec_mag(temp2->next->data)) не работает, что является последним условием.

Any1 может решить проблему? Кстати, это код C.

vector last_vec(vec_store s){  
 node temp3;  
 temp3=s->seq;  
 while (temp3->next!=NULL)  
  {temp3 = temp3->next;  
 }  
  return temp3->data;  
}  


void insert_vec(vec_store s, vector v){  
node temp1,temp2,temp4;  
int i;  
temp1 = malloc(sizeof (struct node_record));  

if(s->seq==NULL){  
 s->seq=temp1;  
 temp1->next=NULL;  
 temp1->data=v;  
 s->size++;  
 printf("1\n");  
}  
else if(vec_mag(v)<=vec_mag(s->seq->data)){  
 s->size++;  
 temp2=s->seq;  
 temp1->data=v;  
 temp1->next=temp2;  
 s->seq=temp1;  
 printf("2\n");  
}  

else if(vec_mag(v)>=vec_mag(last_vec(s)))  
{  s->size=s->size+1;   
  temp4=s->seq;  
  while (temp4->next!=NULL)  
  {temp4 = temp4->next;  
  }  
  temp1->next=NULL;  
  temp1->data=v;  
  temp4->next=temp1;  
  printf("3\n");  
}  
else{  
 temp2 = s->seq;  
 temp4 = s->seq;  
 for(i=0;i<s->size-1;i++){  
  if(vec_mag(v)<=vec_mag(temp2->next->data)){     
  temp1->data = v;  
  temp1->next = temp2->next;  
  temp2->next=temp1;  
  printf("4\n");  
  s->size++;  
  break;  
  }    
 }  

}  
}  

Answer 1

«Anon» правильно - вы перебираете переменную i по размеру списка, вы не сдвигаете указатели перед сравнением.

Но здесь есть и другие проблемы.

Я не уверен, как выглядят ваши структуры данных, поскольку вы не опубликовали их источник, но я собираюсь предположить, что вы подразумеваете, что узлы (temp1 - temp4) являются указателями узлов, а не полными экземплярами структур.

Это хорошее усилие, но используются чрезмерные переменные, ненужные вычисления и ненужное копирование по значению. В этом нет ничего плохого в вычислительном отношении, если вы получите результат, который искали, но я не думаю, что он делает именно то, что вам нужно, и усложняет его отслеживание / поддержание. Иногда очень важно установить все в логические блоки с парой комментариев.

Я не пытался скомпилировать это (попробуйте просто прочитать логику и комментарии), но вам может повезти с чем-то вроде следующего (извинения за комментарии c ++ в коде C):

// construct the node and its data first (except for the next pointer)
// - it's going to be inserted no matter what the list is like
node* inserted = (node*) malloc(sizeof(struct node));
inserted->data = v;
// store the vector magnitude so you don't have to compute it on every comparison
double v_mag = vec_mag(v);

// Case 1 - empty list
if (s->seq == NULL)
{
    inserted->next = NULL;
    s->seq = inserted;
}
// Case 2 - in case there's only one element in the list
// (this is me being too lazy to work this step into the main logic in case 3)
else if (s->seq->next == NULL)
{
    t1_mag = vec_mag(s->seq->data);
    if (v_mag <= t1_mag)
    {
        //insert
        inserted->next = s->seq;
        s->seq = inserted;
    }
    else
    {
        //append
        inserted->next = NULL;
        s->seq = inserted;
    }
}
// Case 3 - there are at least 2 elements in the list
else
{
    // set the temporary nodes to the first 2
    node* temp1 = s->seq;
    node* temp2 = temp1->next;
    // store their magnitudes
    double t1_mag = vec_mag(temp1->data);
    double t2_mag = vec_mag(temp2->data);
    // while we aren't at the list, and we aren't at a spot where the node should be inserted
    while (temp2 != NULL && !(v_mag >= t1_mag && v_mag <= t2_mag ))
    {
        // shift the two to the next in the line
        temp1 = temp2;
        // no need to recompute this magnitude from the last step - just copy it
        t1_mag = t2_mag;
        temp2 = temp2->next;
        t2_mag = vec_mag(temp2->data);
    }
    // if we can trust the integrity of the list, either temp2 is null (at the end of the list),
    // or another node (we found a suitable place to insert).
    // Either way, just blindly insert the node.
    inserted->next = temp2;
    temp1->next = inserted;
}
// Node has been inserted
s->size++;

Answer 2

Проблема в том, что в этом цикле вы вообще не двигаетесь по списку.