Интерфейс класса односвязного списка
Односвязный список предназначен для хранения упорядоченного набора однотипных элементов. Чтобы не определять для каждого типа данных свой список, определим шаблонный класс:
|
1 |
template<typenameT> classList{ private // Объявление структуры узла для использования в классе Iterator structNode; public // Класс итератора односвязного списка classIterator{ // Пока что опускаем … }; public List(); ~List(); // Добавление узла в список voidappend(constT& t ); // Удаление последнего добавленного узла из списка voidremove(); // Получить головной элемент списка Thead()const; // Получить итератор на начало списка Iterator begin()const; // Получить итератор на конец списка Iterator end()const; // Получить размер списка size_t size()const; private // Структура узла односвязного списка structNode{ Node()m_next(NULL){} Node(constT& t ) : m_t( t ), m_next( NULL ) { } // Указатель на следующий узел Node*m_next; }; // Голова односвязного списка Node*m_head; }; |
Наш класс односвязного списка будет поддерживать добавление узла в его начало, удаление последнего добавленного узла и получение значения головного элемента. Кроме того, мы реализуем обход списка с помощью итераторов, а также добавим функцию-член для расчета длины списка.
Узел определяется с помощью структуры
Node, которая содержит два поля:
m_t — значение, привязанное к узлу, и
m_next — указатель на следующий узел.
Изначально список пуст, поэтому головной элемент указывает на
NULL:
|
1 |
template<typenameT> List<T>List()m_head(NULL){ } |
Поиск длины хвоста в списке с циклом[править]
Так как для поиска хвоста мы должны знать, что цикл существует, воспользуемся предыдущей функцией и при выходе из неё запомним «момент встречи» зайца и черепахи. Назовем её .
Наивные реализацииправить
Реализация за править
Будем последовательно идти от начала цикла и проверять, лежит ли этот элемент на цикле. На каждой итерации запустим от вперёд указатель. Если он окажется в текущем элементе, прежде чем посетит снова, то точку окончания (начала) хвоста нашли.
Реализация за править
Реализацию, приведенную выше можно улучшить. Для этого воспользуемся бинарным поиском. Сначала проверим голову списка, потом сделаем шага вперёд, потом , потом и так далее, пока не окажемся на цикле. Теперь у нас есть две позиции — на левой границе, где мы в хвосте, и на правой — в цикле. Сделаем бинарный поиск уже по этому отрезку и таким образом найдём цикл за .
Эффективная реализацияправить
Возможны два варианта цикла в списке. Первый вариант — сам список циклический (указатель последнего элемента равен первому), а второй вариант — цикл внутри списка (указатель последнего элемента равен любому другому (не первому)). В первом случае найти длину цикла тривиально, во второй случай сводится к первому, если найти указатель на начало цикла. Достаточно запустить один указатель из , а другой из головы с одной скоростью. Элемент, где оба указателя встретятся, будет началом цикла. Сложность алгоритма — .
Ниже приведена функция, которая находит эту точку, а возвращает длину хвоста списка.
int getTail(Node head, Node pointMeeting):
firstElement = head.next
secondElement = pointMeeting.next
lengthTail = 1
while firstElement != secondElement
firstElement = firstElement.next
secondElement = secondElement.next
lengthTail = lenghtTail + 1
return lengthTail
Доказательство корректности алгоритмаправить
Рассмотрим цикл длиной с хвостом длины . Напишем функции для обоих указателей в зависимости от шага . Очевидно, что встреча не может произойти при , так как в этом случае для любого . Тогда положения указателей зададутся следующими функциями (при ):
Приравнивая, получим , или .
Пусть — голова списка, — точка встречи, — первый элемент цикла, — расстояние от до . Тогда в точку можно прийти двумя путями: из в длиной и из через в длиной , то есть:
, но так как
Пусть
Известно, что
откуда
Подставив полученные значения, получим:
, откуда следует, что если запустить указатели с одной скоростью из и , то они встретятся через шагов в точке . К этому времени вышедший из пройдёт ровно шагов и остановится в , вышедший из накрутит по циклу шагов и пройдёт ещё шагов. Поскольку , то они встретятся как раз в точке .
Основные операции над односвязными списками
- Инициализировать связанный список InitList
- Уничтожить связанный списокОсвободите все пространство узлов по одному
3. Найдите длину связанного списка.
4. Определите, пуст ли связанный список.
5. Вывести связанный список
6. Найдите определенный элемент данных в указанной позиции (найдите i-й узел данных с начала в связанном списке, если он существует, верните его значение домена данных через переменную e)
7. Найдите и выполните поиск по значению элемента (найдите первый узел, диапазон значений которого равен e, в связанном списке с самого начала, если он существует, вернуть его порядок, в противном случае вернуть 0)
8. Вставьте элемент данных (сначала найдите i-й узел в связанном списке.p, если он существует, присвоить значение узлу es вставляется после него)
![Реализация двусвязного списка на c [айти бубен]](https://myeditor.ru/wp-content/uploads/4/5/9/459e45abb6f653713583cf16977fa9d2.jpeg)
9. Удалить элементы данных.
2020.4.25 Первая заметка Сяо Чэня на языке Си во время эпидемии В следующий раз, когда я обновлю связанный список несколькими более сложными операциями, я все еще внимательно изучаю.
Используйте struct для реализации двусвязного списка в C++
Связанные списки считаются одной из наиболее распространенных структур данных, с которыми вы можете столкнуться при программировании. Эти структуры связаны в том смысле, что каждый узел содержит адрес другого. Связанные списки бывают двух типов: односвязные списки и двусвязные списки. Односвязный список содержит узлы, которые указывают только на следующий узел в списке; таким образом, он делает обход структуры однонаправленным. С другой стороны, двусвязные списки обеспечивают двусторонний доступ из каждого узла в списке.
В этом случае мы реализуем двусвязный список с помощью команды , делая все его элементы данных общедоступными и определяя функции манипулирования элементами отдельно
Обратите внимание, что можно предпочесть объектно-ориентированную версию с функциями-членами, обеспечивающими процедуры управления элементами и некоторые элементы данных для ведения записей
Следующий пример кода включает код драйвера в функцию, которая проверяет базовый сценарий использования, где векторные элементы вставляются в список, а затем список освобождается. Мы используем оператор для динамического выделения каждого узла, и, следовательно, функция выполняет итерацию по списку, вызывая на каждом .
Метод отдельного выделения каждого может быть неэффективным, если пользователь хочет разработать относительно высокопроизводительную структуру связанного списка. Можно рассмотреть массовое выделение ресурсов памяти для быстрого добавления новых узлов и, когда в этом нет необходимости, одновременно освободить несколько узлов. В этом проекте мы начинаем строить список с действительного элемента, представляющего первый узел в структуре. Некоторые реализации могут создавать фиктивный элемент, который обозначает заголовок списка, но не содержит данных элемента.
Выход:
Вы можете использовать связанные списки в качестве строительных блоков более специализированных структур данных, таких как стеки, двухсторонние очереди, очереди или кольцевые списки. Последний интересен тем, что это, по сути, двусвязный список, в котором последний узел указывает на первый элемент как на следующий узел, и, соответственно, первый указывает на последний элемент как на предыдущий узел
Обратите внимание, что следующий фрагмент кода добавляет функцию для отображения содержимого каждого узла в созданном списке
Выход:
Пример реализации на Free Pascal[править]
type spisok=^element; //Сперва требуется обозначить список как тип element=record //обозначаем элементы списка как запись, чтобы поместить туда данные и указатель на следующий элемент infointeger; //поле info отвечает за данные, которые хранит элемент списка (может быть любого типа) nextspisok; //так как список линейный, у нас будет указатель только на следующий элемент end; var p, first,elem,lastspisok; //создаём вспомогательную переменную элемента, переменные начального элемента, вспомогательного элемента и конечного элемента типов список begin New(elem); //создаём новый элемент в динамической памяти elem^.next:=nil; //зануляем указатель на следующий элемент (так как его нету) elem^.info:=random(40)-20; //заполняем поле информации генератором рандома first:=elem; last:=elem; //так как элемент пока первый и последний, присваиваем оба элемента ему // Процедура добавления элемента в конец списка New(elem); elem^.info:=random(40)-20; elem^.next:=nil; last^.next:=elem; //следующий от последнего теперь наш элемент last:=elem; // и наш элемент и есть теперь последним //Процедура добавления элемента в начало списка New(elem); elem^.info:=random(40)-20; elem^.next:=first; //следующим есть первый элемент first:=elem; //наш элемент теперь первый //Процедура удаления элемента с начала списка New(elem); elem:=first; //присваиваем нашему элементу значение первого first:=first^.next; //первым стал следующий элемент dispose(elem); //удаляем наш элемент //Процедура удаления элемента с конца списка (тут потяжелее, так как список линейный) New(elem); elem:=first; while(elem^.next<>last) do //крутим цикл, пока не дойдем до элемента стоящего перед последним p:=elem^.next; elem^.next := nil; //делаем следующий от него элемент 0 dispose(last); //удаляем последний элемент last:= p; //теперь наш элемент последний end.
Пример реализации односвязного списка на C[править]
Заголовочный файл :
#ifndef LIST_H
#define LIST_H
#include<stdio.h>
#include<stdlib.h>
typedefstruct list{
intval;
struct list*next;
}List;
staticList*list_new(intval);
voidlist_add(List**list,intval);
voidlist_node_del(List**node);
voidlist_del_by_value(List**list,intval);
voidlist_free(List*list);
#endif
Файл :
#include"list.h"
staticList*list_new(intval){
List*list=(List*)malloc(sizeof(List));
list->val=val;
list->next=NULL;
returnlist;
}
voidlist_add(List**list,intval){
for(;*list!=NULL;list=&(*list)->next);
*list=list_new(val);
}
voidlist_node_del(List**node){
free(*node);
(*node)=(*node)->next;
}
voidlist_del_by_value(List**list,intval){
for(;*list!=NULL;list=&(*list)->next){
if((*list)->val==val){
list_node_del(list);
break;
}
}
}
voidlist_free(List*list){
for(;list!=NULL;list=list->next)
free(list);
}
Взаимообмен узлов списка
Здесь тоже необходимо рассмотреть две ситуации:
- меняются соседние узлы
При этом узлы могут быть переданы в любом порядке относительно корня списка. Для упрощения реализации функции поменяем узлы так, чтобы node1 стоял перед node2 - меняются отстоящие узлы
1234567891011121314151617181920212223242526272829303132333435
void List::Swap(Node* node1, Node* node2){ if (node1 == NULL || node2 == NULL) return; // не допускаем обмен с несуществующим узлом if (node1 == node2) return; // если один узел указан дважды, менять ничего не надо if (node2->ptr == node1) // если node2 находится перед node1, меняем их местами { Node *p = node1; node1 = node2; node2 = p; } Node *prev1 = Prev(node1); Node *prev2 = Prev(node2); Node *next1 = Next(node1); Node *next2 = Next(node2); if (next1 == node2) // обмен соседних узлов { if (prev1 != NULL) prev1->ptr = node2; else head = node2; node2->ptr = node1; node1->ptr = next2; return; } if (prev1 != NULL) // обмен отстоящих узлов prev1->ptr = node2; else head = node2; if (prev2 != NULL) prev2->ptr = node1; else head = node1; node2->ptr = next1; node1->ptr = next2;}
Взаимообмен узлов ДЛС
В качестве аргументов функция взаимообмена узлов ДЛС принимает два указателя на обмениваемые узлы, а также указатель на корень списка. Функция возвращает адрес корневого узла списка.
Взаимообмен узлов списка осуществляется путем переустановки указателей. Для этого необходимо определить предшествующий и последующий узлы для каждого заменяемого. При этом возможны две ситуации:
- заменяемые узлы являются соседями;
- заменяемые узлы не являются соседями, то есть между ними имеется хотя бы один узел.
При замене соседних узлов переустановка указателей выглядит следующим образом:
При замене узлов, не являющихся соседними переустановка указателей выглядит следующим образом:
Функция взаимообмена узлов списка выглядит следующим образом:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
struct list * swap(struct list *lst1, struct list *lst2, struct list *head){ // Возвращает новый корень списка struct list *prev1, *prev2, *next1, *next2; prev1 = lst1->prev; // узел предшествующий lst1 prev2 = lst2->prev; // узел предшествующий lst2 next1 = lst1->next; // узел следующий за lst1 next2 = lst2->next; // узел следующий за lst2 if (lst2 == next1) // обмениваются соседние узлы { lst2->next = lst1; lst2->prev = prev1; lst1->next = next2; lst1->prev = lst2; if(next2 != NULL) next2->prev = lst1; if (lst1 != head) prev1->next = lst2; } else if (lst1 == next2) // обмениваются соседние узлы { lst1->next = lst2; lst1->prev = prev2; lst2->next = next1; lst2->prev = lst1; if(next1 != NULL) next1->prev = lst2; if (lst2 != head) prev2->next = lst1; } else // обмениваются отстоящие узлы { if (lst1 != head) // указатель prev можно установить только для элемента, prev1->next = lst2; // не являющегося корневым lst2->next = next1; if (lst2 != head) prev2->next = lst1; lst1->next = next2; lst2->prev = prev1; if (next2 != NULL) // указатель next можно установить только для элемента, next2->prev = lst1; // не являющегося последним lst1->prev = prev2; if (next1 != NULL) next1->prev = lst2; } if (lst1 == head) return(lst2); if (lst2 == head) return(lst1); return(head);}
Код примера использования приведенных функцийСтруктуры данных
3.3 Операции с компонентами списка
Ну, перед тем, как проводить какие-то операции с компонентами, их необходимо добавить в список, чем мы сейчас и займемся. Прежде всего, нам необходимо создать новый компонент и заполнить его информационную часть. Так как мы будем помещать его в конец списка, то ссылочная часть узла будет иметь значение NULL. Теперь давайте поймем, что должно происходить со ссылками head и tail при этой операции. Здесь рассматриваются 2 случая — наш список пуст или в нем есть хотя бы один компонент. Если пуст, то и head и tail будут указывать на только что созданный компонент. Если же узлы в списке присутствуют, очевидно, что сначала нужно последний узел связать с добавляемым (для этого ссылочной части компонента, на который указывает tail, присвоить адрес того, который хотим добавить), а затем «передвинуть» tail. Вот как просто все это выглядит на С++:
// Включение в список нового компонента
void comp_in(dyn_list &l, char* n, char* v)
{
comp* c = new comp();
strcpy_s(c->name, 20, n);
strcpy_s(c->value, 10, v);
c->next = NULL;
if (chk_empty(l))
l.head = c;
else
l.tail->next = c;
l.tail = c;
}
// Поиск компонента в списке по имени
comp* search(dyn_list l, char *n)
{
while (l.head != NULL)
{
if (!strcmp(l.head->name,n))
return l.head;
l.head = l.head->next;
}
return l.head;
}
// Удаление компонента из списка
void comp_del(dyn_list &l, comp* c)
{
if (c == l.head)
{
l.head = c->next;
return;
}
comp* r = new comp();
r = l.head;
while (r->next != c)
r = r->next;
r->next = c->next;
delete c;
}
// Изменение значения компонента
void comp_edit(comp &c, char* v)
{
strcpy_s(c.value, 10, v);
}
С операциями закончили, теперь осталось дописать программу.
Стандартные функции для работы с динамической памятью в языке Си
Для работы с динамическим объектами в Си есть new и dispose — это функции стандартной библиотеки malloc и free. Для их
использования нужно включить в программу заголовочный файл ‹stdlib.h›. В этом
файле также вводится обозначение NULL для пустого (нулевого) указателя.
void *malloc (size_t size)
malloc возвращает указатель на место в памяти для объекта размера size.
Выделенная память не инициализируется. Если память отвести не удалось, то
результат работы функции — NULL. (Тип size_t — это беззнаковый целый тип,
определяемый в файле ‹stddef.h›, результат операции sizeof имеет тип size_t). Как
правило, обобщенный указатель, возвращаемый этой функцией, явно
приводится к указателю на тип данных . Об этом говорит сайт https://intellect.icu . Например, создать динамическую
переменную типа double и присвоить значение, возвращаемое malloc,
переменной dp — указателю на double, можно с помощью выражения
dp = (double*) malloc (sizeof (double)).
Созданная динамическая переменная существует вплоть до завершения работы
программы, или до момента, когда она явно уничтожается с помощью функции
free.
void free (void *p)
free освобождает область памяти, на которую указывает p; если p равно NULL,
то функция ничего не делает. Значение p должно указывать на область памяти,
ранее выделенную с помощью функций malloc или calloc После освобождения
памяти результат разыменования указателя p непредсказуем; результат также
непредсказуем при попытке повторного обращения к free c этим же указателем.
Приведем описание еще одной функции распределения памяти в Си. Ею удобно
пользоваться, когда нужно разместить в динамической памяти.
void *calloc (size_t nobj, size_t size)
calloc возвращает указатель на место в памяти, отведенное для массива nobj
объектов, каждый из которых имеет размер size. Выделенная область памяти
побитово обнуляется. (Заметим, что это не всегда равнозначно присваиванию
нулевых значений соответствующим элементам массива. В некоторых
реализациях в побитовом представлении нулевого указателя или значения 0.0 с
плавающей точкой могут быть ненулевые биты). Если память отвести не
удалось, то результат работы функции — NULL.
Добавление узла в ОЦС
Функция добавления узла в список принимает два аргумента:
- Указатель на элемент, после которого происходит добавление
- Данные для добавляемого элемента.
Процедуру добавления элемента можно отобразить следующей схемой:
Добавление элемента в ОЦС включает в себя следующие этапы:
- создание добавляемого узла и заполнение его поля данных;
- переустановка указателя узла, предшествующего добавляемому, на добавляемый узел;
- установка указателя добавляемого узла на следующий узел (тот, на который указывал предшествующий узел).
Таким образом, функция добавления узла в ОЦС имеет вид, полностью аналогичный функции добавления узла в односвязный линейный список:
12345678910
struct list * addelem(list *lst, int number){ struct list *temp, *p; temp = (struct list*)malloc(sizeof(list)); p = lst->ptr; // сохранение указателя на следующий элемент lst->ptr = temp; // предыдущий узел указывает на создаваемый temp->field = number; // сохранение поля данных добавляемого узла temp->ptr = p; // созданный узел указывает на следующий элемент return(temp);}
Поиск цикла в списке[править]
Для начала необходимо уметь определять — список циклический или нет. Воспользуемся алгоритмом Флойда «Черепаха и заяц». Пусть за одну итерацию первый указатель (черепаха) переходит к следующему элементу списка, а второй указатель (заяц) на два элемента вперед. Тогда, если эти два указателя встретятся, то цикл найден, если дошли до конца списка, то цикла нет.
boolean hasCycle(Node head):
tortoise = head
hare = head
repeat
if hare == NULL or hare.next == NULL
return false
tortoise = tortoise.next
hare = hare.next.next
until tortoise == hare
return true
Если цикла не существует, то заяц первым дойдет до конца и функция возвратит . В другом случае, в тот момент, когда и черепаха и заяц находятся в цикле, расстояние между ними будет сокращаться на , что гарантирует их встречу за конечное время.
Двусвязные списки
Последнее обновление: 02.09.2016
Двусвязные списки также представляют последовательность связанных узлов, однако теперь каждый узел хранит ссылку на следующий и на предыдущий элементы.
Двунаправленность списка приходится учитывать при добавлении или удалении элемента,
так как кроме ссылки на следующий элемент надо устанавливать и ссылку на предыдущий. Но в то же время у нас появляется возможность обходить список как от первого к последнему
элементу, так и наоборот — от последнего к первому элементу. В остальном двусвязный список ни чем не будет отличаться от односвязного списка.
Для создания двусвязного списка вначале надо определить класс узла, который будет представлять элемент списка:
public class DoublyNode<T>
{
public DoublyNode(T data)
{
Data = data;
}
public T Data { get; set; }
public DoublyNode<T> Previous { get; set; }
public DoublyNode<T> Next { get; set; }
}
Далее определим сам класс списка:
using System.Collections.Generic;
using System.Collections;
namespace SimpleAlgorithmsApp
{
public class DoublyLinkedList<T> : IEnumerable<T> // двусвязный список
{
DoublyNode<T> head; // головной/первый элемент
DoublyNode<T> tail; // последний/хвостовой элемент
int count; // количество элементов в списке
// добавление элемента
public void Add(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);
if (head == null)
head = node;
else
{
tail.Next = node;
node.Previous = tail;
}
tail = node;
count++;
}
public void AddFirst(T data)
{
DoublyNode<T> node = new DoublyNode<T>(data);
DoublyNode<T> temp = head;
node.Next = temp;
head = node;
if (count == 0)
tail = head;
else
temp.Previous = node;
count++;
}
// удаление
public bool Remove(T data)
{
DoublyNode<T> current = head;
// поиск удаляемого узла
while (current != null)
{
if (current.Data.Equals(data))
{
break;
}
current = current.Next;
}
if(current!=null)
{
// если узел не последний
if(current.Next!=null)
{
current.Next.Previous = current.Previous;
}
else
{
// если последний, переустанавливаем tail
tail = current.Previous;
}
// если узел не первый
if(current.Previous!=null)
{
current.Previous.Next = current.Next;
}
else
{
// если первый, переустанавливаем head
head = current.Next;
}
count--;
return true;
}
return false;
}
public int Count { get { return count; } }
public bool IsEmpty { get { return count == 0; } }
public void Clear()
{
head = null;
tail = null;
count = 0;
}
public bool Contains(T data)
{
DoublyNode<T> current = head;
while (current != null)
{
if (current.Data.Equals(data))
return true;
current = current.Next;
}
return false;
}
IEnumerator IEnumerable.GetEnumerator()
{
return ((IEnumerable)this).GetEnumerator();
}
IEnumerator<T> IEnumerable<T>.GetEnumerator()
{
DoublyNode<T> current = head;
while (current != null)
{
yield return current.Data;
current = current.Next;
}
}
public IEnumerable<T> BackEnumerator()
{
DoublyNode<T> current = tail;
while (current != null)
{
yield return current.Data;
current = current.Previous;
}
}
}
}
По большому счету этот двусвязный список реализует те же действия, что и односвязный, разница заключается в необходимости установки свойства Previous для узлов списка.
В методе добавления , если в списке уже есть элементы, то у добавляемого узла свойство указывает на узел, который до этого
хранился в переменной tail:
if (head == null)
head = node;
else
{
tail.Next = node;
node.Previous = tail;
}
tail = node;
Аналогично в методе добавлении в начало списка для головного элемента свойство Previous начинает указывать на новый элемент, а новый
элемент, таким образом, становиться первым элементом в списке.
При удалении вначале необходимо найти удаляемый элемент. Затем в общем случае надо переустановить две ссылки:
current.Next.Previous = current.Previous; current.Previous.Next = current.Next;
Если удаляются первый и последний элемент, соответственно надо переустановить переменные head и tail.
И также в отличие от односвязной реализации здесь добавлен метод для перебора элементов с конца.
Применение списка:
DoublyLinkedList<string> linkedList = new DoublyLinkedList<string>();
// добавление элементов
linkedList.Add("Bob");
linkedList.Add("Bill");
linkedList.Add("Tom");
linkedList.AddFirst("Kate");
foreach (var item in linkedList)
{
Console.WriteLine(item);
}
// удаление
linkedList.Remove("Bill");
// перебор с последнего элемента
foreach (var t in linkedList.BackEnumerator())
{
Console.WriteLine(t);
}
НазадВперед
3.1. Стандартное начало
Приступим к решению. Создаем консольный проект, и пишем довольно стандартный код — организовываем файловый ввод. Для чтения из файла используем метод getline(), где в качестве третьего параметра указываем пробел, являющийся разделителем в нашем файле.
#include <fstream>
#include <iostream>
#include <cstdlib>
//TODO: Описание списка
//TODO: Операции со списком
using namespace std;
int main()
{
char* fileName = new char;
char* buf_name = new char;
char* buf_value = new char ;
cout << "Enter name of file -> ";
cin >> fileName;
ifstream* inp = new ifstream(fileName);
if (!inp->good())
{
cout << "File opening error!\n";
system("PAUSE");
return 0;
}
while (!inp->eof())
{
inp->getline(buf_name, 20, ' ');
inp->getline(buf_value, 10, ' ');
Вывод элементов списка
/* print: печатает в стандартный выходной поток элементы списка */
void print ( list p )
{
while ( p != NULL ) { /* пока не конец списка, */
putchar ( p−>elem ); /* печатаем очередной элемент */
p = p−>next; /* и переходим к следующему звену */
}
putchar ( '\n' );
}
Заголовок while-цикла можно было записать как while ( p ). Однако, выражение p != NULL более информативно — по нему можно догадаться, что p скорее всего является указателем, даже не видя его описания.
Опишем функцию печати, используя цикл for.
/* print: печать в стандартный выходной поток элементов списка
версия с циклом for */
void print ( list p )
{
for ( ; p ; p = p−>next ) /* пока не конец списка, т.е. p!=NULL */
putchar ( p−>elem ); /* печатаем очередной элемент
и переходим к следующему звену */
putchar( '\n' ) ;
}
Здесь мы использовали p в качестве условия продолжения цикла, а не p != NULL, так как рядом стоящее p –>next (в третьем выражении заголовка for), говорит о том, что p — указатель.
