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

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

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

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

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

};

Тогда, в соответствии с описаниями предыдущего примера можно описать сданный список так:

//Описание и нициализация простого списка

EList FirstList = { &LE1 , &LE3 , 3}; // 3 - Число элементов в списке

// Печать этого списка

printf ("Печать списка FirstList в цикле: \n" );

pETemp = FirstList.pHead; // Во временную переменную - указатель задаем адрес головы спика

while ( pETemp != NULL) // Проверка прохождения последнего элемента списка

{

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

pETemp = pETemp->pNext; // НАВИГАЦИЯ: Важнейщий оператор для работы со списком

};

Результат распечатки такого списка:

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

Элемент простого списка FirstList: 1

Элемент простого списка FirstList: 2

Элемент простого списка FirstList: 3

Важно в дополнение отметить следующее. Данный список является однонаправленным: движение по списку возможно только в одном направлении – от головы к хвосту, так заданы указатели. У последнего элемента списка (хвоста списка), по стандартному соглашению, указатель-адрес задается равным нулю (0, NULL – константа этапа компиляции). Это позволяет проверить завершение цикла печати. В другом случае завершение цикла можно было бы проверить, используя адрес хвоста списка (pTail), сравнив его с адресом текущего элемента для печати. Особое внимание уделим выделенной красным цветом строчке с комментарием НАВИГАЦИЯ. В этом операторе присваивания мы с помощью одного указателя (pETemp) на текущий элемент списка формируется указатель на следующий элемент списка (pETemp->pNext), результат запоминается в первом указателе (pETemp). Такой оператор обеспечивает навигацию по списку. Он будет многократно встречаться в наших примерах.

pETemp = pETemp->pNext;

9 Структура элемента списка с вложенными и внешними данными

Выше было отмечено, что информация в элементах списка может храниться разными способами:

• Данные записываются в самой структуре элемента в виде отдельных переменных

• Данные записываются в самой структуре элемента в виде структурной переменной

• Данные записываются в структуре элемента в виде указателя на структурную переменную, память под которую выделяется динамически.

Н
а рисунке, представленном ниже, показаны эти варианты.

Примерами вариантов таких структур могут служить следующие:

// Структура типа (а)

struct aElem{

aElem * pNext; // адрес следующего элемента списка

char Name[20]; // информация фамилии, содержащаяся в списке

int Num; // информация о номере - курсе, содержащаяся в списке

float Oklad; // информация об окладе, содержащаяся в списке

};

// Структура типа (b)

struct bElem{

bElem * pNext; // адрес следующего элемента списка

Student Stud; // Структура Student включенная в элемент списка

};

// Структура типа (c)

struct cElem{

cElem * pNext; // адрес следующего элемента списка

Student * pStud; // Указатель на структуру типа Student

};

10 Однонаправленные и двунаправленные списки

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

struct DElem{

DElem * pNext; // адрес следующего элемента списка (Заметьте, указатель имеет тип (Elem *))

DElem * pPrev; // адрес ghtlsleotuj элемента списка (Заметьте, указатель имеет тип (Elem *))

int ListVal; // информация, содержащаяся в списке

};

При этом соглашения для нулевого (NULL) последнего элемента списка (для pNext) и первого (для pPrev) справедливы. Для единственного элемента списка (он и первый и последний одновременно) справедлива такая инициализация двунаправленного элемента:

DElem D1 = {NULL,NULL, 5}; // Оба адреса-указателя равны нулю

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

11 Статические и динамические списки

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

Для динамических списков память под элементы, а, возможно, и под списковую структуру выделяется во время выполнения программы с помощью запросов к ОС (функции malloc, calloc и др.). После завершения работы выделенная память должна быть возвращена (функция free). Пусть для примера мы имеем такую структуру списка и его элементов

// Самый простой элемент списка

struct ListElem{

ListElem * pNext; // адрес следующего элемента списка

int ListVal; // информация, содержащаяся в списке

};

// Структура простого списка

struct List {

ListElem Head; // Голова списка стуктурная переменная а не указатель

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

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

};

…

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

#include <malloc.h>

…

// ДИНАМИЧЕСКИЕ СПИСКИ

//Выделение памяти для списка

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

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

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

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

pTempElem->pNext = NULL; // Всего один элемент

pTempElem->ListVal = 5;

// Занесение элемннгта списка в голову списка

pDList->Head.pNext = pTempElem;

pDList->Tail.pNext = pTempElem;

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

printf ("Значение элемента: %d \n", pDList->Head.pNext->ListVal);

// Освобождение памяти и под элемент и список

free (pDList->Head.pNext);

free (pDList);

Результат работы этой программы:

Значение элемента: 5

Здесь для иллюстрации показано добавление только одного элемента списка. В других при мерах мы рассмотрим списки с большим числом элементов.

12 Операции для работы со списком

Основные общие операции для работы со списками:

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

• Добавление нового элемента в список (в голову, в хвост и по номеру)

• Удаление элемента из списка (из головы, с хвоста и по номеру)

• Очистка всего списка

• Распечатка всего списка

• Замена местами элементов по номерам

Эти операции будут различаться для однонаправленных и двунаправленных списков, для динамических и статических списков, а также для списков, в которых учтена специфика хранимых объектов. В основной теоретической части мы будем рассматривать примеры работы с списками. Удаление элементов по номеру операция очень сложная для однонаправленных списков, поэтому в этой части не рассматривается.

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

Рассмотрим основные операции для работы с однонаправленным списком. Будем использовать следующую структуру элемента:

struct ListElem{

ListElem * pNext; // адрес следующего элемента списка

int ListVal; // информация, содержащаяся в списке

};

…

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

// Ручное связывание и распечатка списка

ListElem E11;

ListElem E21;

ListElem E31;

E11.ListVal = 1; // Значение информации 1-го элемента

E11.pNext = &E21;// Ссылается на 2-й элемент

E21.ListVal = 2; // Значение информации 2-го элемента

E21.pNext = &E31; // Ссылается на 3-й элемент

E31.ListVal = 3; // Значение информации 3-го элемента

E31.pNext = NULL; // не ссылается ни на кого

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

ListElem ETemp = {&E11 ,NULL }; // Временный элемент для навигации

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

while (ETemp.pNext != NULL )

{

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

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

};

…

Результат работы программы:

Содержимое ручного списка:

Элемент = 1

Элемент = 2

Элемент = 3

14 Добавление в голову списка

Для добавления элемента в голову списка объявим структурную переменную список (MY_List типа List) и вручную запомним значения для головы и хвоста списка.

struct ListElem{

ListElem * pNext; // адрес следующего элемента списка

int ListVal; // информация, содержащаяся в списке

};

s
truct List {

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

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

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

};

// Описание и инициализация простого списка

List MY_List;

MY_List.Head.pNext = &E11; // Первый элемент списка

MY_List.Tail.pNext = &E31; // Последний элемент списка

// Новый элемент для добавления

ListElem ENew = {NULL , 5};

// Добавить элемент списка в голову

ENew.pNext = MY_List.Head.pNext;

MY_List.Head.pNext = &ENew;

MY_List. Count++;

Распечатка списка после добавления:

ETemp.pNext = MY_List.Head.pNext; // Временный элемент на начало списка

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

while (ETemp.pNext != NULL )

{

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

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

};

Результат распечатки:

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

Элемент = 5

Элемент = 1

Элемент = 2

Элемент = 3

15 Добавление в конец списка (в хвост)

П
ри добавлении в конец (в хвост) списка для изменения адреса используется значение указателя, которое записано в поле Tail.pNext структуры список. Адрес нового элемента (&ENew2) записывается поле адреса предыдущего последнего элемента списка и поле хвоста (Tail) структуры списка. Адресное поле нового элемента должно быть нулевым, в нашем случае мы использовали инициализацию эдемента.

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

ListElem ENew2 = {NULL , 10};

ENew2.pNext = NULL;

MY_List.Tail.pNext->pNext = &ENew2;

MY_List.Tail.pNext = &ENew2;

MY_List. Count++;

// Распечатка списка … (как в предудущем случае)

Результат распечатки:

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

Элемент = 5

Элемент = 1

Элемент = 2

Элемент = 3

Элемент = 10

16 Функция распечатки однонаправленного списка

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

// Распечатка списка, построенного на элементах ListElem

void PrintElemList ( ListElem H )

{

printf ("Печать списка: \n");

ListElem * pE = H.pNext ;

while ( pE != 0)

{

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

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

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