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

     

     

     

     

     

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

     

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

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

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

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

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

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

    Виділимо типові операції над стеком і його елементами:

    додавання елемента в стек;

    видалення елемента з стека;

    перевірка, чи порожній стек;

    перегляд елемента в вершині стека без видалення;

    очищення стека.

    Реалізуємо ці операції, використовуючи розроблений раніше модуль для односпрямований списків (див. матеріал "Динамічні структури даних: списки").        

    (Turbo Pascal, файл STACK.PAS)   

    Unit Stack;   

    Interface   

    Uses Spisok;   

    Procedure V_Stack (Var   Versh: U; X: BT);   

    Procedure   Iz_Stack (Var Versh: U; Var X: BT);   

    Function Pust (Versh:   U): Boolean;   

    Function   V_Vershine (Versh: U): BT;   

    Procedure   Ochistka (Var Versh: U);   

    Implementation   

    Procedure V_Stack;   

    Begin   

    V_Nachalo (Versh, X)   

    End;   

    Procedure Iz_Stack;   

    Begin   

    Iz_Nachala (Versh, X)   

    End;   

    Function Pust;   

    Begin   

    Pust: = Versh = Nil   

    End;   

    Function V_Vershine;   

    Begin   

    V_Vershine: = Versh ^. Inf   

    End;   

    Procedure Ochistka;   

    Begin   

    Spisok.Ochistka (Versh)   

    End;   

    Begin   

    End.         

            

    /* C + +, файл STACK.CPP */   

    # include   "SPIS.CPP"   

    Zveno * V_Stack (Zveno   * Versh, BT X)   

    (   

    return   V_Nachalo (Versh, X);   

    )   

    Zveno * Iz_Stack (Zveno   * Versh)   

    (   

    return   Iz_Nachala (Versh);   

    )   

    int SPust (Zveno   * Versh)   

    (   

    return! Versh;   

    )   

    BT V_Vershine (Zveno   * Versh)   

    (   

    return Versh-> Inf;   

    )   

    Zveno * Chistka (Zveno   * Versh)   

    (   

    while (! Pust (Versh))   Versh = Iz_Stack (Versh);   

    return Versh;   

    )     

    Використовуючи розроблені тут бібліотеки, вирішимо завдання.

    Приклад. Написати програму, яка обчислює як ціле число значення виразів (без змінних), записаних (без помилок) в постфіксной формі в текстовому файлі. Кожен рядок файлу містить рівно один вислів.

    Алгоритм рішення. Вираз проглядається зліва направо. Якщо зустрічається число, то його значення (як ціле) заноситься в стек, а якщо встечаются знак операції, то з стека витягуються два останніх елементу (це операнди даної операції), над ними виконується операція і її результат записується в стек. Наприкінці в стеку залишається тільки одне число - значення всього виразу.        

    (Turbo Pascal, файл ST2.PAS)   

    Program St2;   

    Uses Spisok, Stack;   

    Const Znak = ['+',   '-', '*','/'];   

    Var S, S1: String;   

    T: Text;   

    I, N: Byte;   

    X, Y: BT; Code: Integer;   

    NS: U;   

    Begin   

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

    Assign (T, S1); ReSet (T);   

    NS: = Nil;   

    While Not Eof (T) Do   

    Begin   

    ReadLn (T, S); I: = 1;   

    While I <= Length (S) Do   

    Begin   

    If S [I] In ['0 '.. '9']   

    Then   

    Begin   

    N: = I;   

    While S [I] In ['0 '.. '9'] Do   

    I: = I + 1;   

    Val (Copy (S, N, I - N), X, Code);   

    V_Stack (NS, X);   

    End   

    Else   

    If S [I] In Znak   

    Then   

    Begin   

    Iz_Stack (NS, X);   

    Iz_Stack (NS, Y);   

    Case S [I] Of   

    '+': X: = X + Y;   

    '-': X: = Y - X;   

    '*': X: = X * Y;   

    '/': X: = Y Div X   

    End;   

    V_Stack (NS, X)   

    End;   

    I: = I + 1   

    End;   

    Iz_Stack (NS, X);   

    WriteLn (S, '=', X);   

    End   

    End.         

            

    /* C + +, файл ST2.CPP */   

    # include   "STACK.CPP"   

    # include <   string.h>   

    # include   

    void main (void)   

    (   

    char S [255];   

    FILE * T;   

    int I; BT X, Y;   

    Zveno * NS;   

    clrscr ();   

    cout << "Введіть ім'я файлу:   "; Cin>> S;   

    T = fopen (S, "r");   

    NS = NULL;   

    while (! feof (T))   

    (   

    fgets (S, 255, T);   

    I = 0;   

    while (I <= strlen (S) -1)   

    (   

    if (S [I]> = '0 '& & S [I] <= '9')   

    (   

    X = 0;   

    while (S [I]> = '0 '& & S [I] <= '9')   (X = X * 10 + (S [I] - '0 '); I + +;)   

    NS = V_Stack (NS, X);   

    )   

    else   

    if   (S [I ]=='+'|| S [I ]=='-'|| S [I ]=='/'|| S [I ]=='*')   

    (   

    X = V_Vershine (NS);   

    NS = Iz_Stack (NS);   

    Y = V_Vershine (NS);   

    NS = Iz_Stack (NS);   

    switch (S [I]) (   

    case '+': X + = Y; break;   

    case '-': X = Y - X; break;   

    case '*': X *= Y; break;   

    case '/': X = Y/X; break;)   

    NS = V_Stack (NS, X);   

    )   

    I + +;   

    )   

    X = V_Vershine (NS);   

    NS = Iz_Stack (NS);   

    cout <"   <   

    )     

    Список літератури

    Для підготовки даної роботи були використані матеріали з сайту http://comp-science.narod.ru

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

     

     

     

     

     

     

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