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;

}

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

Висновки

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


 

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

52317. Риторика – наука і мистецтво переконувати 67 KB
  Мета: пояснити що є предметом вивчення риторики як науки; окреслити роль і місце риторики в античному світі внесок зроблений у розвиток риторики східними словянами зясувати причину необхідності поновлення статусу риторики як науки та навчальної дисципліни в сучасній Україні використовуючи сучасне програмне забезпечення в розкритті питань; розвивати мислення комунікативні вміння зокрема робити висновки наводити аргументи та підтвердження тез; увагу пам'ять збагачувати й уточнювати словниковий запас учнів; сприяти духовному...
52318. Самое главное для человека – дружба 110.5 KB
  Ход урока І Организация урока ІІ Мотивація учебной деятельности Учитель зарубежной литературы Сегодня мы проводим необычный урок бинарный по изучению двух произведений из зарубежной и украинской литератур посвящённый теме дружбы т. Что вы знаете о литературном портрете Учитель української літератури Пригадайте що таке літературний портрет. Учитель української літератури Про якого героя йде мова Федькохаламидник із однойменного оповідання Володимира Винниченка. Учитель зарубежной литературы А...
52319. Сім’я як соціальна ланка суспільства 86 KB
  Охарактеризувати сімю як соціальну ланку суспільства логічно повязати її з предметом основи правових знань. Розкрити ознаки сімї в суспільстві активізувати та узагальнити знання учнів про поняття сімя та правові засади сімейних стосунків. Розвиваюча: Розвивати вміння аналізувати уявляти та робити висновки навички спілкування правильної поведінки в сімї.
52320. Цикли з параметром. Площа криволінійної трапеції 49 KB
  Тема уроку з алгебри: Площа криволінійної трапеціїâ. Освітня мета уроку математики: закріпити вміння і навички знаходження площі криволінійної трапеції через поняття первісної; ознайомити учнів із наближеними методами обчислення площі криволінійної трапеції; підготувати учнів до свідомого сприймання поняття інтегралу. Учитель математики: Що собою являє криволінійна трапеція Як знайти площу криволінійної трапеції Який метод використовується для цього Відповідь на це питання повинна бути проілюстрована малюнком і подана детальна...
52321. Народна казка (українська література), література і фольклор - скарбниця духовних багатств людства (зарубіжна література), виконання ілюстрацій до казки (образотворче мистецтво) 39 KB
  Мета: Розширити знання учнів про казки як вид усної народної творчості; повязати розвиток духовного багатства людства з розвитком фольклору і літератури; удосконалювати навички виразного читання та розуміння прочитаного; розвивати усне мислення; дати поняття про ілюстрацію та працю художників - ілюстраторів дитячої книжки
52322. Розмноження й розвиток рослин 48 KB
  Біологічний диктант вибрати окремо ознаки вітро та комахозапильних рослин Квітки дрібні безбарвні запаху не мають. Квітки великі яскраві. Дрібні квітки зібрані в суцвіття. Квітки розцвітають рано до розпускання листя.
52323. Розвиткове навчання засобами пропонованої технології 161 KB
  Та чи всяка діяльність учня є проявом його розумових зусиль Альтернатива тут така: якщо після виконання якогось завдання учень не прагне вдосконалення чи пізнання нового то він досяг рівня дії; якщо ж стає на шлях пошуку нових способів діяльності в біології хоча б до самостійного порівняння аналізу тощо тоді це є ознакою пізнавальної діяльності яка є інструментом розвиткового навчання. Засобами розвиткового навчання на уроці за пропонованою технологією є завданнякарточки друковані на папері чи в компютерному вираженні. Вони є...
52324. Сучасний урок. Яким він повинен бути 163 KB
  Стимулюючу роль в організації навчального процесу відіграють заняття учнів у малих групах парна групова колективна форми. Це найпрогресивніша група тварин. Що їх таких різних обєднує в один тип Від яких тварин вони походять Вивчення нового матеріалу План: Класифікація типу Членистоногі Тип Членистоногі Клас Ракоподібні Клас Павукоподібні Клас Комахи Особливості зовнішньої будови і покривів членистоногих порівняно з кільчаками робота в...
52325. ПРОЦЕСИ ЖИТТЄДІЯЛЬНОСТІ РОСЛИННОГО ОРГАНІЗМУ. УСТАНОВЧО-МОТИВАЦІЙНИЙ ЕТАП НАВЧАЛЬНОГО МОДУЛЯ З БІОЛОГІЇ 440.5 KB
  ПРОЦЕСИ ЖИТТЄДІЯЛЬНОСТІ РОСЛИННОГО ОРГАНІЗМУ. Гельмонт здійснив такий дослід з рослинами. Рослину поливали дощовою водою упродовж п'яти років. Ломоносов припустив що рослина живиться з повітря.