Advertisement
Wojtekd

Selection-Sort na liscie jednokierunkowej

Dec 15th, 2014
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define LIST_LENGTH 15
  6. #define RAND_SPREAD 10
  7.  
  8. // struktura element listy
  9. class CElement
  10. {
  11. public:
  12.     CElement* pNext;
  13.     int nValue;
  14.  
  15.     // globalna glowa:
  16.     static CElement* gpHead;
  17. };
  18. // inicjalizujemy glowe nullem bo nie istnieje jeszcze zaden element.
  19. CElement* CElement::gpHead = NULL;
  20.  
  21. // lista dostępnych funkcji.
  22. void DisplayList(CElement*);
  23. void SelectionSort(CElement*);
  24. CElement* GetMinimum(CElement*);
  25. void SwapValues(CElement*, CElement*);
  26.  
  27. // funkcja main
  28. int main( void )
  29. {
  30.     // wiadomo.
  31.     srand(time(NULL));
  32.  
  33.     // tworzymy 10 elementów listy i łączymy je w całość:
  34.     CElement* pPrev = NULL;
  35.     for (int i = 0; i < LIST_LENGTH; i++)
  36.     {
  37.         // new tworzy nowy obiekt struktury tak jak malloc.
  38.         CElement* pElement = new CElement();
  39.  
  40.         // bezpieczna inicjalizacja.
  41.         pElement->nValue = 0;
  42.         pElement->pNext = NULL;
  43.  
  44.         pElement->nValue = rand() % RAND_SPREAD;
  45.         printf("%d \n", pElement->nValue);
  46.  
  47.         // jak nie istnieje poprzedni to znaczy ze jestemy na samym poczatku (glowa)
  48.         if (!pPrev)
  49.         {
  50.             CElement::gpHead = pElement;
  51.         }
  52.         else
  53.         {
  54.             pPrev->pNext = pElement;
  55.         }
  56.         // zapamietujemy poprzedni element zeby polaczyc go z kolejnym w nastepnej iteracji petli.
  57.         pPrev = pElement;
  58.     }
  59.     // wyświetlamy zawartość listy po jej utworzeniu:
  60.     printf("lista po utworzeniu: \n");
  61.     DisplayList( CElement::gpHead );
  62.  
  63.     // sortujemy
  64.     SelectionSort( CElement::gpHead );
  65.     printf("lista po sortowaniu: \n");
  66.     DisplayList( CElement::gpHead );
  67.  
  68.     return 0;
  69. }
  70. // wyświetla zawartość listy.
  71. void DisplayList( CElement* pElementZero )
  72. {
  73.     CElement* pCurrent = pElementZero;
  74.  
  75.     while (pCurrent != NULL)
  76.     {
  77.         printf("%d   ", pCurrent->nValue);
  78.         pCurrent = pCurrent->pNext;
  79.     }
  80.     printf("\n");
  81. }
  82. // sortowanie przez proste wybieranie
  83. void SelectionSort( CElement* pElementZero )
  84. {
  85.     CElement* pCurrent = pElementZero;
  86.     CElement* pMinimum = NULL;
  87.  
  88.     // przejdz przez kolejne elementy listy.
  89.     while (pCurrent != NULL)
  90.     {
  91.         // i kazdy kolejny swapnij z nowym minimum;
  92.         pMinimum = GetMinimum( pCurrent );
  93.         SwapValues(pCurrent, pMinimum);
  94.         pCurrent = pCurrent->pNext;
  95.     }
  96. }
  97. void SwapValues( CElement* operandA, CElement* operandB )
  98. {
  99.     int temp;
  100.     temp = operandA->nValue;
  101.     operandA->nValue = operandB->nValue;
  102.     operandB->nValue = temp;   
  103. }
  104. // zwraca minimalna wartosc w liscie
  105. CElement* GetMinimum( CElement* pElementZero )
  106. {
  107.     CElement* pCurrent = pElementZero;
  108.     CElement* pMinimum = NULL;
  109.  
  110.     // sprawdz czy lista istnieje
  111.     if (pCurrent)
  112.     {
  113.         pMinimum = pCurrent;
  114.     }
  115.     else
  116.     {
  117.         return NULL;
  118.     }
  119.  
  120.     // a teraz porownujemy z kolejnymi
  121.     while (pCurrent != NULL)
  122.     {
  123.         if (pMinimum->nValue >= pCurrent->nValue)
  124.         {
  125.             // nowe minimum.
  126.             pMinimum = pCurrent;
  127.         }  
  128.         pCurrent = pCurrent->pNext;    
  129.     }
  130.     return pMinimum;
  131. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement