C#. Структуры данных

Массив T[]

Что хранит. Последовательность элементов одного типа с фиксированной длиной. Порядок и повторяющиеся значения сохраняются.

Для чего используют. Подходит, когда количество элементов известно заранее: показания датчиков, результаты измерений, сохранённая история событий.

Основные операции

Пример

Всегда нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.
Начало кода для первой задачи будет таким

using System;
using System.Collections.Generic;
using System.Text;

class Program
{
    static void Main()
    {
       string[] t = Console.In.ReadToEnd().Split(
            (char[])null, StringSplitOptions.RemoveEmptyEntries);
        
        int p = 0;
        
        StringBuilder sb = new StringBuilder();

        int n = int.Parse(t[p++]);
        int lo = int.Parse(t[p++]);
        int hi = int.Parse(t[p++]);
        int[] a = new int[n];
        for (int i = 0; i < n; i++)
            a[i] = int.Parse(t[p++]);
        
       ... далее обработка массива
    }
}

Важно. Индексы идут от 0 до Length − 1. Изменение значения не меняет длину массива. У пустого массива нет первого и последнего элемента.

Для этой задачи

• Минимум и максимум. Начальные значения берите из первого элемента непустого массива.
• Большая сумма. Используйте long, если сумма может выйти за диапазон int.

Динамический массив List<T>

Что хранит. Последовательность элементов одного типа, которая может расти и уменьшаться. Сохраняет порядок и повторы.

Для чего используют. Подходит для плейлиста, заказа и списка результатов, когда элементы добавляются или удаляются во время работы.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

List<int> a = new List<int>();
a.Add(10);
a.Add(30);
a.Insert(1, 20);               // Теперь: 10, 20, 30.
a.Remove(10);                  // Теперь: 20, 30.
Console.WriteLine(a[0]);
Console.WriteLine(a.Count);

Вывод:

20
2

Важно. При вставке допустим индекс Count, при чтении, замене и удалении — нет. Во время foreach не добавляйте и не удаляйте элементы того же списка.

Для этой задачи

• Отбор. Добавляйте подходящие значения в новый список. Исходная последовательность при этом сохраняется.

Динамический массив List<T>

Что хранит. Последовательность элементов одного типа, которая может расти и уменьшаться. Сохраняет порядок и повторы.

Для чего используют. Подходит для плейлиста, заказа и списка результатов, когда элементы добавляются или удаляются во время работы.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

List<int> a = new List<int>();
a.Add(10);
a.Add(30);
a.Insert(1, 20);               // Теперь: 10, 20, 30.
a.Remove(10);                  // Теперь: 20, 30.
Console.WriteLine(a[0]);
Console.WriteLine(a.Count);

Вывод:

20
2

Важно. При вставке допустим индекс Count, при чтении, замене и удалении — нет. Во время foreach не добавляйте и не удаляйте элементы того же списка.

Для этой задачи

• Неверный индекс. Сначала проверьте границы. При ошибке не выполняйте изменение списка.

Динамический массив List<T>

Что хранит. Последовательность элементов одного типа, которая может расти и уменьшаться. Сохраняет порядок и повторы.

Для чего используют. Подходит для плейлиста, заказа и списка результатов, когда элементы добавляются или удаляются во время работы.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

List<int> a = new List<int>();
a.Add(10);
a.Add(30);
a.Insert(1, 20);               // Теперь: 10, 20, 30.
a.Remove(10);                  // Теперь: 20, 30.
Console.WriteLine(a[0]);
Console.WriteLine(a.Count);

Вывод:

20
2

Важно. При вставке допустим индекс Count, при чтении, замене и удалении — нет. Во время foreach не добавляйте и не удаляйте элементы того же списка.

Для этой задачи

• Отмена по значению. Один Remove(x) удаляет только первое совпадение, сохраняя остальные повторы.

Массив T[]

Что хранит. Последовательность элементов одного типа с фиксированной длиной. Порядок и повторяющиеся значения сохраняются.

Для чего используют. Подходит, когда количество элементов известно заранее: показания датчиков, результаты измерений, сохранённая история событий.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

int[] a = { 10, 20, 30 };
a[1] = 25;                     // Изменяем второй элемент.
Console.WriteLine(a.Length);   // Длина не изменилась.
Console.WriteLine(string.Join(" ", a));

Вывод:

3
10 25 30

Важно. Индексы идут от 0 до Length − 1. Изменение значения не меняет длину массива. У пустого массива нет первого и последнего элемента.

Для этой задачи

• Номер страницы. Начальный индекс равен (page − 1) × size. Вычисляйте его в long.
• Последняя страница. Конец перебора ограничьте длиной массива.

Словарь Dictionary<TKey, TValue>

Что хранит. Хранит пары «ключ — значение». Ключи уникальны, значения могут повторяться. Ключ обозначает запись и не является её порядковым номером.

Для чего используют. Подходит для настроек, остатков товара, счётчиков посещений: значение нужно быстро находить по имени или идентификатору.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["tea"] = 2;
stock["tea"] += 1;             // Изменяем существующую запись.
int amount;
if (stock.TryGetValue("tea", out amount))
    Console.WriteLine(amount);
Console.WriteLine(stock.ContainsKey("water"));

Вывод:

3
False

Важно. Чтение d[key] требует существующего ключа. Значение 0 и отсутствие записи — разные случаи. Не полагайтесь на порядок обхода словаря.

Для этой задачи

• Добавление и замена. Add и присваивание по ключу по-разному обрабатывают уже существующий ключ.

Словарь Dictionary<TKey, TValue>

Что хранит. Хранит пары «ключ — значение». Ключи уникальны, значения могут повторяться. Ключ обозначает запись и не является её порядковым номером.

Для чего используют. Подходит для настроек, остатков товара, счётчиков посещений: значение нужно быстро находить по имени или идентификатору.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["tea"] = 2;
stock["tea"] += 1;             // Изменяем существующую запись.
int amount;
if (stock.TryGetValue("tea", out amount))
    Console.WriteLine(amount);
Console.WriteLine(stock.ContainsKey("water"));

Вывод:

3
False

Важно. Чтение d[key] требует существующего ключа. Значение 0 и отсутствие записи — разные случаи. Не полагайтесь на порядок обхода словаря.

Для этой задачи

• Счётчик. Новому ключу соответствует 1, знакомому — прежнее значение плюс 1.

Словарь Dictionary<TKey, TValue>

Что хранит. Хранит пары «ключ — значение». Ключи уникальны, значения могут повторяться. Ключ обозначает запись и не является её порядковым номером.

Для чего используют. Подходит для настроек, остатков товара, счётчиков посещений: значение нужно быстро находить по имени или идентификатору.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["tea"] = 2;
stock["tea"] += 1;             // Изменяем существующую запись.
int amount;
if (stock.TryGetValue("tea", out amount))
    Console.WriteLine(amount);
Console.WriteLine(stock.ContainsKey("water"));

Вывод:

3
False

Важно. Чтение d[key] требует существующего ключа. Значение 0 и отсутствие записи — разные случаи. Не полагайтесь на порядок обхода словаря.

Для этой задачи

• Запас. Храните остатки в Dictionary<int, long>. Сначала проверьте возможность выдачи, затем уменьшайте запас.

Словарь Dictionary<TKey, TValue>

Что хранит. Хранит пары «ключ — значение». Ключи уникальны, значения могут повторяться. Ключ обозначает запись и не является её порядковым номером.

Для чего используют. Подходит для настроек, остатков товара, счётчиков посещений: значение нужно быстро находить по имени или идентификатору.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Dictionary<string, int> stock = new Dictionary<string, int>();
stock["tea"] = 2;
stock["tea"] += 1;             // Изменяем существующую запись.
int amount;
if (stock.TryGetValue("tea", out amount))
    Console.WriteLine(amount);
Console.WriteLine(stock.ContainsKey("water"));

Вывод:

3
False

Важно. Чтение d[key] требует существующего ключа. Значение 0 и отсутствие записи — разные случаи. Не полагайтесь на порядок обхода словаря.

Для этой задачи

• Сортировка ключей. Создайте new List<string>(d.Keys), затем вызовите keys.Sort(StringComparer.Ordinal). Этот порядок соответствует условию.

Множество HashSet<T>

Что хранит. Хранит разные значения: каждый элемент присутствует не более одного раза. Порядок элементов не гарантирован.

Для чего используют. Подходит для уникальных посетителей, списка допуска и проверки, встречался ли идентификатор раньше.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

HashSet<int> ids = new HashSet<int>();
ids.Add(7);
ids.Add(9);
ids.Add(7);                    // Повтор не создаёт новый элемент.
Console.WriteLine(ids.Count);
Console.WriteLine(ids.Contains(9));
ids.Remove(9);
Console.WriteLine(ids.Contains(9));

Вывод:

2
True
False

Важно. Множество не хранит количество повторений и не предоставляет доступ по индексу. Для вывода по возрастанию создайте List<int> из множества и вызовите Sort().

Для этой задачи

• Запрос. Contains не добавляет идентификатор и не меняет число разных посетителей.

Множество HashSet<T>

Что хранит. Хранит разные значения: каждый элемент присутствует не более одного раза. Порядок элементов не гарантирован.

Для чего используют. Подходит для уникальных посетителей, списка допуска и проверки, встречался ли идентификатор раньше.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

HashSet<int> ids = new HashSet<int>();
ids.Add(7);
ids.Add(9);
ids.Add(7);                    // Повтор не создаёт новый элемент.
Console.WriteLine(ids.Count);
Console.WriteLine(ids.Contains(9));
ids.Remove(9);
Console.WriteLine(ids.Contains(9));

Вывод:

2
True
False

Важно. Множество не хранит количество повторений и не предоставляет доступ по индексу. Для вывода по возрастанию создайте List<int> из множества и вызовите Sort().

Для этой задачи

• Результат операции. Возвращаемые значения Add и Remove позволяют отличить реальное изменение от повторной команды.

Множество HashSet<T>

Что хранит. Хранит разные значения: каждый элемент присутствует не более одного раза. Порядок элементов не гарантирован.

Для чего используют. Подходит для уникальных посетителей, списка допуска и проверки, встречался ли идентификатор раньше.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

HashSet<int> ids = new HashSet<int>();
ids.Add(7);
ids.Add(9);
ids.Add(7);                    // Повтор не создаёт новый элемент.
Console.WriteLine(ids.Count);
Console.WriteLine(ids.Contains(9));
ids.Remove(9);
Console.WriteLine(ids.Contains(9));

Вывод:

2
True
False

Важно. Множество не хранит количество повторений и не предоставляет доступ по индексу. Для вывода по возрастанию создайте List<int> из множества и вызовите Sort().

Для этой задачи

• Пересечение A и B. Элементы, которые есть и в A, и в B.
• Разность A и B. Элементы A, которых нет в B. Порядок A и B важен.
• Объединение. Все элементы A и B без повторов. Операции можно реализовать через foreach, Contains и Add.

Очередь Queue<T>

Что хранит. Хранит элементы в порядке поступления. Первым извлекается самый ранний добавленный элемент: FIFO.

Для чего используют. Подходит для очереди печати, заявок и фоновых заданий, которые нужно обслуживать по очереди.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Queue<int> q = new Queue<int>();
q.Enqueue(10);
q.Enqueue(20);
Console.WriteLine(q.Peek());   // Только смотрим на первый.
Console.WriteLine(q.Dequeue());
Console.WriteLine(q.Count);

Вывод:

10
10
1

Важно. Перед Peek и Dequeue проверьте Count > 0. Повторяющиеся значения — отдельные элементы очереди.

Для этой задачи

• Просмотр и печать. Peek оставляет документ в очереди, Dequeue удаляет его.

Очередь и словарь вместе

Что хранит. Очередь хранит порядок идентификаторов, а словарь связывает каждый идентификатор с его текущими данными. Эти коллекции отвечают на разные вопросы об одних записях.

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

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Queue<int> order = new Queue<int>();
Dictionary<int, int> remaining = new Dictionary<int, int>();
order.Enqueue(42);
remaining[42] = 3;
int id = order.Dequeue();      // Очередь выбирает задание.
remaining[id]--;               // Словарь хранит его данные.
order.Enqueue(id);
Console.WriteLine(remaining[order.Peek()]);

Вывод:

2

Важно. Изменение словаря само по себе не удаляет элемент очереди. При отмене можно пометить состояние, а ненужную запись пропустить при извлечении.

Для этой задачи

• Один шаг. Извлеките первое задание, уменьшите остаток работы и при необходимости верните идентификатор в конец.

Стек Stack<T>

Что хранит. Хранит элементы как стопку. Первым извлекается последний добавленный элемент: LIFO.

Для чего используют. Подходит для возврата к предыдущему экрану, отмены изменений и хранения истории состояний.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Stack<int> history = new Stack<int>();
history.Push(10);
history.Push(20);
Console.WriteLine(history.Peek());
Console.WriteLine(history.Pop());
Console.WriteLine(history.Peek());

Вывод:

20
20
10

Важно. Перед Peek и Pop проверьте Count > 0. Для отмены сохраняют данные предыдущего состояния. Обычный перебор стека идёт от последнего добавленного элемента к первому.

Для этой задачи

• Главный экран. Первую запись истории сохраняйте: возврат допустим только при Count > 1.

Стек Stack<T>

Что хранит. Хранит элементы как стопку. Первым извлекается последний добавленный элемент: LIFO.

Для чего используют. Подходит для возврата к предыдущему экрану, отмены изменений и хранения истории состояний.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Stack<int> history = new Stack<int>();
history.Push(10);
history.Push(20);
Console.WriteLine(history.Peek());
Console.WriteLine(history.Pop());
Console.WriteLine(history.Peek());

Вывод:

20
20
10

Важно. Перед Peek и Pop проверьте Count > 0. Для отмены сохраняют данные предыдущего состояния. Обычный перебор стека идёт от последнего добавленного элемента к первому.

Для этой задачи

• Отмена. Перед новым присваиванием сохраните прежнее значение через Push.

Стек Stack<T>

Что хранит. Хранит элементы как стопку. Первым извлекается последний добавленный элемент: LIFO.

Для чего используют. Подходит для возврата к предыдущему экрану, отмены изменений и хранения истории состояний.

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Stack<int> history = new Stack<int>();
history.Push(10);
history.Push(20);
Console.WriteLine(history.Peek());
Console.WriteLine(history.Pop());
Console.WriteLine(history.Peek());

Вывод:

20
20
10

Важно. Перед Peek и Pop проверьте Count > 0. Для отмены сохраняют данные предыдущего состояния. Обычный перебор стека идёт от последнего добавленного элемента к первому.

Для этой задачи

• Два стека. Один хранит текущие строки, второй — отменённые. UNDO и REDO перемещают элементы между ними.
• Новое действие. Новое APPEND очищает стек отменённых строк через Clear.
• Вывод текста. ToArray возвращает строки от последней к первой; для обычного порядка обходите массив с конца.

Очередь и словарь вместе

Что хранит. Очередь хранит порядок идентификаторов, а словарь связывает каждый идентификатор с его текущими данными. Эти коллекции отвечают на разные вопросы об одних записях.

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

Основные операции

Пример

Для примера нужны using System; и using System.Collections.Generic;. Код выполняется внутри Main.

Queue<int> order = new Queue<int>();
Dictionary<int, int> remaining = new Dictionary<int, int>();
order.Enqueue(42);
remaining[42] = 3;
int id = order.Dequeue();      // Очередь выбирает задание.
remaining[id]--;               // Словарь хранит его данные.
order.Enqueue(id);
Console.WriteLine(remaining[order.Peek()]);

Вывод:

2

Важно. Изменение словаря само по себе не удаляет элемент очереди. При отмене можно пометить состояние, а ненужную запись пропустить при извлечении.

Для этой задачи

• Отменённые заявки. Храните их состояние в словаре и пропускайте их номера при извлечении из очереди.
• Уникальность. Сведения об использованных номерах сохраняйте и после завершения заявки.