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

⇐ ПредыдущаяСтр 2 из 2

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

Стиснуте збереження. Нехай у списку 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 <time.h>

#include <stdlib.h>

#include <dos.h>

#include <conio.h>

#include <math.h>

#include <malloc.h>

#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, &regs);

}

void SetTextMode(void)

{

struct REGPACK regs;

regs.r_ax = 0x3;

intr(0x10, &regs);

}

void SetPalette(void)

{

#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, 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)

{

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)

{

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)

{

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

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 С.

Дата добавления: 2019-09-02; просмотров: 143; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!