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

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

      /* n1 - минимальный размер массива нового списка */

      /* kn1 - количество минимальных массивов */

      /* n2 - максимальный размер массива нового списка */

      /* kn2 - количество максимальных массивов */

      int         n1, n2, kn1, kn2, n;

      if (top==NULL) return;        /* пустой список не нужно балансировать */

      curold=top;

      nlist=0;

      /* вычисление количества элементов списка */

      while (curold!=NULL) { nlist++; curold=curold->next; }

      n1=nelems/nlist;              /* вычисление n1, n2, kn1, kn2 */

      n2=n1+1;

      kn1=n2*nlist-nelems;

      kn2=nlist-kn1;

      curold=top;                   /* установка curold на старый список */

      top=curnew=new TElem;         /* установка curnew на новый список */

      curnew->data[0]=NULL;

      curnew->next=NULL;

      inew=iold=0;

      n=n1;

      kn1--;

      /*    цикл по обоим списками, данные из старого переписываем в новый,

            в процессе элементы старого списка удаляются. а нового - создаются */

      while (1) {                                               

            curnew->data[inew]=curold->data[iold]; /* запись в новый список */

            /* шаг по новогму списку */

            if (inew==n-1) {              /* текущий элемент заполнен */           

                  curnew->data[n]=NULL;

                  if (kn1==0 && kn2==0) break;       /* выход */

                  /* определение размера нового элемента */

                  if (kn1>kn2) { kn1--; n=n1; } else { kn2--; n=n2; }       

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

                  curnew=curnew->next;

                  curnew->next=NULL;

                  inew=0;

            } else inew++;

            /* шаг по старому списку */

            iold++;

            if (curold->data[iold]==NULL) {    /* элемент списка свободен */

                  tmp=curold;                   /* удаление элемента списка */

                  curold=curold->next;

                  iold=0;

                  delete tmp;

            }

      }

      /* удаление последнего элемента старого списка */

      delete curold;                                            

}

/* PRIVATE */

template <class T>

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

      int n=0;

      while (pelem->data[n]!=NULL) n++;

      return n;

}

template <class T>

void CListArr<T>::FreeMemory() {         /* освобождение памяти */

      TElem *next;

      int         i;

      while (top) {

            next=top->next;

            i=0;

            while (top->data[i]!=NULL) { delete top->data[i]; i++; }

      /* удаление элементов массива */

            delete top;                   /* удаление элемента списка */

            top=next;

      }

}

int menu(){

    system("cls");

    int x;

      cout << "\n";

      cout << "[1] - Add\n";

      cout << "[2] - Insert by number\n";

      cout << "[3] - Delete by number\n";

      cout << "[4] - Sort\n";

      cout << "[5] - InsertKeepOrder\n";

      cout << "[6] - SaveFile\n";

      cout << "[7] - LoadFile\n";

      cout << "[8] - Balancing\n";

      cout << "[9] - Show\n";

      cout << "[0] - Quit\n";

    cout<<"Your choise: ";

    cin>>x;

    return x;

}

/* основная программа (пример использования класса)  */

void main() {

      CListArr<CMyString>     l;

      double t1,t2,k;

      t1=(double)clock();

      int a;

  while(a=menu()) {

      switch(a) {

            case 1: {

                  CMyString inputstr;

                  cout << "Input string: "; cin >> inputstr;