Методичка по лабораторной работе №2 - файл Met_lab2.doc

Методичка по лабораторной работе №2
скачать (21.1 kb.)
Доступные файлы (1):
Met_lab2.doc106kb.19.09.2003 10:23скачать

Met_lab2.doc

  1   2   3



Методические указания к лабораторной работе

“создание списковых структур данных”

по дисциплине “технология программирования”




1 Цель работы


Усвоение студентами рекурсивных процедур программирования на примере создания списков данных.

2 Краткие теоретические сведения


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

Часто динамические структуры физически представляются в форме связных списков. Связный список – такая структура данных, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей, хранящихся в самих элементах списка.
2.1 Односвязный список.
Наиболее простая динамическая информационная структура - это односвязный список, элементами (звеньями) которого служат объекты, например, такого структурного типа:

struct имя_структурного_типа

{

элементы _структуры; /* данные */

struct имя_структурного_типа * указатель;

};

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

Чтобы продемонстрировать некоторые особенности обработки простых динамических информационных структур, разработаем программу, в которой определим структурный тип для представления звеньев односвязного списка и решим такую простейшую задачу: "Ввести с клавиатуры произвольное количество структур, объединяя их в односвязный список, а затем вывести на экран дисплея содержимое введенного списка в порядке формирования его звеньев".

Анализ динамических информационных структур удобнее всего выполнять с помощью их графического изображения. На рисунке 1 приведены схема односвязного списка и обозначения, которые будут использованы в программе. Для работы со списком понадобятся три указателя: beg - на начало списка; end - на последний элемент, уже включенный в список; rex - указатель для "перебора" элементов списка от его начала.

Начало списка

beg











. . .


rex

. . .






end



(Последний элемент списка)


Рисунок 1. Односвязный динамический список.

Содержательные данные списка представляют собой наименование объекта и его вес. Признаком окончания содержательной информации при ее вводе является нулевое значение веса. Следующая программа решает сформулированную задачу.
#include <stdlib.h>

#include <stdio.h>

/* Определение структурного типа "Звено списка":*/

struct cell {

char sign [10];

int weight;

struct cell * pc;

};

void main()

{

/* Указатель для перебора звеньев списка: */

struct cell * rex;

struct cell * beg=NULL; /* Начало списка */

struct cell * end=NULL; /* Конец списка */

printf("\nВведите значения структур:\n");

/* Цикл ввода и формирования списка */

do

{ /* Выделить память для очередного звена списка: */

rex=(struct cell *)malloc(sizeof(struct cell));

/* Ввести значения элементов звена: */

printf("sign=") ;

scanf("%s",& rex->sign) ;

printf("weight=") ;

scanf("%d",& rex->weight);

if (rex->weight = = 0)

{

free(rex) ;

break; /* Выход из цикла ввода списка */

}

/* Включить звено в список: */

if (beg==NULL && end==NULL)

/* Список пуст – включить введенный элемент в список первым*/

beg=rex;

else /* Включить звено в уже существующий список */ ;

end->pc=rex;

end=rex ;

end->pc=NULL ;

}

while(1) ; /* Конец ввода списка */

/* Напечатать список */

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

rex=beg;

while (rex!=NULL)

{

printf("\nsign=%s\tweight=%d",rex->sign,rex->weight) ;

rex=rex->pc;

}

}

Пример выполнения программы:

Введите данные о структурах:

Sign=sigma

weight=16

Sign=omega

weight=44

Sign=alfa

weight=0

Содержимое списка:

Sign=sigma weight=16

Sign=omega weight=44

Обратите внимание, что при вводе данных о третьем элементе списка введено нулевое значение переменной weight и соответствующий элемент в список не включен.

В программе ввод данных, т.е. заполнение односвязного списка структур, выполняется в цикле. Условием окончания цикла служит нулевое значение, введенное для элемента int weight очередной структуры.

Формирование списка структур происходит динамически. Указатели-beg, end инициализированы нулевыми значениями - вначале список пуст.

Обратите внимание на преобразование типов (struct cell *) при выделении памяти для структуры типа struct cell. Функция malloc() независимо от типа параметров всегда возвращает указатель типа void *, а слева от знака присваивания находится указатель rex типа struct cell *. Используется явное приведение типов, хотя это не обязательно - тип void * совместим по операции присваивания с указателем на объект любого типа.

Остальные особенности программы поясняются комментариями в ее тексте.
2.2.Рекурсия при обработке односвязного списка.
Даже такая простая структура, как динамический односвязный список, представляет собой конструкцию вложенных списков, как показано на рисунке 2. На нем собственно данные или содержательные элементы обозначены D, а связи между записями или указатели обозначены L.





список

список


список


список


. . .


Рисунок 2 Рекурсивное представление односвязного списка
Вложенные структуры удобно обрабатывать с помощью рекурсивных процедур. Рассмотрим ту же задачу об односвязном списке, но оформим формирование списка и вывод списка на экран дисплея в виде рекурсивных функций. Сделаем это с целью показать на этом простом примере особенности рекурсивной обработки динамических информационных структур.

В каждом звене списка содержатся полезная информация (данные) и ссылка (адрес) на следующее звено списка. Если такая ссылка нулевая, то список пройден до конца. Для начала просмотра списка нужно знать только адрес его первого элемента.

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

Функция рекурсивного заполнения списка ниже в программе имеет прототип:

struct cell * input (void) ;

Она возвращает указатель на сформированный динамический список, заполненный вводимыми с клавиатуры дисплея данными. Предполагается, что при каждом вызове этой функции формируется новый список. Функция заканчивает работу, если для очередного звена списка введено нулевое значение переменной weight. В противном случае заполненная с клавиатуры структура подключается к списку, а ее элементу struct cell *рс присваивается значение, которое вернет функция input(), рекурсивно вызванная из тела функции. После этого функция возвращает адрес очередного звена списка, т.е. значение указателя struct cell * рс.

Прежде чем рассматривать текст функции input( ), помещенный в приведенной ниже программе, еще раз сформулируем использованные в ней конструктивные решения.

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

2. Выделение памяти для звеньев списка и заполнение значениями элементов звеньев (структур) зависит от тех значений, которые пользователь присваивает элементам.

3. Если для очередного звена списка вводится нулевое значение элемента weight, то звено не подключается к списку, процесс формирования списка заканчивается. Такой набор данных, введенных для элемента очередного звена, считается терминальным.

4. Если нулевое значение элемента weight введено для первого звена списка, то функция input( ) возвращает значение NULL.

5. Список определяется рекурсивно как первое (головное) звено, за которым следует присоединяемый к нему список.

6. Псевдокод рекурсивного алгоритма формирования списка:

Если введены терминальные данные для звена

Освободить память, выделенную для звена

Вернуть нулевой указатель

Иначе:

Элементу связи звена присвоить результат формирования продолжения списка (использовать тот же алгоритм)
  1   2   3


Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации