Шаблон иерархической структуры данных в памяти (односвязный список, содержащий статический массив указателей на объекты), страница 5

Тестирование

Кол-во строк

Размер 

Сортировка

сек

500

5.5 Кб

6,04

1000

11 Кб

15,23

2000

22 Кб

39,99

5000

55 Кб

65,23

7000

77 Кб

128,58

9000

99 Кб

227,01

График сортировки.

Листинг программы

“1.CPP”

#include <iostream.h>

#include <fstream.h>

#include "mystring.h"

#include <conio.h>

#define     MAXN 4  /* размер статического массива указателей на объекты */

/* интерфейс класса-шаблона */

template <class T>

class CListArr {

      struct TElem {          /*  структура элемента односвязного списка*/

            T           *data[MAXN+1];    /* статический массив указателей */

            TElem *next;                  /* следующий элемент */

            int         nelems; // счётчик обьектов в одном элементе списка

      };

      TElem *top;                   /* голова(вершина) списка */

      int         nelems;     /* общее количество элементов списка */

public:

      CListArr() { top=NULL; nelems=0; } /* конструктор по умолчанию */

      ~CListArr();                            

      void Add(T elem);                  /* добавление элемента */

      int Insert(T elem, int k);         /* вставка элемента по номеру */

      T *Delete(int k);                  /* исключение элемента по номеру */

      T *Get(int k);                     /* получение элемента по номеру */

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

      void InsertKeepOrder(T elem);      /* вставка с сохранением порядка */

      int LoadFile(char * filename);     /* загрузка из файла */

      void SaveFile(char * filename);    /* сохранение в файле  */

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

      void Show();                       /* вывод на экран */

private:

int nElems(TElem *pelem);     /* подсчет количества занятых указателей массива в элементе списка */

      void FreeMemory();            /* освобождение памяти */

};

/* реализация класса-шаблона */

/* PUBLIC */

template <class T>

CListArr<T>::~CListArr() {               /* деструктор */

      FreeMemory();                

}

template <class T>

void CListArr<T>::Add(T elem) {    /* добавление эемента (elem) */

      if (top==NULL) {              /* случай с пустым списком */

            top=new TElem;          /* создание 1-го элемента */

            top->data[0]=NULL;

            top->next=NULL;

      }

      TElem *cur, *prev;

      int         n;

      for (cur=top; cur!=NULL; cur=cur->next) { /* поиск свобоного места для                                                                                элемента */

            n=nElems(cur);

            if (n<MAXN) break;

            prev=cur;

      }

      if (cur!=NULL) {                   /* место найдено */

            cur->data[n]=new T;           /* запись элемента в массив */

            *(cur->data[n])=elem;

            cur->data[n+1]=NULL;

      } else {                           /* место не найдено */

            prev->next=new TElem;        /* создание нового элемента списка */

            prev->next->data[0]=new T;

            *(prev->next->data[0])=elem;       /* запись элемента в массив */

            prev->next->data[1]=NULL;

            prev->next->next=NULL;

      }

      nelems++;                                /* изменение счетчика */

}

template <class T>

void CListArr<T>::Show() {

      TElem *temp;

      for(temp = top ; temp != NULL; temp = temp->next){

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

cout << *(temp->data[i]) << endl;  // вывод на экран каждого объекта списка

            }

      }

}

template <class T>

int CListArr<T>::Insert(T elem, int k) { /* вставка элемента(elem) по номеру(k) */