Программирование

Сортировка (List.Sort()):

Сначала функция переписывает все  элементы списка в массив, затем происходит сортировка массива методом «пузырька», после чего отсортированный массив записывается обратно в структуру. По завершении операции массив удаляется.

 

//--------------------Сортировка--------------------

template <class T, int N>

void List<T,N>::Sort() {

item *q=First;

 

int i=0, n=0;

while ((q!=NULL)&&(i<q->size)) {   //вычисление общего количества строк

    i++;

n++;

if (i==q->size) {q=q->next; i=0;}

}

 

 

q=First;

T* mas= new T[n];     

n=0;

while ((q!=NULL)&&(i<q->size)) {  //запись в  новый массив все строк списка

    mas[n]=q->data[i];

i++;

n++;

if (i==q->size) {q=q->next; i=0;}

}

 

T r;

for (i=n-1; i>0; i--) {         //сортировка массива

for (int j=0; j<i; j++)

if (mas[j]>mas[j+1]) {

r=mas[j];

mas[j]=mas[j+1];

 mas[j+1]=r;} }

 

 

q=First;   //запись отсортированого  массива обратно в структуру

int j1=0;

for (int i=0; (q!=NULL)&&(j1<n); i++) {

   

if (i>=q->size) {i=i-q->size;

                 q=q->next;} 

q->data[i]=mas[j1];

j1++;

}

}

 

Балансировка (List.Balance()):

Происходит выравнивание размерностей структур данных нижнего уровня. Это осуществляется посредством записи в промежуточный файл, удаления списка и считывания его из созданного файла. В силу особенностей функции считывания (List.Load) и добавления (List.Add) размер элемента структуры данных не превышает допустимого значения (N), задаваемого пользователем.

 

 

//----------------------------Балансировка ==b)-----------------------------

template <class T, int N>

void List<T,N>::Balance1() {

item *q=First;

 

int i=0, n=0;

while ((q!=NULL)&&(i<q->size)) { //вычисление  общего количества строк

    i++;

n++;

if (i==q->size) {q=q->next; i=0;}

       }

q=First;

T* mas= new T[n];

n=0;

 

  while ((q!=NULL)&&(i<q->size)) {      //запись в всех данных в массив

mas[n]=q->data[i];

i++;

    n++;

if (i==q->size) {i=0; q=q->next;}

}

 

    q=First;

int j=0; i=0;

 

while (q!=NULL)

{q->size=ceil((double)n/kol); 

//int g=ceil((double) n/kol);

 

q->data[i]=mas[j];

i++;

j++;

 

if (i==q->size)

{q=q->next; n=n-i; kol--; i=0;}

}

 

}

 

Сохранение в бинарный файл (List.Save()):

Производит запись содержимого списка в бинарный файл.

 

//-------------------Запись в бинарный  файл-----------------------

template<class T, int N>

void List<T,N>::Save (char *file)  // сохранение в бинарный файл

{

ofstream out(file, ios::binary); // связывание с указанным файлом

if(!out)      // файл недоступен

{

out.close(); 

cout<<"Ошибка открытия";   

}

item *q= First;

 

int n=0, i=0;

 

        while ((q!=NULL)&&(i<=q->size)) {

i++;

n++;

if (i==q->size) {q=q->next; i=0;}

        }

 

out.write((char*)&n, sizeof(int)); // записать общее кол-во строк

 

q=First;

while(q)

{

for (int i=0; q->data[i]!=NULL; i++)

out.write ((char*)&q->data[i], sizeof(T)); // сами строки

q=q->next;

}

out.close ();  // оборвать связь с файлом

}

 

Загрузка из бинарного  файла (List.Load()):

Считывает значения из бинарного  файла и поочерёдно заносит их в список функцией Add.

//----------------------Чтение из файла------------------------

template <class T, int N>

void List<T,N>::Load (char* file)  // загрузка из бинарного файла

{

ifstream in(file, ios::binary); // связь с файлом

if (!in)

{

in.close();

remove (file);    // файл не существует

cout<<rus("Файл не существует")<<endl;

}

else cout<<rus("Файл загружен")<<endl;

T obj;

int n;

in.read((char*)&n, sizeof(int)); // прочитать кол-во строк

for(int i=0; i<n; i++)

{

in.read ((char*)&obj, sizeof(T)); // прочитать сами строки

Add (obj);    // добавить в список

}

in.close();     // оборвать связь с потоком

 

}  

 

 

Информация о структуре (List.Info()):

Выводит на экран текущее состояние  структуры.

 

/----------------Информация о структуре----------------------------------------

template <class T, int N>

void List<T,N>::Info() {

 

item *q=First;

int i=0, n=0;

 

while ((q!=NULL)&&(i<=q->size)) {

i++;

n++;

if (i==q->size) {q=q->next; i=0;}

}

 

 

cout << rus("\nИНФОРМАЦИЯ")<<endl;

cout << rus("Число элементов списка:  ") << kol << endl;

cout << rus("Количество строк:    ") << n << endl;

}

 

Показать список(List.ShowList() ):

 

Осуществляет вывод списка на экран.

//------------------Показать список-----------------------------

template <class T, int N>

void List<T,N>::ShowList() {

item *q=new item;

q=First;

   

int i=0, n=0;

cout<<endl;

while (q!=NULL) {

cout<<"["<<n<<"]"<<' '<<q->data[i]<<endl;

i++;

n++;

if (i>=q->size)

{i=i-q->size; q=q->next; cout<<"---------------"<<endl;}

}

 

}

 

Разбиение элемента при  переполнении (List.Split())

 

Осуществляет проверку размера  элемента списка, если размер превышает заданное пользователем значение, то происходит запись половины указателей из текущего элемента в следующий.

 

//----------------Разбиение элемента при  переполнении------------------

template <class T, int N>

void List<T,N>::Split (item* q)                  // разбиение элемента списка при переполнении

{

if (q->size < N) return;                        // если разбиение не требуется

 

item *Temp= new item;               // создаем новый элемент списка

Temp->next= q->next;

q->next= Temp;

 

for(int i=0;i<N/2;i++)

{

Temp->data[i] = q->data[i+N/2];     // переписываем  половину указателей

q->data[i+N/2] = NULL;           // удаляем из старого

}

Temp->size= q->size= N/2;

q->data[N/2] = NULL;

Temp->data[N/2] = NULL;

kol++;                                                  // увеличиваем внутрен. счетчик списка

if(Last==q) Last=Temp; // если последний

}

 

 

 

Разработанные функции в полной мере обеспечивают требуемый в техническом  задании функционал по работе с требуемой структурой данных.  
5. Результаты нагрузочных тестов

 

Было проведено тестирование наиболее сложных функций программы: сортировки и балансировки списка.

Тестирование функции сортировки списка проводилось следующим образом: создавался список, в который добавлялись  элементы, после чего производилась сортировка списка. Число элементов увеличивалось с каждой итерацией (от 500 до 10000, шаг 500). Размер элемента списка был ограничен 6-ю.

 

Тестирование  функции балансировки списка было построено  несколько по-иному: в начале происходило хаотичное добавление случайных по величине элементов списка в разные точки списка, после чего производилась балансировка.

 

Из графиков видно, что при увеличении числа элементов списка происходит нарастание времени выполнения функции  в параболической прогрессии.  Для удобства обработки полученной информации результаты тестов записывались в текстовый файл. Текст тестовой программы приведён в приложении.

 

 

Выводы

 

Созданный шаблон структуры  данных позволяет работать со стандартными типами C++, а также более сложными типами данных (например, классом комплексных чисел, созданным отдельно, с перегруженными логическими операциями).  Разработанная структура отвечает всем требованиям, приведённым в задании, и обеспечивает выполнение полного набора необходимых операций (вывод списка на экран; добавление, вывод и удаление элемента по номеру; сортировка; сохранение и загрузка из бинарного файла; удаление списка; информация о структуре). Реализованное в работе меню позволяет работать со списком в интерактивном режиме.  Результаты тестирования программы приведены в соответствующей главе работы.

   
6. Текст программы

 

//-------------------List.h------------------------

#pragma once

#include "iostream"

#include "conio.h"

#include "string.h"

#include "stdio.h"

#include "windows.h"

#include "fstream"

 

char* rus(char* msg)

{

char* s= new char[strlen(msg)+1];

CharToOemA (msg,s);             // эта ф-я обеспечивает вывод  кириллицы

return s;

}

 

 

template <class T, int N>

class List {

 

int kol; //количество элементов  в списке

public:

struct item {

public:

friend class List;

T *data; //данные в списке

item *next; 

int size;

item () { data= new T[N+1]; data[0]=NULL; size=0; next=NULL;}   // конструктор

~item() { delete []data; size=0; next=NULL;} //деструктор

};

item *First, *Last;

 

public:

 

List();

List (List *);

~List();

 

void Split(item*); //разбиение списка

void Info (); //информация о  структуре

void ShowElement(int n);  //вывод  списка на экран

void Insert (T, int); //вставка  в список по указанному номеру

void Add(T); //добавление в конец

void DelElem(int); //удаление  по номеру

T* Get(int); //поиск в списке  по указанному номеру

void DelList(); //удаление всего  списка

void Sort(); //сортировка списка

void Balance(); //балансировка

void Balance1();

void Save(char*); //сохранение в бинарный файл

void Load(char*); //загрузка из  бинарного файла

void ShowList(); //вывод списка  на экран

};

 

template <class T, int N>

List<T,N>::List() { First=Last=NULL; kol=0;}         // конструктор списка

 

 

template <class T, int N>// деструктор списка

List<T,N>::~List () {

item *q=First;

while(q!=NULL) {

First=First->next;

delete q;

q=First; }

 

First=Last=0;

 kol=0;

}

 

 

//----------------Разбиение элемента  при переполнении------------------

template <class T, int N>

void List<T,N>::Split (item* q)                  // разбиение элемента списка при переполнении

{

if (q->size < N) return;                        // если разбиение не требуется

 

item *Temp= new item;               // создаем новый элемент списка

Temp->next= q->next;

q->next= Temp;

 

for(int i=0;i<N/2;i++)

{

Temp->data[i] = q->data[i+N/2];     // переписываем половину указателей

q->data[i+N/2] = NULL;           // удаляем из старого

}

Temp->size= q->size= N/2;

q->data[N/2] = NULL;

Temp->data[N/2] = NULL;

kol++;                                                  // увеличиваем внутрен. счетчик списка

if(Last==q) Last=Temp; // если последний

}

 

 

 

//----------------Информация  о структуре----------------------------------------

template <class T, int N>

void List<T,N>::Info() {

 

item *q=First;

int i=0, n=0;

 

while ((q!=NULL)&&(i<=q->size)) {

i++;

n++;

if (i==q->size) {q=q->next; i=0;}

}

 

 

cout << rus("\nИНФОРМАЦИЯ")<<endl;

cout << rus("Число элементов списка:  ") << kol << endl;

cout << rus("Количество  строк:    ") << n << endl;

}

 

//----------------Вставка в конец-----------------------

 

template <class T, int N>

void List<T,N>::Add(T val) {

 

 

if (First == NULL)         // если список пуст – добавляем  значение первым

{

item *q= new item;

q->next= NULL;

kol=1;

q->data[0]= val;

q->size++;

First= Last= q;

return;

}

item *q= Last;                         // иначе в конец

q->data[q->size]= val;

q->size++;

 

Split(q);  //проверка на  переполнение

}

 

 

//----------------Вставка по  номеру---------------------

 

template <class T, int N>

void List<T,N>::Insert(T val, int n)          // вставка по номеру

{

item *q=First;

 

if (q==NULL&&n==0) {Add(val); return;}

 

while ((q!=NULL)&&(n>=q->size))

{ n=n-q->size;           

  q= q->next;}

 

int j=0;

 

q->size++;

for (j=(q->size); j>n; j--)

q->data[j] = q->data[j-1];                     // раздвижка границ

 

q->data[n]= val;

Split(q);   //проверка  на переполнение

}

 

//--------------------Удаление по номеру---------------------

template <class T, int N>

void List<T, N>::DelElem(int n) {

item *q=new item;

q=First;

 

while ((q!=NULL)&&(n>=q->size))   //поиск нужного элемента списка

{

n=n-q->size;

q=q->next;

}

 

if (q==NULL) return;

 

for (int i=n; i<q->size; i++) 

q->data[i]=q->data[i+1];

 

//if (i==q->size-1)

 

q->size--;

}

 

//-------------------Вывод по номеру---------------------

template <class T, int N>

void List<T, N>::ShowElement(int n) {

item *q=new item;

q=First;

 

while ((q!=NULL)&&(n>=q->size))  //поиск нужного элемента списка

{ n=n-q->size;

 

  q= q->next;}

 

cout<<"["<<n<<"] "<<q->data[n]<<endl;

}

 

//----------------Удаление списка------------------

template <class T, int N>

void List<T,N>::DelList() {

item *q=First;

while(q!=NULL) {

First=First->next;

delete q;

q=First; }

 

First=Last=0;

kol=0;

}

 

 

//--------------------Сортировка--------------------

template <class T, int N>

void List<T,N>::Sort() {

item *q=First;

 

int i=0, n=0;

while ((q!=NULL)&&(i<q->size)) {   //вычисление общего количества  строк

    i++;

n++;

if (i==q->size) {q=q->next; i=0;}

}

 

 

q=First;

T* mas= new T[n];     

n=0;

while ((q!=NULL)&&(i<q->size)) {  //запись в новый массив  все строк списка

    mas[n]=q->data[i];

i++;

n++;

if (i==q->size) {q=q->next; i=0;}

}

 

T r;

for (i=n-1; i>0; i--) {         //сортировка массива

for (int j=0; j<i; j++)

if (mas[j]>mas[j+1]) {

r=mas[j];

mas[j]=mas[j+1];

 mas[j+1]=r;} }

 

 

q=First;   //запись отсортированого  массива обратно в структуру

int j1=0;

for (int i=0; (q!=NULL)&&(j1<n); i++) {

   

if (i>=q->size) {i=i-q->size;

                 q=q->next;} 

q->data[i]=mas[j1];

j1++;

}

}

 

//----------------------------Балансировка -----------------------------

template <class T, int N>

void List<T,N>::Balance1() {

item *q=First;

 

int i=0, n=0;

while ((q!=NULL)&&(i<q->size)) { //вычисление общего количества строк

    i++;

n++;

if (i==q->size) {q=q->next; i=0;}

       }

q=First;

T* mas= new T[n];

n=0;

 

  while ((q!=NULL)&&(i<q->size)) {

mas[n]=q->data[i];

i++;

    n++;

if (i==q->size) {i=0; q=q->next;}

}

 

    q=First;

int j=0; i=0;

 

while ((j<n)&&(q!=NULL))

{q->data[i]=mas[j];

i++;

j++;

if ((n/kol)-q->size>=1)

q->size++;

if ((n/kol)-q->size<=-1)

  q->size--;

 

if (i==q->size) {i=0; q=q->next;}

}

 

}

 

 

//------------------Показать список-----------------------------

template <class T, int N>

void List<T,N>::ShowList() {

item *q=new item;

q=First;

   

int i=0, n=0;

cout<<endl;

while (q!=NULL) {

cout<<"["<<n<<"]"<<' '<<q->data[i]<<endl;

i++;

n++;

if (i>=q->size)

{i=i-q->size; q=q->next; cout<<"---------------"<<endl;}

}

 

}

 

 

 

 

 

//-------------------Запись в  бинарный файл-----------------------

template<class T, int N>

void List<T,N>::Save (char *file)  // сохранение в бинарный файл

{

ofstream out(file, ios::binary); // связывание с указанным файлом

if(!out)      // файл недоступен

{

out.close(); 

cout<<"Ошибка открытия";   

}

item *q= First;

 

int n=0, i=0;

 

        while ((q!=NULL)&&(i<=q->size)) {

i++;

n++;

if (i==q->size) {q=q->next; i=0;}