Динамічні структури даних: списки
Пример. Дан текстовий файл розміром трохи більше 64 Кб, у якому справжні числа, по одній на кожному рядку. Переписати вміст файла в масив, розмістивши їх у динамічно распределяемой пам’яті. Обчислити середнє елементів масиву. Очистити динамічну пам’ять. Створити цілий масив розміром 10 000, заповнити його випадковими цілими числами буде в діапазоні від -100 до 100 і обчислити його середнє… Читати ще >
Динамічні структури даних: списки (реферат, курсова, диплом, контрольна)
Динамические структури даних: списки
Введение
В попередніх оглядах ми розглядали програмування, що з обробкою лише статичних даних. Статичними величинами називаються такі, пам’ять під якими виділяється у час компіляції й тепло зберігається протягом усієї роботи программы.
В мовами програмування (Pascal, З, ін.) існує ще один спосіб виділення пам’яті під дані, що називається динамічним. І тут пам’ять під величини приділяється в час виконання програми. Такі величини називатимемо динамічними. Розділ оперативної пам’яті, що розподіляється статично, називається статичної пам’яттю; динамічно що розподіляється розділ пам’яті називається динамічної пам’яттю (динамічно распределяемой памятью).
Использование динамічних величин надає програмісту ряд додаткових можливостей. По-перше, підключення динамічної пам’яті дозволяє обсяг оброблюваних даних. По-друге, якщо потреба у якихось даних відпала до закінчення програми, то зайняту ними пам’ять можна звільнити для інший інформації. По-третє, використання динамічної пам’яті дозволяє створювати структури даних змінного размера.
Работа з динамічними величинами пов’язані з використанням чергового типу даних — засланого типу. Величини, мають ссылочный тип, називають указателями.
Указатель містить адресу поля була в динамічної пам’яті, котрий зберігає величину певного типу. Сам покажчик міститься у статичної памяти.
Адрес величини — це номер першого байта поля пам’яті, у якому розташовується величина. Розмір поля однозначно визначається типом.
Далее будемо докладніше обговорювати покажчики і дії з ними мові Pascal, приклади наводитимемо на Pascal і C.
Величина засланого типу (покажчик) описується розділ описи змінних наступним образом:
Var: ^;
Вот приклади описи указателей:
Type Mas1 = Array[1.100] Of Integer;
Var P1: ^Integer;
P2: ^String;
Pm: ^Mas1;
Здесь P1 — покажчик на динамічну величину цілого типу; P2 — покажчик на динамічну величину строкового типу; Pm — покажчик на динамічний масив, тип якого заданий розділ Type.
Сами динамічні величини не вимагають описи у програмі, бо за компіляції пам’ять під них виділяється. Під час компіляції пам’ять виділяється тільки під статичні величини. Покажчики — це статичні величини, тому вони вимагають описания.
Каким ж спосіб відбувається виділення пам’яті під динамічну величину? Пам’ять під динамічну величину, пов’язану із покажчиком, виділяється внаслідок виконання процедури NEW. Формат звернення до цієї процедуре:
NEW ();
Считается, що після виконання цієї оператора створена динамічна величина, чиє ім'я має наступний вид:
:= ^.
Пусть в програмі, у якій є наведене вище опис, присутні такі операторы:
NEW (P1); NEW (P2); NEW (Pm);
После їх виконання в динамічної пам’яті виявляється виділеним місце під три величини (дві скалярні і тільки масив), які мають идентификаторы:
P1^, P2^, Pm^.
Например, позначення P1^ можна розшифрувати так: динамічна змінна, яку посилається покажчик P1.
Дальнейшая роботу з динамічними перемінними відбувається як і, як із статичними перемінними відповідних типів. Їм можна присвоювати значення, їх можна використовувати як операндов у висловлюваннях, параметрів підпрограм тощо. Наприклад, якщо перемінної P1^ потрібно привласнити число 25, перемінної P2^ привласнити значення символу «Write », а масив Pm^ заповнити усе своєю чергою цілими числами від 1 до 100, це робиться так:
P1^ := 25;
P2^ := «Write » ;
For I := 1 To 100 Do Pm^[I] := I;
Кроме процедури NEW значення покажчика може визначатися оператором присваивания:
:= ;
В ролі засланого висловлювання можна использовать указатель;
ссылочную функцію (тобто. функцію, значенням якої є покажчик);
константу Nil.
Nil — це зарезервована константа, що означає порожню заслання, тобто. заслання, котра потім не вказує. При привласненні базові типи покажчика і засланого висловлювання повинні бути однаковими. Константу Nil можна присвоювати покажчику із кожним базовим типом.
До присвоювання значення ссылочной перемінної (з допомогою оператора присвоювання чи процедури NEW) вона є неопределенной.
Ввод та виведення покажчиків не допускается.
Рассмотрим приклад. нехай у програмі описані такі указатели:
Var D, P: ^Integer;
K: ^Boolean;
Тогда припустимими є оператори присвоювання.
D := P; K := Nil;
поскольку дотримується принцип відповідності типів. Оператор K := D помилковий, т.к. базові типи біля правої та скільки лівої частини різні.
Если динамічна величина втрачає покажчик, вона стає «сміттям ». У програмуванні під те слово розуміють інформацію, що займає пам’ять, але вже нужна.
Представьте собі, що у програмі, у якій присутні згадані вище покажчики, в розділі операторів записано следующее:
NEW (D); NEW (P);
{Выделено місце в динамічної пам’яті під дві цілі перемінні. Покажчики отримали відповідні значения}.
D^ := 3; P^ := 5;
{Динамическим змінним надано значения}.
P := D;
{Указатели P і D стали посилатися однією й саму величину, рівну 3}.
WriteLn (P^, D^); {Двічі надрукується число 3}.
Таким чином, динамічна величина, рівна 5, втратила свій покажчик і став недоступною. Проте місце у пам’яті на неї припадає. Це і приклад виникнення «сміття ». На схемою показано, що в результаті виконання оператора P := D.
В Паскале є стандартна процедура, що дозволяє звільняти пам’ять від даних, необхідність яких відпала. Її формат:
DISPOSE ();
Например, якщо динамічна змінна P^ большє нє потрібна, то оператор
DISPOSE (P).
удалит їх із пам’яті. Після цього значення покажчика P стає невизначеним. Особливо істотним стає ефект економії пам’яті під час видалення великих масивів.
В версіях Турбо-Паскаля, працюючих під операційній системою MS DOS, під дані однієї програми виділяється 64 кілобайта пам’яті (чи, якщо точніше, 65 520 байт). Це і статична область пам’яті. За необхідності працювати з більшими на масивами інформації цього й виявитися мало. Розмір динамічної пам’яті — багато більше (сотні кілобайтів). Тому використання динамічної пам’яті дозволяє істотно збільшити обсяг оброблюваної информации.
Следует чітко розуміти, що з динамічними даними уповільнює виконання програми, оскільки доступом до величині відбувається у два кроку: спочатку шукається покажчик, потім нього — величина. Як часто буває, діє «закон збереження неприємностей »: виграш у пам’яті компенсується програшем у времени.
Пример. Дан текстовий файл розміром трохи більше 64 Кб, у якому справжні числа, по одній на кожному рядку. Переписати вміст файла в масив, розмістивши їх у динамічно распределяемой пам’яті. Обчислити середнє елементів масиву. Очистити динамічну пам’ять. Створити цілий масив розміром 10 000, заповнити його випадковими цілими числами буде в діапазоні від -100 до 100 і обчислити його середнє значение.
{Язык Turbo Pascal}.
Program Srednee;
Const NMax = 10 000;
Type Diapazon = 1. NMax;
MasInt = Array[Diapazon] Of Integer;
MasReal = Array[Diapazon] Of Real;
Var PIint: ^MasInt; PReal: ^MasReal;
I, Midint: longInt; MidReal: Real; T: Text; P. S: string;
Begin.
Write («Запровадьте ім'я файла: »); ReadLn (S);
Assign (T, P. S); Reset (T); MidReal := 0; MidInt := 0;
Randomize;
NEW (PReal); {Виділення пам’яті під речовинний массив}.
{Введення і підсумовування речовинного массива}.
While Not Eof (T) Do.
Begin ReadLn (T, PReal^[I]); MidReal := MidReal + PReal^[I] End;
DISPOSE (PReal); {Видалення речовинного массива}.
NEW (PInt); {Виділення пам’яті під цілий массив}.
{Обчислення і підсумовування цілого массива}.
For I := 1 To NMax Do.
Begin PInt^[I] := -100 + Random (201); MidInt := MidInt + PInt^[I] End;
{Висновок середніх значений}.
WriteLn («середнє ціле одно: », MidInt DivX NMax);
WriteLn («середнє речовинне одно: », (MidReal / NMax): 10: 6).
End.
// Мова C++.
#include < stdio. h >
#include < time. h >
#include < stdlib. h >
#include < iostream. h >
#define NMax 10 000.
typedef int MasInt;
typedef float MasReal;
MasInt *PInt; MasReal *PReal;
int I, n, MidInt; float MidReal; char S[255];
FILE *t; char *endptr;
void main ().
{ cout > S;
t=fopen (S, «r »);
MidReal = 0; MidInt = 0;
randomize (); I=0;
/*Виділення пам’яті під речовинний массив*/.
PReal = (MasReal*) malloc (sizeof (MasReal));
/*Введення і підсумовування речовинного массива*/.
while (!feof (t)).
{fgets (S, 255, t); // вводимо з файла строку.
PReal[I] = strtod (S, &endptr); // перетворимо введену рядок в речовинне число.
MidReal += PReal[I]; I++;}.
n=I+1;
free (PReal); /*Видалення речовинного массива*/.
PInt = (MasInt*) malloc (sizeof (MasInt)); /*Виділення пам’яті під цілий массив*/.
/* Обчислення і підсумовування цілого масиву */.
for (I=0; I < NMax; I++).
{ PInt[I] = -100 + random (201);
MidInt += PInt[I]; }.
/*Висновок середніх значений*/.
cout Next=First; First=Vsp;
return First;
}.
Zveno *Iz_Nachala (Zveno *First).
{ Zveno *Vsp;
Vsp=First->Next;
free (First);
return Vsp;
}.
Zveno *V_Spisok (Zveno *Pred, BT X).
{ Zveno *Vsp;
Vsp = (Zveno *) malloc (sizeof (Zveno));
Vsp->Inf=X;
Vsp->Next=Pred->Next;
Pred->Next=Vsp;
return Vsp;
}.
BT Iz_Spiska (Zveno *Pred).
{ BT X;
Zveno *Vsp;
Vsp=Pred->Next;
Pred->Next=Pred->Next->Next;
X=Vsp->Inf;
free (Vsp);
return X;
}.
void Print (Zveno *First).
{ Zveno *Vsp;
Vsp=First;
while (Vsp).
{cout Inf Next;}.
cout 0.
Then If S2 = Nil.
Then Begin V_Nachalo (S2, V1^.Inf); V2 := S2 End.
Else Begin V_Spisok (V2, V1^.Inf); V2 := V2^.Next End;
If V1^.Inf < 0.
Then If S3 = Nil.
Then Begin V_Nachalo (s3, V1^.Inf); V3 := S3 End.
Else Begin V_Spisok (V3, V1^.Inf); V3 := V3^.Next End;
V1:= V1^.Next.
End;
WriteLn («Результуючий список з позитивних елементів: »); Print (S2);
WriteLn («Результуючий список з негативних елементів: »); Print (S3);
Ochistka (S1); Ochistka (S2); Ochistka (S3);
End.
// Програма на C++.
#include «SPIS.CPP «.
void main ().
{Zveno *S1, *S2, *S3, *V1, *V2, *V3;
BT a; int і, n;
clrscr ();
randomize ();
S1=NULL;
// створюємо перший элемент.
a=-100+random (201);
S1=V_Nachalo (S1, a);
n=1+random (20);
// формуємо список довільній довжини і виводимо на печать.
V1=S1;
for (i=2; iInf > 0).
if (!S2).
{S2=V_Nachalo (S2, V1->Inf); V2 = S2;}.
else {V_Spisok (V2, V1->Inf); V2 = V2->Next;};
if (V1->Inf < 0).
if (!S3).
{S3=V_Nachalo (S3, V1->Inf); V3 = S3;}.
else {V_Spisok (V3, V1->Inf); V3 = V3->Next;};
V1= V1->Next;}.
cout.