Программирование алгоритмов сортировки массивов

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Российской Федерации

Государственное образовательное учреждение

Высшего профессионального образования

Санкт-Петербургский государственный университет

Аэрокосмического приборостроения

 

 

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ №№1-8

ПРОГРАММИРОВАНИЕ НА ЯЗЫКАХ ВЫСОКОГО УРОВНЯ

 

 

Санкт-Петербург

  Рецензент: В.П.Попов  

ОБЩИЕ ТРЕБОВАНИЯ К СОДЕРЖАНИЮ ОТЧЕТОВ

В методические указания включены задания на 8 лабораторных работ, содержанием которых является разработка программы на языке С. Процесс разработки… 1.Постановка задачи 2.Описание входных и выходных данных

ПРИМЕР ОТЧЕТА О ВЫПОЛНЕНИИ ЛАБОРАТОРНОЙ РАБОТЫ

 

Лабораторная работа

Программирование алгоритмов сортировки массивов

Постановка задачи

 

Написать программу сортировки массива, содержащего не более 100 целых чисел.

 

Описание входных и выходных данных

 

Исходные данные:

int *a – указатель на массив, подлежащий сортировке;

char n - количество реально введенных элементов массива a.

Выходные данные

int *a – указатель на массив, отсортированный по возрастанию значений его первых n элементов.

Оператор прототипа функции сортировки

void sort(int *a, char n)

 

 

Набор тестов

 

Исходные данные:

*a={10,30,20,50,30}

n=5

Выходные данные

*a={10,20,30,30,50}

 

Описание алгоритма

 

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

 

Текст программы

void sort(int *a, char n) //функция сортировки n первых элементов (n<=100) массива a {

Анализ результатов и выводы

 

Объем разработанной программы сортировки вместе с технологической частью, выполняющей ввод исходных данных и вывод результатов, составляет 11260 байт. Массив упорядочивается в отведенной для него памяти с привлечением в качестве дополнительной памяти, необходимой для размещения одного элемента типа int. Время работы программы в количестве операций обмена двух элементов значениями в худшем случае (если исходный массив упорядочен по убыванию) составляет (n*n-n)/2 операций, в лучшем случае - 0 операций, а в количестве операций сравнения двух соседних элементов массива в худшем случае - (n*n+n)/2-1 операций; в лучшем - n-1 операций. В качестве недостатка программной реализации можно отметить отсутствие контроля корректности значения параметра n.

 

ЛАБОРАТОРНЫЕ РАБОТЫ

 

ЛАБОРАТОРНАЯ РАБОТА N 1

  1. Основные типы данных Язык С поддерживает несколько базовых типов данных, которые также называют простыми. Перечислим некоторые из них.

ЛАБОРАТОРНАЯ РАБОТА N 2

  1.Некоторые библиотечные функции для работы с файлами  

ЛАБОРАТОРНАЯ РАБОТА № 3

  1. Введение в постановку задачи 1.1. Позиционные системы счисления

ЛАБОРАТОРНАЯ РАБОТА № 4

  1. Генератор псевдослучайных чисел  

ЛАБОРАТОРНАЯ РАБОТА № 5

  1. Многословные операнды  

ЛАБОРАТОРНАЯ РАБОТА N 6

  1 Понятие табличной структуры данных  

ЛАБОРАТОРНАЯ РАБОТА N 7

  1.Принципы реализации динамических структур данных  

ЛАБОРАТОРНАЯ РАБОТА N 8

  1.Перегрузка и шаблоны функций  

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Вирт Н. Алгоритмы и структуры данных. - М.: Мир,1989. - 360с. 2. Карпов Б., Баранова Т. С++: Специальный справочник. – СПб.: Питер, 2001. –… 3. Кнут Д. Искусство программирования для ЭВМ. Т1. Основные алгоритмы. - М.: Мир, 1976. - 736с.

СОДЕРЖАНИЕ

1 ОБЩИЕ ТРЕБОВАНИЯ К СОДЕРЖАНИЮ ОТЧЕТОВ.. 3

2 ПРИМЕР ОТЧЕТА О ВЫПОЛНЕНИИ ЛАБОРАТОРНОЙ РАБОТЫ... 4

3 ЛАБОРАТОРНЫЕ РАБОТЫ... 6

3.1 ЛАБОРАТОРНАЯ РАБОТА N 1. 6

3.2 ЛАБОРАТОРНАЯ РАБОТА N 2. 7

3.3 ЛАБОРАТОРНАЯ РАБОТА № 3. 9

3.4 ЛАБОРАТОРНАЯ РАБОТА № 4. 11

3.5 ЛАБОРАТОРНАЯ РАБОТА № 5. 13

3.6 ЛАБОРАТОРНАЯ РАБОТА N 6. 14

3.7 ЛАБОРАТОРНАЯ РАБОТА N 7. 16

3.8 ЛАБОРАТОРНАЯ РАБОТА N 8. 18

БИБЛИОГРАФИЧЕСКИЙ СПИСОК.. 20