Удаление двунаправленного списка

Проверка пустоты двунаправленного списка

Поиск элемента в двунаправленном списке

Операция поиска элемента в двунаправленном списке реализуется абсолютно аналогично соответствующей функции для однонаправленного списка. Поиск элемента в двунаправленном списке можно вести:

а) просматривая элементы от начала к концу списка;

б) просматривая элементы от конца списка к началу;

в) просматривая список в обоих направлениях одновременно: от начала к середине списка и от конца к середине (учитывая, что элементов в списке может быть четное или нечетное количество).

//поиск элемента в двунаправленном списке

bool Find_Item_Double_List(Double_List* Head,

int DataItem){

Double_List *ptr; //вспомогательный указатель

ptr = Head;

while (ptr!= NULL){//пока не конец списка

if (DataItem == ptr->Data) return true;

else ptr = ptr->Next;

}

return false;

}

Операция проверки двунаправленного списка на пустоту осуществляется аналогично проверки однонаправленного списка.

//проверка пустоты двунаправленого списка

bool Empty_Double_List(Double_List* Head){

if (Head!=NULL) return false;

else return true;

}

Операция удаления двунаправленного списка реализуется аналогично удалению однонаправленного списка.

//освобождение памяти. выделенной под двунаправленный список

void Delete_Double_List(Double_List* Head){

if (Head!= NULL){

Delete_Double_List(Head->Next);

delete Head;

}

}

Пример 1. N -натуральных чисел являются элементами двунаправленного списка L, вычислить: X₁*X_n+X₂*X_n-1+...+X_n*X₁. Вывести на экран каждое произведение и итоговую сумму.

Алгоритм:

1) Создаём структуру.

2) Формируем список целых чисел.

3) Продвигаемся по списку: от начала к концу и от конца к началу в одном цикле, перемножаем данные, содержащиеся в соответствующих элементах списка.

4) Суммируем полученные результаты.

5) Выводим на печать

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

//поиск последнего элемента списка

Double_List* Find_End_Item_Double_List(Double_List* Head){

Double_List *ptr; //дополнительный указатель

ptr = Head;

while (ptr->Next!= NULL){

ptr = ptr->Next;

}

return ptr;

}

//итоговая сумма произведений

void Total_Sum(Double_List* Head) {

Double_List* lel = Head;

Double_List* mel = Find_End_Item_Double_List(Head);

int mltp,sum=0;

while(lel!= NULL) {

mltp = (lel->Data)*(mel->Data);//умножение элементов

printf("\n\n%d * %d = %d",lel->Data,mel->Data,mltp);

sum = sum + mltp;//суммирование произведений

lel = lel->Next;

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

mel = mel->Prior;

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

}

printf("\n\n Итоговая сумма равна %d",sum);

}

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