ErliPan

Untitled

Jan 6th, 2021
1,010
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <malloc.h>
  3.  
  4. struct list{
  5.     int value;
  6.     struct list *next;
  7. };
  8.  
  9. void init(struct list **ptrptr)
  10. {
  11.     *ptrptr = NULL;
  12. }
  13.  
  14. void suf_insert(struct list **ptrptr, int value)
  15. {
  16.     while (*ptrptr != NULL)
  17.         ptrptr = &((*ptrptr)->next);
  18.     *ptrptr = (struct list *)malloc(sizeof(struct list));
  19.     if(*ptrptr!=NULL){
  20.         (*ptrptr)->value = value;
  21.         (*ptrptr)->next = NULL;
  22.         return;
  23.     }
  24.     else
  25.         return;
  26. }
  27.  
  28. void visit(struct list *ptr)
  29. {
  30.     printf("\nList: ");
  31.     while (ptr != NULL)
  32.     {
  33.         printf("%d ", ptr->value);
  34.         ptr = ptr->next;
  35.     }
  36. }
  37.  
  38. void moveElm(struct list ** ppList, struct list ** elm) {
  39.  
  40.     (*elm)->next = NULL;
  41.     if (*ppList == NULL)
  42.         *ppList = *elm;
  43.     else {
  44.         while ((*ppList)->next != NULL)
  45.             ppList = &(*ppList)->next;
  46.         (*ppList)->next = *elm;
  47.     }
  48.  
  49. }
  50.  
  51. void merge(struct list **ppFirstHalf, struct list **ppSecondHalf) {
  52.  
  53.     struct list ** ppFirstHalfTmp = ppFirstHalf;
  54.     struct list ** ppSecondHalfTmp = ppSecondHalf;
  55.     struct list * returnList = NULL;
  56.  
  57.     while (*ppFirstHalfTmp != NULL || *ppSecondHalfTmp != NULL) {
  58.  
  59.         if (*ppFirstHalfTmp == NULL) {
  60.  
  61.             struct list *tmp = *ppSecondHalfTmp;
  62.             *ppSecondHalfTmp = (*ppSecondHalfTmp)->next;
  63.             moveElm(&returnList, &tmp);
  64.  
  65.         } else if (*ppSecondHalfTmp == NULL) {
  66.  
  67.             struct list *tmp = *ppFirstHalfTmp;
  68.             *ppFirstHalfTmp = (*ppFirstHalfTmp)->next;
  69.             moveElm(&returnList, &tmp);
  70.  
  71.         } else if ((*ppFirstHalfTmp)->value < (*ppSecondHalfTmp)->value) {
  72.  
  73.             struct list *tmp = *ppFirstHalfTmp;
  74.             *ppFirstHalfTmp = (*ppFirstHalfTmp)->next;
  75.             moveElm(&returnList, &tmp);
  76.  
  77.         } else {
  78.  
  79.             struct list *tmp = *ppSecondHalfTmp;
  80.             *ppSecondHalfTmp = (*ppSecondHalfTmp)->next;
  81.             moveElm(&returnList, &tmp);
  82.  
  83.         }
  84.  
  85.     }
  86.  
  87.     *ppFirstHalf = returnList;
  88.  
  89. }
  90.  
  91. void merge_Sort(struct list **ptrptr, int size) {
  92.     if (size > 1) {
  93.  
  94.         int half = size / 2;
  95.         struct list ** pptmp = ptrptr;
  96.         struct list ** ppHalfList;
  97.  
  98.         for (int i = 0;i < half;i++) {
  99.             pptmp = &(*pptmp)->next;
  100.         }
  101.         struct list * tmpEl = malloc(sizeof(struct list));
  102.         tmpEl->next = (*pptmp)->next;
  103.         tmpEl->value = (*pptmp)->value;
  104.         ppHalfList = &tmpEl; //Seconda meta
  105.  
  106.         (*pptmp) = NULL; //ul. el. Prima meta
  107.  
  108.  
  109.         merge_Sort(ptrptr, half);
  110.         merge_Sort(ppHalfList, size - half);
  111.         merge(ptrptr, ppHalfList);
  112.  
  113.     }
  114. }
  115.  
  116. void mergeSort(struct list **ptrptr) {
  117.     int size = 0;
  118.  
  119.     struct list ** pptmp = ptrptr;
  120.  
  121.     while (*pptmp != NULL) {
  122.         pptmp = &(*pptmp)->next;
  123.         size++;
  124.     }
  125.     merge_Sort(ptrptr, size);
  126. }
  127.  
  128. int main() {
  129.     struct list * lista;
  130.     init(&lista);
  131.  
  132.     suf_insert(&lista, 7);
  133.     suf_insert(&lista, 9);
  134.     suf_insert(&lista, 0);
  135.     suf_insert(&lista, 3);
  136.     suf_insert(&lista, 1);
  137.     suf_insert(&lista, 1);
  138.     suf_insert(&lista, 5);
  139.  
  140.     visit(lista);
  141.  
  142.     mergeSort(&lista);
  143.  
  144.     visit(lista);
  145.  
  146.     printf("\nFine");
  147.     return 0;
  148. }
RAW Paste Data