Название: Алгоритмическое мышление при решении задач (Шамшев А. Б.)

Жанр: Информационные системы и технологии

Просмотров: 1387


Задача 7: вставить элемент в массив по индексу.

В этой задаче неявно подразумевается, что у нас есть массив (пусть будет массив целых чисел (пусть с именем data)), новое значение, которое будет добавлено (пусть это будет newValue), и индекс элемента, в который надо вставить новое значение (пусть это будет insIndex).

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

2,4,6,8,4,1,3,7. И надо значение 3 передвинуть на пятую позицию.

Запишем массив в виде таблицы, в первой строке которой будут написаны значения элементов, а во второй – индексы элементов.

Массив data до вставки:

2  4  6  8  4  1  3  7

0  1  2  3  4  5  6  7

И запишем массив после вставки нового значения:

2  4  6  8  4  3  1  3  7

0  1  2  3  4  5  6  7  8

Размер  массива  после  вставки  увеличился  на  единицу.  Т. е.  размер результирующего  массива  равен  (data.Length  +  1).  И  очевидно,  что  после

вставки массив изменился, если изменился его размер. Назовем получившийся массив именем newData. Тогда алгоритм работы для этого конкретного случая

можно записать в виде:

int[] data = new int[] { 2, 4, 6, 8, 4, 1, 3, 7 }; int[] newData = new int[data.Length + 1]; newData[0] = data[0];

newData[1] = data[1]; newData[2] = data[2]; newData[3] = data[3]; newData[4] = data[4]; newData[5] = 3; newData[6] = data[5]; newData[7] = data[6]; newData[8] = data[7];

Верность        этого   алгоритма       в          этом    конкретном    случае не        вызывает

сомнений.      Для      того,    что      бы       приблизиться к          обобщенному алгоритму,

преобразуем данную запись:

int[] data = new int[] { 2, 4, 6, 8, 4, 1, 3, 7 }; int[] newData = new int[data.Length + 1]; newData[0] = data[0];

newData[1] = data[1]; newData[2] = data[2]; newData[3] = data[3]; newData[4] = data[4]; newData[5] = 3; newData[6] = data[6-1]; newData[7] = data[7-1]; newData[8] = data[8-1];

Верность этого преобразования так же очевидна. Теперь еще преобразуем полученный код.

int[] data = new int[] { 2, 4, 6, 8, 4, 1, 3, 7 };

int[] newData = new int[data.Length + 1];

int i = 0;

newData[i] = data[i];

i = 1;

newData[i] = data[i];

i = 2;

newData[i] = data[i];

i = 3;

newData[i] = data[i];

i = 4;

newData[i] = data[i];

newData[5] = 3;

i = 6;

newData[i] = data[i-1];

i = 7;

newData[i] = data[i-1];

i = 8;

newData[i] = data[i-1];

Верность этого преобразования так же не вызывает сомнений. Теперь для

получения последовательных числе в i воспользуемся циклом. Получим: int[] data = new int[] { 2, 4, 6, 8, 4, 1, 3, 7 }; int[] newData = new int[data.Length + 1];

for (int i = 0; i < 5; i++) {

newData[i] = data[i];

}

newData[5] = 3;

for (int i = 6; i < 9; i++) {

newData[i] = data[i - 1];

}

Видно, что 9 – размер нового массива. А 5 – это позиция вставляемого

элемента. А 6 – это 5+1, т. е. insIndex + 1. Воспользуемся этим для дальнейнего преобразования кода.

int[] data = new int[] { 2, 4, 6, 8, 4, 1, 3, 7 };

int[] newData = new int[data.Length + 1];

int insIndex = 5;

for (int i = 0; i < insIndex; i++) {

newData[i] = data[i];

}

newData[insIndex] = 3;

for (int i = insIndex + 1; i < newData.Length; i++) {

newData[i] = data[i - 1];

}

После вставки нам массив data не нужен, а нужен newData. Т. е. можно

сказать, что в data надо записать newData.

int[] data = new int[] { 2, 4, 6, 8, 4, 1, 3, 7 };

int[] newData = new int[data.Length + 1];

int insIndex = 5;

for (int i = 0; i < insIndex; i++) {

newData[i] = data[i];

}

newData[insIndex] = 3;

for (int i = insIndex + 1; i < newData.Length; i++) {

newData[i] = data[i - 1];

}

data = newData;

Введенная последняя строка (data = newData) очень важна, если выделять

отдельную  процедуру  удаления  элемента.  Она  указывает  на  то,  что  data

изменяется. Т. е. в процедуре появится ключевое слово ref.

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

Реализация будет иметь следующий вид:

public void insertValue(ref int[] data, int insValue, int insIndex) {

int[] newData = new int[data.Length + 1];

for (int i = 0; i < insIndex; i++) {

newData[i] = data[i];

}

newData[insIndex] = insValue;

for (int i = insIndex + 1; i < newData.Length; i++) {

newData[i] = data[i - 1];

}

data = newData;

}

Таким образом логика обобщенного алгоритма следующая: массив делится на 2 части – элементы до вставляемого и после вставляемого. До вставляемого

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

массив.

Отметим  некоторые  важные  следствия  алгоритма  вставки  элемента массива по индексу:

1.  Вставка ведет к увеличению размера массива на 1. Как следствие это ведет к изменению массива.

2.  У  элементов,  которые  находятся  после  вставляемого,  индексация

изменяется на единицу.