Операции со списками при связном хранении

При простом связанном хранении каждый элемент списка представляет собой структуру nd, состоящую из двух элементов: val - предназначен для хранения элемента списка, n - для указателя на структуру, содержащую следующий элемент списка. На первый элемент списка указывает указатель dl. Для всех операций над списком используется описание:

        typedef struct nd

          {  float val;

             struct nd * n;  }  ND;

        int i,j;

        ND * dl, * r, * p;

Для реализации операций могут использоваться следующие фрагменты программ:

1) печать значения i-го элемента

        r=dl;j=1;

        while(r!=NULL && j++n ;

        if (r==NULL) printf("\n нет узла %d ",i);

        else printf("\n элемент %d равен %f ",i,r->val);

2) печать обоих соседей узла(элемента), определяемого указателем p (см. рис.16)

 

Рис.16. Схема выбора соседних элементов.

 

        if((r=p->n)==NULL) printf("\n нет соседа справа");

        else  printf("\n  сосед  справа  %f",  r->val);

        if(dl==p) printf("\n нет соседа слева" );

        else { r=dl;

               while( r->n!=p ) r=r->n;

               printf("\n левый сосед %f", r->val);

             }

3) удаление элемента, следующего за узлом, на который указывает р (см. рис.17)

 

Рис.17. Схема удаления элемента из списка.

 

        if ((r=p->n)==NULL) printf("\n  нет  следующего");

        p->n=r->n; free(r->n);

4) вставка нового узла со значением new за элементом, определенным указателем р (см. рис.18)

 

Рис.18. Схема вставки элемента в список.

 

        r=malloc(1,sizeof(ND));

        r->n=p->n;   r->val=new;   p->n=r;

5) частичное упорядочение списка в последовательность значений , s+t+1=l, так что K1'=K1; после упорядочения указатель v указывает на элемент K1' (см. рис.19)

 

Рис.19. Схема частичного упорядочения списка.

 

        ND *v;

        float k1;

        k1=dl->val;

        r=dl;

        while( r->n!=NULL )

        { v=r->n;

           if (v->valn=v->n;

               v->n=dl;

               dl=v;

             }

            else r=v;

        }

Количество действий, требуемых для выполнения указанных операций над списком в связанном хранении, оценивается соотношениями: для операций 1 и 2 - Q=l; для операций 3 и 4 - Q=1; для операции 5 - Q=l.

Оглавление.