Односвязные списки
Простейшими списками являются односвязные, каждый элемент которых содержит единственный указатель на следующий. Такой список является однонаправленным, просмотр его без дополнительных "ухищрений" возможен только от первого элемента к последующему. В некоторых случаях, например при удалении элемента из списка приходится дополнительно запоминать указатель на предыдущий элемент. Рассмотрим ряд функций и фрагментов программ, работающих с односвязным списком (предполагается, что список сформирован и доступен через заголовок). Обратите внимание, что при выполнении операций включения и исключения элементов из списка заголовок может быть изменен, поэтому функция возвращает измененное значение заголовка
//------------------------------------------------------bk53-01.cpp
struct list
{ int val; list *next; };
//----- Линейный просмотр списка --------------------------
void scan(list *ph) // Заголовок списка
{ list *p;
for (p = ph; p != NULL; p = p->next) { /* ...*/ }
}
//----- Включение элемента в начало списка
// v - включаемое значение
// ph - Указатель на заголовок списка
list *insertfirst(list *ph, int v)
{ list *p = new list; // создать элемент списка
p->val = v; // и заполнить его
p->next = ph; // следующий за новым - старый первый
ph = p; // новый первый - вновь созданный
return ph ; } // вернуть указатель на первый
//----- Включение элемента в конец списка ----------------
list *insertlast(list *ph, int v)
{ list *q ,*p= new list; // создать элемент списка;
p->val = v; // и заполнить его
p->next = NULL; // новый элемент - последний
if (*ph == NULL) ph = p; // список пуст
else // поиск последнего в
{ // непустом списке
for (q = *ph; q->next !=NULL; q = q->next);
q->next = p; // включить за последним
}
return ph;
}
//----- Удаление элемента из списка по заданному номеру
list *removelist *p h, int n)
{ list *q ,*pr,*p;
// Двигаться по списку, пока он не кончится, либо пока
// не обнулится счетчик, сохраняя указатель на предыдущий
// элемент - pr
for ( p=ph,pr=NULL; n!=0 && p!=NULL; n--, pr=p, p =p->next);
if (p==NULL) return ph;
if (pr==NULL)
{ q=ph; ph=ph->next; } // Исключить первый
else // Исключить из середины
{ q=p; pr->next=p->next; }
delete q; // Уничтожить элемент списка
return ph;
}
Рассмотрим еще несколько чисто технических решений при работе с односвязным списком. Оба они возникают в связи с известным неудобством использования указателя на предыдущий элемент, который, кстати, равен NULL для первого элемента. Для того, чтобы исключить :
-в качестве заголовка можно использовать " фиктивный" элемент без данных. Тогда все рабочие указатели в списке могут ссылаться не на текущие элементы списка, а на предыдущие ;
-можно использовать не заголовок, а указатель на заголовок. Основной цикл работы со списком будет использовать указатель на указатель на текущий элемент списка, имеющий тип list** (другая интерпретация : указатель на ячейку, где находится указатель на текущий элемент) .
//------------------------------------------------------bk53-02.cpp
// Поиск и удаление элемента списка с минимальным значением
// Заголовок списка - " фиктивный" элемент без данных
// Используется указатель на предыдущий элемент от искомого
int remove_min(list *ph)
{ // pmin - предыдущий перед минимальным
list *pmin,*p;
for (pmin=p=ph; p->next!=NULL; p=p->next)
if (pmin->next->val < p->next->val)
pmin=p;
list *q=pmin->next;
pmin->next = q->next;
int vv=q->val;
delete q;
return vv;
}
void main()
{list PH={0,NULL};} // Заголоков пустого списка в программе
Другим способом возвращения измененного заголовка списка является передача формального параметра по ссылке (использование ссылки на указатель ссылки на заголовок списка).
//------------------------------------------------------bk53-03.cpp
// Включение в конец списка
// Используется ссылка на указатель на переменную-заголовок
void insertlast(list * &ph, int v)
{ list *qq; // указатель на текущий
list *p= new list; // создать элемент списка;
p->val = v; // и заполнить его
p->next = NULL; // новый элемент - последний
if (ph==NULL) ph=p; // Список пустой меняем заголовок
else
{ // Поиск последнего
for (qq = ph; qq->next!=NULL; qq = qq->next);
qq ->next = p;
}
}
//----- Удаление элемента из списка по заданному номеру
// Используется ссылка на указатель на переменную-заголовок
void removelist * &p h, int n)
{ list *q ,*pr,*p;
// Двигаться по списку, пока он не кончится, либо пока
// не обнулится счетчик, сохраняя указатель на предыдущий
// элемент - pr
for ( p=ph,pr=NULL; n!=0 && p!=NULL; n--, pr=p, p =p->next);
if (p==NULL) return ph;
if (pr==NULL)
{ q=ph; ph=ph->next; } // Исключить первый
else // Исключить из середины
{ q=p; pr->next=p->next; }
delete q; // Уничтожить элемент списка
}
