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