Advertisement
globalbus

Untitled

May 15th, 2011
428
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 10.06 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "list.h"
  4.  
  5. int List_Push(List** p_list, int value)
  6. /*
  7. Co robi: Dodaje element na początek listy
  8. Pobiera: wskaźnik do wskaźnika początku listy, wartość do wstawienia.
  9. */
  10. {
  11.     List *new_element = malloc(sizeof(List));//rezerwuj pamięć
  12.     if(!new_element)
  13.         return 1;//malloc fail
  14.     new_element-> data = value;//dodaj wartość
  15.     new_element->next = *p_list;//ustaw wskaźnik next na początek starej listy
  16.     *p_list=new_element;//ustaw adres przekazanej listy na nowy element
  17.     return 0;
  18. }
  19.  
  20. int List_Add(List** p_list, int value)
  21. /*
  22. Co robi: Dodaje element na koniec listy
  23. Pobiera: wskaźnik do wskaźnika początku listy, wartość do wstawienia.
  24. */
  25. {
  26.     List *element =*p_list; //pobierz adres
  27.     if(element==NULL) //jeśli pusta lista
  28.     {
  29.         List_Push(p_list, value);//wywołaj dodawanie na początek
  30.         return 0;
  31.     }
  32.     while(element->next!=NULL) //szukaj wskazania na koniec (NULL terminator)
  33.     {
  34.         element=element->next;//przeskakuj po liście
  35.     }
  36.     element->next = malloc(sizeof(List));//rezerwuj pamięć i zapisz ten adres zamiast NULL
  37.     if(element->next==NULL)//malloc fail
  38.         return 1;
  39.     element=element->next;//przesuwamy się na nowy, ostatni element
  40.     element->next=NULL;//dodajemy terminator
  41.     element->data=value;//wpisujemy wartość
  42.     return 0;
  43. }
  44. int List_Add_List(List** p_list_p, List** p_list_s, int index)
  45. /*
  46. Co robi: Dodaje listę (p_list_s) pod index innej listy (p_list_p)
  47. Pobiera: wskaźnik do wskaźnika początku listy bazowej, wskaźnik do wskaźnika początku listy wstawianej, index pod który wstawiamy
  48. */
  49. {
  50.     int i=0;
  51.     List *base =*p_list_p; //początek bazowej
  52.     List *put =*p_list_s; //początek wstawianej
  53.     while(put->next!=NULL) //poruszamy się na koniec listy wstawianej
  54.     {
  55.         put =put->next;
  56.     }
  57.     if(index==0) //jeśli wstawiamy na początek
  58.     {
  59.  
  60.         put->next=*p_list_p;//początek listy bazowej staje się ostatnim elementem wstawianej
  61.         *p_list_p=*p_list_s;//nowy początek listy staje się początkiem listy wstawianej
  62.         return 0;
  63.     }
  64.     for(i=0; i<index-1; ++i) //przesuwamy się pod index na liście bazowej
  65.     {
  66.         base=base->next;
  67.     }
  68.     put->next=base->next;//pod końcem listy wstawianej wstawiamy adres elementu zapisanego jako "następny"
  69.     base->next=*p_list_s;//pod "następnym" w liście bazowej o zadanym indeksie wstawiamy adres początku listy wstawianej
  70.     return 0;
  71. }
  72.  
  73. int List_Add_At(List** p_list, int value, int index)
  74. /*
  75. Co robi: Dodaje element w wyznaczonym indeksie
  76. Pobiera: wskaźnik do wskaźnika początku listy, wartość do wstawienia, index
  77. */
  78. {
  79.     int i=0;
  80.     if(index==0)//jeśli wstaw na początek
  81.     {
  82.         List_Push(p_list, value);
  83.         return 0;
  84.     }
  85.     List *element =*p_list;//pobierz adres
  86.     for(i=0; i<index-1; ++i) //przesuń się pod wskazany index
  87.     {
  88.         element=element->next;
  89.     }
  90.     List *next_element=element->next;//zapamiętaj element następujący
  91.     element->next= malloc(sizeof(List));//rezerwuj pamięć i przypisz do wskaźnika poprzedzającego
  92.     if(element==NULL)//malloc fail
  93.         return 1;
  94.     element=element->next;//przesuń się na element wstawiany
  95.     element->next=next_element;//wstaw adres następującego
  96.     element->data=value;//wstaw wartość
  97.     return 0;
  98. }
  99.  
  100. int List_Count(List* p_list)
  101. /*
  102. Co robi: Liczy ilość elementów listy
  103. Pobiera: wskaźnik początku listy
  104. */
  105. {
  106.     int count=0;
  107.     if(p_list==NULL)//jeśli pusta
  108.         return 0;
  109.     List *element =p_list->next;
  110.     while(element!=NULL)//szukaj końca i zliczaj elementy
  111.     {
  112.         element =element->next;
  113.         count++;
  114.     }
  115.     count++;
  116.     return count; //zwróć licznik
  117. }
  118.  
  119. int List_Get(List* p_list, int index)
  120. /*
  121. Co robi: zwraca dane z wyznaczonego indeksu listy
  122. Pobiera: wskaźnik początku listy, index
  123. */
  124. {
  125.     int i=0;
  126.     for(i=0; i<index; ++i) //szukaj indeksu
  127.     {
  128.         p_list=p_list->next;
  129.     }
  130.     return p_list->data;//zwróć wartość
  131. }
  132.  
  133. void List_Print_All(List* p_list)
  134. /*
  135. Co robi: drukuje wszystkie elementy listy
  136. Pobiera: wskaźnik początku listy
  137. */
  138. {
  139.     while(p_list!=NULL)//przesuwaj się do końca
  140.     {
  141.         printf("%d\t",p_list->data);//drukuje dane
  142.         p_list=p_list->next;
  143.     }
  144.     printf("\n");
  145. }
  146.  
  147. int List_Del(List** p_list, int index)
  148. {
  149.     /*
  150.     Co robi: usuwa element spod wybranego indeksu
  151.     Pobiera: wskaźnik do wskaźnika początku listy, index
  152.     */
  153.     int i;
  154.     List *element =*p_list;
  155.     if(index==0)//jeśli kasujemy pierwszy
  156.     {
  157.         *p_list=element->next;//nowy początek listy to teraz element o indeksie 1
  158.         free(element);//uwolnij pamięć spod elementu o indeksie 0
  159.         return 0;
  160.     }
  161.     for(i=0; i<index-1; ++i) //szukaj indeksu
  162.     {
  163.         element=element->next;
  164.     }
  165.     List *previous_element=element;//zapamiętaj poprzedzający element
  166.     element=element->next;//przesuń się o jeden
  167.     List *next_element=element->next;//zapamiętaj następny element
  168.     previous_element->next=next_element;//połącz poprzedzający i następny
  169.     free(element);//uwolnij pamięć spod elementu o zadanym indeksie
  170.     return 0;
  171. }
  172.  
  173. int List_Del_All(List** p_list)
  174. /*
  175. Co robi: usuwa całą listę i ustawia wskaźnik do niej na terminator NULL
  176. Pobiera:  wskaźnik do wskaźnika początku listy
  177. */
  178. {
  179.     List *element =*p_list;//bieżący element
  180.     List *temp;
  181.     while(element!=NULL)//przesuwaj się do końca
  182.     {
  183.         temp=element;//zapamiętaj adres
  184.         element=element->next;//przesuń się na następny
  185.         free(temp);//skasuj spod zapisanego adresu
  186.     }
  187.     *p_list=NULL; //pod listę wpisz NULL
  188.     return 0;
  189. }
  190. int List_Add_ToSorted(List** p_list, int value, int sort_direction)
  191. /*
  192. Co robi: wstawia wartość w odpowiednie miejsce na posortowanej liście
  193. Pobiera:  wskaźnik do wskaźnika początku listy, wartość, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
  194. */
  195. {
  196.     List *element =*p_list;
  197.     if(element==NULL || (element->data>=value)^sort_direction) //jeśli pusta lub wstawianie przed pierwszy element
  198.     {
  199.         List_Push(p_list, value);
  200.         return 0;
  201.     }
  202.     while((element->next) && (element->next->data<value)^sort_direction) //jeśli nie osiągnie końca lub wartość z indeksem jeden do przodu nie będzie spełniała nierówności
  203.         element=element->next;//przesuwanie
  204.     List *next_element=element->next;//zapamiętaj element następujący
  205.     element->next= malloc(sizeof(List));//rezerwuj pamięć i przypisz do wskaźnika poprzedzającego
  206.     if(element==NULL)//malloc fail
  207.         return 1;
  208.     element=element->next;//przesuń się na element wstawiany
  209.     element->next=next_element;//wstaw adres następującego
  210.     element->data=value;//wstaw wartość
  211.     return 0;
  212. }
  213.  
  214. int List_Sort_Selection_Sort(List** p_list, int sort_direction)
  215. /*
  216. Co robi: sortuje listę poprzez proste wybieranie, mało wydajne.
  217. Pobiera:  wskaźnik do wskaźnika początku listy, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
  218. */
  219. {
  220.     List *element =*p_list;//pobierz początek starej listy
  221.     List *new_list=NULL;//nowa lista
  222.     List *temp=NULL;//temp
  223.     while(element->next)//przesuwanie się po liście
  224.     {
  225.         List_Add_ToSorted(&new_list,element->data,sort_direction);//dodaj element ze starej do nowej
  226.         temp=element; //zapamiętaj adres bieżącego elementu
  227.         element=element->next;//przesuń się o jeden do przodu
  228.         free(temp);//uwolnij pamięć z wykorzystanego elementu
  229.     }
  230.     List_Add_ToSorted(&new_list,element->data,sort_direction);//dodaj ostatni element
  231.     free(element);//zwolnij ten element
  232.     *p_list=new_list;//podstaw nową listę w miejsce starej
  233.     return 0;
  234. }
  235. List* List_GetRange(List* p_list, int start, int count)
  236. /*
  237. Co robi: zwraca wybrany zakres jako nową tablicę
  238. Pobiera:  wskaźnik do początku listy, indeks startowy i długość kopiowanego fragmentu
  239. */
  240. {
  241.     int i;
  242.     List *new_list=NULL;
  243.     for(i=0; i<start; ++i)
  244.         p_list=p_list->next; //przesuń się pod adres startu
  245.     for(i=0; i<count; ++i)
  246.     {
  247.         List_Add(&new_list,p_list->data);//kopiuj dane
  248.         p_list=p_list->next;
  249.     }
  250.     return new_list;//zwróc skopiowany fragment
  251. }
  252. int List_Merge(List** p_list_a,List** p_list_b, int sort_direction)
  253. /*
  254. Co robi: łączy dwie listy posortowane w tym samym kierunku i zwraca adres we wskaźniku pierwszej listy
  255. Pobiera:  wskaźnik do wskaźnika początku listy 1, wskaźnik do wskaźnika początku listy 2, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
  256. */
  257. {
  258.     List *new_list=NULL;
  259.     List *a=*p_list_a;
  260.     List *b=*p_list_b;
  261.     while (a&&b)
  262.     {
  263.         if ((a->data < b->data)^sort_direction)
  264.         {
  265.             List_Add(&new_list,a->data);
  266.             a=a->next;
  267.         }
  268.         else
  269.         {
  270.             List_Add(&new_list,b->data);
  271.             b=b->next;
  272.         }
  273.     }
  274.     if(a)
  275.         while(a)
  276.         {
  277.             List_Add(&new_list,a->data);
  278.             a=a->next;
  279.         }
  280.     else
  281.         while(b)
  282.         {
  283.             List_Add(&new_list,b->data);
  284.             b=b->next;
  285.         }
  286.     List_Del_All(p_list_a);
  287.     List_Del_All(p_list_b);
  288.     *p_list_a=new_list;
  289.     return 0;
  290. }
  291. List* List_MergeSort(List** p_list, int sort_direction)
  292. /*
  293. Co robi: Sortuje listy rekurencyjną metodą mergesort
  294. Pobiera:  wskaźnik do wskaźnika początku listy, kierunek sortowania (1 dla malejącego, 0 dla rosnącego)
  295. */
  296. {
  297.     {
  298.         int N, k;
  299.         List * A=NULL;
  300.         List * B=NULL;
  301.         N = List_Count(*p_list);
  302.         if (N > 1)
  303.         {
  304.             k = N / 2;
  305.             A=List_GetRange(*p_list, 0, k);
  306.             B=List_GetRange(*p_list, k, N-k);
  307.             A=List_MergeSort(&A, sort_direction);
  308.             B=List_MergeSort(&B, sort_direction);
  309.             List_Del_All(p_list);
  310.             List_Merge(&A, &B, sort_direction);
  311.             return A;
  312.         }
  313.         else
  314.         {
  315.             return *p_list;
  316.         }
  317.  
  318.     }
  319. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement