Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > .NET для новичков > Создание связного списка

Автор: ДобренькийПапаша 25.1.2010, 14:39

В книге "C# 2008 и платформа .NET 3.5 для профессионалов приведён такой код:"

Код


public class LinkedListNode
    {
        public LinkedListNode(object value)
        {
            this.value = value;
        }

        private object value;
        public object Value
        {
            get { return value; }
        }

        private LinkedListNode next;
        public LinkedListNode Next
        {
            get { return next; }
            set { next = value; }
        }

        private LinkedListNode prev;
        public LinkedListNode Prev
        {
            get { return prev; }
            set { prev = value; }
        }
    }

public class LinkedList : IEnumerable
    {
        private LinkedListNode first;

        public LinkedListNode First
        {
            get { return first; }
        }

        private LinkedListNode last;

        public LinkedListNode Last
        {
            get { return last; }
        }

        public LinkedListNode AddLast(object node)
        {
            LinkedListNode newNode = new LinkedListNode(node);
            if (first == null)
            {
                first = newNode;
                last = first;
            }
            else
            {
                last.Next = newNode;
                last = newNode;
            }
            return newNode;
        }
        
        public IEnumerator GetEnumerator()
        {
            LinkedListNode current = first;

            while (current != null)
            {
                yield return current.Value;
                current = current.Next;
            }            
        }
    }

class Program
    {
        static void Main(string[] args)
        {
            LinkedList list1 = new LinkedList();
            list1.AddLast(1);
            list1.AddLast(2);
            list1.AddLast(3);

            foreach (int i in list1)
            {
                Console.WriteLine(i);
            }
        }
    }

Я никак не пойму каким образом здесь работает foreach. Мы объявляем класс, массива нет ни одного. Где хранятся все значения переданные в list1? Битый час смотрю в код, отлаживаю и ничё не понимаю(((

Автор: KelTron 25.1.2010, 14:56

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

На счёт foreach, если ты посмотришь на эту строку, я думаю многое прояснится:

Код


yield return current.Value;

Автор: ДобренькийПапаша 25.1.2010, 15:29

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

Автор: ДобренькийПапаша 25.1.2010, 15:45

Ещё я не понимаю как в это коде происходит вызов last.Next (55-я строка), если конструктор не вызван: поле объявлено просто как

Код


private LinkedListNode last;

Автор: v1rtu0z 25.1.2010, 15:57

Цитата(ДобренькийПапаша @ 25.1.2010, 16:45)

Код


private LinkedListNode last;

Да в 55й строке происходит не вызов last, а присваивание. А конструируется то что присваивается в 47й строке.
Насчет foreach. Я сам не до конца не понимаю механизм, но обеспечивает возможность перебора интерфейс IEnumerable, который реализует список.
Там еще используется ключевое слово yield, которое

Цитата

Используется в блоке итератора для предоставления значения объекта перечислителя или для сообщения о конце итерации.

Автор: KelTron 25.1.2010, 16:11

Цитата(ДобренькийПапаша @ 25.1.2010, 15:29

)

Я не понимаю как организовано хранение данных в памяти в данном случае.

Тогда бери любой учебник и читай - что такое связный список.
http://ru.wikipedia.org/wiki/Связный_список

Цитата(ДобренькийПапаша @ 25.1.2010, 15:45

)

Что то уж совсем какие то элементарные вещи спрашиваешь...
При чём тут конструктор, ссылке значение можно присвоить где угодно, здесь это происходит в этом куске:

Код


if (first == null)
            {
                first = newNode;
                last = first;
            }
            else
            {
                last.Next = newNode;
                last = newNode;
            }

Тут last и инициализируется.

Автор: KuMa1104 25.1.2010, 20:11

Цитата(ДобренькийПапаша @ 25.1.2010, 14:39

)

В книге "C# 2008 и платформа .NET 3.5 для профессионалов приведён такой код:"

А можно ссылочку откуда вы скачали эту книгу если не сложно. Я как то искал её в нете но только на английском находил(((

Автор: ДобренькийПапаша 25.1.2010, 21:19

Цитата(KuMa1104 @ 25.1.2010, 20:11)

Она у меня в текстовом варианте. Очень хорошая книга. Вообще-то мне всё в книге понятно. Наваждение какое-то с этими списками сегодня.

Никак я не пойму где хранятся числа? Кто-нибудь может ответить где здесь хранится массив(ну или как хотите называйте) чисел? Если мы совершенно отдельно вызываем оператор foreach, проходя по всем элементам, значит они где-то хранятся. Я не могу понять где???

Автор: KuMa1104 25.1.2010, 21:45

ИМХО пусть меня поправят если я не прав.

Цитата(ДобренькийПапаша @ 25.1.2010, 21:19

)

Если мы совершенно отдельно вызываем оператор foreach, проходя по всем элементам, значит они где-то хранятся. Я не могу понять где???

У вас в классе LinkedList хранится ссылка на 1 эл списка в нём(в элементе) ссылка
на 2ой и т.д.

Как я понимаю обекты будут удалены из памяти когда на них не будет ни одной действующей ссылки. А пока они есть всё норм. пока каждый объект ссылается на следующий всё это лежит спокойно в куче.

Автор: ДобренькийПапаша 25.1.2010, 22:03

Цитата(KuMa1104 @ 25.1.2010, 21:45)

Я там вижу две ссылки: first и last. Вот собственно два числа тут хранится могут. Но мы добавляем там третье. Первое присваивается first, второе присваивается last и третье тоже присваивает last. Каким образом там сдвиг происходит с помощью Next не понимаю.

Стыдно, конечно. Но лучше такие вещи понять поздно, чем никогда.

Автор: KuMa1104 25.1.2010, 22:17

Код


private  LinkedListNode first;
 private LinkedListNode last;

это же не числа а классы.

Цитата(ДобренькийПапаша @ 25.1.2010, 22:03

)

KelTron это уже приводил.

Код


if (first == null)
            {
                first = newNode;
                last = first;
            }
            else
            {
                last.Next = newNode;
                last = newNode;
            }

Когда происходит
list1.AddLast(3);
то у нас newNode это ваш 3 элемент.Теперь список не заканчиваеться на 2м элементе и мы показываем это last.Next = newNode; т.е есть 3 элемент.
И устанавливаем в last ссылку на последний эл.

Эл1(имет в себе ссылку на эл 2)

Эл2(имет в себе ссылку на эл 3)

Эл3 является последним.

У нас список из 3х эл.

Класс содержит в себе указатели на начальный и конечный эл списка
first - 1й
last -3й.