Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
«Двусвязный список», «Двусвязный кольцевой список
Задача работы: овладеть навыками составления структур АТД «дерево» и написания программ по исследованию АТД «дерево» на любом языке программирования.
Порядок работы :
Краткая теория
В односвязном списке можно передвигаться только в сторону конца списка. Узнать адрес предыдущего элемента из данного невозможно.
В поле указателя последнего элемента списка находится специальный признак null, свидетельствующий о конце списка.
Рис. - Структура односвязного списка
Кольцевой список, может быть организован на основе как односвязного, так и двухсвязного списков.
Кольцевой односвязный список получается из обычного односвязного спичка путем присваивания указателю последнего элемента списка значение указателя начала списка
Рис. – Структура кольцевого односвязного списка
Операции, производимые над односвязными списками:
Рис. - Структура кольцевого двухсвязного списка
Операции над двусвязными списками:
Реализация списков
Класс LinkedList<T> представляет собой двухсвязный список, в котором каждый элемент ссылается на следующий и предыдущий.
Преимущество связного списка в том, что операция вставки элемента в середину выполняется очень быстро.
При этом только ссылки Next (следующий) предыдущего элемента и Previous (предыдущий) следующего элемента должны быть изменены так, чтобы указывать на вставляемый элемент.
В классе List<T> при вставке нового элемента все последующие должны быть сдвинуты.
Недостатки связных списков:
Вот почему LinkedList<T> содержит элементы типа LinkedListNode<T>.
С помощью класса LinkedListNode<T> появляется возможность обратиться к предыдущему и последующему элементам списка.
класс LinkedList<T> определяет члены для доступа к первому (First) и последнему (Last) элементам в списке, для вставки элементов в определенные позиции и для удаления элементов из заданных позиций, для нахождения элементов, начиная поиск либо с начала, либо с конца списка.
В классе LinkedList<T> определяются два приведенных ниже открытых конструктора:
public LinkedList()
public LinkedList(IEnumerable<T> collection)
В первом конструкторе создается пустой связный список, а во втором конструкторе — список, инициализируемый элементами из коллекции collection.
Наиболее часто используемые методы, определенные в классе LinkedList<T>:
AddAfter() Добавляет в список узел со значением непосредственно после указанного узла. Указываемый узел не должен быть пустым (null). Метод возвращает ссылку на узел, содержащий значение.
AddBefore() Добавляет в список узел со значением value непосредственно перед указанным узлом. Указываемый узел не должен быть пустым (null). Метод возвращает ссылку на узел, содержащий значение.
AddFirst(), AddLast() Добавляют узел со значением в начало или в конец списка.
Find() Возвращает ссылку на первый узел в списке, имеющий передаваемое значение. Если искомое значение отсутствует в списке, то возвращается пустое значение.
Remove() Удаляет из списка первый узел, содержащий передаваемое значение. Возвращает логическое значение true, если узел удален, т.е. если узел со значением обнаружен в списке и удален; в противном случае возвращает логическое значение false.
использования связных списков:
using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
// Создадим связный список
LinkedList<string> link = new LinkedList<string>();
// Добавим несколько элементов
link.AddFirst("Квадрат");
link.AddFirst("Круг");
link.AddFirst("Треугольник");
link.AddFirst("ромб");
// Отобразим элементы в прямом направлении
LinkedListNode<string> node;
Console.WriteLine("Элементы коллекции в прямом направлении: ");
for (node = link.First; node != null; node = node.Next)
Console.Write(node.Value + "\t");
// Отобразить элементы в обратном направлении
Console.WriteLine("\n\nЭлементы коллекции в обратном направлении: ");
for (node = link.Last; node != null; node = node.Previous)
Console.Write(node.Value + "\t");
Console.ReadLine();
}
}
}
Сортированный список:
класс SortedList<TKey, TValue>
В классе SortedList<TKey, TValue> предоставляется немало конструкторов. Ниже перечислены наиболее часто используемые конструкторы этого класса:
public SortedList()создается пустой список с выбираемой по умолчанию первоначальной емкостью.
public SortedList(IDictionary<TKey, TValue> dictionary) создается отсортированный список с указанным количеством элементов dictionary
public SortedList(int capacity)создается с помощью параметра capacity задается емкость коллекции, создаваемой в виде отсортированного списка. Если размер списка заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера списка во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов
public SortedList(IComparer<TK> comparer) допускается указывать с помощью параметра comparer способ сравнения объектов, содержащихся в списке.
Емкость коллекции типа SortedList<TKey, TValue> увеличивается автоматически по мере необходимости, когда в список добавляются новые элементы.
Если текущая емкость коллекции превышается, то она увеличивается. Преимущество указания емкости коллекции типа SortedList<TKey, TValue> при ее создании заключается в снижении или полном исключении издержек на изменение размера коллекции. Разумеется, указывать емкость коллекции целесообразно лишь в том случае, если заранее известно, сколько элементов требуется хранить в ней.
В классе SortedList<TKey, TValue> определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются.
наиболее часто используемых методов этого класса:
Add() Добавляет в список пару "ключ-значение". Если ключ уже находится в списке, то его значение не изменяется, и генерируется исключение ArgumentException
ContainsKey() Возвращает логическое значение true, если вызывающий список содержит объект key в качестве ключа; а иначе — логическое значение false
ContainsValue() Возвращает логическое значение true, если вызывающий список содержит значение value; в противном случае — логическое значение false
GetEnumerator() Возвращает перечислитель для вызывающего словаря
IndexOfKey(), IndexOfValue() Возвращает индекс ключа или первого вхождения значения в вызывающем списке. Если искомый ключ или значение не обнаружены в списке, возвращается значение -1.
Remove() Удаляет из списка пару "ключ-значение" по указанному ключу key. При удачном исходе операции возвращается логическое значение true, а если ключ key отсутствует в списке — логическое значение false.
TrimExcess() Сокращает избыточную емкость вызывающей коллекции в виде отсортированного списка.
Кроме того, в классе SortedList<TK, TV> определяются собственные свойства
Capacity Получает или устанавливает емкость вызывающей коллекции в виде отсортированного списка
Comparer Получает метод сравнения для вызывающего списка
Keys Получает коллекцию ключей
Values Получает коллекцию значений
в классе SortedList<TKey, TValue> реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary<TKey, TValue>
public TValue this[TKey key] { get; set; }
Этот индексатор служит для получения и установки значения элемента коллекции, а также для добавления в коллекцию нового элемента. Но в данном случае в качестве индекса служит ключ элемента, а не сам индекс.
пример использования сортированного списка:
using System;
using System.Collections.Generic;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
// Создадим коллекцию сортированного списка
SortedList UserInfo = new SortedList();
// Добавим несколько элементов в коллекию
UserInfo.Add("Alex", "12345");
UserInfo.Add("dm123", "hg78");
UserInfo.Add("Zaya", "98765");
// Коллекция ключей
ICollection keys = UserInfo.Keys;
// Теперь используем ключи, для получения значений
foreach (string s in keys)
Console.WriteLine("User: {0}, Password: {1}",s,UserInfo[s])
Console.ReadLine();
}
}
Задания
Варианты:
|
Поменять местами первый и последний элементы списка |
|
|
Создать кольцевой список. Добавить элемент @ после пятого элемента списка |
|
|
Удалить элемент, который находится в середине двусвязного списка. |
|
|
Создать список. Удалить каждый второй элемент списка. если нечетное число элементов, а если четное, то два средних. |
|
|
Вставить символ '*' в середину кольцевого списка, если четное число элементов, а если нечетное, то после среднего элемента. |
|
|
Создать двусвязный список. Между шестым и седьмым элементом вставить 0. |
|
|
Создать список. Заполнить его символами A, B, C, D, E, F, G. Удалить второй, пятый элемент. Результаты вывести на экран. |
|
|
Удалить четвертый элемент кольцевого списка. После седьмого элемента добавить ТУЧА. |
|
|
Создать двусвязный список. Второй элемент заменить на СЕССИЯ. Удалить последний элемент. Резальтаты проверить. |
|
|
Создать список. Найти предпоследний элемент и вставить после него ЗАЧЁТ. |
|
|
Удалить элемент, который находится в начале списка, если нечетное число элементов, а если четное, то два средних |
|
|
Создать список. Заполнить его элементами : Север, запад, восток. Очистить список. Результаты вывести на экран. |
|
|
Создать список. Найти предпоследний элемент и вставить после него STOP. |
|
|
Удалить третий элемент кольцевого списка. Добавить в середину списка ДЕД, РЕПА. |
|
|
Создать кольцевой список. Удалить все элементы списка, равные последнему. |
|
|
Создать список. Первый, третий, первый, трети элементы заменить на F |
|
|
Используя стек, напечатайте символы в обратном порядке. |
|
|
Удалить третий элемент кольцевого списка. После первого элемента добавить МИР, ТРУД, МАЙ |
|
|
Создать двусвязный список. Пятый элемент заменить на $. |
|
|
Создать список. Заполнить его элементами : ВОЙНА, МАЙ, ПОБЕДА. Результаты вывести на экран. |
|
|
Удалить элемент, который находится в начале списка, если нечетное число элементов, а если четное, то два средних |
|
|
Создать список. Заполнить его элементами : СЕВЕР, ЗАПАД, ЮГ, ВОСТОК. Очистить список. Результаты вывести на экран. |
|
|
24. |
|
|
25 |