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

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

            if (k!=0) return -1;          /* не 0-й нельзя */

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

            top->data[0]=NULL;

      }

      TElem *cur, *prev;

      int         n, i;

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

            n=nElems(cur);

            if (k<n) break;

            k-=n;

            prev=cur;

      }          

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

            а k на номер внутри этого элемента */

      if (cur==NULL) {  /* место не найдено, элемент должен быть в конце списка */

            if (k!=0) return -1;

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

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

            prev->next->next=NULL;

            cur=prev->next;

            n=0;

      }

      if (n==MAXN) {    /* элемент списка найден, но места в массиве нет */

            TElem *p;

            p=new TElem;            /* добавление нового элемента в список */

            p->next=cur->next;

            cur->next=p;

            /* переписывание половины указателей */

            for (i=n/2; i<MAXN; i++) p->data[i-n/2]=cur->data[i];

            cur->data[n/2]=NULL;

            p->data[MAXN-n/2]=NULL;

            n/=2;

            if (k>=n) {                                          /* выбор между 2-мя элементами списка */

                  k-=n;

                  cur=cur->next;

                  n=MAXN-n;

            }

      }

      for (i=n+1; i>k; i--) cur->data[i]=cur->data[i-1];   /* "раздвигаем" массив */

      cur->data[k]=new T;           /* вставка нового элемента */

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

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

      return 0;

}

template <class T>

T *CListArr<T>::Delete(int k) {    /* удаление элемента по номеру(k) */

      TElem *cur, *prev;

      T           *pretelem;        /* указатель на возвращаемый элемент */

      int         n, i;

      cur=top;

      while (1) {                   /* поиск удаляемого элемента */

            n=nElems(cur);

            if (k<n) break;

            k-=n;

            prev=cur;

            cur=cur->next;

      }

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

            а k на номер внутри этого элемента */

      if (k>=n) { return NULL; }    /* элемент не найден */

      pretelem=cur->data[k];

      for (i=k+1; i<n+1; i++) cur->data[i-1]=cur->data[i]; /* "сдвигаем" массив указателей */

      if (cur->data[0]==NULL) {     /* если в массиве ничего не остается, то удаляем целиком элемент списка */

            if (cur==top) top=top->next; else prev->next=cur->next;

            delete cur;

      }

      return pretelem;

}

template <class T>

T *CListArr<T>::Get(int k) {       /* получение элемента по номеру */

      TElem *cur;

      int         n;

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

            n=nElems(cur);

            if (k<n) break;

            k-=n;

      }

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

            а k на номер внутри этого элемент */

      if (cur==NULL) return NULL;   /* возвращаем результат */

      else return cur->data[k];                     

}

template <class T>

void CListArr<T>::Sort() {         /* сортировка всей сруктуры данных */

      TElem *ielem, *jelem, *minelem;

      T           *tmp;

      int         i, j, imin;

      ielem=top;

      i=0;

      while (ielem!=NULL) {         /* цикл по всей структуре (по i) */

            minelem=jelem=ielem;

            imin=j=i;

            while (jelem!=NULL){ /* поиск минимального элемента (цикл по j) */

                  if (*(jelem->data[j])<*(minelem->data[imin])) {

                        minelem=jelem;