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

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

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


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

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

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

рассмотрим    в          начале конкретные    данные.          Пусть  массив            будет   заполнен числами 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

И запишем массив после удаления элемента с индексом 3:

2  4  6  4  1  3  7

0  1  2  3  4  5  6

Видно, что размер массива после удаления уменьшился на единицу. Т. е. размер результирующего массива равен (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[4]; newData[4] = data[5]; newData[5] = data[6]; newData[6] = 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 + 1]; newData[4] = data[4 + 1]; newData[5] = data[5 + 1]; newData[6] = data[6 + 1];

Теперь видно, что алгоритм состоит из двух частей. Первая часть – работа с элементами newData с индексами от 0 до 2 включительно, вторая часть – работа с элементами newData с индексами от 3 до 6 включительно.

Для следующего приближения к обобщенному алгоритму сделаем следующую модификацию:

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 + 1];

i = 4;

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

i = 5;

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

i = 6;

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

В  первой  и  во  второй  части  алгоритма i  принимает последовательные

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

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

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

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

newData[i] = data[i];

}

for (int i = 3; i < 7; i++) {

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

}

Возникает вопрос о том, в каком диапазоне лежат возможные значения i.

С учетом того, что в алгоритме написано newData[i], то i должен лежать в диапазоне возможных   индексов   newData,   т. е.   от   0   включительно   до newData.Length не включая. Поэтому 7 можно заменить на newData.Length.

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

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

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

newData[i] = data[i];

}

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

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

}

Теперь вспомним, что 3 – это позиция удаляемого элемента, т. е. delIndex.

Поэтому мы можем заменить 3 на delIndex (естественно введя эту переменную)

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

int delIndex = 3;

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

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

newData[i] = data[i];

}

for (int i = delIndex; 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 delIndex = 3;

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

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

newData[i] = data[i];

}

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

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

}

data = newData;

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

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

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

Для  удаления  нам  необходимо  знать  массив,  из  которого  удаляется элемент и индекс удаляемого элемента. Реализация будет иметь следующий

вид:

public static void delByIndex(ref int[] data, int delIndex) {

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

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

newData[i] = data[i];

}

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

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

}

data = newData;

}

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

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

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

2.  Можно сказать, что удаляемый элемент «дробит» массив на 2 части –

элементы до удаляемого элемента и элементы после удаляемого.

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