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

Рис.12.

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

Виберемо як індексну функцію 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.

Рис.13. зв'язане індексне збереження списку.

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

Результатом нашої роботи є програмний комплекс для роботи (розробки) візитних карток (мал. 1). Для економії часу при розробці програми ми використали деякі вже готові функції для роботи з графікою.

Мал. 1. Лістинг модуля функцій для роботи з графікою.

Основною частиною програми є модуль для роботи з графічним форматом BMP (лістинг 1).

Лістинг 1.

/* windows bmp format image storage */

BMPsave(int x,int y,int x1,int y1,char a[])

{

struct bmp

{unsigned char name[3];

unsigned char dummy[15];

unsigned int x;

unsigned char dummy1[2];

unsigned int y;

unsigned char dummy2[1];

}bmphead;

FILE *fp,*fq;

int xlen,ylen,i,j,count;

unsigned char c,ch;

fp=fopen(a,"wb");

fq=fopen("electron.bmp","rb");

/*fq=fopen("electron.bmp","rb");*/

if (fp==NULL) return(-1);

fread(&bmphead,sizeof(struct bmp),1,fq);

xlen=x1-x+1;

ylen=y1-y+1;

bmphead.x=xlen;

bmphead.y=ylen;

fwrite(&bmphead,sizeof(struct bmp),1,fp);

for(i=0;i<=1052;i++)

{

fread(&ch,1,1,fq);

fwrite(&ch,1,1,fp);

}

fclose(fq);

/*hidemouse();*/

count=0;

for(j=y1;j>=y;j--)

{

/*setcolor(BLUE);

line(201+count,426,201+count,444);*/

count++;

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

{c=getpixel(i,j);

switch(c)

{

case 0: c=0;break;

case 1: c=12;break;

case 2: c=4;break;

case 3: c=5;break;

case 4: c=16;break;

case 5: c=7;break;

case 6: c=13;break;

case 7: c=15;break;

case 8:c = 1;break;

case 9:c=10;break;

case 10: c=18;break;

case 11: c=24;break;

case 12: c=2;break;

case 13: c=21;break;

case 14: c=22;break;

case 15: c=14;break;

}

fwrite(&c,1,1,fp);

}

fwrite(&c,1,1,fp);

c=0;

fwrite(&c,1,1,fp);

}

count--;

/*setcolor(LIGHTGRAY);

for(i=426;i<=444;i++)

line(201,i,201+count,i);*/

/*showmouse();*/

fclose(fp);

return(0);

}

/* windows bmp format image retrieval */

BMPload(int x,int y,char a[])

{

struct bmp

{unsigned char name[3];

unsigned char dummy[15];

unsigned int x;

unsigned char dummy1[2];

unsigned int y;

unsigned char dummy2[1];

}bmphead;

FILE *fp,*fq;

int xlen,ylen,i,j,diff,count;

unsigned char c,ch;

fp=fopen(a,"rb");

if (fp==NULL) return(-1);

fread(&bmphead,sizeof(struct bmp),1,fp);

if (!(bmphead.name[0]=='B' && bmphead.name[1]=='M'))

{fclose(fp);

return(-2);

}

if (bmphead.name[2]!=250 && bmphead.name[2]!=70)

{fclose(fp);

return(-3);

}

if (bmphead.x>600 || bmphead.y>400)

{fclose(fp);

return(-4);

}

for(i=0;i<=1052;i++)

{

fread(&ch,1,1,fp);

}

/*hidemouse();*/

if (bmphead.name[2]==250) diff=1;

else

if (bmphead.name[2]==70) diff=0;

count=0;

/*hidemouse();*/

/*setcolor(WHITE);

for(i=82;i<=getmaxx()-12;i++)

line(i,47,i,getmaxy()-72); */

for(j=y+bmphead.y-2;j>=y;j--)

{

/*setcolor(BLUE);

line(201+count,426,201+count,444);*/

count++;

for(i=x;i<x+bmphead.x+diff;i++)

{

fread(&c,1,1,fp);

switch(c)

{

case 0: c=0;break;

case 12: c=1;break;

case 4: c=2;break;

case 5: c=3;break;

case 16: c=4;break;

case 7: c=5;break;

case 13: c=6;break;

case 15: c=7;break;

case 1:c = 8;break;

case 10:c=9;break;

case 18: c=10;break;

case 24: c=11;break;

case 2: c=12;break;

case 21: c=13;break;

case 22: c=14;break;

case 14: c=15;break;

}

putpixel(i-100,j-50,c);

}

if (bmphead.name[2]==250)

fread(&c,1,1,fp);

}

count--;

/*setcolor(LIGHTGRAY);

for(i=426;i<=444;i++)

line(201,i,201+count,i);*/

/* showmouse();*/

fclose(fp);

return(0);

}

Інтерфейс програми базується на роботі з мишкою та програмним інтерфейсом користувача (Лістинг 2).

Лістинг 2.

class mouse

{

private:

union REGS i,o;

struct SREGS s;

public:

mouse()

{

initmouse();

showmouseptr();

}

void initmouse()

{

i.x.ax=0;

int86(0x33,&i,&o);

}

void showmouseptr()

{

i.x.ax=1;

int86(0x33,&i,&o);

}

void hidemouseptr()

{

i.x.ax=2;

int86(0x33,&i,&o);

}

void getmousepos(int& button,int& x,int& y)

{

i.x.ax=3;

int86(0x33,&i,&o);

button= o.x.bx;

x=o.x.cx;

y=o.x.dx;

}

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

{

i.x.ax=7;

i.x.cx=x1;

i.x.dx=x2;

int86(0x33,&i,&o);

i.x.ax=8;

i.x.cx=y1;

i.x.dx=y2;

int86(0x33,&i,&o);

}

void changemouseptr(int mark[50],int xstart,int ystart)

{

i.x.ax=9;

i.x.bx=xstart;

i.x.cx=ystart;

i.x.dx=(int)mark;

segread(&s);

s.es=s.ds;

int86x(0x33,&i,&i,&s);

}

};

Головний модуль програми відповідає за управління всіма цими компонентами (лістинг 3).

Лістинг 3.

/* FILE NO: A

auxillary file for img3.cpp ie- Imager 3.1

*/

void toolset(int);

void lift(int);

int imagearea();

void fillwindow();

void back(int,int,int,int,int);

void backtotal(int,int,int,int,int);

void myrect(int,int,int,int);

void ba(int,int,int,int,int);

void invertcolors();

void fliphorizontal();

void flipvertical();

void aboutwindow();

void textgetter(char *);

void saveimage(int,int,int,int,char *);

void loadimage(int,int,char *);

Страницы: 1, 2, 3, 4