Создание информационного ресурса и реализация алгоритма сортировки данных

Размещено на http://www.allbest.ru/

Введение

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

История развития сети Интернет начинается с 1961 года. По заданию министерства обороны США, был основан проект, по созданию экспериментальной сети передачи пакетов. Эта сеть, названная ARPANET, предназначалась первоначально для изучения методов обеспечения надежной связи между компьютерами различных типов. Постепенно, сеть вышла за границы американской армии и стала использоваться обычными людьми. Так появился Интернет. Интернет сделал возможным свободный обмен информацией, не взирая на расстояния и государственные границы. Позже была разработана Всемирная Информационная Паутина (World Wide Web), которая к настоящему времени оплела своими сетями практически весь компьютерный мир и сделала Интернет доступным и привлекательным для миллионов пользователей.

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

Наиболее востребованной профессией на электронном рынке является создание web-сайтов. Web-сайты являются неотъемлемой частью любой организации, служат их интернет-представительством.

Главными инструментами, по разработки web-сайтов, на сегодняшний день являются языки гипертекстовой разметки HTML и скриптовый язык программирования PHP. Именно они использовались в данном курсовом проекте.

Целью курсового проекта является создание информационного ресурса и реализация алгоритма сортировки данных. В данном курсовом проекте используется сортировка слиянием.

Сортировка слиянием (англ. merge sort) - алгоритм сортировки, который упорядочивает списки (или другие структуры данных, доступ к элементам которых можно получать только последовательно, например - потоки) в определённом порядке.

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

1. Общий раздел

1.1 Характеристики программного и аппаратного обеспечения

Для разработки информационного ресурса «Сортировка слиянием» будет использована система со следующими аппаратными характеристиками:

- объем оперативной памяти системы, равный 4ГБ;

- процессор Intel Core 2 Duo CPU T6670 с тактовой частотой 2.20 Гигагерца;

- объем постоянной памяти, равный 320ГБ;

- разрядность шины системы 64 бит;

- видеокарта NVIDIA GeForce GT 320M c поддержкой Microsoft DirectX 10;

- принтер Canon LBP 2900.

Разработка информационного ресурса осуществляется на следующем программном обеспечении:

- операционная система Windows 7 Ultimate SP 1;

- среда для разработки и корректировки изображений графической части системы Adobe Photoshop CS 5;

- набор web-разработчика Denwer 3 со встроенным интерпретатором php версии 6.0, утилитой PHPMyAdmin для работы с базами данных MySQL и автоматический механизм развертывания web-сервера Apache 2.0;

- кроссплатформенный текстовый редактор Scite 3.0.2.94Ru для набора html и php кода.

Adobe Photoshop CS 5 - мощнейший редактор растровой графики для создания безупречных качественных изображений на профессиональном уровне, включающий мощнейшие инструменты обработки и редактирования изображений и интуитивный интерфейс. Программный продукт позволяет создавать многослойные изображения, что обеспечивает превосходный монтаж фотографий. Значительная часть инструментария программы позволяет создавать интегрированные для использования в web-приложениях изображения, что существенно облегчает разработку графического контента для Интернет-ресурсов, позволяя оптимизировать изображения для работы в сети Интернет и создания меньших объемов трафика. Данное программное обеспечение использовалось для разработки макета информационного ресурса.

Denwer 3 - набор дистрибутивов (Apache, PHP, MySQL, Perl и т. д.) и программная оболочка, используемые Web-разработчиками для разработки сайтов на локальной Windows - машине без необходимости выхода в Интернет. Главная особенность Денвера - удобство при удаленной работе сразу над несколькими независимыми проектами и возможность размещения на Flash - накопителе. Набор предполагает централизованную установку и конфигурирование серверных программ, необходимых для реализации запуска web-сервера и тестирования новых созданных страниц и web-приложений. В данном курсовом проекте использовались следующие составляющие набора Denwer: HTTP web-сервер Apache 2.0, интерпретатор PHP 5. Denwer использовался для тестирования информационного ресурса и интерпретирования php-кода.

Scite - кроссплатформенный текстовый редактор. Предназначен в основном для редактирования исходных текстов программ и выполняет подсветку синтаксиса для многих языков программирования (C, C++, C#, Java, Ruby, Pascal, Perl, Python, PHP)разметки (HTML, XML и т. п.), описания аппаратуры (VHDL, Verilog, System Verilog). SciTE характеризуется как компактный текстовый редактор для программистов с удобно реализованным сворачиванием кода, развитой подсветкой синтаксиса и другими полезными функциями. SciTe является переносимым приложением и работает при запуске с переносных устройств. Размер дистрибутива SciTE не превышает 1 Мб. В данном курсовом проекте текстовый редактор Scite использовался для написания HTML, CSS и PHP кода.

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

- Microsoft Office Word 2003;

- Microsoft Office Visio 2003;

- Opera 12;

Microsoft Office Word 2003 - текстовый процессор, предназначенный для работы с документами. Достаточно широкий спектр предоставляемых возможностей по разработке и оформлению документов любой сложности с возможностью дизайна текстового и графического контента. Данное программное обеспечение использовалось для разработки пояснительной записки с внедрением графических элементов.

Microsoft Office Visio 2003 - редактор создания бизнес-изображений и схем. Благодаря обширной библиотеке объектов с помощью редактора возможно создавать любые графические схемы, с использованием стандартных условных обозначений. Графические схемы могут быть созданы любой сложности, начиная от обычной схемы, и заканчивая достаточно сложными схемами бизнес-процессов. Данное программное обеспечение использовалось для составления схем логической и физической структур, а так же для составления схемы программы.

Opera 12 - браузер, предназначенный для просмотра web-страниц. Использовался для тестирования и отладки работы информационного ресурса.

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

Задачей курсового проекта является создание информационного ресурса для реализации алгоритма сортировки слиянием.

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

Суть задачи следующая: упорядочить по неубыванию массив A(n), разбивая его на группы по 1, 2, 4, 8,… элементов и проводя попарно слияние соседних групп (число n не обязательно равно степени 2). Разрешается выделить дополнительный рабочий массив B(n) и проводить слияние поочередно из A в B, затем из B в A и так далее.

Реализация сортировки слиянием осуществляется следующим образом: сначала делим список на кусочки (по 1 элементу), затем сравниваем каждый элемент с соседним, сортируем и объединяем. В итоге, все элементы отсортированы и объединены вместе.

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

Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы.

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

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

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

2. Специальный раздел

2.1 Проектирование логической структуры ресурса

Логическая структура проекта - одна из самых основных составляющих разработки web-ресурсов. Именно от логической структуры зависит структура навигации для более удобной работы с ресурсом. Если выполнить размещение всех файлов ресурса на физическом уровне в одном каталоге, то логически соответствующие файлам на физическом уровне разделы следует разделять по подгруппам, для обеспечения удобной навигации.

Логически страницы ресурса можно разделить на две основные группы:

- страницы справочной информации;

- страницы реализации сортировки массива;

Группу страниц справочной информации можно представить следующим набором файлов:

- index.html - данный файл является главной страницей сайта и предоставляет краткую информацию о сайте;

- theory.html - данная страница содержит теоретический материал по теме курсового проекта;

Группу страниц для реализации сортировки массива:

- execution.html - данная страница содержит форму для ввода одномерного массива

- task.php - скрипт, сортирующий массив методом слияния;

Данный набор файлов можно организовать в общую логическую структуру ресурса. В логической структуре отражена зависимость и взаимосвязь страниц ресурса.

Логическая структура информационного ресурса представлена на рисунке 1.



Рисунок 1 - Проектирование логической структуры ресурса

2.2 Проектирование физической структуры ресурса

Физическую структуру ресурса можно разделить на несколько частей:

- физическая структура web-сервера, данная структура хранит механизмы запуска сервера;

- физическая структура контента, данная структура позволяет хранить непосредственно файлы ресурса для отображения их в браузере при обращении к серверу;

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

Структура web-сервера создается автоматически при установке элементов серверного программного обеспечения. Для исполнителя работ по разработке ресурса необходимо выполнить только физическую организацию физической структуры контента.

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

Условно графически физическую структуру ресурса можно показать как обозначено на рисунке 2.



Рисунок 2 - Проектирование физической структуры ресурса

2.3 Реализация интерфейса

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

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

В качестве основы макета страниц выбрана блочная реализация. Блочная структура интерфейса выбрана как наиболее компактная и надёжная структура, которая соответствует всем стандартам HTML.

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

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

Графическая составляющая ресурса разработана с применением макета, созданного в графическом редакторе Adobe Photoshop CS 6.

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

Для всего содержимого ресурса установлена кодировка «Кириллица Windows». Важно применить данную кодировку на всех страницах ресурса, чтобы избежать проблем с отображением данных при дальнейшей разработке страниц.

Оформляем заголовочный блок. Блок занимает всю ширину страницы. В качестве фона заданно графическое изображение, предварительно подготовленное в графическом редакторе Adobe Photoshop. Заголовочный блок содержит в себе надпись, выполненную жирным шрифтом, семейства Arial Black, а также навигационное меню, выполненное в виде горизонтального списка и предоставляющее навигацию по всему сайту.

Область контента делится на два контейнера. Левый блок-контейнер содержит основную информацию, форму для ввода исходных данных, а так же результат работы программы. Правый блок содержит изображения и ссылки.

Последний блок занимает всю ширину страницы. В данном блоке содержится краткая о ресурсе и разработчике.

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

2.4 Разработка приложения для решения описанного метода

Разработка данного приложения осуществлялась с помощью языка гипертекстовой разметки HTML и скриптового языка программирования PHP.

Ввод массива чисел осуществляется с помощью формы. Посредством метода «post» массив передается в скрипт, который сортирует его, и выводит конечный результат на экран.

Сама программа состоит из четырех основных функций:

- функция slice_array;

- функция merge_array;

- функция merge;

- функция MergeSort;

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

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

Функция merge производит слияние двух упорядоченных подмассивов. В качестве параметров в функцию передаются три массива. Для каждого массива создается свой счетчик, а так же вычисляется размер этих массивов. Затем создается цикл с предусловием, который работает, пока счетчик массива меньше его размера. В цикле есть условный оператор if, с помощью которого сравниваются элементы двух массивов, и, если текущий элемент первого массива меньше или равен текущему элементу второго, то этот элемент записывается в результирующий массив, и счетчик этого массива увеличивается на один. В противном случае, в результирующий массив записывается элемент второго массива, и увеличивается на один его счетчик. После цикла проверяется, перебрали ли мы весь первый массив, если да, то во втором массиве остался последний элемент, который мы извлекаем из массива с помощью описанной выше функции slice_array, и помещаем во вспомогательную переменную; если нет, последний элемент извлекается из первого массива. Функция merge возвращает результирующий массив, к которому с помощью функции merge_array присоединяется вспомогательная переменная.

Функция MergeSort является основной функцией программы. Она выполняет сортировку массива. В качестве параметра в функцию передается введенный пользователем массив. После этого массив разбивается на два массива размерности размер массива/2, для каждого из которых рекурсивно вызывается метод сортировки слиянием. Полученные отсортированные массивы сливаются в единый массив с сохранением упорядоченности. В результате получается отсортированный по возрастанию массив. Функция MergeSort использует описанные выше функции slice_array и merge.

После ввода пользователем строки, из нее удаляются лишние пробелы слева и справа, с помощью функции trim. Создается переменная flag, которая принимает значение true. Далее строка перебирается с помощью цикла, проверяя каждый символ, является ли он числом, с помощью функции is_numeric. Если находится символ, не являющийся числом, то выводится сообщение об ошибке и переменная flag принимает значение false. Далее проверяется условие, если флаг равен true, то строка переписывается в массив. Запись производится с помощью функции explode, которая разделяет строку по пробелам. После этого к массиву применяется функция MergeSort, и с помощью счетного цикла массив поэлементно выводится на экран оператором echo.

2.5 Тестирование и отладка

Тестирование программы - это испытание, проверка правильности работы программы в целом, либо её составных частей.

Отладка программы - это процесс поиска и устранения ошибок в программе.

Тестирование и отладка программы производились с помощью локального сервера Denwer и браузера Opera 12.

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

В ходе тестирования был обнаружен ряд ошибок:

- некорректная передача данных из формы, из-за несоответствия имени формы в html файле и php скрипте.

Для решения был осуществлен правильный ввод имени формы в скрипте.

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

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

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

2.6 Руководство пользователя

Для начала работы с ресурсом необходимо установить набор web-разработчика Denwer 3 со встроенным интерпретатором php версии 6.0 и автоматическим механизмом развертывания web-сервера Apache 2.0. Скачать Denwer можно на главной странице сайта www.denwer.ru. Далее необходимо установить Denwer на ваш компьютер. Для этого просто следуйте указаниям установочной программы. После установки, на системном диске (обычно диск C:) вашего компьютера появится папка Web Servers. Запустите Denwer, с помощью ярлыка на рабочем столе, скопируйте папку kurs_1, которая содержит информационный ресурс, в папку Локальный Диск(C:)/Web Servers/home, перезапустите Denwer. После этого откройте браузер и в строке адреса напишите kurs_1/.

Работа с ресурсом начинается с главной страницы (рисунок 3), на которой находится общая информация о сайте.

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



Рисунок 3 - Главная страница ресурса

В разделе «Теория» (рисунок 4) находится информация об алгоритме сортировки слиянием и методе его реализации.

Рисунок 4 - Страница с теоретической информацией

В разделе «Выполнение» (рисунок 5) предлагается отсортировать одномерный массив. Для сортировки массива, следует ввести исходный массив в форму и нажать кнопку «Готово».

Рисунок 5 - Страница с реализацией сортировки

Для корректного вывода результата следует вводить элементы массива последовательно, через пробел (рисунок 6).



Рисунок 6 - Ввод элементов массива

После нажатия кнопки «Готово», на экране появится отсортированный массив (рисунок 7).

Рисунок 7 - Результат работы программы

В случае некорректного ввода, на экране появится сообщение об ошибке (рисунок 8).

Рисунок 8 - Сообщение об ошибке

Заключение

информационный ресурс сортировка интерфейс

В процессе выполнения данного курсового проекта была изучена специальная литература на заданную тему, и спроектирован информационный ресурс, об алгоритме сортировки методом слияния.

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

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

На основе полученной информации были составлены схемы логической и физической структур ресурса, схема программы.

Информационный ресурс доступен большинству пользователей, так как обладает невысокими требованиями к аппаратным и программным ресурсам.

Информационный ресурс был создан в среде текстового редактора Scite, отлажен и протестирован с помощью браузера Opera и локального сервера Denwer, под управление операционной системы Windows 7.

Список используемой литературы

1. Иванова Г.С. Технология программирования. М., МГТУ им. Баумана, 2003

2. Климова Л.М. Практическое программирование. Решение типовых задач. Кудиц-Образ, 2001

3. Мержевич В.В. Справочник по HTML., Версия 7.0, 2011

4. Пол Хадсон. PHP. Справочник. Кудиц-Пресс, 2006

Приложение А

(обязательное)

Разработка информационного ресурса «Сортировка слиянием»

Схема программы



Размещено на Allbest.ru