Связный список, оператор -> (С++)

#cpp #visual_studio #список #односвязный_список

Есть код:

struct Element      //структура задающая элемент односвязного списка
{
    int data;       //информационное поле для хранения данных
    Element *next;  //указатель на следующий элемент
} *start, *current;

void create_list(int a)
{
    current = new Element;
    current->data = a;
    current->next = NULL;
    start = current;
}

void new_element(int a)
{
    Element *q;
    q = new Element;
    q->data = a;
    q->next = current->next;
    current->next = q;
}

void delete_element(int a)
{
    while (current->data != a)
    {
        current = current->next;
        if (current->data == a)
        {
            delete current;
        }
    }
}


Не совсем понял, что происходит в этих строчках:

current->next = NULL;


функции create_list(int)

и

q->data = a;
q->next = current->next;
current->next = q;


функции new_element(int)

Объясните, пожалуйста.
    

Ответы

Ответ 1

Первый - 

current->next = NULL;


просто устанавливает элемент, на который указывает current, последним в списке -
за ним (next) ничего нет.

q->data = a;
q->next = current->next;
current->next = q;


Это просто вставляет элемент после current - теперь новый элемент q указывает туда
же, куда раньше указывал элемент, на который указывал current, а он теперь указывает на q.

Вот примерный набросок - простите уж за отсутствие художественного таланта :) Видите?
разорвали связь и воткнули туда новый элемент...

развернуть связный список на python

#python #python_3x #односвязный_список

добрый день, не могли бы подсказать, как можно развернуть связный список? Нужно на
python'e..

from typing import Iterable

class LinkedListNode:

    def __init__(self, data):
        self.data = data
        self.next = None  # type: LinkedListNode

    def link(self, node: 'LinkedListNode') -> None:
        self.next = node


class LinkedList:

    def __init__(self, values: Iterable):
        previous = None
        self.head = None
        for value in values:
            current = LinkedListNode(value)
            if previous:
                previous.link(current)
            self.head = self.head or current
            previous = current

    def __iter__(self):
        current = self.head
        while current:
            yield current.data
            current = current.next

    def reverse(self) -> None:
        print("развернуть список")

    

Ответы

Ответ 1

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

def reverse_list(head, tail=None):
    while head:
        head.next, tail, head = tail, head, head.next
    return tail


Код в цикле отсекает голову списка (head/car), добавляя к ней хвост (tail) — head.next = tail
часть. Затем хвост наращивается (новый хвост указывает на только что отсечённую голову
с добавленным старым хвостом) — tail = head часть. Остаток списка (head.next/cdr) становится
новой головой (head) — head = head.next часть. Повторяем до конца списка — while head
часть.

Чтобы лучше понять код, рекомендую по шагам пройти (кнопка Forward>), обращая внимание
на значения head, tail локальных переменных в reverse_list() функции.

В Питоне, объекты в правой части = конструкции вычисляются до того как фактическое
присваивание происходит, которое затем  выполняется слева направо (например, нельзя
поменять местами head.next, head пару. Так как head.next, идущий после head в левой
части присваивания, обращался бы уже к новой изменённой голове списка).

Полный пример:

#!/usr/bin/env python3
"""Reverse linked list."""


class Node:
    """Linked list is either None or a value and a link to the next list."""

    def __init__(self, data, next=None):
        self.data = data
        self.next = next


head = Node(1, Node(2, Node(3, Node(4))))


def print_list(head, end='\n'):
    while head:
        print(head.data, end=' -> ' if head.next else '')
        head = head.next
    print(end=end)


print_list(head)


def reverse_list(head, tail=None):
    while head:
        head.next, tail, head = tail, head, head.next
    return tail


print_list(reverse_list(head))


Результат:

1 -> 2 -> 3 -> 4
4 -> 3 -> 2 -> 1


По сути Питон-код это перевод из Lisp алгоритма:

(define reverse-list (lambda (head tail)
  (if (null? head)
      tail
      (reverse-list (cdr head) (cons (car head) tail)))))

(reverse-list '(1 2 3 4) '())   
; -> (4 3 2 1)

Связный список, оператор -> (С++)

Есть код:
struct Element //структура задающая элемент односвязного списка { int data; //информационное поле для хранения данных Element *next; //указатель на следующий элемент } *start, *current;
void create_list(int a) { current = new Element; current->data = a; current->next = NULL; start = current; }
void new_element(int a) { Element *q; q = new Element; q->data = a; q->next = current->next; current->next = q; }
void delete_element(int a) { while (current->data != a) { current = current->next; if (current->data == a) { delete current; } } }
Не совсем понял, что происходит в этих строчках:
current->next = NULL;
функции create_list(int)
и
q->data = a; q->next = current->next; current->next = q;
функции new_element(int)
Объясните, пожалуйста.

Ответ

Первый -
current->next = NULL;
просто устанавливает элемент, на который указывает current, последним в списке - за ним (next) ничего нет.
q->data = a; q->next = current->next; current->next = q;
Это просто вставляет элемент после current - теперь новый элемент q указывает туда же, куда раньше указывал элемент, на который указывал current, а он теперь указывает на q
Вот примерный набросок - простите уж за отсутствие художественного таланта :) Видите? разорвали связь и воткнули туда новый элемент...