Учебно-методическое пособие Тольятти тгу 2011 удк 004. 3(075) ббк 32. 97

Вид материала

Учебно-методическое пособие

Содержание 2.4Массивы как последовательные структуры данных 2.4.1Массивы одномерные. Описание массивов Объём памяти в байтах = sizeof(базовый тип элемента) * длина массива. 2.4.2Типовые алгоритмы обработки массивов 2.4.3Вопросы для самоконтроля

Подобный материал:

• Учебно-методическое пособие Казань 2006 удк. 316. 4 (075); 11. 07. 13 Ббк 72; 65я73, 2129.18kb.
• Учебно-методическое пособие Новочеркасск юргту (нпи) 2011 г. Удк 004 : 012 (076) ббк, 1329.07kb.
• Учебно-методическое пособие Новочеркасск юргту (нпи) 2011 г. Удк 004 : 012 (076) ббк, 994.64kb.
• Пособие адресовано студентам, изучающим основы самоорганизации, а также всем тем, кто, 2706.76kb.
• Учебно-методическое пособие Нижний Новгород 2010 удк 338. 24(075. 8) Ббк 65. 290-2я73, 2121.39kb.
• Учебно-методическое пособие по изучению дисциплины, 1772.48kb.
• Учебно-методическое пособие Минск 2009 удк 618. 19-006. 03 (075. 9) Ббк 57. 15я73, 956.31kb.
• Учебное пособие Санкт-Петербург 2008 удк 005. 91: 004. 9(075. 8) Ббк 65. 291. 212., 97.7kb.
• Учебно-методическое пособие Майкоп 2009 удк 811. 133. 1(075. 8) Ббк 81. 471. 1-923, 489.6kb.
• Учебное пособие Ульяновск 2010 удк 004. 8(075. 8) Ббк 32. 813я73, 1559.86kb.

2.4Массивы как последовательные структуры данных

Оперативная память с точки зрения программиста – это массив элементов. Любой элемент массива можно прочитать или записать сразу, за одно элементарное действие. Массив можно рассматривать как простейшую структуру данных. Структуры данных, в которых возможен непосредственный доступ к произвольным их элементам, называют структурами данных с прямым, или с произвольным доступом (по-английски random access). Наряду с массивом, структурой данных с прямым доступом является множество. В других структурах данных непосредственный доступ возможен лишь к одному или нескольким элементам, для доступа к остальным элементам надо выполнить дополнительные действия. Такие структуры данных называются структурами последовательного доступа. Примером структуры последовательного доступа является магнитофон, на которым записаны песни. В любой момент можно прослушать лишь очередную песню. Чтобы добраться до других музыкальных фрагментов, надо перемотать ленту вперед или назад. Кстати, такие магнитофоны, или накопители на магнитной ленте, очень долго использовались на ЭВМ, хотя сейчас уступили свое место более надёжным и компактным системам (съёмным магнитным и оптическим дискам, флэш-памяти и т.п.). Устройство компьютерного магнитофона было аналогично устройству обычного бытового магнитофона.

С логической точки зрения, массивом является также важнейшая составляющая компьютера – магнитный диск. Элементарной единицей чтения и записи для магнитного диска служит блок. Размер блока зависит от конструкции конкретного диска, обычно он кратен 512. За одну элементарную операцию можно прочесть или записать один блок с заданным адресом.

Итак, наиболее важные запоминающие устройства компьютера – оперативная память и магнитный диск – представляют собой массивы. Массив как бы дан программисту свыше, так же как математику целые числа. Работа с элементами массива осуществляется исключительно быстро, все элементы массива доступны без всяких предварительных действий.

Тем не менее, массивов недостаточно для написания эффективных программ. Например, поиск элемента в массиве, если его элементы не упорядочены, невозможно реализовать эффективно: нельзя изобрести ничего лучшего, кроме последовательного перебора элементов. В случае упорядоченного хранения элементов можно использовать эффективный бинарный поиск, но затруднения возникают при добавлении или удалении элементов в середине массива и приводят к массовым операциям, т.е. операциям, время выполнения которых зависит от числа элементов структуры. От этих недостатков удаётся избавиться, реализуя множество элементов на базе сбалансированных деревьев или хеш-функции.

Есть и другие причины, по которым необходимо использовать более сложные, чем массивы, структуры данных. Логика многих задач требует организации определённого порядка доступа к данным. Например, в случае очереди элементы можно добавлять только в конец, а забирать только из начала очереди; в стеке доступны лишь элементы в вершине стека, в списке – элементы до и за указателем.

Наконец, массив имеет ограниченный размер. Увеличение размера массива в случае необходимости приводит к переписыванию его содержимого в захваченную область памяти большего размера, т.е. опять же к массовой операции. От этого недостатка свободны ссылочные реализации структур данных: реализации на основе линейных списков или на основе деревьев.

2.4.1Массивы одномерные. Описание массивов

Как и другие переменные, массив должен быть объявлен. Существует несколько способов объявления массива.

Общая форма объявления одномерного массива имеет следующий вид:

<класс> тип имя [размер]

где класс – необязательный элемент, определяющий класс памяти (extern, static, register);

тип – базовый тип элемента массива;

имя – идентификатор массива;

размер – количество элементов в массиве.

Доступ к элементу массива осуществляется с помощью имени массива и индекса. Индекс элемента массива помещается в квадратных скобках после имени. Нижнее значение индекса всегда нуль.

Таким образом, элементами массива, состоящего из N элементов, являются переменные с индексами a[0], a[1], …, a[N–1]. В качестве N в описании должна стоять целая положительная константа.

Ниже приведён пример программы, находящей сумму 15 чисел.

# include 

# define N 15

int main()

{

float x[N],s;

int i;

for (i=0,s=0;i

{

printf("\n Input x[%d]",i);

scanf("%f",&x[i]);

s+=x[i];

}

printf("\n S=%f",s);

return 0;

}

Объём памяти, необходимый для хранения массива, определяется типом элемента массива и количеством элементов, входящих в массив.

Для одномерного массива требуемый объем памяти вычисляется следующим образом:

Объём памяти в байтах = sizeof(базовый тип элемента) * длина массива.

Во время выполнения программы не проверяется ни соблюдение границ массива, ни его содержимое. Задача проверки и соответственно корректности выполнения программы возложена на программиста.

В языке C массивы при объявлении можно инициализировать. Общая форма инициализации массива аналогична инициализации переменной:

<класс> тип имя [размер] = {список значений};

Список значений представляет собой список констант, перечисленных в фигурных скобках через запятую. Типы констант должны быть совместимы с типом массива. Первая константа присваивается первому элементу массива, имеющему индекс нуль, вторая – второму и так далее. После закрывающей фигурной скобки точка с запятой обязательна:

static float x[5]={7.5,0,–3.2,0,4};

В этом случае будет создан массив на 5 элементов. Если в списке инициализации задать количество элементов меньше, чем задано в объявлении массива, то остальные элементы принимаются равными нулю. Если в списке инициализации задать количество элементов больше, чем задано в объявлении массива, это вызовет ошибку при компиляции программы.

При инициализации допустима и следующая форма объявления:

<класс> тип имя [] = {a₀,a₁,…,a_М–1};

В этом случае компилятор сам создаёт массив из М элементов, присваивая им значения a₀, a₁, …, a_М–1.

2.4.2Типовые алгоритмы обработки массивов

В программировании существует ряд классических алгоритмов, которые можно рассматривать как основные операции. Комбинируя эти алгоритмы и видоизменяя их применительно к конкретным условиям, можно решать многие практические задачи. Ниже рассмотрены некоторые из этих алгоритмов. Вo всех приведённых примерах общее количество элементов массива, которое необходимо ввести для решения задачи, задано в директиве препроцессора #define, что является хорошей практикой программирования.

Каждый пример является законченной программой, а количество элементов задано равным 5, чтобы при желании можно было набрать приведённый текст программы и проверить её работу без необходимости вводить большое количество исходных данных.

Пример 1. Задан одномерный массив, состоящий из SIZE элементов. Требуется подсчитать сумму этих элементов.

Эта задача решается следующим образом. Обозначим переменную для накопления суммы как sum, а исходный массив обозначим а. Естественно, в начале программы этот массив, переменная sum и переменная, которая будет использоваться в качестве индекса элементов массива, должны быть описаны.

Для ввода элементов массива оформим цикл, который обеспечит последовательное изменение индекса от 0 до SIZE-1. Тогда на каждом шаге цикла в массив a будет вводиться одно число, которое будет набрано с клавиатуры. Индекс элемента, в который будет записываться вводимое число, совпадает с текущим значением переменной цикла.

После ввода массива приравняем к нулю переменную sum, затем откроем цикл с переменной i, которая последовательно изменяется от 0 до SIZE-1, и, прибавляя по очереди каждый последующий элемент массива к накапливаемой в переменной sum величине, получим требуемую сумму. После окончания цикла выведем полученный результат.

Ниже приведён текст программы, решающей поставленную задачу.

#include

#include

#define SIZE 5

void main() {

/* Объявление пеpеменных */

double a[SIZE], sum;

int i;

/* Очистка экpана */

clrscr();

printf("Введите %d чисел\n",SIZE);

for (i = 0; i < SIZE; i++)

scanf("%lf", &a[i]);

/* Суммиpование элементов массива */

sum = 0;

for (i = 0; i < SIZE; i++)

sum = sum + a[i];

/* Вывод полученного результата */

printf("\nСумма равна %f", sum);

}

Программа работает следующим образом. Оператор double a[SIZE]; резервирует память для размещения SIZE (в данном случае 5) чисел с плавающей точкой. Этот оператор может только резервировать память, но никаких значений элементам не присваивает (точнее на выделенном участке памяти хранится информация, которая осталась от предыдущей программы и обычно совершенно бессмысленна).

Выполним статическое тестирование программы. Введем для массива а значения, например, такие: 1.7; 2.91; -0.8; 9.64; 3.4. Массив а вводится, как было отмечено выше. После присвоения sum значения нуль открывается цикл, т.е. переменной цикла i присваивается начальное значение 0 и выполняется собственно цикл. В данном случае тело цикла содержит один оператор, который к начальному значению переменной sum (которое равно 0) прибавляет значение первого элемента массива а, которое равно 1.7, и эту сумму присваивает переменной sum. На этом операторе проверяется условие выхода из цикла. Поскольку i меньше SIZE, то цикл повторяется, но i принимает значение 1. Снова к предыдущему значению sum (=1.7) прибавляется значение элемента а[1], равное 2.91. Результат (4.61) присваивается переменной sum. Поскольку i не достигло значения SIZE-1, то процесс повторяется, и переменная sum далее последовательно получает значения

4.61 + (-0.8) = 3.81

3.81 + 9.64 = 13.45

13.45 + 3.4 = 16.85

При суммировании последнего элемента массива переменная цикла i имеет значение 4 (т.е. SIZE-1). В языке Си во время выполнения операторов цикла типа for значение переменной цикла как бы «запаздывает» на один шаг. Например, в операторе цикла переменной цикла было присвоено значение 0, но там же было записано и приращение этой переменной. Поэтому следовало бы ожидать, что выполнение цикла начнется со значения i=1, но первый раз цикл выполняется при значении i=0. Таким образом, хотя приращение переменной цикла и записано в заголовке операторов цикла после присвоения начального значения, но фактически это приращение выполняется после реализации всех операторов цикла непосредственно перед повторением цикла. Поэтому при попытке последующего повторения цикла переменная i принимает значение SIZE (равное 5), условие продолжения цикла оказывается ложным (теперь i не меньше SIZE), следовательно, цикл закончен, и выполнение программы продолжается с оператора, записанного сразу после «тела» цикла. Этим оператором осуществляется вывод значения переменной sum (равное 16.85), и выполнение программы заканчивается.

Во всех последующих примерах статическое тестирование программы производиться не будет. При желании можно его выполнить самостоятельно для лучшего понимания работы программ.

Пример 2. Подсчитать количество положительных элементов в массиве, состоящем из SIZE элементов. Эта задача отличается от предыдущей тем, что суммируются не сами элементы, а подсчитывается их количество, причём не всех элементов (количество всех элементов известно заранее, оно равно SIZE), а только тех, которые больше нуля.

Для решения этой задачи некоторая переменная (целочисленная), скажем n, выделяется для подсчета количества элементов. После объявления переменных и ввода значений элементов массива этой переменной присваивается значение нуль. После этого в цикле последовательно просматриваются элементы массива.

Если очередной элемент массива больше нуля, то к предыдущему значению переменной n прибавляется единица, если же очередной элемент равен или меньше нуля, то добавление 1 пропускается. Когда все элементы будут просмотрены (т.е. цикл будет «закрыт»), переменная n будет содержать количество положительных элементов.

Ниже приведён текст программы, решающей поставленную задачу

#include

#include

#define SIZE 5

void main() {

/* Объявление пеpеменных */

double a[SIZE];

int i,n;

/* Очистка экpана */

clrscr();

printf("Введите %d чисел\n",SIZE);

for (i = 0; i < SIZE; i++)

scanf("%lf", &a[i]);

/* Подсчёт количества положительных элементов */

n = 0;

for (i = 0; i < SIZE; i++)

if (a[i] > 0) n++;

printf("\nКоличество положительных чисел равно %d" ,n);

}

Пример 3. Задан одномерный массив, состоящий из SIZE элементов. Найти максимальный элемент.

Решение заключается в следующем. Выберем «кандидата» на максимальный элемент и назовём его аmах. Теперь будем последовательно сравнивать amaх c элементами массива. Если очередной элемент массива больше amaх, то заменим «кандидата» на максимальный элемент элементом массива и запомним его индекс. Если же очередной элемент массива меньше amaх, то никаких действий выполнять не будем, а перейдем к следующему элементу. Когда таким способом будут обработаны все элементы массива, amaх будет содержать значение максимального из элементов массива.

В этом решении есть неясности. Во-первых, каким образом первоначально выбрать «кандидата» на максимальный элемент. Для этого существуют два способа. Первый способ предусматривает выбор в качестве «кандидата» любого элемента массива, например, первого. Этот способ обычно применяется, когда перед началом поиска элементы массива уже существуют. Но задача поиска максимального (или минимального) элемента может быть решена и при одновременном формировании элементов массива и поиска среди них максимального (или минимального) элемента. В этом случае в качестве «кандидата» на максимальный элемент можно выбрать минимально возможное в данной ЭВМ число (при поиске минимума соответственно выбирают максимально возможное число), например, для чисел типа double таким значением является -1.7Е+308 (но можно выбрать число и меньшее по абсолютному значению, например -1.0E100, поскольку при решении реальных задач не может быть таких чисел). Во-вторых, как поступать, если «кандидат» на максимальный элемент и очередной элемент массива равны друг другу. В принципе это зависит от решаемой задачи. Если при равенстве мы будем пропускать обработку для текущего элемента, то обеспечим выбор первого из нескольких равных максимальных элементов. Если же при равенстве мы будем выполнять обработку (т.е. заменять значение «кандидата» значением текущего элемента массива и запоминать его индекс), то само значение при равенстве, естественно, одинаково, но индексы этих элементов разные. В этом случае будет обеспечен выбор последнего из нескольких равных максимальных элементов.

Для поиска минимального элемента в алгоритме требуется изменить на обратное условие проверки, и желательно изменить имя amax, например, на amin. И последнее, для «кандидата» на максимальный элемент в программе использовано специальное имя (amaх), что удобно для анализа работы программы. Иногда в программу не вводят такую дополнительную переменную, а вместо этого используют значение индекса текущего максимального элемента (в примере этот индекс имеет имя n). Принципиально, это также правильное решение, но менее наглядное. Кроме того, на реализацию алгоритма в этом случае будет затрачено чуть больше времени, поскольку время обращения к индексированной переменной больше времени обращения к обычной переменной на время вычисления адреса элемента по индексу.

Ниже приведён текст программы, решающей эту задачу.

#include

#include &360;conio.h>

#define SIZE 5

void main() {

double a[SIZE], amax;

int i,n;

/* Очистка экpана */

clrscr();

/* Ввод элементов массива */

printf("Введите %d чисел\n",SIZE);

for (i = 0; i < SIZE; i++)

scanf("%lf", &a[i]);

/* Назначение «кандидата» на максимальный элемент */

amax = a[0];

n = 0;

/* Поиск максимального элемента массива */

for (i = 0; i < SIZE; i++)

if (a[i] > amax) {

amax = a[i];

n = i;

}

/* Вывод найденного максимального элемента массива */

printf("\nМаксимальное число равно %g, его индекс %d",amax,n);

}

Во всех рассмотренных выше программах операция ввода элементов массива выполнялась отдельно от операций по их обработке, но в этих примерах последовательность ввода элементов совпадает с порядком их обработки, поэтому эти операции можно совместить. Для этого достаточно функцию ввода элементов массива (scanf) записать перед операцией обработки, а цикл ввода исключить. Перед началом цикла в этом случае значение элемента a[0] неизвестно (поскольку этот элемент еще не введён), поэтому для назначения «кандидата» на максимальный элемент следует использовать минимально возможное число, т.е. для переменной amax присвоить значение, например, -1е100. Другими словами, вместо оператора amax = a[0]; записать amax = -1e100;

2.4.3Вопросы для самоконтроля

1. 
   С какого числа начинается нумерация элементов массива?
   
2. С какой целью используются массивы?
   
3. Каким образом задаётся описание массива, что в нём указывается?
   
4. Что представляет собой массив как структура данных?
   
5. Что называют инициализацией массива?
   
6. Какие операторы используются для обработки массивов?
   
7. Пусть объявлен массив int p[]={2, 4, 6, 10, 1};. Чему равно значение элемента p[3]?
   
8. Что является результатом выполнения нижеприведённого фрагмента программы?
   

Int x[]={5,2,3,0,8};

FOR(i=1;i<=3;i++){cout>>”\n”>>x[i];}

9. Каким должен быть тип индекса массива?
   
10. Опишите массив A, содержащий 10 элементов целого типа.
    
11. Пусть объявлен массив int m[6]={5, 3, 2};. Чему равен элемент m[4]?
    
12. Чему равно нижнее значение индекса?
    
13. Что является результатом выполнения нижеприведённого фрагмента программы?
    

For (i=0;i<=5;i++) {A[i]=i; cout <