Однонаправленные циклические списки
Операции над списком
1. Размещение произвольного элемента в начало списка [11]
| p=getnode(); | Выделение места под узел. |
| Запись в переменную р адреса узла. | |
| info(p)=x; | Запись значения х |
| в информационную часть узла. | |
| ptrn(p)=lst; | Подключение узла к началу списка. |
| lst=p; | Установка указателя |
| 1st на новый узел. |
2. Удаление первого элемента списка [11]
| p=lst; | Установка указателя р |
| на начало списка. | |
| lst=ptrn(p); | Установка 1st |
| на второй элемент списка. | |
| x=infо(р); | Сохранение данных |
| из удаляемого узла в переменной х. | |
| freenode(p); | Освобождение памяти, |
| занятой под первый узел. |
3. Размещение элемента после узла с адресом р [11].Новый элемент вследствие однонаправленности списка может помещаться только после узла, адрес которого известен. Поэтому для вставки узла необходимо поступить следующим образом: новый элемент размещаем после старого, затем меняем указатели. Пусть операция insafter(p, x) означает операцию вставки элемента со значением х после/?.
Операция insafter(p, x)
| g=getnode(); | Выделяем память под узел. |
| info(g)=x; | Записываем в новый узел значение х. |
| ptrn(g)=ptrn(p); | Записываем в адресную часть |
| нового узла указатель | |
| на элемент, следующий за р. | |
| ptrn(p)=g; | Записываем в адресную часть |
| узла р указатель д. |
4. Удаление элемента после узла с адресом р [11].В однонаправленном связанном списке можно удалить только элемент, следующий за данным узлом. Пусть default(/?, x) — операция удаления элемента со значением х, следующего за узлом с адресом/?.
Операция default(p, x)
g=ptrn(p); Установка указателя р на адрес
элемента, следующего за р.
| x=info(g); | Сохранение данных из |
| удаляемого узла в переменной х. | |
| ptrn(p)=ptrn (g); | Подключение узла р к узлу, |
| следующему за удаляемым. | |
| freenode(g); | Освобождение участка |
| оперативной памяти, занятой | |
| под узел д. |
Примеры
1. Из списка 1st удаляются все элементы, равные 4. Имеем два указателя: р — для просмотра списка; q — указатель на элемент перед р. Используем операции удаления: pop — из начала списка; default — из середины списка.
q=NULL; /^инициализация указателя*/
p=lst; /^текущий указатель на начало списка*/
while (p!=NULL)
{
if (info(p) == 4) if (q==NULL)
{
/*удалить первый элемент*/ x=pop(1st); freenode(p); p=lst;
} else
{
/^передвинуть р и удалить элемент,*/ /*следующим за node(q)*/ p=ptrn(p); default(q, x);
} else
{
/^продолжить просмотр, передвинуть р и q*/ q=p;
p=ptrn(p); } }
2. Список 1st упорядочен по возрастанию. Вставить х, не нарушая упорядоченность. Используем операции push для добавления элемента к началу списка, insafter — внутрь списка.
q=NULL;
p=lst;
while((p!=NULL) && (x>info(p))
{
q=p; p=ptrn(p);
}
/^размещаем х*/
if(q == NULL)
push(1st, x); /^поместить в начало списка*/ else
insafter(q, x) ;
Одним из недостатков линейных списков является то, что имея указатель р на элемент, мы не можем получить доступа к предшествующим элементам.
Циклический связанный список— это список, в котором последний узел связан с первым узлом [11]. Чтобы превратить линейный список в циклический необходимо в поле адреса последнего элемента записать не NULL, а адрес первого элемента списка 1st (рис. 2.2).
| 1st ----------------------------------- »■ | jiiutiT | 1st | |||||||
| info | pirn | —*■ | info | ptrn | ----- и- ... —и- | mfo | ptrn | ||
| . | |||||||||
Рис. 2.2. Графическое представление циклического списка
В циклическом списке всегда существует возможность доступа к любому элементу, начиная с произвольно выбранного узла.
Простейшие операции над циклическим списком [11]:
1) размещение нового узла после элемента с известным адресом/?;
2) удаление узла после элемента с известным адресом/?.
В виде циклического стека организуются стеки и очереди. Недостатки циклического списка:
1) список нельзя просматривать в обратном направлении;
2) располагая только значением указателя на элемент, его невозможно удалить.
Для преодоления этих недостатков используются двунаправленные связанные списки.