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

Коптильня купить подробнее. |

Односвязные списки


Простейшими списками являются односвязные, каждый элемент которых содержит единственный указатель на следующий. Такой список является однонаправленным, просмотр его без дополнительных "ухищрений" возможен только от первого элемента к последующему. В некоторых случаях, например при удалении элемента из списка приходится дополнительно запоминать указатель на предыдущий элемент. Рассмотрим ряд функций и фрагментов программ, работающих с односвязным списком (предполагается, что список сформирован и доступен через заголовок). Обратите внимание, что при выполнении операций включения и исключения элементов из списка заголовок может быть изменен, поэтому функция возвращает измененное значение заголовка


//------------------------------------------------------bk53-01.cpp


struct list
{ int val; list *next; };
//----- Линейный просмотр списка --------------------------


void scan(list *ph) // Заголовок списка


{ list *p;
for (p = ph; p != NULL; p = p-&#62next) { /* ...*/ }
}
//----- Включение элемента в начало списка


// v - включаемое значение


// ph - Указатель на заголовок списка


list *insertfirst(list *ph, int v)
{ list *p = new list; // создать элемент списка


p-&#62val = v; // и заполнить его


p-&#62next = ph; // следующий за новым - старый первый


ph = p; // новый первый - вновь созданный


return ph ; } // вернуть указатель на первый



//----- Включение элемента в конец списка ----------------


list *insertlast(list *ph, int v)
{ list *q ,*p= new list; // создать элемент списка;


p-&#62val = v; // и заполнить его


p-&#62next = NULL; // новый элемент - последний


if (*ph == NULL) ph = p; // список пуст


else // поиск последнего в


{ // непустом списке


for (q = *ph; q-&#62next !=NULL; q = q-&#62next);
q-&#62next = p; // включить за последним


}
return ph;
}
//----- Удаление элемента из списка по заданному номеру


list *removelist *p h, int n)
{ list *q ,*pr,*p;
// Двигаться по списку, пока он не кончится, либо пока


// не обнулится счетчик, сохраняя указатель на предыдущий




Начало  Назад  Вперед



Книжный магазин