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;

}

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

Висновки

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


 

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

46156. СИСТЕМНО-СТРУКТУРНЫЕ ПОДХОДЫ К МОДЕЛИРОВАНИЮ СИСТЕМ УПРАВЛЕНИЯ 159 KB
  Суть системного подхода можно определить так: это методология научного познания и практической деятельности а также объяснительный принцип в основе которых лежит рассмотрение объекта как системы. Иерархичность познания требующая многоуровневого изучения предмета: изучение самого предмета собственный уровень; изучение этого же предмета как элемента более широкой системы вышестоящий уровень; изучение этого предмета в соотношении с составляющими данный предмет элементами нижестоящий уровень. Можно также сказать что системный...
46157. ОСНОВЫ ТРАНСПОРТНО-ЭКСПЕДИЦИОННОГО ОБСЛУЖИВАНИЯ 1.13 MB
  Сироткин ОСНОВЫ ТРАНСПОРТНОЭКСПЕДИЦИОННОГО ОБСЛУЖИВАНИЯ КУРСОВОЕ ПРОЕКТИРОВАНИЕ Учебнометодическое пособие Нижний Новгород 2010 ФЕДЕРАЛЬНОЕ АГЕНАСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО Волжский государственный инженернопедагогический университет А. Сироткин...
46158. Социология. Общий курс. Учебное пособие 2.78 MB
  социология: общий курс. тощенко получило признание во многих вузах россии так как наука социология в нем трактуется как социология жизни.5я73 тощенко жан терентьевич социология общий курс генеральный директор в. социология как наука.
46159. Web-браузер 16.01 KB
  Среди множества разнообразных программ просмотра гипертекстовых документов наибольшее распространение получили Microsoft Internet Explorer далее Explorer и Netscpe Nvigtor далее Netscpe. Ни та ни другая компания ничего не зарабатывает на распространении своих браузеров Explorer╗бесплатная программа а Netscpe условнобесплатная программа. Далее мы будем ориентироваться на браузер Netscpe. Методы работы с браузером Explorer практически не отличаются от методов работы с Netscpe что позволит приверженцам данного программного продукта...
46160. АДМИНИСТРАТИВНОЕ ПРАВО РОССИИ 797 KB
  Формы и методы государственного управления. Формы государственного управления. Методы государственного управления Правовые акты государственного управления Административно-правовое регулирование в сферах и отраслях управления.
46163. Традиции благотворительности и милосердия в России 60.96 KB
  Деятельность Благотворительного фонда Абсолют-Помощь плане благотворительность это помощь другим людям за счет личного благосостояния либо свободного времени и при условии что оказание данной помощи никаким образом не наносит вреда другим лицам и исполняется легально. Приведенная информация дает определенную характеристику народу способному не только сострадать но и оказывать помощь тем кто попал в беду. Благотворительные фонды оказывают помощь части общества с низким уровнем дохода что повышает общий уровень благосостояния...
46164. Противоэрозионная организация территории АО «Маяк» бригада III 156 KB
  Составление карты категорий эрозионноопасных земель. К факторам рельефа относятся: наличие пересеченного рельефа склоновых земель. Система противоэрозионной организации территории включает прогнозирование планирование и проектирование эрозионноопасных и эродированных земель определяет организационнохозяйственные технические действия по осуществлению противоэрозионных мероприятий на ближайшие годы. В этих документах особым образом выделяются не только...