Mouseartiom

kuznetsov_flta

Dec 6th, 2017
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.14 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5.  
  6. void shellSort(int**, int); //сортировка шелла
  7. void msg(int); //выводит соообщения
  8. int searchNode(char, char*); //функция считает степень каждого узла
  9.  
  10. void main() {
  11.     char* temp = malloc(100);
  12.     char *input = malloc(1000), *startPos = input;
  13.     int inputLength;
  14.     int nodeAmount, i = 0, pos = 0, index;
  15.     printf("Введите количество вершин:\n");
  16.     scanf("%d", &nodeAmount); getchar();
  17.     msg(0); msg(1);
  18.  
  19.     //цикл считывания структуры графа в одну строку
  20.     while(1) {
  21.         fgets(temp, 100, stdin);
  22.         if (*temp == '\n') break;
  23.         strcpy(input+pos, temp);
  24.         pos += strlen(temp)-1;
  25.         *(input+pos) = ' ';
  26.         pos++; }
  27.     *(input+pos) = '\0';
  28.  
  29.     //массив указателей на целые числа, массив целых степеней, степень узла
  30.     int *list[nodeAmount], node[nodeAmount], nodeDegree;
  31.     inputLength = strlen(input);
  32.  
  33.     //проверка корректности ввода структуры графа
  34.     for (int i=0; i<inputLength-3;) {
  35.         if (!isalpha(input[i])) msg(2);
  36.         if (input[i+1] == ' ') i += 2;
  37.         else if ((input[i+1] != '-') || (input[i+2] != '-')) msg(2);
  38.         else i += 3; }
  39.  
  40.     //сканирование массива и сохранение степени и индекса узла в одной ячейке
  41.     //например 302 - степень 3, индекс 2 ==> 2-я буква алфавита, B
  42.     for (int i=0; i < nodeAmount; i++) {
  43.         nodeDegree = searchNode(i+'a', startPos);
  44.         node[i] = nodeDegree*100 + i;
  45.         list[i] = &node[i]; } //заполняем массив указателей
  46.        
  47.     //собственно сама сортировка, сортируются только указатели на числа
  48.     shellSort(list, nodeAmount);
  49.    
  50.     //вывод отсортированного массива оставшихся вершин
  51.     printf("Вершины отсортированы при помощи сортировки Шелла.\n");
  52.     printf("Вершина  Степень\n");
  53.     for (i=0; i<nodeAmount; i++)
  54.         printf("%c%9d\n", 'A'+*list[i]%100, *list[i]/100);
  55. }
  56.  
  57. int searchNode(char node, char* input) {
  58.     int j = 0, i = 0;
  59.     while (*(input+i) != '\0') {
  60.         if (*(input+i) == node) {
  61.             if (*(input+i-1) == '-') j++;
  62.             if (*(input+i+1) == '-') j++; }
  63.         i++; }
  64.     return j;
  65. }
  66.  
  67. void shellSort (int **a, int n) {
  68.     int h, i, j, t;
  69.     for (h = n; h /= 2;) {
  70.         for (i = h; i < n; i++) {
  71.             t = *a[i];
  72.             for (j = i; j >= h && t < *a[j - h]; j -= h) {
  73.                 *a[j] = *a[j - h];}
  74.             *a[j] = t;
  75.         }
  76.     }
  77. }
  78.  
  79. void msg(int action) {
  80.     char* message[10] = {
  81.         "Введите структуру графа.\nПоддерживается мнгострочный ввод, ",
  82.         "используйте  '--'.\nНапример: a--b--c\nВведите пустую строку для завершения ввода.\n",
  83.         "Неверный ввод.\n"
  84.     };
  85.     printf("%s", message[action]);
  86.      if (action > 1) exit(0);
  87. }
Advertisement
Add Comment
Please, Sign In to add comment