Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <string.h>
- #include <ctype.h>
- #define DELETED -1
- void quickSort(int**, int); //быстрая сортировка
- void msg(int); //выводит соообщения
- int searchNode(char, char*); //функция считает степень каждого узла
- int searchIndex(int, int*, int); //функция ищет индекс элемента с заданным значением
- void main() {
- char* temp = malloc(100), remNode;
- char *input = malloc(1000), *startPos = input;
- int inputLength;
- int nodeAmount, i = 0, pos = 0, index;
- printf("Enter amount of the nodes:\n");
- scanf("%d", &nodeAmount); getchar();
- msg(0); msg(1);
- //цикл считывания структуры графа в одну строку
- while(1) {
- fgets(temp, 100, stdin);
- if (*temp == '\n') break;
- strcpy(input+pos, temp);
- pos += strlen(temp)-1;
- *(input+pos) = ' ';
- pos++; }
- *(input+pos) = '\0';
- //массив указателей на целые числа, массив целых степеней, степень узла
- int *list[nodeAmount], node[nodeAmount], nodeDegree;
- inputLength = strlen(input);
- //проверка корректности ввода структуры графа
- for (int i=0; i<inputLength-3;) {
- if (!isalpha(input[i])) msg(4);
- if (input[i+1] == ' ') i += 2;
- else if ((input[i+1] != '-') || (input[i+2] != '-')) msg(4);
- else i += 3; }
- //сканирование массива и сохранение степени и индекса узла в одной ячейке
- //например 302 - степень 3, индекс 2 ==> 2-я буква алфавита, B
- for (int i=0; i < nodeAmount; i++) {
- nodeDegree = searchNode(i+'a', startPos);
- node[i] = nodeDegree*100 + i;
- list[i] = &node[i]; } //заполняем массив указателей
- msg(2);
- remNode = getchar(); getchar(); //ловим удаляемую вершину
- //еще раз проходимся по входной строке и помечаем удаляемые вершины маркером
- for (i=0; i<inputLength; i++) {
- if (input[i] == remNode) {
- node[input[i]-'a'] = DELETED;
- if (input[i+1] != ' ')
- node[input[i-3]-'a'] -= 100; //уменьшаем степень смежных вершин
- if (input[i-1] != ' ')
- node[input[i+3]-'a'] -= 100;
- }
- }
- //собственно сама сортировка, сортируются только указатели на числа
- quickSort(list, nodeAmount); printf("\n");
- //вывод отсортированного массива оставшихся вершин
- printf("Node Degree\n");
- for (i=0; i<nodeAmount; i++) {
- index = searchIndex(*list[i], node, nodeAmount);
- if (*list[i] != DELETED)
- printf("%c%6d\n", 'A'+index, *list[i]/100);
- }
- }
- int searchNode(char node, char* input) {
- int j = 0, i = 0;
- while (*(input+i) != '\0') {
- if (*(input+i) == node) {
- if (*(input+i-1) == '-') j++;
- if (*(input+i+1) == '-') j++; }
- i++; }
- return j;
- }
- int searchIndex(int degree, int* array, int length) {
- for (int i=0; i < length; i++)
- if (array[i] == degree) return i;
- return -1;
- }
- void quickSort(int **array, int len) {
- if (len < 2) return;
- int pivot = *array[len/2];
- int i, j;
- for (i = 0, j = len - 1; ; i++, j--) {
- while (*array[i] < pivot) i++;
- while (*array[j] > pivot) j--;
- if (i >= j) break;
- int *temp = array[i];
- array[i] = array[j];
- array[j] = temp; }
- quickSort(array, i);
- quickSort(array+i, len-i);
- }
- void msg(int action) {
- char* message[10] = {
- "Enter your graph structure.\nSeveral lines are supported,",
- " '--' can be used.\nFor instance: a--b--c\nEnter empty line to take a look at the graph.\n",
- "Enter a node you wold like to remove:\n",
- "",
- "Incorrect input.\n"
- };
- printf("%s", message[action]);
- if (action > 3) exit(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment