1 Глава 6 Массивы. 2 План 6.1 Введение 6.2 Массивы 6.3 Объявление массива 6.4 Примеры использования 6.5 Передача массива в функции 6.6 Сортировка массивов. - презентация

1 1 Глава 6 Массивы

2 2 План 6.1 Введение 6.2 Массивы 6.3 Объявление массива 6.4 Примеры использования 6.5 Передача массива в функции 6.6 Сортировка массивов 6.7 Пример: подсчет Среднего, Медианы и Моды 6.8 Поиск в массиве 6.9 Многомерные массивы

3 3 6.1Введение Массивы Массивы Структуры связанных данных Структуры связанных данных Статический объект – тот же размер в течении работы программы Статический объект – тот же размер в течении работы программы Динамические структуры рассмотрим в Главе 12 Динамические структуры рассмотрим в Главе 12

4 4 6.2Массивы Массив Массив Группа последовательных Группа последовательных ячеек памяти Общее имя и тип Общее имя и тип Для указания элемента Для указания элемента Название массива Название массива Номер позиции Номер позиции Формат: Формат: имямассива [ номерпозиции ] Первый элемент на позиции 0 Первый элемент на позиции 0 n элементов в массиве c : n элементов в массиве c : c[ 0 ], c[ 1 ]... c[ n – 1 ] c[ 0 ], c[ 1 ]... c[ n – 1 ] Имя массива Номер позиции c[6] c[0] c[1] c[2] c[3] c[11] c[10] c[9] c[8] c[7] c[5] c[4]

5 5 6.2Массивы Элементы массива – как обычные переменные Элементы массива – как обычные переменные c[ 0 ] = 3; printf( "%d", c[ 0 ] ); Выполнение операции с индексом. Выполнение операции с индексом. Если x = 3 Если x = 3 c[ ] == c[ 3 ] == c[ x ]

6 6 6.3Объявление массива Нужно указать Нужно указать Имя Имя Тип Тип Количество элементов Количество элементов типМассива имяМассива [ количествоЭлементов ]; Примеры: Примеры: int c[ 10 ]; float myArray[ 3284 ];

7 7 6.3Объявление массива Объявление нескольких массивов одного типа Объявление нескольких массивов одного типа Формат похож на переменные Формат похож на переменные Пример: Пример: int b[ 100 ], x[ 27 ];

8 8 6.4Пример работы с массивом Инициализация Инициализация int n[ 5 ] = { 1, 2, 3, 4, 5 }; Если данных не хватает, все что справа будет = 0 Если данных не хватает, все что справа будет = 0 int n[ 5 ] = { 0 } Все элементы 0 Все элементы 0 Если данных больше – синтаксическая ошибка Если данных больше – синтаксическая ошибка В языке C нет проверки границ массивов В языке C нет проверки границ массивов

9 9 6.4Пример работы с массивом Если нет размера, он определяется инициализацией Если нет размера, он определяется инициализацией int n[ ] = { 1, 2, 3, 4, 5 }; 5 числе, размер массива будет 5 5 числе, размер массива будет 5

10 10 1. Инициализация массива 2. Цикл 3. Печать 1/* Fig. 6.8: fig06_08.c 2 Histogram printing program */ 3#include 4#define SIZE int main() 7{7{ 8 int n[ SIZE ] = { 19, 3, 15, 7, 11, 9, 13, 5, 17, 1 }; 9 int i, j; printf( "%s%13s%17s\n", "Element", "Value", "Histogram" ); for ( i = 0; i

11 11Результат Element Value Histogram 0 19 ******************* 1 3 *** 2 15 *************** 3 7 ******* 4 11 *********** 5 9 ********* 6 13 ************* 7 5 ***** 8 17 ***************** 9 1 *

12 12 6.4Примеры использования массивов Массив символов Массив символов Строка first на самом деле статический массив символов Строка first на самом деле статический массив символов Массивы символов могут быть инициализированы строкой Массивы символов могут быть инициализированы строкой char string1[] = "first"; Символ нуль '\0' завершает строку Символ нуль '\0' завершает строку string1 содержит 6 элементов string1 содержит 6 элементов Это эквивалентно Это эквивалентно char string1[] = { 'f', 'i', 'r', 's', 't', '\0' };

13 13 6.4Примеры использования массивов Массив символов Массив символов Можно получить индивидуальный символ Можно получить индивидуальный символ string1[ 3 ] это символ s Имя массива это его адрес, так что & не нужен для scanf Имя массива это его адрес, так что & не нужен для scanf scanf( "%s", string2 ); Считывает символы, пока не будет введен пробел Считывает символы, пока не будет введен пробел Может записать данные ПОСЛЕ окончания массива Может записать данные ПОСЛЕ окончания массива

14 14 1. Инициализация строк 2. Печать Ввод строк 2.1 Цикл 2.2 Печать посимвольно Результат 1/* Fig. 6.10: fig06_10.c 2 Treating character arrays as strings */ 3#include 4 5int main() 6{6{ 7 char string1[ 20 ], string2[] = "string literal"; 8 int i; 9 10 printf(" Enter a string: "); 11 scanf( "%s", string1 ); 12 printf( "string1 is: %s\nstring2: is %s\n" 13 "string1 with spaces between characters is:\n", 14 string1, string2 ); for ( i = 0; string1[ i ] != '\0'; i++ ) 17 printf( "%c ", string1[ i ] ); printf( "\n" ); 20 return 0; 21} Enter a string: Hello there string1 is: Hello string2 is: string literal string1 with spaces between characters is: H e l l o

15 15 6.5Передача массивов функции Для передачи массива как аргумента, укажите имя массива без скобок Для передачи массива как аргумента, укажите имя массива без скобок int myArray[ 24 ]; myFunction( myArray, 24 ); Обычно передают размер массива как дополнительный аргумент в функцию Обычно передают размер массива как дополнительный аргумент в функцию Массивы передаются по ссылке Массивы передаются по ссылке Название массива это адрес первого элемента Название массива это адрес первого элемента Функция знает где хранится массив Функция знает где хранится массив Изменяем оригинальные значения Изменяем оригинальные значения

16 16 6.5Передача массивов функции Передача элементов массива Передача элементов массива Передача по значению Передача по значению Передача с индексом массива ( myArray[ 3 ] ) Передача с индексом массива ( myArray[ 3 ] )

17 17 6.5Передача массивов функции Прототип функции Прототип функции void modifyArray( int b[], int arraySize ); Имена параметров необязательны в прототипе Имена параметров необязательны в прототипе int b[] можно записать как int [] int b[] можно записать как int [] int arraySize может быть просто int int arraySize может быть просто int

18 18 1. Определение функций 2. Передача массива в функцию 2.1 Передача элемента массива в функцию 3. Печать 1/* Fig. 6.13: fig06_13.c 2 Passing arrays and individual array elements to functions */ 3#include 4#define SIZE 5 5 6void modifyArray( int [], int ); /* appears strange */ 7void modifyElement( int ); 8 9int main() 10{ 11 int a[ SIZE ] = { 0, 1, 2, 3, 4 }, i; printf( "Effects of passing entire array call " 14 "by reference:\n\nThe values of the " 15 "original array are:\n" ); for ( i = 0; i

19 Функции Результат 33 34void modifyArray( int b[], int size ) 35{ 36 int j; for ( j = 0; j

20 20 6.6Сортировка массивов Сортировка данных Сортировка данных Важное приложение для вычислений Важное приложение для вычислений Практически любая сфера деятельности требует сортировки данных Практически любая сфера деятельности требует сортировки данных Пузырьковая Пузырьковая Несколько проходов через весь массив Несколько проходов через весь массив Последовательное сравнение пар элементов Последовательное сравнение пар элементов Если порядок по возрастанию (или равные) – без изменений Если порядок по возрастанию (или равные) – без изменений Если по убыванию, элементы обмениваются Если по убыванию, элементы обмениваются Повторить Повторить

21 21 6.6Сортировка массивов Пример: Пример: начало: начало: проход 1: проход 1: проход 2: проход 2: Меньшие элементы, как пузырьки всплывают наверх Меньшие элементы, как пузырьки всплывают наверх

22 22 6.7Пример: расчет среднего, медиану и моду в массиве Среднее арифметическое Среднее арифметическое Медиана – число в середине сортированного списка Медиана – число в середине сортированного списка 1, 2, 3, 4, 5 1, 2, 3, 4, 5 3 это медиана списка 3 это медиана списка Мода – число, которое встречается чаще всего Мода – число, которое встречается чаще всего 1, 1, 1, 2, 3, 3, 4, 5 1, 1, 1, 2, 3, 3, 4, 5 1 это мода 1 это мода

23 23 1. Прототипы функций 1.1 Инициализация массива 2. Вызов функций mean, median, и mode 1/* Fig. 6.16: fig06_16.c 2 This program introduces the topic of survey data analysis. 3 It computes the mean, median, and mode of the data */ 4#include 5#define SIZE void mean( const int [] ); 8void median( int [] ); 9void mode( int [], const int [] ) ; 10void bubbleSort( int [] ); 11void printArray( const int [] ); 12 13int main() 14{ 15 int frequency[ 10 ] = { 0 }; 16 int response[ SIZE ] = 17 { 6, 7, 8, 9, 8, 7, 8, 9, 8, 9, 18 7, 8, 9, 5, 9, 8, 7, 8, 7, 8, 19 6, 7, 8, 9, 3, 9, 8, 7, 8, 7, 20 7, 8, 9, 8, 9, 8, 9, 7, 8, 9, 21 6, 7, 8, 7, 8, 7, 9, 8, 9, 2, 22 7, 8, 9, 8, 9, 8, 9, 7, 5, 3, 23 5, 6, 7, 2, 5, 3, 9, 4, 6, 4, 24 7, 8, 9, 6, 8, 7, 8, 9, 7, 8, 25 7, 4, 4, 2, 5, 3, 8, 7, 5, 6, 26 4, 5, 6, 1, 6, 5, 7, 8, 7 }; mean( response ); 29 median( response ); 30 mode( frequency, response ); 31 return 0; 32}

24 24 3. Определение функции mean 3.1 Определение функции median Сортировка массива Печать среднего элемента 33 34void mean( const int answer[] ) 35{ 36 int j, total = 0; printf( "%s\n%s\n%s\n", "********", " Mean", "********" ); for ( j = 0; j

25 25 65} 66 67void mode( int freq[], const int answer[] ) 68{ 69 int rating, j, h, largest = 0, modeValue = 0; printf( "\n%s\n%s\n%s\n", 72 "********", " Mode", "********" ); for ( rating = 1; rating

26 Определим bubbleSort 3.3 Определим printArray 95 printf( "\n" ); 96 } printf( "The mode is the most frequent value.\n" 99 "For this run the mode is %d which occurred" 100 " %d times.\n", modeValue, largest ); 101} void bubbleSort( int a[] ) 104 { 105 int pass, j, hold; for ( pass = 1; pass

27 27Результат printf( "%2d", a[ j ] ); 128 } 129 } ******** Mean ******** The mean is the average value of the data items. The mean is equal to the total of all the data items divided by the number of data items (99). The mean value for this run is: 681 / 99 = ******** Median ******** The unsorted array of responses is The sorted array is The median is element 49 of the sorted 99 element array. For this run the median is 7

28 28Результат ******** Mode ******** Response Frequency Histogram * 2 3 *** 3 4 **** 4 5 ***** 5 8 ******** 6 9 ********* 7 23 *********************** 8 27 *************************** 9 19 ******************* The mode is the most frequent value. For this run the mode is 8 which occurred 27 times.

29 29 6.8Поиск в массиве: линейный поиск и бинарный поиск Найти в массиве ключевое значение Найти в массиве ключевое значение Линейный поиск Линейный поиск Простой Простой Сравнивает каждый элемент массива с ключевым значением Сравнивает каждый элемент массива с ключевым значением Подходит для маленьких массивов Подходит для маленьких массивов

30 30 6.8Поиск в массиве: линейный поиск и бинарный поиск Бинарный поиск Бинарный поиск Для сортированных массивов Для сортированных массивов Сравнивает средний элемент с ключом Сравнивает средний элемент с ключом Если равны, мы нашли Если равны, мы нашли Если key < middle, смотрим в первой половине массива Если key < middle, смотрим в первой половине массива Если key > middle, смотрим в правой половине массива Если key > middle, смотрим в правой половине массива Повторяем Повторяем Очень быстро; максимум n шагов, при 2 n > элементах Очень быстро; максимум n шагов, при 2 n > элементах 30 элементов требуют максимум 5 шагов 30 элементов требуют максимум 5 шагов 2 5 > > 30 5

31 31 6.9Массивы большей размерности Таблица строк и столбцов (массив m на n ) Таблица строк и столбцов (массив m на n ) Как матрицы: указываем сначала строку, потом столбец Как матрицы: указываем сначала строку, потом столбец Строка0 Строка1 Строка2 Столбец0Столбец1Столбец2Столбец3 a[ 0 ][ 0 ] a[ 1 ][ 0 ] a[ 2 ][ 0 ] a[ 0 ][ 1 ] a[ 1 ][ 1 ] a[ 2 ][ 1 ] a[ 0 ][ 2 ] a[ 1 ][ 2 ] a[ 2 ][ 2 ] a[ 0 ][ 3 ] a[ 1 ][ 3 ] a[ 2 ][ 3 ] Строка Имя массива Столбец

32 32 6.9Массивы большей размерности Инициализация Инициализация int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; int b[ 2 ][ 2 ] = { { 1, 2 }, { 3, 4 } }; Данные группируем по строкам Данные группируем по строкам Если не хватает, считаем что 0 Если не хватает, считаем что 0 int b[ 2 ][ 2 ] = { { 1 }, { 3, 4 } }; Ссылка на элемент Ссылка на элемент Указываем строку, потом столбец Указываем строку, потом столбец printf( "%d", b[ 0 ][ 1 ] );

33 33 1. Инициализация переменных 1.1 Определение функции, получающей двухмерный массив 1.2 Инициализация studentgrades[ ][] 2. Вызов функций minimum, maximum, и average 1/* Fig. 6.22: fig06_22.c 2 Double-subscripted array example */ 3#include 4#define STUDENTS 3 5#define EXAMS 4 6 7int minimum( const int [][ EXAMS ], int, int ); 8int maximum( const int [][ EXAMS ], int, int ); 9double average( const int [], int ); 10void printArray( const int [][ EXAMS ], int, int ); 11 12int main() 13{ 14 int student; 15 const int studentGrades[ STUDENTS ][ EXAMS ] = 16 { { 77, 68, 86, 73 }, 17 { 96, 87, 89, 78 }, 18 { 70, 90, 86, 81 } }; printf( "The array is:\n" ); 21 printArray( studentGrades, STUDENTS, EXAMS ); 22 printf( "\n\nLowest grade: %d\nHighest grade: %d\n", 23 minimum( studentGrades, STUDENTS, EXAMS ), 24 maximum( studentGrades, STUDENTS, EXAMS ) ); for ( student = 0; student

34 34 3. Определение функций 33 34/* Find the minimum grade */ 35int minimum( const int grades[][ EXAMS ], 36 int pupils, int tests ) 37{ 38 int i, j, lowGrade = 100; for ( i = 0; i

35 35 3. Определение функций 65 int i, total = 0; for ( i = 0; i

36 36Результат The array is: [0] [1] [2] [3] studentGrades[0] studentGrades[1] studentGrades[2] Lowest grade: 68 Highest grade: 96 The average grade for student 0 is The average grade for student 1 is The average grade for student 2 is 81.75