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

ВВЕДЕНИЕ

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

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

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

Указатель – это переменная, содержащая адрес в памяти компьютера. Если удастся осознать смысл этого простого предложения, то это и все, что необходимо знать об указателях. Указатель – это переменная, которая содержит адрес оперативной памяти.

Чтобы лучше понять указатели, рассмотрим устройство оперативной памяти компьютера. Оперативная память разделена на последовательно пронумерованные ячейки. Каждая переменная размещается в одной или нескольких последовательно расположенных отдельных ячейках памяти, адрес первой из них называется адресом переменной. Каждая ячейка в оперативной памяти занимает 1 байт или 8 бит.

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

Задание №1:

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

Входные данные:

Запись{inf}: цел – элементы очереди;

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

kol: цел – счетчик(номера элементов очереди);

key: сим – клавиша события;

tmp: сим – временный массив символов;

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

нет

Задание №2:

Определить количество изолированных вершин неориентированного графа, вывести их список. Сделать выбранную вершину неизолированной.

Входные данные:

Запись {v1, v2}: цел – 1-я и 2-я вершины одного ребра;

n: цел – общее количество вершин в графе.

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

i: цел – счетчик(номера элементов 1-ой очереди);

f: цел – счетчик(проверка на существование висячих вершин);

ch: сим – клавиша события;

s,s1: сим – строки, которые нужны для проверки введенных результатов;

v [10]: сим – показатель степени данной вершины.

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

2<=n<=5;

1<=v1<=n;

1<=v2<=n;

v1<>v2.

Выходные данные:

Запись {v1, v2}: цел – граф после удаления одной из висячих вершин.

2. ОБРАБОТКА СПИСКОВ

2.1. Описание структуры списка

Линейный список - это конечная последовательность однотипных элементов (узлов), возможно, с повторениями. Количество элементов в последовательности называется длиной списка, причем длина в процессе работы программы может изменяться. Линейный список F, состоящий из элементов D1,D2,...,Dn, записывают в виде последовательности значений заключенной в угловые скобки F=, или представляют графически (рисунок 2.1).

D1



D2



D3



...



Dn

Рисунок 2.1. - Изображение линейного списка

Например, F1=< 2,3,1>,F2=< 7,7,7,2,1,12 >, F3=< >. Длина списков F1, F2, F3 равна соответственно 3,6,0. В реальных языках программирования нет какой-либо структуры данных для представления линейного списка. Поэтому при работе с линейными списками важным является представление используемых в программе линейных списков таким образом, чтобы была обеспечена максимальная эффективность и по времени выполнения программы, и по объему требуемой памяти. Методы хранения линейных списков разделяются на методы последовательного и связанного хранения. При последовательном хранении элементы линейного списка размещаются в массиве d фиксированных размеров, например, 100, и длина списка указывается в переменной l, т.е. в программе необходимо иметь объявления вида

float d [100] ; int l;

Размер массива 100 ограничивает максимальные размеры линейного списка. Список F в массиве d формируется так:

d [0] =7; d [1] =10; l=2;

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

l:	2
d:	7	10	...
[0]	[1]	[2]	[3]	[98]	[99]
Рисунок 2.2. – Последовательное хранение линейного списка

При связанном хранении в качестве элементов хранения используются стру

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать