Циклический список, кольцо
Связанное хранение линейного списка называется циклическим списком или кольцом, если его последний элемент указывает на первый элемент списка, а указатель на список - на последний элемент списка (см. рис. 17).
Рис.17. Схема циклического хранения списка.
Двусвязный циклический список
Как и в случае линейного списка, элементы циклического списка могут иметь несколько ссылок. Текст программы, иллюстрирующий работу с двунаправленным циклическим списком, приведен ниже.
#include <stdio.h>
#include <alloc.h>
#include <string.h>
#include <conio.h>
#include <dos.h>
struct zap
{ char inf[50];
zap *l,*r;
};
void see(zap *);
zap *sozd(zap *);
zap *del(zap *);
void srt(zap *);
zap *srt_uk(zap *);
zap * napr(char,zap *);
void main(void)
{ zap *s=NULL;
char l;
clrscr();
while(1)
{ puts("вид операции: 1-создать кольцо");
puts(" 2-вывод содержимого кольца");
puts(" 3-удаление элемента из кольца");
puts(" 4-сортировка (изменяя указатели на элементы)");
puts(" 5-сортировка (изменяя содержимое элементов)");
puts(" 0-выход");
fflush(stdin);
switch(getch())
{ case '1': s=sozd(s); break;
case '2': if(s) see(s);
else puts("Кольцо пустое"); getch(); break;
case '3': if(s) s=del(s); break;
case '4': if(s) s=srt_uk(s); break;
case '5': if(s) srt(s); break;
case '0': return;
}
clrscr();
}
}
// функция создания/добавления в кольцо
// добавление выполняется вправо от элемента входа в кольцо
zap *sozd(zap *s)
{ zap *s1,*s2;
if (!s)
{ if(!(s=(zap *) malloc(sizeof(zap))))
{ puts("Нет свободной памяти");
return NULL;
}
puts("Введите информацию в inf");
scanf("%s",s->inf);
s->l=s;
s->r=s;
s1=s;
}
else s1=s->r; // кольцо уже существует
do
{ if((s2=(zap *) calloc(1,sizeof(zap)))==NULL)
{ puts("Нет свободной памяти");
return NULL;
}
puts("Введите информацию в inf");
scanf("%s",s2->inf);
s1->l=s2;
s2->r=s1;
s1=s2;
puts("Продолжить (y/n): ");
fflush(stdin);
} while(getch()=='y');
s2->l=s;
s->r=s2;
return(s);
}
// функция вывода содержимого кольца
void see(zap *s)
{ zap *s1;
char p;
s1=s;
puts("r - по часовой, l - против часовой\n");
fflush(stdin);
switch(p=getch())
{ case 'r': case 'R':
case 'l': case 'L':
do
{ printf("%s\n",s1->inf);
s1=napr(p,s1);
} while(s1!=s); break;
}
puts("Вывод кольца закончен");
return;
}
// функция удаления элемента кольца
zap *del(zap *s)
{ zap *s1;
char in[50];
s1=s;
puts("Введите информацию в inf");
scanf("%s",in);
do
{ if(strcmp(s1->inf,in)) s1=s1->r;
else
{ if (s1->r==s1) // элемент в кольце один
{ free(s1); return NULL; }
if(s==s1) s=s->r; // удаляемый эл-т - точка входа
s1->l->r=s1->r; // исключаем вершину из кольца
s1->r->l=s1->l;
free(s1);
return s;
}
} while(s1!=s);
printf("Записи с информацией = %s в кольце нет \n",in);
getch();
// return s;
}
// сортировка информации в кольце
void srt(zap *s)
{zap *s1,*s2;
char a[50],c;
int i;
puts("направление r - по часовой, l - против часовой\n");
fflush(stdin);
c=getch();
s1=s; // исходный элемент для замены
do
{ strcpy(a,s1->inf); // исходная информ. для замены
s2=s1;
do
{ s2=napr(c,s2); //
if(strcmp(a,s2->inf)>0)
{ strcpy(s1->inf,s2->inf);
strcpy(s2->inf,a);
strcpy(a,s1->inf);
}
} while(napr(c,s2)!=s);
s1=napr(c,s1);;
} while(napr(c,s1)!=s);
}
// сортировка информации в кольце (методом "отбора")
// рассмотрен только случай сортировки вправо (по возрастанию)
zap * srt_uk(zap *s)
{ zap *s1,*s2,*s3;
int i;
s1=s;
do
{ s2=s1->r; s3=s1; // s3 адрес элемента кольца с min значением
do // блок отбора меньшего (его адрес в s3)
{ if(strcmp(s3->inf,s2->inf)>0)
s3=s2; // s3 премещаем на узел с меньшей строкой
s2=s2->r; // поиск далее по кольцу
} while(s2!=s); // пока не прошли по кольцу
if(s3!=s1)
{ if(s==s1) s=s3; // новая точка входа в кольцо
s3->l->r=s3->r; // исключение элемента s3
s3->r->l=s3->l; // из кольца
s1->l->r=s3; // вставляем
s3->r=s1; // элемент s3
s3->l=s1->l; // перед
s1->l=s3; // s1
}
else
s1=s1->r;
} while(s1->r!=s);
return s;
}
zap * napr(char c,zap * s)
{ switch(c)
{ case 'r': case 'R': return s->r;
case 'l': case 'L': return s->l;
}
}