#include <iostream>
using namespace std;
const int b=1000;
struct chitatel
{
char bilet[8];//«ANNNN-YY»,
char fio[30];
int god;
char adres[30];
char mesta[30];
};
struct chitatel chit[b];
struct kniga
{
char shifr[7];
char afftor[30];
char nazvanie[30];
char izdatelstvo[30];
int god;
int kolvovsego;
int kolvoest;
//struct kniga* left;
// struct kniga* right;
};
struct vidacha
{
char bilet[8];
char shifr[7];
char dacha[30];
char vidat[30];
};
struct spisok
{
struct vidacha dat;
struct spisok *next;
};
struct bmslovo
{
char bukva;
int line;
};
struct tree {
struct kniga book;
int balance;
tree *right;
tree *left;
};
struct stack_elem{
tree *vert;
char pos;
//stack_elem* next;
} stack[100];
int stack_len=0;
//шаг первый-Хэширование
//__________________________________________________________________
int heshnomer(char *nomer)//создание хэш номера
{
int h,g=0;
int hh[10];
h=(nomer[0]+3*nomer[1]+9*nomer[2]+27*nomer[3]+81*nomer[4]+243*nomer[5]+81*nomer[6]+27*nomer[7]);
h=h*h;
int i=1,p=1;
for(int n=9;n>=0;n--)
{
p=10*p;
hh[n]=(h%p-g)/(p/10);
g=h%p;
i++;
}
h=hh[9]*1000+hh[3]*100+hh[2]*10+hh[6];
h=h%b;
return h;
}
bool heshpoisk(struct chitatel chit[b],char *nomer,int &nom)// поиск ключа в хэш таблице
{
bool tyt;
int p,i=2;
nom=heshnomer(nomer);
p=nom;
while(p<b)
{
if (!strcmp(chit[p].bilet,""))
{
nom=p;
return false;
}
else
{
if(!strcmp(nomer,chit[p].bilet))
{
nom=p;// посмотреть баг, что будет если рпревысит 1000.
return true;
}
p=p+i;
i=i*2;
}
}
cout<<"MECTA HET!!!";
return tyt;
}
bool heshdabavka(char *nomer,int &nom)//добавление клиента в хэштааблицу
{
if(heshpoisk(chit,nomer,nom))
return false;
else
{
strcpy(chit[nom].bilet,nomer);
cout<<"BBEDUTE FIO: ";
cin>>chit[nom].fio;//>>'\n';
cout<<"BBEDUTE ADPEC: ";
cin>>chit[nom].adres;//>>'\n';
cout<<"BBEDUTE MECTO Y4Ebi/PAbOTi: ";
cin>>chit[nom].mesta;//>>'\n';
cout<<"BBEDUTE GOD ROJDEHUIA: ";
cin>>chit[nom].god;//>>'\n';
cout<<"\n";
}
}
void delallklient(struct chitatel chit[b])//очистка хэштааблицы
{
int i=0;
while(i<b)
{
strcpy(chit[i].bilet,"");
strcpy(chit[i].fio,"");
strcpy(chit[i].adres,"");
strcpy(chit[i].mesta,"");
chit[i].god=0;
i++;
}
}
bool ydalenieodnogo(char *nomer)//удаление клиента
{
int i=-1;
if(heshpoisk(chit,nomer,i))
{
strcpy(chit[i].bilet,"");
strcpy(chit[i].fio,"");
strcpy(chit[i].adres,"");
strcpy(chit[i].mesta,"");
chit[i].god=0;
return true;
}
return false;
}
int prosmotrall(struct chitatel chit[b])//просмотр всех зарегистрированных читателей;
{
int i=0,l=0;
while (i<b)
{
if(strcmp(chit[i].bilet,""))
{
cout<<i<<") "<<"bU/\ET # "<<chit[i].bilet<<'\n';
cout<<"FIO: "<<chit[i].fio<<'\n';
cout<<" ADPEC: "<<chit[i].adres<<'\n';
cout<<"MECTO Y4Ebi/PAbOTi: "<<chit[i].mesta<<'\n';
cout<<"GOD ROJDEHUIA: "<<chit[i].god<<'\n';
cout<<"\n";
i++;
l++;
}
else
i++;
}
cout<<"BCEGO "<<l<<" K/\UEHTOB";
return l;
}
//_____________________________________________________________________
//шаг второй АВЛ деревья.
struct tree *maloepravoe(struct tree *a)//малое правое
{
struct tree* h;
struct kniga adata,hdata;
int v=0,w,f;
h=a->right;
adata=a->book;
hdata=h->book;
w=h->balance;
f=(max(v,w)+1)-a->balance;
a->book=hdata;
h->book=adata;
a->right=h->right;
h->right=h->left;
h->left=a->left;
a->left=h;
h->balance=v-f;
a->balance=w-(max(f,v)+1);
return a;
}
struct tree *maloelevoe(struct tree *a)//малое левое
{
struct tree* h;
struct kniga adata,hdata;
int v=0,w,f;
h=a->left;
adata=a->book;
hdata=h->book;
w=h->balance;
f=(max(v,w)+1)-a->balance;
a->book=hdata;
h->book=adata;
a->left=h->left;
h->left=h->right;
h->right=a->right;
a->right=h;
h->balance=v-f;
a->balance=w-(max(f,v)+1);
return a;
}
struct tree *bolshoepravoe(struct tree *a)//большое правое
{
struct tree* b;
struct tree* c;
struct kniga adata,bdata,cdata;
int v,w=0,f,p;
b=a->right;
c=b->left;
adata=a->book;
bdata=b->book;
cdata=c->book;
f=c->balance;
p=(max(w,f)+1)+b->balance;
v=1+max(p,p-b->balance)-a->balance;
a->book=cdata;
c->book=adata;
b->left=c->right;
c->right=c->left;
c->left=a->left;
a->left=c;
b->balance=p-f;
c->balance=w-v;
a->balance=max(p,f)-max(v,w);
return a;
}
struct tree *bolshoelevoe(struct tree *a)//большое левое
{
struct tree* b;
struct tree* c;
struct kniga adata,bdata,cdata;
int v,w=0,f,p;
b=a->left;
c=b->right;
adata=a->book;
bdata=b->book;
cdata=c->book;
f=c->balance;
p=(max(w,f)+1)+b->balance;
v=1+max(p,p-b->balance)-a->balance;
a->book=cdata;
c->book=adata;
b->right=c->left;
c->left=c->right;
c->right=a->right;
a->right=c;
b->balance=p-f;
c->balance=w-v;
a->balance=max(p,f)-max(v,w);
return a;
}
void tree_balance(struct tree *a, int &cur_balance)//bolshoepravoe bolshoelevoe maloelevoe maloepravoe
{
struct tree *b;
if (a->balance==2)
{
b=a->right;
if (b->balance==-1)
{
bolshoepravoe(a);
cur_balance=-1;
}
else
{
if (b->balance==0)
{
maloepravoe(a);
cur_balance=0;
}
else
{
maloepravoe(a);
cur_balance=-1;
}
}
}
else
{
if (a->balance==-2)
{
b=a->left;
if (b->balance==1)
{
bolshoelevoe(a);
cur_balance=-1;
}
else
{
if (b->balance==0)
{
maloelevoe(a);
cur_balance=0;
}
else
{
maloelevoe(a);
cur_balance=-1;
}
}
}
else
{
cur_balance=0;
}
}
}
/*
bool search(struct tree *a,char *x,int &kolvoshagov)
{
bool naiden=false;
if(a)
{
if(!strcmp(a->book.shifr,x))
return true;
kolvoshagov++;
if(strcmp(a->book.shifr,x)<0)
search(a->right,x,kolvoshagov);
else
search(a->left,x,kolvoshagov);
}
//return naiden;
}*/
struct tree * search(struct tree *start, char *k, int &steps)
{
if (start==NULL) return NULL;
else
{
if (!strcmp(start->book.shifr,k))
return start;
if (strcmp(start->book.shifr,k)==-1)
search(start->right, k, ++steps);
else
search(start->left, k, ++steps);
}
}
void add2(struct kniga k, struct tree *&start)// добавление с балансировкой.
{
struct tree *newnode, *current;
stack_len=0;
int delta=0;
int change=0;
int newdelta=0;
if (start==NULL)
{
start=new tree;
start->book=k;
start->left=NULL;
start->right=NULL;
start->balance=0;
}
else
{
current=start;
while (((strcmp(current->book.shifr,k.shifr)==-1)&& current->right!=NULL)
||((strcmp(k.shifr,current->book.shifr)==-1) && current->left!=NULL))
{
if (strcmp(k.shifr,current->book.shifr)==1)
{
stack[stack_len].pos='r';
stack[stack_len++].vert=current;
current=current->right;
}
else
{
stack[stack_len].pos='l';
stack[stack_len++].vert=current;
current=current->left;
}
}
if (strcmp(k.shifr,current->book.shifr))
{
newnode=new tree;
newnode->balance=0;
newnode->book=k;
newnode->left=NULL;
newnode->right=NULL;
if(strcmp(k.shifr,current->book.shifr)==1)
{
stack[stack_len].vert=current;
stack[stack_len++].pos='r';
current->right=newnode;
}
else
{
stack[stack_len].vert=current;
stack[stack_len++].pos='l';
current->left=newnode;
}
delta=1;
while (delta!=0 && stack_len!=0)
{
if (stack[stack_len-1].pos=='l')
{
if (stack[stack_len-1].vert->balance==1) change=0;
else change=1;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance-1;
}
else
{
if (stack[stack_len-1].vert->balance==-1) change=0;
else change=1;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance++;
}
tree_balance(stack[stack_len-1].vert, newdelta);
delta=change+newdelta;
stack_len--;
}
}
}
}
bool remove(char *k, struct tree *&start)
{
struct tree *cur2, *current;
stack_len=0;
int delta=0;
int change=0;
int newdelta=0;
int temp=0;
if (start==NULL || search(start, k, temp)==NULL) return false;
else
{
current=start;
while (((strcmp(k,current->book.shifr)==1)&& current->right!=NULL)
||((strcmp(current->book.shifr,k)==-1)&¤t->left!=NULL))
{
if (strcmp(k,current->book.shifr)==1)
{
stack[stack_len].pos='r';
stack[stack_len++].vert=current;
current=current->right;
}
else
{
stack[stack_len].pos='l';
stack[stack_len++].vert=current;
current=current->left;
}
}
if (!strcmp(k,current->book.shifr))
{
if (current->left!=NULL && current->right!=NULL)
{
stack[stack_len].vert=current;
stack[stack_len++].pos='r';
cur2=current->right;
while (cur2->left!=NULL)
{
stack[stack_len].vert=cur2;
stack[stack_len++].pos='l';
cur2=cur2->left;
}
strcpy(current->book.shifr,cur2->book.shifr);
if (stack[stack_len-1].vert!=current) stack[stack_len-1].vert->left=cur2->right;
else stack[stack_len-1].vert->right=cur2->right;
delete cur2;
}
else
{
if (current->left==NULL)
{
if (stack_len!=0)
{
if (stack[stack_len-1].pos=='l') stack[stack_len-1].vert->left=current->right;
else stack[stack_len-1].vert->right=current->right;
}
else start=current->right;
}
if (current->right==NULL)
{
if (stack_len!=0)
{
if (stack[stack_len-1].pos=='l') stack[stack_len-1].vert->left=current->left;
else stack[stack_len-1].vert->right=current->left;
}
else start=current->left;
}
delete current;
}
delta=-1;
while (delta!=0 && stack_len!=0)
{
if (stack[stack_len-1].pos=='l')
{
if (stack[stack_len-1].vert->balance==-1) change=-1;
else change=0;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance+1;
}
else
{
if (stack[stack_len-1].vert->balance==1) change=-1;
else change=0;
stack[stack_len-1].vert->balance=stack[stack_len-1].vert->balance-1;
}
tree_balance(stack[stack_len-1].vert, newdelta);
delta=change+newdelta;
stack_len--;
}
}
}
return true;
}
void preorder(struct tree *bush)
{
cout<<" ,"<<bush->book.shifr;
if(bush->left)
preorder(bush->left);
if(bush->right)
preorder(bush->right);
}
void inorder(struct tree *bush)
{
if (bush->left&&bush->right)
{
inorder(bush->left);
cout<<" ,"<<bush->book.shifr;
preorder(bush->right);
}
else
{
cout<<bush->book.shifr;
if(bush->left)
{
inorder(bush->left);
cout<<bush->book.shifr;
}
if(bush->right)
{
inorder(bush->right);
cout<<bush->book.shifr;
}
}
}
//_____________________________________________________________________
//шаг третий список.
void spisadd(struct vidacha a,struct spisok *&b)
{
if(!b)
{
b=new struct spisok;
b->dat=a;
b->next=b;
}
else
{
struct spisok *c,*g;
c=b;
while (strcmp(b->next->dat.shifr,c->dat.shifr))
b=b->next;
g=new struct spisok;
g->dat=a;
g->next=c;
b->next=g;
}
}
//_____________________________________________________________________
//шаг четвертый Алгоритм поиска слова в тексте.Боуера и Мура .
bool bmsearch(char *ward,int position)
{
int i=0;//индекс начала слова в тексте
int j=0;//индекс текущего символа
int z=0,n;
struct bmslovo alfo[255];
//char mas[255];
int m=strlen(ward)-1;
int t=m;// t,m-размер слово которое ищем
//char *ch;
//создать алфовит.
while(m>0)
{
for(n=z;n>=0;n--)
{
if (ward[m]==alfo[n].bukva)
goto mmm;
}
alfo[z].bukva=ward[m];
alfo[z].line=t-m;
z++;
mmm: m--;
}//создание алфовита закончено
alfo[0].line=1;// расстояние от крайнего правого символа до конца слова.
z--;//z-размер алфовита.
char slovo[255]="abcafdfmbcabdabcabd";
bool sovpalo=false;
n=strlen(slovo);
i=t;
j=t;
WWW:while((i<n)&&(!sovpalo))
{
if(j==-1)
return true;
if(ward[j]==slovo[i])
{
i--;
j--;
}
else
{
for(m=0;m<=z;m++)//поиск несовпавшей буквы в алфовите
{
if(slovo[i]==alfo[m].bukva)
{
i=i+alfo[m].line;
j=t;
goto WWW;
}
}
j=t;
i=i+(t+1);
}
//if(j==0)
// return true;
}
return sovpalo;
}
void main()
{
//int *klientbase[b];
int i;
//for (i=0;i<b;i++)
// klientbase[i]=NULL;
int n=-1;
int a=heshnomer("X999999");//«ANNNN-YY»,
//a=heshnomer("Ч123490");//«ANNNN-YY»,
//a=heshnomer("Ч123390");//«ANNNN-YY»,
//a=heshnomer("Ч113490");//«ANNNN-YY»,
strcpy(chit[446].bilet,"Ч222283");
strcpy(chit[448].bilet,"Ч555583");
strcpy(chit[452].bilet,"X999999");
bool b=heshpoisk(chit,"X999999",n);
//b=heshpoisk(chit,"X997989",n);
//b=heshdabavka("Ч764587",n);
prosmotrall(chit);
//b=heshdabavka("X999999",n);
//delallklient( chit);
//ydalenie("Ч764587");
b=false;
b=bmsearch("abcabd",0);
struct tree *nov;
nov=NULL;
struct kniga k;
strcpy(k.afftor,"aaa");
strcpy(k.izdatelstvo,"aaa");
strcpy(k.nazvanie,"aaa");
strcpy(k.shifr,"aaa");
k.god=1990;
k.kolvoest=2;
k.kolvovsego=3;
add2(k,nov);
strcpy(k.afftor,"bbb");
strcpy(k.izdatelstvo,"bbb");
strcpy(k.nazvanie,"bbb");
strcpy(k.shifr,"bbb");
k.god=1991;
k.kolvoest=12;
k.kolvovsego=13;
add2(k,nov);
strcpy(k.afftor,"ccc");
strcpy(k.izdatelstvo,"ccc");
strcpy(k.nazvanie,"ccc");
strcpy(k.shifr,"ccc");
k.god=1992;
k.kolvoest=22;
k.kolvovsego=33;
add2(k,nov);
strcpy(k.afftor,"ddd");
strcpy(k.izdatelstvo,"ddd");
strcpy(k.nazvanie,"ddd");
strcpy(k.shifr,"ddd");
k.god=1993;
k.kolvoest=2;
k.kolvovsego=3;
add2(k,nov);
strcpy(k.afftor,"eee1");
strcpy(k.izdatelstvo,"eee1");
strcpy(k.nazvanie,"eee1");
strcpy(k.shifr,"eee1");
k.god=1994;
k.kolvoest=2;
k.kolvovsego=3;
add2(k,nov);
strcpy(k.afftor,"fff");
strcpy(k.izdatelstvo,"fff");
strcpy(k.nazvanie,"fff");
strcpy(k.shifr,"fff");
k.god=1995;
k.kolvoest=2;
k.kolvovsego=3;
add2(k,nov);
int l=0;
bool pr=true;
struct tree *mma;
mma=NULL;
mma=search(nov,"fff",l);
l=7;
mma=search(nov,"aaa",l=0);
mma=search(nov,"ddd",l=0);
mma=search(nov,"eee",l=0);
mma=search(nov,"ccc",l=0);
mma=search(nov,"bbb",l=0);
cout<<"\n";
inorder(nov);
pr=remove("eee1", nov);
cout<<"\n";
inorder(nov);
strcpy(k.afftor,"eee1");
strcpy(k.izdatelstvo,"eee1");
strcpy(k.nazvanie,"eee1");
strcpy(k.shifr,"eee1");
k.god=1994;
k.kolvoest=2;
k.kolvovsego=3;
add2(k,nov);
cout<<"\n";
inorder(nov);
}