Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<fstream>
- using namespace std;
- struct nodo{int info; nodo* next; nodo(int a=0, nodo* b=0){info=a; next=b;}}; // nodo di lista
- struct FIFOX{nodo* primo, *ultimo; int valp, valu, nele; FIFOX(nodo*a=0, int b=0, int c=0, int d=0){primo=a; ultimo=a;valp=b;valu=c;nele=d;}};
- ostream & operator<<(ostream & OUT, FIFOX& a)
- {
- OUT<< '['<<"nele="<<a.nele<<" valp="<<a.valp<<" valu="<<a.valu<<']'<<endl;
- int x=0;
- nodo*z=a.primo;
- while(x<a.nele)
- {OUT<<z->info<<' ';z=z->next; x++;}
- OUT<<endl;
- return OUT;
- }
- //PRE=(A è un valore FIFOX corretto che gestisce una lista corretta e b è un nodo. Si assume che i nodi della
- //lista abbiano campo info distinti e anche diversi dal campo info di b)
- FIFOX push_iter(FIFOX A, nodo*b){
- if(!A.primo){
- A.primo=A.ultimo=b;
- A.valp=A.valu=b->info;
- A.nele=1;
- return A;
- }
- else{
- if(b->info<A.valp){
- b->next=A.primo;
- A.primo=b;
- A.valp=b->info;
- A.nele++;
- return A;
- }
- else{
- if(b->info>A.valu){
- A.ultimo->next=b;
- A.ultimo=b;
- A.valu=b->info;
- A.nele++;
- return A;
- }
- else{
- nodo* a=A.primo;
- while(a){
- if(a->info<b->info && a->next->info>b->info){
- b->next=a->next;
- a->next=b;
- A.nele++;
- return A;
- }
- else a=a->next;
- }
- }
- }
- }
- }
- //POST=(restituisce un nuovo valore FIFOX corretto che corrisponde alla lista ordinata ottenuta dalla lista di A
- //inserendo il nodo b in essa)
- //PRE_deleteX=(A è un FIFOX corretto e z è un intero. La lista gestita da A ha i nodi con info distinti)
- FIFOX deleteX(FIFOX A, int z){
- if(z<A.valp || z>A.valu || !A.primo) return A;
- if(A.valp==z){
- if(A.primo->next){
- nodo* tmp=A.primo;
- A.primo=A.primo->next;
- tmp->next=0;
- delete tmp;
- A.valp=A.primo->info;
- A.nele--;
- return A;
- }
- else return 0;
- }
- else{
- if(A.primo->next){
- if(A.primo->next->info==z){
- nodo* tmp=A.primo->next;
- if(tmp->next){
- A.primo->next=tmp->next;
- tmp->next=0;
- delete tmp;
- A.nele--;
- return A;
- }
- else{
- A.ultimo=A.primo;
- A.ultimo->next=0;
- A.valu=A.ultimo->info;
- delete tmp;
- A.nele--;
- return A;
- }
- }
- else{
- A.primo=A.primo->next;
- return deleteX(A,z);
- }
- }
- }
- }
- //POST_deleteX=(restituisce un FIFOX corretto rispetto alla lista ottenuta da quella di A dopo aver eliminato
- //un nodo con info=z, se un tale nodo esiste e altrimenti restituisce A)
- main()
- {
- int dim1,dim2, x;
- cin>>dim1>>dim2;
- FIFOX a;
- while(dim1)
- {
- cin>>x;
- a=push_iter(a,new nodo(x));
- dim1--;
- }
- cout<< a;
- while(dim2)
- {
- cin>>x;
- a=deleteX(a,x);
- dim2--;
- }
- cout<<a;
- cout<<"end"<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement