Лекция 12 Одномерные массивы переменной длины. Вставка и удаление элементов. ЛР 18. Операции, изменяющие длину массива Индивидуальный проект КЭИ УлГТУ 1 курс Власенко Олег Федосович SimbirSoft
Массив состоит из элементов одного и того же типа. Массивы определяются так: int a[100]; char b[20]; float d[50]; В первой строке объявлен массив а из 100 элементов целого типа: а[0], а[1],..., а[99] (индексация всегда начинается с нуля). Во второй строке элементы массива b имеют тип c h ar. Чтобы обратиться к конкретному элементу массива нужно записать так: a[7] = 10 ; a[9] = a[10] + 1; В качестве индекса можно использовать переменную целого типа, либо любое целочисленное выражение, например такое: a[ i ] = 10 ; a[j + 1] = a[j];
// Координаты грибов // количество грибов #define NUM_MUSHROOMS 12 // координата Х каждого гриба int MushroomX [ NUM_MUSHROOMS ] = { 200, 220, 240, 260, 300, 400, 420, 440, 460, 480, 500, 520 }; // координата Y каждого гриба int MushroomY [ NUM_MUSHROOMS ] = { 400, 350, 300, 250, 300, 200, 100, 200, 100, 140, 120, 100 }; // виден ли гриб? (для каждого гриба!) int MushroomVisible [ NUM_MUSHROOMS ] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }; В игре нужно собрать все грибы. В массивах MushroomX и Mushroom Y хранятся координаты каждого гриба. В массиве MushroomVisible хранится признак – «виден» / «не виден».
void DrawMushroom ( HDC hdc, int cx, int cy ) { // Гриб // Шляпка гриба HPEN hPenMushroom1 = CreatePen ( PS_SOLID, 3, RGB (136, 0, 21)); SelectObject ( hdc, hPenMushroom1); Chord( hdc, -15 + cx, -15 + cy, 15 + cx, 15 + cy, 15 + cx, 0 + cy, -15 + cx, 0 + cy ); DeleteObject (hPenMushroom1); // Ножка гриба HPEN hPenMushroom2 = CreatePen ( PS_SOLID, 3, RGB (127, 127, 127)); SelectObject ( hdc, hPenMushroom2); Rectangle( hdc, -5 + cx, 0 + cy, 5 + cx, 15 + cy ); DeleteObject (hPenMushroom2); //Rectangle( hdc, cx - 20, cy - 20, cx + 20, cy + 20); } Функция для отрисовки одного гриба по координатам cx, cy
// Отрисовка всех видимых грибов void DrawMushrooms ( HDC hdc ) { for ( int i = 0; i < NUM_MUSHROOMS; ++ i ) { // если i гриб виден (не съеден) if ( MushroomVisible [ i ]) { // отрисовываем i гриб DrawMushroom ( hdc, MushroomX [ i ], MushroomY [ i ]); } } } Отрисовка всех видимых грибов
case WM_PAINT : { PAINTSTRUCT ps ; HDC hdc = BeginPaint ( hWnd, & ps ); // TODO: Добавьте сюда любой код прорисовки, использующий HDC... DrawMushrooms ( hdc ); DrawKnife ( hdc, 140, 85); DrawKnife ( hdc, 180, 85); DrawKnife ( hdc, 180, 285); DrawApples ( hdc ); DrawHedgehog ( hdc, HedgehogX, HedgehogY ); DrawFox ( hdc, FoxX, FoxY ); EndPaint ( hWnd, & ps ); } break ; Вызов отрисовки грибов
// пытаемся съесть гриб void TryToEatMushroom () { // пробегаем по всем грибам for ( int i = 0; i < NUM_MUSHROOMS; ++ i ) { // если i гриб виден if ( MushroomVisible [ i ]) { // если ежик может съесть i гриб if ( HedgehogX - 20 < MushroomX [ i ] && HedgehogX + 20 > MushroomX [ i ] && HedgehogY - 20 < MushroomY [ i ] && HedgehogY + 20 > MushroomY [ i ]) { // i гриб делаем невидимым - его съели!!! MushroomVisible [ i ] = 0; } } } } Попытка съесть гриб
// подсчитать количество видимых (не съеденных) грибов int CountVisibleMushrooms () { // счетчик видимых грибов int count = 0; // пробегаем по всем грибам for ( int i = 0; i < NUM_MUSHROOMS; ++ i ) { // если i гриб видим - счетчик увеливаем на 1 if ( MushroomVisible [ i ]) { ++count; } } // возвращаем количество видимых (не съеденных) грибов return count; } Подсчет видимых (еще несъеденных) грибов
// Сообщение "Клавишу нажали" case WM_KEYDOWN : switch ( wParam ) { case VK_UP : HedgehogY -= 10; InvalidateRect ( hWnd, NULL, TRUE ); break ; case VK_DOWN : HedgehogY += 10; InvalidateRect ( hWnd, NULL, TRUE ); break ; } TryToEatMushroom (); if ( CountVisibleMushrooms () == 0) { PostQuitMessage (0); } TryToEatApple (); break ; Попытка съесть гриб и проверка - все ли грибы съедены?
Создается массив длиной NUM_ELEMENTS элементов. И создается переменная n в которой хранится количество используемых элементов. И! Все операции выполняются не для всех NUM_ELEMENTS, а только для первых n элементов массива! #include < stdio.h > #include < Windows.h > #define NUM_ELEMENTS 10 int arr [ NUM_ELEMENTS ]; int n = 0; void printElements () { printf ( "< " ); for ( int i = 0; i < n ; i++ ) { printf ( "%d ", arr [ i ]); } printf ( "> \ n" ); } void main() { printElements (); }
void addLastElement ( int value ) { arr [ n++ ] = value ; } void main() { printElements (); addLastElement ( 8 ); printElements (); addLastElement ( 9 ); printElements (); addLastElement ( 9 ); printElements (); } Если количество элементов может изменяться, то добавляются операции ДОБАВЛЕНИЯ и УДАЛЕНИЯ элементов.
void deleteLastElement () { n-- ; } void main() { printElements (); addLastElement ( 8 ); printElements (); addLastElement ( 9 ); printElements (); addLastElement ( 9 ); printElements (); deleteLastElement (); printElements (); deleteLastElement (); printElements (); } Если количество элементов может изменяться, то добавляются операции ДОБАВЛЕНИЯ и УДАЛЕНИЯ элементов.
void keyboardInput () { printf ( "n = " ); scanf_s ( "%d", &n); printf( "input %d values: ", n); for ( int i = 0; i < n; i++ ) { scanf_s ( "%d", & arr [ i ]); } } void main() { printElements (); keyboardInput (); printElements (); deleteLastElement (); printElements (); deleteLastElement (); printElements (); } Иногда нужно значения элементов массива ввести через клавиатуру.
void insertElement ( int insIndex, int value ) { for ( int i = n; i > insIndex ; i -- ) { arr [ i ] = arr [ i - 1]; } n++; arr [ insIndex ] = value ; } void main() { printElements (); addLastElement (1); addLastElement (2); addLastElement (4); printElements (); insertElement (2, 3); printElements (); insertElement (0, 100); printElements (); } Иногда новый элемент нужно вставить в конкретное место в массиве
void insertElement ( int insIndex, int value ) { for ( int i = n; i > insIndex ; i -- ) { arr [ i ] = arr [ i - 1]; } n++; arr [ insIndex ] = value ; } void main() { printElements (); addLastElement (1); addLastElement (2); addLastElement (4); printElements (); insertElement (2, 3); printElements (); insertElement (0, 100); printElements (); } Иногда новый элемент нужно вставить в конкретное место в массиве
void deleteElement ( int delIndex ) { for ( int i = delIndex ; i < n - 1; i ++ ) { arr [ i ] = arr [ i + 1]; } n--; } void main() { printElements (); addLastElement (1); addLastElement (2); addLastElement (4); addLastElement (8); addLastElement (16); printElements (); deleteElement (2); printElements (); deleteElement (0); printElements (); } Иногда нужно удалить элемент, со сдвигом оставшихся
void deleteElement ( int delIndex ) { for ( int i = delIndex ; i < n - 1; i ++ ) { arr [ i ] = arr [ i + 1]; } n--; } void main() { printElements (); addLastElement (1); addLastElement (2); addLastElement (4); addLastElement (8); addLastElement (16); printElements (); deleteElement (2); printElements (); deleteElement (0); printElements (); } Иногда нужно удалить элемент, со сдвигом оставшихся
int findFirstEven () { for ( int i = 0; i < n; i++ ) { if ( arr [ i ] % 2 == 0) { return i ; } } return -1; } void main() { addLastElement (7); addLastElement (5); addLastElement (6); addLastElement (3); addLastElement (4); printElements (); int index = findFirstEven (); printf ( "index of the first even = %d\n", index); arr [index] *= 100; printElements (); } Первый четный элемент увеличить в 100 раз.
int findMin () { int min = arr [0]; for ( int i = 1; i < n; i++ ) { if ( arr [ i ] < min) { min = arr [ i ]; } } return min; } void main() { addLastElement (7); addLastElement (5); addLastElement (6); addLastElement (3); addLastElement (4); printElements (); int min = findMin (); printf ( "min = %d\n", min); } Найти и вывести значение минимального элемента
int findMin () { int min = arr [0]; for ( int i = 1; i < n; i++ ) { if ( arr [ i ] < min) { min = arr [ i ]; } } return min; } void main() { addLastElement (7); addLastElement (5); addLastElement (6); addLastElement (3); addLastElement (4); printElements (); int min = findMin (); printf ( "min = %d\n", min); } Найти и вывести значение минимального элемента
int findIndexMax () { int max = arr [0]; int indexMax = 0; for ( int i = 1; i < n; i++ ) { if ( arr [ i ] > max) { max = arr [ i ]; indexMax = i ; } } return indexMax ; } Поменять местами максимальный и начальный элемент void main() { addLastElement (2); addLastElement (1); addLastElement (3); addLastElement (5); addLastElement (4); printElements (); int index = findIndexMax (); printf ( "index of max = %d\n", index); // перестановка arr [0] <--> max int tmp = arr [0]; arr [0] = arr [index]; arr [index] = tmp ; printElements (); }
int findIndexMax () { int max = arr [0]; int indexMax = 0; for ( int i = 1; i < n; i++ ) { if ( arr [ i ] > max) { max = arr [ i ]; indexMax = i ; } } return indexMax ; } Поменять местами максимальный и начальный элемент void main() { addLastElement (2); addLastElement (1); addLastElement (3); addLastElement (5); addLastElement (4); printElements (); int index = findIndexMax (); printf ( "index of max = %d\n", index);
void main() { addLastElement (2); addLastElement (1); addLastElement (3); addLastElement (5); addLastElement (4); printElements (); int index = findIndexMax (); printf ( "index of max = %d\n", index); // перестановка arr [0] <--> max int tmp = arr [0]; arr [0] = arr [index]; arr [index] = tmp ; printElements (); }
Переставить элементы массива таким образом, чтобы они были упорядочены по возрастанию. Использовать алгоритм «сортировки выбором» https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC void selectionSort () { for (int i = 0; i < n - 1; i ++) { int min_index = i ; for (int j = i + 1; j < size; j++ ) { if ( arr [j] < arr [ min_index ]) { min_index = j; } } if ( min_index != i ) { int tmp = arr [ i ]; arr [ i ] = arr [ min_index ]; arr [ min_index ] = tmp ; } } }
Переставить элементы массива таким образом, чтобы они были упорядочены по возрастанию. Использовать алгоритм «сортировки выбором» https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC void selectionSort () { for (int i = 0; i < n - 1; i ++) { int min_index = i ; for (int j = i + 1; j < size; j++ ) { if ( arr [j] < arr [ min_index ]) { min_index = j; } } if ( min_index != i ) { int tmp = arr [ i ]; arr [ i ] = arr [ min_index ]; arr [ min_index ] = tmp ; } } }
Переставить элементы массива таким образом, чтобы они были упорядочены по возрастанию. Использовать алгоритм «сортировки выбором» https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%8B%D0%B1%D0%BE%D1%80%D0%BE%D0%BC void selectionSort () { for (int i = 0; i < n - 1; i ++) { int min_index = i ; for (int j = i + 1; j < size; j++ ) { if ( arr [j] < arr [ min_index ]) { min_index = j; } } if ( min_index != i ) { int tmp = arr [ i ]; arr [ i ] = arr [ min_index ]; arr [ min_index ] = tmp ; } } }
«Массив переменной длины»
К предыдущему коду (Лабораторная работа №17) добавить операцию удаления заданного элемента массива.
Добавить операцию вставки нового элемента в заданное место
Добавить операцию «Удалить минимальный элемент»
Добавить операцию «Перед минимальным элементом вставить 0»
Добавить операцию «Удалить все четные элементы»
Добавить операцию «Продублировать все четные элементы»
Доделать задачи 1-4. Задача 7*. «Добавить в начало элемент, равный минимальному» Задача 8* Реализовать операцию «Удалить из массива все элементы, значение которых меньше 4» Задача 9. По вариантам – см следующие слайды Задача 10*. По вариантам – см следующие слайды Задача 11**. По вариантам – см следующие слайды ОТЧЕТ Для одной из операций, реализованных через FOR, нужно принести блок-схему.
Вариант 1 Из массива удалить первый из четных элементов. Пример: из массива A[5]: 1 3 4 5 6 должен получиться массив A[4]: 1 3 5 6. Вариант 2 Из массива удалить последний из четных элементов. Пример: из массива A[5]: 1 3 4 5 6 должен получиться массив A[4]: 1 3 4 5. Вариант 3 Из массива удалить последний из нечетных элементов. Пример: из массива A[5]: 1 3 4 5 6 должен получиться массив A[4]: 1 3 4 6. Вариант 4 Из массива удалить первый из нечетных элементов. Пример: из массива A[5]: 1 3 4 5 6 должен получиться массив A[4]: 3 4 5 6. Вариант 5 После максимального из четных элементов вставить 0. Пример: из массива A[5]: 1 9 8 3 5 должен получиться массив A[6]: 1 9 8 0 3 5. Вариант 6 После первого четного элемента вставить 0. Пример: из массива A[5]: 1 6 8 3 4 должен получиться массив A[6]: 1 6 0 8 3 4. Вариант 7 После последнего нечетного элемента вставить 0. Пример: из массива A[5]: 1 3 8 3 5 должен получиться массив A[6]: 1 3 8 3 5 0. Вариант 8 Удалить максимальный из четных элементов. Пример: из массива A[5]: 2 3 4 7 5 должен получиться массив A[4]: 2 3 7 5. Вариант 9 Удалить максимальный из кратных трем элементов. Пример: из массива A[5]: 2 3 4 7 5 должен получиться массив A[4]: 2 4 7 5. Вариант 10 После последнего кратного четырем элемента вставить 0. Пример: из массива A[5]: 1 3 8 3 4 должен получиться массив A[6]: 1 3 8 3 4 0.
Вариант 1 Из массива удалить четные элементы, стоящие после максимального. Пример: из массива A[5]: 2 7 4 6 5 должен получиться массив A[3]: 2 7 5. Вариант 2 Из массива удалить четные элементы, имеющие значение больше среднего арифметического всех элементов массива. Пример: из массива A[5]: 8 7 2 6 5 должен получиться массив A[3]: 7 2 5 (среднее арифметическое всех элементов =(8+7+2+6+5)/5=5.6). Вариант 3 Из массива удалить элементы, имеющие значение меньше среднего арифметического четных элементов массива. Пример: из массива A[5]: 8 7 2 6 5 должен получиться массив A[3]: 8 7 6 (среднее арифметическое четных элементов =(8+2+6)/3=5.33). Вариант 4 Из массива удалить элементы, стоящие после максимального и имеющие значение меньше среднего арифметического всех элементов массива. Пример: из массива A[5]: 8 6 9 4 5 должен получиться массив A[3]: 8 6 9 (среднее арифметическое четных элементов =(8+6+9+4+5)/5=6.4). Вариант 5 Из массива удалить четные элементы, стоящие между максимальным и минимальным элементами. Пример: из массива A[7]: 1 8 8 4 7 0 5 должен получиться массив A[5]: 1 8 7 0 5. Вариант 6 Из массива удалить элементы, кратные трем, стоящие между максимальным и минимальным элементами. Пример: из массива A[7]: 1 9 3 4 9 0 0 должен получиться массив A[5]: 1 9 4 0 0. Вариант 7 Из массива удалить элементы, имеющие четный индекс и стоящие между максимальным и минимальным элементами. Пример: из массива A[7]: 9 3 4 9 1 0 0 должен получиться массив A[5]: 9 4 1 0 0. Вариант 8 Из массива удалить элементы, встречающиеся в массиве более одного раза. Пример: из массива A[7]: 9 3 4 9 1 0 0 должен получиться массив A[3]: 3 4 1. Вариант 9 Из массива удалить элементы, встречающиеся в массиве только один раз. Пример: из массива A[7]: 9 1 4 9 1 9 0 должен получиться массив A[5]: 9 1 9 1 9. Вариант 10 Из массива удалить нечетные элементы, встречающиеся в массиве только один раз. Пример: из массива A[7]: 4 1 4 3 1 9 0 должен получиться массив A[5]: 4 1 4 1 0.
Вариант 1 Из массива удалить самую длинную цепочку четных элементов. Пример: из массива A[8]: 4 1 4 2 1 2 4 6 должен получиться массив A[5]: 4 1 4 2 1 (самая длинная цепочка четных чисел включает элементы с 6 по 8: 2 4 6). Вариант 2 Из массива удалить цепочки из четных элементов, состоящие менее чем из трех элементов. Пример: из массива A[8]: 4 3 4 2 1 2 4 6 должен получиться массив A[5]: 3 1 2 4 6. Вариант 3 Из массива удалить цепочки из нечетных элементов, состоящие менее чем из трех элементов. Пример: из массива A[8]: 3 3 4 5 2 3 7 9 должен получиться массив A[5]: 4 2 3 7 9. Вариант 4 Из массива A удалить те элементы, которые встречаются и в массиве A и в массиве B по крайней мере по 2 раза. Пример: массив A[8]: 3 3 4 5 2 3 5 9 массив B[7]: 1 2 3 4 5 2 5 По 2 раза в обоих массивах встречается только элемент, равный 5. Массив A после удаления примет вид: A[6]: 3 3 4 2 3 9. Вариант 5 Из массива из каждой цепочки четных элементов удалить самый маленький элемент. Пример: из массива A[9]: 3 6 4 5 2 3 4 6 4 должен получиться массив A[6]: 3 6 5 3 6 4. Вариант 6 Из массива A удалить те цепочки четных элементов, в которых есть хотя бы один элемент из массива B. Пример: массив A[9]: 3 2 4 5 2 3 2 6 5 массив B[6]: 1 3 4 7 8 9 Массив A после удаления примет вид: A[7]: 3 5 2 3 2 6 5.
Вариант 7 Из массива A удалить те цепочки нечетных элементов, в которых нет ни одного элемента из массива B. Пример: массив A[10]: 3 2 7 5 2 1 2 6 3 9 массив B[5]: 1 2 5 4 8 Массив A после удаления примет вид: A[7]: 2 7 5 2 1 2 6. Вариант 8 Из массива A удалить те цепочки нечетных элементов, в которых нет ни одного элемента из массива B. Пример: массив A[10]: 3 2 7 5 2 1 2 6 3 9 массив B[5]: 1 2 5 4 8 Массив A после удаления примет вид: A[7]: 2 7 5 2 1 2 6. Вариант 9 Между массивами A и B обменять их самые длинные цепочки из одинаковых элементов. Пример: массив A[10]: 3 2 2 5 2 1 1 1 3 9 массив B[8]: 1 2 5 5 4 8 3 3 В массиве A самая длинная цепочка: 1 1 1 (элементы с 7 по 9). В массиве B самая длинная цепочка: 5 5 (элементы с 3 по 4). Массив A после перестановки в него цепочки из массива B: A[9]: 3 2 2 5 2 5 5 3 9. Массив B после перестановки в него цепочки из массива A: B[9]: 1 2 1 1 1 4 8 3 3. Вариант 10 Между массивами A и B обменять их самые длинные цепочки из четных элементов. Пример: массив A[10]: 3 2 4 6 2 1 1 1 8 9 массив B[7]: 1 0 5 5 4 3 3 В массиве A самая длинная цепочка: 2 4 6 2 (элементы со 2 по 5). В массиве B самая длинная цепочка: 0 (элемент 2). Массив A после перестановки в него цепочки из массива B: A[7]: 3 0 1 1 1 8 9. Массив B после перестановки в него цепочки из массива A: B[10]: 1 2 4 6 2 5 5 4 3 3.
Познакомились с несколькими операциями над массивами, изменяющими его длину
// Задача 31. A void main() { int n, m, k, i; scanf_s( "%d%d", &n, &m); for (i = 1, k = 1; i <= m; i++, k *= n) printf ( "%d\n", k); for (; i >= 1; i--, k /= n) printf ( "%d ", k); } Тест 1. Введите 2 3 Тест 2. Введите 3 4 Тест 3. Введите 5 4
// Задача 31. A void main() { int n, m, k, i; scanf_s( "%d%d", &n, &m); for (i = 1, k = 1; i <= m; i++, k *= n) printf ( "%d\n", k); for (; i >= 1; i--, k /= n) printf ( "%d ", k); }
// Задача 32. A int a1[5] = {1, 2, 3, 7, 8}; void main() { int i, s; for (i = 0; i < 5; i++) if (a1[ i ] % 2 == 1) a1[ i ] = 1; s = 1; for (i = 1; i < 5; i++) s += a1[ i ]; printf ( "%d", s); } Тест 1. Выполните код.
// Задача 32. A int a1[5] = {1, 2, 3, 7, 8}; void main() { int i, s; for (i = 0; i < 5; i++) if (a1[ i ] % 2 == 1) a1[ i ] = 1; s = 1; for (i = 1; i < 5; i++) s += a1[ i ]; printf ( "%d", s); }
int b1[6] = { 1, 2, 1, 3, 1, 4 }; void main() { int i, k, t; scanf_s ( "%d", &k); t = b1[k]; for (i = k; i < 5; i++) b1[ i ] = b1[ i + 1]; b1[5] = t; for (i = 0; i < 6; i++) printf ( "%d ", b1[ i ]); } Тест 1. Введите 2 Тест 2. Введите 0
int b1[6] = { 1, 2, 1, 3, 1, 4 }; void main() { int i, k, t; scanf_s ( "%d", &k); t = b1[k]; for (i = k; i < 5; i++) b1[ i ] = b1[ i + 1]; b1[5] = t; for (i = 0; i < 6; i++) printf ( "%d ", b1[ i ]); } Тест 1. Введите 2 Тест 2. Введите 0
Неименованные константы Идентификатор Переменные Именованные константы #define Именованные константы const Операторы Операнды Выражения Постфиксный инкремент Постфиксный декремент Префиксный инкремент Префиксный декремент lvalue и rvalue FOR Блок-схема цикла FOR Связь между WHILE и FOR Формы FOR в Си
(Одномерный) массив int a[4]; Инициализация массива int b[5] = {2, 20, 200, 2000, 20000}; "Массив переменной длины" в языке Си
Операции над массивами: Ввод массива с клавиатуры Вывод (значений элементов) массива в консоль Заполнение массива определенными значениями (нулями, по формуле) Заполнение массива случайными значениями Выборочное использование элементов массива Добавление элемента в конец массива Удаление последнего элемента массива Подсчет количества элементов (удовлетворяющих условию) Подсчет суммы элементов Изменение элементов по условию Поиск первого элемента, удовлетворяющего условию Поиск значения минимального элемента Поиск индекса максимального элемента Поменять местами максимальный и начальный элемент Сортировка методом выбора* Переставить местами минимальный и максимальный элемент массива*
