Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Впрочем, и без очереди тоже. Вот как раз сейчас у меня задача, в которой новые элементы добавляются только в конец (и никогда никакие элементы не удаляются, потом список уничтожается целиком). И как же мне его реализовать без того, чтобы хранить указатель на конец ? А расходы при этом нулевые — один указатель.
В такой задаче да, выгодно хранить. Ещё выгоднее, и логичнее, к тому же, хранить просто узел, после которого ты вставляешь элементы. Тогда "точку роста" можно в любом месте иметь
А у Вирта, вроде как, было немного не так. Там в качестве итератора элемента списка использовался, помнится, указатель на элемент перед тем, на который мы хотим указать. А в начале списка был один недоступный служебный элемент.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
E>>И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент? PD>А мне вовсе и не надо его удалять.
Мы всё ещё про задачу "разрушить элементы односвязанного списка, начиная с конца" или о чём-то другом?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
E>>Вот я утверждаю, что это можно сделать прямо, не создавая закольцованных списков
PD>Расскажи, как это сделать однопроходным алгоритмом, не храня указатель на конец и не замыкая.
Однопроходность зависит от того, что ты хранишь в списке. В твоём варианте (с указтелем на последний элемент) однопроходно нельзя, не важно кольцуя или нет.
Замыкать для этого в любом случае не надо.
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
PD>>Впрочем, и без очереди тоже. Вот как раз сейчас у меня задача, в которой новые элементы добавляются только в конец (и никогда никакие элементы не удаляются, потом список уничтожается целиком). И как же мне его реализовать без того, чтобы хранить указатель на конец ? А расходы при этом нулевые — один указатель.
E>В такой задаче да, выгодно хранить. Ещё выгоднее, и логичнее, к тому же, хранить просто узел, после которого ты вставляешь элементы. Тогда "точку роста" можно в любом месте иметь
Не знаю я, что за такой узел, и по каким критериям его иметь. Если есть такой критерий — пожалуйста.
E>А у Вирта, вроде как, было немного не так. Там в качестве итератора элемента списка использовался, помнится, указатель на элемент перед тем, на который мы хотим указать. А в начале списка был один недоступный служебный элемент.
Это — самый простой способ построения списка. Но при этом
полученный порядок элементов обратен порядку их «поступ-
«поступления». В некоторых случаях это нежелательно; следова-
следовательно, новые элементы должны добавляться в конец списка.
Хотя конец легко найти проходом по списку, такой непосред-
непосредственный подход потребовал бы затрат, которых просто избе-
избежать, используя вторую ссылку q, которая всегда указывает
на последний элемент. Такой метод применяется, например,
в программе 4.4, формирующей перекрестные ссылки на за-
заданный текст. Недостаток такого метода состоит в том, что
первый включаемый элемент приходится обрабатывать иначе,
чем остальные.
E>>>И как он поможет тебе его удалить первым? Или ты хранишь указатель на предпоследний элемент? PD>>А мне вовсе и не надо его удалять. E> E>Мы всё ещё про задачу "разрушить элементы односвязанного списка, начиная с конца" или о чём-то другом?
Здравствуйте, Pavel Dvorkin, Вы писали:
E>>В такой задаче да, выгодно хранить. Ещё выгоднее, и логичнее, к тому же, хранить просто узел, после которого ты вставляешь элементы. Тогда "точку роста" можно в любом месте иметь PD>Не знаю я, что за такой узел, и по каким критериям его иметь. Если есть такой критерий — пожалуйста.
Ну вот в твоей задаче это последний добавленный...
PD>первый включаемый элемент приходится обрабатывать иначе, PD>чем остальные.
Вот для этого как раз у Вирта в начале списка был невидимый пользователям элемент...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>>А мне вовсе и не надо его удалять. E>> E>>Мы всё ещё про задачу "разрушить элементы односвязанного списка, начиная с конца" или о чём-то другом?
PD>Да , про нее (в моей "интерпретации"
А почему, тогда, тебе не надо удалять последний элемент?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
PD>>Расскажи, как это сделать однопроходным алгоритмом, не храня указатель на конец и не замыкая. E>Однопроходность зависит от того, что ты хранишь в списке.
Это что-то новое. Почему ? На удаление того, что там хранится, есть деструктор ListElement, он должен знать, как там удалять.
>В твоём варианте (с указтелем на последний элемент) однопроходно нельзя, не важно кольцуя или нет.
Вирта почитай. Там есть прием для удаления текущего элемента.
//////////////////////////////////////////////////
Труднее удалить сам указанный элемент (а не следующий
за ним), поскольку мы сталкиваемся с той же проблемой,
что и при включении перед р\: возврат к элементу, который
Рис. 4.9. Удаление из списка и включение в другой список.
предшествует указанному, невозможен. Но можно удалить
последующий элемент, предварительно переслав его значение
ближе к началу списка. Это довольно очевидный и простой
прием, но его можно применить только в случае, когда у р\
есть последующий элемент, т. е. он не является последним
элементом списка.
//////////////////////////////////////////////////
А в циклическом списке как раз и нет последнего в этом смысле элемента
E>Замыкать для этого в любом случае не надо.
Здравствуйте, Erop, Вы писали:
E>>>В такой задаче да, выгодно хранить. Ещё выгоднее, и логичнее, к тому же, хранить просто узел, после которого ты вставляешь элементы. Тогда "точку роста" можно в любом месте иметь PD>>Не знаю я, что за такой узел, и по каким критериям его иметь. Если есть такой критерий — пожалуйста. E>Ну вот в твоей задаче это последний добавленный...
Последний — вполне четкий критерий независимо от задачи.
E>Вот для этого как раз у Вирта в начале списка был невидимый пользователям элемент...
Ты мне будешь про списки с барьером и с начальным элементом рассказывать ? Поверь, после примерно 10 лет чтения студентам этого курса я о них что-то знаю.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Вирта почитай. Там есть прием для удаления текущего элемента.
Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю
PD>Ну так напиши код.
Так я вроде как уже писал
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
>>В твоём варианте (с указтелем на последний элемент) однопроходно нельзя, не важно кольцуя или нет.
PD>Вирта почитай. Там есть прием для удаления текущего элемента.
Кстати, если ты считаешь, что разрушение копии эквивалентно разрушению оригинала, то ты можешь просто обменять содержимое начала и конца списка, а потом ужо разрушать с начала и не париться
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Вирта почитай. Там есть прием для удаления текущего элемента. E>Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю
Доказательства в студию.
PD>>Ну так напиши код.
E>Так я вроде как уже писал
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Ты мне будешь про списки с барьером и с начальным элементом рассказывать ? Поверь, после примерно 10 лет чтения студентам этого курса я о них что-то знаю.
Тем больше меня удивляет то, что ты тут пишешь
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Pavel Dvorkin, Вы писали:
PE>>Это удаление следующего элемента + копирование его данных в текущий. Являются ли эти действия эквивалентными -- вопрос спорный. Я, например, так не считаю
PD>Доказательства в студию.
Доказательства чего?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Кстати, если ты считаешь, что разрушение копии эквивалентно разрушению оригинала, то ты можешь просто обменять содержимое начала и конца списка, а потом ужо разрушать с начала и не париться
Можно и так. Только делать это придется каждый раз, иначе ты после последнего удалишь второй, а не первый.
Здравствуйте, Erop, Вы писали:
PD>>Ты мне будешь про списки с барьером и с начальным элементом рассказывать ? Поверь, после примерно 10 лет чтения студентам этого курса я о них что-то знаю.
E>Тем больше меня удивляет то, что ты тут пишешь
Меня тоже. Если у тебя уж цитаты из Вирта вызывают улыбку, то надо все же аргументы приводить. Их нет, есть лишь одни слова.
