Вставка и удаление элемента в массив. Использование языка Free Pascal для обработки массивов
Чтобы пользоваться предварительным просмотром презентаций создайте себе аккаунт (учетную запись) Google и войдите в него: https://accounts.google.com
Подписи к слайдам:
Одномерные массивы Вставка и удаление элемента
Вставка и удаление элементов Алгоритм удаления элемента: определить номер удаляемого элемента - k (ввести с клавиатуры или найти из каких-то условий) сдвинуть все элементы начиная с k -ого на 1 элемент влево последнему элементу массива присвоить значение 0 При удалении элемента размер массива не меняется! Поэтому необходимо далее в программе указывать не до n , а до n -1.
Элемент который нужно удалить дан массив А: 3 5 6 8 12 15 17 18 20 25 k:=4 3 5 6 12 15 17 18 20 25 25 3 5 6 12 15 17 18 20 25 0
const n= 30; var a: array of integer; k, i: integer; begin {ввод массива и k } ... for i:= k to n-1 do a[i] := a; a[n] := 0; writeln( Результат: ); for i:= 1 to n-1 do write (a[i] :3); readln; end .
Алгоритм вставки элемента: (после k -ого) первые k элементов остаются без изменений все элементы, начиная с k -ого сдвигаются на 1 позицию назад на место (k +1)-ого элемента записываем новый элемент. Массив из n элементов, в который вставляется k элементов необходимо определять как массив, имеющий размер n + k . Вставка перед элементом отличается только тем, что сдвигаются все элементы, начиная с k -ого и на место k -ого записываем новый
дан массив А: k:=4 3 5 6 8 8 12 15 17 18 20 25 3 5 6 8 100 12 15 17 18 20 25 1 2 3 4 5 6 7 8 9 10 3 5 6 8 12 15 17 18 20 25 позиция для добавления нового элемента
Пример: Вставить 100 после элемента номер которого вводится с клавиатуры: const n= 30; var a: array of integer; k, i: integer; begin { ввод массива и k} ... for i:= n downto k+1 do a := a[i]; a := 100; writeln( Результат: ); for i:= 1 to n+1 do write (a[i] :3); readln; end .
По теме: методические разработки, презентации и конспекты
«Одномерные массивы: решение задач на добавление и удаление элемента»
Конспект урока разработан для учащихся 10 классов изучающих язык программирования Pascal. В конспекте подробно на примерах объясняется, как можно добавить и удалить элементы в одномерном ма...
Конспект урока по информатике на тему: Технология ввода текста. Редактирование текста: вставка, удаление и замена символов; вставка и удаление пустых строк. Цель урока: научить техноло...
Схема конспекта урока «Одномерные массивы. Ввод и вывод одномерного массива»
Предмет «Информатика» Класс 9 Тема урока «Одномерные массивы. Ввод и вывод одномерного массива»Тип урока: комбинированныйОборудование: компью...
Работа с элементами одномерного массива
Цель урока:формировать и развивать предметные и ключевые компетенции;расширять представление о зоне применения одномерных массивов;повышать культуру написания программ;прививать навыки структурировани...
Урок из серии: “Программирование на языке Паскаль”
Продолжим знакомиться с алгоритмами обработки одномерных массивов
. Сегодня рассмотрим алгоритмы для вставки элементов в массив
. Как и в алгоритмах с удалением элементов, будем различать два случая: вставку одного элемента и вставку нескольких элементов. Алгоритмы получаются разные.
Вставка одного элемента
Вставить элемент можно до или после данного элемента, номер этого элемента можно вводить с клавиатуры или искать при определённых условиях.
Рассмотрим вставку элемента после элемента с данным номером, номер этого элемента будем вводить с клавиатуры.
Рассмотрим несложную задачу.
Пример 1.
В массив, состоящий из n элементов, вставить число b после k-го элемента.
Решение
Рассмотрим на конкретном примере. Пусть дан следующий одномерный массив из 10 (n = 10) элементов:
3, -12, 5, 14, 27, -6, 1, -34, 10, -15.
Вставим число 100 после 5 элемента (b=100, k = 5)
Алгоритм вставки элемента в массив:
- Первые 5 элементов массива остаются без изменений.
- Сдвинуть все элементы, начиная с шестого, на один назад. Но чтобы не потерять соседнее значение, сдвиг будем начинать с последнего элемента – сдвинуть сначала десятый на один вправо, затем девятый, восьмой и т. д. до шестого (m:=m[i], i=n..k).
- На место шестого элемента записываем значение 100, то есть после 5-го элемента массива (m:=b;).
Получим следующий массив:
3, -12, 5, 14, 27, 100, -6, 1, -34, 10, -15.
Таким образом, в массиве стало 11 элементов, то есть массив надо определять на N+1 элемент:
Type myarray = Array Of Integer.
Составим теперь новую процедуру Insert1 (k1, x1, m ), которой передаются: k 1 – номер элемента, после которого надо вставить, х1 – число, которое вставляем, m – массив, в котором делаем преобразования.
Составим основную программу с использованием новой процедуры Insert1 (k1, x1, m).
Мы рассмотрели алгоритм вставки одного элемента в массив. Рассмотрим следующий случай.
Вставка нескольких элементов
Предположим, что необходимо вставлять не один элемент в массив, а по одному элементу после всех элементов с заданным свойством. Рассмотрим следующую задачу.
Пример 2. Вставить число после всех элементов массива, кратных 3.
Первое, на что необходимо обратить внимание – это описание массива: на сколько элементов может увеличиться массив?
Максимальное количество элементов, после которых может быть вставлен новый элемент, совпадает с количеством элементов массива. Так как может случиться, что все элементы массива отвечают заданному свойству. Поэтому массив может увеличиться в два раза (это его самая большая размерность), а значит, соответствующее ему описание будет следующим:
Type myarray = Array Of Integer;
Второе. Если мы будем просматривать элементы массива с начала и вставлять новый после элемента с заданным свойством, то следующим просматриваемым элементом будет новый (вставленный) элемент и его необходимо будет пропускать (“перепрыгивать”). Поэтому решение будет не очень эффективным.
Поэтому лучше всего просматривать массив, начиная с конца, тогда вставляемый элемент мешать не будет. При этом просмотр будет последовательным от N-го до 1-го.
И последнее, на что нужно обратить внимание, это то, что номер последнего элемента после каждой вставки будет меняться. Его нужно будет переопределять. Для этого нужно вести подсчет количества вставленных элементов на данный момент.
Для вставки нескольких элементов в массив составим новую процедуру Insert2
(k1, x1, m
), в которой будет вестись подсчет количества вставленных элементов и корректироваться номер последнего элемента.
Номер последнего элемента необходим для того, чтобы знать, сколько элементов необходимо сдвинуть при освобождении места для нового элемента, так как количество элементов в этой части массива увеличивается.
Ниже представлен текст процедуры с учетом изменений. Параметры у процедуры оставим прежние.
Теперь можно написать программный код основной программы. Он будет следующий:
Вы познакомились с алгоритмами вставки элементов в одномерный массив. На следующем уроке рассмотрим алгоритмы сортировки одномерных массивов.
Теоретический материал
При объявлении массива мы определяем его максимальную размерность, которая в дальнейшем изменена быть не может. Однако с помощью вспомогательной переменной можно контролировать текущее количество элементов, которое не может быть больше максимального.
Замечание . В пространстве имен System.Collection реализована коллекция ArrayList - массив, динамически изменяющий свой размер. Мы будем рассматривать его позже.
Пример . Рассмотрим фрагмент программы:
int a=new int ;
for (int i=0; i<5;i++) a[i]:=i*i;
В этом случае массив можно представить следующим образом:
| n=5 | ||||||||||
| а |
Так как во время описания был определен массив из 10 элементов, а заполнено только первые 5, то оставшиеся элементы будут заполнены нулями.
Что значит удалить из одномерного массива элемент с номером 3? Удаление должно привести к физическому "уничтожению" элемента с номером 3 из массива, при этом общее количество элементов должно быть уменьшено. В этом понимании удаления элемента итоговый массив должен выглядеть следующем образом
В общем случае, если мы хотим удалить элемент массива с номером k (всего в массиве n элементов, а последний элемент имеет индекс n-1), то нам необходимо произвести сдвиг элементов, начиная с k+1-го на одну позицию влево. Т.е. на k-ое место поставить k+1-й элемент, на место k+1 - k+2-й элемент, …, на место n-2 - n-1-й элемент. После чего значение n уменьшить на 1. В этом случае размерность массива не изменится, изменится лишь текущее количество элементов, и у нас создастся ощущение, что элемент с номером k удален. Рассмотрим данный алгоритм на примере:
namespace ConsoleApplication
static int Input ()
int a=new int[n];
for (int i = 0; i < n; ++i)
Console.Write("a[{0}]= ", i);
for (int i = 0; i < n; ++i) Console.Write("{0} ", a[i]);
Console.WriteLine();
static void DeleteArray(int a, ref int n, int m)
for (int i = m; i < n-1; ++i)
static void Main()
int myArray=Input();
int n=myArray.Length;
Print(myArray, n);
Console.WriteLine("Введите номер элемента для удаления:");
DeleteArray(myArray, ref n,m);
Print(myArray, n);
Задание . Подумайте, какие исключительные ситуации могут возникнуть в данной программе и добавьте в нее соответствующие обработки исключительных ситуаций
Рассмотрим теперь операцию удаления в двумерном массиве. Размерность двумерного массива также зафиксирована на этапе объявления массива. Однако при необходимости можно "смоделировать" удаление целой строки в массиве, выполняя сдвиг всех строк, начиная с k-той на единицу вверх. В этом случае размерность массива не изменится, а текущее количество строк будет уменьшено на единицу. В качестве примера удалим из двумерного массива, строку с номером k.
namespace ConsoleApplication
Console.WriteLine("введите размерность массива");
Console.Write("n = ");
n=int.Parse(Console.ReadLine());
Console.Write("m = ");
m=int.Parse(Console.ReadLine());
int [,]a=new int;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
for (int i = 0; i < n; ++i,Console.WriteLine())
for (int j = 0; j < m; ++j)
static void DeleteArray(int[,] a, ref int n, int m, int k)
for (int i = k; i < n-1; ++i)
for (int j = 0; j < m; ++j)
a = a;
static void Main()
Console.WriteLine("Исходный массив:");
Print(myArray, n, m);
DeleteArray(myArray, ref n, m, k);
Console.WriteLine("Измененный массив:");
Print(myArray, n, m);
Задания .
- Измените программу так, чтобы она удаляла k-тый столбец в двумерном массиве.
Рассмотрим модификацию предыдущей программы, для случая, когда используется ступенчатый массив.
namespace ConsoleApplication
Console.WriteLine("введите размерность массива");
Console.Write("n = ");
n=int.Parse(Console.ReadLine());
Console.Write("m = ");
m=int.Parse(Console.ReadLine());
int a=new int[n];
for (int i = 0; i < n; ++i)
a[i]=new int[m];
for (int j = 0; j < m; ++j)
Console.Write("a[{0},{1}]= ", i, j);
for (int i = 0; i < n; ++i,Console.WriteLine())
for (int j = 0; j < m; ++j)
Console.Write("{0,5} ", a[i] [j]);
static void DeleteArray(int a, ref int n, int k)
for (int i = k; i < n-1; ++i)//производим сдвиг ссылок
static void Main()
Console.WriteLine("Исходный массив:");
Print(myArray, n, m);
Console.WriteLine("Введите номер строки для удаления:");
int k=int.Parse(Console.ReadLine());
DeleteArray(myArray, ref n, k);
Console.WriteLine("Измененный массив:");
Print(myArray, n, m);
Вернемся к массиву, определенному в самом первом примере. И подумаем теперь, что значит добавить элемент в одномерный массив в позицию с номером k? В этом случае все элементы, начиная с k-ого, должны быть сдвинуты вправо на одну позицию. Однако сдвиг нужно начинать с конца, т.е. на первом шаге на n-е место поставить n-1-ый элемент, потом на n-1-ое место поставить n-2-й элемент, …, наконец, на k+1 место вставить k-й элемент. Таким образом, копия k-го элемента будет на k+1-м месте и на k-е место можно поставить новый элемент. Затем необходимо увеличить текущее количество элементов на 1.
Рассмотрим массив из примера 1 и в качестве k зададим значение равное 3. В этом случае массив будет выглядеть следующим образом:
| k=3 | ||||||||||
| а |
Теперь в позицию с номером 3 можно поместить новое значение. А текущее количество элементов в массиве становится равным 6. Подумайте, почему сдвиг нужно выполнять с конца массива, а не с начала, как мы это делали в случае удаления элемента из массива.
Рассмотрим программную реализацию данного алгоритма:
namespace ConsoleApplication
static int Input (out int n)
Console.WriteLine("введите размерность массива");
n=int.Parse(Console.ReadLine());
int a=new int; //выделяем памяти больше чем требуется
for (int i = 0; i < n; ++i)
Console.Write("a[{0}]= ", i);
a[i]=int.Parse(Console.ReadLine());
static void Print(int a, int n)
for (int i = 0; i < n; ++i) Console.Write("{0} ", a[i]);
Console.WriteLine();
static void AddArray(int a, ref int n, int m)
for (int i = n; i >= m; --i)
Console.WriteLine("Введите значение нового элемента");
a[m]=int.Parse(Console.ReadLine());
static void Main()
int myArray=Input(out n);
Console.WriteLine("Исходный массив:");
Print(myArray, n);
Console.WriteLine("Введите номер элемента для вставки:");
AddArray(myArray, ref n,m);
Console.WriteLine("Измененный массив:");
Print(myArray, n);
Теперь рассмотрим добавление строки в двумерный массив. Для этого все строки после строки с номером k передвигаем на 1 строку вниз. Затем увеличиваем количество строк на 1. После этого копия строки с номером k будет находиться в столбце с номером k+1. И, следовательно, k-тый столбец можно заполнить новыми значениями. Рассмотрим программную реализацию алгоритма:
namespace ConsoleApplication
static int [,] Input (out int n, out int m)
Console.WriteLine("введите размерность массива");
Console.Write("n = ");
n=int.Parse(Console.ReadLine());
Console.Write("m = ");
m=int.Parse(Console.ReadLine());
//выделяем памяти больше чем необходимо
int [,]a=new int;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
Console.Write("a[{0},{1}]= ", i, j);
a=int.Parse(Console.ReadLine());
static void Print(int[,] a, int n, int m)
for (int i = 0; i < n; ++i,Console.WriteLine())
for (int j = 0; j < m; ++j)
Console.Write("{0,5} ", a);
static void AddArray(int[,] a, ref int n, int m, int k)
for (int i = n; i >=k; --i)
for (int j = 0; j < m; ++j)
a = a;
for (int j=0; j Console.Write("a[{0},{1}]=", k, j); a=int.Parse(Console.ReadLine()); static void Main() int[,] myArray=Input(out n, out m); Console.WriteLine("Исходный массив:"); Print(myArray, n, m); int k=int.Parse(Console.ReadLine()); Console.WriteLine("Измененный массив:"); Print(myArray, n, m); Задания
. Рассмотрим модификацию предыдущей программы для случая, когда используется ступенчатый массив. namespace ConsoleApplication static int Input (out int n, out int m) Console.WriteLine("введите размерность массива"); Console.Write("n = "); n=int.Parse(Console.ReadLine()); Console.Write("m = "); m=int.Parse(Console.ReadLine()); //выделяем памяти больше чем неообходимо int a=new int; for (int i = 0; i < n; ++i) a[i]=new int [m]; for (int j = 0; j < m; ++j) Console.Write("a[{0}][{1}]= ", i, j); a[i][j]=int.Parse(Console.ReadLine()); static void Print(int a, int n, int m) for (int i = 0; i < n; ++i,Console.WriteLine()) for (int j = 0; j < m; ++j) Console.Write("{0,5} ", a[i][j]); static void AddArray(int a, ref int n, int m, int k) for (int i = n; i >=k; --i)//выполняем сдвиг ссылок a[k]=new int[m]; //создаем новую строку Console.WriteLine("Введите элементы новой строки"); for (int j=0; j Console.Write("a[{0}][{1}]=", k, j); a[k][j]=int.Parse(Console.ReadLine()); static void Main() int myArray=Input(out n, out m); Console.WriteLine("Исходный массив:"); Print(myArray, n, m); Console.WriteLine("Введите номер строки для добавления:"); int k=int.Parse(Console.ReadLine()); AddArray(myArray, ref n, m, k); Console.WriteLine("Измененный массив:"); end;
{for i} Рассмотрим алгоритм вставки элемента в массив. Для простоты будем рассматривать только одномерные массивы. Массив состоит из некоторого количества элементов nmax (емкость массива). Текущее количество элементов массива находится в переменной n. Перед вставкой очередного элемента проверяем, что текущее количество элементов массива меньше, чем его емкость. Далее проверяем, вставляется ли элемент в конец массива или нет. Если элемент вставляется в конец массива, то увеличиваем n на единицу и добавляем элемент. Иначе сдвигаем элементы массива индекс которых больше или равен индексу вставляемого элемента, рисунок 3. Приведенный алгоритм реализован в программе, приведенной в листинге 6. Листинг 6 – Вставка элемента в массив {$MODE DELPHI} {$ENDIF} {$APPTYPE CONSOLE} program InsElt;
i
:integer;
//Ввод массива //Элемент для вставки writeln("Vvedite element"
); readln(element);
//Индекс элемента //Вставка элемента if index < n+1 then begin inc(n);
//увеличиваем длину массива if (Low(a) <= index) and (index <= n) then for i:=n downto index do a[i]:=a;
//сдвиг массива a:=element; end //Вывод элементов массива на экран for i:=1 to n do
writeln("a["
, i,"]="
, a[i]:6:2); Удаление элемента происходит аналогично. Сначала проверяется, что индекс элемента не выходит за диапазон допустимых значений, а затем сдвигаются элементы таким образом, чтобы закрыть удаляемый элемент, рисунок 4 Листинг 7 {$MODE DELPHI} {$ENDIF} {$APPTYPE CONSOLE} program DelElt;
const nmax = 5;
//емкость массива i
:integer;
writeln("Vvedite chislo elementov massiva"); readln(n);
//Ввод массива for i:=1 to n do begin write("a["
, i,"]="
); readln(a[i]); //Индекс элемента writeln("Vvedite index elementa"); readln(index);
//Удаление элементов if index if (Low(a) <= index) and (index <= n) then for i:=index to n do a[i]:=a;
//сдвиг массиваdec(n);
//уменьшаем длину массиваend
else begin writeln("Invalid index"
); readln;Вставка и удаление элемента в массив
