Структуры данных в динамической памяти и разработка программного комплекса 'Улицы города'

Структуры данных в динамической памяти и разработка программного комплекса 'Улицы города'

Введение

В результате постоянного развития нашего общества увеличивается сложность задач, которые приходится решать человеку в процессе своей трудовой деятельности.

Современные вычислительные машины представляют одно из самых значительных достижений человеческой мысли, влияние, которого на развитие научно-технического прогресса трудно переоценить. Области применения ЭВМ непрерывно расширяются. Программное обеспечение для ЭВМ становится все более совершенным и в большей мере позволяет автоматизировать труд человека. Эти программы охватывают все отрасли человеческой деятельности, где, по мнению разработчиков, они могут принести пользу, повысив производительность труда и снизив при этом затраты рабочего времени.

Современное общество предъявляет высокие требования к принципам хранения информации.

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

Предметом курсовой работы является изложение материала на тему «Структуры данных в динамической памяти» и разработка программного комплекса «Улицы города».

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

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

Структуры данных в динамической памяти. Однонаправленные списки

Динамические структуры данных

При динамическом выделении памяти, память под величины отводится во время выполнения программы. Такие величины называются динамическими. Динамически распределяемый раздел памяти называется динамической памятью (динамически распределяемой памятью) [1].

Использование динамических величин предоставляет программисту ряд дополнительных возможностей:

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

если потребность в каких-то данных отпала до окончания программы, то занятую ими память можно освободить для другой информации;

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

Работа с динамическими величинами связана с использованием еще одного типа данных - ссылочного типа. Величины, имеющие ссылочный тип, называют указателями.

Указатель содержит адрес поля в динамической памяти, хранящего величину определенного типа. Сам указатель располагается в статической памяти.

Адрес величины - это номер первого байта поля памяти, в котором располагается величина. Размер поля однозначно определяется типом.

Величина ссылочного типа (указатель) описывается в разделе описания переменных следующим образом:<идентификатор> : ^<имя типа>;

Примеры описания указателей:

Type= array [1..100] of TStreet;: ^Integer;: ^String;

streetList: ^TStreetList;

Здесь kolStreet - указатель на динамическую величину целого типа; nameFile - указатель на динамическую величину строкового типа; streetList - указатель на динамический массив, тип которого задан в разделе Type.

Сами динамические величины не требуют описания в программе, поскольку во время компиляции память под них не выделяется. Во время компиляции память выделяется только под статические величины. Указатели - это статические величины, поэтому они требуют описания [2].

Память под динамическую величину, связанную с указателем, выделяется в результате выполнения стандартной процедуры NEW. Формат обращения к этой процедуре:(<указатель>);

Считается, что после выполнения этого оператора создана динамическая величина, имя которой имеет следующий вид:

<имя динамической величины> := <указатель>^

Пусть в программе, в которой имеется приведенное выше описание, присутствуют следующие операторы:

NEW(kolStreet); NEW(nameFile); NEW(streetList);

После их выполнения в динамической памяти оказывается выделенным место под три величины (две скалярные и один массив), которые имеют идентификаторы:^, nameFile^, streetList^

Например, обозначение kolStreet^ можно расшифровать так: динамическая переменная, на которую ссылается указатель kolStreet.

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

Кроме процедуры NEW значение указателя может определяться оператором присваивания:

<указатель> := <ссылочное выражение>;

В качестве ссылочного выражения можно использовать

указатель;

ссылочную функцию (т.е. функцию, значением которой является указатель);

константу Nil. - это зарезервированная константа, обозначающая пустую ссылку, т.е. ссылку, которая ни на что не указывает. При присваивании базовые типы указателя и ссылочного выражения должны быть одинаковы. Константу Nil можно присваивать указателю с любым базовым типом.

До присваивания значения ссылочной переменной (с помощью оператора присваивания или процедуры NEW) она является неопределенной.

В Паскале имеется стандартная процедура, позволяющая освобождать память от данных, потребность в которых отпала. Ее формат:(<указатель>);

Например, если динамическая переменная nameFile^ больше не нужна, то оператор(nameFile);

удалит ее из памяти. После этого значение указателя nameFile становится неопределенным. Особенно существенным становится эффект экономии памяти при удалении больших массивов.

В версиях Турбо-Паскаля, работающих под операционной системой MS DOS, под данные одной программы выделяется 64 килобайта памяти (или, если быть точнее, 65520 байт). Это и есть статическая область памяти. При необходимости работать с большими массивами информации этого может оказаться мало. Размер динамической памяти - много больше (сотни килобайт). Поэтому использование динамической памяти позволяет существенно увеличить объем обрабатываемой информации [4].

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

Однонаправленные списки

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

Рисунок 1.1 - Пример списковой структуры

где Di - данные. Чтобы получить доступ к данным, достаточно хранить в памяти адрес начала этого списка nach.

В Паскале существует основное правило: перед использованием какого-либо объекта он должен быть описан. Исключение сделано лишь для указателей, которые могут ссылаться на еще не объявленный тип [3].

Type= ^TStreet;= record: real;: string;: integer;: TTip;

Next: ukazat;;

Чтобы список существовал, надо определить указатель на его начало.

Создадим первый элемент списка:(street); {выделяем место в памяти}

street^. Next:= nil; {указатель пуст}^. dlina:=30;

…

Продолжим формирование списка. Для этого нужно добавить элемент либо в конец списка, либо в голову.

Для добавления элемента в “голову” списка необходимо выполнить последовательность действий:

получить память для нового элемента;

поместить туда информацию;

присоединить элемент к голове списка.

New(newStreet); ^.naim:=’Chehova’;

… ^. Next:= street; := newStreet;

Для добавления элемента в конец списка необходимо ввести вспомогательную переменную, которая будет хранить адрес последнего элемента. Пусть это будет указатель с именем hv (хвост). Организация процедуры представлена на рисунке 1.2.:= hv;

Рисунок 1.2 - Организация формирования списка

Выделение памяти для следующего элемента, рисунок 1.3.(newStreet^.next); {выделяем память для следующего элемента}

newStreet:= newStreet^.next; ^.next:= nil;

newStreet^. dlina:= 5;

… :=newStreet;

Рисунок 1.3 - Выделение памяти для следующего элемента

Просмотр списка:street<> nil do

Writeln (street^.inf);

street:= street^.next;>

end;

Удаление элемента из списка:

удаление первого элемента. Для этого во вспомогательном указателе запомним первый элемент, указатель на голову списка переключим на следующий элемент списка и освободим область динамической памяти, на которую указывает вспомогательный указатель. Процедура удаления первого элемента изображена на рисунке 1.4.:= street; := street^.next; (delStreet);

Рисунок 1.4 - Удаление первого элемента

удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, стоящего перед ним, что изображено на рисунке 1.5. Допустим, что delStreet - это длина удаляемой улицы.:= street; (newStreet<>nil) and (newStreet^.dlina <> delStreet) do

dx:= newStreet;

newStreet:= newStreet^.next; ; := newStreet^.next: (newStreet);

Рисунок 1.5 - Удаление элемента из середины списка

удаление из конца списка. Для этого нужно найти предпоследний элемент.

newStreet:= street; := street; newStreet^.next<> nil do

dx:= newStreet;:= newStreet^.next; ; ^.next:= nil; (newStreet);

Прохождение списка. Важно уметь перебирать элементы списка, выполняя над ними какую-либо операцию. Пусть необходимо найти сумму длин улиц.:= 0; := street; newStreet<> nil do

summa:= summa+ newStreet^.dlina;

newStreet:= newStreet^.next;

end;

Описание программного комплекса

Предмет курсовой работы

Темой курсовой работы является разработка программного комплекса «Улицы города».

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

Функции программы:

Создание набора данных.

Добавление новых элементов в конец набора данных.

Просмотр всех элементов набора данных.

Поиск элемента по номеру.

Переход к работе с другим набором данных.

Просмотр элементов и вычисление среднего, минимума и максимума на множестве тех элементов, которые попадают в заданный диапазон по заданному полю (длина улицы).

Добавление содержимого другого набора данных в конец текущего.

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

Для функционирования программного комплекса в каталоге с программой должны присутствовать файлы:.dat;.dat.

При написании программы были реализованы следующие процедуры:- процедура открытия файла настроек;- процедура записи данных в файл настроек;- процедура создание нового набора данных;- процедура открытия набора данных;- процедура открытия файла с набором данных;- процедура записи набора данных в файл;- процедура просмотра данных об улицах;- процедура добавления улиц;- процедура поиска улиц по номеру;- процедура вычисления минимальной, максимальной, средней длины и просмотр улиц, которые попадают в заданный диапазон;- процедура добавления другого набора данных в конец текущего;- процедура главного меню программы.

При вычисление средней длины улицы была использована следующая формула (2.1):

где

 - количество улиц;

 - длина i-й улицы.

Структура данных представлена в таблице 2.1.

Таблица 2.1 - Структура данных

Реализация программы

динамический память программный улица

При реализации данной программы наиболее подходящим методом проектирования был выбран метод расширения ядра.

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

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

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

Демонстрация программы

После запуска программы на экране появится главное меню, рисунок 2.1. После чего необходимо выбрать один из пунктов.

Рисунок 2.1 - Главное меню программы

Рисунок 2.2 - Создание нового набора данных

Рисунок 2.3 - Добавление данных

Для добавления улиц в текущий набор данных необходимо в главном меню выбрать пункт «2» и ввести данные о новой улице, рисунок 2.3.

Для просмотра данных необходимо в главном меню выбрать пункт «3», рисунок 2.4.

Рисунок 2.4 - Просмотр данных

Для поиска данных необходимо в главном меню выбрать пункт «4» и ввести номер улицы, после чего на экране появится данные искомой улицы, если такая имеется, рисунок 2.5.

Рисунок 2.5 - Поиск данных

Для добавления данных другого набора данных в конец текущего необходимо в главном меню выбрать пункт «5» и ввести название другого набора данных, рисунок 2.6.

Рисунок 2.6 - Добавление другого набора данных

Для просмотра и подсчета минимальной, максимальной и средней длины улицы в заданном диапазоне необходимо в главном меню выбрать пункт «6» и ввести название начало и конец диапазоне, после чего появятся улицы подходящие под данные критерии, рисунок 2.7.

Рисунок 2.7 - Просмотр данных в заданном диапазоне

Для работы с другим набором данных необходимо в главном меню выбрать пункт «7» и ввести название другого набора данных, рисунок 2.8.

Рисунок 2.8 - Переход к работе с другим набором данных

Заключение

Результатом проделанной работы стал программный комплекс «Улицы города». Программа предназначена для хранения и предоставления пользователям данных об улицах города.

Разработанная программа позволяет решить проблему с формой хранения данных.

Во время разработки данной программы были усовершенствованы навыки работы с языком программирования Pascal и со средой программирования Turbo Pascal 7.0, в результате чего написана программа, соответствующая всем требованиям, предъявленным к ней.

Список использованных источников

Абрамов, В. Г. Введение в язык Паскаль / В. Г. Абрамов, Н. П. Трифонов, Г. Н. Трифонова - М. : Наука, 1988.

Вирт, Н. А. Алгоритмы + структуры данных = программы / Н. А. Вирт. - М. : 1985.

Грогоно, П. П. Программирование на языке Паскаль / П. П. Грогоно - М. : Мир, 1982.

Культин, Н. Б. Программирование в Turbo Pascal и Delphi / Н. Б. Культин - СПб. : BHV, Санкт-Петербург, 1998.

Приложение А

Код программы kursach;

Uses Crt;= (centr,proezgaj,peshehodnaj,pereylok);= record: real;: string;: integer;: TTip;;= array [1..100] of TStreet;: file of TStreetList;,street1List: TStreetList;,j,kolStreet,kol1Street: integer;: string;openSettingsFile;: text;(fileSettings,'settings.dat');(fileSettings);(fileSettings,nameFile);(fileSettings);;saveSettingsFile;: text;(fileSettings,'settings.dat');(fileSettings);(fileSettings,nameFile);(fileSettings);;createND;;('Tekyschii ND: '+nameFile);;('Vvedite nazvanie novogo ND: ');(nameFile);;(fileStreet,nameFile+'.dat');(fileStreet);(fileStreet);i:=1 to 100 do Begin[i].dlina:=0;[i].naim:='';

streetList[i].kol:=0;

end;;openND;;('Tekyschii ND: '+nameFile);;('Vvedite nazvanie ND: ');(nameFile);;;openDB(fl: string);(fileStreet,fl+'.dat');(fileStreet);(fileStreet,streetList);(fileStreet);i:=1 to 100 do Begin(streetList[i].naim='') Then Begin:=i-1;;;;;saveDB(fl: string);(fileStreet,fl+'.dat');(fileStreet);(fileStreet,streetList);(fileStreet);;view;;('Tekyschii ND: '+nameFile);;('_________________________________________________________');('| # | Dlina | Nazvanie | kol Zdanii | tip |');('_________________________________________________________');i:=1 to kolStreet do BeginstreetList[i] do Begin('|',i:3,'|');(dlina:9:0,'|');(naim:12,'|');(kol:14,'|');(tip=centr) Then

Write('central''naj':13,'|');

if (tip=proezgaj) Then('proezgaj':13,'|');(tip=peshehodnaj) Then('peshehodnaj':13,'|');(tip=pereylok) Then('pereylok':13,'|');;;;('_________________________________________________________');;;add;;('Tekyschii ND: '+nameFile);;('Dannie novoi ylici');(' dlina: ');(streetList[kolStreet+1].dlina);(' nazvanie: ');(streetList[kolStreet+1].naim);(' kolichestvo zdanii: ');(streetList[kolStreet+1].kol);(' tip ylici: ');;(' 1 central''naj');(' 2 proezgaj');(' 3 peshehodnaj');(' 4 pereylok');;(' Num:');(i);i of

: streetList[kolStreet+1].tip:=centr;

: streetList[kolStreet+1].tip:=proezgaj;

: streetList[kolStreet+1].tip:=peshehodnaj;

: streetList[kolStreet+1].tip:=pereylok;;;:=kolStreet+1;(nameFile);('Ylica dobavlena');;;

Procedure found;

clrscr;('Tekyschii ND: '+nameFile);;('Vvedite porjdkovii nomer ylici: ');(j);((j>0) AND (j<kolStreet+1));;('_______________________________________________');('| # | Dlina | Nazvanie | kol Zdanii | tip |');('__________________________________________________');streetList[j] do Begin('|',j:3,'|');(dlina:9:0,'|');(naim:12,'|');(kol:14,'|');(tip=centr) Then('central''naj':13,'|');(tip=proezgaj) Then('proezgaj':13,'|');(tip=peshehodnaj) Then('peshehodnaj':13,'|');(tip=pereylok) Then('pereylok':13,'|');;;('____________________________________________');;;viewDiapazon;,finish,max,min,kol1,summa:real;: real;,minStreet:string;:Boolean;;('Tekyschii ND: '+nameFile);;('Vvedite nachalo diapazona: ');(start);('Vvedite konec diapazona: ');(finish);;:=-1;:=999999999;:=streetList[1].naim;:=streetList[1].naim;

ПРИЛОЖЕНИЕ А

Продолжение:=0;:=false;:=0;('___________________________________________');('| # | Dlina | Nazvanie | kol Zdanii | tip |');

Writeln('_____________________________________________');i:=1 to kolStreet do BeginstreetList[i] do Begin((dlina>start-1) AND (dlina<finish+1)) Then Begin('|',i:3,'|');(dlina:9:0,'|');(naim:12,'|');(kol:14,'|');(tip=centr) Then('central''naj':13,'|');(tip=proezgaj) Then('proezgaj':13,'|');(tip=peshehodnaj) Then('peshehodnaj':13,'|');(tip=pereylok) Then('pereylok':13,'|');;(dlina>max) Then Begin:=dlina;:=naim;;(dlina<min) Then Begin:=dlina;:=naim;;:=summa+dlina;:=kol1+1;:=true;;;;('______________________________________');temp Then Begin('Minimal''naj ylica ',minStreet,' dlinoi ',min:0:0,'km');('Maximal''naj ylica ',maxStreet,' dlinoi ',max:0:0,'km');:=summa/kol1;('Srednjj dlina ylic: ',sredn:0:0,'km');else('V zadannom diapazone ylic ne naideno');

readln;;

Procedure addND;: String;;('Tekyschii ND: '+nameFile);;('Vvedite nazvanie drugogo ND: ');(newND);(fileStreet,newND+'.dat');(fileStreet);(fileStreet,street1List);(fileStreet);i:=1 to 100 do Begin(street1List[i].naim='') Then BeginStreet:=i-1;;;;i:=kolStreet+1 to kolStreet+kol1Street do[i]:=street1List[i-kolStreet];(nameFile);;('ND dobavlen');;;delete;: string;;('Tekyschii ND: '+nameFile);;('Ydalenie');('Vvedite nomer elementa: ');(j);;('Ydalit'' elementi nachinaj s ',j,'-go? (Y/N):');(s);(s='Y') Then Begini:=j to kolStreet do Begin[i].naim:='';[i].dlina:=0;[i].kol:=0;;(nameFile);

Writeln('Ylici ydaleni');

Readln;;;menu;: integer;('Tekyschii ND: '+nameFile);;('Menu');(' 1 Sozdanie novogo nabora dannih');(' 2 Dobavlenie v tekyschii ND');(' 3 Prosmotr tekyschego ND');(' 4 Poisk po nomery v tekyschem ND');(' 5 Dobavlenie sodergimogo grugogo ND v konec tekyschego ND');(' 6 Prosmotr elementov v zadannom diapazone');(' 7 Rabota s drygim ND');;(' 0 Vihod');;('Vvedite pynkt menu:');(idMenu);idMenu of

: Begin;:=0;;;;;

: Begin(nameFile);;;;;

: Begin(nameFile);;;;;

: Begin(nameFile);

found; ;;;

5: Begin(nameFile);;;;;

: Begin(nameFile);;;;;

: Begin;(nameFile);;;;

: Begin(nameFile);;;;; ; end;;

openSettingsFile;;.