Міністерство освіти і науки України Національний Університет « Львівська Політехніка» Кафедра ЕОМ Звіт до лабораторної роботи №4 на тему: « Структура даних „ЧЕРГА”.» Варіант 15. Львів-2007 Назва роботи: Структури даних “черга”. Мета роботи: Закріпити теоретичні знання та оволодіти практичними навиками опрацювання структур даних “черга”. Засвоїти техніку створення та опрацювання складних типів даних. Теоретична частина: Чергою називається впорядкований набір елементів які можуть вилучатись з одного його кінця, який називається початком черги і додаватися в її кінець, який називається кінцем черги. Дег – об’єднання черги і стеку, де додавання і вилучення можливе з двох її кінців. Виконання роботи Завдання: Змоделюйте чергу за допомогою двух стеків, представлених за допомогою вказівників. Додавання елементу до черги зводиться до додавання до одному зі стеков, а перевірка, чи черга порожня - до перевірки, чи порожні обидва стеки. При вилученні елемента з черги можливі два випадки. Якщо стек, де знаходиться початок черги, не порожній, то вилучається з нього елемент. Якщо він порожній, то попередньо в нього переписуються всі елементи другого стеку, змінюючи порядок (це відбувається саме при перекладанні зі стеку в стек) і далі задача зводиться до першого випадку. #include <stdio.h> #include <conio.h> #include <stdlib.h> #define size 10 #define infotype int #define printfspec "%d " struct stacktype { infotype data[size]; int top,EMPTY,FULL; } ; typedef struct stacktype stack; void Init(stack *s); void Push(stack *s, infotype new_data); infotype Pop(stack *s); void Print(stack *s); void main() { stack ST; infotype x; Init(&ST); printf("\nEnter elements in the stack:\n"); do { printf("Enter the new element(zero - break inputing elements): "); scanf("%d",&x); if (x) Push(&ST,x); } while (x); Print(&ST); x=Pop(&ST); Print(&ST); Pop(&ST); Print(&ST); Pop(&ST); Print(&ST); Push(&ST,x); Print(&ST); getch(); return; } void Init(stack *s) { s->EMPTY=1; s->FULL=0; s->top=-1; return; } void Push(stack *s, infotype new_data) { if (s->FULL) printf(" Error : Stack overflowed! \n"); else s->data[++s->top] = new_data; s->EMPTY=0; if(s->top+1==size) s->FULL=1; else s->FULL=0; return; } infotype Pop(stack *s) { if (s->EMPTY) { printf(" Error : Stack is empty! \n"); return 0; } else{ s->FULL=0; if(s->top==0) s->EMPTY=1; else s->EMPTY=0; return s->data[s->top--];} } void Print(stack *s) { int i; printf("Elements of stack: "); if (s->EMPTY) printf("Stack is empty! \n"); else { for (i=0;i<=s->top;i++) printf(printfspec,s->data[i]); printf("\n"); } return; } Результат виконання
Висновок: Закріпив теоретичні знання та оволодів практичними навиками опрацювання структур даних “Черга”. Засвоїв техніку створення та опрацювання складних типів даних.