Информатика и технология программирования

Работа со списками


Особенности работы с динамическими структурами данных заключаются в частом использовании операции косвенного обращения по указателю к структуре или к ее элементу - "*" или "-&#62" . При этом обычно используется указатель, который ссылается на текущий элемент структуры данных. Весь просмотр структуры данных заключается в циклическом или рекурсивном переходе от одного текущего элемента к другому. Для успешной работы необходимо прежде всего научиться интерпретировать средствами языка Си такие понятия, как предыдущий, текущий, последующий, первый, последний элементы, переход к предыдущему, следующему и т.д.. При трудностях сопоставления словесного и алгоритмического описания действий необходимо использовать дополнительно графическое представление. Ниже приведены фрагменты программ, выполняющих различные действия с односвязным списком.


struct list
{
list *next;
int val;
} *ph; // заголовок списка


struct list *p; // указатель на текущий элемент


//


p = ph; // текущий указатель - на первый


//


p-&#62next ... // указатель на следующий элемент


//


p = p-&#62next; // переход к следующему элементу


//


p !=NULL ... // проверка на конец списка


//


p-&#62next ==NULL ... // проверка на последний элемент




//


for (p=ph; p !=NULL; p=p-&#62next)...
// просмотр элементов списка


if (ph !=NULL)
{
for (p=ph; p-&#62next !=NULL; p=p-&#62next);
} // поиск последнего элемента


//


list *pred; // просмотр с сохранением


// указателя на предыдущий элемент


for (pred=NULL, p=ph; p !=NULL; pred=p, p=p-&#62next) ...
// указатель на второй элемент


// от текущего


//


ph-&#62next = pnew; // включение в начало непустого


ph = pnew; // списка


//


pnew-&#62next = NULL; // включение в конец непустого


pred-&#62next = pnew; // списка


//


pred-&#62next = p-&#62next; // исключение текущего элемента


// списка (если он не первый)


//


pnew-&#62next = p-&#62next; // включение после текущего


p-&#62next = pnew; // элемента

Более сложно выглядят операции в двусвязном списке, где используются указатели на следующий и предыдущий элементы:


struct list2
{
list2 *next,*pred;
int val;
} *ph, *p, *pnew;


pnew-&#62pred = p; // включение после текущего


pnew-&#62next = p-&#62next; // элемента


p-&#62next-&#62pred = pnew;
p-&#62next = pnew;
p-&#62pred-&#62next = p-&#62next; // исключение текущего элемента


p-&#62next-&#62pred = p-&#62pred; // из середины списка



Содержание раздела