Mouseartiom

sem5#3

May 22nd, 2017
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 4.58 KB | None | 0 0
  1. //реализицаия АВЛ-дерева
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <stdlib.h>
  5. #define linesPerPage 20
  6.  
  7. typedef struct tnode {
  8.     char* word;
  9.     int ct;
  10.     int pageNum;
  11.     int stringNum;
  12.     unsigned char height;
  13.     struct tnode* left;
  14.     struct tnode* right;
  15. }tnode;
  16.  
  17. char* eatword (FILE*, FILE*, int*);
  18. void man(int);
  19.  
  20. unsigned char treeheight(tnode* node) {
  21.     return node ? node->height : 0; }
  22.  
  23. int bfactor(tnode* node){
  24.     return treeheight(node->right) - treeheight(node->left);}
  25.  
  26. void fixheight(tnode* node) {
  27.     unsigned char leftHeight = treeheight(node->left);
  28.     unsigned char rightHeight = treeheight(node->right);
  29.     node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1; }
  30.  
  31. tnode* rotateRight(tnode* node) {
  32.     tnode* tempNode = node->left;
  33.     node->left = tempNode->right;
  34.     tempNode->right = node;
  35.     fixheight(node);
  36.     fixheight(tempNode);
  37.     return tempNode; }
  38.  
  39. tnode* rotateLeft(tnode* node) {
  40.     tnode* tempNode = node->right;
  41.     node->right = tempNode->left;
  42.     tempNode->left = node;
  43.     fixheight(node);
  44.     fixheight(tempNode);
  45.     return tempNode; }
  46.  
  47. tnode* balance(tnode* node) {
  48.     fixheight(node);
  49.     if (bfactor(node) == 2) {
  50.         if (bfactor(node->right) < 0)
  51.             node->right = rotateRight(node->right);
  52.         return rotateLeft(node); }
  53.     if (bfactor(node) == -2) {
  54.         if (bfactor(node->left) > 0)
  55.             node->left = rotateLeft(node->left);
  56.         return rotateRight(node); }
  57.     return node;
  58. }
  59.  
  60. tnode* addtree(tnode* node, char* word, int str, int page) {
  61.     if (node == NULL) {
  62.         node = (tnode*)malloc(sizeof(tnode));
  63.         node->left = NULL;
  64.         node->right = NULL;
  65.         node->word = (char*)malloc(strlen(word) + 1);
  66.         strcpy(node->word, word);
  67.         node->ct = 1;
  68.         node->stringNum = str;
  69.         node->pageNum = page;
  70.         return node; }
  71.     else {
  72.         int cmp = strcmp(word, node->word);
  73.         if (cmp == 0) {
  74.             node->ct += 1;
  75.             node->stringNum = str;
  76.             node->pageNum = page; }
  77.         else if (cmp < 0)
  78.             node->left = addtree(node->left, word, str, page);
  79.         else
  80.             node->right = addtree(node->right, word, str, page); }
  81.     return balance(node);
  82. }
  83.  
  84. void treeprint(tnode *p) {
  85.     if (p != NULL) {
  86.         treeprint(p->left);
  87.         printf("%-20s%10d%15d%15d\n", p->word, p->ct, p->pageNum, p->stringNum);
  88.         treeprint(p->right); }
  89. }
  90.  
  91. void nodefree(struct tnode* node){
  92.     if (node == NULL) return;
  93.     nodefree(node->left);
  94.     nodefree(node->right);
  95.     free(node->word);
  96.     free(node);
  97.     node = NULL;}
  98.  
  99. void main(int argc, char * argv[]) {
  100.     if (argc != 2) man(2);
  101.     if (strcmp(argv[1], "-?") == 0) man(0);
  102.     tnode* root = NULL;
  103.     char chr, *word;
  104.     int i = 0, str = 1, page = 1;
  105.     FILE *file, *tmpFile;
  106.     tmpFile = tmpfile();
  107.     if ((file = fopen(argv[1], "r")) == NULL) man(3);
  108.     while ((word = eatword(file, tmpFile, &str)) != NULL){
  109.         root = addtree(root, word, str, page);
  110.         if (str >= linesPerPage+1) {
  111.             page++;
  112.             str = 1; }
  113.     }
  114.     fclose(file);
  115.     printf("%d страниц и %d строк в файле \n\n", page, linesPerPage*(page-1)+str);
  116.     printf("Word                    Repeats          Page           Line\n");
  117.     treeprint(root);
  118.     nodefree(root);
  119. }
  120.  
  121. char* eatword(FILE *file, FILE *tmpFile, int *stringCount) {
  122.     char c, *word;
  123.     int i = 0;
  124.     fpos_t pos;
  125.     fgetpos(tmpFile, &pos);
  126.     c = fgetc(file);
  127.     while ((c == '\n') || (c == '\r')) {(*stringCount)++; c = fgetc(file);}
  128.     while (((c >= '0') && (c <= '9')) ||
  129.           ((c >= 'A') && (c <= 'Z')) ||
  130.           ((c >= 'a') && (c <= 'z'))) {
  131.         fputc(c, tmpFile);
  132.         c = fgetc(file);
  133.         i++; }
  134.     if (c == EOF) return NULL;
  135.     fputc('\0', tmpFile);
  136.     fsetpos(tmpFile, &pos);
  137.     word = malloc(i+1);
  138.     fgets(word, i+1, tmpFile);
  139.     fsetpos(tmpFile, &pos);
  140.     if ((c == '\n') || (c == '\r')) (*stringCount)++;
  141.     return word;
  142. }
  143.  
  144. void man(int var) {
  145.     if (var == 0) printf("Программа предназначена для работы с файлами.\nФайл выбирается при помощи аргумента.\nПример: ./a.out file1.txt\nВызов справки -?.\n");
  146.     if (var == 2) printf("Ошибка аргуметов. Укажите файлы при помощи аргумента. -? для справки.\n");
  147.     if (var == 3) printf("Файл не найден.\n");
  148.     exit(0);
  149. }
Advertisement
Add Comment
Please, Sign In to add comment