КАФЕДРА
Дата ___________________
Тема:
аркадна гра “гольф” з елементами трьох-вимірної поверхні
“____” __________ 2007р.
Робота захищена
“____” __________ 2007р.
з оцінкою
_____________________
Підписи членів комісії
Зміст
Вступ
Поставлена задача написати просту аркадну гру “гольф” з елементами трьох-вимірної поверхні. Для створення актуального програмного продукту на цю тематику був обраний шлях написання універсальної програми – яка б могла запускатись з мінімальними потребами до пам”яті та інших ресурсів. Тому в якості засобу розробки був обраний старий компілятор BORLANDC++ 3.0 і прийняте рішення не використовувати графічні функції Windows.
Теорія
Лінійний список - це кінцева послідовність однотипних елементів (вузлів), можливо, з повтореннями. Кількість елементів у послідовності називається довжиною списку, причому довжина в процесі роботи програми може змінюватися.
Лінійний список F, що складається з елементів D1,D2,...,Dn, записують у виді послідовностізначень укладеної в кутові дужки F=, або представляють графічно.
Наприклад, F1=<2,3,1>,F2=<7,7,7,2,1,12>, F3=<>. Довжина списків F1, F2, F3 дорівнює відповідно 3,6,0.
При роботі зі списками на практиці найчастіше приходиться виконувати наступні операції:
- знайти елемент із заданою властивістю;
- визначити перший елемент у лінійному списку;
- уставити додатковий елемент до або після зазначеного вузла;
- виключити визначений елемент зі списку;
- упорядкувати вузли лінійного списку у визначеному порядку.
У реальних мовах програмування немає якої-небудь структури даних для представлення лінійного списку так, щоб усі зазначені операції над ним виконувалися в однаковому ступені ефективно. Тому при роботі з лінійними списками важливим є представлення використовуваних у програмі лінійних списків таким чином, щоб була забезпечена максимальна ефективність і за часом виконання програми, і по обсязі необхідної пам'яті.
Методи збереження лінійних списків розділяються на методи послідовного і зв'язаного збереження. Розглянемо найпростіші варіанти цих методів для списку з цілими значеннями F=<7,10>.
При послідовному збереженні елементи лінійного списку розміщаються в масиві d фіксованих розмірів, наприклад, 100, і довжина списку вказується в перемінної l, тобто в програмі необхідно мати оголошення виду
float d[100]; int l;Розмір масиву 100 обмежує максимальні розміри лінійного списку. Список F у масиві d формується так:
d[0]=7; d[1]=10; l=2;При зв'язаному збереженні як елементи збереження використовуються структури, зв'язані по одній з компонентів у ланцюжок, на початок якої (першу структуру) указує покажчик dl. Структура утворюючий елемент збереження, повинна крім відповідного елемента списку містити і покажчик на сусідній елемент збереження.
Опис структури і покажчика в цьому випадку може мати вид:
typedef struct snd /* структура елемента збереження */{ float val; /* елемент списку */struct snd *n ; /* покажчик на елемент збереження */} DL;DL *p; /* покажчик поточного елемента */DL *dl; /* покажчик на початок списку */Для виділення пам'яті під елементи збереження необхідно користуватися функцією malloc(sizeof(DL)) або calloc(l,sizeof(DL)). Формування списку в зв'язаному збереженні може здійснюється операторами:
p=malloc(sizeof(DL));p->val=10; p->n=NULL;dl=malloc(sizeof(DL));dl->val=7; dl->n=p;В останньому елементі збереження (кінець списку) покажчик на сусідній елемент має значення NULL. Одержуваний список зображений на мал.2.
При виборі методу збереження лінійного списку варто враховувати, які операції будуть виконуватися і з якою частотою, час їхнього виконання й обсяг пам'яті, необхідний для збереження списку.
Нехай мається лінійний список з цілими значеннями і для його збереження використовується масив d (з числом елементів 100), а кількість елементів у списку вказується перемінної l. Реалізація зазначених раніше операцій над списком представляється наступними фрагментами програм які використовують оголошення:
float d[100]; int i,j,l; 1) печатка значення першого елемента (вузла) if (і<0 || і>l) printf("\n немає елемента"); else printf("d[%d]=%f ",і,d[і]); 2) видалення елемента, що випливає за i-тым вузлом if (і>=l) printf("\n немає наступного "); l--; for (j=і+1;j<="1" if вузла i-того сусідів обох печатка 3) d[j]="d[j+1];">=l) printf("\n немає сусіда"); else printf("\n %d %d",d[і-1],d[і+1]); 4) додавання нового елемента new за i-тым вузлом if (і==l || і>l) printf("\n не можна додати"); else { for (j=l; j>i+1; j--) d[j+1]=d[j]; d[i+1]=new; l++; } 5) часткове упорядкування списку з елементами ДО1,ДО2,...,Кl у список K1',K2',...,Ks,K1,Kt",...,Kt", s+t+1=l так, щоб K1'= K1. { int t=1; float aux; for (i=2; i<=l; i++) if (d[i]=2; j--) d[j]=d[j-1]; t++; d[i]=aux; } }Кількість дій Q, необхідних для виконання приведених операцій над списком, визначаєтьсяспіввідношеннями: для операцій 1 і 2 - Q=1; для операцій 3,4 - Q=l; для операції 5 - Q=l*l.
Помітимо, що взагалі операцію 5 можна виконати при кількості дій порядку l, а операції 3 і 4 для включення і виключення елементів наприкінці списку, що часто зустрічаються при роботі зі стеками, - при кількості дій 1.
Більш складна організація операцій потрібно при розміщенні в масиві d декількох списків, або при розміщенні списку без прив'язки його початку до першого елемента масиву.
При простому зв'язаному збереженні кожен елемент списку являє собою структуру nd, що складається з двох елементів: val - призначений для збереження елемента списку, n - для покажчика на структуру, що містить наступний елемент списку. На перший елемент списку вказує покажчик dl. Для всіх операцій над списком використовується опис:
typedef struct nd { float val; struct nd * n; } ND; int i,j; ND * dl, * r, * p;Для реалізації операцій можуть використовуватися наступні фрагменти програм:
1) печатка значення i-го елемента
r=dl;j=1; while(r!=NULL && j++n ; if (r==NULL) printf("\n немає вузла %d ",i); else printf("\n елемент %d дорівнює %f ",i,r->val);2) печатка обох сусідів вузла(елемента), обумовленого покажчиком p (див. мал.4)
if((r=p->n)==NULL) printf("\n немає сусіда праворуч"); else printf("\n сусід праворуч %f", r->val); if(dl==p) printf("\n немає сусіда ліворуч" ); else { r=dl; while( r->n!=p ) r=r->n; printf("\n лівий сусід %f", r->val); }3) видалення елемента, що випливає за вузлом, на який указує р (див. мал.5)
if ((r=p->n)==NULL) printf("\n немає наступного"); p->n=r->n; free(r->n);4) вставка нового вузла зі значенням new за елементом, визначеним покажчиком р (див. мал.6)
r=malloc(1,sizeof(ND));r->n=p->n; r->val=new; p->n=r;5) часткове упорядкування списку в послідовність значень , s+t+1=l, так що K1'=K1; після упорядкування покажчик v указує на елемент K1' (див. мал.7)
ND *v; float k1; k1=dl->val; r=dl; while( r->n!=NULL ) { v=r->n; if (v->valn=v->n; v->n=dl; dl=v; } else r=v; }Кількість дій, необхідних для виконання зазначених операцій над списком у зв'язаному збереженні, оцінюється співвідношеннями: для операцій 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); }У залежності від методу доступу до елементів лінійного списку розрізняють різновиду лінійних списків називані стеком, чергою і двосторонньою чергою.