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;

}

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

Висновки

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


 

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

17576. Дослідження арифметико-логічних команд РІС – контролера 136 KB
  Лабораторна робота № 2 Дослідження арифметикологічних команд РІС контролера Множення без знакових чисел Мета роботи: Вивчення алгоритму множення без знакових чисел та його реалізація за допомогою системи команд периферійного РІС контролера у програмному ...
17577. Программная реализация обнаружения ошибки в пакете 174.5 KB
  Лабораторная работа №6 Тема: Программная реализация обнаружения ошибки в пакете Цель: Научиться обнаружать ошибки в пакете с помощью программной реализации Краткие теоретические сведения: w equ 0; f equ 1; r0 equ 0c; r1 equ 0d; r2 equ 0e; packet equ 45; polinom equ 0b; status equ 03; ...
17578. Исследование команд для работы с битами PIC контроллера 170 KB
  Лабораторная работа № 3 Тема: Исследование команд для работы с битами PIC контроллера Деление без знаковых чисел Цель работы: изучение алгоритма деления без знаковых чисел и его реализация при помощи системы команд периферийного PIC контроллера в программной ср
17579. Исследование команд передачи управления 93.5 KB
  Лабораторная работа № 4 Тема: Исследование команд передачи управления. Программная реализация алгоритма коррекции после сложения чисел в BCD формате. Цель: Исследовать команды передачи управления при помощи программной реализации алгоритма сложения чисел ...
17580. Исследование команд управления и работа с константами 188.5 KB
  Лабораторная работа № 5 Тема: Исследование команд управления и работа с константами. Программная реализация механизма десятичной коррекции при вычислении текста BCD Цель: Изучить принцип механизма десятичной коррекции с использованием системы команд микро...
17581. Исследование команд для работы с битами. Деление без знаковых чисел 168.5 KB
  Лабораторная работа № 3 Исследование команд для работы с битами Деление без знаковых чисел Цель работы: Изучения алгоритма деления без знаковых чисел и его реализация при помощи системы команд периферийного PIC контроллера в программной среде MP LAB. Крат...
17582. ОСНОВЫ РАБОТЫ В СРЕДЕ MATHCAD 811 KB
  Лекция 1. Основы работы в среде MathCAD MathCAD работает с документами. С точки зрения пользователя документ это чистый лист бумаги на котором можно размещать блоки трех основных типов: математические выражения текстовые фрагменты и графические области. Расположение н
17583. РЕШЕНИЕ УРАВНЕНИЙ СРЕДСТВАМИ MATHCAD 1.83 MB
  Лекция 2 Решение уравнений средствами Mathcad Как известно многие уравнения и системы уравнений не имеют аналитических решений. В первую очередь это относится к большинству трансцендентных уравнений. Доказано также что нельзя построить формулу по которой можно было б
17584. ПРОГРАММИРОВАНИЕ C ИСПОЛЬЗОВАНИЕМ ПРОГРАММ ФУНКЦИЙ MATHCAD 366 KB
  Лекция 3 Программирование c использованием программ функций MathCad Реализовать тот или иной алгоритм вычисления в пакете Mathcad можно двумя способами: вставляя соответствующие операторы или функции в текст документа Mathcad. Такой способ называется программированием в те...