Программирование на языке С
Страница 69. Операции со списками при связном хранении


 

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

При простом связанном хранении каждый элемент списка представляет собой структуру 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

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) удаление элемента, следующего за узлом, на который указывает р

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

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

 r=malloc(1,sizeof(ND));
r->n=p->n; r->val=new; p->n=r;

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

 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.

 
« Предыдущая статья   Следующая статья »