Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Разработка программ с использованием динамической памяти

Название: Разработка программ с использованием динамической памяти
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 01:00:09 29 января 2009 Похожие работы
Просмотров: 62 Комментариев: 3 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать
Введение

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

2. Использование динамических структур при работе с графами

2.1. Способы представления графов

2.2. Операции над графами

2.3. Описание программной реализации

2.3.1. Описание процедур и функций языка

2.3.2. Описание функций работы с динамической памятью, графами

Выводы

Приложение А Экранные формы

Приложение Б Листинг программы


1 ПОСТАНОВКА ЗАДАЧИ

Задача.

Найти все источники ориентированного графа.

Исходные данные:

- номер вершины (цел типа), вводимый пользователем;

- дуга графа, задается двумя вершинами источником и стоком, вводимая пользователем.

Промежуточные данные:

Head:TUk – указатель на голову списка смежности графа;

n,m:цел – номера вершин;

c:сим – клавиша события.

Результаты:

V:массив байт – массив вершин источников;

Ограничения:

max=10 – максимальное количество вершин;

V:массив [1..max*max].


2. Использование динамических структур при работе с графами

2.1 Способы представления графов

Способы задания графов:

- матрица смежности;

- матрица инцидентности;

- список смежности;

- список дуг (ребер);

- и др.

Список смежности – для вершины v есть список концов дуг, исходящих из вершины v, в случае орграфа, или список смежных с v вершин, в случае неориентированного графа.

Список дуг – это список, в котом каждой дуге ставится в соответствие пара <x,y> , где x – начало дуги, а y – ее конец. Для нагруженных графов – тройка <x,y,z> ,где x – начало дуги, y – конец дуги, z – вес дуги.

Матрица смежности – это квадратная матрица, строки и столбцы которой соответствуют вершинам графа. Элемент матрицы (i,j) равен 1, если вершина i связана с вершиной j ребром, иначе элемент матрицы равен 0.

Для неориентированных графов матрица смежности является симметричной относительно главной диагонали. Т.е. для получения информации о графе достаточно знать верхнюю или нижнюю треугольную матрицу смежности. Для ориентированных графов матрица смежности не является симметричной.

Матрица инцидентности – это матрица, строки которой – список вершин, а столбцы – список ребер. Элемент матрицы инциденций (i,j) равен 1, если вершина i инцидентна соответствующему ребру.

Для неориентированных графов:

Для ориентированных графов:

Например, дан граф G (см.рис. .1)


Рисунок 2.1 – Граф G

Представление графа списком смежности отображено на рисунке 2.2


Рисунок 2.2 – Список смежности графа G

Представление графа с помощью списка дуг имеет вид отображено на рисунке .3


Рисунок 2.3 – Список дуг графа G

Представление графа с помощью матрицы смежности показано в таблице 2.1

Таблица 2.1 – Матрица смежности

x1

x2

x3

x4

x5

x6

x1

0

1

1

0

0

0

x2

0

0

0

0

0

0

x3

0

1

0

1

1

0

x4

0

0

0

0

1

0

x5

0

0

0

0

0

1

x6

0

0

0

1

0

0

Представление графа с помощью матрицы инцидентности показано в таблице 2.2

Таблица 2.2 – Матрица инцидентности

x 1 x 2

x 1 x 3

x 3 x 2

x 3 x 4

x 3 x 5

x 4 x 5

x 5 x 6

x 6 x 4

x 1

1

1

0

0

0

0

0

0

x 2

-1

0

-1

0

0

0

0

0

x 3

0

-1

1

1

1

0

0

0

x 4

0

0

0

-1

0

1

0

-1

x5

0

0

0

0

-1

-1

1

0

x6

0

0

0

0

0

0

-1

1

2.2 Операции над графами

При решении поставленной задачи для представления графа был выбран список смежности.

type TUk1=^TEl1; //элемент списка вершин

TEl1=record

Next:TUk1;

Inf:integer;

end;

TUk=^TEl;

TEl=record //элемент списка смежности

Left:TUk1;

Inf:integer;

Down:TUk;

end;

Head:TUk; //указатель на начало списка

Схематичное представление списка смежности ориентированного графа представлено на рисунке 2.1

Рисунок 2.3 – Схема списка смежности

Алгоритм нахождения источников ориентированного графа представлен на рисунке 2.4.



Рисунок 2.4 - Алгоритм нахождения источников орграфа


2.3 Описание программной реализации

2.3.1 Описание процедур и функций языка

Процедура New резервирует фрагмент кучи для размещения переменной; формат обращения

New(TP)

TP – типизированный указатель. За одно обращение к процедуре можно зарезервировать не бо­лее 65521 байт динами­ческой памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фраг­ментирована, последовательные обращения к про­цедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.

Процедура Dispose – возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за типизированным указателем; формат обращения

Dispose (TP)

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

2.3.2 Описание функций работы с динамической памятью, графами

Для решения поставленной задачи были разработаны следующие процедуры и функции:

1) procedure AddVer(n:integer); - добавление в список смежности вершины с номером n;

2) procedure AddDug(n,m:integer); - добавление в список дуги (n,m). n и m номера вершин источника дуги и стока соответственно;

3) procedure DelList(p:TUk1); - удаление списка смежных вершин. p – указатель на начало списка;

4) procedure DelVer(n:integer); - удаление вершины с номером n;

5) procedure DelDug(n,m:integer); - удаление дуги (n,m). n и m номера вершин источника дуги и стока соответственно;

6) procedure PrintGraph; - вывод списка смежности на экран в виде матрицы смежности;

7) procedure FindIstok; - поиск и вывод на экран всех источников орграфа.


ВЫВОДЫ

Задание, выданное на летнюю практику, поставило определенные задачи:

1) научится создавать связные структуры данных, используя указатели;

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

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

Решение выданного задания было реализовано с помощью языка программирования Паскаль.

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


Приложение А

ЭКРАННЫЕ ФОРМЫ

Рисунок А.1 – Главное меню программы

Рисунок А.2 – Добавление дуги орграфа

Рисунок А.3 – Матрица смежности орграфа

Рисунок А.4 – Список вершин источников орграфа


Приложение Б

ЛИСТИНГ ПРОГРАММЫ

program OrGraph;

uses Crt;

type TUk1=^TEl1;

TEl1=record

Next:TUk1;

Inf:integer;

end;

TUk=^TEl;

TEl=record

Left:TUk1;

Inf:integer;

Down:TUk;

end;

const

max=10;

var

Head:TUk;

c:char;

n,m:integer;

V:array[1..max] of byte;

{---------добавляем вершину в граф-------------}

procedure AddVer(n:integer);

var

p:TUk;

begin

if (Head=Nil) then

begin

New(Head);

Head^.Inf:=n;

Head^.Left:=Nil;

Head^.Down:=Nil;

end else begin

p:=Head;

while ((p^.Down<>Nil)and(p^.Inf<>n)) do p:=p^.Down;

if (p^.Inf=n) then WriteLn('Такая вершина уже есть!!!')

else begin

New(p^.Down);

p^.Down^.Inf:=n;

p^.Down^.Left:=Nil;

p^.Down^.Down:=Nil;

end;

end;

end;

{-------добавляем дугу в граф----------------------}

procedure AddDug(n,m:integer);

var

p,p1:TUk;

p2:TUk1;

begin

if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')

else begin

p:=Head;

while ((p<>Nil)and(p^.Inf<>n)) do p:=p^.Down;

if (p=Nil) then WriteLn('В графе отсутствует указанная вершина источник!!!')

else begin

p1:=Head;

while ((p1<>Nil)and(p1^.Inf<>m)) do p1:=p1^.Down;

if (p1=Nil) then WriteLn('В графе отсутствует указанная вершина сток!!!')

else begin

if (p^.Left=Nil) then

begin

New(p^.Left);

p^.Left^.Inf:=m;

p^.Left^.Next:=Nil;

end else begin

p2:=p^.Left;

while ((p2^.Next<>Nil)and(p2^.Inf<>m)) do p2:=p2^.Next;

if (p2^.Inf=m) then WriteLn('Указанная дуга уже существует!!!')

else begin

New(p2^.Next);

p2^.Next^.Inf:=m;

p2^.Next^.Next:=Nil;

WriteLn('Дуга добавлена!!!');

end;

end;

end;

end;

end

end;

{--удаляем список дуг--}

procedure DelList(p:TUk1);

var p1:TUk1;

begin

while (p<>Nil) do

begin

p1:=p;

p:=p^.Next;

Dispose(p1);

end;

end;

{---------удаляем вершину из графа---------}

procedure DelVer(n:integer);

var

p,p1:TUk;

p2,p3:TUk1;

begin

if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')

else begin

p:=Head;

if (p^.Inf=n) then

begin

Head:=Head^.Down;

DelList(p^.Left);

Dispose(p);

end else begin

while ((p^.Down^.Inf<>n)and(p^.Down<>Nil)) do p:=p^.Down;

if (p^.Down=Nil) then WriteLn('В графе нет указанной вершины!!!')

else begin

DelList(p^.Down^.Left);

p1:=p^.Down;

p^.Down:=p^.Down^.Down;

Dispose(p1);

end;

end;

p:=Head;

while (p<>Nil) do

begin

if (p^.Left^.Inf=n) then

begin

p2:=p^.Left;

p^.Left:=p^.Left^.Next;

Dispose(p2);

end else begin

p2:=p^.Left;

while ((p2^.Next<>Nil)and(p2^.Next^.Inf=n)) do p2:=p2^.Next;

if(p2^.Next^.Inf=n) then

begin

p3:=p2^.Next;

p2^.Next:=p2^.Next^.Next;

Dispose(p3);

end;

end;

p:=p^.Down;

end;

end;

end;

{------удаляем дугу графа--------}

procedure DelDug(n,m:integer);

var

p,p1:TUk;

p2,p3:TUk1;

begin

if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')

else begin

p:=Head;

while ((p^.Inf<>n)and(p<>Nil)) do p:=p^.Down;

if (p=Nil) then WriteLn('В графе отсутствует указанная вершина источник')

else begin

p1:=Head;

while ((p1<>Nil)and(p1^.Inf<>m)) do p1:=p1^.Down;

if (p1=Nil) then WriteLn('В графе отсутствует указанная вершина сток!!!')

else begin

p2:=p^.Left;

if (p^.Left^.Inf=m) then

begin

p3:=p^.Left;

p^.Left:=p^.Left^.Next;

Dispose(p3);

end else begin

while ((p2^.Next^.Inf<>m)and(p2^.Next<>Nil)) do p2:=p2^.Next;

if (p2=Nil) then WriteLn('Указанного ребра нет в графе!!!')

else begin

p3:=p2^.Next;

p2^.Next:=p2^.Next^.Next;

Dispose(p3);

end;

end;

end;

end;

end;

end;

{---Вывод графа в виде матрицы смежности------}

procedure PrintGraph;

var

i,j,n:integer;

M:array [1..max,1..max] of byte;

p:TUk;

p2:TUk1;

begin

for i:=1 to max do

for j:=1 to max do M[i,j]:=0;

n:=0;

if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')

else begin

p:=Head;

while (p<>Nil) do

begin

inc(n);

p2:=p^.Left;

while (p2<>Nil) do

begin

M[p^.Inf,p2^.Inf]:=1;

p2:=p2^.Next;

end;

p:=p^.Down;

end;

end;

for i:=1 to n do

begin

for j:=1 to n do Write(M[i,j]:2);

WriteLn;

end;

end;

{-----находим все источники орграфа----}

procedure FindIstok;

var

f:boolean;

i,k:integer;

Is:array[1..max*max] of byte;

p,p1:TUk;

p2:TUk1;

begin

for i:=1 to max*max do Is[i]:=0;

if (Head=Nil) then WriteLn('В графе нет ни одной вершины!!!')

else begin

k:=0;

p:=Head;

while (p<>Nil) do

begin

if (p^.Left<>Nil) then

begin

f:=true;

p1:=Head;

while (p1<>Nil) do

begin

p2:=p1^.Left;

while ((f)and(p2<>Nil)) do

begin

if p2^.Inf=p^.Inf then f:=false;

p2:=p2^.Next;

end;

p1:=p1^.Down;

end;

if (f=true) then

begin

inc(k);

Is[k]:=p^.Inf;

end;

end;

p:=p^.Down;

end;

end;

for i:=1 to k do Write(Is[i]:2);

end;

procedure Menu;

begin

WriteLn('1-Показать матрицу смежности графа');

WriteLn('2-Добавить вершину в граф');

WriteLn('3-Добавить дугу в граф');

WriteLn('4-Удалить вершину графа');

WriteLn('5-Удалить дугу графа');

WriteLn('6-Найти источники орграфа');

WriteLn('7-Выход');

end;

{--------основная программа--------}

begin

ClrScr;

repeat

clrscr;

Menu;

c:=ReadKey;

case c of

'1': begin

ClrScr; PrintGraph; ReadKey;

end;

'2': begin

ClrScr;

Write('Введите добавляемую вершину : ');

ReadLn(n); AddVer(n);

end;

'3': begin

ClrScr;

Write('Введите вершину источник дуги : ');

ReadLn(n);

Write('Введите вершину сток дуги : ');

ReadLn(m); AddDug(n,m);

end;

'4': begin

ClrScr;

Write('Введите удаляемую вершину : ');

ReadLn(n); DelVer(n);

end;

'5': begin

ClrScr;

Write('Введите вершину источник удаляемой дуги : ');

ReadLn(n);

Write('Введите вершину сток удаляемой дуги : ');

ReadLn(m); DelDug(n,m);

end;

'6': begin

ClrScr; FindIstok; ReadKey;

end;

'7': begin

halt;

end;

end;

until ord(c)=27;

end.

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений06:39:29 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
12:35:08 29 ноября 2015
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:47:19 28 ноября 2015

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(150557)
Комментарии (1836)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru