![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Операции со списками при связном хранении
При простом связанном хранении каждый элемент списка представляет собой структуру 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 (см. рис.3)
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) удаление элемента, следующего за узлом, на который указывает р (см. рис.4)
if ((r=p-> n)==NULL) printf(" \n нет следующего"); p-> n=r-> n; free(r-> n); 4) вставка нового узла со значением new за элементом, определенным указателем р (см. рис.5)
r=malloc(1, sizeof(ND)); r-> n=p-> n; r-> val=new; p-> n=r; 5) частичное упорядочение списка в последовательность значений, s+t+1=l, так что K1'=K1; после упорядочения указатель v указывает на элемент K1' (см. рис.6)
Количество действий, требуемых для выполнения указанных операций над списком в связанном хранении, оценивается соотношениями: для операций 1 и 2 - Q=l; для операций 3 и 4 - Q=1; для операции 5 - Q=l.
|