Стек на основе списка - C#

Узнай цену своей работы

Формулировка задачи:

Всем привет, нужна ваша помощь в решении следующей задачи: Из элементов двух стеков, хранящих слова, собрать новый стек со словами длины K (задается пользователем),

изменив связи

между элементами стеков (не выделяя новую память). В исходных стеках должны остаться неиспользованные слова. Классы, реализующие список, объединены в пространство имен LinkedListLibrary и находятся в отдельном файле класса ListNode.cs
using System;
 
namespace LinkedListLibrary
{
    class ListNode
    {
        public object Data { get; private set; }
        public ListNode Next { get; set; }
 
        public ListNode(object dataValue)
            : this(dataValue, null)
        {
        }
 
        public ListNode(object dataValue, ListNode nextNode)
        {
            Data = dataValue;
            Next = nextNode;
        }
    }
 
    public class List
    {
        private ListNode firstNode;
        private ListNode lastNode;
        private string name;
 
        public List(string listName)
        {
            name = listName;
            firstNode = lastNode = null;
        }
 
        public List()
            : this("list")
        {
        }
 
        //метод: вставка объекта в начале списка List. Если список пуст, то
        //firstNode и lastNode содержит ссылку на один и тот же объект.
        //Иначе, firstNode содержит ссылку на новый узел.
        public void InsertAtFront(object insertItem)
        {
            if (IsEmpty())
                firstNode = lastNode = new ListNode(insertItem);
            else
                firstNode = new ListNode(insertItem, firstNode);
        }
 
        //метод: вставка объекта в конец списка List
        public void InsertAtBack(object insertItem)
        {
            if (IsEmpty())
                firstNode = lastNode = new ListNode(insertItem);
            else
                lastNode = lastNode.Next = new ListNode(insertItem);
        }
 
        //метод: удаление первого узла из списка List
        public object RemoveFromFront()
        {
            if (IsEmpty())
                throw new EmptyListException(name);
            object removeItem = firstNode.Data; //сохранение данных
            //изменение ссылок firstNode и lastNode
            if (firstNode == lastNode)
                firstNode = lastNode = null;
            else
                firstNode = firstNode.Next;
            return removeItem; //возврат удаленных данных
        }
 
        //метод: удаление последнего узла из списка List
        public object RemoveFromBack()
        {
            if (IsEmpty())
                throw new EmptyListException(name);
            object removeItem = firstNode.Data; 
            if (firstNode == lastNode)
                firstNode = lastNode = null;
            else
            {
                ListNode current = firstNode;
                //выполнять, пока current.Next отлично от lastNode
                while (current.Next != lastNode)
                    current = current.Next;
                //current становится новым значением lastNode
                lastNode = current;
                current.Next = null;
            }
            return removeItem; 
        }
 
        //метод: возврат true, если список List путой
        public bool IsEmpty()
        {
            return firstNode == null;
        }
 
        //метод: вывод содержимого списка List
        public void Display()
        {
            if (IsEmpty())
                Console.WriteLine("Пустой " + name);
            else
            {
                Console.Write("список {0} содержит: ", name);
                ListNode current = firstNode;
                while (current != null)
                {
                    Console.Write(current.Data + " ");
                    current = current.Next;
                }
                Console.WriteLine("\n");
            }
        }
    }
 
    public class EmptyListException : Exception
    {
 
        public EmptyListException()
            : base("Список пустой")
        {
        }
 
        public EmptyListException(string name)
            : base("Список " +  name + " пустой")
        {
        }
    }
}
Класс StackInheritance для работы со стеком объединен в пространство имен StackInheritanceLibrary и находится в отдельном файле класса StackInheritance.cs. Работа со стеком реализуется наследованием от класса List.
using System;
using LinkedListLibrary;
 
namespace StackInheritanceLibrary
{
    public class StackInheritance : List
    {
        public StackInheritance()
            : base("stack") { }
 
        public StackInheritance(string n)
            : base(n) { }
 
        public void Push(object dataValue)
        {
            InsertAtFront(dataValue);
        }
 
        public object Pop()
        {
            return RemoveFromFront();
        }
    }
}
Класс StackInheritanceTest для тестирования работы со стеком.
using System;
using StackInheritanceLibrary;
using LinkedListLibrary;
 
class StackInheritanceTest
{
    public static void Main()
    {
        StackInheritance stack = new StackInheritance("stack1");
        stack.Push("Рот");
        stack.Push("Нет");
        stack.Push("Да");
        stack.Push("no");
 
        StackInheritance stack2 = new StackInheritance("stack2");
        stack2.Push("На");
        stack2.Push("но");
 
        StackInheritance stack3 = new StackInheritance("stack3");
 
        Console.WriteLine("Содержимое стеков до: ");
        stack.Display();
        stack2.Display();
        stack3.Display();
 
        Console.Write("Введите число: ");
        int k = Convert.ToInt32(Console.ReadLine());
 
        //здесь нужно вызвать метод, который будет решать поставленную задачу
 
        Console.WriteLine("\nСодержимое стеков после: ");
        stack.Display();
        stack2.Display();
        stack3.Display();
    }
}
Долго сидел над задачей, в классе List добавил свойство, чтобы получить ссылку на первый элемент стека:
        public ListNode FirstNode 
        {
            get {return firstNode;}
        }
но для этого мне пришлось внести изменения в класс ListNode, сделав его открытым (преподаватель сказал, что этим я нарушил принципы ООП, но я не знаю, как иначе получить доступ к firstNode). Затем в классе StackInheritance я создал метод, который проходится по всему стеку и копирует слова длины k в новый стек:
        public void Move(int k, StackInheritance stack)
        {
            ListNode c = FirstNode;
 
            while (c != null)
            {
                string temp = (string)c.Data;
                if (temp.Length == k)
                    stack.Push(c.Data);
                c = c.Next;
            }
        }
но я не изменяю связи, как это требуется в задании, поэтому в исходных стеках все остается без изменений, а должны остаться только неиспользованные слова. Я понимаю, что нужно изменить метод таким образом, чтобы firstNode.Next указывал на следующий эл-т стека длины k, но для этого мне нужно хранить все ссылки и потом как-то вывести то, что осталось в исходном стеке. У меня не получается это сделать.

Решение задачи: «Стек на основе списка»

textual
Листинг программы
        public void Delete(int k)
        {
            ListNode prev = null;
            ListNode cur = firstNode;
 
            while (cur != null)
            {
                // Иначе не узнать длину строки, с другими типами не будет работать
                string data = (string)cur.Data;
 
                if (data.Length == k)
                {
                    if (prev == null) // Удаляем первый элемент
                    {
                        firstNode = cur.Next;
                        cur = firstNode;
                        continue;
                    }
 
                    // Перебрасываем ссылку 
                    prev.Next = cur.Next;
                    cur = prev.Next;
                }
                else
                {
                    // Сдвигаемся на следующий элемент
                    prev = cur;
                    cur = cur.Next;
                }
            }
        }

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

8   голосов , оценка 3.625 из 5
Похожие ответы