При рішенні задачі в кожен момент часу маємо упорядкований список 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);

}

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

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

Стиснуте збереження. Нехай у списку B= кілька елементів мають однакове значення V, а список В'= виходить з B заміною кожного елемента Ki на пари Ki'=(і,Ki). Нехай далі B"= - підсписок В', що виходить викреслюванням усіх пар Ki=(і,V). Стиснутим збереженням У є метод збереження В", у якому елементи зі значенням V. Розрізняють послідовне стиснуте збереження і зв'язане стиснуте збереження. Наприклад, для списку B=, що містить кілька вузлів зі значенням Х, послідовного стиснутого і зв'язане стиснуте збереження, з умовчуванням елементів зі значенням Х, представлені на мал.22,23.

Достоїнство стиснутого збереження списку при великому числі елементів зі значенням V полягає в можливості зменшення обсягу пам'яті для його збереження.

Пошук i-го елемента в зв'язаному стиснутому збереженні здійснюється методом повного перегляду, при послідовному збереженні - методом бінарного пошуку.

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

Розглянемо наступну задачу. На вході задані дві послідовності цілих чисел M=, N=, причому 92% елементів послідовності М дорівнюють нулеві. Скласти програму для обчислення суми добутків Mi * Ni, і=1,2,...,10000.

Припустимо, що список М зберігається послідовно стисло в масиві структур m з оголошенням:

struct

{ int nm;

float val; } m[10000];

Для визначення кінця списку додамо ще один елемент із порядковим номером m[j].nm=10001, що називається стопером (stopper) і розташовується за останнім елементом стиснутого збереження списку в масиві m.

Програма для перебування шуканої суми має вигляд:

# include

main()

{ int і,j=0;

float inp,sum=0;

struct /* оголошення масиву */

{ int nm; /* структур */

float val; } m[10000];

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, у підсписку В або від значення визначеної частини компоненти ДО - її ключа.

Розглянемо список B= з елементами

ДО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, то список розділиться на три підсписка:

B1a=<(17,Y),(23,H),(60,I)>,

B2a=<(90,S),(66,T),(77,T)>,

B3a=<(50,U),(88,W),(30,S)>.

Додаючи усюди ще і початкову позицію елемента в списку, одержуємо:

B1a'=<(1,17,Y),(2,23,H),(3,60,I)>,

B2a'=<(4,90,S),(5,66,T),(6,77,T)>,

B3а'=<(7,50,U),(8,88,W),(9,30,S)>.

Якщо як індексну функцію вибрати іншу функцію Gb(K)=1+(поз.K-1)%3, то одержимо списки:

B1b"=<(1,17,Y),(4,90,S),(7,50,U)>,

B2b"=<(2,23,H),(5,66,T),(8,88,U)>,

B3b"=<(3,60,I),(6,77,T),(9,30,S)>.

Тепер для перебування вузла K6 досить переглянути тільки одну з трьох послідовностей (списків). При використанні функції Ga(K) це список B2а', а при функції Gb(K) список B3b".

Для індексної функції Gc(K)=1+K1/100, де K1 - перший компонент елемента ДО, знаходимо:

B1=<(17,Y),(23,H),(60,I),(90,S)>,

B2=<(66,T),(77,T)>,

B3=<(50,U),(88,W)>,

B4=<(30,S)>.

Щоб знайти тут вузол К с першим компонентом-ключем ДО1=77, досить переглянути список B2.

При реалізації індексного збереження застосовується методика А для збереження індексного списку Х (функція Ga(X) ) і методика C для збереження підсписків B1,B2,...,Bm (функція Gc(Bi)), тобто використовується, так називане, A-C індексне збереження.

У практиці часто використовується послідовно-зв'язане індексне збереження. Тому що звичайно довжина списку індексів відома, те його зручно зберігати послідовно, забезпечуючи прямій доступ до будь-якого елемента списку індексів. Підсписки B1,B2,...,Bm зберігаються пов'язано, що спрощує вставку і видалення вузлів(елементів). Зокрема, подібний метод збереження використовується в ЄС ЕОМ для організації, так званих, індексно-послідовних наборів даних, у яких доступ до окремих записів можливий як послідовно, так і за допомогою ключа.

Послідовно-зв‘язане індексне збереження для приведеного приклада зображене на мал.24, де X=.

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

Виберемо як індексну функцію G(K)=K%100+1, а як індексний список Х - масив з 100 елементів. Наступна функція вирішує поставлену задачу:

#include

#include

typedef struct nd

{ float val;

struct nd *n; } ND;

int index (ND *x[100])

{ ND *p;

int i,j=0;

float inp;

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;

p->n=x[i];

x[i]=p;

scanf("%d",&inp);

}

return j;

}

Значенням функції, що повертається, 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.

Практична частина

Лістінг програми

Основний модуль golf.c

#include

#include

#include

#include

#include

#include

#define GRIDSIZE 80 /* Must be bigger than VIEWSIZE */

#define VIEWSIZE 61 /* MUST be odd */

#define DIFF (GRIDSIZE-VIEWSIZE)

#define DEF_DIST -1100

#define DEF_PITCH 122

#define DEF_HEIGHT 120

#define DEF_ROLL 315

#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 SHIFT 14

#define MASK (GRIDSIZE*GRIDSIZE)

/*

#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 void far *view_screen;

extern void far *screen;

extern int sn_tbl[360];

extern unsigned char grid[GRIDSIZE*GRIDSIZE];

extern unsigned rand_seed;

unsigned idx = 0;

extern long pitch_sine;

extern long pitch_cosine;

extern long roll_sine;

extern long roll_cosine;

int num_points = GRIDSIZE*GRIDSIZE;

#define START (DIFF/2)

int gx = START,gy = START;

unsigned char *gp;

int cz = DEF_DIST;

int cy = DEF_HEIGHT;

int roll = DEF_ROLL;

int cpitch = DEF_PITCH;

extern void SetMyMode(void);

extern void ClearMyScreen(void);

extern void Project(void);

extern void SwapScreens(void);

extern void DoPlasma(int,int,int,int);

extern int GetRand(void);

extern unsigned GetGrid(void);

extern void PutGrid(void);

#define _GetGrid(X,Y) (_AX = (X), _BX = (Y), GetGrid())

#define _PutGrid(X,Y,C) { _CX = (C); _AX = (X); _BX = (Y); PutGrid(); }

void SetMode(void)

{

struct REGPACK regs;

regs.r_ax = 0x13;

intr(0x10, ®s);

}

void SetTextMode(void)

{

struct REGPACK regs;

regs.r_ax = 0x3;

intr(0x10, ®s);

}

void SetPalette(void)

{

register int i;

register int j;

#define DEPTH(X) max((((X)*(3-j))/3), 3)

for (j = 0; j<4; j++)

for (i = 0; i<64; i+=4)

{

if (i+j > 0)

{

disable();

outportb(0x3c8, (i >> 2)+64*j);

outportb(0x3c9, 0);

outportb(0x3c9, 0);

outportb(0x3c9, DEPTH(2*i/3));

enable();

}

disable();

outportb(0x3c8, (i >> 2)+64*j+16);

outportb(0x3c9, DEPTH(i/2+10));

outportb(0x3c9, DEPTH(i/4+10));

outportb(0x3c9, DEPTH(i/6+10));

enable();

disable();

outportb(0x3c8, (i >> 2)+64*j+32);

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)));

enable();

disable();

outportb(0x3c8, (i >> 2)+64*j+48);

outportb(0x3c9, DEPTH(i));

outportb(0x3c9, DEPTH(63));

outportb(0x3c9, DEPTH(i));

enable();

}

}

/*

int RandPixel(int x,int y,int x1,int y1,int x2,int y2)

{

int col;

col = (GetRand()%200 - 100) * (abs(x-x1)+abs(y-y1)) / (GRIDSIZE/6)

+((_GetGrid(x1,y1)+_GetGrid(x2,y2)) >> 1);

if (col < 1) col = 1;

if (col > 255) col = 255;

_PutGrid(x,y,col);

return col;

}

*/

/*

void DoPlasma(int x1, int y1, int x2, int y2)

{

int x,y,s,p;

if (x2-x1 <= 1 && y2-y1 <= 1)

return;

x = (x1+x2) >> 1;

y = (y1+y2) >> 1;

if ((p = _GetGrid(x, y1)) == 0)

p = RandPixel(x,y1,x1,y1,x2,y1);

s = p;

if ((p = _GetGrid(x2,y)) == 0)

p = RandPixel(x2,y,x2,y1,x2,y2);

s += p;

if ((p = _GetGrid(x,y2)) == 0)

p = RandPixel(x,y2,x1,y2,x2,y2);

s += p;

if ((p = _GetGrid(x1,y)) == 0)

p = RandPixel(x1,y,x1,y1,x1,y2);

s += p;

if (_GetGrid(x,y) == 0)

_PutGrid(x,y,s >> 2);

DoPlasma(x1,y1,x,y);

DoPlasma(x,y1,x2,y);

DoPlasma(x1,y,x,y2);

DoPlasma(x,y,x2,y2);

}

*/

void BlankGrid(int x1,int y1,int x2,int y2)

{

register int x,y;

for (y = y1; y <= y2; y++)

for (x = x1; x <= x2; x++)

_PutGrid(x,y,0);

}

void NewLand(int x1,int y1,int x2,int y2)

{

unsigned av = 0;

int val;

int num = 0;

if ((val = _GetGrid(x1,y1)) > 0)

{

av += val;

num++;

}

if ((val = _GetGrid(x2,y1)) > 0)

{

av += val;

num++;

}

if ((val = _GetGrid(x2,y2)) > 0)

{

av += val;

num++;

}

if ((val = _GetGrid(x1,y2)) > 0)

{

av += val;

num++;

}

if (!av || GetRand() % 32 == 0)

av = GetRand() % 256;

else

av /= num;

if (_GetGrid(x1,y1) == 0)

_PutGrid(x1,y1, av + (GetRand() % 80 -40));

if (_GetGrid(x2,y1) == 0)

_PutGrid(x2,y1, av + (GetRand() % 80 -40));

if (_GetGrid(x2,y2) == 0)

_PutGrid(x2,y2, av + (GetRand() % 80 -40));

if (_GetGrid(x1,y2) == 0)

_PutGrid(x1,y2, av + (GetRand() % 80 -40));

DoPlasma(x1,y1,x2,y2);

}

void Test(void)

{

register int p;

register int x;

int y;

for (y = 0,p = idx; y < GRIDSIZE; y++)

for (x = 0; x < GRIDSIZE; x++, p = (p+1) % MASK)

C_Plot(x,y,max(grid[p],63) >> 2);

for (x = 0; x < VIEWSIZE; x++)

{

C_Plot(gx+x, gy, 0);

C_Plot(gx+x, gy+VIEWSIZE, 0);

C_Plot(gx, gy+x, 0);

C_Plot(gx+VIEWSIZE, gy+x, 0);

}

/*

for (y = 0, p = gp; y < VIEWSIZE; y++, p += DIFF)

for (x = 0; x < VIEWSIZE; x++,p++)

C_Plot(gx+x,gy+y,*p >> 3);

*/

}

void ClearScr(void)

{

register unsigned i;

for (i = 0; i < (320U*150); i++)

pokeb(0xa000,i,0);

}

void check_gx(void)

{

if (gx < 0)

{

idx = (idx-DIFF/2 + MASK) % MASK;

gx = START-1;

BlankGrid(0,0, DIFF/2-1, GRIDSIZE-1);

NewLand(0,0,DIFF/2,GRIDSIZE/4);

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);

}

else if (gx >= DIFF)

{

idx = (idx+DIFF/2) % MASK;

gx = START+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,

2*GRIDSIZE/4);

NewLand(GRIDSIZE-DIFF/2-1,2*GRIDSIZE/4,GRIDSIZE-1,

3*GRIDSIZE/4);

NewLand(GRIDSIZE-DIFF/2-1,3*GRIDSIZE/4,GRIDSIZE-1,

GRIDSIZE-1);

}

}

void check_gy(void)

{

if (gy < 0)

{

idx = (idx-DIFF/2*GRIDSIZE + MASK) % MASK;

gy = START-1;

BlankGrid(0,0, GRIDSIZE-1, DIFF/2-1);

NewLand(0,0,GRIDSIZE/4,DIFF/2);

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);

}

else if (gy >= DIFF)

{

idx = (idx+DIFF/2*GRIDSIZE) % MASK;

gy = START+1;

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,

2*GRIDSIZE/4,GRIDSIZE-1);

NewLand(2*GRIDSIZE/4,GRIDSIZE-DIFF/2-1,

3*GRIDSIZE/4, GRIDSIZE-1);

NewLand(3*GRIDSIZE/4,GRIDSIZE-DIFF/2-1,

GRIDSIZE-1,GRIDSIZE-1);

}

}

void main(void)

{

int rollspeed = 0;

int xspeed = 0, yspeed = 0;

int i;

rand_seed = (unsigned) time(NULL);

/* rand_seed = 2; */

for (i = 0; i<(360+90); i++)

sn_tbl[i]=(int)(sin((double)i / 180.0*3.14159265) * (double)(1<

NewLand(0,0,GRIDSIZE-1,GRIDSIZE-1);

SetMode();

SetPalette();

// goto skip;

for (;)

{

Test();

switch(getch())

{

case 27:

SetTextMode();

exit(0);

case 'e':

gx--;

check_gx();

break;

case 'r':

gx++;

check_gx();

break;

case 'w':

gy--;

check_gy();

break;

case 's':

gy++;

check_gy();

break;

case ' ':

goto skip;

}

gp = CalcAddress(gx,gy);

while (kbhit())

getch();

}

skip:

;

SetMyMode();

SetPalette();

gp = CalcAddress(gx,gy);

// yspeed = -1;

// rollspeed = (rollspeed+358) % 360;

for (;)

{

if (kbhit())

{

switch(getch())

{

case 27:

SetTextMode();

exit(0);

case 'q':

cz += 50;

break;

case 'a':

cz -= 50;

break;

case 'u':

cy -= 50;

break;

case 'j':

cy += 50;

break;

case 'Q':

cpitch = (cpitch+1) % 360;

break;

case 'A':

cpitch = (cpitch+359) % 360;

break;

case 'E':

if (xspeed > -1) xspeed--;

break;

case 'R':

if (xspeed < 1) xspeed++;

break;

case 'e':

gx--;

break;

case 'r':

gx++;

break;

case 'W':

if (yspeed > -1) yspeed--;

break;

case 'S':

if (yspeed < 1) yspeed++;

break;

case 'w':

gy--;

break;

case 's':

gy++;

break;

case 'i':

roll = (roll+1) % 360;

break;

case 'o':

roll = (roll+359) % 360;

break;

case 'I':

rollspeed = (rollspeed+1) % 360;

break;

case 'O':

rollspeed = (rollspeed+359) % 360;

break;

case ' ':

rollspeed = 0;

xspeed = yspeed = 0;

cz = DEF_DIST;

cy = DEF_HEIGHT;

roll = DEF_ROLL;

cpitch = DEF_PITCH;

break;

}

while (kbhit())

getch();

}

gy += yspeed;

gx += xspeed;

check_gx();

check_gy();

gp = CalcAddress(gx,gy);

roll = (roll+rollspeed) % 360;

roll_sine = sine(roll);

roll_cosine = cosine(roll);

pitch_sine = sine(cpitch);

pitch_cosine = cosine(cpitch);

ClearMyScreen();

Project();

SwapScreens();

}

}

Робота з програмою

Далі наведено три скріншоти, які описують процес удару по м”ячику.

Висновки

Була розроблена комп’ютерна гра “Гольф 3D” з елементами трьохвимірної графіки на основі функцій прямого доступу до відеопам’яті в системі MS DOS. При розробці програми використовувався пакет BORLAND C++ 3.0 та бібліотека BGI.

Література.

1. Касаткин А.И., Вальвачев А.Н. Профессиональное прогрпммирование на языке Си. Мн., 1992. 240 С.

2. Нейбауэр А. Моя первая программа на С/С++. П., 1995. 368 С.

3. Бруно Бабэ. Просто и ясно о Borland C++. М., 1996. 400 С.

4. Шамас Н.К. Основы С++ и обьектно-ориентированного программирования. К., 1996. 448 С.

5. Справочник по классам Borland C++ 4.0. К., 1994. 256 С.

6. ObjectWindows для C++. К., 1993., 208 С.

7. Том Сван. Программирование для Windows в Borland C++. М., 480 С.

8. Н. Барканати. Программирование игр для Windows на Borland C++. М., 1994. 512 С.