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;

}

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

Висновки

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


 

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

41200. Стимулированное плазмой осаждение из газовой фазы пленок переходных металлов и их силицидов 137.5 KB
  Осаждение пленок вольфрама. Чистый WF6 непригоден для использования в стимулированных плазмой процессах осаждения вольфрама из за того что при температуре подложки выше 900С преобладает травление а не осаждение слоя поскольку атомы фтора являются основными травящими агентами вольфрама. Действительно в результате соударения с электроном генерируются атомы фтора и предельные фториды вольфрама: е WF6 ↔ WF6х хF е . 1 Если атомы фтора не удаляются из зоны реакции или не связываются каким либо методом то происходит...
41204. ПРОБЛЕМА ЯЗЫКА И СОЗНАНИЯ 165 KB
  Все это позволяет считать что у человека есть гораздо более сложные формы получения и переработки информации чем те которые даются непосредственным восприятием. Я имею в виду тот опыт который известен как опыт Бойтендайка и который лучше других показывает отличия мышления человека от мышления животных. Такая особенность и характеризует сознание человека отличая его от психики животных. Эта черта способность человека переходить за пределы наглядного непосредственного опыта и есть фундаментальная особенность его сознания.
41205. СЛОВО И ЕГО СЕМАНТИЧЕСКОЕ СТРОЕНИЕ 143.5 KB
  Прежде всего нас будет интересовать слово и его семантическое строение т. слово как носитель определенного значения. Как известно слово является основным элементом языка.
41206. РАЗВИТИЕ ЗНАЧЕНИЯ СЛОВ В ОНТОГЕНЕЗЕ 119 KB
  Первый из них мы обозначили как предметную отнесенность понимаемую как функция слова заключающаяся в обозначении предмета признака действия или отношения. Вторым основным компонентом слова является его значение которое мы понимаем как функцию выделения отдельных признаков в предмете обобщения их и введения предмета в известную систему категорий. Сейчас мы продолжим это рассуждение и остановимся на одном из важнейших открытий советской психологической науки которое показало что оба этих компонента предметная отнесенность слова и...
41207. РАЗВИТИЕ ПОНЯТИЙ И МЕТОДЫ ИХ ИССЛЕДОВАНИЯ 165.5 KB
  Мы сказали далее что если в раннем возрасте значение слова носит у ребенка аффективный характер то к концу дошкольного и к началу школьного возраста за значением слова кроются конкретные впечатления от реального практического наглядного опыта а на дальнейших этапах за словом начинают уже стоять сложные системы отвлеченных связей и отношений и слово начинает вводить данный предмет в известную категорию иерархически построенных понятийных систем. Это положение принципиально важно для современной психологической науки потому что оно...
41208. СЛОЖНЫЕ ФОРМЫ РЕЧЕВОГО ПАРАДИГМАТИЧЕСКИЕ КОМПОНЕНТЫ В СИНТАГМАТИЧЕСКИХ СТРУКТУРАХ 149 KB
  Лишь в некоторых случаях примером которых являются так называемые пассивные конструкции например Мальчик укушен собакой синпраксическая и логическая структуры предложения расходятся и действующее лицо логическое подлежащее ставится в творительном падеже который семантически остается именительным в то время как объект воздействия в именительном который по своему значению принимает функции косвенного однако и в этом случае флексия этого косвенного падежа является средством управления. На самом деле это не два рядом...