Министерствообразования и науки Республики Казахстан
КазахстанскийИнженерно Технологический университет
(колледж)
Кафедра«Вычислительная техника, автоматизация и телекоммуникация»
Курсоваяработа
по дисциплине
программирование
Тема:Массивы. Двумерные массивы
Выполнила: 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/ ANSIX3.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-м месте, при условии, чтоNp. Из оставшихся (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) — это значит предоставить свободных ячеекв памяти ЭВМ для массива с именем А. Если описание массива отсутствует, то пододномерный массив выделяется 10 ячеек памяти. Каждый элемент массива в общемвиде описывается как А(I), где А — имя массива, I -номер или индекс массива(0
Массивв Паскале.:= array of ; Каждый элемент массива в общем виде описывается как А[I], где А- имя массива, I — номер или индекс массива (0
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 + SizeElem * 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;
…
procedureprimer (a: matrix);
…
Вернемся теперь к нашимпроцедурам.
Процедура ввода матрицыназывается vvod, параметром процедуры является матрица, причем она должнабыть, как результат, передана в основную программу, следовательно, параметрдолжен передаваться по ссылке.
Тогда заголовок нашейпроцедуры будет выглядеть так:
Procedurevvod ( 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;
Procedurevvod (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;
Procedureprint (m: matrix);
Var k, h:byte;
Begin
For i:=1to n do
begin
For j:=1to m do
Write(M[i, j]: 4);
Writeln;
end;
End;
Begin {начало основнойпрограммы}
Writeln (‘Введитеразмерность матрицы:’);
Readln(N, M);
Vvod(a);
14
Print(a);
P:=1;
For i:=1to N do
For j:=1to 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 ;
structINDEX * 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 не будет выполнен.
Массивы указателей
В языке СИ элементымассивов могут иметь любой тип, и, в частности, могут быть указателями на любойтип. Рассмотрим несколько примеров с использованием указателей.
Следующие объявленияпеременных
inta[]={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 1415
Схема размещенияпеременных при объявлении.
При выполнении операции 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
a[i]=(double*)calloc(n,sizeof(double));
… .
}
Аналогичным образом можнораспределить память и для трехмерного массива размером n,m,l. Следует толькопомнить, что ненужную для дальнейшего выполнения программы память следуетосвобождать при помощи функции free.
#include
main ()
{ long***a;
intn,m,l,i,j;
scanf("%d%d %d",&n,&m,&l);
/*-------- распределение памяти— */
a=(long***)calloc(m,sizeof(long **));
for (i=0;i
{a[i]=(long **)calloc(n,sizeof(long *));
for (j=0;i
a[i][j]=(long*)calloc(l,sizeof(long));
}
….… .
/*--------- освобождение памяти----------*/
for (i=0;i
{ for(j=0; j
free(a[i][j]);
free(a[i]);
}
free (a);
}
Рассмотрим еще одининтересный пример, в котором память для массивов распределяется в вызываемойфункции, а используется в вызывающей. В таком случае в вызываемую функциютребуется передавать указатели, которым будут присвоены адреса выделяемой длямассивов памяти.
Пример:
#include
main()
{ intvvod(double ***, long **);
double **a; /* указатель для массива a[n][m] */
long *b; /* указательдля массива b[n] */
vvod (&a,&b);
… /* в функциюvvod передаются адреса указателей, */
… /* а не их значения */
..
}
intvvod(double ***a, long **b)
{ intn,m,i,j;
scanf(" %d %d ",&n,&m);
*a=(double**)calloc(n,sizeof(double *));
*b=(long*)calloc(n,sizeof(long));
for (i=0;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--;
/* вновь измениминдексацию. */
/* Дляосвобождения области памяти в которой размещен */
/* массив qиспользуется функцияfree(q), но поскольку */
/* значениеуказателя q смещено, то выполнение */
/* функцииfree(q) приведет к непредсказуемым последствиям.*/
/* Для правильного выполнения этойфункции */
/* указатель q должен бытьвозвращен в первоначальное */
/* положение */
free(++q);
/* Рассмотрим возможность измененияиндексации и */
/* освобождения памяти для двумерногомассива */
b=(float**)calloc(m,sizeof(float *));
for (i=0;i
b[i]=(float*)calloc(n,sizeof(float));
/* После распределения памяти начальным элементом */
/* массива будетэлемент b[0][0] */
/* Выполним сдвиг индексов так, чтобыначальным */
/* элементом стал элементb[1][1] */
for (i=0;i
b--;
/* Теперьприсвоим каждому элементу массива сумму его */
/* индексов */
for (i=1;i
for (j=1;j
b[i][j]=(float)(i+j);
/* Обратите внимание на начальные значения счетчиков */
/* циклов i и j, он начинаются с 1а не с 0 */
/* Возвратимся к прежней индексации */
for (i=1; i
b++;
/* Выполним освобождение памяти */
for (i=0;i
free(b);
...
...
return 0;
}
В качестве последнегопримера рассмотрим динамическое распределение памяти для массива указателей нафункции, имеющие один входной параметр типа double и возвращающие значение типаdouble.
Пример:
#include
#include
doublecos(double);
doublesin(double);
doubletan(double);
int main()
{ double(*(*masfun))(double);
doublex=0.5, y;
int i;
masfun=(double(*(*))(double))
calloc(3,sizeof(double(*(*))(double)));
masfun[0]=cos;
masfun[1]=sin;
masfun[2]=tan;
for (i=0;i
{y=masfun[i](x);
printf("\nx=%g y=%g",x,y);
}
return 0;
}
Элементом массива может быть в свою очередь тожемассив. Таким образом, мы приходим к понятию двумерного массива или матрицы.Описание двумерного массива строится из описания одномерного путем добавлениявторой размерности, например:
int a[4][3];
Анализ подобного описаниянеобходимо проводить в направлении выполнения операций [], то есть слеванаправо. Таким образом, переменная a является массивом из четырех элементов,что следует из первой части описания a[4]. Каждый элемент a[i] этого массива всвою очередь является массивом из трех элементов типа int, что следует извторой части описания.
Для наглядности двумерныймассив можно представить в виде таблицы с числом строк, равным первому размерумассива, и числом столбцов, равным второму размеру массива, например:
Массива
Столбец 0
Столбец 1
Столбец 2
Строка 0
18
21
5
Строка 1
6
7
11
Строка 2
30
52
34
Строка 3
24
4
67
Имя двумерного массивабез квадратных скобок за ним имеет значение адреса первого элемента этогомассива, то есть значение адреса первой строки — одномерного массива из трехэлементов. При использовании в выражениях тип имени двумерного массивапреобразуется к типу адреса строки этого массива. В нашем примере тип именимассива a в выражениях будет приведен к типу адреса массива из трех элементовтипа int и может использоваться во всех выражениях, где допускаетсяиспользование соответствующего адреса.
Имя двумерного массива содним индексным выражением в квадратных скобках за ним обозначает соответствующуюстроку двумерного массива и имеет значение адреса первого элемента этой строки.Например, в нашем случае a[2] является адресом величины типа int, а именноячейки, в которой находится число 30, и может использоваться везде, гдедопускается использование адреса величины типа int.
Имя двумерного массива сдвумя индексными выражениями в квадратных скобках за ним обозначаетсоответствующий элемент двумерного массива и имеет тот же тип. Например, внашем примере a[2][1] является величиной типа int, а именно ячейкой, в которойнаходится число 52, и может использоваться везде, где допускается использованиевеличины типа int.
В соответствии синтерпретацией описания двумерного массива (слева-направо) элементы последнегорасполагаются в памяти ЭВМ по строкам.
Инициализация двумерногомассива также проводится по строкам, например, для того чтобы получитьвышеописанный массив a, можно было бы провести следующую инициализацию
int a[][3] = {
{ 18, 21, 5 },
{ 6, 7, 11 },
{ 30, 52, 34 },
{ 24, 4, 67 }
};
Здесь первый размермассива будет определен компилятором. Следует отметить, что второй размермассива должен быть всегда указан. Это необходимо для того, чтобы сообщитькомпилятору размер строки массива, без которого компилятор не может правильноразместить двумерный массив в памяти ЭВМ.
Для инициализациидвумерного массива символов можно использовать упрощенный синтаксисинициализации строк:
char s[][17] = {
«Строка 1»,
«Длинная строка2»,
«Строка 3»
}
Размер памяти заказанныйпод каждую строку в этом случае должен быть равным длине самой длинной строки сучетом нуль-символа. При этом, для части строк (строка 1 и строка 3) будетвыделено излишнее количество памяти. Таким образом, хранение строк различнойдлины в двумерном массиве символов недостаточно эффективно с точки зренияиспользования памяти.
Ввод двумерного массиваосуществляется поэлементно с помощью двух вложенных циклов. Следующий фрагментпрограммы предназначен для ввода по строкам двумерного массива элементов типаdouble размером n строк на m столбцов
for (i=0;i
for (j=0;j
{
printf(«a[%d][%d]= », i, j);
scanf("%lf", &a[i][j]);
}
Для ввода массива постолбцам достаточно поменять местами строки программы, являющиеся заголовкамициклов.
Вывод такого же двумерногомассива иллюстрирует следующий фрагмент:
for (i=0;i
{
for (j=0;j
printf("\n");
}
В данном фрагменте послевывода очередной строки массива осуществляется переход на следующую строкудисплея.
В языке Си допускаетсяиспользовать не только двумерные, но и трехмерные, четырехмерные и т. д.массивы. Их использование ничем принципиально не отличается от использованиядвумерных массивов, однако на практике они применяются значительно реже.
Индексный массив
Индексный массив (внекоторых языках программирования также таблица, ряд) — именованный набороднотипных переменных, расположенных в памяти непосредственно друг за другом (вотличие от списка), доступ к которым осуществляется по индексу.
Индекс массива — целоечисло, либо значение типа, приводимого к целому, указывающее на конкретныйэлемент массива.
В ряде скриптовых языков,например JavaScript, PHP, Ruby применяются также ассоциативные массивы, вкоторых переменные не обязаны быть однотипными,
и доступ к ним необязательно осуществляется по индексу.
Общее описание
Количество используемыхиндексов массива может быть различным. Массивы с одним индексом называютодномерными, с двумя — двумерными и т. д. Одномерный массив нестрогосоответствует вектору в математике, двумерный — матрице. Чаще всего применяютсямассивы с одним или двумя индексами, реже — с тремя, ещё большее количествоиндексов встречается крайне редко.
Пример статическогомассива на Паскале -
word Array: array [Word]of Integer; { Статический, размер= High(Word) + 1 }
multiArray: array [Byte, 1..5] of Char; { Статический массив, 2 измерения }
rang eArray: array [5..20] of String; { Статический массив, размер = 16 }
Пример статического массива на С/С++-
int Array[10]; // Статический,размер 10, базовый тип данных — целое число (int)
double Array[12][15];// Статическиймассив, 2 измерения, базовый тип данных — число// с дробнойчастью(double)
Поддержка индексныхмассивов (свой синтаксис объявления, функции для работы с элементами и т. д.)есть в большинстве высокоуровневых языков программирования. Максимальнодопустимая размерность массива, типы и диапазоны значений индексов, ограниченияна типы элементов определяются языком программирования и/или конкретнымтранслятором.
В языкахпрограммирования, допускающих объявления программистом собственных типов, какправило, существует возможность создания типа «массив». В определении такоготипа может указываться размер, тип элемента, диапазон значений и типы индексов.В дальнейшем возможно определение переменных созданного типа. Все такиепеременные-массивы имеют одну структуру. Некоторые языки поддерживают дляпеременных-массивов операции присваивания (когда одной операцией всем элементаммассива присваиваются значения соответствующих элементов другого массива).
Объявление типа «массив»в Паскале -
type
T ArrayType = array [0..9] of Integer; (* Объявления типа «массив» *)
var
arr1, arr2, arr3:TArrayType; (* Объявлениетрёх переменных-массивов одного типа *)
Специфические типымассивов
Динамическиемассивы
Динамическим называетсямассив, размер которого может меняться во время исполнения программы. Дляизменения размера динамического массива язык программирования, поддерживающийтакие массивы, должен предоставлять встроенную функцию или оператор.Динамические массивы дают возможность более гибкой работы с данными, так какпозволяют не прогнозировать хранимые объёмы данных, а регулировать размермассива в соответствии с реально необходимыми объёмами. Обычные, нединамические массивы называют ещё статическими.
Пример динамическогомассива на Delphi
byte Array: Array ofByte; // Одномерный массив
multi Array: Array ofArray of string; // Многомерныймассив
Пример динамическогомассива на Си
float *array1; // Одномерный массив
int **array2; // Многомерный массив
array1=(float*)malloc(10*sizeof(float));// выделение 10блоков поsizeof(float)байт каждый
array2=(int**)malloc(16*sizeof(int*)); // выделение 16*8блоков поsizeof(int) байт каждый
for(i=0;i
array2[i]=(int*)malloc(8*sizeof(int));
Пример динамическогомассива на С++
float *array1; // Одномерный массив
int **array2; // Многомерный массив
array1=new float[10];// выделение10 блоковразмером типаfloat
array2=new int*[16]; //выделение 16*8 блоковразмером типа int
for(int i=0;i
array2[i]=newint[8];
Гетерогенныемассивы
Гетерогенным называетсямассив, в разные элементы которого могут быть непосредственно записанызначения, относящиеся к различным типам данных. Массив, хранящий указатели назначения различных типов, не является гетерогенным, так как собственнохранящиеся в массиве данные относятся к единственному типу — типу «указатель».Гетерогенные массивы удобны как универсальная структура для хранения наборовданных произвольных типов. Отсутствие их поддержки в языке программированияприводит к необходимости реализации более сложных схем хранения данных. Сдругой стороны, реализация гетерогенности требует усложнения механизмаподдержки массивов в трансляторе языка. Гетерогенный массив как встроенный типданных присутствует в языке PHP.
Массивы массивов
Многомерные массивы, какправило, реализованные как одномерные массивы, каждый элемент которых являетсяссылкой на другой одномерный массив.
Реализация
Стандартным способомреализации статических массивов с одним типом элементов является следующий:
Под массив выделяетсянепрерывный блок памяти объёмом S*m1*m2*m3…mn, где S — размер одного элемента,а m1…mn — размеры диапазонов индексов (то есть количество значений, которыеможет принимать соответствующий индекс).
При обращении к элементумассива A[i1, i2, i3, … in] адрес соответствующего элемента вычисляется какB+S*(i1p*m1+i2p*m2+…+i(n-1)p*mn-1+inp), где B —
27
база (адрес начала блокапамяти массива), ikp-значение k-го индекса, приведённое к целому с нулевымначальным смещением.
Таким образом, адресэлемента с заданным набором индексов вычисляется так, что время доступа ко всемэлементам массива одинаково.
Первый элемент массива, взависимости от языка программирования, может иметь различный индекс. Различаюттри основных разновидности массивов: с отсчетом от нуля (zero-based), сотсчетом от единицы (one-based) и с отсчетом от специфического значениязаданного программистом (n-based). Отсчет индекса элемента массивов с нуляболее характерен для низкоуровневых ЯП, однако этот метод был популяризирован вязыках более высокого уровня языком программирования С.
Более сложные типымассивов — динамические и гетерогенные — реализуются сложнее.
Достоинства
легкость вычисленияадреса элемента по его индексу (поскольку элементы массива располагаются одинза другим)
одинаковое время доступако всем элементам
малый размер элементов:они состоят только из информационного поля
Недостатки
для статического массива— отсутствие динамики, невозможность удаления или добавления элемента безсдвига других
для динамического и/илигетерогенного массива — более низкое (по сравнению с обычным статическим)быстродействие и дополнительные накладные расходы на поддержку динамическихсвойств и/или гетерогенности.
при работе с массивом встиле C (с указателями) и при отсутствии дополнительных средств контроля —угроза выхода за границы массива и повреждения данных
Заключение
На данный момент мироваякомпьютерная индустрия развивается очень стремительно.Производительностьсистем возрастает, а следовательно возрастают возможности обработки большихобъёмов данных. Операционные системы класса MS-DOS уже не справляются с такимпотоком данных и не могут целиком использовать ресурсы современных компьютеров.Поэтому она больше нигде широко не используется. Все стараются перейти наболее совершенные ОС, какими являются UNIX и Windows. Но из-за “непопулярности “, UNIX мало кто использует этот ОС. Во всем мире все, начиная от домохозяек и заканчиваякорпоративными пользователями, пользуются Windows 9x.
В данной Курсовой работемы рассмотрели основное понятие программирования.
Не смотря на внешне кажущуюся простоту данной программы, онтаит в себе ряд сложностей, которые реализуются с использованием всех основныхприемов Турбо Паскаль. Вообще Турбо Паскаль как среда программирование ужедавно устарела, но основы, которые лежат в среде программировании в ТурбоПаскаль, лежат в большинстве известных и популярных приложений. На мой взгляд,изучая программирование в Турбо Паскаль, можно освоить основные приемыпрограммирования.
Двумерные массивысеребряных наностержней в диэлектрической пластине обладают нетривиальнымиоптическими свойствами. Вследствие малых по сравнению с длиной волны размерамитакие структуры должны моделироваться с использованием точной электромагнитнойтеории. На ее основе построены модели усреднения материала, в частности,рассматривается НМ усреднения. Результаты аналитического моделированиясравниваются с анализом распространения света через точную структуру численнымпериодическим методом конечных граничных элементов. Сравнение показалоэффективность НМ в ТМ — случае для расчета структур с металлическими стержнями.Сумма отклонений коэффициентов отражения и пропускания возрастает с расстояниеммежду стержнями. В том случае модель может быть использована только длякачественного анализа.
Целью данной курсовой работы, являлось углубление знаний ирасширение навыков по разработке массивам и их реализации на персональномкомпьютере, на мой взгляд, разработанная мной программа, вполне отвечаетпоставленным целям.
Списоклитературы
Основная
1.Львовский М.Б. Методическое пособие«BOOK» по информатике для 9-11 классов.
2.Гусак А.А. Высшая математика. В 2-хт. Т. 2.: Учеб. Пособие для студентов вузов. – Мн.: ТетраСистемс, 1998. – 448 с.
3.Лиходед Н.А.Методы распараллеливания гнезд циклов: Курс лекций. – Мн.: БГУ. 2007. – 100 с.Ser314\ subFaculty\ Каф. Дискр. мат. и алгор\ КУРСЫ ДМА\ 4 курс\ Лиходед\Лекции\ Распараллеливание гнезд циклов.
4.Вирт Н. Алгоритмы+ структуры данных = программы. — М.: Мир, 1985. — С. 406.
5.Светозарова Г.И.,Мельников А.А., Козловский А.В. Практикум по программированию на языке Бейсик:Учебное пособие для вузов. – М.: Наука, 1988.
Дополнительная
1.Источник: Львовский М.Б. Методическоепособие «BOOK» по информатике для 9-11 классов. Адрес: markbook.chat.ru/book/
2.Йенсен К., Вирт Н. Паскаль. Руководстводля пользователя и описание языка. — М.: Финансы и статистика, 1982. — С. 151.
3.Перминов О. Н. Языкпрограммирования Паскаль: Справочник. — М.: Радио и связь, 1989. — С. 128. —ISBN 5-256-00311-9
4.Для подготовкиданной работы были использованы материалы с сайта www.comp-science.ru/
5.Вострикова З.П., Вострикова О.Ю.,Туева С.С. Программирование на языке “Бейсик” для персональных ЭВМ. – М.:Финансы и статистика, 1993.