daily pastebin goal
77%
SHARE
TWEET

Untitled

a guest Jul 20th, 2018 53 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Palindrome.cpp: определяет точку входа для консольного приложения.
  2. //
  3.  
  4. #include "stdafx.h"
  5. #include "string.h"
  6. #include "stdio.h"
  7. #include "stdlib.h"
  8. #define SPACE 1                                 /*пробел не должен участвовать в сравнении*/
  9.  
  10. enum State{ NO_CONCUR, PARTIALLY, OVERLAP, ERR};/*нет совпадений, частичное совпадение, полное*/
  11. struct Word{                                    /*структура содержит информацию о "нужности" слова и указатель на само слово*/
  12.     State state;
  13.     char* word1;
  14.     char* word2;
  15. };
  16.  
  17. char** Load();                                  /*Функция читает файл и возвращает массив строк, заканчивающийся NULL*/
  18. State Rev_comp(char* word1, char* word2);       /*Функция сравнивает два слова и выносит вердикт о соответствии*/
  19. char* Compilation(int len,Word* arr);                           /*Функция создет палиндром*/
  20. char* Search(Word word, Word* arr, int len);    /*Функция поиска подходящих слов для палиндрома*/
  21. char* Remove_Space(char*);                      /*Функция просто удаляет из слов пробелы*/
  22.  
  23. char* Remove_Space(char* word){
  24.     int i = 0;
  25.     while(word[i++] != ' ');
  26.     word[i - 1] = '\0';
  27.     return word;
  28. }
  29.  
  30. char* Search(Word word, Word* arr,int len){
  31.     char buffer4straight[32] = { 0 };                       /*буфер слова, для которого ищется пара*/
  32.     char buffer4compare[32] = { 0 };                        /*буфер слова, с которым в итоге будет сравниваться*/
  33.     char buffer4reverse[64] = { 0 };                        /*буфер соединения и разворачивания слов, хранящихся в buffer4straight и temp_bufer*/
  34.     char temp_bufer[32] = { 0 };                            /*буфер для хранения слова, которое будет подставляться к передаваемому*/
  35.     char* complete_string = NULL;                           /*в конце этот указатель укажет на готовую, подобранную строку*/
  36.     for (int i = 0; i < len; i++){
  37.         if (arr[i].state == PARTIALLY){
  38.             /*удаляем пробелы из слова, для которого ищется пара*/
  39.             strcpy(buffer4straight, word.word1);
  40.             Remove_Space(buffer4straight);
  41.             /*удаляем пробелы из слова, с которым мы будем сравнивать*/
  42.             strcpy(buffer4compare, word.word2);
  43.             Remove_Space(buffer4compare);
  44.             /*разворачиваем слово, для которого ищется пара*/
  45.             strrev(buffer4straight);
  46.  
  47.             for (int j = 0; j < len && arr[j].word1 != NULL; j++){                  /*получили после цикла либо составленную часть палиндрома, либо ничего*/
  48.                 /*даже не рассматриваем слова, для которых есть идеальная пара*/
  49.                 if (arr[i].state == OVERLAP)
  50.                     continue;
  51.                 /*копируем в temp_buffer тестовое слово, убирая из него пробел*/
  52.                 strcpy(temp_bufer, arr[j].word1);
  53.                 Remove_Space(temp_bufer);
  54.                 /*копируем в буфер для соединения слов тестовое слово, и для которого ищем пару*/
  55.                 strcpy(buffer4reverse, temp_bufer);
  56.                 strcat(buffer4reverse, buffer4straight);
  57.  
  58.                 /*если строки совпали, то формируем нормальное словосочетание и возвращаем его из функции*/
  59.                 if (strcmp(buffer4reverse, buffer4compare) == 0){
  60.                     complete_string = (char*)calloc(strlen(buffer4reverse + SPACE), sizeof(char));
  61.                     strcpy(complete_string, arr[j].word1);
  62.                     strcat(complete_string,word.word1);
  63.                     return complete_string;
  64.                 }
  65.                
  66.             }
  67.         }
  68.     }
  69.    
  70.     return complete_string;
  71. }
  72.  
  73.  
  74. char* Compilation(int len, Word* arr){
  75.     char** palindrome = (char**)calloc(len + 1,sizeof(char*)); /*+1 для обозначения конца списка*/
  76.     char buffer[256] = { 0 };                       /*занулит весь буфер*/
  77.     int i, j, save_i;                               /*будем знать, на какой позиции закончились чистые палиндромы*/
  78.     for (i = 0, j = 0; i < len; i++, j--){
  79.         /*располагаем идеальные слова с концов палиндрома*/
  80.         if (arr[i].state == OVERLAP){
  81.             palindrome[i] = arr[i].word1;
  82.             palindrome[j] = arr[i].word2;
  83.             save_i = i;
  84.         }
  85.     }
  86.     /*я чувствую, что какая-то хрень с этим save_i, но уже не соображаю)))*/
  87.     /*по идее тут в каждую следующую ячейку палиндрома записывается найденное, сформированное словосочетание*/
  88.     for (i = save_i; i < len; i++){
  89.             if (arr[i].state == PARTIALLY){
  90.                 palindrome[i] = Search(arr[i],arr,len);
  91.             }
  92.         }
  93.     /*ну это просто с запасом, короче писать, чем маллок*/
  94.     static char output[1024];
  95.     output[0] = ' ';
  96.     for (i = 0; i < len; i++)
  97.         /*конкатинируем все непустые ячейки*/
  98.         if (palindrome[i] != NULL)
  99.             strcat(output,palindrome[i]);
  100.         /*возвращаем результат*/
  101.     return output;
  102. }
  103.  
  104. State Rev_comp(char* word1, char* word2){
  105.     if (word1 == NULL || word2 == NULL)
  106.         return ERR;
  107.     int size1 = strlen(word1), \
  108.         size2 = strlen(word2);
  109.     char* matching_place = NULL;
  110.     /*так как пробел всегда в конце слова, то его место заменит \0*/
  111.     /*приходится вычитать SPACE, strlen считает не от 0, а от 1*/
  112.     char* word1_wio_space = (char*)malloc((size1)*sizeof(char));
  113.     char* word2_wio_space = (char*)malloc((size2)*sizeof(char));
  114.  
  115.     strcpy(word1_wio_space, word1);
  116.     word1_wio_space[size1 - SPACE] = '\0';
  117.  
  118.     strcpy(word2_wio_space, word2);
  119.     word2_wio_space[size2 - SPACE] = '\0';
  120.  
  121.     /*ищем в большей строке перевернутую меньшую*/
  122.     /*strstr ищет подстроку, strrev - переворачивает строку. STRREV не стандартная функция!*/
  123.     if (size1 < size2){
  124.         strrev(word1_wio_space);
  125.         matching_place = strstr(word2_wio_space, word1_wio_space);
  126.     }
  127.     else{
  128.         strrev(word2_wio_space);
  129.         matching_place = strstr(word1_wio_space, word2_wio_space);
  130.     }
  131.  
  132.     if (matching_place == NULL)            
  133.         return NO_CONCUR;
  134.     /*если размер строк совпадает и указатель на одну из строк совпадает с поисковым, то слова являются полными палиндромами*/
  135.     else if (matching_place == word1_wio_space || matching_place == word2_wio_space && size1 - size2 == 0)
  136.         return OVERLAP;
  137.     /*иначе совпадают частично*/
  138.     else return PARTIALLY;
  139.  
  140. }
  141.  
  142. char** Load(){
  143.     /*Функция читает файл и возвращает массив строк, заканчивающийся NULL*/
  144.     FILE* file = fopen("1.txt", "r");
  145.  
  146.     if (file == NULL){
  147.         printf("\nError occured while reading\n");
  148.         return NULL;
  149.     }
  150.  
  151.  
  152.     fseek(file, 0, SEEK_END);
  153.     int FileSize = ftell(file);    //узнаем размер файла
  154.     fseek(file, 0, SEEK_SET);
  155.  
  156.     char* txt = (char*)malloc(sizeof(char)*FileSize + 1);
  157.     FileSize = fread(txt, sizeof(char), FileSize, file);    //Присваиваем FileSize количество реально прочитанных байт
  158.     txt[FileSize] = '\0';
  159.  
  160.     void* search_ptr = txt;
  161.     char** strings = (char**)calloc(1000, sizeof(char*));          //выделим побольше памяти, потом ее урежем realloc'ом
  162.     int cnt = 0;
  163.     do{                                    //считаем количество формул
  164.         int length = 0;
  165.         if (memchr(search_ptr, '\n', FileSize*sizeof(char)) != NULL)    //длина формулы
  166.             length = (intptr_t)memchr(search_ptr, '\n', FileSize*sizeof(char)) - (intptr_t)search_ptr + 1;
  167.         else
  168.             length = strlen((char*)search_ptr) + 1;
  169.  
  170.         strings[cnt] = (char*)calloc(length, sizeof(char));
  171.         memcpy(strings[cnt], search_ptr, length - 1);            //копируем -1 символ, чтобы сохранить \0 в конце строки
  172.         cnt++;
  173.         //+ (intptr_t)sizeof(char) отвечает за пропуск \n, а != (void*)1 за обрыв цикла, когда memchr выдал NULL (\n не найден)
  174.     } while ((search_ptr = (void*)((intptr_t)memchr(search_ptr, '\n', FileSize*sizeof(char)) + (intptr_t)sizeof(char))) != (void*)1);
  175.  
  176.     strings = (char**)realloc(strings, (cnt + 1)*sizeof(char*));
  177.     fclose(file);
  178.     return strings;
  179. }
  180.  
  181. void main()
  182. {
  183.     int len;
  184.     int real_len = 0;
  185.     char** strings = Load();
  186.     for (len = 0; strings[len] != NULL; len++);             /*считаем количество слов из файла*/
  187.     Word* check_arr = (Word*)calloc(len*len, sizeof(Word));     /*массив, из которого выкинем ненужные слова*/
  188.  
  189.     State state;
  190.     for (int i = 0,k = 0; i < len; i++){
  191.         for (int j = 0; j < len; j++){
  192.             if (strings[i] == strings[j])       /*одно и то же слово*/
  193.                 continue;
  194.             state = Rev_comp(strings[i], strings[j]);
  195.             if (state == OVERLAP || state == PARTIALLY){   
  196.                 /*если слова удовлетворяют требованиям, то заносим их в check_arr
  197.                   и больше не проверяем*/
  198.  
  199.                 check_arr[k].state = state;
  200.                 check_arr[k].word1 = strings[i];
  201.  
  202.                 check_arr[k].state = state;
  203.                 check_arr[k].word2 = strings[j];
  204.                 k++;
  205.             }
  206.         }
  207.     }
  208.     while (check_arr[real_len++].word1 != NULL);
  209.     char* out = Compilation(len, check_arr);
  210.     while (1);
  211. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top