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

Внутренняя строка является самостоятельным объектом. Несколько позиций внешнего массива могут ссылаться на один объект, перестановка строк меняет только ссылки, а замена одной позиции не перенаправляет остальные псевдонимы. Поверхностная копия создаёт только новый внешний массив; независимая глубокая копия разрывает общие строки, а структурная глубокая копия создаёт новые объекты, но сохраняет топологию совместного использования внутри результата.

Выбор между T[,] и T[][] является частью спецификации данных. Прямоугольный массив гарантирует одинаковую длину строк и существование каждой позиции; зубчатый хранит только реальные элементы нерегулярной формы, но требует дополнительных объектов, ссылок и проверок. Свёртка, перенос в прямоугольную форму и транспонирование должны сопровождаться метаданными, достаточными для восстановления null, пустых строк, длин и при необходимости отношений псевдонимов.

Опора — Раздел 18: зубчатые массивы. Дополнительно используются вложенные циклы, инварианты и классы роста из Раздела 12, методы и кортежи из Раздела 13, одномерные массивы и бинарный поиск из Раздела 15, ссылочная семантика, идентичность, глубина копии и null из Раздела 16, прямоугольные массивы и координатные преобразования из Раздела 17.

Каждая задача оформляется отдельной консольной программой полным шаблоном курса и компилируется с <Nullable>enable</Nullable>. Разрешены только конструкции Разделов 1–18. Для структуры, в которой строки могут отсутствовать, используется тип int[]?[]; внешняя ссылка считается ненулевой, если условие не утверждает обратное. Коллекции, LINQ, собственные struct, дополнительные классы, делегаты, лямбда-выражения, Index, Range, Span<T> и обработка исключений запрещены. Внутренняя граница всегда получается из Length текущей строки после проверки null. Каждый метод фиксирует изменение либо сохранение входа, допустимость общих строк, глубину копирования и политику отсутствующих позиций. Потенциально аварийные обращения и намеренно некомпилируемые варианты исследуются только в отдельных копиях проекта.

База практических заданий

Уровень I. Базовый

Число внешних позиций, способ создания строк, их длины, порядок обхода и политика null заданы условием. Требуется точно построить готовую структуру, применять собственную границу каждой строки и проследить указанные изменения ссылок и объектов. Ученик не выбирает представление и глубину копии: сложность возрастает от двухэтапного создания к агрегатам, псевдонимам, копированию, треугольным формам и заданным преобразованиям.

1. Двухэтапное создание лесенки: Реализовать:

static int[][] BuildStaircase(int rowCount)

для rowCount >= 0. Сначала создать внешний массив длины rowCount, затем для каждой позиции отдельно создать строку длины row + 1 и заполнить её последовательными целыми числами, продолжающими общую нумерацию от 0. Вывести внешнюю длину, длину каждой строки, общее число элементов и последний присвоенный номер. Инвариант внешнего цикла: строки [0, row) созданы, заполнены и содержат начальный участок сквозной последовательности.

2. Отсутствующая, пустая и непустая строка: Создать int[]?[] data, содержащий null, new int[0] и непустые строки. За один защищённый обход отдельно вычислить:

  • число отсутствующих строк;
  • число пустых строк;
  • число непустых строк;
  • общее число существующих элементов;
  • сумму элементов.

Объяснить порядок проверок: обращение к row.Length допустимо только после установления row is not null, а пустая строка является существующим объектом с длиной 0.

3. Профиль каждой строки: Для int[]?[] data вывести по каждой внешней позиции один из трёх результатов:

  • строка отсутствует;
  • строка существует, но пуста;
  • длина, сумма, минимум и максимум непустой строки.

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

4. Все координаты искомого значения: Для зубчатого массива с возможными null-строками и значения target вывести все пары (row, column), в которых встречается цель, и общее число вхождений. Внутренний цикл запускается только для существующей строки и ограничивается её длиной. При отсутствии совпадений вывести отдельный результат. Инвариант: после обработки внешнего префикса известны все вхождения в полностью просмотренных строках.

5. Одна строка под несколькими именами: Создать:

int[] shared = { 1, 2, 3 };
int[]?[] data =
{
    shared,
    new[] { 8, 9 },
    shared
};

Изменить data[2]![1], затем вывести data[0] и проверить ReferenceEquals(data[0], data[2]). После этого заменить data[2] новым массивом и показать, что data[0] продолжает ссылаться на старую строку. Разделить изменение объекта строки и замену ссылки во внешней ячейке.

6. Перестановка строк без копирования элементов: Реализовать:

static void SwapRows(
    int[]?[] data,
    int first,
    int second)

Метод обменивает две ссылки одной временной переменной и не обходит элементы внутренних массивов. До вызова сохранить псевдонимы двух непустых строк; после подтвердить через ReferenceEquals, что объекты и их содержимое не изменились, а только заняли другие позиции. Проверить также обмен null и пустой строки.

7. Поверхностная и позиционная глубокая копии: Реализовать:

static int[]?[] ShallowCopy(int[]?[] source)

static int[]?[] IndependentDeepCopy(int[]?[] source)

ShallowCopy создаёт новый внешний массив с теми же ссылками. IndependentDeepCopy сохраняет null, но для каждой существующей внешней позиции создаёт отдельную копию строки; если две позиции источника разделяли один объект, в результате они становятся независимыми. После копирования изменить исходную строку и строку глубокой копии, затем сравнить внешние и внутренние ссылки.

8. Разворот каждой существующей строки: Реализовать:

static void ReverseRows(int[]?[] data)

Каждая существующая строка разворачивается на месте двумя индексами; null, пустая и одноэлементная строки не требуют особого результата. Предусловие задачи: разные внешние позиции не ссылаются на одну строку. Объяснить, почему без этого предусловия один общий объект мог бы быть развёрнут несколько раз.

9. Треугольник Паскаля: Построить первые rowCount строк треугольника Паскаля как long[][]. Строка row имеет длину row + 1, крайние элементы равны 1, внутренние вычисляются:

crow,column=crow−1,column−1+crow−1,column.c_{row,column} = c_{row-1,column-1} + c_{row-1,column}.

Подтвердить симметрию каждой строки и сумму строки:

∑column=0rowcrow,column=2row\sum_{column=0}^{row} c_{row,column}=2^{row}

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

10. Прямоугольная таблица и массив строк: Реализовать:

static int[][] ToJagged(int[,] source)

static int[,] ToRectangular(int[][] source)

ToJagged создаёт по одной строке длины source.GetLength(1) для каждой строки таблицы. ToRectangular имеет предусловие: все строки существуют и обладают одинаковой длиной; пустой внешний массив восстанавливается как таблица формы 0 × 0. Выполнить полный круг преобразований и подтвердить форму и поэлементное равенство.

11. Удаление заполнителя из прямоугольной формы: Дана int[,] source, где в каждой строке значащие элементы образуют префикс, а первое значение -1 и весь хвост после него являются заполнителем. По заданному двухпроходному алгоритму построить int[][]:

  1. определить длину значащего префикса каждой строки;
  2. создать строку точного размера и перенести значения.

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

12. Компактная свёртка с массивом смещений: Для int[]?[] data построить:

static (
    int[] values,
    int[] offsets) Flatten(int[]?[] data)

offsets имеет длину data.Length + 1:

offsets0=0,offsets_0=0, offsetsi+1=offsetsi+{0,datai равно null,datai.Length,иначе.offsets_{i+1} = offsets_i + \begin{cases} 0,&data_i\text{ равно }null,\\ data_i.Length,&\text{иначе}. \end{cases}

values содержит все существующие элементы в порядке строк. Для строки i её элементы занимают полуинтервал [offsets[i], offsets[i + 1]). Подтвердить неубывание offsets, равенство последнего смещения длине values и сохранение последовательности элементов. Зафиксировать, что одних values и offsets недостаточно для различения null и пустой строки.

Уровень II. Продвинутый

Условие описывает данные или требуемое преобразование, но не готовую форму, число проходов, политику пропусков и глубину копирования. Требуется самостоятельно выбрать прямоугольное либо зубчатое представление, вывести длины строк результата и определить метаданные, достаточные для восстановления. В отличие от Уровня I ученик проектирует структуру данных и доказывает, какая информация сохраняется, а какая осознанно теряется.

1. Группы переменного размера: Даны int[] sizes и int[] values, причём сумма неотрицательных размеров должна равняться values.Length. Спроектировать:

static bool TryBuildGroups(
    int[] sizes,
    int[] values,
    out int[][] groups,
    out long[] groupSums)

Отрицательный размер либо несогласованная общая длина дают false и пустые результаты. Нулевой размер создаёт пустую строку. При успехе каждый элемент values переносится ровно один раз и сохраняет порядок внутри своей группы.

2. Распределение длин строк: Для int[]?[] data вернуть:

  • число null-строк;
  • число пустых строк;
  • int? минимальной и максимальной длины существующей строки;
  • int[] frequencies, где индекс равен длине существующей строки.

Самостоятельно определить число проходов: до создания frequencies требуется узнать максимальную длину. Если существующих строк нет, экстремумы равны null, а массив частот пуст.

3. Устойчивая сортировка строк по форме: Упорядочить внешний массив на месте по правилам:

  1. сначала null;
  2. затем существующие строки по неубыванию длины;
  3. при равной длине — по неубыванию суммы.

Использовать устойчивую сортировку вставками и перемещать только ссылки. До сортировки сохранить псевдонимы нескольких строк; после подтвердить идентичность объектов. При полном равенстве ключей исходный порядок должен сохраниться.

4. Вертикальные агрегаты нерегулярной структуры: Для int[]?[] data построить:

static (
    long[] sums,
    int[] counts,
    double?[] means) BuildColumnProfiles(int[]?[] data)

Логический столбец column включает только строки, в которых эта позиция существует. Длина результатов равна максимальной длине существующей строки. Для столбца без участников среднее равно null; в корректно выбранной ширине такие хвостовые столбцы обычно отсутствуют, но контракт должен оставаться полным.

5. Свёртка с полным восстановлением состояния строк: Спроектировать:

static (
    int[] values,
    int[] offsets,
    bool[] wasNull) Encode(int[]?[] source)

static int[]?[] Decode(
    int[] values,
    int[] offsets,
    bool[] wasNull)

offsets задаёт длины строк, wasNull различает отсутствующую и существующую пустую строку. До декодирования проверить согласованность длин, начального и последнего смещения и неубывание массива. Выполнить полный круг и подтвердить состояния строк и значения. Отношения общих строк сохранять не требуется.

6. Координата по глобальному номеру элемента: Для корректного представления (values, offsets) найти координату элемента с глобальным номером position, где 0 <= position < values.Length. Из-за повторяющихся смещений пустых строк требуется найти индекс:

row=UpperBound⁡(offsets,position)−1,row=\operatorname{UpperBound}(offsets,position)-1,

а затем:

column=position−offsetsrow.column=position-offsets_{row}.

Реализовать UpperBound бинарным поиском и вернуть (row, column). Подтвердить обратное равенство offsets[row] + column == position.

7. Прямоугольная форма с маской и обратное восстановление: Спроектировать преобразование int[]?[] в три объекта:

  • int[,] values минимальной достаточной ширины;
  • bool[,] present, отмечающий реальные элементы;
  • bool[] wasNull, различающий null и существующую пустую строку.

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

8. Компактное транспонирование: Для зубчатого массива без null-строк построить результат, где строка column содержит source[row][column] только для тех исходных строк, у которых позиция существует. Пропуски удаляются. Самостоятельно определить:

  • число строк результата;
  • длину каждой строки;
  • порядок элементов.

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

9. Транспонирование с сохранением пропусков: Для int[]?[] source построить int?[][] result. Число строк равно максимальной длине существующей исходной строки; каждая строка результата имеет длину source.Length:

resultcolumn[row]={sourcerow[column],позиция существует,null,иначе.result_{column}[row] = \begin{cases} source_{row}[column],&\text{позиция существует},\\ null,&\text{иначе}. \end{cases}

Отдельный bool[] wasNull сохраняет состояние исходных строк. Спроектировать обратное преобразование и подтвердить восстановление формы, null, пустых строк и значений.

10. Сжатое хранение симметричной матрицы: Квадратная симметричная таблица порядка n хранится нижним треугольником: строка row имеет длину row + 1 и содержит значения от (row, 0) до (row, row). Спроектировать:

  • проверку симметрии и упаковку;
  • восстановление полной таблицы;
  • чтение элемента (row, column) непосредственно из сжатой формы.

При column > row координаты меняются местами. Сравнить число хранимых элементов:

n2иn(n+1)2.n^2 \quad\text{и}\quad \frac{n(n+1)}{2}.

11. Умножение нерегулярных строк на вектор: Дан int[]?[] rows и вектор int[] weights, длина которого не меньше максимальной длины существующей строки. Построить long?[] result:

  • null-строка даёт null;
  • пустая строка даёт 0;
  • непустая строка даёт скалярное произведение с соответствующим префиксом weights.

Самостоятельно сформулировать инвариант внутреннего цикла и объяснить, почему отсутствующая группа и существующая группа без элементов имеют разные предметные результаты.

12. Выбор формы по спецификации: Для трёх наборов данных письменно выбрать int[,] либо int[][], затем реализовать создание и один содержательный агрегат:

  1. плотная таблица измерений фиксированной ширины;
  2. группы наблюдений переменной длины;
  3. нижний треугольник симметричной матрицы.

Решение должно сравнить гарантии формы, число хранимых элементных ячеек, число объектов массива, необходимость проверок и сложность обхода, а не сводить выбор к различию синтаксиса.

Уровень III. Экспертный

Исследуется не прикладной агрегат, а граф внешних и внутренних объектов, достаточность метаданных либо цена выбранного представления. До сборки и запуска требуется нарисовать ссылки, предсказать идентичность строк, форму результата, число сохранённых элементов и возможную потерю информации; после — объяснить наблюдение через глубину копии, политику обработки псевдонимов и обратимость преобразования.

1. Полная трассировка графа строк: Построить пять внешних позиций:

  • две ссылаются на одну строку;
  • одна — на отдельную строку с тем же содержимым;
  • одна равна null;
  • одна содержит пустой массив.

Затем последовательно:

  1. изменить общий объект;
  2. переставить две внешние позиции;
  3. заменить одну позицию новым массивом;
  4. создать поверхностную копию внешнего массива;
  5. изменить строку через копию.

До запуска составить таблицу содержимого и ReferenceEquals после каждого шага. После объяснить, какие операции меняют внутренний объект, какие — внешнюю ячейку, а какие создают только новый внешний массив.

2. Две модели глубокой копии: Для структуры с общими строками реализовать:

  • независимую копию, создающую отдельный объект для каждой существующей позиции;
  • структурную глубокую копию, создающую одну новую строку на каждый уникальный исходный объект и сохраняющую отношения псевдонимов внутри результата.

Коллекции запрещены: уникальные исходные строки и соответствующие копии хранить в двух параллельных массивах и искать линейно. Результат не должен разделять строки с источником. Сравнить идентичность и оценить худшую сложность.

3. Равенство формы, содержимого и топологии ссылок: Спроектировать три независимых отношения для двух int[]?[]:

static bool HaveSameShape(...)

static bool HaveSameValues(...)

static bool HaveSameAliasPattern(...)

HaveSameShape сравнивает внешнюю длину, состояния null и длины существующих строк. HaveSameValues дополнительно сравнивает элементы. HaveSameAliasPattern требует, чтобы для любых внешних позиций i и j выполнялось:

ReferenceEquals(lefti,leftj)=ReferenceEquals(righti,rightj).ReferenceEquals(left_i,left_j) = ReferenceEquals(right_i,right_j).

До запуска построить примеры, совпадающие по первым двум отношениям, но различающиеся по третьему. Объяснить, почему поэлементное равенство не описывает граф объектов.

4. Обработка по внешним позициям и по уникальным объектам: Реализовать две операции прибавления delta:

  1. первая обходит внешние позиции и изменяет каждую встреченную строку;
  2. вторая изменяет каждый уникальный объект строки ровно один раз.

Для второй версии использовать массив ранее встреченных ссылок и линейный поиск через ReferenceEquals. На структуре с общими строками до запуска предсказать итог. Объяснить, почему первая операция имеет семантику «один раз на позицию», а вторая — «один раз на объект», и почему контракт обязан выбирать одну из них явно.

5. Обратимость двух транспонирований: На нескольких нерегулярных структурах сравнить компактное транспонирование и транспонирование с null-пропусками. Найти две различные исходные структуры с одинаковым компактным результатом. Затем доказать, что сохраняющая пропуски форма вместе с wasNull допускает обратное восстановление. Разделить потерю длин строк, положения пропусков и различия между null и пустой строкой.

6. Перестановка строк по циклам: Дан зубчатый массив и int[] permutation, где строка из старой позиции i должна перейти в новую позицию permutation[i]. Сначала проверить, что массив индексов является перестановкой. Затем выполнить преобразование на месте по циклам, используя bool[] visited и одну временную ссылку; элементы внутренних массивов не копируются. До запуска разложить перестановку на циклы. После доказать, что каждая внешняя позиция записана один раз и все исходные объекты и отношения псевдонимов сохранены.

7. Минимальные метаданные для точного восстановления: Последовательно исследовать четыре представления зубчатой структуры:

  1. только values;
  2. values + offsets;
  3. values + offsets + wasNull;
  4. values + offsets + wasNull + representative.

representative[i] хранит индекс первой внешней позиции, с которой строка i разделяет объект; для null используется отдельное согласованное значение. Для каждого уровня указать, какие свойства можно восстановить: последовательность элементов, длины строк, различие null и пустой строки, топологию псевдонимов. Реализовать точное кодирование и декодирование четвёртого представления без коллекций.

8. Цена треугольного представления: Для нижнетреугольных данных порядка n сравнить:

  • прямоугольный int[n,n];
  • зубчатый массив со строками длины 1,2,\ldots,n.

До запуска вычислить:

Nrect=n2,N_{\mathrm{rect}}=n^2, Njagged=n(n+1)2,N_{\mathrm{jagged}}=\frac{n(n+1)}{2}, saved=1−NjaggedNrect.saved= 1-\frac{N_{\mathrm{jagged}}}{N_{\mathrm{rect}}}.

Для n = 1, 10, 100, 1000 определить долю исключённых элементных ячеек. Затем реализовать одинаковую сумму значимых элементов и подсчитать обращения к элементам. Объяснить компромисс: меньше отсутствующих ячеек против дополнительных объектов, ссылок и нерегулярных границ. Фактический объём памяти и скорость не измерять до Раздела 21.

Обязательные контрольные наборы

ЗадачаИсходные данные
I.1rowCount = 0, 1, 5
I.2[null, [], [3,4], null, [0]]
I.3[null, [], [4,-2,7], [5], [-1,-1]]
I.4[null, [2,5,2], [], [2], [7,2]], цели 2 и 9
I.5общий ряд [1,2,3] в позициях 0 и 2
I.6[[1,2], null, [], [7,8,9]], обмены (0,3) и (1,2)
I.7[null, [1,2], shared, shared, []], где shared = [7,8]
I.8[null, [], [1], [1,2,3,4], [5,6,7]] без общих строк
I.9rowCount = 0, 1, 6, 20
I.10таблицы форм 0 × 0, 2 × 0, 2 × 3
I.11[[1,2,-1,-1],[3,4,5,-1],[-1,-1,-1,-1],[6,7,8,9]]
I.12[null, [], [1,2,3], [4], null, [5,6]]
II.1sizes = [3,0,2,4], значения [1,2,3,4,5,6,7,8,9]; отрицательный размер и неверная общая длина
II.2[null, [], [1,2], [3], null, [4,5]]
II.3[null, [5], [1,2], [], [3,4], [9]]
II.4[null, [1,2,3], [], [4], [5,6]]
II.5[null, [], [1,2,3], [4], null, [5,6]]; повреждённые offsets
II.6представление предыдущего набора; все допустимые глобальные позиции
II.7[null, [7,-1], [], [-1,5,9]], fillValue = -1
II.8[[1,2,3],[4],[5,6]]; затем [[1],[2,3]] и [[1,2],[3]]
II.9[null, [1,2,3], [], [4], [5,6]]
II.10симметричные таблицы порядков 0, 1, 4; несимметричная таблица
II.11[null, [], [1,2,3], [4,-1]], weights = [10,20,30]
II.12плотная форма 3 × 4, строки длин [2,5,1], нижний треугольник порядка 5
III.1общий ряд [1,2], отдельная строка [1,2], null, []
III.2[shared, [1,2], null, shared, []], где shared = [7,8,9]
III.3пары с одинаковой формой и значениями, но различной топологией общих строк
III.4[shared, [10], shared, null], где shared = [1,2], delta = 5
III.5структуры из II.8–II.9 и две различные формы с одинаковым компактным транспонированием
III.6строки A,B,C,D,E; перестановки [2,0,1,4,3], тождественная и один цикл длины 5
III.7[shared, null, [], shared, [1,2]], где shared = [7,8]
III.8n = 1, 10, 100, 1000

Итог модуля

Ученик создаёт внешний массив и внутренние строки отдельно, различает null, пустую и непустую строку и получает границу каждого внутреннего обхода из текущего объекта. Он прослеживает общие строки, переставляет ссылки без копирования элементов и различает поверхностную, независимую и структурную глубокую копии, а также обработку по внешним позициям и по уникальным объектам. Представление T[,] либо T[][] выбирается по гарантированной форме и цене хранения; свёртка, перенос в прямоугольную область и транспонирование сопровождаются явной политикой пропусков и метаданными, достаточными для восстановления длин, null, пустых строк и при необходимости топологии псевдонимов.

Покрытие опоры и границы

  • Синтаксис T[][], внешний массив ссылок и отдельное создание строк: I.1–I.2.
  • null, пустая и непустая строка, внешняя и внутренняя длина: I.2–I.4, II.2, III.1.
  • Защищённый вложенный обход и собственная граница каждой строки: I.2–I.4, I.8–I.12, II.1–II.12.
  • Несколько ссылок на одну строку, изменение объекта и замена внешней ссылки: I.5–I.8, III.1–III.4.
  • Перестановка строк без копирования элементов: I.6, II.3, III.6.
  • Поверхностная, независимая и структурная глубокая копии: I.7, III.2–III.3.
  • Треугольные и иные нерегулярные структуры: I.9, II.10, II.12, III.8.
  • Перенос между T[,] и T[][]: I.10–I.11, II.7.
  • Свёртка, offsets, обратное восстановление и поиск координаты: I.12, II.5–II.6, III.7.
  • Вертикальные агрегаты и алгоритмы над логическими столбцами: II.4, II.11.
  • Компактное и сохраняющее пропуски транспонирование: II.8–II.9, III.5.
  • Выбор прямоугольной или зубчатой формы: II.12, III.8.
  • Достаточность метаданных и обратимость преобразований: II.5, II.7–II.9, III.5 и III.7.
  • Сравнение формы, содержимого и топологии ссылок: III.3.
  • Цена дополнительных объектов, ссылок, проверок и исключённых ячеек: II.10–II.12, III.2, III.4 и III.8.

За границей: строки как текстовые последовательности рассматриваются в Модуле 9, а собственные структуры — в Модуле 10. Массивы произвольной вложенности, рекурсивные графы объектов, обобщённые коллекции, LINQ, Span<T>, специализированные разреженные форматы и низкоуровневая оценка фактической памяти относятся к последующим курсам. Зубчатый массив не считается автоматически более быстрым или более экономным: вывод ограничивается числом элементных позиций, объектов, ссылок и выполняемых операций до проведения измерений в Разделе 21.