8. .
, . , , , . .
( ), - . , , ..
: , , . . . .
, : . : , . (, ) :
struct Node
{
.
. //
.
Node *next;
};
.
, , , . : " ".
, . add, del. pbeg, pend.
#include <iostream.h>
#include <conio.h>
Struct Info
{
Int i;
};
Struct FIFO
{
Info d;
FIFO *next;
};
FIFO * first(Info d); // 1
void add(FIFO **pend, Info d); //
Info del(FIFO **pbeg); //
Void main()
{
Info d;
d.i=1;
FIFO *pbeg = first (d);
FIFO *pend = pbeg;
for (int i = 2; i<6; i++)
{
d.i=i;
add(&pend, d);
}
While (pbeg)
{
d=del(&pbeg);
cout<<d.i<<' ';
}
Getch();
}
FIFO *first(Info d) //
{
FIFO *pv = new FIFO;
pv->d = d;
pv->next = 0;
Return pv;
}
void add(FIFO **pend, Info d) //
{
FIFO *pv = new FIFO;
pv->d = d;
pv->next = 0;
(*pend)->next = pv;
*pend = pv;
}
Info del(FIFO **pbeg) //
{
Info temp = (*pbeg)->d;
|
|
FIFO *pv = *pbeg;
*pbeg = (*pbeg)->next;
Delete pv;
Return temp;
}
:
1 2 3 4 5
, . : " ".
, (1, 2, 3, 4, 5) add, del (top) .
#include <iostream.h>
#include <conio.h>
Struct Info
{
Int i;
};
Struct LIFO
{
Info d;
LIFO *next;
};
LIFO * first(Info d); // 1
void add(LIFO **top, Info d); //
Info del(LIFO **top); //
Int main()
{
Info d;
d.i=1;
LIFO *top = first (d);
for (int i = 2; i<6; i++)
{
d.i=i;
add(&top, d);
}
While (top)
{
d=del(&top);
cout<<d.i<<' ';
}
Getch();
Return 0;
}
LIFO *first(Info d) //
{
LIFO *pv = new LIFO;
pv->d = d;
pv->next = 0;
Return pv;
}
void add(LIFO **top, Info d) //
{
LIFO *pv = new LIFO;
pv->d = d;
pv->next = *top;
*top = pv;
}
Info del(LIFO **top) //
{
Info temp = (*top)->d;
LIFO *pv = *top;
*top = (*top)->next;
Delete pv;
Return temp;
}
, , , ; , , , , , . :
, , . , . .
:
struct Node
{
d; //
Node *next;
Node *prev;
};
:
- ( );
- ;
- ;
- ( );
- ;
- .
, ( 1 2 3 4), , . bg, pend, pv pkey
, (, ), .
|
|
#include <iostream.h>
#include <conio.h>
#include<string.h>
struct info
{char fam[20];
int gr;
};
struct LIST
{
info d;
LIST *next;
LIST *prev;
};
//... -... ---.----.---- ----- -..--...-.--...-
void vvod(info &d);
LIST * first(info d); ////
void add(LIST **pend, info d); //
LIST * find(LIST * const pbeg, char *key); //
bool remove(LIST **pbeg, LIST **pend, char *key); //
LIST * insert(LIST * const pbeg, LIST **pend, char *key, info d); //
void sort(LIST **pbeg, LIST **pend);
void vyvod(LIST *pbeg);
//-.... -..--..--.-.---..----.------. -----.--
int main()
{char fam[20];
info d;
int i;
vvod(d);
LIST *pbeg = first(d); //
LIST *pend = pbeg; //
// 2 3 4 5
for (i = 0;i<3;i++)
{
vvod(d);
add(&pend,d);
}
// 200 2
vyvod(pbeg);
cout <<" posle Fam ";
cin>>fam;
vvod(d);
insert(pbeg,&pend, fam, d);
vyvod(pbeg);
// 5
cout <<" Fam dla delet ";
cin>>fam;
if(!remove (&pbeg, &pend,fam)) cout<< " ";
vyvod(pbeg);
cout<<"do sort"<<endl;
for(i=0;i<2;i++)
{vyvod(pbeg);
if(!i){ cout<<"posle sort"<<endl;
sort(&pbeg,&pend);}}
cout<<"fam for find\n";
cin>>fam;
LIST *pv=pbeg;
do{
if(pv=find(pv,fam))
{cout << pv->d.fam<<' '<<pv->d.gr<<endl;
pv=pv->next;}
}while(pv);
return 0;
}
//... -- ---. ---- -..-..-- ---.. --..---... --
void vvod(info &d)
{cout <<"Fam"<<endl;
cin>>d.fam;
cout<<"G r"<<endl;
cin>>d.gr;
}
void vyvod(LIST *pbeg)
{LIST *pv = pbeg;
while (pv){ //
cout << pv->d.fam<<' '<<pv->d.gr<<endl;
pv = pv->next;
}}
//
LIST * first(info d)
{
LIST *pv= new LIST;
pv->d = d;
pv->next = 0;
pv->prev = 0;
return pv;
}
//..-...-.....-...------ ---- --- --..----. --
//
void add(LIST **pend, info d)
{
LIST *pv = new LIST;
pv->d = d;
pv->next= 0;
pv->prev = *pend;
(*pend)->next = pv;
*pend = pv;
} //-...----...----....--.---..-...-..--.......-----
//
LIST * find(LIST * const pbeg, char *key)
{ LIST *pv = pbeg;
while (pv){
if(!strcmp(pv->d.fam,key))break;
pv = pv->next;
} return pv;
}
//..-----.-.....---..--.....--....------.-....----
//
bool remove(LIST **pbeg, LIST **pend, char *key){
if(LIST *pkey = find(*pbeg, key)){ // 1
if (pkey == *pbeg)
{ // 2
*pbeg = (*pbeg)->next;
(*pbeg)->prev =0;
}
else if (pkey == *pend)
{ // 3
*pend = (*pend)->prev;
(*pend)->next =0;
}
else
{ // 4
(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev;
}
delete pkey;
return true; //5
}
return false; // 6
}
//..-----...------....------.......--I--......---.
//
LIST * insert(LIST * const pbeg, LIST **pend, char *key, info d)
{ if(LIST *pkey = find(pbeg, key)){
LIST *pv = new LIST;
pv->d = d;
// 1 - :
pv->next = pkey->next;
// 2 - :
pv->prev = pkey;
// 3 - -
pkey->next = pv;
// 4 -
if(pkey!= *pend) (pv->next)->prev = pv;
//
//
|
|
else *pend = pv;
return pv;
} return 0;
}
//---------------
void sort(LIST **pbeg, LIST **pend)
{bool f;
LIST *pv,*pt,*pk=*pbeg;
while(pk)
{ pv=new LIST;
pv->d =pk->d;
pt = *pbeg;
f=true;
while (pt!=pk){ //
if ((pv->d).gr < (pt->d).gr){ // (pt)
f=false;
pv->next = pt;
if (pt == *pbeg){ //
pv->prev = 0; *pbeg = pv;}
else{ //
(pt->prev)->next = pv;
pv->prev = pt->prev;}
pt->prev = pv;
//
pt=pk->next;
// pk
if(pk==*pend)//
{(pk->prev)->next=0;
*pend=pk->prev;}
else //
{(pk->prev)->next= pk->next;
(pk->next)->prev=pk->prev;
}
delete pk;
pk=pt;
break;
} pt = pt->next;
}
if(f) pk=pk->next;
}
}
remove , 1 pkey, find 0, . pkey , i f ( ), 2, false ( 6).
- , , 2 , pbeg , , next
( 3), pend , prev , , , , - , true
3 2 .
, , ,
(, ):
void add_sort(Node **pbeg, Node **pend, int d)
{ Node *pv = new Node; //
pv->d = d;
Node * pt = *pbeg;
while (pt){ //
1f (d < pt->d){ // (pt)
pv->next = pt;
if (pt == *pbeg){ //
pv->prev = ; *pbeg = pv;}
e1se{ //
(pt->prev)->next = pv;
pv->prev = pt->prev;}
pt->prev = pv:
return;
} pt = pt->next:
}
pv->next = 0; //
pv->prev = *pend:
(*pend)->next = pv;
*pend = pv;
|
|
}
, , , , . . .
. , , . , . , .
, , , . . , . , , .
( - ). :
;
;
;
(, ).
, .. , , - . , 17, 18, 6, 5, 9, 23, 12, 7, 8, :
, , . , , (Y) (NEW). NEW < Y, ; - . , , , .
11 .
:
) - ( );
) ;
) ( , ).
, 6 :
. , .
1) : A, R, ( , - , , ).(5 6 7 8 9 11 12 17 18 23)
2) : R, , ( ).(17 6 5 9 7 8 12 11 18 23)
3) : , , R ( ). (5 8 7 11 12 9 6 17 23 18)
.
; .
der(), , print_der(), .
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<windows.h>
char buf[256];
char *rus(char *text)
{CharToOem(text,buf);
return buf;}
struct info
{ char *w;
int c;
};
struct TREE
{ info d;
TREE *l;
TREE *r;
};
TREE *first(char *word);//
TREE *der(TREE *kr, char *word);//
void print_der(TREE *kr);//
void main()
{ int i=0;
char word[40][20],ch;
puts(rus(" , Esc"));
scanf ("%s",word[i]);
TREE *kr=first(word[i]);
do
{
scanf("%s", word[++i]);
der(kr,word[i]);
printf("");}
while((ch=getch())!=27);
print_der(kr);
}
TREE *first(char *word)
{TREE *pv=new TREE;
(pv->d).w=word;
(pv->d).c=1;
pv->l=0;
pv->r=0;
return pv;}
TREE *der(TREE *kr, char *word)
{TREE *pv=kr,*prev;
int flag=0;
int sr;
while(pv&&!flag)
{prev=pv;
if((sr=strcmp(word, (pv->d).w))==0) {((pv->d).c)++;flag=1;}
else if(sr<0) pv= pv->l;
else pv= pv->r;}
|
|
if (flag) return pv;
//
TREE *pnew=new TREE;
(pnew->d).w=word;
(pnew->d).c=1;
pnew->l=0;
pnew->r=0;
if(sr<0) prev->l= pnew;
else prev->r=pnew;
return pnew;
}
void print_der(TREE *kr)
{
if(kr)
{ print_der(kr->l);
printf(rus(" - %-20s \t- .- %d\n"), (kr->d).w, (kr->d).c);
print_der (kr->r);
}
}