Работа со списками
Особенности работы с динамическими структурами данных заключаются в частом использовании операции косвенного обращения по указателю к структуре или к ее элементу - "*" или "->" . При этом обычно используется указатель, который ссылается на текущий элемент структуры данных. Весь просмотр структуры данных заключается в циклическом или рекурсивном переходе от одного текущего элемента к другому. Для успешной работы необходимо прежде всего научиться интерпретировать средствами языка Си такие понятия, как предыдущий, текущий, последующий, первый, последний элементы, переход к предыдущему, следующему и т.д.. При трудностях сопоставления словесного и алгоритмического описания действий необходимо использовать дополнительно графическое представление. Ниже приведены фрагменты программ, выполняющих различные действия с односвязным списком.
struct list
{
list *next;
int val;
} *ph; // заголовок списка
struct list *p; // указатель на текущий элемент
//
p = ph; // текущий указатель - на первый
//
p->next ... // указатель на следующий элемент
//
p = p->next; // переход к следующему элементу
//
p !=NULL ... // проверка на конец списка
//
p->next ==NULL ... // проверка на последний элемент
//
for (p=ph; p !=NULL; p=p->next)...
// просмотр элементов списка
if (ph !=NULL)
{
for (p=ph; p->next !=NULL; p=p->next);
} // поиск последнего элемента
//
list *pred; // просмотр с сохранением
// указателя на предыдущий элемент
for (pred=NULL, p=ph; p !=NULL; pred=p, p=p->next) ...
// указатель на второй элемент
// от текущего
//
ph->next = pnew; // включение в начало непустого
ph = pnew; // списка
//
pnew->next = NULL; // включение в конец непустого
pred->next = pnew; // списка
//
pred->next = p->next; // исключение текущего элемента
// списка (если он не первый)
//
pnew->next = p->next; // включение после текущего
p->next = pnew; // элемента
Более сложно выглядят операции в двусвязном списке, где используются указатели на следующий и предыдущий элементы:
struct list2
{
list2 *next,*pred;
int val;
} *ph, *p, *pnew;
pnew->pred = p; // включение после текущего
pnew->next = p->next; // элемента
p->next->pred = pnew;
p->next = pnew;
p->pred->next = p->next; // исключение текущего элемента
p->next->pred = p->pred; // из середины списка
