Вставка элемента в однонаправленный список

Печать (просмотр) однонаправленного списка

Создание однонаправленного списка

Для того, чтобы создать список, нужно создать сначала первый элемент списка, а затем при помощи функции добавить к нему остальные элементы. При относительно небольших размерах списка наиболее изящно и красиво использование рекурсивной функции. Добавление может выполняться как в начало, так и в конец списка.

//создание однонаправленного списка (добавления в конец)

void Make_Single_List(int n,Single_List** Head){

if (n > 0) {

(*Head) = new Single_List();

//выделяем память под новый элемент

cout << "Введите значение ";

cin >> (*Head)->Data;

//вводим значение информационного поля

(*Head)->Next=NULL;//обнуление адресного поля

Make_Single_List(n-1,&((*Head)->Next));

}

}

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

//печать однонаправленного списка

void Print_Single_List(Single_List* Head) {

if (Head!= NULL) {

cout << Head->Data << "\t";

Print_Single_List(Head->Next);

//переход к следующему элементу

}

else cout << "\n";

}

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

Рис. 2. Вставка элемента в однонаправленный список

/*вставка элемента с заданным номером в однонаправленный список*/

Single_List* Insert_Item_Single_List(Single_List* Head,

int Number, int DataItem){

Number--;

Single_List *NewItem=new(Single_List);

NewItem->Data=DataItem;

NewItem->Next = NULL;

if (Head == NULL) {//список пуст

Head = NewItem;//создаем первый элемент списка

}

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

Single_List *Current=Head;

for(int i=1; i < Number && Current->Next!=NULL; i++)

Current=Current->Next;

if (Number == 0){

//вставляем новый элемент на первое место

NewItem->Next = Head;

Head = NewItem;

}

else {//вставляем новый элемент на непервое место

if (Current->Next!= NULL)

NewItem->Next = Current->Next;

Current->Next = NewItem;

}

}

return Head;

}

Дата добавления: 2014-01-04