Перемещение на следующий элемент списка Однонаправленный список

р=	=Р"	->ptrn;
Двунаправленный список
Р= Р=	=Р" =Р"	->ptrnl; ->ptrn2;	/^перемещение /^перемещение	влево вправе	*/ */

Примеры работы со списками

Определение количества узлов в линейном однонаправленном списке (рис. 2.5).

p=lst;

k=0;

while(p!=NULL)

{

k++; p=p->ptrn;

}

printf("\nB списке %о! узлов. ",k);

1st—^			ptrn=NULL
info	ptrn	►... *■	info	ptrn

Рис. 2.5. Линейный однонаправленный список

Включение узла в двунаправленный связанный список после элемента с адресом р (рис. 2.6).

p2=(struct NODE*)malloc(sizeof(struct NODE));

p3=p->ptrn2; p->ptrn2=p2; p2->ptrnl=p; p2->ptrn2=p3; p3->ptrnl=p2; p2->info=x;

Рис. 2.6

3. Удаление узла с адресом р из двунаправленного связанного списка (рис. 2.7).

x=p->infо; q=p->ptrnl; r=p->ptrn2; q->ptrn2=r; r->ptrnl=q; free(p);

Рис. 2.7 4. Создание линейного двунаправленного списка, состоящего из п узлов.

lst=(struct NODE*)malloc(sizeof(struct NODE;

lst->ptrnl=NULL;

lst->info=...;

pl=lst;

for(i=l;i<=n-l;i++)

{

pl->ptrn2=(struct NODE*)

malloc(sizeof(struct NODE)); p2=pl;

pl=pl->ptrn2; pl->info=...; pl->ptrnl=p2;

} pl->ptrn2=NULL;

Пример. Рассмотрим реализацию списка с двойными связями. Каждый узел содержит три поля: обратный указатель В, прямой указатель F и данные info (рис. 2.8). Рассматриваемый список является циклическим.

+
В	info	F	— *■	В	info	F		В	info	F
						+

Рис. 2.8. Пример Определим структуру, представляющую узел списка.

Узел списка

struct NODE

{

struct listnode *pred;

/^обратный указатель*/ struct listnode *succ;

/*прямой указатель*/ char data[NAME_SIZE];

/*поле данных*/ };

Разработаем программу, которая упорядочивает имена в поле info по алфавиту. Функция main в диалоге запрашивает вводимые имена и вызывает функцию insert, которая образует узел для очередного имени и включает его в соответствующее место списка.

Чтобы сохранить информацию о положении начального узла списка создадим особый узел, называемый головой списка. Прямому и обратному указателям головы присваивается адрес его начала, тем самым образуется пустой список.

Функция insert просматривает список, пока не найдет место для имени.