Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент



Скачать 45.36 Kb.
Дата13.05.2013
Размер45.36 Kb.
ТипПояснительная записка
gif" align=left>Новосибирский государственный технический университет
Пояснительная записка

к расчетно-графическому заданию

по информатике

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


Студент:

Группа: АМ-09

Семестр: 2

Факультет: АВТ

Преподаватель: Романов Евгений Леонидович


Новосибирск

2001

Содержание:

  1. Задание

  2. Описание принципов работы программы, структур данных и алгоритмов.

  3. Графическая интерпретация работы программы (иллюстрации)

  4. Функциональное описание программы: переменные, функции (на уровне интерфейсов), особенности алгоритмов.

  5. Текст программы с комментариями


1. Задание

Сортировка односвязного списка простым однократным слиянием. Список разделяется на n-частей, каждый сортируется независимо. Затем производится слияние в выходной список. Промежуточная структура данных – массив указателей на списки.
2. Алгоритм работы программы

Программа начинается с меню. В меню содержится три опции: ручной ввод списка, программный ввод списка, выход из программы. Каждый элемент списка – структура, содержащая указатель на следующую в списке структуру – list *next, и информационную часть – переменную int val, относительно значения которой и производится сортировка.

Ручной ввод списка реализован в цикле, на каждом шаге которого программа выделяет в динамической памяти с помощью оператора new место под структуру (возвращает указатель на него). Пользователь вводит числовые значения (информационную часть структуры), цифра 0 ограничивает список. При программном вводе списка реализуется тот же механизм, что и при ручном вводе списка. Отличие в том, что пользователь вводит длину списка (количество элементов), а значения val – случайные числа от 0 до 100. В обоих случаях получаем односвязный список с заголовком list *l (указатель на первый элемент списка). Он подается в качестве формального параметра функции BIGSORT(list *q) .

Функция BIGSORT(list *q) – основная функция программы. Основным элементом функции является массив указателей на списки (заголовки) list **ph. **ph реализуется в динамической памяти, объем которой определяется числом элементов первоначального списка, а именно, количеством разбиений первоначального списка. Число элементов определяется при пробегании первоначального списка циклом, после чего исходный список разбивается на n списков. Пользователь сам определяет длину каждого разбиения - s.

В цикле пробегается весь первоначальный список и под ph[i] заголовок кладется указатель на каждый s-ый элемент исходного списка, одновременно ограничивая предыдущий список (под указатель next предыдущей структуры кладется NULL).

После чего разбиения сортируются функцией SORT(list *in). Данная функция сортирует список вставками с сохранением порядка. Результат функции – указатель на отсортированный список, который кладется под ph[i].

В дальнейшем между собой сортируются первые элементы каждого разбиения при помощи функции FIND(list **ph, int n), которая из первых элементов разбиений выбирает наименьший. Указатель на него и есть результат функции. Заголовок списка настраивается на следующий, за найденным элементом, элемент списка. Поиск элементов реализован в цикле: каждый новый элемент настраивается на предыдущий, цикл завершается при отсутствии элементов в разбиениях. Первый элемент полученного списка кладется под указатель *q, который является результатом функции BIGSORT(list *q).
3. Графическая интерпретация работы программы

Первоначальный список:

*q NULL

5 3 1 4 6 2

Разбиение на списки:

ph ph[0] NULL

ph[1] 5 3

ph[2] NULL

1 4

NULL

6 2
Результат сортировки:

*q NULL

1 2 3 4 5 6
4. Текст программы

Похожие:

Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка расчетно-графическая работе по дисциплине "Информатика" Шейкер-сортировка двусвязного циклического списка
Шейкер сортировка двусвязного циклического списка. Используются указатели на границы отсортированных частей списка
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка расчетно-графическая работе по дисциплине "Информатика" " Шейкер-cортировка" Группа: ам-216
...
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconМетодические указания к расчетно-графическому заданию для студентов IV курса фпми направление 510200 "Прикладная математика и информатика"
Методические указания предназначены для студентов, выполняющих расчетно-графическое задание по курсу «Математическая статистика»...
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка по информатике и информационно-комуникационным технологиям на 2011-2012 учебный год Программа по информатике и икт составлена на основе
Мо с зам директора по увр директор маоу сош №98 информатики и математики Н. Е. Мясникова М. А. Утманцева
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка к практическому заданию по дисциплине «Современные проблемы информатики и вычислительной техники»

Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка в основу программы «Детская литература»
В результате изучения дисциплины студент будет иметь представление об историческом развитии детской литературы
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка Посылаем материал на конкурс "Дистанционный урок"
...
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка к заданию по методам оптимизации " Нахождение минимума функции при наличии ограничений численными методами"
...
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка Данная программа является индивидуальной для
«Информатика и икт» с учетом необходимости существования индивидуального подхода к обучению учащихся, имеющих широкий кругозор, достаточно...
Пояснительная записка к расчетно-графическому заданию по информатике Сортировка односвязного списка разделением Студент iconПояснительная записка к учебному плану на 2012-2013 уч год мкоу «Синелипяговская сош» Настоящая пояснительная записка включает
Мкоу «Синелипяговская сош» от Прот. № от
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org