nht_cntt

struct 2

Mar 19th, 2015
450
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 12.64 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <windows.h>
  5. #include <time.h>
  6.  
  7. struct tdien
  8. {
  9.     char en[30];
  10. };
  11.  
  12.  
  13. void Hoanvi(tdien &a,tdien &b)
  14. {
  15.     tdien t;
  16.     t=a;a=b;b=t;
  17. }
  18.  
  19.  
  20. void LocTA(tdien *td, int &x)
  21. {
  22.     char str[300];
  23.     char* str1,*str2;
  24.     FILE *ds;
  25.     ds = fopen("va.dd","rt");
  26.     while (fgets(str,300,ds)>0)
  27.     {
  28.         str1 = strstr(str,"##");
  29.         if (str1!=NULL)
  30.         {
  31.             str2 = strstr(str1,"|-");
  32.             if (str2!=NULL && strlen(str2)<=17 && strlen(str2)>4)
  33.             {
  34.                 strcpy(td[x].en,str2+3);
  35.                 x++;     
  36.             }          
  37.         }
  38.     }
  39.     fclose(ds);
  40. }
  41.  
  42.  
  43. void TuDientxt(tdien td[], int x)
  44. {
  45.     FILE *tudien;
  46.     LocTA(td,x);
  47.     tudien = fopen("tudien.txt","w");
  48.     for(int i=0;i<x;i++)
  49.     {
  50.         fputs(td[i].en,tudien);
  51.         fflush (tudien);   
  52.     }
  53.     fclose(tudien);
  54. }
  55.  
  56.  
  57. void writetofile2 (FILE *f, tdien b[], int n)
  58. {
  59.     for (int i=0; i<n;i++)
  60.     {
  61.         fputs (b[i].en,f);
  62.         fflush (f);
  63.     }
  64. }
  65.  
  66. void QuickSort (tdien a[], int left, int right)
  67. {
  68.     int i,j;
  69.     char x[30];
  70.     strcpy (x,a[(left+right)/2].en);
  71.     i=left;
  72.     j=right;
  73.     while (i<j)
  74.     {
  75.         while ( strcmp(a[i].en,x) <0 ) i++;
  76.         while (strcmp (a[j].en,x) >0 ) j--;
  77.         if (i<=j)
  78.         {
  79.             Hoanvi(a[i],a[j]);
  80.             i++;
  81.             j--;
  82.         }
  83.  
  84.     }
  85.     if (left <j)
  86.         QuickSort(a,left,j);
  87.     if (i < right)
  88.         QuickSort(a,i,right);
  89. }
  90.  
  91.  
  92. void BubbleSort (tdien a[], int n)
  93. {
  94.  
  95.     int i,j;
  96.     for( i=0; i<n-1;i++)
  97.         for (j=n-1;j>i;j--)
  98.         {
  99.             if ( strcmp (a[j].en,a[j-1].en) < 0 )
  100.                 Hoanvi(a[j],a[j-1]);
  101.         }
  102. }
  103.  
  104.  
  105. void ShakerSort (tdien a[],int n)
  106. {
  107.     int j;
  108.     int left, right,k;
  109.    
  110.     left =0;
  111.     right = n-1;
  112.     k=n-1;
  113.  
  114.  
  115.     while (left < right)
  116.     {
  117.         for (j=right; j>left; j--)
  118.             if ( strcmp (a[j].en,a[j-1].en) < 0)
  119.             {
  120.                 Hoanvi(a[j],a[j-1]);
  121.                 k=j;
  122.             }
  123.         left =k;
  124.         for (j=left; j < right; j++)
  125.             if (strcmp (a[j].en, a[j+1].en) > 0 )
  126.             {
  127.                 Hoanvi(a[j],a[j+1]);
  128.                 k=j;
  129.             }
  130.         right = k;
  131.     }
  132.  
  133. }
  134.  
  135.  
  136. void InterchangeSort (tdien a[], int n)
  137. {
  138.     int i,j;
  139.     for (i=0;i<n;i++)
  140.         for (j=i+1; j<n; j++)
  141.             if ( strcmp (a[j].en,a[i].en) < 0)
  142.                 Hoanvi(a[j],a[i]);
  143. }
  144.  
  145.  
  146. void Heapify(tdien a[], int n, int i)
  147. {
  148.     int Left = 2 * (i + 1) - 1;
  149.     int Right = 2 * (i + 1);
  150.     int Largest;
  151.     if (Left<n && (strcmp(a[Left].en, a[i].en ) > 0))
  152.         Largest = Left;
  153.     else
  154.         Largest = i;
  155.     if (Right<n && (strcmp(a[Right].en, a[Largest].en) > 0))
  156.         Largest = Right;
  157.     if (i != Largest)
  158.     {
  159.         Hoanvi(a[i], a[Largest]);
  160.         Heapify(a, n, Largest);
  161.     }
  162. }
  163.  
  164. void BuildHeap(tdien a[], int n)
  165. {
  166.     for (int i = n / 2 - 1; i >= 0; i--)
  167.         Heapify(a, n, i);
  168. }
  169.  
  170. void HeapSort(tdien a[], int n)
  171. {
  172.     BuildHeap(a, n);
  173.     for (int i = n - 1; i > 0; i--)
  174.     {
  175.         Hoanvi(a[0], a[i]);
  176.         Heapify(a, i, 0);
  177.     }
  178. }
  179.  
  180.  
  181. void BinsertionSort(tdien a[], int n)
  182. {
  183.     int l, r, m, i;
  184.     char s[30];
  185.     for (int i = 1; i < n; i++)
  186.     {
  187.         strcpy(s, a[i].en);
  188.         l = 0;
  189.         r = i - 1;
  190.         while (l <= r)
  191.         {
  192.             m = (l + r) / 2;
  193.             if (strcmp(s, a[m].en) < 0)
  194.             {
  195.                 r = m - 1;
  196.             }
  197.             else
  198.             {
  199.                 l = m + 1;
  200.             }
  201.         }
  202.  
  203.         for (int j = i - 1; j >= l; j--)
  204.         {
  205.             strcpy(a[j + 1].en, a[j].en);
  206.         }
  207.  
  208.         strcpy(a[l].en, s);
  209.  
  210.     }
  211.  
  212.    
  213. }
  214.  
  215.  
  216. void InsertionSort(tdien a[], int n)
  217. {
  218.     int pos;
  219.     char s[30];
  220.     for (int i = 0; i < n; i++)
  221.     {
  222.         strcpy(s, a[i].en);
  223.         pos = i - 1;
  224.         while ((pos >= 0) && (strcmp(a[pos].en, s) > 0))
  225.         {
  226.             strcpy(a[pos + 1].en, a[pos].en);
  227.             pos--;
  228.         }
  229.         strcpy(a[pos + 1].en, s);
  230.  
  231.     }
  232. }
  233.  
  234.  
  235. void SelectionSort(tdien b[], int n)
  236. {
  237.     int min,i,j;
  238.     for (i=0;i< n-1; i++)
  239.     {
  240.         min =i;
  241.         for (j=i+1; j<n; j++)
  242.         {
  243.             if ( strcmp (b[j].en,b[min].en) < 0)
  244.                 min =j;
  245.         }
  246.         Hoanvi(b[i],b[min]);
  247.     }
  248. }
  249.  
  250.  
  251. void ShellSort(tdien a[], int n)
  252. {
  253.     int h[6] = { 13, 8, 5, 3, 2, 1 };
  254.     int k=6;
  255.     int step, i, j, len;
  256.     char s[30];
  257.     for ( step = 0; step < k; step++)
  258.     {
  259.         len = h[step];
  260.         for ( i = len; i < n; i++)
  261.         {
  262.             strcpy(s, a[i].en);
  263.             j = i - len;
  264.             while ( j >= 0 && (strcmp(a[j].en, s) > 0) )
  265.             {
  266.                 strcpy(a[j + len].en, a[j].en);
  267.                 j = j - len;
  268.             }
  269.             strcpy(a[j + len].en, s);
  270.         }
  271.     }
  272. }
  273.  
  274.  
  275. void xuat(tdien a[], int n)
  276. {
  277.     for (int i=0;i<n;i++)
  278.         puts (a[i].en);
  279. }
  280.  
  281.  
  282.  
  283. void luachon (tdien a[],int n)
  284. {
  285.     int s;
  286.     FILE *Sort;
  287.     time_t t;
  288.  
  289.    
  290.     printf("\n Nhap so thu tu thuat toan muon thuc hien: \n 1.InterchangeSort \n 2.BubbleSort \n 3.ShakerSort \n 4.InsertionSort \n 5.BinsertionSort \n 6.ShellSort \n 7.SelectionSort \n 8.QuickSort \n 9.HeapSort \n");
  291.     printf("\n Luu chon: ");
  292.     scanf("%d",&s);
  293.    
  294.     switch (s)
  295.     {
  296.     case 1:
  297.         t=clock();
  298.         InterchangeSort(a,n);
  299.         t=clock() - t;
  300.         Sort = fopen("TuDien_InterchangeSort.txt","w");
  301.         writetofile2(Sort,a,n);
  302.         break;
  303.     case 2:
  304.         t=clock();
  305.         BubbleSort (a,n);
  306.         t=clock() - t;
  307.         Sort = fopen ("TuDien_BubbleSort.txt","w");
  308.         writetofile2 (Sort,a,n);
  309.         break;
  310.     case 3:
  311.         t=clock();
  312.         ShakerSort (a,n);
  313.         t=clock() - t;
  314.         Sort = fopen("TuDien_ShakerSort.txt","w");
  315.         writetofile2 (Sort,a,n);
  316.         break;
  317.     case 4:
  318.         t=clock();
  319.         InsertionSort (a,n);
  320.         t=clock() - t;
  321.         Sort = fopen ("TuDien_InsertionSort.txt","w");
  322.         writetofile2 (Sort,a,n);
  323.         break;
  324.     case 5:
  325.         t=clock();
  326.         BinsertionSort (a,n);
  327.         t=clock() - t;
  328.         Sort = fopen ("TuDien_BinsertionSort.txt","w");
  329.         writetofile2 (Sort,a,n);
  330.         break;
  331.     case 6:
  332.         t=clock();
  333.         ShellSort(a,n);
  334.         t=clock() - t;
  335.         Sort = fopen("TuDien_ShellSort.txt","w");
  336.         writetofile2(Sort,a,n);
  337.         break;
  338.     case 7:
  339.         t=clock();
  340.         SelectionSort(a,n);
  341.         t=clock() - t;
  342.         Sort = fopen ("TuDien_SelectionSort.txt","w");
  343.         writetofile2(Sort,a,n);
  344.         break;
  345.     case 8:
  346.         t=clock();
  347.         QuickSort (a,0,n-1);
  348.         t=clock() - t;
  349.         Sort = fopen ("TuDien_QuickSort.txt","w");
  350.         writetofile2 (Sort,a,n);
  351.         break;
  352.     case 9:
  353.         t=clock();
  354.         HeapSort (a,n);
  355.         t=clock() - t;
  356.         Sort = fopen ("TuDien_HeapSort.txt","w");
  357.         writetofile2 (Sort,a,n);
  358.         break;
  359. //  case 10:
  360. //      t=clock();
  361. //      MergeSort (a,b,0,n-1);
  362. //      t=clock() - t;
  363. //      Sort = fopen ("TuDien_MergeSort.txt","w");
  364. //      writetofile2 (Sort,a,n);
  365. //      break;
  366.     }
  367.  
  368.     fputs ("Thuat toan chay mat:",Sort);
  369.     fprintf(Sort,"%10.5f seconds",((float) t / CLOCKS_PER_SEC ) );
  370.  
  371.     fclose (Sort);
  372. }
  373.  
  374.  
  375.  
  376. void main()
  377. {
  378.     FILE *f;
  379.     int x=0, t=0;
  380.     char a[300];
  381.     tdien *dsta, *td;
  382.     td=new struct tdien[100000];
  383.     TuDientxt(td,x);
  384.     f=fopen("tudien.txt","rt");
  385.     dsta=new struct tdien[100000];
  386.     while (fgets(a,300,f)>0)
  387.     {
  388.         strcpy(dsta[t].en,a);
  389.         t++;
  390.     }
  391.     luachon(dsta,t);
  392.     printf("%d\n",t);
  393.     fclose(f);
  394. }
  395. #include <stdio.h>
  396. #include <string.h>
  397. #include <stdlib.h>
  398. #include <windows.h>
  399. #include <time.h>
  400.  
  401. struct tdien
  402. {
  403.     char en[30];
  404. };
  405.  
  406.  
  407. void Hoanvi(tdien &a,tdien &b)
  408. {
  409.     tdien t;
  410.     t=a;a=b;b=t;
  411. }
  412.  
  413.  
  414. void LocTA(tdien *td, int &x)
  415. {
  416.     char str[300];
  417.     char* str1,*str2;
  418.     FILE *ds;
  419.     ds = fopen("va.dd","rt");
  420.     while (fgets(str,300,ds)>0)
  421.     {
  422.         str1 = strstr(str,"##");
  423.         if (str1!=NULL)
  424.         {
  425.             str2 = strstr(str1,"|-");
  426.             if (str2!=NULL && strlen(str2)<=17 && strlen(str2)>4)
  427.             {
  428.                 strcpy(td[x].en,str2+3);
  429.                 x++;     
  430.             }          
  431.         }
  432.     }
  433.     fclose(ds);
  434. }
  435.  
  436.  
  437. void TuDientxt(tdien td[], int x)
  438. {
  439.     FILE *tudien;
  440.     LocTA(td,x);
  441.     tudien = fopen("tudien.txt","w");
  442.     for(int i=0;i<x;i++)
  443.     {
  444.         fputs(td[i].en,tudien);
  445.         fflush (tudien);   
  446.     }
  447.     fclose(tudien);
  448. }
  449.  
  450.  
  451. void writetofile2 (FILE *f, tdien b[], int n)
  452. {
  453.     for (int i=0; i<n;i++)
  454.     {
  455.         fputs (b[i].en,f);
  456.         fflush (f);
  457.     }
  458. }
  459.  
  460. void QuickSort (tdien a[], int left, int right)
  461. {
  462.     int i,j;
  463.     char x[30];
  464.     strcpy (x,a[(left+right)/2].en);
  465.     i=left;
  466.     j=right;
  467.     while (i<j)
  468.     {
  469.         while ( strcmp(a[i].en,x) <0 ) i++;
  470.         while (strcmp (a[j].en,x) >0 ) j--;
  471.         if (i<=j)
  472.         {
  473.             Hoanvi(a[i],a[j]);
  474.             i++;
  475.             j--;
  476.         }
  477.  
  478.     }
  479.     if (left <j)
  480.         QuickSort(a,left,j);
  481.     if (i < right)
  482.         QuickSort(a,i,right);
  483. }
  484.  
  485.  
  486. void BubbleSort (tdien a[], int n)
  487. {
  488.  
  489.     int i,j;
  490.     for( i=0; i<n-1;i++)
  491.         for (j=n-1;j>i;j--)
  492.         {
  493.             if ( strcmp (a[j].en,a[j-1].en) < 0 )
  494.                 Hoanvi(a[j],a[j-1]);
  495.         }
  496. }
  497.  
  498.  
  499. void ShakerSort (tdien a[],int n)
  500. {
  501.     int j;
  502.     int left, right,k;
  503.    
  504.     left =0;
  505.     right = n-1;
  506.     k=n-1;
  507.  
  508.  
  509.     while (left < right)
  510.     {
  511.         for (j=right; j>left; j--)
  512.             if ( strcmp (a[j].en,a[j-1].en) < 0)
  513.             {
  514.                 Hoanvi(a[j],a[j-1]);
  515.                 k=j;
  516.             }
  517.         left =k;
  518.         for (j=left; j < right; j++)
  519.             if (strcmp (a[j].en, a[j+1].en) > 0 )
  520.             {
  521.                 Hoanvi(a[j],a[j+1]);
  522.                 k=j;
  523.             }
  524.         right = k;
  525.     }
  526.  
  527. }
  528.  
  529.  
  530. void InterchangeSort (tdien a[], int n)
  531. {
  532.     int i,j;
  533.     for (i=0;i<n;i++)
  534.         for (j=i+1; j<n; j++)
  535.             if ( strcmp (a[j].en,a[i].en) < 0)
  536.                 Hoanvi(a[j],a[i]);
  537. }
  538.  
  539.  
  540. void Heapify(tdien a[], int n, int i)
  541. {
  542.     int Left = 2 * (i + 1) - 1;
  543.     int Right = 2 * (i + 1);
  544.     int Largest;
  545.     if (Left<n && (strcmp(a[Left].en, a[i].en ) > 0))
  546.         Largest = Left;
  547.     else
  548.         Largest = i;
  549.     if (Right<n && (strcmp(a[Right].en, a[Largest].en) > 0))
  550.         Largest = Right;
  551.     if (i != Largest)
  552.     {
  553.         Hoanvi(a[i], a[Largest]);
  554.         Heapify(a, n, Largest);
  555.     }
  556. }
  557.  
  558. void BuildHeap(tdien a[], int n)
  559. {
  560.     for (int i = n / 2 - 1; i >= 0; i--)
  561.         Heapify(a, n, i);
  562. }
  563.  
  564. void HeapSort(tdien a[], int n)
  565. {
  566.     BuildHeap(a, n);
  567.     for (int i = n - 1; i > 0; i--)
  568.     {
  569.         Hoanvi(a[0], a[i]);
  570.         Heapify(a, i, 0);
  571.     }
  572. }
  573.  
  574.  
  575. void BinsertionSort(tdien a[], int n)
  576. {
  577.     int l, r, m, i;
  578.     char s[30];
  579.     for (int i = 1; i < n; i++)
  580.     {
  581.         strcpy(s, a[i].en);
  582.         l = 0;
  583.         r = i - 1;
  584.         while (l <= r)
  585.         {
  586.             m = (l + r) / 2;
  587.             if (strcmp(s, a[m].en) < 0)
  588.             {
  589.                 r = m - 1;
  590.             }
  591.             else
  592.             {
  593.                 l = m + 1;
  594.             }
  595.         }
  596.  
  597.         for (int j = i - 1; j >= l; j--)
  598.         {
  599.             strcpy(a[j + 1].en, a[j].en);
  600.         }
  601.  
  602.         strcpy(a[l].en, s);
  603.  
  604.     }
  605.  
  606.    
  607. }
  608.  
  609.  
  610. void InsertionSort(tdien a[], int n)
  611. {
  612.     int pos;
  613.     char s[30];
  614.     for (int i = 0; i < n; i++)
  615.     {
  616.         strcpy(s, a[i].en);
  617.         pos = i - 1;
  618.         while ((pos >= 0) && (strcmp(a[pos].en, s) > 0))
  619.         {
  620.             strcpy(a[pos + 1].en, a[pos].en);
  621.             pos--;
  622.         }
  623.         strcpy(a[pos + 1].en, s);
  624.  
  625.     }
  626. }
  627.  
  628.  
  629. void SelectionSort(tdien b[], int n)
  630. {
  631.     int min,i,j;
  632.     for (i=0;i< n-1; i++)
  633.     {
  634.         min =i;
  635.         for (j=i+1; j<n; j++)
  636.         {
  637.             if ( strcmp (b[j].en,b[min].en) < 0)
  638.                 min =j;
  639.         }
  640.         Hoanvi(b[i],b[min]);
  641.     }
  642. }
  643.  
  644.  
  645. void ShellSort(tdien a[], int n)
  646. {
  647.     int h[6] = { 13, 8, 5, 3, 2, 1 };
  648.     int k=6;
  649.     int step, i, j, len;
  650.     char s[30];
  651.     for ( step = 0; step < k; step++)
  652.     {
  653.         len = h[step];
  654.         for ( i = len; i < n; i++)
  655.         {
  656.             strcpy(s, a[i].en);
  657.             j = i - len;
  658.             while ( j >= 0 && (strcmp(a[j].en, s) > 0) )
  659.             {
  660.                 strcpy(a[j + len].en, a[j].en);
  661.                 j = j - len;
  662.             }
  663.             strcpy(a[j + len].en, s);
  664.         }
  665.     }
  666. }
  667.  
  668.  
  669. void xuat(tdien a[], int n)
  670. {
  671.     for (int i=0;i<n;i++)
  672.         puts (a[i].en);
  673. }
  674.  
  675.  
  676.  
  677. void luachon (tdien a[],int n)
  678. {
  679.     int s;
  680.     FILE *Sort;
  681.     time_t t;
  682.  
  683.    
  684.     printf("\n Nhap so thu tu thuat toan muon thuc hien: \n 1.InterchangeSort \n 2.BubbleSort \n 3.ShakerSort \n 4.InsertionSort \n 5.BinsertionSort \n 6.ShellSort \n 7.SelectionSort \n 8.QuickSort \n 9.HeapSort \n");
  685.     printf("\n Luu chon: ");
  686.     scanf("%d",&s);
  687.    
  688.     switch (s)
  689.     {
  690.     case 1:
  691.         t=clock();
  692.         InterchangeSort(a,n);
  693.         t=clock() - t;
  694.         Sort = fopen("TuDien_InterchangeSort.txt","w");
  695.         writetofile2(Sort,a,n);
  696.         break;
  697.     case 2:
  698.         t=clock();
  699.         BubbleSort (a,n);
  700.         t=clock() - t;
  701.         Sort = fopen ("TuDien_BubbleSort.txt","w");
  702.         writetofile2 (Sort,a,n);
  703.         break;
  704.     case 3:
  705.         t=clock();
  706.         ShakerSort (a,n);
  707.         t=clock() - t;
  708.         Sort = fopen("TuDien_ShakerSort.txt","w");
  709.         writetofile2 (Sort,a,n);
  710.         break;
  711.     case 4:
  712.         t=clock();
  713.         InsertionSort (a,n);
  714.         t=clock() - t;
  715.         Sort = fopen ("TuDien_InsertionSort.txt","w");
  716.         writetofile2 (Sort,a,n);
  717.         break;
  718.     case 5:
  719.         t=clock();
  720.         BinsertionSort (a,n);
  721.         t=clock() - t;
  722.         Sort = fopen ("TuDien_BinsertionSort.txt","w");
  723.         writetofile2 (Sort,a,n);
  724.         break;
  725.     case 6:
  726.         t=clock();
  727.         ShellSort(a,n);
  728.         t=clock() - t;
  729.         Sort = fopen("TuDien_ShellSort.txt","w");
  730.         writetofile2(Sort,a,n);
  731.         break;
  732.     case 7:
  733.         t=clock();
  734.         SelectionSort(a,n);
  735.         t=clock() - t;
  736.         Sort = fopen ("TuDien_SelectionSort.txt","w");
  737.         writetofile2(Sort,a,n);
  738.         break;
  739.     case 8:
  740.         t=clock();
  741.         QuickSort (a,0,n-1);
  742.         t=clock() - t;
  743.         Sort = fopen ("TuDien_QuickSort.txt","w");
  744.         writetofile2 (Sort,a,n);
  745.         break;
  746.     case 9:
  747.         t=clock();
  748.         HeapSort (a,n);
  749.         t=clock() - t;
  750.         Sort = fopen ("TuDien_HeapSort.txt","w");
  751.         writetofile2 (Sort,a,n);
  752.         break;
  753. //  case 10:
  754. //      t=clock();
  755. //      MergeSort (a,b,0,n-1);
  756. //      t=clock() - t;
  757. //      Sort = fopen ("TuDien_MergeSort.txt","w");
  758. //      writetofile2 (Sort,a,n);
  759. //      break;
  760.     }
  761.  
  762.     fputs ("Thuat toan chay mat:",Sort);
  763.     fprintf(Sort,"%10.5f seconds",((float) t / CLOCKS_PER_SEC ) );
  764.  
  765.     fclose (Sort);
  766. }
  767.  
  768.  
  769.  
  770. void main()
  771. {
  772.     FILE *f;
  773.     int x=0, t=0;
  774.     char a[300];
  775.     tdien *dsta, *td;
  776.     td=new struct tdien[100000];
  777.     TuDientxt(td,x);
  778.     f=fopen("tudien.txt","rt");
  779.     dsta=new struct tdien[100000];
  780.     while (fgets(a,300,f)>0)
  781.     {
  782.         strcpy(dsta[t].en,a);
  783.         t++;
  784.     }
  785.     luachon(dsta,t);
  786.     printf("%d\n",t);
  787.     fclose(f);
  788. }
Advertisement
Add Comment
Please, Sign In to add comment