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>
- void shellSort(int**, int); //сортировка шелла
- void msg(int); //выводит соообщения
- int searchNode(char, char*); //функция считает степень каждого узла
- void main() {
- char* temp = malloc(100);
- char *input = malloc(1000), *startPos = input;
- int inputLength;
- int nodeAmount, i = 0, pos = 0, index;
- printf("Введите количество вершин:\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(2);
- if (input[i+1] == ' ') i += 2;
- else if ((input[i+1] != '-') || (input[i+2] != '-')) msg(2);
- 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]; } //заполняем массив указателей
- //собственно сама сортировка, сортируются только указатели на числа
- shellSort(list, nodeAmount);
- //вывод отсортированного массива оставшихся вершин
- printf("Вершины отсортированы при помощи сортировки Шелла.\n");
- printf("Вершина Степень\n");
- for (i=0; i<nodeAmount; i++)
- printf("%c%9d\n", 'A'+*list[i]%100, *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;
- }
- void shellSort (int **a, int n) {
- int h, i, j, t;
- for (h = n; h /= 2;) {
- for (i = h; i < n; i++) {
- t = *a[i];
- for (j = i; j >= h && t < *a[j - h]; j -= h) {
- *a[j] = *a[j - h];}
- *a[j] = t;
- }
- }
- }
- void msg(int action) {
- char* message[10] = {
- "Введите структуру графа.\nПоддерживается мнгострочный ввод, ",
- "используйте '--'.\nНапример: a--b--c\nВведите пустую строку для завершения ввода.\n",
- "Неверный ввод.\n"
- };
- printf("%s", message[action]);
- if (action > 1) exit(0);
- }
Advertisement
Add Comment
Please, Sign In to add comment