Двусвязный линейный список
Связанное хранение линейного списка называется списком с двумя связями или двусвязным списком, если каждый элемент хранения имеет два указателя (на предыдущий и последующий элементы линейного списка).
В программе двусвязный список можно реализовать с помощью описаний:
typedef struct ndd
{ float val; // значение элемента
ndd * n; // указатель на следующий элемент
ndd * m; // указатель на предыдующий элемент
} NDD;
NDD *dl, *p, *r;
Графическая интерпретация списка с двумя связями приведена на рис. 16.
Рис. 16. Схема хранения двусвязного списка.
Вставка нового узла со значением new за элементом, определяемым указателем p, осуществляется при помощи операторов:
r=(NDD*)malloc(NDD);
r->val=new;
r->n=p->n;
(p->n)->m=r;
p->=r;
Удаление элемента, следующего за узлом, на который указывает p
p->n=r;
p->n=(p->n)->n;
( (p->n)->n )->m=p;
free(r);
Ниже приводится текст программы, иллюстрирующий работу с двунаправленным списком.
#include <stdio.h>
#include <alloc.h>
#include <conio.h>
#include <string.h>
struct zap
{ char inf[50];
zap *pr;
zap *nx;
};
void add(zap **, zap **);
void ins(zap **, char *);
void del_any(zap **, zap **, char *);
void see(zap *, int);
void sort(zap **, zap **);
void main(void)
{ zap *h,*g; // указатели на хвост и голову очереди
char l,*st;
st=(char *)malloc(10);
h=g=NULL;
clrscr();
while(1)
{ puts("вид операции: 1-создать очередь");
puts(" 2-вывод содержимого очереди");
puts(" 3-вставка нового элемента в очередь");
puts(" 4-удаление любого элемента из очереди");
puts(" 5-сортировка очереди");
puts(" 0-окончить");
fflush(stdin);
switch(getch())
{ case '1': add(&h,&g); break;
case '2': clrscr();
puts("0-просмотр с хвоста\n1- просмотр с головы");
l=getch();
if(l=='0') see(h,0);
else see(g,1);
break;
case '3': if(h)
{ gets(st);
ins(&h,st);
} break;
case '4': if(h)
{ gets(st);
del_any(&h,&g,st);
} break;
case '5': if (h) sort(&h,&g); break;
case '0': return;
default: printf("Ошибка, повторите \n");
}
}
}
// функция создания очереди и добавления (только) в хвост очереди
void add(zap **ph,zap **pg)
{ zap *n;
puts("Создание очереди \n");
do
{ if(!(n=(zap *) calloc(1,sizeof(zap))))
{ puts("Нет свободной памяти");
return;
}
puts("Введите информацию в inf");
scanf("%s",n->inf);
if (!*ph || !*pg) // очередь еще не создана
{ *ph=n; // указатель на хвост очереди
*pg=n; // указатель на голову очереди
}
else
{ n->nx=*ph; // указатель на элемент (хвост) очереди
(*ph)->pr=n; // хвост указывает на новый элемент
*ph=n; // передвигаем указатель хвоста на новый элемент
}
puts("Продолжить (y/n): ");
fflush(stdin);
} while(getch()=='y');
}
// функция вывода содержимого очереди
// вывод начинать с хвоста (i==0) или головы (i==1)
void see(zap *p,int i)
{ puts("Вывод содержимого очереди \n");
if (!p)
{ puts("Очередь пуста");
return;
}
do
{ printf("%s\n",p->inf);
if(!i) p=p->nx;
else p=p->pr;
} while(p);
return;
}
// функция добавления элемента в очередь (до головы очереди)
// добавление работает правильно только если очередь упорядочена
// с хвоста по возрастанию [ (хвост) 1 2 5 7 9 (голова) вставить 4 ]
void ins(zap **ph,char *s)
{ zap *p=*ph,*n;
while(p && strcmp(p->inf,s)<0) p=p->nx;
if(!(n=(zap *) calloc(1,sizeof(zap))))
{ puts("Нет свободной памяти");
return;
}
strcpy(n->inf,s); // копирует s n->inf
p->pr->nx=n; // предыдущий элемент очереди указывает
// на вводимый элементт (n)
n->nx=p; // новый элемент указывает на следующий
// элемент очереди p
n->pr=p->pr; // новый элемент указывает на предыдующий
// элемент очереди p
p->pr=n; // последующий элемент очереди указывает на
// вводимый элемент
}
// функция удаления любого одного элемента очереди
// p1- указатель на хвост p2- на голову очереди
void del_any(zap **p1,zap **p2,char *st)
{ zap *ph=*p1;
if (!*p1 || !p2)
{ puts("Очередь пуста");
return;
}
if (ph->nx==NULL && // в очереди только один элемент
(!strcmp(ph->inf,st) || *st=='\0'))
{ free(ph);
*p1=*p2=NULL; // очередь пуста
return;
}
while(ph && strcmp(ph->inf,st)) ph=ph->nx;
if (!strcmp(ph->inf,st)) // найден элемент со строкой st
{ if(ph==*p1) // удаляемая вершина - хвост очереди
{ *p1=(*p1)->nx; // новый указатель на хвост очереди
(*p1)->pr=NULL;
}
else if(ph==*p2) // удаляемая вершина - голова очереди
{ *p2=(*p2)->pr; // новый указатель на голову очереди
(*p2)->nx=NULL;
}
else
{ ph->pr->nx=ph->nx; // обходим элемент pr
ph->nx->pr=ph->pr;
}
free(ph); // удаляем элемент pr очереди
}
}
// функция сортировки содержимого очереди
void sort(zap **ph,zap **pg)
{ zap *s1,*s2,*s3;
for(s2=*pg ;s2; s2=s2->pr)
for(s1=*ph; s1->nx; s1=s1->nx)
{ if(strcmp(s1->nx->inf,s1->inf)>0)
{ s3=s1->nx; // s3- вершина следующая за s1
if(!s1->pr) *ph=s1->nx; // модификация хвоста очереди
s1->nx=s1->nx->nx; // s1-nx указывает через вершину
if(s1->nx) s1->nx->pr=s1; // s1->nx выше был модифицирован
else s2=*pg=s1; // s1->nx==NULL -коррекция головы
s3->pr=s1->pr;
s3->nx=s1;
if (s3->pr) s3->pr->nx=s3;
s1->pr=s3;
s1=s1->pr; // откат для s1=s1->nx в цикле for
}
}
puts("Сортировка выполнена");
}