Функція print_sorted_items.

КУРСОВИЙ ПРОЕКТ

На тему

«Помічник керівника роботи»

Тернопіль 2013

ЗМІСТ

3

Вступ………………………………………………………………………………………………..3

Анотація.............................................................................................................................................4

Введення…………………………………………………………………………………………....5

Зміст і структура прграми…………………………………………………………………………7

Текст програми на мові Сі………………………………………………………………………...9

Результат роботи………………………………………………………………………………….16

Висновок…………………………………………………………………………………………..17

Література…………………………………………………………………………………………18

ВСТУП

Сучасна людина постійно стикається з величезним потоком інформації і великою кількістю справ. Для того щоб не втратити важливу інформацію, а також організувати свої дії, необхідна чітка система — конкретний план.

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

Для бази даних найпростіше використовувати автоматичні програмні продукти.

У сучасному комп’ютерному світі все більше виникає потреба у виконанні однорідних дій, як от у створення конкретної бази даних. Все це досягається із використанням програмних продуктів, які створюються за допомогою спеціальних мов програмування — засобів спілкування програмістів з електронно обчислювальних машин (ЕОМ).

В загальному мови програмування можуть бути розділені на три загальні типи:

· Машинні мови;

· Асемблерні мови;

· Мови високого рівня;

Машинні мови незручні для сприйняття людиною.

З появою мов асемблера використовування комп'ютерів значно розширилося, проте все ще було потрібне написання великої кількості інструкцій навіть для реалізації рішення найпростіших задач.

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

Мова С була розроблена ДенісомРітчі з “BellLaboratories” і була вперше реалізована в 1972 році. Популярність С отримала як мова операційної системи UNIX. Сьогодні практично всі основні операційні системи написані на С або C++.

C++ зробив величезний вплив на інші мови програмування, в першу чергу на Java і C#. Будучи одним з найбільш популярних мов програмування, C++ широко використовується для розробки програмного забезпечення.

Моя програма для ведення конкретних записів, та їх систематизаціїMicrosoftVisualStudio мовою С++.

Аннотація

Работа зфайловоюсистемою. Динамічні структуриданних. Пошук і сортування.

Текст завдання

Створити файл, який містить у собівідомості прокомп’ютери в коледжі. Кожен запис міститьнаступну інформацію:

а) тип процесора;

б) рік випуску;

в) об'ємпамяті;

г) об’ємвінчестера.

Вивести в файл для друку відомостей про комп’ютери:

а) випущені до заданогороку;

б) відсортовані по зростанню об’єму пам’яті;

в) )відсортовані по зростанню об’єму вінчестеру.

Уданійроботістворюєтьсязбереження  вєдинний файл всюінформацію, і організовано сортує введенуінформацію для подальшоговиведення на друк. Цей проект демонструєможливостізастосуваннямовиСі для розробкиефективногопрограмногозабезпечення. У ньомурозглянутіаспектистворенняпрограм для упорядкування та сортуванняінформації.

Введення

Завданняданної роботиполягає в створенні програми задача якоївведену користувачем інформаціюінадалі відсортувати її за необхідними критеріями, отримати  файл для друкувідсортованої інформації.

Для цьогодобре використовувати динамічну структуру данних,а самезв’язаний список. 

Зв’язаний список - структура данних, що складається з вузлів, кожен з якихкожен з яких містить данні, так іоднеабо двапосилання («зв’язки») на наступний або попередній вузол списку. Принциповоюперед масивомєструктурна гнучкість: порядок елементів зв’язногоспискуможе не співпадати з порядком розміщення елементів данних в памяті комп’ютера, а порядок обхода спискузавжди явно задаєтсяйоговнутрішніми зв’язками.

Для формування списку в потрібномупорядкувикористовується сортування методом злиття.

Сортвання злиттям (англ. mergesort) — алгоритм сортування, якийвпорядковує списки (абоінші структуриданних, доступ доелементівяких можнаотримуватьлишепослідовно, наприклад — потоками) впевному порядку.

Приклад сортуваннязлиттям. Спочаткуділимо список на шматочки (по 1 елементу), потімпорівнюємокоженелемент з сусіднім, сортуємо і об'єднуємо. У підсумку, всіелементивідсортовані і об'єднані разом.

Для вирішеннязадачісортуванняці три етапивиглядають так:

· Сортованиймасиврозбивається на двічастиниприблизнооднаковогорозміру;

· Кожна з отриманихчастинсортуєтьсяокремо, наприклад - тим же самим алгоритмом;   

· Два впорядкованихмасивиполовинногорозміруз'єднуються в один.

1.1. - 2.1. Рекурсивнерозбиттязавдання на меншівідбувається до тих пір, покирозмірмасиву не досягнеодиниці (будь-якиймасивдовжини 1 можнавважативпорядкованим).

3.1.З’єднаннядвохвпорядкованихмасивівв один.

Основнуідеюзлиттядвохвідсортованихмасивівможнапояснити на наступномуприкладі. Нехай ми маємо два підмассиви. Нехай також, елементи підмасивівв кожному з цих підмасивіввідсортовані за зростанням. тоді:

3.2. Злиттядвох підмасивів втретійрезультуючиймасив. На кожному кроці ми беремоменший з двох перших елементівпідмасивів і записуємойого в результуючиймасив. Лічильникиномерівелементіврезультуючогомасиву і підмасива з якогобувузятийелементзбільшуємо на 1.

3.3. "Прищіплення" залишку.

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

Програма, що розробляєтьсявключатиме в себе такіфункції:

my_sorty() – Дозволяєвибратипараметрисортування та передатиїх для безпосередньогосортування та виведенняотриманихданних;даних;print_sorted_items( ) – Викликає і передаєфункціїсортування данних, порівнюєзначеннясортованоїдати з виведеної на друк і виводить результат у файл;sort_list( ) – Функція сортування;

cmp( )-Функція виборупараметрів для сортування.

Зміст і структура програми

Алгоритм програмивиконаний на мові Сі. Програмаскладається з п'ятифункцій:

main( ), my_sorty(), print_sorted_items( ), sort_list( ), cmp( )

Головна функція main () відображає інтерфейс, виробляє читання з файлу бази даних "base.bd", зчитує в пам'ять введені дані, викликає інші вищеперелічені функції.

Для обробкиінформації в БД використовуютьсянаступніфункції:

my_sorty () - Дозволяєвибратипараметрисортування та передатиїх для безпосередньосортування та виведенняотриманихданих;

print_sorted_items () - Викликає і передаєфункціїсортування данних, порівнюєзначеннясортованоїдати з виведеної на друк і виводить результат у файл;

sort_list () - Функціясортування;

cmp ()-Функція виборупараметрів сортування, року випуску, обсягупам'яті, об'ємжорсткого диска.

Для зберіганняінформації створено структуру hardware_infoзі

наступними полями:

cpu_type - Тип процесора

year - Ріквипуску

mem - Об'ємпам'яті

hdd - Об'єм HDD

item - показник на структуру

* next - показник на наступнийелементструктури

* t - показник на опрацьований елемент структуру

* head - показник на перший елементструктури

* p - показникелементуоб'єднаного списку, використовується при сортуванні

* q - показникелементуоб'єднаного списку, використовується при сортуванні

* e - показникелементуоб'єднаного списку, використовується при сортуванні

* tail - показникелементуоб'єднаного списку, використовується при сортуванні

* list – показникпідсумковийелементуоб'єднаного списку, використовується при сортуванні

Функція main( )

Дана функція є основноюфункцієюпрограми. Зцієїфункції

починаєтьсявиконаннявсієїпрограми.

Функція main () оголошує використовувані змінні і показники, виконує читання і запис у файл динних, виділяє пам'ять для елементів структури, і відповідає за інтерфейс завантаження і введення даних.

Функція my_sorty.

Функціяmy_sorty () - Дозволяєвибратипараметрисортування та передатиїх для безпосередньосортування та виведенняотриманихданих.

Передаєпараметрифункціївиведенняданихprint_sorted_items

Функція print_sorted_items.

Функція print_sorted_items () - виконує функцію введення даних, викликає і передає дані у функцію сортування даних, порівнює значення сортованої дати з виведеною на друк і виводить результат у файл.

Функцияsort_list.

Функція sort_list () - функція сортування, сортує нашу структуру, визначаючи параметри сортування викликаючи підфункціюcmp. Сортування проводиться методом злиття - алгоритм сортування, якийвпорядковує списки (абоіншіструктуриданих, доступ до елементівякихможнаотримуватитількипослідовно, наприклад - потоки) в певному порядку.

Приклад сортуваннязлиттям. Спочаткуділимо список на шматочки (по 1 елементу), потімпорівнюємокоженелемент з сусіднім, сортуємо і об'єднуємо в загальну структуру. У підсумку, всіелементивідсортовані і об'єднані разом.

Описанінаступні показники:

* P - показникелементуоб'єднаного списку, використовуваний при сортуванні, в початковому станівказує на несортоване стек

* Q – показникелементоб'єднаного списку, використовуваний при сортування, як наступнийелемент для сортування

* E - показникелементоб'єднаного списку, використовуваний при сортуванні, як допоміжнийелемент (temp)

* Tail - показник на об'єднаний список, використовуваний при сортуванні

* List - показник на підсумковий список, використовуваний при сортуванні

Описані наступні змінні:

Nmerges - підрахунок числа злиттів - сортувань;

Psize - умовний розмір-кількість елементів p;

Qsize - умовний розмір-кількість елементів p;

Insize - умовна кількість необхідних злиттів-сортувань, за замовчуванням дорівнює одній, і збільшується при необхідності.

Текст програми на мові Сі:

#include <windows.h>

#include <stdio.h>

#include <stdlib.h>

structhardware_info // Описуємо структуру

{

charcpu_type[20];

int year;

intmem;

inthdd;

structhardware_info *next;

};

typedefstructhardware_info item; // Можливість роботи з ім’ям структури

intcmp(item *a, item *b, int field) // ф-я, цо повідомляє, які елементи сортувати

{

if (field == 1)

{

return a->mem - b->mem;

}

else if (field == 2)

{

return a->hdd - b->hdd;

}

else

{

return a->year - b->year;

}

}

item *sort_list(item *list, int field) // ф-ясортування

{

item *p, *q, *e, *tail;

intinsize, nmerges, psize, qsize, i;

insize = 1;

while (1)

{

   p = list;

list = NULL; // кінцевийсписок

tail = NULL; // об’єднанийсписок

nmerges = 0; //підрахунок кількості злиттів

while (p) // Виконання потоку p існує

   {

nmerges++; // рухуємо злиття

q = p;

psize = 0;

for (i = 0; i<insize; i++)

       {

psize++;

           q = q->next;

if (!q) break; // покиє q виконуємо злиття

       }

qsize = insize;

while (psize> 0 || (qsize> 0 && q)) // поки існує два списки виконуємо злиття

{

if (psize == 0) // якщо p пусто то е берем з q

{

               e = q;

               q = q->next;

qsize--;

           }

else if (qsize == 0 || !q) // якщо q пустотоеберемз p

           {

               e = p;

               p = p->next;

psize--;

           }

else if (cmp(p, q, field) <= 0) // пропонуємополяпоякимбудемсортувати, ідізнаємосьяке поле куди перемістити (яке поле менше)

           {

               e = p;

               p = p->next;

psize--;

           }

else

           {

               e = q;

               q = q->next;

qsize--;

           }

if (tail) // Додаємо наступний елемент в загальний список, якщо він є

           {

tail->next = e;

           }

else

           {

list = e; //якщо немає то додаємо елемент в кінцевий список

}

tail = e;

       }

       p = q;

   }

tail->next = NULL;

if (nmerges<= 1) return list; // якщо злиття було тільки одне, то закінчуємо структуру

insize = 2*insize; // якщо не виконується то сортуємо 2 рази

}

}

Void print_sorted_items(item *head, intsort_field, intmax_year) // Ф-явиводуданних

{

FILE *o = NULL;

item *t = sort_list(head, sort_field);

o = fopen("print.txt","w");

while(t)

{

if (t->year >= max_year) // перевіряємо до якого року, друкуємо порівнюючи роки

   {

fprintf(o,"Типпроцессора: %s\n", t->cpu_type);

fprintf(o,"Год: %d\n", t->year);

fprintf(o,"Размерпамяти: %d\n", t->mem);

fprintf(o,"Размер HDD: %d\n\n", t->hdd);

   }

   t = t->next ; //переміщуємо зчитуюче t

}

}

voidmy_sorty(item *head) // Вибіртипусортування, іпередачадляподальшого сортування

{

chartmp[128];

intyear = 0;

printf("Введіть тип сортування: пам’ять(m)/розмір жорсткого диска(h)/рік(y)");

if (scanf("%s", tmp))

{

if (tmp[0] == 'm')

   {

print_sorted_items(head, 1, 0);

   }

else if (tmp[0] == 'h')

   {

print_sorted_items(head, 2, 0);

   }

else

   {

printf("Введітьмаксимальнийрік: ");

if (scanf("%d", &year))

       {

print_sorted_items(head, 3, year);

       }

   }

}

}

main()

{

SetConsoleOutputCP(1251);

SetConsoleCP(1251);

item *t;

item *head = NULL; // вказівник на перший елемент списку

FILE *f = NULL;

int items = 0;

chartmp[128];

if(!(f = fopen("base.bd","a+")))

printf("Помилка відкриття файлу\n");

else if(!( t = (item *)malloc(sizeof(item)))) //виділяємо пам’ять під _один_ елементструктури

printf("Помилка виділення пам’яті\n");

else

{

while(fread(t, (sizeof(item)-sizeof(item *)), 1, f)) //Читаємо файл в пам’ять, по одному елементу, і розміщуємо його t

{

       // Якщо читання не виконано, отже елементів немає

items += 1; // ведем рахунок прочитаних елементів

       t->next = head; // записуєм прочитаний елемент в структуру

head = t;

//     t = (item *)malloc(sizeof(item)); // виділяєм пам’ять під новий елемент

if (!(t = (item *)malloc(sizeof(item))))

       {

printf("Помилка виділення пам’яті\n");

break;

       }

   }

if (items == 0) // якщо елементів незнайдено, то звільнюємо t

   {

free(t);

   }

else

   {

printf("Прочитано %d записій.\n", items); // Друкуємо скільки прочитано записів з файлу

printf("Очиститибазу (d). Відсортувати (s) або додати (a) елементи?");

scanf("%s", tmp);

if (tmp[0]=='s')

       {

my_sorty(head);

fclose(f);

return 0;

       }

else if (tmp[0]=='d')

       {

           f = fopen("base.bd","w");

printf("Базаочищена.");

free(t);

items = 0;

       }

else if (tmp[0]!='a')

{

printf("Помилка введення данних\n");

return 0;

       }

   }

while(1)

   {

printf("Додати нове значення.\n");

if (!(t = (item *)malloc(sizeof(item))))

       {

printf("Помилка виділення пам’яті\n");

return -1;

       }

printf("ВведітьтипПроцесора: ");

scanf("%s", t->cpu_type);

printf("Введитьдатувиробництва: ");

scanf("%d", &t->year);

printf("Введитьразмірпамяті: ");

scanf("%d", &t->mem);

printf("Введитьразмір HDD: ");

scanf("%d", &t->hdd);

printf("Для закінчення введення натисніть (f), для продовження (a): ");

scanf("%s", tmp);

if (tmp[0] == 'f')

       {

fwrite(t, (sizeof(item)-sizeof(item *)), 1, f);

t->next = head;

head = t;

items += 1;

break;

       }

else if (tmp[0]== 'a')

       {

fwrite(t, (sizeof(item)-sizeof(item *)), 1, f);

t->next = head;

head = t;

items += 1;

       }

else

       {

printf("\n\nПомилка введення нових данних, повторіть введення.\n\n");

free(t);

continue;

       }

   }

my_sorty(head);

printf("%d Записів збережено.\n", items);

printf("Робота програмизакінчена.\n");

fclose(f);

}

return 0;

}

Результат роботипрограми

Додайтеновізначення.

Введіть тип процесора: Intel

Введіть дату виробництва: 1983

Введітьрозмірпам'яті: 64

Введітьрозмір HDD: 2

Для закінченнявведеннянатисніть (f), для продовження (a): a

Додайтеновізначення.

Введіть тип Процесора: AMD

Введіть дату виробництва: 2000

Введітьрозмірпам'яті: 1024

Введітьрозмір HDD: 23

Для закінченнявведеннянатисніть (f), для продовження (a): f

Введіть тип сортування: пам'ять (m) / розміржорсткого диска (h) / рік (y) m

2 записизбережено.

Робота програмизакінчена

В результатіроботипрограмиотримано 2 файли:

Файл з базою даних: base.bd;

Файл з результатом сортуванняпридатним для друку: print.txt.

Дані з файлу "print.txt":

Тип процесора: Intel

Рік: 1983

Розмірпам'яті: 64

Розмір HDD: 2

Тип процесора: AMD

Рік: 2000

Розмірпам'яті: 1024

Розмір HDD: 23

Висновок

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

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

Література

1. О.Ю. ПЕТРИК  КУРС ПРОГРАМУВАНН НА МОВІ СІ "Конспект лекцій" Галицький коледж 2012-2013рр.

2. http://ru.wikipedia.org/wiki/Сортировка связного списка

3. http://ru.wikipedia.org/wiki/Сортировка слиянием

4. http://algolist.manual.ru/sort/merge_sort.php

5. http://code.dawnofthegeeks.com/resources/cLinkedList.h