prog_s2_cw_report

Федеральное агентство связи
ФГОБУ ВПО «СибГУТИ»









Факультет ИВТ




Кафедра вычислительных систем






Курсовая работа
на тему "Обработка последовательности информации"
Вариант 1.1







Выполнил:
студент гр. ИС-441
Трофименко П.М.















Новосибирск, 2014

Задание
Реализовать динамическую библиотеку сортировок. Алгоритмы сортировок выбираются в соответсвии с вариантом задания. Проанализировать эффективность алгоритмов сортировки. Разработать демонстрационную программу, использующую созданную билиотеку.
Алгоритм Bubble Sort
Алгоритм Bubble Sort ...Сортировка простыми обменами, сортиро
·вка пузырько
·м (англ. bubble sort) простой алгоритм сортировки. Для понимания и реализации этот алгоритм простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n^2).
Исходныйт код BubbleSort:
void bubble_sort (int *a, int n) {
int i, t, s = 1;
while (s) {
s = 0;
for (i = 1; i < n; i++) {
if (a[i] < a[i - 1]) {
t = a[i] = a[i - 1];
a[i - 1] = t;
s = 1;
}
}
}
}

Алгоритм Quick Sort
Quicksort - один из самых быстрых известных универсальных алгоритмов сортировки массивов: в среднем O(nlogn) обменов при упорядочении n элементов; из-за наличия ряда недостатков на практике обычно используется с некоторыми доработками.
Исходный код алгоритма:
void quick_sort (int *a, int n) {
int i, j, p, t;
if (n < 2)
return;
p = a[n / 2];
for (i = 0, j = n - 1;;
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Ход работы

Для создания динамической библиотеки, в первую очередь, необходимо создать файлы, в которых будут содержаться функции, которые войдут в нашу библиотеку. Я создал 2 файла quick.c и bubble.c. После этого необходимо скомпилировать их с ключом –fPIC. Команда будет выглядеть так:
gcc -fPIC –c quick.c
В результате мы получим файлы quick.o и bubble.o.
Для создания динамической библиотеки используется ключ –shared:
gcc –shared –o libsort.so quick.o bubble.o
Эта команда скомпилировала нашу библиотеку.
Следующим шагом будет компиляция программы с подключением нашей новой библиотеки. Для начала необходимо скомпилировать файл, содержащий main:
gcc –c bubble_sort.c
На выходе получаем файл bubble_sort.o. Следующим шагом будет компиляция результирующей программы с подключением библиотеки:
gcc bubble_sort.o –L. libsort.so –o bubbleprog
В итоге мы получили файл, который будет получать функцию сортировки из динамической библиотеки. Но есть одно «но». При запуске мы получили ошибку. Проблема в том, что динамический линковщик не может найти нашу библиотеку, так как у него нет данных о её местоположении. Эта проблема решается созданием специальной переменной среды LD_LIBRARY_PATH, в которой перечисляются все каталоги, содержащие пользовательские динамические библиотеки. Устанавливается она следующим образом:
LD_LIBRARY_PATH=/root^${LD_LIBRARY_PATH}
export LD_LIBRARY_PATH
После проделанных манипуляций наша программа запустилась и отработала без ошибок.

Заголовок 1 Заголовок 2 Заголовок 315

Приложенные файлы

  • doc 353275
    Размер файла: 52 kB Загрузок: 0

Добавить комментарий