Пример создания связанного списка имен, упорядоченных по алфавиту

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

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

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

Удаление узла

ЦИКЛИЧЕСКИЙ ДВУНАПРАВЛЕННЫЙ СПИСОК

Ptrn2

Info

Ptrnl

Ptm2

Info

Ptrnl

Рис. 2.4. Графическое представление двунаправленных связанных списков

Двунаправленные списки имеют следующее удобное свойство [11]: если р — указатель на элемент, то

left(right(p))=p=right(left(p)),

где right(p) — ссылка на адрес следующего элемента; \ей(р) — ссылка на адрес предыдущего элемента.

Операция, которую можно выполнить над двунаправленным списком, но нельзя над обычным — это удаление элемента с заданным адресом.

Пример удаления элемент с заданным адресом/?#•

if( ptr == NULL )

printf("Удаление запрещено."); else

{

х = info(ptr); g = left(ptr); r = right(ptr); right(g) = r; left(r) = g; freenode(ptr);

Реализация списков на языке Си

1. Узел однонаправленного списка

2. Узел двунаправленного списка

3. Указатель на список

struct NODE *lst; struct NODE *p;

4. Выделение блока оперативной памяти под узел

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

5. Обращения к полям узла Однонаправленный список

p->ptrn=...; p->infо=...;

Двунаправленный список

free(p);

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

p=lst;

k=0;

while(p!=NULL)

{

k++; p=p->ptrn;

}

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

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

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). Рассматриваемый список является циклическим.

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

Узел списка

struct NODE

{

struct listnode *pred;

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

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

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

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

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

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

#include <stdio.h> #define NAME_SIZE 30

struct NODE

{

struct listnode*pred;

struct listnode*succ;

char data[NAME_SIZE]; };

main()

{

char name [NAME_SIZE];

struct NODE *root; /^Голова списка.*/

struct NODE *np; /^Используется при просмотре.*/

/*3анять блок памяти для головы списка и иницилизировать его так, чтобы он показывал сам на себя.*/ root=malloc(sizeof(struct NODE) ) ;

root->pred= root->succ=root; root->data[0]='\0' ;

/^Создать связанный список имен.*/ for ( ; ; )

{

printf ("имя:");

gets (name);

if (strcmp(name), "конец")==0)

break; if (insert(root, name)==0)

{

printf ("не хватает динамической памяти \п"); exit(1); } } /^Изобразить содержимое списка.*/

for (np=root->succ; np!=np->succ) printf ("имя=%з \n", np->data);

printf ("работа закончена \п"); }

/^Зарезервировать память для нового узла списка; скопировать в него имя и вставить новый узел в список в алфавитном порядке. Возвратить либо указатель на новый узел, либо NULL, если для создания узла не хватило памяти.*/

struct NODE *insert (node, name); struct NODE *node; /*Голова списка.*/ char *name;

{

NODE *np; /*Узел списка.*/ NODE *newnode;

/*Узел, вставленный в список.*/

/*Просматривать список, пока не обнаружится узел, поле info которого имеет значение, большее введенного имени или равное ему.*/

for (np=node->succe; (np!=node) &&

strcmp (name, np->data)>0); np=np->succe);

/^Зарезервировать память для нового узла; поместить введеное имя в его поле info и вставить новый узел перед тем, на который показывает указатель пр.*/

if( (newnode=malloc(sizeof(struct NODE)))!=0 ) {

strncpy(newnode->data, name, №\ME_SIZE);

newnode->succ=np;

newnode->pred=np->pred;

/^Изменить прямой указатель в узле, предшествующем вставленному (теперь он должен показывать на вставленный узел) и изменить обратный указатель в узле, следующем за вставленным.*/

(newnode->pred)->succ=newnode; np->pred=newnode; }

return (newnode); }