печать связанного списка с начала

Question

Я получил код из Википедии для связанного списка (http://en.wikipedia.org/wiki/Linked_list).

Но он печатает результат в обратном порядке (5 4 3 2 1). Как сделать так, чтобы это печаталось с самого начала (1 2 3 4 5).

Answer 1

Я предполагаю, что вы говорите о реализации C в разделе "Поддержка языков".

Не печатается в обратном порядке. Это потому, что элементы вставляются в начало списка, поэтому вставка 1, 2, 3 приведет к списку, который содержит 3, 2, 1.

Это потому, что список представлен его головой, поэтому он быстрее вставляется в голову, чем в хвост. Чтобы вставить хвост, вам придется пройти весь список. Это делает вставку O (n) вместо O (1).

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

Answer 2

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

typedef struct node {
    int data;
    struct node *next;     /* pointer to next element in list */
    struct node *previous; /* pointer to previous element in list */
} node;

typedef struct list {
    node *head;            /* first element in list */
    node *tail;            /* last element in list */
} list;

Затем вы можете распечатать список с головы и / или с хвоста.

Answer 3

У меня есть эта программа, которая печатает строку в обратном порядке, используя рекурсию.Можете ли вы использовать свой связанный список в качестве входных данных для него?

void reversePrint(char *str)
{
if(*str == '\0')
return;
reversePrint(str+1);
printf("%c",*str);
}
int main()
{
char *input;
input = malloc(10);
strcpy(input,"wolfrevo");
reversePrint(input);
}

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

Подсказки:

1. Передать связанный список вместо строки // Изменить также прототип
2. Проверить, что список имеет значение NULL
3. Рекурсировать путем передачи следующий элемент связанного списка
4. Печатать данные внутри списка вместо строки

Answer 4

Порядок, в котором печатается список, - это порядок, в котором элементы присутствуют в списке.Вы можете распечатать его в обратном порядке (т.е. в том порядке, в котором были вставлены элементы), используя рекурсию.следующий код распечатает список в обратном порядке

void list_print (LLIST * n) {
if (n == NULL)
{
printf ("список пуст \"n ");
return;
}
}

void print_recursive (LLIST * n) {
if (n-> next == NULL)
printf ("% d \ n ", n-> data);
else
print_recursive (LLIST n-> next);
}

Answer 5

Рассмотрим следующий пример:

/****************************************************************/
/*  Function: Add an element to our list                        */
/*                                                              */
/*   Parameters: **p is the node that we wish to insert at.     */
/*               if the node is the null insert it at the beginning    */
/*               Other wise put it in the next space                   */


LLIST *list_add(LLIST **p, int i)
{
    if (p == NULL)           /*checks to see if the pointer points somewhere in space*/
        return NULL;

    LLIST *n = malloc(sizeof(LLIST));   /* creates a new node of the correct data size */
    if (n == NULL)
        return NULL;

    n->next = *p; /* the previous element (*p) now becomes the "next" element */
    *p = n;       /* add new empty element to the front (head) of the list */
    n->data = i;

    return *p;
}

Элементы добавляются в начало связанного списка при вызове list_add.Это из соображений эффективности;вам не нужно пересекать весь связанный список, чтобы вставить элемент (что вам нужно было бы сделать, если вы хотите добавить).

Для обратной печати вы можете использовать рекурсию, построить свой собственный стеккоторый является рекурсией слепого), или воссоздать список в обратном порядке.Рекурсивная версия:

void list_print_reverse(LLIST *n)
{
    if (n == NULL)
    {
        printf("list is empty\n");
        return;
    }

    if (n->next != NULL)
    {
        list_print_reverse(n->next);
    }

    printf("print %p %p %d\n", n, n->next, n->data);
}

Answer 6

Это потому, что список построен.

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