исправить обратную ссылку

Question

эй, по какой-то причине мой связанный список печатается в обратном порядке, например, если мой ввод 2-> 4-> 6, мой вывод 6-> 4-> 2

list* add_int_list(list* a,int b)
{
    list *temp;
    temp = (list*)malloc(sizeof(list*));
    temp->next = NULL;
    if (a->next == NULL)//insert to the first node
    {
        temp->data = b;
        temp->next = a;
        a = temp;

    }
    else 
    {
        temp->data = b;
        temp->next = a;
        a = temp;//I think the problem is here, couldnt find how to fix 
}

Answer 1

Для начала в этом утверждении

temp = (list*)malloc(sizeof(list*));
                            ^^^^^

выделена память размером, равным размеру указателя, а не размеру узла. Вы должны написать либо

temp = (list*)malloc(sizeof(list));

, либо

temp = (list*)malloc(sizeof( *temp));

Это выражение if

if (a->next == NULL)

может вызывать неопределенное поведение, поскольку изначально список может быть пустым. Таким образом, указатель a может быть равен NULL. То есть для доступа к памяти используется пустой указатель.

Нет разницы между этими двумя блоками кода после частей if и else оператора if-else

if (a->next == NULL)//insert to the first node
{
    temp->data = b;
    temp->next = a;
    a = temp;
}
else 
{
    temp->data = b;
    temp->next = a;
    a = temp;//
}

То есть фрагмент кода пытается вставить новый узел в начало списка.

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

Если вы хотите добавить узел в конец односвязного списка, сделайте его двусторонним.

Вот демонстрационная программа.

#include <stdio.h>
#include <stdlib.h>

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

typedef struct List
{
    Node *head;
    Node *tail;
} List;

int push_front( List *list, int data )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = data;
        new_node->next = list->head;

        list->head = new_node;

        if ( list->tail == NULL ) list->tail = list->head;
    }

    return success;
}

int push_back( List *list, int data )
{
    Node *new_node = malloc( sizeof( Node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->data = data;
        new_node->next = NULL;

        if ( list->tail == NULL )
        {
            list->head = list->tail = new_node;
        }
        else
        {
            list->tail = list->tail->next = new_node;
        }
    }   

    return success;
}

void output( const List *list )
{
    for ( const Node *current = list->head; current != NULL; current = current->next )
    {
        printf( "%d -> ", current->data );
    }

    puts( "null" );
}

int main(void) 
{
    List list = { .head = NULL, .tail = NULL };

    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        if ( i % 2 != 0 )
        {
            push_front( &list, i );
        }
        else
        {
            push_back( &list, i );
        }

        output( &list );
    }

    return 0;
}

Его вывод

0 -> null
1 -> 0 -> null
1 -> 0 -> 2 -> null
3 -> 1 -> 0 -> 2 -> null
3 -> 1 -> 0 -> 2 -> 4 -> null
5 -> 3 -> 1 -> 0 -> 2 -> 4 -> null
5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> null
7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> null
7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> 8 -> null
9 -> 7 -> 5 -> 3 -> 1 -> 0 -> 2 -> 4 -> 6 -> 8 -> null

В этой демонстрационной программе четные числа вставляются в конец списка с помощью функции push_back и нечетные числа вставляются в начало списка с помощью функции push_front.

Если ваш C компилятор не поддерживает назначенные инициализаторы, тогда это объявление

List list = { .head = NULL, .tail = NULL };

может изменить следующим образом

List list = { NULL, NULL };

Answer 2

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

  i = a; // to iterate
  while(i->next != NULL)
  {
   i = i->next;
  }
  // Now i is last node of list a
  i->next = temp;

Теперь приведенный ниже код, я просто проверяю его на Turbo C, я используя вашу функцию и вставив три значения, а затем распечатав список. Пожалуйста, смотрите все комментарии строки:

#include <stdio.h>
#include <malloc.h>
typedef struct node{
 int data;
 struct node *next;

}list;

list* add_int_list(list* a,int b)
{
    list *temp;
    list *i;

    temp = (list*)malloc(sizeof(list*));
    temp->next = NULL;
    temp->data = b;

    if (a == NULL)//insert to the first node
    {
       //temp->data = b; -  done above
    //temp->next = a; no reason for this line
        a = temp;
    }
    else
    {
       // temp->data = b; - done above
       //temp->next = a; wrong logic
       // a = temp;//I think the problem is here, couldnt find how to fix : Yes it is also wrong

      //Here it required to iterate complete list and go to end

      i = a; // to iterate
      while(i->next != NULL)
      {
       i = i->next;
      }
      // Now i is last node of list a
      i->next = temp;
    }

    return a;
}
void printList(list *root)
{
   list *i;

   if(root == NULL)
   {
    printf("List is empty");
   }
   else
   {
    i = root;
    while(i != NULL){
      printf("%d,",i->data);
      i = i->next;
    }
   }
}
int main()
{
  list *root = NULL;
  clrscr();
  root =  add_int_list(root, 3);
  root =  add_int_list(root, 4);
  root =  add_int_list(root, 5);
  printList(root);
    return 0;
}

Answer 3

Проблема в том, что ваш код добавляет узел в начало списка в обоих случаях. Если вы хотите всегда добавлять в конец списка, вам нужно пройтись по списку до конца, а затем добавить туда temp.

Я написал этот код не по назначению, поэтому примите его как псевдокод:

// Assuming this function returns the front (head) of the list.
list* append_element_to_list(list* a, int b)
{
    list *newNode;
    newNode = (list*)malloc(sizeof(list*));
    newNode->data = b;

    // Handle the case where `a` is NULL. This means
    // no list was passed in, so the newly created node
    // will be returned to start the list.
    if (a == NULL)
    {
      return newNode;
    }

    // If we get this far, it means `a` contains at least
    // one node. So walk the list until the end.
    list *currentNode = a;
    while (currentNode->next != NULL)
    {
      currentNode = currentNode->next;
    }

    // Once you reach the end of the list, set
    // `newNode` as the last node.
    currentNode->next = newNode;

    // The front of the list hasn't changed, so return that.
    return a;
}