Операции над списковыми структурами
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.