МУ_ЛР8_ОП (1079941), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

// Удаление

pTemp->pNext = pTemp->pNext->pNext;

//Выход

return;

}

…

Фрагмент текста программы для удаления из списка:

//ФУНКЦИИ УДАЛЕНИЯ для однонаравленного списка

printf ("Содержимое списка до удаления функциями: \n");

PrintElemList ( *(MY_List.Head.pNext) );

DelList( &MY_List); // Из головы

DelLastList( &MY_List ); // Из хвоста

DelListNum ( &MY_List , 2 ); // По номеру

printf ("Содержимое списка после удаления функциями: \n");

PrintElemList ( *(MY_List.Head.pNext) );

…

Результаты работы программы при удалении.

Содержимое списка до удаления функциями:

Печать списка элементов:

Элемент = 55

Элемент = 1

Элемент = 2

Элемент = 99

Элемент = 3

Элемент = 77

Содержимое списка после удаления функциями:

Печать списка элементов:

Элемент = 1

Элемент = 2

Элемент = 3

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

Функция для замены двух элементов списке (SwapNum). Данная функция может быть использована для различных алгоритмов сортировки списков. Для замены указываются два номера. Для удобства и прозрачности замен используется вспомогательная функция (GetListNum) позволяющая пол номеру получить адрес элемента списка.

// Получение элемента по номеру без удаления

int GetListNum( List * pL , ListElem ** ppE , int Num , ListElem ** ppPrev = NULL)

{

*ppE = NULL;

ListElem ETemp = {NULL , 33};

ListElem * pETemp = &ETemp;

ListElem ** ppTemp = &pETemp ;

if ( ppPrev == NULL ) ppPrev = ppTemp;

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

if (( Num < NULL) || ( Num > pL->Count)) return -1 ; // Нет удаления

// Проверка на первый и последний

if ( Num <= NULL) { *ppE = pL->Head.pNext ;

*ppPrev = &(pL->Head);

return 0;}// ГОЛОВА

if ( Num >= pL->Count ) { *ppE = pL->Tail.pNext ;

*ppPrev = &(pL->Tail);

return 0;}// ХВРСТ

// Удалить в середину Num > 0 и Num < Count

// Найти указатель заданного номера

ListElem * pTemp = pL->Head.pNext;

*ppPrev = & (pL->Head) ;

int nCur ;

for ( nCur = 0 ; nCur < Num ; nCur++ )

{

*ppPrev = pTemp;

pTemp = pTemp->pNext;

}

//

*ppE = pTemp;

//Выход

return 0;

}

Функция замены по номеру

// Замена в списке по номеру

void SwapNum ( List * pL , int Num1 , int Num2)

{

ListElem * pE1;

ListElem * pE2;

ListElem * pPrevE1;

ListElem * pPrevE2;

ListElem * pTemp;

GetListNum( pL , &pE1 , Num1, &pPrevE1);

GetListNum( pL , &pE2 , Num2 ,&pPrevE2);

if ( pE1 != pE2) // Равны элементы

{

//

pTemp = pPrevE1->pNext;

pPrevE1->pNext = pPrevE2->pNext;

pPrevE2->pNext = pTemp;

//

pTemp = pE1->pNext;

pE1->pNext = pE2->pNext;

pE2->pNext = pTemp;

}

return;

};

Пример использования функции замены по номерам в списке.

printf ("Содержимое списка после SWAP по номеру: \n");

SwapNum ( &MY_List, 1 , 5);

PrintElemList ( *(MY_List.Head.pNext) );

Результат работы функции замены:

Печать списка элементов:

Элемент = 55

Элемент = 1

Элемент = 2

Элемент = 99

Элемент = 3

Элемент = 77

Содержимое списка после SWAP по номеру:

Печать списка элементов:

Элемент = 55

Элемент = 77

Элемент = 2

Элемент = 99

Элемент = 3

Элемент = 1

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

Функция для замены двух элементов списке (SwapPtr). Данная функция может быть использована для различных алгоритмов сортировки списков. Для замены указываются два адреса. Для удобства и прозрачности замен используется вспомогательная функция (GetListPNT) позволяющая по адресу получить номер элемента списка.

int GetListPNT( List * pL , ListElem * pE , int * Num)

{

*Num = 0;

ListElem * pTemp = pL->Head.pNext;

int Flag = false;

while ( pTemp != NULL)

{

if ( pTemp == pE ) { Flag = true; break;}

pTemp = pTemp->pNext;

(*Num)++;

};

return Flag;

};

Пример использования функции замены по адресам в списке.

/// Замена в списке на основе элументов - указателей на них

void SwapPtr ( List * pL , ListElem * pE1, ListElem * pE2)

{

int Num1;

int Num2;

if ((GetListPNT( pL , pE1 , &Num1) == true) && (GetListPNT( pL , pE2 , &Num2) == true ))

SwapNum ( pL , Num1 , Num2);

return;

};

…

Вызов функции замены:

printf ("Содержимое списка после SWAP по адресу: \n");

SwapPtr (&MY_List, &E77 , &E99);

PrintElemList ( *(MY_List.Head.pNext) );

…

Результат работы функции:

Печать списка элементов:

Элемент = 55

Элемент = 77

Элемент = 2

Элемент = 99

Элемент = 3

Элемент = 1

Содержимое списка после SWAP по адресу:

Печать списка элементов:

Элемент = 55

Элемент = 99

Элемент = 2

Элемент = 77

Элемент = 3

Элемент = 1

Задачник Абрамова!!! Гл 13 , 14, 18, 22, 23, 27, 28, 29, 33, 35, 36

29 Описание структур и основных функций для двунаправленного списка

Структуры данных, необходимые для демонстрации работы с двунаправленными списками в следующих примерах.

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

struct Node {

Node * pNext;

Node * pPrev;

int ListVal;

};

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

struct DList {

Node Head; // Голова списка

Node Tail; // Хвост списка

int Count; // Число элементов

};

…

Функции, необходимые для демонстрации работы с двунаправленными списками в следующих примерах.

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

void InitNode ( Node * pNode , Node * pN, Node * pP, int Val)

{

if ( pN != NULL) pNode->pNext = pN;

else pNode->pNext = NULL;

if ( pP != NULL) pNode->pPrev = pP;

else pNode->pPrev = NULL;

pNode->ListVal = Val;

};

// Инициализация двунаправленнного списка

void InitList( DList * pL )

{

pL->Head.pNext = NULL;

pL->Tail.pNext = NULL;

//

pL->Head.pPrev = NULL;

pL->Tail.pPrev = NULL;

pL->Count =NULL ;

};

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

void DListPrint ( DList L )

{

printf ("Содержимое списка DList: \n");

Node * pE = L.Head.pNext;

if ( pE == NULL) printf ("Список пуст! \n");

while ( pE != NULL )

{

printf ("Элемент = %d \n", pE->ListVal );

pE = pE->pNext; // Очень важно - навигация по списку

};

};

// Добавление в голову двунаправленнного списка

void AddDList( DList * pL , Node * pNode ){

// В голову

if ( pL->Head.pNext == NULL)

{ pL->Head.pNext = pNode;

pL->Tail.pNext = pNode;

pNode->pNext = NULL;

pNode->pPrev = NULL;

( pL->Count ) ++ ;

return; };

// Для новой

pNode->pNext = pL->Head.pNext;

pNode->pPrev = NULL;

// Для старой первой

pL->Head.pNext->pPrev = pNode;

// Для головы

pL->Head.pNext = pNode;

//

( pL->Count ) ++ ;

};

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

void AddTailDList( DList * pL , Node * pNode ){

// Проверка пустого списка

if ( pL->Tail.pNext == NULL)

{

//до добавления список был пуст

pL->Head.pNext = pNode;

pL->Tail.pNext = pNode;

pNode->pNext = NULL;

pNode->pPrev = NULL;

( pL->Count ) ++ ;

return; };

// Для новой в хвост

pNode->pPrev = pL->Tail.pNext ;

pNode->pNext = NULL ;

// Для бывшей последней

pL->Tail.pNext->pNext = pNode;

// Для хвоста

pL->Tail.pNext = pNode;

// увеличим счетчик элементов

( pL->Count ) ++ ;

};

…

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

…

// Прототипы функций для двунаправленнного списка

void InitNode ( Node * pNode , Node * pN, Node * pP, int Val);

void InitList( DList * pL );

void DListPrint( DList L );

void AddDList( DList * pL , Node * pNode );

void AddTailDList( DList * pL , Node * pNode );

30 Создание, заполнение и распечатка двунаправленного списка

Рассмотрим пример программы, в который включено следующее: описание списка (DList) и его элемента(Node); инициализацию двунаправленного списка и его элементов (InitList , InitNode); ручное добавление элементов в список (AddDList) и распечатку списка (DListPrint).

…

// Динамические двунаправленные списки

DList L1;

// Начальная настройка списка

InitList( &L1 );

DListPrint ( L1 ); // печать пустого списка

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

Node * pNode;

printf ("Добавление в голову: \n");

// Выделение памяти, заполнение первого элемента и добавление в список

pNode = (Node *) malloc (sizeof(Node));

InitNode ( pNode , NULL,NULL, 1 );

AddDList( &L1 , pNode );

DListPrint ( L1 ); // печать списка с одним элементом

…

После выполнения фрагмента программы, расположенного выше, получим следующий результат:

Содержимое списка DList:

Список пуст!

Добавление в голову:

Содержимое списка DList:

Элемент = 1

Добавим еще несколько элементов в список и получим результат, расположенный ниже:

// Выделение памяти, заполнение второго элемента

pNode = (Node *) malloc (sizeof(Node));

InitNode ( pNode , NULL,NULL, 2 );

AddDList( &L1 , pNode );

pNode = (Node *) malloc (sizeof(Node));

InitNode ( pNode , NULL,NULL, 3 );

AddDList( &L1 , pNode );

DListPrint ( L1 ); // добавлено всего 3 элемента

printf ("Добавление в хвост и в голову: \n");

pNode = (Node *) malloc (sizeof(Node));

InitNode ( pNode , NULL,NULL, 55 );

AddTailDList( &L1 , pNode ); // добавлен элемент в хфост

DListPrint ( L1 ); // печать списка

Результат:

Добавление в хвост и в голову:

Содержимое списка DList:

Элемент = 3

Элемент = 2

Элемент = 1

Элемент = 55

…

31 Сумма целочисленных переменных списка

Заполним список элементами, как в предыдущем примере, и подсчитаем сумму его целочисленных значений (pTemp->ListVal).

// Динамический списк

DList L1;

// Инициализация списка и его заполнение

InitList( &L1 );

pNode = (Node *) malloc (sizeof(Node));

InitNode ( pNode , NULL,NULL, 1 );

AddDList( &L1 , pNode );

pNode = (Node *) malloc (sizeof(Node));

InitNode ( pNode , NULL,NULL, 2 );

AddDList( &L1 , pNode );

pNode = (Node *) malloc (sizeof(Node));

InitNode ( pNode , NULL,NULL, 3 );

AddDList( &L1 , pNode );

DListPrint ( L1 ); // добавлено всего 3 элемента

// Сумма данных в списке

int Sum;

Sum = 0;

Node * pTemp;

pTemp = L1.Head.pNext;

while ( pTemp != NULL)

{

Sum = Sum + pTemp->ListVal;

pTemp = pTemp->pNext; // Очень важный оператор -- навигация по списку!!!

};

printf ("Результат суммирования в списке: Sum = %d \n\n", Sum);

Навигация по списку выполняется через указатели на следующий элемент списка(pTemp = pTemp->pNext). Проверка завершения цикла выполняется сравнением этого временного указателя с нулевым значением ( pTemp != NULL).

Результат печати списка и суммы его целочисленных элементов:

Содержимое списка DList:

Элемент = 3

Элемент = 2

Элемент = 1

Результат суммирования в списке: Sum = 6

32 Сумма и печать переменных списка с вложенной структурой

Вычисление суммы и печать переменных списка с вложенными структурами.

// Структура для демонстрации

struct Student {

char Name[20];

int Num;

float Oklad;

};

// Для однонаправленного списка с включенными данными

struct SNode {

SNode * pNext;

Student Stud;

};

SNode S3 ={ NULL, {"Сидоров" , 3 , 30.00f}}; // Инициализация структуры при описании

SNode S2 ={ &S3, {"Петров" , 2 , 20.00f}}; // Инициализация структуры при описании

Характеристики

Список файлов книги