ЛАБОРАТОРНАЯ РАБОТА № 9. Динамические структуры данных

Цель работы: научиться использовать динамические структуры данных при создании программного обеспечения.

Лабораторная работа рассчитана на 4 академических часа.

Теоретическая часть. Статические и динамические данные

При написании программ необходимо постоянно использовать переменные для хранения данных. При обычном объявлении переменной целочисленного массива на языке С++ (здесь и далее в качестве языка выбран С++, но аналогичные структуры данных есть и в других языках высокого уровня):

1шаг;

на этапе компиляции программы происходит автоматическое резервирование памяти под эту переменную (рис Л9.1, а). Это имеет ряд серьезных недостатков:

· • невозможность вернуть компьютеру неиспользуемую память. Например, большой массив будет использоваться только один раз, а память нельзя освободить до окончания работы программы;

· • захват памяти, которая вообще может не использоваться программой. Эта ситуация, к сожалению, также не редкость. Зачастую трудно заранее определить размер массива, который понадобится для работы, и под него отводят память «с запасом».

Для решения описанных проблем используются динамические структуры данных. С помощью этого типа данных необходимую память можно выделять в ходе программы и возвращать компьютеру, когда она становится ненужной для работы. Например:

float *a;

a=new float; &a=7.89; delete(a);

//Объявляем указатель на переменную а //(переменная, в которой хранится //адрес ячейки данных)

//Выделяем память под переменную //Присваиваем значение переменной //Удаляем переменную и возвращаем память

А23В:0004

Рис. Л9.1. Распределение памяти при объявлении: а — статических переменных; б — динамических переменных

Указатель — адрес ячейки памяти. При использовании оператора new компьютер выделяет необходимую память, и адрес этой ячейки памяти записывается в переменную-«указатель» (в примере — это переменная а).

Создание списка

Список — последовательность ячеек памяти, хранящих элементы массива данных. Каждая ячейка такого списка состоит как минимум из двух частей: в первой хранится элемент массива, во второй — указатель на следующую такую же ячейку памяти (рис. Л9.2).

Рис. Л9.2. Пример динамического списка

Ниже приводится код программы для работы со списком на языке C++. Используя его, познакомимся с технологией создания списка.

Для работы со списками, как говорилось выше, используется структура, состоящая как минимум из двух элементов:

struct spisok

{

int elem; //Данные

spisok *next; //Указатель, адрес следующего

элемента };

В отличие от простого объявления переменной, для динамических данных добавляется значение «звездочка» (оно означает, что это адрес памяти, где расположен элемент, но не он сам). Чтобы в ходе программы получить значение элемента по известному адресу или, наоборот, присвоить значение, используется знак & (&а=56).

1. Далее в программе следует строка:

spisok *1;

Это адрес первого элемента списка. Его необходимо знать всегда.

2. Рассмотрим построчно процедуру создания списка (для объяснения строки пронумерованы):

void FormSpisok()

{

· (1) spisok *m,*k;

· (2) int i;

· (3) randomize ();

· (4) k=new spisok;

· (5) k->elem=random(5);

· (6) l=k;

· (7) for (i=l;i<10;i++)

{

· (8) m=new spisok;

· (9) m->elem=random(5);

· (10) k->next=m;

· (11) k=m;

}

(12) k->next=NULL;

}

В строках (1) и (2) объявляются служебные переменные. Строка (3) — инициализация генератора случайных чисел для последующего присвоения произвольных значений элементам списка.

(4) k=new spisok; Выделяется ячейка память для переменной типа «список», и ее адрес сохраняется в переменной к:

(5) k->elem=random(5); Присваивается значение элементу списка:

(6) 1=к ; Указатель на первый элемент списка запоминается в переменной /:

· (7) for (i=l;i<10;i++). Для создания списка из 10 элементов используется цикл.

· (8) m=new spisok; Выделяется еще один участок памяти под переменную spisok. Адрес памяти запоминается в переменную т:

к 1

(9) m->elem=random(5); Заносим значение в переменную:

(10) k->next=m; Связываем существующие две ячейки:

к 1

(11) к=т; Для создания остальных элементов меняем значение указателя к, как показано на рисунке:

Далее действия повторяются в цикле

(12) k->next=NULL; Для задания значения «последующий» для последнего элемента используется значение NULL.

Пример программы по работе со списками на языке C++

#include

struct spisok

{

int elem; spisok *next;

};

spisok *1;

//Процедура создания списка void FormSpisok()

{

spisok *m,*k; int i;

randomize();

k=new spisok; k->elem=random(5); l=k;

for (i=l;i<10;i++)

{

m=new spisok; m->elem=random(5) ; k->next=m; k=nn;

}

k->next=NULL;

}

void vivodSpisok()

{

spisok *m; m=l;

while (m!=NULL)

{

cout<elem<<' ';

m=m->next;

}

void VstavkaO

{

spisok *m,*k,*r; int i,a,s; m=l;

COUt<<endl<<"bbeflhte позицию,="" после="" которой="" нужно="" вставить="" новый="" элемент:="" cin="">>a;</endl<<"bbeflhte>

сои1:<<"Введите значение элемента: cin>>s;

for (i=l;inext;

k=new spisok;

k->elem=s;

r=m->next;

m->next=k;

k->next=r;

}

void Del()

{

spisok *m,*k,*r; int i,a;

cout<<endl<<"vvedite posiciju:="" cin="">>a;</endl<<"vvedite>

if (a==0)

{

m=l ;

l=l->next; delete(m);

}

else

{

m=l;

for(i=l;inext; //Поиск позиции

// удаления

k=m->next; r=k->next;

m->next=r; delete(k);

void main()

{

clrscr();

FormSpisok() ; vivodSpisok() ;

Vstavka (); vivodSpisok ();

Del () ;

vivodSpisok(); getch () ;

}

Пример программы на Delphi по работе со списками

unit Unitl;

interface

uses

Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,

StdCtrls, Buttons;

type

TForml = class(TForm)

Buttonl: TButton;

Button2: TButton;

Button3: TButton;

Button4: TButton; vivod: TEdit;

BitBtnl: TBitBtn;

Labell: TLabel;

Edit2: TEdit;

Label2: TLabel;

Edit3: TEdit;

Label3: TLabel;

Editl: TEdit;

procedure ButtonlClick(Sender: TObject); procedure Button2Click(Sender: TObject); procedure Button3Click(Sender: TObject); procedure Button4Click(Sender: TObject); private

{ Private declarations } public

{ Public declarations } end;

var

Forml: TForml;

implementation

{$R *.DFM} const n=10; type spisok=^Azveno; zveno = record elem:integer; next:spisok; end;

var 1:spisok;

procedure TForml.ButtonlClick(Sender: TObject); var m,k:spisok;

i:integer; begin randomize;

new(k);

к^л.elem:=random(5);

1: =k;

for i:=l to n-1 do begin new(m);

т^л.elem:=random(5); к^л.next:=m; к: =m ; end;

к^л.next:=nil;

end;

procedure TForml.Button2Click(Sender: TObject); var m:spisok;

str:string[100] ; begin

str:=''; //Добавил

m:=l;

while monil do begin

str:=str+IntToStr(т^Л.elem)+' ';

// write(т^л.elem,' ');

m:=т^л.next;

end;

vivod.Text:=str;

end;

procedure TForml.Button3Click(Sender: TObject); var m,k,r:spisok;

i:integer; begin m:=l;

for i:=l to StrToInt(Edit3.Text)-1 do m:=m^A.next; //Поиск позиции вставки

new(k);

к^л.elem:=StrToInt(Edit2.Text); //Создали элемент

г:=т^Л.next; т^Л.next:=к; к^Л.next:=r;

end;

procedure TForml.Button4Click(Sender: TObject); var m,k,r:spisok;

i:integer; begin

if Editl.Text='0' then begin m:=l;

1:=1^л.next; dispose(m); end

else begin m:=l;

for i:=l to StrToInt(Editl.Text)-1 do m;=m^A.next; //Поиск позиции удаления к:=т^Л.next; г:=к^л.next;

т^л.next:=г; dispose(к); end;

end;

end.

Порядок выполнения работы

· 1. В соответствии с вариантом задания написать программу обработки списка на языке С++ или Delphi.

· 2. Отладить программу.

· 3. Получить результат.

· 4. Показать текст программы и результат ее работы преподавателю.

· 5. Сдать и защитить работу.

Защита отчета по лабораторной работе

Отчет по лабораторной работе должен состоять из:

· 1. Постановки задачи.

· 2. Блок-схемы программы.

· 3. Текста программы на языке программирования.

· 4. Результатов.

Защита отчета по лабораторной работе заключается в предъявлении преподавателю полученных результатов (на экране монитора), демонстрации полученных навыков и ответах на вопросы преподавателя.

Контрольные вопросы

· 1. Приведите классификацию данных.

· 2. Что такое простые типы данных?

· 3. Что такое статические и полустатические структуры данных?

· 4. Какие существуют динамические структуры данных?

· 5. Как осуществляется размещение переменных в памяти компьютера?

Варианты задания

· 1. Создать список. Поменять местами максимальный и минимальный элементы.

· 2. Создать список. Удалить из него повторяющиеся элементы.

· 3. Создать два списка. Создать 3-й список, состоящий из элементов, которые есть как в первом, так и во втором списке.

· 4. Создать два списка. Создать 3-й список, объединяющий первый и второй списки. Удалить максимальный элемент в новом списке.

· 5. Создать список и отсортировать его по убыванию.

· 6. Создать два списка одинаковой длины. Произвести поэлементное вычитание из первого списка элементов второго списка.

· 7. Создать два списка. Создать 3-й список, состоящий из неповторяющихся элементов первых двух списков.

· 8. Создать список. Вставить в него после максимального элемента копию минимального элемента.

· 9. Создать список. После каждого отрицательного элемента вставить элемент, равный 0.

· 10. Создать список. Посчитать сумму всех элементов. Полученный результат вставить после минимального элемента списка.

· 11. Создать список. Удалить из него все отрицательные элементы.

· 12. Создать два списка. Создать 3-й список, состоящий из положительных элементов двух первых списков.

Дата добавления: 2020-04-08; просмотров: 216; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 4 567 8 9 Следующая ⇒

Мы поможем в написании ваших работ!