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

       

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


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


//------------------------------------------------------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;
// Двигаться по списку, пока он не кончится, либо пока


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



// элемент - pr

for ( p=ph,pr=NULL; n!=0 &#38&#38 p!=NULL; n--, pr=p, p =p-&#62next);
if (p==NULL) return ph;
if (pr==NULL)
{ q=ph; ph=ph-&#62next; } // Исключить первый

else // Исключить из середины

{ q=p; pr-&#62next=p-&#62next; }
delete q; // Уничтожить элемент списка

return ph;
}

Рассмотрим еще несколько чисто технических решений при работе с односвязным списком. Оба они возникают в связи с известным неудобством использования указателя на предыдущий элемент, который, кстати, равен
NULL для первого элемента. Для того, чтобы исключить :


-в качестве заголовка можно использовать " фиктивный" элемент без данных. Тогда все рабочие указатели в списке могут ссылаться не на текущие элементы списка, а на предыдущие ;


-можно использовать не заголовок, а указатель на заголовок. Основной цикл работы со списком будет использовать указатель на указатель на текущий элемент списка, имеющий тип
list** (другая интерпретация : указатель на ячейку, где находится указатель на текущий элемент) .



//------------------------------------------------------bk53-02.cpp

// Поиск и удаление элемента списка с минимальным значением

// Заголовок списка - " фиктивный" элемент без данных

// Используется указатель на предыдущий элемент от искомого

int remove_min(list *ph)
{ // pmin - предыдущий перед минимальным

list *pmin,*p;
for (pmin=p=ph; p-&#62next!=NULL; p=p-&#62next)
if (pmin-&#62next-&#62val &#60 p-&#62next-&#62val)
pmin=p;
list *q=pmin-&#62next;
pmin-&#62next = q-&#62next;
int vv=q-&#62val;
delete q;
return vv;
}
void main()
{list PH={0,NULL};} // Заголоков пустого списка в программе

Другим способом возвращения измененного заголовка списка является передача формального параметра по ссылке (использование ссылки на указатель ссылки на заголовок списка).



//------------------------------------------------------bk53-03.cpp

// Включение в конец списка

// Используется ссылка на указатель на переменную-заголовок




void insertlast(list * &#38ph, int v)
{ list *qq; // указатель на текущий

list *p= new list; // создать элемент списка;

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

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

if (ph==NULL) ph=p; // Список пустой меняем заголовок

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

for (qq = ph; qq-&#62next!=NULL; qq = qq-&#62next);
qq -&#62next = p;
}
}
//----- Удаление элемента из списка по заданному номеру

// Используется ссылка на указатель на переменную-заголовок

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

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

// элемент - pr

for ( p=ph,pr=NULL; n!=0 &#38&#38 p!=NULL; n--, pr=p, p =p-&#62next);
if (p==NULL) return ph;
if (pr==NULL)
{ q=ph; ph=ph-&#62next; } // Исключить первый

else // Исключить из середины

{ q=p; pr-&#62next=p-&#62next; }
delete q; // Уничтожить элемент списка

}


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