Mouseartiom

my_flta

Dec 5th, 2017
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.92 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <ctype.h>
  5. #define DELETED -1
  6.  
  7. void quickSort(int**, int); //быстрая сортировка
  8. void msg(int); //выводит соообщения
  9. int searchNode(char, char*); //функция считает степень каждого узла
  10. int searchIndex(int, int*, int); //функция ищет индекс элемента с заданным значением
  11.  
  12. void main() {
  13.     char* temp = malloc(100), remNode;
  14.     char *input = malloc(1000), *startPos = input;
  15.     int inputLength;
  16.     int nodeAmount, i = 0, pos = 0, index;
  17.     printf("Enter amount of the nodes:\n");
  18.     scanf("%d", &nodeAmount); getchar();
  19.     msg(0); msg(1);
  20.  
  21.     //цикл считывания структуры графа в одну строку
  22.     while(1) {
  23.         fgets(temp, 100, stdin);
  24.         if (*temp == '\n') break;
  25.         strcpy(input+pos, temp);
  26.         pos += strlen(temp)-1;
  27.         *(input+pos) = ' ';
  28.         pos++; }
  29.     *(input+pos) = '\0';
  30.  
  31.     //массив указателей на целые числа, массив целых степеней, степень узла
  32.     int *list[nodeAmount], node[nodeAmount], nodeDegree;
  33.     inputLength = strlen(input);
  34.  
  35.     //проверка корректности ввода структуры графа
  36.     for (int i=0; i<inputLength-3;) {
  37.         if (!isalpha(input[i])) msg(4);
  38.         if (input[i+1] == ' ') i += 2;
  39.         else if ((input[i+1] != '-') || (input[i+2] != '-')) msg(4);
  40.         else i += 3; }
  41.  
  42.     //сканирование массива и сохранение степени и индекса узла в одной ячейке
  43.     //например 302 - степень 3, индекс 2 ==> 2-я буква алфавита, B
  44.     for (int i=0; i < nodeAmount; i++) {
  45.         nodeDegree = searchNode(i+'a', startPos);
  46.         node[i] = nodeDegree*100 + i;
  47.         list[i] = &node[i]; } //заполняем массив указателей
  48.        
  49.     msg(2);
  50.     remNode = getchar(); getchar(); //ловим удаляемую вершину
  51.    
  52.     //еще раз проходимся по входной строке и помечаем удаляемые вершины маркером
  53.     for (i=0; i<inputLength; i++) {
  54.         if (input[i] == remNode) {
  55.             node[input[i]-'a'] = DELETED;
  56.             if (input[i+1] != ' ')
  57.                 node[input[i-3]-'a'] -= 100; //уменьшаем степень смежных вершин
  58.             if (input[i-1] != ' ')
  59.                 node[input[i+3]-'a'] -= 100;
  60.         }
  61.     }
  62.  
  63.     //собственно сама сортировка, сортируются только указатели на числа
  64.     quickSort(list, nodeAmount); printf("\n");
  65.    
  66.     //вывод отсортированного массива оставшихся вершин
  67.     printf("Node  Degree\n");
  68.     for (i=0; i<nodeAmount; i++) {
  69.         index = searchIndex(*list[i], node, nodeAmount);
  70.         if (*list[i] != DELETED)
  71.             printf("%c%6d\n", 'A'+index, *list[i]/100);
  72.     }
  73. }
  74.  
  75. int searchNode(char node, char* input) {
  76.     int j = 0, i = 0;
  77.     while (*(input+i) != '\0') {
  78.         if (*(input+i) == node) {
  79.             if (*(input+i-1) == '-') j++;
  80.             if (*(input+i+1) == '-') j++; }
  81.         i++; }
  82.     return j;
  83. }
  84.  
  85. int searchIndex(int degree, int* array, int length) {
  86.     for (int i=0; i < length; i++)
  87.         if (array[i] == degree) return i;
  88.     return -1;
  89. }
  90.  
  91. void quickSort(int **array, int len) {
  92.     if (len < 2) return;
  93.     int pivot = *array[len/2];
  94.     int i, j;
  95.     for (i = 0, j = len - 1; ; i++, j--) {
  96.         while (*array[i] < pivot) i++;
  97.         while (*array[j] > pivot) j--;
  98.         if (i >= j) break;
  99.         int *temp = array[i];
  100.         array[i] = array[j];
  101.         array[j] = temp; }
  102.     quickSort(array, i);
  103.     quickSort(array+i, len-i);
  104. }
  105.  
  106. void msg(int action) {
  107.     char* message[10] = {
  108.         "Enter your graph structure.\nSeveral lines are supported,",
  109.         " '--' can be used.\nFor instance: a--b--c\nEnter empty line to take a look at the graph.\n",
  110.         "Enter a node you wold like to remove:\n",
  111.         "",
  112.         "Incorrect input.\n"
  113.     };
  114.     printf("%s", message[action]);
  115.      if (action > 3) exit(0);
  116. }
Advertisement
Add Comment
Please, Sign In to add comment