Скачиваний:
38
Добавлен:
10.02.2019
Размер:
28.03 Кб
Скачать

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В. И. Ульянова (Ленина)

Кафедра МОЭВМ

отчет

по лабораторной работе №2

по дисциплине «Программирование»

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

Студент гр. 3303

Преподаватель

Санкт-Петербург

2018

Цель работы:

Требуется написать программу, моделирующую работу стека, реализовав перечисленные ниже методы. Программе на вход подаётся последовательность команд с новой строки (не более 100 команд), в зависимости от которых программа выполняет ту или иную операцию и выводит результат ее выполнения с новой строки.

Перечень команд:

  • push n -добавляет целое число n в стек. Программа должна вывести "ok";

  • pop -удаляет из стека последний элемент и выводит его значение на экран;

  • top -программа должна вывести верхний элемент стека на экран не удаляя его из стека;

  • size -программа должна вывести количество элементов в стеке;

  • exit -программа должна вывести "bye" и завершить работу,

Если в процессе вычисления возникает ошибка программа должна вывести "error" и завершиться.

Стек требуется реализовать на базе списка.

Ход работы:

В начале программы создаётся структура Node, включающая в себя поле целого числа и указатель на следующую структуру, и структура-обёртка Stack, содержащая указатель на голову и количество элементов стека. Затем реализуются методы для работы с стеком:

  • функция push принимает в качестве аргументов указатель на стек и элемент для добавления, который кладёт в стек, и пишет “ok”;

  • функция pop принимает в качестве аргумента указатель на стек, выводит его значение и удаляет из стека;

  • функция top принимает в качестве аргумента указатель на стек и выводит его значение;

  • функция size принимает в качестве аргумента указатель на стек и выводит количество элементов с стеке;

  • функция exits принимает в качестве аргумента указатель на стек и высвобождает память и пишет “bue”;

  • функция isEmpty принимает в качестве аргумента указатель на стек и выводит состояние стека(1 - пуст, 0 - полон).

Файл main.c

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

struct Node{

    int date;

    struct Node *next;

};

struct Stack{

    struct Node *head;

    int size;

};

struct Stack initStack(){

    struct Stack stack = {NULL,0};

    return stack;

}

void push(struct Stack *stack,int x){

    struct Node *node = malloc(sizeof(struct Node));

    node->date = x;

    node->next = stack->head;

    stack->head = node;

    stack->size++;

    

    printf("ok\n");

}

void pop(struct Stack *stack){

    struct Node *node = stack->head;

    stack->head = stack->head->next;

    stack->size--;

    printf("%d\n",node->date);

    free(node);

}

void top(struct Stack *stack){

    printf("%d\n",stack->head->date);

}

void size(struct Stack *stack){

    printf("%d\n",stack->size);

}

int isEmpty(struct Stack *stack){

    return !stack->size;

}

void exit(struct Stack *stack){

    while(!isEmpty(stack)){

    struct Node *node = stack->head;

    stack->head = stack->head->next;

    stack->size--;

    free(node);

    }

    printf("bye\n");

}

int main() {

    struct Stack stack = initStack();

    long int elem;

    int return_flag = 1;

    char str[5];

    while(return_flag){

        scanf("%s",&str);

        if(!strcmp(str,"push")){

            scanf("%li",&elem);

            push(&stack,elem);

            

            continue;

        }

        if(!strcmp(str,"pop")&& !isEmpty(&stack)){

            pop(&stack);

            continue;

        }

        if(!strcmp(str,"top")&& !isEmpty(&stack)){

            top(&stack);

            continue;

        }

        if(!strcmp(str,"size")){

            size(&stack);

            continue;

        }

        if(!strcmp(str,"exit")){

            exit(&stack);

            return 0;

        }

        return_flag = 0;

    }

printf("error");

return 0;

}

Вывод:

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

Соседние файлы в папке lab2