Функция вставки связанного списка возвращает неверное значение при тестировании с единицей - PullRequest
Новая
       6

Функция вставки связанного списка возвращает неверное значение при тестировании с единицей

1 голос
/ 10 января 2020

Я работаю над простой реализацией двусвязного списка в c, я создал свои структуры следующим образом. 

typdef struct node{
  void *data;
  struct node *next, *prev;
}node;

typedef struct list{
  struct node *head, *tail;
  size_t size;
}list;

Я вставляю элементы в свой связанный список, используя эту функцию, и все, кажется, работает нормально. Давайте предположим, что я заполняю свой список целыми числами, вызывая функцию 4 раза для вставки {2,4,6,8}. Когда я выполняю свою функцию печати, она правильно возвращает 2,4,6,8. 

void insert_node(list *l, void *elem)
{
  node *n = create_node(elem); //here i just create and initialize the new node;
  if(l->size == 0){
    l->head = n;
    l->tail = n;
  }else{
    l->tail->next = n;
    n->prev = l->tail;
    l->tail = n;
  }
  l->size++;
}

Проблема возникает, когда я пытаюсь проверить свою функцию с единицей, я написал этот простой модульный тест: 

void test_list_insert(){
 list *l = list_test(); //this function creates a list and inserts in it {2,4,6,8} as values
 TEST_ASSERT_EQUAL_INT(2, *(int*)(get_node_i(l,0))->data);
 TEST_ASSERT_EQUAL_INT(4, *(int*)(get_node_i(l,1))->data); //problem seems to be here..
 TEST_ASSERT_EQUAL_INT(6, *(int*)(get_node_i(l,2))->data);
 TEST_ASSERT_EQUAL_INT(8, *(int*)(get_node_i(l,3))->data);
}

Когда я выполняю свой модульный тест, я получаю следующий вывод: 

test.c:73:test_list_insert:FAIL Expected 4 was 1

На данный момент проблема, похоже, связана с функцией 'get_node_i', которая используется для извлечения элемента в i-м положение списка ... вот функция: 

node *get_node_i(list *l, int pos){
 if(pos > l->size || pos < 0){
   return NULL;
 }
 node *curr = l->head;
 int currPos = 0;
 if(pos == 0) return curr;
 while(curr != NULL){
   if(currPos == pos){
     return curr; 
   }
   currPos++;
   curr = curr->next;  
 }
 return NULL;
}

Я попытался выполнить свою функцию печати внутри модульного теста и обнаружил, что она правильно печатает только первые два узла (2,4) а для других узлов он печатает указатели ... Для меня это довольно странно, как будто я пытаюсь выполнить функцию печати в любой другой части моего кода, он возвращает список правильно ..

Вот как я создаю списки и узлы 

//create new node
node* create_node(void * elem){
  node *n = (node *)malloc(sizeof (node));
  n->data = elem;
  n->next = NULL;
  n->prev = NULL;
  return n;
}
//create an empty list
list  *create_list(){
  list *l = (list *)malloc(sizeof(list));
  l->size = 0;
  l->head = NULL;
  l->tail = NULL;
  return l;
}

Вот функция list_test и функция печати, 

list* list_test(){
   list *l = create_list();
   int a = 2;
   int b = 4;
   int c = 6;
   int d = 8;
   insert_node(l, &a);
   insert_node(l, &b);
   insert_node(l, &c);
   insert_node(l, &d);
   return l;

}


//print the list
void print_list(list *l){
  node *tmp = l->head;
  while(tmp != NULL){
    printf("%d\t" , *(int *)tmp->data);
    tmp = tmp->next;
  }
}

если что-то еще нужно уточнить, дайте мне знать, спасибо.

1 Ответ

0 голосов
/ 10 января 2020

В вашей функции list_test вы вставляете адрес локальных переменных. Таким образом, node->data назначается адрес локальной переменной. Когда функция вернется, данные, указанные по этому адресу, изменятся.

Функция list_test должна выглядеть примерно так: 

list* list_test(){
   list *l = create_list();
   int a = 2, *ap = malloc(sizeof(int));
   int b = 4, *bp = malloc(sizeof(int));
   int c = 6, *cp = malloc(sizeof(int));
   int d = 8, *dp = malloc(sizeof(int));
   *ap = a;
   *bp = b;
   *cp = c;
   *dp = d;
   insert_node(l, ap);
   insert_node(l, bp);
   insert_node(l, cp);
   insert_node(l, dp);
   return l;
}
...