Программная инженерия 1 курс / 2 семестр / lab2 / report_lab2
.docxМИНОБРНАУКИ РОССИИ
Санкт-Петербургский государственный
электротехнический университет
«ЛЭТИ» им. В. И. Ульянова (Ленина)
Кафедра МОЭВМ
отчет
по лабораторной работе №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;
}
Вывод:
В процессе работы была изучена структура данных – стек и написана программа, моделирующая работу стека на основе списка.