Массивы. Двумерные массивы

Министерство образования и науки Республики Казахстан

Казахстанский Инженерно Технологический университет

(колледж)

Кафедра «Вычислительная техника, автоматизация и телекоммуникация»

Курсовая работа

по дисциплине

программирование

Тема: Массивы. Двумерные массивы

Выполнила:<ИС> 3 курс Исмаилова А. С.

Проверила: Желилова К.А.

Алматы, 2010г

Содержание:

1.Введение

1)История создания языка Pascal

2)Краткий обзор языка

2.Основная часть

1)Массив.

2)Одномерные массивы

3)Алгоритмы сортировки одномерных массивов

4)Массивы в языках Pascal и Basic

5)Массив в Бейсике

6)Массив в Паскале

7)Двумерные массивы Паскаля - матрицы

8)Описание двумерного массива Паскаля

9)Основные действия с двумерными массивами Паскаля

10)Ввод двумерного массива Паскаля

11)Вывод двумерного массива Паскаля на экран

12)Представление двумерного массива Паскаля в памяти

13)Методы доступа к элементам массивов

14)Индексный массив

15)Специфические типы массивов

16)Динамические массивы

17)Гетерогенные массивы

3.Заключение

1)Основная

2) Дополнительная

Список литературы

1)основная литература

2)дополнительная дополнительная

Введение

Развитие современного общества предполагает широкое использование компьютерных и информационных технологий, на основе которых создаются разнообразные информационные системы. Обычно получаемая в них информация анализируется человеком, который будет играть определяющую роль. Такие информационные системы являются автоматизированными, так как в их функционировании принимает участие человек.

Компьютерные программы получают результаты, обрабатывая данные. Легкость, с которой выполняется этот процесс, зависит от того, насколько точно типы данных соответствуют реальной задаче. Следовательно, очень важно, чтобы в языке была предусмотрена поддержка соответствующего разнообразия типов и структур данных.

Современные концепции типов данных развиваются на протяжении последних 40 лет. В ранних языках программирования все структуры данных, соответствующие конкретным задачам, моделировались небольшим количеством основных структур данных, поддерживаемых этими языками. Например, в версиях языка FORTRAN, разработанных до языка FORTRAN 90, связные списки и двоичные деревья обычно моделировались с помощью массивов.

Первый шаг в сторону от модели, использованной в языке FORTRAN I, был сделан разработчиками структур данных в языке COBOL, позволившими программистам устанавливать точность десятичных чисел и предложившими использовать структурные типы данных для представления записей, содержащих информацию.

Концепции разработки типов данных, появившиеся в конце 1970-х годов в результате естественного обобщения идеи типов, определяемых пользователем, были воплощены в языке Ada 83. Методология, лежащая в основе определяемых пользователем типов данных, состоит в том, что программисту следует позволить создавать отдельный тип для каждого отдельного класса переменных, определяемых предметной областью задачи. Более того, язык должен обеспечивать уникальность типов, являющихся, фактически, абстракциями переменных из предметной области задачи. Это довольно мощная концепция, оказывающая значительное влияние на общий процесс разработки программного обеспечения.

Двумя самыми распространенными структурными (нескалярными) типами данных являются массивы и записи. Они, а также несколько других типов данных, задаются операторами типов, или конструкторами, используемыми для создания переменных данного типа. В качестве примера операторов типа можно назвать существующие в языке С круглые и квадратные скобки, а также звездочки, используемые для задания массивов, функций и указателей.

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

Актуальность темы заключается в том, что ни один язык программирования не обходится без описанной структуры данных.

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

История создания языка Pascal

Pascal разрабатывался с 1968 по 1970 г. Николаусом Виртом. Цель заключалась в том, чтобы создать язык, лишенный многочисленных недостатков ALGOL. Pascal был назван в честь французского математика Блеза Паскаля, который еще в 1642 г. изобрел цифровой калькулятор. С конца 70-х до конца 80-х гг. этот язык доминировал среди языков, используемых на начальном этапе обучения программированию; позже его заменили С и C++, а затем Java.

ALGOL 60 был первой попыткой создания языка на основе формального описания, однако его реализация оказалась сложной. В частности, оказалось достаточно трудно реализовать передачу параметров по имени, хотя это довольно элегантный механизм. В языке ALGOL 60 не были определены операторы ввода-вывода, поскольку в то время считалось, что они зависят от реализации, да и собственную статическую память также трудно было реализовать. Помимо того, в 60-х гг. были разработаны новые практические решения, например типы данных и структурное программирование. Языки типа FORTRAN были популярны благодаря своей эффективности при выполнении программ, несмотря на отсутствие элегантности.

В 1965 г., во время работы в Стенфордском университете (Stanford University), Вирт разработал новую, расширенную версию ALGOL 60 для компьютеров серии IBM 360, в которую вошло определение указателей и структур данных. Этот язык, известный как ALGOLW, использовался в нескольких университетах, но его реализация ограничивалась только компьютерами IBM 360. Для выполнения программ на этом языке требовался значительный по размерам пакет программ поддержки обработки строк, вещественных чисел двойной точности и других сложных типов данных. Таким образом, ALGOL W в качестве системного языка программирования оказался малоэффективным.

В 1968 г. Вирт вернулся в Швейцарию и начал работу над преемником ALGOL W - языком, который мог бы компилироваться за один проход. Для создания исходного компилятора был использован алгоритм рекурсивного спуска. Этот компилятор выполнялся на компьютере Control Data. Также был разработан широко известный теперь интерпретатор Р-кода. Компилятор языка Pascal сначала транслировал исходную программу в программу на языке гипотетической машины со стековой архитектурой. Благодаря такой своей организации Pascal легко переносился на компьютеры других систем. Компилятор Pascal был написан на одноименном языке. Все, что требовалось для перехода в другую систему, - это переписать соответствующим образом интерпретатор Р-кода.Появившийся в 1970 г. Pascal начал завоевывать признание.В 1983 г. был разработан американский стандарт языка (IEEE 770/ ANSI X3.97), а вскоре был разработан стандарт ISO (ISO 7185).

Краткий обзор языка

Структура программ на языке Pascal напоминает программы на С. Тем не менее в Pascal предусмотрена возможность описания внутренних локальных процедур и создания вложенной иерархии имен. Программа на Pascal представляет собой единый программный блок, в котором содержатся определения используемых подпрограмм.

В Pascal имеется достаточно широкий набор простых и структурированных типов данных: целые и вещественные числа, символьные данные, перечисления, логические (булевы) значения, массивы, записи, последовательные файлы и ограниченный тип множеств. Оператор type позволяет программисту определять новые типы данных, хотя не обеспечивает группирование и инкапсуляцию определения нового типа данных с набором подпрограмм, обеспечивающих выполнение основных операций над объектами данных этого нового типа. Кроме того, указатель и операция создания новых объектов данных любого типа позволяют программисту конструировать новые объекты связанных данных непосредственно во время выполнения программы.

Подпрограммы принимают форму функций (если они возвращают одно какое-либо значение) или процедур (если их действие сводится к модификации переданных параметров или глобальных переменных). Операторы управления последовательностью действий базируются на конструкциях структурного программирования: составных операторах, условных операторах и операторах выбора (case), а также трех видах операторов цикла. В Pascal имеется также оператор goto, который редко используется и без которого практически всегда можно обойтись. Вызов подпрограмм и возвращение значений осуществляется с помощью обычной рекурсивной структуры вызова-возврата.

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

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

Из вспомогательных подпрограмм нужны в основном стандартные программы ввода-вывода для последовательных файлов и процедуры для управления ресурсами памяти.

Хотя Pascal в целом очень удобный и полезный язык, у него есть свои недостатки, перечень которых приведен ниже.

1. В определении этого языка имеется некоторое противоречие между идеологией самого языка и его реализацией. Например, конструкция forward нужна только для того, чтобы компиляция могла выполняться в один проход, - это следствие представлений о том, что таким образом достигается максимальная эффективность компиляции. Но это не всегда верно. Например, компилятор PL/C для языка PL/I совершал три прохода и вместе с тем являлся одним из самых эффективных среди наиболее распространенных компиляторов своего времени . Кроме того, в настоящее время при использовании недорогих быстродействующих компьютеров скорость компиляции не имеет большого значения.

2. Возможно, самой главной слабостью языка Pascal является то, что массивы рассматриваются как отдельные типы, а не как агрегация различных объектов одного типа. Это приводит к тому, что, например, array [1. .10] of Integer и аггау[1. .20] of integer представляют собой/разные типы данных. В результате алгоритмы обработки массивов усложняются, поскольку массивы различных размеров невозможно передать общей подпрограмме (например, подпрограмме перемножения матриц). Строки реализованы как массивы символов, что также затрудняет их обработку в случае строк различной длины.

3. Синтаксис определения процедуры в Pascal выглядит следующим образом: заголовок процедуры локальные переменные локальные параметры begin тело процедуры end. Поскольку в программе может содержаться большое количество вложенных локальных процедур, то определение локальной переменной, которая используется в какой-либо процедуре, оказывается (синтаксически) сильно отдаленным от места ее использования в теле подпрограммы. Это приводит к затруднениям при создании документации и чтении больших программ на Pascal.

4. Возможности, предоставляемые языком, должны выполняться не с помощью пропуска некоторой информации, а явным указанием этой информации. В Pascal передача параметров нарушает это правило. Все параметры в Pascal передаются по значению, если только в списке параметров не указан явным образом атрибут var, который означает, что соответствующий параметр должен передаваться по ссылке.Многие начинающие программисты часами

рассматривали листинги программ, стараясь обнаружить ошибку, связанную с пропуском ключевого слова var.

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

было принято соглашение, что допускаются дополнительные внешние процедуры, аналогичные заголовочным файлам с расширением h в языке С. Но такая нестандартная реализация ограничивает возможность перенесения программ на Pascal на другие машины.

6. Хотя в Pascal допускается определение новых типов данных для поддержки абстракций, в нем фактически не предусмотрена возможность инкапсуляции и сокрытия информации.Это замечание является скорее не критикой данного языка,а комментарием,касающимся общего уровня развития программирования в 1970 г., когда создавался Pascal.

Массив - это множество однотипных элементов, объединённых общим именем и занимающих в компьютере определённую область памяти. Количество элементов в массиве всегда конечно. В общем случае массив - это структурированный тип данных, состоящий из фиксированного числа элементов, имеющих один и тот же тип. Название регулярный тип (или ряды) массивы получили за то, что в них объединены однотипные (логически однородные) элементы, упорядоченные (урегулированные) по индексам, определяющим положение каждого элемента в массиве. В качестве элементов массива можно использовать любой тип данных, поэтому вполне правомерно существование массивов записей, массивов указателей, массивов строк, массивов и т.д.Элементами массива могут быть данные любого типа, включая структурированные.Тип элементов массива называется базовым. Особенностью языка Паскаль является то, что число элементов массива фиксируется при описании и в процессе выполнения программы не меняется. Элементы, образующие массив, упорядочены таким образом, что каждому элементу соответствует совокупность номеров (индексов), определяющих его местоположение в общей последовательности. Доступ к каждому отдельному элементу осуществляется путем индексирования элементов массива. Индексы представляют собой выражения любого скалярного типа (чаще целого), кроме вещественного. Тип индекса определяет границы изменения значений индекса. Для описания массива предназначено словосочетание array of (массив из).

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

Одномерные массивы

Алгоритмы сортировки одномерных массивов. Сортировка - один из наиболее распространённых процессов современной обработки данных. Сортировкой называется распределение элементов массива в соответствии с определёнными правилами. Например, сортировка массива по возрастанию или убыванию его элементов. Обменная сортировка (метод "пузырька"). Алгоритм начинается со сравнения 1-го и 2-го элементов массива.

Если 2-й элемент меньше 1-го, то они меняются местами. Этот процесс повторяется для каждой пары соседних элементов массива, пока все N элементов не будут обработаны. За один "проход" массива самый большой элемент встанет на старшее (N-е) место. Далее алгоритм повторяется, причем например "проходе" первые (N-p) элементов сравниваются со своими правыми соседями. Если на очередном "проходе" перестановок не было, то алгоритм свою работу закончил. Таким образом, самые "легкие" элементы в процессе исполнения алгоритма постепенно "всплывают".

Сортировка вставками. Вначале упорядочиваются два первых элемента массива. Они образуют начальное упорядоченное множество S. Далее на каждом шаге берется следующий по порядку элемент и вставляется в уже упорядоченное множество S так, чтобы слева от него все элементы были не больше, а справа не меньше обрабатываемого. Место для вставки текущего элемента в упорядоченное множество S ищется методом деления пополам. Алгоритм сортировки заканчивает свою работу, когда элемент, стоящий на N-м месте, будет обработан. (Именно таким образом игроки в бридж обычно упорядочивают свои карты).

Сортировка выбором. Находится наибольший элемент в массиве из N элементов (пусть он имеет номер р) и меняется местами с элементом, стоящим на N-м месте, при условии, что N<>p. Из оставшихся (N-1) элементов снова выделяется наибольший и меняется местами с элементом, стоящим на (N-1)-м месте и т. д. Алгоритм заканчивает свою работу, когда элементы, стоящие на 1-м и 2-м местах в массиве, будут упорядочены (для этого понадобится N-1 "проход" алгоритма). Аналогично данный алгоритм можно применять и к наименьшим элементам.

Действия над массивами

Для работы с массивом как единым целым используется идентификатор массива без указания индекса вквадратных скобках. Массив может участвовать только воперациях отношения "равно", "не равно" и воператоре присваивания. Массивы, участвующие вэтих действиях, должны быть идентичны по структуре, т. е. иметь одинаковые типы индексов и одинаковые типы компонентов.Например, если массивы А и Вописаны как var А, В: array[1..20] of real;то применение к ним допустимых операций даст следующий результат:выражение результат А=ВTrue,если значение каждого элемента массива А равно соответствующему значению элемента массива ВА<>ВTrue, если хотя бы одно значение элемента массива А не равно значению соответствующего элемента массива ВА:=В все значения элементов массива В присваиваются соответствующим элементам массива А. Значения элементов массива В остаются неизменны.

Действия над элементами массива После объявления массива каждый его элемент можно обработать, указав идентификатор (имя) массива и индекс элемента в квадратных скобках. Например, запись Mas[2], VectorZ[10] позволяет обратить- ся ко второму элементу массива Mas и десятому элементу массива VectorZ.

При работе с двумерным массивом указываются два индекса, с n-мерным массивом - n индексов. Например, запись MatrU[4,4] дела- ет доступным для обработки значение элемента, находящегося в чет- вертой строке четвертого столбца массива MatrU. Индексированные элементы массива называются индексированными пе- ременными и могут быть использованы так же, как и простые пере- менные. Например, они могут находиться в выражениях в качестве операндов, использоваться в операторах for, while, repeat, вхо- дить в качестве параметров в операторы Read, Readln, Write,

Массивы в языках Pascal и Basic

С понятием "массив" приходится сталкиваться при решении научно-технических и экономических задач обработки совокупностей большого количества значений.

Массив в Бейсике. Описывать массив DIM A(N) - это значит предоставить < N > свободных ячеек в памяти ЭВМ для массива с именем А. Если описание массива отсутствует, то под одномерный массив выделяется 10 ячеек памяти. Каждый элемент массива в общем виде описывается как А(I), где А - имя массива, I -номер или индекс массива (0<=I<= N, но практически употребляется 1<=I<=N) A(I) - значение элемента массива.

Массив в Паскале. <имя массива>:= array <количество элементов> of <тип переменной>; Каждый элемент массива в общем виде описывается как А[I], где А - имя массива, I - номер или индекс массива (0<=I<=N, но практически употребляется 1<=I<=N) A[I] - значение элемента массива.

Wri- teln; им можно присваивать любые значения, соответствующие их типу.

Двумерные массивы Паскаля - матрицы

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

Рассмотрим двумерный массив Паскаля размерностью 3*3, то есть в ней будет три строки, а в каждой строке по три элемента:

Каждый элемент имеет свой номер, как у одномерных массивов, но сейчас номер уже состоит из двух чисел - номера строки, в которой находится элемент, и номера столбца. Таким образом, номер элемента определяется пересечением строки и столбца. Например, a 21 - это элемент, стоящий во второй строке и в первом столбце.

Описание двумерного массива Паскаля.

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

Мы уже умеем описывать одномерные массивы, элементы которых могут иметь любой тип, а, следовательно, и сами элементы могут быть массивами. Рассмотрим следующее описание типов и переменных:

Пример описания двумерного массива Паскаля

Type

Vector = array [1..5] of <тип_элементов>;

Matrix= array [1..10] of vector;

Var m: matrix;

Мы объявили двумерный массив Паскаля m, состоящий из 10 строк, в каждой из которых 5 столбцов. При этом к каждой i -й строке можно обращаться m [ i ], а каждому j -му элементу внутри i -й строки - m [ i , j ].

Определение типов для двумерных массивов Паскаля можно задавать и в одной строке:

Type

Matrix= array [1..5] of array [1..10] of < тип элементов >;

или еще проще:

type

matrix = array [1..5, 1..10] of <тип элементов>;

Обращение к элементам двумерного массива имеет вид: M [ i , j ]. Это означает, что мы хотим получить элемент, расположенный в i -й строке и j -м столбце. Тут главное не перепутать строки со столбцами, а то мы можем снова получить обращение к несуществующему элементу. Например, обращение к элементу M [10, 5] имеет правильную форму записи, но может вызвать ошибку в работе программы.

Основные действия с двумерными массивами Паскаля

Все, что было сказано об основных действиях с одномерными массивами, справедливо и для матриц. Единственное действие, которое можно осуществить над однотипными матрицами целиком - это присваивание. Т.е.,если в программе у нас описаны две матрицы одного типа, например,

type

matrix= array [1..5, 1..10] of integer;

var

a , b : matrix ;

то в ходе выполнения программы можно присвоить матрице a значение матрицы b ( a := b ). Все остальные действия выполняются поэлементно, при этом над элементами можно выполнять все допустимые операции, которые определены для типа данных элементов массива. Это означает, что если массив состоит из целых чисел, то над его элементами можно выполнять операции, определенные для целых чисел, если же массив состоит из символов, то к ним применимы операции, определенные для работы с символами.

Ввод двумерного массива Паскаля

Для последовательного ввода элементов одномерного массива мы использовали цикл for, в котором изменяли значение индекса с 1-го до последнего. Но положение элемента в двумерном массиве Паскаля определяется двумя индексами: номером строки и номером столбца.

Это значит, что нам нужно будет последовательно изменять номер строки с 1-й до последней и в каждой строке перебирать элементы столбцов с 1-го до последнего. Значит, нам потребуется два цикла for , причем один из них будет вложен в другой.

Рассмотрим пример ввода двумерного массива Паскаля с клавиатуры:

type

matrix= array [1..5, 1..10] of integer;

var

a, : matrix;

i, j: integer; { индексы массива }

begin

for i :=1 to 5 do {цикл для перебора всех строк}

for j :=1 to 10 do {перебор всех элементов строки по столбцам}

readln ( a [ i , j ]); {ввод с клавиатуры элемента, стоящего в i -й строке и j -м столбце}

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

Вывод двумерного массива Паскаля на экран

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

Пример программы вывода двумерного массива Паскаля

for i :=1 to 5 do {цикл для перебора всех строк}

begin

for j :=1 to 10 do {перебор всех элементов строки по столбцам}

write ( a [ i , j ]:4); {печать элементов, стоящих в i -й строке матрицы в одной экранной строке, при этом для вывода каждого элемента отводится 4 позиции}

writeln ; {прежде, чем сменить номер строки в матрице, нужно перевести курсор на начало новой экранной строки}

end ;

Замечание (это важно!): очень часто в программах студентов встречается ошибка, когда ввод с клавиатуры или вывод на экран массива пытаются осуществить следующим образом: readln (a), writeln (a), где а - это переменная типа массив. При этом их удивляет сообщение компилятора, что переменную этого типа невозможно считать или напечатать. Может быть, вы поймете, почему этого сделать нельзя, если представите N кружек, стоящих в ряд, а у вас в руках, например, чайник с водой. Можете вы по команде «налей воду» наполнить сразу все кружки? Как бы вы ни старались, но в каждую кружку придется наливать отдельно. Заполнение и вывод на экран элементов массива также должно осуществляться последовательно и поэлементно, т.к. в памяти ЭВМ элементы массива располагаются в последовательных ячейках.

Представление двумерного массива Паскаля в памяти

Элементы абстрактного массива в памяти машины физически располагаются последовательно, согласно описанию. При этом каждый элемент занимает в памяти количество байт, соответствующее его размеру. Например, если массив состоит из элементов типа integer , то каждый элемент будет занимать по два байта. А весь массив займет S^2 байта, где S - количество элементов в массиве.

А сколько места займет массив, состоящий из массивов, т.е. матрица? Очевидно: S i^S j , где S i - количество строк, а S j - количество элементов в каждой строке. Например, для массива типа

Matrix = array [1..3, 1..2] of integer ;

потребуется 12 байт памяти.

Как будут располагаться в памяти элементы этого массива? Рассмотрим схему размещения массива M типа matrix в памяти.

Под каждый элемент M [i,j] типа integer выделяется две ячейки памяти. Размещение в памяти осуществляется «снизу вверх». Элементы размещаются в порядке изменения индекса, что соответствует схеме вложенных циклов: сначала размещается первая строка, затем вторая, третья... Внутри строки по порядку идут элементы: первый, второй и т.д.

Как мы знаем, доступ к любой переменной возможен, только если известен адрес ячейки памяти, в которой хранится переменная. Конкретная память выделяется для переменной при загрузке программы, то есть устанавливается взаимное соответствие между переменной и адресом ячейки. Но если мы объявили переменную как массив, то программа «знает» адрес начала массива, то есть первого его элемента. Как же происходит доступ ко всем другим элементам массива?

При реальном доступе к ячейке памяти, в которой хранится элемент двумерного массива, система вычисляет ее адрес по формуле:

Addr + Size Elem * Cols *( I -1)+ Size Elem *( J -1),

где Addr - фактический начальный адрес, по которому массив располагается в памяти; I , J - индексы элемента в двумерном массиве; SizeElem - размер элемента массива (например, два байта для элементов типа integer ); Cols - количество элементов в строке.

Выражение SizeElem * Cols *( I -1)+ SizeElem *( J -1) называют смещением относительно начала массива.

Примеры решения задач с двумерными массивами Паскаля

Задача: Найти произведение ненулевых элементов матрицы.

Решение:

Для решения данной задачи нам потребуются переменные: матрица, состоящая, например, из целочисленных элементов; P - произведение элементов, отличных от 0; I , J - индексы массива; N , M - количество строк и столбцов в матрице. Входными данными являются N , M - их значения введем с клавиатуры; матрица - ввод матрицы оформим в виде процедуры, заполнение матрицы осуществим случайным образом, т.е. с помощью функции random (). Выходными данными будет являться значение переменной P (произведение). Чтобы проверить правильность выполнения программы, необходимо вывести матрицу на экран, для этого оформим процедуру вывода матрицы. Ход решения задачи:

обсудим сначала выполнение основной программы, реализацию процедур обговорим чуть позже:

введем значения N и M ; Введем двумерный массив Паскаля, для этого обращаемся к процедуре vvod ( a ), где а - матрица; Напечатаем полученную матрицу, для этого обращаемся к процедуре print ( a ); Присвоим начальное значение переменной P =1; Будем последовательно перебирать все строки I от 1-й до N -й, в каждой строке будем перебирать все столбцы J от 1-го до M -го, для каждого элемента матрицы будем проверять условие: если a ij ? 0, то произведение P будем домножать на элемент a ij ( P = P * a ij ); Выведем на экран значение произведения ненулевых элементов матрицы - P ;

А теперь поговорим о процедурах.

Замечание (это важно!) Параметром процедуры может быть любая переменная предопределенного типа, это означает, что для передачи в процедуру массива в качестве параметра, тип его должен быть описан заранее. Например :

Type

Matrix=array [1..10, 1..10] of integer;

..............................

procedure primer (a: matrix);

..............................

Вернемся теперь к нашим процедурам.

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

Тогда заголовок нашей процедуры будет выглядеть так:

Procedure vvod ( var m : matrix );

Для реализации вложенных циклов в процедуре нам потребуются локальные переменные-счетчики, например, k и h . Алгоритм заполнения матрицы уже обсуждался, поэтому не будем его повторять.

Процедура вывода матрицы на экран называется print , параметром процедуры является матрица, но в этом случае она является входным параметром, следовательно, передается по значению. Заголовок этой процедуры будет выглядеть следующим образом:

Procedure print ( m : matrix );

И вновь для реализации вложенных циклов внутри процедуры нам потребуются счетчики, пусть они называются так же - k и h . Алгоритм вывода матрицы на экран был описан выше, воспользуемся этим описанием.

Пример программы двумерного массива Паскаля

Program proizvedenie;

Type

Matrix=array [1..10, 1..10] of integer;

Var

A: matrix;

N, m, i, j: byte;

P: integer;

Procedure vvod (var m: matrix);

Var k , h : byte ;

Begin

For i :=1 to n do {переменная n для процедуры является глобальной, а значит «известной»}

For j :=1 to m do {переменная m для процедуры является глобальной, а значит «известной»}

M[i,j]:= random(10);

End;

Procedure print (m: matrix);

Var k, h: byte;

Begin

For i:=1 to n do

begin

For j:=1 to m do

Write (M[i, j]: 4);

Writeln;

end ;

End ;

Begin {начало основной программы}

Writeln (`Введите размерность матрицы:');

Readln(N, M);

Vvod(a);

14

Print(a);

P:=1;

For i:=1 to N do

For j:=1 to M do

If a[i, j]<>0 then p:=p*a[i, j];

Writeln ( p );

End .

Методы доступа к элементам массивов

В языке СИ между указателями и массивами существует тесная связь. Например, когда объявляется массив в виде int array[25], то этим определяется не только выделение памяти для двадцати пяти элементов массива, но и для указателя с именем array, значение которого равно адресу первого по счету (нулевого) элемента массива, т.е. сам массив остается безымянным, а доступ к элементам массива осуществляется через указатель с именем array. С точки зрения синтаксиса языка указатель arrey является константой, значение которой можно использовать в выражениях, но изменить это значение нельзя.

Поскольку имя массива является указателем допустимо, например, такое присваивание:

int array[25];

int *ptr;

ptr=array;

Здесь указатель ptr устанавливается на адрес первого элемента масcива, причем присваивание ptr=arrey можно записать в эквивалентной форме ptr=&arrey[0].

Для доступа к элементам массива существует два различных способа. Первый способ связан с использованием обычных индексных выражений в квадратных скобках, например, array[16]=3 или array[i+2]=7. При таком способе доступа записываются два выражения, причем второе выражение заключается в квадратные скобки. Одно из этих выражений должно быть указателем, а второе - выражением целого типа. Последовательность записи этих выражений может быть любой, но в квадратных скобках записывается выражение следующее вторым. Поэтому записи array[16] и 16[array] будут эквивалентными и обозначают элемент массива с номером шестнадцать. Указатель используемый в индексном выражении не обязательно должен быть константой, указывающей на какой-либо массив, это может быть и переменная. В частности после выполнения присваивания ptr=array доступ к шестнадцатому элементу массива можно получить с помощью указателя ptr в форме ptr[16] или 16[ptr].

Второй способ доступа к элементам массива связан с использованием адресных выражений и операции разадресации в форме *(array+16)=3 или *(array+i+2)=7. При таком способе доступа адресное выражение равное адресу шестнадцатого элемента массива тоже может быть записано разными способами *(array+16) или *(16+array).

При реализации на компьютере первый способ приводится ко второму, т.е. индексное выражение преобразуется к адресному.

15

Для приведенных примеров array[16] и 16[array] преобразуются в *(array+16).

Для доступа к начальному элементу массива (т.е. к элементу с нулевым индексом) можно использовать просто значение указателя array или ptr. Любое из присваиваний

*array = 2;

array[0] = 2;

*(array+0) = 2;

*ptr = 2;

ptr[0] = 2;

*(ptr+0) = 2;

присваивает начальному элементу массива значение 2, но быстрее всего выполнятся присваивания *array=2 и *ptr=2, так как в них не требуется выполнять операции сложения.

Указатели на многомерные массивы

Указатели на многомерные массивы в языке СИ - это массивы массивов, т.е. такие массивы, элементами которых являются массивы. При объявлении таких массивов в памяти компьютера создается несколько различных объектов. Например при выполнении объявления двумерного массива int arr2[4][3] в памяти выделяется участок для хранения значения переменной arr, которая является указателем на массив из четырех указателей. Для этого массива из четырех указателей тоже выделяется память. Каждый из этих четырех указателей содержит адрес массива из трех элементов типа int, и, следовательно, в памяти компьютера выделяется четыре участка для хранения четырех массивов чисел типа int, каждый из которых состоит из трех элементов. Такое выделение памяти показано на схеме на arr

Распределение памяти для двумерного массива.

arr[0] а	arr[0][0]	arr[0][1]	arr[0][2]
arr[1] а	arr[1][0]	arr[1][1]	arr[1][2]
arr[2] а	arr[2][0]	arr[2][2]	arr[2][1]
arr[3] а	arr[3][0]	arr[3][1]	arr[3][2]

Таким образом, объявление arr2[4][3] порождает в программе три разных объекта: указатель с идентификатором arr, безымянный массив из четырех указателей и безымянный массив из двенадцати чисел типа int. Для доступа к безымянным массивам используются адресные выражения с указателем arr. Доступ к элементам массива указателей осуществляется с указанием одного индексного выражения в форме arr2[2] или *(arr2+2). Для доступа к элементам двумерного массива чисел типа int должны быть использованы два индексных выражения в форме arr2[1][2] или эквивалентных ей *(*(arr2+1)+2) и (*(arr2+1))[2]. Следует учитывать, что с точки зрения синтаксиса языка СИ указатель arr и указатели arr[0], arr[1], arr[2], arr[3] являются константами и их значения нельзя изменять во время выполнения программы.

Размещение трехмерного массива происходит аналогично и объявление float arr3[3][4][5] порождает в программе кроме самого трехмерного массива из шестидесяти чисел типа float массив из четырех указателей на тип float, массив из трех указателей на массив указателей на float, и указатель на массив массивов указателей на float.

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

Например, обращение к элементу arr2[1][2] можно осуществить с помощью указателя ptr2, объявленного в форме int *ptr2=arr2[0] как обращение ptr2[1*4+2] (здесь 1 и 2 это индексы используемого элемента, а 4 это число элементов в строке) или как ptr2[6]. Заметим, что внешне похожее обращение arr2[6] выполнить невозможно так как указателя с индексом 6 не существует.

Для обращения к элементу arr3[2][3][4] из трехмерного массива тоже можнo использовать указатель, описанный как float *ptr3=arr3[0][0] с одним индексным выражением в форме ptr3[3*2+4*3+4] или ptr3[22].

Далее приведена функция, позволяющая найти минимальный элемент в трехмерном массиве. В функцию передается адрес начального элемента и размеры массива, возвращаемое значение - указатель на структуру, содержащую индексы минимального элемента.

struct INDEX { int i,

int j,

int k } min_index ;

struct INDEX * find_min (int *ptr1, int l, int m int n)

{ int min, i, j, k, ind;

min=*ptr1;

min_index.i=min_index.j=min_index.k=0;

for (i=0; i*(ptr1+ind)

{ min=*(ptr1+ind);

min_index.i=i;

min_index.j=j;

min_index.k=k;

}

}

return &min_index;

}

Операции с указателями

Над указателями можно выполнять унарные операции:инкремент и декремент. При выполнении операций ++ и -- значение указателя увеличивается или уменьшается на длину типа, на который ссылается используемый указатель.

Пример:

int *ptr, a[10];

ptr=&a[5];

ptr++; /* равно адресу элемента a[6] */

ptr--; /* равно адресу элемента a[5] */

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

Пример:

int *ptr1, *ptr2, a[10];

int i=2;

ptr1=a+(i+4); /* равно адресу элемента a[6] */

ptr2=ptr1-i; /* равно адресу элемента a[4] */

В операции вычитания могут участвовать два указателя на один и тот же тип. Результат такой операции имеет тип int и равен числу элементов исходного типа между уменьшаемым и вычитаемым, причем если первый адрес младше, то результат имеет отрицательное значение.

Пример:

int *ptr1, *ptr2, a[10];

int i;

ptr1=a+4;

ptr2=a+9;

i=ptr1-ptr2; /* равно 5 */

i=ptr2-ptr1; /* равно -5 */

Значения двух указателей на одинаковые типы можно сравнивать в операциях ==, !=, <, <=, >, >= при этом значения указателей рассматриваются просто как целые числа, а результат сравнения равен 0 (ложь) или 1 (истина).

Пример:

int *ptr1, *ptr2, a[10];

ptr1=a+5;

ptr2=a+7;

if (prt1>ptr2) a[3]=4;

В данном примере значение ptr1 меньше значения ptr2 и поэтому оператор a[3]=4 не будет выполнен.

Массивы указателей

В языке СИ элементы массивов могут иметь любой тип, и, в частности, могут быть указателями на любой тип. Рассмотрим несколько примеров с использованием указателей.

Следующие объявления переменных

int a[]={10,11,12,13,14,};

int *p[]={a, a+1, a+2, a+2, a+3, a+4};

int **pp=p;

порождают программные объекты, представленные на схеме

pp pа . . . . .

в в в в в

18

aа 11 12 13 14 15

Схема размещения переменных при объявлении.

При выполнении операции pp-p получим нулевое значение, так как ссылки pp и p равны и указывают на начальный элемент массива указателей, связанного с указателем p ( на элемент p[0]).

После выполнения операции pp+=2 схема изменится и примет вид, изображенный

pp pа . . . .

в в в в в

aа 10 11 12 13 14

Схема размещения переменных после выполнения операции pp+=2.

Результатом выполнения вычитания pp-p будет 2, так как значение pp есть адрес третьего элемента массива p. Ссылка *pp-a тоже дает значение 2, так как обращение *pp есть адрес третьего элемента массива a, а обращение a есть адрес начального элемента массива a. При обращении с помощью ссылки **pp получим 12 - это значение третьего элемента массива a. Ссылка *pp++ даст значение четвертого элемента массива p т.е. адрес четвертого элемента массива.

Если считать, что pp=p, то обращение *++pp это значение первого элемента массива a (т.е. значение 11), операция ++*pp изменит содержимое указателя p[0], таким образом, что он станет равным значению адреса элемента a[1].

Сложные обращения раскрываются изнутри. Например обращение *(++(*pp)) можно разбить на следующие действия: *pp дает значение начального элемента массива p[0], далее это значение инкременируется ++(*p) в результате чего указатель p[0] станет равен значению адреса элемента a[1], и последнее действие это выборка значения по полученному адресу, т.е. значение 11.

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

int a[3][3]={ { 11,12,13 },

{ 21,22,23 },

{ 31,32,33 } };

int *pa[3]={ a,a[1],a[2] };

int *p=a[0];

Схема размещения указателей на двумерный массив.

Согласно этой схеме доступ к элементу a[0][0] получить по указателям a, p, pa при помощи следующих ссылок: a[0][0], *a, **a[0], *p, **pa, *p[0].

Рассмотрим теперь пример с использованием строк символов. Объявления переменных можно изобразить схемой представленной:

char *c[]={ "abs", "d", "yes", "no" };

char **cp[]={ c+3, c+2 , c+1 , c };

char ***cpp=cp;

Схема размещения указателей на строки.

Динамическое размещение массивов

При динамическом распределении памяти для массивов следует описать соответствующий указатель и присваивать ему значение при помощи функции calloc. Одномерный массив a[10] из элементов типа float можно создать следующим образом

float *a;

a=(float*)(calloc(10,sizeof(float));

Для создания двумерного массива вначале нужно распределить память для массива указателей на одномерные массивы, а затем распределять память для одномерных массивов. Пусть, например, требуется создать массив a[n][m], это можно сделать при помощи следующего фрагмента программы:

#include

main ()

{ double **a;

int n,m,i;

scanf("%d %d",&n,&m);

a=(double **)calloc(m,sizeof(double *));

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

a[i]=(double *)calloc(n,sizeof(double));

. . . . . . . . . . . .

}

Аналогичным образом можно распределить память и для трехмерного массива размером n,m,l. Следует только помнить, что ненужную для дальнейшего выполнения программы память следует освобождать при помощи функции free.

#include

main ()

{ long ***a;

int n,m,l,i,j;

scanf("%d %d %d",&n,&m,&l);

/* -------- распределение памяти -------- */

a=(long ***)calloc(m,sizeof(long **));

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

{ a[i]=(long **)calloc(n,sizeof(long *));

for (j=0; i<=l; j++)

a[i][j]=(long *)calloc(l,sizeof(long));

}

. . . . . . . . . . . .

/* --------- освобождение памяти ----------*/

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

{ for (j=0; j<=l; j++)

free (a[i][j]);

free (a[i]);

}

free (a);

}

Рассмотрим еще один интересный пример, в котором память для массивов распределяется в вызываемой функции, а используется в вызывающей. В таком случае в вызываемую функцию требуется передавать указатели, которым будут присвоены адреса выделяемой для массивов памяти.

Пример:

#include

main()

{ int vvod(double ***, long **);

double **a; /* указатель для массива a[n][m] */

long *b; /* указатель для массива b[n] */

vvod (&a,&b);

.. /* в функцию vvod передаются адреса указателей, */

.. /* а не их значения */

..

}

int vvod(double ***a, long **b)

{ int n,m,i,j;

scanf (" %d %d ",&n,&m);

*a=(double **)calloc(n,sizeof(double *));

*b=(long *)calloc(n,sizeof(long));

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

*a[i]=(double *)calloc(m,sizeof(double));

.....

}

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

Пример:

#include

int main()

{ float *q, **b;

int i, j, k, n, m;

scanf("%d %d",&n,&m);

q=(float *)calloc(m,sizeof(float));

/* сейчас указатель q показывает на начало массива */

q[0]=22.3;

q-=5;

/* теперь начальный элемент массива имеет индекс 5, */

/* а конечный элемент индекс n-5 */

q[5]=1.5;

/* сдвиг индекса не приводит к перераспределению */

/* массива в памяти и изменится начальный элемент */

q[6]=2.5; /* - это второй элемент */

q[7]=3.5; /* - это третий элемент */

q+=5;

/* теперь начальный элемент вновь имеет индекс 0, */

/* а значения элементов q[0], q[1], q[2] равны */

/* соответственно 1.5, 2.5, 3.5 */

q+=2;

/* теперь начальный элемент имеет индекс -2, */

/* следующий -1, затем 0 и т.д. по порядку */

q[-2]=8.2;

q[-1]=4.5;

q-=2;

/* возвращаем начальную индексацию, три первых */

/* элемента массива q[0], q[1], q[2], имеют */

/* значения 8.2, 4.5, 3.5 */

q--;