75668

Лінійні динамічні структури. Списки

Практическая работа

Информатика, кибернетика и программирование

На початку програми виводиться список, створений у програмі. Список записується у файл output.txt. Після натиснення клавіші відбувається сортування списку за значенням числового поля-ключа (тут поле вік (age)) за допомогою функції

Украинкский

2015-01-24

365.01 KB

1 чел.

Міністерство  освіти  і  науки України

Вінницький національний технічний університет

Інститут інформаційних технологій та комп’ютерної інженерії

Кафедра ПЗ

Практична робота №4 варіант №9

з дисципліни Алгоритми та структури даних

Виконала: ст. гр. 1 ПІ-13б                            Лілик Л. С.

Перевірив:                                                       Власюк В. Х.

Вінниця, 2013


Тема: Лінійні динамічні структури. Списки.

 

Мета:  Засвоїти знання про лінійні динамічні структури даних на прикладі реалізації АТД Список. Сформувати уміння і навички обробки списків.

Завдання:

Варіант № 9 (1). Реалізувати процедуру побудови списку, значущі елементи якого зберігаються у файлі F

а) F: File of Record Key: Integer; Data: Real End; зі збереженням порядку розташування елементів у файлі. Оцінити складність алгоритму за часом.

б) F: File of Record Key: Integer; Data: Real End; Список повинен бути упорядкований за значеннями полів Key. Оцінити складність алгоритму за часом.

Опис алгоритму виконання

На початку програми виводиться список, створений у програмі. Список записується у файл output.txt. Після натиснення клавіші відбувається сортування списку за значенням числового поля-ключа (тут поле вік (age)) за допомогою функції Person::Sort(). Відсортований список записується у файл sorted_1.txt. Після того з підготовленого файлу input.txt виводяться нові елементи у список (додаються до існуючого списку). Після сортування вже нового списку, доповнений і впорядкований, він записується у файл sorted_2.txt.

Складність алгоритму

Складність алгоритму дорівнює О( 8N2 + 3N + 4) від деякого часу виконання T.  


Блок-схема алгоритму

 


Лістинг програми

#include <iostream>

#include "string"

#include "fstream"

using namespace std;

class Person

{

protected:

public:

int age;  // key

float weight;  // data

static Person *begin; // pointer to the beginnig of list

Person *next;  // pointer to the next element of list

public:

Person(int _age, float _weight);

Person(void);

Person(const Person &arg);

virtual ~Person(void);

virtual void Show(void);

static void Add(Person *n);

static void ShowList();

static void Sort(void);

friend ofstream & operator<< ( ofstream &out, Person *a);

friend ifstream & operator>> ( ifstream &in, Person *a);

};

Person *Person::begin;

Person::Person(int _age, float _weight): age(_age), weight(_weight)

{

next=0;

}

Person::Person(void)

{

   next=0;

}

Person::Person(const Person &arg)  //copy ctor

{

   age=arg.age;

   weight=arg.weight;

   next=0;

}

Person::~Person(void)

{

}

void Person::Show(void)

{

   cout<<"Age: "<<age<<" weight: "<<weight<<endl;

}

void Person::Add(Person *n)

{

Person *a;

if(begin!=0)

{

 a = begin;

 while(a->next!=0)

 {

  a=a->next;

 }

 a->next=n;

}

else

{

 begin = n;

}

}

void Person::ShowList()

{

Person *a;

a = begin;

while (a!=0)

{

 a->Show();

 cout<<endl;

 a=a->next;

}

}

void Person::Sort(void)

{

   Person *current=begin;

   bool isDone=false;

   while(!isDone)

   {

       Person *prev=0;

       isDone=true;

       current=begin;

       while(current->next!=0)

       {

           if(current->age > current->next->age)

           {

               isDone=false;

               if(prev==0)

               {

                   begin=current->next;

                   current->next=begin->next;

                   begin->next=current;

                   prev=begin;

               }

               else

               {

                   Person *temp=current->next->next;

                   prev->next=current->next;

                   prev=current->next;

                   prev->next=current;

                   current->next=temp;

               }

           }

           else

           {

               prev=current;

               current=current->next;

           }

       }

   }

}

ifstream & operator>> ( ifstream &in, Person *a)

{

if (a!=0)

{

 string st;

 in>>st;

 in>>a->age;

         in>>st;

 in>>a->weight;

 in>>st;

}

   return in;

}

ofstream & operator<< ( ofstream &out, Person *a)

{

   a = a->begin;

while (a!=0)

{

out<<"Age: \n"<<a->age<<endl;

out<<"Weight: \n"<<a->weight<<endl;

out<<"~~~~~~~~~~~~~~~~";

if(a->next!=0)

       out<<endl;

   a=a->next;

}

return out;

}

int main()

{

   cout<<"\tList of data: \n\n";

Person *a; a= new Person(9, 24.3);

Person *b; b= new Person(5, 30.8);

Person *c; c= new Person(6, 33.5);

Person *d; d= new Person(7, 36.5);

Person::Add(a);

Person::Add(b);

Person::Add(c);

   Person::Add(d);

Person::ShowList();

Person *p = a;

   ofstream out("output.txt");

out<<p;

out.close();

   cout<<"\nTo sort list press 1: ";

   int com=0;

   cin>>com;

   if(com!=1) return 0;

   cout<<"\n------- Sorted list by key (age)-------\n\n";

Person::Sort();

Person::ShowList();

ofstream outsort("sorted_1.txt");

outsort<<p;

outsort.close();

   cout<<"\nTo load list from file press 1: ";

   com=0;

   cin>>com;

   if(com!=1) return 0;

   ifstream inp("input.txt");

   while(!inp.eof())

   {

       Person *p=new Person();

       inp>>p;

       Person::Add(p);

   }

   inp.close();

cout<<"\n------- List from file -------\n\n";

Person::ShowList();

   cout<<"\nTo sort list press 1: ";

   com=0;

   cin>>com;

   if(com!=1) return 0;

   cout<<"\n------- Sorted list from file by key (age)-------\n\n";

Person::Sort();

Person::ShowList();

ofstream outsort_2("sorted_2.txt");

outsort_2<<p;

outsort_2.close();

cout<<endl;

delete a;

delete b;

delete c;

delete d;

return 0;

}

Результат виконання

Висновки

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


 

А также другие работы, которые могут Вас заинтересовать

41085. Віртуальний офіс і віртуальна організація 33.5 KB
  Віртуальний офіс Забезпечувана в останні роки технічними і програмними засобами можливість автоматизації офісу щодо електронного звязку між людьми зробила доступною новий напрям забезпечення функціонування офісу що навіть усунуло потребу роботи яка виконується в офісі [100]. Цей термін означає що робота офісу може бути виконана фактично незалежно від географічного розміщення службовців оскільки робоча територіальна мережа зєднує кілька фіксованих розміщень фірми деяким типом електронної системи звязку. Очевидність віртуального офісу...
41086. Сучасне розуміння поняття «інформація» 62 KB
  Сучасне розуміння поняття інформація Інформація і дані У контексті автоматизованого оброблення інформації та інформаційних систем термін інформація має виключно важливе значення і від правильної його інтерпретації значною мірою залежить ефективність людиномашинних систем. Згідно з Державним стандартом України ДСТУ 293894 Системи оброблення інформації. Через те що вартість інформації включаючи витрати на збирання зберігання пошук і оброблення значна величезну перевагу має її колективне використання. Отже однією з головних цілей...
41087. Озеленення міст. Влаштування озеленення на штучних поверхнях 275.5 KB
  Природоохоронні та історіко культурні ландшафти Внаслідок його експлуатації сформувалися гірничо промислові ландшафти. Тому шкільна географічна освіта в Україні потребує узагальнюючих праць про сучасні антропогенні ландшафти на території нашої країни. У працях що розглядають антропогенні ландшафти України територія Полтавщини характеризувалася побіжно у складі геосистем вищого рангу.
41088. Рішення в організаційному управлінні. Сутність створення рішення 136.5 KB
  Рішення в організаційному управлінніСутність створення рішення Компютерна інформаційна система СППР використовується для підтримки різних видів діяльності в процесі прийняття рішень: вибору загальної стратегії дій визначення спеціальних завдань делегування відповідальності оцінювання результатів ініціювання змін. Проблеми прийняття рішень і особи які їх приймають останнім часом заслуговують на все більшу увагу. Це зумовлено зростаючим динамізмом навколишнього середовища збільшенням взаємозалежності багатьох рішень стрімким темпом...
41089. Процеси створення рішень 70.5 KB
  Процеси створення рішень Загальна модель процесу прийняття рішення Як індивіди і групи осіб розробляють і приймають рішення Які кроки можна вважати безперечно ефективними Модель послідовного процесу прийняття рішення може допомогти аналізувати те як рішення розробляються і як це слід робити. Саймон 1960 року виділив такі три стадії в послідовному процесі прийняття рішень: інтелектуальна intelligence виявлення обставин можливостей для розроблення рішення збирання та упорядкування інформації і знань передбачення можливих варіантів...
41090. Структура і загальна характеристика СППР 2.07 MB
  Структура і загальна характеристика Еволюція концепції і структури СППР Концепція систем підтримки прийняття рішень виникла в кінці 60х років ХХ століття разом з ідеєю розподіленого компютерного обчислення. Терміна СППР DSS не було до 1971 року. Як уже зазначалося не існує загальноприйнятого визначення СППР.
41091. Сфери та приклади застосування СППР 63.5 KB
  Сфери та приклади застосування СППР Галузі застосування СППР Системи підтримки прийняття рішень набули широкого застосування в економіках передових країн світу причому їх кількість постійно зростає. На рівні стратегічного управління використовується ряд СППР зокрема для довго середньо і короткострокового а також для фінансового планування включаючи систему для розподілу капіталовкладень. Орієнтовані на операційне управління СППР застосовуються в маркетингу для прогнозування та аналізу збуту дослідження ринку і цін за виконання...
41092. Загальний опис Visual IFPS/Plus 581 KB
  Інтерактивна система планування фінансів Interctive Finncil Plnning System скорочено IFPS була оригінально розроблена на початку 70х років ХХ ст. Система IFPS набула надзвичайного поширення. З того часу система під назвою Visul IFPS Plus постійно вдосконалювалася.
41093. Система підтримки прийняття рішень PLEXSYS 40 KB
  Система підтримки прийняття рішень PLEXSYS Загальне описання ГСППР PLEXSYS Одним із найперспективніших напрямів розвитку СППР є створення групових систем підтримки прийняття рішень ГСППР. Дослідження галузі ГСППР дають змогу переглядати ролі й обовязки в групових діях повязаних із оцінюванням ситуації виявленням і генеруванням ідей діалектикою обговорення а також розвязанням інших завдань які приводять до прийняття групових рішень. ГСППР обєднують комунікації обчислення і технологію підтримки рішень з тим щоб допомогти деякій...