fork(1) download 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>
  4.  
  5.  
  6. struct TNode
  7. {
  8.      int data;
  9.      struct TNode *next;
  10.      struct TNode *prev;  
  11. };
  12.  
  13. struct TList
  14. {
  15.     struct TNode *head;
  16.     struct TNode *tail;   
  17. };
  18.  
  19. void ListInit(struct TList *L)
  20. {
  21.      (*L).head = NULL;
  22.      (*L).tail = NULL;
  23. }
  24.  
  25. int ListIsEmpty(struct TList L)
  26. {
  27.    return (L.head == NULL);  
  28. }
  29.  
  30. void ListDisplayForward(struct TList L)
  31. {
  32.      int counter = 0;
  33.      struct TNode *curr = L.head;
  34.      printf("List (head-->tail): ");
  35.      while(curr != NULL)
  36.      {
  37.          printf("%d -> ",curr->data);       
  38.          curr = curr->next;
  39.          counter++;       
  40.      }
  41.      printf("NULL \n");
  42.      printf("Liczba wezlow listy : %d \n",counter);
  43. }
  44.  
  45. void ListDisplayBackward(struct TList L)
  46. {
  47.      int counter = 0;
  48.      struct TNode *curr = L.tail;
  49.      printf("List (tail-->head): ");
  50.      while(curr != NULL)
  51.      {
  52.          printf("%d -> ",curr->data);       
  53.          curr = curr->prev;
  54.          counter++;       
  55.      }
  56.      printf("NULL \n");
  57.      printf("Liczba wezlow listy : %d \n",counter);
  58. }
  59.  
  60.  
  61. void ListInsert(struct TList *L,int k)
  62. {
  63.     struct TNode *x = (struct TNode *)malloc(sizeof(struct TNode )) ;
  64.     x->data = k;
  65.     x->next = (*L).head;
  66.     if((*L).head != NULL)
  67.        (*L).head->prev = x;
  68.     (*L).head = x;
  69.     x->prev = NULL; 
  70.     if(x->next == NULL)
  71.         (*L).tail = x;      
  72. }
  73.  
  74. void ListDelete(struct TList *L)
  75. {
  76.      struct TNode *x = (*L).head;
  77.      if((*L).head != NULL)
  78.      {
  79.         if((*L).head->next == NULL)     
  80.              (*L).tail = (*L).head->prev;              
  81.          (*L).head = x->next;
  82.          if(x->next != NULL)
  83.             x->next->prev = x->prev;       
  84.          free(x);    
  85.      }
  86. }
  87.  
  88. struct TNode *headdel(struct TNode **first,struct TNode **last)
  89. {
  90.     struct TNode *temp = (*first);
  91.     if((*first) != NULL)
  92.     {
  93.         if((*first)->next == NULL)
  94.             (*last) = NULL;
  95.         else
  96.             (*first)->next->prev = NULL;
  97.         (*first) = (*first)->next;                       
  98.     }
  99.     return temp;  
  100. }
  101.  
  102. void tailins(struct TNode *p,struct TNode **first,struct TNode **last)
  103. {
  104.      p->next = NULL;
  105.      if((*first) == NULL)
  106.      {
  107.          p->prev = NULL;
  108.          (*first) = p;        
  109.      }
  110.      else
  111.      {
  112.          (*last)->next = p;
  113.          p->prev = (*last);
  114.      }
  115.      (*last) = p;
  116. }
  117.  
  118. int ListSplit(struct TList L,struct TList *A,struct TList *B)
  119. {
  120.     int isEmptyB,swapLists;
  121.     struct TNode *currNode,*prevNode;
  122.     swapLists = 1;
  123.     isEmptyB = 1;
  124.     ListInit(A);
  125.     ListInit(B);
  126.     if(L.head != NULL)
  127.     {        
  128.         // Usun wezel z glowy listy L
  129.         //Wstaw wezel za ogon listy A
  130.         currNode = headdel(&L.head,&L.tail);
  131.         tailins(currNode,&(*A).head,&(*A).tail);
  132.         prevNode = currNode;
  133.     }
  134.     while(L.head != NULL)
  135.     {
  136.         // Usun wezel z glowy listy L
  137.         currNode = headdel(&L.head,&L.tail);
  138.         if(prevNode->data > currNode->data)
  139.            swapLists = !swapLists;
  140.         if(swapLists)
  141.         {
  142.            //Wstaw wezel za ogon listy A
  143.            tailins(currNode,&(*A).head,&(*A).tail);
  144.         }
  145.         else
  146.         {
  147.             //Wstaw wezel za ogon listy B
  148.             tailins(currNode,&(*B).head,&(*B).tail);
  149.             isEmptyB = 0;
  150.         }
  151.         prevNode = currNode;                  
  152.     }
  153.     return isEmptyB;
  154. }
  155.  
  156. void ListMerge(struct TList A,struct TList B,struct TList *L)
  157. {
  158.      struct TNode *tmpA = NULL;
  159.      struct TNode *tmpB = NULL;
  160.      struct TNode *poprzedniZtmpA = NULL;
  161.      struct TNode *poprzedniZtmpB = NULL;
  162.      int koniecSeriiWtmpA,koniecSeriiWtmpB;
  163.      ListInit(L);
  164.      if(A.head != NULL)
  165.      {
  166.          // Usun wezel z glowy listy A
  167.          tmpA = headdel(&A.head,&A.tail);                      
  168.      }
  169.      if(B.head != NULL)
  170.      {
  171.          // Usun wezel z glowy listy B
  172.          tmpB = headdel(&B.head,&B.tail);                    
  173.      }
  174.      koniecSeriiWtmpA = (tmpA == NULL);
  175.      koniecSeriiWtmpB = (tmpB == NULL);
  176.      while(A.head != NULL || B.head != NULL)
  177.      {
  178.            while(!koniecSeriiWtmpA && !koniecSeriiWtmpB)
  179.                if(tmpA->data <= tmpB->data)
  180.                {
  181.                   // Wstaw wezel z listy A za ogon listy L
  182.                   tailins(tmpA,&(*L).head,&(*L).tail);
  183.                   poprzedniZtmpA = tmpA;
  184.                  // Usun wezel z glowy listy A
  185.                  tmpA = headdel(&A.head,&A.tail);     
  186.                  if(poprzedniZtmpA == NULL || tmpA == NULL || poprzedniZtmpA->data > tmpA->data)
  187.                       koniecSeriiWtmpA = 1;                                  
  188.                }
  189.                else
  190.                {
  191.                    // Wstaw wezel z listy B za ogon listy L
  192.                    tailins(tmpB,&(*L).head,&(*L).tail);
  193.                    poprzedniZtmpB = tmpB;
  194.                    // Usun wezel z glowy listy B
  195.                    tmpB = headdel(&B.head,&B.tail);
  196.                    if(poprzedniZtmpB == NULL || tmpB == NULL || poprzedniZtmpB->data > tmpB->data)
  197.                       koniecSeriiWtmpB = 1;
  198.                }
  199.             while(!koniecSeriiWtmpA)
  200.             {
  201.                 // Wstaw wezel z listy A za ogon listy L
  202.                 tailins(tmpA,&(*L).head,&(*L).tail);
  203.                  poprzedniZtmpA = tmpA;
  204.                // Usun wezel z glowy listy A
  205.                  tmpA = headdel(&A.head,&A.tail);
  206.                  if(poprzedniZtmpA == NULL || tmpA==NULL || poprzedniZtmpA->data > tmpA->data)
  207.                       koniecSeriiWtmpA = 1;
  208.             }
  209.             while(!koniecSeriiWtmpB)
  210.             {
  211.                 // Wstaw wezel z listy B za ogon listy L
  212.                 tailins(tmpB,&(*L).head,&(*L).tail);
  213.                 poprzedniZtmpB = tmpB;
  214.                // Usun wezel z glowy listy B
  215.                tmpB = headdel(&B.head,&B.tail);
  216.                if(poprzedniZtmpB == NULL || tmpB==NULL || poprzedniZtmpB->data > tmpB->data)
  217.                    koniecSeriiWtmpB = 1;
  218.             }
  219.            koniecSeriiWtmpA = (tmpA == NULL);
  220.            koniecSeriiWtmpB = (tmpB == NULL);
  221.            poprzedniZtmpA = NULL;
  222.            poprzedniZtmpB = NULL;                               
  223.      }
  224. }
  225.  
  226. int main()
  227. {
  228.     int k,n,m;
  229.     struct TList L,L1,L2;
  230.     ListInit(&L);
  231.     srand(time(NULL));
  232.     scanf("%d %d",&n,&m);
  233.     for(k = 1;k <= n;k++)
  234.         ListInsert(&L,rand()%m);
  235.     printf("List L \n");
  236.     ListDisplayForward(L);
  237.     ListDisplayBackward(L);
  238.     ListSplit(L,&L1,&L2);
  239.    printf("List L1 \n");
  240.     ListDisplayForward(L1);
  241.     ListDisplayBackward(L1);
  242.     printf("List L2 \n");
  243.     ListDisplayForward(L2);
  244.     ListDisplayBackward(L2);
  245.     ListMerge(L1,L2,&L);
  246.     printf("List L \n");
  247.     ListDisplayForward(L);
  248.     ListDisplayBackward(L);
  249.     while(!ListIsEmpty(L))
  250.       ListDelete(&L);                   
  251.     system("PAUSE");
  252.     return 0;
  253. }
  254.  
Success #stdin #stdout #stderr 0s 9432KB
comments (?)
stdin 
20 1000
stdout 
List L 
List (head-->tail): 978 -> 701 -> 83 -> 568 -> 731 -> 945 -> 939 -> 339 -> 901 -> 198 -> 38 -> 32 -> 538 -> 941 -> 910 -> 124 -> 646 -> 251 -> 604 -> 685 -> NULL 
Liczba wezlow listy : 20 
List (tail-->head): 685 -> 604 -> 251 -> 646 -> 124 -> 910 -> 941 -> 538 -> 32 -> 38 -> 198 -> 901 -> 339 -> 939 -> 945 -> 731 -> 568 -> 83 -> 701 -> 978 -> NULL 
Liczba wezlow listy : 20 
List L1 
List (head-->tail): 978 -> 83 -> 568 -> 731 -> 945 -> 339 -> 901 -> 38 -> 910 -> 251 -> 604 -> 685 -> NULL 
Liczba wezlow listy : 12 
List (tail-->head): 685 -> 604 -> 251 -> 910 -> 38 -> 901 -> 339 -> 945 -> 731 -> 568 -> 83 -> 978 -> NULL 
Liczba wezlow listy : 12 
List L2 
List (head-->tail): 701 -> 939 -> 198 -> 32 -> 538 -> 941 -> 124 -> 646 -> NULL 
Liczba wezlow listy : 8 
List (tail-->head): 646 -> 124 -> 941 -> 538 -> 32 -> 198 -> 939 -> 701 -> NULL 
Liczba wezlow listy : 8 
List L 
List (head-->tail): 701 -> 939 -> 978 -> 83 -> 198 -> 568 -> 731 -> 945 -> 32 -> 339 -> 538 -> 901 -> 941 -> 38 -> 124 -> 646 -> 910 -> 251 -> 604 -> 685 -> NULL 
Liczba wezlow listy : 20 
List (tail-->head): 685 -> 604 -> 251 -> 910 -> 646 -> 124 -> 38 -> 941 -> 901 -> 538 -> 339 -> 32 -> 945 -> 731 -> 568 -> 198 -> 83 -> 978 -> 939 -> 701 -> NULL 
Liczba wezlow listy : 20
stderr 
sh: 1: PAUSE: not found
https://ideone.com/9blNrM
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!