ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Динамічні структури даних: списки
         

     

    Інформатика, програмування

    Динамічні структури даних: списки

    Вступ

    В мовах програмування (Pascal, C, ін) існує й інший спосіб виділення пам'яті під дані, який називається динамічним. У цьому випадку пам'ять під величини відводиться під час виконання програми. Такі величини будемо називати динамічними. Розділ оперативної пам'яті, розподіляється статичний, називається статичної пам'яттю; динамічно розподілена розділ пам'яті називається динамічною пам'яттю (динамічно розподіленою пам'яттю).

    Використання динамічних величин надає програмісту ряд додаткових можливостей. По-перше, підключення динамічної пам'яті дозволяє збільшити обсяг оброблюваних даних. По-друге, якщо потреба в якихось даних відпала до закінчення програми, то зайняту ними пам'ять можна звільнити для іншої інформації. По-третє, використання динамічної пам'яті дозволяє створювати структури даних змінного розміру.

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

    Покажчик містить адресу поля в динамічній пам'яті, що зберігає величину певного типу. Сам покажчик розташовується в статичної пам'яті.

    Адреса величини - це номер першого байта поля пам'яті, в якому розташовується величина. Розмір поля однозначно визначається типом.

    Далі будемо більш докладно обговорювати покажчики і дії з ними в мові Pascal, приклади будемо приводити на Pascal та C.

    Величина посилального типу (покажчик) описується в розділі опису змінних наступним так:

    Var: ^;

    Ось приклади опису покажчиків:

    Type Mas1 = Array [1 .. 100] Of Integer;

    Var P1: ^ Integer;

    P2: ^ String;

    Pm: ^ Mas1;

    Тут P1 - покажчик на динамічну величину цілого типу; P2 - покажчик на динамічну величину строкового типу; Pm - покажчик на динамічний масив, тип якого задано у роздiлi 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 кілобайт пам'яті (або, якщо точніше, 65520 байт). Це і є статична область пам'яті. При необхідності працювати з великими масивами інформації цього може виявитися мало. Розмір динамічної пам'яті - набагато більше (сотні кілобайт). Тому використання динамічної пам'яті дозволяє істотно збільшити обсяг оброблюваної інформації.

    Слід чітко розуміти, що робота з динамічними даними уповільнює виконання програми, оскільки доступ до величини відбувається у два кроки: спочатку шукається покажчик, потім по ньому - величина. Як це часто буває, діє "закон збереження неприємностей": виграш в пам'яті компенсується програшем в часі.

    Приклад. Дан текстовий файл розміром не більше 64 Кб, що містить дійсні числа, за одному в кожному рядку. Переписати вміст файлу в масив, розмістивши його в динамічно розподіляє пам'яті. Обчислити середнє значення елементів масиву. Очистити динамічну пам'ять. Створити цілий масив розміром 10000, заповнити його випадковими цілими числами в діапазоні від -100 до 100 і обчислити його середнє значення.

    (Мова Turbo Pascal)

    Program Srednee;

    Const NMax = 10000;

    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; S: string;

    Begin

    Write ( 'Введіть ім'я файлу: '); ReadLn (S);

    Assign (T, 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 Div NMax);

    WriteLn ( 'середнє речовий одно: ', (MidReal/NMax): 10: 6)

    End.

    // Мова C + +

    # include

    # include

    # include

    # include

    # define NMax 10000

    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

    (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 i, 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

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status