1

Добрый день, такое задание :

Написать класс, реализующий односвязный список. Класс должен содержать методы Push (добавление элемента в начало списка), Pop (извлечение элемента из начала списка). Также он должен переопределять унаследованный метод Print , возвращающий строковое представление списка. Написать метод Reverse , обращающий порядок следования элементов спис- ка. Написать программу, использующую класс.

Проблема в методе реверс. Как я сделал :

public void Reverse()
{
    if (head == null)
        throw new ListUnderflow();
    StringBuilder PrintList = new StringBuilder();
    Node temp = head;


    while (temp != null)
    {
        PrintList.Append(temp.value);
        PrintList.Append(" ");
        temp = temp.next;
    }

    StringBuilder builder = new StringBuilder();
    for (int i = PrintList.Length - 1; i >= 0; i--)
    {
        builder.Append(PrintList[i]);
    }
    string newName = builder.ToString();

    Console.WriteLine(newName);

}

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

public SinglyLinkedList Reverse()
{
    if (head == null)
        throw new ListUnderflow();
    SinglyLinkedList l2 = new SinglyLinkedList();
    l2.Push(Pop());
    return l2;
}

но я не уверен, по этому обратился сюда, можете подсказать ?

6
  • 3
    ну я бы предположил что список вообще менять не надо, а только развернуть связи. ru.stackoverflow.com/questions/509477/…
    – pavel
    21 июн 2016 в 10:18
  • интересно, спасибо. А вообще расмтаривается как решение выше приведенное предположение о новом списке ?
    – Lolidze
    21 июн 2016 в 10:45
  • 2
    обычно метод reverse не создаёт нового элемента. А меняет исходный. В некоторых реализациях он вообще ничего не меняет в самом контейнере а просто выставляет флаг, который учитывает при других операциях.
    – pavel
    21 июн 2016 в 10:48
  • Я автор задачника, из которого взята эта задача и, по-видимому, преподаватель автора вопроса. У меня к нему меня большая просьба — решайте задачи самостоятельно!
    – velikodniy
    10 янв 2017 в 16:46
  • И да, лучше просто связи перестроить. Вариант с новым списком менее оптимален, но гораздо проще программируется.
    – velikodniy
    10 янв 2017 в 16:53

1 ответ 1

3

Ниже представлены две простые реализации реверса списка (без проверок, оптимизаций и т.д) - итерационная и рекурсивная:

public static void Reverse(ref Node head)
{
    if (head == null) return;

    Node prev = null, current = head, next = null;

    while( current.Next != null )
    {
        next = current.Next;
        current.Next = prev;
        prev = current;
        current = next;
    }

    current.Next = prev;
    head = current;
}

public static void ReverseUsingRecursion(Node head)
{
    if (head == null) return;

    if (head.Next == null)
    {
        newHead = head;
        return;
    }

    ReverseUsingRecursion(head.Next);
    head.Next.Next = head;
    head.Next = null;

}
4
  • У топикастера вопрос про односвязные списки, а не про списки на массивах :)
    – user177221
    27 июн 2016 в 9:08
  • @PashaPash, а что здесь может не сработать в односвязном списке? Разве что static лишний.
    – Mirdin
    27 июн 2016 в 10:10
  • @Mirdin код который был в ответе на момент моего комментария мог вполне не сработать в односвязном списке. посмотрите историю правок.
    – user177221
    27 июн 2016 в 13:47
  • Моя ошибка. ;-) Не досмотрел условия, но я исправился... Спасибо за коммент @PashaPash 27 июн 2016 в 13:50

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.