asyan.org
добавить свой файл
1
Практична робота № 1.

Тема: Представлення даних за допомогою лінійних та нелінійних структур.

Мета: Навчитись представляти дані за допомогою лінійних і нелінійних структур та ознайомитись із основними операціями над цими структурами.

Завдання.

  1. Повторити основні структури даних та синтаксис їх представлення на мові С.

  2. Ознайомитись із алгоритмами операцій для стеків і черг.

Робота із стеком

Над стеком виконують дві основні операції:

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

  • pop ("виштовхнути елемент"): отримує елемент з верхівки стеку. При цьому він видаляється зі стеку і його місце в верхівці стеку займає наступний за ним відповідно до правила LIFO, а розмір стеку зменшується на одиницю. При намаганні "виштовхнути" елемент з вже пустого стеку, відбувається ситуація "незаповнення" стеку (англ. stack underflow)

Для зберігання елементів стеку резервується масив stаk[Max] певного розміру та додаткова змінна tos, яка буде зберігати індекс верхівки стеку.

Операції push та pop тоді можуть бути записані так :
int stack[MAX];

int tos=0; /* вершина стеку */
/* Додати елемент в стек. */

void push(int i)

{
if(tos >= MAX) {

printf("Стек заповнений\n");

return;

}

stack[tos] = i;

tos++;

}
/* отримати верхній елемент стеку. */

int pop(void)

{

tos--;

if(tos < 0) {

printf("Стек пустий\n");

return 0;

}

return stack[tos];

}

^ Операції над чергою

Черга - це лінійний список інформації, робота з яким відбувається за принципом "першим прийшов - першим вийшов" (first-in, first-out); цей принцип ще називається FIFO.
Щоб уявити собі роботу черзі, давайте введемо дві функції: enqueue () і dequeue () . Функція enqueue () поміщає елемент в кінець черги, а функція dequeue () видаляє елемент з початку черги і повертає його значення.

#define MAX 100
char *p[MAX];

int spos = 0;

int rpos = 0;
/* додавання елементу */

void enqueue (char *q)

{

if(spos==MAX) {

printf("Черга переповнена\n");

return;

}

p[spos] = q;

spos++;

}
/* видалення елементу. */

char * dequeue()

{

if(rpos==spos) {

printf("Черга пуста\n");

return '\0';

}

rpos++;

return p[rpos-1];

}

  1. Виконати завдання згідно варіанту.

4. Оформити результати у звіт.