Аркадна гра "гольф" з елементами трьохвимірної поверхні - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Аркадна гра "гольф" з елементами трьохвимірної поверхні

Засоби організації збереження і обробки даних для графічних програм. Операції зі списками при послідовному збереженні, при зв'язному збереженні. Реалізація стеков і черг у програмі. Стиснуте й індексне збереження лінійних списків. Основний модуль golf.c.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Лінійний список - це кінцева послідовність однотипних елементів (вузлів), можливо, з повтореннями. Кількість елементів у послідовності називається довжиною списку, причому довжина в процесі роботи програми може змінюватися.
Лінійний список 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, тобто в програмі необхідно мати оголошення виду
Розмір масиву 100 обмежує максимальні розміри лінійного списку. Список F у масиві d формується так:
При зв'язаному збереженні як елементи збереження використовуються структури, зв'язані по одній з компонентів у ланцюжок, на початок якої (першу структуру) указує покажчик dl. Структура утворюючий елемент збереження, повинна крім відповідного елемента списку містити і покажчик на сусідній елемент збереження.
Опис структури і покажчика в цьому випадку може мати вид:
typedef struct snd /* структура елемента збереження */
struct snd *n ; /* покажчик на елемент збереження */
DL *p; /* покажчик поточного елемента */
DL *dl; /* покажчик на початок списку */
Для виділення пам'яті під елементи збереження необхідно користуватися функцією malloc(sizeof(DL)) або calloc(l,sizeof(DL)). Формування списку в зв'язаному збереженні може здійснюється операторами:
В останньому елементі збереження (кінець списку) покажчик на сусідній елемент має значення NULL. Одержуваний список зображений на мал.2.
При виборі методу збереження лінійного списку варто враховувати, які операції будуть виконуватися і з якою частотою, час їхнього виконання й обсяг пам'яті, необхідний для збереження списку.
Нехай мається лінійний список з цілими значеннями і для його збереження використовується масив d (з числом елементів 100), а кількість елементів у списку вказується перемінної l. Реалізація зазначених раніше операцій над списком представляється наступними фрагментами програм які використовують оголошення:
1) печатка значення першого елемента (вузла)
if (і<0 || і>l) printf("\n немає елемента");
2) видалення елемента, що випливає за i-тым вузлом
if (і>=l) printf("\n немає наступного ");
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 не можна додати");
{ for (j=l; j>i+1; j--) d[j+1]=d[j];
5) часткове упорядкування списку з елементами ДО1,ДО2,...,Кl у
список K1',K2',...,Ks,K1,Kt",...,Kt", s+t+1=l так, щоб K1'= K1.
for (i=2; i<=l; i++) if (d[i]=2; j--) d[j]=d[j-1];
Кількість дій Q, необхідних для виконання приведених операцій над списком, визначаєтьсяспіввідношеннями: для операцій 1 і 2 - Q=1; для операцій 3,4 - Q=l; для операції 5 - Q=l*l.
Помітимо, що взагалі операцію 5 можна виконати при кількості дій порядку l, а операції 3 і 4 для включення і виключення елементів наприкінці списку, що часто зустрічаються при роботі зі стеками, - при кількості дій 1.
Більш складна організація операцій потрібно при розміщенні в масиві d декількох списків, або при розміщенні списку без прив'язки його початку до першого елемента масиву.
При простому зв'язаному збереженні кожен елемент списку являє собою структуру nd, що складається з двох елементів: val - призначений для збереження елемента списку, n - для покажчика на структуру, що містить наступний елемент списку. На перший елемент списку вказує покажчик dl. Для всіх операцій над списком використовується опис:
Для реалізації операцій можуть використовуватися наступні фрагменти програм:
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 немає сусіда ліворуч" );
printf("\n лівий сусід %f", r->val);
3) видалення елемента, що випливає за вузлом, на який указує р (див. мал.5)
if ((r=p->n)==NULL) printf("\n немає наступного");
4) вставка нового вузла зі значенням new за елементом, визначеним покажчиком р (див. мал.6)
5) часткове упорядкування списку в послідовність значень , s+t+1=l, так що K1'=K1; після упорядкування покажчик v указує на елемент K1' (див. мал.7)
Кількість дій, необхідних для виконання зазначених операцій над списком у зв'язаному збереженні, оцінюється співвідношеннями: для операцій 1 і 2 - Q=l; для операцій 3 і 4 - Q=1; для операції 5 - Q=l.
Зв'язане збереження лінійного списку називається списком із двома зв'язками або двузв`язним списком, якщо кожен елемент збереження має два компоненти покажчика (посилання на попередній і наступний елементи лінійного списку).
У програмі двузв`язний список можна реалізувати за допомогою описів:
{ float val; /* значення елемента */
struct ndd * n; /* покажчик на наступний елемент */
struct ndd * m; /* покажчик на попередній елемент */
Графічна інтерпретація методу зв'язаного збереження списку F=<2,5,7,1> як списку з двома зв'язками приведена на мал.8.
Вставка нового вузла зі значенням new за елементом, обумовленим покажчиком p, здійснюється за допомогою операторів:
Видалення елемента, що випливає за вузлом, на який указує p
Зв'язане збереження лінійного списку називається циклічним списком, якщо його останній указує на перший елемент, а покажчик dl - на останній елемент списку.
Схема циклічного збереження списку F=<2,5,7,1> приведена на мал.9.
При рішенні конкретних задач можуть виникати різні види зв'язаного збереження.
Нехай на вході задана послідовність цілих чисел B1,B2,...,Bn з інтервалу від 1 до 9999, і нехай Fi (1.
Розглянемо програму рішення поставленої задачі, у якій покажчики dl, r, p, v мають наступне значення: dl указує початок списку; p, v - два сусідніх вузли; r фіксує вузол, що містить чергове введене значення in.
ND *arrange() /* формування упорядкованого списку */
r->val=10000; r->n=NULL; /* останній елемент */
У залежності від методу доступу до елементів лінійного списку розрізняють різновиду лінійних списків називані стеком, чергою і двосторонньою чергою.
Стек - це кінцева послідовність деяких однотипних елементів - скалярних перемінних, масивів, структур або об'єднань, серед яких можуть бути й однакові. Стік позначається у виді: S= і представляє динамічну структуру даних; її кількість елементів заздалегідь не вказується й у процесі роботи, як правило змінюється. Якщо в стеці елементів ні, то він називається порожнім і позначається S=<>.
Припустимими операціями над стеком є:
- перевірка стека на порожнечу S=<>,
- додавання нового елемента Sn+1 у кінець стека - перетворення < S1,...,Sn> у < S1,...,Sn+1>;
- вилучення останнього елемента зі стека - перетворення < S1,...,Sn-1,Sn> у < S1,...,Sn-1>;
- доступ до його останнього елемента Sn, якщо стік не порожній.
Таким чином, операції додавання і видалення елемента, а також доступу до елемента виконуються тільки наприкінці списку. Стік можна представити як стопку книг на столі, де додавання або узяття нової книги можливо тільки зверху.
Черга - це лінійний список, де елементи віддаляються з початку списку, а додаються наприкінці списку (як звичайна черга в магазині).
Двостороння черга - це лінійний список, у якого операції додавання і видалення елементів і доступу до елементів можливі як спочатку так і наприкінці списку. Таку чергу можна представити як послідовність книг на полку, так що доступ до них можливий з обох кінців.
Реалізація стеков і черг у програмі може бути виконана у виді послідовного або зв'язаного збереження. Розглянемо приклади організації стека цими способами.
Однієї з форм представлення виражень є польський інверсний запис, що задає вираження так, що операції в ньому записуються в порядку виконання, а операнди знаходяться безпосередньо перед операцією.
у польському інверсному записі має вигляд
Особливість такого запису полягає в тому, що значення вираження можна обчислити за один перегляд запису ліворуч праворуч, використовуючи стек, що до цього повинний бути порожній. Кожне нове число заноситься в стек, а операції виконуються над верхніми елементами стека, заміняючи ці елементи результатом операції. Для приведеного вираження динаміка зміни стека буде мати вигляд
S = <>; <6>; <6,8>; <14>; <14,5>; <70>;
Нижче приведена функція 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.
typedef struct st /* оголошення типу STACK */
При збереженні великих обсягів інформації у формі лінійних списків небажано зберігати елементи з однаковим значенням, тому використовують різні методи стиску списків.
Стиснуте збереження. Нехай у списку B= кілька елементів мають однакове значення V, а список В'= виходить з B заміною кожного елемента Ki на пари Ki'=(і,Ki). Нехай далі B"= - підсписок В', що виходить викреслюванням усіх пар Ki=(і,V). Стиснутим збереженням У є метод збереження В", у якому елементи зі значенням V. Розрізняють послідовне стиснуте збереження і зв'язане стиснуте збереження. Наприклад, для списку B=, що містить кілька вузлів зі значенням Х, послідовного стиснутого і зв'язане стиснуте збереження, з умовчуванням елементів зі значенням Х, представлені на мал.22,23.
Достоїнство стиснутого збереження списку при великому числі елементів зі значенням V полягає в можливості зменшення обсягу пам'яті для його збереження.
Пошук i-го елемента в зв'язаному стиснутому збереженні здійснюється методом повного перегляду, при послідовному збереженні - методом бінарного пошуку.
Переваги і недоліки послідовного стиснутого і зв'язаного стиснутого аналогічні перевагам і недолікам послідовного і зв'язаного збереження.
Розглянемо наступну задачу. На вході задані дві послідовності цілих чисел M=, N=, причому 92% елементів послідовності М дорівнюють нулеві. Скласти програму для обчислення суми добутків Mi * Ni, і=1,2,...,10000.
Припустимо, що список М зберігається послідовно стисло в масиві структур m з оголошенням:
Для визначення кінця списку додамо ще один елемент із порядковим номером m[j].nm=10001, що називається стопером (stopper) і розташовується за останнім елементом стиснутого збереження списку в масиві m.
Програма для перебування шуканої суми має вигляд:
for(i=0;i<10000;i++) /* читання списку M */ { scanf("%f",&inp); if (inp!="0)" { m[j].nm="i;" m[j++].val="inp;" } } m[j].nm="10001;" /* stopper */ for(i="0,j=0;" i<10000; i++) { scanf("%f",&inp); /* читання списку N */ if(i="=m[j].nm)" /* обчислення суми */ sum+="m[j++].val*inp;" } printf( "сума добутків Mi*Ni дорівнює %f",sum); }
Індексне збереження використовується для зменшення часу пошуку потрібного елемента в списку і полягає в наступному. Вихідний список B = розбивається на трохи підсписків У1,У2, ...,Вм таким чином, що кожен елемент списку В попадає тільки в один з підсписків, і додатково використовується індексний список з М елементами, що вказують на початок списків У1,У2, ...,Ум.
Вважається, що список зберігається індексно за допомогою підсписків B1,B2, ...,Bm і індексного списку X = , де ADGj - адреса початку підсписка Bj, j=1,M.
При індексному збереженні елемент До підсписка Bj має індекс j. Для одержання індексного збереження вихідний список У часто перетвориться в список В' шляхом включення в кожен вузол ще і його порядкового номера у вихідному списку В, а в j-ий елемент індексного списку Х, крім ADGj, може включатися деяка додаткова інформація про підсписок Bj. Розбивка списку В на підсписки здійснюється так, щоб всі елементи В, що володіють визначеною властивістю Рj, попадали в один підсписок Bj.
Достоїнством індексного збереження є те, що для перебування елемента К с заданою властивістю Pj досить переглянути тільки елементи підсписка Bj; його початок знаходиться по індексному списку Х, тому що для кожного ДО, що належить Bi, при і не рівному j властивість Pj не виконується.
У розбивці В часто використовується індексна функція G(K), що обчислює по елементі До його індекс j, тобто G(K)=j. Функція G звичайно залежить від позиції ДО, що позначається поз.K, у підсписку В або від значення визначеної частини компоненти ДО - її ключа.
ДО1=(17,Y), K2=(23,H), K3=(60,I), K4=(90,S), K5=(66,T),
K6=(77,T), K7=(50,U), K8=(88,W), K9=(30,S).
Якщо для розбивки цього списку на підсписки як індексну функцію взяти Ga(K)=1+(поз.K-1)/3, то список розділиться на три підсписка:
Додаючи усюди ще і початкову позицію елемента в списку, одержуємо:
Якщо як індексну функцію вибрати іншу функцію Gb(K)=1+(поз.K-1)%3, то одержимо списки:
Тепер для перебування вузла K6 досить переглянути тільки одну з трьох послідовностей (списків). При використанні функції Ga(K) це список B2а', а при функції Gb(K) список B3b".
Для індексної функції Gc(K)=1+K1/100, де K1 - перший компонент елемента ДО, знаходимо:
Щоб знайти тут вузол К с першим компонентом-ключем ДО1=77, досить переглянути список B2.
При реалізації індексного збереження застосовується методика А для збереження індексного списку Х (функція Ga(X) ) і методика C для збереження підсписків B1,B2,...,Bm (функція Gc(Bi)), тобто використовується, так називане, A-C індексне збереження.
У практиці часто використовується послідовно-зв'язане індексне збереження. Тому що звичайно довжина списку індексів відома, те його зручно зберігати послідовно, забезпечуючи прямій доступ до будь-якого елемента списку індексів. Підсписки B1,B2,...,Bm зберігаються пов'язано, що спрощує вставку і видалення вузлів(елементів). Зокрема, подібний метод збереження використовується в ЄС ЕОМ для організації, так званих, індексно-послідовних наборів даних, у яких доступ до окремих записів можливий як послідовно, так і за допомогою ключа.
Послідовно-зв`язане індексне збереження для приведеного приклада зображене на мал.24, де X=.
Розглянемо ще одну задачу. На вході задана послідовність цілих позитивних чисел, що закінчується нулем. Скласти процедуру для введення цієї послідовності й організації її індексного збереження таким чином, щоб числа, що збігаються в двох останніх цифрах, містилися в один підсписок.
Виберемо як індексну функцію G(K)=K%100+1, а як індексний список Х - масив з 100 елементів. Наступна функція вирішує поставлену задачу:
for (i=0; i<100; i++) x[i]="NULL;" scanf("%d",&inp); while (inp!="0)" { j++; p="malloc(sizeof(ND));" i="inp%100+1;" p->val=inp;
Значенням функції, що повертається, index буде число оброблених елементів списку.
Для індексного списку також може використовуватися індексне збереження. Нехай, наприклад, мається список B= з елементами
K1=(338,Z), K2=(145,A), K3=(136,H), K4=(214,I), K5 =(146,C),
K6=(334,Y), K7=(333,P), K8=(127,G), K9=(310,O), K10=(322,X).
Потрібно розділити його на сімох підсписків, тобто X= таким чином, щоб у кожен список B1,B2,...,B7 попадали елементи, що збігаються в першому компоненті першими двома цифрами. Список Х, у свою чергу, будемо індексувати списком індексів Y=, щоб у кожен список Y1,Y2,Y3 попадали елементи з X, у яких у першому компоненті збігаються перші цифри. Якщо списки B1,B2,...,B7 зберігати пов'язано, а списки індексів X,Y індексно, те такий спосіб збереження списку B називається зв'язаним індексним збереженням. Графічне зображення цього збереження приведене на мал.25.
#define GRIDSIZE 80 /* Must be bigger than VIEWSIZE */
#define VIEWSIZE 61 /* MUST be odd */
#define sine(X) ((long)(sn_tbl[X]))
#define cosine(X) ((long)(sn_tbl[((X)+90) % 360]))
#define C_Plot(X,Y,C) pokeb(0xa000, (X) + 320U*(Y), C)
#define GetGrid(X,Y) ((unsigned)grid[((X) + GRIDSIZE*(Y) +idx) % MASK])
#define PutGrid(X,Y,C) grid[((X) + GRIDSIZE*(Y) +idx) % MASK] = (unsigned char)(C)
#define CalcAddress(X,Y) (&grid[((X) + GRIDSIZE*(Y) + idx) % MASK])
extern unsigned char grid[GRIDSIZE*GRIDSIZE];
int num_points = GRIDSIZE*GRIDSIZE;
extern void DoPlasma(int,int,int,int);
#define _GetGrid(X,Y) (_AX = (X), _BX = (Y), GetGrid())
#define _PutGrid(X,Y,C) { _CX = (C); _AX = (X); _BX = (Y); PutGrid(); }
#define DEPTH(X) max((((X)*(3-j))/3), 3)
outportb(0x3c9, DEPTH(max(63/2+10-i,0)));
outportb(0x3c9, DEPTH(min(64/4+10+3*i/4,63)));
outportb(0x3c9, DEPTH(max(63/6+10-i,0)));
int RandPixel(int x,int y,int x1,int y1,int x2,int y2)
col = (GetRand()%200 - 100) * (abs(x-x1)+abs(y-y1)) / (GRIDSIZE/6)
+((_GetGrid(x1,y1)+_GetGrid(x2,y2)) >> 1);
void DoPlasma(int x1, int y1, int x2, int y2)
void BlankGrid(int x1,int y1,int x2,int y2)
void NewLand(int x1,int y1,int x2,int y2)
_PutGrid(x1,y1, av + (GetRand() % 80 -40));
_PutGrid(x2,y1, av + (GetRand() % 80 -40));
_PutGrid(x2,y2, av + (GetRand() % 80 -40));
_PutGrid(x1,y2, av + (GetRand() % 80 -40));
for (y = 0,p = idx; y < GRIDSIZE; y++)
for (x = 0; x < GRIDSIZE; x++, p = (p+1) % MASK)
for (y = 0, p = gp; y < VIEWSIZE; y++, p += DIFF)
BlankGrid(0,0, DIFF/2-1, GRIDSIZE-1);
NewLand(0,GRIDSIZE/4,DIFF/2,2*GRIDSIZE/4);
NewLand(0,2*GRIDSIZE/4,DIFF/2,3*GRIDSIZE/4);
NewLand(0,3*GRIDSIZE/4,DIFF/2,GRIDSIZE-1);
BlankGrid(GRIDSIZE-DIFF/2,0, GRIDSIZE-1, GRIDSIZE-1);
NewLand(GRIDSIZE-DIFF/2-1,0,GRIDSIZE-1,GRIDSIZE/4);
NewLand(GRIDSIZE-DIFF/2-1,GRIDSIZE/4,GRIDSIZE-1,
NewLand(GRIDSIZE-DIFF/2-1,2*GRIDSIZE/4,GRIDSIZE-1,
NewLand(GRIDSIZE-DIFF/2-1,3*GRIDSIZE/4,GRIDSIZE-1,
idx = (idx-DIFF/2*GRIDSIZE + MASK) % MASK;
BlankGrid(0,0, GRIDSIZE-1, DIFF/2-1);
NewLand(GRIDSIZE/4,0,2*GRIDSIZE/4,DIFF/2);
NewLand(2*GRIDSIZE/4,0,3*GRIDSIZE/4,DIFF/2);
NewLand(3*GRIDSIZE/4,0,GRIDSIZE-1,DIFF/2);
idx = (idx+DIFF/2*GRIDSIZE) % MASK;
BlankGrid(0,GRIDSIZE-DIFF/2,GRIDSIZE-1, GRIDSIZE-1);
NewLand(0,GRIDSIZE-DIFF/2-1,GRIDSIZE/4,GRIDSIZE-1);
NewLand(GRIDSIZE/4,GRIDSIZE-DIFF/2-1,
NewLand(2*GRIDSIZE/4,GRIDSIZE-DIFF/2-1,
NewLand(3*GRIDSIZE/4,GRIDSIZE-DIFF/2-1,
sn_tbl[i]=(int)(sin((double)i / 180.0*3.14159265) * (double)(1<Аркадна гра "гольф" з елементами трьохвимірної поверхні курсовая работа. Программирование, компьютеры и кибернетика.
Курсовая работа по теме История земельных отношений в России
Контрольная работа по теме Адміністративно-правові норми
Комплекс Упражнений Для Утренней Зарядки Реферат
Реферат: Бургундский округ
Гносеологиялық Оптимизм Эссе
Реферат На Тему Моделирование Систем Знаний, Необходимых Для Расследования Фальшивомонетничества
Добролюбов Собрание Сочинений
Уроки Чернобыля Реферат
Объем Зимнего Сочинения
Лекция по теме Особенности изучения тем 'Внутренняя энергия', 'Работа', 'Количество теплоты' раздела 'Термодинамика'
Структура Культурологии Реферат
Учебное пособие: Экономическая теория
Реферат: Fried Green Tomatoes Human Nature Essay Research
Курсовая Работа На Тему Конфлікти І Методи Їх Вирішення При Реалізації Інноваційних Проектів
Доклад: Синклер, Малькольм
Реферат: Economic Report Of Ford Essay Research Paper
Книга: Ювенильное море
Реферат по теме Первые декреты Советской власти
Дипломная работа по теме Керамічна віцьба
Гагарин Реферат 5 Класс
Шляхи вдосконалення правового регулювання місцевого самоврядування в Україні - Государство и право дипломная работа
Глобализация - Международные отношения и мировая экономика реферат
Основы юрислингвистики - Государство и право контрольная работа