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

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

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

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

};

};

Сначала печатается заголовок печати, а затем последовательно распечатываются все элементы списка, для перебора элементов списка используется оператор навигации, а для проверки конца цикла значение текущего адреса (указатель - PE). Вызов этой функции через структуру список (List - MY_List) выглядит так (полученный адрес первого элемента списка преобразуется в сам элемент с помощью операции разыменования):

…

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

…

Такая запись эквивалентно следующей записи для нашего примера:

PrintElemList ( E11 );

…

Результат вывода:

Печать списка:

Элемент = 1

Элемент = 2

Элемент = 3

17 Удаление из головы списка

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

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

// Удаление из головы списка

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

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

MY_List.Head.pNext = MY_List.Head.pNext->pNext;

MY_List. Count--;

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

PrintElemList ( *(MY_List.Head.pNext) ); // Вызов функции печати списка

Результат вывода:

Содержимое списка до удаления из головы:

Печать списка:

Элемент = 5

Элемент = 1

Элемент = 2

Элемент = 3

Элемент = 10

Содержимое списка после удаления из головы:

Печать списка:

Элемент = 1

Элемент = 2

Элемент = 3

Элемент = 10

18 Удаление из хвоста списка

У
даление с хвоста списка для однонаправленного списка намного сложнее, так как адрес предпоследнего элемента с хвоста неизвестен. В этом случае первоначально определяется адрес этого элемента: нужно “добежать” до хвоста, запомнив предварительно адрес предыдущего элемента (pPrevTemp), а затем выполнить операцию удаления (изменить адрес хвоста списка и обнулив адрес у найденного предпоследнего элемента).

// Удаление с хвоста списка

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

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

// Поиск предпоследнего элемента списка!!!!!!(в pPrevT)

ListElem * pPrevT = MY_List.Head.pNext;

// ETemp.pNext = MY_List.Head.pNext; // временный указатель для цикла

ListElem * pPrevTemp = MY_List.Head.pNext; // временный указатель для предыдущего элемента

if ( pPrevT != NULL ) // Элементы в списке есть

{

while ( pPrevT != NULL)

{

pPrevTemp = pPrevT; // Запоминание предыдущего элемента

pPrevT = pPrevT ->pNext ; // Навигация

if (pPrevT->pNext == NULL ) break;

}

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

MY_List.Tail.pNext = pPrevTemp;

pPrevTemp->pNext = NULL;

MY_List. Count--;

// Печать измененного списка списка

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

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

};

…

Результат вывода:

Содержимое списка до удаления с хвоста:

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

Элемент = 1

Элемент = 2

Элемент = 3

Элемент = 10

Содержимое списка после удаления с хвоста:

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

Элемент = 1

Элемент = 2

Элемент = 3

Примечание 1: Рассмотрены основные операции добавления и удаления элементов в/из списков. К сожалению, они в таком виде применимы только для частных случаев, так как обычно текущее состояние списка заранее неизвестно. В окончательном виде при добавлении и удалении необходимо учитывать следующие факторы: текущее состояние списка (пуст ли он?), каким он будет после выполнения операции, как нужно установить основные поля структуры списка после завершения операции. В разделе примеров данных МУ представлены функции более универсального характера для выполнения этих операций.

19 Очистка статического списка

Для очистки статического списка, все элементы которого являются также статическими (описаны в программе) достаточно установить указатели головы и хвоста в нуль, при построении списка с полями в виде элементов списка:

struct List {

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

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

int Count; // Счетчик элементов

};

…

MY_List.Head.pNext = NULL;

MY_List.Tail.pNext = NULL;

Если список организован по-другому, для головы и хвоста используются указатели на элементы списка, то очистка списка будет выглядеть иначе:

struct PList {

ListElem * pHead; // Голова списка

ListElem * pTail; // Хвост списка

int Count; // Счетчик элементов

};

…

MY_List. pHead = NULL;

MY_List. pTail = NULL;

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

20 Простая ручная работа с динамическим списком

Перед каждым фрагментом программы дано пояснение сути действий. Для работы используются: структура однонаправленного списка (List) и элемента списка(ListElem). Для работы используется библиотека (<malloc.h>). Красным цветом выделены операции навигации по списку и операция работы со списклм.

Создание динамического списка:

// Динамический список - пока только ручная работа

////Создание динамического списка

List * pList = (List *) malloc ( sizeof(List));

// Начальная инициализация списка

pList->Count = 0;

pList->Head.pNext = NULL;

pList->Tail.pNext = NULL;

Создание элементов списка и связывание списка (три элемента):

////Создание и добавление элементов

ListElem *pDETemp;

// 1 = й

pDETemp = (ListElem *) malloc ( sizeof(ListElem));

pDETemp->pNext = NULL;

pDETemp->ListVal = 1 ;

pList->Count = 1;

pList->Head.pNext = pDETemp; // Добавить первый

pList->Tail.pNext = pDETemp;

// 2 - й в голову

pDETemp = (ListElem *) malloc ( sizeof(ListElem));

pDETemp->ListVal = 2 ;

pDETemp->pNext = pList->Head.pNext;// Добавить второй в голову

pList->Head.pNext = pDETemp;

// 3 - й в хвост

pDETemp = (ListElem *) malloc ( sizeof(ListElem));

pDETemp->ListVal = 3 ;

pDETemp->pNext = NULL ;

pList->Tail.pNext->pNext = pDETemp;

pList->Tail.pNext = pDETemp;// Добавить третий в хвост

////Печать списка

PrintElemList ( *(pList->Head.pNext) );

Удаление ч головы списка:

////Удаление с головы

pDETemp = pList->Head.pNext ; // Запомним для очистки памяти

pList->Head.pNext = pList->Head.pNext->pNext;

free( pDETemp ); // Очистить память

Удаление с хвоста списка:

////Удаления с хвоста

pDETemp = pList->Tail.pNext ; // Запомним для очистки памяти

// Поиск предпоследнего для укорочения списка

ListElem * pFind = pList->Head.pNext ;

while( pFind != NULL)

{

if ( pFind ->pNext->pNext == NULL) break;

pFind = pFind->pNext;

};

pFind->pNext = NULL; // Укоротить список

free( pDETemp ); // Очистить память

//

printf ("Печать после удаления с головы и хвоста: \n");

PrintElemList ( *(pList->Head.pNext) );

Цикл занесения динамических элементов в список:

// Цикл динамического заполнения списка в голову (5 элементов)

for ( int i = 0 ; i< 3 ; i++ )

{

pDETemp = (ListElem *) malloc ( sizeof(ListElem));

pDETemp->ListVal = i + 10;

pDETemp->pNext = pList->Head.pNext;// Добавить текущий элемент в голову

pList->Head.pNext = pDETemp;

};

Печать списка в цикле:

// Печать списка

pDETemp = pList->Head.pNext;

printf ("Печать списка после динамического добавления: \n");

while( pDETemp != NULL)

{

printf ("Элемент списка: - %d \n" , pDETemp->ListVal );

pDETemp = pDETemp->pNext; // Навигация

};

Очистка динамического списка (в цикле удаляем все элементы – pTemp, а затем структуру списка pList, созданного динамически выше )

////Очистка динамического спиcка (с головы?)

pDETemp = pList->Head.pNext;

k=1;

while( pDETemp != NULL)

{

ListElem * pTemp = pDETemp;

pDETemp = pDETemp->pNext; // Навигация

free (pTemp);

};

free (pList);

…

Работы программы для динамических списков:

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

Элемент = 2

Элемент = 1

Элемент = 3

Печать после удаления с головы и хвоста:

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

Элемент = 1

Печать списка после динамического добавления:

Элемент списка: - 12

Элемент списка: - 11

Элемент списка: - 10

Элемент списка: - 1

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

21 Простая ручная работа с двунаправленным списком

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

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

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

struct Student {

char Name[20];

int Num;

float Oklad;

};

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

struct DElem {

DElem * pNext;

DElem * pPrev;

Student * pSTud;

};

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

struct DoubleList {

DElem * pHead; // Голова списка - указатель

DElem * pTail; // Хвост списка - указатель

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

};

Инициализация и заполнение списка (DoubleList) статическими элементами списка (DElem):

// Список

DoubleList My_DList;

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

My_DList.Count = 0;

My_DList.pHead = NULL;

My_DList.pTail = NULL;

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

DElem D1 = { NULL , NULL , NULL};

D1.pSTud = (Student *) malloc ( sizeof(Student));

D1.pSTud->Num = 1;

D1.pSTud->Oklad = 10.0f;

strcpy( D1.pSTud->Name,"Петров");

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

DElem D2 = { NULL , NULL , NULL};

D2.pSTud = (Student *) malloc ( sizeof(Student));

D2.pSTud->Num = 2;

D2.pSTud->Oklad = 20.0f;

strcpy( D2.pSTud->Name,"Сидоров");

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

DElem D3 = { NULL , NULL , NULL};

D3.pSTud = (Student *) malloc ( sizeof(Student));

D3.pSTud->Num = 3;

D3.pSTud->Oklad = 30.0f;

strcpy( D3.pSTud->Name,"Иванов");

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

My_DList.pHead = &D1;

My_DList.pTail = &D3;

// Прямая адресация

D1.pNext = &D2; // Текущий (первый) ссылается на следующий (второй) …

D2.pNext = &D3;

D3.pNext = NULL;

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

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