Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа № 7
Цель работы - изучить операторы и алгоритмы, используемые при организации вычислительных процессов обработки одномерных массивов данных, получить практические навыки в составлении подобных программ.
2 Общие сведения
До настоящего момента в программах были использованы простые переменные. Для хранения значения каждой такой переменной, имеющей свое имя, выделяется своя область памяти. По сути, имя имеет эта выделенная область памяти, которая хранит текущее значение переменной. Если переменных много, программа, предназначенная для их обработки, получается длинной, и в ней не удается в полной мере использовать компьютерные возможности. Одним из случаев, когда ее удается сделать лаконичной и эффективной, является ситуация, требующая обработки однотипных величин, которые к тому же должны обрабатываться по одним и тем же правилам.
Поскольку при решении очень многих задач требуется именно такая обработка, для нее в любом процедурном языке существует понятие массива — ограниченной совокупности однотипных величин. Введение понятия массива позволяет широко использовать циклические процессы, получая компактные коды программ.
Массив - это последовательность элементов одинакового типа, обращение к которым происходит с использованием общего для всех имени. Каждый элемент массива имеет свой порядковый номер (индекс) в последовательности: известно какая величина является в ней первой, какая второй и т.д., и в этом плане массив является упорядоченной последовательностью.
Создание массива начинается с выделения памяти под его элементы. Элементами массива могут быть величины как значимых, так и ссылочных типов (в том числе массивы).
Массив значимых типов хранит значения, массив ссылочных типов — ссылки на элементы. Всем элементам при создании массива присваиваются значения по умолчанию: нули для значимых типов и null — для ссылочных.
Вот, например, как выглядят операторы создания массива из 5 целых чисел и массива из 5 строк:
int[ ] а = new int[5];
string[ ] z = new string[5];
В первом операторе описан массив а, состоящий из пяти элементов значимого типа int[ ]. Операция new выделяет память под 5 целых элементов, и они заполняются нулями (рис. 1).
Рисунок 1- Массив из элементов значимого типа
Во втором операторе описан массив z ссылочного типа string[ ]. Операция new выделяет память под 5 ссылок на строки, и эти ссылки заполняются значением null. Память под сами строки, составляющие массив, не выделяется — это будет необходимо сделать перед заполнением массива (рис. 2).
Рисунок 2 - Массив из элементов ссылочного типа
Количество элементов в массиве (размерность) задается при выделении памяти и не может быть изменено впоследствии. Размерность может задаваться не только константой, но и выражением. Результат вычисления этого выражения должен быть неотрицательным, а его тип должен иметь неявное преобразование к int, uint, long или ulong.
Пример размерности массива, заданной выражением:
short m = . . . ;
string[ ] s = new string[m + 1];
Элементы массива нумеруются с нуля, поэтому максимальный номер элемента всегда на единицу меньше размерности (например, в описанном выше массиве а элементы имеют индексы от 0 до 4). Для обращения к элементу массива конструкция переменная с индексом, где после имени массива указывается порядковый номер элемента в квадратных скобках, например:
а[4] z[i]
Элементы массива могут участвовать во всех операциях, которые допустимы для простых переменных того же типа. При работе с массивом программисту необходимо внимательно следить за тем, чтобы его индекс не принял значение, лежащее за границами его описания, т.е. не разрешать программе работать с чужой областью памяти.
В С# для предотвращения подобной ситуации автоматически выполняется контроль выхода индекса за его объявленные границы и, если индекс принимает недопустимое значение, генерируется исключение IndexOutOfRangeException.
Массивы одного типа можно присваивать друг другу. При этом происходит присваивание ссылок, а не элементов, как и для любого другого объекта ссылочного типа, например:
int [ ] а = new int[10];
int[ ] b = а; / / b и а указывают на один и тот же массив
В С# массивы могут быть одномерными или многомерными. Многомерные массивы, в свою очередь, могут быть прямоугольными и ступенчатыми (невыровненными).
Одномерные массивы
Одномерный массив - это такой массив, для идентификации которого требуется указать значение только одного индекса.
Для объявления одномерного массива используется следующая форма записи:
тип[] имя_массива = new тип [размер];
Формат инициализации одномерного массива имеет следующий вид:
тип[] имя_массива = [val1, val2,…, valN];
Здесь начальные значения, присваиваемые элементам массива, задаются с помощью последовательности val1-valN. Для получения доступа к элементу одномерного массива требуется указать индекс нужного элемента:
имя_массива[индекс] = val;
Существует несколько вариантов описания массива:
тип[ ] имя;
тип[] имя = new тип [ размерность ];
тип[] имя = { список_инициализаторов };
тип[] имя = new тип [] { список_инициализаторов };
тип[] имя = new тип [ размерность ] { список_ииициализаторов };
Примеры описаний (один пример для каждого варианта описания):
int[ ] а; / / 1 элементов нет
int[ ] b = new int[4]; / / 2 элементы равны 0
int[ ] с = { 61, 2, 5, -9 }; / / 3 new подразумевается
int[ ] d = new int[ ] { 61, 2, 5, -9 }; / / 4 размерность вычисляется
int[ ] е = new int[4] { 61, 2, 5, -9 }; / / 5 избыточное описание
Здесь описано пять массивов. Отличие первого оператора от остальных состоит в том, что в нем, фактически, описана только ссылка на массив, а память под элементы массива не выделена. Если список инициализации не задан, размерность может быть не только константой, но и выражением типа, приводимого к целому,
В каждом из остальных массивов по четыре элемента целого типа. Как видно из операторов 3-5, массив при описании можно инициализировать. Если при этом не задана размерность (оператор 4), количество элементов вычисляется по количеству инициализирующих значений. Для полей объектов и локальных переменных можно опускать операцию new, она будет выполнена по умолчанию (оператор 3). Если присутствует и размерность, и список инициализаторов, размерность должна быть константой (оператор 5).
Если количество инициализирующих значений не совпадает с размерностью, возникает ошибка компиляции.
Рассмотрим несколько часто встречающихся на практике задач обработки одномерных массивов.
Некоторые алгоритмы обработки массивов
Пример 1. Поиск наибольшего элемента в одномерном массиве.
Исходными данными в поставленной задаче являются массив x и его размерность n. Решение этой задачи осуществляется с помощью цикла по параметру i, изменяющегося с шагом +1 от 1 до n-1. Перед входом в цикл переменной max присваивается значение первого элемента массива х[0].
С каждым итерацией цикла происходит переход к новому элементу массива и сравнение его значения со значением, хранящемся в переменной max. Если значение текущего элемента массива оказывается больше значения max, то переменной max присваивается значение элемента массива с текущим порядковым номером. После выхода из цикла выводится найденное значение наибольшего элемента массива.
Листинг 1 – Поиск максимального элемента в одномерном массиве
using System;
namespace ConsoleApplication5
{
class Program
{
static void Main(string[] args)
{
const int n = 6;
int[] a = new int[n] { 3, 12, 5, -9, 8, -4 };
Console.WriteLine("Исходный массив:");
for (int i = 0; i < n; ++i)
Console.WriteLine("\t" + a[i]);
Console.WriteLine();
int max = a[0];
for (int i = 0; i < n; ++i)
if (a[i] > max)
max = a[i];
Console.WriteLine("Максимальный элемент = " + max);
Console.Read();
}
}
}
Результаты расчета:
Обратите внимание на то, что для вывода элементов исходного массива требуется организовать цикл.
Пример 2. Найти сумму и количество отрицательных элементов, а также максимальный элемент массива.
В данной задаче предыдущий алгоритм входит как составная часть общего решения (листинг 2). Дополнительный независимый цикл с параметром:
long sum=0; // сумма отрицательных элементов
int num = 0; // количество отрицательных элементов
for ( int i = 0; i < n; ++i )
if ( a[i] < 0 )
{
sum += a[i];
++num;
}
введен в программу для выявления отрицательных элементов массива и подсчета их суммы и количества. Для переменных, в которых накапливаются сумма и количество отрицательных элементов, перед входом в цикл определены типы и начальные значения.
Листинг 2 - Работа с одномерным массивом к примеру 2
using System;
namespace ConsoleApplication1
{
class Class1
{
static void Main()
{
const int n = 6;
int[ ] a= new int[n] { 3,12,5,-9,8,-4};
Console.WriteLine( "Исходный массив:" );
for ( int i =0; i < n; ++i)
Console.WriteLine( "\t" + a[i] );
Console.WriteLine( );
long sum=0; // сумма отрицательных элементов
int num = 0; // количество отрицательных элементов
for ( int i = 0; i < n; ++i )
if ( a[i] < 0 )
{
sum += a[i];
++num;
}
Console.WriteLine( "Сумма отрицательных = " + sum );
Console.WriteLine( "Кол-во отрицательных = " + num );
int mах = a[0]; // максимальный элемент
for ( int i = 1; i < n; ++i )
if ( a[i] > mах ) mах = a[i];
Console.WriteLine( "Максимальный элемент = " + mах );
Console.Read();
}
}
}
Результаты расчета:
Пример 3. Сортировка элементов одномерного массива по убыванию методом выбора.
Введем дополнительные определения:
X - исходный массив, который нужно упорядочить;
Max- максимальный элемент массива;
Im- индекс максимального элемента;
сh- переменная для обмена элементов;
exch- признак нахождения Max в неотсортированной части массива.
Суть представленного ниже алгоритма заключается в следующем. Упорядочение начинается с поиска элемента, который должен находиться на первом месте в отсортированном массиве. Таким элементом является максимальный элемент всего массива.
После нахождения такого элемента происходит его установка на первое место в массиве, а первый элемент устанавливается на место найденного наибольшего элемента. Далее считая, что первое место в массиве занято необходимым элементом, оно исключается из рассмотрения, и описанные выше действия применяются к его оставшейся части: поиск наибольшего элемента в неупорядоченной части и его обмен с первым элементом этой части.
Листинг 3 – Сортировка одномерного массива методом «выбора»
using System;
namespace ConsoleApplication7
{
class Program
{
static void Main(string[] args)
{
const int n = 6;
int ch;
int[] x = new int[n] { 3, 12, 5, -9, 8, -4 };
Console.WriteLine("Исходный массив:");
for (int i = 0; i <= n - 1; ++i)
Console.Write(" " + x[i]);
int im = n - 1;
for (int j = 0; j <= n - 2; j++)
{
int max = x[j];
bool exch = false;
for (int i = j + 1; i <= n - 1; ++i)
if (x[i] > max)
{
max = x[i];
im = i;
exch = true;
}
if (exch == true)
{
ch = x[j];
x[j] = max;
x[im] = ch;
}
}
Console.WriteLine();
Console.WriteLine("Результирующий массив:");
for (int i = 0; i <= n - 1; ++i)
Console.Write(" " + x[i]);
Console.Read();
}
}
}
Результаты расчета:
Пример 4. Сортировка элементов одномерного массива по убыванию методом вставки.
Обозначения:
X - исходный массив, который нужно упорядочить;
n- количество элементов массива;
i,j,k- переменные цикла;
ch- переменная обмена.
Схема алгоритма представлена ниже. Суть метода состоит в следующем. Предполагается, что первый элемент массива уже стоит на своём месте. Чтобы упорядочить второй элемент массива, нужно найти для него такое место в упорядоченной части массива, чтобы упорядоченность сохранялась. Затем требуется вставить этот элемент на найденное место. Чтобы упорядочить все элементы массива, эти действия нужно выполнить n-1 раз, т.е. для всех элементов, кроме первого.
Схема алгоритма решения данной задачи по структуре представляет собой внешний цикл для выполнения указанных выше действий, который содержит еще два вложенных в него следующих друг за другом цикла.
Первый из них организован как цикл с предусловием для поиска в упорядоченной части массива такого элемента массива, чье значение будет больше величины устанавливаемого элемента. Для достижения этой цели в указанном цикле осуществляется продвижение от конца упорядоченной части к ее началу путем уменьшения номера элемента i с каждой итерацией на единицу. Выход из цикла осуществляется тогда, когда такой элемент будет найден, либо будет достигнуто начало упорядоченной части.
Следующий за ним цикл производит перемещение элементов упорядоченной части, начиная с ее конца и заканчивая i+1 элементом, на один элемент вправо для освобождения места упорядочиваемому j элементу.
После выхода из цикла (цикл с параметром) производится запись j элемента, хранимого в переменной ch, на освобожденное место.
Схема алгоритма:
Листинг 4 – Сортировка одномерного массива методом «вставки»
Листинг
using System;
namespace ConsoleApplication7
{
class Program
{
static void Main(string[] args)
{
const int n = 6;
int ch;
int[] x = new int[n] { 3, 12, 5, -9, 8, -4 };
Console.WriteLine("Исходный массив:");
for (int i = 0; i <= n - 1; ++i)
Console.Write(" " + x[i]);
for (int j = 1; j <= n - 1; j++)
{
ch = x[j];
int i = j - 1;
while ((i > -1) && (x[i] < ch))
i--;
for (int k = j - 1; k >= i+1; --k)
x[k + 1] = x[k];
x[i+1] = ch;
}
Console.WriteLine();
Console.WriteLine("Результирующий массив:");
for (int i = 0; i <= n - 1; ++i)
Console.Write(" " + x[i]);
Console.Read();
}
}
}
Результаты расчета:
Пример 5. Сортировка элементов одномерного массива по возрастанию методом «пузырька».
Обозначения:
X - исходный массив, который нужно упорядочить;
n- количество элементов массива;
i,j- переменные цикла;
ch- переменная обмена;
exch- признак существования инверсии.
Суть метода состоит в последовательном просмотре соседних элементов массива. Если они нарушают требуемый порядок следования, то они меняются местами - осуществляется инверсия. Просмотр нужно выполнить n-1 раз.
Очень существенна проверка на наличие инверсии (нарушения порядка). Если в процессе просмотра массива была осуществлена хотя бы одна инверсия (exch=TRUE), то просмотр массива повторяется. В противном случае (exch=FALSE) в массиве уже все элементы упорядочены и целесообразно прервать работу цикла оператором break.
Листинг5– Сортировка одномерного массива методом «пузырька»
using System;
namespace ConsoleApplication7
{
class Program
{
static void Main(string[] args)
{
const int n = 6;
int ch;
int[] x = new int[n] { 3, 12, 5, -9, 8, -4 };
Console.WriteLine("Исходный массив:");
for (int i = 0; i <= n - 1; ++i)
Console.Write(" " + x[i]);
for (int j = 0; j <= n - 1; j++)
{
bool exch = false;
for (int i = 0; i <= n - 2 - j; ++i)
if (x[i] > x[i + 1])
{
ch = x[i + 1];
x[i + 1] = x[i];
x[i] = ch;
exch = true;
}
if (exch == false) break;
}
Console.WriteLine();
Console.WriteLine("Результирующий массив:");
for (int i = 0; i <= n - 1; ++i)
Console.Write(" " + x[i]);
Console.Read();
}
}
}
Схема алгоритма:
Результаты расчета:
Класс System.Arrау
Для облегчения программирования задач обработки массивов данных в С# все массивы имеют общий базовый класс Аrrау, определенный в пространстве имен System. Приведем несколько полезных методов этого класса (табл. 1).
Таблица 1 - Основные элементы класса Аггау
|
Элемент |
Вид |
Описание |
|
Length |
Свойство |
Количество элементов массива (по всем размерностям) |
|
Rank |
Свойство |
Количество размерностей массива |
|
BinarySearch |
Статический метод |
Двоичный поиск в отсортированном массиве |
|
Сlear |
Статический метод |
Присваивание элементам массива значений по умолчанию |
|
Сору |
Статический метод |
Копирование заданного диапазона элементов одного массива в другой массив |
|
СоруТо |
Метод |
Копирование всех элементов текущего одномерного массива в другой одномерный массив |
|
GetValue |
Метод |
Получение значения элемента массива |
|
IndexOf |
Статический метод |
Поиск первого вхождения элемента в одномерный массив |
|
LastIndexOf |
Статический метод |
Поиск последнего вхождения элемента в одномерный массив |
|
Reverse |
Статический метод |
Изменение порядка следования элементов на обратный |
|
SetValue |
Метод |
Установка значения элемента массива |
|
Sort |
Статический метод |
Упорядочивание элементов одномерного массива |
Свойство Length позволяет реализовывать алгоритмы, которые будут работать с массивами различной длины. Использование этого свойства вместо явного задания размерности исключает возможность выхода индекса за границы массива. В листинге продемонстрировано применение двух элементов класса Аrrау при работе с одномерным массивом.
Листинг 6 – Использование методов класса Аrrау
using System;
namespace ConsoleApplication1
{
class Class1
{
static void Main()
{
int[] x = { 21, 2, 14, -6, 38, -7, 30};
Console.WriteLine();
Console.WriteLine("Исходный массив:");
for (int i = 0; i < x.Length; ++i)
Console.Write(" " + x[i]);
Array.Sort(x);
Console.WriteLine();
Console.WriteLine("Упорядоченный массив:");
for (int i = 0; i < x.Length; ++i)
Console.Write(" " + x[i]);
Array.Reverse(x);
Console.WriteLine();
Console.WriteLine("Обратный порядок в массиве:");
for (int i = 0; i < x.Length; ++i)
Console.Write(" " + x[i]);
Console.Read();
}
}
}
Методы Sort, Reverse являются статическими, поэтому к ним обращаются через имя класса Array, а не экземпляра, и передают в них имя массива.
Как видно по результатам работы программы метод Sort осуществляет сортировку массива по возрастанию. Применив к массиву, отсортированному таким образом, метод Reverse, получим массив, отсортированный по убыванию.
Результаты работы:
Класс Random
Класс Random, определенный в пространстве имен System, содержит методы, позволяющие при отладке программ генерировать исходные данные, заданные случайным образом. Особенно это удобно при отладке программ обработки массивов данных, поскольку появляется возможность освободить программиста от утомительной работы ввода последовательности данных. Разумеется, подобный вариант может быть использован лишь тогда, когда ход решения задачи позволяет применять данные, полученные путем такой генерации.
В С# для получения псевдослучайной последовательности чисел существует два варианта создания экземпляра класса Random: конструктор без параметров и конструктор с параметром типа int. Рассмотрим их.
Конструктор без параметров:
Random a = new Random( );
создает уникальную последовательность, так как использует начальное значение генератора, вычисленное на основе текущего времени.
Конструктор с параметром типа int:
Random b = new Random(5);
задает начальное значение генератора, что обеспечивает возможность получения одинаковых последовательностей чисел.
Для получения очередного значения серии пользуются методами, перечисленными в табл. 2.
Таблица 2 - Основные методы класса System.Random
|
Название |
Описание |
|
Next( ) |
Возвращает целое положительное число во всем положительном диапазоне типа int |
|
Next(макс) |
Возвращает целое положительное число в диапазоне [0, макс] |
|
Next(мин, макс) |
Возвращает целое положительное число в диапазоне [мин, макс] |
|
NextDouble() |
Возвращает вещественное положительное число в диапазоне [0. 1) |
|
NextBytes(массив) |
Возвращает массив чисел в диапазоне [0, 255] |
Первые четыре метода позволяют получить одно число. Для получения последовательности случайных чисел необходима организация цикла. Последний метод табл. 2 генерирует массив чисел.
Посмотрим результаты использования методов данного класса, которые дадут представление об их работе (листинг 7).
Листинг 7– Работа с генератором псевдослучайных чисел
using System;
namespace ConsoleApplication1
{ class Program
{ Random l = new Random( );
Random d = new Random( 1 );
const int n = 5;
Console.WriteLine( "Числа в диапазоне [0, 1]" );
for (int i = 0; i < n; ++i)
Console.Write( "{0,6:0.##}", l.NextDouble() );
Console.WriteLine();
Console.WriteLine("Числа в диапазоне [0, 100]");
for ( int i = 0; i < n; ++i )
Console.Write( " " + d.Next( 100 ) );
Console.WriteLine();
Console.WriteLine("Числа в диапазоне [-5, 5]");
for ( int i = 0; i < n; ++i )
Console.Write( " " + l.Next( -5, 5) );
Console.WriteLine();
Console.WriteLine("Массив чисел в диапазоне[0, 255]");
byte[ ] mas = new byte[n];
l.NextBytes(mas);
for (int i = 0; i < n; ++i)
Console.Write(" " + mas[i] );
}
}
}
Результат работы программы:
3. Варианты заданий для самостоятельной работы
Программа. Дано 100 целых чисел. Отсортировать их по возрастанию и распечатать их в обратном порядке по 6 чисел в строке.
x(0)=x(0), x(n)=x(n), x(k)=(x(k)-1+x(k)+x(k)+1)/3 при k=2,3,...,n-1.
Вычислить: a[0]/1! + a[1]/2! +...+ a[5]/5!.
4.1. Титульный лист.
4.2. Краткое теоретическое описание.
4.3. Задание на лабораторную работу, включающее математическую формулировку задачи.
4.4. Результаты выполнения работы, включающие схему алгоритма, тексты программ, результаты вычислений.
PAGE \* MERGEFORMAT 87
a[0]
[1]
a[2]
a[4]
a[3]
z[0]
z[1]
z[4]
z[2]
z[3]
Значение
Значение
Значение
Значение
Значение