Графическая и программная реализация алгоритмов обработки сложных структур данных

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ

РЕСПУБЛИКИ КАЗАХСТАН

НАО «АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ»

 

Факультет «информационные  технологии»            Кафедра «информационные системы»

 

 

 

ОТЧЁТ

по расчётно – графической работе № 2

по дисциплине «Алгоритмы, структуры данных и

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

Тема: «Графическая и программная реализация алгоритмов обработки сложных структур данных».

Вариант № 19

 

 

Выполнил ст. гр. БИС-12-2

      Нечаев  Н.И.

            Проверил к.т.н., доцент

            _______________ Ни А.Г.

                     “_____” ___________2013

 

 

Алматы 2013

Содержание

 

 

Введение………...……………………………………………………..………......3

1. Теоретическая часть………………………………………..…………..…………4
2. Задание А…………………………………………………………………………..8
1. Содержательная постановка задачи……………………………………………...8
2. Проектная часть……………………………………………….……………..…....8
1. Словестное описание алгоритма…………...………………………………..…...8
2. Блок – схема……….....…………………………………………………………....9
3. Описание и схема пользовательского интерфейса………………………….....10
3. Прикладная часть……………………………………………………………......11
1. Программное описание алгоритма……………..............………………………11
2. Результат выполнения программы………………………………………….….15
3. Задание Б…………………………………………………………………………15
1. Содержательная постановка задачи……………...……………………………..15
2. Проектная часть………………………………………………...………………..16
1. Словестное описание алгоритма…………...……………………..………..…...16
2. Блок – схема ……………………..……….....……………………………...........17
3. Описание и схема пользовательского интерфейса……...…………………..…18
3. Прикладная часть………….………………..…………………………..…….…19
1. Программное описание алгоритма……………...……………………….……..19
2. Результат выполнения программы………..…....….…………………….……..23

Заключение………………………………………………………….………...….24

Список  использованной литературы………..……………………..………..…26

 

Приложение А………………....………………….………………………….......25

Приложение Б……………………………………………………………...….…25

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

 

 

Си — стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Bell Labs Кеном Томпсоном и Деннисом Ритчи. Си был создан для использования в операционной системе UNIX. С тех пор он был перенесён на многие другие операционные системы и стал одним из самых используемых языков программирования. Си ценят за его эффективность. Он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ. Несмотря на то, что Си не разрабатывался для новичков, он активно используется для обучения программированию. В дальнейшем синтаксис языка Си стал основой для многих других языков.

Язык программирования СИ – это универсальный язык с  богатым набором операторов и  компактным способом записи выражений. Язык C обеспечивает разнообразие типов  данных. Базовыми типами являются целые, вещественные числа и символы (литеры). Язык разрешает модификацию базовых  типов данных, а также создание пользовательских типов. В языке  используются стандартные типы данных int, char, float, double; применяются массивы, структуры (записи), файлы; имеется возможность конструирования очередей, списков.

В данном отчете будет представлено решение двух типов задач: одномерного массива и матрицы соответственно. Будет представлено подробное описание решения в форме словесного описания, блок-схемы, кода программы, которую реализовали на языке Си. Также будет осуществлена проверка с помощью MS Excel.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретическая часть

 

 

Цель. Закрепить навыки разработки и программирования на языке Си алгоритмов обработки сложных структур данных: одномерных массивов и матриц.  Приобрести навыки программирования с переменными типа указатель.

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

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

 Существует 3 вида алгоритмов:

-линейный

-разветвляющийся

-циклический

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

   Структурированные ( интегрированные, композитные, сложные) – такие структуры данных, составными частями которых есть другие структуры данных

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

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

   Полустатические - это стеки, очереди, деки, дерева

   Динамические - линейные и разветвленные связные списки, графы, дерева.

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

Можно говорить о массивах целых  чисел, массивов символов и.т.д. Мы можем даже определить масссив, элементы которого – массивы (массив массивов), определяя, таким образом, многомерные массивы. Любой массив в программе должен быть описан: после имени массива добавляют квадратные скобки [], внутри которых обычно стоит число, показывающее количество элементов массива. Например, запись int x[10]; определяет x как массив из 10 целых чисел. В случае многомерных массивов показывают столько пар скобок, какова размерность массива, а число внутри скобок показывает размер массива по данному измерению. Например, описание двумерного массива выглядит так: int a[2][5]. Такое описание можно трактовать как матрицу из 2 строк и 5 столбцов. Для обрщения к некоторому элементу массива указывают его имя и индекс, заключенный в квадратные скобки (для многомерного массива - несколько индексов , заключенные в отдельные квадратные скобки): a[1][3], x[i] a[0][k+2]. Индексы массива в Си всегда начинаются с 0, а не с 1, т.е. описание int x[5]; порождает элементы x[0], x[1], x[2], x[3], x[4], x[5].

В общем случае объявление массива  имеет следующий синтаксис:

тип_данных имя_переменной[<количество_элементов>] = <список, элементов, массива>

int arr[100];

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

char ch[]  = {'R','u','b','y','D','e','v','.','r','u'};

Динамическим называется массив, размер которого может меняться во время исполнения программы.

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

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

Указатель является одной  из наиболее важных концепций языка C.

·     указатели являются средством, при помощи которого функции могут изменять значения передаваемых в нее аргументов;

·     при помощи указателей выполняется динамическое распределение памяти;

·     указатели позволяют повысить эффективность программирования;

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

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

Общая форма объявления указателя:

тип *имя;

 Например:

int *p1;

char *ch2;

float  *fl1;

Понятие указателя тесно  связано с понятием адреса объекта. В C есть специальная операция, позволяющая получить адрес любой переменной:

&p – получение адреса, где p – идентификатор переменной. Результатом операции является адрес переменной p.

 

Над указателями определено 5 основных операций.

1.     Определение адреса указателя: &p, где p – указатель (&p – адрес ячейки, в которой находится указатель).

2.    Присваивание. Указателю можно присвоить адрес переменной p=&q, где p – указатель, q – идентификатор переменной.

3.    Определение значения, на которое ссылается указатель: *p (операция косвенной адресации).

4.    Увеличение (уменьшение) указателя. Увеличение выполняется как с помощью операции сложения (+), так и с помощью операции инкремента (++). Уменьшение – с помощью операции вычитания (–) либо декремента (––).

Например, пусть p1 – указатель, тогда р1++ перемещает указатель на:

a)   1 байт, если *p1 имеет тип char;

b)   4 байта, если *p1 имеет тип int (в 32 разрядной операционной системе) или 2 байта (в 16 разрядной операционной системе);

c)   4 байта, если *p1 имеет тип float.

5.       Разность двух указателей. Пусть р1 и р2 – указатели одного и того же типа. Можно определить разность р1 и р2, чтобы найти, на каком расстоянии друг от друга находятся элементы массива.

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

 

Наименование	Обозначение	Функция
Блок начало-конец  (пуск-остановка)		Элемент отображает вход из внешней среды или выход из неё (наиболее частое применение −  начало и конец программы). Внутри фигуры записывается соответствующее  действие.
Блок действия		Выполнение одной или  нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно  сами операции.
Логический блок (блок условия)		Отображает решение или  функцию переключательного типа с одним входом и двумя или  более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента.
Предопределённый  процесс		Символ отображает выполнение процесса, состоящего из одной или  нескольких операций, который определен  в другом месте программы.
Данные  (ввод-вывод)		Преобразование данных в  форму, пригодную для обработки (ввод) или отображения результатов  обработки (вывод).
Граница цикла		Символ состоит из двух частей − соответственно, начало и  конец цикла − операции, выполняемые  внутри цикла, размещаются между  ними. Условия цикла и приращения записываются внутри символа начала или конца цикла − в зависимости  от типа организации цикла.
Соединитель		Символ отображает вход в  часть схемы и выход из другой части этой схемы. Используется для  обрыва линии и продолжения её в другом месте.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Задание А