Реферат Курсовая Конспект
ЛАБОРАТОРНАЯ РАБОТА N 7 - раздел Программирование, Программирование алгоритмов сортировки массивов Операции Над Списковыми Структурами 1.принципы Реали...
|
Операции над списковыми структурами
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.
– Конец работы –
Эта тема принадлежит разделу:
Государственное образовательное учреждение... Высшего профессионального образования... Санкт Петербургский государственный университет...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ЛАБОРАТОРНАЯ РАБОТА N 7
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов