Skocz do zawartości


Zdjęcie

[C++] Lista jednokierunkowa - tworzenie, sortowanie itp


  • Zaloguj się, aby dodać odpowiedź
Brak odpowiedzi do tego tematu

#1 Leogict

Leogict

    Początkujący

  • 28 postów

Napisano 06 12 2009 - 18:56

Witam, napisałem program tworzący listę jednokierunkową, sortujący ją, usuwający wielokrotności liczby 5, mający opcję dodawanie elementów (na początku listy wewnątrz i na końcu) oraz usuwanie elementów (na początku, wewnątrz i na końcu).

Elementy listy posiadają wartości wg wzoru (i^2)%50, gdzie i jest jakby indeksem elementu.

Będę wdzięczny za wszelkie opinie, uwagi, wskazówki i co byście dodali, zmienili, napisali inaczej, z góry dziękuję.

1.      // Lista jednokierunkowa   2.      //   3.      // tworzenie, sortowanie, usuwanie wielokrotnosci liczby 5,    4.      // dodawanie elementow (na poczatku, wewnatrz i na koncu),   5.      // usuwanie elementow (na poczatku, wewnatrz i na koncu).   6.   7.      #include <iostream>   8.   9.      using namespace std;  10.  11.      void UtworzListe();  12.      void SortujListe();  13.      void UsunWielokrotnosci5();  14.      void DodajNaPoczatku();  15.      void DodajWewnatrz();  16.      void DodajNaKoniec();  17.      void UsunPoczatek();  18.      void UsunWewnatrz();  19.      void UsunKoncowy();  20.      void WyswietlListe();  21.      void DodawanieElementu();  22.      void UsuwanieElementu();  23.      void DodajLubUsunElementy();  24.  25.      class element // element listy  26.      {  27.      public:  28.        int wartosc;  29.        element *next; // wskaznik na nastepny element  30.        element(int x) : wartosc(x), next(NULL) {}; // konstruktor, pod wartosc podstawiamy argument, pod wskaznik na nastepny element NULL  31.        void wyswietl();  32.      };  33.  34.      void element::wyswietl()  35.      {  36.        cout << wartosc << " ";  37.      }  38.  39.       element lista(-2); // nasza lista  40.       element *start=&lista, *koniec=start, *a, *b, *c, *temp, *temp2; // potrzeba wskazniki: na poczatek listy, koniec listy, 3 kolejne elementy i wskaznik pomocniczy do sortowania   41.  42.      void UtworzListe()  43.      {  44.        cout << "lista: " << endl;  45.        for(int i=0; i<50; i++, koniec=koniec->next) koniec->next=new element((i*i)%50);  // zapelnianie listy  46.        WyswietlListe();  47.      }  48.  49.      void SortujListe()  50.      {  51.        cout << "\n\nLista posortowana:\n";  52.        for(int i=0; i<50; i++)  53.      	{  54.      	 a=start;       //  55.      	 b=start->next; // ustawienie wskaznikow na poczatek listy  56.         	 c=b->next;     //  57.      	 temp=c;        //  58.      	 for(a; c->next;) // rownoznaczne for(int j=0; j<50; j++)  59.      		{  60.      			if((c->next) && (c->wartosc < b->wartosc)) // najpierw sprawdzamy czy nie koniec listy a potem stosunek wartosci sasiednich elementow listy  61.      			{  62.      				temp=b->next;          //  temp bo zaraz stracimy adres elementu b  63.      				b->next=temp->next;    //  64.      				temp->next=b;          //  manipulacja wskaznikami, np. z fragmentu listy 3,5,2 robimy 3,2,5  65.      				a->next=c;             //  66.      				temp=c;                //  67.      				  68.      				c=a->next->next->next;  // aktualizacja wskaznikow  69.      				a=a->next;              // j.w.  70.      			}  71.      			else if(c->next)  // jezeli wartosci rosnace (w porzadku) to lecimy dalej  72.      			{  73.      				a=a->next; //     3,4,5,6  74.      				b=b->next; //     a,b,c, ->  75.      				c=c->next; // ->    a,b,c  76.      			}  77.      		}  78.      	}  79.      	WyswietlListe();  80.      }  81.  82.      void UsunWielokrotnosci5()  83.      {  84.        b=start->next;  85.        int counter=0;  86.        for(a=start; b->next;) // petla od poczatku do konca listy  87.        {  88.      	   if((counter==0) && !((a->wartosc)%5))  // zabezpieczamy sie przed wielokrotnoscia 5 na poczatku listy - przestawiamy "glowe listy"  89.      		  {  90.      			  temp2=start;  91.      			  //start=b->next;  92.      			  a=start;  93.      			  b=start->next;  94.      		  }  95.            if(!((b->wartosc)%5)) // jezeli jakas wartosc jest podzielna przez 5  96.            {  97.      		temp=b; // zmienna pomocnicza  98.      		a->next=b->next; // przestawienie wskaznika  99.      		delete temp; // usuniecie wielokrotnosci 100.      			if((a->next->wartosc)%5) // nowe a niepodzielne przez 5 101.      			{ 102.      				a=a->next; 103.      				b=a->next; 104.      			} 105.      			else b=a->next; //podzielne, stare a zostawiemy bez zmian, a a traktujemy jak b i je usuwamy bo jest podzielne przez 5 106.            } 107.      	  else if(a->next && b->next) 108.            { 109.              a=a->next;  // jak b nie jest podzielne przez 5 to szukamy dalej 110.              b=b->next;  // j.w. 111.            } 112.      	  if(b->next==NULL)  // usuwamy nadmiarowy element bo za daleko wyjechalismy o jeden 113.      		  a->next=NULL;  // 114.        } 115.        cout << "\nLista z usunietymi wielokrotnosciami liczby 5: \n"; 116.        WyswietlListe(); 117.      } 118. 119.      void DodajNaPoczatku() 120.      { 121.      	int wartosc; 122.      	cout << "\nPodaj wartosc nowego elementu: "; 123.      	cin >> wartosc; 124.      	temp=start;  // zmienna pomocnicza do zapamietanie start, bo za chwile nadpiszemy ja 125.      	start=new element(wartosc); 126.      	start->next=temp; 127.      	WyswietlListe(); 128.      } 129. 130.      void DodajWewnatrz() 131.      { 132.      	int wartosc,indeks,e,counter=0; 133.      	cout << "\nPodaj indeks gdzie go wstawic: "; 134.      	cin >> indeks; 135.      	for(a=start;a;a=a->next) ++counter; // ilosc elementow na liscie, musimy ograniczyc podanie indeksu przez uzytkownika do tej wartosci 136.      	while(indeks<0 || indeks>counter) // zabezpieczenie przed przekroczeniem lub podaniem ujemnego idneksu 137.      	{ 138.      		cout << "Zly indeks, podaj jeszcze raz!\n"; 139.      		cin >> indeks; 140.      	} 141.      	if(indeks==counter) // w przypadku gdy podalismy ostatni indeks 142.      	{ 143.      		DodajNaKoniec(); 144.      		return; 145.      	} 146.      	if(indeks==0) // jezeli chcemy dodac na poczatek 147.      	{ 148.      		DodajNaPoczatku(); 149.      		return; 150.      	} 151.      	cout << "Podaj wartosc nowego elementu: "; 152.      	cin >> wartosc; 153.      	 154.      	  // dodawanie gdzies dalej wglab listy 155.      	 156.      		  for(a=start, c=a->next, e=1; e<indeks; a=a->next, c=c->next, e++);  // dojscie do danego miejsca w liscie 157.      		  temp=a->next; 158.      		  c=new element(wartosc); 159.      		  c->next=temp; 160.      		  a->next=c; 161.      	 162.      	WyswietlListe(); 163.      } 164. 165.      void DodajNaKoniec() 166.      { 167.      	  int wartosc; 168.      	  cout << "\n\nPodaj wartosc nowego elementu: "; 169.      	  for(a=start; a->next; a=a->next); // dojscie do konca listy 170.      	  cin >> wartosc; 171.      	  a->next=new element(wartosc);  // dodanie nowego elementu na koniec 172.      	  WyswietlListe(); 173.      } 174. 175.      void UsunPoczatek() 176.      { 177.      		a=start; 178.      		start=start->next; 179.      		WyswietlListe(); 180.      		delete a; 181.      } 182. 183.      void UsunWewnatrz() 184.      { 185.      	int indeks; 186.      	cout << "Ktory element listy usunac? Podaj indeks: "; 187.      	cin >> indeks; 188.      	int counter=0,e; 189.      	for(a=start;a;a=a->next) ++counter; // ilosc elementow na liscie, musimy ograniczyc podanie indeksu przez uzytkownika do tej wartosci 190.      	while(indeks<0 || indeks>counter-1) // zabezpieczenie przed przekroczeniem lub podaniem ujemnego idneksu 191.      	{ 192.      		cout << "Zly indeks, podaj jeszcze raz!\n"; 193.      		cin >> indeks; 194.      	} 195.      	if(indeks==0) UsunPoczatek(); 196.      	else if(indeks==counter) UsunKoncowy(); 197.      	else 198.      	{ 199.      		for(a=start, c=a->next, e=1; e<indeks; a=a->next, c=c->next, e++);  // dojscie do danego miejsca w liscie 200.      		temp=c; 201.      		a->next=c->next; 202.      		delete c; 203.      		WyswietlListe(); 204.      	} 205.      } 206. 207.      void UsunKoncowy() 208.      { 209.      	for(a=start, b=start->next; b->next; a=a->next, b=b->next);  // po wykonaniu tej linijki a jest przedostatnim elementem, b - ostatnim 210.      	a->next=NULL; // konczymy liste o jeden element wczesniej 211.      	delete b; // i usuwamy ostatni element 212.      	WyswietlListe(); 213.      } 214. 215.      void WyswietlListe() 216.      { 217.      	for(a=start; a; a=a->next) //wyswietlanie listy 218.      		a->wyswietl(); 219.      	cout << endl; 220.      } 221. 222.      void DodawanieElementu() 223.      { 224.      	int wybormiejsca; 225.      	cout << "1. na poczatku\n2. w obrebie listy\n3. na koncu\nTwoj wybor: "; 226.      	cin >> wybormiejsca; 227.      	if(wybormiejsca==1) DodajNaPoczatku(); // dodajemy na poczatku 228.      	else if(wybormiejsca==2) DodajWewnatrz(); // dodanie elementu w obrebie listy 229.      	else if(wybormiejsca==3) DodajNaKoniec(); // dodanie na koniec listy 230.      } 231. 232.      void UsuwanieElementu() 233.      { 234.      	int wybormiejsca; 235.      	cout << "1. na poczatku\n2. w obrebie listy\n3. na koncu\nTwoj wybor: "; 236.      	cin >> wybormiejsca; 237.      	if(wybormiejsca==1) UsunPoczatek(); // usuwamy poczatek listy (pierwszy element) 238.      	else if(wybormiejsca==2) UsunWewnatrz(); // usuwamy element w obrebie listy 239.      	else if(wybormiejsca==3) UsunKoncowy();// usuwamy ostatni element listy 240.      } 241. 242.      void DodajLubUsunElementy() 243.      { 244.      	cout << endl << "\n1 - wstawienie elementu\n2 - usuniecie elementu\n\n"; 245.      	int wybor; 246.      	cout << "Twoj wybor: "; 247.      	do 248.      	{ 249.      		cin >> wybor; 250.      		switch(wybor) 251.      		{ 252.      			case 1: 253.      				DodawanieElementu(); 254.      				break; 255.      			case 2: 256.      				UsuwanieElementu(); 257.      				break; 258.      			default: 259.      				cout << "Nie ma takiej opcji\nTwoj wybor: "; 260.      		} 261.      	}while(wybor!=1 && wybor!=2); 262.      } 263. 264.      int main() 265.      { 266.      	UtworzListe(); 267.      	SortujListe(); 268.      	UsunWielokrotnosci5(); 269.      	DodajLubUsunElementy(); 270. 271.      	//DodajNaPoczatku();   // 272.      	//DodajNaPoczatku();   //  273.      	//DodajNaPoczatku();   // 274.      	//UsunKoncowy();       // tak prosto mozemy teraz dzialac na liscie <img src='http://www.forum.tweaks.pl/public/style_emoticons/<#EMO_DIR#>/smile.png' class='bbc_emoticon' alt=':)' /> 275.      	//UsunKoncowy();       // 276.      	//UsunKoncowy();       // 277.      	//UsunKoncowy();       // 278.      	return 0; 279.      }

http://wklej.org/id/227107/

Użytkownik macsch15 edytował ten post 10 12 2009 - 20:06

  • 0

Zobacz więcej tematów z tagiem: język C++



Użytkownicy przeglądający ten temat: 0

0 użytkowników, 0 gości, 0 anonimowych