Структуры данных и алгоритмы обработки

Алгоритмы преобразования одномерных массивов

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

Студента 2 курса направления подготовки 00.00.00

Педагогическое образование (Профили «Физика» и «Информатика»)

Горлова Михаила Вячеславовича

Научный руководитель:

Маврин С.А., к.п.н., доцент

Курсовая сдана:

«__»_________ 2017 г.

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

___________________________

Курсовая работа защищена

«__»_________ 2017 г.

Оценка ________________

Подпись членов комиссии:

_______________________

Самара 2017

ВВЕДЕНИЕ
§1. Структуры данных и алгоритмы обработки
§2. Программная реализация алгоритмов преобразования одномерных массивов средствами среды программирования Pascal.ABC.Net
ЗАКЛЮЧЕНИЕ
БИБЛИОГРАФИЯ
ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

Объект исследования – одномерные массивы и способы их преобразования.

Предмет исследования – реализация алгоритмы преобразования одномерных массивов средствами языка программирования Pascal.ABC.

Цель исследования – разработать программы на языке программирования Pascal.ABC, реализующие некоторые алгоритмы преобразования одномерных массивов.

Задачи исследования:

1. Провести анализ учебно-методической и технической литературы по проблеме исследования.

2. Разработать некоторые алгоритмы преобразования одномерных массивов.

3. Реализовать алгоритмы преобразования одномерных массивов средствами языка программирования Pascal.ABC.

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

Структуры данных и алгоритмы обработки

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

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

Существуют несколько видов массивов: одномерный, двумерный и многомерный (рис.1).

Структуры данных и алгоритмы обработки

Рисунок 1. Упрощенная схема представления массивов

Одномерный массив – это массив, элементы которого нумеруются одним индексом (линейный массив). Двумерный массив – это массив, элементы которого нумеруются двумя индексами: строкой и столбцом (табличный массив). Каждый элемент массива пронумерован. Можно обратиться целиком к массиву, а можно обратиться к нужной переменной, указав её индекс.

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

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

type = array [] of

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

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

1. C помощью служебного слова type описывается тип массива, а затем с помощью var вводится переменная этого типа:

type = array [тип индекса] of

var :

2. С помощью слова var сразу описывается переменная типа массив:

var : array [тип индекса] of

Примеры описания массивов:

var

A, BB : array [1..40] of real;

C : array [‘A’..’Z’] of integer;

D : array [-20..20] of word;

E : array [1..40] of real;

Теперь переменные A, BB и E представляют собой массивы из сорока вещественных чисел; массив C имеет индексы символьного типа и целочисленные элементы; массив D может хранить в себе 41 число типа word.

Основное отличие элемента массива от простой переменной состоит в том, что для элемента массива в квадратных скобках может стоять не только соответствующее значение индекса, но и выражение, приводящее к значению индексного типа. То есть реализуется косвенная адресация: BB[15] — прямая адресация;

BB[m] — косвенная адресация через переменную m, значение которой будет использовано в качестве индекса элемента массива BB.

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

Например, таблица символов a ? b, где a – число строк и b – число столбцов, может быть описана:

var tab : array [1..a, 1..b] of char;

Общая форма записи:

var : array [тип индекса строки, тип индекса столбца]

of ;

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

type

line = array [1..b] of char;

stolb = array [1..a] of line;

var tab : stolb.

Здесь tab [i] – переменная типа line, а tab [i][j] – переменная типа char.

Описание двумерного массива:

Способ 1. В разделе описания переменных.

Имя Массива : array [Верх. Гр.1..Ниж. Гр.1, Верх. Гр.2.. Ниж. Гр.2] of тип элементов;

Способ 2. В разделе описания типов.

massive: array [Верх. Гр.1.. Ниж. Гр.1, Верх. Гр.2.. Ниж. Гр.2] of тип элементов;

Способ 3. В разделе описания констант.

const

massive: array [1..3,1..3] of real = ((1.2,2.4,0.4),(0.045,-0.47,0.003),(1.24,1,-7.4));

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

04 — Алгоритмы. Структуры данных. Хеш-таблицы


Похожие статьи.

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