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

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

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

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

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

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

Ptrn2

Info

Ptrnl

Ptm2

Info

Ptrnl

ptrnl

info

ptrn2

ptrnl - NULL

^1

■

ptrn2=NULL

ptrnl

info

ptrn2

—•■ ■*—

ptrnl

info

ptrn2

—* —»■ *— -*—

ptrnl

info

ptrn2

..

Рис. 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. Узел однонаправленного списка

struct NODE
{
<тип> info;
struct NODE	*ptrn;
};

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

St {	ruct NODE
struct	NODE	*ptrnl;
	<тип>	info;
	struct	NODE	*ptrn2;
};

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

struct NODE *lst; struct NODE *p;

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

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

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

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

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

р-	->ptrnl=.	• • г
р-	->info=..	• г
р-	->ptrn2=.	• • г

free(p);

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

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

p=lst;

k=0;

while(p!=NULL)

{

k++; p=p->ptrn;

}

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

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

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

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

Рис. 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); }

Дата добавления: 2014-11-29