Тема 3. Одномерные массивы в языке C#. Сортировка и поиск данных
Лекция 9. МАССИВЫ
9.1 Понятие ссылочного типа
В языке C# существует два типа переменных – значимые и символьные.
Переменные значимых типов способны хранить значения данных
соответствующего типа. Ссылочные переменные хранят физические адреса
памяти компьютера (ссылки), по которым в памяти
компьютера
размещаются соответствующие значения данных.
Память под данные переменным значимых типов обычно выделяется во
время компиляции программы, а переменным ссылочного типа – во время
выполнения программы с помощью оператора new.
В предыдущих программах мы уже использовали переменную
ссылочного типа – переменную (объект rnd) класса Random, с помощью
метода которой формировались псевдослучайные числа.
Необходимо отметить, что ссылочный тип обычно используется для
организации данных типа массивы, строки, классы, то есть данных сложной
структуры. Все эти данные размещаются в специальной памяти компьютера,
получившей научное название куча.
Все переменные значимых типов размещаются в программном стеке, а
переменные ссылочного типа – в управляемой операционной системой куче.
Поэтому время доступа к значимым переменным несколько меньше, чем к
переменным ссылочного типа, но объемы памяти, выделяемые под
переменные ссылочного типа на порядки больше чем объемы памяти,
выделяемые программе под переменные значимых типов.
Иногда распределение памяти компьютера под значимые переменные
называют статическим распределение памяти – т.е. процесс выделения
памяти компьютера происходит во время компиляции программы, а
распределение памяти компьютера под ссылочные переменные получило
название динамическое распределение памяти – т.е. процесс выделения
памяти компьютера под эти переменные происходит во время выполнения
программы.
Еще раз отметим, что выделение памяти компьютера под переменные
ссылочного типа осуществляется с помощью оператора new.
9.2 Понятие массива
Массив это форма описания группы переменных одного типа с помощью
одной переменной – переменной массива. Все переменные, объединяемые в
массив, пронумерованы от 0 до n и каждой переменой поставлен в
соответствие ее номер – индекс. Для обращения к конкретной переменной
массива необходимо указать имя массива и индекс переменной. Поэтому
часто переменную массива называют переменной с индексами.
Различают одномерные массивы (вектор), например, массив имен,
массив оценок за один экзамен, массив дат рождения и т.д.
Двумерные массивы (матрица или таблица), например, результаты игр
чемпионата страны по футболу, итоговая таблица результатов экзаменов
студентов и т.д.
Многомерные массивы – все остальные массивы.
Описание массива в программе осуществляется в два этапа: объявление
массива и инициализация массива.
При объявлении массива указывается тип переменных массива и имя
массива, например:
int[ ] masi;
double[ ] masf; ,
где в первой строке мы объявляем, что будем использовать массив
целых переменных с именем masi, а во второй строке мы объявляем массив
вещественных переменных masf. При этом в программном стеке во время
компиляции программы выделяется место только под переменную всего
массива, например, masi или masf которым присваиваются «нулевые»
значения.
Память компьютера под переменные входящие в массивы будет
выделяться в куче на этапе инициализации массива с помощью операции
new, например,
masi = new int[10];
masf = new double[20] ; ,
где значение в квадратных скобках фактически определяет объем
массива (0 . . . кол-во элементов -1 – диапазон значений индексов, который
можно использовать при обращении к элементам массива).
На этапе инициализации массива в куче создается «объект» массива и
всем его переменным присваивается «нулевые» значения (выполняется его
инициализация). Начальный адрес выделенной в куче памяти по переменные
входящие в массив – ссылка на выделенный объем памяти кучи записывается
в переменную всего массива, которая находится в программном стеке.
Нулевые значения переменных соответствуют:
– для числовых переменных это нули;
– для строковых переменных это пустые строки;
– для символьных переменных это отсутствие символа.
После инициализации массива его переменные можно использовать в
программе.
9.3 Динамические массивы
Значения элементов массивов языка C# являются динамическими –
память для них выделяется в «куче» в процессе работы программы с
помощью операции new. Такая особенность языка C# позволила создавать в
программах динамические массивы – то есть массивы, количество элементов
которых также определяется в процессе работы программы. Существует
большая группа задач, в которых размеры массива выясняются либо в
процессе работы программы, либо их необходимо задавать в диалоге с
пользователем, например, количество файлов в каталоге или товаров на
складе.
Чисто синтаксически нет существенной разницы в объявлении
статических или динамических массивов. Действительно в объявлении
массивов не присутствуют количественные характеристики, например,
double[ ] masf;, а инициализация массива выполняется с помощью операции
new уже во время работы программы. Можно совмещать объявление и
инициализацию динамического массива, если в диалоге задать число
элементов массива. Например:
Console.WriteLine("Введите число элементов массива masi");
int size = int.Parse(Console.ReadLine());
int[] masi = new int[size];
Динамическими массивами в языке C# могут быть только
одномерные массивы.
Значение переменных количествам элементов динамических массивов
должны быть определены до их инициализации.
Рассмотрим учебную программу на использование динамического
массива.
Задача 9.1 Студенты группы сдают экзамен по дисциплине
«Алгоритмизация и основы программирования». Количество студентов в
группе задается в режиме диалога (не более 20). Оценки (в виде баллов)
формируются случайным образом в диапазоне от 20 до 100. Оценки за
экзамен группы организовать в динамическом массиве. Напечатать
результаты экзаменов.
Исходный код программы:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
Console.WriteLine("Введите число студентов в группе
не более 20");
int size = int.Parse(Console.ReadLine());
int[] masi = new int[size];
int i;
Random rnd = new Random();
for (i = 0; i < size; i++)
Console.Write(" {0,3}", i+1);
Console.WriteLine();
for (i = 0; i < size; i++)
{
masi[i] = rnd.Next() % 81 + 20;
Console.Write(" {0,3}",masi[i]);
}
Console.WriteLine();
Console.WriteLine("Для продолжения нажмите клавишу
Enter");
Console.ReadLine();
}
}
}
Работа программы:
Введите число студентов в группе не более 20
17
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
54 43 70 70 32 56 59 25 23 39 59 85 90 72 72 69 55
Для продолжения нажмите клавишу Enter
Как видно из кода программы количество переменных, включаемых в
массив (количество студентов группы), определялось во время работы
программы и перед инициализацией массива. Таким образом, выделение
памяти под переменные массива осуществлялось не на этапе компиляции
программы, а на этапе ее выполнения – то есть динамически.
При выводе значений массива использовалось указание о количестве
позиций для вывода каждого значения – {0,3}, что позволяет представлять
результаты работы программы в удобном виде.
9.4 Вопросы для проверки
9.4.1 Укажите правильный вариант объявления переменной типа одномерный
массив:
A) int a : array[ 0..10];
B) char[] a;
C) char a[];
D) int a[] of array;
E) string a[ 0..10] as integer;
9.4.2 Сколько чисел можно записать в одномерный массив a[15];?
A) 12.
B) 13.
C) 14.
D) 15.
E) 16.
9.4.3 Понятие переменных значимых и ссылочных типов.
9.4.4 Какие переменные можно размещать в массиве?
9.4.5 Что делает следующей фрагмент программы для массива a[11]:
for (I = 0; I < 10; I++)
{k = a[I]; a[I] = a[10 - I]; a[I] = k;} ?
Продолжение тема 3. Одномерные массивы в языке C#. Сортировка и поиск
данных
Лекция 10. ИСПОЛЬЗОВАНИЕ МАССИВОВ ПРИ РЕШЕНИИ
РАЗЛИЧНЫХ ЗАДАЧ
10.1 Примеры использования массивов в различных задачах
Рассмотрим различные варианты объявления и инициализации массивов
на примерах решения различных задач.
Существует много задач, в которых необходимо использовать массив.
Часть задач связанны с обработками текстов, так как тексты (строки) это
массивы символов.
Математические или физические задачи, например, вычисление среднего
значения некоторой функции представленной массивом экспериментальных
значений.
Информационные задачи, например, список имен, который необходимо
упорядочить в алфавитном порядке или поисковые задачи в массиве и т.д.
Рассмотрим решение некоторых учебных задач, требующих
использование массива.
10.1.1 Следующую задачу можно отнести к классу «физических» задач.
Задача 10.1 Некоторая экспериментальная функция представлена
таблицей 12 своих значений, записанных в массив. Необходимо найти все
максимумы этой функции. Для вычислений использовать следующие
значения функции: 1.05, 3.17, 5.24, 4.38, 6.42, 4.93, 6.59, 7.84, 5.73, 5.14, 4.87
и 3.18.
Алгоритм решения задачи включает следующие шаги:
– проверку на максимум первого значения функции – если второе
значение функции меньше первого значения, то первое значение является
максимумом;
– поиск максимумов – если предыдущее и последующее значения
функции меньше текущего значения, то текущее значение является
максимум;
– проверку на максимум последнего значения функции – если последнее
значение функции больше предпоследнего значения функции, то последнее
значение является максимум.
В данном алгоритме мы не рассматриваем ситуации, в которых функция
несколько значений подряд имеет одинаковые значения. В реальной жизни
такая ситуация маловероятна. Алгоритм решения задачи, допускающий эти
ситуации, можете разработать самостоятельно.
Исходный код программы:
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
int i;
double j, n;
double[] mas = {1.05, 3.17, 5.24, 4.38, 6.42, 4.93,
6.59, 7.84, 5.73, 7.14, 3.87, 2.18 };
//методически более провильно
//float[] mas;
//mas = new float[12] { 1.05, 3.17, 5.24, 4.38,
6.42,
//
4.93, 6.59, 7.84, 5.73, 6.14, 4.87, 3.18 };
//можно совмещать объявление и инициализацию массива в одно
действие, например:
int[] max = new int[7]; // массив индексов
максимумов
//представим массив в "графической" форме
for (i = 0; i <= 11; i++)
{
Console.Write(i);
n = Math.Round(mas[i]);
j = 0;
while (j <= n) { Console.Write(" "); j++; }
Console.WriteLine('*');
}
int k; // индекс максимумов
k=0;
// проверка первого значения функции на максимум
if (mas[0] > mas[1]) {max[k]=0; k++;}
// поиск максимумов
for ( i = 1; i < 11; i++)
if ((mas[i-1]<mas[i]) && (mas[i]>mas[i+1]))
{max[k]=i; k++;}
// проверка последнего значения функции на максимум
if (mas[10]<mas[11]) {max[k]=11; k++;}
// печать максимумом функции
Console.WriteLine("максимумы функции:");
for ( i = 0; i < k; i++)
Console.WriteLine("{0}
-
{1}", max[i],
mas[max[i]]);
Console.ReadLine();
}
}
}
Работа программы:
0 *
1 *
2 *
3 *
4
*
5 *
6
*
7
*
8
*
9
*
10 *
11 *
максимумы функции:
2 - 5,24
4 - 6,42
7 - 7,84
9 - 7,14
В приведенной программе рассмотрено несколько вариантов объявления
и инициализации массивов.
Для небольшого количества переменных можно совмещать объявление и
инициализацию массивов, особенно если значения элементов массива
определяются не в программе – элементы массива представлены константами
массива. Например:
float[] mas = { 1.05, 3.17, 5.24, 4.38, 6.42,
4.93, 6.59, 7.84, 5.73, 6.14, 4.87, 3.18 };
Второй вариант объявления и инициализации массива требует сначала
объявление переменной типа массив, а затем его инициализацию. Например:
float[] mas;
mas = new float[12] { 1.05, 3.17, 5.24, 4.38, 6.42,
4.93, 6.59, 7.84, 5.73, 6.14, 4.87, 3.18 };
В третьем варианте объявление и инициализация массива выполняются в
одном действии. Например:
int[] max = new int[7];
10.1.2 Следующая задача относится к классу информационных задач.
Задача 10.2 Группа из 20 студентов сдавала экзамен. Оценки
формируются случайным образом в диапазоне от 2 до 5. Определить сколько
студентов получило оценку 5, 4, 3 и 2.
Алгоритм решения задачи включает следующие шаги:
– в цикле от 1 до 20 формируем случайным образом массив оценок за
экзамен 20 студентов;
– при повторном просмотре массива оценок студентов подсчитываем
число 5, 4, 3 и 2;
– выводим на экран монитора результаты работы программы.
Исходный код программы:
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
int i,j;
int[] a = new int[20];
int[] b = new int[6];
Random rnd = new Random();
// формируем случайным образом оценки 20 студентов
// выводим их на экран монитора
Console.Write("Оценки студентов: ");
for (i=0;i<=19;i++)
{
a[i] = rnd.Next()%4 + 2;
Console.Write(" {0}", a[i]);
}
Console.WriteLine();
// подсчитываем число 5, 4, 3 и 2 – результат заносим в массив b
for (i=0;i<=19;i++)
{
if (a[i]==2) b[2]++;
if (a[i]==3) b[3]++;
if (a[i]==4) b[4]++;
if (a[i]==5) b[5]++;
}
// выводим результат работы программы
for (i=2;i<=5;i++)
Console.WriteLine("Оценку {0} получило {1}
студентов",i, b[i]);
Console.ReadLine();
}
}
}
Работа программы:
Оценки студентов: 4 5 2 4 3 4 2 5 3 5 4 4 5 2 5 5 4 5 2 5
Оценку 2 получило 4 студентов
Оценку 3 получило 2 студентов
Оценку 4 получило 6 студентов
Оценку 5 получило 8 студентов
Оператор цикла for, в котором проверяются условия, можно заменить
следующим фрагментом:
for (i=0;i<=19;i++)
for (j = 2; j <= 5; j++)
if (a[i] == j) b[j]++;
или
for (i=0;i<=19;i++)
b[a[i]]++;
Можно все проверки поместить в одном цикле, сразу после
формирования случайного числа:
for (i=0;i<=19;i++)
{
a[i] = rnd.Next()%4 + 2;
b[a[i]]++;
Console.Write(" {0}", a[i]);
}
Для данной задачи были рассмотрены несколько вариантов реализации
алгоритма решения задачи, но в последних вариантах реализация алгоритма
не очень очевидна.
Нахождение минимальной записи исходного кода программы,
реализующий алгоритм решения задачи, является самостоятельной очень
интересной задачей, которая в лекциях данной дисциплины не
рассматривается.
В лекциях мы стараемся в приведенных вариантах реализации алгоритма
решения задач записывать не самый минимальный вариант исходного кода
программы, а вариант, в котором очевидна реализация алгоритма решения
задачи.
В последнем варианте исходного кода программы значение индекса
массива b определяется оценкой, которую студент получил на экзамене.
Если индекс массива вычисляется по некоторому сложному алгоритму
или формируется случайным образом, то такое обращение к массиву
называется ассоциативным.
10.1.3 Следующую задачу можно отнести к классу математических
задач.
Массивы часто используется в математике при описании коэффициентов
полиномов. Например, коэффициенты полинома n – ой степени
,
обычно записываемого в виде функции
можно представить массивом a[n+1], в котором индекс массива будет
изменяться от 0 до n.
Одной из задач математики является исследование поведения функции,
представленной в виде полинома n степени, на некотором отрезке значений
переменной x.
Задача 10.3 Задан массив коэффициентов полинома 10 степени (n = 10) –
1.05,3.17,5.24,4.38,6.42,4.93,6.59,7.84,5.73,7.14,3.87,2.18.
Значение массива с индексом 0 равно нулевому коэффициенту полинома и
т.д.
Исследовать «поведение» полинома на отрезке от 0 до 1 с шагом 0.1
(переменная x изменяется от 0 до 1 с шагом 0.1).
Вывести на экран монитора поведение полинома в табличной и
графической формах.
Исходный код программы:
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
double j, n, x, y, p;
int i, k;
double[] mas = {1.05, 3.17, 5.24, 4.38, 6.42, 4.93,
6.59, 7.84, 5.73, 7.14, 3.87, 2.18 };
double[] masf = new double[11]; // массив значений полинома
Console.WriteLine("Графическая форма представления
полинома:");
k = 0;
for (x = 0; x < 1; x = x + 0.1)
{
y = x; p=mas[0];
for (i = 1; i <= 11; i++)
{
p = p + y * mas[i];
y = y * x;
}
masf[k] = p; k++;
Console.Write(x);
n = Math.Round(p);
j = 0;
while (j <= n) { Console.Write(" "); j++; }
Console.WriteLine('*');
}
Console.WriteLine("Табличная форма представления
полинома:");
i = 0;
for (x = 0; x < 1; x = x + 0.1)
{
Console.WriteLine("x = {0} P = {1}", x, masf[i]);
i++;
}
Console.ReadLine();
}
}
}
Работа программы:
Графическая форма представления полинома:
0 *
0,1 *
0,2 *
0,3 *
0,4 *
0,5 *
0,6
*
0,7
*
0,8
*
0,9
*
1
*
Табличная форма представления полинома:
x = 0 P = 1,05
x = 0,1 P = 1,4244787388488
x = 0,2 P = 1,9410304774144
x = 0,3 P = 2,6619038136876
x = 0,4 P = 3,6975170516992
x = 0,5 P = 5,253203125
x = 0,6 P = 7,7263077961728
x = 0,7 P = 11,9008032176404
x = 0,8 P = 19,3213982427136
x = 0,9 P = 32,9819936534232
x = 1 P = 58,54
В алгоритме вычисления полинома использовано рекуррентное
вычисление переменной x в степени n. Для этого переменной y
первоначально присвоено значение x и выполнено вычисление слагаемого
полинома с индексом 1. Затем y умножается на x (получаем значение x2) и
вычисляется значение второго слагаемого и т.д.
10.2 Вопросы для проверки
10.2.1 Что делает следующей фрагмент программы:
for (I = 0; I <= 10; I++)
Console.Write(" {0} \t", a[I]); ?
10.2.2 Что делает следующей фрагмент программы для массива a[11]:
for (I = 1; I <= 10; I++)
{k = a[I]; a[I] = a[11 - I]; a[11 - I] = k;} ?
10.2.3 Что делает следующей фрагмент программы:
k = a[0];
for (I = 0;I <= 10; I++)
if (a[I] > k) k = a[I];
Console.WriteLine(" {0} ", k); ?
10.2.4 Что делает следующей фрагмент программы:
for (I = 0; I <= 9; I++)
{ k = a[I]; a[I] = a[I+1]; a[I+1] = k;} ?
10.2.5 Что делает следующей фрагмент программы:
I = 0;
while (I <= 10)
{
a[I] = a[I] * (-1);
I++;
}?
