Шаблон иерархической структуры данных в памяти (односвязный список, содержащий статический массив указателей на объекты), страница 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) */