Курсовая работа: Аркадна гра "гольф" з елементами трьохвимірної поверхні

Кількість дій, необхідних для виконання зазначених операцій над списком у зв'язаному збереженні, оцінюється співвідношеннями: для операцій 1 і 2 - Q=l; для операцій 3 і 4 - Q=1; для операції 5 - Q=l.

Організація двузв‘язних списків

Зв'язане збереження лінійного списку називається списком із двома зв'язками або двузв‘язним списком, якщо кожен елемент збереження має два компоненти покажчика (посилання на попередній і наступний елементи лінійного списку).

У програмі двузв‘язний список можна реалізувати за допомогою описів:

typedef struct ndd { float val; /* ???????? ???????? */ struct ndd * n; /* ???????? ?? ????????? ??????? */ struct ndd * m; /* ???????? ?? ?????????? ??????? */ } NDD; NDD * dl, * p, * r;

Графічна інтерпретація методу зв'язаного збереження списку F=<2,5,7,1> як списку з двома зв'язками приведена на мал.8.

Вставка нового вузла зі значенням new за елементом, обумовленим покажчиком p, здійснюється за допомогою операторів:

r=malloc(NDD); r->val=new; r->n=p->n; (p->n)->m=r; p->=r;

Видалення елемента, що випливає за вузлом, на який указує p

p->n=r; p->n=(p->n)->n; ( (p->n)->n )->m=p; free(r);

Зв'язане збереження лінійного списку називається циклічним списком, якщо його останній указує на перший елемент, а покажчик dl - на останній елемент списку.

Схема циклічного збереження списку F=<2,5,7,1> приведена на мал.9.

При рішенні конкретних задач можуть виникати різні види зв'язаного збереження.

Нехай на вході задана послідовність цілих чисел B1,B2,...,Bn з інтервалу від 1 до 9999, і нехай Fi (1<I по зростанню. Скласти процедуру для формування Fn у зв'язаному збереженні і повернення покажчика на його початок.

При рішенні задачі в кожен момент часу маємо упорядкований список Fi і при введенні елемента Bi+1 уставляємо його в потрібне місце списку Fi, одержуючи упорядкований список Fi+1. Тут можливі три варіанти: у списку немає елементів; число вставляється в початок списку; число вставляється в кінець списку. Щоб уніфікувати всі можливі варіанти, початковий список організуємо як зв'язаний список із двох елементів <0,1000>.

Розглянемо програму рішення поставленої задачі, у якій покажчики dl, r, p, v мають наступне значення: dl указує початок списку; p, v - два сусідніх вузли; r фіксує вузол, що містить чергове введене значення in.

#include #include typedef struct str1 { float val; struct str1 *n; } ND; main() { ND *arrange(void); ND *p; p=arrange(); while(p!=NULL) { printf("\n %f ",p->val); p=p->n; } } ND *arrange() /* ?????????? ?????????????? ?????? */ { ND *dl, *r, *p, *v; float in=1; char *is; dl=malloc(sizeof(ND)); dl->val=0; /* ?????? ??????? */ dl->n=r=malloc(sizeof(ND)); r->val=10000; r->n=NULL; /* ???????? ??????? */ while(1) { scanf(" %s",is); if(* is=='q') break; in=atof(is); r=malloc(sizeof(ND)); r->val=in; p=dl; v=p->n; while(v->valn; } r->n=v; p->n=r; } return(dl); }

Стеки і черги

У залежності від методу доступу до елементів лінійного списку розрізняють різновиду лінійних списків називані стеком, чергою і двосторонньою чергою.

Стек - це кінцева послідовність деяких однотипних елементів - скалярних перемінних, масивів, структур або об'єднань, серед яких можуть бути й однакові. Стік позначається у виді: S= і представляє динамічну структуру даних; її кількість елементів заздалегідь не вказується й у процесі роботи, як правило змінюється. Якщо в стеці елементів ні, то він називається порожнім і позначається S=<>.

Припустимими операціями над стеком є:

- перевірка стека на порожнечу S=<>,

- додавання нового елемента Sn+1 у кінець стека - перетворення < S1,...,Sn> у < S1,...,Sn+1>;

- вилучення останнього елемента зі стека - перетворення < S1,...,Sn-1,Sn> у < S1,...,Sn-1>;

- доступ до його останнього елемента Sn, якщо стік не порожній.

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

Черга - це лінійний список, де елементи віддаляються з початку списку, а додаються наприкінці списку (як звичайна черга в магазині).

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

Реалізація стеков і черг у програмі може бути виконана у виді послідовного або зв'язаного збереження. Розглянемо приклади організації стека цими способами.

Однієї з форм представлення виражень є польський інверсний запис, що задає вираження так, що операції в ньому записуються в порядку виконання, а операнди знаходяться безпосередньо перед операцією.

Наприклад, вираз

(6+8)*5-6/2

у польському інверсному записі має вигляд

6 8 + 5 * 6 2 / -

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

S = <>; <6>; <6,8>; <14>; <14,5>; <70>;<70,6>; <70,6,2>; <70,3>; <67>.

Нижче приведена функція eval, що обчислює значення вираження, заданого в масиві m у формі польського інверсного запису, причому m[i]>0 означає ненегативне число, а значення m[i]<0 операції. Як кодування операцій додавання, вирахування, множення і розподіли обрані негативні числа 1, 2, 3, 4. Для організації послідовного збереження стека використовується внутрішній масив stack. Параметрами функції є вхідний масив a і його довжина l.

float eval (float *m, int l) { int p,n,i; float stack[50],c;for(i=0; i < l ;i++) if ((n=m[i])<0) { c="st[p--];" switch(n) { case 1: stack[p]+="c;" break; case 2: stack[p]-="c;" break; case 3: stack[p]*="c;" break; case 4: stack[p]/="c;" } } else stack[++p]="n;" return(stack[p]); }

Розглянемо іншу задачу. Нехай потрібно ввести деяку послідовність символів, що закінчується крапкою, і надрукувати неї в зворотному порядку (тобто якщо на вході буде "ABcEr-1." те на виході повинне бути "1-rEcBA"). Представлена нижче програма спочатку уводить усі символи послідовності, записуючи них у стек, а потім уміст стека друкується в зворотному порядку. Це основна особливість стека - чим пізніше елемент занесений у стек, тим раніш він буде витягнутий зі стека. Реалізація стека виконана в зв'язаному збереженні за допомогою покажчиків p і q на тип, іменований ім'ям STACK.

#include typedef struct st /* ?????????? ???? STACK */ { char ch; struct st *ps; } STACK; main() { STACK *p,*q; char a; p=NULL; do /* ?????????? ????? */ { a=getch(); q=malloc(sizeof(STR1)); q->ps=p; p=q; q->ch=a; } while(a!='.'); do /* ??????? ????? */ { p=q->ps;free(q);q=p; printf("%c",p->ch); } while(p->ps!=NULL); }

Стиснуте й індексне збереження лінійних списків