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;

}

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

Висновки

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


 

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

25229. Критерії вибору теорії (Поппер, Кун, Фейрабенд) 33 KB
  Поппер видiляє декiлька видiв змiсту теорiй. Перш за все згiдно критерiя демаркацiї усяка наукова теорiя має емпiричний змiст сукупнiсть тих базисних речень котрi вона забороняє. Iнакше кажучи емпiричний змiст теорiї дорiвнює класовi її потенцiйних фальсифiкаторiв. Логiчним змiстом деякого твердження чи теорiї Т символiчно CtT Поппер називає клас всiх логiчних наслiдкiв Т.
25230. Суть Сократових тез “Пізнай самого себе” і ”Я знаю лише те, що Я нічого не знаю” 25 KB
  Характерним для класики стає пізнання чуттєвого космосу в якості обєкту. Відкриває метод отримання істинного знання шляхом відкриття у загальному сутнісного змісту одиничного що дозволяє керуватись у пошуках істини добра і краси. На відміну від софістів які вважали себе справжніми вчителями мудрості Сократ критично ставився до власного знання: €œя знаю тільки що я нічого не знаю€ методологічний сумнів головний зміст якого полягає в тому що отримати знання людина може лише власними духовнодушевними зусиллями не очікуючи його...
25231. Платон про ідеї як „досконалі речі” 28 KB
  Платон про ідеї як досконалі речі€ Оригінальне вчення про ідеї. Ідеї вічні незмінні безвідносні вони не залежать від умов простору і часу. По відношенню до чуттєвих речей ідеї одночасно є їх причинами і тими зразками за якими були створені ці речи. Водночас ідеї є метою до якої прагнуть істоти чуттєвого світу.
25232. Еллінізм: відкриття духовної реальності (Сенека, Епіктет) 29.5 KB
  Саме тут вперше на основі причасності всіх людей логосу формується ідея спільного братства на місце ідеалу національної держави приходить космополітизм. Нехай з середини ти будеш інший у всьому а ззовні ми не повинні відрізнятись від людей.€ Перше що обіцяє дати філософія це вміння жити серед людей. Епіктет проповідував близькі до християнства ідеї про різку відмінність Духа від тіла про братську любов до всіх людей про необхідність постійного звернення людини до бога.
25233. Епікуреїзм: таємниця «паренклізісу» (самочинне відхилення атомів від лінії необхідності) 22.5 KB
  грекоримський епікуреїзм середній Сад епікуреїзм у Римі пізній Сад.
25234. К. Леві-Строс Структурна антропологія 33.5 KB
  полягає в застосуванні структурного методу до аналізу історикоетнографічних процесів культури як окремого людського буття так і етногенезу в цілому а також до становлення окремих форм соціального буття. полягає в тому щоб в процесі аналізу конкретної етнографічної проблематики наблизитися до осягнення проблеми становлення і формування людського суспільства і людської культури. З огляду на це вивчення життя первісних народів є ключем для розуміння загальних закономірностей культури. Енґельса оскільки момент якісного стрибка від...
25235. Поняття історичних законів у новоєвропейській філософії історії 25 KB
  Поняття історичних законів у новоєвропейській філософії історії. Поняття історичної закономірності у новоєвропейській філософії співіснує із поняттям прогресу.Час дух осягає себе в поняттях. Яскравої конкретизації поняття історичної закономірності набуває в марксизмі.
25236. Поняття системи у філософії науки 27 KB
  Поняття системи розкривається в двох основних значеннях онтологічному та методологічному. В методології широко використовується поняття теоретичної системи знання яке описує встановлення єдності між різними елементами знання на основі певних семантичних та синтаксичних правил. Онтологічний зміст поняття система розкривається в формі опису складно існуючої реальності яку поділяють на елементи звязки між ними і характеризують як цілісне утвореня. Специфічне тлумачення поняття система набуває в рамках діалектики та синергетики де вона...
25237. Проблема міфології у філософській спадщині Лосєва 41 KB
  Проблема міфології у філософській спадщині Лосєва Олексій Лосєв 1893 1988 представник російської філософії її €œзолотого віку€. Головні праці: €œФілософія імені€ €œМузика як предмет логіки€ €œДіалектика міфу€ €œІсторія античної естетики€. Міфологічна проблематика займає центральне місце в філософській спадщіні Лосєва. Сам себе він називава філософом міфу оскільки всі його роботи в тій чи іншій мірі спроба відкрити світ міфу для читатача.