Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.49 KB | None | 0 0
  1. #include<iostream>
  2. #include<fstream>
  3. using namespace std;
  4. struct nodo{int info; nodo* next; nodo(int a=0, nodo* b=0){info=a; next=b;}}; // nodo di lista
  5. 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;}};
  6.  
  7. ostream & operator<<(ostream & OUT, FIFOX& a)
  8. {
  9. OUT<< '['<<"nele="<<a.nele<<" valp="<<a.valp<<" valu="<<a.valu<<']'<<endl;
  10. int x=0;
  11. nodo*z=a.primo;
  12. while(x<a.nele)
  13. {OUT<<z->info<<' ';z=z->next; x++;}
  14. OUT<<endl;
  15. return OUT;
  16. }
  17.  
  18. //PRE=(A è un valore FIFOX corretto che gestisce una lista corretta e b è un nodo. Si assume che i nodi della
  19. //lista abbiano campo info distinti e anche diversi dal campo info di b)
  20. FIFOX push_iter(FIFOX A, nodo*b){
  21. if(!A.primo){
  22. A.primo=A.ultimo=b;
  23. A.valp=A.valu=b->info;
  24. A.nele=1;
  25. return A;
  26. }
  27. else{
  28. if(b->info<A.valp){
  29. b->next=A.primo;
  30. A.primo=b;
  31. A.valp=b->info;
  32. A.nele++;
  33. return A;
  34. }
  35. else{
  36. if(b->info>A.valu){
  37. A.ultimo->next=b;
  38. A.ultimo=b;
  39. A.valu=b->info;
  40. A.nele++;
  41. return A;
  42. }
  43. else{
  44. nodo* a=A.primo;
  45. while(a){
  46. if(a->info<b->info && a->next->info>b->info){
  47. b->next=a->next;
  48. a->next=b;
  49. A.nele++;
  50. return A;
  51. }
  52. else a=a->next;
  53. }
  54. }
  55. }
  56. }
  57. }
  58. //POST=(restituisce un nuovo valore FIFOX corretto che corrisponde alla lista ordinata ottenuta dalla lista di A
  59. //inserendo il nodo b in essa)
  60.  
  61. //PRE_deleteX=(A è un FIFOX corretto e z è un intero. La lista gestita da A ha i nodi con info distinti)
  62. FIFOX deleteX(FIFOX A, int z){
  63. if(z<A.valp || z>A.valu || !A.primo) return A;
  64. if(A.valp==z){
  65. if(A.primo->next){
  66. nodo* tmp=A.primo;
  67. A.primo=A.primo->next;
  68. tmp->next=0;
  69. delete tmp;
  70. A.valp=A.primo->info;
  71. A.nele--;
  72. return A;
  73. }
  74. else return 0;
  75. }
  76. else{
  77. if(A.primo->next){
  78. if(A.primo->next->info==z){
  79. nodo* tmp=A.primo->next;
  80. if(tmp->next){
  81. A.primo->next=tmp->next;
  82. tmp->next=0;
  83. delete tmp;
  84. A.nele--;
  85. return A;
  86. }
  87. else{
  88. A.ultimo=A.primo;
  89. A.ultimo->next=0;
  90. A.valu=A.ultimo->info;
  91. delete tmp;
  92. A.nele--;
  93. return A;
  94. }
  95. }
  96. else{
  97. A.primo=A.primo->next;
  98. return deleteX(A,z);
  99. }
  100. }
  101. }
  102. }
  103. //POST_deleteX=(restituisce un FIFOX corretto rispetto alla lista ottenuta da quella di A dopo aver eliminato
  104. //un nodo con info=z, se un tale nodo esiste e altrimenti restituisce A)
  105.  
  106. main()
  107. {
  108. int dim1,dim2, x;
  109.  
  110. cin>>dim1>>dim2;
  111. FIFOX a;
  112. while(dim1)
  113. {
  114.  
  115. cin>>x;
  116. a=push_iter(a,new nodo(x));
  117. dim1--;
  118. }
  119. cout<< a;
  120.  
  121. while(dim2)
  122. {
  123. cin>>x;
  124. a=deleteX(a,x);
  125. dim2--;
  126. }
  127. cout<<a;
  128.  
  129. cout<<"end"<<endl;
  130. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement