ЛАБОРАТОРНАЯ РАБОТА N 7

Операции над списковыми структурами

 

1.Принципы реализации динамических структур данных

 

Линейный список является примером динамической структуры данных, т.е. такой, которая формируется в процессе выполнения программы. Каждый элемент линейной структуры имеет свой порядковый номер в этой структуре, и для каждого элемента, кроме первого, существует предыдущий элемент с номером, на единицу меньшим, и для каждого элемента, кроме последнего, существует последующий элемент с номером, на единицу б’ольшим. Такая линейная упорядоченность в динамической структуре организуется с помощью дополнительного поля, которое, помимо некоторого количества информационных полей, присутствует в каждом элементе списка, и которое содержит указатель, или адрес, следующего элемента линейной структуры. В C-программе описание такой структуры выполняется по схеме:

 

struct listrec{

<тип1> info1; //информационные

. . .

<типn>infon; //поля

listrec *link; //поле указателя

};

Динамический линейный список является примером структуры с последовательным доступом. Он задается указателем (т.е., с использованием вышеприведенных обозначений, - переменной-указателем на данные типа listrec) на первый элемент списка, и для того, чтобы получить доступ к i-ому элементу, необходимо последовательно просмотреть i-1 элементов списка, начиная с первого:

base=first;

for( j=1; j<= i-1; j++)

base=base->link;

Приведенный фрагмент программы подразумевает, что переменные base и first имеют тип: listrec *first, *base ; и в переменной first содержится адрес первого элемента списка. Результатом выполнения фрагмента является значение переменной base - адрес i-го элемента списка.

Формирование элементов динамической структуры выполняется в два действия: отведение памяти для элемента и заполнение отведенной памяти некоторыми значениями. Первое действие выполняется оператором: <указатель>=new <тип>. Результатом его выполнения является выделение из динамической области фрагмента памяти, объем которого определяется типом, указанным после new, а адрес выделенного фрагмента будет помещен в переменную-указатель. Полученное значение, таким образом, следует поместить в поле link предыдущего по отношению к формируемому элемента списка. В поле link последнего элемента списка следует поместить «пустой» адрес, который обозначается зарезервированным словом NULL. Заполнение остальных (информационных) полей элемента списка осуществляется в соответствии с назначением списка в конкретной задаче и алгоритмом ее решения. При этом доступ к полю организуется через указатель на элемент списка, например:

base->info1=<значение типа <тип 1>>;

если base содержит адрес формируемого элемента списка.

Нижеприведенная программа формирует линейный список из последовательности записей текстового файла.

void main()

{

struct list{ //тип элемента списка

char *inf;

list *link;

}

FILE *f;

list *first, *base, *r;

f=fopen(”file.txt”,”r”); //файл с данными для списка

first=new list; //отведение памяти для первого элемента списка

base=first; r=base;

while( !feof(f)) {

base->inf=new char [5]; // заполнение информационного

fgets(base->inf,5,f,); // поля элемента списка

base->link=new list; //отведение памяти для очередного элемента и заполнение //поля указателя предыдущего элемента списка

r=base;

base=base->link; //перемещение текущего указателя на следующий элемент списка

};

delete base; //освобождение напрасно отведенной памяти

 

if (r!=first ) r->link=NULL; else first=NULL; //заполнение поля указателя последнего

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

}

 

2.Задание на лабораторную работу

 

Написать программу построения линейной списковой структуры, содержащей данные символьного типа, а также процедуру, реализующую в соответствии с вариантом задания одну из операций над списковой структурой.

1.Включение в список новой записи после записи с заданным номером k.

2.Удаление из списка записи с заданным номером k.

3.Обмен данными записей с заданными номерами k и l.

4.Включение в список новой записи после записи с заданным значением поля данных.

5.Удаление из списка записи с заданным значением поля данных.

6.Разбиение списка на два списка одинаковой длины (+-1).

7.Изменение порядка следования записей в списке на противоположный.

8.Объединение двух заданных списков в один.

9.Построение копии заданного списка.

10.Преобразование заданного линейного списка в кольцевой с указателем на первую запись, имевшую в линейном списке номер k.